phis?

6 files changed, 162 insertions, 139 deletions

diff --git a/ir.c b/ir.c
index d0866ef..f6cf3a6 100644
--- a/ir.c
+++ b/ir.c
@@ -8,15 +8,18 @@ const uchar siz2intcls[] = { [1] = KI4, [2] = KI4, [4] = KI4, [8] = KI8 };
 static vec_of(struct irdat) dats;
 struct instr instr[1<<14];
 static int ninstr;
-vec_of(struct ircall) calls;
+vec_of(struct call) calls;
+vec_of(struct phi) phis;
 
 void
 irinit(struct function *fn)
 {
-   static struct ircall callsbuf[64];
+   static struct call callsbuf[64];
+   static struct phi phisbuf[64];
 
    ninstr = 0;
    vinit(&calls, callsbuf, arraylength(callsbuf));
+   vinit(&phis, phisbuf, arraylength(phisbuf));
    if (!type2cls[TYINT]) {
       for (int i = TYBOOL; i <= TYUVLONG; ++i) {
          int siz = targ_primsizes[i];
@@ -54,13 +57,13 @@ addcon(const struct xcon *con)
    }
 }
 
-union irref
+/* union ref
 adddat(struct function *fn, const struct irdat *dat)
 {
    assert(dats.n < 1u<<29);
    vpush(&dats, *dat);
-   /* return mkref(RDAT, dats.n - 1); */
-}
+   return mkref(RDAT, dats.n - 1); 
+} */
 
 static void
 targwrite2(uchar *d, ushort x)
@@ -128,7 +131,7 @@ mkirtype(union type t)
    return (union irtype) { .isagg = 1, .dat = t.dat };
 }
 
-union irref
+union ref
 mkintcon(struct function *fn, enum irclass k, vlong i)
 {
    if (i < 1ll << 28 && i >= -(1ll << 28)) {
@@ -142,7 +145,7 @@ mkintcon(struct function *fn, enum irclass k, vlong i)
    }
 }
 
-union irref
+union ref
 mkfltcon(struct function *fn, enum irclass k, double f)
 {
    struct xcon con = { 0, k };
@@ -151,18 +154,18 @@ mkfltcon(struct function *fn, enum irclass k, double f)
    return mkref(RXCON, addcon(&con));
 }
 
-union irref
+union ref
 mksymref(struct function *fn, const char *s)
 {
    struct xcon con = { 1, KPTR, .sym = s };
    return mkref(RXCON, addcon(&con));
 }
 
