mem2reg: implement ssa construction; this breaks regalloc right now

9 files changed, 300 insertions, 159 deletions

diff --git a/abi0.c b/abi0.c
index 8523c99..2024424 100644
--- a/abi0.c
+++ b/abi0.c
@@ -198,11 +198,19 @@ abi0_call(struct function *fn, struct instr *ins, struct block *blk, int *curi)
       union irtype retty = call->ret;
       struct instr alloca = { .cls = KPTR };
       struct typedata *td = &typedata[retty.dat];
+      int ialloca ;
 
       sretarghidden = ni == 0;
       alloca.op = Oalloca8 + (td->align == 16);
       alloca.l = mkref(RICON, td->align == 16 ? 1 : td->siz / 8);
-      retmem = insertinstr(blk, (*curi)++ - call->narg, alloca);
+      /* swap alloca and call temps so users of original call point to alloca */
+      retmem = insertinstr(blk, ialloca = (*curi)++ - call->narg, *ins);
+      *ins = alloca;
+      blk->ins.p[ialloca] = ins - instrtab;
+      blk->ins.p[*curi] = retmem.i;
+      ins = &instrtab[retmem.i];
+      retmem.i = blk->ins.p[ialloca];
+
       if (!nret) /* hidden pointer argument */
          insertinstr(blk, (*curi)++ - call->narg,
                      mkinstr(Oarg, 0, mktyperef((union irtype){.cls=KPTR}), retmem));
@@ -219,7 +227,6 @@ abi0_call(struct function *fn, struct instr *ins, struct block *blk, int *curi)
    }
    /* adjust return */
    if (call->ret.isagg) {
-      replref(fn, blk, (*curi), mkref(RTMP, ins - instrtab), retmem);
       ins->cls = 0;
       if (!nret) { /* hidden pointer argument */
          ins->cls = 0;
diff --git a/common.h b/common.h
index ecee563..319903e 100644
--- a/common.h
+++ b/common.h
@@ -393,7 +393,7 @@ int imap_set_(struct imapbase *, void **v, uint vsiz, short k);
                        (m)->mb.n = 0)
 #define imap_get(m, k) (((m)->tmp = imap_get_(&(m)->mb, k)) < 0 ? NULL : &(m)->v[(m)->tmp])
 #define imap_set(m, k, x) ((m)->tmp = imap_set_(&(m)->mb, (void **)&(m)->v, sizeof*(m)->v, k), \
-                           (m)->v[(m)->tmp] = (x))
+                           (m)->v[(m)->tmp] = (x), &(m)->v[(m)->tmp])
 
 struct pmapbase { void **k; uint n, N; };
 /* map of non-null ptr -> T */
