en Copyright 2015 Java http://kernelsources.org:8080/source/history/linux/kernel/bpf/loops.c#2fa579694ddf3a96454669c764ca0c06dea50817 bpf: Record basic-block ends in insn_aux_dataSCEV needs information about the program's basic-block structure.Piggyback on compute_predecessors() and setinsn_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 List of files: /linux/kernel/bpf/loops.c Fri, 09 Oct 2026 12:47:49 +0200 Eduard Zingerman <ezingerman@fb.com> http://kernelsources.org:8080/source/history/linux/kernel/bpf/loops.c#9ae7f5e8bf1d8be74797f937cdbeb730178a8c3d bpf: Compute loop hierarchySCEV needs to process loops from innermost to outermost, summarizingresults 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 List of files: /linux/kernel/bpf/loops.c Fri, 09 Oct 2026 12:47:42 +0200 Eduard Zingerman <eddyz87@gmail.com> http://kernelsources.org:8080/source/history/linux/kernel/bpf/loops.c#6254fb69328963be95ff9b2760e879a9220ae6c3 bpf: Compute immediate dominatorsSCEV needs to find an exit condition that dominates a loop's backedge;such conditions bound every loop iteration. Compute the immediatedominator 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 List of files: /linux/kernel/bpf/loops.c Fri, 09 Oct 2026 12:47:41 +0200 Eduard Zingerman <eddyz87@gmail.com>