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

[Quan Anh Mai]

On Fri, 21 Nov 2025 08:29:27 GMT, Manuel Hässig <mhaessig at openjdk.org> wrote:

>> Quan Anh Mai has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains five commits:
>> 
>>  - Merge branch 'master' into typejoin
>>  - Move dual to ASSERT only
>>  - Keep old version for verification
>>  - whitespace
>>  - Reimplement Type::join
>
> I have done a bit of digging as to why we have the symmetry requirement and found [Cliff talking about it in the Coffee Compiler Club](https://youtu.be/pBx6hoNV_eQ?t=240). He uses the symmetry to guarantee work-order independence (he also calls this the [Church-Rosser property](https://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem) of the lattice in some places) and that provably guarantees that the optimistic analysis in the form of CCP will fixpoint at a better result than the pessimistic analysis of IGVN. He mentions playing around with non-symmetric lattices for C2 but running into issues with CCP giving different results based on the order of the work list. So I guess the main question I have is how we would ensure that any lattice ensures work order independence if it is not by construction.

@mhaessig

Firstly, the type system is already not well-formed, as pointed out above, so it is unsound to think that the properties you mentioned are withheld. Furthermore, the construction of the lattice is not enough to enforce those properties, you need each and every operation on the lattice to conform to certain properties, too. For example, without monotonicity, we can easily come up with cases where CCP gives worse results compared to GVN.

> the optimistic analysis in the form of CCP will fixpoint at a better result than the pessimistic analysis of IGVN

This is guaranteed by monotonicity, since the type of each node at the beginning of CCP is a subset of the corresponding type during GVN. This property will be withheld throughout each iteration of CCP.

> CCP giving different results based on the order of the work list

Tbh I don't see this being an issue at all.

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

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