RFR: 8370914: C2: Reimplement Type::join [v3]

[Quan Anh Mai]

On Thu, 20 Nov 2025 10:57:11 GMT, Andrew Dinn <adinn at openjdk.org> wrote:

>> It's worth noting that Graal implements `meet` and `join` separately in its `Stamp` type system, with no "dual" tricks, and apparently no worries about being "symmetrical" or even mentioning the words "lattice" or "centerline".  For example:
>> [compiler/src/jdk.graal.compiler/src/jdk/graal/compiler/core/common/type/AbstractObjectStamp.java](https://github.com/oracle/graal/blob/ee2e127f76d2b2fe39e74aa2994d785d0591b567/compiler/src/jdk.graal.compiler/src/jdk/graal/compiler/core/common/type/AbstractObjectStamp.java)
>
>> It's worth noting that Graal implements meet and join separately in its Stamp type system, with no "dual" tricks, and apparently no worries about being "symmetrical" or even mentioning the words "lattice" or "centerline". ...
> 
> It's also worth noting that the theory on which most of the C2 optimization is based stresses heavily the need for the type hierarchy to be a 'well-formed' lattice and relies on that to ensure that the join or meet for any two types is both correct and as strong as possible. The use of dual types to derive the join/meet is not critical and is not computationally optimal but it does enable a uniform computation model which provides the strength guarantee.
> 
> That strength guarantee depends on the lattice obeying certain well-formedness constraints which are not always met in the C2 type system. I recall the issue was that for some pairings there is not always a unique strongest type for the meet (or join?) of two OopPtr types (although there will always be a weaker Ptr type that is the parent of all such strongest valid types). This means that in some cases C2 misses opportunities to perform some optimizations. Years ago Cliff Click wrote a series of articles describing how the lattice worked which explained how this possibility arose but it disappeared from the interwebs quite a while back.

@adinn Oh, I think I kind of understand. For example, the issue I found with the current implementation when joining 2 nullable types. If we try to join `BotPTR: Integer` and `BotPTR: Float`, we will try to meet `TopPTR: Integer` and `TopPTR: Float`. In this case, we have:

- `TopPTR: Integer < Null` and `TopPTR: Float < Null`

or

- `TopPTR: Integer < AnyNull: Integer < NotNull: Integer < NotNull: Number` and `TopPTR: Float < AnyNull: Float < NotNull: Float < NotNull: Number`.
 
As a result, there are 2 LCAs for `TopPTR: Integer` and `TopPTR: Float` which are `Null` and `NotNull: Number`, and they do not subtype each other.

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

PR Comment: https://git.openjdk.org/jdk/pull/28051#issuecomment-3557416742