explicitly store predecessors in each block

8 files changed, 135 insertions, 115 deletions

diff --git a/amd64/isel.c b/amd64/isel.c
index e5aa281..3f83312 100644
--- a/amd64/isel.c
+++ b/amd64/isel.c
@@ -413,10 +413,10 @@ amd64_isel(struct function *fn)
    do {
       int i;
       for (i = 0; i < blk->phi.n; ++i) {
-         struct phi *phi = &phitab.p[instrtab[blk->phi.p[i]].l.i];
-         for (int i = 0; i < phi->n; ++i) {
-            int curi = phi->blk[i]->ins.n;
-            fixarg(&phi->ref[i], NULL, phi->blk[i], &curi);
+         union ref *phi = phitab.p[instrtab[blk->phi.p[i]].l.i];
+         for (int i = 0; i < blk->npred; ++i) {
+            int curi = blkpred(blk, i)->ins.n;
+            fixarg(&phi[i], NULL, blkpred(blk, i), &curi);
          }
       }
       iflagsrc = -1;
diff --git a/c.c b/c.c
index a8f2aa4..27abfe9 100644
--- a/c.c
+++ b/c.c
@@ -1255,7 +1255,6 @@ Loop:
 }
 
 struct condphis {
-   vec_of(struct block *) blk;
    vec_of(union ref) ref;
 };
 
@@ -1289,7 +1288,6 @@ condexprrec(struct function *fn, const struct expr *ex, struct condphis *phis,
       condexprrec(fn, &ex->sub[2], phis, -1, end, zero);
    } else {
       r = exprvalue(fn, ex);
-      vpush(&phis->blk, fn->curblk);
       if (boolcon == -2)
          r = cvt(fn, TYBOOL, ex->ty.t, r);
       if (boolcon >= 0)
@@ -1305,6 +1303,23 @@ condexprrec(struct function *fn, const struct expr *ex, struct condphis *phis,
    }
 }
 
+/* the naive way to generate something like a ? b : c ? d : e, uses multiple phis,
+ * this code reduces such nested conditional expressions into one phi */
+static union ref
+condexprvalue(struct function *fn, const struct expr *ex)
+{
+   union ref refbuf[8];
+   struct condphis phis = { VINIT(refbuf, arraylength(refbuf)) };
+   struct block *dst = newblk(fn);
+   union ref r;
+   condexprrec(fn, ex, &phis, -1, dst, NULL);
+   useblk(fn, dst);
+   assert(fn->curblk->npred == phis.ref.n);
+   r = addphi(fn, type2cls[ex->ty.t], phis.ref.p);
+   vfree(&phis.ref);
+   return r;
+}
+
 static union ref
 compilecall(struct function *fn, const struct expr *ex)
 {
@@ -1335,25 +1350,6 @@ compilecall(struct function *fn, const struct expr *ex)
    return addinstr(fn, ins);
 }
 
-/* the naive way to generate something like a ? b : c ? d : e, uses multiple phis,
- * this code reduces such nested conditional expressions into one phi */
-static union ref
-condexprvalue(struct function *fn, const struct expr *ex)
-{
-   struct block *blkbuf[8];
-   union ref refbuf[8];
-   struct condphis phis = { VINIT(blkbuf, arraylength(blkbuf)),
-                            VINIT(refbuf, arraylength(refbuf))};
-   struct block *dst = newblk(fn);
-   union ref r;
-   condexprrec(fn, ex, &phis, -1, dst, NULL);
-   useblk(fn, dst);
-   r = addphi(fn, type2cls[ex->ty.t], phis.blk.p, phis.ref.p, phis.blk.n);
-   vfree(&phis.blk);
-   vfree(&phis.ref);
-   return r;
-}
-
 static union ref
 compileexpr(struct function *fn, const struct expr *ex, bool discard)
 {
diff --git a/common.h b/common.h
index a1cc1f8..ecee563 100644
--- a/common.h
+++ b/common.h
@@ -329,10 +329,32 @@ struct arena {
 
 #define vec_of(T) struct { T *p; int _cap; uint n; }
 
+/* libc *alloc wrappers */
 extern void *xcalloc(size_t n, const char *);
 extern void *xrealloc(void *, size_t n, const char *);
 #define xcalloc(n) xcalloc(n, __func__)
 #define xrealloc(p,n) xrealloc(p, n, __func__)
+
+/* growable buffer that stores its capacity in the allocated memory */
+#define xbnew_(n) (void *)(1 + (size_t *)xcalloc(sizeof(size_t) + (n)))
+#define xbcap_(p) ((size_t *)(p))[-1]
+static inline void
+xbgrow_(void **p, size_t n)
+{
+   if (!n) return;
+   if (!*p) { *p = xbnew_(n); xbcap_(*p) = n; assert(n>0); }
+   else if (xbcap_(*p) < n) {
+      size_t k = xbcap_(*p);
+      assert(k > 0);
+      do k *= 2; while (k < n);
+      *p = 1 + (size_t *)xrealloc(&xbcap_(*(p)), sizeof(size_t) + k);
+      xbcap_(*p) = k;
+   };
+}
+#define xbgrow(p, n) xbgrow_((void **)(p), (n) * sizeof**(p))
+#define xbpush(p, n, x) (xbgrow(p, (*(n) + 1)), (*(p))[(*(n))++] = (x))
+#define xbfree(p) ((p) ? free(&xbcap_(p)) : (void)0)
+
 struct arena *newarena(uint chunksiz);
 void *alloc(struct arena **, uint siz, uint align);
 static inline void *
@@ -341,6 +363,7 @@ alloccopy(struct arena **arena, const void *src, uint siz, uint align)
    return memcpy(alloc(arena, siz, align), src, siz);
 }
 void freearena(struct arena *);
+
 void vinit_(void **p, int *pcap, void *inlbuf, int cap, uint siz);
 void vpush_(void **p, int *pcap, uint *pn, uint siz);
 void *vpushn_(void **p, int *pcap, uint *pn, uint siz, const void *dat, uint ndat);
diff --git a/ir.c b/ir.c
index 9f6e86d..2c1fc06 100644
--- a/ir.c
+++ b/ir.c
@@ -27,12 +27,13 @@ void
 irinit(struct function *fn)
 {
    static struct call callsbuf[64];
-   static struct phi phisbuf[64];
+   static union ref *phisbuf[64];
    static struct irdat datsbuf[64];
 
    ninstr = 0;
    instrfreelist = -1;
    vinit(&calltab, callsbuf, arraylength(callsbuf));
+   for (int i = 0; i < phitab.n; ++i) xbfree(phitab.p[i]);
    vinit(&phitab, phisbuf, arraylength(phisbuf));
    vinit(&dattab, datsbuf, arraylength(datsbuf));
    if (naddrht >= arraylength(addrht)/2)
@@ -218,6 +219,23 @@ mkaddr(struct addr addr)
    return mkref(RMORE, addaddr(&addr));
 }
 
+static inline void
+addpred(struct block *blk, struct block *p)
+{
+   if (blk->npred == 0) {
+      blk->_pred0 = p;
+      ++blk->npred;
+      return;
+   }
+   if (blk->npred == 1) {
+      struct block *p0 = blk->_pred0;
+      blk->_pred = 0;
+      xbgrow(&blk->_pred, 4);
+      *blk->_pred = p0;
+   }
+   xbpush(&blk->_pred, &blk->npred, p);
+}
+
 static inline int
 newinstr(void)
 {
@@ -230,15 +248,6 @@ newinstr(void)
    return ninstr++;
 }
 
-union ref
-addinstr(struct function *fn, struct instr ins)
-{
-   int new = newinstr();
-   assert(fn->curblk != NULL);
-   instrtab[new] = ins;
-   vpush(&fn->curblk->ins, new);
-   return mkref(RTMP, new);
-}
 
 union ref
 insertinstr(struct block *blk, int idx, struct instr ins)
@@ -268,51 +277,7 @@ delinstr(struct block *blk, int idx)
    --blk->ins.n;
 }
 
-union ref
-addphi2(struct function *fn, enum irclass cls,
-        struct block *b1, union ref r1, struct block *b2, union ref r2)
-{
-   int new;
-   struct phi phi = { .n = 2, .cap = -1 };
-   struct instr ins = { Ophi, cls };
-
-   phi.blk = alloc(&fn->arena, 2*sizeof(struct block *) + 2*sizeof r1, 0);
-   phi.ref = (union ref *)((char *)phi.blk + 2*sizeof(struct block *));
-   phi.blk[0] = b1;
-   phi.ref[0] = r1;
-   phi.blk[1] = b2;
-   phi.ref[1] = r2;
-   vpush(&phitab, phi);
-   ins.l = mkref(RMORE, phitab.n-1);
-   assert(fn->curblk != NULL);
-   assert(fn->curblk->ins.n == 0);
-   new = newinstr();
-   instrtab[new] = ins;
-   vpush(&fn->curblk->phi, new);
-   return mkref(RTMP, new);
-}
-
-union ref
-addphi(struct function *fn, enum irclass cls, struct block **blk, union ref *ref, uint n)
-{
-   int new;
-   struct phi phi = { .n = n, .cap = -1 };
-   struct instr ins = { Ophi, cls };
-
-   assert(n > 0);
-   phi.blk = alloc(&fn->arena, n*sizeof(struct block *) + n*sizeof(union ref), 0);
-   phi.ref = (union ref *)((char *)phi.blk + n*sizeof(struct block *));
-   memcpy(phi.blk, blk, n * sizeof(struct block *));
-   memcpy(phi.ref, ref, n * sizeof(union ref));
-   vpush(&phitab, phi);
-   ins.l = mkref(RMORE, phitab.n-1);
-   assert(fn->curblk != NULL);
-   assert(fn->curblk->ins.n == 0);
-   new = newinstr();
-   instrtab[new] = ins;
-   vpush(&fn->curblk->phi, new);
-   return mkref(RTMP, new);
-}
+/** IR builders **/
 
 struct block *
 newblk(struct function *fn)
@@ -339,6 +304,36 @@ useblk(struct function *fn, struct block *blk)
    fn->curblk = blk;
 }
 
