o1_local_cse.sh (7737B)
1 #!/usr/bin/env bash 2 # Structural + correctness checks for the -O1 W5 same-block redundant-load + 3 # CSE elimination (O1.md W5), implemented in src/opt/pass_combine.c 4 # (try_local_load_cse / try_local_compute_cse). 5 # 6 # W5 is a single forward pass per block that reuses the last load of an 7 # address (and the last result of a pure expression) until a store / call / 8 # memory barrier invalidates it. It is deliberately conservative: ALIASING is 9 # the whole game -- a load is reused only when NO intervening store may alias 10 # (and a write to memory is treated as a full barrier that forgets every 11 # pending load), and a pure compute is reused only when its inputs are 12 # unchanged since. 13 # 14 # This guard validates: 15 # A. ELIMINATION: a same-block redundant load of the same address with no 16 # intervening aliasing store between is eliminated (the second ldr is 17 # reused from a register, not re-loaded). 18 # B. ALIAS-HAZARD PRESERVATION: a load, then a store that MAY alias, then a 19 # reload KEEPS the reload -- W5 must NOT delete a load that may see the 20 # new value. 21 # C. BARRIER PRESERVATION: a load across a call is not reused (the call is a 22 # full barrier), and a volatile load is never reused. 23 # D. RUNTIME CORRECTNESS: a function exercising same-block reload + recompute, 24 # alias hazards, volatile, and a call barrier computes the identical, 25 # correct result at -O0 and -O1. 26 set -euo pipefail 27 28 ROOT="$(cd "$(dirname "$0")/../.." && pwd)" 29 KIT="${KIT:-$ROOT/build/kit}" 30 WORK="$ROOT/build/test/opt/o1_local_cse" 31 mkdir -p "$WORK" 32 33 fail() { 34 printf 'o1_local_cse FAILED: %s\n' "$1" >&2 35 shift || true 36 for f in "$@"; do 37 printf ' --- %s ---\n' "$f" >&2 38 sed 's/^/ | /' "$f" >&2 39 done 40 exit 1 41 } 42 43 fn_body() { # $1 = file, $2 = symbol name -> stdout body 44 awk -v want="$2" ' 45 $0 ~ ("^[0-9a-f]+ <_?" want ">:") { in_fn = 1; next } 46 /^[0-9a-f]+ </ { in_fn = 0 } 47 in_fn { print } 48 ' "$1" 49 } 50 51 # ---- A. elimination: redundant same-address load reused from a register ---- 52 # Two reads of the SAME global through the same pointer with no store between. 53 # Both reads are of the SAME address with nothing in between that writes 54 # memory, so W5 reuses the first load. We count the loads of the slot. 55 SRC_A="$WORK/elim.c" 56 cat > "$SRC_A" <<'EOF' 57 /* Two dependent uses of *p with no intervening write: the second load of *p is 58 * redundant and W5 reuses the first. The address (p in x0) is unchanged and 59 * no store/call happens between the two loads. */ 60 long load_twice(long *p) { 61 long a = *p; /* ldr */ 62 long b = *p + 1; /* redundant ldr -> reuse */ 63 return a * b; 64 } 65 EOF 66 OBJ_A="$WORK/elim.o" 67 "$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC_A" \ 68 -o "$OBJ_A" > "$WORK/elim.cc.out" 2>&1 || fail "elim compile failed" "$WORK/elim.cc.out" 69 "$KIT" objdump -d "$OBJ_A" > "$WORK/elim.dis" 2>&1 70 A="$(fn_body "$WORK/elim.dis" load_twice)" 71 [ -n "$A" ] || fail "load_twice not found" "$WORK/elim.dis" 72 # Exactly one ldr from the pointer should remain (the redundant second is reused). 73 NLDR="$(printf '%s\n' "$A" | grep -cE '\bldr\b' || true)" 74 [ "$NLDR" -le 1 ] || fail "expected <=1 ldr in load_twice (redundant load not reused, got $NLDR)" "$WORK/elim.dis" 75 76 # ---- B. alias-hazard: store between two loads MUST keep the reload ---- 77 SRC_B="$WORK/alias.c" 78 cat > "$SRC_B" <<'EOF' 79 /* *p is read, then *q is written (q may alias p), then *p is read again. The 80 * reload of *p must NOT be eliminated: it may observe the value stored to *q. */ 81 long load_store_load(long *p, long *q, long v) { 82 long a = *p; 83 *q = v; /* may alias *p -- full barrier */ 84 long b = *p; /* must reload */ 85 return a + b; 86 } 87 EOF 88 OBJ_B="$WORK/alias.o" 89 "$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC_B" \ 90 -o "$OBJ_B" > "$WORK/alias.cc.out" 2>&1 || fail "alias compile failed" "$WORK/alias.cc.out" 91 "$KIT" objdump -d "$OBJ_B" > "$WORK/alias.dis" 2>&1 92 B="$(fn_body "$WORK/alias.dis" load_store_load)" 93 [ -n "$B" ] || fail "load_store_load not found" "$WORK/alias.dis" 94 # Both loads of *p must survive (>=2 ldr): the store is a barrier. 95 NLDR_B="$(printf '%s\n' "$B" | grep -cE '\bldr\b' || true)" 96 [ "$NLDR_B" -ge 2 ] || fail "reload after may-alias store was wrongly eliminated (ldr=$NLDR_B)" "$WORK/alias.dis" 97 # And a store must be present. 98 printf '%s\n' "$B" | grep -qE '\bstr\b' || fail "store missing in load_store_load" "$WORK/alias.dis" 99 100 # ---- C. barrier: load across a call + volatile load never reused ---- 101 SRC_C="$WORK/barrier.c" 102 cat > "$SRC_C" <<'EOF' 103 extern void sink(void); 104 /* Load across a call: the call is a full memory barrier; the reload survives. */ 105 long load_call_load(long *p) { 106 long a = *p; 107 sink(); 108 long b = *p; 109 return a + b; 110 } 111 /* Volatile load: never reused, each read must re-load. */ 112 long vol_twice(volatile long *p) { 113 long a = *p; 114 long b = *p; 115 return a + b; 116 } 117 EOF 118 OBJ_C="$WORK/barrier.o" 119 "$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC_C" \ 120 -o "$OBJ_C" > "$WORK/barrier.cc.out" 2>&1 || fail "barrier compile failed" "$WORK/barrier.cc.out" 121 "$KIT" objdump -d "$OBJ_C" > "$WORK/barrier.dis" 2>&1 122 C1="$(fn_body "$WORK/barrier.dis" load_call_load)" 123 [ -n "$C1" ] || fail "load_call_load not found" "$WORK/barrier.dis" 124 NLDR_C1="$(printf '%s\n' "$C1" | grep -cE '\bldr\b' || true)" 125 [ "$NLDR_C1" -ge 2 ] || fail "reload across a call was wrongly eliminated (ldr=$NLDR_C1)" "$WORK/barrier.dis" 126 C2="$(fn_body "$WORK/barrier.dis" vol_twice)" 127 [ -n "$C2" ] || fail "vol_twice not found" "$WORK/barrier.dis" 128 NLDR_C2="$(printf '%s\n' "$C2" | grep -cE '\bldr\b' || true)" 129 [ "$NLDR_C2" -ge 2 ] || fail "volatile load was wrongly reused (ldr=$NLDR_C2)" "$WORK/barrier.dis" 130 131 # ---- D. runtime correctness at -O0 vs -O1 (native arch) ---- 132 SRC_D="$WORK/run.c" 133 cat > "$SRC_D" <<'EOF' 134 /* Freestanding (no libc): the result is reduced to a small exit code, so -O0 135 * and -O1 must produce identical exit status. Exercises same-block redundant 136 * loads + recompute + an alias hazard + a call barrier + a volatile read. */ 137 static long acc_calls = 0; 138 long ext_call(long x) { acc_calls += x; return x * 2; } 139 140 static long kern(long *p, long *q, volatile long *vp, long n) { 141 long s = 0; 142 for (long i = 0; i < n; ++i) { 143 long a = p[0]; /* load */ 144 long b = p[0] + 7; /* redundant load -> reuse */ 145 long c = (a * 3) + (a * 3); /* a*3 computed twice -> reuse one */ 146 q[0] = i; /* may alias p[0]: later p[0] read must reload */ 147 long d = p[0]; /* reload after the store (alias hazard) */ 148 long w = vp[0] + vp[0]; /* volatile: never reused, two real reads */ 149 s += a + b + c + d + w; 150 s += ext_call(i & 3); /* call barrier */ 151 long e = p[1] + p[1]; /* p[1] redundant load -> reuse, after the call */ 152 s += e; 153 } 154 return s + acc_calls; 155 } 156 157 int main(void) { 158 long arr[2] = {5, 9}; 159 long other = 0; 160 volatile long vol = 2; 161 long r = 0; 162 for (long t = 0; t < 11; ++t) { 163 arr[0] = 3 + t; arr[1] = 100 - t; other = 0; acc_calls = 0; vol = t + 1; 164 r ^= kern(arr, &other, &vol, 17); 165 r ^= other; /* observe the aliasing store target */ 166 } 167 return (int)(r & 0x7f); 168 } 169 EOF 170 BIN_O0="$WORK/run_o0" 171 BIN_O1="$WORK/run_o1" 172 "$KIT" cc -O0 -std=c11 "$SRC_D" -o "$BIN_O0" > "$WORK/run.o0.cc.out" 2>&1 \ 173 || fail "run -O0 compile failed" "$WORK/run.o0.cc.out" 174 "$KIT" cc -O1 -std=c11 "$SRC_D" -o "$BIN_O1" > "$WORK/run.o1.cc.out" 2>&1 \ 175 || fail "run -O1 compile failed" "$WORK/run.o1.cc.out" 176 set +e 177 "$BIN_O0"; EC_O0=$? 178 "$BIN_O1"; EC_O1=$? 179 set -e 180 [ "$EC_O0" = "$EC_O1" ] || fail "O0/O1 exit codes differ: $EC_O0 vs $EC_O1" 181 182 printf 'o1_local_cse: OK (elim=%s ldr; alias kept %s ldr; call kept %s; vol kept %s; run rc=%s)\n' \ 183 "$NLDR" "$NLDR_B" "$NLDR_C1" "$NLDR_C2" "$EC_O0"