new UNDEF Ref

Crashing loads of uninitialized memory
proved to be a problem when implementing
unions using qbe.  This patch introduces
a new UNDEF Ref to represent data that is
known to be uninitialized.  Optimization
passes can make use of it to eliminate
some code.  In the last compilation stages,
UNDEF is treated as the constant 0xdeaddead.

8 files changed, 46 insertions, 28 deletions

diff --git a/all.h b/all.h
index 47a61d8..7eba443 100644
--- a/all.h
+++ b/all.h
@@ -90,10 +90,11 @@ enum {
 	RMem,
 };
 
-#define R        (Ref){0, 0}
+#define R        (Ref){RTmp, 0}
+#define UNDEF    (Ref){RCon, 0}  /* represents uninitialized data */
+#define CON_Z    (Ref){RCon, 1}
 #define TMP(x)   (Ref){RTmp, x}
 #define CON(x)   (Ref){RCon, x}
-#define CON_Z    CON(0)          /* reserved zero constant */
 #define SLOT(x)  (Ref){RSlot, (x)&0x1fffffff}
 #define TYPE(x)  (Ref){RType, x}
 #define CALL(x)  (Ref){RCall, x}
diff --git a/amd64/isel.c b/amd64/isel.c
index 6d62275..3e3fe62 100644
--- a/amd64/isel.c
+++ b/amd64/isel.c
@@ -482,7 +482,7 @@ seljmp(Blk *b, Fn *fn)
 	}
 	fi = flagi(b->ins, &b->ins[b->nins]);
 	if (!fi || !req(fi->to, r)) {
-		selcmp((Ref[2]){r, CON_Z}, Kw, 0, fn); /* todo, long jnz */
+		selcmp((Ref[2]){r, CON_Z}, Kw, 0, fn);
 		b->jmp.type = Jjf + Cine;
 	}
 	else if (iscmp(fi->op, &k, &c)
diff --git a/copy.c b/copy.c
index 1f9e1f3..77a8f06 100644
--- a/copy.c
+++ b/copy.c
@@ -125,7 +125,7 @@ subst(Ref *pr, Ref *cpy)
 	*pr = copyof(*pr, cpy);
 }
 
