start conventional ssa construction

1 files changed, 137 insertions, 92 deletions

diff --git a/lisc/ssa.c b/lisc/ssa.c
index 5d89b90..8e65f7f 100644
--- a/lisc/ssa.c
+++ b/lisc/ssa.c
@@ -87,114 +87,159 @@ fillrpo(Fn *f)
 	}
 }
 
-static Ref *top, *bot;
-static Ref topdef(Blk *, Fn *, int);
+/* for dominators computation, read
+ * "A Simple, Fast Dominance Algorithm"
+ * by K. Cooper, T. Harvey, and K. Kennedy.
+ */
 
-static Ref
-botdef(Blk *b, Fn *f, int w)
+static Blk *
+inter(Blk *b1, Blk *b2)
 {
-	Ref r;
+	Blk *bt;
 
-	if (!req(bot[b->id], R))
-		return bot[b->id];
-	r = topdef(b, f, w);
-	bot[b->id] = r;
-	return r;
+	if (b1 == 0)
+		return b2;
+	while (b1 != b2) {
+		if (b1->id > b2->id) {
+			bt = b1;
+			b1 = b2;
+			b2 = bt;
+		}
+		while (b1->id < b2->id)
+			b1 = b1->idom;
+	}
+	return b1;
 }
 
-static Ref
-topdef(Blk *b, Fn *f, int w)
+static void
+filldom(Fn *fn)
 {
-	uint i;
-	int t1;
-	Ref r;
-	Phi *p;
+	Blk *b, *d;
+	int ch, n;
+	uint p;
 
-	if (!req(top[b->id], R))
-		return top[b->id];
-	assert(b->npred && "invalid ssa program detected");
-	if (b->npred == 1) {
-		r = botdef(b->pred[0], f, w);
-		top[b->id] = r;
-		return r;
+	for (b=fn->start; b; b=b->link) {
+		b->idom = 0;
+		b->dom = 0;
+		b->dlink = 0;
 	}
-	/* add a phi node */
-	t1 = f->ntmp++;
-	r = TMP(t1);
-	top[b->id] = r;
-	p = alloc(sizeof *p);
-	p->link = b->phi;
-	b->phi = p;
-	p->to = r;
-	p->wide = w;
-	for (i=0; i<b->npred; i++) {
-		p->arg[i] = botdef(b->pred[i], f, w);
-		p->blk[i] = b->pred[i];
+	do {
+		ch = 0;
+		for (n=1; n<fn->nblk; n++) {
+			b = fn->rpo[n];
+			d = 0;
+			for (p=0; p<b->npred; p++)
+				if (b->pred[p]->idom)
+					d = inter(d, b->pred[p]);
+			if (d != b->idom) {
+				ch++;
+				b->idom = d;
+			}
+		}
+	} while (ch);
+	for (b=fn->start; b; b=b->link)
+		if ((d=b->idom)) {
+			assert(d != b);
+			b->dlink = d->dom;
+			d->dom = b;
+		}
+}
+
+static int
+sdom(Blk *b1, Blk *b2)
+{
+	if (b1 == b2)
+		return 0;
+	while (b2->id > b1->id)
+		b2 = b2->idom;
+	return b1 == b2;
+}
+
+static void
+addfron(Blk *a, Blk *b)
+{
+	int n;
+
+	for (n=0; n<a->nfron; n++)
+		if (a->fron[n] == b)
+			return;
+	if (!a->nfron)
+		a->fron = vnew(++a->nfron, sizeof a->fron[0]);
+	else
+		vgrow(&a->fron, ++a->nfron);
+	a->fron[a->nfron-1] = b;
+}
+
+static void
+fillfron(Fn *fn)
+{
+	Blk *a, *b;
+
+	for (b=fn->start; b; b=b->link) {
+		if (b->s1)
+			for (a=b; !sdom(a, b->s1); a=a->link)
+				addfron(a, b->s1);
+		if (b->s2)
+			for (a=b; !sdom(a, b->s2); a=a->link)
+				addfron(a, b->s2);
 	}
-	p->narg = i;
-	return r;
 }
 
-/* restore ssa form for a temporary t
- * predecessors must be available
- */
-void
-ssafix(Fn *f, int t)
+static void
+phiins(Fn *fn)
 {
-	uint n;
-	int t0, t1, w;
-	Ref rt;
+	Bits u;
 	Blk *b;
-	Phi *p;
 	Ins *i;
+	Phi *p;
+	int t, n, w;
+	uint a;
 
-	w = 0;
-	top = alloc(f->nblk * sizeof top[0]);
-	bot = alloc(f->nblk * sizeof bot[0]);
-	rt = TMP(t);
-	t0 = f->ntmp;
-	for (b=f->start; b; b=b->link) {
-		t1 = 0;
-		/* rename defs and some in-blocks uses */
-		for (p=b->phi; p; p=p->link)
-			if (req(p->to, rt)) {
-				t1 = t0++;
-				p->to = TMP(t1);
-				w |= p->wide;
-			}
-		for (i=b->ins; i-b->ins < b->nins; i++) {
-			if (t1) {
-				if (req(i->arg[0], rt))
-					i->arg[0] = TMP(t1);
-				if (req(i->arg[1], rt))
-					i->arg[1] = TMP(t1);
-			}
-			if (req(i->to, rt)) {
-				w |= i->wide;
-				t1 = t0++;
-				i->to = TMP(t1);
-			}
+	for (t=Tmp0; t<fn->ntmp; t++) {
+		u = (Bits){{0}};
+		w = -1;
+		for (b=fn->start; b; b=b->link) {
+			b->visit = 0;
+			for (i=b->ins; i-b->ins < b->nins; i++)
+				if (req(i->to, TMP(t))) {
+					BSET(u, b->id);
+					if (w == -1)
+						w = i->wide;
+					if (w != i->wide)
+						/* uh, oh, warn */
+						;
+				}
 		}
-		if (t1 && req(b->jmp.arg, rt))
-			b->jmp.arg = TMP(t1);
-		top[b->id] = R;
-		bot[b->id] = t1 ? TMP(t1) : R;
-	}
-	for (b=f->start; b; b=b->link) {
-		for (p=b->phi; p; p=p->link)
-			for (n=0; n<p->narg; n++)
-				if (req(p->arg[n], rt))
-					p->arg[n] = botdef(p->blk[n], f, w);
-		for (i=b->ins; i-b->ins < b->nins; i++) {
-			if (req(i->arg[0], rt))
-				i->arg[0] = topdef(b, f, w);
-			if (req(i->arg[1], rt))
-				i->arg[1] = topdef(b, f, w);
+		for (;;) {
+		NextBlk:
+			for (n=0; !BGET(u, n); n++)
+				if (n == fn->nblk)
+					goto NextVar;
+			BCLR(u, n);
+			b = fn->rpo[n];
+			if (b->visit)
+				goto NextBlk;
+			b->visit = 1;
+			for (p=b->phi; p; p=p->link)
+				for (a=0; a<p->narg; a++)
+					if (req(p->arg[a], TMP(t)))
+						goto NextBlk;
+			p = alloc(sizeof *p);
+			p->wide = w;
+			p->to = TMP(t);
+			p->link = b->phi;
+			b->phi = p->link;
+			for (n=0; n<b->nfron; n++)
+				if (b->fron[n]->visit == 0)
+					BSET(u, b->fron[n]->id);
 		}
-		if (req(b->jmp.arg, rt))
-			b->jmp.arg = topdef(b, f, w);
+	NextVar:;
 	}
-	/* add new temporaries */
-	for (t1=f->ntmp; t1<t0; t1++)
-		newtmp(f->tmp[t].name, f);
+}
+
+void
+ssa(Fn *fn)
+{
+	filldom(fn);
+	fillfron(fn);
 }