backend: general simplification pass skeleton

4 files changed, 155 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index fe9a34e..90cdeef 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
 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/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 \
 	x86_64/sysv.c x86_64/isel.c x86_64/emit.c obj/obj.c obj/elf.c \
 	embedfilesdir.c
 CFLAGS=-Wall -std=c11 -pedantic
diff --git a/ir/ir.c b/ir/ir.c
index 8ae41a9..5f1797c 100644
--- a/ir/ir.c
+++ b/ir/ir.c
@@ -221,7 +221,7 @@ addpred(struct block *blk, struct block *p)
    xbpush(&blk->_pred, &blk->npred, p);
 }
 
-static void
+void
 delpred(struct block *blk, struct block *p)
 {
    for (int i = 0; i < blk->npred; ++i) {
@@ -640,6 +640,9 @@ irfini(struct function *fn)
       mem2reg(fn);
       copyopt(fn);
    }
+   if (ccopt.o >= OPT1) {
+      simpl(fn);
+   }
    if (ccopt.dbg.o) {
       bfmt(ccopt.dbgout, "<< Before isel >>\n");
       irdump(fn);
diff --git a/ir/ir.h b/ir/ir.h
index 4049811..ad22eb9 100644
--- a/ir/ir.h
+++ b/ir/ir.h
@@ -275,6 +275,7 @@ void filluses(struct function *);
 void delinstr(struct block *, int idx);
 void delphi(struct block *, int idx);
 void delnops(struct block *blk);
+void delpred(struct block *blk, struct block *p);
 void fillblkids(struct function *);
 #define startbbvisit() (void)(++visitmark)
 #define wasvisited(blk) ((blk)->visit == visitmark)
@@ -311,6 +312,9 @@ void filldom(struct function *fn);
 void abi0(struct function *);
 void abi0_call(struct function *, struct instr *, struct block *blk, int *curi);
 
+/** simpl.c **/
+void simpl(struct function *);
+
 /** mem2reg.c **/
 void mem2reg(struct function *);
 
diff --git a/ir/simpl.c b/ir/simpl.c
new file mode 100644
index 0000000..fb89c07
--- /dev/null
+++ b/ir/simpl.c
@@ -0,0 +1,146 @@
+#include "ir.h"
+
+static int
+ins(struct function *fn, struct instr *ins, struct block *blk, int *curi)
+{
+   int narg = opnarg[ins->op];
+   if ((oisarith(ins->op) || oiscmp(ins->op)) && isnumcon(ins->l) && (narg == 1 || isnumcon(ins->r))) {
+      bool ok;
+      if (narg == 1) ok = foldunop(&ins->l, ins->op, ins->cls, ins->l);
+      else ok = foldbinop(&ins->l, ins->op, ins->cls, ins->l, ins->r);
+      if (!ok) return 0; /* could be div/0 */
+      ins->op = Ocopy;
+      ins->cls = insrescls(*ins);
+      ins->r = NOREF;
+      return 1;
+   }
+   return 0;
+}
+
+static void
+jmpfind(struct block **final, struct block **pblk)
+{
+   struct block **p2 = &final[(*pblk)->id];
+   if (*p2 && !(*p2)->phi.n) {
+      jmpfind(final, p2);
+      *pblk = *p2;
+   }
+}
+
+static void
+fillpredsrec(struct block *blk)
+{
+   while (blk && !wasvisited(blk)) {
+      markvisited(blk);
+      if (!blk->s1) return;
+      if (!blk->s1->phi.n) addpred(blk->s1, blk);
+      if (!blk->s2) {
+         blk = blk->s1;
+         continue;
+      }
+      if (!blk->s2->phi.n) addpred(blk->s2, blk);
+      fillpredsrec(blk->s1);
+      blk = blk->s2;
+   }
+}
+
+static void
+fillpreds(struct function *fn)
+{
+   struct block *blk = fn->entry, *next;
+   do {
+      if (blk->phi.n) continue;
+      if (blk->npred > 1)
+         xbfree(blk->_pred);
+      blk->npred = 0;
+      blk->_pred = NULL;
+   } while ((blk = blk->lnext) != fn->entry);
+   startbbvisit();
+   fillpredsrec(fn->entry);
+   blk = fn->entry->lnext;
+   do { /* remove dead blocks */
+      next = blk->lnext;
+      if (!blk->npred) freeblk(fn, blk);
+   } while ((blk = next) != fn->entry);
+}
+
+void
+simpl(struct function *fn)
+{
+   FREQUIRE(FNUSE);
+   int inschange = 0,
+       blkchange = 0;
+   struct block **jmpfinal = xcalloc(fn->nblk * sizeof *jmpfinal);
+   struct block *blk = fn->entry;
+
+   do {
+      for (int i = 0; i < blk->phi.n; ++i) {
+
+      }
+      for (int i = 0; i < blk->ins.n; ++i) {
+         inschange += ins(fn, &instrtab[blk->ins.p[i]], blk, &i);
+      }
+
+      /* merge blocks:
+       * @blk:
+       *   ... (1)
+       *   b @s
+       * @s:
+       *   ... (2)
+       *   b {...}
+       *=>
+       * @blk:
+       *   ... (1)
+       *   ... (2)
+       *   b {...}
+       * */
+      if (blk != fn->entry) while (blk->s1 && !blk->s2 && blk->s1->npred == 1 && !blk->phi.n) {
+         struct block *s = blk->s1;
+         vpushn(&blk->ins, s->ins.p, s->ins.n);
+         blk->jmp = blk->s1->jmp;
+         for (int i = 0; i < 2; ++i) {
+            struct block *ss = (&s->s1)[i];
+            if (ss) for (int j = 0; j < ss->npred; ++j) {
+               if (blkpred(ss, j) == s) {
+                  blkpred(ss, j) = blk;
+                  break;
+               }
+            }
+         }
+         /* breaks use for temps used in s */
+         if (s->ins.n || s->jmp.arg[0].t == RTMP || s->jmp.arg[1].t == RTMP)
+            fn->prop &= ~FNUSE;
+         blk->s1 = s->s1;
+         blk->s2 = s->s2;
+         freeblk(fn, s);
+      }
+      /* thread jumps.. */
+      if (!blk->phi.n && !blk->ins.n) {
+         if (blk->jmp.t == Jb && !blk->s2) {
+            jmpfind(jmpfinal, &blk->s1);
+            if (blk->s1 != blk) {
+               ++blkchange;
+               jmpfinal[blk->id] = blk->s1;
+            }
+         }
+      }
+   } while ((blk = blk->lnext) != fn->entry);
+   if (inschange) {
+      if (!(fn->prop & FNUSE)) filluses(fn);
+      copyopt(fn);
+   }
+   if (blkchange) {
+      do {
+         if (blk->s1) jmpfind(jmpfinal, &blk->s1);
+         if (blk->s2) jmpfind(jmpfinal, &blk->s2);
+         if (blk->s1 && blk->s1 == blk->s2) {
+            memset(blk->jmp.arg, 0, sizeof blk->jmp.arg);
+            blk->s2 = NULL;
+         }
+      } while ((blk = blk->lnext) != fn->entry);
+      fillpreds(fn);
+   }
+   free(jmpfinal);
+}
+
+/* vim:set ts=3 sw=3 expandtab: */