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

[Daniel Lundén]

On Thu, 30 Jan 2025 13:57:18 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

>>> But if the memory input of a load is `m`, we will never find `kill m1`?
>> 
>> That is an interesting question. I believe the answer is that the load we are considering cannot have `m` as `initial_mem`, as `initial_mem` is always the earliest possible memory definition (`m1`, in this case).
>> 
>> As a thought experiment, if we instead were to consider loading the parts of memory killed by `m2`, `initial_mem` would instead be `m`. There could also be no kills of the load-relevant parts of `m1` or `m2` after `m`, as they are now already killed by `m` (the `Phi` now actually matters as the part of memory we are loading is different in `m1` and `m2`).
>
>> initial_mem is always the earliest possible memory definition (m1, in this case).
> 
> This is a really bold assumption and I assume you do not have any concrete reason for it. "After" in the sense of CFG can only emerge after scheduling, while:
> 
> - We are scheduling.
> - The load and its memory input have existed before scheduling, which makes it very hard to imagine that this is a valid assumption.
> 
> And "after" in the sense of graph edges seems not to be the case, either. As your example has pointed out.

Thanks for the review effort @merykitty. I wrote some ad-hoc assertion code to check if `initial_mem` is always the earliest possible memory input for every load, and you are right: I found a few cases (<0.1% of all cases in my experiment) where the load's memory state is also represented by a memory node in a block strictly dominating `initial_mem`. However, all the failures we've seen in this issue has missing search roots at or below `initial_mem`. I also see no clean way to find search roots above `initial_mem`, so I suggest we go with the current changeset for now. Further investigation is for sure warranted though, and I have a number of RFEs in mind.

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

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