diff options
Diffstat (limited to 'src/mid/dead_loop.cc')
| -rw-r--r-- | src/mid/dead_loop.cc | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/src/mid/dead_loop.cc b/src/mid/dead_loop.cc new file mode 100644 index 0000000..26b915a --- /dev/null +++ b/src/mid/dead_loop.cc @@ -0,0 +1,227 @@ +/* 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 dead_loop.cc +/// @brief Dead Loop Elimination: removal of entire loops that have no side-effects, are provably +/// terminating, and have no live-outs. +/// +/// See docs/dead_loop.md for architectural notes. + +#include "rcc/all.h" +#include "rcc/loopinfo.h" + +#include <unordered_set> +#include <vector> + +namespace rcc { + +namespace { + +bool has_side_effect_op(uint op) { + if (isstore(op)) + return true; + if (isalloc(op)) + return true; + if (ispar(op)) + return true; + if (isarg(op)) + return true; + if (op == Ocall) + return true; + if (op == Oblit0 || op == Oblit1) + return true; + if (op == Ovastart || op == Ovaarg) + return true; + if (op == Odbgloc) + return true; + if (op == Osel0 || op == Osel1) + return true; + return false; +} + +bool defined_outside(Fn* fn, const Loop& 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; + return L.body_bid.find(bid) == L.body_bid.end(); +} + +Ins* find_cmp_in(Blk* b, Ref cond) { + for (uint i = 0; i < b->nins; i++) + if (req(b->ins[i].to, cond)) + return &b->ins[i]; + return nullptr; +} + +int find_biv_idx(const std::vector<Biv>& bivs, Ref r) { + for (size_t k = 0; k < bivs.size(); k++) + if (req(bivs[k].to, r)) + return static_cast<int>(k); + return -1; +} + +void collect_body_defs(const Loop& L, std::vector<Ref>& defs) { + for (Blk* b : L.body) { + for (Phi* p = b->phi; p; p = p->link) + if (rtype(p->to) == RTmp) + defs.push_back(p->to); + for (uint k = 0; k < b->nins; k++) + if (rtype(b->ins[k].to) == RTmp) + defs.push_back(b->ins[k].to); + } +} + +bool all_uses_inside(Fn* fn, const Loop& L, Ref tmp_ref) { + if (rtype(tmp_ref) != RTmp) + return true; + if (tmp_ref.val >= static_cast<uint>(fn->ntmp)) + return true; + Tmp* t = &fn->tmp[tmp_ref.val]; + for (uint u = 0; u < t->nuse; u++) { + const Use& uu = t->use[u]; + if (L.body_bid.find(uu.bid) == L.body_bid.end()) + return false; + } + return true; +} + +bool delete_loop_if_dead(Fn* fn, const Loop& L) { + // Topology: unique exit_block + unique exiting_block + Blk* exit_block = nullptr; + Blk* exiting_block = nullptr; + for (Blk* b : L.body) { + Blk* succs[2] = {b->s1, b->s2}; + for (Blk* s : succs) { + if (!s) + continue; + if (L.body_bid.find(s->id) != L.body_bid.end()) + continue; // Internal edge + // Exit loop edge + if (!exit_block) { + exit_block = s; + exiting_block = b; + } else if (exit_block != s || exiting_block != b) { + return false; // Multiple exits or multiple exiting blocks + } + } + } + if (!exit_block) + return false; // No exit -- infinite loop + + // Termination: at least one constant BIV + header Jjnz cmp(BIV, invariant) + std::vector<Biv> bivs; + detect_bivs(fn, L, bivs); + if (bivs.empty()) + return false; + if (L.header->jmp.type != Jjnz) + return false; + Ref cond = L.header->jmp.arg; + if (rtype(cond) != RTmp) + return false; + Ins* cmp = find_cmp_in(L.header, cond); + if (!cmp) + return false; + int bi = find_biv_idx(bivs, cmp->arg[0]); + Ref other = cmp->arg[1]; + if (bi < 0) { + bi = find_biv_idx(bivs, cmp->arg[1]); + other = cmp->arg[0]; + } + if (bi < 0) + return false; + if (!defined_outside(fn, L, other)) + return false; + if (exiting_block != L.header) + return false; + + // Side-effect scan + for (Blk* b : L.body) { + for (uint k = 0; k < b->nins; k++) { + if (has_side_effect_op(b->ins[k].op)) + return false; + } + } + + // Live-out scan + for (Phi* p = exit_block->phi; p; p = p->link) { + for (uint k = 0; k < p->narg; k++) { + if (p->blk[k] != exiting_block) + continue; + if (!defined_outside(fn, L, p->arg[k])) + return false; + } + } + std::vector<Ref> defs; + collect_body_defs(L, defs); + for (Ref r : defs) { + if (!all_uses_inside(fn, L, r)) + return false; + } + + for (Phi* p = exit_block->phi; p; p = p->link) { + for (uint k = 0; k < p->narg; k++) + if (p->blk[k] == L.preheader) + return false; + } + + // Rewrite + // preheader's jmp outgoing edge: the one pointing to header is changed to point to exit_block; + if (L.preheader->s1 == L.header) + L.preheader->s1 = exit_block; + if (L.preheader->s2 == L.header) + L.preheader->s2 = exit_block; + for (Phi* p = exit_block->phi; p; p = p->link) { + for (uint k = 0; k < p->narg; k++) + if (p->blk[k] == exiting_block) + p->blk[k] = L.preheader; + } + + return true; +} + +} // namespace + +void dead_loop(Ctx* ctx, Fn* fn) { + fillpreds(ctx, fn); + fillcfg(ctx, fn); + filluse(ctx, fn); + + std::vector<Loop> loops; + find_loops(fn, loops); + if (loops.empty()) + return; + + int deleted = 0; + for (const Loop& L : loops) { + if (delete_loop_if_dead(fn, L)) + deleted++; + } + + if (debug['L']) { + FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr; + fprintf(out, "\n> dead_loop %s: deleted %d of %zu loop(s)\n", fn->name, deleted, + loops.size()); + } +} + +} // namespace rcc |