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

1 files changed, 469 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/loopswap.cc b/rcc-legacy/src/mid/loopswap.cc
new file mode 100644
index 0000000..cd8acf0
--- /dev/null
+++ b/rcc-legacy/src/mid/loopswap.cc
@@ -0,0 +1,469 @@
+/* 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 loopswap.cc
+/// @brief Integer perfect 2-level nested loop interchange.
+///
+/// See docs/loopswap.md for architectural notes.
+
+#include "rcc/all.h"
+#include "rcc/loopinfo.h"
+
+#include <cstdlib>
+#include <unordered_set>
+#include <vector>
+
+namespace rcc {
+
+namespace {
+
+// Helper: reaches
+bool reaches(Fn* fn, Ref r, Ref target, std::unordered_set<uint>& visiting, int budget) {
+    if (req(r, target))
+        return true;
+    if (budget <= 0)
+        return false;
+    if (rtype(r) != RTmp || r.val >= static_cast<uint>(fn->ntmp))
+        return false;
+    if (!visiting.insert(r.val).second)
+        return true;
+
+    Ins* def = fn->tmp[r.val].def;
+    if (def && def->op == Ocopy) {
+        bool ok = reaches(fn, def->arg[0], target, visiting, budget - 1);
+        visiting.erase(r.val);
+        return ok;
+    }
+    for (Blk* bb = fn->start; bb; bb = bb->link) {
+        for (Phi* p = bb->phi; p; p = p->link) {
+            if (!req(p->to, r))
+                continue;
+            bool ok = true;
+            for (uint k = 0; k < p->narg; k++) {
+                if (req(p->arg[k], r))
+                    continue;
+                if (!reaches(fn, p->arg[k], target, visiting, budget - 1)) {
+                    ok = false;
+                    break;
+                }
+            }
+            visiting.erase(r.val);
+            return ok;
+        }
+    }
+    visiting.erase(r.val);
+    return false;
+}
+
+bool carries(Fn* fn, Ref r, Ref target) {
+    std::unordered_set<uint> v;
+    return reaches(fn, r, target, v, 64);
+}
+
+// Affine decomposition
+struct Aff {
+    int64_t outer_c;
+    int64_t inner_c;
+};
+
+Aff affine(Fn* fn, Ref r, Ref outer_to, Ref inner_to, int depth) {
+    if (depth > 24)
+        return {0, 0};
+    if (rtype(r) == RCon)
+        return {0, 0};
+    if (rtype(r) != RTmp)
+        return {0, 0};
+    if (carries(fn, r, outer_to))
+        return {1, 0};
+    if (carries(fn, r, inner_to))
+        return {0, 1};
+    if (r.val >= static_cast<uint>(fn->ntmp))
+        return {0, 0};
+    Ins* def = fn->tmp[r.val].def;
+    if (!def)
+        return {0, 0};
+    switch (def->op) {
+        case Oadd: {
+            Aff a = affine(fn, def->arg[0], outer_to, inner_to, depth + 1);
+            Aff b = affine(fn, def->arg[1], outer_to, inner_to, depth + 1);
+            return {a.outer_c + b.outer_c, a.inner_c + b.inner_c};
+        }
+        case Osub: {
+            Aff a = affine(fn, def->arg[0], outer_to, inner_to, depth + 1);
+            Aff b = affine(fn, def->arg[1], outer_to, inner_to, depth + 1);
+            return {a.outer_c - b.outer_c, a.inner_c - b.inner_c};
+        }
+        case Omul: {
+            int64_t c;
+            if (ref_is_const(fn, def->arg[1], c)) {
+                Aff a = affine(fn, def->arg[0], outer_to, inner_to, depth + 1);
+                return {a.outer_c * c, a.inner_c * c};
+            }
+            if (ref_is_const(fn, def->arg[0], c)) {
+                Aff a = affine(fn, def->arg[1], outer_to, inner_to, depth + 1);
+                return {a.outer_c * c, a.inner_c * c};
+            }
+            return {0, 0};
+        }
+        case Oextsw:
+        case Ocopy:
+            return affine(fn, def->arg[0], outer_to, inner_to, depth + 1);
+        default:
+            return {0, 0};
+    }
+}
+
+// Perfect nest: L1.body \ L2.body \ {L1.header, L1.latch} must only contain empty Jjmp blocks.
+bool perfect_nest(const Loop& L1, const Loop& L2) {
+    for (Blk* bb : L1.body) {
+        if (bb == L1.header || bb == L1.latch)
+            continue;
+        if (L2.body_bid.count(bb->id))
+            continue;
+        if (bb->nins != 0)
+            return false;
+        if (bb->jmp.type != Jjmp)
+            return false;
+    }
+    return true;
+}
+
+// Does the cmp ins for header.jmp.arg reference bv.to (or its carrier equiv)?
+int find_header_cmp(Fn* fn, const Loop& L, const Biv& bv) {
+    Ref a = L.header->jmp.arg;
+    if (rtype(a) != RTmp)
+        return -1;
+    for (uint k = 0; k < L.header->nins; k++) {
+        Ins* ii = &L.header->ins[k];
+        if (!req(ii->to, a))
+            continue;
+        if (carries(fn, ii->arg[0], bv.to) || carries(fn, ii->arg[1], bv.to))
+            return static_cast<int>(k);
+        return -1;
+    }
+    return -1;
+}
+
+// Find index of BIV's latch increment ins (the Oadd) in latch->ins array.
+int find_latch_inc(const Loop& L, const Biv& bv) {
+    Phi* P = nullptr;
+    for (Phi* p = L.header->phi; p; p = p->link)
+        if (req(p->to, bv.to)) {
+            P = p;
+            break;
+        }
+    if (!P)
+        return -1;
+    Ref next = Ref::none();
+    for (uint k = 0; k < P->narg; k++)
+        if (P->blk[k] == L.latch) {
+            next = P->arg[k];
+            break;
+        }
+    if (rtype(next) != RTmp)
+        return -1;
+    for (uint k = 0; k < L.latch->nins; k++)
+        if (req(L.latch->ins[k].to, next) && L.latch->ins[k].op == Oadd)
+            return static_cast<int>(k);
+    return -1;
+}
+
+Phi* find_phi(Blk* b, Ref to) {
+    for (Phi* p = b->phi; p; p = p->link)
+        if (req(p->to, to))
+            return p;
+    return nullptr;
+}
+
+void unlink_phi(Blk* b, Phi* t) {
+    for (Phi** cur = &b->phi; *cur; cur = &(*cur)->link)
+        if (*cur == t) {
+            *cur = t->link;
+            t->link = nullptr;
+            return;
+        }
+}
+
+void prepend_phi(Blk* b, Phi* p) {
+    p->link = b->phi;
+    b->phi = p;
+}
+
+void rewrite_phi_blk(Phi* p, Blk* from, Blk* to) {
+    for (uint k = 0; k < p->narg; k++)
+        if (p->blk[k] == from)
+            p->blk[k] = to;
+}
+
+void rewrite_uses(Fn* fn, Ref from, Ref to) {
+    for (Blk* b = fn->start; b; b = b->link) {
+        for (Phi* p = b->phi; p; p = p->link)
+            for (uint k = 0; k < p->narg; k++)
+                if (req(p->arg[k], from))
+                    p->arg[k] = to;
+        for (uint k = 0; k < b->nins; k++) {
+            Ins* i = &b->ins[k];
+            if (req(i->arg[0], from))
+                i->arg[0] = to;
+            if (req(i->arg[1], from))
+                i->arg[1] = to;
+        }
+        if (req(b->jmp.arg, from))
+            b->jmp.arg = to;
+        if (req(b->jmp.arg2, from))
+            b->jmp.arg2 = to;
+    }
+}
+
+struct AccessRec {
+    Ref addr;
+    int64_t inner_s;
+    bool is_store;
+};
+
+bool try_swap(Ctx* ctx, Fn* fn, const Loop& L1, const Loop& L2) {
+    if (!perfect_nest(L1, L2))
+        return false;
+
+    std::vector<Biv> bs1, bs2;
+    detect_bivs(fn, L1, bs1);
+    detect_bivs(fn, L2, bs2);
+    if (bs1.empty() || bs2.empty())
+        return false;
+
+    // Pick the BIV referenced by header.cmp (SysY loops typically compare one BIV).
+    Biv b1{}, b2{};
+    int cmp1 = -1, cmp2 = -1;
+    for (auto& bv : bs1) {
+        int idx = find_header_cmp(fn, L1, bv);
+        if (idx >= 0) {
+            b1 = bv;
+            cmp1 = idx;
+            break;
+        }
+    }
+    for (auto& bv : bs2) {
+        int idx = find_header_cmp(fn, L2, bv);
+        if (idx >= 0) {
+            b2 = bv;
+            cmp2 = idx;
+            break;
+        }
+    }
+    if (cmp1 < 0 || cmp2 < 0)
+        return false;
+    if ((b1.cls != Kw && b1.cls != Kl) || (b2.cls != Kw && b2.cls != Kl))
+        return false;
+
+    int inc1 = find_latch_inc(L1, b1);
+    int inc2 = find_latch_inc(L2, b2);
+    if (inc1 < 0 || inc2 < 0)
+        return false;
+
+    // Scan L2.body: integer only + decompose addr.
+    int64_t sum_outer = 0, sum_inner = 0;
+    std::vector<AccessRec> mems;
+    for (Blk* bb : L2.body) {
+        for (uint k = 0; k < bb->nins; k++) {
+            Ins* ii = &bb->ins[k];
+            int op = ii->op;
+            if (op == Ocall)
+                return false;
+            if (ii->cls == Ks || ii->cls == Kd)
+                return false;
+            bool is_ld = isload(op);
+            bool is_st = isstore(op);
+            if (!is_ld && !is_st)
+                continue;
+            if (op == Ostores || op == Ostored)
+                return false;
+            Ref addr = is_st ? ii->arg[1] : ii->arg[0];
+            Aff a = affine(fn, addr, b1.to, b2.to, 0);
+            sum_outer += std::abs(a.outer_c);
+            sum_inner += std::abs(a.inner_c);
+            mems.push_back({addr, a.inner_c, is_st});
+        }
+    }
+
+    // accumulator pattern: if there are stores => every store has inner_s==0 and matches a load
+    // with same addr and inner_s==0.
+    bool has_store = false;
+    for (auto& m : mems)
+        if (m.is_store) {
+            has_store = true;
+            break;
+        }
+    if (has_store) {
+        for (auto& s : mems) {
+            if (!s.is_store)
+                continue;
+            if (s.inner_s != 0)
+                return false;
+            bool found = false;
+            for (auto& l : mems) {
+                if (!l.is_store && req(l.addr, s.addr) && l.inner_s == 0) {
+                    found = true;
+                    break;
+                }
+            }
+            if (!found)
+                return false;
+        }
+    }
+
+    if (sum_inner == 0)
+        return false;
+    if (sum_outer * 4 >= sum_inner)
+        return false;
+
+    // Execute
+    Blk* h1 = L1.header;
+    Blk* h2 = L2.header;
+
+    Phi* P1 = find_phi(h1, b1.to);
+    Phi* P2 = find_phi(h2, b2.to);
+    if (!P1 || !P2)
+        return false;
+
+    // Collect self-loop carrier of b1.to on L2.header (Braun artifact; invalid after swap, needs
+    // removal).
+    std::vector<Phi*> stale;
+    for (Phi* p = h2->phi; p; p = p->link) {
+        if (p->narg != 2)
+            continue;
+        Ref pre = Ref::none();
+        bool is_self = false;
+        for (uint k = 0; k < p->narg; k++) {
+            if (p->blk[k] == L2.preheader)
+                pre = p->arg[k];
+            else if (p->blk[k] == L2.latch && req(p->arg[k], p->to))
+                is_self = true;
+        }
+        if (is_self && carries(fn, pre, b1.to))
+            stale.push_back(p);
+    }
+
+    // Snapshot: copy 4 target ins before swap to avoid distortion.
+    Ins C1 = h1->ins[cmp1];
+    Ins C2 = h2->ins[cmp2];
+    Ins I1 = L1.latch->ins[inc1];
+    Ins I2 = L2.latch->ins[inc2];
+
+    // Swap phi: unlink + rewrite edge + prepend to the other.
+    unlink_phi(h1, P1);
+    unlink_phi(h2, P2);
+    rewrite_phi_blk(P1, L1.preheader, L2.preheader);
+    rewrite_phi_blk(P1, L1.latch, L2.latch);
+    rewrite_phi_blk(P2, L2.preheader, L1.preheader);
+    rewrite_phi_blk(P2, L2.latch, L1.latch);
+    prepend_phi(h1, P2);
+    prepend_phi(h2, P1);
+
+    // Swap cmp ins + jmp descriptor.
+    h1->ins[cmp1].op = Onop;
+    h2->ins[cmp2].op = Onop;
+    addins(ctx, &h1->ins, &h1->nins, &C2);
+    addins(ctx, &h2->ins, &h2->nins, &C1);
+    std::swap(h1->jmp.arg, h2->jmp.arg);
+    std::swap(h1->jmp.cls, h2->jmp.cls);
+    std::swap(h1->jmp.arg2, h2->jmp.arg2);
+
+    // Swap increment.
+    L1.latch->ins[inc1].op = Onop;
+    L2.latch->ins[inc2].op = Onop;
+    addins(ctx, &L1.latch->ins, &L1.latch->nins, &I2);
+    addins(ctx, &L2.latch->ins, &L2.latch->nins, &I1);
+
+    // Invalidate carriers: rewrite_uses to substitute with b1.to, then unlink phi.
+    for (Phi* s : stale) {
+        rewrite_uses(fn, s->to, b1.to);
+        unlink_phi(h2, s);
+    }
+
+    return true;
+}
+
+// L2 is immediate-child of L1: strict subset of body, with no L3 strictly in between.
+bool is_immediate_child(const std::vector<Loop>& loops, size_t i_par, size_t j_chl) {
+    const Loop& par = loops[i_par];
+    const Loop& chl = loops[j_chl];
+    if (chl.body_bid.size() >= par.body_bid.size())
+        return false;
+    for (uint id : chl.body_bid)
+        if (!par.body_bid.count(id))
+            return false;
+    for (size_t m = 0; m < loops.size(); m++) {
+        if (m == i_par || m == j_chl)
+            continue;
+        const Loop& mid = loops[m];
+        if (mid.body_bid.size() <= chl.body_bid.size())
+            continue;
+        if (mid.body_bid.size() >= par.body_bid.size())
+            continue;
+        bool chl_in_mid = true;
+        for (uint id : chl.body_bid)
+            if (!mid.body_bid.count(id)) {
+                chl_in_mid = false;
+                break;
+            }
+        if (!chl_in_mid)
+            continue;
+        bool mid_in_par = true;
+        for (uint id : mid.body_bid)
+            if (!par.body_bid.count(id)) {
+                mid_in_par = false;
+                break;
+            }
+        if (mid_in_par)
+            return false;
+    }
+    return true;
+}
+
+}  // namespace
+
+void loopinterchange(Ctx* ctx, Fn* fn) {
+    std::vector<Loop> loops;
+    find_loops(fn, loops);
+    if (loops.size() < 2)
+        return;
+
+    for (size_t i = 0; i < loops.size(); i++) {
+        Loop& L1 = loops[i];
+        Loop* L2 = nullptr;
+        bool amb = false;
+        for (size_t j = 0; j < loops.size(); j++) {
+            if (i == j)
+                continue;
+            if (!is_immediate_child(loops, i, j))
+                continue;
+            if (L2) {
+                amb = true;
+                break;
+            }
+            L2 = &loops[j];
+        }
+        if (!L2 || amb)
+            continue;
+        if (try_swap(ctx, fn, L1, *L2))
+            return;  // One swap per pass, CFG/loops are invalidated
+    }
+}
+
+}  // namespace rcc