add basic mem2reg

promotes uniform stack slots to temporaries

currently only for immutable variables, next thing to implement is ssa
construction

8 files changed, 221 insertions, 14 deletions

diff --git a/Makefile b/Makefile
index 96b49f4..603ae7a 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,5 @@
-SRC=main.c io.c mem.c c.c lex.c type.c targ.c eval.c ir.c irdump.c intrin.c abi0.c regalloc.c amd64/sysv.c amd64/isel.c amd64/emit.c obj.c elf.c
+SRC=main.c io.c mem.c c.c lex.c type.c targ.c eval.c ir.c irdump.c ssa.c intrin.c abi0.c \
+	optmem.c regalloc.c amd64/sysv.c amd64/isel.c amd64/emit.c obj.c elf.c
 CFLAGS=-Wall -std=c11 -pedantic
 OBJ=$(patsubst %.c,obj/%.o,$(SRC))
 DEP=$(OBJ:.o=.d)
diff --git a/common.h b/common.h
index ec2c6d7..a1cc1f8 100644
--- a/common.h
+++ b/common.h
@@ -114,6 +114,7 @@ struct option {
       struct {
          bool p : 1, /* after parsing */
               a : 1, /* after abi0 */
+              m : 1, /* after mem */
               i : 1, /* after isel */
               r : 1; /* after regalloc */
       };
diff --git a/ir.c b/ir.c
index 2a7de47..9f6e86d 100644
--- a/ir.c
+++ b/ir.c
@@ -413,6 +413,7 @@ irfini(struct function *fn)
    extern int nerror;
    if (!nerror) {
       abi0(fn);
+      mem2reg(fn);
       lowerintrin(fn);
       mctarg->isel(fn);
       regalloc(fn);
diff --git a/ir.h b/ir.h
index 8208dea..e34cb6a 100644
--- a/ir.h
+++ b/ir.h
@@ -113,6 +113,12 @@ 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,
 };
@@ -235,9 +241,13 @@ void replref(struct function *, struct block *, int, union ref from, union ref t
 
 void irdump(struct function *);
 
-void lowerintrin(struct function *);
+struct uses *ssauses(struct function *);
+void freeuses(struct uses *, int n);
+
 void abi0(struct function *);
 void abi0_call(struct function *, struct instr *, struct block *blk, int *curi);
+void mem2reg(struct function *);
+void lowerintrin(struct function *);
 void regalloc(struct function *);
 
 /* vim:set ts=3 sw=3 expandtab: */
diff --git a/main.c b/main.c
index 5103117..6f9e0dc 100644
--- a/main.c
+++ b/main.c
@@ -117,6 +117,7 @@ optparse(char **args)
          case 'a': ccopt.dbg.a = 1; break;
          case 'i': ccopt.dbg.i = 1; break;
          case 'r': ccopt.dbg.r = 1; break;
+         case 'm': ccopt.dbg.m = 1; break;
          default: warn(NULL, "-d: invalid debug flag %'c", *arg);
          }
       } else if (*arg == 'o') {
diff --git a/optmem.c b/optmem.c
new file mode 100644
index 0000000..ba81cd2
--- /dev/null
+++ b/optmem.c
@@ -0,0 +1,99 @@
+#include "ir.h"
+
+static const uchar loadszcls[] = {
+   [Oloads1 - Oloads1] = 1|KI4<<4, [Oloadu1 - Oloads1] = 1|KI4<<4,
+   [Oloads2 - Oloads1] = 2|KI4<<4, [Oloadu2 - Oloads1] = 2|KI4<<4,
+   [Oloads4 - Oloads1] = 4|KI4<<4, [Oloadu4 - Oloads1] = 4|KI4<<4,
+   [Oloadi8 - Oloads1] = 8|KI8<<4,
+   [Oloadf4 - Oloads1] = 4|KF4<<4,
+   [Oloadf8 - Oloads1] = 8|KF8<<4,
+};
+static const uchar load2ext[] = {
+   [Oloads1 - Oloads1] = Oexts1, [Oloadu1 - Oloads1] = Oextu1,
+   [Oloads2 - Oloads1] = Oexts2, [Oloadu2 - Oloads1] = Oextu2,
+   [Oloads4 - Oloads1] = Oexts4, [Oloadu4 - Oloads1] = Oextu4,
+   [Oloadi8 - Oloads1] = Ocopy,
+};
+#define loadsz(o) (loadszcls[(o) - Oloads1] & 0xF)
+#define loadcls(o) (loadszcls[(o) - Oloads1] >> 4)
+#define load2ext(o) (load2ext[(o) - Oloads1])
+#define storesz(o) (1 << ((o) - Ostore1))
+
+void
+mem2reg(struct function *fn)
+{
+   extern int ninstr;
+   struct uses *uses = ssauses(fn);
+   struct block *blk = fn->entry;
+
+   do {
+      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];
+         
+         if (!oisalloca(ins->op)) continue;
+         for (use = uses[t].use, uend = &uses[t].use[uses[t].nuse]; use < uend; ++use) {
+            struct instr *m;
+            
+            if (use->isjmp) goto Next;
+            m = &instrtab[use->ins];
+            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
+            && (!sz || sz == storesz(m->op))) {
+               sz = storesz(m->op);
+               ++ndef;
+               continue;
+            }
+            goto Next;
+         }
+         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];
+
+            if (oisstore(m->op)) {
+               if (sz < 4) {
+                  *m = mkinstr(ext, KI4, m->r);
+                  var = mkref(RTMP, use->ins);
+               } else {
+                  var = m->r;
+                  *m = mkinstr(Onop,0,);
+               }
+            } else if (oisload(m->op)) {
+               if (!var.t) /* use before def */
+                  goto Next;
+               *m = mkinstr(Ocopy, k, var);
+            }
+         }
+         
+      Next:;
+      }
+   } while ((blk = blk->lnext) != fn->entry);
+
+   freeuses(uses, ninstr);
+   if (ccopt.dbg.m) {
+      efmt("<< After mem2reg >>\n");
+      irdump(fn);
+   }
+}
+
+
+/* vim:set ts=3 sw=3 expandtab: */
diff --git a/regalloc.c b/regalloc.c
index 2cbfd4c..6f08b5b 100644
--- a/regalloc.c
+++ b/regalloc.c
@@ -28,7 +28,7 @@ addstkslotref(union ref inst)
    vpush(&stkslotrefs, &instrtab[inst.i].l);
 }
 
