hot_slot_order.sh (5120B)
1 #!/usr/bin/env bash 2 # Structural check for W1.0 hot-slot-low frame ordering (doc/plan/O1.md #### W1.0). 3 # 4 # At -O1 the frame is fully known before the body is emitted, so the optimizer 5 # presents the body spill slots to the backend in DESCENDING spill-traffic 6 # priority order (pass_native_emit.c). The bump allocator (native_frame_slot_alloc) 7 # then gives the hottest spills the smallest final displacement -- which is the 8 # cheapest to encode on every arch: 9 # 10 # x64 : disp8 [rbp - k] (1 disp byte, -128..127) vs disp32 (4 disp bytes). 11 # rv64 : single-instruction `ld/sd off(s0)` while off fits the +/-2KB imm12 12 # window; a far slot needs a 3-instruction `lui; addiw; add; ld 0(t)` 13 # build. 14 # 15 # The probe is a function with 16 hot accumulators updated EVERY loop iteration 16 # (so several must spill to the frame and they carry by far the highest spill 17 # cost) plus ~280 cold scalars that survive to the end. The cold pile pushes the 18 # total frame WELL past x64 disp8 (128B) and past rv64's imm12 window (2KB), so 19 # the layout MUST choose which slots get the cheap low offsets. W1.0 makes that 20 # choice the hot accumulators: the hot loop body then addresses them with the 21 # short/single-instruction form while the cold tail takes the far offsets. 22 # 23 # Gate is correctness, not byte-identity (W1.0 deliberately reorders slots); this 24 # guard pins the resulting addressing shape on x64 + rv64 (the arches where the 25 # doc expects a measurable win; aa64 is mostly subsumed by W1.1). 26 set -euo pipefail 27 28 ROOT="$(cd "$(dirname "$0")/../.." && pwd)" 29 KIT="${KIT:-$ROOT/build/kit}" 30 WORK="$ROOT/build/test/opt/hot_slot_order" 31 mkdir -p "$WORK" 32 33 SRC="$WORK/case.c" 34 { 35 echo 'typedef unsigned long long u64;' 36 echo 'extern u64 sink(u64 *);' 37 echo 'u64 hot_loop(const u64 *in, int n) {' 38 # 16 hot accumulators (more than the GP register file) -> the allocator must 39 # spill several; all carry the highest spill cost (touched every iteration). 40 for i in $(seq 0 15); do echo " u64 h$i = in[$i];"; done 41 # ~280 cold scalars -> inflates the frame past disp8 (128B) and imm12 (2KB). 42 for i in $(seq 0 279); do echo " u64 k$i = in[$((i % 64))] + ${i}u;"; done 43 echo ' for (int i = 0; i < n; i++) {' 44 echo ' u64 x = in[i & 63];' 45 for i in $(seq 0 15); do echo " h$i = (h$i ^ x) + h$(((i + 1) % 16));"; done 46 echo ' }' 47 # Keep the cold scalars live across the loop (low priority, far offsets). 48 echo " u64 ks[280];" 49 for i in $(seq 0 279); do echo " ks[$i] = k$i;"; done 50 echo ' sink(ks);' 51 printf ' return' 52 for i in $(seq 0 15); do printf ' h%d ^' "$i"; done 53 echo ' 0;' 54 echo '}' 55 } > "$SRC" 56 57 dump_for() { # $1 = -target triple, $2 = out tag 58 local triple="$1" tag="$2" 59 "$KIT" cc -target "$triple" -O1 -std=c11 -ffreestanding -nostdinc \ 60 -I"$ROOT/rt/include" -c "$SRC" -o "$WORK/$tag.o" > "$WORK/$tag.cc.out" 2>&1 \ 61 || { printf 'hot_slot_order FAILED: %s cc failed\n' "$tag" >&2 62 sed 's/^/ | /' "$WORK/$tag.cc.out" >&2; exit 1; } 63 "$KIT" objdump -d "$WORK/$tag.o" > "$WORK/$tag.dis" 2>&1 64 } 65 66 fail() { 67 printf 'hot_slot_order FAILED: %s\n' "$1" >&2 68 printf ' --- %s disassembly (head) ---\n' "${2:-}" >&2 69 [ -n "${2:-}" ] && sed -n '1,80p' "$WORK/$2.dis" | sed 's/^/ | /' >&2 70 exit 1 71 } 72 73 # ---- x64: hot accumulators must land in disp8 range ----------------------- 74 # Count frame accesses by displacement magnitude: disp8 = |off| <= 127, disp32 75 # otherwise. A large frame (cold tail) guarantees disp32 accesses exist; W1.0 76 # must also produce a healthy block of disp8 accesses -- the hot accumulators 77 # the loop touches every iteration. (Without ordering the hot slots could be 78 # pushed entirely into disp32, so a substantial disp8 count is the signal.) 79 dump_for x86_64-macos x64 80 x64_d8="$(grep -oE '\-?[0-9]+\(%rbp\)' "$WORK/x64.dis" | sed -E 's/\(%rbp\)//' \ 81 | awk '{v=$1<0?-$1:$1} v<=127{n++} END{print n+0}')" 82 x64_d32="$(grep -oE '\-?[0-9]+\(%rbp\)' "$WORK/x64.dis" | sed -E 's/\(%rbp\)//' \ 83 | awk '{v=$1<0?-$1:$1} v>127{n++} END{print n+0}')" 84 [ "$x64_d32" -gt 0 ] || fail "x64 frame not large enough (no disp32 access -- probe too small)" x64 85 [ "$x64_d8" -ge 8 ] || fail "x64 hot slots not in disp8 range (disp8=$x64_d8 disp32=$x64_d32)" x64 86 87 # ---- rv64: hot slots must stay single-instruction (inside imm12) ---------- 88 # A single-instruction frame access is `ld/sd reg, off(s0)`; a far slot needs a 89 # `lui; addiw; add; ld 0(t)` build. The big frame guarantees `lui` far-slot 90 # builds exist (cold tail past +/-2KB); W1.0 must keep the hot accumulators 91 # single-instruction, so the count of direct `(s0)` accesses must dominate. 92 dump_for riscv64-linux-gnu rv64 93 rv_single="$(grep -cE '(ld|sd) [a-z0-9]+, -?[0-9]+\(s0\)' "$WORK/rv64.dis" || true)" 94 rv_lui="$(grep -cE ' lui ' "$WORK/rv64.dis" || true)" 95 [ "${rv_lui:-0}" -gt 0 ] || fail "rv64 frame not large enough (no lui far-slot build -- probe too small)" rv64 96 [ "${rv_single:-0}" -ge 16 ] || fail "rv64 hot slots not single-instruction (single=$rv_single lui=$rv_lui)" rv64 97 98 printf 'hot_slot_order: OK (x64 disp8=%s/disp32=%s, rv64 single=%s/lui=%s)\n' \ 99 "$x64_d8" "$x64_d32" "$rv_single" "$rv_lui"