[X86] GenericScheduler's RegCritical heuristic costs ~3% on a large AVX-512 loop

This is essentially a successor to https://github.com/llvm/llvm-project/issues/212375 with more measurements, still done with LLM assistance, but I have audited and edited this before sending here (as much as someone who is not a compiler engineer can).

My earlier numbers compared BLAKE3's C intrinsics against its hand-written assembly in https://github.com/llvm/llvm-project/issues/212375 used stable release. That comparison was not fair to the C: the stable kernel had real source-level deficiencies that have since been fixed in https://github.com/BLAKE3-team/BLAKE3/pull/573. All numbers below use that branch (specifically commit `7138c34daeed270df37ce0fd2a63dafab1a2ed42` if that PR gets updated over time), so what remains is a codegen difference rather than a source one.

## Summary

On BLAKE3's 16-lane AVX-512 compression kernel, scheduling for register pressure produces materially worse code than not scheduling for pressure at all: `-mllvm -misched-regpressure=false` is worth **+2.7%** on Cascade Lake and **1.9 of the 3.3 percentage points** separating the compiled intrinsics from the hand-written assembly in the same repository.

The region genuinely needs more registers than exist, so some spilling is unavoidable. The heuristic is not failing to prevent spills - it is choosing worse ones.

I am reporting rather than proposing a patch, and the reason is not that "it is wrong on average": the sign of the effect flips between two kernels in the same library, and spill counts predict the wrong sign for both. See "The same flag regresses the sibling AVX2 kernel" below. Details of the predicates I tried and why each failed are in the last two sections, to save anyone repeating them.

## Reproducer

BLAKE3 branch from https://github.com/BLAKE3-team/BLAKE3/pull/573 - the current stable release has source-level deficiencies that PR fixes, so comparing the release against its own assembly is not a fair test of codegen.

```bash
git clone -b improve-avx2-avx512-c-rust https://github.com/nazar-pc/blake3
clang -O3 -mavx512f -mavx512vl -Iblake3/c -c blake3/c/blake3_avx512.c -o a.o
clang -O3 -mavx512f -mavx512vl -Iblake3/c -mllvm -misched-regpressure=false \
-c blake3/c/blake3_avx512.c -o b.o
```

Benchmark `blake3_hash_many_avx512` with 16 inputs x 16 blocks per call.
`blake3_avx512_x86-64_unix.S` in the same repo is the natural reference: same algorithm, hand-scheduled, no compiler scheduling involved.

## Performance

Generic tuning throughout, `taskset` to one core, best of 9 randomized interleaved rounds, 1 MiB working set.

Zen 4 Threadripper:

| | MB/s | vs asm |
|---|---|------------|
| assembly | 9756.6 | - |
| default | 9437.4 | -3.27% |
| `-misched-regpressure=false` | **9621.3** | **-1.39%** |
| `-enable-misched=false` | 9618.6 | -1.41% |

Cascade Lake Xeon, three independent sweeps:

| | MB/s | vs asm |
|---|---|-----------|
| assembly | 6604 / 6584 / 6595 | - |
| default | 6386 / 6371 / 6373 | -3.3% |
| `-misched-regpressure=false` | **6560 / 6544 / 6547** | **-0.7%** |

Two microarchitectures agreeing closely. Disabling *only* the pressure heuristic is indistinguishable from disabling the whole scheduler, so everything else the scheduler does here is neutral. At an 8 MiB working set the effect persists (Zen 4: -2.51% default, -1.03% with the flag).

## What the scheduler is doing

`llc -O3 -debug-only=machine-scheduler`, hot region (917 scheduling units):

```
FR16X Limit 32 Actual 48
Excess PSets: FR16X
```

FR16X's limit is 32 and x86-64 has exactly 32 zmm registers, so 48 values are live at peak against 32 registers. The source agrees: `h_vecs[8]` is live across the whole block loop with `v[16]` and `m[16]` inside it - 40 before transpose temporaries. **At least 16 spills are mandatory in this region.**

Effect on the hot loop body, per iteration:

| | instructions | vector spill stores / reloads | stack frame |
|---|---|---|---|
| default | 1126 | 14 / 10 | 1176 B |
| `-misched-regpressure=false` | 1094 | **6 / 4** | 824 B |

## The same flag regresses the sibling AVX2 kernel

`blake3_avx2.c` in the same tree, built the same way, is an 8-lane version of the same algorithm against 16 ymm registers. The scheduler reports `FR16 Limit 16 Actual 37` for it - 2.3x over the limit, where the AVX-512 kernel
is 1.5x over.

Cascade Lake Xeon, 1 MiB working set, three independent sweeps:

