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

[Emanuel Peter]

On Thu, 12 Sep 2024 16:47: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 incrementally with one additional commit since the last revision:
> 
>   refine comments

I see there are lots more comments. I'm out of time today, so I'll just drop a few comments.

Looking forward to reading the bulk of the code soon!

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

> 42:     return {true, false, {}};
> 43:   }
> 44: };

And here we have another `optional`, right?
This could be some kind of `Status<Optional<T>>`. Where `Status` has a `progress` and `payload` (the optional). And the `Optional` has a `present` and `payload` (the `T`).

Boah not sure if this level of abstration I'm thinking about here is worth it.

But it would be nice if your comments were consistently above the field or on the same line.
And a quick comment above the class would be appreciated too ;)

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

> 62:     return {false, {}, {}};
> 63:   }
> 64: };

Yet another `Optional`?

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

> 44:  * Bits that are known to be 0 or 1. A value v satisfies this constraint iff
> 45:  * (v & zeros) == 0 && (v & ones) == ones. I.e, all bits that is set in zeros
> 46:  * must be unset in v, and all bits that is set in ones must be set in v.

Suggestion:

 * (v & zeros) == 0 && (v & ones) == ones. I.e, any bit that is set in zeros
 * must be unset in v, and any bit that is set in ones must be set in v.

I think that is more correct "math speak".

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

> 45:  * (v & zeros) == 0 && (v & ones) == ones. I.e, all bits that is set in zeros
> 46:  * must be unset in v, and all bits that is set in ones must be set in v.
> 47:  *

You could also make a table like this:


zeros    ones    allowed bits
0        0       0 or 1
1        0       0
0        1       1
1        1       none (impossible state)

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

> 73: 
> 74: template <class S, class U>
> 75: class CanonicalizedTypeIntPrototype {

Ah, is this basically an **Optional**, like `std::optional`? Maybe add a comment above the class for that!

Honestly, you could also just define a `Optional<T>` class. Maybe even in a separate `optional.hpp` file. I'm sure we can use this construct again.

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

> 84: 
> 85: template <class S, class U>
> 86: class TypeIntPrototype {

Hmm ok, and what does `Prototype` mean here? Not really "optional". Probably this is the whole type-information needed for an `IntType` or `LongType`? A comment for the class would be appreciated :)

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

> 103: 
> 104: // The result is tuned down by one since we do not have empty type
> 105: // and this is not required to be accurate

I don't understand this comment. Why does it not need to be accurate? Maybe you should rather focus on what this method is intuitively supposed to do, and then define what it guarantees for its return?

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

> 105: // and this is not required to be accurate
> 106: template <class S, class U>
> 107: U cardinality_from_bounds(const RangeInt<S>& srange, const RangeInt<U>& urange) {

Do you want to add some `static_assert` for the `S / U` types here?

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

All these names are exposed globally. Are we sure we want to do that? Or should we maybe put them in a class as static methods?

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-2312603872
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765526324
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765527916
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765009043
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765005303
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765176515
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765184929
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765190821
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765188144
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1765193860