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).

3 files changed, 34 insertions, 28 deletions

diff --git a/all.h b/all.h
index cc94161..a40627c 100644
--- 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
index 5385811..8c6278f 100644
--- 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
index c8d490c..0cbd6fa 100644
--- 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;
 	}