Integrated: 8333393: PhaseCFG::insert_anti_dependences can fail to raise LCAs and to add necessary anti-dependence edges

[Daniel Lundén]

On Wed, 19 Feb 2025 09:52:41 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/actions/runs/13394882532)
> - `tier1` to `tier4` (an...

This pull request has now been integrated.

Changeset: b40be225
Author:    Daniel Lundén <dlunden at openjdk.org>
URL:       https://git.openjdk.org/jdk/commit/b40be22512a8d3b3350fef8d6668d80134a6f1a6
Stats:     366 lines in 3 files changed: 356 ins; 1 del; 9 mod

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

Co-authored-by: Roberto Castañeda Lozano <rcastanedalo at openjdk.org>
Co-authored-by: Christian Hagedorn <chagedorn at openjdk.org>
Co-authored-by: Tobias Hartmann <thartmann at openjdk.org>
Co-authored-by: Emanuel Peter <epeter at openjdk.org>
Co-authored-by: Quan Anh Mai <qamai at openjdk.org>
Reviewed-by: rcastanedalo, chagedorn, epeter

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

PR: https://git.openjdk.org/jdk/pull/23691