IR: mark free'd instructions as such

That way they are not copied when inlining.
Also rename ninstr -> ninstrtab. opnarg -> opnoper

8 files changed, 54 insertions, 44 deletions

diff --git a/src/ir.c b/src/ir.c
index f0d58b2..4f3a43d 100644
--- a/src/ir.c
+++ b/src/ir.c
@@ -20,7 +20,7 @@ const char *opnames[] = {
 #undef _
 };
 
-const uchar opnarg[] = {
+const uchar opnoper[] = {
    0,
 #define _(o,n) n,
 #include "ir_op.def"
@@ -29,7 +29,7 @@ const uchar opnarg[] = {
 
 Instr instrtab[MAXINSTR];
 IRUse *instruse[MAXINSTR];
-int ninstr;
+int ninstrtab, nfreeinstr;
 static int instrfreelist;
 static IRUse *usefreelist;
 static Arena **usearena;
@@ -53,7 +53,8 @@ irinit(Function *fn)
 
    assert(fn->arena && !fn->passarena);
 
-   ninstr = 0;
+   ninstrtab = 0;
+   nfreeinstr = 0;
    instrfreelist = -1;
    usefreelist = NULL;
    usearena = fn->arena;
@@ -376,16 +377,27 @@ allocinstr(void)
    int t;
    if (instrfreelist != -1) {
       t = instrfreelist;
-      memcpy(&instrfreelist, &instrtab[t], sizeof(int));
+      instrfreelist = instrtab[t].l.i;
+      instrtab[t].l = mkref(RXXX, 0);
+      --nfreeinstr;
       if (instruse[t]) deluses(t);
    } else {
-      assert(ninstr < countof(instrtab));
-      t = ninstr++;
+      assert(ninstrtab < countof(instrtab));
+      t = ninstrtab++;
       instruse[t] = NULL;
    }
    return t;
 }
 
+static inline void
+freeinstr(int t)
+{
+   instrtab[t].op = Oxxx;
+   instrtab[t].l = mkref(RXXX, instrfreelist);
+   instrfreelist = t;
+   ++nfreeinstr;
+}
+
 void
 adduse(Block *ublk, int ui, Ref r) {
    if (r.t != RTMP) return;
@@ -426,7 +438,7 @@ filluses(Function *fn)
 {
    Block *blk = fn->entry;
 
-   for (int i = 0; i < ninstr; ++i)
+   for (int i = 0; i < ninstrtab; ++i)
       deluses(i);
 
    do {
@@ -535,6 +547,8 @@ replcuses(Ref from, Ref to)
       if (use->u == USERJUMP) {
          u = &use->blk->jmp.arg[0];
          n = 2;
+      } else if (!instrtab[use->u].op) { /* dead */
+         continue;
       } else if (instrtab[use->u].op == Ophi) {
          u = phitab.p[instrtab[use->u].l.i];
          n = use->blk->npred;
@@ -576,8 +590,7 @@ delinstr(Block *blk, int idx)
    for (int i = 0; i < 2; ++i) {
       deluse(blk, t, (&instrtab[t].l)[i]);
    }
-   memcpy(&instrtab[t], &instrfreelist, sizeof(int));
-   instrfreelist = t;
+   freeinstr(t);
    deluses(t);
    for (int i = idx; i < blk->ins.n - 1; ++i)
       blk->ins.p[i] = blk->ins.p[i + 1];
@@ -589,8 +602,7 @@ delphi(Block *blk, int idx)
 {
    int t = blk->phi.p[idx];
    assert(idx >= 0 && idx < blk->phi.n);
-   memcpy(&instrtab[t], &instrfreelist, sizeof(int));
-   instrfreelist = t;
+   freeinstr(t);
    deluses(t);
    for (int i = idx; i < blk->phi.n - 1; ++i)
       blk->phi.p[i] = blk->phi.p[i + 1];
@@ -605,15 +617,13 @@ delnops(Block *blk)
    while (blk->ins.n > 0 && instrtab[t = blk->ins.p[blk->ins.n - 1]].op == Onop) {
       --blk->ins.n;
       deluses(t);
-      memcpy(&instrtab[t], &instrfreelist, sizeof(int));
-      instrfreelist = t;
+      freeinstr(t);
    }
    /* delete rest of nops */
    for (i = blk->ins.n - 2, n = 0; i >= 0; --i) {
       if (instrtab[t = blk->ins.p[i]].op == Onop) {
          deluses(t);
-         memcpy(&instrtab[t], &instrfreelist, sizeof(int));
-         instrfreelist = t;
+         freeinstr(t);
          ++n;
       } else if (n) {
          memmove(blk->ins.p+i+1, blk->ins.p+i+1+n, (blk->ins.n - n - i - 1)*sizeof *blk->ins.p);
@@ -669,6 +679,7 @@ irfini(Function *fn)
    }
    if (ccopt.o >= OPT1) {
       doinline(fn);
+      freearena(fn->passarena);
       filldom(fn);
       if (!(fn->prop & FNUSE)) filluses(fn);
       cselim(fn);
diff --git a/src/ir.h b/src/ir.h
index 7c372bb..2d7cb42 100644
--- a/src/ir.h
+++ b/src/ir.h
@@ -106,7 +106,7 @@ enum op {
 #define oisstore(o) in_range(o, Ostorei8, Ostoref64)
 #define oisload(o) in_range(o, Oloads8, Oloadf64)
 extern const char *opnames[];
-extern const uchar opnarg[];
+extern const uchar opnoper[];
 
 enum intrin {
    INxxx,
diff --git a/src/ir_abi0.c b/src/ir_abi0.c
index 61a310f..74a9d62 100644
--- a/src/ir_abi0.c
+++ b/src/ir_abi0.c
@@ -235,8 +235,9 @@ patcharg(Block *blk, int *icall, IRCall *call,
          return 1;
       } else { /* aggregate in registers */
          Ref r[2];
+         IRType typ = ref2type(arg->l);
          delinstr(blk, arginst);
-         load2regs(r, ref2type(arg->l), arg->r, nabi, abi, r2off, blk, &arginst);
+         load2regs(r, typ, arg->r, nabi, abi, r2off, blk, &arginst);
          for (int i = 0; i < nabi; ++i)
             insertinstr(blk, arginst++, mkinstr2(Oarg, 0, mktyperef(abi[i].ty), r[i]));
          *icall = arginst + (call->narg - argidx - 1);
diff --git a/src/ir_cse.c b/src/ir_cse.c
index 6007f8c..8e1805d 100644
--- a/src/ir_cse.c
+++ b/src/ir_cse.c
@@ -12,7 +12,7 @@ insequ(const Instr *a, const Instr *b)
 {
    if (a->op != b->op) return 0;
    enum op op = a->op;
-   switch (opnarg[op]) {
+   switch (opnoper[op]) {
    default: assert(0);
    case 2: if (a->r.bits != b->r.bits) return 0;
    case 1: if (a->l.bits != b->l.bits) return 0;
@@ -68,8 +68,8 @@ void
 cselim(Function *fn)
 {
    FREQUIRE(FNUSE | FNRPO | FNDOM | FNBLKID);
-   extern int ninstr;
-   for (ninsht = 32; ninsht <= ninstr; ninsht *= 2) ;
+   extern int ninstrtab;
+   for (ninsht = 32; ninsht <= ninstrtab; ninsht *= 2) ;
    insht = allocz(fn->passarena, ninsht * sizeof *insht, 0);
    int memno = 0, cutoff = 0;
    Block *blk = fn->entry;
diff --git a/src/ir_dump.c b/src/ir_dump.c
index 89d34d4..4c18a70 100644
--- a/src/ir_dump.c
+++ b/src/ir_dump.c
@@ -210,7 +210,7 @@ dumpinst(const Instr *ins)
       if (oiscmp(ins->op))
          bfmt(out, "%s ", clsname[ins->cls]);
    }
-   for (i = 0; i < opnarg[ins->op]; ++i) {
+   for (i = 0; i < opnoper[ins->op]; ++i) {
       if (i) bfmt(out, ", ");
       if (i == 1 && (ins->op == Ocall || ins->op == Ointrin)) {
          dumpcall(&calltab.p[ins->r.i]);
diff --git a/src/ir_inliner.c b/src/ir_inliner.c
index db89479..c1c36e2 100644
--- a/src/ir_inliner.c
+++ b/src/ir_inliner.c
@@ -1,7 +1,7 @@
 #include "ir.h"
 
 typedef struct SavedFunc {
-   uint ninstr;
+   uint ninstrtab;
    Instr *instrtab;
    IRCon *contab;
    IRCall *calltab;
@@ -22,12 +22,12 @@ bool
 maybeinlinee(Function *fn)
 {
    static Arena *savearena;
-   extern int ninstr;
+   extern int ninstrtab, nfreeinstr;
 
    // TODO better heuristics
    if (ccopt.o < OPT1) return 0;
    if (!fn->inlin && ccopt.o < OPT2) return 0;
-   if (ninstr > MAX_INLINED_FN_NINS) return 0;
+   if (ninstrtab - nfreeinstr > MAX_INLINED_FN_NINS) return 0;
    if (fn->nblk > MAX_INLINED_FN_NBLK) return 0;
    for (int i = 0; i < fn->nabiarg; ++i) {
       /* TODO inlining functions with stack args */
@@ -80,7 +80,7 @@ maybeinlinee(Function *fn)
       b->lnext = b->lnext == fn->entry ? NULL : bmap[b->lnext->id];
    } while ((b = b->lnext));
    
-   sv->instrtab = alloccopy(&savearena, instrtab, sizeof *instrtab * (sv->ninstr = ninstr), 0);
+   sv->instrtab = alloccopy(&savearena, instrtab, sizeof *instrtab * (sv->ninstrtab = ninstrtab), 0);
    sv->contab = alloccopy(&savearena, contab.p, sizeof *contab.p * contab.n, 0);
    if (calltab.n) {
       sv->calltab = alloccopy(&savearena, calltab.p, sizeof *calltab.p * calltab.n, 0);
@@ -148,16 +148,14 @@ inlcall(Function *fn, Block *blk, int curi, SavedFunc *sv)
    }
 
    Block *bmap[MAX_INLINED_FN_NBLK];
-   short instrmap[MAX_INLINED_FN_NINS];
+   short *instrmap = alloc(fn->passarena, sv->ninstrtab * sizeof *instrmap, 0);
    for (Block *b = sv->entry; b; b = b->lnext) {
       bmap[b->id] = newblk(fn);
    }
-   for (int i = 0; i < sv->ninstr; ++i) {
-      /* TODO don't wastefully allocate for tombstone instructions
-       * - mark instructions some way when they are freed (put in instrfreelist)
-       * */
+   for (int i = 0; i < sv->ninstrtab; ++i) {
       int allocinstr(void);
-      instrmap[i] = allocinstr();
+      if (sv->instrtab[i].op)
+         instrmap[i] = allocinstr();
    }
 
    exit->npred = 0;
diff --git a/src/ir_regalloc.c b/src/ir_regalloc.c
index ec1802d..3c2820b 100644
--- a/src/ir_regalloc.c
+++ b/src/ir_regalloc.c
@@ -85,13 +85,13 @@ liveuse(BitSet *defined, Instr *ins, Ref *r, Block *blk)
 static void
 fixlive(Function *fn)
 {
-   extern int ninstr;
+   extern int ninstrtab;
    Block *blk = fn->entry;
    BitSet definedbuf[4] = {0};
    BitSet *defined = definedbuf;
 
-   if (BSSIZE(ninstr) >= countof(definedbuf))
-      defined = xcalloc(sizeof *defined * BSSIZE(ninstr));
+   if (BSSIZE(ninstrtab) >= countof(definedbuf))
+      defined = xcalloc(sizeof *defined * BSSIZE(ninstrtab));
    npendingphi = 0;
 
    do {
@@ -597,10 +597,10 @@ defreg(RegAlloc *ra, int reg, int pos) {
 static void
 buildintervals(RegAlloc *ra)
 {
-   extern int ninstr;
+   extern int ninstrtab;
    Block *blk, *last;
    BitSet **livein = alloc(ra->arena, ra->fn->nblk * sizeof *livein, 0);
-   size_t bssize = BSSIZE(ninstr);
+   size_t bssize = BSSIZE(ninstrtab);
    struct Loop {
       struct Loop *next;
       Block *hdr, *end;
@@ -608,8 +608,8 @@ buildintervals(RegAlloc *ra)
    } *loops = NULL;
    for (int i = 0; i < ra->fn->nblk; ++i)
       livein[i] = allocz(ra->arena, bssize * sizeof *livein[i], 0);
-   ra->intertab = allocz(ra->arena, ninstr * sizeof *ra->intertab, 0);
-   ra->ninter = ninstr;
+   ra->intertab = allocz(ra->arena, ninstrtab * sizeof *ra->intertab, 0);
+   ra->ninter = ninstrtab;
 
    uint n = numberinstrs(ra->fn);
    assert((ushort)n == n && "too many instrs for Range");
@@ -724,7 +724,7 @@ buildintervals(RegAlloc *ra)
             nqueue = 1;
             queue[0] = ins->r;
          } else {
-            switch ((nqueue = opnarg[ins->op])) {
+            switch ((nqueue = opnoper[ins->op])) {
             case 3: queue[2] = ins->oper[2];
             case 2: queue[1] = ins->oper[1];
             case 1: queue[0] = ins->oper[0];
@@ -801,7 +801,7 @@ buildintervals(RegAlloc *ra)
    } while ((blk = blk->lprev) != last);
 
    if (ccopt.dbg.r) {
-      for (int var = 0; var < ninstr; ++var) {
+      for (int var = 0; var < ninstrtab; ++var) {
          Interval *it = &ra->intertab[var];
          if (!it->nrange) continue;
          DBG("lifetime of %%%d: ", var);
@@ -982,7 +982,7 @@ linearscan(RegAlloc *ra)
          }
       }
       /* for 2-address instrs, exclude reg from 2nd arg (unless arg#1 == arg#2) */
-      if (ins->inplace && opnarg[ins->op] == 2) {
+      if (ins->inplace && opnoper[ins->op] == 2) {
          int xreg;
          if (ins->r.t == RREG) rsset(&excl, ins->r.i);
          else if (ins->r.t == RTMP && (xreg = instrtab[ins->r.i].reg)) {
@@ -1046,7 +1046,7 @@ linearscan(RegAlloc *ra)
          goto GotReg;
       } else {
          /* for two-address instructions, try to use the reg of left arg */
-         if (ins->op != Ophi && (opnarg[ins->op] == 1 || (opnarg[ins->op] == 2 && ins->inplace))) {
+         if (ins->op != Ophi && (opnoper[ins->op] == 1 || (opnoper[ins->op] == 2 && ins->inplace))) {
             DBG(" %%%d try %d,%d\n", this, ins->l.t,ins->l.i);
             if (ins->l.t == RREG && rstest(avail, reg = ins->l.i))
                goto GotReg;
@@ -1155,7 +1155,7 @@ devirt(RegAlloc *ra, Block *blk)
       int nspill = 0;
 
       /** devirtualize operands **/
-      for (int i = 0; i < opnarg[ins->op]; ++i) {
+      for (int i = 0; i < opnoper[ins->op]; ++i) {
          Ref *r = &ins->oper[i];
          if (r->t == RADDR) {
             IRAddr *a = &addrtab.p[r->i];
diff --git a/src/ir_simpl.c b/src/ir_simpl.c
index d353cfa..1a3eb76 100644
--- a/src/ir_simpl.c
+++ b/src/ir_simpl.c
@@ -84,7 +84,7 @@ divmodk(Instr *ins, Block *blk, int *curi)
 static int
 doins(Instr *ins, Block *blk, int *curi)
 {
-   int narg = opnarg[ins->op];
+   int narg = opnoper[ins->op];
    if (oisarith(ins->op)) {
       Ref r = narg == 1 ? irunop(NULL, ins->op, ins->cls, ins->l)
                               : irbinop(NULL, ins->op, ins->cls, ins->l, ins->r);