diff options
Diffstat (limited to 'src/mid/alias.cc')
| -rw-r--r-- | src/mid/alias.cc | 445 |
1 files changed, 445 insertions, 0 deletions
diff --git a/src/mid/alias.cc b/src/mid/alias.cc new file mode 100644 index 0000000..8dc6041 --- /dev/null +++ b/src/mid/alias.cc @@ -0,0 +1,445 @@ +/* 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 alias.cc +/// @brief Alias analysis: computes a conservative Alias descriptor for each tmp, serving downstream +/// load/mem optimizations. +/// +/// See docs/alias.md for architectural notes. + +#include "rcc/all.h" + +#include <cstring> + +namespace rcc { + +void getalias(Alias* a, Ref r, Fn* fn) { + switch (rtype(r)) { + case RTmp: + *a = fn->tmp[r.val].alias; + // astack: follow to root slot to get latest type (slot might have been upgraded to AEsc + // by esc()) + if (astack(a->type)) + a->type = a->slot->type; + assert(a->type != Alias::ABot); + return; + case RCon: { + Con* c = &fn->con[r.val]; + if (c->type == Con::CAddr) { + a->type = Alias::ASym; + a->u.sym = c->sym; + } else { + a->type = Alias::ACon; + } + a->offset = c->bits.i; + a->offset_unknown = false; + a->slot = nullptr; + a->base = 0; + return; + } + default: + die("getalias: unreachable ref kind"); + } +} + +int alias(Ref p, int op, int sp, Ref q, int sq, int* delta, Fn* fn) { + Alias ap, aq; + getalias(&ap, p, fn); + getalias(&aq, q, fn); + ap.offset += op; + + // sp, sq are guaranteed by caller to be <= 2^28, offset difference won't overflow int + *delta = static_cast<int>(ap.offset - aq.offset); + bool ovlap = ap.offset < aq.offset + sq && aq.offset < ap.offset + sp; + // When offset_unknown, overlap is untrustworthy, all "same base + overlap" judgements must + // degrade + bool ovlap_known = !ap.offset_unknown && !aq.offset_unknown; + + bool p_stack = astack(ap.type); + bool q_stack = astack(aq.type); + + if (p_stack && q_stack) + return (ap.base == aq.base && ovlap) ? MustAlias : NoAlias; + + if (ap.type == Alias::ASym && aq.type == Alias::ASym) { + if (!symeq(ap.u.sym, aq.u.sym)) + return NoAlias; + if (!ovlap_known) + return MayAlias; + return ovlap ? MustAlias : NoAlias; + } + + bool both_con = (ap.type == Alias::ACon && aq.type == Alias::ACon); + bool same_base = (ap.type == aq.type && ap.base == aq.base); + if (both_con || same_base) { + assert(ap.type == Alias::ACon || ap.type == Alias::AUnk); + if (!ovlap_known) + return MayAlias; + return ovlap ? MustAlias : NoAlias; + } + + if (ap.type == Alias::AUnk && aq.type != Alias::ALoc) + return MayAlias; + if (aq.type == Alias::AUnk && ap.type != Alias::ALoc) + return MayAlias; + + return NoAlias; +} + +int escapes(Ref r, Fn* fn) { + if (rtype(r) != RTmp) + return 1; + Alias* a = &fn->tmp[r.val].alias; + // astack and slot is still ALoc -> didn't escape; otherwise (not astack or slot is AEsc) it + // escapes + return !astack(a->type) || a->slot->type == Alias::AEsc; +} + +namespace { + +void esc(Ref r, Fn* fn) { + assert(rtype(r) <= RType); + if (rtype(r) != RTmp) + return; + Alias* a = &fn->tmp[r.val].alias; + if (astack(a->type)) + a->slot->type = Alias::AEsc; +} + +void store(Ref r, int sz, Fn* fn) { + if (rtype(r) != RTmp) + return; + Alias* a = &fn->tmp[r.val].alias; + if (!a->slot) + return; + assert(astack(a->type)); + int64_t off = a->offset; + bits m; + if (sz >= static_cast<int>(NBit) || off < 0 || off >= static_cast<int64_t>(NBit)) + m = static_cast<bits>(-1); + else + m = (BIT(sz) - 1) << off; + a->slot->u.loc.m |= m; +} + +bool getalias_safe(Alias* a, Ref r, Fn* fn) { + switch (rtype(r)) { + case RTmp: + *a = fn->tmp[r.val].alias; + if (a->type == Alias::ABot) + return false; + if (astack(a->type)) + a->type = a->slot->type; + return true; + case RCon: { + Con* c = &fn->con[r.val]; + if (c->type == Con::CAddr) { + a->type = Alias::ASym; + a->u.sym = c->sym; + } else { + a->type = Alias::ACon; + } + a->offset = c->bits.i; + a->offset_unknown = false; + a->slot = nullptr; + a->base = 0; + return true; + } + default: + die("getalias_safe: unreachable ref kind"); + } +} + +bool alias_eq(const Alias& a, const Alias& b) { + if (a.type != b.type) + return false; + if (a.offset != b.offset) + return false; + if (a.offset_unknown != b.offset_unknown) + return false; + if (a.slot != b.slot) + return false; + if (a.base != b.base) + return false; + if (a.type == Alias::ASym) { + if (a.u.sym.type != b.u.sym.type) + return false; + if (a.u.sym.id != b.u.sym.id) + return false; + } else if (astack(a.type)) { + if (a.u.loc.sz != b.u.loc.sz) + return false; + if (a.u.loc.m != b.u.loc.m) + return false; + } + return true; +} + +bool alias_meet(Alias* a, const Alias& b) { + Alias old = *a; + + if (a->type == Alias::ABot) { + *a = b; + } else if (b.type == Alias::ABot) { + // Unchanged + } else { + // Same type + same identity: offset compatible + bool same_id = false; + if (a->type == b.type) { + if (astack(a->type)) + same_id = (a->slot == b.slot); + else if (a->type == Alias::ASym) + same_id = symeq(a->u.sym, b.u.sym); + else if (a->type == Alias::ACon) + same_id = true; // ACon has no base/sym, purely based on offset + else if (a->type == Alias::AUnk) + same_id = (a->base == b.base); + } + if (same_id) { + // ASym path legitimately accepts offset_unknown; ALoc/AEsc do not (store-mask + // assumes offset is known), degrade to AUnk on offset mismatch. + bool both_offset_known = !a->offset_unknown && !b.offset_unknown; + bool offset_match = both_offset_known && a->offset == b.offset; + if (astack(a->type) && !offset_match) { + a->type = Alias::AUnk; + a->slot = nullptr; + a->offset = 0; + a->offset_unknown = false; + // base fixed by caller + } else { + if (!offset_match) + a->offset_unknown = true; + } + } else { + // Type or identity mismatch -> AUnk + a->type = Alias::AUnk; + a->slot = nullptr; + a->offset = 0; + a->offset_unknown = false; + // base fixed by caller + } + } + + return !alias_eq(*a, old); +} + +bool compute_phi(Phi* p, Fn* fn) { + assert(rtype(p->to) == RTmp); + Alias* a = &fn->tmp[p->to.val].alias; + Alias old = *a; + + Alias acc; + std::memset(&acc, 0, sizeof acc); + acc.type = Alias::ABot; + + for (uint k = 0; k < p->narg; k++) { + Alias arg; + if (!getalias_safe(&arg, p->arg[k], fn)) + continue; // This arg is still ABot, skip and wait for next round + alias_meet(&acc, arg); + } + + if (acc.type == Alias::ABot) { + // All args still ABot: retain ABot, doesn't count as change + return false; + } + + // If meet degrades to AUnk, set base to phi's own tmp id (uniqueness, avoids sharing base with + // other AUnks) + if (acc.type == Alias::AUnk) + acc.base = p->to.val; + + if (!alias_eq(*a, acc)) { + *a = acc; + return true; + } + (void)old; + return false; +} + +struct InsResult { + bool consumed_next; + bool changed; +}; + +InsResult process_ins(Ins* i, Ins* end, Fn* fn) { + InsResult res{false, false}; + Alias* a = nullptr; + Alias old; + bool has_def = !req(i->to, Ref::none()); + + if (has_def) { + assert(rtype(i->to) == RTmp); + a = &fn->tmp[i->to.val].alias; + old = *a; + + if (isalloc(i->op)) { + // alloc: install only on first time (ABot), afterwards type might upgrade to AEsc via + // esc, but slot pointer, loc.sz, loc.m must be preserved (loc.m accumulates with OR + // across rounds). + if (a->type == Alias::ABot) { + a->type = Alias::ALoc; + a->slot = a; // Self reference = this tmp is the root slot + a->u.loc.sz = -1; // Unknown size placeholder + a->u.loc.m = 0; + if (rtype(i->arg[0]) == RCon) { + Con* c = &fn->con[i->arg[0].val]; + int64_t x = c->bits.i; + if (c->type == Con::CBits && 0 <= x && x <= static_cast<int64_t>(NBit)) + a->u.loc.sz = static_cast<int>(x); + } + a->base = i->to.val; + a->offset = 0; + a->offset_unknown = false; + } + } else if (i->op == Ocopy || i->op == Oaddr) { + // Oaddr passes through alias: IRGen wraps `$sym` as `%t = addr $sym`, here + // we must propagate ASym identity from RCon CAddr to %t, otherwise alias() sees + // load/store addr as AUnk Tmp, losing "different globals don't alias". + Alias src; + if (getalias_safe(&src, i->arg[0], fn)) { + *a = src; + } + // src still ABot: don't touch *a, wait for next round + } else if (i->op == Oadd) { + Alias a0, a1; + bool ok0 = getalias_safe(&a0, i->arg[0], fn); + bool ok1 = getalias_safe(&a1, i->arg[1], fn); + if (ok0 && ok1) { + Alias newval; + std::memset(&newval, 0, sizeof newval); + newval.type = Alias::AUnk; // Default + newval.base = i->to.val; + + if (a0.type == Alias::ACon) { + newval = a1; + newval.offset += a0.offset; + } else if (a1.type == Alias::ACon) { + newval = a0; + newval.offset += a1.offset; + } else if (a0.type == Alias::ASym) { + newval = a0; + newval.offset_unknown = true; + } else if (a1.type == Alias::ASym) { + newval = a1; + newval.offset_unknown = true; + } + // Both are neither ACon nor ASym -> keep default AUnk + *a = newval; + } + // Any operand still ABot: don't touch *a, wait for next round + } else { + // Other ops: def is always AUnk, one-time init + if (a->type == Alias::ABot) { + a->type = Alias::AUnk; + a->slot = nullptr; + a->base = i->to.val; + a->offset = 0; + a->offset_unknown = false; + } + } + + if (!alias_eq(*a, old)) + res.changed = true; + } + + // 3. esc mark: when no def or def is already AUnk, arg is treated as escaping local + // abstraction. + // Skip on ABot -- def undetermined, decide next round. + // Multiple iterations: esc is monotonically accumulated (slot type one-way ALoc->AEsc), + // idempotent. + bool def_known_unk = has_def && a->type == Alias::AUnk; + if (!has_def || def_known_unk) { + if (i->op != Oblit0) { + if (!isload(i->op)) + esc(i->arg[0], fn); + if (!isstore(i->op) && i->op != Oargc) + esc(i->arg[1], fn); + } + } + + // 4. Memory write accounting: Oblit0/Oblit1 pair / normal store (multiple rounds OR accumulate + // idempotent) + if (i->op == Oblit0) { + Ins* i1 = i + 1; + assert(i1 < end && i1->op == Oblit1); + (void)end; + assert(rtype(i1->arg[0]) == RInt); + int sz = std::abs(rsval(i1->arg[0])); + store(i->arg[1], sz, fn); + res.consumed_next = true; + } + if (isstore(i->op)) + store(i->arg[1], storesz(i), fn); + + return res; +} + +void escape_phi_args(Fn* fn) { + for (Blk* b = fn->start; b; b = b->link) + for (Phi* p = b->phi; p; p = p->link) + for (uint n = 0; n < p->narg; n++) + esc(p->arg[n], fn); +} + +} // namespace + +void fillalias(Fn* fn) { + for (int t = 0; t < fn->ntmp; t++) { + std::memset(&fn->tmp[t].alias, 0, sizeof(Alias)); + fn->tmp[t].alias.type = Alias::ABot; + } + + int iter = 0; + bool changed = true; + for (; iter < 16 && changed; ++iter) { + changed = false; + for (uint n = 0; n < fn->nblk; ++n) { + Blk* b = fn->rpo[n]; + for (Phi* p = b->phi; p; p = p->link) + if (compute_phi(p, fn)) + changed = true; + for (Ins* i = b->ins; i < &b->ins[b->nins];) { + InsResult r = process_ins(i, &b->ins[b->nins], fn); + if (r.changed) + changed = true; + i += r.consumed_next ? 2 : 1; + } + // Block tail jump arg considered escaped (Jretc exception: ret-by-copy pointer doesn't + // escape). Multiple rounds esc idempotent. + if (b->jmp.type != Jretc) + esc(b->jmp.arg, fn); + } + } + + for (int t = 0; t < fn->ntmp; t++) { + Alias* a = &fn->tmp[t].alias; + if (a->type == Alias::ABot) { + a->type = Alias::AUnk; + a->base = t; + a->offset = 0; + a->offset_unknown = false; + a->slot = nullptr; + } + } + + escape_phi_args(fn); +} + +} // namespace rcc |