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

[Jatin Bhateja]

On Thu, 19 Sep 2024 17:12:22 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:
> 
>   formality

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

> 210:     // first_violation is the position of the violation counting from the
> 211:     // lowest bit up (0-based), since i == 2, first_difference == 6
> 212:     juint first_violation = W - 1 - count_leading_zeros(one_violation); // 6

FTR, A zero violation can never cause a value to be smaller than smallest possible value represented by Known bits, while one violation can.

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

> 68: template <class U>
> 69: class KnownBits {
> 70:   static_assert(std::is_unsigned<U>::value, "bit info should be unsigned");

Since you are forcing bit info should correspond to unsigned type, it will be good to add KnownBits.minValue() and KnownBits.maxValue() routines where,

MinValue = KnownBits.ONES (assuming all the unknown bits are 0s)
MaxValue = ~KnownBits.ZERO (assuming all unknown bits are 1s)

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

> 153:     return t1->_lo == t2->_lo && t1->_hi == t2->_hi && t1->_ulo == t2->_ulo && t1->_uhi == t2->_uhi &&
> 154:           t1->_bits._zeros == t2->_bits._zeros && t1->_bits._ones == t2->_bits._ones;
> 155:   }

For clarity, Expression can be broken into separate signed, unsigned and known bit comparison followed by logical anding.

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

> 157:   template <class CT>
> 158:   static bool int_type_subset(const CT* super, const CT* sub) {
> 159:     return super->_lo <= sub->_lo && super->_hi >= sub->_hi && super->_ulo <= sub->_ulo && super->_uhi >= sub->_uhi &&

Same as above.

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

> 617:  * it by one, which contradicts the assumption of the TypeInt being canonical.
> 618:  *
> 619:  * 2. Either _lo == jint(_lo) and _hi == jint(_uhi), or all elements of a

Suggestion:

 * 2. Either _lo == jint(_ulo) and _hi == jint(_uhi), or all elements of a

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

PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1768434099
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1768471879
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1768271214
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1768271934
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1768496674