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