BPF verifier gains scalar evolution to widen bounded loops

The Linux BPF verifier is set to gain scalar evolution analysis, a classical compiler technique that should let it accept more realistic bounded loops without exhaustively exploring every iteration.

Eduard Zingerman posted the second version of a large series to the BPF mailing list that builds algebraic expressions for how registers change inside a loop body. Those expressions yield iteration counts and value ranges, so an induction variable that simply counts from 0 to 9 can be treated as the interval [0..9] rather than ten separate states. The same machinery relaxes long-standing limits on memory accesses through pointers whose offsets vary inside the loop, including stack slots and BTF-typed objects.

Today the verifier often widens or rejects such patterns because precise tracking explodes. Scalar evolution, drawing on work by Robert van Engelen on chains of recurrences, gives it a compact summary instead. Supporting pieces compute the immediate-dominator tree and loop nest hierarchy, extend liveness information, and introduce stepped interval representations so that stride-aware pruning remains sound.

The change matters for anyone writing non-trivial BPF programs: packet parsers, iterators, and map-walking helpers that use ordinary counted loops should face fewer artificial restrictions while the safety guarantees stay intact. Extensive selftests cover nested and irreducible loops, helper side effects, and the new base/step reasoning. The series targets bpf-next.