commit c6baf36fafe141c1625be8f320347b9ab92b8b88
parent b1950955c39e11f77ff7b1c0ad2987ec0dc4c49d
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 23:05:41 -0700
opt: local frame-address sub-CSE at O1 (O1.md W1a)
Diffstat:
3 files changed, 181 insertions(+), 1 deletion(-)
diff --git a/mk/test.mk b/mk/test.mk
@@ -859,7 +859,7 @@ test-macho: lib $(TEST_RT_DEP) $(ROUNDTRIP_BIN_MACHO) $(LINK_EXE_RUNNER) $(JIT_R
OPT_TEST_BIN = build/test/cg_ir_lower_test
TINY_INLINE_TEST_BIN = build/test/tiny_inline_test
-test-opt: bin $(OPT_TEST_BIN) test-opt-tiny-inline test-opt-inline test-opt-zero-arg test-opt-static-prune-aa64 test-opt-aa64-tail test-opt-x64-win-tail-sret test-opt-prologue-tier test-opt-whole-program-inline test-opt-lto-phase1 test-opt-redundant-copy-ext
+test-opt: bin $(OPT_TEST_BIN) test-opt-tiny-inline test-opt-inline test-opt-zero-arg test-opt-static-prune-aa64 test-opt-aa64-tail test-opt-x64-win-tail-sret test-opt-prologue-tier test-opt-whole-program-inline test-opt-lto-phase1 test-opt-redundant-copy-ext test-opt-redundant-frame-sub
$(OPT_TEST_BIN)
@@ -869,6 +869,12 @@ test-opt: bin $(OPT_TEST_BIN) test-opt-tiny-inline test-opt-inline test-opt-zero
test-opt-redundant-copy-ext: bin
@KIT=$(abspath $(BIN)) bash test/opt/redundant_copy_ext.sh
+# Structural disasm check: the -O1 local frame-address sub-CSE (a back-to-back
+# rebuild of the same frame/GOT address is dropped while the holder is live).
+.PHONY: test-opt-redundant-frame-sub
+test-opt-redundant-frame-sub: bin
+ @KIT=$(abspath $(BIN)) bash test/opt/redundant_frame_sub.sh
+
test-opt-tiny-inline: bin $(TINY_INLINE_TEST_BIN)
$(TINY_INLINE_TEST_BIN)
diff --git a/src/opt/pass_combine.c b/src/opt/pass_combine.c
@@ -379,6 +379,20 @@ static int combine_subst_slot(const Inst* in, u32 idx, SubstKind kind,
/* ---- per-BB tracking context ---- */
+/* W1a (O1.md): local frame-address `sub`-CSE. A bounded ring of the most
+ * recently produced frame-/global-address values in this BB so a back-to-back
+ * `IR_ADDR_OF rD, <same addr>` recompute (which lowers to a re-`sub xN,x29,#k`
+ * frame build, or an `adrp;add`/GOT global build) can be rewritten to an
+ * `IR_COPY` off the still-live earlier producer. Bounded slot count keeps the
+ * scan O(1) per inst → the pass stays linear. */
+enum { COMBINE_ADDR_CSE_SLOTS = 8 };
+
+typedef struct AddrCseEntry {
+ i32 inst_idx; /* producing IR_ADDR_OF index in this BB, -1 if empty */
+ Operand dst; /* the produced address register (OPK_REG) */
+ Operand addr; /* the address operand (OPK_LOCAL / OPK_GLOBAL) */
+} AddrCseEntry;
+
typedef struct CombineCtx {
Func* f;
Block* bl;
@@ -387,12 +401,18 @@ typedef struct CombineCtx {
* -1 means no definition seen this BB. */
i32 last_def[OPT_REG_CLASSES][OPT_MAX_HARD_REGS];
i32 last_mem_def;
+ /* W1a addr-of CSE ring (most-recent-wins). */
+ AddrCseEntry addr_cse[COMBINE_ADDR_CSE_SLOTS];
+ u32 addr_cse_next;
int block_change_p;
} CombineCtx;
static void ctx_reset(CombineCtx* ctx) {
memset(ctx->last_def, 0xff, sizeof ctx->last_def); /* all -1 */
ctx->last_mem_def = -1;
+ for (u32 k = 0; k < COMBINE_ADDR_CSE_SLOTS; ++k)
+ ctx->addr_cse[k].inst_idx = -1;
+ ctx->addr_cse_next = 0;
ctx->block_change_p = 0;
}
@@ -1254,6 +1274,77 @@ static int try_combine_exts(CombineCtx* ctx, Inst* in, i32 i) {
return 0;
}
+/* ---- Rewrite 6 (W1a): local frame-address `sub`-CSE ----
+ *
+ * O1.md W1a. An `IR_ADDR_OF rD, <addr>` materializes a frame-slot or global
+ * address into a register; on aa64 that is a `sub xN,x29,#k` (frame) or an
+ * `adrp;add`/GOT build (global), on rv64 a `lui;…;add`. A back-to-back
+ * `IR_ADDR_OF` of the *same* address operand recomputes the identical value.
+ * While an earlier producer register is unclobbered, rewrite the recompute to
+ * an `IR_COPY` off it (copy-prop + DCE retire it; worst case it is a same-cost
+ * register move). The address sources are immutable — a frame slot's offset and
+ * a global sym+addend never change — so no source-availability check beyond the
+ * producer register being unclobbered is required.
+ *
+ * Bounded per-BB ring (COMBINE_ADDR_CSE_SLOTS) → O(1) per inst → linear.
+ * Deliberately minimal: W1.1 (positive far-slot layout) subsumes the spill
+ * far-slot case; this PR stands up the gate + structural guard and mops up the
+ * `&local` / global recompute residual. */
+
+/* Two address operands name the same address iff same kind and same payload. */
+static int same_addr_operand(const Operand* a, const Operand* b) {
+ if (a->kind != b->kind) return 0;
+ switch (a->kind) {
+ case OPK_LOCAL:
+ return a->v.frame_slot == b->v.frame_slot;
+ case OPK_GLOBAL:
+ return a->v.global.sym == b->v.global.sym &&
+ a->v.global.addend == b->v.global.addend;
+ default:
+ return 0;
+ }
+}
+
+/* Is this an addr-of whose address is a CSE-able immutable frame/global ref? */
+static int addr_of_is_cseable(const Inst* in) {
+ if ((IROp)in->op != IR_ADDR_OF || in->nopnds < 2) return 0;
+ if (in->opnds[0].kind != OPK_REG) return 0;
+ return in->opnds[1].kind == OPK_LOCAL || in->opnds[1].kind == OPK_GLOBAL;
+}
+
+static void addr_cse_record(CombineCtx* ctx, const Inst* in, i32 i) {
+ if (!addr_of_is_cseable(in)) return;
+ AddrCseEntry* e = &ctx->addr_cse[ctx->addr_cse_next];
+ e->inst_idx = i;
+ e->dst = in->opnds[0];
+ e->addr = in->opnds[1];
+ ctx->addr_cse_next = (ctx->addr_cse_next + 1u) % COMBINE_ADDR_CSE_SLOTS;
+}
+
+static int try_addr_of_cse(CombineCtx* ctx, Inst* in, i32 i) {
+ if (!addr_of_is_cseable(in)) return 0;
+ const Operand* addr = &in->opnds[1];
+ for (u32 k = 0; k < COMBINE_ADDR_CSE_SLOTS; ++k) {
+ const AddrCseEntry* e = &ctx->addr_cse[k];
+ if (e->inst_idx < 0 || e->inst_idx >= i) continue;
+ if (!same_addr_operand(&e->addr, addr)) continue;
+ /* The producer register must still hold the address: it is this BB's live
+ * producer of (cls,reg) and was not redefined/clobbered since. */
+ if (ctx_producer_of(ctx, e->dst.cls, e->dst.v.reg) != e->inst_idx) continue;
+ if (ctx_def_changed_since(ctx, e->dst.cls, e->dst.v.reg, e->inst_idx))
+ continue;
+ /* A copy of the producer reg into self is a no-op the dst already holds. */
+ if (same_phys_reg(&in->opnds[0], &e->dst)) continue;
+ /* Rewrite `addr_of rD, <addr>` into `copy rD, rP`. */
+ in->op = (u16)IR_COPY;
+ in->opnds[1] = e->dst;
+ in->nopnds = 2;
+ ctx->block_change_p = 1;
+ return 1;
+ }
+ return 0;
+}
+
/* ---- Existing IR_RET retarget (kept; runs in the forward pass) ---- */
static int try_ret_retarget(Func* f, Block* bl, i32 i) {
@@ -1387,12 +1478,18 @@ static int opt_combine_fold_block(Func* f, Block* bl,
}
if (enable_o1_combine_rewrites) {
+ /* W1a addr-of CSE first: if it rewrites the addr_of into a copy, record
+ * it as an ordinary reg def (not as an addr-of producer) below. */
+ try_addr_of_cse(&ctx, in, i);
try_fold_const_convert(&ctx, in, i);
try_combine_exts(&ctx, in, i);
try_substitute(&ctx, in, i);
try_addr_synth(&ctx, in, i);
}
+ /* Track this inst as an addr-of producer for later W1a CSE (only when it is
+ * still an addr-of: a prior rewrite may have turned it into a copy). */
+ addr_cse_record(&ctx, in, i);
ctx_record(&ctx, in, i);
}
return ctx.block_change_p;
diff --git a/test/opt/redundant_frame_sub.sh b/test/opt/redundant_frame_sub.sh
@@ -0,0 +1,77 @@
+#!/usr/bin/env bash
+# Structural check for the -O1 local frame-address `sub`-CSE (O1.md W1a).
+#
+# An `IR_ADDR_OF` of a frame-local materializes a frame-slot address into a
+# register; on aarch64 that lowers to `sub xN, x29, #k` (the offset built off the
+# frame base). Two back-to-back addr-of's of the *same* local recompute the
+# identical `sub xN, x29, #k`. The W1a peephole in src/opt/pass_combine.c
+# (mir_combine) tracks the still-live earlier producer and rewrites the
+# recompute into a register move (`mov xN, xM`), so the second `sub` vanishes.
+#
+# This pins the resulting disassembly on aarch64 (the reference backend), where
+# the pattern has a stable mnemonic. Each local is addressed twice as adjacent
+# call arguments; with the peephole only ONE `sub xN, x29, #k` survives per
+# distinct constant K, and the duplicate becomes a `mov`.
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "$0")/../.." && pwd)"
+KIT="${KIT:-$ROOT/build/kit}"
+WORK="$ROOT/build/test/opt/redundant_frame_sub"
+mkdir -p "$WORK"
+
+SRC="$WORK/case.c"
+cat > "$SRC" <<'EOF'
+extern void sink4(char *, char *, char *, char *);
+/* Two distinct locals at frame offsets past stur's -256 range; each is passed
+ * twice as adjacent arguments, so the frontend records two IR_ADDR_OF of the
+ * same slot back-to-back. Without W1a each lowers to its own `sub xN,x29,#k`. */
+void g(void) {
+ char a[600], b[600];
+ sink4(a, a, b, b);
+}
+EOF
+
+OBJ="$WORK/case.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC" \
+ -o "$OBJ" > "$WORK/cc.out" 2>&1
+"$KIT" objdump -d "$OBJ" > "$WORK/dis.out" 2>&1
+
+fn_body() { # $1 = symbol name -> stdout body
+ awk -v want="$1" '
+ $0 ~ ("^[0-9a-f]+ <" want ">:") { in_fn = 1; next }
+ /^[0-9a-f]+ </ { in_fn = 0 }
+ in_fn { print }
+ ' "$WORK/dis.out"
+}
+
+fail() {
+ printf 'redundant_frame_sub FAILED: %s\n' "$1" >&2
+ printf ' --- disassembly ---\n' >&2
+ sed 's/^/ | /' "$WORK/dis.out" >&2
+ exit 1
+}
+
+B="$(fn_body _g)"
+[ -n "$B" ] || B="$(fn_body g)"
+[ -n "$B" ] || fail "g not found in disassembly"
+
+# For each distinct constant K appearing in `sub xN, x29, #K`, the address is
+# built exactly once; a back-to-back recompute of the same K must NOT survive.
+# Collect the K constants and assert no duplicates.
+KS="$(printf '%s\n' "$B" | grep -oE 'sub[[:space:]]+x[0-9]+, x29, #[0-9]+' \
+ | grep -oE '#[0-9]+$' | sort)"
+[ -n "$KS" ] || fail "expected at least one 'sub xN, x29, #k' frame-address build"
+
+DUP="$(printf '%s\n' "$KS" | uniq -d || true)"
+if [ -n "$DUP" ]; then
+ fail "duplicate frame-address build survived (sub xN, x29, #k recomputed for: $DUP)"
+fi
+
+# Sanity: the de-duplicated address must be reused via a register move, so the
+# body should contain at least one `mov xN, xM` (the CSE'd copy) — confirms the
+# peephole rewrote the recompute rather than the case simply not arising.
+if ! printf '%s\n' "$B" | grep -Eq 'mov[[:space:]]+x[0-9]+, x[0-9]+'; then
+ fail "expected a 'mov xN, xM' reusing the CSE'd frame address"
+fi
+
+printf 'redundant_frame_sub: OK (no duplicate sub xN,x29,#k; address reused via mov)\n'
