diff options
| author | Eduard Zingerman <eddyz87@gmail.com> | 2026-10-09 03:47:39 -0700 |
|---|---|---|
| committer | Alexei Starovoitov <ast@kernel.org> | 2026-10-09 20:29:13 +0000 |
| commit | f414d20879ae1bac413619b8352701a7da2a1c0e (patch) | |
| tree | 75149ecc98ef43d4ae3d2ce37a63b63e513a06c9 /include/linux | |
| parent | 89e72f81a45576b0abe31a509a2660f3dc0c5d21 (diff) | |
bpf: Save DFS postorder numbers for program instructions
Dominator intersections and SCEV worklist scheduling need to compare
instructions by their DFS postorder rank. Save per-instruction
postorder numbers alongside the existing postorder sequence.
This commit modifies bpf_compute_postorder() to actually do the DFS
traversal, instead of scheduling traversal of all siblings at once.
Consider a graph:
A -> B
A -> C
C -> B
Old result: C, B, A
DFS result: B, C, A
Fixes: efcda22aa541 ("bpf: compute instructions postorder per subprogram")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-21-bcba9bc53ac9@gmail.com
Diffstat (limited to 'include/linux')
| -rw-r--r-- | include/linux/bpf_verifier.h | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 2560754ed56c..bd7733fbe930 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1036,6 +1036,7 @@ struct bpf_verifier_env { * see bpf_subprog_info->postorder_start. */ int *insn_postorder; + int *postorder_nums; int cur_stack; /* current position in the insn_postorder vector */ int cur_postorder; |