[legacy/mid] Add analysis passes: CFG, dominance, liveness, loops, alias

4 files changed, 1451 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/alias.cc b/rcc-legacy/src/mid/alias.cc
new file mode 100644
index 0000000..8dc6041
--- /dev/null
+++ b/rcc-legacy/src/mid/alias.cc
@@ -0,0 +1,445 @@
+/* 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 alias.cc
+/// @brief Alias analysis: computes a conservative Alias descriptor for each tmp, serving downstream
+/// load/mem optimizations.
+///
+/// See docs/alias.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <cstring>
+
+namespace rcc {
+
+void getalias(Alias* a, Ref r, Fn* fn) {
+    switch (rtype(r)) {
+        case RTmp:
+            *a = fn->tmp[r.val].alias;
+            // astack: follow to root slot to get latest type (slot might have been upgraded to AEsc
+            // by esc())
+            if (astack(a->type))
+                a->type = a->slot->type;
+            assert(a->type != Alias::ABot);
+            return;
+        case RCon: {
+            Con* c = &fn->con[r.val];
+            if (c->type == Con::CAddr) {
+                a->type = Alias::ASym;
+                a->u.sym = c->sym;
+            } else {
+                a->type = Alias::ACon;
+            }
+            a->offset = c->bits.i;
+            a->offset_unknown = false;
+            a->slot = nullptr;
+            a->base = 0;
+            return;
+        }
+        default:
+            die("getalias: unreachable ref kind");
+    }
+}
+
+int alias(Ref p, int op, int sp, Ref q, int sq, int* delta, Fn* fn) {
+    Alias ap, aq;
+    getalias(&ap, p, fn);
+    getalias(&aq, q, fn);
+    ap.offset += op;
+
+    // sp, sq are guaranteed by caller to be <= 2^28, offset difference won't overflow int
+    *delta = static_cast<int>(ap.offset - aq.offset);
+    bool ovlap = ap.offset < aq.offset + sq && aq.offset < ap.offset + sp;
+    // When offset_unknown, overlap is untrustworthy, all "same base + overlap" judgements must
+    // degrade
+    bool ovlap_known = !ap.offset_unknown && !aq.offset_unknown;
+
+    bool p_stack = astack(ap.type);
+    bool q_stack = astack(aq.type);
+
+    if (p_stack && q_stack)
+        return (ap.base == aq.base && ovlap) ? MustAlias : NoAlias;
+
+    if (ap.type == Alias::ASym && aq.type == Alias::ASym) {
+        if (!symeq(ap.u.sym, aq.u.sym))
+            return NoAlias;
+        if (!ovlap_known)
+            return MayAlias;
+        return ovlap ? MustAlias : NoAlias;
+    }
+
+    bool both_con = (ap.type == Alias::ACon && aq.type == Alias::ACon);
+    bool same_base = (ap.type == aq.type && ap.base == aq.base);
+    if (both_con || same_base) {
+        assert(ap.type == Alias::ACon || ap.type == Alias::AUnk);
+        if (!ovlap_known)
+            return MayAlias;
+        return ovlap ? MustAlias : NoAlias;
+    }
+
+    if (ap.type == Alias::AUnk && aq.type != Alias::ALoc)
+        return MayAlias;
+    if (aq.type == Alias::AUnk && ap.type != Alias::ALoc)
+        return MayAlias;
+
+    return NoAlias;
+}
+
+int escapes(Ref r, Fn* fn) {
+    if (rtype(r) != RTmp)
+        return 1;
+    Alias* a = &fn->tmp[r.val].alias;
+    // astack and slot is still ALoc -> didn't escape; otherwise (not astack or slot is AEsc) it
+    // escapes
+    return !astack(a->type) || a->slot->type == Alias::AEsc;
+}
+
+namespace {
+
+void esc(Ref r, Fn* fn) {
+    assert(rtype(r) <= RType);
+    if (rtype(r) != RTmp)
+        return;
+    Alias* a = &fn->tmp[r.val].alias;
+    if (astack(a->type))
+        a->slot->type = Alias::AEsc;
+}
+
+void store(Ref r, int sz, Fn* fn) {
+    if (rtype(r) != RTmp)
+        return;
+    Alias* a = &fn->tmp[r.val].alias;
+    if (!a->slot)
+        return;
+    assert(astack(a->type));
+    int64_t off = a->offset;
+    bits m;
+    if (sz >= static_cast<int>(NBit) || off < 0 || off >= static_cast<int64_t>(NBit))
+        m = static_cast<bits>(-1);
+    else
+        m = (BIT(sz) - 1) << off;
+    a->slot->u.loc.m |= m;
+}
+
+bool getalias_safe(Alias* a, Ref r, Fn* fn) {
+    switch (rtype(r)) {
+        case RTmp:
+            *a = fn->tmp[r.val].alias;
+            if (a->type == Alias::ABot)
+                return false;
+            if (astack(a->type))
+                a->type = a->slot->type;
+            return true;
+        case RCon: {
+            Con* c = &fn->con[r.val];
+            if (c->type == Con::CAddr) {
+                a->type = Alias::ASym;
+                a->u.sym = c->sym;
+            } else {
+                a->type = Alias::ACon;
+            }
+            a->offset = c->bits.i;
+            a->offset_unknown = false;
+            a->slot = nullptr;
+            a->base = 0;
+            return true;
+        }
+        default:
+            die("getalias_safe: unreachable ref kind");
+    }
+}
+
+bool alias_eq(const Alias& a, const Alias& b) {
+    if (a.type != b.type)
+        return false;
+    if (a.offset != b.offset)
+        return false;
+    if (a.offset_unknown != b.offset_unknown)
+        return false;
+    if (a.slot != b.slot)
+        return false;
+    if (a.base != b.base)
+        return false;
+    if (a.type == Alias::ASym) {
+        if (a.u.sym.type != b.u.sym.type)
+            return false;
+        if (a.u.sym.id != b.u.sym.id)
+            return false;
+    } else if (astack(a.type)) {
+        if (a.u.loc.sz != b.u.loc.sz)
+            return false;
+        if (a.u.loc.m != b.u.loc.m)
+            return false;
+    }
+    return true;
+}
+
+bool alias_meet(Alias* a, const Alias& b) {
+    Alias old = *a;
+
+    if (a->type == Alias::ABot) {
+        *a = b;
+    } else if (b.type == Alias::ABot) {
+        // Unchanged
+    } else {
+        // Same type + same identity: offset compatible
+        bool same_id = false;
+        if (a->type == b.type) {
+            if (astack(a->type))
+                same_id = (a->slot == b.slot);
+            else if (a->type == Alias::ASym)
+                same_id = symeq(a->u.sym, b.u.sym);
+            else if (a->type == Alias::ACon)
+                same_id = true;  // ACon has no base/sym, purely based on offset
+            else if (a->type == Alias::AUnk)
+                same_id = (a->base == b.base);
+        }
+        if (same_id) {
+            // ASym path legitimately accepts offset_unknown; ALoc/AEsc do not (store-mask
+            // assumes offset is known), degrade to AUnk on offset mismatch.
+            bool both_offset_known = !a->offset_unknown && !b.offset_unknown;
+            bool offset_match = both_offset_known && a->offset == b.offset;
+            if (astack(a->type) && !offset_match) {
+                a->type = Alias::AUnk;
+                a->slot = nullptr;
+                a->offset = 0;
+                a->offset_unknown = false;
+                // base fixed by caller
+            } else {
+                if (!offset_match)
+                    a->offset_unknown = true;
+            }
+        } else {
+            // Type or identity mismatch -> AUnk
+            a->type = Alias::AUnk;
+            a->slot = nullptr;
+            a->offset = 0;
+            a->offset_unknown = false;
+            // base fixed by caller
+        }
+    }
+
+    return !alias_eq(*a, old);
+}
+
+bool compute_phi(Phi* p, Fn* fn) {
+    assert(rtype(p->to) == RTmp);
+    Alias* a = &fn->tmp[p->to.val].alias;
+    Alias old = *a;
+
+    Alias acc;
+    std::memset(&acc, 0, sizeof acc);
+    acc.type = Alias::ABot;
+
+    for (uint k = 0; k < p->narg; k++) {
+        Alias arg;
+        if (!getalias_safe(&arg, p->arg[k], fn))
+            continue;  // This arg is still ABot, skip and wait for next round
+        alias_meet(&acc, arg);
+    }
+
+    if (acc.type == Alias::ABot) {
+        // All args still ABot: retain ABot, doesn't count as change
+        return false;
+    }
+
+    // If meet degrades to AUnk, set base to phi's own tmp id (uniqueness, avoids sharing base with
+    // other AUnks)
+    if (acc.type == Alias::AUnk)
+        acc.base = p->to.val;
+
+    if (!alias_eq(*a, acc)) {
+        *a = acc;
+        return true;
+    }
+    (void)old;
+    return false;
+}
+
+struct InsResult {
+    bool consumed_next;
+    bool changed;
+};
+
+InsResult process_ins(Ins* i, Ins* end, Fn* fn) {
+    InsResult res{false, false};
+    Alias* a = nullptr;
+    Alias old;
+    bool has_def = !req(i->to, Ref::none());
+
+    if (has_def) {
+        assert(rtype(i->to) == RTmp);
+        a = &fn->tmp[i->to.val].alias;
+        old = *a;
+
+        if (isalloc(i->op)) {
+            // alloc: install only on first time (ABot), afterwards type might upgrade to AEsc via
+            // esc, but slot pointer, loc.sz, loc.m must be preserved (loc.m accumulates with OR
+            // across rounds).
+            if (a->type == Alias::ABot) {
+                a->type = Alias::ALoc;
+                a->slot = a;       // Self reference = this tmp is the root slot
+                a->u.loc.sz = -1;  // Unknown size placeholder
+                a->u.loc.m = 0;
+                if (rtype(i->arg[0]) == RCon) {
+                    Con* c = &fn->con[i->arg[0].val];
+                    int64_t x = c->bits.i;
+                    if (c->type == Con::CBits && 0 <= x && x <= static_cast<int64_t>(NBit))
+                        a->u.loc.sz = static_cast<int>(x);
+                }
+                a->base = i->to.val;
+                a->offset = 0;
+                a->offset_unknown = false;
+            }
+        } else if (i->op == Ocopy || i->op == Oaddr) {
+            // Oaddr passes through alias: IRGen wraps `$sym` as `%t = addr $sym`, here
+            // we must propagate ASym identity from RCon CAddr to %t, otherwise alias() sees
+            // load/store addr as AUnk Tmp, losing "different globals don't alias".
+            Alias src;
+            if (getalias_safe(&src, i->arg[0], fn)) {
+                *a = src;
+            }
+            // src still ABot: don't touch *a, wait for next round
+        } else if (i->op == Oadd) {
+            Alias a0, a1;
+            bool ok0 = getalias_safe(&a0, i->arg[0], fn);
+            bool ok1 = getalias_safe(&a1, i->arg[1], fn);
+            if (ok0 && ok1) {
+                Alias newval;
+                std::memset(&newval, 0, sizeof newval);
+                newval.type = Alias::AUnk;  // Default
+                newval.base = i->to.val;
+
+                if (a0.type == Alias::ACon) {
+                    newval = a1;
+                    newval.offset += a0.offset;
+                } else if (a1.type == Alias::ACon) {
+                    newval = a0;
+                    newval.offset += a1.offset;
+                } else if (a0.type == Alias::ASym) {
+                    newval = a0;
+                    newval.offset_unknown = true;
+                } else if (a1.type == Alias::ASym) {
+                    newval = a1;
+                    newval.offset_unknown = true;
+                }
+                // Both are neither ACon nor ASym -> keep default AUnk
+                *a = newval;
+            }
+            // Any operand still ABot: don't touch *a, wait for next round
+        } else {
+            // Other ops: def is always AUnk, one-time init
+            if (a->type == Alias::ABot) {
+                a->type = Alias::AUnk;
+                a->slot = nullptr;
+                a->base = i->to.val;
+                a->offset = 0;
+                a->offset_unknown = false;
+            }
+        }
+
+        if (!alias_eq(*a, old))
+            res.changed = true;
+    }
+
+    // 3. esc mark: when no def or def is already AUnk, arg is treated as escaping local
+    // abstraction.
+    //    Skip on ABot -- def undetermined, decide next round.
+    //    Multiple iterations: esc is monotonically accumulated (slot type one-way ALoc->AEsc),
+    //    idempotent.
+    bool def_known_unk = has_def && a->type == Alias::AUnk;
+    if (!has_def || def_known_unk) {
+        if (i->op != Oblit0) {
+            if (!isload(i->op))
+                esc(i->arg[0], fn);
+            if (!isstore(i->op) && i->op != Oargc)
+                esc(i->arg[1], fn);
+        }
+    }
+
+    // 4. Memory write accounting: Oblit0/Oblit1 pair / normal store (multiple rounds OR accumulate
+    // idempotent)
+    if (i->op == Oblit0) {
+        Ins* i1 = i + 1;
+        assert(i1 < end && i1->op == Oblit1);
+        (void)end;
+        assert(rtype(i1->arg[0]) == RInt);
+        int sz = std::abs(rsval(i1->arg[0]));
+        store(i->arg[1], sz, fn);
+        res.consumed_next = true;
+    }
+    if (isstore(i->op))
+        store(i->arg[1], storesz(i), fn);
+
+    return res;
+}
+
+void escape_phi_args(Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link)
+        for (Phi* p = b->phi; p; p = p->link)
+            for (uint n = 0; n < p->narg; n++)
+                esc(p->arg[n], fn);
+}
+
+}  // namespace
+
+void fillalias(Fn* fn) {
+    for (int t = 0; t < fn->ntmp; t++) {
+        std::memset(&fn->tmp[t].alias, 0, sizeof(Alias));
+        fn->tmp[t].alias.type = Alias::ABot;
+    }
+
+    int iter = 0;
+    bool changed = true;
+    for (; iter < 16 && changed; ++iter) {
+        changed = false;
+        for (uint n = 0; n < fn->nblk; ++n) {
+            Blk* b = fn->rpo[n];
+            for (Phi* p = b->phi; p; p = p->link)
+                if (compute_phi(p, fn))
+                    changed = true;
+            for (Ins* i = b->ins; i < &b->ins[b->nins];) {
+                InsResult r = process_ins(i, &b->ins[b->nins], fn);
+                if (r.changed)
+                    changed = true;
+                i += r.consumed_next ? 2 : 1;
+            }
+            // Block tail jump arg considered escaped (Jretc exception: ret-by-copy pointer doesn't
+            // escape). Multiple rounds esc idempotent.
+            if (b->jmp.type != Jretc)
+                esc(b->jmp.arg, fn);
+        }
+    }
+
+    for (int t = 0; t < fn->ntmp; t++) {
+        Alias* a = &fn->tmp[t].alias;
+        if (a->type == Alias::ABot) {
+            a->type = Alias::AUnk;
+            a->base = t;
+            a->offset = 0;
+            a->offset_unknown = false;
+            a->slot = nullptr;
+        }
+    }
+
+    escape_phi_args(fn);
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/cfg.cc b/rcc-legacy/src/mid/cfg.cc
new file mode 100644
index 0000000..e03b1e1
--- /dev/null
+++ b/rcc-legacy/src/mid/cfg.cc
@@ -0,0 +1,582 @@
+/* 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 cfg.cc
+/// @brief CFG structure analysis and simplification passes.
+///
+/// See docs/cfg.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <utility>
+
+namespace rcc {
+
+// Block construction
+
+Blk* newblk(Ctx* ctx) {
+    auto* b = static_cast<Blk*>(alloc(ctx, sizeof(Blk)));
+    memset(b, 0, sizeof *b);
+    b->ins = static_cast<Ins*>(vnew(ctx, 0, sizeof(Ins), PFn));
+    b->pred = static_cast<Blk**>(vnew(ctx, 0, sizeof(Blk*), PFn));
+    return b;
+}
+
+// Reverse Post-Order (RPO) numbering + dead block elimination
+
+namespace {
+
+void post_visit(Blk* b, uint* counter) {
+    if (!b || b->visit)
+        return;
+    b->visit = 1;
+    // Heuristic: recurse outer branch first.
+    Blk* a = b->s1;
+    Blk* c = b->s2;
+    if (a && c && a->loop > c->loop)
+        std::swap(a, c);
+    post_visit(a, counter);
+    post_visit(c, counter);
+    b->id = (*counter)++;
+}
+
+void fillrpo(Ctx* ctx, Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link)
+        b->visit = 0;
+
+    uint cnt = 0;
+    post_visit(fn->start, &cnt);
+    fn->nblk = cnt;
+
+    vensure(ctx, &fn->rpo, fn->nblk, sizeof(Blk*), PFn);
+
+    // Second pass: remove unvisited, invert post-order.
+    Blk** slot = &fn->start;
+    while (Blk* b = *slot) {
+        if (!b->visit) {
+            b->id = ~0u;
+            *slot = b->link;
+        } else {
+            b->id = fn->nblk - 1 - b->id;
+            fn->rpo[b->id] = b;
+            slot = &b->link;
+        }
+    }
+}
+
+}  // namespace
+
+// Predecessor sets
+
+void fillpreds(Ctx* ctx, Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link)
+        b->npred = 0;
+
+    for (Blk* src = fn->start; src; src = src->link) {
+        if (src->s1)
+            src->s1->npred++;
+        if (src->s2 && src->s2 != src->s1)
+            src->s2->npred++;
+    }
+
+    for (Blk* b = fn->start; b; b = b->link) {
+        if (b->npred)
+            vensure(ctx, &b->pred, b->npred, sizeof(Blk*), PFn);
+        b->npred = 0;
+    }
+
+    for (Blk* src = fn->start; src; src = src->link) {
+        if (src->s1)
+            src->s1->pred[src->s1->npred++] = src;
+        if (src->s2 && src->s2 != src->s1)
+            src->s2->pred[src->s2->npred++] = src;
+    }
+}
+
+// phi cleanup.
+
+namespace {
+
+void fixphis(Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link) {
+        for (Phi* p = b->phi; p; p = p->link) {
+            uint keep = 0;
+            for (uint i = 0; i < p->narg; i++) {
+                Blk* src = p->blk[i];
+                if (src->id == ~0u)
+                    continue;
+                if (src->s1 != b && src->s2 != b)
+                    continue;
+                if (keep != i) {
+                    p->blk[keep] = src;
+                    p->arg[keep] = p->arg[i];
+                }
+                keep++;
+            }
+            assert(keep > 0 && "phi has no live incoming edge");
+            p->narg = keep;
+        }
+    }
+}
+
+}  // namespace
+
+void fillcfg(Ctx* ctx, Fn* fn) {
+    fillrpo(ctx, fn);
+    fillpreds(ctx, fn);
+    fixphis(fn);
+}
+
+// Dominator Tree (Cooper-Harvey-Kennedy)
+
+namespace {
+
+/// Walk up idom chain to find the lowest common ancestor of x and y in dom-tree.
+/// Invariant: Larger RPO id means a deeper node in the tree, move the deeper one up by one step
+/// each time.
+Blk* dom_meet(Blk* x, Blk* y) {
+    if (!x)
+        return y;
+    while (x != y) {
+        if (x->id < y->id)
+            std::swap(x, y);
+        x = x->idom;
+        assert(x);
+    }
+    return x;
+}
+
+}  // namespace
+
+void filldom(Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link) {
+        b->idom = nullptr;
+        b->dom = nullptr;
+        b->dlink = nullptr;
+    }
+
+    // Fixpoint iteration.
+    for (bool changed = true; changed;) {
+        changed = false;
+        for (uint i = 1; i < fn->nblk; i++) {
+            Blk* b = fn->rpo[i];
+            Blk* d = nullptr;
+            for (uint k = 0; k < b->npred; k++) {
+                Blk* p = b->pred[k];
+                if (p->idom || p == fn->start)
+                    d = dom_meet(d, p);
+            }
+            if (d != b->idom) {
+                b->idom = d;
+                changed = true;
+            }
+        }
+    }
+
+    // Reverse chain: attach dom-children.
+    for (Blk* b = fn->start; b; b = b->link) {
+        if (Blk* d = b->idom) {
+            assert(d != b);
+            b->dlink = d->dom;
+            d->dom = b;
+        }
+    }
+}
+
+int sdom(Blk* a, Blk* b) {
+    assert(a && b);
+    if (a == b)
+        return 0;
+    while (b->id > a->id)
+        b = b->idom;
+    return a == b;
+}
+
+int dom(Blk* a, Blk* b) {
+    return a == b || sdom(a, b);
+}
+
+// Dominance Frontier
+
+namespace {
+
+void push_fron(Ctx* ctx, Blk* host, Blk* node) {
+    for (uint i = 0; i < host->nfron; i++)
+        if (host->fron[i] == node)
+            return;
+    vensure(ctx, &host->fron, host->nfron + 1, sizeof(Blk*), PFn);
+    host->fron[host->nfron++] = node;
+}
+
+/// For edge (src -> dst): walk up idom chain from src, collect dst into the dominance frontier of
+/// all ancestors that do not strictly dominate dst.
+void contribute_fron(Ctx* ctx, Blk* src, Blk* dst) {
+    for (Blk* a = src; a && !sdom(a, dst); a = a->idom)
+        push_fron(ctx, a, dst);
+}
+
+}  // namespace
+
+void fillfron(Ctx* ctx, Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link)
+        b->nfron = 0;
+    for (Blk* b = fn->start; b; b = b->link) {
+        if (b->s1)
+            contribute_fron(ctx, b, b->s1);
+        if (b->s2)
+            contribute_fron(ctx, b, b->s2);
+    }
+}
+
+// Natural loop identification / Loop weights
+
+namespace {
+
+void mark_loop_body(Blk* hd, Blk* node, void (*cb)(Blk*, Blk*)) {
+    if (node->id < hd->id || node->visit == hd->id)
+        return;
+    node->visit = hd->id;
+    cb(hd, node);
+    for (uint k = 0; k < node->npred; k++)
+        mark_loop_body(hd, node->pred[k], cb);
+}
+
+void loop_x10(Blk* hd, Blk* b) {
+    (void)hd;
+    b->loop *= 10;
+}
+
+}  // namespace
+
+void loopiter(Fn* fn, void (*cb)(Blk*, Blk*)) {
+    for (Blk* b = fn->start; b; b = b->link)
+        b->visit = ~0u;
+    for (uint i = 0; i < fn->nblk; i++) {
+        Blk* hd = fn->rpo[i];
+        for (uint k = 0; k < hd->npred; k++)
+            if (hd->pred[k]->id >= i)
+                mark_loop_body(hd, hd->pred[k], cb);
+    }
+}
+
+void fillloop(Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link)
+        b->loop = 1;
+    loopiter(fn, loop_x10);
+}
+
+// dom-tree depth + lowest common ancestor
+
+void filldepth(Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link)
+        b->depth = -1;
+    fn->start->depth = 0;
+
+    // Walk up idom chain.
+    for (Blk* b = fn->start; b; b = b->link) {
+        if (b->depth != -1)
+            continue;
+        Blk* d = b->idom;
+        int steps = 1;
+        while (d->depth == -1) {
+            d = d->idom;
+            steps++;
+        }
+        steps += d->depth;
+        b->depth = steps;
+        for (Blk* a = b->idom; a->depth == -1; a = a->idom)
+            a->depth = --steps;
+    }
+}
+
+Blk* lca(Blk* a, Blk* b) {
+    if (!a)
+        return b;
+    if (!b)
+        return a;
+    while (a->depth > b->depth)
+        a = a->idom;
+    while (b->depth > a->depth)
+        b = b->idom;
+    while (a != b) {
+        a = a->idom;
+        b = b->idom;
+    }
+    return a;
+}
+
+// simpljmp: fold empty transit blocks.
+
+namespace {
+
+/// Union-find query with path compression: find root along uf[], redirecting each node on the chain
+/// to root.
+Blk* uf_find(Blk** uf, Blk* x) {
+    Blk* root = x;
+    while (uf[root->id])
+        root = uf[root->id];
+    while (uf[x->id] && uf[x->id] != root) {
+        Blk* nxt = uf[x->id];
+        uf[x->id] = root;
+        x = nxt;
+    }
+    return root;
+}
+
+}  // namespace
+
+void simpljmp(Ctx* ctx, Fn* fn) {
+    Blk* exit_blk = newblk(ctx);
+    exit_blk->id = fn->nblk++;
+    exit_blk->jmp.type = Jret0;
+    exit_blk->name = strf(ctx, PFn, "ret");
+
+    Blk** uf = static_cast<Blk**>(emalloc(fn->nblk * sizeof(Blk*)));
+    memset(uf, 0, fn->nblk * sizeof(Blk*));
+
+    for (Blk* b = fn->start; b; b = b->link) {
+        assert(!b->phi && "simpljmp requires phi-free CFG");
+        if (b->jmp.type == Jret0) {
+            b->jmp.type = Jjmp;
+            b->s1 = exit_blk;
+        }
+        if (b->nins == 0 && b->jmp.type == Jjmp) {
+            Blk* r = uf_find(uf, b->s1);
+            if (r != b)
+                uf[b->id] = r;
+        }
+    }
+
+    Blk** tail = &fn->start;
+    for (Blk* b; (b = *tail); tail = &b->link) {
+        if (b->s1)
+            b->s1 = uf_find(uf, b->s1);
+        if (b->s2)
+            b->s2 = uf_find(uf, b->s2);
+        if (b->s1 && b->s1 == b->s2) {
+            b->jmp.type = Jjmp;
+            b->s2 = nullptr;
+        }
+    }
+    *tail = exit_blk;
+
+    free(uf);
+}
+
+// Reachability / if-graph pattern recognition
+
+namespace {
+
+int dfs_can_reach(Blk* from, Blk* to) {
+    if (from == to)
+        return 1;
+    if (!from || from->visit)
+        return 0;
+    from->visit = 1;
+    if (dfs_can_reach(from->s1, to))
+        return 1;
+    if (dfs_can_reach(from->s2, to))
+        return 1;
+    return 0;
+}
+
+}  // namespace
+
+int reaches(Fn* fn, Blk* from, Blk* to) {
+    assert(to);
+    int r = dfs_can_reach(from, to);
+    for (Blk* b = fn->start; b; b = b->link)
+        b->visit = 0;
+    return r;
+}
+
+int reachesnotvia(Fn* fn, Blk* from, Blk* to, Blk* excl) {
+    excl->visit = 1;
+    return reaches(fn, from, to);
+}
+
+int ifgraph(Blk* head, Blk** pthen, Blk** pelse, Blk** pjoin) {
+    if (head->jmp.type != Jjnz)
+        return 0;
+
+    Blk* lo = head->s1;
+    Blk* hi = head->s2;
+    bool swapped = false;
+    if (lo->id > hi->id) {
+        std::swap(lo, hi);
+        swapped = true;
+    }
+    if (lo == hi)
+        return 0;
+    if (lo->jmp.type != Jjmp || lo->npred != 1)
+        return 0;
+
+    Blk** out_then = swapped ? pelse : pthen;
+    Blk** out_else = swapped ? pthen : pelse;
+
+    if (lo->s1 == hi) {
+        // if-then (no else branch: head directly serves as else)
+        if (hi->npred != 2)
+            return 0;
+        *out_then = lo;
+        *out_else = head;
+        *pjoin = hi;
+        return 1;
+    }
+
+    if (hi->jmp.type != Jjmp || hi->npred != 1)
+        return 0;
+    if (lo->s1 != hi->s1 || lo->s1->npred != 2)
+        return 0;
+
+    assert(lo->s1 != head);
+    *out_then = lo;
+    *out_else = hi;
+    *pjoin = lo->s1;
+    return 1;
+}
+
+// simplcfg
+
+namespace {
+
+struct JmpSnap {
+    short type;
+    Ref arg;
+    Blk* s1;
+    Blk* s2;
+};
+
+bool snap_eq(const JmpSnap& a, const JmpSnap& b) {
+    return a.type == b.type && req(a.arg, b.arg) && a.s1 == b.s1 && a.s2 == b.s2;
+}
+
+bool target_phi_free(const JmpSnap& j) {
+    if (j.s1 && j.s1->phi)
+        return false;
+    if (j.s2 && j.s2->phi)
+        return false;
+    return true;
+}
+
+bool block_is_empty(Blk* b) {
+    if (b->phi)
+        return false;
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; i++)
+        if (i->op != Onop && i->op != Odbgloc)
+            return false;
+    return true;
+}
+
+void phi_to_copies(Ctx* ctx, Blk* b) {
+    assert(b->npred == 1);
+    Blk* p = b->pred[0];
+    Ins copy{};
+    copy.op = Ocopy;
+    for (Phi* phi = b->phi; phi; phi = phi->link) {
+        copy.cls = static_cast<uint>(phi->cls);
+        copy.to = phi->to;
+        copy.arg[0] = phiarg(phi, p);
+        copy.arg[1] = Ref::none();
+        addins(ctx, &p->ins, &p->nins, &copy);
+    }
+    b->phi = nullptr;
+}
+
+}  // namespace
+
+void simplcfg(Ctx* ctx, Fn* fn) {
+    if (debug['C']) {
+        fprintf(ctx->dbg_buf, "\n> Before CFG simplification:\n");
+        printfn(fn, ctx->dbg_buf);
+    }
+
+    for (Blk* b = fn->start; b; b = b->link)
+        if (b->npred == 1)
+            phi_to_copies(ctx, b);
+
+    auto* snap = static_cast<JmpSnap*>(emalloc(fn->nblk * sizeof(JmpSnap)));
+    auto* empty = static_cast<bool*>(emalloc(fn->nblk * sizeof(bool)));
+    for (Blk* b = fn->start; b; b = b->link) {
+        snap[b->id] = {b->jmp.type, b->jmp.arg, b->s1, b->s2};
+        empty[b->id] = block_is_empty(b);
+    }
+
+    bool dirty;
+    do {
+        dirty = false;
+        for (Blk* b = fn->start; b; b = b->link) {
+            if (b->id == ~0u)
+                continue;
+            JmpSnap* j = &snap[b->id];
+
+            if (j->type == Jjmp && j->s1->npred == 1) {
+                Blk* s = j->s1;
+                assert(!s->phi);
+                addbins(ctx, &b->ins, &b->nins, s);
+                empty[b->id] = empty[b->id] && empty[s->id];
+
+                JmpSnap* sj = &snap[s->id];
+                Blk* succs[2] = {sj->s1, sj->s2};
+                for (Blk* sb : succs) {
+                    if (!sb)
+                        continue;
+                    for (Phi* p = sb->phi; p; p = p->link) {
+                        uint n = phiargn(p, s);
+                        if (n != ~0u)
+                            p->blk[n] = b;
+                    }
+                }
+
+                s->id = ~0u;
+                *j = *sj;
+                dirty = true;
+            } else if (j->type == Jjnz && empty[j->s1->id] && empty[j->s2->id] &&
+                       snap_eq(snap[j->s1->id], snap[j->s2->id]) &&
+                       target_phi_free(snap[j->s1->id])) {
+                *j = snap[j->s1->id];
+                dirty = true;
+            }
+        }
+    } while (dirty);
+
+    for (Blk* b = fn->start; b; b = b->link) {
+        if (b->id == ~0u)
+            continue;
+        JmpSnap* j = &snap[b->id];
+        b->jmp.type = j->type;
+        b->jmp.arg = j->arg;
+        b->s1 = j->s1;
+        b->s2 = j->s2;
+        assert(!j->s1 || j->s1->id != ~0u);
+        assert(!j->s2 || j->s2->id != ~0u);
+    }
+
+    fillcfg(ctx, fn);
+
+    free(empty);
+    free(snap);
+
+    if (debug['C']) {
+        fprintf(ctx->dbg_buf, "\n> After CFG simplification:\n");
+        printfn(fn, ctx->dbg_buf);
+    }
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/live.cc b/rcc-legacy/src/mid/live.cc
new file mode 100644
index 0000000..ee718ad
--- /dev/null
+++ b/rcc-legacy/src/mid/live.cc
@@ -0,0 +1,198 @@
+/* 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 live.cc
+/// @brief Backward dataflow liveness analysis.
+///
+/// See docs/live.md for architectural notes.
+
+#include "rcc/all.h"
+
+namespace rcc {
+
+void liveon(BSet* v, Blk* b, Blk* s) {
+    bscopy(v, s->in);
+
+    // s's phi-defs.
+    for (Phi* p = s->phi; p; p = p->link)
+        if (rtype(p->to) == RTmp)
+            bsclr(v, p->to.val);
+
+    // phi-arg edge check.
+    for (Phi* p = s->phi; p; p = p->link) {
+        for (uint n = 0; n < p->narg; n++) {
+            if (p->blk[n] != b)
+                continue;
+            if (rtype(p->arg[n]) != RTmp)
+                continue;
+            uint t = p->arg[n].val;
+            bsset(v, t);
+            bsset(b->gen, t);
+        }
+    }
+}
+
+namespace {
+
+/// Add ref (if tmp) to b->gen and b->in; on first entry to b->in, increment live count for its K
+/// bucket.
+inline void use_ref(Ref r, Blk* b, int nlv[2], Tmp* tmp) {
+    if (rtype(r) != RTmp)
+        return;
+    uint t = r.val;
+    bsset(b->gen, t);
+    if (!bshas(b->in, t)) {
+        nlv[KBASE(tmp[t].cls)]++;
+        bsset(b->in, t);
+    }
+}
+
+/// Get maximum of two elements.
+inline int imax(int a, int b) {
+    return a > b ? a : b;
+}
+
+}  // namespace
+
+void filllive(Ctx* ctx, Fn* fn) {
+    BSet prev_out[1];
+    BSet edge_set[1];
+
+    bsinit(ctx, prev_out, static_cast<uint>(fn->ntmp));
+    bsinit(ctx, edge_set, static_cast<uint>(fn->ntmp));
+
+    // Initialize sets.
+    for (Blk* b = fn->start; b; b = b->link) {
+        bsinit(ctx, b->in, static_cast<uint>(fn->ntmp));
+        bsinit(ctx, b->out, static_cast<uint>(fn->ntmp));
+        bsinit(ctx, b->gen, static_cast<uint>(fn->ntmp));
+    }
+
+    // Fixpoint loop.
+    bool changed = true;
+    while (changed) {
+        changed = false;
+
+        // Reverse rpo scan.
+        for (int n = static_cast<int>(fn->nblk) - 1; n >= 0; n--) {
+            Blk* b = fn->rpo[n];
+
+            // Merge successors liveon.
+            bscopy(prev_out, b->out);
+
+            if (b->s1) {
+                liveon(edge_set, b, b->s1);
+                bsunion(b->out, edge_set);
+            }
+            if (b->s2) {
+                liveon(edge_set, b, b->s2);
+                bsunion(b->out, edge_set);
+            }
+            if (!bsequal(b->out, prev_out))
+                changed = true;
+
+            // Initial in.
+            int nlv[2] = {0, 0};
+            b->out->t[0] |= T.rglob;
+            bscopy(b->in, b->out);
+            for (int t = 0; bsiter(b->in, &t); t++)
+                nlv[KBASE(fn->tmp[t].cls)]++;
+
+            // Terminal jump args.
+            if (rtype(b->jmp.arg) == RCall) {
+                assert(static_cast<int>(bscount(b->in)) == T.nrglob && b->in->t[0] == T.rglob);
+                b->in->t[0] |= T.retregs(b->jmp.arg, nlv);
+            } else {
+                use_ref(b->jmp.arg, b, nlv, fn->tmp);
+            }
+            // Fused cmp+jnz check.
+            use_ref(b->jmp.arg2, b, nlv, fn->tmp);
+
+            // Initial nlive.
+            for (int k = 0; k < 2; k++)
+                b->nlive[k] = nlv[k];
+
+            // Reverse scan instructions.
+            for (int idx = static_cast<int>(b->nins) - 1; idx >= 0; idx--) {
+                Ins* i = &b->ins[idx];
+
+                // Post-ABI lowering call.
+                if (i->op == Ocall && rtype(i->arg[1]) == RCall) {
+                    int call_kill[2];
+                    b->in->t[0] &= ~T.retregs(i->arg[1], call_kill);
+                    for (int k = 0; k < 2; k++) {
+                        nlv[k] -= call_kill[k];
+                        // Midpoint call.
+                        nlv[k] += T.nrsave[k];
+                        b->nlive[k] = imax(b->nlive[k], nlv[k]);
+                    }
+                    int call_arg[2];
+                    b->in->t[0] |= T.argregs(i->arg[1], call_arg);
+                    for (int k = 0; k < 2; k++) {
+                        nlv[k] -= T.nrsave[k];
+                        nlv[k] += call_arg[k];
+                    }
+                }
+
+                // def kill.
+                if (!req(i->to, Ref::none())) {
+                    assert(rtype(i->to) == RTmp);
+                    uint t = i->to.val;
+                    if (bshas(b->in, t))
+                        nlv[KBASE(fn->tmp[t].cls)]--;
+                    bsset(b->gen, t);
+                    bsclr(b->in, t);
+                }
+
+                // args gen.
+                for (int k = 0; k < 2; k++) {
+                    Ref a = i->arg[k];
+                    if (rtype(a) == RMem) {
+                        Mem* m = &fn->mem[a.val];
+                        use_ref(m->base, b, nlv, fn->tmp);
+                        use_ref(m->index, b, nlv, fn->tmp);
+                    } else {
+                        use_ref(a, b, nlv, fn->tmp);
+                    }
+                }
+
+                // Update peak.
+                for (int k = 0; k < 2; k++)
+                    b->nlive[k] = imax(b->nlive[k], nlv[k]);
+            }
+        }
+    }
+
+    // Debug dump.
+    if (debug['L']) {
+        FILE* f = ctx->dbg_buf;
+        fprintf(f, "\n> Liveness analysis:\n");
+        for (Blk* b = fn->start; b; b = b->link) {
+            fprintf(f, "\t%-10sin:   ", b->name);
+            dumpts(b->in, fn->tmp, f);
+            fprintf(f, "\t          out:  ");
+            dumpts(b->out, fn->tmp, f);
+            fprintf(f, "\t          gen:  ");
+            dumpts(b->gen, fn->tmp, f);
+            fprintf(f, "\t          live: %d %d\n", b->nlive[0], b->nlive[1]);
+        }
+    }
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/loopinfo.cc b/rcc-legacy/src/mid/loopinfo.cc
new file mode 100644
index 0000000..d6041fc
--- /dev/null
+++ b/rcc-legacy/src/mid/loopinfo.cc
@@ -0,0 +1,226 @@
+/* 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 loopinfo.cc
+/// @brief find_loops + detect_bivs + ref_is_const (shared).
+
+#include "rcc/loopinfo.h"
+
+#include "rcc/all.h"
+
+namespace rcc {
+
+bool ref_is_const(Fn* fn, Ref r, int64_t& out) {
+    if (rtype(r) != RCon)
+        return false;
+    if (r.val >= static_cast<uint>(fn->ncon))
+        return false;
+    Con* c = &fn->con[r.val];
+    if (c->type != Con::CBits || c->flt)
+        return false;
+    out = c->bits.i;
+    return true;
+}
+
+Ins* def_ins(Fn* fn, Ref r) {
+    if (rtype(r) != RTmp || r.val >= static_cast<uint>(fn->ntmp))
+        return nullptr;
+    return fn->tmp[r.val].def;
+}
+
+void find_loops(Fn* fn, std::vector<Loop>& out) {
+    out.clear();
+    for (Blk* b = fn->start; b; b = b->link)
+        b->visit = ~0u;
+
+    for (uint i = 0; i < fn->nblk; i++) {
+        Blk* hd = fn->rpo[i];
+        if (hd->npred != 2)
+            continue;
+
+        Blk* pre = nullptr;
+        Blk* latch = nullptr;
+        for (uint k = 0; k < hd->npred; k++) {
+            Blk* p = hd->pred[k];
+            if (p->id != ~0u && p->id >= hd->id)
+                latch = p;
+            else
+                pre = p;
+        }
+        if (!pre || !latch)
+            continue;
+
+        Loop L;
+        L.header = hd;
+        L.preheader = pre;
+        L.latch = latch;
+        L.body.push_back(hd);
+        L.body_bid.insert(hd->id);
+        hd->visit = hd->id;
+        std::vector<Blk*> stk = {latch};
+        while (!stk.empty()) {
+            Blk* n = stk.back();
+            stk.pop_back();
+            if (n->visit == hd->id)
+                continue;
+            n->visit = hd->id;
+            L.body.push_back(n);
+            L.body_bid.insert(n->id);
+            for (uint k = 0; k < n->npred; k++)
+                stk.push_back(n->pred[k]);
+        }
+        out.push_back(std::move(L));
+    }
+}
+
+void detect_bivs(Fn* fn, const Loop& L, std::vector<Biv>& out) {
+    for (Phi* p = L.header->phi; p; p = p->link) {
+        if (p->narg != 2)
+            continue;
+        Ref init_ref = Ref::none(), next_ref = Ref::none();
+        for (uint k = 0; k < p->narg; k++) {
+            if (p->blk[k] == L.preheader)
+                init_ref = p->arg[k];
+            else if (p->blk[k] == L.latch)
+                next_ref = p->arg[k];
+        }
+        int64_t init_v = 0;
+        if (!ref_is_const(fn, init_ref, init_v))
+            continue;
+        Ins* nx = def_ins(fn, next_ref);
+        if (!nx || nx->op != Oadd)
+            continue;
+        int64_t step_v = 0;
+        if (req(nx->arg[0], p->to) && ref_is_const(fn, nx->arg[1], step_v)) {
+        } else if (req(nx->arg[1], p->to) && ref_is_const(fn, nx->arg[0], step_v)) {
+        } else {
+            continue;
+        }
+        if (step_v == 0)
+            continue;
+        out.push_back({p->to, static_cast<int>(p->cls), init_v, step_v});
+    }
+}
+
+bool pick_pointer_iv(Fn* fn, const Loop& L, Phi* p, PointerIV* out) {
+    if (p->cls != Kl)
+        return false;
+    if (p->narg != 2)
+        return false;
+    Ref base = Ref::none(), next = Ref::none();
+    for (uint k = 0; k < p->narg; k++) {
+        if (p->blk[k] == L.preheader)
+            base = p->arg[k];
+        else if (p->blk[k] == L.latch)
+            next = p->arg[k];
+        else
+            return false;
+    }
+    if (rtype(base) == -1 || rtype(next) == -1)
+        return false;
+    Ins* nx = def_ins(fn, next);
+    if (!nx || nx->op != Oadd)
+        return false;
+    int64_t step = 0;
+    if (req(nx->arg[0], p->to) && ref_is_const(fn, nx->arg[1], step)) {
+    } else if (req(nx->arg[1], p->to) && ref_is_const(fn, nx->arg[0], step)) {
+    } else {
+        return false;
+    }
+    if (step <= 0)
+        return false;
+    out->phi_to = p->to;
+    out->base = base;
+    out->next = next;
+    out->step = step;
+    return true;
+}
+
+bool check_exit_cmp(Fn* fn, const Loop& L, Ref p, Ref* end_out, Blk** after_out) {
+    Blk* hd = L.header;
+    if (hd->jmp.type != Jjnz)
+        return false;
+    Ref cmp_r = hd->jmp.arg;
+    if (rtype(cmp_r) != RTmp)
+        return false;
+    Ins* cmp_def = nullptr;
+    for (uint k = 0; k < hd->nins; k++) {
+        Ins* ii = &hd->ins[k];
+        if (req(ii->to, cmp_r)) {
+            cmp_def = ii;
+            break;
+        }
+    }
+    if (!cmp_def)
+        return false;
+    if (cmp_def->op != Ocultl && cmp_def->op != Ocsltl)
+        return false;
+    if (!req(cmp_def->arg[0], p))
+        return false;
+    Ref end = cmp_def->arg[1];
+    if (rtype(end) == RTmp) {
+        Ins* d = def_ins(fn, end);
+        if (d) {
+            for (Blk* bb : L.body)
+                if (bb->ins <= d && d < bb->ins + bb->nins)
+                    return false;
+        }
+    }
+    Blk* s1 = hd->s1;
+    Blk* s2 = hd->s2;
+    bool s1_in = L.body_bid.count(s1->id) != 0;
+    bool s2_in = L.body_bid.count(s2->id) != 0;
+    if (s1_in == s2_in)
+        return false;
+    *end_out = end;
+    *after_out = s1_in ? s2 : s1;
+    return true;
+}
+
+bool has_outside_use(Fn* fn, const Loop& L) {
+    std::unordered_set<uint> loop_def;
+    for (Blk* bb : L.body) {
+        for (Phi* ph = bb->phi; ph; ph = ph->link)
+            if (rtype(ph->to) == RTmp)
+                loop_def.insert(ph->to.val);
+        for (uint k = 0; k < bb->nins; k++)
+            if (rtype(bb->ins[k].to) == RTmp)
+                loop_def.insert(bb->ins[k].to.val);
+    }
+    for (Blk* b = fn->start; b; b = b->link) {
+        if (L.body_bid.count(b->id))
+            continue;
+        for (Phi* ph = b->phi; ph; ph = ph->link)
+            for (uint k = 0; k < ph->narg; k++)
+                if (rtype(ph->arg[k]) == RTmp && loop_def.count(ph->arg[k].val))
+                    return true;
+        for (uint k = 0; k < b->nins; k++) {
+            Ins* i = &b->ins[k];
+            for (int a = 0; a < 2; a++)
+                if (rtype(i->arg[a]) == RTmp && loop_def.count(i->arg[a].val))
+                    return true;
+        }
+        if (rtype(b->jmp.arg) == RTmp && loop_def.count(b->jmp.arg.val))
+            return true;
+        if (rtype(b->jmp.arg2) == RTmp && loop_def.count(b->jmp.arg2.val))
+            return true;
+    }
+    return false;
+}
+
+}  // namespace rcc