amd64: fix aggregate abi stuff;; ir: fold, peephole optimizing constructors

6 files changed, 375 insertions, 101 deletions

diff --git a/ir/builder.c b/ir/builder.c
new file mode 100644
index 0000000..213a491
--- /dev/null
+++ b/ir/builder.c
@@ -0,0 +1,217 @@
+#include "ir.h"
+
+/* binary arithmetic builder with peephole optimizations */
+union ref
+irbinop(struct function *fn, enum op op, enum irclass k, union ref l, union ref r)
+{
+   static const union ref ONE = {.t=RICON, .i=1};
+   vlong iv;
+   union ref c;
+
+   if (foldbinop(&c, op, k, l, r))
+      return c;
+
+   switch (op) {
+   case Oadd:
+      if (l.bits == ZEROREF.bits) return r; /* 0 + x ==> x */
+      /* fallthru */
+   case Osub:
+      if (r.bits == ZEROREF.bits) return l; /* x +/- 0 ==> x */
+      break;
+   case Omul: case Oumul:
+      if (iscon(l)) rswap(l, r); /* put const in rhs */
+      if (r.bits == ZEROREF.bits) /* x * 0 ==> 0 */
+         return ZEROREF;
+      if (r.bits == ONE.bits) /* x * 1 ==> x */
+         return l;
+      if (isintcon(r) && ispo2(iv = intconval(r))) {
+         /* x * 2^y ==> x << y */
+         op = Oshl;
+         r = mkintcon(k, ilog2(iv));
+      }
+      break;
+   case Odiv:
+      break;
+   case Oudiv:
+      if (isintcon(r) && ispo2(iv = intconval(r))) {
+         /* x / 2^y ==> x >> y */
+         op = Oslr;
+         r = mkintcon(k, ilog2(iv));
+      }
+      break;
+   case Orem:
+      break;
+   case Ourem:
+      if (isintcon(r) && ispo2(iv = intconval(r))) {
+         /* x % 2^y ==> x & 2^y-1 */
+         op = Oand;
+         r = mkintcon(k, iv - 1);
+      }
+      break;
+   case Oand:
+      if (iscon(l)) rswap(l, r); /* put const in rhs */
+      if (r.bits == ZEROREF.bits) /* x & 0 ==> 0 */
+         return ZEROREF;
+      break;
+   case Oior:
+      if (iscon(l)) rswap(l, r); /* put const in rhs */
+      if (r.bits == ZEROREF.bits) /* x | 0 ==> x */
+         return l;
+   case Oxor:
+      if (iscon(l)) rswap(l, r); /* put const in rhs */
+      if (r.bits == ZEROREF.bits) /* x ^ 0 ==> x */
+         return l;
+   case Oshl: case Osar: case Oslr:
+      if (r.bits == ZEROREF.bits) /* x shift 0 ==> x */
+         return l;
+      break;
+   case Oequ:
+      if (r.bits == l.bits && kisint(k))
+         return ONE;
+      break;
+   case Oneq:
+      if (r.bits == l.bits && kisint(k))
+         return ZEROREF;
+      break;
+   case Olth:
+      break;
+   case Ogth:
+      break;
+   case Olte:
+      break;
+   case Ogte:
+      break;
+   case Oulth:
+      break;
+   case Ougth:
+      break;
+   case Oulte:
+      break;
+   case Ougte:
+      break;
+   default:
+      assert(!"binop?");
+   }
+   return addinstr(fn, mkinstr(op, k, l, r));
+}
+
+union ref
+irunop(struct function *fn, enum op op, enum irclass k, union ref a)
+{
+   union ref c;
+   struct instr *ins = NULL;
+   if (foldunop(&c, op, k, a))
+      return c;
+   if (a.t == RTMP) ins = &instrtab[a.i];
+   switch (op) {
+   case Oneg:
+      if (ins && ins->op == Oneg) /* -(-x) ==> x */
+         return ins->l;
+      break;
+   case Onot:
+      if (ins && ins->op == Onot) /* ~(~x) ==> x */
+         return ins->l;
+      break;
+   case Ocvtf4s: case Ocvtf4u: case Ocvtf4f8: case Ocvtf8s: 
+   case Ocvtf8u: case Ocvtf8f4: case Ocvts4f: case Ocvtu4f: 
+   case Ocvts8f: case Ocvtu8f: 
+   case Oexts1: case Oextu1: case Oexts2: case Oextu2: 
+   case Oexts4: case Oextu4:
+   case Ocopy:
+      break;
+   default: assert(!"unop?");
+   }
+   return addinstr(fn, mkinstr(op, k, a));
+}
+
+int newinstr(void);
+
+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);
+}
+
+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
+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
+
+/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/fold.c b/ir/fold.c
new file mode 100644
index 0000000..fd6076e
--- /dev/null
+++ b/ir/fold.c
@@ -0,0 +1,119 @@
+#include "ir.h"
+
+static union ref
+foldint(enum op op, enum irclass k, union ref lr, union ref rr)
+{
+   vlong x;
+   union {
+      vlong s;
+      uvlong u;
+   } l = {.s = intconval(lr)}, r = {.s = intconval(rr)};
+   bool w = cls2siz[k] == 8;
+   if (in_range(op, Odiv, Ourem)) assert(r.u != 0);
+   switch (op) {
+   case Ocopy: x = l.s; break;
+   case Oneg:  x = -l.s; break;
+   case Onot:  x = ~l.s; break;
+   case Ocvtf4s: x = (int)(float)fltconval(lr); break;
+   case Ocvtf4u: x = (uint)(float)fltconval(lr); break;
+   case Ocvtf8s: x = (vlong)fltconval(lr); break;
+   case Ocvtf8u: x = (uvlong)fltconval(lr); break;
+   case Oexts1: x = (schar)l.s; break;
+   case Oextu1: x = (uchar)l.s; break;
+   case Oexts2: x = (short)l.s; break;
+   case Oextu2: x = (ushort)l.s; break;
+   case Oexts4: x = (int)l.s; break;
+   case Oextu4: x = (uint)l.s; break;
+   case Oadd:  x = l.u + r.u; break;
+   case Osub:  x = l.u - r.u; break;
+   case Omul:  x = l.u * r.u; break;
+   case Oumul: x = l.u * r.u; break;
+   case Odiv:  x = w ? l.s / r.s : (int)l.s / (int)r.s; break;
+   case Oudiv: x = w ? l.u / r.u : (uint)l.u / (uint)r.u; break;
+   case Orem:  x = w ? l.s % r.s : (int)l.s % (int)r.s; break;
+   case Ourem: x = w ? l.u % r.u : (uint)l.u % (uint)r.u; break;
+   case Oand:  x = l.u & r.u; break;
+   case Oior:  x = l.u | r.u; break;
+   case Oxor:  x = l.u ^ r.u; break;
+   case Oshl:  x = l.u << (r.u & (w ? 63 : 31)); break;
+   case Oslr:  x = w ? l.u >> (r.u&63) : (int)l.s >> (r.u&31); break;
+   case Osar:  x = w ? l.s >> (r.u&63) : (int)l.s >> (r.u&31); break;
+   case Oequ:  x = l.s == r.s; break;
+   case Oneq:  x = l.s != r.s; break;
+   case Olth:  x = l.s < r.s; break;
+   case Ogth:  x = l.s > r.s; break;
+   case Olte:  x = l.s <= r.s; break;
+   case Ogte:  x = l.s >= r.s; break;
+   case Oulth: x = l.u < r.u; break;
+   case Ougth: x = l.u > r.u; break;
+   case Oulte: x = l.u <= r.u; break;
+   case Ougte: x = l.u >= r.u; break;
+   default: assert(0);
+   }
+   return mkintcon(k, x);
+}
+
+static union ref
+foldflt(enum op op, enum irclass k, union ref lr, union ref rr)
+{
+   int xi;
+   double x, l = fltconval(lr), r = fltconval(rr);
+   bool w = k == KF8;
+   if (in_range(op, Odiv, Ourem)) assert(r != 0.0);
+   switch (op) {
+   case Ocopy: x = l; break;
+   case Oneg:  x = -l; break;
+   case Ocvtf4f8: x = (float)l; break;
+   case Ocvtf8f4: x = (float)l; break;
+   case Ocvts4f:  x = (int)intconval(lr); break;
+   case Ocvtu4f:  x = (int)intconval(lr); break;
+   case Ocvts8f:  x = (vlong)intconval(lr); break;
+   case Ocvtu8f:  x = (uvlong)intconval(lr); break;
+   case Oadd: x = l + r; break;
+   case Osub: x = l - r; break;
+   case Omul: x = l * r; break;
+   case Odiv: x = l / r; break;
+   case Oequ: xi = l == r; break;
+   case Oneq: xi = l != r; break;
+   case Olth: xi = l < r; break;
+   case Ogth: xi = l > r; break;
+   case Olte: xi = l <= r; break;
+   case Ogte: xi = l >= r; break;
+   default: assert(0);
+   }
+   if (oiscmp(op)) return mkref(RICON, xi);
+   if (!w) x = (float)x;
+   return mkfltcon(k, x);
+}
+
+bool
+foldbinop(union ref *to, enum op op, enum irclass k, union ref l, union ref r)
+{
+   if (!iscon(l) || !iscon(r)) return 0;
+   if (in_range(op, Odiv, Ourem) && (kisint(k) ? intconval(r) == 0 : fltconval(r) == 0))
+      return 0;
+   if (!oisarith(op))
+      return 0;
+   to->t = oiscmp(op) ? KI4 : k;
+   if (kisint(k))
+      *to = foldint(op, k, l, r);
+   else
+      *to = foldflt(op, k, l, r);
+   return 1;
+}
+
+bool
+foldunop(union ref *to, enum op op, enum irclass k, union ref a)
+{
+   if (!iscon(a)) return 0;
+   if (op != Ocopy && !oisarith(op))
+      return 0;
+   to->t = k;
+   if (kisint(k))
+      *to = foldint(op, k, a, ZEROREF);
+   else
+      *to = foldflt(op, k, a, ZEROREF);
+   return 1;
+}
+
+/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/ir.c b/ir/ir.c
index 49d8d5e..2a5cde6 100644
--- a/ir/ir.c
+++ b/ir/ir.c
@@ -297,7 +297,7 @@ insertblk(struct function *fn, struct block *pred, struct block *subst)
    assert(0);
 }
 
