aboutsummaryrefslogtreecommitdiff
path: root/rcc-legacy/src
diff options
context:
space:
mode:
Diffstat (limited to 'rcc-legacy/src')
-rw-r--r--rcc-legacy/src/mid/load.cc556
-rw-r--r--rcc-legacy/src/mid/mem.cc653
-rw-r--r--rcc-legacy/src/mid/ssa.cc512
-rw-r--r--rcc-legacy/src/mid/storemrg.cc231
4 files changed, 1952 insertions, 0 deletions
diff --git a/rcc-legacy/src/mid/load.cc b/rcc-legacy/src/mid/load.cc
new file mode 100644
index 0000000..a26f847
--- /dev/null
+++ b/rcc-legacy/src/mid/load.cc
@@ -0,0 +1,556 @@
+/* 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 load.cc
+/// @brief Load/store meta information + load-forwarding optimization (loadopt).
+///
+/// See docs/load.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <cstdlib>
+
+namespace rcc {
+
+// loadsz / storesz - also used by alias.cc / mem.cc
+
+int loadsz(Ins* l) {
+ switch (l->op) {
+ case Oloadsb:
+ case Oloadub:
+ return 1;
+ case Oloadsh:
+ case Oloaduh:
+ return 2;
+ case Oloadsw:
+ case Oloaduw:
+ return 4;
+ case Oload:
+ return KWIDE(l->cls) ? 8 : 4;
+ }
+ die("loadsz: not a load op");
+}
+
+int storesz(Ins* s) {
+ switch (s->op) {
+ case Ostoreb:
+ return 1;
+ case Ostoreh:
+ return 2;
+ case Ostorew:
+ case Ostores:
+ return 4;
+ case Ostorel:
+ case Ostored:
+ return 8;
+ }
+ die("storesz: not a store op");
+}
+
+namespace {
+
+struct Slice {
+ Ref ref;
+ int off;
+ short sz;
+ short cls;
+};
+
+struct Loc {
+ enum Type { LRoot, LLoad, LNoLoad } type;
+ uint off;
+ Blk* blk;
+};
+
+} // namespace
+
+struct Insert {
+ uint isphi : 1;
+ uint num : 31;
+ uint bid;
+ uint off;
+ Ins ins; // valid when !isphi
+ Slice slice; // valid when isphi
+ Phi* phi_node; // valid when isphi
+};
+
+namespace {
+
+// MASK(w): All-1 mask of width w bytes. Relies on unsigned overflow for w==8.
+inline bits mskbits(int w) {
+ return (BIT(8 * w - 1) << 1) - 1;
+}
+
+// Insert a deferred instruction, returning new tmp
+Ref iins(Ctx* ctx, int cls, int op, Ref a0, Ref a1, Loc* l) {
+ vgrow(ctx, &ctx->load_ilog, ++ctx->load_nlog);
+ Insert* ist = &ctx->load_ilog[ctx->load_nlog - 1];
+ ist->isphi = 0;
+ ist->num = ctx->load_inum++;
+ ist->bid = l->blk->id;
+ ist->off = l->off;
+ Ref to = newtmp(ctx, "ld", cls, ctx->load_curf);
+ ist->ins.op = static_cast<uint>(op);
+ ist->ins.cls = static_cast<uint>(cls);
+ ist->ins.to = to;
+ ist->ins.arg[0] = a0;
+ ist->ins.arg[1] = a1;
+ return to;
+}
+
+// Cast *r to cls, possibly inserting multiple Ocast / Oextuw
+void cast_ref(Ctx* ctx, Ref* r, int cls, Loc* l) {
+ if (rtype(*r) == RCon)
+ return;
+ assert(rtype(*r) == RTmp);
+ int cls0 = ctx->load_curf->tmp[r->val].cls;
+ if (cls0 == cls || (cls == Kw && cls0 == Kl))
+ return;
+ if (KWIDE(cls0) < KWIDE(cls)) {
+ if (cls0 == Ks)
+ *r = iins(ctx, Kw, Ocast, *r, Ref::none(), l);
+ *r = iins(ctx, Kl, Oextuw, *r, Ref::none(), l);
+ if (cls == Kd)
+ *r = iins(ctx, Kd, Ocast, *r, Ref::none(), l);
+ } else {
+ if (cls0 == Kd && cls != Kl)
+ *r = iins(ctx, Kl, Ocast, *r, Ref::none(), l);
+ if (cls0 != Kd || cls != Kw)
+ *r = iins(ctx, cls, Ocast, *r, Ref::none(), l);
+ }
+}
+
+void mask_ref(Ctx* ctx, int cls, Ref* r, bits msk, Loc* l) {
+ cast_ref(ctx, r, cls, l);
+ *r = iins(ctx, cls, Oand, *r, getcon(ctx, static_cast<int64_t>(msk), ctx->load_curf), l);
+}
+
+// emit_load: Insert an actual load (fallback when forwarding fails)
+Ref emit_load(Ctx* ctx, Slice sl, bits msk, Loc* l) {
+ int ld;
+ switch (sl.sz) {
+ case 1:
+ ld = Oloadub;
+ break;
+ case 2:
+ ld = Oloaduh;
+ break;
+ case 4:
+ ld = Oloaduw;
+ break;
+ case 8:
+ ld = Oload;
+ break;
+ default:
+ die("loadopt: emit_load on slice size %d", sl.sz);
+ }
+ bits all_msk = mskbits(sl.sz);
+ bool all = (msk == all_msk);
+ int cls = all ? sl.cls : (sl.sz > 4 ? Kl : Kw);
+
+ Ref r = sl.ref;
+ if (rtype(r) == RTmp) {
+ Alias* a = &ctx->load_curf->tmp[r.val].alias;
+ // offset_unknown aliases will not match via slice - invariant broken if reached
+ assert(!a->offset_unknown);
+ switch (a->type) {
+ case Alias::ALoc:
+ case Alias::AEsc:
+ case Alias::AUnk:
+ r = Ref::tmp(static_cast<uint>(a->base));
+ if (a->offset) {
+ Ref r1 = getcon(ctx, a->offset, ctx->load_curf);
+ r = iins(ctx, Kl, Oadd, r, r1, l);
+ }
+ break;
+ case Alias::ACon:
+ case Alias::ASym: {
+ Con c;
+ memset(&c, 0, sizeof c);
+ c.type = Con::CAddr;
+ c.sym = a->u.sym;
+ c.bits.i = a->offset;
+ r = newcon(ctx, &c, ctx->load_curf);
+ break;
+ }
+ default:
+ die("loadopt: emit_load on alias type %d", a->type);
+ }
+ }
+ r = iins(ctx, cls, ld, r, Ref::none(), l);
+ if (!all)
+ mask_ref(ctx, cls, &r, msk, l);
+ return r;
+}
+
+// rebase: Replace sl.ref with alias base + off
+void rebase(Ctx* ctx, Slice* sl) {
+ if (rtype(sl->ref) != RTmp)
+ return;
+ Alias* a = &ctx->load_curf->tmp[sl->ref.val].alias;
+ // offset_unknown aliases cannot be rebased
+ if (a->offset_unknown)
+ return;
+ if (static_cast<int16_t>(a->offset) != a->offset)
+ return;
+ if (a->type != Alias::ALoc && a->type != Alias::AEsc && a->type != Alias::AUnk)
+ return;
+ sl->ref = Ref::tmp(static_cast<uint>(a->base));
+ sl->off = static_cast<int>(a->offset);
+}
+
+// killsl: whether r is sl's base tmp (only valid for stack type)
+bool killsl(Ctx* ctx, Ref r, Slice sl) {
+ if (rtype(sl.ref) != RTmp)
+ return false;
+ Alias* a = &ctx->load_curf->tmp[sl.ref.val].alias;
+ switch (a->type) {
+ case Alias::ALoc:
+ case Alias::AEsc:
+ case Alias::AUnk:
+ return req(Ref::tmp(static_cast<uint>(a->base)), r);
+ case Alias::ACon:
+ case Alias::ASym:
+ return false;
+ default:
+ die("loadopt: killsl on alias type %d", a->type);
+ }
+}
+
+// qsort comparator: bid asc -> phi before ins -> off asc -> num asc
+int icmp(const void* pa, const void* pb) {
+ const Insert* a = static_cast<const Insert*>(pa);
+ const Insert* b = static_cast<const Insert*>(pb);
+ int c;
+ if ((c = static_cast<int>(a->bid) - static_cast<int>(b->bid)))
+ return c;
+ if (a->isphi && b->isphi)
+ return 0;
+ if (a->isphi)
+ return -1;
+ if (b->isphi)
+ return 1;
+ if ((c = static_cast<int>(a->off) - static_cast<int>(b->off)))
+ return c;
+ return static_cast<int>(a->num) - static_cast<int>(b->num);
+}
+
+Ref def(Ctx* ctx, Slice sl, bits msk, Blk* b, Ins* i, Loc* il);
+
+Ref try_def(Ctx* ctx, Slice sl, bits msk, Blk* b, Ins* i, Loc* il) {
+ // CFG traversal invariants
+ assert(dom(b, il->blk));
+
+ if (!i)
+ i = &b->ins[b->nins];
+ int cls = (sl.sz > 4) ? Kl : Kw;
+ bits msks = mskbits(sl.sz);
+
+ // Scan backward in block
+ while (i > b->ins) {
+ --i;
+ if (killsl(ctx, i->to, sl))
+ return Ref::none();
+ if (i->op == Ocall && escapes(sl.ref, ctx->load_curf))
+ return Ref::none();
+
+ bool is_load = isload(i->op);
+ int sz;
+ Ref r1, r;
+ if (is_load) {
+ sz = loadsz(i);
+ r1 = i->arg[0];
+ r = i->to;
+ } else if (isstore(i->op)) {
+ sz = storesz(i);
+ r1 = i->arg[1];
+ r = i->arg[0];
+ } else if (i->op == Oblit1) {
+ assert(rtype(i->arg[0]) == RInt);
+ sz = std::abs(rsval(i->arg[0]));
+ assert(i > b->ins);
+ --i;
+ assert(i->op == Oblit0);
+ r1 = i->arg[1];
+ r = Ref::none(); // blit does not use r
+ } else {
+ continue;
+ }
+
+ int off;
+ switch (alias(sl.ref, sl.off, sl.sz, r1, sz, &off, ctx->load_curf)) {
+ case MustAlias: {
+ Slice sl1 = sl;
+ if (i->op == Oblit0) {
+ // adjust blit source slice
+ sl1.ref = i->arg[0];
+ if (off >= 0) {
+ assert(off < sz);
+ sl1.off = off;
+ sz -= off;
+ off = 0;
+ } else {
+ sl1.off = 0;
+ sl1.sz = static_cast<short>(sl1.sz + off);
+ }
+ if (sz > sl1.sz)
+ sz = sl1.sz;
+ assert(sz <= 8);
+ sl1.sz = static_cast<short>(sz);
+ }
+
+ bits msk1;
+ int op;
+ if (off < 0) {
+ off = -off;
+ msk1 = (mskbits(sz) << (8 * off)) & msks;
+ op = Oshl;
+ } else {
+ msk1 = (mskbits(sz) >> (8 * off)) & msks;
+ op = Oshr;
+ }
+ if ((msk1 & msk) == 0)
+ continue;
+
+ if (i->op == Oblit0) {
+ r = def(ctx, sl1, mskbits(static_cast<int>(sl1.sz)), b, i, il);
+ if (req(r, Ref::none()))
+ return Ref::none();
+ }
+
+ if (off) {
+ int cls1 = cls;
+ if (op == Oshr && off + sl.sz > 4)
+ cls1 = Kl;
+ cast_ref(ctx, &r, cls1, il);
+ Ref r2 = getcon(ctx, 8 * off, ctx->load_curf);
+ r = iins(ctx, cls1, op, r, r2, il);
+ }
+ if ((msk1 & msk) != msk1 || off + sz < sl.sz)
+ mask_ref(ctx, cls, &r, msk1 & msk, il);
+ if ((msk & ~msk1) != 0) {
+ Ref r2 = def(ctx, sl, msk & ~msk1, b, i, il);
+ if (req(r2, Ref::none()))
+ return Ref::none();
+ r = iins(ctx, cls, Oor, r, r2, il);
+ }
+ if (msk == msks)
+ cast_ref(ctx, &r, sl.cls, il);
+ return r;
+ }
+ case MayAlias:
+ if (is_load)
+ continue;
+ return Ref::none();
+ case NoAlias:
+ continue;
+ default:
+ die("loadopt: alias() returned unexpected value");
+ }
+ }
+
+ // Block head: check if ilog already has a phi for this block and slice
+ for (Insert* ist = ctx->load_ilog; ist < &ctx->load_ilog[ctx->load_nlog]; ++ist) {
+ if (!ist->isphi || ist->bid != b->id)
+ continue;
+ if (!req(ist->slice.ref, sl.ref))
+ continue;
+ if (ist->slice.off != sl.off)
+ continue;
+ if (ist->slice.sz != sl.sz)
+ continue;
+ Ref r = ist->phi_node->to;
+ if (msk != msks)
+ mask_ref(ctx, cls, &r, msk, il);
+ else
+ cast_ref(ctx, &r, sl.cls, il);
+ return r;
+ }
+
+ // Check if real phi kills sl
+ for (Phi* p = b->phi; p; p = p->link)
+ if (killsl(ctx, p->to, sl))
+ return Ref::none();
+
+ // Predecessors
+ if (b->npred == 0)
+ return Ref::none();
+ if (b->npred == 1) {
+ Blk* bp = b->pred[0];
+ assert(bp->loop >= il->blk->loop);
+ Loc l = *il;
+ if (bp->s2)
+ l.type = Loc::LNoLoad;
+ Ref r1 = def(ctx, sl, msk, bp, nullptr, &l);
+ if (req(r1, Ref::none()))
+ return Ref::none();
+ return r1;
+ }
+
+ // Multiple predecessors: insert new phi into log, recurse on predecessors
+ Ref r = newtmp(ctx, "ld", sl.cls, ctx->load_curf);
+ Phi* p = static_cast<Phi*>(alloc(ctx, sizeof(Phi)));
+ memset(p, 0, sizeof *p);
+ vgrow(ctx, &ctx->load_ilog, ++ctx->load_nlog);
+ Insert* ist = &ctx->load_ilog[ctx->load_nlog - 1];
+ ist->isphi = 1;
+ ist->bid = b->id;
+ ist->slice = sl;
+ ist->phi_node = p;
+ p->to = r;
+ p->cls = static_cast<short>(sl.cls);
+ p->narg = b->npred;
+ p->arg = static_cast<Ref*>(vnew(ctx, p->narg, sizeof(Ref), PFn));
+ p->blk = static_cast<Blk**>(vnew(ctx, p->narg, sizeof(Blk*), PFn));
+ for (uint np = 0; np < b->npred; ++np) {
+ Blk* bp = b->pred[np];
+ Loc l;
+ if (!bp->s2 && il->type != Loc::LNoLoad && bp->loop < il->blk->loop)
+ l.type = Loc::LLoad;
+ else
+ l.type = Loc::LNoLoad;
+ l.blk = bp;
+ l.off = bp->nins;
+ Ref r1 = def(ctx, sl, msks, bp, nullptr, &l);
+ if (req(r1, Ref::none()))
+ return Ref::none();
+ p->arg[np] = r1;
+ p->blk[np] = bp;
+ // XXX QBE note "multiplicity in predecessors" - same bp in b->pred multiple times not
+ // handled.
+ }
+ if (msk != msks)
+ mask_ref(ctx, cls, &r, msk, il);
+ return r;
+}
+
+Ref def(Ctx* ctx, Slice sl, bits msk, Blk* b, Ins* i, Loc* il) {
+ uint oldl = ctx->load_nlog;
+ int oldt = ctx->load_curf->ntmp;
+ Ref r = try_def(ctx, sl, msk, b, i, il);
+ if (!req(r, Ref::none()))
+ return r;
+ // Rollback log and fresh tmp (vgrow does not shrink, capacity kept for reuse)
+ ctx->load_nlog = oldl;
+ ctx->load_curf->ntmp = oldt;
+ if (il->type != Loc::LLoad)
+ return Ref::none();
+ return emit_load(ctx, sl, msk, il);
+}
+
+} // namespace
+
+void loadopt(Ctx* ctx, Fn* fn) {
+ ctx->load_curf = fn;
+ ctx->load_ilog = static_cast<Insert*>(vnew(ctx, 0, sizeof(Insert), PHeap));
+ ctx->load_nlog = 0;
+ ctx->load_inum = 0;
+
+ // solve each load
+ for (Blk* b = fn->start; b; b = b->link) {
+ for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i) {
+ if (!isload(i->op))
+ continue;
+ int sz = loadsz(i);
+ Slice sl;
+ sl.ref = i->arg[0];
+ sl.off = 0;
+ sl.sz = static_cast<short>(sz);
+ sl.cls = static_cast<short>(i->cls);
+ Loc l;
+ l.type = Loc::LRoot;
+ l.off = static_cast<uint>(i - b->ins);
+ l.blk = b;
+ rebase(ctx, &sl);
+ i->arg[1] = def(ctx, sl, mskbits(sz), b, i, &l);
+ }
+ }
+
+ // sort and rebuild each block
+ qsort(ctx->load_ilog, ctx->load_nlog, sizeof(Insert), icmp);
+ vgrow(ctx, &ctx->load_ilog, ctx->load_nlog + 1);
+ ctx->load_ilog[ctx->load_nlog].bid = fn->nblk; // sentinel: stops ist->bid == n check
+
+ Ins* ib = static_cast<Ins*>(vnew(ctx, 0, sizeof(Ins), PHeap));
+ Insert* ist = ctx->load_ilog;
+ for (uint n = 0; n < fn->nblk; ++n) {
+ Blk* b = fn->rpo[n];
+
+ // Push block's phi inserts to b->phi head
+ for (; ist->bid == n && ist->isphi; ++ist) {
+ ist->phi_node->link = b->phi;
+ b->phi = ist->phi_node;
+ }
+
+ uint ni = 0;
+ uint nt = 0;
+ for (;;) {
+ Ins* i;
+ if (ist->bid == n && ist->off == ni) {
+ i = &ist->ins;
+ ++ist;
+ } else {
+ if (ni == b->nins)
+ break;
+ i = &b->ins[ni++];
+ if (isload(i->op) && !req(i->arg[1], Ref::none())) {
+ // Solved load -> rewrite op + arg
+ int ext = Oextsb + (static_cast<int>(i->op) - Oloadsb);
+ switch (i->op) {
+ case Oloadsb:
+ case Oloadub:
+ case Oloadsh:
+ case Oloaduh:
+ i->op = static_cast<uint>(ext);
+ break;
+ case Oloadsw:
+ case Oloaduw:
+ if (i->cls == Kl) {
+ i->op = static_cast<uint>(ext);
+ break;
+ }
+ // fall through: under Kw sub-word is equivalent to full word -> direct
+ // copy
+ [[fallthrough]];
+ case Oload:
+ i->op = Ocopy;
+ break;
+ default:
+ die("loadopt: unreachable in solved-load rewrite");
+ }
+ i->arg[0] = i->arg[1];
+ i->arg[1] = Ref::none();
+ }
+ }
+ vgrow(ctx, &ib, ++nt);
+ ib[nt - 1] = *i;
+ }
+ idup(ctx, b, ib, nt);
+ }
+ vfree(ib);
+ vfree(ctx->load_ilog);
+ ctx->load_ilog = nullptr;
+
+ if (debug['M']) {
+ fprintf(ctx->dbg_buf, "\n> After load elimination:\n");
+ printfn(fn, ctx->dbg_buf);
+ }
+}
+
+} // namespace rcc
diff --git a/rcc-legacy/src/mid/mem.cc b/rcc-legacy/src/mid/mem.cc
new file mode 100644
index 0000000..12b9ef8
--- /dev/null
+++ b/rcc-legacy/src/mid/mem.cc
@@ -0,0 +1,653 @@
+/* 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 mem.cc
+/// @brief Memory optimizations: `promote` and `coalesce`.
+///
+/// See docs/mem.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <climits>
+#include <cstdlib>
+#include <cstring>
+
+namespace rcc {
+
+// promote slots.
+
+namespace {
+
+/// Describes the result of a promote compatibility scan.
+struct UniformFit {
+ int sz; // Shared access width; -1 means "undetermined" (only in all-load state)
+ int k; // Shared store cls; -1 means "no store" (pure read slot, dies later)
+};
+
+/// Scan all uses of alloc tmp to check if it can be promoted. Returns true and fills *fit on
+/// success.
+bool check_uniform(Tmp* t, Ref alloc_ref, UniformFit* fit) {
+ int s = -1, k = -1;
+ for (Use* u = t->use; u < &t->use[t->nuse]; u++) {
+ if (u->type != Use::UIns)
+ return false;
+ Ins* l = u->u.ins;
+
+ if (isload(l->op)) {
+ int ls = loadsz(l);
+ if (s != -1 && s != ls)
+ return false;
+ s = ls;
+ continue;
+ }
+
+ if (isstore(l->op)) {
+ // Must be store(value, addr=alloc): addr in arg[1], value in arg[0]
+ if (!req(alloc_ref, l->arg[1]) || req(alloc_ref, l->arg[0]))
+ return false;
+ int ss = storesz(l);
+ if (s != -1 && s != ss)
+ return false;
+ int sk = optab[l->op].argcls[0][0];
+ if (k != -1 && k != sk)
+ return false;
+ s = ss;
+ k = sk;
+ continue;
+ }
+
+ return false; // Non load/store use (addr passed out, compared, etc.)
+ }
+ fit->sz = s;
+ fit->k = k;
+ return true;
+}
+
+inline Ins make_nop() {
+ Ins n{};
+ n.op = Onop;
+ return n;
+}
+
+/// Rewrite uses to copy / cast / ext (see docs/mem.md).
+void rewrite_uses(Tmp* t, int k, Fn* fn) {
+ Use* ue = &t->use[t->nuse];
+ for (Use* u = t->use; u != ue; u++) {
+ Ins* l = u->u.ins;
+
+ if (isstore(l->op)) {
+ // store value, addr → copy value to addr-as-def
+ l->cls = static_cast<uint>(k);
+ l->op = Ocopy;
+ l->to = l->arg[1];
+ l->arg[1] = Ref::none();
+ t->nuse--;
+ t->ndef++;
+ continue;
+ }
+
+ // Check lock.
+ if (k == -1)
+ die("promote: slot %%%s is read but never stored to", fn->tmp[l->arg[0].val].name);
+
+ bool extend = false;
+ switch (l->op) {
+ case Oloadsw:
+ case Oloaduw:
+ if (k == Kl) {
+ extend = true;
+ break;
+ }
+ [[fallthrough]];
+ case Oload:
+ if (KBASE(k) != KBASE(static_cast<int>(l->cls)))
+ l->op = Ocast;
+ else
+ l->op = Ocopy;
+ break;
+ default:
+ extend = true;
+ break;
+ }
+ if (extend)
+ l->op = static_cast<uint>(Oextsb + (static_cast<int>(l->op) - Oloadsb));
+ }
+}
+
+} // namespace
+
+void promote(Ctx* ctx, Fn* fn) {
+ Blk* b = fn->start;
+ for (Ins* i = b->ins; i < &b->ins[b->nins]; i++) {
+ if (i->op < Oalloc || i->op > Oalloc1)
+ continue;
+ // Assumption NAlign == 3.
+ assert(rtype(i->to) == RTmp);
+ Tmp* t = &fn->tmp[i->to.val];
+ if (t->ndef != 1)
+ continue;
+
+ UniformFit fit;
+ if (!check_uniform(t, i->to, &fit))
+ continue;
+
+ // Kill alloc, rewrite all uses.
+ *i = make_nop();
+ t->ndef--;
+ rewrite_uses(t, fit.k, fn);
+ }
+
+ if (debug['M']) {
+ fprintf(ctx->dbg_buf, "\n> After slot promotion:\n");
+ printfn(fn, ctx->dbg_buf);
+ }
+}
+
+// coalesce slots.
+
+namespace {
+
+/// Half-open interval [a, b). b == 0 means "empty interval" (slot not yet radd'ed).
+struct Range {
+ int a, b;
+};
+
+/// store-record: a store instruction recorded on a slot + its ip.
+struct Store {
+ int ip;
+ Ins* i;
+};
+
+struct Slot {
+ int t; // corresponding tmp number
+ int sz; // alloc size (bytes)
+ bits m; // accumulated write mask for this slot (from fillalias)
+ bits l; // read mask accumulated during reverse block traversal
+ Range r; // live range (covers all active ips)
+ Slot* s; // fused representative (s == this means self is rep); nullptr if not fused
+ Store* st; // array of store records on this slot (PHeap-vnew)
+ int nst;
+};
+
+inline bool rin(Range r, int n) {
+ return r.a <= n && n < r.b;
+}
+
+inline bool rovlap(Range r0, Range r1) {
+ // Overlap check.
+ return r0.b && r1.b && r0.a < r1.b && r1.a < r0.b;
+}
+
+void radd(Range* r, int n) {
+ if (!r->b) {
+ r->a = n;
+ r->b = n + 1;
+ } else if (n < r->a) {
+ r->a = n;
+ } else if (n >= r->b) {
+ r->b = n + 1;
+ }
+}
+
+/// Translate ref r to its slot (if any) and offset. Returns false if r does not point to a coalesce
+/// candidate.
+bool slot_of(Slot** ps, int64_t* off, Ref r, Fn* fn, Slot* sl) {
+ Alias a;
+ getalias(&a, r, fn);
+ if (a.type != Alias::ALoc)
+ return false;
+ Tmp* t = &fn->tmp[a.base];
+ if (t->visit < 0)
+ return false; // tmp not in sl[]
+ *off = a.offset;
+ *ps = &sl[t->visit];
+ return true;
+}
+
+/// Encountered a read of x high-order bytes from r during reverse RPO.
+void load(Ref r, bits x, int ip, Fn* fn, Slot* sl) {
+ int64_t off;
+ Slot* s;
+ if (!slot_of(&s, &off, r, fn, sl))
+ return;
+ s->l |= x << off;
+ s->l &= s->m;
+ if (s->l)
+ radd(&s->r, ip);
+}
+
+/// Encountered a write of x bytes to r during reverse RPO.
+/// Encountered a write.
+void store(Ref r, bits x, int ip, Ins* i, Ctx* ctx, Fn* fn, Slot* sl) {
+ int64_t off;
+ Slot* s;
+ if (!slot_of(&s, &off, r, fn, sl))
+ return;
+ if (s->l) {
+ // Currently has live bytes: store is valid, advance live range.
+ radd(&s->r, ip);
+ s->l &= ~(x << off);
+ } else {
+ // No live bytes: store is a potential dead store, record in slot.st[].
+ vgrow(ctx, &s->st, static_cast<ulong>(++s->nst));
+ s->st[s->nst - 1].ip = ip;
+ s->st[s->nst - 1].i = i;
+ }
+}
+
+/// qsort comparator: descending by sz; ascending by r.a if sz equal (earlier first).
+int scmp(const void* pa, const void* pb) {
+ const Slot* a = static_cast<const Slot*>(pa);
+ const Slot* b = static_cast<const Slot*>(pb);
+ if (a->sz != b->sz)
+ return b->sz - a->sz;
+ return a->r.a - b->r.a;
+}
+
+/// loopiter callback (see docs/mem.md).
+void maxrpo(Blk* hd, Blk* b) {
+ if (hd->loop < static_cast<int>(b->id))
+ hd->loop = static_cast<int>(b->id);
+}
+
+struct SlotList {
+ Slot* sl;
+ int nsl;
+};
+
+SlotList collect_slots(Ctx* ctx, Fn* fn) {
+ SlotList sls;
+ sls.nsl = 0;
+ sls.sl = static_cast<Slot*>(vnew(ctx, 0, sizeof(Slot), PHeap));
+ for (int n = Tmp0; n < fn->ntmp; n++) {
+ Tmp* t = &fn->tmp[n];
+ t->visit = -1;
+ // Qualification check.
+ if (t->alias.type != Alias::ALoc)
+ continue;
+ if (t->alias.slot != &t->alias)
+ continue;
+ if (t->bid != fn->start->id)
+ continue;
+ if (t->alias.u.loc.sz == -1)
+ continue;
+
+ t->visit = sls.nsl;
+ vgrow(ctx, &sls.sl, static_cast<ulong>(++sls.nsl));
+ Slot* s = &sls.sl[sls.nsl - 1];
+ s->t = n;
+ s->sz = t->alias.u.loc.sz;
+ s->m = t->alias.u.loc.m;
+ s->l = 0;
+ s->r = Range{0, 0};
+ s->s = nullptr;
+ s->st = static_cast<Store*>(vnew(ctx, 0, sizeof(Store), PHeap));
+ s->nst = 0;
+ }
+ return sls;
+}
+
+struct LiveOut {
+ Range* br; // br[n] is the entry/exit ip range of the n-th RPO block; PHeap, freed at coalesce
+ // end.
+ Ins** bl; // blit list (PHeap vnew)
+ int nbl;
+ int ip; // final ip (minimum); used for debugging output restoration.
+};
+
+LiveOut compute_liveness(Ctx* ctx, Fn* fn, Slot* sl, int nsl) {
+ LiveOut lo;
+ lo.nbl = 0;
+ lo.bl = static_cast<Ins**>(vnew(ctx, 0, sizeof(Ins*), PHeap));
+ lo.br = static_cast<Range*>(emalloc(static_cast<size_t>(fn->nblk) * sizeof(Range)));
+
+ // Initialize b->loop for maxrpo
+ for (Blk* b = fn->start; b; b = b->link)
+ b->loop = -1;
+ loopiter(fn, maxrpo);
+
+ int ip = INT_MAX - 1;
+ for (int n = static_cast<int>(fn->nblk) - 1; n >= 0; n--) {
+ Blk* b = fn->rpo[n];
+
+ // succ array (s1, s2 deduplicated, terminated by nullptr)
+ Blk* succ[3];
+ succ[0] = b->s1;
+ succ[1] = b->s2;
+ succ[2] = nullptr;
+
+ lo.br[n].b = ip--;
+
+ // For each slot: inherit live bytes from successor entries.
+ for (Slot* s = sl; s < &sl[nsl]; s++) {
+ s->l = 0;
+ for (Blk** ps = succ; *ps; ps++) {
+ int m = static_cast<int>((*ps)->id);
+ if (m > n && rin(s->r, lo.br[m].a)) {
+ s->l = s->m;
+ radd(&s->r, ip);
+ }
+ }
+ }
+
+ // Process Jretc jmp arg: treat as full slot read.
+ if (b->jmp.type == Jretc)
+ load(b->jmp.arg, static_cast<bits>(-1), --ip, fn, sl);
+
+ // Reverse traversal of instructions
+ for (Ins* i = &b->ins[b->nins]; i != b->ins;) {
+ --i;
+ Ref* arg = i->arg;
+
+ if (i->op == Oargc) {
+ // by-value struct arg: mark entire slot as read
+ load(arg[1], static_cast<bits>(-1), --ip, fn, sl);
+ }
+ if (isload(i->op)) {
+ bits x = BIT(loadsz(i)) - 1;
+ load(arg[0], x, --ip, fn, sl);
+ }
+ if (isstore(i->op)) {
+ bits x = BIT(storesz(i)) - 1;
+ store(arg[1], x, ip--, i, ctx, fn, sl);
+ }
+ if (i->op == Oblit0) {
+ assert((i + 1)->op == Oblit1);
+ assert(rtype((i + 1)->arg[0]) == RInt);
+ int sz = std::abs(rsval((i + 1)->arg[0]));
+ bits x = sz >= static_cast<int>(NBit) ? static_cast<bits>(-1) : BIT(sz) - 1;
+ store(arg[1], x, ip--, i, ctx, fn, sl);
+ load(arg[0], x, ip, fn, sl);
+ vgrow(ctx, &lo.bl, static_cast<ulong>(++lo.nbl));
+ lo.bl[lo.nbl - 1] = i;
+ }
+ }
+
+ // Block entry update.
+ for (Slot* s = sl; s < &sl[nsl]; s++)
+ if (s->l) {
+ radd(&s->r, ip);
+ if (b->loop != -1) {
+ assert(b->loop >= n);
+ radd(&s->r, lo.br[b->loop].b - 1);
+ }
+ }
+ lo.br[n].a = ip;
+ }
+
+ lo.ip = ip;
+ return lo;
+}
+
+void kill_dead_stores(Slot* sl, int nsl) {
+ for (Slot* s = sl; s < &sl[nsl]; s++) {
+ for (int n = 0; n < s->nst; n++) {
+ if (rin(s->r, s->st[n].ip))
+ continue;
+ // ip not in r -> dead store
+ Ins* i = s->st[n].i;
+ if (i->op == Oblit0)
+ *(i + 1) = make_nop();
+ *i = make_nop();
+ }
+ }
+}
+
+/// Kills empty interval slots recursively (see docs/mem.md).
+struct KillStats {
+ int new_nsl;
+ uint total;
+ uint freed;
+};
+
+KillStats kill_empty_slots(Ctx* ctx, Slot* sl, int nsl, Fn* fn) {
+ int* stk = static_cast<int*>(vnew(ctx, 0, sizeof(int), PHeap));
+ int n = 0;
+ uint total = 0, freed = 0;
+
+ // Compact sl[].
+ Slot* s0 = sl;
+ for (Slot* s = sl; s < &sl[nsl]; s++) {
+ total += static_cast<uint>(s->sz);
+ if (!s->r.b) {
+ vfree(s->st);
+ vgrow(ctx, &stk, static_cast<ulong>(++n));
+ stk[n - 1] = s->t;
+ freed += static_cast<uint>(s->sz);
+ } else {
+ *s0++ = *s;
+ }
+ }
+ int new_nsl = static_cast<int>(s0 - sl);
+
+ if (debug['M']) {
+ fputs("\n> Slot coalescing:\n", ctx->dbg_buf);
+ if (n) {
+ fputs("\tkill [", ctx->dbg_buf);
+ for (int m = 0; m < n; m++)
+ fprintf(ctx->dbg_buf, " %%%s", fn->tmp[stk[m]].name);
+ fputs(" ]\n", ctx->dbg_buf);
+ }
+ }
+
+ // Propagate kill.
+ while (n--) {
+ Tmp* t = &fn->tmp[stk[n]];
+ assert(t->ndef == 1 && t->def);
+ Ins* i = t->def;
+ if (isload(i->op)) {
+ // This tmp is a pointer loaded; change to copy UNDEF so subsequent fold cleans it
+ // naturally.
+ i->op = Ocopy;
+ i->arg[0] = Ref::undef();
+ continue;
+ }
+ *i = make_nop();
+ for (Use* u = t->use; u < &t->use[t->nuse]; u++) {
+ if (u->type == Use::UJmp) {
+ Blk* b = fn->rpo[u->bid];
+ assert(isret(b->jmp.type));
+ b->jmp.type = Jret0;
+ b->jmp.arg = Ref::none();
+ continue;
+ }
+ assert(u->type == Use::UIns);
+ i = u->u.ins;
+ if (!req(i->to, Ref::none())) {
+ assert(rtype(i->to) == RTmp);
+ vgrow(ctx, &stk, static_cast<ulong>(++n));
+ stk[n - 1] = static_cast<int>(i->to.val);
+ } else if (isarg(i->op)) {
+ // Only Oargc reaches here: change its arg[1] to CON_Z to crash the callee
+ // intentionally.
+ assert(i->op == Oargc);
+ i->arg[1] = Ref::con_z();
+ } else {
+ if (i->op == Oblit0)
+ *(i + 1) = make_nop();
+ *i = make_nop();
+ }
+ }
+ }
+ vfree(stk);
+
+ return KillStats{new_nsl, total, freed};
+}
+
+uint fuse_slots(Slot* sl, int nsl) {
+ qsort(sl, static_cast<size_t>(nsl), sizeof(Slot), scmp);
+ uint fused = 0;
+
+ for (int n = 0; n < nsl; n++) {
+ Slot* s0 = &sl[n];
+ if (s0->s)
+ continue;
+ s0->s = s0;
+ Range r = s0->r;
+
+ for (Slot* s = s0 + 1; s < &sl[nsl]; s++) {
+ if (s->s || !s->r.b)
+ continue;
+ if (rovlap(r, s->r)) {
+ // Scan for collision.
+ bool conflict = false;
+ for (int m = n; &sl[m] < s; m++) {
+ if (sl[m].s == s0 && rovlap(sl[m].r, s->r)) {
+ conflict = true;
+ break;
+ }
+ }
+ if (conflict)
+ continue;
+ }
+ radd(&r, s->r.a);
+ radd(&r, s->r.b - 1);
+ s->s = s0;
+ fused += static_cast<uint>(s->sz);
+ }
+ }
+ return fused;
+}
+
+void substitute_fused_slots(Slot* sl, int nsl, Fn* fn) {
+ for (Slot* s = sl; s < &sl[nsl]; s++) {
+ Tmp* t = &fn->tmp[s->t];
+ // Reset visit.
+ t->visit = static_cast<int>(s - sl);
+ assert(t->ndef == 1 && t->def);
+ if (s->s == s)
+ continue;
+
+ // Erase alloc instruction of this slot
+ *t->def = make_nop();
+
+ Tmp* ts = &fn->tmp[s->s->t];
+ assert(t->bid == ts->bid);
+
+ // Guarantee dominance.
+ if (t->def < ts->def) {
+ *t->def = *ts->def;
+ *ts->def = make_nop();
+ ts->def = t->def;
+ }
+
+ // Rewrite all uses to point to the representative tmp
+ for (Use* u = t->use; u < &t->use[t->nuse]; u++) {
+ if (u->type == Use::UJmp) {
+ Blk* b = fn->rpo[u->bid];
+ b->jmp.arg = Ref::tmp(static_cast<uint>(s->s->t));
+ continue;
+ }
+ assert(u->type == Use::UIns);
+ Ref* arg = u->u.ins->arg;
+ for (int n = 0; n < 2; n++)
+ if (req(arg[n], Ref::tmp(static_cast<uint>(s->t))))
+ arg[n] = Ref::tmp(static_cast<uint>(s->s->t));
+ }
+ }
+}
+
+void fix_blits(Ins** bl, int nbl, Slot* sl, Fn* fn) {
+ for (int n = 0; n < nbl; n++) {
+ Ins* i = bl[n];
+ if (i->op != Oblit0)
+ continue; // Already cleaned up in some round
+ Slot *sa, *sb;
+ int64_t off0, off1;
+ if (!slot_of(&sa, &off0, i->arg[0], fn, sl))
+ continue;
+ if (!slot_of(&sb, &off1, i->arg[1], fn, sl))
+ continue;
+ if (sa->s != sb->s)
+ continue;
+
+ // Both ends fused into same slot
+ if (off0 < off1) {
+ // Reverse blit: negative size to tell backend to reverse memmove.
+ int sz = rsval((i + 1)->arg[0]);
+ assert(sz >= 0);
+ (i + 1)->arg[0] = Ref::integer(-sz);
+ } else if (off0 == off1) {
+ // Self-blit: delete entirely.
+ *i = make_nop();
+ *(i + 1) = make_nop();
+ }
+ }
+}
+
+void print_fuse_groups(Ctx* ctx, Slot* sl, int nsl, int ip, Fn* fn, uint freed, uint fused,
+ uint total) {
+ FILE* f = ctx->dbg_buf;
+ for (Slot* s0 = sl; s0 < &sl[nsl]; s0++) {
+ if (s0->s != s0)
+ continue;
+ fprintf(f, "\tfuse (% 3db) [", s0->sz);
+ for (Slot* s = s0; s < &sl[nsl]; s++) {
+ if (s->s != s0)
+ continue;
+ fprintf(f, " %%%s", fn->tmp[s->t].name);
+ if (s->r.b)
+ fprintf(f, "[%d,%d)", s->r.a - ip, s->r.b - ip);
+ else
+ fputs("{}", f);
+ }
+ fputs(" ]\n", f);
+ }
+ fprintf(f, "\tsums %u/%u/%u (killed/fused/total)\n\n", freed, fused, total);
+ printfn(fn, f);
+}
+
+} // namespace
+
+void coalesce(Ctx* ctx, Fn* fn) {
+ // Collect candidate slots
+ SlotList sls = collect_slots(ctx, fn);
+ Slot* sl = sls.sl;
+ int nsl = sls.nsl;
+
+ // Single reverse RPO to compute live ranges
+ LiveOut lo = compute_liveness(ctx, fn, sl, nsl);
+ free(lo.br);
+
+ // Kill out-of-range stores
+ kill_dead_stores(sl, nsl);
+
+ // Kill empty interval slots and propagate use-chain cleanup
+ KillStats ks = kill_empty_slots(ctx, sl, nsl, fn);
+ nsl = ks.new_nsl;
+
+ // Fuse slots
+ uint fused = fuse_slots(sl, nsl);
+
+ // Redirect def/use of fused slots to representatives
+ substitute_fused_slots(sl, nsl, fn);
+
+ // Fix instructions that became same-slot self-blits
+ fix_blits(lo.bl, lo.nbl, sl, fn);
+ vfree(lo.bl);
+
+ if (debug['M'])
+ print_fuse_groups(ctx, sl, nsl, lo.ip, fn, ks.freed, fused, ks.total);
+
+ for (Slot* s = sl; s < &sl[nsl]; s++)
+ vfree(s->st);
+ vfree(sl);
+}
+
+} // namespace rcc
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
diff --git a/rcc-legacy/src/mid/storemrg.cc b/rcc-legacy/src/mid/storemrg.cc
new file mode 100644
index 0000000..65b4bd4
--- /dev/null
+++ b/rcc-legacy/src/mid/storemrg.cc
@@ -0,0 +1,231 @@
+/* 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 storemrg.cc
+/// @brief Fuses adjacent 4B stores into 8B storel.
+///
+/// See docs/storemrg.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <vector>
+
+namespace rcc {
+
+namespace {
+
+// Read 32-bit integer constant value from Ref r (put into *val_out).
+bool get_int_con32(Fn* fn, Ref r, uint32_t* val_out) {
+ if (rtype(r) != RCon)
+ return false;
+ Con* c = &fn->con[r.val];
+ if (c->type != Con::CBits || c->flt)
+ return false;
+ *val_out = static_cast<uint32_t>(c->bits.i);
+ return true;
+}
+
+bool ref_eq(Ref a, Ref b) {
+ return a.type == b.type && a.val == b.val;
+}
+
+// Decompose addr into (base, offset).
+void decompose_addr(Fn* fn, Ref addr, Ref* base_out, int64_t* off_out) {
+ *base_out = addr;
+ *off_out = 0;
+ if (rtype(addr) != RTmp)
+ return;
+ Tmp* t = &fn->tmp[addr.val];
+ if (!t->def)
+ return;
+ Ins* def = t->def;
+ if (def->op != Oadd)
+ return;
+ Ref ra = def->arg[0], rb = def->arg[1];
+ auto try_split = [&](Ref tmp_r, Ref con_r) -> bool {
+ if (rtype(tmp_r) != RTmp || rtype(con_r) != RCon)
+ return false;
+ Con* c = &fn->con[con_r.val];
+ if (c->type != Con::CBits || c->flt)
+ return false;
+ *base_out = tmp_r;
+ *off_out = c->bits.i;
+ return true;
+ };
+ if (try_split(ra, rb))
+ return;
+ try_split(rb, ra);
+}
+
+bool con_is_aligned8(Fn* fn, Ref r) {
+ if (rtype(r) != RCon)
+ return false;
+ Con* c = &fn->con[r.val];
+ return c->type == Con::CBits && !c->flt && (c->bits.i & 7) == 0;
+}
+
+bool tmp_in_align8(const std::vector<bool>& a8, Ref r) {
+ if (rtype(r) != RTmp)
+ return false;
+ if (r.val >= a8.size())
+ return false;
+ return a8[r.val];
+}
+
+// Optimistic fixpoint: compute aligned8 set.
+std::vector<bool> compute_aligned8(Fn* fn) {
+ std::vector<bool> a8(static_cast<size_t>(fn->ntmp), true);
+ bool changed = true;
+ while (changed) {
+ changed = false;
+ for (Blk* b = fn->start; b; b = b->link) {
+ for (Phi* p = b->phi; p; p = p->link) {
+ if (rtype(p->to) != RTmp)
+ continue;
+ uint tid = p->to.val;
+ if (tid >= a8.size() || !a8[tid])
+ continue;
+ bool ok = p->narg > 0;
+ for (uint k = 0; k < p->narg; k++) {
+ Ref r = p->arg[k];
+ if (tmp_in_align8(a8, r))
+ continue;
+ if (con_is_aligned8(fn, r))
+ continue;
+ ok = false;
+ break;
+ }
+ if (!ok) {
+ a8[tid] = false;
+ changed = true;
+ }
+ }
+ for (uint k = 0; k < b->nins; k++) {
+ Ins* i = &b->ins[k];
+ if (rtype(i->to) != RTmp)
+ continue;
+ uint tid = i->to.val;
+ if (tid >= a8.size() || !a8[tid])
+ continue;
+ bool ok = false;
+ int op = i->op;
+ if (op == Oalloc8 || op == Oalloc16) {
+ ok = true;
+ } else if (op == Ocopy) {
+ if (tmp_in_align8(a8, i->arg[0]))
+ ok = true;
+ } else if (op == Oadd) {
+ if ((tmp_in_align8(a8, i->arg[0]) && con_is_aligned8(fn, i->arg[1])) ||
+ (tmp_in_align8(a8, i->arg[1]) && con_is_aligned8(fn, i->arg[0])))
+ ok = true;
+ }
+ // All other ops (Omul / Oload / Opar / Ocall / ...) are unconditionally demoted.
+ if (!ok) {
+ a8[tid] = false;
+ changed = true;
+ }
+ }
+ }
+ }
+ return a8;
+}
+
+} // namespace
+
+void storemrg(Ctx* ctx, Fn* fn) {
+ std::vector<bool> a8 = compute_aligned8(fn);
+
+ int merged = 0;
+ for (Blk* b = fn->start; b; b = b->link) {
+ struct Pending {
+ uint idx;
+ Ref base;
+ int64_t off;
+ uint32_t val; // 32-bit store value
+ };
+ std::vector<Pending> pending;
+ auto flush = [&]() { pending.clear(); };
+
+ for (uint k = 0; k < b->nins; k++) {
+ Ins* i = &b->ins[k];
+ int op = i->op;
+
+ // Memory barrier: any load / call / other store flushes pending.
+ if (op == Ocall || isload(op)) {
+ flush();
+ continue;
+ }
+
+ uint32_t val32 = 0;
+ if (op == Ostorew && get_int_con32(fn, i->arg[0], &val32)) {
+ Ref base;
+ int64_t off;
+ decompose_addr(fn, i->arg[1], &base, &off);
+ if (tmp_in_align8(a8, base)) {
+ bool matched = false;
+ for (auto it = pending.begin(); it != pending.end(); ++it) {
+ bool prev_is_lower = (it->off + 4 == off) && (it->off & 7) == 0;
+ bool curr_is_lower = (off + 4 == it->off) && (off & 7) == 0;
+ // Must be same base + same 32-bit value + lower offset 8B-aligned pair.
+ if (ref_eq(it->base, base) && it->val == val32 &&
+ (prev_is_lower || curr_is_lower)) {
+ uint lo_idx = prev_is_lower ? it->idx : k;
+ uint hi_idx = prev_is_lower ? k : it->idx;
+ b->ins[lo_idx].op = Ostorel;
+ if (val32 != 0) {
+ // Assemble 64-bit duplicated constant.
+ uint64_t combined = static_cast<uint64_t>(val32) |
+ (static_cast<uint64_t>(val32) << 32);
+ b->ins[lo_idx].arg[0] =
+ getcon(ctx, static_cast<int64_t>(combined), fn);
+ }
+ // When val32==0, RCon{0} has identical bit pattern for Kw/Kl.
+ b->ins[hi_idx] = Ins{};
+ b->ins[hi_idx].op = Onop;
+ pending.erase(it);
+ merged++;
+ matched = true;
+ break;
+ }
+ }
+ if (!matched)
+ pending.push_back({k, base, off, val32});
+ continue;
+ }
+ // base not in align8 set -> cannot prove no-alias with pending, flush.
+ flush();
+ continue;
+ }
+
+ if (isstore(op)) {
+ flush();
+ continue;
+ }
+
+ // Pure instructions have no memory side-effects, pending untouched.
+ }
+ }
+
+ if (debug['M']) {
+ FILE* out = ctx->dbg_buf ? ctx->dbg_buf : stderr;
+ fprintf(out, "\n> storemrg %s: merged %d storew pairs → storel\n", fn->name, merged);
+ }
+}
+
+} // namespace rcc
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 16:46:06 +0000