ir: arena-backed linked list for uselists

Is much simpler than the growable buffers, seems to be just as efficient
if not a little faster when benchmarked.

4 files changed, 96 insertions, 117 deletions

diff --git a/bootstrap.sh b/bootstrap.sh
index a65824e..1761ac5 100755
--- a/bootstrap.sh
+++ b/bootstrap.sh
@@ -7,10 +7,14 @@ test -n "$cc" || cc=cc
 opt="$O"
 test -n "$opt" || opt=
 
-cflags="-std=c11"
+cflags=$CFLAGS
+test -n "$cflags" || : ${cflags:="-std=c11"}
+if test -n "$V"; then
+    opt="$opt -v"
+fi
 src=$(grep -o '\([_A-Za-z0-9/]\)\+\.c' < Makefile)
 X() {
-    echo "> $@" | ([ x"$V" == x1 ] && cat || sed -s 's/\([^ ]\+\.c \?\)\{10\}$/.../')
+    echo "> $@" | (test -n "$V" && cat || sed -s 's/\([^ ]\+\.c \?\)\{10\}$/.../')
     $@
 }
 echo "== Stage 0 (compiling with $cc) =="
diff --git a/ir/ir.c b/ir/ir.c
index 6edc429..1f1c9bc 100644
--- a/ir/ir.c
+++ b/ir/ir.c
@@ -25,10 +25,10 @@ const uchar opnarg[] = {
 
 struct instr instrtab[MAXINSTR];
 struct use *instruse[MAXINSTR];
-short instrnuse[MAXINSTR];
-static struct use instrusebuf[MAXINSTR][2];
 int ninstr;
 static int instrfreelist;
+static struct use *usefreelist;
+static struct arena **usearena;
 struct calltab calltab;
 struct phitab phitab;
 struct dattab dattab;
@@ -49,6 +49,8 @@ irinit(struct function *fn)
 
    ninstr = 0;
    instrfreelist = -1;
+   usefreelist = NULL;
+   usearena = fn->arena;
    vinit(&calltab, callsbuf, countof(callsbuf));
    for (int i = 0; i < phitab.n; ++i) xbfree(phitab.p[i]);
    vinit(&phitab, phisbuf, countof(phisbuf));
@@ -77,7 +79,7 @@ irinit(struct function *fn)
 }
 
 static int
-addaddr(const struct addr *addr)
+newaddr(const struct addr *addr)
 {
    uint h = hashb(0, addr, sizeof *addr);
    uint i = h, n = countof(addrht);
@@ -95,7 +97,7 @@ addaddr(const struct addr *addr)
 }
 
 static int
-addcon(const struct xcon *con)
+newcon(const struct xcon *con)
 {
    uint h = hashb(0, con, sizeof *con);
    uint i = h, n = countof(conht);
@@ -131,7 +133,7 @@ mkintcon(enum irclass k, vlong i)
       struct xcon con = { .cls = k, .i = i };
       if (cls2siz[k] == 4) /* check upper half is zero or -1 */
          assert(in_range((i >> 32) + 1, 0, 1));
-      return mkref(RXCON, addcon(&con));
+      return mkref(RXCON, newcon(&con));
    }
 }
 
@@ -139,14 +141,14 @@ union ref
 mkfltcon(enum irclass k, double f)
 {
    struct xcon con = { .cls = k, .f = k == KF32 ? (float) f : f };
-   return mkref(RXCON, addcon(&con));
+   return mkref(RXCON, newcon(&con));
 }
 
 union ref
 mksymref(internstr s, bool isfunc)
 {
    struct xcon con = { .issym = 1, .sym = s, .isfunc = isfunc };
-   return mkref(RXCON, addcon(&con));
+   return mkref(RXCON, newcon(&con));
 }
 
 union ref
@@ -170,7 +172,7 @@ mkdatref(internstr name, union type ctype, uint siz, uint align, const void *byt
    if (n) memcpy(p, bytes, n);
    if (dat.section != Stext) memset(p+n, 0, siz - n);
    vpush(&dattab, dat);
-   return mkref(RXCON, addcon(&(struct xcon){.isdat = 1, .deref = deref, .dat = dattab.n - 1}));
+   return mkref(RXCON, newcon(&(struct xcon){.isdat = 1, .deref = deref, .dat = dattab.n - 1}));
 }
 
 internstr
