diff options
Diffstat (limited to 'src/mid/live.cc')
| -rw-r--r-- | src/mid/live.cc | 198 |
1 files changed, 198 insertions, 0 deletions
diff --git a/src/mid/live.cc b/src/mid/live.cc new file mode 100644 index 0000000..ee718ad --- /dev/null +++ b/src/mid/live.cc @@ -0,0 +1,198 @@ +/* Source code for RCC-Legacy. + Copyright (C) 2026 Richard Qin + +This file is part of RCC. + +RCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +RCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with RCC; see the file LICENSE. If not see +<http://www.gnu.org/licenses/>. */ + +/// @file live.cc +/// @brief Backward dataflow liveness analysis. +/// +/// See docs/live.md for architectural notes. + +#include "rcc/all.h" + +namespace rcc { + +void liveon(BSet* v, Blk* b, Blk* s) { + bscopy(v, s->in); + + // s's phi-defs. + for (Phi* p = s->phi; p; p = p->link) + if (rtype(p->to) == RTmp) + bsclr(v, p->to.val); + + // phi-arg edge check. + for (Phi* p = s->phi; p; p = p->link) { + for (uint n = 0; n < p->narg; n++) { + if (p->blk[n] != b) + continue; + if (rtype(p->arg[n]) != RTmp) + continue; + uint t = p->arg[n].val; + bsset(v, t); + bsset(b->gen, t); + } + } +} + +namespace { + +/// Add ref (if tmp) to b->gen and b->in; on first entry to b->in, increment live count for its K +/// bucket. +inline void use_ref(Ref r, Blk* b, int nlv[2], Tmp* tmp) { + if (rtype(r) != RTmp) + return; + uint t = r.val; + bsset(b->gen, t); + if (!bshas(b->in, t)) { + nlv[KBASE(tmp[t].cls)]++; + bsset(b->in, t); + } +} + +/// Get maximum of two elements. +inline int imax(int a, int b) { + return a > b ? a : b; +} + +} // namespace + +void filllive(Ctx* ctx, Fn* fn) { + BSet prev_out[1]; + BSet edge_set[1]; + + bsinit(ctx, prev_out, static_cast<uint>(fn->ntmp)); + bsinit(ctx, edge_set, static_cast<uint>(fn->ntmp)); + + // Initialize sets. + for (Blk* b = fn->start; b; b = b->link) { + bsinit(ctx, b->in, static_cast<uint>(fn->ntmp)); + bsinit(ctx, b->out, static_cast<uint>(fn->ntmp)); + bsinit(ctx, b->gen, static_cast<uint>(fn->ntmp)); + } + + // Fixpoint loop. + bool changed = true; + while (changed) { + changed = false; + + // Reverse rpo scan. + for (int n = static_cast<int>(fn->nblk) - 1; n >= 0; n--) { + Blk* b = fn->rpo[n]; + + // Merge successors liveon. + bscopy(prev_out, b->out); + + if (b->s1) { + liveon(edge_set, b, b->s1); + bsunion(b->out, edge_set); + } + if (b->s2) { + liveon(edge_set, b, b->s2); + bsunion(b->out, edge_set); + } + if (!bsequal(b->out, prev_out)) + changed = true; + + // Initial in. + int nlv[2] = {0, 0}; + b->out->t[0] |= T.rglob; + bscopy(b->in, b->out); + for (int t = 0; bsiter(b->in, &t); t++) + nlv[KBASE(fn->tmp[t].cls)]++; + + // Terminal jump args. + if (rtype(b->jmp.arg) == RCall) { + assert(static_cast<int>(bscount(b->in)) == T.nrglob && b->in->t[0] == T.rglob); + b->in->t[0] |= T.retregs(b->jmp.arg, nlv); + } else { + use_ref(b->jmp.arg, b, nlv, fn->tmp); + } + // Fused cmp+jnz check. + use_ref(b->jmp.arg2, b, nlv, fn->tmp); + + // Initial nlive. + for (int k = 0; k < 2; k++) + b->nlive[k] = nlv[k]; + + // Reverse scan instructions. + for (int idx = static_cast<int>(b->nins) - 1; idx >= 0; idx--) { + Ins* i = &b->ins[idx]; + + // Post-ABI lowering call. + if (i->op == Ocall && rtype(i->arg[1]) == RCall) { + int call_kill[2]; + b->in->t[0] &= ~T.retregs(i->arg[1], call_kill); + for (int k = 0; k < 2; k++) { + nlv[k] -= call_kill[k]; + // Midpoint call. + nlv[k] += T.nrsave[k]; + b->nlive[k] = imax(b->nlive[k], nlv[k]); + } + int call_arg[2]; + b->in->t[0] |= T.argregs(i->arg[1], call_arg); + for (int k = 0; k < 2; k++) { + nlv[k] -= T.nrsave[k]; + nlv[k] += call_arg[k]; + } + } + + // def kill. + if (!req(i->to, Ref::none())) { + assert(rtype(i->to) == RTmp); + uint t = i->to.val; + if (bshas(b->in, t)) + nlv[KBASE(fn->tmp[t].cls)]--; + bsset(b->gen, t); + bsclr(b->in, t); + } + + // args gen. + for (int k = 0; k < 2; k++) { + Ref a = i->arg[k]; + if (rtype(a) == RMem) { + Mem* m = &fn->mem[a.val]; + use_ref(m->base, b, nlv, fn->tmp); + use_ref(m->index, b, nlv, fn->tmp); + } else { + use_ref(a, b, nlv, fn->tmp); + } + } + + // Update peak. + for (int k = 0; k < 2; k++) + b->nlive[k] = imax(b->nlive[k], nlv[k]); + } + } + } + + // Debug dump. + if (debug['L']) { + FILE* f = ctx->dbg_buf; + fprintf(f, "\n> Liveness analysis:\n"); + for (Blk* b = fn->start; b; b = b->link) { + fprintf(f, "\t%-10sin: ", b->name); + dumpts(b->in, fn->tmp, f); + fprintf(f, "\t out: "); + dumpts(b->out, fn->tmp, f); + fprintf(f, "\t gen: "); + dumpts(b->gen, fn->tmp, f); + fprintf(f, "\t live: %d %d\n", b->nlive[0], b->nlive[1]); + } + } +} + +} // namespace rcc |