RFR: 8333393: PhaseCFG::insert_anti_dependences can fail to raise LCAs and to add necessary anti-dependence edges [v5]

[Emanuel Peter]

On Fri, 28 Feb 2025 09:00:40 GMT, Daniel Lundén <dlunden at openjdk.org> wrote:

>> When searching for load anti-dependences in GCM, the memory state for the load is sometimes represented not only by the memory node input of the load, but also other memory nodes. Because PhaseCFG::insert_anti_dependences searches for anti-dependences only from the load's memory input, it is, therefore, possible to sometimes overlook anti-dependences. The result is that loads are potentially scheduled too late, after stores that redefine the memory states of the loads.
>> 
>> ### Changeset
>> 
>> It is not yet clear why multiple nodes sometimes represent the memory state of a load, nor if this is expected. We can, however, resolve all the miscompiled test cases seen in this issue by improving the idealization of Phi nodes. Specifically, there is an idealization where we split Phis through input MergeMems, that we, prior to this changeset, applied too conservatively.
>> 
>> To illustrate the idealization and how it resolves this issue, consider the example below.
>> 
>> ![failure-graph-1](https://github.com/user-attachments/assets/ecbd204f-bdf0-49cb-a62e-8081d08cfe0c)
>> 
>> `64 membar_release` is a critical anti-dependence for `183 loadI`. The anti-dependence search starts at the load's direct memory input, `107 Phi`, and stops immediately at Phis. Therefore, the search ends at `106 Phi` and we never find `64 membar_release`.
>> 
>> We can apply the split-through-MergeMem Phi idealization to `119 Phi`. This idealization pushes `119 Phi` through `120 MergeMem` and `121 MergeMem`, splitting it into the individual inputs of the MergeMems in the process. As a result, we replace `119 Phi` with two new Phis. One of these generated Phis has identical inputs to `107 Phi` (`106 Phi` and `104 Phi`), and further idealizations will merge this new Phi and `107 Phi`. As a result, `107 Phi` then has a Phi-free path to `64 membar_release` and we correctly discover the anti-dependence.
>> 
>> The changeset consists of the following changes.
>> - Add an analysis that allows applying the split-through-MergeMem idealization in more cases than before (including in the above example) while still ensuring termination.
>> - Add a missing `ResourceMark` in `PhiNode::split_out_instance`.
>> - Add multiple new regression tests in `TestGCMLoadPlacement.java`.
>> 
>> For reference, [here](https://github.com/openjdk/jdk/pull/22852) is a previous PR with an alternative fix that we decided to discard in favor of the fix in this PR.
>> 
>> ### Testing
>> 
>> - [GitHub Actions](https://github.com/dlunde/jdk/ac...
>
> Daniel Lundén has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Update after Christian's review

@dlunde This looks reasonable :)

I have a question about compile time below.

Also: do you still intend to add some kind of verification code to catch these kinds of missing anti-dependnece edges? That should probably be a separate RFE if we do it at all.

src/hotspot/share/opto/cfgnode.cpp line 2061:

> 2059: // non-termination. For more details, see comments at the call site in
> 2060: // PhiNode::Ideal. This is really a const method, but Node_List currently only
> 2061: // permits non-const elements.

Which `Node_List` is this about? Would `GrowabelArray` be a good alternative?

src/hotspot/share/opto/cfgnode.cpp line 2062:

> 2060: // PhiNode::Ideal. This is really a const method, but Node_List currently only
> 2061: // permits non-const elements.
> 2062: bool PhiNode::is_split_through_mergemem_terminating() {

This method could walk a significant part of the graph, right? And since this happens during IGVN, this could happen repeatedly, correct?

Often we have limits on traversals, but maybe we don't want that here.

I'm just wondering if this could have an impact on compile time. But then again: I don't know if there is even an alternative 🙈

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

Marked as reviewed by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/23691#pullrequestreview-2653878700
PR Review Comment: https://git.openjdk.org/jdk/pull/23691#discussion_r1977365361
PR Review Comment: https://git.openjdk.org/jdk/pull/23691#discussion_r1977402218