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

0 files changed, 0 insertions, 0 deletions