[legacy/mid] Add memory SSA: construction, promotion, load/store optimization

1 files changed, 512 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/ssa.cc b/rcc-legacy/src/mid/ssa.cc
new file mode 100644
index 0000000..75e2773
--- /dev/null
+++ b/rcc-legacy/src/mid/ssa.cc
@@ -0,0 +1,512 @@
+/* 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 ssa.cc
+/// @brief Use chain population / SSA construction (Cytron-style) / SSA invariant validation.
+///
+/// See docs/ssa.md for architectural notes.
+
+#include "rcc/all.h"
+
+namespace rcc {
+
+// Use chain append
+
+namespace {
+
+inline void use_append(Ctx* ctx, Tmp* tmp, decltype(Use::type) ty, Blk* b, Phi* phi, Ins* ins) {
+    if (!tmp->use)
+        return;
+    uint n = tmp->nuse++;
+    vgrow(ctx, &tmp->use, tmp->nuse);
+    Use* u = &tmp->use[n];
+    u->type = ty;
+    u->bid = b->id;
+    if (ty == Use::UPhi)
+        u->u.phi = phi;
+    else if (ty == Use::UIns)
+        u->u.ins = ins;
+    // UJmp has no extra payload
+}
+
+}  // namespace
+
+void adduse_ins(Ctx* ctx, Tmp* tmp, Blk* b, Ins* ins) {
+    use_append(ctx, tmp, Use::UIns, b, nullptr, ins);
+}
+void adduse_phi(Ctx* ctx, Tmp* tmp, Blk* b, Phi* phi) {
+    use_append(ctx, tmp, Use::UPhi, b, phi, nullptr);
+}
+void adduse_jmp(Ctx* ctx, Tmp* tmp, Blk* b) {
+    use_append(ctx, tmp, Use::UJmp, b, nullptr, nullptr);
+}
+
+// filluse - Recompute def / use / cls / width / phi-equiv-class for each tmp
+
+namespace {
+
+/// Derive width from def instruction op (sub-word width info, for spill storage selection).
+int derive_width(Ins* i) {
+    int op = i->op;
+    if (isparbh(op))
+        return Tmp::Wsb + (op - Oparsb);
+    if (isload(op) && op != Oload)
+        return Tmp::Wsb + (op - Oloadsb);
+    if (isext(op))
+        return Tmp::Wsb + (op - Oextsb);
+    int kx, cx;
+    if (iscmp(op, &kx, &cx))
+        return Tmp::Wub;
+    return Tmp::WFull;
+}
+
+}  // namespace
+
+void filluse(Ctx* ctx, Fn* fn) {
+    Tmp* tmp = fn->tmp;
+
+    // Reset metadata for each user tmp; first call creates empty vnew head for use[].
+    for (int t = Tmp0; t < fn->ntmp; t++) {
+        tmp[t].def = nullptr;
+        tmp[t].bid = ~0u;
+        tmp[t].ndef = 0;
+        tmp[t].nuse = 0;
+        tmp[t].cls = 0;
+        tmp[t].phi = 0;
+        tmp[t].width = Tmp::WFull;
+        if (!tmp[t].use)
+            tmp[t].use = static_cast<Use*>(vnew(ctx, 0, sizeof(Use), PFn));
+    }
+
+    // Iterate blocks, register phi def/use, ins def/use, jmp arg use.
+    for (Blk* b = fn->start; b; b = b->link) {
+        // phi
+        for (Phi* p = b->phi; p; p = p->link) {
+            assert(rtype(p->to) == RTmp);
+            int td = p->to.val;
+            tmp[td].bid = b->id;
+            tmp[td].ndef++;
+            tmp[td].cls = p->cls;
+
+            int td_cls = phicls(td, fn->tmp);
+            for (uint a = 0; a < p->narg; a++) {
+                if (rtype(p->arg[a]) != RTmp)
+                    continue;
+                int ta = p->arg[a].val;
+                adduse_phi(ctx, &tmp[ta], b, p);
+                int ta_cls = phicls(ta, fn->tmp);
+                if (ta_cls != td_cls)
+                    tmp[ta_cls].phi = td_cls;
+            }
+        }
+
+        // Instruction def + double arg use
+        for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) {
+            if (!req(i->to, Ref::none())) {
+                assert(rtype(i->to) == RTmp);
+                int td = i->to.val;
+                int w = derive_width(i);
+                // Under Kw cls, Wsw/Wuw is equivalent to WFull (high bits don't exist anyway)
+                if ((w == Tmp::Wsw || w == Tmp::Wuw) && i->cls == Kw)
+                    w = Tmp::WFull;
+                tmp[td].width = static_cast<decltype(tmp[td].width)>(w);
+                tmp[td].def = i;
+                tmp[td].bid = b->id;
+                tmp[td].ndef++;
+                tmp[td].cls = static_cast<short>(i->cls);
+            }
+            for (int m = 0; m < 2; m++) {
+                if (rtype(i->arg[m]) != RTmp)
+                    continue;
+                int ta = i->arg[m].val;
+                adduse_ins(ctx, &tmp[ta], b, i);
+            }
+        }
+
+        // Terminating jump arg
+        if (rtype(b->jmp.arg) == RTmp)
+            adduse_jmp(ctx, &tmp[b->jmp.arg.val], b);
+    }
+}
+
+// Name Pool - per-Ctx, emalloc nodes reused across fn, drained at ~Ctx
+
+struct Name {
+    Ref r;
+    Blk* b;
+    Name* up;
+};
+
+namespace {
+
+Name* nnew(Ctx* ctx, Ref r, Blk* b, Name* up) {
+    Name* n;
+    if (ctx->ssa_namel) {
+        n = ctx->ssa_namel;
+        ctx->ssa_namel = n->up;
+    } else {
+        // Reused across fn, so not in SubPool (SubPool frees with fn, list would dangle)
+        n = static_cast<Name*>(emalloc(sizeof(Name)));
+    }
+    n->r = r;
+    n->b = b;
+    n->up = up;
+    return n;
+}
+
+void nfree(Ctx* ctx, Name* n) {
+    n->up = ctx->ssa_namel;
+    ctx->ssa_namel = n;
+}
+
+}  // namespace
+
+void ssa_drain_namel(Ctx* ctx) {
+    Name* n = ctx->ssa_namel;
+    while (n) {
+        Name* nxt = n->up;
+        free(n);
+        n = nxt;
+    }
+    ctx->ssa_namel = nullptr;
+}
+
+// Rename helpers: rendef registers new def, getstk queries currently visible name, renblk DFS along
+// dom tree
+
+namespace {
+
+Ref fresh_rename(Ctx* ctx, int t, Fn* fn) {
+    return newtmp(ctx, fn->tmp[t].name, fn->tmp[t].cls, fn);
+}
+
+inline bool needs_rename(Fn* fn, int t) {
+    return fn->tmp[t].visit != 0;
+}
+
+/// Change a def to a fresh name.
+void rendef(Ctx* ctx, Ref* r, Blk* b, Name** stk, Fn* fn) {
+    if (req(*r, Ref::none()))
+        return;
+    int t = r->val;
+    if (!needs_rename(fn, t))
+        return;
+    Ref r1 = fresh_rename(ctx, t, fn);
+    fn->tmp[r1.val].visit = t;  // Record "this fresh name originates from original tmp t"
+    stk[t] = nnew(ctx, r1, b, stk[t]);
+    *r = r1;
+}
+
+/// Query currently visible name of tmp t at b.
+Ref getstk(Ctx* ctx, int t, Blk* b, Name** stk) {
+    Name* n = stk[t];
+    while (n && !dom(n->b, b)) {
+        Name* dead = n;
+        n = n->up;
+        nfree(ctx, dead);
+    }
+    stk[t] = n;
+    return n ? n->r : Ref::undef();
+}
+
+void renblk(Ctx* ctx, Blk* b, Name** stk, Fn* fn) {
+    // Rename phi-def
+    for (Phi* p = b->phi; p; p = p->link)
+        rendef(ctx, &p->to, b, stk, fn);
+
+    // Instructions: rename args first (read old -> write new), then rendef def
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) {
+        for (int m = 0; m < 2; m++) {
+            if (rtype(i->arg[m]) != RTmp)
+                continue;
+            int t = i->arg[m].val;
+            if (needs_rename(fn, t))
+                i->arg[m] = getstk(ctx, t, b, stk);
+        }
+        rendef(ctx, &i->to, b, stk, fn);
+    }
+
+    // jmp arg
+    if (rtype(b->jmp.arg) == RTmp) {
+        int t = b->jmp.arg.val;
+        if (needs_rename(fn, t))
+            b->jmp.arg = getstk(ctx, t, b, stk);
+    }
+
+    // Append arg from this block to phi of each successor s
+    Blk* succs[2] = {b->s1, (b->s2 == b->s1) ? nullptr : b->s2};
+    for (Blk* s : succs) {
+        if (!s)
+            continue;
+        for (Phi* p = s->phi; p; p = p->link) {
+            int orig_t = p->to.val;
+            int src_t = fn->tmp[orig_t].visit;  // phi.to was inserted by phiins, visit=source tmp
+            if (!src_t)
+                continue;
+            uint k = p->narg++;
+            vgrow(ctx, &p->arg, p->narg);
+            vgrow(ctx, &p->blk, p->narg);
+            p->arg[k] = getstk(ctx, src_t, b, stk);
+            p->blk[k] = b;
+        }
+    }
+
+    // Recurse dom-tree children
+    for (Blk* s = b->dom; s; s = s->dlink)
+        renblk(ctx, s, stk, fn);
+}
+
+// phiins - Cytron-style phi insertion
+
+/// Scan all blocks, handle intra-block multi-defs of tmp t.
+short collect_real_defs(Ctx* ctx, Fn* fn, int t, BSet* on_worklist, Blk** be, Blk*** bp_io) {
+    short k = Kx;
+    Ref t_ref = Ref::tmp(static_cast<uint>(t));
+
+    for (Blk* b = fn->start; b; b = b->link) {
+        b->visit = 0;
+        Ref running = Ref::none();
+
+        for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) {
+            // Rewrite uses appearing after running to running name
+            if (!req(running, Ref::none())) {
+                if (req(i->arg[0], t_ref))
+                    i->arg[0] = running;
+                if (req(i->arg[1], t_ref))
+                    i->arg[1] = running;
+            }
+            if (!req(i->to, t_ref))
+                continue;
+
+            if (!bshas(b->out, static_cast<uint>(t))) {
+                // Def that doesn't escape block at the end: fresh naming in-place
+                running = fresh_rename(ctx, t, fn);
+                i->to = running;
+            } else {
+                // Truly escaping def: push b to worklist
+                if (!bshas(on_worklist, b->id)) {
+                    bsset(on_worklist, b->id);
+                    *--(*bp_io) = b;
+                }
+                if (clsmerge(&k, static_cast<short>(i->cls)))
+                    die("ssa: incompatible classes for %%%s", fn->tmp[t].name);
+            }
+        }
+        (void)be;
+
+        // Block tail jmp arg also follows running
+        if (!req(running, Ref::none()) && req(b->jmp.arg, t_ref))
+            b->jmp.arg = running;
+    }
+    return k;
+}
+
+void phiins(Ctx* ctx, Fn* fn) {
+    BSet on_worklist[1], original_defs[1];
+    bsinit(ctx, on_worklist, fn->nblk);
+    bsinit(ctx, original_defs, fn->nblk);
+
+    // worklist is a stack, growing backwards from blist end. bp == be means empty.
+    Blk** blist = static_cast<Blk**>(emalloc(fn->nblk * sizeof(Blk*)));
+    Blk** be = blist + fn->nblk;
+
+    for (int t = Tmp0; t < fn->ntmp; t++) {
+        fn->tmp[t].visit = 0;
+        if (fn->tmp[t].phi != 0)
+            continue;  // Not head of phi-equiv-class, skip (meaning tmp is already handled by its
+                       // representative)
+
+        // Fast path: single def and (def at entry, or all uses in same block as def) -> no phi and
+        // rename needed
+        if (fn->tmp[t].ndef == 1) {
+            bool same = true;
+            uint defb = fn->tmp[t].bid;
+            Use* uses = fn->tmp[t].use;
+            for (uint n = 0; n < fn->tmp[t].nuse; n++)
+                if (uses[n].bid != defb) {
+                    same = false;
+                    break;
+                }
+            if (same || defb == fn->start->id)
+                continue;
+        }
+
+        bszero(on_worklist);
+        Blk** bp = be;
+        short k = collect_real_defs(ctx, fn, t, on_worklist, be, &bp);
+
+        // original_defs is used later to check "did phi block originally have def of t"
+        bscopy(original_defs, on_worklist);
+
+        // Phase 2: IDF main loop
+        while (bp != be) {
+            fn->tmp[t].visit = t;  // Mark: t actually entered renaming
+            Blk* b = *bp++;
+            bsclr(on_worklist, b->id);
+
+            for (uint n = 0; n < b->nfron; n++) {
+                Blk* a = b->fron[n];
+                if (a->visit++ != 0)
+                    continue;  // Already inserted phi for a in this round
+                if (!bshas(a->in, static_cast<uint>(t)))
+                    continue;  // t not live at a entry, no phi needed
+
+                Phi* p = static_cast<Phi*>(alloc(ctx, sizeof(Phi)));
+                memset(p, 0, sizeof(Phi));
+                p->cls = k;
+                p->to = Ref::tmp(static_cast<uint>(t));
+                p->link = a->phi;
+                p->arg = static_cast<Ref*>(vnew(ctx, 0, sizeof(Ref), PFn));
+                p->blk = static_cast<Blk**>(vnew(ctx, 0, sizeof(Blk*), PFn));
+                a->phi = p;
+
+                // a is now also a def block of t (phi form), push a to worklist to continue IDF
+                if (bshas(original_defs, a->id))
+                    continue;
+                if (bshas(on_worklist, a->id))
+                    continue;
+                bsset(on_worklist, a->id);
+                *--bp = a;
+            }
+        }
+    }
+
+    free(blist);
+}
+
+}  // namespace
+
+// ssa() - Main entry: filldom -> fillfron -> filllive -> phiins -> renblk
+
+void ssa(Ctx* ctx, Fn* fn) {
+    // stk[] is allocated by "ntmp before rename".
+    int ntmp0 = fn->ntmp;
+    Name** stk = static_cast<Name**>(emalloc(static_cast<size_t>(ntmp0) * sizeof(Name*)));
+
+    // Internal filllive call in ssa() is only for phiins, avoiding leak to -d L dump
+    int saved_L = debug['L'];
+    debug['L'] = 0;
+
+    filldom(fn);
+
+    if (debug['N']) {
+        FILE* f = ctx->dbg_buf;
+        fprintf(f, "\n> Dominators:\n");
+        for (Blk* bb = fn->start; bb; bb = bb->link) {
+            if (!bb->dom)
+                continue;
+            fprintf(f, "%10s:", bb->name);
+            for (Blk* c = bb->dom; c; c = c->dlink)
+                fprintf(f, " %s", c->name);
+            fputc('\n', f);
+        }
+    }
+
+    fillfron(ctx, fn);
+    filllive(ctx, fn);
+    phiins(ctx, fn);
+    renblk(ctx, fn->start, stk, fn);
+
+    // Reclaim all leftover Names on stk[] to free list (only walking ntmp0 range)
+    for (int t = ntmp0; --t >= 0;) {
+        Name* n = stk[t];
+        while (n) {
+            Name* nx = n->up;
+            nfree(ctx, n);
+            n = nx;
+        }
+    }
+    free(stk);
+
+    debug['L'] = static_cast<char>(saved_L);
+
+    if (debug['N']) {
+        fprintf(ctx->dbg_buf, "\n> After SSA construction:\n");
+        printfn(fn, ctx->dbg_buf);
+    }
+}
+
+// ssacheck - SSA invariant validation
+
+namespace {
+
+bool phi_arg_dominated_by(Phi* p, Blk* def_blk, Ref defref) {
+    for (uint n = 0; n < p->narg; n++) {
+        if (!req(p->arg[n], defref))
+            continue;
+        if (!dom(def_blk, p->blk[n]))
+            return false;
+    }
+    return true;
+}
+
+[[noreturn]] void ssa_err(Tmp* t, Blk* ub) {
+    if (t->visit)
+        die("ssa: %%%s violates SSA invariant", t->name);
+    die("ssa: %%%s used undefined in @%s", t->name, ub->name);
+}
+
+/// Verify all uses of t are dominated by (def_blk, def_ins). def_ins = nullptr means phi-def.
+void verify_uses(Fn* fn, Blk* def_blk, Ins* def_ins, Tmp* t, Ref defref) {
+    for (Use* u = t->use; u < &t->use[t->nuse]; u++) {
+        Blk* ub = fn->rpo[u->bid];
+
+        if (u->type == Use::UPhi) {
+            if (!phi_arg_dominated_by(u->u.phi, def_blk, defref))
+                ssa_err(t, ub);
+            continue;
+        }
+
+        if (ub == def_blk) {
+            // Intra-block: ins-use must be after ins-def (pointer order; valid comparison in same
+            // b->ins array)
+            if (def_ins && u->type == Use::UIns && u->u.ins <= def_ins)
+                ssa_err(t, ub);
+            // UJmp is at block end, definitely after def; no extra check needed
+        } else {
+            if (!sdom(def_blk, ub))
+                ssa_err(t, ub);
+        }
+    }
+}
+
+}  // namespace
+
+void ssacheck(Fn* fn) {
+    // Global check: each tmp <=1 def; use must have def
+    for (Tmp* t = &fn->tmp[Tmp0]; t - fn->tmp < fn->ntmp; t++) {
+        if (t->ndef > 1)
+            die("ssa: temporary %%%s defined more than once", t->name);
+        if (t->nuse > 0 && t->ndef == 0)
+            ssa_err(t, fn->rpo[t->use[0].bid]);
+    }
+
+    // Each def's use must be dominated by it
+    for (Blk* b = fn->start; b; b = b->link) {
+        for (Phi* p = b->phi; p; p = p->link)
+            verify_uses(fn, b, nullptr, &fn->tmp[p->to.val], p->to);
+        for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) {
+            if (rtype(i->to) != RTmp)
+                continue;
+            verify_uses(fn, b, i, &fn->tmp[i->to.val], i->to);
+        }
+    }
+}
+
+}  // namespace rcc