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

[Emanuel Peter]

On Sat, 20 Jan 2024 19:40:45 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) == 0. 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 normalize 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:
> 
>   fix tests, add verify

@merykitty I just had a quick look. Thanks for spitting out parts and making it more reviewable that way! Since John Rose is generally excited (https://github.com/openjdk/jdk/pull/15440#issuecomment-1901609719), I'll now put in a bit more effort into reviewing this.

Thanks for adding some gtests.
I would really like to see some IR tests, where we can see that this folds cases, and folds them correctly.
And just some general java-code correctness tests, which test your optimizations in an end-to-end way.

I have a general concern with the math functions. They have quite a few arguments, often 5-10. And on average half of them are passed as a reference. Sometimes it is hard to immediately see which are the arguments that will not be mutated, and which are return values, and which are both arguments and return values, which are simply further constrained/narrowed etc.

I wonder if it might be better to have types like:

SRange<int/long> {lo, hi}
URange<int/long> {lo, hi}
KnownBits<int/long> {ones, zeros}

Make them immutable, i.e. the fields are constant.
Then as function parameters, you always pass in these as const, and return the new values (possibly in some combined type, or a pair or tuple or whatever).

I think it would make the code cleaner, have fewer arguments, and a bit easier to reason about when things are immutable.

Plus, then you can put the range-inference methods inside those classes, you can directly ask such an object if it is empty etc. You could for example have somelthing like:
`SRange::constrained_with(KnownBits) -> returns SRange`. Basically I'm asking for the code to be a little more object-oriented, and less C-style ;)

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

> 29: 
> 30: template <class T>
> 31: static bool adjust_bounds_from_bits(bool& empty, T& lo, T& hi, T zeros, T ones) {

Some nice comments at the beginning of functions would help me know what to expect here.

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

> 118: 
> 119: template <class T, class U>
> 120: void normalize_constraints(bool& empty, T& lo, T& hi, U& ulo, U& uhi, U& zeros, U& ones) {

With function signatures like this it is hard to know what are the arguments and what are the return values.

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

> 162:   U zeros2 = zeros;
> 163:   U ones2 = ones;
> 164:   normalize_constraints_simple(empty2, lo2, hi2, zeros2, ones2);

At a quick glance of the code, it is not immediately clear why we need 2 ranges here. Can you add some comments, or maybe improve the naming from 1 and 2 to something more expressive?

src/hotspot/share/opto/type.hpp line 558:

> 556: 
> 557:   // Use to compute join of 2 sets
> 558:   const bool _dual;

I think you need to add some comments, explaining why this is here

src/hotspot/share/opto/type.hpp line 596:

> 594:   const jint _lo, _hi;          // Lower bound, upper bound
> 595:   const juint _ulo, _uhi;
> 596:   const juint _zeros, _ones;

Add comments, say how all of these fields constrain the type.

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-1835981534
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1461575254
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1461582547
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1461584297
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1461559253
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1461559662