diff options
| author | Quentin Carbonneaux <quentin@c9x.me> | 2019-04-11 19:36:13 +0200 |
|---|---|---|
| committer | Quentin Carbonneaux <quentin@c9x.me> | 2019-04-11 20:18:20 +0200 |
| commit | 81da1cdebb213077a1ce2c1aaed051de0751e13c (patch) | |
| tree | 0d4022e2db324543bf9e0caf802043a5b11495d7 /ssa.c | |
| parent | d84f5fcbb75dcf8f6ff1f12e7509d05598a4b561 (diff) | |
| download | roux-81da1cdebb213077a1ce2c1aaed051de0751e13c.tar.gz | |
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 (limited to 'ssa.c')
| -rw-r--r-- | ssa.c | 21 |
1 files changed, 16 insertions, 5 deletions
diff --git a/ssa.c b/ssa.c index 7ae8117..c098438 100644 --- 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) { |