+union ref
+addinstr(struct function *fn, struct instr ins)
+{
+   int new = newinstr();
+   assert(fn->curblk != NULL);
+   instrtab[new] = ins;
+   vpush(&fn->curblk->ins, new);
+   return mkref(RTMP, new);
+}
+
+union ref
+addphi(struct function *fn, enum irclass cls, union ref *r)
+{
+   int new;
+   struct instr ins = { Ophi, cls };
+   union ref **prefs;
+
+   vpush(&phitab, NULL);
+   prefs = &phitab.p[phitab.n - 1];
+   xbgrow(prefs, fn->curblk->npred);
+   memcpy(*prefs, r, fn->curblk->npred * sizeof *r);
+   ins.l = mkref(RMORE, phitab.n-1);
+   assert(fn->curblk != NULL);
+   assert(fn->curblk->ins.n == 0);
+   new = newinstr();
+   instrtab[new] = ins;
+   vpush(&fn->curblk->phi, new);
+   return mkref(RTMP, new);
+}
+
 #define putjump(fn, j, arg0, arg1, T, F) \
    fn->curblk->jmp.t = j;                \
    fn->curblk->jmp.arg[0] = arg0;        \
@@ -350,14 +345,17 @@ useblk(struct function *fn, struct block *blk)
 void
 putbranch(struct function *fn, struct block *blk)
 {
-   assert(blk);
+   assert(fn->curblk && blk);
+   addpred(blk, fn->curblk);
    putjump(fn, Jb, NOREF, NOREF, blk, NULL);
 }
 
 void
 putcondbranch(struct function *fn, union ref arg, struct block *t, struct block *f)
 {
-   assert(t && f);
+   assert(fn->curblk && t && f);
+   addpred(t, fn->curblk);
+   addpred(f, fn->curblk);
    putjump(fn, Jb, arg, NOREF, t, f);
 }
 
