diff options
Diffstat (limited to 'src/mid/licm.cc')
| -rw-r--r-- | src/mid/licm.cc | 213 |
1 files changed, 213 insertions, 0 deletions
diff --git a/src/mid/licm.cc b/src/mid/licm.cc new file mode 100644 index 0000000..87d61a3 --- /dev/null +++ b/src/mid/licm.cc @@ -0,0 +1,213 @@ +/* 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 licm.cc +/// @brief Phase A Loop Invariant Code Motion (LICM). +/// +/// See docs/licm.md for architectural notes. + +#include "rcc/all.h" + +#include <vector> + +namespace rcc { + +namespace { + +struct LoopInfo { + Blk* header; + std::vector<Blk*> body; // includes header + Blk* preheader; // nullptr if no unique non-back-edge predecessor +}; + +Ins make_nop() { + Ins i = {}; + i.op = Onop; + return i; +} + +// Loop Identification. +void build_loops(Fn* fn, std::vector<LoopInfo>& loops, std::vector<int>& blk_loop) { + loops.clear(); + blk_loop.assign(static_cast<size_t>(fn->nblk), -1); + + for (Blk* b = fn->start; b; b = b->link) + b->visit = ~0u; + + auto refine_inner = [&](uint bid, int lidx) { + int cur = blk_loop[bid]; + if (cur < 0 || loops[static_cast<size_t>(cur)].header->id < + loops[static_cast<size_t>(lidx)].header->id) + blk_loop[bid] = lidx; + }; + + 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; + + int lidx = static_cast<int>(loops.size()); + loops.push_back({hd, {hd}, nullptr}); + refine_inner(hd->id, lidx); + + // DFS body collect. + 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; + loops[static_cast<size_t>(lidx)].body.push_back(n); + refine_inner(n->id, lidx); + for (uint k = 0; k < n->npred; k++) + stack.push_back(n->pred[k]); + } + } + + // Find preheader. + for (auto& L : loops) { + Blk* phdr = nullptr; + bool unique = true; + for (uint k = 0; k < L.header->npred; k++) { + Blk* p = L.header->pred[k]; + bool in_body = false; + for (Blk* b : L.body) + if (b == p) { + in_body = true; + break; + } + if (in_body) + continue; // back-edge + if (phdr) { + unique = false; + break; + } + phdr = p; + } + L.preheader = unique ? phdr : nullptr; + } +} + +// Invariance +bool blk_in(Blk* x, const std::vector<Blk*>& body) { + for (Blk* b : body) + if (b == x) + return true; + return false; +} + +bool is_invariant(Fn* fn, Ref r, const LoopInfo& L) { + if (rtype(r) == RCon) + return true; + if (rtype(r) != RTmp) + return false; + Tmp* t = &fn->tmp[r.val]; + if (t->bid == ~0u) + return true; // Undefined (treat as param/global-like) - equivalent to "outside loop" + return !blk_in(fn->rpo[t->bid], L.body); +} + +// Check safety. +bool clobbered_in_loop(Fn* fn, Ins* load_ins, Ref addr, int sz, const LoopInfo& L) { + for (Blk* b : L.body) { + for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) { + if (i == load_ins) + continue; + if (i->op == Ocall) + return true; // Conservative: call is treated as writing all escapable memory + if (isstore(i->op)) { + int ssz = storesz(i); + int delta; + if (alias(addr, 0, sz, i->arg[1], ssz, &delta, fn) != NoAlias) + return true; + } + } + } + return false; +} + +} // namespace + +void licm(Ctx* ctx, Fn* fn) { + fillloop(fn); + + // Phase A hoisted load. + int total_hoisted = 0; + int iter = 0; + for (; iter < 16; iter++) { + std::vector<LoopInfo> loops; + std::vector<int> blk_loop; + build_loops(fn, loops, blk_loop); + if (loops.empty()) + break; + + int round_hoisted = 0; + for (Blk* b = fn->start; b; b = b->link) { + if (b->id >= blk_loop.size()) + continue; + int lidx = blk_loop[b->id]; + if (lidx < 0) + continue; + LoopInfo& L = loops[static_cast<size_t>(lidx)]; + if (!L.preheader) + continue; + + for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) { + if (!isload(i->op)) + continue; + if (!is_invariant(fn, i->arg[0], L)) + continue; + int sz = loadsz(i); + if (clobbered_in_loop(fn, i, i->arg[0], sz, L)) + continue; + + // Hit: move to preheader. + addins(ctx, &L.preheader->ins, &L.preheader->nins, i); + *i = make_nop(); + round_hoisted++; + } + } + + total_hoisted += round_hoisted; + if (round_hoisted == 0) + break; + // Reset loop state. + filluse(ctx, fn); + } + + if (debug['L']) { + FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr; + fprintf(out, "\n> LICM hoisted %d load(s) in %s (in %d round%s)\n", total_hoisted, fn->name, + iter, iter == 1 ? "" : "s"); + } +} + +} // namespace rcc |