Set up a git repoHEADmaster

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