aboutsummaryrefslogtreecommitdiff
path: root/src/backend/spill.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/spill.cc')
-rw-r--r--src/backend/spill.cc600
1 files changed, 600 insertions, 0 deletions
diff --git a/src/backend/spill.cc b/src/backend/spill.cc
new file mode 100644
index 0000000..360dcb3
--- /dev/null
+++ b/src/backend/spill.cc
@@ -0,0 +1,600 @@
+/* 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 backend/spill.cc
+/// @brief Register spilling pass.
+
+#include "rcc/all.h"
+
+#include <algorithm>
+#include <climits>
+#include <cstdio>
+#include <vector>
+
+namespace rcc {
+
+// fillcost
+
+namespace {
+
+// loopiter callback: aggregate gen/nlive of loop body to loop header.
+void aggreg(Blk* hd, Blk* b) {
+ bsunion(hd->gen, b->gen);
+ for (int k = 0; k < 2; ++k)
+ if (b->nlive[k] > hd->nlive[k])
+ hd->nlive[k] = b->nlive[k];
+}
+
+// Single Ref use accumulation.
+void tmpuse(Ref r, int use, int loop, Fn* fn) {
+ if (rtype(r) == RMem) {
+ Mem* m = &fn->mem[r.val];
+ tmpuse(m->base, 1, loop, fn);
+ tmpuse(m->index, 1, loop, fn);
+ return;
+ }
+ if (rtype(r) == RTmp && r.val >= Tmp0) {
+ Tmp* t = &fn->tmp[r.val];
+ t->nuse += static_cast<uint>(use);
+ t->ndef += static_cast<uint>(!use);
+ t->cost += static_cast<uint>(loop);
+ }
+}
+
+void accumulate_phi_costs(Blk* b, Fn* fn) {
+ for (Phi* p = b->phi; p; p = p->link) {
+ Tmp* t = &fn->tmp[p->to.val];
+ tmpuse(p->to, 0, 0, fn);
+ for (uint a = 0; a < p->narg; ++a) {
+ int n = p->blk[a]->loop;
+ t->cost += static_cast<uint>(n);
+ tmpuse(p->arg[a], 1, n, fn);
+ }
+ }
+}
+
+void accumulate_ins_costs(Blk* b, Fn* fn) {
+ int n = b->loop;
+ for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i) {
+ tmpuse(i->to, 0, n, fn);
+ tmpuse(i->arg[0], 1, n, fn);
+ tmpuse(i->arg[1], 1, n, fn);
+ }
+ tmpuse(b->jmp.arg, 1, n, fn);
+ tmpuse(b->jmp.arg2, 1, n, fn); // Second operand for Jjfi/Jjff.
+}
+
+void dump_loop_info(Ctx* ctx, Fn* fn) {
+ FILE* f = ctx->dbg_buf;
+ fprintf(f, "\n> Loop information:\n");
+ for (Blk* b = fn->start; b; b = b->link) {
+ uint a;
+ for (a = 0; a < b->npred; ++a)
+ if (b->id <= b->pred[a]->id)
+ break;
+ if (a != b->npred) {
+ fprintf(f, "\t%-10s", b->name);
+ fprintf(f, " (% 3d ", b->nlive[0]);
+ fprintf(f, "% 3d) ", b->nlive[1]);
+ dumpts(b->gen, fn->tmp, f);
+ }
+ }
+}
+
+} // namespace
+
+void fillcost(Ctx* ctx, Fn* fn) {
+ loopiter(fn, aggreg);
+
+ if (debug['S'])
+ dump_loop_info(ctx, fn);
+
+ // Register cost = UINT_MAX (never spill); normal tmp accumulates from 0.
+ for (Tmp* t = fn->tmp; t - fn->tmp < fn->ntmp; ++t) {
+ t->cost = (t - fn->tmp < Tmp0) ? UINT_MAX : 0;
+ t->nuse = 0;
+ t->ndef = 0;
+ }
+
+ for (Blk* b = fn->start; b; b = b->link) {
+ accumulate_phi_costs(b, fn);
+ accumulate_ins_costs(b, fn);
+ }
+
+ if (debug['S']) {
+ FILE* f = ctx->dbg_buf;
+ fprintf(f, "\n> Spill costs:\n");
+ for (int n = Tmp0; n < fn->ntmp; ++n)
+ fprintf(f, "\t%-10s %d\n", fn->tmp[n].name, fn->tmp[n].cost);
+ fprintf(f, "\n");
+ }
+}
+
+// spill
+
+namespace {
+
+// Per-call state.
+struct SpillCtx {
+ Ctx* ctx; // Back reference to ctx.
+ Tmp* tmp; // Cache of fn->tmp.
+ int ntmp;
+ int locs; // fn->slot entrance snapshot.
+ int slot4; // Next 4B slot.
+ int slot8; // Next 8B slot.
+ BSet mask[2]; // GPR and FPR bitsets.
+ BSet b2_scratch; // Scratch buffer for limit2.
+ std::vector<int> tarr; // Scratch buffer for limit.
+};
+
+// Allocate stack slot on demand.
+Ref alloc_spill_slot(SpillCtx& s, int t) {
+ assert(t >= Tmp0 && "cannot spill register");
+ int existing = s.tmp[t].slot;
+ if (existing != -1)
+ return Ref::slot(existing);
+
+ int pos;
+ if (KWIDE(s.tmp[t].cls)) {
+ pos = s.slot8;
+ if (s.slot4 == s.slot8)
+ s.slot4 += 2;
+ s.slot8 += 2;
+ } else {
+ pos = s.slot4;
+ if (s.slot4 == s.slot8) {
+ s.slot8 += 2;
+ s.slot4 += 1;
+ } else {
+ // 4B hole filled, jump to slot8.
+ s.slot4 = s.slot8;
+ }
+ }
+ pos += s.locs;
+ s.tmp[t].slot = pos;
+ return Ref::slot(pos);
+}
+
+// Limit bitset to at most k elements.
+void limit_one(SpillCtx& s, BSet* b, int k, BSet* f) {
+ int nt = static_cast<int>(bscount(b));
+ if (nt <= k)
+ return;
+
+ s.tarr.resize(static_cast<size_t>(nt));
+
+ // Pull elements from b to tarr, clear b.
+ int collected = 0;
+ int t = 0;
+ while (bsiter(b, &t)) {
+ bsclr(b, static_cast<uint>(t));
+ s.tarr[static_cast<size_t>(collected++)] = t;
+ ++t;
+ }
+ assert(collected == nt);
+
+ if (nt > 1) {
+ Tmp* tmp = s.tmp;
+ if (f) {
+ BSet* fst = f;
+ std::stable_sort(s.tarr.begin(), s.tarr.begin() + nt, [fst, tmp](int x, int y) {
+ int fx = bshas(fst, static_cast<uint>(x));
+ int fy = bshas(fst, static_cast<uint>(y));
+ if (fx != fy)
+ return fx > fy;
+ return tmp[x].cost > tmp[y].cost;
+ });
+ } else {
+ std::stable_sort(s.tarr.begin(), s.tarr.begin() + nt,
+ [tmp](int x, int y) { return tmp[x].cost > tmp[y].cost; });
+ }
+ }
+
+ int i = 0;
+ for (; i < k && i < nt; ++i)
+ bsset(b, static_cast<uint>(s.tarr[static_cast<size_t>(i)]));
+ for (; i < nt; ++i)
+ alloc_spill_slot(s, s.tarr[static_cast<size_t>(i)]);
+}
+
+// Limit GPR/FPR separately.
+void limit_two(SpillCtx& s, BSet* b1, int k1, int k2, BSet* f) {
+ BSet* b2 = &s.b2_scratch;
+ bscopy(b2, b1);
+ bsinter(b1, &s.mask[0]);
+ bsinter(b2, &s.mask[1]);
+ limit_one(s, b1, T.ngpr - k1, f);
+ {
+ int cnt = static_cast<int>(bscount(b2));
+ if (cnt > s.ctx->spill_fp_live_peak)
+ s.ctx->spill_fp_live_peak = cnt;
+ }
+ limit_one(s, b2, T.nfpr - k2, f);
+ bsunion(b1, b2);
+}
+
+// Set register hint for tmp in u.
+void sethint(SpillCtx& s, BSet* u, bits r) {
+ int t = Tmp0;
+ while (bsiter(u, &t)) {
+ s.tmp[phicls(t, s.tmp)].hint.m |= r;
+ ++t;
+ }
+}
+
+// Emit Oload for tmp in u \ v.
+void reloads(Ctx* ctx, SpillCtx& s, BSet* u, BSet* v) {
+ int t = Tmp0;
+ while (bsiter(u, &t)) {
+ if (!bshas(v, static_cast<uint>(t)))
+ emit(ctx, Oload, s.tmp[t].cls, Ref::tmp(static_cast<uint>(t)), alloc_spill_slot(s, t),
+ Ref::none());
+ ++t;
+ }
+}
+
+// Emit Ostore to SLOT(s) if s != -1.
+void store_to_slot(Ctx* ctx, SpillCtx& spc, Ref r, int slot_id) {
+ if (slot_id == -1)
+ return;
+ int cls = spc.tmp[r.val].cls;
+ emit(ctx, Ostorew + cls, 0, Ref::none(), r, Ref::slot(slot_id));
+}
+
+inline bool is_regcopy(Ins* i) {
+ return i->op == Ocopy && isreg(i->arg[0]);
+}
+
+// Process parallel moves (contiguous reg->tmp copies).
+Ins* spill_par_moves(Ctx* ctx, SpillCtx& s, Blk* b, Ins* i, BSet* v) {
+ BSet u[1];
+ bsinit(ctx, u, static_cast<uint>(s.ntmp));
+
+ // Backward scan of contiguous regcpy segment.
+ Ins* i1 = ++i;
+ do {
+ --i;
+ int t = i->to.val;
+ if (!req(i->to, Ref::none()))
+ if (bshas(v, static_cast<uint>(t))) {
+ bsclr(v, static_cast<uint>(t));
+ store_to_slot(ctx, s, i->to, s.tmp[t].slot);
+ }
+ bsset(v, i->arg[0].val);
+ } while (i != b->ins && is_regcopy(i - 1));
+
+ bscopy(u, v);
+
+ bits r;
+ if (i != b->ins && (i - 1)->op == Ocall) {
+ // Call site: return registers are dead, argregs must be preserved.
+ Ins* call = i - 1;
+ v->t[0] &= ~T.retregs(call->arg[1], nullptr);
+ limit_two(s, v, T.nrsave[0], T.nrsave[1], nullptr);
+ r = 0;
+ for (int n = 0; T.rsave[n] >= 0; ++n)
+ r |= BIT(T.rsave[n]);
+ v->t[0] |= T.argregs(call->arg[1], nullptr);
+ } else {
+ limit_two(s, v, 0, 0, nullptr);
+ r = v->t[0];
+ }
+ sethint(s, v, r);
+ reloads(ctx, s, u, v);
+
+ // Re-emit original regcpy in the segment.
+ do
+ emiti(ctx, *--i1);
+ while (i1 != i);
+ return i;
+}
+
+// Loop header path merge.
+void merge_pred(SpillCtx& s, BSet* u, Blk* bu, BSet* v, Blk* bv) {
+ if (bu->loop <= bv->loop) {
+ bsunion(u, v);
+ return;
+ }
+ int t = 0;
+ while (bsiter(v, &t)) {
+ if (s.tmp[t].slot == -1)
+ bsset(u, static_cast<uint>(t));
+ ++t;
+ }
+}
+
+// Compute exit set v.
+void compute_exit_set(SpillCtx& s, Blk* b, BSet* u, BSet* v, BSet* w) {
+ Blk* s1 = b->s1;
+ Blk* s2 = b->s2;
+ Blk* hd = nullptr;
+ if (s1 && s1->id <= b->id)
+ hd = s1;
+ if (s2 && s2->id <= b->id)
+ if (!hd || s2->id >= hd->id)
+ hd = s2;
+
+ if (hd) {
+ // Back-edge handling.
+ bszero(v);
+ hd->gen->t[0] |= T.rglob; // Global registers never spill.
+ for (int k = 0; k < 2; ++k) {
+ uint n = (k == 0) ? static_cast<uint>(T.ngpr) : static_cast<uint>(T.nfpr);
+ bscopy(u, b->out);
+ bsinter(u, &s.mask[k]);
+ bscopy(w, u);
+ bsinter(u, hd->gen);
+ bsdiff(w, hd->gen);
+ if (bscount(u) < n) {
+ int j = static_cast<int>(bscount(w)); // Live-through.
+ int l = hd->nlive[k];
+ if (k == 1 && static_cast<int>(bscount(w)) > s.ctx->spill_fp_live_peak)
+ s.ctx->spill_fp_live_peak = static_cast<int>(bscount(w));
+ limit_one(s, w, static_cast<int>(n) - (l - j), nullptr);
+ bsunion(u, w);
+ } else {
+ if (k == 1 && static_cast<int>(bscount(u)) > s.ctx->spill_fp_live_peak)
+ s.ctx->spill_fp_live_peak = static_cast<int>(bscount(u));
+ limit_one(s, u, static_cast<int>(n), nullptr);
+ }
+ bsunion(v, u);
+ }
+ } else if (s1) {
+ // Forward edge handling.
+ bszero(v);
+ liveon(w, b, s1);
+ merge_pred(s, v, b, w, s1);
+ if (s2) {
+ liveon(u, b, s2);
+ merge_pred(s, v, b, u, s2);
+ bsinter(w, u);
+ }
+ limit_two(s, v, 0, 0, w);
+ } else {
+ bscopy(v, b->out);
+ if (rtype(b->jmp.arg) == RCall)
+ v->t[0] |= T.retregs(b->jmp.arg, nullptr);
+ }
+}
+
+// Single instruction processing in main loop.
+
+// Process i->to.
+void process_def(Ins* i, BSet* v, BSet* w) {
+ if (req(i->to, Ref::none()))
+ return;
+ assert(rtype(i->to) == RTmp);
+ uint t = i->to.val;
+ if (bshas(v, t)) {
+ bsclr(v, t);
+ } else {
+ // Dead def.
+ assert(t >= Tmp0 && "dead reg");
+ bsset(v, t);
+ bsset(w, t);
+ }
+}
+
+// Process args.
+void process_args(Ins* i, BSet* v, BSet* w, int lvarg[2], Fn* fn) {
+ int memquota = T.memargs(static_cast<int>(i->op));
+ for (int n = 0; n < 2; ++n)
+ if (rtype(i->arg[n]) == RMem)
+ --memquota;
+
+ for (int n = 0; n < 2; ++n) {
+ switch (rtype(i->arg[n])) {
+ case RMem: {
+ uint t = i->arg[n].val;
+ Mem* m = &fn->mem[t];
+ if (rtype(m->base) == RTmp) {
+ bsset(v, m->base.val);
+ bsset(w, m->base.val);
+ }
+ if (rtype(m->index) == RTmp) {
+ bsset(v, m->index.val);
+ bsset(w, m->index.val);
+ }
+ break;
+ }
+ case RTmp: {
+ uint t = i->arg[n].val;
+ lvarg[n] = bshas(v, t);
+ bsset(v, t);
+ if (memquota-- <= 0)
+ bsset(w, t);
+ break;
+ }
+ default:
+ break;
+ }
+ }
+}
+
+// Rewrite evicted args after limit2.
+void rewrite_evicted_args(SpillCtx& s, Ins* i, BSet* u, BSet* v, const int lvarg[2]) {
+ for (int n = 0; n < 2; ++n) {
+ if (rtype(i->arg[n]) != RTmp)
+ continue;
+ uint t = i->arg[n].val;
+ if (!bshas(v, t)) {
+ if (!lvarg[n])
+ bsclr(u, t);
+ i->arg[n] = alloc_spill_slot(s, static_cast<int>(t));
+ }
+ }
+}
+
+// Process jmp args.
+void process_jmp_arg(SpillCtx& s, Blk* b, BSet* v) {
+ bool has1 = rtype(b->jmp.arg) == RTmp;
+ bool has2 = rtype(b->jmp.arg2) == RTmp;
+ if (!has1 && !has2)
+ return;
+ int t1 = has1 ? static_cast<int>(b->jmp.arg.val) : -1;
+ int t2 = has2 ? static_cast<int>(b->jmp.arg2.val) : -1;
+ if (has1) {
+ assert(KBASE(s.tmp[t1].cls) == 0);
+ bsset(v, static_cast<uint>(t1));
+ }
+ if (has2) {
+ assert(KBASE(s.tmp[t2].cls) == 0);
+ bsset(v, static_cast<uint>(t2));
+ }
+ limit_two(s, v, 0, 0, nullptr);
+ if (has1 && !bshas(v, static_cast<uint>(t1)))
+ b->jmp.arg = alloc_spill_slot(s, t1);
+ if (has2 && !bshas(v, static_cast<uint>(t2)))
+ b->jmp.arg2 = alloc_spill_slot(s, t2);
+}
+
+// Slot unselected outs.
+void slot_unselected_outs(SpillCtx& s, Blk* b, BSet* v) {
+ int t = Tmp0;
+ while (bsiter(b->out, &t)) {
+ if (!bshas(v, static_cast<uint>(t)))
+ alloc_spill_slot(s, t);
+ ++t;
+ }
+}
+
+// Process block phis.
+void process_block_phis(Ctx* ctx, SpillCtx& s, Blk* b, BSet* v) {
+ for (Phi* p = b->phi; p; p = p->link) {
+ assert(rtype(p->to) == RTmp);
+ uint t = p->to.val;
+ if (bshas(v, t)) {
+ bsclr(v, t);
+ store_to_slot(ctx, s, p->to, s.tmp[t].slot);
+ } else if (bshas(b->in, t)) {
+ p->to = alloc_spill_slot(s, static_cast<int>(t));
+ }
+ }
+}
+
+void dump_spill_result(Ctx* ctx, Fn* fn) {
+ FILE* f = ctx->dbg_buf;
+ fprintf(f, "\n> Block information:\n");
+ for (Blk* b = fn->start; b; b = b->link) {
+ fprintf(f, "\t%-10s (% 5d) ", b->name, b->loop);
+ dumpts(b->out, fn->tmp, f);
+ }
+ fprintf(f, "\n> After spilling:\n");
+ printfn(fn, f);
+}
+
+} // namespace
+
+// spill main entry.
+
+void spill(Ctx* ctx, Fn* fn) {
+ SpillCtx s{};
+ s.ctx = ctx;
+ s.tmp = fn->tmp;
+ s.ntmp = fn->ntmp;
+ s.locs = fn->slot;
+ s.slot4 = 0;
+ s.slot8 = 0;
+
+ uint n = static_cast<uint>(s.ntmp);
+ bsinit(ctx, &s.mask[0], n);
+ bsinit(ctx, &s.mask[1], n);
+ bsinit(ctx, &s.b2_scratch, n);
+
+ BSet u[1], v[1], w[1];
+ bsinit(ctx, u, n);
+ bsinit(ctx, v, n);
+ bsinit(ctx, w, n);
+
+ // Mask initialization.
+ for (int t = 0; t < s.ntmp; ++t) {
+ int k = 0;
+ if (t >= T.fpr0 && t < T.fpr0 + T.nfpr)
+ k = 1;
+ if (t >= Tmp0)
+ k = KBASE(s.tmp[t].cls);
+ bsset(&s.mask[k], static_cast<uint>(t));
+ }
+
+ // RPO reverse order iteration.
+ for (Blk** bp = &fn->rpo[fn->nblk]; bp != fn->rpo;) {
+ Blk* b = *--bp;
+
+ // Determine exit set v.
+ ctx->curi = nullptr; // emit/reloads disabled here.
+ compute_exit_set(s, b, u, v, w);
+ process_jmp_arg(s, b, v);
+ slot_unselected_outs(s, b, v);
+ bscopy(b->out, v);
+
+ // Reverse process instructions, fill insb.
+ ctx->curi = ctx->insb + NIns;
+ for (Ins* i = &b->ins[b->nins]; i != b->ins;) {
+ --i;
+ if (is_regcopy(i)) {
+ i = spill_par_moves(ctx, s, b, i, v);
+ continue;
+ }
+
+ bszero(w);
+ int lvarg[2] = {0, 0};
+ process_def(i, v, w);
+ process_args(i, v, w, lvarg, fn);
+
+ bscopy(u, v);
+ limit_two(s, v, 0, 0, w);
+ rewrite_evicted_args(s, i, u, v, lvarg);
+ reloads(ctx, s, u, v);
+
+ if (!req(i->to, Ref::none())) {
+ uint t = i->to.val;
+ store_to_slot(ctx, s, i->to, s.tmp[t].slot);
+ if (t >= Tmp0)
+ bsclr(v, t);
+ }
+ emiti(ctx, *i);
+
+ bits r = v->t[0]; // Low 64 bits are physical registers.
+ if (r)
+ sethint(s, v, r);
+ }
+
+ // Entry handling.
+ if (b == fn->start) {
+ assert(v->t[0] == (T.rglob | fn->reg));
+ } else {
+ assert(v->t[0] == T.rglob);
+ }
+
+ // Block entry phis.
+ process_block_phis(ctx, s, b, v);
+ bscopy(b->in, v);
+
+ idup(ctx, b, ctx->curi, static_cast<ulong>(ctx->insb + NIns - ctx->curi));
+ }
+
+ // 16-byte alignment.
+ s.slot8 += s.slot8 & 3;
+ fn->slot += s.slot8;
+
+ if (debug['S'])
+ dump_spill_result(ctx, fn);
+}
+
+} // namespace rcc
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 03:08:33 +0000