@@ -369,13 +367,15 @@ putreturn(struct function *fn, union ref r0, union ref r1)
 
 #undef putjump
 
+/** 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) {
-      struct phi *phi = &phitab.p[instrtab[blk->phi.p[i]].l.i];
-      for (int i = 0; i < phi->n; ++i)
-         if (phi->ref[i].bits == to.bits) phi->ref[i] = from;
+      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) {
diff --git a/ir.h b/ir.h
index bdf422f..594b6d4 100644
--- a/ir.h
+++ b/ir.h
@@ -58,12 +58,6 @@ struct call {
    struct abiarg abiret[2];
 };
 
-struct phi {
-   struct block **blk;
-   union ref *ref;
-   int n, cap;
-};
-
 enum refkind {
    RNONE,
    RTMP,   /* reference to another instruction's result */
@@ -125,11 +119,16 @@ enum jumpkind {
 
 struct block {
    int id;
+   int npred;
+   union {
+      struct block *_pred0;
+      struct block **_pred;
+   };
+   struct block *lprev, *lnext;
    struct block *s1, *s2;
    vec_of(ushort) phi;
    vec_of(ushort) ins;
    struct { uchar t; union ref arg[2]; } jmp;
-   struct block *lprev, *lnext;
 };
 
 enum { MAXREGS = 64 };
@@ -194,7 +193,7 @@ extern const uchar siz2intcls[];
 extern struct instr instrtab[];
 extern struct xcon conht[];
 extern struct calltab {vec_of(struct call);} calltab;
-extern struct phitab {vec_of(struct phi);} phitab;
+extern struct phitab {vec_of(union ref *);} phitab;
 extern struct dattab {vec_of(struct irdat);} dattab;
 extern struct addr addrht[];
 #define insrescls(ins) (oiscmp((ins).op) ? KI4 : (ins).cls)
@@ -226,17 +225,19 @@ 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);
-union ref addinstr(struct function *, struct instr);
 union ref insertinstr(struct block *, int idx, struct instr);
 void delinstr(struct block *, int idx);
