[legacy/mid] Add loop restructuring: unrolling, unswitching, interchange, dead-loop elimination

1 files changed, 227 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/dead_loop.cc b/rcc-legacy/src/mid/dead_loop.cc
new file mode 100644
index 0000000..26b915a
--- /dev/null
+++ b/rcc-legacy/src/mid/dead_loop.cc
@@ -0,0 +1,227 @@
+/* Source code for RCC-Legacy.
+   Copyright (C) 2026 Richard Qin
+
+This file is part of RCC.
+
+RCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+RCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with RCC; see the file LICENSE.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/// @file dead_loop.cc
+/// @brief Dead Loop Elimination: removal of entire loops that have no side-effects, are provably
+/// terminating, and have no live-outs.
+///
+/// See docs/dead_loop.md for architectural notes.
+
+#include "rcc/all.h"
+#include "rcc/loopinfo.h"
+
+#include <unordered_set>
+#include <vector>
+
+namespace rcc {
+
+namespace {
+
+bool has_side_effect_op(uint op) {
+    if (isstore(op))
+        return true;
+    if (isalloc(op))
+        return true;
+    if (ispar(op))
+        return true;
+    if (isarg(op))
+        return true;
+    if (op == Ocall)
+        return true;
+    if (op == Oblit0 || op == Oblit1)
+        return true;
+    if (op == Ovastart || op == Ovaarg)
+        return true;
+    if (op == Odbgloc)
+        return true;
+    if (op == Osel0 || op == Osel1)
+        return true;
+    return false;
+}
+
+bool defined_outside(Fn* fn, const Loop& L, Ref r) {
+    if (rtype(r) == RCon)
+        return true;
+    if (rtype(r) != RTmp)
+        return false;
+    if (r.val >= static_cast<uint>(fn->ntmp))
+        return false;
+    uint bid = fn->tmp[r.val].bid;
+    return L.body_bid.find(bid) == L.body_bid.end();
+}
+
+Ins* find_cmp_in(Blk* b, Ref cond) {
+    for (uint i = 0; i < b->nins; i++)
+        if (req(b->ins[i].to, cond))
+            return &b->ins[i];
+    return nullptr;
+}
+
+int find_biv_idx(const std::vector<Biv>& bivs, Ref r) {
+    for (size_t k = 0; k < bivs.size(); k++)
+        if (req(bivs[k].to, r))
+            return static_cast<int>(k);
+    return -1;
+}
+
+void collect_body_defs(const Loop& L, std::vector<Ref>& defs) {
+    for (Blk* b : L.body) {
+        for (Phi* p = b->phi; p; p = p->link)
+            if (rtype(p->to) == RTmp)
+                defs.push_back(p->to);
+        for (uint k = 0; k < b->nins; k++)
+            if (rtype(b->ins[k].to) == RTmp)
+                defs.push_back(b->ins[k].to);
+    }
+}
+
+bool all_uses_inside(Fn* fn, const Loop& L, Ref tmp_ref) {
+    if (rtype(tmp_ref) != RTmp)
+        return true;
+    if (tmp_ref.val >= static_cast<uint>(fn->ntmp))
+        return true;
+    Tmp* t = &fn->tmp[tmp_ref.val];
+    for (uint u = 0; u < t->nuse; u++) {
+        const Use& uu = t->use[u];
+        if (L.body_bid.find(uu.bid) == L.body_bid.end())
+            return false;
+    }
+    return true;
+}
+
+bool delete_loop_if_dead(Fn* fn, const Loop& L) {
+    // Topology: unique exit_block + unique exiting_block
+    Blk* exit_block = nullptr;
+    Blk* exiting_block = nullptr;
+    for (Blk* b : L.body) {
+        Blk* succs[2] = {b->s1, b->s2};
+        for (Blk* s : succs) {
+            if (!s)
+                continue;
+            if (L.body_bid.find(s->id) != L.body_bid.end())
+                continue;  // Internal edge
+            // Exit loop edge
+            if (!exit_block) {
+                exit_block = s;
+                exiting_block = b;
+            } else if (exit_block != s || exiting_block != b) {
+                return false;  // Multiple exits or multiple exiting blocks
+            }
+        }
+    }
+    if (!exit_block)
+        return false;  // No exit -- infinite loop
+
+    // Termination: at least one constant BIV + header Jjnz cmp(BIV, invariant)
+    std::vector<Biv> bivs;
+    detect_bivs(fn, L, bivs);
+    if (bivs.empty())
+        return false;
+    if (L.header->jmp.type != Jjnz)
+        return false;
+    Ref cond = L.header->jmp.arg;
+    if (rtype(cond) != RTmp)
+        return false;
+    Ins* cmp = find_cmp_in(L.header, cond);
+    if (!cmp)
+        return false;
+    int bi = find_biv_idx(bivs, cmp->arg[0]);
+    Ref other = cmp->arg[1];
+    if (bi < 0) {
+        bi = find_biv_idx(bivs, cmp->arg[1]);
+        other = cmp->arg[0];
+    }
+    if (bi < 0)
+        return false;
+    if (!defined_outside(fn, L, other))
+        return false;
+    if (exiting_block != L.header)
+        return false;
+
+    // Side-effect scan
+    for (Blk* b : L.body) {
+        for (uint k = 0; k < b->nins; k++) {
+            if (has_side_effect_op(b->ins[k].op))
+                return false;
+        }
+    }
+
+    // Live-out scan
+    for (Phi* p = exit_block->phi; p; p = p->link) {
+        for (uint k = 0; k < p->narg; k++) {
+            if (p->blk[k] != exiting_block)
+                continue;
+            if (!defined_outside(fn, L, p->arg[k]))
+                return false;
+        }
+    }
+    std::vector<Ref> defs;
+    collect_body_defs(L, defs);
+    for (Ref r : defs) {
+        if (!all_uses_inside(fn, L, r))
+            return false;
+    }
+
+    for (Phi* p = exit_block->phi; p; p = p->link) {
+        for (uint k = 0; k < p->narg; k++)
+            if (p->blk[k] == L.preheader)
+                return false;
+    }
+
+    // Rewrite
+    // preheader's jmp outgoing edge: the one pointing to header is changed to point to exit_block;
+    if (L.preheader->s1 == L.header)
+        L.preheader->s1 = exit_block;
+    if (L.preheader->s2 == L.header)
+        L.preheader->s2 = exit_block;
+    for (Phi* p = exit_block->phi; p; p = p->link) {
+        for (uint k = 0; k < p->narg; k++)
+            if (p->blk[k] == exiting_block)
+                p->blk[k] = L.preheader;
+    }
+
+    return true;
+}
+
+}  // namespace
+
+void dead_loop(Ctx* ctx, Fn* fn) {
+    fillpreds(ctx, fn);
+    fillcfg(ctx, fn);
+    filluse(ctx, fn);
+
+    std::vector<Loop> loops;
+    find_loops(fn, loops);
+    if (loops.empty())
+        return;
+
+    int deleted = 0;
+    for (const Loop& L : loops) {
+        if (delete_loop_if_dead(fn, L))
+            deleted++;
+    }
+
+    if (debug['L']) {
+        FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr;
+        fprintf(out, "\n> dead_loop %s: deleted %d of %zu loop(s)\n", fn->name, deleted,
+                loops.size());
+    }
+}
+
+}  // namespace rcc