add rpo test and some liveness code

6 files changed, 146 insertions, 14 deletions

diff --git a/lisc/Makefile b/lisc/Makefile
index 381452d..fcf91a5 100644
--- a/lisc/Makefile
+++ b/lisc/Makefile
@@ -1,5 +1,5 @@
 BIN = lisc
-OBJ = parse.o ssa.o
+OBJ = parse.o ssa.o live.o
 
 CFLAGS = -Wall -Wextra -std=c99 -g
 
diff --git a/lisc/lisc.h b/lisc/lisc.h
index 2f6ada4..0ed9411 100644
--- a/lisc/lisc.h
+++ b/lisc/lisc.h
@@ -1,41 +1,56 @@
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 typedef unsigned int uint;
 typedef unsigned short ushort;
 typedef unsigned char uchar;
+typedef unsigned long long ullong;
 
 enum {
 	NReg    = 32,
 	Tmp0    = NReg+1,
+
 	NString = 32,
 	NPred   = 15,
 	NBlk    = 128,
 	NIns    = 256,
+
+	BITS    = 4,
+	NBit    = 8 * sizeof(ullong),
 };
 
+typedef struct Bits Bits;
+typedef struct Ref Ref;
 typedef struct OpDesc OpDesc;
 typedef struct Ins Ins;
 typedef struct Phi Phi;
 typedef struct Blk Blk;
 typedef struct Sym Sym;
 typedef struct Fn Fn;
-typedef struct Ref Ref;
+
+struct Bits {
+	ullong t[BITS];
+};
+
+#define BGET(b, n) (1&((b).t[n/NBit]>>(n%NBit)))
+#define BSET(b, n) ((b).t[n/NBit] |= (ullong)1<<(n%NBit))
+#define BCLR(b, n) ((b).t[n/NBit] &= ~((ullong)1<<(n%NBit)))
 
 struct Ref {
 	ushort type:1;
 	ushort val:15;
 };
 
+#define R (Ref){0, 0} // Invalid reference
+
 static inline int
 req(Ref a, Ref b)
 {
 	return a.type == b.type && a.val == b.val;
 }
 
