A bundle split twice around call clobbers spills in the call-free loops it spans #268

Summary

With MAX_SPLITS_PER_SPILLSET = 2, a bundle that needs a few splits to get
around call clobbers reaches the limit and falls back to
split_into_minimal_bundles. That puts every gap between uses into the spill
bundle. The spill bundle covers the original bundle's whole range, calls
included, so it gets a stack slot. A value that is live across calls in an outer
loop, and updated in a call-free inner loop, is then loaded and stored on every
iteration of the inner loop, with free registers available.

Reproducer

spill-in-loop.clif (attached, 1220 lines): a real function, tract's
wasm_i32_4x1 int8 matrix-vector kernel, emitted by wasmtime 49
(wasmtime compile --emit-clif) with an x86_64 AVX2/AVX512 target header added.
Run it on Cranelift main (dcfbea188d), which uses regalloc2 0.15.2:

CRANELIFT_TEST_BLESS=1 clif-util test spill-in-loop.clif

The inner loop (block58 in the CLIF) has two vector accumulators. The first
stays in a register; the second goes through the stack:

vpmaddwd %xmm0, %xmm4, %xmm0
vpaddd   %xmm1, %xmm0, %xmm1        ; first accumulator, in a register
...
vpmaddwd %xmm2, %xmm0, %xmm0
movdqu   0x10(%rsp), %xmm5          ; second accumulator: reload,
vpaddd   %xmm5, %xmm0, %xmm5
movdqu   %xmm5, 0x10(%rsp)          ; update, store, every iteration
testl    %edi, %edi
jne      <loop>

Only %xmm0–%xmm5 are used in the loop.

What happens

From the trace-log output (RUST_LOG=regalloc2=trace):

1. Blockparam merging puts the second accumulator's in-loop vregs (v1081,
   v1767) into one bundle with the long-lived value they come from (v230 and
   its outer-loop block params v1150, v1184, v1130, …), about 30 vregs in
   all. That bundle (bundle15) spans the function's outer dispatch loop,
   including the blocks that make calls.
2. Every vector register is clobbered across a call, so the bundle is split:
   split bundle LiveBundleIndex(15) at progpoint634-post, then at progpoint626-post.
3. The third conflict hits the limit: Splitting bundle LiveBundleIndex(15) into minimal bundles. The inner loop's def and use each get a one-instruction
   bundle, and the range between them is in the spill bundle, which crosses the
   calls and ends up on the stack.

Confirming that it is the calls and the limit:

• With the calls removed from the CLIF (replaced by constants), both
  accumulators stay in registers.
• Sweeping MAX_SPLITS_PER_SPILLSET on this function:

Impact

On wasmtime with the inner loop's other bottleneck already removed
(bytecodealliance/wasmtime#14848), the kernel is 3–12% faster with the
spill gone, depending on shape:

Two runs each, pinned to one core. A scalar kernel in the same module, which has
no such loop, is unchanged (12.8–13.4 µs at 256 × 256 in all four runs).

History

• Limit split count per original bundle with fallback 1-to-N split. #59 added the per-spillset split counter and the minimal-bundle fallback, with
  a limit of 10, for the quadratic case in Large compile-time-memory-usage regression with regalloc2 wasmtime#4291.
• Initial support for overlapping LiveRanges #122 (overlapping live ranges) lowered the limit from 10 to 2, alongside its
  compile-time improvements; the PR does not discuss that value separately.
• Redefine a minimal bundle to have only one LiveRange. #214 redefined minimal bundles; Release v0.11.3 (but not v0.11.2) hangs while compiling a few specific wasm modules #218 was a compile-time hang it caused, fixed
  in Fix minimal-bundle splitting to avoid infinite loops. #220 (Cranelift: roll forward to RA2 once bytecodealliance/regalloc2#218 is fixed wasmtime#10562 tracked rolling forward).
• Spill for VReg lifetimes instead of SpillSet lifetimes #171 tried to spill per vreg rather than per spillset, and was closed over
  execution-time regressions.
• Allocation results in unnecessary moves around destructive operations #265 is another open allocation-quality report, with a different pattern.

Possible fixes

• Raise the limit. 4 is the smallest value that fixes this function; a PR with
  measurements follows.
• Make the fallback less pessimistic: give the spill bundle's ranges inside loops
  free of clobbers a chance at a register, or count only splits that did not
  make progress. More involved; I have not tried it.

spill-in-loop.clif.txt