ir: blk loop index for spill cost

3 files changed, 39 insertions, 4 deletions

diff --git a/ir/cfg.c b/ir/cfg.c
index 984b6a9..86af3f3 100644
--- a/ir/cfg.c
+++ b/ir/cfg.c
@@ -95,4 +95,36 @@ filldom(struct function *fn)
    fn->prop |= FNBLKID | FNDOM;
 }
 
+static void
+loopmark(struct block *head, struct block *blk)
+{
+   if (blk->id < head->id || blk->visit == head->id) return;
+   blk->visit = head->id;
+   ++blk->loop;
+   for (int i = 0; i < blk->npred; ++i)
+      loopmark(head, blkpred(blk, i));
+}
+
+void
+fillloop(struct function *fn)
+{
+   struct block *b = fn->entry;
+   int id = 0;
+   FREQUIRE(FNRPO);
+   do {
+      b->id = id++;
+      b->visit = -1u;
+      b->loop = 0;
+   } while ((b = b->lnext) != fn->entry);
+   do {
+      for (int i = 0; i < b->npred; ++i) {
+         struct block *p = blkpred(b, i);
+         if (p->id > b->id) { /* b is loop header */
+            loopmark(b, p);
+         }
+      }
+   } while ((b = b->lnext) != fn->entry);
+   fn->prop |= FNBLKID;
+}
+
 /* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir/dump.c b/ir/dump.c
index b693a24..b0ce603 100644
--- a/ir/dump.c
+++ b/ir/dump.c
@@ -237,9 +237,10 @@ dumpblk(struct function *fn, struct block *blk)
          bfmt(out, " @%d", blkpred(blk, i)->id);
       }
    }
-   if (fn->prop & FNDOM && blk->idom) {
+   if (fn->prop & FNDOM && blk->idom)
       bfmt(out, "\t; idom: @%d", blk->idom->id);
-   }
+   if (blk->loop)
+      bfmt(out, "\t; loop depth: %d", blk->loop);
    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 a4da8ad..e7eb62a 100644
--- a/ir/ir.h
+++ b/ir/ir.h
@@ -130,6 +130,7 @@ struct block {
    int id;
    int npred;
    int visit;
+   ushort loop;
    int inumstart;
    union {
       struct block *_pred0;
@@ -322,8 +323,9 @@ void mem2reg(struct function *);
 void copyopt(struct function *);
 
 /** cfg.c **/
-void sortrpo(struct function *fn);
-void filldom(struct function *fn);
+void sortrpo(struct function *);
+void filldom(struct function *);
+void fillloop(struct function *);
 
 /** abi0.c **/
 void abi0(struct function *);