diff options
Diffstat (limited to 'rcc-legacy/src/mid/unswitch.cc')
| -rw-r--r-- | rcc-legacy/src/mid/unswitch.cc | 447 |
1 files changed, 447 insertions, 0 deletions
diff --git a/rcc-legacy/src/mid/unswitch.cc b/rcc-legacy/src/mid/unswitch.cc new file mode 100644 index 0000000..fa8bf73 --- /dev/null +++ b/rcc-legacy/src/mid/unswitch.cc @@ -0,0 +1,447 @@ +/* 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 unswitch.cc +/// @brief Loop Unswitching. +/// +/// See docs/unswitch.md for architectural notes. + +#include "rcc/all.h" + +#include <cassert> +#include <cstdio> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +namespace rcc { + +namespace { + +constexpr int kUnswitchMaxBodyIns = 64; +constexpr int kUnswitchFixpointIters = 3; + +// Loop Identification +struct LoopShape { + Blk* header; + Blk* preheader; + Blk* latch; + Blk* exit_bb; + std::vector<Blk*> body; // includes header / latch +}; + +// Find simple loops (derived from unroll.cc). +std::vector<LoopShape> find_simple_loops(Fn* fn) { + std::vector<LoopShape> out; + 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]; + if (hd->id == ~0u) + continue; + + int back_cnt = 0, pre_cnt = 0; + uint latch_idx = 0, pre_idx = 0; + for (uint k = 0; k < hd->npred; k++) { + Blk* p = hd->pred[k]; + if (p->id == ~0u) + continue; + if (p->id >= i) { + back_cnt++; + latch_idx = k; + } else { + pre_cnt++; + pre_idx = k; + } + } + if (back_cnt != 1 || pre_cnt != 1) + continue; + + Blk* latch = hd->pred[latch_idx]; + Blk* preheader = hd->pred[pre_idx]; + + // Reverse DFS to collect body + std::vector<Blk*> body = {hd}; + std::vector<Blk*> stack = {latch}; + hd->visit = hd->id; + while (!stack.empty()) { + Blk* n = stack.back(); + stack.pop_back(); + if (n->visit == hd->id) + continue; + n->visit = hd->id; + body.push_back(n); + for (uint k = 0; k < n->npred; k++) + stack.push_back(n->pred[k]); + } + + // single-exit gate + if (hd->jmp.type != Jjnz) + continue; + Blk* exit_bb = hd->s2; + if (!exit_bb || !hd->s1) + continue; + + auto in_body = [&](Blk* x) -> bool { + for (Blk* bb : body) + if (bb == x) + return true; + return false; + }; + if (in_body(exit_bb)) + continue; + if (!in_body(hd->s1)) + continue; + + bool ok = true; + for (Blk* bb : body) { + if (bb == hd) + continue; + if (isret(bb->jmp.type)) { + ok = false; + break; + } + auto check = [&](Blk* s) -> bool { return !s || in_body(s); }; + if (!check(bb->s1) || !check(bb->s2)) { + ok = false; + break; + } + } + if (!ok) + continue; + + LoopShape L; + L.header = hd; + L.preheader = preheader; + L.latch = latch; + L.exit_bb = exit_bb; + L.body = std::move(body); + out.push_back(std::move(L)); + } + return out; +} + +// Loop Invariance +bool ref_is_invariant(Fn* fn, const LoopShape& 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; + if (bid == ~0u) + return true; + for (Blk* b : L.body) + if (b->id == bid) + return false; + return true; +} + +// Find a hoistable Jjnz branch. Returns nullptr if no candidate. +Blk* find_unswitch_blk(Fn* fn, const LoopShape& L) { + for (Blk* b : L.body) { + if (b == L.header) + continue; // header.Jjnz is loop exit, cannot hoist + if (b == L.latch) + continue; // Jjnz on latch is usually back-edge directed, skip to simplify analysis + if (b->jmp.type != Jjnz) + continue; + if (rtype(b->jmp.arg) != RTmp) + continue; // RCon left to simplcfg + if (!ref_is_invariant(fn, L, b->jmp.arg)) + continue; + if (!b->s1 || !b->s2 || b->s1 == b->s2) + continue; + bool s1_in = false, s2_in = false; + for (Blk* bb : L.body) { + if (bb == b->s1) + s1_in = true; + if (bb == b->s2) + s2_in = true; + } + if (!s1_in || !s2_in) + continue; + return b; + } + return nullptr; +} + +int count_body_ins(const LoopShape& L) { + int n = 0; + for (Blk* b : L.body) { + for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) + if (i->op != Onop) + n++; + for (Phi* p = b->phi; p; p = p->link) + (void)p, n++; + } + return n; +} + +// Clone Infrastructure (derived from unroll.cc with minor adaptations) +struct CopyState { + std::unordered_map<uint, Blk*> blk_map; // body blk.id -> clone + std::unordered_map<uint, Ref> tmp_map; // body-defined tmp.val -> clone Ref +}; + +Ref remap_tmp(Ref r, const std::unordered_map<uint, Ref>& m) { + if (rtype(r) != RTmp) + return r; + auto it = m.find(r.val); + return (it != m.end()) ? it->second : r; +} + +// Generic block clone. +void clone_blk(Ctx* ctx, const CopyState& st, Blk* src, Blk* dst) { + dst->phi = nullptr; + Phi** tail = &dst->phi; + for (Phi* sp = src->phi; sp; sp = sp->link) { + Phi* np = static_cast<Phi*>(alloc(ctx, sizeof(Phi))); + np->to = remap_tmp(sp->to, st.tmp_map); + np->cls = sp->cls; + np->visit = 0; + np->narg = sp->narg; + np->arg = static_cast<Ref*>(vnew(ctx, sp->narg, sizeof(Ref), PFn)); + np->blk = static_cast<Blk**>(vnew(ctx, sp->narg, sizeof(Blk*), PFn)); + for (uint k = 0; k < sp->narg; k++) { + np->arg[k] = remap_tmp(sp->arg[k], st.tmp_map); + auto it = st.blk_map.find(sp->blk[k]->id); + np->blk[k] = (it != st.blk_map.end()) ? it->second : sp->blk[k]; + } + np->link = nullptr; + *tail = np; + tail = &np->link; + } + + dst->ins = static_cast<Ins*>(vnew(ctx, 0, sizeof(Ins), PFn)); + dst->nins = 0; + for (Ins* si = src->ins; si < &src->ins[src->nins]; si++) { + Ins ni; + ni.op = si->op; + ni.cls = si->cls; + ni.to = remap_tmp(si->to, st.tmp_map); + ni.arg[0] = remap_tmp(si->arg[0], st.tmp_map); + ni.arg[1] = remap_tmp(si->arg[1], st.tmp_map); + addins(ctx, &dst->ins, &dst->nins, &ni); + } + + auto map_succ = [&](Blk* s) -> Blk* { + if (!s) + return nullptr; + auto it = st.blk_map.find(s->id); + return (it != st.blk_map.end()) ? it->second : s; + }; + dst->jmp.type = src->jmp.type; + dst->jmp.arg = remap_tmp(src->jmp.arg, st.tmp_map); + dst->s1 = map_succ(src->s1); + dst->s2 = map_succ(src->s2); +} + +CopyState clone_loop(Ctx* ctx, Fn* fn, const LoopShape& L, const char* tag) { + CopyState st; + + std::unordered_set<uint> body_defined; + for (Blk* b : L.body) { + for (Phi* p = b->phi; p; p = p->link) + if (rtype(p->to) == RTmp) + body_defined.insert(p->to.val); + for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) + if (rtype(i->to) == RTmp && i->to.val != 0) + body_defined.insert(i->to.val); + } + + for (Blk* b : L.body) { + Blk* nb = newblk(ctx); + nb->name = strf(ctx, PFn, "%s.%s", tag, b->name ? b->name : "blk"); + nb->id = fn->nblk++; + st.blk_map[b->id] = nb; + } + + for (uint tv : body_defined) { + const char* prfx = fn->tmp[tv].name ? fn->tmp[tv].name : "u"; + st.tmp_map[tv] = newtmp(ctx, prfx, fn->tmp[tv].cls, fn); + } + + for (Blk* b : L.body) + clone_blk(ctx, st, b, st.blk_map[b->id]); + + return st; +} + +// Remove dangling phi incoming edges from deactivated successors. +void remove_phi_entry(Blk* succ, Blk* old_pred) { + for (Phi* p = succ->phi; p; p = p->link) { + uint w = 0; + for (uint k = 0; k < p->narg; k++) { + if (p->blk[k] == old_pred) + continue; + if (w != k) { + p->arg[w] = p->arg[k]; + p->blk[w] = p->blk[k]; + } + w++; + } + p->narg = w; + } +} + +void do_unswitch(Ctx* ctx, Fn* fn, const LoopShape& L, Blk* unsw_blk) { + Ref cond = unsw_blk->jmp.arg; + Blk* orig_s1 = unsw_blk->s1; + Blk* orig_s2 = unsw_blk->s2; + + CopyState A = clone_loop(ctx, fn, L, "uA"); + CopyState B = clone_loop(ctx, fn, L, "uB"); + + Blk* header_A = A.blk_map.at(L.header->id); + Blk* header_B = B.blk_map.at(L.header->id); + Blk* unsw_A = A.blk_map.at(unsw_blk->id); + Blk* unsw_B = B.blk_map.at(unsw_blk->id); + + // In A, collapse to true branch (orig.s1) + unsw_A->jmp.type = Jjmp; + unsw_A->jmp.arg = Ref::none(); + unsw_A->s1 = A.blk_map.at(orig_s1->id); + unsw_A->s2 = nullptr; + // orig.s2 clone in A is no longer reached by unsw_A; must remove phi edges from unsw_A + remove_phi_entry(A.blk_map.at(orig_s2->id), unsw_A); + + // In B, collapse to false branch (orig.s2) + unsw_B->jmp.type = Jjmp; + unsw_B->jmp.arg = Ref::none(); + unsw_B->s1 = B.blk_map.at(orig_s2->id); + unsw_B->s2 = nullptr; + remove_phi_entry(B.blk_map.at(orig_s1->id), unsw_B); + + // guard block: Jjnz cond, header_A, header_B + Blk* guard = newblk(ctx); + guard->name = strf(ctx, PFn, "uG.%s", L.header->name ? L.header->name : ""); + guard->id = fn->nblk++; + guard->phi = nullptr; + guard->ins = static_cast<Ins*>(vnew(ctx, 0, sizeof(Ins), PFn)); + guard->nins = 0; + guard->jmp.type = Jjnz; + guard->jmp.arg = cond; + guard->s1 = header_A; + guard->s2 = header_B; + + // preheader -> guard (replaces original preheader -> header) + if (L.preheader->s1 == L.header) + L.preheader->s1 = guard; + if (L.preheader->s2 == L.header) + L.preheader->s2 = guard; + + // Update header_A / header_B phi.blk[k]==preheader to guard + auto fix_hdr_pred = [&](Blk* hdr_clone) { + for (Phi* p = hdr_clone->phi; p; p = p->link) + for (uint k = 0; k < p->narg; k++) + if (p->blk[k] == L.preheader) + p->blk[k] = guard; + }; + fix_hdr_pred(header_A); + fix_hdr_pred(header_B); + + // exit_bb phi: split blk==L.header incoming edges into two + Blk* exit = L.exit_bb; + for (Phi* p = exit->phi; p; p = p->link) { + uint header_entries = 0; + for (uint k = 0; k < p->narg; k++) + if (p->blk[k] == L.header) + header_entries++; + if (header_entries == 0) + continue; + + uint new_narg = p->narg + header_entries; // Expand each into 2 = +1 + Ref* new_arg = static_cast<Ref*>(vnew(ctx, new_narg, sizeof(Ref), PFn)); + Blk** new_blk = static_cast<Blk**>(vnew(ctx, new_narg, sizeof(Blk*), PFn)); + uint w = 0; + for (uint k = 0; k < p->narg; k++) { + if (p->blk[k] == L.header) { + new_arg[w] = remap_tmp(p->arg[k], A.tmp_map); + new_blk[w] = header_A; + w++; + new_arg[w] = remap_tmp(p->arg[k], B.tmp_map); + new_blk[w] = header_B; + w++; + } else { + new_arg[w] = p->arg[k]; + new_blk[w] = p->blk[k]; + w++; + } + } + p->narg = new_narg; + p->arg = new_arg; + p->blk = new_blk; + } + + // link chain: preheader -> guard -> A.body -> B.body -> original preheader.link + Blk* saved = L.preheader->link; + L.preheader->link = guard; + Blk** plink = &guard->link; + for (Blk* b : L.body) { + *plink = A.blk_map.at(b->id); + plink = &(*plink)->link; + } + for (Blk* b : L.body) { + *plink = B.blk_map.at(b->id); + plink = &(*plink)->link; + } + *plink = saved; + + if (debug['W']) { + FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr; + fprintf(out, "> unswitch %s: hdr b%u, unsw b%u, body=%zu\n", fn->name, L.header->id, + unsw_blk->id, L.body.size()); + } +} + +bool unswitch_pass(Ctx* ctx, Fn* fn) { + auto loops = find_simple_loops(fn); + for (auto& L : loops) { + Blk* u = find_unswitch_blk(fn, L); + if (!u) + continue; + if (count_body_ins(L) > kUnswitchMaxBodyIns) + continue; + do_unswitch(ctx, fn, L, u); + return true; // Process one per pass to avoid scanning mutated CFG + } + return false; +} + +} // namespace + +void unswitch(Ctx* ctx, Fn* fn) { + // Caller should have done fillcfg + filluse; filldom not needed (only Tmp.bid is used). + int iter = 0; + for (; iter < kUnswitchFixpointIters; iter++) { + if (!unswitch_pass(ctx, fn)) + break; + fillcfg(ctx, fn); + filluse(ctx, fn); + } + if (debug['W'] && iter > 0) { + FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr; + fprintf(out, "> unswitch %s: %d round%s\n", fn->name, iter, iter == 1 ? "" : "s"); + } +} + +} // namespace rcc |