bpf: Support 32-bit linear scalar evolution

Representation
--------------

Represent ALU32 recurrences as:

  w0 += step  ->  (zext32 (linear r0 step))

Extend simplify() rules to maintain the above form for latch
expressions. E.g. for a post-condition loop such as:

     w0 = 0;
  l: w0 += 1;
     if w0 != 3 goto l;
     exit;

          SCEV at header: (zext32 (linear r0 1))
   Initial SCEV at latch: (zext32 (+ (zext32 (linear r0 1)) 1))
Simplified SCEV at latch: (zext32 (+ (zext32 (linear r0 1)) 1))
                          -> (zext32 (+ (linear r0 1) 1))
                          -> (zext32 (linear (+ r0 1) 1))

Iterations count computation
----------------------------

- Extract the main iteration-count logic from compute_max_iters() into
  compute_backedge_taken_count(). Reuse its 64-bit arithmetic after
  sign/zero extending the latch operands.

- Reject the computed count if the predicted exit value falls outside
  signed/unsigned 32-bit range, e.g.:

       w0 = 0x7ffffffe;
    l: w0 += 1;
       if w0 s<= 0x7fffffff goto l;

  The 64-bit computation predicts an exit at S32_MAX + 1, but the
  32-bit value wraps to S32_MIN and the comparison remains true.

- Handle mixed 64-bit/32-bit comparisons/recurrences only when initial
  bounds and step fit in 32-bit ranges, e.g.:

       w0 = 0;
       r1 = 0x100000003 ll;
    l: w0 += 1;
       if r0 != r1 goto l;

  Truncating the bound to 32 bits would predict three header visits.
  However, `w0 += 1` keeps r0 within [0, U32_MAX], so it can never
  be equal to the 64-bit bound.

Widened bounds computation
--------------------------

- Update linear_bounds() to truncate the initially computed 64-bit
  range to 32 bits, then zero-extend it to obtain the 64-bit range
  of iteration values. Step computation needs to handle:
  - unsigned 32-bit wraparound;
  - entry and zero-extended iteration values disagreeing on base/step.

- Union both ranges with the corresponding register ranges at entry,
  since the entry value need not be zero-extended.

- Extend `struct bounds` to keep both {32,64}-bit ranges and pass both
  to bpf_set_reg_range(). A 64-bit range alone loses useful 32-bit
  information, e.g.:

    entry = 0, step = -1, two header visits
    r64: [0, U32_MAX]
    r32: [-1, 0]

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261020-scev-32bit-v1-1-838f34f9f0cd@gmail.com

1 files changed, 1 insertions, 1 deletions

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 6606b341351e..5926f13ff43c 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1896,7 +1896,7 @@ int bpf_compute_subprog_arg_access(struct bpf_verifier_env *env);
 bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a,
 			    const struct bpf_reg_state *reg_b);
 int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
-		      struct cnum64 range, u16 base, u16 step);
+		      struct cnum64 r64, struct cnum32 r32, u16 base, u16 step);
 bool bpf_reg_union_compatible(const struct bpf_reg_state *a, const struct bpf_reg_state *b);
 int bpf_reg_union(struct bpf_verifier_env *env, struct bpf_reg_state *acc,
 		  const struct bpf_reg_state *src);