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

[Quan Anh Mai]

On Fri, 24 Jan 2025 14:32:39 GMT, Daniel Lundén <dlunden at openjdk.org> wrote:

>> When searching for load anti dependences in GCM, it is not always sufficient to just search starting at the direct initial memory input to the load. Specifically, there are cases when we must also search for anti dependences starting at relevant Phi memory nodes in between the load's early block and the initial memory input's block. Here, "in between" refers to blocks in the dominator tree in between the early and initial memory blocks.
>> 
>> #### Example 1
>> 
>> Consider the ideal graph below. The initial memory for 183 loadI is 107 Phi and there is an important anti dependency for node 64 membar_release. To discover this anti dependency, we must rather search from 119 Phi which contains overlapping memory slices with 107 Phi. Looking at the ideal graph block view, we see that both 107 Phi and 119 Phi are in the initial memory block (B7) and thus dominate the early block (B20). If we only search from 107 Phi, we fail to add the anti dependency to 64 membar_release and do not force the load to schedule before 64 membar_release as we should. In the block view, we see that the load is actually scheduled in B24 _after_ a number of anti-dependent stores, the first of which is in block B20 (corresponding to the anti dependency on 64 membar_release). The result is the failure we see in this issue (we load the wrong value).
>> 
>> ![failure-graph-1](https://github.com/user-attachments/assets/e5458646-7a5c-40e1-b1d8-e3f101e29b73)
>> ![failure-blocks-1](https://github.com/user-attachments/assets/a0b1f724-0809-4b2f-9feb-93e9c59a5d6a)
>> 
>> #### Example 2
>> 
>> There are also situations when we need to start searching from Phis that are strictly in between the initial memory block and early block. Consider the ideal graph below. The initial memory for 100 loadI is 18 MachProj, but we also need to search from 76 Phi to find that we must raise the LCA to the last block on the path between 76 Phi and 75 Phi: B9 (= the load's early block). If we do not search from 76 Phi, the load is again likely scheduled too late (in B11 in the example) after anti-dependent stores (the first of which corresponds to 58 membar_release in B10). Note that the block B6 for 76 Phi is strictly dominated by the initial memory block B2 and also strictly dominates the early block B9.
>> 
>> ![failure-graph-2](https://github.com/user-attachments/assets/ede0c299-6251-4ff8-8b84-af40a1ee9e8c)
>> ![failure-blocks-2](https://github.com/user-attachments/assets/e5a87e43-b6fe-4fa3-8961-54752f63633e)
>> 
>> ### Cha...
>
> Daniel Lundén has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Clarifications after comments from Roberto

Tbh I find it really hard to understand your comments

    // There are rare situations where multiple memory nodes are valid inputs to
    // the load. That is, we could replace the actual memory input to the load
    // (initial_mem) with any of these nodes and still have a semantically
    // equivalent graph.

What does this even mean? What equivalency relation we are talking about here? It is surely not equivalent in the graph sense since moving an edge by definition gives you a different graph. I suppose you want to talk about equivalency from the scheduling perspective. But then it is unclear what the relation between the graph topology and the constraints put on us regarding scheduling is. I believe the bug is due to us not fully comprehending this relation, so starting the explanation as if this relation is clear seems not a good idea.

    // In the following, we refer to equivalent memory nodes as additional
    // (search) roots. If we do not search for anti-dependences from all roots,
    // it is possible that we do not discover all relevant anti-dependences.

I don't understand this part, I would assume if the memory roots here are equivalent, then if you start searching from any one of those, you would obtain the same result, which seems not the case here.

    // Facts:
    // - If L is live, any simultaneously live memory node that can alias L is a
    //   potential root.
    // - Roots only reside in blocks dominating the early block.
    // - L is by definition live just after initial_mem.
    // - If the initial_mem block strictly dominates the early block, L is
    //   necessarily live all the way to the start of the early block.
    // - If initial_mem is a Phi, L is live at the entry of the initial_mem block
    //   (Phis execute in parallel at the start of the block by definition).

I don't see these being proved, I can see that points 1, 3, and 5 seems correct. Point 2 I don't understand but it is probably because I don't understand what a root is. Point 4, I thought `initial_mem` should dominate the early block, because it is an input of the load?

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

PR Comment: https://git.openjdk.org/jdk/pull/22852#issuecomment-2612932093