regalloc: fix lifetime construction for nested loops

Previously, given something like

```
1  a = ...
2  loop { // outer
3    b = do something with a
4    loop { // inner
5      ...
6      if (b < 0)
7        break 'inner;
8      if (b == 0)
9        return;
10     ...
11   }
12 }
```

Regalloc thought outer goes from 2..6, because 6 is the last place where
flow jumps directly back to 2. So `a` would have the lifetime [1,7).
However if neither the break nor return are taken, the inner loop
repeats and then control could flow back to 7 -> 3. But now the physical
location for `a` might have been clobbered between 8..10, which is
wrong.  This fixes that by making sure the outer loop is considered to
span 2..10.

The way I went about it might not be the best way of doing it. I'm not
100% certain that it's fully correct and will always find the correct
loopend, either. It's surprising it took this long to hit this edge
case.

1 files changed, 34 insertions, 17 deletions

diff --git a/ir/regalloc.c b/ir/regalloc.c
index bb7eff1..29d9f88 100644
--- a/ir/regalloc.c
+++ b/ir/regalloc.c
@@ -116,7 +116,7 @@ fixlive(struct function *fn)
    } while ((blk = blk->lnext) != fn->entry);
 
    if (ccopt.dbg.l) {
-      efmt("<< After liveness fixup >>\n");
+      bfmt(ccopt.dbgout, "<< After liveness fixup >>\n");
       irdump(fn);
    }
    if (defined != definedbuf) free(defined);
@@ -581,6 +581,10 @@ buildintervals(struct rega *ra)
    struct block *blk, *last;
    struct bitset **livein = alloc(ra->arena, ra->fn->nblk * sizeof *livein, 0);
    size_t bssize = BSSIZE(ninstr);
+   struct loops {
+      struct loops *link;
+      struct block *hdr, *end;
+   } *loops = NULL;
    for (int i = 0; i < ra->fn->nblk; ++i)
       livein[i] = allocz(ra->arena, bssize * sizeof *livein[i], 0);
    ra->intervals.temps = allocz(ra->arena, ninstr * sizeof *ra->intervals.temps, 0);
@@ -731,10 +735,21 @@ buildintervals(struct rega *ra)
       for (int i = 0; i < blk->npred; ++i) {
          struct block *pred = blkpred(blk, i);
          if (pred->id > blk->id)
-         loopend = loopend && loopend->id > pred->id ? loopend : pred;
+            loopend = loopend && loopend->id > pred->id ? loopend : pred;
       }
       if (loopend) {
-         // DBG("i'm loop header - @%d (to @%d)\n", blk->id, loopend->id);
+         if (loops) DBG("@lp @%d\n", blk->id);
+         for (struct loops *l = loops; l; l = l->link) {
+            /* a nested loop might end later than loopend, which lengthens this outer loop. */
+            /* XXX is this correct? proper loop analysis might be required */
+            if (l->hdr->id > loopend->id) break;
+            DBG("  check <@%d-@%d>\n", l->hdr->id, l->end->id);
+            if (l->hdr->id > blk->id && l->hdr->id < loopend->id && l->end->id > loopend->id)
+               loopend = l->end;
+         }
+         DBG("i'm loop header - @%d (to @%d)\n", blk->id, loopend->id);
+         /* append to loop list */
+         loops = alloccopy(ra->arena, &(struct loops) { loops, blk, loopend }, sizeof *loops, 0);
          for (uint opd = 0; bsiter(&opd, live, bssize); ++opd) {
             // DBG("  i have live %%%d\n", opd);
             addrange(&ra->intervals, opd, (struct range){blk->inumstart, loopend->inumstart + loopend->ins.n+1}, -1);
@@ -747,21 +762,23 @@ buildintervals(struct rega *ra)
       }
    } while ((blk = blk->lprev) != last);
 
-   for (int var = 0; var < ninstr; ++var) {
-      struct interval *it = &ra->intervals.temps[var];
-      if (!it->nrange) continue;
-      DBG("lifetime of %%%d: ", var);
-      for (int i = 0; i < it->nrange; ++i) {
-         struct range r = itrange(it, i);
-         DBG("[%d,%d)%s", r.from, r.to, i < it->nrange-1 ? ", " : "");
+   if (ccopt.dbg.r) {
+      for (int var = 0; var < ninstr; ++var) {
+         struct interval *it = &ra->intervals.temps[var];
+         if (!it->nrange) continue;
+         DBG("lifetime of %%%d: ", var);
+         for (int i = 0; i < it->nrange; ++i) {
+            struct range r = itrange(it, i);
+            DBG("[%d,%d)%s", r.from, r.to, i < it->nrange-1 ? ", " : "");
+         }
+         DBG("\n");
+      }
+      for (struct fixinterval *fx = ra->intervals.fixed; fx; fx = fx->next) {
+         DBG("fixed {");
+         for (int r = 0; rsiter(&r, fx->rs); ++r)
+            DBG("%s,", mctarg->rnames[r]);
+         DBG("}: [%d,%d)\n", fx->range.from, fx->range.to);
       }
-      DBG("\n");
-   }
-   for (struct fixinterval *fx = ra->intervals.fixed; fx; fx = fx->next) {
-      DBG("fixed {");
-      for (int r = 0; rsiter(&r, fx->rs); ++r)
-         DBG("%s,", mctarg->rnames[r]);
-      DBG("}: [%d,%d)\n", fx->range.from, fx->range.to);
    }
 }