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

[Emanuel Peter]

On Mon, 21 Apr 2025 12:05:27 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 with a new target base due to a merge or a rebase. The pull request now contains 61 commits:
> 
>  - Merge branch 'master' into unsignedbounds
>  - Merge branch 'master' into unsignedbounds
>  - reviews
>  - Merge branch 'master' into unsignedbounds
>  - refine comments
>  - Merge branch 'master' into unsignedbounds
>  - Merge branch 'master' into unsignedbounds
>  - harden SimpleCanonicalResult
>  - number lemmas
>  - include
>  - ... and 51 more: https://git.openjdk.org/jdk/compare/0995b940...cdab1911

A few comments for the `if (zero_violation < one_violation) {` section.

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

> 255:     //   0-vio = 0 0 0 0 0 0 0 0
> 256:     // Since the result must have the 2nd bit set, it must be at least:
> 257:     //           1 1 0 0 0 0 0 0

It might be better to have the violation a little more close to the middle. Right now it is only a single bit off from the `highest_bit`.

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

> 261: 
> 262:     // first_violation is the position of the violation counting from the
> 263:     // highest bit down (0-based), since i == 2, first_difference == 1

Suggestion:

    // highest bit down (0-based). For example: i == 2, first_violation == 1.

If that is not what you wanted, then I'm not sure what `first_difference` refers to ;)

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

> 262:     // first_violation is the position of the violation counting from the
> 263:     // highest bit down (0-based), since i == 2, first_difference == 1
> 264:     juint first_violation = count_leading_zeros(one_violation); // 1

Suggestion:

    juint first_violation = count_leading_zeros(one_violation);

What was the comment for?

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

> 266:     constexpr U highest_bit = (std::numeric_limits<U>::max() >> 1) + U(1);
> 267:     //           0 1 0 0 0 0 0 0
> 268:     U alignment = highest_bit >> first_violation;

Could it also be called `violated_bit_mask`? Not sure if that is more helpful... why did you name it `alignment`?

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

> 270:     // that the result should not be smaller than this
> 271:     //           1 1 0 0 0 0 0 0
> 272:     U new_lo = (lo & -alignment) + alignment;

Ouff, this is one of these one-liners that need some explanation... I'll try to decode it.

Hmm, it is also not really the `new_lo` which we return, there is another operation below. Maybe we can give this intermediate result a descriptive name?

It seems that already `-alignment` does something interesting... but I'll leave it to you to explain. I'm less familiar with all the bit tricks, and continually amazed what is possible :)

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-2784525953
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2054382718
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2054370630
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2054365480
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2054387217
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2054396626