| AVX2 kernel | best MB/s |
|---|---|
| assembly | 3983 / 3971 / 3972 |
| default | **3497 / 3493 / 3497** |
| `-misched-regpressure=false` | 3437 / 3431 / 3429 |

The flag costs **1.8%** here, and 1.9% at an 8 MiB working set. Its spill counts say the opposite: 36340 loop-weighted with the flag against 38560 without, and 385 plain spills against 409.

So within one library, one source tree and one set of compiler flags:

| kernel | effect of the flag | what spill counts predicted |
|---|---|---|
| AVX-512 16-lane | **+2.7%** | better |
| AVX2 8-lane | **-1.8%** | better |

This is the core difficulty. It is not that the heuristic is right on average and this kernel is unlucky - the sign of the change is not recoverable from any static signal I have found, so it cannot be validated by compiling a corpus. It has to be run.

## Which heuristic

In `GenericScheduler::tryCandidate`, `RegExcess` and `RegCritical` are consulted before latency, clustering and node order - only `tryBiasPhysRegs` precedes them. Isolating the two:

| config | loop-weighted spills | spills in hot function |
|---|---|---|
| default | 14933 | 180 |
| `RegExcess` disabled | 15303 | 180 |
| **`RegCritical` disabled** | **10924** | **140** |
| `-misched-regpressure=false` (both) | 12323 | 152 |
| both disabled via separate flags | 16224 | 191 |

`RegExcess` is harmless here; `RegCritical` accounts for all of it. The two interact non-monotonically - disabling both individually is worse than disabling either alone.

## Why the obvious fixes do not work

**Spill counts do not predict performance for this kernel.** `RegCritical` disabled has strictly better spill numbers than `-misched-regpressure=false` (140 vs 152 spills, 10924 vs 12323 loop-weighted) and measures **slower**:

| 1 MiB, 3 sweeps | best MB/s | gain over default |
|---|---|---|
| `RegCritical` disabled | 6485 / 6457 / 6488 | +1.6% |
| `-misched-regpressure=false` | 6560 / 6544 / 6547 | **+2.7%** |

Ranked by spills the order is RegCritical-off, then regpressure-off, then default. Ranked by throughput it is regpressure-off, then RegCritical-off, then default. The orderings disagree - and on the AVX2 kernel above, spill counts get the *sign* wrong, not merely the ordering. A predicate search driven by spill counting is searching the wrong space.

Gates I implemented and measured anyway. Each was verified faithful first: with the threshold set so it fires everywhere, output is byte-identical to`-misched-regpressure=false`. Corpus is every `llvm/test/CodeGen/X86/*.ll` that compiles standalone (4451 files), spill comments weighted by loop-nesting depth, excluding three files that alone are 99% of the absolute total.

| gate | corpus | files better / worse |
|---|---|---|
| blanket `-misched-regpressure=false` | +0.61% | 10 / 125 |
| `RegCritical` disabled | -1.58% | 19 / 24 |
| region peak pressure >= 300% of limit | +1.18% | 11 / 106 |
| region peak pressure >= 145% of limit | +0.34% | 4 / 72 |
| region larger than 400 instructions | +2.52% | 3 / 49 |
| pressure ranked below latency | 0.00% | 0 / 0 |

Excess ratio does not separate the populations - regions where the flag helps span 1.2x-5.4x, regions where it hurts span 1.9x-18x. Region size does not either: the `vector-interleaved-*` tests have both large regions and very high pressure, and there the heuristic genuinely helps.

## Notes for anyone reproducing this

* **A translation-unit spill count misses this bug entirely.** BLAKE3's total is 290 either way while its hot loop halves; a whole-file corpus scan classifies this case as "no change".
* Corpus aggregates are dominated by a single file (`vector-replicaton-i1-mask.ll` is 99.3% of the weighted total). Exclude it or you are measuring one test.
* `grep -c` exits 1 on zero matches, which silently drops every file with no spills from a naive scan.
* Ranking pressure below latency changes nothing across the whole X86 corpus because `tryLatency` almost never fires there - that corpus cannot validate latency-related changes.
* More fundamentally, `llvm/test/CodeGen/X86` is not runnable: no `main`, no workload, nothing to time. It can only yield spill counts, and per the AVX2 result above those do not carry the sign of the performance change. Validating a fix needs runnable benchmarks (llvm-test-suite or similar), not a larger corpus scan.

## Environment

LLVM trunk `2e3553def14cbc819013c107ff3edd4fb08e348c`, Release + assertions, X86. Confirmed on Cascade Lake Xeon (model 85 stepping 7) and Zen 4 Threadripper 7970X.

Investigation done with LLM assistance; every number above was produced by running the commands described.