basic CSE

5 files changed, 120 insertions, 0 deletions

diff --git a/Makefile b/Makefile
index 726f121..4aab646 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,6 @@
 SRC=main.c io.c mem.c c/c.c c/lex.c c/eval.c c/builtin.c type.c targ.c \
 	ir/ir.c ir/builder.c ir/fold.c ir/dump.c ir/ssa.c ir/cfg.c ir/intrin.c ir/abi0.c ir/mem2reg.c ir/regalloc.c ir/simpl.c ir/stack.c \
+	ir/cse.c \
 	x86_64/sysv.c x86_64/isel.c x86_64/emit.c \
 	aarch64/aapcs.c aarch64/isel.c aarch64/emit.c \
 	obj/obj.c obj/elf.c \
diff --git a/ir/cse.c b/ir/cse.c
new file mode 100644
index 0000000..23c5cf9
--- /dev/null
+++ b/ir/cse.c
@@ -0,0 +1,92 @@
+#include "ir.h"
+
+static inline bool
+pure(const struct instr *ins)
+{
+   return oisarith(ins->op) || (oisload(ins->op) && !ins->keep);
+}
+
+static inline bool
+insequ(const struct instr *a, const struct instr *b)
+{
+   if (a->op != b->op) return 0;
+   enum op op = a->op;
+   switch (opnarg[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;
+   }
+   return 1;
+}
+
+static struct ht {
+   uint t;
+   ushort memno, cutoff;
+   struct block *b;
+} *insht;
+static uint ninsht;
+
+static inline size_t
+hashins(const struct instr *ins)
+{
+   return hashb(0, ins, sizeof *ins);
+}
+
+static bool
+doms(struct block *blk, struct block *b)
+{
+   for (;; b = b->idom) {
+      if (blk == b) return 1;
+      if (blk == b->idom) return 1;
+      if (blk->id > b->id) return 0;
+   }
+}
+
+static int
+uniq(int t, struct block *blk, int cutoff, int memno)
+{
+   assert((uint)t < MAXINSTR);
+   struct instr *ins = &instrtab[t];
+   if (!pure(ins)) return t;
+   for (size_t h = hashins(&instrtab[t]), i = h;; ++i) {
+      struct ht *p = &insht[i &= (ninsht-1)];
+      if (!p->b) Put: {
+         p->b = blk;
+         p->memno = memno;
+         p->cutoff = cutoff;
+         return p->t = t;
+      } else if (insequ(&instrtab[p->t], ins)) {
+         if (p->cutoff == cutoff && (!oisload(ins->op) || p->memno == memno) && doms(p->b, blk))
+            return p->t;
+         goto Put;
+      }
+   }
+}
+
+void
+cselim(struct function *fn)
+{
+   FREQUIRE(FNUSE | FNRPO | FNDOM | FNBLKID);
+   extern int ninstr;
+   for (ninsht = 32; ninsht <= ninstr; ninsht *= 2) ;
+   insht = allocz(fn->passarena, ninsht * sizeof *insht, 0);
+   int memno = 0, cutoff = 0;
+   struct block *blk = fn->entry;
+   do {
+      ++memno;
+      for (int i = 0; i < blk->ins.n; ++i) {
+         int t = blk->ins.p[i], q;
+         if ((q = uniq(t, blk, cutoff, memno)) != t) {
+            replcuses(mkref(RTMP, t), mkref(RTMP, q));
+            delinstr(blk, i--);
+         } else if (oisstore(instrtab[t].op)) {
+            /* assume everything alias everything */
+            ++memno;
+         } else if (instrtab[t].op == Ocall) {
+            ++cutoff;
+         }
+      }
+   } while ((blk = blk->lnext) != fn->entry);
+}
+
+/* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/ir.c b/ir/ir.c
index f6c0aa2..83861af 100644
--- a/ir/ir.c
+++ b/ir/ir.c
@@ -647,6 +647,9 @@ irfini(struct function *fn)
       copyopt(fn);
    }
    if (ccopt.o >= OPT1) {
+      filldom(fn);
+      cselim(fn);
+      freearena(fn->passarena);
       simpl(fn);
       freearena(fn->passarena);
    }
diff --git a/ir/ir.h b/ir/ir.h
index d072f23..d32885e 100644
--- a/ir/ir.h
+++ b/ir/ir.h
@@ -325,6 +325,9 @@ void abi0_call(struct function *, struct instr *, struct block *blk, int *curi);
 /** simpl.c **/
 void simpl(struct function *);
 
+/** cselim.c **/
+void cselim(struct function *);
+
 /** mem2reg.c **/
 void mem2reg(struct function *);
 
diff --git a/ir/simpl.c b/ir/simpl.c
index 740a5a7..d651bb6 100644
--- a/ir/simpl.c
+++ b/ir/simpl.c
@@ -104,6 +104,26 @@ ins(struct instr *ins, struct block *blk, int *curi)
    case Odiv: case Oudiv: case Orem: case Ourem:
       if (kisflt(k)) break;
       if (isintcon(ins->r)) return divmodk(ins, blk, curi);
+      break;
+   case Oequ: case Oneq:
+      if (ins->l.t == RTMP && isintcon(ins->r)) {
+         /* optimize `x <op> C <cmp> Q` */
+         /* could apply with add/sub to lth/lte/gth/gte iff no signed wraparound, which isn't assumed */
+         struct instr *lhs = &instrtab[ins->l.i];
+         enum op o = lhs->op;
+         if (ins->cls == lhs->cls && (o == Oadd || o == Osub || o == Oxor) && isintcon(lhs->r)) {
+            uvlong c = intconval(ins->r), q = intconval(lhs->r);
+            switch (o) { default: assert(0);
+            case Oadd: c -= q; break; /* x + 3 == C ==> x == C - 3 */
+            case Osub: c += q; break; /* x - 3 == C ==> x == C + 3 */
+            case Oxor: c ^= q; break; /* x ^ 3 == C ==> x == C ^ 3 */
+            }
+            ins->l = lhs->l, ins->r = mkintcon(ins->cls, c);
+            deluse(blk, ins - instrtab, mkref(RTMP, lhs - instrtab));
+            if (!instruse[lhs - instrtab]) *lhs = mkinstr(Onop,0,);
+            return 1;
+         }
+      }
    }
    return 0;
 }
@@ -232,6 +252,7 @@ simpl(struct function *fn)
       } while ((blk = blk->lnext) != fn->entry);
       fillpreds(fn);
    }
+   fn->prop &= ~FNDOM;
 }
 
 /* vim:set ts=3 sw=3 expandtab: */