qbe

commit 844b97cf37e245a538b5b5946ae5c765d2a7733c
parent a9bc0541b5e69f902758210eb3bfa275a53a07e0
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date:   Thu,  8 Dec 2016 22:15:46 -0500

use a queue for copy elimination

Diffstat:
M
copy.c
 | 
32
+++++++++++++++++---------------

1 file changed, 17 insertions(+), 15 deletions(-)
diff --git a/copy.c b/copy.c
@@ -16,7 +16,7 @@ copyof(Ref r, Ref *cp)
 }
 
 static void
-update(Ref r, Ref rcp, Ref *cp, RList **w)
+update(Ref r, Ref rcp, Ref *cp, RList ***pw)
 {
 	RList *l;
 
@@ -24,13 +24,14 @@ update(Ref r, Ref rcp, Ref *cp, RList **w)
 		cp[r.val] = rcp;
 		l = emalloc(sizeof *l);
 		l->t = r.val;
-		l->l = *w;
-		*w = l;
+		l->l = 0;
+		**pw = l;
+		*pw = &l->l;
 	}
 }
 
 static void
-visitphi(Phi *p, Ref *cp, RList **w)
+visitphi(Phi *p, Ref *cp, RList ***pw)
 {
 	uint a;
 	Ref r, r1;
@@ -47,20 +48,20 @@ visitphi(Phi *p, Ref *cp, RList **w)
 			break;
 		}
 	}
-	update(p->to, r, cp, w);
+	update(p->to, r, cp, pw);
 }
 
 static void
-visitins(Ins *i, Ref *cp, RList **w)
+visitins(Ins *i, Ref *cp, RList ***pw)
 {
 	Ref r;
 
 	if (i->op == Ocopy) {
 		r = copyof(i->arg[0], cp);
-		update(i->to, r, cp, w);
+		update(i->to, r, cp, pw);
 	} else if (!req(i->to, R)) {
 		assert(rtype(i->to) == RTmp);
-		update(i->to, i->to, cp, w);
+		update(i->to, i->to, cp, pw);
 	}
 }
 
@@ -76,7 +77,7 @@ copy(Fn *fn)
 {
 	Blk *b;
 	Ref *cp, r;
-	RList *w, *w1;
+	RList *w, *w1, **pw;
 	Use *u, *u1;
 	Ins *i;
 	Phi *p, **pp;
@@ -84,32 +85,33 @@ copy(Fn *fn)
 	int t;
 
 	w = 0;
+	pw = &w;
 	cp = emalloc(fn->ntmp * sizeof cp[0]);
 	for (b=fn->start; b; b=b->link) {
 		for (p=b->phi; p; p=p->link)
-			visitphi(p, cp, &w);
+			visitphi(p, cp, &pw);
 		for (i=b->ins; i-b->ins < b->nins; i++)
-			visitins(i, cp, &w);
+			visitins(i, cp, &pw);
 	}
 	while ((w1=w)) {
 		t = w->t;
-		w = w->l;
-		free(w1);
 		u = fn->tmp[t].use;
 		u1 = u + fn->tmp[t].nuse;
 		for (; u<u1; u++)
 			switch (u->type) {
 			case UPhi:
-				visitphi(u->u.phi, cp, &w);
+				visitphi(u->u.phi, cp, &pw);
 				break;
 			case UIns:
-				visitins(u->u.ins, cp, &w);
+				visitins(u->u.ins, cp, &pw);
 				break;
 			case UJmp:
 				break;
 			default:
 				die("invalid use %d", u->type);
 			}
+		w = w->l;
+		free(w1);
 	}
 	for (b=fn->start; b; b=b->link) {
 		for (pp=&b->phi; (p=*pp);) {