BPF verifier swaps scalar IDs for scalar-evolution links

Alexei Starovoitov has posted a large bpf-next change that retires scalar IDs in the BPF verifier and instead finds linked registers with scalar-evolution analysis run before the main pass.

Scalar IDs once marked when two scalars held the same value or differed by a constant, so a jump that bounded one could refine the others. That mechanism was brittle and costly. Links vanished on a second add, sign extension, or narrow spill; a jump could refine at most five live slots; every move had to assign or clear IDs; and states that differed only in those IDs were verified twice. Nothing tied a pointer to its index. Compilers routinely emit the awkward pattern: compute p = buf + i, then test i later. The verifier rejected safe map accesses even when the bound made the offset legal.

The new path builds expressions for whole subprograms. Values without a closed form get SSA-style names. At each conditional jump, analysis lists live registers and stack slots that equal the tested register plus a constant on every path to that jump, including through loops when the difference holds at the header and on every backedge. The main pass then refines those linked values with the tested range. Links are not stored in verifier state, have no fixed cap of five, and can describe a pointer as an address base plus the tested index.

That last point is the first use of scalar evolution outside loops and the practical win for string and record walks in map values: after the jump bounds the index, the pointer is recomputed so its offset matches. Related cleanups drop copy-of-induction-variable tracking that depended on IDs, recover links inside basic blocks of irreducible loops via local value numbering, and teach state-join heuristics to spot copies by matching ranges instead of IDs.

Once nothing consumed scalar IDs, assignment stopped. IDs for pointers, references, dynptrs, and iterators remain. Starovoitov reports some precision loss where only dynamic state knew a link (across frames, or on one of several paths to a jump), and one selftest had to change. Intersection of ranges can also be stricter than the old overwrite. Against selftests, Cilium, sched_ext, katran, bpfjailer, and Rust programs, verdicts held; overall instruction and state counts fell a few percent, more for Rust loads.