o1_switch_imm.sh (6957B)
1 #!/usr/bin/env bash 2 # Structural check for the -O1 switch-chain immediate-compare lowering (O1.md W7): 3 # 4 # A non-jump-table switch chain replays in pass_native_emit.c as a sequence of 5 # `IR_SWITCH` case compares. The chain must route each case value through the 6 # SAME NATIVE_IMM_CMP immediate-or-register logic the normal IR_CMP_BRANCH 7 # emitter uses, so that: 8 # 9 # A. an in-range case value becomes a direct compare immediate 10 # (`cmp wN, #k` on aarch64) with NO per-case constant materialization 11 # (`movz wScratch, #k; cmp wN, wScratch`) preceding it; and 12 # B. a case value too large (or negative) for the target's compare-immediate 13 # encoding still falls back to materializing into a scratch register -- 14 # the selector itself stays pinned in one register across the whole chain 15 # and is never reloaded per case. 16 # 17 # The check pins aarch64 (the reference backend), where the compare-immediate 18 # encoding is a 12-bit unsigned immediate (optionally <<12) and the mnemonics 19 # are stable. x64 (rich cmp-imm32 forms) is spot-checked too. rv64 is excluded 20 # on purpose: it has no compare-against-non-zero-immediate branch form, so it 21 # always materializes -- that is the documented fallback, not a regression. 22 set -euo pipefail 23 24 ROOT="$(cd "$(dirname "$0")/../.." && pwd)" 25 KIT="${KIT:-$ROOT/build/kit}" 26 WORK="$ROOT/build/test/opt/o1_switch_imm" 27 mkdir -p "$WORK" 28 29 SRC="$WORK/case.c" 30 cat > "$SRC" <<'EOF' 31 /* Sparse switch, all case values small enough to fit an aarch64 cmp imm12. 32 Below the jump-table threshold (5 non-contiguous cases) so it lowers to a 33 compare chain, not a table. */ 34 int sparse(int x) { 35 switch (x) { 36 case 3: return 100; 37 case 17: return 200; 38 case 42: return 300; 39 case 99: return 400; 40 case 256: return 500; 41 default: return -1; 42 } 43 } 44 45 /* Mixed chain: small cases fold to cmp #imm; 0x12345 and -7 cannot be encoded 46 as an aarch64 compare immediate, so they must fall back to materializing the 47 constant into a scratch register (selector stays pinned). */ 48 long bigvals(long x) { 49 switch (x) { 50 case 5L: return 1; /* fits cmp imm */ 51 case 74565L: return 2; /* 0x12345 -- too big, fallback */ 52 case -7L: return 3; /* negative -- aa64 cmp imm needs >=0, fallback */ 53 case 4096L: return 4; /* fits via the shifted (<<12) imm form */ 54 default: return 0; 55 } 56 } 57 EOF 58 59 OBJ="$WORK/case_aa64.o" 60 "$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC" \ 61 -o "$OBJ" > "$WORK/cc_aa64.out" 2>&1 62 "$KIT" objdump -d "$OBJ" > "$WORK/dis_aa64.out" 2>&1 63 64 fn_body() { # $1 = dis file, $2 = symbol name -> stdout body 65 awk -v want="$2" ' 66 $0 ~ ("^[0-9a-f]+ <" want ">:") { in_fn = 1; next } 67 /^[0-9a-f]+ </ { in_fn = 0 } 68 in_fn { print } 69 ' "$1" 70 } 71 72 fail() { 73 printf 'o1_switch_imm FAILED: %s\n' "$1" >&2 74 printf ' --- aarch64 disassembly ---\n' >&2 75 sed 's/^/ | /' "$WORK/dis_aa64.out" >&2 76 exit 1 77 } 78 79 # --- A: sparse switch -- every case is a `cmp wN, #imm`, none preceded by a 80 # movz-into-scratch. ---------------------------------------------------- 81 A="$(fn_body "$WORK/dis_aa64.out" sparse)" 82 [ -n "$A" ] || A="$(fn_body "$WORK/dis_aa64.out" _sparse)" 83 [ -n "$A" ] || fail "sparse not found in disassembly" 84 85 # Expect at least 5 immediate compares (one per case value). 86 ncmp_imm="$(printf '%s\n' "$A" | grep -Ec '\bcmp\s+w[0-9]+, #[0-9]+' || true)" 87 [ "$ncmp_imm" -ge 5 ] || \ 88 fail "sparse: expected >=5 'cmp wN, #imm' case compares, saw $ncmp_imm" 89 90 # And NO per-case constant materialization: with the W7 fold every case value 91 # is folded into the cmp immediate, so the chain has ZERO register-register 92 # compares. (The baseline materialized each value into a scratch register and 93 # emitted `cmp wSel, wScratch` -- one per case. Note: return-value `movz w0,#k` 94 # in the case bodies is unrelated to the chain, so we key off the register 95 # COMPARE, which only the chain materialization produces.) 96 nreg_cmp="$(printf '%s\n' "$A" | grep -Ec '\bcmp\s+w[0-9]+, w[0-9]+' || true)" 97 [ "$nreg_cmp" -eq 0 ] || \ 98 fail "sparse: $nreg_cmp register compares survived (cmp wN, wM) -- a case value was materialized into a scratch instead of folded into cmp #imm" 99 100 # --- B: bigvals -- small cases fold (cmp #imm), too-large/negative cases fall 101 # back to materialization (movz/movk), and the selector is pinned. ------ 102 B="$(fn_body "$WORK/dis_aa64.out" bigvals)" 103 [ -n "$B" ] || B="$(fn_body "$WORK/dis_aa64.out" _bigvals)" 104 [ -n "$B" ] || fail "bigvals not found in disassembly" 105 106 # 5 and 4096 fold to immediate compares (4096 uses the shifted imm form). 107 printf '%s\n' "$B" | grep -Eq '\bcmp\s+x[0-9]+, #5\b' || \ 108 fail "bigvals: case 5 did not fold to 'cmp xN, #5'" 109 printf '%s\n' "$B" | grep -Eq '\bcmp\s+x[0-9]+, #1, lsl #12\b' || \ 110 fail "bigvals: case 4096 did not fold to the shifted 'cmp xN, #1, lsl #12'" 111 112 # 0x12345 (74565) and -7 cannot be a cmp immediate -> they must materialize 113 # (movz) and then use a register compare. 114 printf '%s\n' "$B" | grep -Eq '\bmovz\b' || \ 115 fail "bigvals: expected a fallback materialization (movz) for the too-large/negative case" 116 printf '%s\n' "$B" | grep -Eq '\bcmp\s+x[0-9]+, x[0-9]+' || \ 117 fail "bigvals: expected a register compare for the materialized (fallback) case" 118 119 # Selector pinning: the selector is moved into a register once at the top of the 120 # function; the per-case fallback scratch must be a DIFFERENT register than the 121 # selector (so the selector is never clobbered/reloaded mid-chain). Derive both 122 # from the disassembly rather than hard-coding register numbers. 123 sel_reg="$(printf '%s\n' "$B" | grep -Eo '\bcmp\s+x[0-9]+, #5\b' | head -1 | grep -Eo 'x[0-9]+')" 124 [ -n "$sel_reg" ] || fail "bigvals: could not determine the selector register" 125 scratch_reg="$(printf '%s\n' "$B" | grep -E '\bmovz\b' | head -1 | grep -Eo 'w[0-9]+|x[0-9]+' | head -1)" 126 [ -n "$scratch_reg" ] || fail "bigvals: could not determine the fallback scratch register" 127 # Compare by register number (movz writes the w-view of the same x reg). 128 sel_n="${sel_reg#x}" 129 scr_n="${scratch_reg#w}"; scr_n="${scr_n#x}" 130 [ "$sel_n" != "$scr_n" ] || \ 131 fail "bigvals: fallback scratch reused the selector register ($sel_reg) -- selector pinning lost" 132 133 # --- x64 spot check: the rich cmp-imm32 forms mean even large/negative case 134 # values fold straight into `cmpq $imm, %reg` (no scratch). ---------------- 135 OBJX="$WORK/case_x64.o" 136 "$KIT" cc -target x86_64-linux-gnu -O1 -std=c11 -c "$SRC" \ 137 -o "$OBJX" > "$WORK/cc_x64.out" 2>&1 138 "$KIT" objdump -d "$OBJX" > "$WORK/dis_x64.out" 2>&1 139 BX="$(fn_body "$WORK/dis_x64.out" bigvals)" 140 [ -n "$BX" ] || BX="$(fn_body "$WORK/dis_x64.out" _bigvals)" 141 if [ -n "$BX" ]; then 142 nx="$(printf '%s\n' "$BX" | grep -Ec 'cmpq?\s+\$(-?[0-9]+|0x[0-9a-f]+),' || true)" 143 [ "$nx" -ge 3 ] || \ 144 fail "x64 bigvals: expected >=3 immediate cmp forms (rich cmp-imm32), saw $nx" 145 fi 146 147 printf 'o1_switch_imm: OK (sparse -> cmp #imm chain, large/neg fallback materializes, selector pinned; x64 cmp-imm)\n'