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

[Quan Anh Mai]

On Mon, 27 Jan 2025 13:28:05 GMT, Daniel Lundén <dlunden at openjdk.org> wrote:

> 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?

My problem is that you don't formally define what "equivalent memory inputs" is, and as a consequence, I don't understand what it means. We are working with graphs and any definitions you pull out must define itself on the graph. Your patch has this:

    // 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 preserve ideal graph
    // validity.

This raises the question what you mean by "ideal graph validity" and how it presents itself on the graph. If I wire all nodes to `C->immutable_memory()`, then I will surely have a valid graph, the issue is that the result does not represent the same program as the original graph, but it is still a valid graph, and I don't find a way out of this contradiction. Previously, you mention equivalency in terms of program semantics, but I don't understand how it presents itself in the graph during this stage of compilation. Please make a formal definition for this.

> 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.

I strongly disagree, unless we can come up with a formal restriction on the memory graph that will imply this property, just thinking we mess up somewhere and blindly following this assumption that something must hold is not a good approach.

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

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