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

[Daniel Lundén]

On Mon, 27 Jan 2025 11:52:38 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

> I feel less comfortable with a fix that does not understand the issue and just try to find a seemingly arbitrary way to fix the issues that are observed because it will not fix the unobserved issues. Of course, this will reduce the probability that we mis-schedule a program but it will just kick the can down the road for us to come back later.

Fair enough, but I do not agree the fix is uninformed nor arbitrary. The required (local) fix is clear from the failures we've seen. Summarizing our discussion so far, the problem you see is that my justification reasons about equivalent memory inputs and not the memory graph topology directly? I of course do not disagree that we should continue investigating the issue and, in particular, try to strengthen memory graph invariants to potentially make the fix redundant.

If there is a preference for not fixing the issue urgently in expectation of a more fundamental fix, I'm fine with that. However, a more fundamental fix that is likely not local to `insert_anti_dependences` may also be more difficult to backport.

> This part assumes a scheduled program and reason about its behaviours, with which we can go back and realize the constraints we have regarding anti-dependencies.

> When an input of a Phi is 2-killed, the Phi is 2-killed. This prevents the kill of this Phi from affecting the liveness of other inputs of the same Phi because this cascade requires 1-kill which is stronger.

OK, thanks for clarifying.

> From the sole topology of the graph, I am not convinced by this, unless the memory graph has additional invariants that ensure it is not relevant (e.g. a memory node becomes undefined after a MergeMem or a Phi, but I'm not aware of any such properties).

I agree, looking at the memory graph _currently_ it is not enough to go downwards (in fact, I have an example where there is not even a downwards path from the load's memory input to the anti-dependence). But, I think this is because we mess up the memory graph earlier on, and that it's not an issue with the anti-dependence search.

> Suppose initial_mem is 2 Phi, we need to search for kills at in (go up, which means we reach in from below), then from in we go down to 1 Phi and search for kills at it, too.

If we can ensure that there is only one possible memory input to each load (which currently is not true), I do not believe we must search upwards from Phis.

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

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