-#define R (Ref){0, 0} // Invalid reference
-
 enum {
 	RSym = 0,
 	RConst = 1,
@@ -46,7 +61,7 @@ enum {
 #define CONST(x) (Ref){RConst, x}
 
 enum {
-	OXXX,
+	OXXX = 0,
 	OAdd,
 	OSub,
 	ODiv,
@@ -58,12 +73,6 @@ enum {
 	OLast
 };
 
-struct OpDesc {
-	int arity;
-	int commut:1;
-	char *name;
-};
-
 enum {
 	JXXX,
 	JRet,
@@ -71,6 +80,12 @@ enum {
 	JJez,
 };
 
+struct OpDesc {
+	int arity;
+	int commut:1;
+	char *name;
+};
+
 struct Ins {
 	short op;
 	Ref to;
@@ -99,6 +114,7 @@ struct Blk {
 
 	Blk **pred;
 	uint npred;
+	Bits in, out;
 	char name[NString];
 	int id;
 };
@@ -124,7 +140,6 @@ struct Fn {
 
 /* parse.c */
 extern OpDesc opdesc[];
-
 void *alloc(size_t);
 Fn *parsefn(FILE *);
 void printfn(Fn *, FILE *);
@@ -133,3 +148,6 @@ void printfn(Fn *, FILE *);
 void fillpreds(Fn *);
 void fillrpo(Fn *);
 void ssafix(Fn *, int);
+
+/* live.c */
+void filllive(Fn *);
diff --git a/lisc/live.c b/lisc/live.c
new file mode 100644
index 0000000..82acae9
--- /dev/null
+++ b/lisc/live.c
@@ -0,0 +1,59 @@
+#include "lisc.h"
+
+/* liveness analysis
+ * requires rpo computation
+ */
+void
+filllive(Fn *f)
+{
+	Blk *b;
+	Ins *i;
+	Phi *p;
+	int z, n, chg;
+	Bits *kill, *use, *k, *u, bt;
+
+	assert(f->ntmp <= NBit*BITS);
+	kill = alloc(f->ntmp * sizeof kill[0]);
+	use = alloc(f->ntmp * sizeof use[0]);
+	for (b=f->start; b; b=b->link) {
+		k = &kill[b->id];
+		u = &use[b->id];
+		for (p=b->phi; p; p=p->link)
+			BSET(*k, p->to.val);
+		for (i=b->ins; i-b->ins < b->nins; i++) {
+			if (!req(i->to, R))
+				BSET(*k, i->to.val);
+			if (!req(i->arg[0], R))
+				BSET(*u, i->arg[0].val);
+			if (!req(i->arg[1], R))
+				BSET(*u, i->arg[1].val);
+		}
+		if (!req(b->jmp.arg, R))
+			BSET(*u, b->jmp.arg.val);
+		for (z=0; z<BITS; z++)
+			u->t[z] &= ~k->t[z];
+		memset(&b->in, 0, sizeof(Bits));
+		memset(&b->out, 0, sizeof(Bits));
+	}
+Again:
+	chg = 0;
+	for (n=f->nblk-1; n>=0; n--) {
+		b = f->rpo[n];
+		bt = b->out;
+		if (b->s1)
+			for (z=0; z<BITS; z++)
+				b->out.t[z] |= b->s1->in.t[z];
+		if (b->s2)
+			for (z=0; z<BITS; z++)
+				b->out.t[z] |= b->s2->in.t[z];
+		chg |= memcmp(&b->out, &bt, sizeof(Bits)) != 0;
+		k = &kill[n];
+		u = &use[n];
+		for (z=0; z<BITS; z++)
+			b->in.t[z] = (b->out.t[z]|u->t[z]) & ~k->t[z];
+	}
+	if (chg)
+		goto Again;
+	free(kill);
+	free(use);
+}
diff --git a/lisc/parse.c b/lisc/parse.c
index 3c00144..d8e2095 100644
--- a/lisc/parse.c
+++ b/lisc/parse.c
@@ -534,11 +534,21 @@ printfn(Fn *fn, FILE *f)
 }
 
 
+static void
+dumprset(Bits *b, Fn *fn)
+{
+	int t;
+
+	for (t=Tmp0; t<fn->ntmp; t++)
+		if (BSET(*b, t))
+			fprintf(stderr, " %s", fn->sym[t].name);
+	fprintf(stderr, "\n");
+}
+
 int
 main(int ac, char *av[])
 {
 	int opt;
-	int tx, ntmp;
 	Fn *fn;
 
 	fn = parsefn(stdin);
@@ -548,7 +558,9 @@ main(int ac, char *av[])
 		opt = av[1][1];
 
 	switch (opt) {
-	case 'f':
+	case 'f': {
+		int tx, ntmp;
+
 		fprintf(stderr, "[test ssafix:");
 		fillpreds(fn);
 		for (ntmp=fn->ntmp, tx=Tmp0; tx<ntmp; tx++) {
@@ -558,6 +570,38 @@ main(int ac, char *av[])
 		fprintf(stderr, "]\n");
 		break;
 	}
+	case 'r': {
+		int n;
+
+		fprintf(stderr, "[test rpo]\n");
+		fillrpo(fn);
+		assert(fn->rpo[0] == fn->start);
+		for (n=0;; n++)
+			if (n == fn->nblk-1) {
+				fn->rpo[n]->link = 0;
+				break;
+			} else
+				fn->rpo[n]->link = fn->rpo[n+1];
+		break;
+	}
+	case 'l': {
+		Blk *b;
+
+		fprintf(stderr, "[test liveness]\n");
+		fillrpo(fn);
+		filllive(fn);
+		for (b=fn->start; b; b=b->link) {
+			fprintf(stderr, "> Block %s\n", b->name);
+			fprintf(stderr, "\tlive in :");
+			dumprset(&b->in, fn);
+			fprintf(stderr, "\tlive out:");
+			dumprset(&b->out, fn);
+		}
+		break;
+	}
+	default:
+		break;
+	}
 
 	printfn(fn, stdout);
 	return 0;
diff --git a/lisc/ssa.c b/lisc/ssa.c
index c08d6b1..c4710f6 100644
--- a/lisc/ssa.c
+++ b/lisc/ssa.c
@@ -46,6 +46,7 @@ rporec(Blk *b, int x)
 {
 	if (b->id >= 0)
 		return x;
+	b->id = 1;
 	if (b->s1)
 		x = rporec(b->s1, x);
 	if (b->s2)
diff --git a/lisc/test/rpo.ssa b/lisc/test/rpo.ssa
new file mode 100644
index 0000000..44d0056
--- /dev/null
+++ b/lisc/test/rpo.ssa
@@ -0,0 +1,10 @@
+@start
+	jmp @foo
+@baz
+	jez 1, @end, @foo
+@bar
+	jmp @end
+@foo
+	jez 0, @bar, @baz
+@end
+	ret