diff options
Diffstat (limited to 'src/mid/dce.cc')
| -rw-r--r-- | src/mid/dce.cc | 149 |
1 files changed, 149 insertions, 0 deletions
diff --git a/src/mid/dce.cc b/src/mid/dce.cc new file mode 100644 index 0000000..6ee631a --- /dev/null +++ b/src/mid/dce.cc @@ -0,0 +1,149 @@ +/* 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 dce.cc +/// @brief Dead Code Elimination: mark-and-sweep starting from side-effect / control flow roots. +/// +/// See docs/dce.md for architectural notes. + +#include "rcc/all.h" + +#include <vector> + +namespace rcc { + +namespace { + +bool is_root(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; +} + +} // namespace + +void dce(Ctx*, Fn* fn) { + int ntmp = fn->ntmp; + std::vector<Phi*> phi_def(static_cast<size_t>(ntmp), nullptr); + std::vector<Ins*> ins_def(static_cast<size_t>(ntmp), nullptr); + + for (Blk* b = fn->start; b; b = b->link) { + for (Phi* p = b->phi; p; p = p->link) + if (rtype(p->to) == RTmp && p->to.val < static_cast<uint>(ntmp)) + phi_def[p->to.val] = p; + for (uint k = 0; k < b->nins; k++) { + Ins* i = &b->ins[k]; + if (rtype(i->to) == RTmp && i->to.val < static_cast<uint>(ntmp)) + ins_def[i->to.val] = i; + } + } + + std::vector<char> alive(static_cast<size_t>(ntmp), 0); + std::vector<uint> wl; + auto mark = [&](Ref r) { + if (rtype(r) == RTmp && r.val < static_cast<uint>(ntmp) && !alive[r.val]) { + alive[r.val] = 1; + wl.push_back(r.val); + } + }; + + for (Blk* b = fn->start; b; b = b->link) { + for (uint k = 0; k < b->nins; k++) { + Ins* i = &b->ins[k]; + if (is_root(i->op)) { + mark(i->arg[0]); + mark(i->arg[1]); + } + } + mark(b->jmp.arg); + } + + while (!wl.empty()) { + uint t = wl.back(); + wl.pop_back(); + if (Ins* d = ins_def[t]) { + mark(d->arg[0]); + mark(d->arg[1]); + continue; + } + if (Phi* p = phi_def[t]) { + for (uint a = 0; a < p->narg; a++) + mark(p->arg[a]); + } + } + + int killed_ins = 0, killed_phi = 0; + for (Blk* b = fn->start; b; b = b->link) { + Phi** pp = &b->phi; + while (*pp) { + Phi* p = *pp; + bool dead = + (rtype(p->to) == RTmp && p->to.val < static_cast<uint>(ntmp) && !alive[p->to.val]); + if (dead) { + *pp = p->link; + killed_phi++; + } else { + pp = &p->link; + } + } + + uint w = 0; + for (uint k = 0; k < b->nins; k++) { + Ins* i = &b->ins[k]; + if (i->op == Onop) { + killed_ins++; + continue; + } + bool root = is_root(i->op); + bool has_to = (rtype(i->to) == RTmp && i->to.val < static_cast<uint>(ntmp)); + if (!root && has_to && !alive[i->to.val]) { + killed_ins++; + continue; + } + if (w != k) + b->ins[w] = *i; + w++; + } + b->nins = w; + } + + if (debug['D']) { + fprintf(stderr, "\n> DCE for %s: killed %d ins, %d phi\n", fn->name, killed_ins, + killed_phi); + } +} + +} // namespace rcc |