qbe

commit 0f0ee0466e52155888ec3052c24145d036a27bea
parent 7be3711bb6c53eac89ca475a471dac629ce2c402
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date:   Tue, 21 Jul 2015 17:08:48 -0400

rework liveness to compute reg pressure

Diffstat:
M
lisc/lisc.h
 | 
4
+++-
M
lisc/live.c
 | 
77
+++++++++++++++++++++++++++++++++++++++++++----------------------------------
M
lisc/main.c
 | 
5
+++--

3 files changed, 49 insertions(+), 37 deletions(-)
diff --git a/lisc/lisc.h b/lisc/lisc.h
@@ -130,7 +130,8 @@ struct Blk {
 
 	Blk **pred;
 	uint npred;
-	Bits in, out;
+	Bits in, out, gen;
+	int nlive;
 	int loop;
 	char name[NString];
 	int id;
@@ -175,5 +176,6 @@ void filllive(Fn *);
 void isel(Fn *);
 
 /* spill.c */
+int bcnt(Bits *);
 void fillcost(Fn *);
 void spill(Fn *);
diff --git a/lisc/live.c b/lisc/live.c
@@ -1,10 +1,14 @@
 #include "lisc.h"
 
-static inline void
-bset(Bits *b, Ref r)
+static void
+bset(Ref r, Blk *b, int *nlv)
 {
 	if (rtype(r) == RSym)
-		BSET(*b, r.val);
+	if (!BGET(b->in, r.val)) {
+		++*nlv;
+		BSET(b->in, r.val);
+		BSET(b->gen, r.val);
+	}
 }
 
 /* liveness analysis
@@ -16,51 +20,56 @@ filllive(Fn *f)
 	Blk *b;
 	Ins *i;
 	Phi *p;
-	int z, n, chg;
+	int z, n, chg, nlv;
 	uint a;
-	Bits *kill, *use, *k, *u, bt;
+	Bits tb;
 
 	assert(f->ntmp <= NBit*BITS);
-	kill = alloc(f->nblk * sizeof kill[0]);
-	use = alloc(f->nblk * sizeof use[0]);
-	for (b=f->start; b; b=b->link) {
-		memset(&b->in, 0, sizeof(Bits));
-		memset(&b->out, 0, sizeof(Bits));
-	}
 	for (b=f->start; b; b=b->link) {
-		k = &kill[b->id];
-		u = &use[b->id];
-		for (p=b->phi; p; p=p->link) {
-			for (a=0; a<p->narg; a++)
-				bset(&p->blk[a]->out, p->arg[a]);
-			bset(k, p->to);
-		}
-		for (i=b->ins; i-b->ins < b->nins; i++) {
-			bset(k, i->to);
-			bset(u, i->arg[0]);
-			bset(u, i->arg[1]);
-		}
-		bset(u, b->jmp.arg);
+		b->in = (Bits){{0}};
+		b->out = (Bits){{0}};
+		b->gen = (Bits){{0}};
+		b->nlive = 0;
 	}
-Again:
-	chg = 0;
+	chg = 1;
+	if (0)
+	Again:
+		chg = 0;
 	for (n=f->nblk-1; n>=0; n--) {
 		b = f->rpo[n];
-		bt = b->out;
+
+		tb = 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];
+		chg |= memcmp(&b->out, &tb, sizeof(Bits)) != 0;
+
+		b->in = b->out;
+		nlv = bcnt(&b->in);
+		bset(b->jmp.arg, b, &nlv);
+		b->nlive = nlv;
+		for (i=&b->ins[b->nins]; i!=b->ins;) {
+			i--;
+			if (!req(i->to, R)) {
+				nlv -= BGET(b->in, i->to.val);
+				BCLR(b->in, i->to.val);
+			}
+			bset(i->arg[0], b, &nlv);
+			bset(i->arg[1], b, &nlv);
+			if (nlv > b->nlive)
+				b->nlive = nlv;
+		}
+
+		for (p=b->phi; p; p=p->link) {
+			BCLR(b->in, p->to.val);
+			for (a=0; a<p->narg; a++)
+				if (rtype(p->arg[a]) == RSym)
+					BSET(p->blk[a]->out, p->arg[a].val);
+		}
 	}
 	if (chg)
 		goto Again;
-	free(kill);
-	free(use);
 }
diff --git a/lisc/main.c b/lisc/main.c
@@ -59,12 +59,13 @@ main(int ac, char *av[])
 		filllive(fn);
 		for (b=fn->start; b; b=b->link) {
 			printf("> Block %s\n", b->name);
-			printf("\t in: [");
+			printf("\t in:   [");
 			dumprset(&b->in, fn);
 			printf(" ]\n");
-			printf("\tout: [");
+			printf("\tout:   [");
 			dumprset(&b->out, fn);
 			printf(" ]\n");
+			printf("\tnlive: %d\n", b->nlive);
 		}
 		pr = 0;
 		break;