[legacy/mid] Add loop idiom recognition: memset/memcpy, scalar replacement, reduction unrolling

1 files changed, 528 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/reduction_unroll.cc b/rcc-legacy/src/mid/reduction_unroll.cc
new file mode 100644
index 0000000..08edb3d
--- /dev/null
+++ b/rcc-legacy/src/mid/reduction_unroll.cc
@@ -0,0 +1,528 @@
+/* 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 reduction_unroll.cc
+/// @brief Identifies inner loop integer reductions and unrolls them into K-way parallel
+/// accumulators.
+///
+/// See docs/reduction_unroll.md for architectural notes.
+
+#include "rcc/all.h"
+#include "rcc/loopinfo.h"
+
+#include <algorithm>
+#include <cstring>
+#include <unordered_set>
+#include <vector>
+
+namespace rcc {
+
+namespace {
+
+constexpr int kUnrollK = 4;
+
+int load_bytes(int op, int cls) {
+    switch (op) {
+        case Oloadsb:
+        case Oloadub:
+            return 1;
+        case Oloadsh:
+        case Oloaduh:
+            return 2;
+        case Oloadsw:
+        case Oloaduw:
+            return 4;
+        case Oload:
+            return (cls == Kl || cls == Kd) ? 8 : 4;
+        default:
+            return 0;
+    }
+}
+
+bool is_int_reduce_op(int op) {
+    return op == Oadd || op == Omul || op == Oand || op == Oor || op == Oxor;
+}
+
+int64_t identity_for(int op) {
+    switch (op) {
+        case Oadd:
+        case Oor:
+        case Oxor:
+            return 0;
+        case Omul:
+            return 1;
+        case Oand:
+            return -1;
+        default:
+            return 0;
+    }
+}
+
+bool is_int_cls(int cls) {
+    return cls == Kw || cls == Kl;
+}
+
+struct Match {
+    PointerIV iv_p;  // pointer IV
+    Phi* phi_p;      // pointer phi
+    Phi* phi_s;      // accumulator phi
+    Ref s_init;      // accumulator init (preheader side)
+    Ref s_next;      // accumulator next (latch side, = s_op.to)
+    Ins* load_ins;   // load inside body
+    Ins* op_ins;     // reduce op inside body (s.next = OP s, v)
+    Ins* p_inc_ins;  // pointer increment inside body
+    Ref end;         // end ref for exit cmp
+    Blk* after;      // exit block
+    int op;          // op_ins->op
+    int s_cls;       // accumulator and op cls
+    int load_op;     // load_ins->op
+    int load_cls;    // load_ins->cls
+};
+
+// Check latch body.
+bool scan_body(Fn* /*fn*/, const Loop& L, const PointerIV& iv_p, Phi* phi_s, Match* m) {
+    m->load_ins = nullptr;
+    m->op_ins = nullptr;
+    m->p_inc_ins = nullptr;
+
+    Ref p = iv_p.phi_to;
+    Ref s = phi_s->to;
+    Ref s_next = Ref::none(), p_next = iv_p.next;
+    for (uint k = 0; k < phi_s->narg; k++)
+        if (phi_s->blk[k] == L.latch)
+            s_next = phi_s->arg[k];
+    if (rtype(s_next) != RTmp)
+        return false;
+
+    for (Blk* bb : L.body) {
+        for (uint k = 0; k < bb->nins; k++) {
+            Ins* i = &bb->ins[k];
+            int op = i->op;
+            // header allows exit cmp (guaranteed unique by check_exit_cmp)
+            if (bb == L.header && req(i->to, L.header->jmp.arg))
+                continue;
+            if (op == Onop)
+                continue;
+            if (op == Ocall || op == Oalloc4 || op == Oalloc8 || op == Oalloc16 || op == Ovaarg ||
+                op == Ovastart || op == Odbgloc || op == Osel0 || op == Osel1 || op == Oblit0 ||
+                op == Oblit1 || op == Osalloc || op == Oudiv || op == Ourem || op == Odiv ||
+                op == Orem)
+                return false;
+            // pointer increment?
+            if (req(i->to, p_next)) {
+                if (m->p_inc_ins)
+                    return false;
+                m->p_inc_ins = i;
+                continue;
+            }
+            // accumulator increment?
+            if (req(i->to, s_next)) {
+                if (m->op_ins)
+                    return false;
+                if (!is_int_reduce_op(op))
+                    return false;
+                if (!is_int_cls(static_cast<int>(i->cls)))
+                    return false;
+                // Must be OP(s, v) or OP(v, s)
+                if (!req(i->arg[0], s) && !req(i->arg[1], s))
+                    return false;
+                m->op_ins = i;
+                continue;
+            }
+            // Is it a load?
+            int lb = load_bytes(op, static_cast<int>(i->cls));
+            if (lb > 0) {
+                if (m->load_ins)
+                    return false;
+                if (!req(i->arg[0], p))
+                    return false;
+                m->load_ins = i;
+                continue;
+            }
+            // Reject any other ins (reduction form requires a clean body)
+            return false;
+        }
+    }
+    if (!m->load_ins || !m->op_ins || !m->p_inc_ins)
+        return false;
+    // Loaded value must equal the other operand of the OP
+    Ref v_ref = m->load_ins->to;
+    if (!(req(m->op_ins->arg[0], v_ref) || req(m->op_ins->arg[1], v_ref)))
+        return false;
+    // class & width
+    int lb = load_bytes(m->load_ins->op, static_cast<int>(m->load_ins->cls));
+    if (lb != iv_p.step)
+        return false;
+    if (m->op_ins->cls != m->load_ins->cls)
+        return false;
+    m->s_next = s_next;
+    return true;
+}
+
+bool try_match_loop(Fn* fn, const Loop& L, Match* m) {
+    if (L.body.size() > 2)
+        return false;
+    if (!L.preheader)
+        return false;
+    if (L.preheader->jmp.type != Jjmp)
+        return false;
+    if (L.preheader->s1 != L.header || L.preheader->s2 != nullptr)
+        return false;
+
+    // Collect header phis.
+    PointerIV iv_p{};
+    Phi* phi_p = nullptr;
+    Phi* phi_s = nullptr;
+    int n_ptr = 0, n_acc = 0;
+    for (Phi* ph = L.header->phi; ph; ph = ph->link) {
+        PointerIV cand{};
+        if (pick_pointer_iv(fn, L, ph, &cand)) {
+            iv_p = cand;
+            phi_p = ph;
+            n_ptr++;
+            continue;
+        }
+        if (ph->narg == 2 && is_int_cls(static_cast<int>(ph->cls))) {
+            phi_s = ph;
+            n_acc++;
+            continue;
+        }
+        return false;  // Reject any third type of phi
+    }
+    if (n_ptr != 1 || n_acc != 1)
+        return false;
+
+    // accumulator phi incoming edges
+    Ref s_init = Ref::none();
+    for (uint k = 0; k < phi_s->narg; k++) {
+        if (phi_s->blk[k] == L.preheader)
+            s_init = phi_s->arg[k];
+        else if (phi_s->blk[k] != L.latch)
+            return false;
+    }
+    if (rtype(s_init) == -1)
+        return false;
+
+    Ref end_ref;
+    Blk* after = nullptr;
+    if (!check_exit_cmp(fn, L, iv_p.phi_to, &end_ref, &after))
+        return false;
+
+    if (!scan_body(fn, L, iv_p, phi_s, m))
+        return false;
+
+    // accumulator cls == op cls, must match load cls (same bitwidth)
+    if (phi_s->cls != m->op_ins->cls)
+        return false;
+
+    if (has_outside_use(fn, L)) {
+        // Check outside loop uses strictly.
+        std::unordered_set<uint> loop_def;
+        for (Blk* bb : L.body) {
+            for (Phi* ph = bb->phi; ph; ph = ph->link)
+                if (rtype(ph->to) == RTmp)
+                    loop_def.insert(ph->to.val);
+            for (uint k = 0; k < bb->nins; k++)
+                if (rtype(bb->ins[k].to) == RTmp)
+                    loop_def.insert(bb->ins[k].to.val);
+        }
+        loop_def.erase(phi_p->to.val);
+        loop_def.erase(phi_s->to.val);
+        for (Blk* b = fn->start; b; b = b->link) {
+            if (L.body_bid.count(b->id))
+                continue;
+            for (Phi* ph = b->phi; ph; ph = ph->link)
+                for (uint k = 0; k < ph->narg; k++)
+                    if (rtype(ph->arg[k]) == RTmp && loop_def.count(ph->arg[k].val))
+                        return false;
+            for (uint k = 0; k < b->nins; k++) {
+                Ins* i = &b->ins[k];
+                for (int a = 0; a < 2; a++)
+                    if (rtype(i->arg[a]) == RTmp && loop_def.count(i->arg[a].val))
+                        return false;
+            }
+            if (rtype(b->jmp.arg) == RTmp && loop_def.count(b->jmp.arg.val))
+                return false;
+            if (rtype(b->jmp.arg2) == RTmp && loop_def.count(b->jmp.arg2.val))
+                return false;
+        }
+    }
+
+    m->iv_p = iv_p;
+    m->phi_p = phi_p;
+    m->phi_s = phi_s;
+    m->s_init = s_init;
+    m->end = end_ref;
+    m->after = after;
+    m->op = m->op_ins->op;
+    m->s_cls = m->op_ins->cls;
+    m->load_op = m->load_ins->op;
+    m->load_cls = static_cast<int>(m->load_ins->cls);
+    return true;
+}
+
+Phi* make_phi(Ctx* ctx, int cls, Ref to, Ref arg_pre, Blk* pre, Ref arg_back, Blk* back) {
+    Phi* p = static_cast<Phi*>(alloc(ctx, sizeof(Phi)));
+    p->cls = static_cast<short>(cls);
+    p->visit = 0;
+    p->to = to;
+    p->narg = 2;
+    p->arg = static_cast<Ref*>(vnew(ctx, 2, sizeof(Ref), PFn));
+    p->blk = static_cast<Blk**>(vnew(ctx, 2, sizeof(Blk*), PFn));
+    p->arg[0] = arg_pre;
+    p->blk[0] = pre;
+    p->arg[1] = arg_back;
+    p->blk[1] = back;
+    p->link = nullptr;
+    return p;
+}
+
+static int rd_seq = 0;
+
+void execute(Ctx* ctx, Fn* fn, const Loop& L, const Match& m) {
+    int K = kUnrollK;
+    int S = static_cast<int>(m.iv_p.step);
+    int KS = K * S;
+    int my_seq = rd_seq++;
+
+    Blk* pre = L.preheader;
+    Blk* tail_hdr = L.header;
+    int s_cls = m.s_cls;
+    int load_op = m.load_op;
+    int load_cls = m.load_cls;
+    int op = m.op;
+
+    // Append size / size_main / end_main to the end of preheader
+    Ref size_ref = newtmp(ctx, "rd.size", Kl, fn);
+    Ref size_main_ref = newtmp(ctx, "rd.szm", Kl, fn);
+    Ref end_main_ref = newtmp(ctx, "rd.endm", Kl, fn);
+
+    Ins sub_i{};
+    sub_i.op = Osub;
+    sub_i.cls = Kl;
+    sub_i.to = size_ref;
+    sub_i.arg[0] = m.end;
+    sub_i.arg[1] = m.iv_p.base;
+    addins(ctx, &pre->ins, &pre->nins, &sub_i);
+
+    Ins and_i{};
+    and_i.op = Oand;
+    and_i.cls = Kl;
+    and_i.to = size_main_ref;
+    and_i.arg[0] = size_ref;
+    and_i.arg[1] = getcon(ctx, -static_cast<int64_t>(KS), fn);
+    addins(ctx, &pre->ins, &pre->nins, &and_i);
+
+    Ins add_i{};
+    add_i.op = Oadd;
+    add_i.cls = Kl;
+    add_i.to = end_main_ref;
+    add_i.arg[0] = m.iv_p.base;
+    add_i.arg[1] = size_main_ref;
+    addins(ctx, &pre->ins, &pre->nins, &add_i);
+
+    // Create main_header / main_body / main_join
+    Blk* mh = newblk(ctx);
+    mh->name = strf(ctx, PFn, "rd%d.mh", my_seq);
+    mh->id = fn->nblk++;
+
+    Blk* mb = newblk(ctx);
+    mb->name = strf(ctx, PFn, "rd%d.mb", my_seq);
+    mb->id = fn->nblk++;
+
+    Blk* mj = newblk(ctx);
+    mj->name = strf(ctx, PFn, "rd%d.mj", my_seq);
+    mj->id = fn->nblk++;
+
+    // Pre-generate names (main_header phi.to, etc.)
+    Ref pm_ref = newtmp(ctx, "rd.pm", Kl, fn);
+    Ref pm_next_ref = newtmp(ctx, "rd.pm.n", Kl, fn);
+    std::vector<Ref> s_refs(static_cast<size_t>(K)), s_next_refs(static_cast<size_t>(K));
+    for (size_t i = 0; i < static_cast<size_t>(K); i++) {
+        s_refs[i] = newtmp(ctx, "rd.s", s_cls, fn);
+        s_next_refs[i] = newtmp(ctx, "rd.s.n", s_cls, fn);
+    }
+
+    // Identity ref
+    Ref ident_ref = getcon(ctx, identity_for(op), fn);
+
+    // main_header phi chain: pm + s0..K-1
+    Phi* phi_pm = make_phi(ctx, Kl, pm_ref, m.iv_p.base, pre, pm_next_ref, mb);
+    mh->phi = phi_pm;
+    Phi* tail_phi = phi_pm;
+    for (size_t i = 0; i < static_cast<size_t>(K); i++) {
+        Ref init = (i == 0) ? m.s_init : ident_ref;
+        Phi* ph = make_phi(ctx, s_cls, s_refs[i], init, pre, s_next_refs[i], mb);
+        tail_phi->link = ph;
+        tail_phi = ph;
+    }
+
+    // main_header cmp + jnz
+    Ref cmpm_ref = newtmp(ctx, "rd.cmpm", Kw, fn);
+    Ins cmpm_i{};
+    cmpm_i.op = Ocultl;
+    cmpm_i.cls = Kw;
+    cmpm_i.to = cmpm_ref;
+    cmpm_i.arg[0] = pm_ref;
+    cmpm_i.arg[1] = end_main_ref;
+    addins(ctx, &mh->ins, &mh->nins, &cmpm_i);
+    mh->jmp.type = Jjnz;
+    mh->jmp.arg = cmpm_ref;
+    mh->jmp.arg2 = Ref::none();
+    mh->s1 = mb;
+    mh->s2 = mj;
+
+    // main_body: K loads + K ops + 1 pointer step
+    std::vector<Ref> v_refs(static_cast<size_t>(K));
+    for (size_t i = 0; i < static_cast<size_t>(K); i++) {
+        Ref addr;
+        if (i == 0) {
+            addr = pm_ref;
+        } else {
+            addr = newtmp(ctx, "rd.adr", Kl, fn);
+            Ins ai{};
+            ai.op = Oadd;
+            ai.cls = Kl;
+            ai.to = addr;
+            ai.arg[0] = pm_ref;
+            ai.arg[1] = getcon(ctx, static_cast<int64_t>(i) * S, fn);
+            addins(ctx, &mb->ins, &mb->nins, &ai);
+        }
+        v_refs[i] = newtmp(ctx, "rd.v", load_cls, fn);
+        Ins li{};
+        li.op = static_cast<uint>(load_op);
+        li.cls = static_cast<uint>(load_cls) & 3u;
+        li.to = v_refs[i];
+        li.arg[0] = addr;
+        li.arg[1] = Ref::none();
+        addins(ctx, &mb->ins, &mb->nins, &li);
+    }
+    for (size_t i = 0; i < static_cast<size_t>(K); i++) {
+        Ins oi{};
+        oi.op = static_cast<uint>(op);
+        oi.cls = static_cast<uint>(s_cls) & 3u;
+        oi.to = s_next_refs[i];
+        oi.arg[0] = s_refs[i];
+        oi.arg[1] = v_refs[i];
+        addins(ctx, &mb->ins, &mb->nins, &oi);
+    }
+    Ins pn_i{};
+    pn_i.op = Oadd;
+    pn_i.cls = Kl;
+    pn_i.to = pm_next_ref;
+    pn_i.arg[0] = pm_ref;
+    pn_i.arg[1] = getcon(ctx, static_cast<int64_t>(KS), fn);
+    addins(ctx, &mb->ins, &mb->nins, &pn_i);
+    mb->jmp.type = Jjmp;
+    mb->jmp.arg = Ref::none();
+    mb->jmp.arg2 = Ref::none();
+    mb->s1 = mh;
+    mb->s2 = nullptr;
+
+    // main_join: log2(K) tree reduction
+    Ref s01_ref = newtmp(ctx, "rd.s01", s_cls, fn);
+    Ref s23_ref = newtmp(ctx, "rd.s23", s_cls, fn);
+    Ref s_main_ref = newtmp(ctx, "rd.sm", s_cls, fn);
+
+    Ins j1{};
+    j1.op = static_cast<uint>(op);
+    j1.cls = static_cast<uint>(s_cls) & 3u;
+    j1.to = s01_ref;
+    j1.arg[0] = s_refs[0];
+    j1.arg[1] = s_refs[1];
+    addins(ctx, &mj->ins, &mj->nins, &j1);
+
+    Ins j2{};
+    j2.op = static_cast<uint>(op);
+    j2.cls = static_cast<uint>(s_cls) & 3u;
+    j2.to = s23_ref;
+    j2.arg[0] = s_refs[2];
+    j2.arg[1] = s_refs[3];
+    addins(ctx, &mj->ins, &mj->nins, &j2);
+
+    Ins j3{};
+    j3.op = static_cast<uint>(op);
+    j3.cls = static_cast<uint>(s_cls) & 3u;
+    j3.to = s_main_ref;
+    j3.arg[0] = s01_ref;
+    j3.arg[1] = s23_ref;
+    addins(ctx, &mj->ins, &mj->nins, &j3);
+
+    mj->jmp.type = Jjmp;
+    mj->jmp.arg = Ref::none();
+    mj->jmp.arg2 = Ref::none();
+    mj->s1 = tail_hdr;
+    mj->s2 = nullptr;
+
+    // Change preheader.s1 -> main_header
+    pre->s1 = mh;
+
+    // Link new blocks.
+    mj->link = pre->link;
+    mb->link = mj;
+    mh->link = mb;
+    pre->link = mh;
+
+    // Update tail_header phis.
+    for (Phi* ph = tail_hdr->phi; ph; ph = ph->link) {
+        for (uint k = 0; k < ph->narg; k++) {
+            if (ph->blk[k] != pre)
+                continue;
+            ph->blk[k] = mj;
+            if (req(ph->to, m.phi_p->to))
+                ph->arg[k] = pm_ref;
+            else if (req(ph->to, m.phi_s->to))
+                ph->arg[k] = s_main_ref;
+            break;
+        }
+    }
+}
+
+}  // namespace
+
+void reduction_unroll(Ctx* ctx, Fn* fn) {
+    std::vector<Loop> loops;
+    find_loops(fn, loops);
+    if (loops.empty())
+        return;
+
+    // Inner loops first (smaller body first)
+    std::sort(loops.begin(), loops.end(),
+              [](const Loop& a, const Loop& b) { return a.body.size() < b.body.size(); });
+
+    std::unordered_set<uint> consumed;
+    for (const Loop& L : loops) {
+        bool clash = false;
+        for (Blk* bb : L.body)
+            if (consumed.count(bb->id)) {
+                clash = true;
+                break;
+            }
+        if (clash)
+            continue;
+        Match m{};
+        if (!try_match_loop(fn, L, &m))
+            continue;
+        execute(ctx, fn, L, m);
+        for (Blk* bb : L.body)
+            consumed.insert(bb->id);
+    }
+}
+
+}  // namespace rcc