linux-toradex.git/kernel/bpf/loops.c, branch master Linux kernel for Apalis and Colibri modules bpf: Record basic-block ends in insn_aux_data 2026-10-09T20:29:14+00:00 Eduard Zingerman ezingerman@fb.com 2026-10-09T10:47:49+00:00 2fa579694ddf3a96454669c764ca0c06dea50817 SCEV needs information about the program's basic-block structure. Piggyback on compute_predecessors() and set insn_aux_data->bb_end for an instruction if: - it has multiple successors, or - its sole successor has multiple predecessors, or - it is a jump instruction. 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-31-bcba9bc53ac9@gmail.com 
SCEV needs information about the program's basic-block structure.
Piggyback on compute_predecessors() and set
insn_aux_data->bb_end for an instruction if:
- it has multiple successors, or
- its sole successor has multiple predecessors, or
- it is a jump instruction.

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-31-bcba9bc53ac9@gmail.com
bpf: Compute loop hierarchy 2026-10-09T20:29:13+00:00 Eduard Zingerman eddyz87@gmail.com 2026-10-09T10:47:42+00:00 9ae7f5e8bf1d8be74797f937cdbeb730178a8c3d SCEV needs to process loops from innermost to outermost, summarizing results for nested loops. Add a pass to compute the loop structure. Use a non-recursive adaptation of the algorithm from: "A New Algorithm for Identifying Loops in Decompilation" by Wei et al. Record the loop hierarchy per instruction: - The field insn_aux_data->loop_header records the innermost loop header containing it. - The field insn_aux_data->loop records additional information about the loop if this instruction is a loop header (exits, backedges, irreducibility). 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-24-bcba9bc53ac9@gmail.com 
SCEV needs to process loops from innermost to outermost, summarizing
results for nested loops. Add a pass to compute the loop structure.

Use a non-recursive adaptation of the algorithm from:
"A New Algorithm for Identifying Loops in Decompilation" by Wei et al.

Record the loop hierarchy per instruction:
- The field insn_aux_data->loop_header records the innermost loop
  header containing it.
- The field insn_aux_data->loop records additional information about
  the loop if this instruction is a loop header (exits, backedges,
  irreducibility).

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-24-bcba9bc53ac9@gmail.com
bpf: Compute immediate dominators 2026-10-09T20:29:13+00:00 Eduard Zingerman eddyz87@gmail.com 2026-10-09T10:47:41+00:00 6254fb69328963be95ff9b2760e879a9220ae6c3 SCEV needs to find an exit condition that dominates a loop's backedge; such conditions bound every loop iteration. Compute the immediate dominator tree as a prerequisite for identifying such conditions. Use the iterative reverse-postorder algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper et al. 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-23-bcba9bc53ac9@gmail.com 
SCEV needs to find an exit condition that dominates a loop's backedge;
such conditions bound every loop iteration. Compute the immediate
dominator tree as a prerequisite for identifying such conditions.

Use the iterative reverse-postorder algorithm from:
"A Simple, Fast Dominance Algorithm" by Cooper et al.

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-23-bcba9bc53ac9@gmail.com