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

[Daniel Lundén]

On Fri, 24 Jan 2025 16:30:53 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

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

No, I do not mean graph equivalence (I'll improve my wording) nor scheduling equivalence. What I mean is semantic equivalence in the sense of [programming language semantics](https://en.wikipedia.org/wiki/Semantics_(computer_science)). I.e., the IR resulting from replacing the load's memory input with one of the roots represents the same computation as the original IR, whereas replacing the input with some arbitrary memory node in the graph would likely break semantic equivalence (and likely cause a crash or miscompilation).

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

Same here, equivalent in the sense of program semantics, not scheduling equivalence. I'm open to rewording suggestions.

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

- With point 2 I mean that all equivalent memory inputs to the load (= roots) must occur before it (i.e., dominate the earliest possible block in which we can schedule the load).
- Note the wording in point 4: _strictly_ dominates. Yes, `initial_mem_block` always dominates the the early block, and often `initial_mem_block` = `early` (in which case `initial_mem` may occur late in the block and is not live at entry).

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

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