-static int allocreg(struct rega *ra, enum irclass cls, union ref ref, int excl);
+static int allocreg(struct rega *ra, enum irclass cls, union ref ref, uvlong excl);
 
 #if 0
 #define DBG efmt
@@ -75,7 +75,7 @@ def(struct rega *ra, struct instr *ins, struct block *blk, int curi)
             }
          }
          if (reg < 0)
-            reg = allocreg(ra, insrescls(*ins), mkref(RTMP, var), -1);
+            reg = allocreg(ra, insrescls(*ins), mkref(RTMP, var), 0);
          store = mkinstr(Ostore1 + ilog2(cls2siz[insrescls(*ins)]), 0,
                          mkref(RICON, astk.a*8), mkref(RREG, reg));
          DBG("-- unspill %%%d s%d -> %s\n", var, astk.a, mctarg->rnames[ins->reg+1]);
@@ -115,7 +115,7 @@ take(struct rega *ra, int reg, union ref ref) {
 }
 
 static int
-allocreg(struct rega *ra, enum irclass cls, union ref ref, int excl)
+allocreg(struct rega *ra, enum irclass cls, union ref ref, uvlong excl)
 {
    int r0, rend, reg;
 
@@ -129,7 +129,7 @@ allocreg(struct rega *ra, enum irclass cls, union ref ref, int excl)
    } else assert(0);
    for (reg = r0; reg < rend; ++reg) {
       if (bstest(mctarg->rglob, reg)) continue;
-      if (reg != excl && !ra->regs[reg].t) {
+      if (!(excl >> reg & 1) && !ra->regs[reg].t) {
          take(ra, reg, ref);
          return reg;
       }
@@ -194,8 +194,8 @@ forcetake(struct rega *ra, int reg, union ref ref, struct block *blk, int curi)
        * we need to explictly exclude it from the pool of rename registers
        * e.g.: given 'R0 = copy R1'; if R1 => %x, we need to prevent renaming %x => R0
        */
-      int excl = instrtab[blk->ins.p[curi]].reg-1;
-      int rename = allocreg(ra, isgpr(reg) ? KI4 : KF4, ra->regs[reg], excl);
+      uvlong excl = instrtab[blk->ins.p[curi]].reg;
+      int rename = allocreg(ra, isgpr(reg) ? KI4 : KF4, ra->regs[reg], excl ? 1ull<<(excl-1) : 0);
       if (ccopt.dbg.r)DBG("-- rename %%%d %s -> %s\n", var, mctarg->rnames[reg], mctarg->rnames[rename]);
       /* introduce move from rename -> original (since we allocate backwards) */
       insertinstr(blk, ++curi, mkmove(insrescls(instrtab[var]), reg, rename));
@@ -215,7 +215,7 @@ static void
 use(struct rega *ra, struct block *blk, int curi, enum op op, int hint, union ref *ref, union ref other)
 {
    struct instr *ins;
-   int excl = other.t == RREG ? other.i : -1;
+   uvlong excl = other.t == RREG ? 1ull<<other.i : 0;
 
    if (ref->t == RMORE) {
       struct addr addr = addrht[ref->i];
@@ -224,13 +224,12 @@ use(struct rega *ra, struct block *blk, int curi, enum op op, int hint, union re
       *ref = mkaddr(addr);
       return;
    } else if (ref->t == RREG) {
-      assert(ref->i != excl);
+      assert(!(excl >> hint & 1));
       forcetake(ra, ref->i, *ref, blk, curi);
    }
    if (ref->t != RTMP) return;
 
    ins = &instrtab[ref->i];
-   if (oisalloca(ins->op)) return;
    if (!ins->cls) return;
    if (!ins->reg) {
       int s = -1;
@@ -238,9 +237,10 @@ use(struct rega *ra, struct block *blk, int curi, enum op op, int hint, union re
          s = ra->allocs[ref->i].a;
 
       assert(ins->op != Ocall);
+      if (ins->r.t == RREG && ins->inplace) excl |= 1ull<<ins->r.i;
       if (hint == -1 && ins->op == Ocopy && ins->l.t == RREG) /* for '%x = copy Rx', hint %x to use Rx */
          hint = ins->l.i;
-      if (hint != -1 && hint != excl && !ra->regs[hint].t) {
+      if (hint != -1 && !(excl >> hint & 1) && !ra->regs[hint].t) {
          take(ra, hint, *ref);
          ins->reg = hint + 1;
       } else {
@@ -317,8 +317,13 @@ regalloc(struct function *fn)
                if (ins->r.bits != ins->l.bits)
                   use(&ra, blk, i, ins->op, hint1, &ins->r, NOREF);
             } else {
-               if (ins->l.t) use(&ra, blk, i, ins->op, hint0, &ins->l, ins->r);
-               if (ins->r.t) use(&ra, blk, i, ins->op, hint1, &ins->r, NOREF);
+               if (ins->r.t == RREG) {
+                  use(&ra, blk, i, ins->op, hint0, &ins->r, NOREF);
+                  use(&ra, blk, i, ins->op, hint0, &ins->l, ins->r);
+               } else {
+                  if (ins->l.t) use(&ra, blk, i, ins->op, hint0, &ins->l, ins->r);
+                  if (ins->r.t) use(&ra, blk, i, ins->op, hint1, &ins->r, NOREF);
+               }
             }
          } else {
             struct call *call = &calltab.p[ins->r.i];
diff --git a/ssa.c b/ssa.c
new file mode 100644
index 0000000..0db9aaf
--- /dev/null
+++ b/ssa.c
@@ -0,0 +1,89 @@
+#include "ir.h"
+#include <stdint.h>
+
+struct uses *
+ssauses(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)
+
+   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);
+         }
+      }
+      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);
+      }
+      USE(blk->jmp.arg[0], 1, blk->id);
+      USE(blk->jmp.arg[1], 1, blk->id);
+   } 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: */