-static int
+int
 newinstr(void)
 {
    int t;
@@ -383,8 +383,7 @@ 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);
+   xbgrowz(&refs, blk->npred);
    vpush(&phitab, refs);
    instrtab[new] = mkinstr(Ophi, cls, mkref(RXXX, phitab.n - 1));
    vpush(&blk->phi, new);
@@ -506,96 +505,6 @@ fillblkids(struct function *fn)
    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
diff --git a/ir/ir.h b/ir/ir.h
index a49432d..149a74b 100644
--- a/ir/ir.h
+++ b/ir/ir.h
@@ -77,6 +77,7 @@ struct addr {
 #define mkref(t, x) ((union ref) {{ (t), (x) }})
 #define mktyperef(t) ((union ref) {{ RTYPE, (t).bits }})
 #define ref2type(r) ((union irtype) {.bits = (r).i})
+#define rswap(a,b) do { union ref _t = (a); (a) = (b); (b) = _t; } while (0)
 
 enum op {
    Oxxx,
@@ -86,6 +87,7 @@ enum op {
 };
 
 #define oiscmp(o) in_range(o, Oequ, Ougte)
+#define oisarith(o) in_range(o, Oneg, Ougte)
 #define oisalloca(o) in_range(o, Oalloca1, Oalloca16)
 #define oisstore(o) in_range(o, Ostore1, Ostore8)
 #define oisload(o) in_range(o, Oloads1, Oloadf8)
@@ -219,7 +221,7 @@ union ref mkfltcon(enum irclass, double);
 #define isnumcon(r) ((r).t == RICON || ((r).t == RXCON && conht[(r).i].cls))
 #define isaddrcon(r) ((r).t == RXCON && !conht[(r).i].cls && !conht[(r).i].deref)
 #define intconval(r) ((r).t == RICON ? (r).i : conht[(r).i].i)
-#define fltconval(r) (conht[(r).i].f)
+#define fltconval(r) ((r).t == RICON ? (r).i : conht[(r).i].f)
 union ref mksymref(const char *);
 union ref mkdatref(const char *name, uint siz, uint align, const void *, uint n, bool deref);
 const char *xcon2sym(int ref);
@@ -247,7 +249,9 @@ void fillblkids(struct function *);
 #define markvisited(blk) ((blk)->visit = visitmark)
 void numberinstrs(struct function *);
 
-/* IR builder functions */
+/** builder.c **/
+union ref irbinop(struct function *, enum op, enum irclass, union ref lhs, union ref rhs);
+union ref irunop(struct function *, enum op, enum irclass, union ref);
 union ref addinstr(struct function *, struct instr);
 union ref addphi(struct function *, enum irclass, union ref []);
 void useblk(struct function *, struct block *);
@@ -255,6 +259,10 @@ 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);
 
+/** fold.c **/
+bool foldbinop(union ref *to, enum op, enum irclass, union ref l, union ref r);
+bool foldunop(union ref *to, enum op, enum irclass, union ref);
+
 /** irdump.c **/
 void irdump(struct function *);
 
diff --git a/ir/optmem.c b/ir/optmem.c
index 471f11c..9b71c8d 100644
--- a/ir/optmem.c
+++ b/ir/optmem.c
@@ -246,6 +246,20 @@ mem2reg(struct function *fn)
                                k, mkref(RREG, mctarg->bpr));
                } else {
                   adduse(use->blk, use->u, val);
+                  if (isintcon(val) && ext != Ocopy) {
+                     vlong x = intconval(val);
+                     switch (ext) {
+                     case Oexts1: x = (schar)x; break;
+                     case Oextu1: x = (uchar)x; break;
+                     case Oexts2: x = (short)x; break;
+                     case Oextu2: x = (ushort)x; break;
+                     case Oexts4: x = (int)x; break;
+                     case Oextu4: x = (uint)x; break;
+                     default: assert(0);
+                     }
+                     val = mkintcon(k, x);
+                     ext = Ocopy;
+                  }
                   *m = mkinstr(ext, k, val);
                }
             }
