Organize source files into directories

1 files changed, 618 insertions, 0 deletions

diff --git a/ir/ir.c b/ir/ir.c
new file mode 100644
index 0000000..0132a97
--- /dev/null
+++ b/ir/ir.c
@@ -0,0 +1,618 @@
+#include "ir.h"
+#include "../obj/obj.h"
+
+uchar type2cls[NTYPETAG];
+uchar cls2siz[KF8+1];
+const uchar siz2intcls[] = { [1] = KI4, [2] = KI4, [4] = KI4, [8] = KI8 };
+
+const char *opnames[] = {
+   "?\??",
+#define _(o,...) #o,
+#include "op.def"
+#undef _
+};
+
+const uchar opnarg[] = {
+   0,
+#define _(o,n) n,
+#include "op.def"
+#undef _
+};
+
+struct instr instrtab[MAXINSTR];
+struct use *instruse[MAXINSTR];
+short instrnuse[MAXINSTR];
+static struct use instrusebuf[MAXINSTR][2];
+int ninstr;
+static int instrfreelist;
+struct calltab calltab;
+struct phitab phitab;
+struct dattab dattab;
+struct addr addrht[1 << 12];
+static int naddrht;
+struct xcon conht[1 << 12];
+static int nconht;
+int visitmark;
+
+void
+irinit(struct function *fn)
+{
+   static struct call callsbuf[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));
+   if (!dattab.p) vinit(&dattab, datsbuf, arraylength(datsbuf));
+   if (naddrht >= arraylength(addrht)/2)
+      memset(addrht, naddrht = 0, sizeof addrht);
+   if (nconht >= arraylength(conht)/2)
+      memset(conht, nconht = 0, sizeof conht);
+   if (!type2cls[TYINT]) {
+      for (int i = TYBOOL; i <= TYUVLONG; ++i) {
+         int siz = targ_primsizes[i];
+         type2cls[i] = siz < 8 ? KI4 : KI8;
+      }
+      type2cls[TYFLOAT] = KF4;
+      type2cls[TYDOUBLE] = KF8;
+      type2cls[TYLDOUBLE] = KF8;
+      type2cls[TYPTR] = KPTR;
+      type2cls[TYARRAY] = KPTR;
+      cls2siz[KI4] = cls2siz[KF4] = 4;
+      cls2siz[KI8] = cls2siz[KF8] = 8;
+      cls2siz[KPTR] = targ_primsizes[TYPTR];
+   }
+   fn->entry = fn->curblk = allocz(fn->arena, sizeof(struct block), 0);
+   fn->nblk = 1;
+   fn->entry->lprev = fn->entry->lnext = fn->entry;
+}
+
+static int
+addaddr(const struct addr *addr)
+{
+   uint h = hashb(0, addr, sizeof *addr);
+   uint i = h, n = arraylength(addrht);
+   for (;; ++i) {
+      i &= arraylength(addrht) - 1;
+      if (!addrht[i].base.bits && !addrht[i].index.bits) {
+         addrht[i] = *addr;
+         ++naddrht;
+         return i;
+      } else if (!memcmp(&addrht[i], addr, sizeof *addr)) {
+         return i;
+      }
+      assert(--n > 0 && "addrht full");
+   }
+}
+
+static int
+addcon(const struct xcon *con)
+{
+   uint h = hashb(0, con, sizeof *con);
+   uint i = h, n = arraylength(conht);
+   assert(con->issym || con->isdat || con->cls);
+   for (;; ++i) {
+      i &= arraylength(conht) - 1;
+      if (!conht[i].issym && !conht[i].cls) {
+         conht[i] = *con;
+         ++nconht;
+         return i;
+      } else if (!memcmp(&conht[i], con, sizeof *con)) {
+         return i;
+      }
+      assert(--n > 0 && "conht full");
+   }
+}
+
+union irtype
+mkirtype(union type t)
+{
+   if (t.t == TYVOID || isscalar(t))
+      return (union irtype) { .cls = type2cls[scalartypet(t)] };
+   assert(isagg(t));
+   return (union irtype) { .isagg = 1, .dat = t.dat };
+}
+
+union ref
+mkintcon(enum irclass k, vlong i)
+{
+   if (i < 1l << 28 && i >= -(1l << 28)) {
+      return mkref(RICON, i);
+   } else {
+      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));
+   }
+}
+
+union ref
+mkfltcon(enum irclass k, double f)
+{
+   struct xcon con = { .cls = k, .f = k == KF4 ? (float) f : f };
+   return mkref(RXCON, addcon(&con));
+}
+
+union ref
+mksymref(const char *s)
+{
+   struct xcon con = { .issym = 1, .sym = s };
+   return mkref(RXCON, addcon(&con));
+}
+
+union ref
+mkdatref(const char *name, uint siz, uint align, const void *bytes, uint n, bool deref)
+{
+   struct irdat dat = { .align = align, .siz = siz, .name = name, .section = Srodata };
+
+   assert(n <= siz && siz && align);
+   if (!name) {
+      extern const char *intern(const char *);
+      char buf[32];
+      struct wbuf wbuf = MEMBUF(buf, sizeof buf);
+
+      bfmt(&wbuf, ".L.%d", dattab.n);
+      ioputc(&wbuf, 0);
+      assert(!wbuf.err);
+      dat.name = name = intern(buf);
+   }
+   dat.off = objnewdat(name, dat.section, 0, siz, align);
+   memcpy(objout.rodata.p+dat.off, bytes, n);
+   memset(objout.rodata.p+dat.off+n, 0, siz - n);
+   vpush(&dattab, dat);
+   return mkref(RXCON, addcon(&(struct xcon){.isdat = 1, .deref = deref, .dat = dattab.n - 1}));
+}
+
+const char *
+xcon2sym(int ref)
+{
+   struct xcon con = conht[ref];
+   assert(con.issym ^ con.isdat);
+   return con.issym ? con.sym : dattab.p[con.dat].name;
+}
+
+struct instr
+mkalloca(uint siz, uint align)
+{
+   struct instr ins = { .cls = KPTR };
+   assert(ispo2(align) && align <= 16);
+   ins.op = Oalloca1 + ilog2(align);
+   ins.l = mkref(RICON, siz/align + (siz%align != 0));
+   return ins;
+}
+
+union ref
+mkcallarg(union irtype ret, uint narg, int vararg)
+{
+   struct call call = { .ret=ret, .narg=narg, .vararg=vararg };
+   assert((long) vararg <= narg);
+   vpush(&calltab, call);
+   return mkref(RXXX, calltab.n-1);
+}
+
+union ref
+mkaddr(struct addr addr)
+{
+   return mkref(RADDR, addaddr(&addr));
+}
+
+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 void
+delpred(struct block *blk, struct block *p)
+{
+   for (int i = 0; i < blk->npred; ++i) {
+      if (blkpred(blk, i) == p) {
+         for (int k = i; k < blk->npred - 1; ++k) {
+            blkpred(blk, k) = blkpred(blk, k + 1);
+         }
+         --blk->npred;
+         return;
+      }
+   }
+   assert(0&&"blk not in p");
+}
+
+struct block *
+newblk(struct function *fn)
+{
+   struct block *blk = alloc(fn->arena, sizeof(struct block), 0);
+   memset(blk, 0, sizeof *blk);
+   blk->id = -1;
+   return blk;
+}
+
+void
+freeblk(struct function *fn, struct block *blk)
+{
+   if (blk->npred > 1)
+      xbfree(blk->_pred);
+   vfree(&blk->phi);
+   vfree(&blk->ins);
+   if (blk->lnext) blk->lnext->lprev = blk->lprev;
+   if (blk->lprev) blk->lprev->lnext = blk->lnext;
+   blk->id = 1u<<31;
+   --fn->nblk;
+}
+
+struct block *
+insertblk(struct function *fn, struct block *pred, struct block *subst)
+{
+   struct block *new = newblk(fn);
+   struct block **s = pred->s1 == subst ? &pred->s1 : &pred->s2;
+   assert(*s == subst);
+   new->lnext = pred->lnext;
+   new->lprev = pred;
+   pred->lnext->lprev = new;
+   pred->lnext = new;
+   *s = new;
+   new->jmp.t = Jb;
+   new->s1 = subst;
+   addpred(new, pred);
+   for (int i = 0; i < subst->npred; ++i) {
+      if (blkpred(subst, i) == pred) {
+         blkpred(subst, i) = new;
+         ++fn->nblk;
+         return new;
+      }
+   }
+   assert(0);
+}
+
+
+static int
+newinstr(void)
+{
+   int t;
+   if (instrfreelist != -1) {
+      t = instrfreelist;
+      memcpy(&instrfreelist, &instrtab[t], sizeof(int));
+   } else {
+      assert(ninstr < arraylength(instrtab));
+      t = ninstr++;
+   }
+   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] < arraylength(instrusebuf[r.i])) {
+      instruse[r.i][instrnuse[r.i]++] = user;
+   } else if (instrnuse[r.i] == arraylength(*instrusebuf)) {
+      struct use *use = NULL;
+      xbgrow(&use, arraylength(*instrusebuf) + 2);
+      memcpy(use, instruse[r.i], sizeof(*instrusebuf));
+      use[instrnuse[r.i]++] = user;
+      instruse[r.i] = use;
+   } else {
+      xbpush(&instruse[r.i], &instrnuse[r.i], user);
+   }
+}
+
+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;
+      }
+   }
+   return 0;
+
+Shrink:
+   if (instrnuse[r.i] == arraylength(*instrusebuf) + 1) {
+      struct use *use = instruse[r.i];
+      instruse[r.i] = instrusebuf[r.i];
+      memcpy(instruse[r.i], use, sizeof *instrusebuf);
+   }
+   --instrnuse[r.i];
+   return 1;
+}
+
+union ref
+insertinstr(struct block *blk, int idx, struct instr ins)
+{
+   int new = newinstr();
+
+   instrtab[new] = ins;
+   if (idx == blk->ins.n) vpush(&blk->ins, new);
+   else {
+      assert(idx >= 0 && idx < blk->ins.n);
+      vpush_((void **)&blk->ins.p, &blk->ins._cap, &blk->ins.n, sizeof *blk->ins.p);
+      vresize(&blk->ins, blk->ins.n);
+      for (int i = blk->ins.n++; i > idx; --i)
+         blk->ins.p[i] = blk->ins.p[i - 1];
+      blk->ins.p[idx] = new;
+   }
+   adduse(blk, new, ins.l);
+   adduse(blk, new, ins.r);
+   return mkref(RTMP, new);
+}
+
+union ref
+insertphi(struct block *blk, enum irclass cls)
+{
+   int new = newinstr();
+   union ref *refs = NULL;
+   assert(blk->npred > 0);
+   xbgrow(&refs, blk->npred);
+   memset(refs, 0, blk->npred * sizeof *refs);
+   vpush(&phitab, refs);
+   instrtab[new] = mkinstr(Ophi, cls, mkref(RXXX, phitab.n - 1));
+   vpush(&blk->phi, new);
+   return mkref(RTMP, new);
+}
+
+void
+numberinstrs(struct function *fn)
+{
+   struct block *blk = fn->entry;
+   int start = 0;
+   do {
+      blk->inumstart = start;
+      start += blk->ins.n+2;
+   } while ((blk = blk->lnext) != fn->entry);
+}
+
+/* require use */
+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];
+      union ref *u;
+      int n, j;
+      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 {
+         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;
+            break;
+         }
+      }
+   }
+}
+
+void
+deluses(int ins)
+{
+   if (instruse[ins] != instrusebuf[ins]) {
+      xbfree(instruse[ins]);
+      instruse[ins] = instrusebuf[ins];
+   }
+   instrnuse[ins] = 0;
+}
+
+void
+delinstr(struct block *blk, int idx)
+{
+   int t = blk->ins.p[idx];
+   assert(idx >= 0 && idx < blk->ins.n);
+   memcpy(&instrtab[t], &instrfreelist, sizeof(int));
+   instrfreelist = t;
+   deluses(t);
+   for (int i = idx; i < blk->ins.n - 1; ++i)
+      blk->ins.p[i] = blk->ins.p[i + 1];
+   --blk->ins.n;
+}
+
+void
+delphi(struct 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;
+   deluses(t);
+   for (int i = idx; i < blk->phi.n - 1; ++i)
+      blk->phi.p[i] = blk->phi.p[i + 1];
+   --blk->phi.n;
+}
+
+void
+delnops(struct block *blk)
+{
+   int i, n, t;
+   /* delete trailing nops */
+   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;
+   }
+   /* 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;
+         ++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);
+         blk->ins.n -= n;
+         n = 0;
+      }
+   }
+   if (n)
+      memmove(blk->ins.p, blk->ins.p + n, (blk->ins.n -= n)*sizeof *blk->ins.p);
+}
+
+void
+fillblkids(struct function *fn)
+{
+   int i = 0;
+   struct block *blk = fn->entry;
+   do blk->id = i++; while ((blk = blk->lnext) != fn->entry);
+}
+
+/** IR builders **/
+
+void
+useblk(struct function *fn, struct block *blk)
+{
+   extern int nerror;
+   if (fn->curblk && nerror == 0) assert(fn->curblk->jmp.t && "never finished block");
+   if (blk) assert(!blk->jmp.t && "reusing built block");
+   if (!blk->lprev) { /* initialize */
+      blk->lnext = fn->entry;
+      blk->lprev = fn->entry->lprev;
+      blk->lprev->lnext = blk;
+      blk->id = blk->lprev->id + 1;
+      ++fn->nblk;
+      fn->entry->lprev = blk;
+   }
+   fn->curblk = blk;
+}
+
+union ref
+addinstr(struct function *fn, struct instr ins)
+{
+   int new = newinstr();
+   assert(fn->curblk != NULL);
+   instrtab[new] = ins;
+   adduse(fn->curblk, new, ins.l);
+   adduse(fn->curblk, new, ins.r);
+   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 *refs = NULL;
+
+   xbgrow(&refs, fn->curblk->npred);
+   memcpy(refs, r, fn->curblk->npred * sizeof *r);
+   vpush(&phitab, refs);
+   ins.l = mkref(RXXX, phitab.n-1);
+
+   assert(fn->curblk != NULL);
+   assert(fn->curblk->ins.n == 0);
+   new = newinstr();
+   instrtab[new] = ins;
+   for (int i = 0; i < fn->curblk->npred; ++i) {
+      adduse(fn->curblk, new, r[i]);
+   }
+   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;        \
+   fn->curblk->jmp.arg[1] = arg1;        \
+   fn->curblk->s1 = T;                   \
+   fn->curblk->s2 = F;                   \
+   fn->curblk = NULL;
+
+void
+putbranch(struct function *fn, struct block *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(fn->curblk && t && f);
+   adduse(fn->curblk, USERJUMP, arg);
+   addpred(t, fn->curblk);
+   addpred(f, fn->curblk);
+   putjump(fn, Jb, arg, NOREF, t, f);
+}
+
+void
+putreturn(struct function *fn, union ref r0, union ref r1)
+{
+   adduse(fn->curblk, USERJUMP, r0);
+   adduse(fn->curblk, USERJUMP, r1);
+   putjump(fn, Jret, r0, r1, NULL, NULL);
+}
+
+#undef putjump
+
+/** Misc **/
+
+static void
+freefn(struct function *fn)
+{
+   struct block *blk = fn->entry;
+   do {
+      if (blk->npred > 1) xbfree(blk->_pred);
+      vfree(&blk->phi);
+      vfree(&blk->ins);
+   } while ((blk = blk->lnext) != fn->entry);
+}
+
+void
+irfini(struct function *fn)
+{
+   extern int nerror;
+   if (nerror) {
+      freefn(fn);
+      return;
+   }
+
+   abi0(fn);
+   lowerintrin(fn);
+   mem2reg(fn);
+   copyopt(fn);
+   if (ccopt.dbg.o) {
+      efmt("<< Before isel >>\n");
+      irdump(fn);
+   }
+   mctarg->isel(fn);
+   regalloc(fn);
+   if (!ccopt.dbg.any)
+      mctarg->emit(fn);
+
+   freefn(fn);
+}
+
+/* vim:set ts=3 sw=3 expandtab: */