2 files changed, 144 insertions, 0 deletions
diff --git a/lisc/lisc.h b/lisc/lisc.h
new file mode 100644
index 0000000..dbe4d63
--- /dev/null
+++ b/lisc/lisc.h
@@ -0,0 +1,62 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+enum {
+	R = -1,        /* Invalid reference. */
+	Temp0 = 32,    /* First temporary, below are machine registers. */
+	MaxPreds = 16, /* Maximum number of predecessors for a block. */
+	MaxBlks = 128,
+	MaxInss = 128,
+	MaxPhis = 128,
+};
+
+typedef int Ref;
+typedef struct Ins Ins;
+typedef struct Phi Phi;
+typedef struct Blk Blk;
+typedef enum Op Op;
+typedef enum Jmp Jmp;
+
+enum Op {
+	ONop,
+	OAdd,
+	OSub,
+	OSDiv,
+	OMod,
+	OParam,
+	OCall,
+
+	/* x86 instructions (reserved) */
+	XDiv,
+};
+
+enum Jmp {
+	JRet,
+	JJmp,
+	JCnd,
+};
+
+struct Ins {
+	Op op;
+	Ref res;
+	Ref arg0, arg1;
+};
+
+struct Phi {
+	Ref res;
+	int na;
+	Ref args[MaxPreds];
+};
+
+struct Blk {
+	int np;
+	int ni;
+	Phi *ps;
+	Ins *is;
+	struct {
+		Jmp ty;
+		Ref arg;
+	} jmp;
+	int suc0, suc1;
+	int dpth;
+};
diff --git a/lisc/lo.c b/lisc/lo.c
new file mode 100644
index 0000000..931385e
--- /dev/null
+++ b/lisc/lo.c
@@ -0,0 +1,82 @@
+/*% clang -Wall -o # %
+ */
+#include "lisc.h"
+
+
+static void
+rporec(int *rpo, int *cnt, Blk *bs, int b)
+{
+	if (rpo[b] >= 0)
+		return;
+	if (bs[b].suc1 >= 0)
+		rporec(rpo, cnt, bs, bs[b].suc1);
+	if (bs[b].suc0 >= 0)
+		rporec(rpo, cnt, bs, bs[b].suc0);
+	rpo[b] = --*cnt;
+}
+
+int
+dorpo(Blk *bs, int nb)
+{
+	static int rpo[MaxBlks];
+	Blk t;
+	int cnt, i, j;
+
+	for (i=0; i<nb; i++)
+		rpo[i] = -1;
+	cnt = nb;
+	rporec(rpo, &cnt, bs, 0);
+	if (cnt) {
+		for (i=0; i<nb; i++)
+			rpo[i] -= cnt;
+	}
+	for (i=0; i<nb; i++) {
+		if (bs[i].suc0 >= 0)
+			bs[i].suc0 = rpo[bs[i].suc0];
+		if (bs[i].suc1 >= 0)
+			bs[i].suc1 = rpo[bs[i].suc1];
+	}
+/*
+  A little messy, the idea is that we have an
+  array permutation inside the rpo array, now we
+  apply it to the bs array with a linear algorithm
+  using swaps.
+*/
+	for (i=0; i<nb; i++)
+		while (rpo[i] >= 0 && rpo[i] != i) {
+			j = rpo[i];
+			rpo[i] = rpo[j];
+			rpo[j] = j;
+			t = bs[i];
+			bs[i] = bs[j];
+			bs[j] = t;
+		}
+	return nb - cnt;
+}
+
+
+#define LEN(a) sizeof a / sizeof a[0]
+
+Blk rpocond[] = {
+	{ .suc0 =  2, .suc1 =  3 },
+	{ .suc0 = -1, .suc1 = -1 },
+	{ .suc0 =  1, .suc1 = -1 },
+	{ .suc0 = -1, .suc1 =  1 },
+	{ .suc0 = 12, .suc1 = -1 }, /* dead */
+};
+
+int
+main()
+{
+	Blk *bs;
+	int i, nb;
+
+	bs = rpocond;
+	nb = LEN(rpocond);
+	nb = dorpo(bs, nb);
+	for (i=0; i<nb; i++) {
+		printf("%02d -> [%02d, %02d]\n", i,
+			bs[i].suc0, bs[i].suc1);
+	}
+	return 0;
+}