ir: implement dominator tree computation

3 files changed, 40 insertions, 0 deletions

diff --git a/ir/cfg.c b/ir/cfg.c
index 758fa4e..671722d 100644
--- a/ir/cfg.c
+++ b/ir/cfg.c
@@ -52,4 +52,39 @@ sortrpo(struct function *fn)
    fn->prop |= FNBLKID | FNRPO;
 }
 
+/* also blkid */
+void
+filldom(struct function *fn)
+{
+   struct block *blk = fn->entry;
+   int i = 0;
+
+   FREQUIRE(FNRPO);
+
+   /* Implements 'A Simple, Fast Dominance Algorithm' by K. Cooper, T. Harvey, and K. Kennedy */
+   do blk->id = i++, blk->idom = NULL; while ((blk = blk->lnext) != fn->entry);
+   fn->entry->idom = fn->entry;
+   for (bool changed = 1; changed;) {
+      changed = 0;
+      blk = fn->entry->lnext;
+      do {
+         struct block *new = blkpred(blk, 0);
+         for (int i = 1; i < blk->npred; ++i) {
+            struct block *p = blkpred(blk, i);
+            if (p->idom) { /* new = intersect(p, new) */
+               while (p != new) {
+                  while (p->id > new->id) p = p->idom;
+                  while (p->id < new->id) new = new->idom;
+               }
+            }
+         }
+         if (blk->idom != new) {
+            blk->idom = new;
+            changed = 1;
+         }
+      } while ((blk = blk->lnext) != fn->entry);
+   }
+   fn->prop |= FNBLKID | FNDOM;
+}
+
 /* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/dump.c b/ir/dump.c
index f7d005c..7e7d650 100644
--- a/ir/dump.c
+++ b/ir/dump.c
@@ -219,6 +219,9 @@ dumpblk(struct function *fn, struct block *blk)
          bfmt(out, " @%d", blkpred(blk, i)->id);
       }
    }
+   if (fn->prop & FNDOM && blk->idom) {
+      bfmt(out, "\t; idom: @%d", blk->idom->id);
+   }
    ioputc(out, '\n');
    for (i = 0; i < blk->phi.n; ++i) {
       struct instr *phi = &instrtab[blk->phi.p[i]];
diff --git a/ir/ir.h b/ir/ir.h
index 1c7c02e..77f25d4 100644
--- a/ir/ir.h
+++ b/ir/ir.h
@@ -128,6 +128,7 @@ struct block {
    };
    struct block *lprev, *lnext;
    struct block *s1, *s2;
+   struct block *idom;
    vec_of(ushort) phi;
    vec_of(ushort) ins;
    struct { uchar t; union ref arg[2]; } jmp;
@@ -301,6 +302,7 @@ void copyopt(struct function *);
 
 /** cfg.c **/
 void sortrpo(struct function *fn);
+void filldom(struct function *fn);
 
 /** abi0.c **/
 void abi0(struct function *);