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

Fri May 2 08:17:08 UTC 2025

On Fri, 2 May 2025 00:50:31 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:
> 
>   Emanuel's reviews

Comments for `type.hpp`

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

> 291: 
> 292:   template <typename TypeClass>
> 293:   const TypeClass* try_cast() const;

This is a way to get to the `isa_...` via templated types, right?

I wonder if it might be better to name it `isa_???`, or even just `isa`, so that it is clearer that it is about the `isa` query.

Currently, it is not very clear what it does, until you look at the implementation. That's a bit unfortunate.

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

> 634:  * of a TypeInt iff:
> 635:  *
> 636:  * v >= _lo && v <= _hi && juint(v) >= _ulo && juint(v) <= _uhi && _bits.is_satisfied_by(v)

Suggestion:

 * A TypeInt represents a set of non-empty jint values. A jint v is an element
 * of a TypeInt iff:
 *   _lo  <=       v  <= _hi  &&
 *   _ulo <= juint(v) <= _uhi &&
 *   _bits.is_satisfied_by(v)

Would be equivalent, but more readable, right?

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

> 643:  *
> 644:  * Then, t1 and t2 both represent the set {3, 5}. We can also see that the
> 645:  * constraints of t2 are tightest possible. I.e there exists no TypeInt t3

Suggestion:

 * constraints of t2 are the tightest possible. I.e there exists no TypeInt t3

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

> 647:  *
> 648:  * t3._lo > t2._lo || t3._hi < t2._hi || t3._ulo > t2._ulo || t3._uhi < t2._uhi ||
> 649:  *     (t3._bits._zeros &~ t2._bis._zeros) != 0 || (t3._bits._ones &~ t2._bits._ones) != 0

Suggestion:

 * which also represents {3, 5} such that any of these would be true:
 *  1)  t3._lo  > t2._lo
 *  2)  t3._hi  < t2._hi
 *  3)  t3._ulo > t2._ulo
 *  4)  t3._uhi < t2._uhi
 *  5)  (t3._bits._zeros &~ t2._bis._zeros) != 0
 *  6)  (t3._bits._ones  &~ t2._bits._ones) != 0

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

> 652:  * t3._bits._zeros and t2._bits._zeros is not empty, which means that the
> 653:  * bits in t3._bits._zeros is not a subset of those in t2._bits._zeros, the
> 654:  * same applies to _bits._ones

Then you can refer to the `condition 5)` and `condition 6)` and the reader can find them quicker, and does not have to worry if you are counting 0 or 1 based ;)

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

> 655:  *
> 656:  * As a result, every TypeInt is canonicalized to its tightest form upon
> 657:  * construction. This makes it easier to reason about them in optimizations.

As a result of what? I think this could be better:
Suggestion:

 * To simplify reasoning about the types in optimizations, we canonicalize every
 * TypeInt to its tightest form, already at construction.

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

> 700:  *
> 701:  *   Proof of lemma 3:
> 702:  *   Lemma 3.1: For 2 jint value x, y such that they are both >= 0 or both < 0.

Suggestion:

 *   Lemma 3.1: Given 2 jint values x, y where either both >= 0 or both < 0.

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

> 706:  *   I.e. x <= y in the signed domain iff x <= y in the unsigned domain
> 707:  *
> 708:  *   Then, we have:

The two `Then` are confusing me a little. The assumption is only the first sentence, not `x <= y iff juint(x) <= juint(y)`, right?

Hmm, ah you have an additional Lemma 3.1 here. But it is a little unclear where that starts and ends. Maybe that can be fixed with some indentation?

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

> 712:  *   a. t._lo >= 0, we have:
> 713:  *
> 714:  *     0 <= t_lo <= jint(t._ulo)           (lemma 2.1)

Suggestion:

 *   a. 0 <= t._lo, we have:
 *
 *     0 <= t._lo <= jint(t._ulo)           (lemma 2.1)

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

> 733:  *   b. t._hi < 0. Similarly, t._lo == jint(t._ulo) and t._hi == jint(t._uhi)
> 734:  *
> 735:  *   c. t._lo < 0, t._hi >= 0.

Suggestion:

 *   c. t._lo < 0, 0 <= t._hi.

I like ordering numbers according to their value :)

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

> 743:  *
> 744:  *     In this case, all elements of t belongs to either [t._lo, jint(t._uhi)] or
> 745:  *     [jint(t._ulo), t._hi].

When you say "all elements belong to x or y", one might misunderstand that they all are in one range and the other is empty.
Suggestion:

 *     In this case, each element of t belongs to either [t._lo, jint(t._uhi)] or
 *     [jint(t._ulo), t._hi].

Here we look at them individually, and so it sounds a little less misleading to me. But that may just be my brain that sees it like this 😅

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

> 770: private:
> 771:   TypeInt(const TypeIntPrototype<jint, juint>& t, int w, bool dual);
> 772:   static const Type* try_make(const TypeIntPrototype<jint, juint>& t, int widen, bool dual);

Just an idea, very optional.
`try_make` does not say what it does when it fails.
Exception? `nullptr`? `TOP`?
You you could rename it to `try_make_else_null` or `make_or_null`. Something like that.

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

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-2811316183
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071192824
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071196300
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071197526
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071201252
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071202049
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071205778
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071210512
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071215527
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071222242
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071229350
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071232432
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r2071242488