RFR: 8370914: C2: Reimplement Type::join

[Quan Anh Mai]

On Fri, 31 Oct 2025 03:09:22 GMT, Dean Long <dlong at openjdk.org> wrote:

>> Hi,
>> 
>> Currently, `Type::join` is implemented using `Type::dual`. The idea seems to be that the dual of a join would be the meet of the duals of the operands. This helps us avoid the need to implement a separate join operation. The comments also discuss the symmetry of the join and the meet operations, which seems to refer to the various fundamental laws of set union and intersection.
>> 
>> However, it requires us to find a representation of a `Type` class that is symmetric, which may not always be possible without outright dividing its value set into the normal set and the dual set, and effectively implementing join and meet separately (e.g. `TypeInt` and `TypeLong`).
>> 
>> In other cases, the existence of dual types introduces additional values into the value set of a `Type` class. For example, a pointer can be a nullable pointer (`BotPTR`), a not-null pointer (`NotNull`), a not-null constant (`Constant`), a null constant (`Null`), an impossible value (`TopPTR`), and `AnyNull`? This is really hard to conceptualize even when we know that `AnyNull` is the dual of `NotNull`. It also does not really work, which leads to us sprinkling `above_centerline` checks all over the place. Additionally, the number of combinations in a meet increases quadratically with respect to the number of instances of a `Type`. This makes the already hard problem of meeting 2 complicated sets a nightmare to understand.
>> 
>> This PR reimplements `Type::join` as a separate operation and removes most of the `dual` concept from the `Type` class hierachy. There are a lot of benefits of this:
>> 
>> - It makes the operation much more intuitive, and changes to `Type` classes can be made easier. Instead of thinking about type lattices and how the representation places the `Type` objects on the lattices, it is much easier to conceptualize a join when we think a `Type` as a set of possible values.
>> - It tightens the invariants of the classes in the hierachy. Instead of having 5 possible `ptr()` value when a `TypeInstPtr` participating in a meet/join operation, there are only 3 left (`AnyNull` is non-sensical and `TopPTR` must be an `AnyPtr`). This, in turns, reduces the number of combinations in a meet/join from 25 to 9, making it much easier to reason about.
>> 
>> This PR also tries to limit the interaction between unrelated types. For example, meeting and joining of a float and an int seem to happen only when we try to do those operations on the array types of those types. Limiting these p...
>
> I like this idea, but even if it is 100% correct, how do we prove that?  Can we exhaustively test all possibilities?  We might consider introducing the new join as a parallel implementation, so it can compare the result with the old join as a sanity check.  Then after we are convinced of its correctness, we remove the old join.  As for unit testing, all we have is check_symmetrical(), right?  With a change this fundamental, I think we will need correspondingly better tests.

@dean-long Thanks for your great suggestion. I have tried implemented the idea to compare the results of the old and the new approach each time we call `meet` or `join` between 2 types. The implementation can be found on [this branch](https://github.com/merykitty/jdk/tree/typejoindraft). Unfortunately, it exposes incorrect results in the current approach. For example:

    === Join May Be Incorrect ===
    t1                                    = jdk/internal/jrtfs/JrtFileSystemProvider:exact *
    t2                                    = sun/nio/fs/LinuxFileSystemProvider *
    t1 joins t2                           = null
    (t1->dual() meets t2->dual())->dual() = java/nio/file/spi/FileSystemProvider:AnyNull *,iid=top

Apparently, both `t1` and `t2` are nullable, the result of the join cannot be empty, which an `AnyNull` represents.

If I add this to master:

    diff --git a/src/hotspot/share/opto/type.cpp b/src/hotspot/share/opto/type.cpp
    index f62eea893cd..da3e929634b 100644
    --- a/src/hotspot/share/opto/type.cpp
    +++ b/src/hotspot/share/opto/type.cpp
    @@ -983,6 +983,15 @@ void Type::check_symmetrical(const Type* t, const Type* mt, const VerifyMeet& ve
       // Interface:AnyNull meet Oop:AnyNull == Interface:AnyNull
       // Interface:NotNull meet Oop:NotNull == java/lang/Object:NotNull

    +  const Type* join = verify.meet(dual(), t->dual())->dual();
    +  if (isa_instptr() && t->isa_instptr() && maybe_null() && t->maybe_null() && join->empty()) {
    +    tty->print("Cannot be empty:\n");
    +    tty->print("t1         : "); dump(); tty->cr();
    +    tty->print("t2         : "); t->dump(); tty->cr();
    +    tty->print("t1 joins t2: "); join->dump(); tty->cr();
    +    assert(false, "incorrect join");
    +  }
    +
       if (t2t != t->_dual || t2this != this->_dual) {
         tty->print_cr("=== Meet Not Symmetric ===");
         tty->print("t   =                   ");              t->dump(); tty->cr();

Similar failures can be observed when I run `make test-tier1`:

    Cannot be empty:
    t1         : com/sun/tools/javac/code/Symbol$PackageSymbol (com/sun/tools/javac/jvm/PoolConstant,javax/lang/model/AnnotatedConstruct,javax/lang/model/element/Element,javax/lang/model/element/QualifiedNameable,javax/lang/model/element/PackageElement) *
    t2         : com/sun/tools/javac/code/Symbol$ModuleSymbol (com/sun/tools/javac/jvm/PoolConstant,javax/lang/model/AnnotatedConstruct,javax/lang/model/element/Element,javax/lang/model/element/QualifiedNameable,javax/lang/model/element/ModuleElement) *
    t1 joins t2: com/sun/tools/javac/code/Symbol$TypeSymbol (com/sun/tools/javac/jvm/PoolConstant,javax/lang/model/AnnotatedConstruct,javax/lang/model/element/Element,javax/lang/model/element/QualifiedNameable):AnyNull *,iid=top

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

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