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

[Jasmine Karthikeyan]

On Sun, 8 Sep 2024 05:07:59 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 23 commits:
> 
>  - change (~v & ones) == 0 to (v & ones) == ones
>  - Merge branch 'master' into unsignedbounds
>  - fix builds
>  - add trivial test cases
>  - make should return the correct type
>  - rename tests
>  - more explanation
>  - fix build
>  - fix build
>  - add more comments, group KnownBits
>  - ... and 13 more: https://git.openjdk.org/jdk/compare/5b72bbf9...9b70213e

This is looking really nice, I'm very excited to see this work continue! The added comments definitely help in understanding the theory and implementation. I think the approach of splitting the domain as `[lo, uhi] U [ulo, hi]` is quite clever, as it nicely avoids needing to consider how the bits interact across signs. I've added some comments below.

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

> 290:   // Trivially canonicalize the bounds so that srange._lo and urange._hi are
> 291:   // both < 0 or >= 0. The same for srange._hi and urange._ulo
> 292:   if (S(urange._lo) > S(urange._hi)) {

I think it would be worth mentioning in the comments that the case where `ulo` can be greater than `uhi` in the signed domain happens when the range crosses zero, to make it easier for people to understand the purpose of the logic from reading the comments.

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

> 447: // convergence by abandoning the bounds
> 448: template <class CT>
> 449: const Type* int_type_widen(const CT* nt, const CT* ot, const CT* lt) {

I think here and in `int_type_narrow` it would be good to write the parameters as `new_type`, `old_type`, and `limit_type` for clarity.

src/hotspot/share/opto/rangeinference.hpp line 112:

> 110:   }
> 111: 
> 112:   return urange._hi - U(srange._lo) + U(srange._hi) - urange._lo + 1;

Suggestion:

  return (urange._hi - U(srange._lo)) + (U(srange._hi) - urange._lo) + 1;

The functionality is the same but this makes it more clear that the logic is `(uhi - lo) + (hi - ulo)`.

src/hotspot/share/opto/rangeinference.hpp line 146:

> 144: 
> 145: void int_type_dump(const TypeInt* t, outputStream* st, bool verbose);
> 146: void int_type_dump(const TypeLong* t, outputStream* st, bool verbose);

Maybe this could be called `long_type_dump`? Since it's not a template function and is specific to TypeLong.

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

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-2287119764
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1749325904
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1749376527
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1751096189
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1749378575