@@ -203,7 +205,7 @@ mkcallarg(union irtype ret, uint narg, int vararg)
 union ref
 mkaddr(struct addr addr)
 {
-   return mkref(RADDR, addaddr(&addr));
+   return mkref(RADDR, newaddr(&addr));
 }
 
 void
@@ -351,58 +353,48 @@ allocinstr(void)
    if (instrfreelist != -1) {
       t = instrfreelist;
       memcpy(&instrfreelist, &instrtab[t], sizeof(int));
+      if (instruse[t]) deluses(t);
    } else {
       assert(ninstr < countof(instrtab));
       t = ninstr++;
+      instruse[t] = NULL;
    }
-   if (instruse[t] != instrusebuf[t])
-      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] < countof(instrusebuf[r.i])) {
-      instruse[r.i][instrnuse[r.i]++] = user;
-   } else if (instrnuse[r.i] == countof(*instrusebuf)) {
-      struct use *use = NULL;
-      xbgrow(&use, countof(*instrusebuf) + 2);
-      memcpy(use, instruse[r.i], sizeof(*instrusebuf));
-      use[instrnuse[r.i]++] = user;
-      instruse[r.i] = use;
+   struct use *use; 
+   if (usefreelist) {
+      use = usefreelist;
+      usefreelist = usefreelist->next;
    } else {
-      xbpush(&instruse[r.i], &instrnuse[r.i], user);
+      use = alloc(usearena, sizeof *use, 0);
    }
+   assert(use != instruse[r.i]);
+   use->next = instruse[r.i];
+   use->blk = ublk,
+   use->u = ui;
+   instruse[r.i] = use;
 }
 
 bool
 deluse(struct block *ublk, int ui, union ref r) {
    if (r.t != RTMP) return 0;
 
-   for (int i = 0; i < instrnuse[r.i]; ++i) {
-      if (instruse[r.i][i].blk == ublk && instruse[r.i][i].u == ui) {
-         for (int k = i; k < instrnuse[r.i] - 1; ++k) {
-            instruse[r.i][k] = instruse[r.i][k+1];
-         }
-         goto Shrink;
+   for (struct use **puse = &instruse[r.i]; *puse; puse = &(*puse)->next) {
+      struct use *use = *puse;
+      if (use->blk == ublk && use->u == ui) {
+         *puse = use->next;
+         use->blk = 0;
+         use->u = 0;
+         use->next = usefreelist;
+         usefreelist = use;
+         return 1;
       }
    }
    return 0;
-
-Shrink:
-   if (instrnuse[r.i] == countof(*instrusebuf) + 1) {
-      struct use *use = instruse[r.i];
-      instruse[r.i] = instrusebuf[r.i];
-      memcpy(instruse[r.i], use, sizeof *instrusebuf);
-      xbfree(use);
-   }
-   --instrnuse[r.i];
-   return 1;
 }
 
 void
@@ -510,27 +502,27 @@ void
 replcuses(union ref from, union ref to)
 {
    assert(from.t == RTMP);
-   for (int i = 0; i < instrnuse[from.i]; ++i) {
-      struct use use = instruse[from.i][i];
+   for (struct use *use = instruse[from.i], *next; use; use = next) {
       union ref *u;
       int n, j;
-      if (use.u == from.i) continue;
-      if (use.u == USERJUMP) {
-         u = &use.blk->jmp.arg[0];
+      next = use->next;
+      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 if (instrtab[use->u].op == Ophi) {
+         u = phitab.p[instrtab[use->u].l.i];
+         n = use->blk->npred;
       } else {
-         u = &instrtab[use.u].l;
+         u = &instrtab[use->u].l;
          n = 2;
       }
       
       for (j = 0; j < n; ++j) {
          if (u[j].bits == from.bits) {
             u[j].bits = to.bits;
-            adduse(use.blk, use.u, to);
-            --i;
+            adduse(use->blk, use->u, to);
+            next = use;
             break;
          }
       }
@@ -540,11 +532,14 @@ replcuses(union ref from, union ref to)
 void
 deluses(int ins)
 {
-   if (instruse[ins] != instrusebuf[ins]) {
-      xbfree(instruse[ins]);
-      instruse[ins] = instrusebuf[ins];
+   for (struct use *use = instruse[ins], *next; use; use = next) {
+      next = use->next;
+      use->blk = 0;
+      use->u = 0;
+      use->next = usefreelist;
+      usefreelist = use;
    }
-   instrnuse[ins] = 0;
+   instruse[ins] = NULL;
 }
 
 void
diff --git a/ir/ir.h b/ir/ir.h
index 4248016..8e18e1f 100644
--- a/ir/ir.h
+++ b/ir/ir.h
@@ -141,7 +141,7 @@ struct block {
 #define blkpred(blk, i) 0[(blk)->npred < 2 ? &(blk)->_pred0 : &(blk)->_pred[i]]
 
 enum { USERJUMP = 0xFFFF };
-struct use { struct block *blk; ushort u; };
+struct use { struct use *next; struct block *blk; ushort u; };
 
 enum { MAXREGS = 64 };
 /** register set **/
@@ -233,7 +233,6 @@ extern uchar cls2load[];
 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;
diff --git a/ir/mem2reg.c b/ir/mem2reg.c
index 0bd78ca..4b0b007 100644
--- a/ir/mem2reg.c
+++ b/ir/mem2reg.c
@@ -65,7 +65,7 @@ deltrivialphis(struct ssabuilder *sb, int var, struct block *blk, union ref phir
 
    /* 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) {
+   for (struct use *use = instruse[phiref.i]; use; use = use->next) {
       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);
@@ -210,14 +210,14 @@ blkfindins(struct block *blk, int ins)
 }
 
 static int
-cmpuse(const void *a, const void *b)
+rcmpuse(const void *a, const void *b)
 {
-   const struct use *ua = a, *ub = b;
+   /* postorder sort */
+   const struct use *ua = *(struct use **)a, *ub = *(struct use **)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);
+   if (ua->blk != ub->blk) return ub->blk->id - ua->blk->id;
+   assert(ua->u != USERJUMP && ub->u != USERJUMP);
+   return blkfindins(blk, ub->u) - blkfindins(blk, ua->u);
 }
 
 void
@@ -234,75 +234,56 @@ mem2reg(struct function *fn)
    struct block *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;
+         int sz = 0;
          enum op ext = Ocopy;
          int var = blk->ins.p[i];
          struct instr *ins = &instrtab[var];
+         struct use *use;
          
-         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];
+         /* find allocas only used in loads/stores of uniform size */
+         if (!oisalloca(ins->op) || !(use = instruse[var])) continue;
+         struct use *usesbuf[64];
+         vec_of(struct use *) uses = VINIT(usesbuf, countof(usesbuf));
+         do {
+            if (use->u == USERJUMP) goto Skip;
+            struct instr *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))) {
+            } else 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 && instrnuse[var] > 0) /* slot is read from but never written to */
-            goto Next;
+            } else goto Skip;
+            vpush(&uses, use);
+         } while ((use = use->next));
          
-         qsort(instruse[var], instrnuse[var], sizeof *instruse[var], cmpuse);
-         for (use = instruse[var]; use < uend; ++use) {
-            struct instr *m = &instrtab[use->u];
+         /* visit uses in rpo */
+         qsort(uses.p, uses.n, sizeof *uses.p, rcmpuse);
+         for (int i = uses.n-1; i >= 0; --i) {
+            use = uses.p[i];
+            ins = &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);
+            if (oisstore(ins->op)) {
+               writevar(&sb, var, use->blk, ins->r);
+               *ins = mkinstr(Onop,0,);
+            } else if (oisload(ins->op)) {
+               union ref val = readvar(&sb, var, k = ins->cls, use->blk);
+               adduse(use->blk, use->u, val);
+               if (ext != Ocopy && isintcon(val)) { /* fold constant int extension */
+                  val = irunop(NULL, ext, k, val);
+                  assert(val.bits);
+                  ext = Ocopy;
                }
+               *ins = mkinstr(ext, k, val);
             }
          }
          /* remove alloca */
          delinstr(blk, i--);
          
-      Next:;
+      Skip:
+         vfree(&uses);
       }
 
       assert(sb.lastvisit == blk->id);