diff options
Diffstat (limited to 'rcc-legacy')
| -rw-r--r-- | rcc-legacy/src/mid/loop_idiom.cc | 401 | ||||
| -rw-r--r-- | rcc-legacy/src/mid/reduction_unroll.cc | 528 | ||||
| -rw-r--r-- | rcc-legacy/src/mid/scalar_repl.cc | 528 |
3 files changed, 1457 insertions, 0 deletions
diff --git a/rcc-legacy/src/mid/loop_idiom.cc b/rcc-legacy/src/mid/loop_idiom.cc new file mode 100644 index 0000000..8cbbf00 --- /dev/null +++ b/rcc-legacy/src/mid/loop_idiom.cc @@ -0,0 +1,401 @@ +/* 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 loop_idiom.cc +/// @brief Recognize zero-fill / array-copy inner loops -> rewrite to runtime Ocall. +/// +/// See docs/loop_idiom.md for architectural notes. + +#include "rcc/all.h" +#include "rcc/loopinfo.h" + +#include <algorithm> +#include <cstring> +#include <unordered_set> +#include <vector> + +namespace rcc { + +namespace { + +// store op -> byte width; non-store returns 0 +int store_bytes(int op) { + switch (op) { + case Ostoreb: + return 1; + case Ostoreh: + return 2; + case Ostorew: + case Ostores: + return 4; + case Ostorel: + case Ostored: + return 8; + default: + return 0; + } +} + +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; + } +} + +// Check byte splat. +bool is_byte_splat(Fn* fn, Ref v, uint8_t* byte_out) { + if (rtype(v) != RCon) + return false; + Con* c = &fn->con[v.val]; + if (c->type != Con::CBits || c->flt) + return false; + uint64_t bits = static_cast<uint64_t>(c->bits.i); + uint8_t b = bits & 0xff; + uint64_t splat = static_cast<uint64_t>(b); + splat |= splat << 8; + splat |= splat << 16; + splat |= splat << 32; + if (bits != splat) + return false; + *byte_out = b; + return true; +} + +// Trace Ocopy chain back to a non-Ocopy root Ref. +Ref base_root(Fn* fn, Ref r) { + for (int hop = 0; hop < 16; hop++) { + Ins* d = def_ins(fn, r); + if (!d || d->op != Ocopy) + break; + r = d->arg[0]; + } + return r; +} + +// Find IV increment index. +int find_iv_inc_idx(Blk* latch, Ref next) { + for (uint k = 0; k < latch->nins; k++) + if (req(latch->ins[k].to, next)) + return static_cast<int>(k); + return -1; +} + +enum class Idiom { None, Memset, Memcpy, Memmove }; + +struct Match { + Idiom kind; + Ref base_dst; + Ref base_src; // memcpy/memmove only + uint8_t value; // memset only + Ref end_dst; // for size = end - base + Blk* after; +}; + +bool try_match_loop(Fn* fn, const Loop& L, Match* out) { + // Validate loop structure. + if (L.body.size() > 2) + return false; + // Disallow nesting. + + // Primary pointer IV (dst pointer for memset/memcpy) + PointerIV iv_dst{}; + Phi* phi_dst = nullptr; + int found = 0; + for (Phi* ph = L.header->phi; ph; ph = ph->link) { + PointerIV cand{}; + if (pick_pointer_iv(fn, L, ph, &cand)) { + iv_dst = cand; + phi_dst = ph; + found++; + } + } + if (found == 0) + return false; + // 1 IV -> memset candidate; 2 -> memcpy candidate; >2 -> reject + PointerIV iv_src{}; + Phi* phi_src = nullptr; + if (found >= 2) { + if (found != 2) + return false; + // Rescan to get the two + std::vector<std::pair<PointerIV, Phi*>> ivs; + for (Phi* ph = L.header->phi; ph; ph = ph->link) { + PointerIV cand{}; + if (pick_pointer_iv(fn, L, ph, &cand)) + ivs.push_back({cand, ph}); + } + if (ivs.size() != 2) + return false; + // Will decide which is dst when scanning store in body + iv_dst = ivs[0].first; + phi_dst = ivs[0].second; + iv_src = ivs[1].first; + phi_src = ivs[1].second; + } + + // exit cmp must be based on iv_dst (memset) or either one (memcpy) + Ref end_dst; + Blk* after = nullptr; + if (!check_exit_cmp(fn, L, iv_dst.phi_to, &end_dst, &after)) { + if (phi_src && check_exit_cmp(fn, L, iv_src.phi_to, &end_dst, &after)) { + // Reversed: cmp based on src, swap dst/src naming + std::swap(iv_dst, iv_src); + std::swap(phi_dst, phi_src); + } else { + return false; + } + } + if (iv_dst.step != iv_src.step && phi_src) + return false; + + // Find IV self-update ins (add in latch) + int iv_dst_inc = find_iv_inc_idx(L.latch, iv_dst.next); + int iv_src_inc = phi_src ? find_iv_inc_idx(L.latch, iv_src.next) : -1; + if (iv_dst_inc < 0) + return false; + if (phi_src && iv_src_inc < 0) + return false; + + // Body scan. + Ins* load_ins = nullptr; + Ins* store_ins = nullptr; + for (Blk* bb : L.body) { + for (uint k = 0; k < bb->nins; k++) { + Ins* i = &bb->ins[k]; + int op = i->op; + // Allowed: exit cmp (in header), IV self-update (in latch) + if (bb == L.header && req(i->to, L.header->jmp.arg)) + continue; // exit cmp + if (bb == L.latch && + (static_cast<int>(k) == iv_dst_inc || static_cast<int>(k) == iv_src_inc)) + continue; + // Disallowed: call / alloc / FP / div / vastart / vaarg / dbgloc / sel / blit + 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) + return false; + if (op == Oudiv || op == Ourem || op == Odiv || op == Orem) + return false; + if (op == Ocopy && (i->cls == Ks || i->cls == Kd)) + return false; + // load / store + int lb = load_bytes(op, static_cast<int>(i->cls)); + int sb = store_bytes(op); + if (lb > 0) { + if (load_ins) + return false; // Reject multiple loads + load_ins = i; + continue; + } + if (sb > 0) { + if (store_ins) + return false; + store_ins = i; + continue; + } + // Other allowed. + if (op == Oadd || op == Osub || op == Omul || op == Oand || op == Oor || op == Oxor || + op == Oshl || op == Oshr || op == Osar || op == Oextsw || op == Oextuw || + op == Oextsh || op == Oextuh || op == Oextsb || op == Oextub || op == Ocopy || + op == Onop) + continue; + // Other cmp (besides LFTR cmp): conservatively reject + return false; + } + } + + if (!store_ins) + return false; + int sw = store_bytes(store_ins->op); + if (sw != iv_dst.step) + return false; + if (!req(store_ins->arg[1], iv_dst.phi_to)) + return false; + + if (has_outside_use(fn, L)) + return false; + + if (load_ins) { + // memcpy path + if (!phi_src) + return false; + int lw = load_bytes(load_ins->op, static_cast<int>(load_ins->cls)); + if (lw != sw) + return false; + if (!req(load_ins->arg[0], iv_src.phi_to)) + return false; + if (!req(store_ins->arg[0], load_ins->to)) + return false; + // Noalias check. + Ref root_dst = base_root(fn, iv_dst.base); + Ref root_src = base_root(fn, iv_src.base); + out->kind = req(root_dst, root_src) ? Idiom::Memmove : Idiom::Memcpy; + out->base_dst = iv_dst.base; + out->base_src = iv_src.base; + out->value = 0; + out->end_dst = end_dst; + out->after = after; + return true; + } + + // memset path + if (phi_src) + return false; // Second IV present but no load, abnormal shape + uint8_t bv = 0; + if (!is_byte_splat(fn, store_ins->arg[0], &bv)) + return false; + out->kind = Idiom::Memset; + out->base_dst = iv_dst.base; + out->base_src = Ref::none(); + out->value = bv; + out->end_dst = end_dst; + out->after = after; + return true; +} + +const char* runtime_name(Idiom k) { + switch (k) { + case Idiom::Memset: + return "__rcc_memset"; + case Idiom::Memcpy: + return "__rcc_memcpy"; + case Idiom::Memmove: + return "__rcc_memmove"; + default: + return ""; + } +} + +Ref make_runtime_callee(Ctx* ctx, Fn* fn, const char* name) { + Con c; + std::memset(&c, 0, sizeof(c)); + c.type = Con::CAddr; + c.sym.type = Sym::SGlo; + c.sym.id = intern(const_cast<char*>(name)); + return newcon(ctx, &c, fn); +} + +void execute_rewrite(Ctx* ctx, Fn* fn, const Loop& L, const Match& m) { + Blk* pre = L.preheader; + + // size = end - base (Osub Kl) + Ref size_ref = newtmp(ctx, "midiom", Kl, fn); + Ins sub_ins{}; + sub_ins.op = Osub; + sub_ins.cls = Kl; + sub_ins.to = size_ref; + sub_ins.arg[0] = m.end_dst; + sub_ins.arg[1] = m.base_dst; + addins(ctx, &pre->ins, &pre->nins, &sub_ins); + + // Oarg dst (Kl) + Ins arg0{}; + arg0.op = Oarg; + arg0.cls = Kl; + arg0.to = Ref::none(); + arg0.arg[0] = m.base_dst; + arg0.arg[1] = Ref::none(); + addins(ctx, &pre->ins, &pre->nins, &arg0); + + // Oarg val/src + Ins arg1{}; + arg1.op = Oarg; + arg1.to = Ref::none(); + arg1.arg[1] = Ref::none(); + if (m.kind == Idiom::Memset) { + arg1.cls = Kw; + arg1.arg[0] = getcon(ctx, static_cast<int64_t>(m.value), fn); + } else { + arg1.cls = Kl; + arg1.arg[0] = m.base_src; + } + addins(ctx, &pre->ins, &pre->nins, &arg1); + + // Oarg size (Kl) + Ins arg2{}; + arg2.op = Oarg; + arg2.cls = Kl; + arg2.to = Ref::none(); + arg2.arg[0] = size_ref; + arg2.arg[1] = Ref::none(); + addins(ctx, &pre->ins, &pre->nins, &arg2); + + // Ocall (returns void -> cls=Kw, to=none) + Ins call_ins{}; + call_ins.op = Ocall; + call_ins.cls = Kw; + call_ins.to = Ref::none(); + call_ins.arg[0] = make_runtime_callee(ctx, fn, runtime_name(m.kind)); + call_ins.arg[1] = Ref::none(); + addins(ctx, &pre->ins, &pre->nins, &call_ins); + + fn->leaf = 0; + + // change preheader to jump directly to after + pre->jmp.type = Jjmp; + pre->jmp.arg = Ref::none(); + pre->jmp.arg2 = Ref::none(); + pre->s1 = m.after; + pre->s2 = nullptr; +} + +} // namespace + +void loop_idiom(Ctx* ctx, Fn* fn) { + std::vector<Loop> loops; + find_loops(fn, loops); + if (loops.empty()) + return; + + // Sort innermost 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_blk; + for (const Loop& L : loops) { + bool clash = false; + for (Blk* bb : L.body) + if (consumed_blk.count(bb->id)) { + clash = true; + break; + } + if (clash) + continue; + Match m{}; + if (!try_match_loop(fn, L, &m)) + continue; + execute_rewrite(ctx, fn, L, m); + for (Blk* bb : L.body) + consumed_blk.insert(bb->id); + } +} + +} // namespace rcc 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 diff --git a/rcc-legacy/src/mid/scalar_repl.cc b/rcc-legacy/src/mid/scalar_repl.cc new file mode 100644 index 0000000..04c0a82 --- /dev/null +++ b/rcc-legacy/src/mid/scalar_repl.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 scalar_repl.cc +/// @brief Converts in-loop memory accumulators into a register + phi node. +/// +/// See docs/scalar_repl.md for architectural notes. + +#include "rcc/all.h" + +#include <cstring> +#include <vector> + +namespace rcc { + +namespace { + +Ins make_nop_ins() { + Ins i = {}; + i.op = Onop; + return i; +} + +struct LoopInfo { + Blk* header; + std::vector<Blk*> body; + Blk* preheader; + Blk* latch; + Blk* exit_blk; + Blk* exit_pred; // exit_blk's only pred inside the body +}; + +bool blk_in(Blk* x, const std::vector<Blk*>& body) { + for (Blk* b : body) + if (b == x) + return true; + return false; +} + +bool find_loops(Fn* fn, std::vector<LoopInfo>& out) { + out.clear(); + for (Blk* b = fn->start; b; b = b->link) + b->visit = ~0u; + + for (uint i = 0; i < fn->nblk; i++) { + Blk* hd = fn->rpo[i]; + bool has_back = false; + for (uint k = 0; k < hd->npred; k++) + if (hd->pred[k]->id >= i) { + has_back = true; + break; + } + if (!has_back) + continue; + + LoopInfo L{hd, {hd}, nullptr, nullptr, nullptr, nullptr}; + std::vector<Blk*> stack; + for (uint k = 0; k < hd->npred; k++) + if (hd->pred[k]->id >= i) + stack.push_back(hd->pred[k]); + while (!stack.empty()) { + Blk* n = stack.back(); + stack.pop_back(); + if (n->id < hd->id || n->visit == hd->id) + continue; + n->visit = hd->id; + L.body.push_back(n); + for (uint k = 0; k < n->npred; k++) + stack.push_back(n->pred[k]); + } + + Blk* phdr = nullptr; + Blk* latch = nullptr; + bool unique = true; + for (uint k = 0; k < hd->npred; k++) { + Blk* p = hd->pred[k]; + if (blk_in(p, L.body)) { + if (latch) { + unique = false; + break; + } + latch = p; + } else { + if (phdr) { + unique = false; + break; + } + phdr = p; + } + } + if (!unique || !phdr || !latch) + continue; + L.preheader = phdr; + L.latch = latch; + + Blk* exit_blk = nullptr; + bool exit_unique = true; + for (Blk* b : L.body) { + Blk* succs[2] = {b->s1, b->s2}; + for (Blk* s : succs) { + if (!s || blk_in(s, L.body)) + continue; + if (exit_blk && exit_blk != s) { + exit_unique = false; + break; + } + exit_blk = s; + } + if (!exit_unique) + break; + } + if (!exit_unique || !exit_blk) + continue; + int from_loop = 0; + Blk* exit_pred = nullptr; + for (uint k = 0; k < exit_blk->npred; k++) + if (blk_in(exit_blk->pred[k], L.body)) { + from_loop++; + exit_pred = exit_blk->pred[k]; + } + if (from_loop != 1) + continue; + L.exit_blk = exit_blk; + L.exit_pred = exit_pred; + + out.push_back(std::move(L)); + } + return !out.empty(); +} + +// Recursively check address invariance. +bool is_pure_arith(int op) { + switch (op) { + case Oadd: + case Osub: + case Omul: + case Oand: + case Oor: + case Oxor: + case Oshl: + case Oshr: + case Osar: + case Oextsw: + case Oextuw: + case Oextsh: + case Oextuh: + case Oextsb: + case Oextub: + case Ocopy: + return true; + default: + return false; + } +} + +// Find phi node for t in a blk (t->def doesn't point to phi, must scan). +Phi* find_phi(Fn* fn, Ref r) { + if (rtype(r) != RTmp) + return nullptr; + Tmp* t = &fn->tmp[r.val]; + if (t->bid == ~0u) + return nullptr; + Blk* b = fn->rpo[t->bid]; + for (Phi* p = b->phi; p; p = p->link) + if (req(p->to, r)) + return p; + return nullptr; +} + +// Each incoming phi arg must be invariant. Cannot do optimistic cycle back-edge. +bool phi_invariant(Fn* fn, Phi* p, const LoopInfo& L) { + for (uint k = 0; k < p->narg; k++) { + Ref a = p->arg[k]; + if (req(a, p->to)) + continue; + if (rtype(a) == RCon) + continue; + if (rtype(a) != RTmp) + return false; + Tmp* t = &fn->tmp[a.val]; + if (t->bid == ~0u) + continue; + if (blk_in(fn->rpo[t->bid], L.body)) + return false; + } + return true; +} + +bool addr_invariant_rec(Fn* fn, Ref addr, const LoopInfo& L, int depth) { + if (rtype(addr) == RCon) + return true; + if (rtype(addr) != RTmp) + return false; + Tmp* t = &fn->tmp[addr.val]; + if (t->bid == ~0u) + return true; + if (!blk_in(fn->rpo[t->bid], L.body)) + return true; + if (depth <= 0) + return false; + if (Phi* p = find_phi(fn, addr)) + return phi_invariant(fn, p, L); + Ins* d = t->def; + if (!d || !is_pure_arith(static_cast<int>(d->op))) + return false; + if (!addr_invariant_rec(fn, d->arg[0], L, depth - 1)) + return false; + if (!req(d->arg[1], Ref::none()) && !addr_invariant_rec(fn, d->arg[1], L, depth - 1)) + return false; + return true; +} + +bool addr_invariant(Fn* fn, Ref addr, const LoopInfo& L) { + return addr_invariant_rec(fn, addr, L, 8); +} + +// Structural equivalence: two Ref chains compute the same value. +bool addr_same_value(Fn* fn, Ref a, Ref b, int depth = 8) { + if (req(a, b)) + return true; + if (rtype(a) == RCon && rtype(b) == RCon) { + Con* ca = &fn->con[a.val]; + Con* cb = &fn->con[b.val]; + if (ca->type != cb->type) + return false; + if (ca->type == Con::CAddr && !symeq(ca->sym, cb->sym)) + return false; + return ca->bits.i == cb->bits.i; + } + if (rtype(a) != RTmp || rtype(b) != RTmp) + return false; + if (depth <= 0) + return false; + Tmp* ta = &fn->tmp[a.val]; + Tmp* tb = &fn->tmp[b.val]; + Ins* da = ta->def; + Ins* db = tb->def; + if (!da || !db) + return false; + if (da->op != db->op) + return false; + if (!is_pure_arith(static_cast<int>(da->op))) + return false; + if (!addr_same_value(fn, da->arg[0], db->arg[0], depth - 1)) + return false; + if (req(da->arg[1], Ref::none()) && req(db->arg[1], Ref::none())) + return true; + return addr_same_value(fn, da->arg[1], db->arg[1], depth - 1); +} + +// Clone invariant address chain to preheader. +Ref clone_invariant_to_preheader(Ctx* ctx, Fn* fn, Ref r, const LoopInfo& L, + std::vector<std::pair<uint, Ref>>& cache, int depth = 8) { + if (rtype(r) == RCon) + return r; + if (rtype(r) != RTmp) + return Ref::none(); + Tmp* t = &fn->tmp[r.val]; + if (t->bid == ~0u || !blk_in(fn->rpo[t->bid], L.body)) + return r; // Already defined outside loop, reuse directly + if (depth <= 0) + return Ref::none(); + for (auto& kv : cache) + if (kv.first == r.val) + return kv.second; + + Phi* p = find_phi(fn, r); + if (p) { + // Look for preheader-side arg in phi.blk[] + for (uint k = 0; k < p->narg; k++) + if (p->blk[k] == L.preheader) { + Ref v = clone_invariant_to_preheader(ctx, fn, p->arg[k], L, cache, depth - 1); + if (rtype(v) == -1) + return Ref::none(); + cache.push_back(std::make_pair(static_cast<uint>(r.val), v)); + return v; + } + return Ref::none(); + } + Ins* d = t->def; + if (!d || !is_pure_arith(static_cast<int>(d->op))) + return Ref::none(); + Ref a0 = clone_invariant_to_preheader(ctx, fn, d->arg[0], L, cache, depth - 1); + if (rtype(a0) == -1) + return Ref::none(); + Ref a1 = Ref::none(); + if (!req(d->arg[1], Ref::none())) { + a1 = clone_invariant_to_preheader(ctx, fn, d->arg[1], L, cache, depth - 1); + if (rtype(a1) == -1) + return Ref::none(); + } + Ref nt = newtmp(ctx, "sr.addr", static_cast<int>(d->cls), fn); + Ins ni{}; + ni.op = d->op; + ni.cls = d->cls; + ni.to = nt; + ni.arg[0] = a0; + ni.arg[1] = a1; + addins(ctx, &L.preheader->ins, &L.preheader->nins, &ni); + cache.push_back(std::make_pair(static_cast<uint>(r.val), nt)); + return nt; +} + +// Globally replace all ref==from with to (in phi.arg / ins.arg / jmp.arg / jmp.arg2). +void rewrite_ref(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 (Ins* i = b->ins; i < &b->ins[b->nins]; i++) { + 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; + } +} + +void prepend_ins(Ctx* ctx, Blk* b, const Ins& ins) { + vgrow(ctx, &b->ins, b->nins + 1); + std::memmove(b->ins + 1, b->ins, b->nins * sizeof(Ins)); + b->ins[0] = ins; + b->nins += 1; +} + +// Try one promotion on L. Returns true on hit; outer loop recomputes use/dom/alias. +bool try_promote(Ctx* ctx, Fn* fn, const LoopInfo& L) { + for (Blk* b : L.body) { + for (Ins* iload = b->ins; iload < &b->ins[b->nins]; iload++) { + if (!isload(iload->op)) + continue; + Ref addr = iload->arg[0]; + if (!addr_invariant(fn, addr, L)) + continue; + int sz = loadsz(iload); + + std::vector<Ins*> matched_loads; + Blk* store_blk = nullptr; + Ins* matched_store = nullptr; + int store_count = 0; + bool ok = true; + + // Three-tier classification: structurally identical -> matched, NoAlias -> skip, + // MayAlias -> bail. + auto classify = [&](Ref jaddr, int jsz) -> int { + // ret: 0=matched, 1=skip(NoAlias), 2=bail + if (jsz != sz) + return 2; // Different size cannot be promoted (conservative) + if (addr_same_value(fn, addr, jaddr)) + return 0; + int delta; + int r = alias(addr, 0, sz, jaddr, jsz, &delta, fn); + if (r == NoAlias) + return 1; + if (r == MustAlias && delta == 0) + return 0; + return 2; + }; + + for (Blk* bb : L.body) { + for (Ins* j = bb->ins; j < &bb->ins[bb->nins]; j++) { + if (j->op == Ocall || j->op == Oblit0 || j->op == Oblit1) { + ok = false; + break; + } + if (isload(j->op)) { + int jsz = loadsz(j); + // Different size but NoAlias can still be skipped + if (jsz != sz) { + int delta; + int r = alias(addr, 0, sz, j->arg[0], jsz, &delta, fn); + if (r != NoAlias) { + ok = false; + break; + } + continue; + } + int c = classify(j->arg[0], jsz); + if (c == 0) + matched_loads.push_back(j); + else if (c == 2) { + ok = false; + break; + } + } else if (isstore(j->op)) { + int jsz = storesz(j); + if (jsz != sz) { + int delta; + int r = alias(addr, 0, sz, j->arg[1], jsz, &delta, fn); + if (r != NoAlias) { + ok = false; + break; + } + continue; + } + int c = classify(j->arg[1], jsz); + if (c == 0) { + store_count++; + if (store_count > 1) { + ok = false; + break; + } + matched_store = j; + store_blk = bb; + } else if (c == 2) { + ok = false; + break; + } + } + } + if (!ok) + break; + } + if (!ok || store_count != 1) + continue; + // Store must be must-execute. + if (!dom(store_blk, L.latch)) + continue; + if (!dom(store_blk, L.exit_pred)) + continue; + + int cls = static_cast<int>(iload->cls); + + // Clone address chain to preheader, then issue load. + std::vector<std::pair<uint, Ref>> addr_cache; + Ref pre_addr = clone_invariant_to_preheader(ctx, fn, addr, L, addr_cache); + if (rtype(pre_addr) == -1) + continue; // Clone failed (rare corner case) + Ref init_ref = newtmp(ctx, "sr.init", cls, fn); + Ins pre_ld{}; + pre_ld.op = iload->op; + pre_ld.cls = static_cast<uint>(cls); + pre_ld.to = init_ref; + pre_ld.arg[0] = pre_addr; + pre_ld.arg[1] = Ref::none(); + addins(ctx, &L.preheader->ins, &L.preheader->nins, &pre_ld); + + // Insert phi at header top. + Ref back_val = matched_store->arg[0]; + Ref phi_ref = newtmp(ctx, "sr.phi", cls, fn); + Phi* p = static_cast<Phi*>(alloc(ctx, sizeof(Phi))); + std::memset(p, 0, sizeof *p); + p->to = phi_ref; + p->cls = static_cast<short>(cls); + 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] = init_ref; + p->blk[0] = L.preheader; + p->arg[1] = back_val; + p->blk[1] = L.latch; + p->link = L.header->phi; + L.header->phi = p; + + // Change all matched_loads def tmps to phi_ref; original loads become Onop. + for (Ins* ml : matched_loads) { + rewrite_ref(fn, ml->to, phi_ref); + *ml = make_nop_ins(); + } + + // Sink store at top of exit_blk. + Ins sink{}; + sink.op = matched_store->op; + sink.cls = matched_store->cls; + sink.to = Ref::none(); + sink.arg[0] = phi_ref; + sink.arg[1] = pre_addr; + prepend_ins(ctx, L.exit_blk, sink); + + // Original store becomes Onop. + *matched_store = make_nop_ins(); + + return true; + } + } + return false; +} + +} // namespace + +void scalar_repl(Ctx* ctx, Fn* fn) { + int total = 0; + for (int iter = 0; iter < 16; iter++) { + std::vector<LoopInfo> loops; + if (!find_loops(fn, loops)) + break; + bool changed = false; + for (const LoopInfo& L : loops) { + if (try_promote(ctx, fn, L)) { + changed = true; + total++; + break; + } + } + if (!changed) + break; + filluse(ctx, fn); + filldom(fn); + fillalias(fn); + } + if (debug['L']) { + FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr; + fprintf(out, "\n> scalar-repl promoted %d location(s) in %s\n", total, fn->name); + } +} + +} // namespace rcc |