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

Mon Jan 27 14:19:12 UTC 2025

On Wed, 22 Jan 2025 15:43:03 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 44 commits:
> 
>  - remove precompiled.hpp
>  - Merge branch 'master' into unsignedbounds
>  - copyright
>  - Merge branch 'master' into unsignedbounds
>  - Merge branch 'master' into unsignedbounds
>  - move try_cast to Type
>  - Merge branch 'master' into unsignedbounds
>  - build failure
>  - build failures
>  - whitespace
>  - ... and 34 more: https://git.openjdk.org/jdk/compare/893d00ac...c4d46c87

@merykitty I've always had this on the list. I'm a little tired today, so won't tough the math heavy stuff, but I have some other suggestions. I'll try to put in a bit of time multiple time a week to get through this eventually.

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

> 40: 
> 41:   static AdjustResult<T> make_empty() {
> 42:     return {true, false, {}};

I'd say you should choose between `empty` and `consistent` and `contradiction`. Three synonyms is a little much 😅

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

> 45: 
> 46: // In the canonical form, [lo, hi] intersects with [ulo, uhi] can result in 2
> 47: // cases:

Fix grammar. Would this be correct?
Suggestion:

// In the canonical form, intersection of [lo, hi] with [ulo, uhi] can result in 2
// cases:

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

> 50: // being [lo, uhi] and [ulo, hi], lo and uhi are < 0 while ulo and hi are >= 0.
> 51: // This class deals with each interval with both bounds being >= 0 or < 0 in
> 52: // the signed domain.

I would indent to the bullet points consistently.

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

> 340: }
> 341: 
> 342: // Try to tighten both the bounds and the bits at the same time

Suggestion:

// Try to tighten both the bounds and the bits at the same time.

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

> 341: 
> 342: // Try to tighten both the bounds and the bits at the same time
> 343: // Iteratively tighten 1 using the other until no progress is made.

Suggestion:

// Iteratively tighten one using the other until no progress is made.

Or are you talking about the number `1`?

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

> 343: // Iteratively tighten 1 using the other until no progress is made.
> 344: // This function converges because at each iteration, some bits that are
> 345: // unknown is made known. As there are at most 64 bits, the number of

Suggestion:

// unknown are made known. As there are at most 64 bits, the number of

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

> 344: // This function converges because at each iteration, some bits that are
> 345: // unknown is made known. As there are at most 64 bits, the number of
> 346: // iterations should not be larger than 64

Suggestion:

// iterations should not be larger than 64.

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

> 347: template <class U>
> 348: static SimpleCanonicalResult<U>
> 349: canonicalize_constraints_simple(const RangeInt<U>& bounds, const KnownBits<U>& bits) {

What does the "simple" mean here? To me, what is happening here is not really "simple" if that is what you were trying to say 😆

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

> 350:   AdjustResult<KnownBits<U>> nbits = adjust_bits_from_bounds(bits, bounds);
> 351:   if (!nbits._is_result_consistent) {
> 352:     return SimpleCanonicalResult<U>::make_empty();

Suggestion:

  if (nbits._is_result_empty) {
    return SimpleCanonicalResult<U>::make_empty();

That would read much more easily ;)

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

> 352:     return SimpleCanonicalResult<U>::make_empty();
> 353:   }
> 354:   AdjustResult<RangeInt<U>> nbounds{true, true, bounds};

`nbounds`: what is the `n` here?

Since you are doing this iteratively, I think `nbits` -> `current_bits`, and `nbounds` -> `current_bounds` would be more explicit.

Alternatively, you rename the inputs to `old_...`, and just call the ones you keep updating `bits` and `bounds`. Up to you.

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

> 359:     nbounds = adjust_bounds_from_bits(nbounds._result, nbits._result);
> 360:     if (!nbounds._progress || !nbounds._is_result_consistent) {
> 361:       return {nbounds._is_result_consistent, nbounds._result, nbits._result};

That sounds a little scary to me:
It sounds like we could have inconsistent results: `!nbounds._is_result_consistent` and then simply return the `nbounds._result`. Is that ok, or just confusing wording?
I think again here `empty` would be our friend: returning an empty result is more sane than returning an inconsistent one 😅

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

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-2575032986
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930286401
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930289367
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930569492
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930576397
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930576938
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930577571
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930577850
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930580768
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930583715
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930586968
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1930593064