aboutsummaryrefslogtreecommitdiff
path: root/src/backend/rv64/isel.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/rv64/isel.cc')
-rw-r--r--src/backend/rv64/isel.cc518
1 files changed, 518 insertions, 0 deletions
diff --git a/src/backend/rv64/isel.cc b/src/backend/rv64/isel.cc
new file mode 100644
index 0000000..c2ded02
--- /dev/null
+++ b/src/backend/rv64/isel.cc
@@ -0,0 +1,518 @@
+/* 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 isel.cc
+/// @brief RISC-V 64 instruction selection.
+
+#include "rcc/rv64.h"
+
+#include <cinttypes>
+#include <climits>
+#include <cstdio>
+
+namespace rcc {
+namespace {
+
+// Operand role classification.
+
+// is_mem_arg: Does the arg slot pointed to by r have "memory operand" semantics?
+bool is_mem_arg(Ref* r, int op, Ins* i) {
+ if (isload(op) || op == Ocall)
+ return r == &i->arg[0];
+ if (isstore(op))
+ return r == &i->arg[1];
+ return false;
+}
+
+// is_imm_arg: Is r the immediate slot for this op?
+bool is_imm_arg(Ref* r, int op, Ins* i) {
+ return rv64_op[op].imm && r == &i->arg[1];
+}
+
+// Compare op -> (sign, swap, neg) tuple.
+
+struct CmpCfg {
+ uint8_t sign; // 1=signed (Ocsltl), 0=unsigned (Ocultl)
+ uint8_t swap; // 1=swap arg0/arg1
+ uint8_t neg; // 1=negate i.to
+};
+
+constexpr CmpCfg kIntOrderCmp[8] = {
+ /* Cisge */ {1, 0, 1}, // a >= b ⇔ !(a < b)
+ /* Cisgt */ {1, 1, 0}, // a > b ⇔ (b < a)
+ /* Cisle */ {1, 1, 1}, // a <= b ⇔ !(b < a)
+ /* Cislt */ {1, 0, 0}, // a < b
+ /* Ciuge */ {0, 0, 1},
+ /* Ciugt */ {0, 1, 0},
+ /* Ciule */ {0, 1, 1},
+ /* Ciult */ {0, 0, 0},
+};
+
+// Utilities.
+
+// boolean negate: emit `xor pr, src, 1`
+void negate_to(Ctx* ctx, Ref* pr, Fn* fn) {
+ Ref src = newtmp(ctx, "isel", Kw, fn);
+ emit(ctx, Oxor, Kw, *pr, src, getcon(ctx, 1, fn));
+ *pr = src;
+}
+
+// fixarg: operand fixup.
+
+// Fix constant operand.
+void fix_con_arg(Ctx* ctx, Ref* r, int k, Ins* i, int op, Fn* fn) {
+ Con* c = &fn->con[r->val];
+
+ // CAddr as mem operand: no materialization needed.
+ if (c->type == Con::CAddr && is_mem_arg(r, op, i))
+ return;
+
+ // Integer immediate within I-form range.
+ if (KBASE(k) == 0 && c->type == Con::CBits && is_imm_arg(r, op, i)) {
+ if (-2048 <= c->bits.i && c->bits.i < 2048)
+ return;
+ }
+
+ // Integer store value of 0: emit `s* zero, ...` without materialization.
+ if (i && c->type == Con::CBits && c->bits.i == 0 && r == &i->arg[0] &&
+ INRANGE(op, Ostoreb, Ostorel)) {
+ return;
+ }
+
+ Ref dst = newtmp(ctx, "isel", k, fn);
+
+ if (KBASE(k) == 1) {
+ // Floating-point constants must be stashed to ro data section.
+ assert(c->type == Con::CBits);
+ int slot_id = stashbits(ctx, static_cast<bits>(c->bits.i), KWIDE(k) ? 8 : 4);
+
+ vgrow(ctx, &fn->con, static_cast<ulong>(++fn->ncon));
+ Con* nc = &fn->con[fn->ncon - 1];
+ *nc = {};
+ nc->type = Con::CAddr;
+
+ char buf[32];
+ snprintf(buf, sizeof(buf), "\"%sfp%d\"", T.asloc, slot_id);
+ nc->sym.id = intern(buf);
+
+ emit(ctx, Oload, k, dst, Ref::con(static_cast<uint>(nc - fn->con)), Ref::none());
+ } else {
+ // Integer constants out of imm range use Ocopy.
+ emit(ctx, Ocopy, k, dst, *r, Ref::none());
+ }
+
+ *r = dst;
+}
+
+// Operations that do not require sext.w when Kw is input.
+bool skip_sext_for_kw(int op) {
+ switch (op) {
+ // *w-form arithmetic.
+ case Oadd:
+ case Osub:
+ case Omul:
+ case Odiv:
+ case Orem:
+ case Oudiv:
+ case Ourem:
+ case Osar:
+ case Oshr:
+ case Oshl:
+ // Narrow stores.
+ case Ostoreb:
+ case Ostoreh:
+ case Ostorew:
+ // Extensions.
+ case Oextsb:
+ case Oextub:
+ case Oextsh:
+ case Oextuh:
+ case Oextsw:
+ case Oextuw:
+ // int->float conversions.
+ case Oswtof:
+ case Ouwtof:
+ return true;
+ default:
+ return false;
+ }
+}
+
+// Fix temporary operand.
+void fix_tmp_arg(Ctx* ctx, Ref* r, int k, Ins* i, int op, Fn* fn) {
+ if (isreg(*r))
+ return;
+
+ int s = fn->tmp[r->val].slot;
+ if (s != -1) {
+ // Tmp with slot allocated.
+ if (is_mem_arg(r, op, i)) {
+ *r = Ref::slot(s);
+ } else {
+ Ref dst = newtmp(ctx, "isel", k, fn);
+ emit(ctx, Oaddr, k, dst, Ref::slot(s), Ref::none());
+ *r = dst;
+ }
+ return;
+ }
+
+ // Tmp is Kl but used as Kw.
+ if (k == Kw && fn->tmp[r->val].cls == Kl) {
+ if (!skip_sext_for_kw(op)) {
+ Ref dst = newtmp(ctx, "isel", k, fn);
+ emit(ctx, Oextsw, Kl, dst, *r, Ref::none());
+ *r = dst;
+ }
+ // Skip sext.w.
+ return;
+ }
+
+ assert(k == fn->tmp[r->val].cls);
+}
+
+void fixarg(Ctx* ctx, Ref* r, int k, Ins* i, Fn* fn) {
+ int op = i ? static_cast<int>(i->op) : Ocopy;
+ switch (rtype(*r)) {
+ case RCon:
+ fix_con_arg(ctx, r, k, i, op, fn);
+ break;
+ case RTmp:
+ fix_tmp_arg(ctx, r, k, i, op, fn);
+ break;
+ default:
+ // RSlot/RType/RCall/RMem/RInt/RNone don't need fixing.
+ break;
+ }
+}
+
+// Fixarg both operands of the instruction.
+void fixarg2(Ctx* ctx, int k, Fn* fn) {
+ Ins* h = ctx->curi;
+ fixarg(ctx, &h->arg[0], k, h, fn);
+ fixarg(ctx, &h->arg[1], k, h, fn);
+}
+
+// Compare selection.
+
+void selcmp(Ctx* ctx, Ins i, int k, int op, Fn* fn) {
+ assert(op >= 0 && op < NCmp);
+
+ // (1) Integer eq/ne.
+ if (op == Cieq || op == Cine) {
+ Ref r = newtmp(ctx, "isel", k, fn);
+ emit(ctx, op == Cieq ? Oreqz : Ornez, static_cast<int>(i.cls), i.to, r, Ref::none());
+ emit(ctx, Oxor, k, r, i.arg[0], i.arg[1]);
+ fixarg2(ctx, k, fn);
+ return;
+ }
+
+ // (2) Integer ordered comparisons.
+ if (op < NCmpI) {
+ const CmpCfg cfg = kIntOrderCmp[op - Cisge];
+ i.op = static_cast<uint>(cfg.sign ? Ocsltl : Ocultl);
+ if (cfg.swap) {
+ Ref t = i.arg[0];
+ i.arg[0] = i.arg[1];
+ i.arg[1] = t;
+ }
+ if (cfg.neg)
+ negate_to(ctx, &i.to, fn);
+ emiti(ctx, i);
+ fixarg2(ctx, k, fn);
+ return;
+ }
+
+ // (3) Floating point comparisons.
+ int fop = op - NCmpI;
+
+ // Cfo (ordered) / Cfuo (unordered).
+ if (fop == Cfo || fop == Cfuo) {
+ if (fop == Cfuo)
+ negate_to(ctx, &i.to, fn);
+ Ref r0 = newtmp(ctx, "isel", static_cast<int>(i.cls), fn);
+ Ref r1 = newtmp(ctx, "isel", static_cast<int>(i.cls), fn);
+ int ceq_op = KWIDE(k) ? Oceqd : Oceqs;
+ emit(ctx, Oand, static_cast<int>(i.cls), i.to, r0, r1);
+ emit(ctx, ceq_op, static_cast<int>(i.cls), r0, i.arg[0], i.arg[0]);
+ fixarg2(ctx, k, fn);
+ emit(ctx, ceq_op, static_cast<int>(i.cls), r1, i.arg[1], i.arg[1]);
+ fixarg2(ctx, k, fn);
+ return;
+ }
+
+ // Cfne: a != b -> !(a == b).
+ if (fop == Cfne) {
+ i.op = static_cast<uint>(KWIDE(k) ? Oceqd : Oceqs);
+ negate_to(ctx, &i.to, fn);
+ }
+ // Remaining Cfeq/Cfge/Cfgt/Cfle/Cflt.
+
+ emiti(ctx, i);
+ fixarg2(ctx, k, fn);
+}
+
+// Load/store constant offset folding.
+
+Ref new_offset_mem(Ctx* ctx, Fn* fn, Ref base, int64_t off) {
+ vensure(ctx, &fn->mem, static_cast<ulong>(fn->nmem + 1), sizeof(Mem), PFn);
+ Mem* m = &fn->mem[fn->nmem];
+ *m = {};
+ m->offset.type = Con::CBits;
+ m->offset.bits.i = off;
+ m->base = base;
+ m->index = Ref::none();
+ m->scale = 1;
+ return Ref::mem(static_cast<uint>(fn->nmem++));
+}
+
+// Reverse fold Oaddr -> CAddr.
+[[maybe_unused]] void fold_addr_into_mem(Ctx* ctx, Ref* paddr, uint bid, Fn* fn) {
+ if (rtype(*paddr) == RTmp) {
+ Tmp* t = &fn->tmp[paddr->val];
+ Ins* def = t->def;
+ if (!def || static_cast<int>(def->op) != Oaddr)
+ return;
+ if (t->nuse != 1 || t->bid != bid)
+ return;
+ if (rtype(def->arg[0]) != RCon)
+ return;
+ Con* c = &fn->con[def->arg[0].val];
+ if (c->type != Con::CAddr)
+ return;
+ *paddr = def->arg[0];
+ def->op = Onop;
+ return;
+ }
+ if (rtype(*paddr) == RMem) {
+ Mem* m = &fn->mem[paddr->val];
+ if (rtype(m->base) != RTmp)
+ return;
+ if (!req(m->index, Ref::none()))
+ return;
+ if (m->offset.type != Con::CBits)
+ return;
+ Tmp* t = &fn->tmp[m->base.val];
+ Ins* def = t->def;
+ if (!def || static_cast<int>(def->op) != Oaddr)
+ return;
+ if (t->nuse != 1 || t->bid != bid)
+ return;
+ if (rtype(def->arg[0]) != RCon)
+ return;
+ Con* c = &fn->con[def->arg[0].val];
+ if (c->type != Con::CAddr)
+ return;
+ // Create new CAddr combining bits.
+ vgrow(ctx, &fn->con, static_cast<ulong>(fn->ncon + 1));
+ Con* nc = &fn->con[fn->ncon];
+ *nc = *c;
+ nc->bits.i = c->bits.i + m->offset.bits.i;
+ uint cidx = static_cast<uint>(fn->ncon++);
+ *paddr = Ref::con(cidx);
+ def->op = Onop;
+ return;
+ }
+}
+
+void fold_mem_offset(Ctx* ctx, Ref* paddr, uint bid, Fn* fn) {
+ if (rtype(*paddr) != RTmp)
+ return;
+ Tmp* t = &fn->tmp[paddr->val];
+ Ins* def = t->def;
+ if (!def || static_cast<int>(def->op) != Oadd || static_cast<int>(def->cls) != Kl)
+ return;
+ if (t->nuse != 1 || t->bid != bid)
+ return;
+
+ // Oadd is commutative.
+ Ref base, koff;
+ if (rtype(def->arg[0]) == RTmp && rtype(def->arg[1]) == RCon) {
+ base = def->arg[0];
+ koff = def->arg[1];
+ } else if (rtype(def->arg[0]) == RCon && rtype(def->arg[1]) == RTmp) {
+ base = def->arg[1];
+ koff = def->arg[0];
+ } else {
+ return;
+ }
+
+ Con* c = &fn->con[koff.val];
+ if (c->type != Con::CBits)
+ return;
+ int64_t off = c->bits.i;
+ if (off < -2048 || off > 2047)
+ return;
+
+ // base must be a normal tmp (value is address).
+ if (fn->tmp[base.val].slot != -1)
+ return;
+
+ *paddr = new_offset_mem(ctx, fn, base, off);
+ def->op = Onop;
+}
+
+// Single instruction selection.
+
+void sel(Ctx* ctx, Ins i, Blk* b, Fn* fn) {
+ // Oalloc{4,8,16} non-constant sizes.
+ if (INRANGE(i.op, Oalloc, Oalloc1)) {
+ Ins* head = ctx->curi - 1;
+ salloc(ctx, i.to, i.arg[0], fn);
+ fixarg(ctx, &head->arg[0], Kl, head, fn);
+ return;
+ }
+
+ int ck, cc;
+ if (iscmp(static_cast<int>(i.op), &ck, &cc)) {
+ selcmp(ctx, i, ck, cc, fn);
+ return;
+ }
+
+ // Consume Onop.
+ if (i.op == Onop)
+ return;
+
+ // Oaddr from IRGen.
+ if (i.op == Oaddr) {
+ emiti(ctx, i);
+ return;
+ }
+
+ // Load/store constant offset folding.
+ int op = static_cast<int>(i.op);
+ Ref* paddr = nullptr;
+ if (isload(op))
+ paddr = &i.arg[0];
+ else if (isstore(op))
+ paddr = &i.arg[1];
+ if (paddr) {
+ fold_mem_offset(ctx, paddr, b->id, fn);
+ }
+
+ emiti(ctx, i);
+ Ins* h = ctx->curi; // capture head.
+ fixarg(ctx, &h->arg[0], argcls(&i, 0), h, fn);
+ fixarg(ctx, &h->arg[1], argcls(&i, 1), h, fn);
+}
+
+// Jump selection.
+
+// cmp+jnz fusion.
+inline short cmp_to_jjfi(int cc) {
+ assert(cc >= 0 && cc < NCmpI);
+ return static_cast<short>(Jjfieq + cc);
+}
+
+void seljmp(Ctx* ctx, Blk* b, Fn* fn) {
+ if (b->jmp.type != Jjnz)
+ return;
+
+ if (rtype(b->jmp.arg) == RTmp) {
+ Tmp* t = &fn->tmp[b->jmp.arg.val];
+ Ins* def = t->def;
+ if (t->nuse == 1 && def && t->bid == b->id) {
+ int ck, cc;
+ if (iscmp(static_cast<int>(def->op), &ck, &cc) && cc < NCmpI) {
+ b->jmp.type = cmp_to_jjfi(cc);
+ b->jmp.cls = static_cast<short>(ck);
+ b->jmp.arg = def->arg[0];
+ b->jmp.arg2 = def->arg[1];
+ def->op = Onop;
+ fixarg(ctx, &b->jmp.arg, ck, nullptr, fn);
+ fixarg(ctx, &b->jmp.arg2, ck, nullptr, fn);
+ return;
+ }
+ }
+ }
+ fixarg(ctx, &b->jmp.arg, Kw, nullptr, fn);
+}
+
+// Pass A: fast alloc -> slot.
+
+void assign_fast_alloc_slots(Fn* fn) {
+ Blk* b = fn->start;
+
+ int align_bytes = 4;
+ for (int op = Oalloc; op <= Oalloc1; ++op, align_bytes *= 2) {
+ Ins* ie = b->ins + b->nins;
+ for (Ins* i = b->ins; i < ie; ++i) {
+ if (static_cast<int>(i->op) != op)
+ continue;
+ if (rtype(i->arg[0]) != RCon)
+ continue;
+
+ int64_t sz = fn->con[i->arg[0].val].bits.i;
+ if (sz < 0 || sz >= INT_MAX - 15)
+ err(const_cast<char*>("invalid alloc size %" PRId64), sz);
+
+ sz = (sz + align_bytes - 1) & -align_bytes;
+ sz /= 4;
+ if (sz > INT_MAX - fn->slot)
+ die("alloc too large");
+
+ fn->tmp[i->to.val].slot = fn->slot;
+ fn->slot += static_cast<int>(sz);
+
+ *i = Ins{};
+ i->op = Onop;
+ }
+ }
+}
+
+} // namespace
+
+// rv64_isel: Main entry point.
+
+void rv64_isel(Ctx* ctx, Fn* fn) {
+ assign_fast_alloc_slots(fn);
+
+ for (Blk* b = fn->start; b; b = b->link) {
+ ctx->curi = ctx->insb + NIns;
+
+ // Phi nodes of successors.
+ Blk* succ[3] = {b->s1, b->s2, nullptr};
+ for (Blk** ps = succ; *ps; ++ps) {
+ for (Phi* p = (*ps)->phi; p; p = p->link) {
+ uint n = 0;
+ while (p->blk[n] != b) {
+ ++n;
+ assert(n < p->narg);
+ }
+ fixarg(ctx, &p->arg[n], static_cast<int>(p->cls), nullptr, fn);
+ }
+ }
+
+ seljmp(ctx, b, fn);
+
+ // Reverse iteration for emit prepending.
+ for (Ins* i = b->ins + b->nins; i != b->ins;) {
+ --i;
+ sel(ctx, *i, b, fn);
+ }
+
+ idup(ctx, b, ctx->curi, static_cast<ulong>(ctx->insb + NIns - ctx->curi));
+ }
+
+ if (debug['I']) {
+ fprintf(ctx->dbg_buf, "\n> After instruction selection:\n");
+ printfn(fn, ctx->dbg_buf);
+ }
+}
+
+} // namespace rcc
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 02:56:16 +0000