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

Emanuel Peter epeter at openjdk.org
Fri May 2 15:37:08 UTC 2025 

On Fri, 2 May 2025 11:38:42 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 one additional commit since the last revision:
> 
>   add some more sanity static_asserts

Making another pass from the top. Here mostly comments about `adjust_lo`.
I'm excited, it is now much more readable, and I understand almost everything now :)

src/hotspot/share/opto/compile.cpp line 4505:

> 4503:   if (sizetype != nullptr && sizetype->_hi > 0) {
> 4504:     index_max = sizetype->_hi - 1;
> 4505:   }

Maybe I asked this before: where does the `sizetype->_hi > 0` come from?

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

> 68:     // 0b1000...
> 69:     constexpr U mid_point = (std::numeric_limits<U>::max() >> 1) + U(1);
> 70:     assert((bounds._lo < mid_point) == (bounds._hi < mid_point), "must be a simple interval");

Suggestion:

    assert((bounds._lo < mid_point) == (bounds._hi < mid_point), "must be a simple interval, see Lemma 4");

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

> 242:     - lo[x] satisfies bits for 0 <= x < i (3.1)
> 243:     - zeros[i] = 0                        (3.2)
> 244:     - lo[i] = 0                           (3.3)

Suggestion:

    - lo[i] = 0                           (3.3)
    If there is no such i, then there is also no r that is the smallest
    value not smaller than lo that satisfies bits.

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

> 249:   // 0 in one_violation. Since all higher bits are 0 in zero_violation and
> 250:   // one_violation, we have zero_violation > one_violation. Similarly, if the
> 251:   // first violation violates ones, we have zero_violation < one_violation.

Suggestion:

  // The algorithm depends on whether the first violation violates zeros or
  // ones. If it violates zeros, we have the bit being 1 in zero_violation and
  // 0 in one_violation. Since all higher bits are 0 in zero_violation and
  // one_violation, we have zero_violation > one_violation. Similarly, if the
  // first violation violates ones, we have zero_violation < one_violation.

Might as well make it a new sentence.

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

> 329:     // - lo[x] satisfies bits for 0 <= x < i (3.1)
> 330:     // - zeros[i] = 0                        (3.2)
> 331:     // - lo[i] = 0                           (3.3)

Suggestion:

    // - lo[i] = 0                           (3.3)
    // If there is no such i, then there is also no r that is the smallest
    // value not smaller than lo that satisfies bits.

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

> 334:     // holds. However, first_violation is not the value i we are looking for
> 335:     // because lo[first_violation] == 1. We can also see that any larger value
> 336:     // of i would violate 3.1 since lo[first_violation] does not satisfy bits.

Suggestion:

    // of i would violate (3.1) since lo[first_violation] does not satisfy bits.

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 😊

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;

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;

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

> 376:     // it directly without going through i.
> 377:     //           0 0 1 0 0 0 0 0
> 378:     U alignment = tmp & (-tmp);

Suggestion:

    // We now want to select the last one of these candidates, which is
    // exactly the last index i upto first_violation such that lo[i] == zeros[i] == 0.
    // In our example we have i == 2.
    //           0 0 1 0 0 0 0 0
    U alignment = alignment_candidates & (-alignment_candidates);

Ok, well what is still missing is how the bit trick with `-alignment_candidates` works here.

Let me try:

 alignment_candidates =  0 1 1 0 0 0 0 0
-alignment_candidates =  1 0 1 0 0 0 0 0

Hmm yeah I'm not sure about this one....
I suppose I would have tried this via trailing zeros, but not sure about it...

What is the argument here, why this extracts the last bit?

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 ;)

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;

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

> 399:     // In this case, new_lo may not always be a valid answer. This can happen
> 400:     // if there is no bit upto first_violation that is 0 in both lo and zeros,
> 401:     // i.e. tmp == 0. In such cases, alignment == 0 && lo == bits._ones. It is

Suggestion:

    // i.e. tmp == 0. In such cases, alignment == 0 and new_lo == bits._ones. It is

Or do we somehow also know that `lo = ones`? I think this was a typo, right?

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

> 409:     // result of rounding up being 0.
> 410:     assert(lo < new_lo || new_lo == bits._ones, "overflow must return bits._ones");
> 411:     return new_lo;

Hmm, I would not say that it can return a **non valid** answer. Because we declared that it is ok to return overflowed values at the top of the method, in fact we must prove that in those cases where we cannot find an `r` we at least get `new_lo < lo`.

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

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-2812099778
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071663002
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071672800
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071757681
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071676461
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071759171
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071688886
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071691139
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071706093
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071721498
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071732378
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071755163
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071773264
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071778224
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071789763

More information about the hotspot-compiler-dev mailing list