-union ref addphi2(struct function *, enum irclass cls,
-                  struct block *b1, union ref r1, struct block *b2, union ref r2);
-union ref addphi(struct function *, enum irclass cls, struct block **blk, union ref *ref, uint n);
+#define blkpred(blk, i) 0[(blk)->npred < 2 ? &(blk)->_pred0 : &(blk)->_pred[i]]
+
+/* IR builder functions */
+union ref addinstr(struct function *, struct instr);
+union ref addphi(struct function *, enum irclass, union ref []);
 struct block *newblk(struct function *);
 void useblk(struct function *, struct block *);
 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);
 
diff --git a/irdump.c b/irdump.c
index c936638..16f3063 100644
--- a/irdump.c
+++ b/irdump.c
@@ -104,15 +104,7 @@ dumpref(enum op o, union ref ref)
       prityp(ref2type(ref));
       break;
    case RMORE:
-      if (o == Ophi) {
-         struct phi *phi = &phitab.p[ref.i];
-         assert(phitab.n > ref.i);
-         for (int i = 0; i < phi->n; ++i) {
-            if (i) efmt(", ");
-            efmt("@%d ", phi->blk[i]->id);
-            dumpref(0, phi->ref[i]);
-         }
-      } else {
+      {
          const struct addr *addr = &addrht[ref.i];
          bool k = 0;
          efmt("addr [");
@@ -197,7 +189,15 @@ dumpblk(struct function *fn, struct block *blk)
    int i;
    efmt("  @%d:\n", blk->id);
    for (i = 0; i < blk->phi.n; ++i) {
-      dumpinst(&instrtab[blk->phi.p[i]]);
+      struct instr *phi = &instrtab[blk->phi.p[i]];
+      union ref *refs = phitab.p[phi->l.i];
+      efmt("    %s %%%d = phi ", clsname[phi->cls], blk->phi.p[i]);
+      for (int i = 0; i < blk->npred; ++i) {
+         if (i) efmt(", ");
+         efmt("@%d ", blkpred(blk, i)->id);
+         dumpref(0, refs[i]);
+      }
+      efmt("\n");
    }
    for (i = 0; i < blk->ins.n; ++i) {
       dumpinst(&instrtab[blk->ins.p[i]]);
diff --git a/regalloc.c b/regalloc.c
index a30ebe5..19df61c 100644
--- a/regalloc.c
+++ b/regalloc.c
@@ -368,16 +368,16 @@ regalloc(struct function *fn)
          }
       }
       for (int i = blk->phi.n - 1; i >= 0; --i) {
-         struct phi *phi;
+         union ref *phi;
          ins = &instrtab[blk->phi.p[i]];
          assert(ins->op == Ophi);
-         phi = &phitab.p[ins->l.i];
+         phi = phitab.p[ins->l.i];
          if (ins->reg) {
             /* introduce necessary moves in each pred,
              * XXX this doesn't work for backwards branches */
-            for (int i = 0; i < phi->n; ++i) {
-               struct instr mov = mkinstr(Omove, insrescls(*ins), mkref(RREG, ins->reg-1), phi->ref[i]);
-               insertinstr(phi->blk[i], phi->blk[i]->ins.n, mov);
+            for (int i = 0; i < blk->npred; ++i) {
+               struct instr mov = mkinstr(Omove, insrescls(*ins), mkref(RREG, ins->reg-1), phi[i]);
+               insertinstr(blkpred(blk, i), blkpred(blk, i)->ins.n, mov);
             }
          }
          def(&ra, ins, NULL, 0);
diff --git a/ssa.c b/ssa.c
index 0db9aaf..46e0741 100644
--- a/ssa.c
+++ b/ssa.c
@@ -30,9 +30,9 @@ ssauses(struct function *fn)
    do {
       for (int i = 0; i < blk->phi.n; ++i) {
          int ins = blk->phi.p[i];
-         struct phi *phi = &phitab.p[instrtab[ins].l.i];
-         for (int i = 0; i < phi->n; ++i) {
-            USE(phi->ref[i], 0, ins);
+         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->ins.n; ++i) {