JIT: Reconsider ordering of SSA-based phases

[jakobbotsch]

SSA currently is considered invalid after RBO since it makes non-trivial changes to the flow graph. However, we still make use of SSA information in assertion prop, range check and VN-based dead store removal that all run after RBO. I think we should either 1) Make an explicit decision that SSA information can be considered valid after RBO and assertion prop. This means we should run the SSA-checker after these phases as well. IIRC assertion prop makes changes that are not actually compatible with SSA, which seems scary with the current state of things. 2) Reorder things so that no SSA-based phase runs after RBO. This probably means having assertion prop leave some breadcrumbs for flowgraph updates to be made by RBO since I think assertion prop does make some FG changes today.

cc @dotnet/jit-contrib

[ghost]

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch See info in area-owners.md if you want to be subscribed.

Issue Details

---

SSA currently is considered invalid after RBO since it makes non-trivial changes to the flow graph. However, we still make use of SSA information in assertion prop, range check and VN-based dead store removal that all run after RBO. I think we should either 1) Make an explicit decision that SSA information can be considered valid after RBO and assertion prop. This means we should run the SSA-checker after these phases as well. IIRC assertion prop makes changes that are not actually compatible with SSA, which seems scary with the current state of things. 2) Reorder things so that no SSA-based phase runs after RBO. This probably means having assertion prop leave some breadcrumbs for flowgraph updates to be made by RBO since I think assertion prop does make some FG changes today. cc @dotnet/jit-contrib

Author:	jakobbotsch
Assignees:	-
Labels:	`area-CodeGen-coreclr`, `untriaged`
Milestone:	-

[SingleAccretion]

assertion prop

IIRC, there is not much dependence in assertion propagation on SSA (there is one minor optimization with non-nullness and PHIs). Assertion prop also invokes morph, which makes the set of possible transformations to the IR/flowgraph rather large. This all points to it being a good candidate for an "invalid SSA, valid VN" state.

range check

Depends deeply on assertions, and so must be after assertion propagation, but depends equally deeply on SSA. A circular dependency.

VN-based dead store removal and RBO

VN-based dead store removal invalidated SSA "violently", by deleting SSA definitions. It means it has to run after all of the other SSA-dependent phases (or be deleted, it is not a hugely important optimization). If RBO also invalidates SSA, that's another circular dependency.

All in all, it doesn't seem viable to do the simple thing of 2 (unless you're willing to recompute SSA). It means we have to rationalize what sort of changes are legal and what sort of "damage" is tolerable, i. e. some variation on 1.

BTW, here's an example of a recent-ish bug caused by this SSA maintenance problem: https://github.com/dotnet/runtime/issues/91839.

[jakobbotsch]

We consider SSA invalid after RBO, but that's pretty new -- with https://github.com/dotnet/runtime/pull/95682. Before that we considered it valid until before assertion prop (not much better considering what runs after assertion prop). RBO already makes sure it doesn't invalidate phis for downstream phases, so it does try to keep SSA valid, even with the flowgraph changes made.

From what you say it does seem like the only viable solution is to get a better grasp of assertion prop and what changes it should be making. That probably starts out by avoiding its call into morph.

[jakobbotsch]

@AndyAyersMS Is something fundamental stopping us from running RBO later (say right before VN-based dead store removal)? If SSA is not valid at that point that's problematic for the phi-based threading, but other phases running at that point are already relying on SSA... It also seems like it would allow RBO to not worry about messing up phis.

Really what I'm hoping for is that we can make sure no flow graph changes are made until we stop relying on SSA (well, VN-based dead store removal still would have a dependency, but it's easier to reason about). That should simplify SSA updating significantly and also allow me to move #97865 to a much more natural point later during opts (after range check but before RBO).

[AndyAyersMS]

@AndyAyersMS Is something fundamental stopping us from running RBO later

Nothing fundamental, just phase ordering. Assertion prop does dataflow, so it gets sharper propagation running after RBO and so does a better job. Not sure how significant this is.

CSE has a similar tension with RBO, I'd rather run it before than after to avoid the messiness with BBF_NO_CSE_IN, but swapping them misses cases.

What this might be pointing us at is something like: we run RBO late, and if it succeeds, we think about doing an opt repeat. Though it would also be nice for some phases to know we're on the last optimization pass.