diff options
Diffstat (limited to 'optmem.c')
| -rw-r--r-- | optmem.c | 178 |
1 files changed, 149 insertions, 29 deletions
@@ -19,36 +19,144 @@ static const uchar load2ext[] = { #define load2ext(o) (load2ext[(o) - Oloads1]) #define storesz(o) (1 << ((o) - Ostore1)) +/* Implements algorithm in 'Simple and Efficient Construction of Static Single' (Braun et al) */ + +struct pendingphi { ushort var, phi; }; +struct ssabuilder { + vec_of(struct pendingphi) *pendingphis; /* map of block to list of incomplete phis in block */ + imap_of(union ref *) curdefs; /* map of var to (map of block to def of var) */ + int nsealed; /* num of sealed blocks */ + int nblk; +}; + +static union ref readvar(struct ssabuilder *, int var, enum irclass, struct block *); + +static union ref +deltrivialphis(struct block *blk, union ref phiref) +{ + struct use *use, *uend; + 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 */ + replcins(phiref, same); + + /* remove phi */ + for (int i = 0; i < blk->phi.n; ++i) { + if (blk->phi.p[i] == phiref.i) { + for (int k = i; k < blk->phi.n - 1; ++k) + blk->phi.p[k] = blk->phi.p[k + 1]; + --blk->phi.n; + break; + } + } + instrtab[phiref.i].op = Onop; + + /* recursively try to remove all phi users as they might have become trivial */ + for (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) + deltrivialphis(use->blk, mkref(RTMP, use->u)); + + 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]); + } + return deltrivialphis(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))); + } + (*pcurdefs)[blk->id] = val; +} + +static union ref +readvarrec(struct ssabuilder *sb, int var, enum irclass cls, struct block *blk) +{ + union ref val; + assert(blk->npred > 0); + if (blk->id >= sb->nsealed) { + /* unsealed block */ + val = insertphi(blk, cls); + vpush(&sb->pendingphis[blk->id], ((struct pendingphi) { var, val.i })); + } else if (blk->npred == 1) { + val = readvar(sb, var, cls, blkpred(blk, 0)); + } else { + val = insertphi(blk, cls); + writevar(sb, var, blk, val); + val = addphiargs(sb, var, cls, blk, 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].t) + return (*pcurdefs)[blk->id]; + if (blk->npred == 0) /* entry block, var is read before being written to */ + return NOREF; + return readvarrec(sb, var, cls, blk); +} + void mem2reg(struct function *fn) { - extern int ninstr; - struct uses *uses = ssauses(fn); struct block *blk = fn->entry; + struct ssabuilder sb = { .nblk = fn->nblk }; + + sb.pendingphis = xcalloc(fn->nblk * sizeof *sb.pendingphis); do { + vec_of(struct pendingphi) *pending; + for (int i = 0; i < blk->ins.n; ++i) { struct use *use, *uend; - union ref var; enum irclass k = 0; int sz = 0, ndef = 0; - enum op ext; - int t = blk->ins.p[i]; - struct instr *ins = &instrtab[t]; + enum op ext = Ocopy; + int var = blk->ins.p[i]; + struct instr *ins = &instrtab[var]; if (!oisalloca(ins->op)) continue; - for (use = uses[t].use, uend = &uses[t].use[uses[t].nuse]; use < uend; ++use) { + uend = instruse[var] + instrnuse[var]; + for (use = instruse[var]; use < uend; ++use) { struct instr *m; - if (use->isjmp) goto Next; - m = &instrtab[use->ins]; + 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, t).bits + if (oisstore(m->op) && m->l.bits == mkref(RTMP, var).bits && (!sz || sz == storesz(m->op))) { sz = storesz(m->op); ++ndef; @@ -58,37 +166,49 @@ mem2reg(struct function *fn) } if (!ndef) /* slot is read from but never written to */ goto Next; - - if (ndef>1) /* TODO phi construction */ - goto Next; - - /* remove alloca */ - *ins = mkinstr(Onop, 0,); - var.t = 0; - for (use = uses[t].use; use < uend; ++use) { - struct instr *m = &instrtab[use->ins]; + for (use = instruse[var]; use < uend; ++use) { + struct instr *m = &instrtab[use->u]; if (oisstore(m->op)) { - if (sz < 4) { - *m = mkinstr(ext, KI4, m->r); - var = mkref(RTMP, use->ins); + writevar(&sb, var, use->blk, m->r); + *m = mkinstr(Onop,0,); + } else if (oisload(m->op)) { + union ref val = readvar(&sb, var, k, use->blk); + if (!val.t) { /* var is used uninitialized */ + /* TODO emit diagnostic */ + /* load some garbage */ + *m = mkinstr(kisflt(k) ? Oloadf4 + (k==KF8) : Oloads1+ilog2(sz)*2, + k, mkref(RREG, mctarg->bpr)); } else { - var = m->r; - *m = mkinstr(Onop,0,); + adduse(use->blk, use->u, val); + *m = mkinstr(ext, k, val); } - } else if (oisload(m->op)) { - if (!var.t) /* use before def */ - goto Next; - *m = mkinstr(Ocopy, k, var); } } + /* remove alloca */ + delinstr(blk, i); Next:; } + + /* seal block */ + assert(sb.nsealed == blk->id); + ++sb.nsealed; + pending = (void *) &sb.pendingphis[blk->id]; + for (int i = 0; i < pending->n; ++i) { + addphiargs(&sb, pending->p[i].var, instrtab[pending->p[i].phi].cls, blk, + mkref(RTMP, pending->p[i].phi)); + } + vfree(pending); } while ((blk = blk->lnext) != fn->entry); - freeuses(uses, ninstr); + free(sb.pendingphis); + + 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) { efmt("<< After mem2reg >>\n"); irdump(fn); |