commit 9f3f9a01597ac46d82d5c3369e4c5851a43b57eb
parent 6f4cd59a6b440abffd17633fbccf372962005789
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Mon, 15 Jun 2026 23:54:57 -0700
opt: switch-chain immediate compares at O1 (O1.md W7)
Diffstat:
3 files changed, 172 insertions(+), 5 deletions(-)
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-redundant-frame-sub test-opt-o1-branch-cleanup test-opt-hot-slot-order test-opt-o1-remat test-opt-aa64-x29-bottom test-opt-o1-coalesce
+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 test-opt-o1-branch-cleanup test-opt-hot-slot-order test-opt-o1-remat test-opt-aa64-x29-bottom test-opt-o1-coalesce test-opt-o1-switch-imm
$(OPT_TEST_BIN)
@@ -905,6 +905,12 @@ test-opt-aa64-x29-bottom: bin
test-opt-o1-coalesce: bin
@KIT=$(abspath $(BIN)) bash test/opt/o1_coalesce.sh
+# Structural disasm check: O1 switch chains compare case values as immediates
+# (cmp wN,#k) instead of materializing each into a scratch; selector stays pinned.
+.PHONY: test-opt-o1-switch-imm
+test-opt-o1-switch-imm: bin
+ @KIT=$(abspath $(BIN)) bash test/opt/o1_switch_imm.sh
+
test-opt-tiny-inline: bin $(TINY_INLINE_TEST_BIN)
$(TINY_INLINE_TEST_BIN)
diff --git a/src/opt/pass_native_emit.c b/src/opt/pass_native_emit.c
@@ -1027,15 +1027,29 @@ static void emit_inst(NativeEmitCtx* e, u32 block, u32 order_index, Inst* in,
}
case IR_SWITCH: {
IRSwitchAux* aux = (IRSwitchAux*)in->extra.aux;
+ /* Pin the selector in a register ONCE before the chain. */
NativeLoc sel =
materialize(e, loc_from_operand(e, &in->opnds[0], in->loc),
class_for_type(e, in->opnds[0].type), in->opnds[0].type,
REG_NONE, REG_NONE, in->loc);
- NativeLoc imm =
- scratch_loc(e, in->opnds[0].type, (NativeAllocClass)sel.cls,
- sel.v.reg, REG_NONE, in->loc);
+ /* Each case value is interpreted at the selector type (matches the CG
+ * fallback chain in cg/native_direct_target.c). Route each through the
+ * same NATIVE_IMM_CMP immediate-or-register logic IR_CMP_BRANCH uses, so
+ * a legal compare immediate becomes `cmp sel, #k` with no per-case
+ * materialization; an illegal immediate (e.g. too large for the target's
+ * compare encoding) falls back to load_imm into a scratch that avoids the
+ * pinned selector register. */
+ KitCgTypeId case_type =
+ aux && aux->selector_type ? aux->selector_type : in->opnds[0].type;
for (u32 i = 0; aux && i < aux->ncases; ++i) {
- e->target->load_imm(e->target, imm, (i64)aux->cases[i].value);
+ OptOperand case_op;
+ NativeLoc imm;
+ memset(&case_op, 0, sizeof case_op);
+ case_op.kind = OPK_IMM;
+ case_op.type = case_type;
+ case_op.v.imm = (i64)aux->cases[i].value;
+ imm = operand_imm_or_reg(e, &case_op, NATIVE_IMM_CMP, (u32)CMP_EQ,
+ sel.v.reg, REG_NONE, in->loc);
e->target->cmp_branch(e->target, CMP_EQ, sel, imm,
ensure_label(e, aux->cases[i].block, in->loc));
}
diff --git a/test/opt/o1_switch_imm.sh b/test/opt/o1_switch_imm.sh
@@ -0,0 +1,147 @@
+#!/usr/bin/env bash
+# Structural check for the -O1 switch-chain immediate-compare lowering (O1.md W7):
+#
+# A non-jump-table switch chain replays in pass_native_emit.c as a sequence of
+# `IR_SWITCH` case compares. The chain must route each case value through the
+# SAME NATIVE_IMM_CMP immediate-or-register logic the normal IR_CMP_BRANCH
+# emitter uses, so that:
+#
+# A. an in-range case value becomes a direct compare immediate
+# (`cmp wN, #k` on aarch64) with NO per-case constant materialization
+# (`movz wScratch, #k; cmp wN, wScratch`) preceding it; and
+# B. a case value too large (or negative) for the target's compare-immediate
+# encoding still falls back to materializing into a scratch register --
+# the selector itself stays pinned in one register across the whole chain
+# and is never reloaded per case.
+#
+# The check pins aarch64 (the reference backend), where the compare-immediate
+# encoding is a 12-bit unsigned immediate (optionally <<12) and the mnemonics
+# are stable. x64 (rich cmp-imm32 forms) is spot-checked too. rv64 is excluded
+# on purpose: it has no compare-against-non-zero-immediate branch form, so it
+# always materializes -- that is the documented fallback, not a regression.
+set -euo pipefail
+
+ROOT="$(cd "$(dirname "$0")/../.." && pwd)"
+KIT="${KIT:-$ROOT/build/kit}"
+WORK="$ROOT/build/test/opt/o1_switch_imm"
+mkdir -p "$WORK"
+
+SRC="$WORK/case.c"
+cat > "$SRC" <<'EOF'
+/* Sparse switch, all case values small enough to fit an aarch64 cmp imm12.
+ Below the jump-table threshold (5 non-contiguous cases) so it lowers to a
+ compare chain, not a table. */
+int sparse(int x) {
+ switch (x) {
+ case 3: return 100;
+ case 17: return 200;
+ case 42: return 300;
+ case 99: return 400;
+ case 256: return 500;
+ default: return -1;
+ }
+}
+
+/* Mixed chain: small cases fold to cmp #imm; 0x12345 and -7 cannot be encoded
+ as an aarch64 compare immediate, so they must fall back to materializing the
+ constant into a scratch register (selector stays pinned). */
+long bigvals(long x) {
+ switch (x) {
+ case 5L: return 1; /* fits cmp imm */
+ case 74565L: return 2; /* 0x12345 -- too big, fallback */
+ case -7L: return 3; /* negative -- aa64 cmp imm needs >=0, fallback */
+ case 4096L: return 4; /* fits via the shifted (<<12) imm form */
+ default: return 0;
+ }
+}
+EOF
+
+OBJ="$WORK/case_aa64.o"
+"$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC" \
+ -o "$OBJ" > "$WORK/cc_aa64.out" 2>&1
+"$KIT" objdump -d "$OBJ" > "$WORK/dis_aa64.out" 2>&1
+
+fn_body() { # $1 = dis file, $2 = symbol name -> stdout body
+ awk -v want="$2" '
+ $0 ~ ("^[0-9a-f]+ <" want ">:") { in_fn = 1; next }
+ /^[0-9a-f]+ </ { in_fn = 0 }
+ in_fn { print }
+ ' "$1"
+}
+
+fail() {
+ printf 'o1_switch_imm FAILED: %s\n' "$1" >&2
+ printf ' --- aarch64 disassembly ---\n' >&2
+ sed 's/^/ | /' "$WORK/dis_aa64.out" >&2
+ exit 1
+}
+
+# --- A: sparse switch -- every case is a `cmp wN, #imm`, none preceded by a
+# movz-into-scratch. ----------------------------------------------------
+A="$(fn_body "$WORK/dis_aa64.out" sparse)"
+[ -n "$A" ] || A="$(fn_body "$WORK/dis_aa64.out" _sparse)"
+[ -n "$A" ] || fail "sparse not found in disassembly"
+
+# Expect at least 5 immediate compares (one per case value).
+ncmp_imm="$(printf '%s\n' "$A" | grep -Ec '\bcmp\s+w[0-9]+, #[0-9]+' || true)"
+[ "$ncmp_imm" -ge 5 ] || \
+ fail "sparse: expected >=5 'cmp wN, #imm' case compares, saw $ncmp_imm"
+
+# And NO per-case constant materialization: with the W7 fold every case value
+# is folded into the cmp immediate, so the chain has ZERO register-register
+# compares. (The baseline materialized each value into a scratch register and
+# emitted `cmp wSel, wScratch` -- one per case. Note: return-value `movz w0,#k`
+# in the case bodies is unrelated to the chain, so we key off the register
+# COMPARE, which only the chain materialization produces.)
+nreg_cmp="$(printf '%s\n' "$A" | grep -Ec '\bcmp\s+w[0-9]+, w[0-9]+' || true)"
+[ "$nreg_cmp" -eq 0 ] || \
+ fail "sparse: $nreg_cmp register compares survived (cmp wN, wM) -- a case value was materialized into a scratch instead of folded into cmp #imm"
+
+# --- B: bigvals -- small cases fold (cmp #imm), too-large/negative cases fall
+# back to materialization (movz/movk), and the selector is pinned. ------
+B="$(fn_body "$WORK/dis_aa64.out" bigvals)"
+[ -n "$B" ] || B="$(fn_body "$WORK/dis_aa64.out" _bigvals)"
+[ -n "$B" ] || fail "bigvals not found in disassembly"
+
+# 5 and 4096 fold to immediate compares (4096 uses the shifted imm form).
+printf '%s\n' "$B" | grep -Eq '\bcmp\s+x[0-9]+, #5\b' || \
+ fail "bigvals: case 5 did not fold to 'cmp xN, #5'"
+printf '%s\n' "$B" | grep -Eq '\bcmp\s+x[0-9]+, #1, lsl #12\b' || \
+ fail "bigvals: case 4096 did not fold to the shifted 'cmp xN, #1, lsl #12'"
+
+# 0x12345 (74565) and -7 cannot be a cmp immediate -> they must materialize
+# (movz) and then use a register compare.
+printf '%s\n' "$B" | grep -Eq '\bmovz\b' || \
+ fail "bigvals: expected a fallback materialization (movz) for the too-large/negative case"
+printf '%s\n' "$B" | grep -Eq '\bcmp\s+x[0-9]+, x[0-9]+' || \
+ fail "bigvals: expected a register compare for the materialized (fallback) case"
+
+# Selector pinning: the selector is moved into a register once at the top of the
+# function; the per-case fallback scratch must be a DIFFERENT register than the
+# selector (so the selector is never clobbered/reloaded mid-chain). Derive both
+# from the disassembly rather than hard-coding register numbers.
+sel_reg="$(printf '%s\n' "$B" | grep -Eo '\bcmp\s+x[0-9]+, #5\b' | head -1 | grep -Eo 'x[0-9]+')"
+[ -n "$sel_reg" ] || fail "bigvals: could not determine the selector register"
+scratch_reg="$(printf '%s\n' "$B" | grep -E '\bmovz\b' | head -1 | grep -Eo 'w[0-9]+|x[0-9]+' | head -1)"
+[ -n "$scratch_reg" ] || fail "bigvals: could not determine the fallback scratch register"
+# Compare by register number (movz writes the w-view of the same x reg).
+sel_n="${sel_reg#x}"
+scr_n="${scratch_reg#w}"; scr_n="${scr_n#x}"
+[ "$sel_n" != "$scr_n" ] || \
+ fail "bigvals: fallback scratch reused the selector register ($sel_reg) -- selector pinning lost"
+
+# --- x64 spot check: the rich cmp-imm32 forms mean even large/negative case
+# values fold straight into `cmpq $imm, %reg` (no scratch). ----------------
+OBJX="$WORK/case_x64.o"
+"$KIT" cc -target x86_64-linux-gnu -O1 -std=c11 -c "$SRC" \
+ -o "$OBJX" > "$WORK/cc_x64.out" 2>&1
+"$KIT" objdump -d "$OBJX" > "$WORK/dis_x64.out" 2>&1
+BX="$(fn_body "$WORK/dis_x64.out" bigvals)"
+[ -n "$BX" ] || BX="$(fn_body "$WORK/dis_x64.out" _bigvals)"
+if [ -n "$BX" ]; then
+ nx="$(printf '%s\n' "$BX" | grep -Ec 'cmpq?\s+\$(-?[0-9]+|0x[0-9a-f]+),' || true)"
+ [ "$nx" -ge 3 ] || \
+ fail "x64 bigvals: expected >=3 immediate cmp forms (rich cmp-imm32), saw $nx"
+fi
+
+printf 'o1_switch_imm: OK (sparse -> cmp #imm chain, large/neg fallback materializes, selector pinned; x64 cmp-imm)\n'
