From d43ebe8f58983da12ba9c0e53c633029335b8619 Mon Sep 17 00:00:00 2001
From: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Tue, 27 Oct 2015 14:21:33 -0400
Subject: break phi-classes following interferences

---
 lisc/live.c | 47 ++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 36 insertions(+), 11 deletions(-)

(limited to 'lisc')

diff --git a/lisc/live.c b/lisc/live.c
index ddb1e31..57e7533 100644
--- a/lisc/live.c
+++ b/lisc/live.c
@@ -19,15 +19,31 @@ liveon(Blk *b, Blk *s)
 }
 
 static void
-bset(Ref r, Blk *b, int *nlv)
+bset(Ref r, Blk *b, int *nlv, short *phi, Tmp *tmp)
 {
+	int t, t1, t2;
+
 	if (rtype(r) != RTmp)
 		return;
-	BSET(b->gen, r.val);
-	if (!BGET(b->in, r.val)) {
+	t1 = r.val;
+	BSET(b->gen, t1);
+	if (!BGET(b->in, t1)) {
 		++*nlv;
-		BSET(b->in, r.val);
+		BSET(b->in, t1);
+	}
+	/* detect temporaries in the same
+	 * phi-class that interfere and
+	 * separate them
+	 */
+	t = phirepr(tmp, t1);
+	t2 = phi[t];
+	if (t2 && t2 != t1) {
+		if (tmp[t1].phi != t1)
+			tmp[t1].phi = t1;
+		else
+			tmp[t2].phi = t2;
 	}
+	phi[t] = t1;
 }
 
 /* liveness analysis
@@ -38,11 +54,13 @@ filllive(Fn *f)
 {
 	Blk *b;
 	Ins *i;
-	int z, m, n, chg, nlv;
+	int t, z, m, n, chg, nlv;
+	short *phi;
 	Bits u, v;
 	Mem *ma;
 
 	assert(f->ntmp <= NBit*BITS);
+	phi = emalloc(f->ntmp * sizeof phi[0]);
 	for (b=f->start; b; b=b->link) {
 		b->in = (Bits){{0}};
 		b->out = (Bits){{0}};
@@ -66,9 +84,13 @@ Again:
 		}
 		chg |= memcmp(&b->out, &u, sizeof(Bits));
 
-		b->in = b->out;
-		nlv = bcnt(&b->in);
-		bset(b->jmp.arg, b, &nlv);
+		memset(phi, 0, f->ntmp * sizeof phi[0]);
+		b->in = (Bits){{0}};
+		nlv = 0;
+		for (t=0; t<f->ntmp; t++)
+			if (BGET(b->out, t))
+				bset(TMP(t), b, &nlv, phi, f->tmp);
+		bset(b->jmp.arg, b, &nlv, phi, f->tmp);
 		b->nlive = nlv;
 		for (i=&b->ins[b->nins]; i!=b->ins;) {
 			if ((--i)->op == OCall) {
@@ -83,16 +105,18 @@ Again:
 				assert(rtype(i->to) == RTmp);
 				nlv -= BGET(b->in, i->to.val);
 				BCLR(b->in, i->to.val);
+				t = phirepr(f->tmp, i->to.val);
+				phi[t] = 0;
 			}
 			for (m=0; m<2; m++)
 				switch (rtype(i->arg[m])) {
 				case RAMem:
 					ma = &f->mem[i->arg[m].val & AMask];
-					bset(ma->base, b, &nlv);
-					bset(ma->index, b, &nlv);
+					bset(ma->base, b, &nlv, phi, f->tmp);
+					bset(ma->index, b, &nlv, phi, f->tmp);
 					break;
 				default:
-					bset(i->arg[m], b, &nlv);
+					bset(i->arg[m], b, &nlv, phi, f->tmp);
 					break;
 				}
 			if (nlv > b->nlive)
@@ -103,6 +127,7 @@ Again:
 		chg = 0;
 		goto Again;
 	}
+	free(phi);
 
 	if (debug['L']) {
 		fprintf(stderr, "\n> Liveness analysis:\n");
-- 
cgit 1.4.1