diff options
Diffstat (limited to 'ir/optmem.c')
| -rw-r--r-- | ir/optmem.c | 345 |
1 files changed, 0 insertions, 345 deletions
diff --git a/ir/optmem.c b/ir/optmem.c deleted file mode 100644 index f9ad245..0000000 --- a/ir/optmem.c +++ /dev/null @@ -1,345 +0,0 @@ -#include "ir.h" -#include <stdlib.h> /* qsort */ - -static const uchar loadszcls[] = { - [Oloads8 - Oloads8] = 1|KI32<<4, [Oloadu8 - Oloads8] = 1|KI32<<4, - [Oloads16 - Oloads8] = 2|KI32<<4, [Oloadu16 - Oloads8] = 2|KI32<<4, - [Oloads32 - Oloads8] = 4|KI32<<4, [Oloadu32 - Oloads8] = 4|KI32<<4, - [Oloadi64 - Oloads8] = 8|KI64<<4, - [Oloadf32 - Oloads8] = 4|KF32<<4, - [Oloadf64 - Oloads8] = 8|KF64<<4, -}; -static const uchar load2ext[] = { - [Oloads8 - Oloads8] = Oexts8, [Oloadu8 - Oloads8] = Oextu8, - [Oloads16 - Oloads8] = Oexts16, [Oloadu16 - Oloads8] = Oextu16, - [Oloads32 - Oloads8] = Oexts32, [Oloadu32 - Oloads8] = Oextu32, - [Oloadi64 - Oloads8] = Ocopy, -}; -#define loadsz(o) (loadszcls[(o) - Oloads8] & 0xF) -#define loadcls(o) (loadszcls[(o) - Oloads8] >> 4) -#define load2ext(o) (load2ext[(o) - Oloads8]) -#define storesz(o) (1 << ((o) - Ostore8)) - -/* Implements algorithm in 'Simple and Efficient Construction of Static Single Assignment' (Braun et al) */ - -struct ssabuilder { - imap_of(union ref *) curdefs; /* map of var to (map of block to def of var) */ - struct bitset *sealed, /* set of sealed blocks */ - *marked; /* blocks marked, for 'Marker Algorithm' in the paper */ - int lastvisit; - int nblk; -}; - -static union ref readvar(struct ssabuilder *, int var, enum irclass, struct block *); - -static union ref -deltrivialphis(struct ssabuilder *sb, int var, struct block *blk, union ref phiref) -{ - assert(instrtab[phiref.i].op == Ophi); - union ref *args = phitab.p[instrtab[phiref.i].l.i]; - union ref same = {0}; - for (int i = 0; i < blk->npred; ++i) { - if (args[i].bits == same.bits || args[i].bits == phiref.bits) { - continue; /* unique value or self-reference */ - } if (same.bits != 0) { - return phiref; /* non-trivial */ - } - same = args[i]; - } - - if (same.bits == 0) - same = UNDREF; /* the phi is unreachable or in the start block */ - - /* replace uses */ - replcuses(phiref, same); - union ref **pcurdefs = imap_get(&sb->curdefs, var); - assert (pcurdefs); - for (int i = blk->id; i < sb->nblk; ++i) { - if ((*pcurdefs)[i].bits == phiref.bits) - (*pcurdefs)[i] = same; - } - - /* stops infinite recursion and marks phi for removal */ - instrtab[phiref.i].op = Onop; - - /* recursively try to remove all phi users as they might have become trivial */ -Redo: - for (struct use *use = instruse[phiref.i], *uend = use + instrnuse[phiref.i]; use < uend; ++use) { - if (use->u != USERJUMP && instrtab[use->u].op == Ophi && use->u != phiref.i) { - union ref it = mkref(RTMP, use->u); - union ref vphi2 = deltrivialphis(sb, var, use->blk, it); - if (vphi2.bits != it.bits) { - same = vphi2; - /* deletion happened so phiref use may have changed */ - goto Redo; - } - } - } - deluses(phiref.i); - - return same; -} - -static union ref -addphiargs(struct ssabuilder *sb, int var, enum irclass cls, struct block *blk, union ref phiref) -{ - union ref *args = phitab.p[instrtab[phiref.i].l.i]; - for (int i = 0; i < blk->npred; ++i) { - struct block *pred = blkpred(blk, i); - args[i] = readvar(sb, var, cls, pred); - adduse(blk, phiref.i, args[i]); - } - instrtab[phiref.i].r.bits = 0; - return deltrivialphis(sb, var, blk, phiref); -} - -static void -writevar(struct ssabuilder *sb, int var, struct block *blk, union ref val) -{ - union ref **pcurdefs; - if (!(pcurdefs = imap_get(&sb->curdefs, var))) { - pcurdefs = imap_set(&sb->curdefs, var, xcalloc(sb->nblk * sizeof(union ref))); - } - if (val.t == RTMP) assert(instrtab[val.i].op != Onop); - (*pcurdefs)[blk->id] = val; -} - -enum { RPENDINGPHI = 7 }; -static union ref -readvarrec(struct ssabuilder *sb, int var, enum irclass cls, struct block *blk) -{ - union ref val; - assert(blk->npred > 0); - if (!bstest(sb->sealed, blk->id)) { /* unsealed block */ - /* add pending phi */ - val = insertphi(blk, cls); - instrtab[val.i].r = mkref(RPENDINGPHI, var); - } else if (blk->npred == 1) { /* trivial case when block has a single predecessor */ - val = readvar(sb, var, cls, blkpred(blk, 0)); - } else if (!bstest(sb->marked, blk->id)) { - /* Marker Algorithm to optimize the common case where a control flow join doesn't - * need a phi function for the variable: mark the block in case we recursively reach - * it again, collect defs from predecessors, only create a phi if they differ. - * This avoids creating temporary trivial phi functions in acyclic data flow - */ - bsset(sb->marked, blk->id); - for (int i = 0; i < blk->npred; ++i) { - struct block *pred = blkpred(blk, i); - union ref it = readvar(sb, var, cls, pred); - if (!bstest(sb->marked, blk->id)) { - /* recursion reached this blk again, use its phi */ - union ref **pcurdefs = imap_get(&sb->curdefs, var); - /* must have called writevar */ - assert(*pcurdefs && (*pcurdefs)[blk->id].bits); - return (*pcurdefs)[blk->id]; - } - if (i == 0) val = it; - else if (it.bits != val.bits) /* found a different definition, must add phi */ - goto AddPhi; - } - bsclr(sb->marked, blk->id); - } else { /* reached block while recursing */ - AddPhi: - val = insertphi(blk, cls); - writevar(sb, var, blk, val); - val = addphiargs(sb, var, cls, blk, val); - bsclr(sb->marked, blk->id); - return val; - } - writevar(sb, var, blk, val); - return val; -} - -static union ref -readvar(struct ssabuilder *sb, int var, enum irclass cls, struct block *blk) -{ - union ref **pcurdefs; - if ((pcurdefs = imap_get(&sb->curdefs, var)) && (*pcurdefs)[blk->id].bits) - return (*pcurdefs)[blk->id]; - if (blk->npred == 0) /* entry block, var is read before being written to */ - return UNDREF; - return readvarrec(sb, var, cls, blk); -} - -static bool -trysealrec(struct ssabuilder *sb, struct block *blk) -{ -Recur: - if (bstest(sb->sealed, blk->id)) return 1; - if (blk->id > sb->lastvisit) return 0; - markvisited(blk); - for (int i = 0; i < blk->npred; ++i) { - struct block *p = blkpred(blk, i); - if (wasvisited(p)) continue; - if (p->id > sb->lastvisit) return 0; - } - - bsset(sb->sealed, blk->id); - for (int i = 0; i < blk->phi.n; ++i) { - struct instr *ins = &instrtab[blk->phi.p[i]]; - if (ins->r.t == RPENDINGPHI) - addphiargs(sb, ins->r.i, ins->cls, blk, mkref(RTMP, blk->phi.p[i])); - } - if (blk->s1 && !blk->s2) { - blk = blk->s1; - goto Recur; - } else if (blk->s1 && blk->s2) { - trysealrec(sb, blk->s1); - blk = blk->s2; - goto Recur; - } - return 1; -} - -static void -tryseal(struct ssabuilder *sb, struct block *blk) -{ - startbbvisit(); - trysealrec(sb, blk); -} - -static int -blkfindins(struct block *blk, int ins) -{ - for (int i = 0; i < blk->phi.n; ++i) - if (blk->phi.p[i] == ins) return -1; - for (int i = 0; i < blk->ins.n; ++i) - if (blk->ins.p[i] == ins) return i; - assert(0 && "ins not in blk"); -} - -static int -cmpuse(const void *a, const void *b) -{ - const struct use *ua = a, *ub = b; - struct block *blk = ua->blk; - if (ua->blk != ub->blk) return ua->blk->id - ub->blk->id; - if (ua->u == USERJUMP) return ub->u != USERJUMP; - if (ub->u == USERJUMP) return -(ua->u != USERJUMP); - return blkfindins(blk, ua->u) - blkfindins(blk, ub->u); -} - -void -mem2reg(struct function *fn) -{ - static struct bitset bsbuf[2][4]; - struct ssabuilder sb = { .nblk = fn->nblk }; - struct block *blk; - - FREQUIRE(FNUSE); - - if (fn->nblk <= BSNBIT * countof(bsbuf[0])) { - sb.sealed = bsbuf[0]; - sb.marked = bsbuf[1]; - memset(bsbuf[0], 0, BSSIZE(fn->nblk) * sizeof *bsbuf[0]); - memset(bsbuf[1], 0, BSSIZE(fn->nblk) * sizeof *bsbuf[1]); - } else { - sb.sealed = xcalloc(BSSIZE(fn->nblk) * sizeof *sb.sealed); - sb.marked = xcalloc(BSSIZE(fn->nblk) * sizeof *sb.marked); - } - - sortrpo(fn); - blk = fn->entry; - - do { - for (int i = 0; i < blk->ins.n; ++i) { - struct use *use, *uend; - enum irclass k = 0; - int sz = 0, ndef = 0; - enum op ext = Ocopy; - int var = blk->ins.p[i]; - struct instr *ins = &instrtab[var]; - - if (!oisalloca(ins->op)) continue; - uend = instruse[var] + instrnuse[var]; - for (use = instruse[var]; use < uend; ++use) { - struct instr *m; - - if (use->u == USERJUMP) goto Next; - m = &instrtab[use->u]; - if (oisload(m->op) && (!sz || sz == loadsz(m->op))) { - sz = loadsz(m->op); - k = loadcls(m->op); - if (sz < 4) ext = load2ext(m->op); - continue; - } - if (oisstore(m->op) && m->l.bits == mkref(RTMP, var).bits - && (!sz || sz == storesz(m->op))) { - sz = storesz(m->op); - ++ndef; - continue; - } - goto Next; - } - if (!ndef) /* slot is read from but never written to */ - goto Next; - - qsort(instruse[var], instrnuse[var], sizeof *instruse[var], cmpuse); - for (use = instruse[var]; use < uend; ++use) { - struct instr *m = &instrtab[use->u]; - - if (oisstore(m->op)) { - writevar(&sb, var, use->blk, m->r); - *m = mkinstr(Onop,0,); - } else if (oisload(m->op)) { - union ref val = readvar(&sb, var, k = m->cls, use->blk); - if (!val.bits) { /* var is used uninitialized */ - /* TODO emit diagnostic */ - /* load some garbage */ - *m = mkinstr(kisflt(k) ? Oloadf32 + (k==KF64) : Oloads8+ilog2(sz)*2, - k, mkref(RREG, mctarg->bpr)); - } else { - adduse(use->blk, use->u, val); - if (isintcon(val) && ext != Ocopy) { - vlong x = intconval(val); - switch (ext) { - case Oexts8: x = (schar)x; break; - case Oextu8: x = (uchar)x; break; - case Oexts16: x = (short)x; break; - case Oextu16: x = (ushort)x; break; - case Oexts32: x = (int)x; break; - case Oextu32: x = (uint)x; break; - default: assert(0); - } - val = mkintcon(k, x); - ext = Ocopy; - } - *m = mkinstr(ext, k, val); - } - } - } - /* remove alloca */ - delinstr(blk, i--); - - Next:; - } - - assert(sb.lastvisit == blk->id); - ++sb.lastvisit; - tryseal(&sb, blk); - } while ((blk = blk->lnext) != fn->entry); - - do { - /* remove phis marked for deletion */ - for (int i = 0; i < blk->phi.n; ++i) - if (instrtab[blk->phi.p[i]].op == Onop) - delphi(blk, i--); - } while ((blk = blk->lnext) != fn->entry); - - if (sb.sealed != bsbuf[0]) { - free(sb.sealed); - free(sb.marked); - } - - for (int i = 0; i < sb.curdefs.mb.N; ++i) - if (bstest(sb.curdefs.mb.bs, i)) - free(sb.curdefs.v[i]); - imap_free(&sb.curdefs); - if (ccopt.dbg.m) { - bfmt(ccopt.dbgout, "<< After mem2reg >>\n"); - irdump(fn); - } -} - - -/* vim:set ts=3 sw=3 expandtab: */ |