diff --git a/io.c b/io.c
index d8652e3..d85d8d3 100644
--- a/io.c
+++ b/io.c
@@ -637,8 +637,8 @@ mapopen(const char **err, const char *path)
       int ret;
 
       do {
-         enum { CHUNKSIZ = 1<<16 };
-         if ((cap += CHUNKSIZ) < CHUNKSIZ) {
+         enum { CHUNKSIZ = 1<<10 };
+         if (f.n + CHUNKSIZ >= cap && (cap += CHUNKSIZ) < CHUNKSIZ) {
             /* overflow */
             free(p);
             goto Big;
diff --git a/ir.c b/ir.c
index 2c1fc06..d1f3ec9 100644
--- a/ir.c
+++ b/ir.c
@@ -13,6 +13,9 @@ const char *opnames[] = {
 };
 
 struct instr instrtab[MAXINSTR];
+struct use *instruse[MAXINSTR];
+short instrnuse[MAXINSTR];
+static struct use instrusebuf[MAXINSTR][2];
 int ninstr;
 static int instrfreelist;
 struct calltab calltab;
@@ -236,23 +239,46 @@ addpred(struct block *blk, struct block *p)
    xbpush(&blk->_pred, &blk->npred, p);
 }
 
-static inline int
+static int
 newinstr(void)
 {
+   int t;
    if (instrfreelist != -1) {
-      int t = instrfreelist;
+      t = instrfreelist;
       memcpy(&instrfreelist, &instrtab[t], sizeof(int));
-      return t;
+   } else {
+      assert(ninstr < arraylength(instrtab));
+      t = ninstr++;
    }
-   assert(ninstr < arraylength(instrtab));
-   return ninstr++;
+   if (instrnuse[t] > 2)
+      xbfree(instruse[t]);
+   instruse[t] = instrusebuf[t];
+   instrnuse[t] = 0;
+   return t;
 }
 
+void
+adduse(struct block *ublk, int ui, union ref r) {
+   struct use user = { ublk, ui };
+   if (r.t != RTMP) return;
+   if (instrnuse[r.i] < 2) {
+      instruse[r.i][instrnuse[r.i]++] = user;
+   } else if (instrnuse[r.i] == arraylength(*instrusebuf)) {
+      struct use *use = NULL;
+      xbgrow(&use, arraylength(*instrusebuf) + 2);
+      memcpy(use, instruse[r.i], arraylength(*instrusebuf) * sizeof *use);
+      use[instrnuse[r.i]++] = user;
+      instruse[r.i] = use;
+   } else {
+      xbpush(&instruse[r.i], &instrnuse[r.i], user);
+   }
+}
 
 union ref
 insertinstr(struct block *blk, int idx, struct instr ins)
 {
    int new = newinstr();
+
    instrtab[new] = ins;
    if (idx == blk->ins.n) vpush(&blk->ins, new);
    else {
@@ -263,15 +289,73 @@ insertinstr(struct block *blk, int idx, struct instr ins)
          blk->ins.p[i] = blk->ins.p[i - 1];
       blk->ins.p[idx] = new;
    }
+   adduse(blk, new, ins.l);
+   adduse(blk, new, ins.r);
    return mkref(RTMP, new);
 }
 
+union ref
+insertphi(struct block *blk, enum irclass cls)
+{
+   int new = newinstr();
+   union ref *refs = NULL;
+   assert(blk->npred > 0);
+   xbgrow(&refs, blk->npred);
+   memset(refs, 0, blk->npred * sizeof *refs);
+   vpush(&phitab, refs);
+   instrtab[new] = mkinstr(Ophi, cls, mkref(RMORE, phitab.n - 1));
+   vpush(&blk->phi, new);
+   return mkref(RTMP, new);
+}
+
+/* require use */
+void
+replcins(union ref from, union ref to)
+{
+   struct use *use, *uend;
+
+   assert(from.t == RTMP);
+   uend = (use = instruse[from.i]) + instrnuse[from.i];
+   for (; use < uend; ++use) {
+      union ref *u;
+      int n, i;
+      if (use->u == from.i) continue;
+      if (use->u == USERJUMP) {
+         u = &use->blk->jmp.arg[0];
+         n = 2;
+      } else if (instrtab[use->u].op == Ophi) {
+         u = phitab.p[instrtab[use->u].l.i];
+         n = use->blk->npred;
+      } else {
+         u = &instrtab[use->u].l;
+         n = 2;
+      }
+      
+      for (i = 0; i < n; ++i) {
+         if (u[i].bits == from.bits) {
+            u[i].bits = to.bits;
+            break;
+         }
+      }
+   }
+}
+
+void
+deluses(int ins)
+{
+   if (instrnuse[ins] > 2)
+      xbfree(instruse[ins]);
+   instrnuse[ins] = 0;
+}
+
 void
 delinstr(struct block *blk, int idx)
 {
+   int t = blk->ins.p[idx];
    assert(idx >= 0 && idx < blk->ins.n);
-   memcpy(&instrtab[blk->ins.p[idx]], &instrfreelist, sizeof(int));
-   instrfreelist = blk->ins.p[idx];
+   memcpy(&instrtab[t], &instrfreelist, sizeof(int));
+   instrfreelist = t;
+   deluses(t);
    for (int i = idx; i < blk->ins.n; ++i)
       blk->ins.p[i] = blk->ins.p[i + 1];
    --blk->ins.n;
@@ -310,6 +394,8 @@ addinstr(struct function *fn, struct instr ins)
    int new = newinstr();
    assert(fn->curblk != NULL);
    instrtab[new] = ins;
+   adduse(fn->curblk, new, ins.l);
+   adduse(fn->curblk, new, ins.r);
    vpush(&fn->curblk->ins, new);
    return mkref(RTMP, new);
 }
@@ -319,17 +405,20 @@ addphi(struct function *fn, enum irclass cls, union ref *r)
 {
    int new;
    struct instr ins = { Ophi, cls };
-   union ref **prefs;
+   union ref *refs = NULL;
 
-   vpush(&phitab, NULL);
-   prefs = &phitab.p[phitab.n - 1];
-   xbgrow(prefs, fn->curblk->npred);
-   memcpy(*prefs, r, fn->curblk->npred * sizeof *r);
+   xbgrow(&refs, fn->curblk->npred);
+   memcpy(refs, r, fn->curblk->npred * sizeof *r);
+   vpush(&phitab, refs);
    ins.l = mkref(RMORE, phitab.n-1);
+
    assert(fn->curblk != NULL);
    assert(fn->curblk->ins.n == 0);
    new = newinstr();
    instrtab[new] = ins;
+   for (int i = 0; i < fn->curblk->npred; ++i) {
+      adduse(fn->curblk, new, r[i]);
+   }
    vpush(&fn->curblk->phi, new);
    return mkref(RTMP, new);
 }
@@ -354,6 +443,7 @@ void
 putcondbranch(struct function *fn, union ref arg, struct block *t, struct block *f)
 {
    assert(fn->curblk && t && f);
+   adduse(fn->curblk, USERJUMP, arg);
    addpred(t, fn->curblk);
    addpred(f, fn->curblk);
    putjump(fn, Jb, arg, NOREF, t, f);
@@ -362,6 +452,8 @@ putcondbranch(struct function *fn, union ref arg, struct block *t, struct block
 void
 putreturn(struct function *fn, union ref r0, union ref r1)
 {
+   adduse(fn->curblk, USERJUMP, r0);
+   adduse(fn->curblk, USERJUMP, r1);
    putjump(fn, Jret, r0, r1, NULL, NULL);
 }
 
@@ -369,42 +461,15 @@ putreturn(struct function *fn, union ref r0, union ref r1)
 
 /** Misc **/
 
-void
-blkreplref(struct block *blk, int i0, union ref from, union ref to)
-{
-   if (i0 == 0) for (int i = 0; i < blk->phi.n; ++i) {
-      union ref *phi = phitab.p[instrtab[blk->phi.p[i]].l.i];
-      for (int i = 0; i < blk->npred; ++i)
-         if (phi[i].bits == to.bits) phi[i] = from;
-   }
-
-   for (int i = i0; i < blk->ins.n; ++i) {
-      struct instr *ins = &instrtab[blk->ins.p[i]];
-      for (int i = 0; i < 2; ++i) {
-         union ref *r = &(&ins->l)[i];
-         if (r->bits == from.bits) *r = to;
-      }
-   }
-}
-
-void
-replref(struct function *fn, struct block *blk, int i0, union ref from, union ref to)
-{
-   do {
-      blkreplref(blk, i0, from, to);
-      i0 = 0;
-   } while ((blk = blk->lnext) != fn->entry);
-}
-
 static void
 freefn(struct function *fn)
 {
    struct block *blk = fn->entry;
    do {
+      if (blk->npred > 1) xbfree(blk->_pred);
       vfree(&blk->phi);
       vfree(&blk->ins);
-      blk = blk->lnext;
-   } while (blk != fn->entry);
+   } while ((blk = blk->lnext) != fn->entry);
 }
 
 void
diff --git a/ir.h b/ir.h
index 594b6d4..45a64a2 100644
--- a/ir.h
+++ b/ir.h
@@ -107,15 +107,7 @@ struct instr {
    union ref l, r;
 };
 
-struct use { bool isjmp; union { ushort ins, blk; }; };
-struct uses {
-   int nuse;
-   struct use *use, _use0[2];
-};
-
-enum jumpkind {
-   JXXX, Jb, Jret,
-};
+enum jumpkind { JXXX, Jb, Jret, };
 
 struct block {
    int id;
@@ -131,12 +123,17 @@ struct block {
    struct { uchar t; union ref arg[2]; } jmp;
 };
 
+enum { USERJUMP = 0xFFFF };
+struct use { struct block *blk; ushort u; };
+
 enum { MAXREGS = 64 };
 
 struct function {
    struct arena *arena;
    const char *name;
    struct block *entry, *curblk;
+   struct use *use;
+   short *nuse;
    union type fnty, retty;
    struct abiarg *abiarg, abiret[2];
    uint nblk;
@@ -191,6 +188,8 @@ extern uchar type2cls[];
 extern uchar cls2siz[];
 extern const uchar siz2intcls[];
 extern struct instr instrtab[];
+extern struct use *instruse[];
+extern short instrnuse[];
 extern struct xcon conht[];
 extern struct calltab {vec_of(struct call);} calltab;
 extern struct phitab {vec_of(union ref *);} phitab;
@@ -198,6 +197,7 @@ extern struct dattab {vec_of(struct irdat);} dattab;
 extern struct addr addrht[];
 #define insrescls(ins) (oiscmp((ins).op) ? KI4 : (ins).cls)
 #define NOREF ((union ref) {0})
+#define UNDREF ((union ref) {{ 0, -1 }})
 #define ZEROREF ((union ref) {{ RICON, 0 }})
 #define mkref(t, x) ((union ref) {{ (t), (x) }})
 #define mktyperef(t) ((union ref) {{ RTYPE, (t).bits }})
@@ -225,7 +225,11 @@ void conputdat(struct irdat *, uint off, enum typetag t, const void *dat);
 union ref mkcallarg(union irtype ret, uint narg, int vararg);
 #define mkintrin(B, C, N) mkinstr(Ointrin, C, {.t=RICON,B}, mkcallarg((union irtype){{0}},N,-1))
 union ref mkaddr(struct addr);
+void adduse(struct block *ublk, int ui, union ref r);
 union ref insertinstr(struct block *, int idx, struct instr);
+union ref insertphi(struct block *, enum irclass cls);
+void replcins(union ref from, union ref to);
+void deluses(int ins);
 void delinstr(struct block *, int idx);
 #define blkpred(blk, i) 0[(blk)->npred < 2 ? &(blk)->_pred0 : &(blk)->_pred[i]]
 
@@ -238,13 +242,10 @@ void putbranch(struct function *, struct block *);
 void putcondbranch(struct function *, union ref arg, struct block *t, struct block *f);
 void putreturn(struct function *, union ref r0, union ref r1);
 
-void blkreplref(struct block *, int, union ref from, union ref to);
-void replref(struct function *, struct block *, int, union ref from, union ref to);
-
 void irdump(struct function *);
 
-struct uses *ssauses(struct function *);
-void freeuses(struct uses *, int n);
+void filluses(struct function *);
+void freeuses(struct use *, int n);
 
 void abi0(struct function *);
 void abi0_call(struct function *, struct instr *, struct block *blk, int *curi);
diff --git a/irdump.c b/irdump.c
index 16f3063..5835c81 100644
--- a/irdump.c
+++ b/irdump.c
@@ -73,6 +73,12 @@ dumpref(enum op o, union ref ref)
 {
    struct xcon *con;
    switch (ref.t) {
+   case RNONE:
+      if (ref.bits == UNDREF.bits)
+         efmt("undef");
+      else
+         efmt("??");
+      break;
    case RTMP:
       if (instrtab[ref.i].reg)
          efmt("%s", mctarg->rnames[instrtab[ref.i].reg - 1]);
@@ -191,6 +197,7 @@ dumpblk(struct function *fn, struct block *blk)
    for (i = 0; i < blk->phi.n; ++i) {
       struct instr *phi = &instrtab[blk->phi.p[i]];
       union ref *refs = phitab.p[phi->l.i];
+      assert(phi->op == Ophi);
       efmt("    %s %%%d = phi ", clsname[phi->cls], blk->phi.p[i]);
       for (int i = 0; i < blk->npred; ++i) {
          if (i) efmt(", ");
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);
diff --git a/ssa.c b/ssa.c
index 46e0741..a2abf7b 100644
--- a/ssa.c
+++ b/ssa.c
@@ -1,89 +1,32 @@
+#include "common.h"
 #include "ir.h"
-#include <stdint.h>
 
-struct uses *
-ssauses(struct function *fn)
+void
+filluses(struct function *fn)
 {
    extern int ninstr;
-   struct uses *uses = xcalloc(ninstr * sizeof *uses);
-   vec_of(struct use) *vuse = xcalloc(ninstr * sizeof *vuse), useacc = {0};
    struct block *blk = fn->entry;
 
-   #define USE(r, isjmp, x) do {                       \
-      struct use u0, u = {isjmp, {x}};                 \
-      if ((r).t == RTMP) {                             \
-         if (vuse[(r).i].n == 0){                      \
-            memcpy(&vuse[(r).i].p, &u, sizeof u);      \
-            ++vuse[(r).i].n;                           \
-         } else {                                      \
-            if (vuse[(r).i].n == 1) {                  \
-               memcpy(&u0, &vuse[(r).i].p, sizeof u0); \
-               vuse[(r).i].n = 0;                      \
-               vuse[(r).i].p = 0;                      \
-               vpush(&vuse[(r).i], u0);                \
-            }                                          \
-            vpush(&vuse[(r).i], u);                    \
-         }                                             \
-      }                                                \
-   } while (0)
+   for (int i = 0; i < ninstr; ++i)
+      deluses(i);
 
    do {
       for (int i = 0; i < blk->phi.n; ++i) {
          int ins = blk->phi.p[i];
          union ref *phi = phitab.p[instrtab[ins].l.i];
-         for (int i = 0; i < blk->npred; ++i) {
-            USE(phi[i], 0, ins);
-         }
+         for (int i = 0; i < blk->npred; ++i)
+            adduse(blk, ins, phi[i]);
       }
       for (int i = 0; i < blk->ins.n; ++i) {
          int ins = blk->ins.p[i];
          assert(instrtab[ins].l.t != RMORE);
          if (instrtab[ins].op != Ocall) assert(instrtab[ins].l.t != RMORE);
-         USE(instrtab[ins].l, 0, ins);
-         USE(instrtab[ins].r, 0, ins);
+         adduse(blk, ins, instrtab[ins].l);
+         adduse(blk, ins, instrtab[ins].r);
       }
-      USE(blk->jmp.arg[0], 1, blk->id);
-      USE(blk->jmp.arg[1], 1, blk->id);
+      adduse(blk, USERJUMP, blk->jmp.arg[0]);
+      adduse(blk, USERJUMP, blk->jmp.arg[1]);
    } while ((blk = blk->lnext) != fn->entry);
-   for (int i = 0; i < ninstr; ++i) {
-      int nuse = uses[i].nuse = vuse[i].n;
-      if (!nuse) continue;
-      if (nuse == 1) {
-         uses[i].use = uses[i]._use0;
-         memcpy(uses[i].use, &vuse[i].p, sizeof *uses[i].use);
-      } else if (nuse < arraylength(uses[i]._use0)) {
-         uses[i].use = uses[i]._use0;
-         memcpy(uses[i].use, vuse[i].p, nuse * sizeof(struct use));
-         vfree(&vuse[i]);
-      } else {
-         intptr_t o;
-         o = useacc.n;
-         memcpy(&uses[i].use, &o, sizeof o);
-         vpushn(&useacc, vuse[i].p, nuse);
-         vfree(&vuse[i]);
-      }
-   }
-   for (int i = 0; i < ninstr; ++i) {
-      if (uses[i].use != uses[i]._use0) {
-         intptr_t o;
-         memcpy(&o, &uses[i].use, sizeof o);
-         uses[i].use = useacc.p + o;
-      }
-   }
-   free(vuse);
-   return uses;
-}
-
-void
-freeuses(struct uses *u, int n)
-{
-   for (int i = 0; i < n; ++i) {
-      if (u[i].use != u[i]._use0) {
-         free(u[i].use);
-         break;
-      }
-   }
-   free(u);
 }
 
 /* vim:set ts=3 sw=3 expandtab: */
diff --git a/todo.txt b/todo.txt
index 3a5ef2f..7981f04 100644
--- a/todo.txt
+++ b/todo.txt
@@ -1,8 +1,6 @@
 Things to finish before moving onto compiler optimizations, C extensions, other nice features
 
 - regalloc: fix phi-eliminating moves
-- frontend: try to repr vars as ssa temps until they have their address taken or are mutated (to reduce no. of mem instrs)??
-- ir: implement mem2reg
 - frontend: finish C impl: initializers, preprocessor (#include, fn-like macros, etc), forward declarations, switch, goto
 
 at some point add another backend like arm64 to make sure the non target specific stuff is generic enough..