[legacy/mid] Add scalar optimizations: fold, copy, GVN, GCM, SCCP, reassociation, DCE

7 files changed, 2604 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/copy.cc b/rcc-legacy/src/mid/copy.cc
new file mode 100644
index 0000000..8a35498
--- /dev/null
+++ b/rcc-legacy/src/mid/copy.cc
@@ -0,0 +1,360 @@
+/* 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 copy.cc
+/// @brief copy equivalence check + narrow parameter sinking - for GVN, no independent driver.
+///
+/// See docs/copy.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <algorithm>
+
+namespace rcc {
+
+namespace {
+
+struct Ext {
+    char zext;
+    char nopw;
+    char usew;
+};
+
+bool decode_ext(int op, Ext* e) {
+    switch (op) {
+        case Oextsb:
+            *e = Ext{0, 7, 8};
+            return true;
+        case Oextub:
+            *e = Ext{1, 8, 8};
+            return true;
+        case Oextsh:
+            *e = Ext{0, 15, 16};
+            return true;
+        case Oextuh:
+            *e = Ext{1, 16, 16};
+            return true;
+        case Oextsw:
+            *e = Ext{0, 31, 32};
+            return true;
+        case Oextuw:
+            *e = Ext{1, 32, 32};
+            return true;
+    }
+    return false;
+}
+
+int bitwidth(uint64_t v) {
+    return v ? 64 - __builtin_clzll(v) : 0;
+}
+
+template <typename Walk>
+int walk_phi_memo(Fn* fn, Ref r, int w, Walk walk) {
+    int ret = walk(fn, r, w);
+    for (Blk* b = fn->start; b; b = b->link)
+        for (Phi* p = b->phi; p; p = p->link)
+            p->visit = 0;
+    return ret;
+}
+
+int uwl(Fn* fn, Ref r, int w);
+
+bool phi_use_ok(Fn* fn, Phi* p, int w) {
+    if (p->visit || req(p->to, Ref::none()))
+        return true;
+    p->visit = 1;
+    return uwl(fn, p->to, w) != 0;
+}
+
+bool ins_use_ok(Fn* fn, Ins* i, Ref r, int w) {
+    Ext e;
+    if (i->op == Ocopy && uwl(fn, i->to, w))
+        return true;
+    if (decode_ext(i->op, &e)) {
+        if (e.usew <= w)
+            return true;
+        return uwl(fn, i->to, w) != 0;
+    }
+    if (i->op == Oand) {
+        Ref rc;
+        if (req(r, i->arg[0])) {
+            rc = i->arg[1];
+        } else {
+            assert(req(r, i->arg[1]));
+            rc = i->arg[0];
+        }
+        int64_t v;
+        return isconbits(fn, rc, &v) && bitwidth(static_cast<uint64_t>(v)) <= w;
+    }
+    return false;
+}
+
+int uwl(Fn* fn, Ref r, int w) {
+    assert(rtype(r) == RTmp);
+    Tmp* t = &fn->tmp[r.val];
+    for (Use* u = &t->use[0]; u < &t->use[t->nuse]; ++u) {
+        bool ok;
+        switch (u->type) {
+            case Use::UPhi:
+                ok = phi_use_ok(fn, u->u.phi, w);
+                break;
+            case Use::UIns:
+                assert(u->u.ins);
+                ok = ins_use_ok(fn, u->u.ins, r, w);
+                break;
+            default:
+                ok = false;
+                break;
+        }
+        if (!ok)
+            return 0;
+    }
+    return 1;
+}
+
+/* no more than w bits are used */
+int usewidthle(Fn* fn, Ref r, int w) {
+    return walk_phi_memo(fn, r, w, uwl);
+}
+
+int dwl(Fn* fn, Ref r, int w) {
+    int64_t v;
+    if (isconbits(fn, r, &v) && bitwidth(static_cast<uint64_t>(v)) <= w)
+        return 1;
+    if (w <= 0)
+        return 0;
+    if (rtype(r) != RTmp)
+        return 0;
+    Tmp* t = &fn->tmp[r.val];
+    if (t->cls != Kw)
+        return 0;
+
+    if (!t->def) {
+        Phi* p = fn->rpo[t->bid]->phi;
+        for (; p; p = p->link)
+            if (req(p->to, r))
+                break;
+        assert(p);
+        if (p->visit && p->visit <= w)
+            return 1;
+        p->visit = w;
+        for (uint n = 0; n < p->narg; ++n)
+            if (!dwl(fn, p->arg[n], w))
+                return 0;
+        return 1;
+    }
+
+    Ins* i = t->def;
+    if (i->op == Ocopy)
+        return dwl(fn, i->arg[0], w);
+
+    if (i->op == Oshr || i->op == Osar) {
+        if (isconbits(fn, i->arg[1], &v) && 0 < v && v <= 32) {
+            if (i->op == Oshr && w + v >= 32)
+                return 1;
+            if (w < 32) {
+                int cap = (i->op == Osar) ? 31 : 32;
+                w = std::min(cap, static_cast<int>(w + v));
+            }
+        }
+        return dwl(fn, i->arg[0], w);
+    }
+
+    int x;
+    if (iscmp(i->op, &x, &x))
+        return w >= 1;
+
+    if (i->op == Oand)
+        return (dwl(fn, i->arg[0], w) || dwl(fn, i->arg[1], w)) ? 1 : 0;
+
+    if (i->op == Oor || i->op == Oxor)
+        return (dwl(fn, i->arg[0], w) && dwl(fn, i->arg[1], w)) ? 1 : 0;
+
+    Ext e;
+    if (decode_ext(i->op, &e)) {
+        if (e.zext && e.usew <= w)
+            return 1;
+        w = std::min(w, static_cast<int>(e.nopw));
+        return dwl(fn, i->arg[0], w);
+    }
+
+    return 0;
+}
+
+/* is the ref narrower than w bits */
+int defwidthle(Fn* fn, Ref r, int w) {
+    return walk_phi_memo(fn, r, w, dwl);
+}
+
+int isw1(Fn* fn, Ref r) {
+    return defwidthle(fn, r, 1);
+}
+
+bool phieq(Phi* pa, Phi* pb) {
+    assert(pa->narg == pb->narg);
+    for (uint n = 0; n < pa->narg; ++n)
+        if (!req(pa->arg[n], phiarg(pb, pa->blk[n])))
+            return false;
+    return true;
+}
+
+}  // namespace
+
+Ref copyref(Ctx* ctx, Fn* fn, Blk* b, Ins* i) {
+    static const bits extcpy[] = {
+        /*WFull*/ 0,
+        /*Wsb*/ BIT(Tmp::Wsb) | BIT(Tmp::Wsh) | BIT(Tmp::Wsw),
+        /*Wub*/ BIT(Tmp::Wub) | BIT(Tmp::Wuh) | BIT(Tmp::Wuw),
+        /*Wsh*/ BIT(Tmp::Wsh) | BIT(Tmp::Wsw),
+        /*Wuh*/ BIT(Tmp::Wuh) | BIT(Tmp::Wuw),
+        /*Wsw*/ BIT(Tmp::Wsw),
+        /*Wuw*/ BIT(Tmp::Wuw),
+    };
+    MAKESURE(extcpy_covers_all_widths, sizeof(extcpy) / sizeof(extcpy[0]) == Tmp::Wuw + 1);
+
+    if (i->op == Ocopy)
+        return i->arg[0];
+
+    const Op& od = optab[i->op];
+
+    if (od.hasid && KBASE(i->cls) == 0 && req(i->arg[1], ctx->gvn_con01[od.idval]) &&
+        (!od.cmpeqwl || isw1(fn, i->arg[0])))
+        return i->arg[0];
+
+    if (od.idemp && req(i->arg[0], i->arg[1]))
+        return i->arg[0];
+
+    if ((od.cmpeqwl || od.cmplgtewl) && req(i->arg[0], i->arg[1]))
+        return ctx->gvn_con01[od.eqval];
+
+    int z;
+    if (od.cmpeqwl && req(i->arg[1], Ref::con_z()) && zeroval(fn, b, i->arg[0], argcls(i, 0), &z))
+        return ctx->gvn_con01[od.eqval ^ z ^ 1];
+
+    int64_t v;
+    if (i->op == Oand && isconbits(fn, i->arg[1], &v) && v > 0 && ((v + 1) & v) == 0 &&
+        defwidthle(fn, i->arg[0], bitwidth(static_cast<uint64_t>(v))))
+        return i->arg[0];
+
+    if (i->cls == Kw && (i->op == Oextsw || i->op == Oextuw))
+        return i->arg[0];
+
+    Ext e;
+    if (decode_ext(i->op, &e) && rtype(i->arg[0]) == RTmp) {
+        Tmp* t = &fn->tmp[i->arg[0].val];
+        assert(KBASE(t->cls) == 0);
+
+        if (KWIDE(i->cls) > KWIDE(t->cls))
+            return Ref::none();
+
+        int w = Tmp::Wsb + (static_cast<int>(i->op) - Oextsb);
+        if (BIT(w) & extcpy[t->width])
+            return i->arg[0];
+
+        if ((!t->def || !ispar(t->def->op)) && usewidthle(fn, i->to, e.usew))
+            return i->arg[0];
+
+        if (defwidthle(fn, i->arg[0], e.nopw))
+            return i->arg[0];
+    }
+
+    return Ref::none();
+}
+
+Ref phicopyref(Ctx* ctx, Fn* fn, Blk* b, Phi* p) {
+    Ref r = Ref::none();
+    uint n = 0;
+    for (; n < p->narg; ++n)
+        if (!req(p->arg[n], p->to)) {
+            if (req(r, Ref::none()))
+                r = p->arg[n];
+            else if (!req(p->arg[n], r))
+                break;
+        }
+    if (n == p->narg)
+        return r;
+
+    for (Phi* p1 = b->phi; p1 != p; p1 = p1->link) {
+        assert(p1);
+        if (phieq(p1, p))
+            return p1->to;
+    }
+
+    Blk* d = b->idom;
+    if (p->narg != 2 || d->jmp.type != Jjnz || !isw1(fn, d->jmp.arg))
+        return Ref::none();
+
+    Blk* s[2] = {nullptr, nullptr};
+    for (uint k = 0; k < 2; ++k)
+        for (uint c = 0; c < 2; ++c)
+            if (req(p->arg[k], ctx->gvn_con01[c]))
+                s[c] = p->blk[k];
+
+    if (d->s1 == s[1] && d->s2 == s[0] && d->s1->jmp.type == Jjmp && d->s2->jmp.type == Jjmp)
+        return d->jmp.arg;
+
+    return Ref::none();
+}
+
+void narrowpars(Ctx* ctx, Fn* fn) {
+    bool has_loop = false;
+    for (Blk* b = fn->start; b; b = b->link)
+        if (b->loop > 1) {
+            has_loop = true;
+            break;
+        }
+    if (!has_loop)
+        return;
+
+    Blk* b = fn->start;
+
+    uint npar = 0;
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i) {
+        if (!ispar(i->op))
+            break;
+        ++npar;
+    }
+    if (npar == 0)
+        return;
+
+    uint nins = b->nins + npar;
+    Ins* ins = static_cast<Ins*>(vnew(ctx, nins, sizeof(Ins), PFn));
+    icpy(ins, b->ins, npar);
+    icpy(ins + 2 * npar, b->ins + npar, b->nins - npar);
+    b->ins = ins;
+    b->nins = nins;
+
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i) {
+        if (!ispar(i->op))
+            break;
+        Ins extins = {};
+        extins.op = Onop;
+        if (i->cls == Kw && usewidthle(fn, i->to, 16)) {
+            extins.op = usewidthle(fn, i->to, 8) ? Oextub : Oextuh;
+            Ref r = newtmp(ctx, "vw", i->cls, fn);
+            extins.cls = i->cls;
+            extins.to = i->to;
+            extins.arg[0] = r;
+            i->to = r;
+        }
+        *(i + npar) = extins;
+    }
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/dce.cc b/rcc-legacy/src/mid/dce.cc
new file mode 100644
index 0000000..6ee631a
--- /dev/null
+++ b/rcc-legacy/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
diff --git a/rcc-legacy/src/mid/fold.cc b/rcc-legacy/src/mid/fold.cc
new file mode 100644
index 0000000..df88694
--- /dev/null
+++ b/rcc-legacy/src/mid/fold.cc
@@ -0,0 +1,423 @@
+/* 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 fold.cc
+/// @brief Constant folding utilities -- called by GVN (dedupins / assoccon), no standalone driver.
+///
+/// See docs/fold.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <cstdint>
+#include <cstring>
+
+namespace rcc {
+
+namespace {
+
+inline bool iscon(const Con* c, int w, uint64_t k) {
+    if (c->type != Con::CBits)
+        return false;
+    int64_t v = w ? c->bits.i : static_cast<int32_t>(c->bits.i);
+    return static_cast<uint64_t>(v) == (w ? k : static_cast<uint32_t>(k));
+}
+
+union Bits64 {
+    int64_t s;
+    uint64_t u;
+    float fs;
+    double fd;
+};
+
+inline Bits64 read_bits(const Con* c) {
+    Bits64 b;
+    b.s = c->bits.i;
+    return b;
+}
+
+int addr_combine(int op, const Con* cl, const Con* cr, int* typ_out, Sym* sym_out) {
+    int ctyp = Con::CBits;
+    Sym sym;
+    std::memset(&sym, 0, sizeof sym);
+
+    bool al = (cl->type == Con::CAddr);
+    bool ar = (cr->type == Con::CAddr);
+
+    if (op == Oadd) {
+        if (al && ar)
+            return 1;
+        if (al || ar) {
+            ctyp = Con::CAddr;
+            sym = al ? cl->sym : cr->sym;
+        }
+    } else if (op == Osub) {
+        if (al && ar) {
+            if (!symeq(cl->sym, cr->sym))
+                return 1;
+            // Subtract same sym.
+        } else if (al) {
+            ctyp = Con::CAddr;
+            sym = cl->sym;
+        } else if (ar) {
+            return 1;  // Number - address is invalid
+        }
+    } else if (op == Ocast) {
+        if (al) {
+            ctyp = Con::CAddr;
+            sym = cl->sym;
+        }
+    } else if (al || ar) {
+        return 1;
+    }
+    *typ_out = ctyp;
+    *sym_out = sym;
+    return 0;
+}
+
+uint64_t foldcmp_int(int cmp, int w, Bits64 l, Bits64 r) {
+    if (!w) {
+        l.u = static_cast<uint64_t>(static_cast<int32_t>(l.u));
+        r.u = static_cast<uint64_t>(static_cast<int32_t>(r.u));
+    }
+    switch (cmp) {
+        case Cieq:
+            return l.u == r.u;
+        case Cine:
+            return l.u != r.u;
+        case Ciule:
+            return l.u <= r.u;
+        case Ciult:
+            return l.u < r.u;
+        case Ciuge:
+            return l.u >= r.u;
+        case Ciugt:
+            return l.u > r.u;
+        case Cisle:
+            return l.s <= r.s;
+        case Cislt:
+            return l.s < r.s;
+        case Cisge:
+            return l.s >= r.s;
+        case Cisgt:
+            return l.s > r.s;
+        default:
+            die("foldcmp_int: bad cmp %d", cmp);
+    }
+}
+
+template <typename F>
+uint64_t foldcmp_flt(int cmp, F l, F r) {
+    switch (cmp) {
+        case Cfeq:
+            return l == r;
+        case Cfne:
+            return l != r;
+        case Cfle:
+            return l <= r;
+        case Cflt:
+            return l < r;
+        case Cfge:
+            return l >= r;
+        case Cfgt:
+            return l > r;
+        case Cfo:
+            return (l < r) || (l >= r);
+        case Cfuo:
+            return !((l < r) || (l >= r));
+        default:
+            die("foldcmp_flt: bad cmp %d", cmp);
+    }
+}
+
+void foldflt(Con* res, int op, int w, const Con* cl, const Con* cr) {
+    if (cl->type != Con::CBits || cr->type != Con::CBits)
+        err(const_cast<char*>("invalid address operand for '%s'"), optab[op].name);
+
+    res->type = Con::CBits;
+    res->sym = Sym{};
+    std::memset(&res->bits, 0, sizeof res->bits);
+    res->flt = 0;
+
+    if (w) {
+        double ld = cl->bits.d, rd = cr->bits.d, xd;
+        switch (op) {
+            case Oadd:
+                xd = ld + rd;
+                break;
+            case Osub:
+                xd = ld - rd;
+                break;
+            case Oneg:
+                xd = -ld;
+                break;
+            case Odiv:
+                xd = ld / rd;
+                break;
+            case Omul:
+                xd = ld * rd;
+                break;
+            case Oswtof:
+                xd = static_cast<double>(static_cast<int32_t>(cl->bits.i));
+                break;
+            case Ouwtof:
+                xd = static_cast<double>(static_cast<uint32_t>(cl->bits.i));
+                break;
+            case Osltof:
+                xd = static_cast<double>(static_cast<int64_t>(cl->bits.i));
+                break;
+            case Oultof:
+                xd = static_cast<double>(static_cast<uint64_t>(cl->bits.i));
+                break;
+            case Oexts:
+                xd = static_cast<double>(cl->bits.s);
+                break;
+            case Ocast:
+                xd = ld;
+                break;
+            default:
+                die("foldflt: bad op Kd %d", op);
+        }
+        res->bits.d = xd;
+        res->flt = 2;
+    } else {
+        float ls = cl->bits.s, rs = cr->bits.s, xs;
+        switch (op) {
+            case Oadd:
+                xs = ls + rs;
+                break;
+            case Osub:
+                xs = ls - rs;
+                break;
+            case Oneg:
+                xs = -ls;
+                break;
+            case Odiv:
+                xs = ls / rs;
+                break;
+            case Omul:
+                xs = ls * rs;
+                break;
+            case Oswtof:
+                xs = static_cast<float>(static_cast<int32_t>(cl->bits.i));
+                break;
+            case Ouwtof:
+                xs = static_cast<float>(static_cast<uint32_t>(cl->bits.i));
+                break;
+            case Osltof:
+                xs = static_cast<float>(static_cast<int64_t>(cl->bits.i));
+                break;
+            case Oultof:
+                xs = static_cast<float>(static_cast<uint64_t>(cl->bits.i));
+                break;
+            case Otruncd:
+                xs = static_cast<float>(cl->bits.d);
+                break;
+            case Ocast:
+                xs = ls;
+                break;
+            default:
+                die("foldflt: bad op Ks %d", op);
+        }
+        res->bits.s = xs;
+        res->flt = 1;
+    }
+}
+
+}  // namespace
+
+int foldint(Con* res, int op, int w, Con* cl, Con* cr) {
+    // Address combination check.
+    int ctyp;
+    Sym sym;
+    if (addr_combine(op, cl, cr, &ctyp, &sym))
+        return 1;
+
+    Bits64 l = read_bits(cl);
+    Bits64 r = read_bits(cr);
+
+    // Div / rem.
+    if (op == Odiv || op == Orem || op == Oudiv || op == Ourem) {
+        if (iscon(cr, w, 0))
+            return 1;
+        if (op == Odiv || op == Orem) {
+            uint64_t intmin = w ? static_cast<uint64_t>(INT64_MIN)
+                                : static_cast<uint64_t>(static_cast<uint32_t>(INT32_MIN));
+            if (iscon(cr, w, static_cast<uint64_t>(-1)) && iscon(cl, w, intmin))
+                return 1;
+        }
+    }
+
+    // Dispatch.
+    uint64_t x;
+
+    if (op >= Ocmpw && op <= Ocmpw1) {
+        x = foldcmp_int(op - Ocmpw, /*w=*/0, l, r);
+    } else if (op >= Ocmpl && op <= Ocmpl1) {
+        x = foldcmp_int(op - Ocmpl, /*w=*/1, l, r);
+    } else if (op >= Ocmps && op <= Ocmps1) {
+        x = foldcmp_flt<float>(op - Ocmps, cl->bits.s, cr->bits.s);
+    } else if (op >= Ocmpd && op <= Ocmpd1) {
+        x = foldcmp_flt<double>(op - Ocmpd, cl->bits.d, cr->bits.d);
+    } else {
+        // Shift count mask.
+        const uint64_t shmask = static_cast<uint64_t>(31 | (w << 5));
+        switch (op) {
+            case Oadd:
+                x = l.u + r.u;
+                break;
+            case Osub:
+                x = l.u - r.u;
+                break;
+            case Oneg:
+                x = -l.u;
+                break;
+            case Omul:
+                x = l.u * r.u;
+                break;
+            case Odiv:
+                x = w ? static_cast<uint64_t>(l.s / r.s)
+                      : static_cast<uint64_t>(static_cast<int32_t>(l.s) /
+                                              static_cast<int32_t>(r.s));
+                break;
+            case Orem:
+                x = w ? static_cast<uint64_t>(l.s % r.s)
+                      : static_cast<uint64_t>(static_cast<int32_t>(l.s) %
+                                              static_cast<int32_t>(r.s));
+                break;
+            case Oudiv:
+                x = w ? l.u / r.u : static_cast<uint32_t>(l.u) / static_cast<uint32_t>(r.u);
+                break;
+            case Ourem:
+                x = w ? l.u % r.u : static_cast<uint32_t>(l.u) % static_cast<uint32_t>(r.u);
+                break;
+            case Oand:
+                x = l.u & r.u;
+                break;
+            case Oor:
+                x = l.u | r.u;
+                break;
+            case Oxor:
+                x = l.u ^ r.u;
+                break;
+            // Signed right shift.
+            case Osar:
+                x = static_cast<uint64_t>((w ? l.s : static_cast<int32_t>(l.s)) >> (r.u & shmask));
+                break;
+            case Oshr:
+                x = (w ? l.u : static_cast<uint32_t>(l.u)) >> (r.u & shmask);
+                break;
+            case Oshl:
+                x = l.u << (r.u & shmask);
+                break;
+
+            case Oextsb:
+                x = static_cast<uint64_t>(static_cast<int8_t>(l.u));
+                break;
+            case Oextub:
+                x = static_cast<uint8_t>(l.u);
+                break;
+            case Oextsh:
+                x = static_cast<uint64_t>(static_cast<int16_t>(l.u));
+                break;
+            case Oextuh:
+                x = static_cast<uint16_t>(l.u);
+                break;
+            case Oextsw:
+                x = static_cast<uint64_t>(static_cast<int32_t>(l.u));
+                break;
+            case Oextuw:
+                x = static_cast<uint32_t>(l.u);
+                break;
+
+            case Ostosi:
+                x = w ? static_cast<uint64_t>(static_cast<int64_t>(cl->bits.s))
+                      : static_cast<uint64_t>(static_cast<int32_t>(cl->bits.s));
+                break;
+            case Ostoui:
+                x = w ? static_cast<uint64_t>(cl->bits.s)
+                      : static_cast<uint64_t>(static_cast<uint32_t>(cl->bits.s));
+                break;
+            case Odtosi:
+                x = w ? static_cast<uint64_t>(static_cast<int64_t>(cl->bits.d))
+                      : static_cast<uint64_t>(static_cast<int32_t>(cl->bits.d));
+                break;
+            case Odtoui:
+                x = w ? static_cast<uint64_t>(cl->bits.d)
+                      : static_cast<uint64_t>(static_cast<uint32_t>(cl->bits.d));
+                break;
+            case Ocast:
+                x = l.u;
+                break;
+            default:
+                die("foldint: unsupported op %d", op);
+        }
+    }
+
+    // Write back.
+    res->type = static_cast<decltype(res->type)>(ctyp);
+    res->sym = sym;
+    std::memset(&res->bits, 0, sizeof res->bits);
+    res->bits.i = static_cast<int64_t>(x);
+    res->flt = 0;
+    return 0;
+}
+
+namespace {
+
+Ref opfold(Ctx* ctx, int op, int cls, Con* cl, Con* cr, Fn* fn) {
+    Con c;
+    std::memset(&c, 0, sizeof c);
+
+    if (cls == Kw || cls == Kl) {
+        if (foldint(&c, op, cls == Kl, cl, cr))
+            return Ref::none();
+    } else {
+        foldflt(&c, op, cls == Kd, cl, cr);
+    }
+
+    if (!KWIDE(cls))
+        c.bits.i &= 0xffffffff;
+
+    Ref r = newcon(ctx, &c, fn);
+    assert((cls != Ks && cls != Kd) || c.flt);
+    return r;
+}
+
+}  // namespace
+
+Ref foldref(Ctx* ctx, Fn* fn, Ins* i) {
+    if (rtype(i->to) != RTmp)
+        return Ref::none();
+    if (!optab[i->op].canfold)
+        return Ref::none();
+    if (rtype(i->arg[0]) != RCon)
+        return Ref::none();
+
+    Ref rr = i->arg[1];
+    if (req(rr, Ref::none()))
+        rr = Ref::con_z();
+    if (rtype(rr) != RCon)
+        return Ref::none();
+
+    Con* cl = &fn->con[i->arg[0].val];
+    Con* cr = &fn->con[rr.val];
+    return opfold(ctx, i->op, i->cls, cl, cr, fn);
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/gcm.cc b/rcc-legacy/src/mid/gcm.cc
new file mode 100644
index 0000000..cb3c1df
--- /dev/null
+++ b/rcc-legacy/src/mid/gcm.cc
@@ -0,0 +1,373 @@
+/* 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 gcm.cc
+/// @brief Global Code Motion (GCM, Click's algorithm) -- rearranges instructions into the
+/// "shallowest loop" legal block on the dominator tree.
+///
+/// See docs/gcm.md for architectural notes.
+
+#include "rcc/all.h"
+
+namespace rcc {
+
+namespace {
+
+constexpr uint NOBID = ~0u;
+
+bool isdivwl(Ins* i) {
+    return INRANGE(i->op, Odiv, Ourem) && KBASE(i->cls) == 0;
+}
+
+bool canelim(Ins* i) {
+    return isload(i->op) || isalloc(i->op) || isdivwl(i);
+}
+
+Ins nopins() {
+    Ins i = {};
+    i.op = Onop;
+    return i;
+}
+
+bool cheap(Ins* i) {
+    if (KBASE(i->cls) != 0)
+        return false;
+    switch (i->op) {
+        case Oneg:
+        case Oadd:
+        case Osub:
+        case Omul:
+        case Oand:
+        case Oor:
+        case Oxor:
+        case Osar:
+        case Oshr:
+        case Oshl:
+            return true;
+        default: {
+            int x;
+            return iscmp(i->op, &x, &x) != 0;
+        }
+    }
+}
+
+// schedearly
+
+uint earlyins(Fn*, Blk*, Ins*);
+
+uint schedearly(Fn* fn, Ref r) {
+    if (rtype(r) != RTmp)
+        return 0;
+
+    Tmp* t = &fn->tmp[r.val];
+    if (t->gcmbid != NOBID)
+        return t->gcmbid;
+
+    if (!t->def)
+        return t->gcmbid = t->bid;  // phi doesn't move, pinned to def block
+
+    Blk* b = fn->rpo[t->bid];
+    assert(b->ins <= t->def && t->def < &b->ins[b->nins]);
+    t->gcmbid = 0;  // Visiting sentinel (recursive backedge gets 0 = start)
+    return t->gcmbid = earlyins(fn, b, t->def);
+}
+
+uint earlyins(Fn* fn, Blk* b, Ins* i) {
+    uint ba = schedearly(fn, i->arg[0]);
+    uint bb = schedearly(fn, i->arg[1]);
+    assert(ba != NOBID && bb != NOBID);
+
+    // Take the deeper operand block in dominator tree (shallower dominates deeper)
+    if (fn->rpo[ba]->depth < fn->rpo[bb]->depth) {
+        assert(dom(fn->rpo[ba], fn->rpo[bb]));
+        ba = bb;
+    }
+    return pinned(i) ? b->id : ba;
+}
+
+void earlyblk(Fn* fn, uint bid) {
+    Blk* b = fn->rpo[bid];
+
+    for (Phi* p = b->phi; p; p = p->link)
+        for (uint n = 0; n < p->narg; n++)
+            schedearly(fn, p->arg[n]);
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; i++)
+        if (pinned(i)) {
+            schedearly(fn, i->arg[0]);
+            schedearly(fn, i->arg[1]);
+        }
+    schedearly(fn, b->jmp.arg);
+}
+
+// schedlate + bestbid
+
+uint lcabid(Fn* fn, uint b1, uint b2) {
+    if (b1 == NOBID)
+        return b2;
+    if (b2 == NOBID)
+        return b1;
+    Blk* b = lca(fn->rpo[b1], fn->rpo[b2]);
+    assert(b);
+    return b->id;
+}
+
+uint bestbid(Fn* fn, uint earlybid, uint latebid) {
+    if (latebid == NOBID)
+        return NOBID;  // Unused
+    assert(earlybid != NOBID);
+
+    Blk* earlyb = fn->rpo[earlybid];
+    Blk* bestb = fn->rpo[latebid];
+    assert(dom(earlyb, bestb));
+
+    for (Blk* curb = bestb; curb != earlyb;) {
+        curb = curb->idom;
+        if (curb->loop < bestb->loop)
+            bestb = curb;
+    }
+    return bestb->id;
+}
+
+uint lateins(Fn*, Blk*, Ins*, Ref);
+uint latephi(Fn*, Phi*, Ref);
+uint latejmp(Blk*, Ref);
+
+uint schedlate(Fn* fn, Ref r) {
+    if (rtype(r) != RTmp)
+        return NOBID;
+
+    Tmp* t = &fn->tmp[r.val];
+    if (t->visit)
+        return t->gcmbid;
+    t->visit = 1;
+
+    uint earlybid = t->gcmbid;
+    if (earlybid == NOBID)
+        return NOBID;  // Unused
+
+    t->gcmbid = t->bid;  // Reuse gcmbid field to temporarily store late
+    uint latebid = NOBID;
+    for (Use* u = t->use; u < &t->use[t->nuse]; u++) {
+        assert(u->bid < fn->nblk);
+        Blk* b = fn->rpo[u->bid];
+        uint usebid;
+        switch (u->type) {
+            case Use::UPhi:
+                usebid = latephi(fn, u->u.phi, r);
+                break;
+            case Use::UIns:
+                usebid = lateins(fn, b, u->u.ins, r);
+                break;
+            case Use::UJmp:
+                usebid = latejmp(b, r);
+                break;
+            default:
+                die("unreachable");
+        }
+        latebid = lcabid(fn, latebid, usebid);
+    }
+    // latebid might still be NOBID: temp is only indirectly used by "deletable pinned instructions"
+
+    if (t->def && !pinned(t->def))
+        t->gcmbid = bestbid(fn, earlybid, latebid);
+    // Otherwise keep early
+
+    return t->gcmbid;
+}
+
+uint lateins(Fn* fn, Blk* b, Ins* i, Ref r) {
+    assert(b->ins <= i && i < &b->ins[b->nins]);
+    assert(req(i->arg[0], r) || req(i->arg[1], r));
+
+    uint latebid = schedlate(fn, i->to);
+    if (pinned(i)) {
+        if (latebid == NOBID && canelim(i))
+            return NOBID;
+        return b->id;
+    }
+    return latebid;
+}
+
+uint latephi(Fn* fn, Phi* p, Ref r) {
+    if (!p->narg)
+        return NOBID;  // Marked unused
+
+    uint latebid = NOBID;
+    for (uint n = 0; n < p->narg; n++)
+        if (req(p->arg[n], r))
+            latebid = lcabid(fn, latebid, p->blk[n]->id);
+
+    assert(latebid != NOBID);
+    return latebid;
+}
+
+uint latejmp(Blk* b, Ref r) {
+    if (req(b->jmp.arg, Ref::none()))
+        return NOBID;
+    assert(req(b->jmp.arg, r));
+    return b->id;
+}
+
+void lateblk(Fn* fn, uint bid) {
+    Blk* b = fn->rpo[bid];
+
+    for (Phi** pp = &b->phi; *pp;) {
+        if (schedlate(fn, (*pp)->to) == NOBID) {
+            (*pp)->narg = 0;    // Mark unused
+            *pp = (*pp)->link;  // Remove this phi
+        } else {
+            pp = &(*pp)->link;
+        }
+    }
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; i++)
+        if (pinned(i))
+            schedlate(fn, i->to);
+}
+
+// gcmmove
+
+void addgcmins(Ctx* ctx, Fn* fn, Ins* vins, uint nins) {
+    for (Ins* i = vins; i < &vins[nins]; i++) {
+        assert(rtype(i->to) == RTmp);
+        Tmp* t = &fn->tmp[i->to.val];
+        Blk* b = fn->rpo[t->gcmbid];
+        addins(ctx, &b->ins, &b->nins, i);
+    }
+}
+
+void gcmmove(Ctx* ctx, Fn* fn) {
+    uint nins = 0;
+    Ins* vins = static_cast<Ins*>(vnew(ctx, nins, sizeof vins[0], PFn));
+
+    for (Tmp* t = fn->tmp; t < &fn->tmp[fn->ntmp]; t++) {
+        if (!t->def || t->bid == t->gcmbid)
+            continue;
+        Ins* i = t->def;
+        if (pinned(i) && !canelim(i))
+            continue;
+        assert(rtype(i->to) == RTmp && t == &fn->tmp[i->to.val]);
+        if (t->gcmbid != NOBID)
+            addins(ctx, &vins, &nins, i);
+        *i = nopins();
+    }
+    addgcmins(ctx, fn, vins, nins);
+}
+
+// schedblk (intra-block DFS ordering)
+
+Ins* schedins(Ctx* ctx, Fn* fn, Blk* b, Ins* i, Ins** pvins, uint* pnins) {
+    Ins *i0, *i1;
+    igroup(b, i, &i0, &i1);
+
+    // First recursively order the defs in this block that are depended on by operands in this group
+    for (i = i0; i < i1; i++)
+        for (uint n = 0; n < 2; n++) {
+            if (rtype(i->arg[n]) != RTmp)
+                continue;
+            Tmp* t = &fn->tmp[i->arg[n].val];
+            if (t->bid != b->id || !t->def)
+                continue;
+            schedins(ctx, fn, b, t->def, pvins, pnins);
+        }
+    // Then emit this group, wipe original to nop (prevent double emission)
+    for (i = i0; i < i1; i++) {
+        addins(ctx, pvins, pnins, i);
+        *i = nopins();
+    }
+    return i1;
+}
+
+void schedblk(Ctx* ctx, Fn* fn) {
+    Ins* vins = static_cast<Ins*>(vnew(ctx, 0, sizeof vins[0], PHeap));
+
+    for (Blk* b = fn->start; b; b = b->link) {
+        uint nins = 0;
+        for (Ins* i = b->ins; i < &b->ins[b->nins];)
+            i = schedins(ctx, fn, b, i, &vins, &nins);
+        idup(ctx, b, vins, nins);
+    }
+    vfree(vins);
+}
+
+// sink (trivial op sinking)
+
+void sinkref(Ctx* ctx, Fn* fn, Blk* b, Ref* pr) {
+    if (rtype(*pr) != RTmp)
+        return;
+    Tmp* t = &fn->tmp[pr->val];
+    if (!t->def || t->bid == b->id || pinned(t->def) || !cheap(t->def))
+        return;
+
+    // Copy t->def and sink to b
+    Ins i = *t->def;
+    Ref r = newtmp(ctx, "snk", t->cls, fn);
+    t = nullptr;  // newtmp might realloc fn->tmp, old pointer invalid
+    *pr = r;
+    i.to = r;
+    fn->tmp[r.val].gcmbid = b->id;
+    emiti(ctx, i);
+    sinkref(ctx, fn, b, &i.arg[0]);
+    sinkref(ctx, fn, b, &i.arg[1]);
+}
+
+void sink(Ctx* ctx, Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link) {
+        for (Ins* i = b->ins; i < &b->ins[b->nins]; i++)
+            if (isload(i->op))
+                sinkref(ctx, fn, b, &i->arg[0]);
+            else if (isstore(i->op))
+                sinkref(ctx, fn, b, &i->arg[1]);
+        sinkref(ctx, fn, b, &b->jmp.arg);
+    }
+    addgcmins(ctx, fn, ctx->curi, static_cast<uint>(&ctx->insb[NIns] - ctx->curi));
+}
+
+}  // namespace
+
+int pinned(Ins* i) {
+    return optab[i->op].pinned || isdivwl(i);
+}
+
+void gcm(Ctx* ctx, Fn* fn) {
+    filldepth(fn);
+    fillloop(fn);
+
+    for (Tmp* t = fn->tmp; t < &fn->tmp[fn->ntmp]; t++) {
+        t->visit = 0;
+        t->gcmbid = NOBID;
+    }
+    for (uint bid = 0; bid < fn->nblk; bid++)
+        earlyblk(fn, bid);
+    for (uint bid = 0; bid < fn->nblk; bid++)
+        lateblk(fn, bid);
+
+    gcmmove(ctx, fn);
+    filluse(ctx, fn);
+    ctx->curi = &ctx->insb[NIns];
+    sink(ctx, fn);
+    filluse(ctx, fn);
+    schedblk(ctx, fn);
+
+    if (debug['G']) {
+        fprintf(ctx->dbg_buf, "\n> After GCM:\n");
+        printfn(fn, ctx->dbg_buf);
+    }
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/gvn.cc b/rcc-legacy/src/mid/gvn.cc
new file mode 100644
index 0000000..8e029da
--- /dev/null
+++ b/rcc-legacy/src/mid/gvn.cc
@@ -0,0 +1,414 @@
+/* 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 gvn.cc
+/// @brief Global Value Numbering (GVN) - Cross-block deduplication + jnz simplification + dead
+/// block rescue.
+///
+/// See docs/gvn.md for Global Value Numbering architectural notes.
+
+#include "rcc/all.h"
+
+namespace rcc {
+
+namespace {
+
+// Instruction hashing.
+
+inline uint mix(uint x0, uint x1) {
+    return x0 + 31 * x1;
+}
+
+inline uint rhash(Ref r) {
+    return mix(r.type, r.val);
+}
+
+uint ihash(Ins* i) {
+    uint h = mix(i->op, i->cls);
+    h = mix(h, rhash(i->arg[0]));
+    h = mix(h, rhash(i->arg[1]));
+    return h;
+}
+
+bool ieq(Ins* a, Ins* b) {
+    return a->op == b->op && a->cls == b->cls && req(a->arg[0], b->arg[0]) &&
+           req(a->arg[1], b->arg[1]);
+}
+
+// Lookup instruction.
+Ins* gvndup(Ctx* ctx, Ins* i, int insert) {
+    uint idx = ihash(i) % ctx->gvn_tbln;
+    for (Ins* ii; (ii = ctx->gvn_tbl[idx]);) {
+        if (ieq(i, ii))
+            return ii;
+        if (++idx >= ctx->gvn_tbln)
+            idx = 0;
+    }
+    if (insert)
+        ctx->gvn_tbl[idx] = i;
+    return nullptr;
+}
+
+// Use replacement.
+
+void replaceuse(Ctx* ctx, Fn* fn, Use* u, Ref r1, Ref r2) {
+    Tmp* t2 = (rtype(r2) == RTmp) ? &fn->tmp[r2.val] : nullptr;
+    Blk* b = fn->rpo[u->bid];
+    switch (u->type) {
+        case Use::UPhi: {
+            Phi* p = u->u.phi;
+            for (Ref* pr = p->arg; pr < &p->arg[p->narg]; ++pr)
+                if (req(*pr, r1))
+                    *pr = r2;
+            if (t2)
+                adduse_phi(ctx, t2, b, p);
+            break;
+        }
+        case Use::UIns: {
+            Ins* i = u->u.ins;
+            for (int n = 0; n < 2; ++n)
+                if (req(i->arg[n], r1))
+                    i->arg[n] = r2;
+            if (t2)
+                adduse_ins(ctx, t2, b, i);
+            break;
+        }
+        case Use::UJmp:
+            if (req(b->jmp.arg, r1))
+                b->jmp.arg = r2;
+            if (t2)
+                adduse_jmp(ctx, t2, b);
+            break;
+        case Use::UXXX:
+            die("unreachable");
+    }
+}
+
+void replaceuses(Ctx* ctx, Fn* fn, Ref r1, Ref r2) {
+    assert(rtype(r1) == RTmp);
+    Tmp* t1 = &fn->tmp[r1.val];
+    for (Use* u = t1->use; u < &t1->use[t1->nuse]; ++u)
+        replaceuse(ctx, fn, u, r1, r2);
+    t1->nuse = 0;
+}
+
+// Nullify instruction.
+void killins(Ctx* ctx, Fn* fn, Ins* i, Ref r) {
+    replaceuses(ctx, fn, i->to, r);
+    *i = {};
+    i->op = Onop;
+}
+
+// Handle degraded phi.
+void dedupphi(Ctx* ctx, Fn* fn, Blk* b) {
+    Phi** pp = &b->phi;
+    for (Phi* p; (p = *pp);) {
+        Ref r = phicopyref(ctx, fn, b, p);
+        if (req(r, Ref::none())) {
+            pp = &p->link;
+        } else {
+            replaceuses(ctx, fn, p->to, r);
+            p->to = Ref::none();
+            *pp = p->link;
+        }
+    }
+}
+
+// Instruction normalization.
+
+int rcmp(Ref a, Ref b) {
+    if (rtype(a) != rtype(b))
+        return rtype(a) - rtype(b);
+    return static_cast<int>(a.val) - static_cast<int>(b.val);
+}
+
+void normins(Ctx* ctx, Fn* fn, Ins* i) {
+    int64_t v;
+    // Truncate to 32 bits.
+    for (int n = 0; n < 2; ++n)
+        if (!KWIDE(argcls(i, n)) && isconbits(fn, i->arg[n], &v) && (v & 0xffffffffLL) != v)
+            i->arg[n] = getcon(ctx, v & 0xffffffffLL, fn);
+    // Commutative op sort.
+    if (optab[i->op].commutes && rcmp(i->arg[0], i->arg[1]) > 0) {
+        Ref r = i->arg[1];
+        i->arg[1] = i->arg[0];
+        i->arg[0] = r;
+    }
+}
+
+// Negate constant.
+int negcon(int cls, Con* c) {
+    Con z = {};
+    z.type = Con::CBits;
+    z.bits.i = 0;
+    return foldint(c, Osub, cls, &z, c);
+}
+
+// Merge constants.
+void assoccon(Ctx* ctx, Fn* fn, Blk* b, Ins* i1) {
+    int op = (i1->op == Osub) ? Oadd : static_cast<int>(i1->op);
+
+    if (!optab[op].assoc || KBASE(i1->cls) != 0 || rtype(i1->arg[0]) != RTmp ||
+        rtype(i1->arg[1]) != RCon)
+        return;
+    Con c1 = fn->con[i1->arg[1].val];
+
+    Tmp* t2 = &fn->tmp[i1->arg[0].val];
+    if (!t2->def)
+        return;
+    Ins* i2 = t2->def;
+
+    if (op != (i2->op == Osub ? Oadd : static_cast<int>(i2->op)) || rtype(i2->arg[1]) != RCon)
+        return;
+    Con c2 = fn->con[i2->arg[1].val];
+
+    assert(KBASE(i2->cls) == 0);
+    assert(KWIDE(i2->cls) >= KWIDE(i1->cls));
+
+    // Unify as add.
+    if (i1->op == Osub && negcon(i1->cls, &c1))
+        return;
+    if (i2->op == Osub && negcon(i2->cls, &c2))
+        return;
+    Con c;
+    if (foldint(&c, op, i1->cls, &c1, &c2))
+        return;
+
+    // Revert to sub.
+    if (op == Oadd && c.type == Con::CBits &&
+        ((i1->cls == Kl && c.bits.i < 0) ||
+         (i1->cls == Kw && static_cast<int32_t>(c.bits.i) < 0))) {
+        int fail = negcon(i1->cls, &c);
+        assert(fail == 0);
+        (void)fail;
+        op = Osub;
+    }
+
+    i1->op = static_cast<uint>(op);
+    i1->arg[0] = i2->arg[0];
+    i1->arg[1] = newcon(ctx, &c, fn);
+    adduse_ins(ctx, &fn->tmp[i1->arg[0].val], b, i1);
+}
+
+// Deduplication.
+void dedupins(Ctx* ctx, Fn* fn, Blk* b, Ins* i) {
+    normins(ctx, fn, i);
+    if (i->op == Onop || pinned(i))
+        return;
+    // sel skip.
+    assert(i->op != Osel0);
+    assert(!req(i->to, Ref::none()));
+    assoccon(ctx, fn, b, i);
+
+    Ref r = copyref(ctx, fn, b, i);
+    if (!req(r, Ref::none())) {
+        killins(ctx, fn, i, r);
+        return;
+    }
+    r = foldref(ctx, fn, i);
+    if (!req(r, Ref::none())) {
+        killins(ctx, fn, i, r);
+        return;
+    }
+    Ins* i1 = gvndup(ctx, i, 1);
+    if (i1)
+        killins(ctx, fn, i, i1->to);
+}
+
+// jnz simplification.
+
+// Check cmp eq/ne 0.
+int cmpeqz(Fn* fn, Ref r, Ref* arg, int* cls, int* eqval) {
+    if (rtype(r) != RTmp)
+        return 0;
+    Ins* i = fn->tmp[r.val].def;
+    if (i && optab[i->op].cmpeqwl && req(i->arg[1], Ref::con_z())) {
+        *arg = i->arg[0];
+        *cls = argcls(i, 0);
+        *eqval = optab[i->op].eqval;
+        return 1;
+    }
+    return 0;
+}
+
+// Check branch dominance.
+int branchdom(Fn* fn, Blk* bif, Blk* bbr1, Blk* bbr2, Blk* b) {
+    assert(bif->jmp.type == Jjnz);
+    return b != bif && dom(bbr1, b) && !reachesnotvia(fn, bbr2, b, bif);
+}
+
+// Check 0-branch.
+int domzero(Fn* fn, Blk* d, Blk* b, int* z) {
+    if (branchdom(fn, d, d->s1, d->s2, b)) {
+        *z = 0;
+        return 1;
+    }
+    if (branchdom(fn, d, d->s2, d->s1, b)) {
+        *z = 1;
+        return 1;
+    }
+    return 0;
+}
+
+// Actual width class.
+int usecls(Use* u, Ref r, int cls) {
+    switch (u->type) {
+        case Use::UIns: {
+            int k = Kx;  // widest
+            if (req(u->u.ins->arg[0], r))
+                k = argcls(u->u.ins, 0);
+            if (req(u->u.ins->arg[1], r) && (k == Kx || !KWIDE(k)))
+                k = argcls(u->u.ins, 1);
+            return k == Kx ? cls : k;
+        }
+        case Use::UPhi:
+            if (req(u->u.phi->to, Ref::none()))
+                return cls;  // eliminated
+            return u->u.phi->cls;
+        case Use::UJmp:
+            return Kw;
+        default:
+            break;
+    }
+    die("unreachable");
+}
+
+// Replace with 0.
+void propjnz0(Ctx* ctx, Fn* fn, Blk* bif, Blk* s0, Blk* snon0, Ref r, int cls) {
+    if (s0->npred != 1 || rtype(r) != RTmp)
+        return;
+    Tmp* t = &fn->tmp[r.val];
+    for (Use* u = t->use; u < &t->use[t->nuse]; ++u) {
+        Blk* b = fn->rpo[u->bid];
+        // Match width.
+        if (usecls(u, r, cls) == cls && branchdom(fn, bif, s0, snon0, b))
+            replaceuse(ctx, fn, u, r, Ref::con_z());
+    }
+}
+
+void dedupjmp(Ctx* ctx, Fn* fn, Blk* b) {
+    if (b->jmp.type != Jjnz)
+        return;
+
+    // Propagate jmp arg.
+    propjnz0(ctx, fn, b, b->s2, b->s1, b->jmp.arg, Kw);
+    // Propagate underlying arg.
+    Ref arg;
+    int cls, eqval;
+    if (cmpeqz(fn, b->jmp.arg, &arg, &cls, &eqval)) {
+        Blk* ps[2] = {b->s1, b->s2};
+        propjnz0(ctx, fn, b, ps[eqval ^ 1], ps[eqval], arg, cls);
+    }
+
+    // Collapse jnz.
+    int64_t v = 1;
+    int z = 0;
+    if (b->s1 == b->s2 || isconbits(fn, b->jmp.arg, &v) || zeroval(fn, b, b->jmp.arg, Kw, &z)) {
+        if (v == 0 || z)
+            b->s1 = b->s2;
+        b->s2 = nullptr;  // Dead branch live instructions are rescued later in rebuildcfg
+        b->jmp.type = Jjmp;
+        b->jmp.arg = Ref::none();
+    }
+}
+
+// Rebuild CFG.
+
+void rebuildcfg(Ctx* ctx, Fn* fn) {
+    uint nblk = fn->nblk;
+    Blk** rpo = static_cast<Blk**>(emalloc(nblk * sizeof rpo[0]));
+    memcpy(rpo, fn->rpo, nblk * sizeof rpo[0]);
+
+    fillcfg(ctx, fn);  // Dead blocks are marked with id == ~0u here
+
+    Blk* s = fn->start;
+    for (uint n = 0; n < nblk; ++n) {
+        Blk* b = rpo[n];
+        if (b->id != ~0u)
+            continue;  // Still reachable after GVN, skip
+        assert(b != s);
+        for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i)
+            if (!optab[i->op].pinned && gvndup(ctx, i, 0) == i)
+                addins(ctx, &s->ins, &s->nins, i);
+    }
+    free(rpo);
+}
+
+}  // namespace
+
+// zeroval infer.
+int zeroval(Fn* fn, Blk* b, Ref r, int cls, int* z) {
+    Ref arg;
+    int cls1, eqval;
+    for (Blk* d = b->idom; d; d = d->idom) {
+        if (d->jmp.type != Jjnz)
+            continue;
+        if (req(r, d->jmp.arg) && cls == Kw && domzero(fn, d, b, z))
+            return 1;
+        if (cmpeqz(fn, d->jmp.arg, &arg, &cls1, &eqval) && req(r, arg) && cls == cls1 &&
+            domzero(fn, d, b, z)) {
+            *z ^= eqval;
+            return 1;
+        }
+    }
+    return 0;
+}
+
+// gvn entry.
+void gvn(Ctx* ctx, Fn* fn) {
+    ctx->gvn_con01[0] = getcon(ctx, 0, fn);
+    ctx->gvn_con01[1] = getcon(ctx, 1, fn);
+
+    // Zero out width memo.
+    for (Blk* b = fn->start; b; b = b->link)
+        for (Phi* p = b->phi; p; p = p->link)
+            p->visit = 0;
+
+    fillloop(fn);
+    narrowpars(ctx, fn);
+    filluse(ctx, fn);
+    ssacheck(fn);
+
+    uint nins = 0;
+    for (Blk* b = fn->start; b; b = b->link) {
+        b->visit = 0;
+        nins += b->nins;
+    }
+
+    ctx->gvn_tbln = nins + nins / 2;
+    ctx->gvn_tbl = static_cast<Ins**>(emalloc(ctx->gvn_tbln * sizeof ctx->gvn_tbl[0]));
+    for (uint n = 0; n < fn->nblk; ++n) {
+        Blk* b = fn->rpo[n];
+        dedupphi(ctx, fn, b);
+        for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i)
+            dedupins(ctx, fn, b, i);
+        dedupjmp(ctx, fn, b);
+    }
+    rebuildcfg(ctx, fn);
+    free(ctx->gvn_tbl);
+    ctx->gvn_tbl = nullptr;
+    ctx->gvn_tbln = 0;
+
+    if (debug['G']) {
+        fprintf(ctx->dbg_buf, "\n> After GVN:\n");
+        printfn(fn, ctx->dbg_buf);
+    }
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/reassoc.cc b/rcc-legacy/src/mid/reassoc.cc
new file mode 100644
index 0000000..91ff747
--- /dev/null
+++ b/rcc-legacy/src/mid/reassoc.cc
@@ -0,0 +1,436 @@
+/* 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 reassoc.cc
+/// @brief Reassociation pass (LLVM rank-based style).
+///
+/// See docs/reassoc.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <cstdio>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+namespace rcc {
+
+namespace {
+
+enum Family { FAdd, FMul, FAnd, FOr, FXor, FNone };
+
+Family family_of(uint op) {
+    switch (op) {
+        case Oadd:
+        case Osub:
+            return FAdd;
+        case Omul:
+            return FMul;
+        case Oand:
+            return FAnd;
+        case Oor:
+            return FOr;
+        case Oxor:
+            return FXor;
+        default:
+            return FNone;
+    }
+}
+
+// Binary op for the family.
+int family_binop(Family f) {
+    switch (f) {
+        case FAdd:
+            return Oadd;
+        case FMul:
+            return Omul;
+        case FAnd:
+            return Oand;
+        case FOr:
+            return Oor;
+        case FXor:
+            return Oxor;
+        default:
+            return Onop;
+    }
+}
+
+struct Leaf {
+    Ref ref;
+    int sign;  // Only meaningful for FAdd, otherwise always +1
+};
+
+struct Reassoc {
+    Ctx* ctx;
+    Fn* fn;
+    std::unordered_set<Ins*> absorbed;
+    std::unordered_map<Ins*, std::vector<Ins>>
+        prelude;  // root ins -> intermediate instructions in chain
+    int n_trees = 0, n_folded = 0, n_addsub = 0, n_chainmax = 0;
+
+    bool is_family_node(Ins* d, Family fam, int cls) {
+        return d && family_of(d->op) == fam && static_cast<int>(d->cls) == cls;
+    }
+
+    int64_t mask_val(int cls, int64_t v) {
+        return (cls == Kw) ? static_cast<int64_t>(static_cast<int32_t>(v)) : v;
+    }
+
+    // Flatten nodes.
+    void collect(Ins* root, Family fam, int cls, std::vector<Leaf>& out) {
+        std::vector<Leaf> stk;
+        if (fam == FAdd) {
+            stk.push_back({root->arg[0], +1});
+            stk.push_back({root->arg[1], (root->op == Osub) ? -1 : +1});
+        } else {
+            stk.push_back({root->arg[0], +1});
+            stk.push_back({root->arg[1], +1});
+        }
+        while (!stk.empty()) {
+            Leaf cur = stk.back();
+            stk.pop_back();
+            if (rtype(cur.ref) == RTmp && cur.ref.val != 0) {
+                Tmp* t = &fn->tmp[cur.ref.val];
+                Ins* d = t->def;
+                if (d && t->nuse == 1 && is_family_node(d, fam, cls) && !absorbed.count(d)) {
+                    absorbed.insert(d);
+                    if (fam == FAdd) {
+                        stk.push_back({d->arg[0], cur.sign});
+                        stk.push_back({d->arg[1], (d->op == Osub) ? -cur.sign : cur.sign});
+                    } else {
+                        stk.push_back({d->arg[0], cur.sign});
+                        stk.push_back({d->arg[1], cur.sign});
+                    }
+                    continue;
+                }
+            }
+            out.push_back(cur);
+        }
+    }
+
+    // rank nodes.
+    static uint64_t rank_of(Ref r) {
+        if (rtype(r) == RCon)
+            return (static_cast<uint64_t>(UINT32_MAX) << 32) | r.val;
+        return (static_cast<uint64_t>(r.val) << 32) | r.val;
+    }
+
+    void sort_terms(std::vector<Leaf>& v) {
+        std::sort(v.begin(), v.end(),
+                  [](const Leaf& a, const Leaf& b) { return rank_of(a.ref) < rank_of(b.ref); });
+    }
+
+    // Build left-leaning chain.
+    Ref build_full(const std::vector<Ref>& refs, int bop, int cls, std::vector<Ins>& pre) {
+        Ref acc = refs[0];
+        for (size_t k = 1; k < refs.size(); k++) {
+            Ref t = newtmp(ctx, "rea", cls, fn);
+            Ins ni;
+            ni.op = static_cast<uint>(bop);
+            ni.cls = static_cast<uint>(cls);
+            ni.to = t;
+            ni.arg[0] = acc;
+            ni.arg[1] = refs[k];
+            pre.push_back(ni);
+            acc = t;
+        }
+        return acc;
+    }
+
+    void make_copy(Ins* root, Ref r) {
+        root->op = Ocopy;
+        root->arg[0] = r;
+        root->arg[1] = Ref::none();
+    }
+
+    void make_bin(Ins* root, int op, Ref a0, Ref a1) {
+        root->op = static_cast<uint>(op);
+        root->arg[0] = a0;
+        root->arg[1] = a1;
+    }
+
+    // Add/Sub Reconstruction
+    void rebuild_addsub(Ins* root, int cls, std::vector<Leaf>& leaves) {
+        // Constant folding.
+        int64_t cacc = 0;
+        std::vector<Leaf> terms;
+        int nconst = 0;
+        for (const Leaf& lf : leaves) {
+            int64_t v;
+            if (isconbits(fn, lf.ref, &v)) {
+                cacc += lf.sign * v;
+                nconst++;
+            } else {
+                terms.push_back(lf);
+            }
+        }
+        cacc = mask_val(cls, cacc);
+        if (nconst >= 2)
+            n_folded++;
+
+        sort_terms(terms);
+        // Net sum of signs.
+        std::vector<Leaf> canon;
+        for (size_t k = 0; k < terms.size();) {
+            size_t j = k;
+            int64_t net = 0;
+            while (j < terms.size() && req(terms[j].ref, terms[k].ref)) {
+                net += terms[j].sign;
+                j++;
+            }
+            int s = (net > 0) ? +1 : -1;
+            for (int64_t c = 0; c < (net < 0 ? -net : net); c++)
+                canon.push_back({terms[k].ref, s});
+            k = j;
+        }
+
+        // Merge constants.
+        std::vector<Ref> pos, neg;
+        for (const Leaf& lf : canon) {
+            if (lf.sign > 0)
+                pos.push_back(lf.ref);
+            else
+                neg.push_back(lf.ref);
+        }
+        if (cacc != 0)
+            pos.push_back(getcon(ctx, cacc, fn));
+
+        n_addsub++;
+
+        if (pos.empty() && neg.empty()) {
+            make_copy(root, getcon(ctx, cacc, fn));  // cacc==0 here -> copy 0
+            return;
+        }
+        std::vector<Ins>& pre = prelude[root];
+        if (neg.empty()) {
+            if (pos.size() == 1) {
+                make_copy(root, pos[0]);
+            } else {
+                Ref acc = build_full(std::vector<Ref>(pos.begin(), pos.end() - 1), Oadd, cls, pre);
+                make_bin(root, Oadd, acc, pos.back());
+            }
+        } else if (pos.empty()) {
+            Ref negr = build_full(neg, Oadd, cls, pre);
+            make_bin(root, Oneg, negr, Ref::none());
+        } else {
+            Ref posr = build_full(pos, Oadd, cls, pre);
+            Ref negr = build_full(neg, Oadd, cls, pre);
+            make_bin(root, Osub, posr, negr);
+        }
+        size_t len = pos.size() + neg.size();
+        if (static_cast<int>(len) > n_chainmax)
+            n_chainmax = static_cast<int>(len);
+    }
+
+    // Mul/And/Or/Xor Reconstruction
+    void rebuild_logic(Ins* root, Family fam, int cls, std::vector<Leaf>& leaves) {
+        int bop = family_binop(fam);
+        int64_t mask = (cls == Kw) ? 0xffffffffLL : ~0LL;
+        int64_t allones = mask;
+
+        // Identity starting point
+        int64_t acc;
+        switch (fam) {
+            case FMul:
+                acc = 1;
+                break;
+            case FAnd:
+                acc = allones;
+                break;
+            default:
+                acc = 0;  // Or / Xor
+                break;
+        }
+        int nconst = 0;
+        std::vector<Leaf> terms;
+        for (const Leaf& lf : leaves) {
+            int64_t v;
+            if (isconbits(fn, lf.ref, &v)) {
+                nconst++;
+                v &= mask;
+                switch (fam) {
+                    case FMul:
+                        acc *= v;
+                        break;
+                    case FAnd:
+                        acc &= v;
+                        break;
+                    case FOr:
+                        acc |= v;
+                        break;
+                    default:
+                        acc ^= v;
+                        break;
+                }
+            } else {
+                terms.push_back(lf);
+            }
+        }
+        acc &= mask;
+        if (nconst >= 2)
+            n_folded++;
+
+        // Short circuit.
+        if ((fam == FMul && acc == 0 && nconst > 0) || (fam == FAnd && acc == 0 && nconst > 0)) {
+            make_copy(root, getcon(ctx, 0, fn));
+            return;
+        }
+        if (fam == FOr && acc == allones && nconst > 0) {
+            make_copy(root, getcon(ctx, mask_val(cls, allones), fn));
+            return;
+        }
+
+        sort_terms(terms);
+        // Cancellation.
+        std::vector<Ref> refs;
+        if (fam == FAnd || fam == FOr) {
+            for (size_t k = 0; k < terms.size(); k++)
+                if (k == 0 || !req(terms[k].ref, terms[k - 1].ref))
+                    refs.push_back(terms[k].ref);
+        } else if (fam == FXor) {
+            for (size_t k = 0; k < terms.size();) {
+                size_t j = k;
+                while (j < terms.size() && req(terms[j].ref, terms[k].ref))
+                    j++;
+                if ((j - k) & 1)
+                    refs.push_back(terms[k].ref);
+                k = j;
+            }
+        } else {
+            for (const Leaf& lf : terms)
+                refs.push_back(lf.ref);
+        }
+
+        // Whether to merge constant: only add if not identity.
+        bool const_is_id = (fam == FMul && acc == 1) || (fam == FAnd && acc == allones) ||
+                           ((fam == FOr || fam == FXor) && acc == 0);
+        if (!const_is_id || refs.empty())
+            refs.push_back(getcon(ctx, mask_val(cls, acc), fn));
+
+        if (refs.size() == 1) {
+            make_copy(root, refs[0]);
+        } else {
+            std::vector<Ins>& pre = prelude[root];
+            Ref acc_ref = build_full(std::vector<Ref>(refs.begin(), refs.end() - 1), bop, cls, pre);
+            make_bin(root, bop, acc_ref, refs.back());
+        }
+        if (static_cast<int>(refs.size()) > n_chainmax)
+            n_chainmax = static_cast<int>(refs.size());
+    }
+
+    void process_root(Ins* root) {
+        Family fam = family_of(root->op);
+        int cls = static_cast<int>(root->cls);
+        size_t before = absorbed.size();
+        std::vector<Leaf> leaves;
+        collect(root, fam, cls, leaves);
+        size_t delta = absorbed.size() - before;
+
+        // Act on trees.
+        int nconst = 0;
+        for (const Leaf& lf : leaves) {
+            int64_t v;
+            if (isconbits(fn, lf.ref, &v))
+                nconst++;
+        }
+        if (delta == 0 && nconst < 2)
+            return;
+
+        n_trees++;
+        if (fam == FAdd)
+            rebuild_addsub(root, cls, leaves);
+        else
+            rebuild_logic(root, fam, cls, leaves);
+    }
+
+    void run() {
+        // Collect root candidates.
+        std::vector<Ins*> roots;
+        for (Blk* b = fn->start; b; b = b->link) {
+            for (uint k = 0; k < b->nins; k++) {
+                Ins* i = &b->ins[k];
+                if (rtype(i->to) != RTmp)
+                    continue;
+                Family fam = family_of(i->op);
+                if (fam == FNone)
+                    continue;
+                if (KBASE(i->cls) != 0)
+                    continue;  // integer only
+                // Check root.
+                Tmp* t = &fn->tmp[i->to.val];
+                if (t->nuse == 1 && t->use && t->use[0].type == Use::UIns) {
+                    Ins* parent = t->use[0].u.ins;
+                    if (is_family_node(parent, fam, static_cast<int>(i->cls)))
+                        continue;
+                }
+                roots.push_back(i);
+            }
+        }
+
+        // Process each root.
+        for (Ins* r : roots) {
+            if (absorbed.count(r))
+                continue;
+            process_root(r);
+        }
+
+        // Mark absorbed intermediate nodes as Onop.
+        for (Ins* a : absorbed)
+            a->op = Onop;
+
+        // Reconstruct.
+        for (Blk* b = fn->start; b; b = b->link) {
+            Ins* nins = static_cast<Ins*>(vnew(ctx, 0, sizeof(Ins), PFn));
+            uint cnt = 0;
+            for (uint k = 0; k < b->nins; k++) {
+                Ins* i = &b->ins[k];
+                if (i->op == Onop)
+                    continue;
+                auto it = prelude.find(i);
+                if (it != prelude.end())
+                    for (Ins& p : it->second)
+                        addins(ctx, &nins, &cnt, &p);
+                addins(ctx, &nins, &cnt, i);
+            }
+            b->ins = nins;
+            b->nins = cnt;
+        }
+
+        if (debug['E']) {
+            FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr;
+            fprintf(out, "> reassoc %s: trees=%d folded=%d addsub=%d chain_max=%d\n", fn->name,
+                    n_trees, n_folded, n_addsub, n_chainmax);
+        }
+    }
+};
+
+}  // namespace
+
+void reassoc(Ctx* ctx, Fn* fn) {
+    // Pre/post conditions.
+    Reassoc r;
+    r.ctx = ctx;
+    r.fn = fn;
+    r.run();
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/sccp.cc b/rcc-legacy/src/mid/sccp.cc
new file mode 100644
index 0000000..537773a
--- /dev/null
+++ b/rcc-legacy/src/mid/sccp.cc
@@ -0,0 +1,449 @@
+/* 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 sccp.cc
+/// @brief Sparse Conditional Constant Propagation (Wegman-Zadeck).
+///
+/// See docs/sccp.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <cassert>
+#include <cstdio>
+#include <set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+namespace {
+
+enum LatState : uchar { Top = 0, Const = 1, Bot = 2 };
+
+struct Lat {
+    LatState state;
+    Ref con;  // Only valid when state==Const, type==RCon
+};
+
+constexpr Lat kTop = {Top, {RTmp, 0}};
+constexpr Lat kBot = {Bot, {RTmp, 0}};
+
+bool con_eq(Fn* fn, Ref a, Ref b) {
+    if (req(a, b))
+        return true;
+    if (rtype(a) != RCon || rtype(b) != RCon)
+        return false;
+    if (a.val >= static_cast<uint>(fn->ncon) || b.val >= static_cast<uint>(fn->ncon))
+        return false;
+    Con* ca = &fn->con[a.val];
+    Con* cb = &fn->con[b.val];
+    if (ca->type != cb->type)
+        return false;
+    if (ca->type == Con::CAddr && !symeq(ca->sym, cb->sym))
+        return false;
+    return ca->bits.i == cb->bits.i && ca->flt == cb->flt;
+}
+
+bool lat_eq(Fn* fn, Lat a, Lat b) {
+    if (a.state != b.state)
+        return false;
+    if (a.state == Const)
+        return con_eq(fn, a.con, b.con);
+    return true;
+}
+
+// Check if unfoldable type.
+bool op_is_unfoldable(uint op) {
+    if (isstore(op))
+        return true;  // store does not define tmp, but safe
+    if (isload(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;
+    if (op == Onop)
+        return true;
+    return false;
+}
+
+struct Sccp {
+    Ctx* ctx;
+    Fn* fn;
+    std::vector<Lat> lat;             // ntmp
+    std::vector<char> blk_reachable;  // nblk
+    // edge_exec pairs.
+    std::set<std::pair<uint, uint>> edge_exec;
+    std::vector<Blk*> cfg_wl;
+    std::vector<uint> ssa_wl;  // tmp val queue
+
+    Lat arg_lat(Ref r) {
+        if (rtype(r) == RCon)
+            return {Const, r};
+        if (rtype(r) == RTmp) {
+            if (r.val >= lat.size())
+                return kBot;
+            return lat[r.val];
+        }
+        // RSlot / RType / RCall / RMem etc: do not participate in constant propagation
+        return kBot;
+    }
+
+    void set_lat(uint t, Lat nv) {
+        if (t >= lat.size() || t == 0)
+            return;
+        if (lat_eq(fn, lat[t], nv))
+            return;
+        // lattice monotonically descends: Top -> Const -> Bot
+        lat[t] = nv;
+        ssa_wl.push_back(t);
+    }
+
+    // Evaluate instruction using lattice.
+    Lat eval_ins(Ins* i) {
+        if (rtype(i->to) != RTmp)
+            return kBot;
+        if (op_is_unfoldable(i->op))
+            return kBot;
+
+        Lat a0 = arg_lat(i->arg[0]);
+        Lat a1;
+        if (req(i->arg[1], Ref::none()))
+            a1 = {Const, Ref::con_z()};  // phantom arg[1] for unary op
+        else
+            a1 = arg_lat(i->arg[1]);
+
+        // Ocopy special case: lattice equals arg[0]
+        if (i->op == Ocopy)
+            return a0;
+
+        if (a0.state == Top || a1.state == Top)
+            return kTop;
+        if (a0.state == Bot || a1.state == Bot)
+            return kBot;
+
+        // Both sides are Const: try to fold
+        Ins tmp = *i;
+        tmp.arg[0] = a0.con;
+        tmp.arg[1] = a1.con;
+        Ref r = foldref(ctx, fn, &tmp);
+        if (req(r, Ref::none()))
+            return kBot;
+        return {Const, r};
+    }
+
+    Lat eval_phi(Phi* p, Blk* in_blk) {
+        Lat acc = kTop;
+        for (uint k = 0; k < p->narg; k++) {
+            Blk* pred = p->blk[k];
+            if (!pred)
+                continue;
+            if (!edge_exec.count({pred->id, in_blk->id}))
+                continue;  // Incoming edge unreachable - skip
+            Lat a = arg_lat(p->arg[k]);
+            if (a.state == Bot)
+                return kBot;
+            if (a.state == Top)
+                continue;
+            // Const
+            if (acc.state == Top) {
+                acc = a;
+            } else if (!con_eq(fn, acc.con, a.con)) {
+                return kBot;
+            }
+        }
+        return acc;
+    }
+
+    // Activate CFG edge.
+    void activate_edge(Blk* pred, Blk* succ) {
+        if (!succ)
+            return;
+        auto key = std::make_pair(pred->id, succ->id);
+        if (!edge_exec.insert(key).second)
+            return;  // Already activated
+        // Enqueue succ if needed.
+        cfg_wl.push_back(succ);
+        if (!blk_reachable[succ->id])
+            blk_reachable[succ->id] = 1;
+    }
+
+    void eval_jmp(Blk* b) {
+        int t = b->jmp.type;
+        if (isret(t) || t == Jhlt)
+            return;
+        if (t == Jjmp) {
+            activate_edge(b, b->s1);
+            return;
+        }
+        if (INRANGE(t, Jjf, Jjf1)) {
+            // Conditional jumps.
+            activate_edge(b, b->s1);
+            activate_edge(b, b->s2);
+            return;
+        }
+        if (t == Jjnz) {
+            Lat c = arg_lat(b->jmp.arg);
+            if (c.state == Top)
+                return;
+            if (c.state == Bot) {
+                activate_edge(b, b->s1);
+                activate_edge(b, b->s2);
+                return;
+            }
+            // Const: check if non-zero
+            if (rtype(c.con) != RCon || c.con.val >= static_cast<uint>(fn->ncon)) {
+                activate_edge(b, b->s1);
+                activate_edge(b, b->s2);
+                return;
+            }
+            Con* cc = &fn->con[c.con.val];
+            if (cc->type != Con::CBits) {
+                // CAddr is treated as truthy (non-null address)
+                activate_edge(b, b->s1);
+                return;
+            }
+            if (cc->bits.i != 0)
+                activate_edge(b, b->s1);
+            else
+                activate_edge(b, b->s2);
+            return;
+        }
+        // Other unknown jmp types: activate both sides
+        activate_edge(b, b->s1);
+        activate_edge(b, b->s2);
+    }
+
+    void visit_block(Blk* b) {
+        // Re-eval phis.
+        for (Phi* p = b->phi; p; p = p->link) {
+            if (rtype(p->to) != RTmp)
+                continue;
+            Lat nv = eval_phi(p, b);
+            set_lat(p->to.val, nv);
+        }
+        for (uint k = 0; k < b->nins; k++) {
+            Ins* i = &b->ins[k];
+            if (rtype(i->to) != RTmp)
+                continue;
+            Lat nv = eval_ins(i);
+            set_lat(i->to.val, nv);
+        }
+        eval_jmp(b);
+    }
+
+    // Process tmp uses.
+    void visit_uses(uint t) {
+        if (t >= static_cast<uint>(fn->ntmp))
+            return;
+        Tmp* tt = &fn->tmp[t];
+        for (uint u = 0; u < tt->nuse; u++) {
+            Use& uu = tt->use[u];
+            if (uu.bid >= blk_reachable.size())
+                continue;
+            if (!blk_reachable[uu.bid])
+                continue;  // In unreachable block, ignore for now
+            Blk* ub = fn->rpo[uu.bid];
+            if (uu.type == Use::UPhi) {
+                Phi* p = uu.u.phi;
+                if (rtype(p->to) == RTmp) {
+                    Lat nv = eval_phi(p, ub);
+                    set_lat(p->to.val, nv);
+                }
+            } else if (uu.type == Use::UIns) {
+                Ins* i = uu.u.ins;
+                if (rtype(i->to) == RTmp) {
+                    Lat nv = eval_ins(i);
+                    set_lat(i->to.val, nv);
+                }
+            } else if (uu.type == Use::UJmp) {
+                eval_jmp(ub);
+            }
+        }
+    }
+
+    void solve() {
+        // Init state.
+        lat.assign(static_cast<size_t>(fn->ntmp), kTop);
+        blk_reachable.assign(static_cast<size_t>(fn->nblk), 0);
+        edge_exec.clear();
+        cfg_wl.clear();
+        ssa_wl.clear();
+
+        blk_reachable[fn->start->id] = 1;
+        cfg_wl.push_back(fn->start);
+        // Enqueue start.
+
+        while (!cfg_wl.empty() || !ssa_wl.empty()) {
+            // Process worklists.
+            while (!cfg_wl.empty()) {
+                Blk* b = cfg_wl.back();
+                cfg_wl.pop_back();
+                visit_block(b);
+            }
+            while (!ssa_wl.empty()) {
+                uint t = ssa_wl.back();
+                ssa_wl.pop_back();
+                visit_uses(t);
+            }
+        }
+    }
+
+    // Apply: Commit lattice to IR.
+    Ref maybe_const(Ref r) {
+        if (rtype(r) != RTmp)
+            return r;
+        if (r.val >= lat.size())
+            return r;
+        Lat& l = lat[r.val];
+        if (l.state == Const)
+            return l.con;
+        return r;
+    }
+
+    int apply() {
+        int n_ins = 0, n_phi = 0, n_jmp = 0, n_arg = 0;
+        for (Blk* b = fn->start; b; b = b->link) {
+            if (b->id >= blk_reachable.size() || !blk_reachable[b->id])
+                continue;
+
+            // Phi: Remove incoming edges from unreachable preds; replace arg operands
+            for (Phi* p = b->phi; p; p = p->link) {
+                uint w = 0;
+                for (uint k = 0; k < p->narg; k++) {
+                    Blk* pred = p->blk[k];
+                    if (!pred || !edge_exec.count({pred->id, b->id})) {
+                        // This incoming edge was not activated during SCCP -> unreachable -> delete
+                        continue;
+                    }
+                    Ref na = maybe_const(p->arg[k]);
+                    if (!req(na, p->arg[k]))
+                        n_arg++;
+                    if (w != k) {
+                        p->arg[w] = na;
+                        p->blk[w] = pred;
+                    } else {
+                        p->arg[w] = na;
+                    }
+                    w++;
+                }
+                p->narg = w;
+
+                // Keep constant phi.to for DCE.
+                if (rtype(p->to) == RTmp && p->to.val < lat.size() && lat[p->to.val].state == Const)
+                    n_phi++;
+            }
+
+            // Ins: Change Const def to Ocopy; replace arg operands
+            for (uint k = 0; k < b->nins; k++) {
+                Ins* i = &b->ins[k];
+                bool is_const_def = (rtype(i->to) == RTmp && i->to.val < lat.size() &&
+                                     lat[i->to.val].state == Const);
+                if (is_const_def && i->op != Ocopy && !op_is_unfoldable(i->op)) {
+                    Ref cr = lat[i->to.val].con;
+                    i->op = Ocopy;
+                    i->arg[0] = cr;
+                    i->arg[1] = Ref::none();
+                    n_ins++;
+                    continue;
+                }
+                // Otherwise just replace args
+                Ref na0 = maybe_const(i->arg[0]);
+                Ref na1 = maybe_const(i->arg[1]);
+                if (!req(na0, i->arg[0])) {
+                    i->arg[0] = na0;
+                    n_arg++;
+                }
+                if (!req(na1, i->arg[1])) {
+                    i->arg[1] = na1;
+                    n_arg++;
+                }
+            }
+
+            // jmp: Jjnz cond Const -> Jjmp; replace args
+            if (b->jmp.type == Jjnz) {
+                Lat c = arg_lat(b->jmp.arg);
+                if (c.state == Const && rtype(c.con) == RCon &&
+                    c.con.val < static_cast<uint>(fn->ncon)) {
+                    Con* cc = &fn->con[c.con.val];
+                    if (cc->type == Con::CBits) {
+                        // Choose succ
+                        Blk* taken = (cc->bits.i != 0) ? b->s1 : b->s2;
+                        b->jmp.type = Jjmp;
+                        b->jmp.arg = Ref::none();
+                        b->s1 = taken;
+                        b->s2 = nullptr;
+                        n_jmp++;
+                    } else if (cc->type == Con::CAddr) {
+                        // Address is always truthy
+                        b->jmp.type = Jjmp;
+                        b->jmp.arg = Ref::none();
+                        b->s1 = b->s1;
+                        b->s2 = nullptr;
+                        n_jmp++;
+                    }
+                } else {
+                    Ref na = maybe_const(b->jmp.arg);
+                    if (!req(na, b->jmp.arg)) {
+                        b->jmp.arg = na;
+                        n_arg++;
+                    }
+                }
+            } else if (!isret(b->jmp.type) && b->jmp.type != Jhlt && b->jmp.type != Jjmp) {
+                Ref na = maybe_const(b->jmp.arg);
+                if (!req(na, b->jmp.arg)) {
+                    b->jmp.arg = na;
+                    n_arg++;
+                }
+            }
+        }
+
+        if (debug['S']) {
+            FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr;
+            fprintf(out, "> SCCP %s: const_ins=%d const_phi=%d jjnz_collapse=%d arg_subst=%d\n",
+                    fn->name, n_ins, n_phi, n_jmp, n_arg);
+        }
+        return n_ins + n_phi + n_jmp + n_arg;
+    }
+};
+
+}  // namespace
+
+void sccp(Ctx* ctx, Fn* fn) {
+    // Prerequisites: filluse and rpo ready.
+    Sccp s;
+    s.ctx = ctx;
+    s.fn = fn;
+    s.solve();
+    s.apply();
+}
+
+}  // namespace rcc