Register deprivation: spills and runtime under forced register scarcity

We compiled nine small kernels while progressively reserving registers with gcc -ffixed-<reg>, then measured spills and runtime on one machine. Reserving registers reliably increases spills, but the static spill count is a weak predictor of the runtime cost, and one kernel gains 23 spills with no slowdown at all. Code is at https://github.com/rjpower/spillbench; the numbers behind every figure below are in results.json. TL;DR Removing registers slows 8 of 9 kernels by 14–76% at the tightest budget; the ninth (SipHash) does not move. Results are bit-identical at every budget, so the reservation only changes generated code, not the computation. Added spill instructions correlate weakly with slowdown (Pearson r = 0.55 over 105 points). The cost of one added spill ranges from about 0%/spill (SipHash) to 2.2%/spill (FIR filter), a ~30× spread. The effect is specific to the register file the kernel uses. Reserving XMM registers on SHA-256 costs +5.6%; reserving GP registers costs +33%. Reserving GP registers on a double-precision matmul is flat; reserving XMM costs +34%. GCC auto-vectorizes part of SHA-256 with SSE at -O2, so reserving XMM is not inert for that integer kernel: its stack-spill count rises 8→65 while runtime moves +5.6%. Measured with gcc 15.2.0 -O2 on an Intel Xeon E-2236, wall-clock, minimum of 15 repetitions on one pinned core. Setup We test three hypotheses: H1: fewer registers produce more spills and slower code, monotonically in the number of registers removed. H2: the slowdown is specific to the register file the kernel actually uses (integer kernels to GP registers, floating-point kernels to XMM). H3: the static spill count predicts the runtime cost. We reserve registers with gcc -ffixed-<reg>, which removes a register from the allocator's pool for the whole compilation. We recompile each kernel once per budget, adding one reservation each pass. GP kernels give up r15 r14 r13 r12 rbp rbx r11 r10 r9 r8 in that order (15 allocatable registers down to 5; rsp is never allocatable). XMM kernels give up xmm15 … xmm4 (16 down to 4). We never reserve the ABI registers (rax rcx rdx rsi rdi, xmm0–3), which argument passing and instructions like mul and variable shifts require. Six integer kernels exercise the GP file, three floating-point kernels exercise the XMM file. Each is a single C function with a known-answer test. KernelFileWhat it isCorrectness check ChaCha20GP20-round stream cipher block, 16×32-bit stateRFC 8439 §2.3.2 keystream SHA-256GPcompression function, 8 vars + 64-word scheduleSHA-256("abc") SipHash-2-4GPkeyed hash, 4×64-bit ARXreference vector (15-byte msg) Integer matmulGP4×4 register-blocked int64 micro-kernelvs. naive triple loop LZ77 compressGPhash-chain match findercompress→decompress round-trip QuicksortGPin-place recursive sort of int32output is sorted Double matmulXMM4×4 register-blocked f64 micro-kernelvs. naive triple loop FIR filterXMM16-tap filter, 8 output lanesvs. naive tap sum MandelbrotXMMescape-time, few live doubles per pixelescape counts at known points For the spill metric, we disassemble the hot function (objdump) and count instructions that reference a fixed stack slot (…(%rsp)), excluding indexed array access. This is a static proxy for spill/reload traffic. We do not have dynamic spill counts: hardware performance counters are disabled in this environment (perf_event_paranoid=4). For timing, a Rust harness dlopens each build, runs its known-answer test, and times the whole workload with a monotonic clock, keeping the minimum over 15 repetitions on one pinned core. Each kernel's workload is sized to ~100 ms. Machine: Intel Xeon E-2236 @ 3.40 GHz, gcc 15.2.0, -O2 -fPIC -shared. Every build passes its known-answer test, and every kernel returns the same checksum at all budgets. Reservation is a pure allocation constraint here; it never changed a result. Result 1: removing registers slows most kernels, but not all Eight of nine kernels slow down as registers are removed; SipHash-2-4 does not. Figure 1. Runtime vs registers reserved, integer and float kernels Figure 2. Spill count vs registers reserved Figure 3. Slowdown at the tightest register budget KernelFileRuntime full→min (ms)SlowdownSpills full→min FIR filterXMM135.5 → 238.9+76%8 → 43 Integer matmulGP140.5 → 199.7+42%60 → 82 Double matmulXMM131.5 → 176.4+34%66 → 100 SHA-256GP89.4 → 119.0+33%8 → 80 QuicksortGP134.2 → 171.7+28%4 → 49 ChaCha20GP88.5 → 110.0+24%55 → 121 LZ77 compressGP123.2 → 146.8+19%39 → 115 MandelbrotXMM101.6 → 116.2+14%0 → 7 SipHash-2-4GP79.4 → 78.1−2%0 → 23 Spill counts rise for all nine kernels. Runtime rises for eight. H1 holds in direction but not in shape: neither curve is cleanly monotonic in the budget. Static spills drop when a register is removed in a few cases (ChaCha20 and Quicksort each have one such step), and the runtime curves have local dips within measurement noise (LZ77 has 5 steps that decrease by more than 0.5 ms as budget falls, SipHash 3, Quicksort 3). The allocator is not monotone, and the runtime signal is noisy at the ~1% level even with minimum-of-15 timing. Integer matmul starts at 60 spills with a full register file: its 4×4 block holds 16 int64 accumulators, already more than the 15 allocatable GP registers, so it spills before we take anything away. Result 2: the spill count does not predict the slowdown The number of added spills explains little of the slowdown. Figure 4. Added spills vs slowdown, all kernel-budget points Across all 105 (kernel, budget) points, Pearson r between added spills and slowdown is 0.55. The per-kernel cost of a spill varies by about 30×: KernelAdded spills at minSlowdownSlowdown per added spill FIR filter+35+76%2.18 %/spill Mandelbrot+7+14%2.05 %/spill Integer matmul+22+42%1.92 %/spill Double matmul+34+34%1.00 %/spill Quicksort+45+28%0.62 %/spill SHA-256+72+33%0.46 %/spill ChaCha20+66+24%0.37 %/spill LZ77 compress+76+19%0.25 %/spill SipHash-2-4+23−2%≈0 %/spill Integer matmul reaches +42% with only 22 added spills; LZ77 adds 76 spills for +19%. SipHash adds 23 spills with no measurable slowdown. We think the explanation is that the stack lives in L1, so a spill that is not on the critical dependency path is nearly free, while a spill inside a tight recurrence (the ARX chain, the accumulator update) serializes on the reload latency. The static count does not distinguish the two. Result 3: the slowdown is specific to the register file Reserving the register file a kernel does not use is much cheaper than reserving the file it does. Figure 5. Reserving the wrong register file barely moves runtime We reran two kernels against the opposite register file. Reserving GP registers on the double-precision matmul is flat (131.9 → 131.1 ms across 0→10 reserved); reserving XMM on the same kernel costs +34%. This is the clean case: the floating-point work is XMM-bound and has GP registers to spare. SHA-256 is the messy case. Reserving XMM costs +5.6%, against +33% for GP. But XMM reservation is not inert: SHA-256's stack-spill count rises 8→65. Its hot function contains 155 XMM-referencing instructions at full budget, because GCC auto-vectorizes the message-schedule byte-swapping and word computation with SSE at -O2. Reserving XMM forces that work back onto GP registers and the stack, which shows up as stack spills but barely as runtime, because the schedule is not the critical path. So H2 holds for runtime, with the caveat that "the file the kernel uses" is not clean: GCC uses XMM opportunistically inside integer code. What surprised us Spill count is a weak runtime predictor (r = 0.55, 30× spread in cost per spill). We expected a tighter relationship, since the spill count is what the register-pressure story is usually told with. SipHash gains 23 stack spills for a −2% change in runtime. Spills off the critical path, into L1-resident stack, are close to free here. Quicksort is not a flat control. Its live set is small (two cursors, a pivot, a swap), but the partition loop still spills once the GP file is tight, and it slows +28%. Reserving XMM registers changed an integer kernel's stack-spill count by 8×, because GCC auto-vectorizes part of SHA-256. The register files are less separable than the "integer vs float" framing suggests. Removing a register sometimes lowers the static spill count. The allocator's output is not monotone in the size of the register file. Historical note: what would this have cost on x86-32? This section is extrapolation, not measurement. Read it as a back-of-envelope, not a result. 32-bit x86 had eight GP registers, but esp is never allocatable and ebp is usually the frame pointer, so real code had six or seven to work with, against fifteen here. Our sweep has points at exactly those budgets, so we can read the cost off the curve instead of guessing: Usable GP registersMean, 6 integer kernels32-bit-native kernelsHungriest (int matmul / SHA-256) 7 (≈ x86-32, frame ptr omitted)+13%+16%+27% / +14% 6 (≈ x86-32, frame ptr kept)+18%+15%+32% / +18% 5 (tighter than x86-32 ever was)+24%+26%+42% / +33% On this machine, going from 15 to 6–7 GP registers costs about 15% on a typical kernel and about 30% on the most register-hungry integer code. The popular "~30%" figure is defensible for the hungry tail, but it is roughly double the average kernel. Two things make this an under-estimate of the real 1990s cost. First, a 64-bit value occupies a register pair on x86-32, so the int64-heavy kernels (the matmul, SipHash's lanes) would have felt pressure our -ffixed count does not model. Second, and larger: the reason spills are cheap here is that the stack lives in L1 and out-of-order execution overlaps the reload with other work. Period hardware could not do that overlap. The latency gap itself was, if anything, smaller then. Approximate load-use latency for a first-level-cache hit, in core clocks: CPU (year)GP registerL1 hitnotes 80386 (1985)0—no on-chip cache; mov reg,[mem] ≈ 4 clk to external SRAM, DRAM adds wait states