Skip to contentSkip to conversation

Scalar Evolution for BPF Verifier

LSF/MM/BPF TOPIC Eduard Zingerman 1 participant 1 message Feb 19 BPF

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

Hi Everyone,

I would like to suggest "Scalar Evolution for the BPF Verifier" as a topic for discussion at the upcoming LSF/MM/BPF conference.

There are several ways to encode a loop in a BPF program:
1. Directly, using a loop counter together with for(){}, while(){} or goto statements.
2. Using iterators in conjunction with for(){}, while(){} or goto statements.
3. Using the bpf_loop() helper and a callback function.

While (1) is the most natural way to express loops for many use cases, it also has significant verification drawbacks: each loop iteration is verified separately and in full. When combined with nested loops or a high degree of branching within the loop body, this can quickly lead to hitting the 1M instruction verification limit.

Scalar Evolution is a static analysis technique used by both LLVM and GCC to estimate the number of iterations a loop in a program’s control-flow graph will execute at runtime. The core idea of the technique is a one-pass traversal of the program’s control-flow graph, assigning recurrence relations to variables within loop bodies. For example, consider the program below:

    while (i != 10) {
      f(i);
      i++;
      g(i);
    }

Scalar Evolution analysis would first track the evolution of the variable 'i' within the loop body:

    while (i != 10) { // i = i0 at loop entry <---. Arrive back to
      f(i);           // i = i0                   | the loop entry 
      i += 2;         // i = i0 + 2               | with i = i0 + 2.
      g(i);           // i = i0 + 2               |
    }                 // '------------------------'

It would then conclude that the recurrence relation for 'i' at the loop header is 'i0 + 2*k', where 'k' is the loop iteration number. When combined with loop nesting information and information about conditions guarding loop back-edges, this recurrence relation can be used to compute the number of iterations the loop will execute:
'k = (10 - i0) / 2'.

I am currently working on adapting this technique for the BPF verifier and hope to have a working RFC ready sometime next month. At the conference, I would like to present the main ideas behind this adaptation and discuss both the coding patterns understood by this analysis and those for which it fails to provide improvements.

References:
- R. van Engelen, "Symbolic Evaluation of Chains of Recurrences for Loop Optimization"
https://www.researchgate.net/publication/2801813_Symbolic_Evaluation_of_Chains_of_Recurrences_for_Loop_Optimization
- R. van Engelen, "Efficient Symbolic Analysis for Optimizing Compilers"
https://www.researchgate.net/publication/2385991_Efficient_Symbolic_Analysis_for_Optimizing_Compilers
- R. van Engelen, "The CR\# Algebra and its Application in Loop Analysis and Optimization"
https://www.researchgate.net/publication/382316876_The_CR_Algebra_and_its_Application_in_Loop_Analysis_and_Optimization
- LLVM SCEV implementation source code
https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ScalarEvolution.cpp
- John Fastabend, "Using SCEV to establish pre and post-conditions over BPF code"
https://lpc.events/event/4/contributions/450/
- My work-in-progress implementation:
https://github.com/eddyz87/bpf/tree/scev

Best regards,
Eduard Zingerman