diff --git a/ir/regalloc.c b/ir/regalloc.c
index fae1a61..f43bcc7 100644
--- a/ir/regalloc.c
+++ b/ir/regalloc.c
@@ -2,7 +2,7 @@
 
 /** Implements linear scan register allocation **/
 
-#if 0
+#if 1
 #define DBG(...) if(ccopt.dbg.r) efmt(__VA_ARGS__)
 #else
 #define DBG(...) ((void)0)
@@ -1000,12 +1000,19 @@ devirt(struct rega *ra, struct block *blk)
                bool dosave;
                /* pick scratch register, or any register that doesn't conflict with this instr's srcs/dst */
                if (nspill > 0) {
-                  for (reg = kisflt(ld.cls) ? mctarg->fpr0 : mctarg->gpr0;; ++reg) {
-                     if (reg == ins->reg-1) continue;
-                     for (int j = 0; j < i; ++j)
-                        if (argref[j]->t == RREG && argref[j]->i == reg) continue;
-                     break;
+                  regset avail = kisflt(ld.cls) ? fpregset : gpregset;
+                  if (ins->reg) rsclr(&avail, ins->reg-1);
+                  for (int j = 0; j < nargref; ++j) {
+                     struct interval *it;
+                     if (argref[j]->t == RREG) rsclr(&avail, argref[j]->i);
+                     else if (argref[j]->t == RTMP) {
+                        it = &ra->intervals.temps[argref[j]->i];
+                        if (it->alloc.t == AREG) rsclr(&avail, it->alloc.a);
+                     }
                   }
+                  assert(avail != 0);
+                  if (reg &~ (fn->regusage | mctarg->rcallee)) reg &= ~(fn->regusage | mctarg->rcallee);
+                  reg = lowestsetbit(avail);
                   /* if not the designated scratch register, we need to save+restore */
                   if ((dosave = rstest(fn->regusage, reg) || rstest(mctarg->rcallee, reg))) {
                      insertinstr(blk, curi++, mkinstr(Oxsave, 0, .l = mkref(RREG, reg)));