Re: [PATCH bpf-next 16/37] bpf: Count loops whose first value or bound is a range

["Alexei Starovoitov" <alexei.starovoitov@gmail.com>]

On Tue, Nov 03, 2026 at 11:26 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> On Tue, 2026-11-03 at 23:40 +0000, Alexei Starovoitov wrote:
>
>> +/* What is known about a scalar or about the offset of a pointer. */
>>  struct scev_value {
>> -	u64 value;	/* scalar value or a pointer offset */
>> +	u64 umin, umax;
>> +	s64 smin, smax;
>> +	u32 u32_min, u32_max;
>> +	s32 s32_min, s32_max;
>>  	int ptr_reg;	/* SCEV register identifying the pointer origin, or -1. */
>>  };
>
> Nice set of improvements.

Thanks for the quick review. Much appreciate it.

> Quick question: can the above use cnum{32,64} instead of direct bounds?
> Reason being, that I thought compute_backedge_taken_count() can be
> expressed in terms of cnums as well, in which case there would be no
> need to split it as two functions.

Yes. Will switch to r64 + r32 in a follow up.
scev_value_add() becomes cnum64_add() + cnum32_add().
It's more precise too. [-1, 0] + 1 is [0, 1] for an unsigned compare.
The direct bounds make it [0, U64_MAX].

cnums don't remove the split though. They merge signed and unsigned.
The split is between constants and ranges.

> cnums aside, it appears surprising that both compute_backedge_taken_count()
> and compute_backedge_taken_max() are necessary.
> For example, I'd expect that compute_backedge_taken_max() should be
> expressible using compute_backedge_taken_count() as:
>
>   high  := compute_backedge_taken_count(..., min(initial), step, max(bound), ...);
>   low   := compute_backedge_taken_count(..., max(initial), step, min(bound), ...);
>   ... overflow check for iv with `low` and `high` ...
>
> Or vice-versa, compute_backedge_taken_count() seem to be expressible
> as a special case for compute_backedge_taken_max() with ranges
> [initial, initial] and [bound, bound].
>
> Is there some precision loss I don't understand?

well... Below _count() and _max() are the two functions.

The problem

The value that ends the loop depends on (bound - first value) % step.

  for (u64 i = first; i > 0; i -= 2)

  first   i at the latch     _count()
  -----   ----------------   ---------------------
  10      10 8 6 4 2 0       5
  11      11 9 7 5 3 1 -1    none, -1 wraps around
  12      12 10 8 6 4 2 0    6

For 10..12 both ends have a count, and 11 wraps around.
A range needs a check that holds for each remainder.
The value that ends the loop is less than a step behind the bound.
Here the worst one is 0 - 2 + 1 = -1, so 10..12 has no count.
The same check rejects [10, 10], and _count() accepts 10.

The options

Four ways to get a count for constants and for ranges:

  option                           what breaks
  -------------------------------  ------------------------------
  _count() for constants and       nothing, it is two functions
  _max() for ranges (the patch)
  _max() from two _count() calls   11 in the example
  _count() as _max() of [c, c]     constants lose counts
  one function on top of cnums     the same as [c, c]

Two _count() calls

The overflow check in _count() is exact for one first value.
It passes for both ends in the example, so it says nothing about 11.
The check has to come from the bound, and that is what _max() does.
_count() also returns false when the latch is false at first.
'low' of 'i = 0; i < (n & 15)' is _count(0, 1, 0), which is false.
The division is all that the two can share.

_max() of [c, c]

The two differ in what must not wrap around and in '!='.

                _count()                     _max()
  -----------   --------------------------   ----------------------------
  wrap around   first + step * count         bound + step - 1 for '<'
  '!='          step divides bound - first   step is 1 or -1, each first
                                             value in front of each bound

post32_lt, post32_sgt and post32_slt_max end the loop at U32_MAX,
S32_MIN and S32_MAX. The check of _max() gives them no count.
pre_ne, post_ne and pre_ne_wrap_up have a step of 2.
The '!=' rule of _max() gives them no count.

_max() can restore both with branches for constants.
That is the same two calculations in one function.
imo it's better to keep _count() as is.
It's exact and the tests cover it.

But I'm open to any other approach that my bots couldn't think of.

> Also, you'd consider it a nit, but compute_backedge_taken_count() has
> a nice set of comments explaining where each condition is coming from.

Makes sense. Will add such comments to _max() in follow up.