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

[Emanuel Peter]

On Thu, 1 May 2025 07:00:46 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

>> Hi,
>> 
>> This patch adds unsigned bounds and known bits constraints to TypeInt and TypeLong. This opens more transformation opportunities in an elegant manner as well as helps avoid some ad-hoc rules in Hotspot.
>> 
>> In general, a `TypeInt/Long` represents a set of values `x` that satisfies: `x s>= lo && x s<= hi && x u>= ulo && x u<= uhi && (x & zeros) == 0 && (x & ones) == ones`. These constraints are not independent, e.g. an int that lies in [0, 3] in signed domain must also lie in [0, 3] in unsigned domain and have all bits but the last 2 being unset. As a result, we must canonicalize the constraints (tighten the constraints so that they are optimal) before constructing a `TypeInt/Long` instance.
>> 
>> This is extracted from #15440 , node value transformations are left for later PRs. I have also added unit tests to verify the soundness of constraint normalization.
>> 
>> Please kindly review, thanks a lot.
>> 
>> Testing
>> 
>> - [x] GHA
>> - [x] Linux x64, tier 1-4
>
> Quan Anh Mai has updated the pull request incrementally with two additional commits since the last revision:
> 
>  - wording
>  - grammar, more details for non-existence

src/hotspot/share/opto/rangeinference.cpp line 263:

> 261:     // is a 0 that should be a 1. Obviously, since the bit at that position in
> 262:     // ones is 1, the same bit in zeros is 0. Which means this is the value of
> 263:     // i we are looking for.

Suggestion:

    // This means that the first bit that does not satisfy the bit requirement
    // is a 0 that should be a 1. Obviously, since the bit at that position in
    // ones is 1, the same bit in zeros is 0. Which means this is the value of
    // we are looking for.
    // We know i is the largest bit index such that:
    // - lo[x] satisfies bits for 0 <= x < i (2.2)
    // - zeros[i] = 0                        (2.3)
    // - lo[i]    = 0                        (2.4)
    // For the given i, we know that lo satisfies all bits before i, hence (2.2)
    // holds. Further, lo[i] = 0 (2.3), and we have a one violation at i, hence
    // zero[i] = 0 (2.4). Any smaller i would not be the largest possible such
    // index. Any larger i would violate (2.2), since lo[i] does not satisfy bits.

I just realized that we should explicitly tie this back in to the proof we wrote above, and link it to the numbers there.

src/hotspot/share/opto/rangeinference.cpp line 285:

> 283:     // all bits after to zero. This is similar to an operation that aligns lo
> 284:     // up to this modulo
> 285:     //           0 0 0 1 0 0 0 0

Suggestion:

    // This is the bit at which we want to change the bit 0 in lo to a 1, and
    // all bits after to zero. This is similar to an operation that aligns lo
    // up to this modulo
    //           0 0 0 1 0 0 0 0
    // This is in preparation for (2.6) in the construction: v[i] = 1.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2069929837
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2069931509