From 5e9726946dcb9248dbd34ded1bdd4f7af8dc2d31 Mon Sep 17 00:00:00 2001 From: Quentin Carbonneaux Date: Sun, 18 Dec 2022 17:35:19 +0100 Subject: 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. --- all.h | 5 +++-- amd64/isel.c | 2 +- copy.c | 12 ++++++++---- fold.c | 12 +++++++----- mem.c | 25 +++++++++++++++---------- parse.c | 9 +++++++-- ssa.c | 2 +- util.c | 7 ++++--- 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; anarg; 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; icon[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; incon; i++) { + for (i=1; incon; 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; cncon; c++) - if (fn->con[c].type == CBits && fn->con[c].bits.i == val) + for (c=1; cncon; 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}; -- cgit 1.4.1