commit 81da1cdebb213077a1ce2c1aaed051de0751e13c
parent d84f5fcbb75dcf8f6ff1f12e7509d05598a4b561
Author: Quentin Carbonneaux <quentin@c9x.me>
Date: Thu, 11 Apr 2019 19:36:13 +0200
properly detect ssa form
Previously, we would skip ssa construction when
a temporary has a single definition. This is
only part of the ssa invariant: we must also
check that all uses are dominated by the single
definition. The new code does this.
In fact, qbe does not store all the dominators
for a block, so instead of walking the idom
linked list we use a rough heuristic and declare
conservatively that B0 dominates B1 when one of
the two conditions is true:
a. B0 is the start block
b. B0 is B1
Some measurements on a big file from Michael
Forney show that the code is still as fast as
before this patch.
Diffstat:
3 files changed, 19 insertions(+), 6 deletions(-)
diff --git a/all.h b/all.h
@@ -248,7 +248,7 @@ struct Use {
UIns,
UJmp,
} type;
- int bid;
+ uint bid;
union {
Ins *ins;
Phi *phi;
@@ -279,6 +279,7 @@ struct Alias {
struct Tmp {
char name[NString];
+ uint bid; /* id of a defining block */
Use *use;
uint ndef, nuse;
uint cost;
diff --git a/main.c b/main.c
@@ -65,6 +65,7 @@ func(Fn *fn)
fillpreds(fn);
filluse(fn);
memopt(fn);
+ filluse(fn);
ssa(fn);
filluse(fn);
ssacheck(fn);
diff --git a/ssa.c b/ssa.c
@@ -47,6 +47,7 @@ filluse(Fn *fn)
/* todo, is this the correct file? */
tmp = fn->tmp;
for (t=Tmp0; t<fn->ntmp; t++) {
+ tmp[t].bid = -1u;
tmp[t].ndef = 0;
tmp[t].nuse = 0;
tmp[t].cls = 0;
@@ -59,6 +60,7 @@ filluse(Fn *fn)
for (p=b->phi; p; p=p->link) {
assert(rtype(p->to) == RTmp);
tp = p->to.val;
+ tmp[tp].bid = b->id;
tmp[tp].ndef++;
tmp[tp].cls = p->cls;
tp = phicls(tp, fn->tmp);
@@ -84,6 +86,7 @@ filluse(Fn *fn)
w = WFull;
t = i->to.val;
tmp[t].width = w;
+ tmp[t].bid = b->id;
tmp[t].ndef++;
tmp[t].cls = i->cls;
}
@@ -111,9 +114,10 @@ phiins(Fn *fn)
Blk *a, *b, **blist, **be, **bp;
Ins *i;
Phi *p;
+ Use *use;
Ref r;
- int t, nt;
- uint n;
+ int t, nt, ok;
+ uint n, defb;
short k;
bsinit(u, fn->nblk);
@@ -125,8 +129,15 @@ phiins(Fn *fn)
fn->tmp[t].visit = 0;
if (fn->tmp[t].phi != 0)
continue;
- if (fn->tmp[t].ndef == 1)
- continue;
+ if (fn->tmp[t].ndef == 1) {
+ ok = 1;
+ defb = fn->tmp[t].bid;
+ use = fn->tmp[t].use;
+ for (n=fn->tmp[t].nuse; n--; use++)
+ ok &= use->bid == defb;
+ if (ok || defb == fn->start->id)
+ continue;
+ }
bszero(u);
k = -1;
bp = be;
@@ -293,7 +304,7 @@ renblk(Blk *b, Name **stk, Fn *fn)
renblk(s, stk, fn);
}
-/* require rpo and ndef */
+/* require rpo and use */
void
ssa(Fn *fn)
{
