o1_stack_dse.sh (4756B)
1 #!/usr/bin/env bash 2 # Checks for the -O1 W8 same-block stack dead-store elimination (O1.md W8), in 3 # src/opt/pass_combine.c (stack_dse_block). 4 # 5 # W8 deletes a spill store when a LATER store to the same spill slot fully 6 # overwrites it in the same block before any possible read or barrier. It is 7 # deliberately exact and spill-only. The canonical MIR operand walker clears 8 # only the pending slot named by any explicit OPK_STACK use, including stack 9 # locations nested in indirect or auxiliary operands. Non-candidate memory 10 # writes (call/asm/intrinsic/atomic/volatile/aggregate and uncertain stores) 11 # remain full barriers; a differently shaped direct spill store replaces the 12 # pending shape without treating semantic locals as allocator spill traffic. 13 # 14 # Important: in kit's current -O1 pipeline this pass is correct but rarely finds 15 # work -- upstream rematerialization (W2) + dead-definition-elimination + the 16 # adjacent store/load coalesce already remove redundant spill traffic, so two 17 # stores to one slot almost always have a reload or a barrier between them. This 18 # guard therefore validates the two properties that matter for correctness: 19 # 20 # A. PRESERVATION: two stores to the same spill slot that are separated by a 21 # call (a barrier) AND whose value is reloaded between them must keep BOTH 22 # stores -- W8 must NOT delete a store that may be read. 23 # B. RUNTIME CORRECTNESS: a high-register-pressure function (forcing real 24 # spills) computes the identical, correct result at -O0 and -O1. 25 # 26 # (When a future pass exposes a barrier-free double store, W8 will retire the 27 # first store; that path is exercised by the differential -O0/-O1 run here.) 28 set -euo pipefail 29 30 ROOT="$(cd "$(dirname "$0")/../.." && pwd)" 31 KIT="${KIT:-$ROOT/build/kit}" 32 WORK="$ROOT/build/test/opt/o1_stack_dse" 33 mkdir -p "$WORK" 34 35 fail() { 36 printf 'o1_stack_dse FAILED: %s\n' "$1" >&2 37 shift || true 38 for f in "$@"; do 39 printf ' --- %s ---\n' "$f" >&2 40 sed 's/^/ | /' "$f" >&2 41 done 42 exit 1 43 } 44 45 # ---- A. preservation: barrier + reload between two stores keeps both ---- 46 SRC_A="$WORK/preserve.c" 47 cat > "$SRC_A" <<'EOF' 48 extern long c1(void); 49 extern long c2(void); 50 extern long c3(void); 51 extern void use2(long, long, long, long, long, long); 52 /* The call results are not rematerializable, so they spill across the later 53 * calls; each spilled value is stored, then reloaded (for use2 and the return), 54 * then its slot is reused -- two stores to a slot with a barrier+read between. 55 * W8 must keep both stores. */ 56 long preserve(void) { 57 long a = c1(), b = c2(), c = c3(), d = c1(), e = c2(), g = c3(); 58 long h = c1(), i = c2(), j = c3(), k = c1(), l = c2(), m = c3(); 59 use2(a, b, c, d, e, g); 60 use2(h, i, j, k, l, m); 61 return a + b + c + d + e + g + h + i + j + k + l + m; 62 } 63 EOF 64 OBJ_A="$WORK/preserve.o" 65 "$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC_A" \ 66 -o "$OBJ_A" > "$WORK/preserve.cc.out" 2>&1 67 "$KIT" objdump -d "$OBJ_A" > "$WORK/preserve.dis" 2>&1 68 # There must be at least one spill store (str to a frame/stack base) AND the 69 # function must still load values back (ldr) -- proving stores were not stripped. 70 STR_N="$(grep -cE '\b(str|stur)\b' "$WORK/preserve.dis" || true)" 71 LDR_N="$(grep -cE '\b(ldr|ldur|ldp)\b' "$WORK/preserve.dis" || true)" 72 [ "$STR_N" -ge 1 ] || fail "expected spill stores in preserve()" "$WORK/preserve.dis" 73 [ "$LDR_N" -ge 1 ] || fail "expected reloads in preserve()" "$WORK/preserve.dis" 74 75 # ---- B. runtime correctness at -O0 vs -O1 under heavy spill pressure ---- 76 SRC_B="$WORK/run.c" 77 cat > "$SRC_B" <<'EOF' 78 /* Heavy live-range pressure: many simultaneously-live longs feeding several 79 * dependent expressions, forcing the allocator to spill and reload. The result 80 * is a fixed deterministic value; -O0 and -O1 must agree. */ 81 static long mix(long s) { 82 long a=s+1,b=s+2,c=s+3,d=s+4,e=s+5,g=s+6,h=s+7,i=s+8; 83 long j=s+9,k=s+10,m=s+11,n=s+12,o=s+13,p=s+14,q=s+15,r=s+16; 84 long t = a*b + c*d + e*g + h*i + j*k + m*n + o*p + q*r; 85 long u = a-b + c-d + e-g + h-i + j-k + m-n + o-p + q-r; 86 long v = a^b ^ c^d ^ e^g ^ h^i ^ j^k ^ m^n ^ o^p ^ q^r; 87 return t + u + v + a + r; 88 } 89 int main(void) { 90 long acc = 0; 91 for (long s = 0; s < 50; ++s) acc += mix(s); 92 /* Reduce to a small exit code so the JIT entry's return value is comparable. */ 93 return (int)(acc % 251); 94 } 95 EOF 96 run_rc() { # $1 = -O level -> echoes exit code 97 if "$KIT" run "$1" -e main "$SRC_B" > "$WORK/run.$1.out" 2>&1; then 98 echo 0 99 else 100 echo $? 101 fi 102 } 103 RC0="$(run_rc -O0)" 104 RC1="$(run_rc -O1)" 105 if [ "$RC0" != "$RC1" ]; then 106 fail "spill-heavy run mismatch: -O0=$RC0 -O1=$RC1" \ 107 "$WORK/run.-O0.out" "$WORK/run.-O1.out" 108 fi 109 110 printf 'o1_stack_dse: OK (preservation across barrier+reload; -O0==-O1=%s on spill-heavy run)\n' "$RC1"