Re: [PATCH bpf-next v2 03/13] bpf: track low-32 scalar equality across zero-extending movs

[Eduard Zingerman <eddyz87@gmail.com>]

On Mon, 2026-09-21 at 21:55 +0000, Alexei Starovoitov wrote:
> On Mon Sep 21, 2026 at 7:44 PM UTC, Eduard Zingerman wrote:
> > > > > > 
> > > > > > Where:
> > > > > > - id == 0 => no id link
> > > > > > - full => all 64-bits of the register are identical to
> > > > > >           all 64-bits of a scalar value `id' (let's call it X).
> > > > > >           ∀ rA{.id == X, .link == full}, rB{X,full} => rA == rB
> > > > > > - zext => lower 32-bits of the register are identical to
> > > > > >           lower 32-bits of a scalar value X,
> > > > > >           upper 32-bits of the register are null.
> > > > > >           ∀ rA{.id == X, .link == ?}, rB{X,zext} => rA % 32 == rB % 32
> > > > > > - sext => lower 32-bits of the register are identical to
> > > > > >           lower 32-bits of a scalar value X,
> > > > > >           upper 32-bits of the register are either 0 or 1,
> > > > > >           depending on the bit 31 value.
> > > > > >           ∀ rA{.id == X, .link == ?}, rB{X,sext} => sext(rA % 32) == sext(rB % 32)
> > > > > 
> > > > > hmm.
> > > > > there is also 32-bit link with delta, right?
> > > > 
> > > > My point is that delta is independent of 32-bit/64-bit property.
> > > > `delta' can be used to propagate in both directions:
> > > > - full 64 bit -> 32 bit sign/zero-extened
> > > > - 32 bit sign/zero-extened -> full 64-bit
> > > 
> > > both? how ?
> > > I was under impression that in 32-bit domain delta is one way.
> > > rX = ...
> > > wY = wX
> > > wY += 5
> > > 
> > > if wY == 10
> > > We cannot do -5 to rX
> > 
> > Why?
> > It is still valid to transfer r32 and tnum_subreg knowledge from wY to rX.
> > 
> >   wY + 5 == rX % 32 + 5 => hence rX % 32 knowledge can be recovered.
> > 
> > If rX itself had some delta, e.g.:
> > 
> >   rX = ...
> >   rX += 7
> >   wY = wX
> >   wY += 5
> > 
> > Then it would still be possible:
> > 
> >   wY + 5 == (rX - 7) % 32 + 5 = rX % 32 - 2.
> > 
> > Again, in case of this direction, only lower 32-bits of the 'full'
> > register can be inferred.
> 
> Ok, so we're argeeing that it's not 'full' in your above definition.
> Your enum id_link_kind needs a 4th category : apply-delta-to-lower-32bit-...
> and it's not bi-directional.

It's not really a category, it's just a direction in a sync function:
- if known_reg is 'full' -> sync to sext/zext register recovers lower
  32-bits and infers upper
- if known_reg is sext/zext -> sync to 'full' register recovers only
  lower 32-bits and keeps upper untouched (counting on cross-domain
  bounds sync logic).
- 'full' -> 'full' and 'sext/zext' -> 'sext/zext' syncs are trivial.

> rX = ...
> wY = wX
> wY += 5
> if wY == 10
> here can apply -5 to lower 32-bit of rX only.
> 
> rX = ...
> wY = wX
> wY += 5
> if rX == 10
> here can apply +5 to lower 32-bit of wY _and_ do zero extend into full rY.
> 
> I don't see a value of 'zext' kind alone that doesn't do 'add delta'.

Exactly, that's why I suggest this as a completely orthogonal encoding.
Effectively for an abstract scalar value X it would encode whether
the particular register is:
- X + delta
- zext(X + delta)
- sext(X + delta)