-/* requires use and rpo, breaks use */
+/* requires use and dom, breaks use */
 void
 copy(Fn *fn)
 {
@@ -155,12 +155,16 @@ copy(Fn *fn)
 			for (a=0; a<p->narg; a++)
 				if (p->blk[a]->id < n) {
 					r1 = copyof(p->arg[a], cpy);
-					if (req(r, R) || req(r1, r))
+					if (req(r, R) || req(r, UNDEF))
+						r = r1;
+					if (req(r1, r) || req(r1, UNDEF))
 						eq++;
-					r = r1;
 				}
 			assert(!req(r, R));
-			if (eq == p->narg)
+			if (rtype(r) == RTmp
+			&& !dom(fn->rpo[fn->tmp[r.val].bid], b))
+				cpy[p->to.val] = p->to;
+			else if (eq == p->narg)
 				cpy[p->to.val] = r;
 			else {
 				cpy[p->to.val] = p->to;
diff --git a/fold.c b/fold.c
index f992b3a..3ff0bc7 100644
--- a/fold.c
+++ b/fold.c
@@ -1,8 +1,8 @@
 #include "all.h"
 
 enum {
-	Bot = -2, /* lattice bottom */
-	Top = -1, /* lattice top */
+	Bot = -1, /* lattice bottom */
+	Top = 0,  /* lattice top (matches UNDEF) */
 };
 
 typedef struct Edge Edge;
@@ -126,7 +126,6 @@ visitjmp(Blk *b, int n, Fn *fn)
 	switch (b->jmp.type) {
 	case Jjnz:
 		l = latval(b->jmp.arg);
-		assert(l != Top && "ssa invariant broken");
 		if (l == Bot) {
 			edge[n][1].work = flowrk;
 			edge[n][0].work = &edge[n][1];
@@ -174,7 +173,6 @@ renref(Ref *r)
 
 	if (rtype(*r) == RTmp)
 		if ((l=val[r->val]) != Bot) {
-			assert(l != Top && "ssa invariant broken");
 			*r = CON(l);
 			return 1;
 		}
@@ -294,9 +292,13 @@ fold(Fn *fn)
 		for (i=b->ins; i<&b->ins[b->nins]; i++)
 			if (renref(&i->to))
 				*i = (Ins){.op = Onop};
-			else
+			else {
 				for (n=0; n<2; n++)
 					renref(&i->arg[n]);
+				if (isstore(i->op))
+				if (req(i->arg[0], UNDEF))
+					*i = (Ins){.op = Onop};
+			}
 		renref(&b->jmp.arg);
 		if (b->jmp.type == Jjnz && rtype(b->jmp.arg) == RCon) {
 				if (iscon(&fn->con[b->jmp.arg.val], 0, 0)) {
diff --git a/mem.c b/mem.c
index 5d59b96..1db632f 100644
--- a/mem.c
+++ b/mem.c
@@ -201,7 +201,7 @@ coalesce(Fn *fn)
 	Ref *arg;
 	bits x;
 	int64_t off0, off1;
-	int n, m, sz, nsl, nbl, ip, *stk;
+	int n, m, ip, sz, nsl, nbl, *stk;
 	uint total, freed, fused;
 
 	/* minimize the stack usage
@@ -317,26 +317,31 @@ coalesce(Fn *fn)
 	while (n--) {
 		t = &fn->tmp[stk[n]];
 		assert(t->ndef == 1 && t->def);
-		*t->def = (Ins){.op = Onop};
+		i = t->def;
+		if (isload(i->op)) {
+			i->op = Ocopy;
+			i->arg[0] = UNDEF;
+			continue;
+		}
+		*i = (Ins){.op = Onop};
 		for (u=t->use; u<&t->use[t->nuse]; u++) {
 			if (u->type == UJmp) {
 				b = fn->rpo[u->bid];
-				b->jmp.arg = CON_Z;
+				assert(isret(b->jmp.type));
+				b->jmp.type = Jret0;
+				b->jmp.arg = R;
 				continue;
 			}
 			assert(u->type == UIns);
 			i = u->u.ins;
-			/* make loads crash */
-			if (isload(i->op))
-				i->arg[0] = CON_Z;
-			else if (i->op == Oargc)
-				i->arg[1] = CON_Z;
-			else if (!req(i->to, R)) {
+			if (!req(i->to, R)) {
 				assert(rtype(i->to) == RTmp);
 				vgrow(&stk, ++n);
 				stk[n-1] = i->to.val;
+			} else if (isarg(i->op)) {
+				assert(i->op == Oargc);
+				i->arg[1] = CON_Z;  /* crash */
 			} else {
-				assert(!isarg(i->op));
 				if (i->op == Oblit0)
 					*(i+1) = (Ins){.op = Onop};
 				*i = (Ins){.op = Onop};
diff --git a/parse.c b/parse.c
index 68488a2..aed9427 100644
--- a/parse.c
+++ b/parse.c
@@ -867,7 +867,7 @@ parsefn(Lnk *lnk)
 	curi = insb;
 	curf = alloc(sizeof *curf);
 	curf->ntmp = 0;
-	curf->ncon = 1; /* first constant must be 0 */
+	curf->ncon = 2;
 	curf->tmp = vnew(curf->ntmp, sizeof curf->tmp[0], PFn);
 	curf->con = vnew(curf->ncon, sizeof curf->con[0], PFn);
 	for (i=0; i<Tmp0; ++i)
@@ -876,6 +876,8 @@ parsefn(Lnk *lnk)
 		else
 			newtmp(0, Kl, curf);
 	curf->con[0].type = CBits;
+	curf->con[0].bits.i = 0xdeaddead;  /* UNDEF */
+	curf->con[1].type = CBits;
 	curf->lnk = *lnk;
 	blink = &curf->start;
 	curf->retty = Kx;
@@ -1230,7 +1232,10 @@ printref(Ref r, Fn *fn, FILE *f)
 			fprintf(f, "%%%s", fn->tmp[r.val].name);
 		break;
 	case RCon:
-		printcon(&fn->con[r.val], f);
+		if (req(r, UNDEF))
+			fprintf(f, "UNDEF");
+		else
+			printcon(&fn->con[r.val], f);
 		break;
 	case RSlot:
 		fprintf(f, "S%d", rsval(r));
diff --git a/ssa.c b/ssa.c
index 849f679..356135b 100644
--- a/ssa.c
+++ b/ssa.c
@@ -264,7 +264,7 @@ getstk(int t, Blk *b, Name **stk)
 	stk[t] = n;
 	if (!n) {
 		/* uh, oh, warn */
-		return CON_Z;
+		return UNDEF;
 	} else
 		return n->r;
 }
diff --git a/util.c b/util.c
index 8432b5a..8997f6c 100644
--- a/util.c
+++ b/util.c
@@ -361,7 +361,7 @@ newcon(Con *c0, Fn *fn)
 	Con *c1;
 	int i;
 
-	for (i=0; i<fn->ncon; i++) {
+	for (i=1; i<fn->ncon; i++) {
 		c1 = &fn->con[i];
 		if (c0->type == c1->type
 		&& symeq(c0->sym, c1->sym)
@@ -378,8 +378,9 @@ getcon(int64_t val, Fn *fn)
 {
 	int c;
 
-	for (c=0; c<fn->ncon; c++)
-		if (fn->con[c].type == CBits && fn->con[c].bits.i == val)
+	for (c=1; c<fn->ncon; c++)
+		if (fn->con[c].type == CBits
+		&& fn->con[c].bits.i == val)
 			return CON(c);
 	vgrow(&fn->con, ++fn->ncon);
 	fn->con[c] = (Con){.type = CBits, .bits.i = val};