qbe

commit 8215b50a10e240581bd1f9e8ae4d13c48f865c6c
parent 1a76fd11f501d0bf762e01661d8a67c18c3e01bd
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date:   Mon,  6 Feb 2017 14:38:47 -0500

fix edge deletion bug in sccp

When an edge is deleted, the phis and predecessors of the
destination block have to be updated.  This is what blkdel()
was doing, but at a level too coarse.  The new function
edgedel() allows to remove a single edge (and takes care of
multiple edges).

Diffstat:
M
all.h
 | 
2
+-
M
cfg.c
 | 
48
+++++++++++++++++++++++++-----------------------
M
fold.c
 | 
12
++++++++----

3 files changed, 34 insertions(+), 28 deletions(-)
diff --git a/all.h b/all.h
@@ -547,7 +547,7 @@ void err(char *, ...) __attribute__((noreturn));
 
 /* cfg.c */
 Blk *blknew(void);
-void blkdel(Blk *);
+void edgedel(Blk *, Blk **);
 void fillpreds(Fn *);
 void fillrpo(Fn *);
 void filldom(Fn *);
diff --git a/cfg.c b/cfg.c
@@ -12,32 +12,33 @@ blknew()
 }
 
 void
-blkdel(Blk *b)
+edgedel(Blk *bs, Blk **pbd)
 {
-	Blk *s, **ps, *succ[3];
+	Blk *bd;
 	Phi *p;
 	uint a;
+	int mult;
 
-	succ[0] = b->s1;
-	succ[1] = b->s2 == b->s1 ? 0 : b->s2;
-	succ[2] = 0;
-	for (ps=succ; (s=*ps); ps++) {
-		for (p=s->phi; p; p=p->link) {
-			for (a=0; p->blk[a]!=b; a++)
-				assert(a+1<p->narg);
-			p->narg--;
-			memmove(&p->blk[a], &p->blk[a+1],
-				sizeof p->blk[0] * (p->narg-a));
-			memmove(&p->arg[a], &p->arg[a+1],
-				sizeof p->arg[0] * (p->narg-a));
-		}
-		if (s->npred != 0) {
-			for (a=0; s->pred[a]!=b; a++)
-				assert(a+1<s->npred);
-			s->npred--;
-			memmove(&s->pred[a], &s->pred[a+1],
-				sizeof s->pred[0] * (s->npred-a));
-		}
+	bd = *pbd;
+	mult = 1 + (bs->s1 == bs->s2);
+	*pbd = 0;
+	if (!bd || mult > 1)
+		return;
+	for (p=bd->phi; p; p=p->link) {
+		for (a=0; p->blk[a]!=bs; a++)
+			assert(a+1<p->narg);
+		p->narg--;
+		memmove(&p->blk[a], &p->blk[a+1],
+			sizeof p->blk[0] * (p->narg-a));
+		memmove(&p->arg[a], &p->arg[a+1],
+			sizeof p->arg[0] * (p->narg-a));
+	}
+	if (bd->npred != 0) {
+		for (a=0; bd->pred[a]!=bs; a++)
+			assert(a+1<bd->npred);
+		bd->npred--;
+		memmove(&bd->pred[a], &bd->pred[a+1],
+			sizeof bd->pred[0] * (bd->npred-a));
 	}
 }
 
@@ -110,7 +111,8 @@ fillrpo(Fn *f)
 	f->rpo = alloc(f->nblk * sizeof f->rpo[0]);
 	for (p=&f->start; (b=*p);) {
 		if (b->id == -1u) {
-			blkdel(b);
+			edgedel(b, &b->s1);
+			edgedel(b, &b->s2);
 			*p = b->link;
 		} else {
 			b->id -= n;
diff --git a/fold.c b/fold.c
@@ -275,7 +275,8 @@ fold(Fn *fn)
 			d = 1;
 			if (debug['F'])
 				fprintf(stderr, "%s ", b->name);
-			blkdel(b);
+			edgedel(b, &b->s1);
+			edgedel(b, &b->s2);
 			*pb = b->link;
 			continue;
 		}
@@ -296,11 +297,14 @@ fold(Fn *fn)
 					renref(&i->arg[n]);
 		renref(&b->jmp.arg);
 		if (b->jmp.type == Jjnz && rtype(b->jmp.arg) == RCon) {
-				b->jmp.type = Jjmp;
-				if (czero(&fn->con[b->jmp.arg.val], 0))
+				if (czero(&fn->con[b->jmp.arg.val], 0)) {
+					edgedel(b, &b->s1);
 					b->s1 = b->s2;
+					b->s2 = 0;
+				} else
+					edgedel(b, &b->s2);
+				b->jmp.type = Jjmp;
 				b->jmp.arg = R;
-				b->s2 = 0;
 		}
 		pb = &b->link;
 	}