-union irref
-mkcall(struct function *fn, union type fnty, uint narg, union irref *args, union irtype *typs)
+union ref
+mkcall(struct function *fn, union type fnty, uint narg, union ref *args, union irtype *typs)
 {
    const struct typedata *td = &typedata[fnty.dat];
-   struct ircall call = { narg, td->variadic ? td->nmemb : -1 };
+   struct call call = { narg, td->variadic ? td->nmemb : -1 };
 
    if (!td->kandr) assert(td->variadic ? narg >= td->nmemb : narg == td->nmemb);
    if (narg) {
@@ -172,10 +175,10 @@ mkcall(struct function *fn, union type fnty, uint narg, union irref *args, union
       memcpy(call.typs, typs, narg*sizeof *typs);
    }
    vpush(&calls, call);
-   return mkref(RCALL, calls.n-1);
+   return mkref(REXT, calls.n-1);
 }
 
-union irref
+union ref
 addinstr(struct function *fn, struct instr ins)
 {
    assert(ninstr < arraylength(instr));
@@ -185,6 +188,28 @@ addinstr(struct function *fn, struct instr ins)
    return mkref(RTMP, ninstr++);
 }
 
+union ref
+addphi2(struct function *fn, enum irclass cls,
+        struct block *b1, union ref r1, struct block *b2, union ref r2)
+{
+   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(&phis, phi);
+   ins.l = mkref(REXT, phis.n-1);
+   assert(ninstr < arraylength(instr));
+   assert(fn->curblk != NULL);
+   assert(fn->curblk->ins.n == 0);
+   instr[ninstr] = ins;
+   vpush(&fn->curblk->phi, ninstr);
+   return mkref(RTMP, ninstr++);
+}
+
 struct block *
 newblk(struct function *fn)
 {
@@ -209,7 +234,7 @@ useblk(struct function *fn, struct block *blk)
 }
 
 void
-putjump(struct function *fn, enum jumpkind j, union irref arg, struct block *t, struct block *f)
+putjump(struct function *fn, enum jumpkind j, union ref arg, struct block *t, struct block *f)
 {
    fn->curblk->jmp.t = j;
    fn->curblk->jmp.arg = arg;
diff --git a/ir.h b/ir.h
index 6b5446e..eee4859 100644
--- a/ir.h
+++ b/ir.h
@@ -42,18 +42,24 @@ struct xcon {
    };
 };
 
-struct ircall {
+struct call {
    short narg;
    short vararg; /* first variadic arg or -1 */
    union irtype *typs;
-   union irref *args;
+   union ref *args;
 };
 
-enum irrefkind {
-   RNONE, RTMP, RARG, RICON, RXCON, RSYM, RCALL
+struct phi {
+   struct block **blk;
+   union ref *ref;
+   int n, cap;
 };
 
-union irref {
+enum refkind {
+   RNONE, RTMP, RARG, RICON, RXCON, RSYM, REXT
+};
+
+union ref {
    struct { uint t : 3, idx : 29; };
    struct { signed _0: 3, i : 29; }; /* RICON */
    uint bits;
@@ -69,8 +75,7 @@ enum op {
 struct instr {
    uchar op;
    uchar cls;
-   union irref l;
-   union irref r;
+   union ref l, r;
 };
 
 enum jumpkind {
@@ -80,7 +85,8 @@ enum jumpkind {
 struct block {
    int id;
    struct block *s1, *s2;
-   struct { uchar t; union irref arg; } jmp;   
+   struct { uchar t; union ref arg; } jmp;   
+   vec_of(ushort) phi;
    vec_of(ushort) ins;
    struct block *lprev, *lnext;
 };
@@ -99,19 +105,21 @@ extern uchar type2cls[];
 extern uchar cls2siz[];
 extern const uchar siz2intcls[];
 void irinit(struct function *);
-#define NOREF ((union irref) {0})
-#define mkref(t, x) ((union irref) {{ (t), (x) }})
+#define NOREF ((union ref) {0})
+#define mkref(t, x) ((union ref) {{ (t), (x) }})
 #define mkzerocon() ((union irref){ RICON, 0 })
 union irtype mkirtype(union type);
-union irref mkintcon(struct function *, enum irclass, vlong);
-union irref mkfltcon(struct function *, enum irclass, double);
-union irref mksymref(struct function *, const char *);
+union ref mkintcon(struct function *, enum irclass, vlong);
+union ref mkfltcon(struct function *, enum irclass, double);
+union ref mksymref(struct function *, const char *);
 void conputdat(struct irdat *, uint off, enum typetag t, const void *dat);
-union irref mkcall(struct function *, union type fnty, uint narg, union irref *, union irtype *);
-union irref addinstr(struct function *, struct instr);
+union ref mkcall(struct function *, union type fnty, uint narg, union ref *, union irtype *);
+union ref addinstr(struct function *, struct instr);
+union ref addphi2(struct function *, enum irclass cls,
+                  struct block *b1, union ref r1, struct block *b2, union ref r2);
 struct block *newblk(struct function *);
 void useblk(struct function *, struct block *);
-void putjump(struct function *, enum jumpkind, union irref arg, struct block *t, struct block *f);
+void putjump(struct function *, enum jumpkind, union ref arg, struct block *t, struct block *f);
 void irdump(struct function *, const char *fname);
 
 /* vim:set ts=3 sw=3 expandtab: */
diff --git a/irdump.c b/irdump.c
index 7855244..f225431 100644
--- a/irdump.c
+++ b/irdump.c
@@ -2,7 +2,6 @@
 #include "ir.h"
 
 extern struct xcon conht[];
-extern vec_of(struct ircall) calls;
 
 static const char *clsname[] = {
    "?", "i4", "i8", "ptr", "f4", "f8"
@@ -24,10 +23,9 @@ prityp(union irtype typ)
 }
 
 static void
-dumpref(union irref ref)
+dumpref(enum op o, union ref ref)
 {
    struct xcon *con;
-   struct ircall *call;
    switch (ref.t) {
    case RTMP: efmt("%%%d", ref.idx); break;
    case RARG: efmt("%%arg%d", ref.idx); break;
@@ -44,16 +42,28 @@ dumpref(union irref ref)
       default: assert(0);
       }
       break;
-   case RCALL:
-      call = &calls.p[ref.idx];
-      for (int i = 0; i < call->narg; ++i) {
-         if (call->vararg == i) {
+   case REXT:
+      if (o == Ocall) {
+         extern vec_of(struct call) calls;
+         struct call *call = &calls.p[ref.idx];
+         for (int i = 0; i < call->narg; ++i) {
+            if (call->vararg == i) {
+               if (i > 0) efmt(", ");
+               efmt("..., ");
+            }
+            prityp(call->typs[i]);
+            efmt(" ");
+            dumpref(0, call->args[i]);
+         }
+      } else if (o == Ophi) {
+         extern vec_of(struct phi) phis;
+         struct phi *phi = &phis.p[ref.idx];
+         for (int i = 0; i < phi->n; ++i) {
             if (i > 0) efmt(", ");
-            efmt("..., ");
+            efmt("[.L%d ", phi->blk[i]->id);
+            dumpref(0, phi->ref[i]);
+            efmt("]");
          }
-         prityp(call->typs[i]);
-         efmt(" ");
-         dumpref(call->args[i]);
       }
       break;
    default: assert(!"ref");
@@ -84,7 +94,7 @@ dumpinst(const struct instr *ins)
    efmt("%s ", opname[ins->op]);
    for (i = 0; i < opnarg[ins->op]; ++i) {
       if (i) efmt(", ");
-      dumpref((&ins->l)[i]);
+      dumpref(ins->op, (&ins->l)[i]);
    }
    efmt("\n");
 }
@@ -95,12 +105,15 @@ dumpblk(struct block *blk)
    static const char *jnames[] = { 0, "b", "b", "ret", "rets" };
    static const uchar jnarg[] = { 0, 0, 1, 0, 1 };
    efmt("  .L%d:\n", blk->id);
+   for (int i = 0; i < blk->phi.n; ++i) {
+      dumpinst(&instr[blk->phi.p[i]]);
+   }
    for (int i = 0; i < blk->ins.n; ++i) {
       dumpinst(&instr[blk->ins.p[i]]);
    }
    efmt("    %s ", jnames[blk->jmp.t]);
    if (jnarg[blk->jmp.t]) {
-      dumpref(blk->jmp.arg);
+      dumpref(0, blk->jmp.arg);
       if (blk->s1) efmt(", ");
    }
    if (blk->s1 && blk->s2) efmt(".L%d, .L%d", blk->s1->id, blk->s2->id);
diff --git a/op.def b/op.def
index 915d832..290611c 100644
--- a/op.def
+++ b/op.def
@@ -58,3 +58,4 @@ _(store2,   2)
 _(store4,   2)
 _(store8,   2)
 _(call,     2)
+_(phi,      1)
diff --git a/parse.c b/parse.c
index e86663a..bc9af99 100644
--- a/parse.c
+++ b/parse.c
@@ -947,13 +947,13 @@ commaexpr(struct parser *pr)
 /* -> IR */
 /*********/
 
-static union irref exprvalue(struct function *, const struct expr *);
+static union ref exprvalue(struct function *, const struct expr *);
 
-static union irref
+static union ref
 expraddr(struct function *fn, const struct expr *ex)
 {
    struct decl *decl;
-   union irref r;
+   union ref r;
    struct instr ins;
 
    switch (ex->t) {
@@ -990,8 +990,8 @@ expraddr(struct function *fn, const struct expr *ex)
 
 }
 
-static union irref
-genload(struct function *fn, union type t, union irref ref)
+static union ref
+genload(struct function *fn, union type t, union ref ref)
 {
    struct instr ins = {0};
 
@@ -1008,8 +1008,8 @@ genload(struct function *fn, union type t, union irref ref)
    return addinstr(fn, ins);
 }
 
-static union irref
-genstore(struct function *fn, union type t, union irref ptr, union irref val)
+static union ref
+genstore(struct function *fn, union type t, union ref ptr, union ref val)
 {
    struct instr ins = {0};
 
@@ -1026,8 +1026,8 @@ genstore(struct function *fn, union type t, union irref ptr, union irref val)
    return addinstr(fn, ins);
 }
 
-static union irref
-cvt(struct function *fn, enum typetag to, enum typetag from, union irref ref)
+static union ref
+cvt(struct function *fn, enum typetag to, enum typetag from, union ref ref)
 {
    enum irclass kto = type2cls[to], kfrom = type2cls[from];
    struct instr ins = {0};
@@ -1056,8 +1056,8 @@ cvt(struct function *fn, enum typetag to, enum typetag from, union irref ref)
    return addinstr(fn, ins);
 }
 
-static union irref
-narrow(struct function *fn, enum irclass to, enum typetag tt, union irref ref)
+static union ref
+narrow(struct function *fn, enum irclass to, enum typetag tt, union ref ref)
 {
    struct instr ins;
    assert(isintt(tt) || tt == TYPTR);
@@ -1084,29 +1084,34 @@ ilog2(uint x) { /* assumes x is a power of 2 */
 #endif
 }
 
-union irref
-genptroff(struct function *fn, enum op op, uint siz, union irref ptr,
-          enum typetag tt, union irref idx)
+union ref
+genptroff(struct function *fn, enum op op, uint siz, union ref ptr,
+          enum typetag tt, union ref idx)
 {
    uint cls = type2cls[targ_sizetype];
-   union irref off;
+   union ref off;
    assert(siz);
+
    idx = cvt(fn, targ_sizetype, tt, idx);
    if (siz ==  1) off = idx;
+   else if (idx.t == RICON)
+      off = mkintcon(fn, cls, idx.i * siz);
    else if ((siz & siz-1) == 0) /* is power of 2 */
-      off = addinstr(fn, (struct instr) { Oshl, cls, idx, mkintcon(fn, cls, ilog2(siz)) });
+      off = addinstr(fn,
+            (struct instr) { Oshl, cls, .l = idx, .r = mkintcon(fn, cls, ilog2(siz)) });
    else
-      off = addinstr(fn, (struct instr) { Omul, cls, idx, mkintcon(fn, cls, siz) });
+      off = addinstr(fn,
+            (struct instr) { Omul, cls, .l = idx, .r = mkintcon(fn, cls, siz) });
    assert(in_range(op, Oadd, Osub));
-   return addinstr(fn, (struct instr) { op, KPTR, ptr, off });
+   return addinstr(fn, (struct instr) { op, KPTR, .l = ptr, .r = off });
 }
 
-union irref
-genptrdiff(struct function *fn, uint siz, union irref a, union irref b)
+union ref
+genptrdiff(struct function *fn, uint siz, union ref a, union ref b)
 {
    uint cls = type2cls[targ_ptrdifftype];
    assert(siz > 0);
-   a = addinstr(fn, (struct instr) { Osub, cls, a, b });
+   a = addinstr(fn, (struct instr) { Osub, cls, .l = a, .r = b });
    if (siz == 1) return a;
    else if ((siz & siz-1) == 0) /* is power of 2 */
       return addinstr(fn, (struct instr) { Osar, cls, a, mkintcon(fn, cls, ilog2(siz)) });
@@ -1114,11 +1119,12 @@ genptrdiff(struct function *fn, uint siz, union irref a, union irref b)
       return addinstr(fn, (struct instr) { Odiv, cls, a, mkintcon(fn, cls, siz) });
 }
 
-static union irref
+static union ref
 exprvalue(struct function *fn, const struct expr *ex)
 {
    union type ty;
-   union irref r, q;
+   union ref r, q;
+   struct block *tr, *fl, *end;
    enum irclass cls = type2cls[ex->ty.t];
    struct instr ins = {0};
    int swp = 0;
@@ -1315,9 +1321,9 @@ exprvalue(struct function *fn, const struct expr *ex)
    case ECALL:
       {
          const struct typedata *td = &typedata[sub[0].ty.dat];
-         union irref argsbuf[10];
+         union ref argsbuf[10];
          union irtype typbuf[10];
-         vec_of(union irref) args = VINIT(argsbuf, arraylength(argsbuf));
+         vec_of(union ref) args = VINIT(argsbuf, arraylength(argsbuf));
          vec_of(union irtype) typs = VINIT(typbuf, arraylength(typbuf));
          ins.op = Ocall;
          assert(isscalar(ex->ty) || ex->ty.t == TYVOID);
@@ -1334,6 +1340,42 @@ exprvalue(struct function *fn, const struct expr *ex)
          vfree(&typs);
          return addinstr(fn, ins);
       }
+   case ECOND:
+      r = exprvalue(fn, &sub[0]);
+      tr = newblk(fn);
+      fl = newblk(fn);
+      end = newblk(fn);
+      putjump(fn, Jbcnd, r, tr, fl);
+      useblk(fn, tr);
+      r = cvt(fn, ex->ty.t, sub[1].ty.t, exprvalue(fn, &sub[1]));
+      putjump(fn, Jb, NOREF, end, NULL);
+      useblk(fn, fl);
+      q = cvt(fn, ex->ty.t, sub[2].ty.t, exprvalue(fn, &sub[2]));
+      putjump(fn, Jb, NOREF, end, NULL);
+      useblk(fn, end);
+      return addphi2(fn, type2cls[ex->ty.t], tr, r, fl, q);
+   case ELOGAND:
+      r = exprvalue(fn, &sub[0]);
+      fl = fn->curblk;
+      tr = newblk(fn);
+      end = newblk(fn);
+      putjump(fn, Jbcnd, r, tr, end);
+      useblk(fn, tr);
+      q = cvt(fn, TYBOOL, sub[1].ty.t, exprvalue(fn, &sub[1]));
+      putjump(fn, Jb, NOREF, end, NULL);
+      useblk(fn, end);
+      return addphi2(fn, KI4, fl, mkref(RICON, 0), tr, q);
+   case ELOGIOR:
+      r = exprvalue(fn, &sub[0]);
+      tr = fn->curblk;
+      fl = newblk(fn);
+      end = newblk(fn);
+      putjump(fn, Jbcnd, r, end, fl);
+      useblk(fn, fl);
+      q = cvt(fn, TYBOOL, sub[1].ty.t, exprvalue(fn, &sub[1]));
+      putjump(fn, Jb, NOREF, end, NULL);
+      useblk(fn, end);
+      return addphi2(fn, KI4, tr, mkref(RICON, 1), fl, q);
    case ESEQ:
       (void)exprvalue(fn, &sub[0]);
       return exprvalue(fn, &sub[1]);
@@ -1354,7 +1396,7 @@ stmt(struct parser *pr, struct function *fn)
 {
    struct block *tr, *fl, *end, *begin;
    struct expr ex;
-   union irref r;
+   union ref r;
    bool terminates = 0;
    const bool doemit = fn->curblk;
 
diff --git a/test.c b/test.c
index ff9b430..461d42f 100644
--- a/test.c
+++ b/test.c
@@ -9,78 +9,12 @@ boop
 #endif
 int glob [ wow+wow];
 
-int add (int x, int y) {
-    return x + y + *glob;
-}
-
 struct foo {
-    struct foo *foo;
-    struct n0 {
-        char z;
-        struct n1 {
-            char q;
-            struct n2 {
-                int ww;
-            } n2;
-        } n1;
-    } n0;
-    union {
-        struct { short x, y; };
-        int xy;
-    };
-    char flex[];
-};
-
-int foop(struct foo *foo) {
-    if (foo->foo) foo = foo->foo;
-    ++foo->n0.n1.n2.ww;
-    int xy = (*foo).xy;
-    foo->flex[2] *= 5;
-    if (foo->x)return xy;
-    return foo->y;
-}
-
-int abs(int x){
-    return (x ^ x >> 3\
-1) - (x >> 31);
-}
-
-int popcnt(unsigned x) {
-    int n = 0;
-    while (x) x >>= 1, n++;
-    return n + sizeof "ab\r\
-c";
-}
-
-struct f {
-    char x[(1<<12)-1];
+    int x, y, z;
 };
 
-int diff(struct f *x, struct f *y)
-{
-    x += 3;
-    --x;
-    return x - y;
-}
-
-_Bool narrow(int x)
-{
-    return (float) x;
-}
-
-#define xx 2
-
-int waaa[xx == 0 ?  'Z'
-        : xx == 1? 'O'
-        : xx == 2? 'T'
-        : '?'];
-
-extern int printf(char *, ...);
-int main() {
-    unsigned char x = 255;
-    int k = x += 1;
-    1+waaa;
-    return abs(k);
-}
+int test0(struct foo *foo) { return foo->x ? foo->y : foo->z; }
+int test1(int x, int y, int z) { return x && y || z; }
+int test2(int x, int y, int z) { return x || y && z; }
 
 //