RFR: 8315066: Add unsigned bounds and known bits to TypeInt/Long [v59]

[Emanuel Peter]

On Fri, 2 May 2025 14:23:07 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> Quan Anh Mai has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   add some more sanity static_asserts
>
> src/hotspot/share/opto/rangeinference.cpp line 338:
> 
>> 336:     // of i would violate 3.1 since lo[first_violation] does not satisfy bits.
>> 337:     // As a result, we should find the last i upto first_violation such that
>> 338:     // lo[i] == zeros[i] == 0.
> 
> Excellent, this really sets up the bit tricks below! Nice 😊

Let's try to match the wording below to this, so it is clear that we are working towards this.

> src/hotspot/share/opto/rangeinference.cpp line 370:
> 
>> 368:     // bits. We will expand the implication of such cases below.
>> 369:     //           0 1 1 0 0 0 0 0
>> 370:     U tmp = ~either & find_mask;
> 
> Suggestion:
> 
>     // In tmp exactly those bits are set that are upto first_violation and where
>     // lo[i] == zeros[i] == 0. Hence: The last one of these bits is at bit index i.
>     // Note that there may not exist such bits, i.e. tmp == 0. Hence we cannot
>     // find any i that satisfies (3.1-3.3), and so there is no value not less than
>     // lo that satisfies bits. We will expand the implication of such cases below.
>     //           0 1 1 0 0 0 0 0
>     U tmp = ~either & find_mask;

That is the smaller suggestion, I have a larger one below.

> src/hotspot/share/opto/rangeinference.cpp line 370:
> 
>> 368:     // bits. We will expand the implication of such cases below.
>> 369:     //           0 1 1 0 0 0 0 0
>> 370:     U tmp = ~either & find_mask;
> 
> Suggestion:
> 
>     // We want to find the last i upto first_violation such that lo[i] == zeros[i] == 0.
>     // We start with all bits where lo[i] == zeros[i] == 0:
>     //           0 1 1 0 0 0 0 1
>     U lo_eq_zeros_eq_zero = ~(lo | bits._zeros).
>     // Now let us find all the bit indices x upto first_violation such that
>     // lo[x] == zeros[x] == 0. The last one of these bits must be at index i.
>     //           0 1 1 0 0 0 0 0
>     // Note that there may not exist such bits, i.e. tmp == 0. Hence we cannot
>     // find any i that satisfies (3.1-3.3), and so there is no value not less than
>     // lo that satisfies bits. We will expand the implication of such cases below.
>     U alignment_candidates = lo_eq_zeros_eq_zero & find_mask;

The benefit here: we have more explicit names. And the wording matches a little closer to our goal above.

> src/hotspot/share/opto/rangeinference.cpp line 387:
> 
>> 385:     // - new_lo[i] = 1                     (2.6)
>> 386:     // - new_lo[x] = 0, for x > i          (not yet 2.7)
>> 387:     //           1 0 1 0 0 0 0 0
> 
> That's a little misleading if there is no such `i`...
> In that case `alignment = 0`, and `-alignment = 0`, and so `new_lo = 0`... which is not exactly an overflow, but smaller than `lo`, so kinda an overflow ;)

Suggestion:

    // similar to aligning lo upto alignment. Also similar to the above case,
    // this computation cannot overflow.
    // We now have:
    // - new_lo[x] = lo[x], for 0 <= x < i (2.5)
    // - new_lo[i] = 1                     (2.6)
    // - new_lo[x] = 0, for x > i          (not yet 2.7)
    // If there is no such candidate, and no such i, then new_lo = 0.
    //           1 0 1 0 0 0 0 0

> src/hotspot/share/opto/rangeinference.cpp line 398:
> 
>> 396:     // This is the result we are looking for.
>> 397:     //           1 0 1 0 0 0 1 1
>> 398:     new_lo |= bits._ones;
> 
> Now we should probably also split the cases with and without candidates.
> Suggestion:
> 
>     // Assume there was at least one candidate, and i is the index of the last one:
>     // Then there exists no value x not larger than i such that
>     // new_lo[x] == 0 and ones[x] == 1. This is because all bits of lo before i
>     // should satisfy bits, and new_lo[i] == 1. As a result, doing
>     // new_lo |= bits.ones will give us a value such that:
>     // - new_lo[x] = lo[x], for 0 <= x < i (2.5)
>     // - new_lo[i] = 1                     (2.6)
>     // - new_lo[x] = ones[x], for x > i    (2.7)
>     // This is the result r we are looking for.
>     //           1 0 1 0 0 0 1 1
>     // If there was no candidate, then above we had new_lo = 0, and the
>     // computation below gives us new_lo = ones.
>     new_lo |= bits._ones;

The "no candidate" case should now have an argument why this is an ok value to return.
It does satisfy bits, since `ones` satisfy bits.
But do we know that `ones < lo`? We need that to get the "overflow" we promised at the very top of the method.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071695189
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071706651
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071722541
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071763058
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071788373