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

[Emanuel Peter]

On Thu, 1 May 2025 07:59:15 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 three additional commits since the last revision:
> 
>  - new_hi computation
>  - refer back to the formality section
>  - clarify where overflow comes from

Another batch before lunch :)

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

> 624: bool TypeIntPrototype<S, U>::contains(S v) const {
> 625:   U u(v);
> 626:   return v >= _srange._lo && v <= _srange._hi && u >= _urange._lo && u <= _urange._hi && _bits.is_satisfied_by(u);

Suggestion:

  return _srange._lo <= v && v <= _srange._hi &&
         _urange._lo <= u && u <= _urange._hi &&
         _bits.is_satisfied_by(u);

Optional: improve readability.

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

> 668:   if (i1 == t2 || t2 == Type::TOP) {
> 669:     return i1;
> 670:   }

Not sure if I got this right, I'm not fully understanding what the `dual` flag does here yet.
Is this correct?
`meet = intersection` - `dual = false`
`join = union` - `dual = true`

So if `i1 == t2`, then we can return `i1` in both cases, as it is both the intersection and union.
But if `t2 == Type::TOP`, and `i1` is not TOP, then `i1` is not the intersection.

What am I missing?

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

> 676:                                          {MIN2(i1->_ulo, i2->_ulo), MAX2(i1->_uhi, i2->_uhi)},
> 677:                                          {i1->_bits._zeros & i2->_bits._zeros, i1->_bits._ones & i2->_bits._ones}},
> 678:                   MAX2(i1->_widen, i2->_widen), false);

Ok, this looks like a union. And below like a intersection.

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

> 936: 
> 937: template <class U>
> 938: const char* TypeIntHelper::bitname(char* buf, size_t buf_size, U zeros, U ones) {

Wow, these will look incredibly long for 64bit long values, no?
Well, if it ever gets too much in the way, we can still try to find more compressed representations later.
Maybe things like: `*..*000` for 8-aligned values.
Others: `0..0***`, `00*..*`, `1..1***` etc.
`0..0*..*` would be a little unfortunate as we would lose the position where the bits flip.

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

> 1014:   } else {
> 1015:     if (verbose) {
> 1016:       st->print("long:%s..%s ^ %s..%s, bits:%s",

Suggestion:

      st->print("long:%s..%s, %s..%s, bits:%s",

That's what you have for the ints above.

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

> 1032:         }
> 1033:       } else {
> 1034:         st->print("long:%s..%s ^ %s..%s",

Suggestion:

        st->print("long:%s..%s, %s..%s",

That's what you have for the ints above.

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

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-2809373002
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2069998856
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2070007333
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2070017853
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2070094305
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2070103170
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2070103489