This patch set introduces a simple live register DFA analysis. The analysis is performed as a separate step before the main verification pass, and results are stored in `env->insn_aux_data` for each instruction. This change improves handling of iterator/callback-based loops, as regular register liveness marks are not finalized while loops are being processed. See veristat results for selftests and sched_ext in patch #2. The patch set was tested in branch [1] by disabling the current register parentage chain liveness computation, using DFA-based liveness for registers while assuming all stack slots as live. No notable regressions were found in test_progs-based tests. Note: For regular subprogram calls, the analysis conservatively assumes that registers r1-r5 are used and that r0 is used at each `exit` instruction. Experiments in [1] show that adding precise handling for these cases has no impact on verification performance for selftests and sched_ext. This was previously shared as RFC [2]. Changes since RFC: - The parameter count for helpers and kfuncs is now taken into account. - The analysis is now enabled only in privileged mode (Alexei); - The `copy_verifier_state()` bug fix was merged separately and is no longer a part of this patch set. [1] https://github.com/eddyz87/bpf/tree/liveregs-dfa-std-liveregs-off [2] https://lore.kernel.org/bpf/20250122120442.3536298-1-eddyz87@xxxxxxxxx/ Eduard Zingerman (3): bpf: simple DFA-based live registers analysis bpf: use register liveness information for func_states_equal selftests/bpf: test cases for compute_live_registers() include/linux/bpf_verifier.h | 7 + kernel/bpf/verifier.c | 394 +++++++++++++++-- .../testing/selftests/bpf/prog_tests/align.c | 11 +- .../bpf/prog_tests/compute_live_registers.c | 9 + tools/testing/selftests/bpf/progs/bpf_misc.h | 12 + .../bpf/progs/compute_live_registers.c | 397 ++++++++++++++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- 8 files changed, 804 insertions(+), 38 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/compute_live_registers.c create mode 100644 tools/testing/selftests/bpf/progs/compute_live_registers.c -- 2.48.1
