mem2reg: implement ssa construction; this breaks regalloc right now

1 files changed, 149 insertions, 29 deletions

diff --git a/optmem.c b/optmem.c
index ba81cd2..c9b4536 100644
--- a/optmem.c
+++ b/optmem.c
@@ -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);