o1_branch_cleanup.sh (5762B)
1 #!/usr/bin/env bash 2 # Structural + behavioral checks for the -O1 one-pass branch cleanup (O1.md W9) 3 # and constant cmp_branch folding (O1.md W10): 4 # 5 # A. W10 same-register integer compare: `if (x == x)` is statically true, so 6 # the conditional `cmp wN, wN` + `b.<cc>` is folded away and the taken arm 7 # runs unconditionally -- a same-target conditional branch becomes a single 8 # unconditional flow. 9 # B. W10 dead-arm fold: a `while (x == x)` loop condition is always true, so 10 # the per-iteration `cmp wN, wN` / `b.eq` loop-header test disappears (only 11 # the real `break` condition's branch survives). 12 # C. W9 label-address guard: a computed-goto (`&&label`) program keeps every 13 # label block defined (not bypassed by branch forwarding) AND runs 14 # correctly through the in-process JIT. 15 # 16 # All folds are local, target-agnostic, and keep -O1 linear. The disasm checks 17 # pin aarch64 (the reference backend) where the mnemonics are stable. 18 set -euo pipefail 19 20 ROOT="$(cd "$(dirname "$0")/../.." && pwd)" 21 KIT="${KIT:-$ROOT/build/kit}" 22 WORK="$ROOT/build/test/opt/o1_branch_cleanup" 23 mkdir -p "$WORK" 24 25 fail() { 26 printf 'o1_branch_cleanup FAILED: %s\n' "$1" >&2 27 shift || true 28 for f in "$@"; do 29 printf ' --- %s ---\n' "$f" >&2 30 sed 's/^/ | /' "$f" >&2 31 done 32 exit 1 33 } 34 35 fn_body() { # $1 = dis file, $2 = symbol -> stdout body 36 awk -v want="$2" ' 37 $0 ~ ("^[0-9a-f]+ <" want ">:") { in_fn = 1; next } 38 /^[0-9a-f]+ </ { in_fn = 0 } 39 in_fn { print } 40 ' "$1" 41 } 42 43 # --------------------------------------------------------------------------- 44 # A + B: W10 constant cmp_branch folding (same-register integer compares). 45 # --------------------------------------------------------------------------- 46 SRC="$WORK/fold.c" 47 cat > "$SRC" <<'EOF' 48 /* A: a same-register compare is statically true; the dead else arm collapses 49 * and the taken value loads unconditionally. */ 50 int ifxx(int x) { if (x == x) return 7; return x; } 51 /* B: a same-register loop condition is always true; the loop-header test 52 * folds away, leaving only the real break-condition branch. */ 53 int loop_xx(int x) { int s = 0; while (x == x) { s++; if (s > 3) break; } return s; } 54 EOF 55 56 OBJ="$WORK/fold.o" 57 "$KIT" cc -target aarch64-linux-gnu -O1 -std=c11 -c "$SRC" \ 58 -o "$OBJ" > "$WORK/fold.cc.out" 2>&1 59 "$KIT" objdump -d "$OBJ" > "$WORK/fold.dis" 2>&1 60 61 # A: ifxx must contain no `cmp wN, wN` (self compare) and no conditional branch 62 # -- the always-true compare folded and the taken arm runs unconditionally. 63 A="$(fn_body "$WORK/fold.dis" ifxx)" 64 [ -n "$A" ] || A="$(fn_body "$WORK/fold.dis" _ifxx)" 65 [ -n "$A" ] || fail "ifxx not found in disassembly" "$WORK/fold.dis" 66 if printf '%s\n' "$A" | grep -Eq 'cmp\s+(w|x)([0-9]+), \1\2\b'; then 67 fail "ifxx kept a self-compare (W10 did not fold x==x)" "$WORK/fold.dis" 68 fi 69 if printf '%s\n' "$A" | grep -Eq '\bb\.(eq|ne|gt|ge|lt|le|hi|hs|lo|ls)\b|\bcbz\b|\bcbnz\b'; then 70 fail "ifxx kept a conditional branch (W10 did not fold the dead arm)" \ 71 "$WORK/fold.dis" 72 fi 73 # And the unconditional value (7) must be present. 74 printf '%s\n' "$A" | grep -Eq '\bmovz?\b.*0x7\b' \ 75 || fail "ifxx lost its unconditional movz #7" "$WORK/fold.dis" 76 77 # B: loop_xx must have NO self-compare; the only surviving compare is `cmp wN,#3` 78 # (the break test). The folded loop condition would have been `cmp wN, wN`. 79 B="$(fn_body "$WORK/fold.dis" loop_xx)" 80 [ -n "$B" ] || B="$(fn_body "$WORK/fold.dis" _loop_xx)" 81 [ -n "$B" ] || fail "loop_xx not found in disassembly" "$WORK/fold.dis" 82 if printf '%s\n' "$B" | grep -Eq 'cmp\s+(w|x)([0-9]+), \1\2\b'; then 83 fail "loop_xx kept the x==x loop-condition self-compare (W10 missed it)" \ 84 "$WORK/fold.dis" 85 fi 86 87 # --------------------------------------------------------------------------- 88 # C: W9 label-address guard -- computed goto must keep its label blocks and run. 89 # --------------------------------------------------------------------------- 90 GSRC="$WORK/cgoto.c" 91 cat > "$GSRC" <<'EOF' 92 /* A computed-goto dispatch. The branch cleanup must NOT forward/bypass the 93 * &&label-referenced blocks; doing so would corrupt the jump table. p() 94 * returns 1+10+100+1000 == 1111 by walking the table L0 -> Ld via L1 -> L2. */ 95 int p(void) { 96 static const void *tab[] = { &&L0, &&L1, &&L2, &&Ld }; 97 int acc = 0, n = 0; 98 goto *tab[n]; 99 L0: acc += 1; goto *tab[1]; 100 L1: acc += 10; goto *tab[2]; 101 L2: acc += 100; goto *tab[3]; 102 Ld: acc += 1000; 103 return acc; 104 } 105 EOF 106 107 GOBJ="$WORK/cgoto.o" 108 "$KIT" cc -target aarch64-linux-gnu -O1 -c "$GSRC" \ 109 -o "$GOBJ" > "$WORK/cgoto.cc.out" 2>&1 110 "$KIT" nm "$GOBJ" > "$WORK/cgoto.nm" 2>&1 111 # The &&label control-flow-block symbols must be defined (a [dDrR] / text def), 112 # never left undefined (U) -- an undefined .Lcfblk means a label target was 113 # dropped/bypassed by forwarding. 114 if grep -Eq '[[:space:]][uU][[:space:]]+\.Lcfblk' "$WORK/cgoto.nm"; then 115 fail "computed-goto label target is undefined (W9 bypassed a &&label block)" \ 116 "$WORK/cgoto.nm" 117 fi 118 119 # Runtime correctness through the in-process JIT, using a small-total program so 120 # the exit code is unambiguous (exit codes are u8; 1111 would wrap mod 256). 121 SSRC="$WORK/cgoto_small.c" 122 cat > "$SSRC" <<'EOF' 123 int p(void) { 124 static const void *tab[] = { &&L0, &&L1, &&Ld }; 125 int acc = 0, n = 0; 126 goto *tab[n]; 127 L0: acc += 2; goto *tab[1]; 128 L1: acc += 40; goto *tab[2]; 129 Ld: acc += 0; 130 return acc; /* 2 + 40 == 42 */ 131 } 132 EOF 133 for opt in -O0 -O1; do 134 if "$KIT" run "$opt" -e p "$SSRC" > "$WORK/cgoto_small_$opt.out" 2>&1; then 135 rc=0 136 else 137 rc=$? 138 fi 139 if [ "$rc" -ne 42 ]; then 140 fail "computed-goto runtime wrong at $opt: exit $rc (want 42)" \ 141 "$WORK/cgoto_small_$opt.out" 142 fi 143 done 144 145 printf 'o1_branch_cleanup: OK (W10 x==x fold, W10 loop fold, W9 &&label guard)\n'