JIT: Flow Graph Modernization and Improved Block Layout

Overview

The current block layout algorithm in the JIT is based on local permutations of block order. It is complicated and likely far from optimal. We would like to improve the overall block layout algorithm used by the JIT, in particular adopting a global cost-minimizing approach to layout—for instance, one in the style of Young et. al.'s Near-optimal intraprocedural branch alignment. Additional complexities arise in our case because of various EH reporting requirements, so the JIT cannot freely reorder all blocks, but we should be able to apply the global ordering techniques within EH regions.

Before we can tackle this problem there are several important (and sizeable) prerequisites, which we can lump together as "flow graph modernization." There are a lot of details here, but at a high level:

Update the flow graph to make fall-through behavior explicit for most phases (until layout). This means disallowing BBJ_NONE and adding explicit fall through successors for BBJ_COND and BBJ_SWITCH. More on this below.
Defer most block reordering work until late in the JIT phase pipeline (ideally, perhaps, waiting until after LSRA has run, so we can properly position any new blocks it introduces).
Leverage the work done in .NET 8 to make flow edges persistent and ensure that those edges accurately describe successor likelihoods. Possibly make successor edge enumeration a first-class concept.

It is not yet clear how much progress we can make during .NET 9. The list of items below is preliminary and subject to change.

Motivation

Past studies have shown that the two phases that benefit most from block-level PGO data are inlining and block layout. In a previous compiler project, the net benefit from PGO was on the order of 15%, with about 12% attributable to inlining, and 2% to improved layout.

The current JIT is likely seeing a much smaller benefit from layout. The goal here is to ensure that we are using the accurate PGO data to make informed decisions about the ordering of blocks, with the hope of realizing perhaps a 1 or 2% net benefit across a wide range of applications (with some benefiting much more, and others, not at all).

Flow Graph Modernization

[ ] No implicit fall through (until layout)
- [x] Hide various fields on BasicBlock behind setters/getters (bbNext, bbJumpKind, bbJumpTarget, ...)
- https://github.com/dotnet/runtime/pull/92908
- https://github.com/dotnet/runtime/pull/93032
- https://github.com/dotnet/runtime/pull/93152
- https://github.com/dotnet/runtime/pull/93415
- [x] Introduce explicit fall through successor field and make sure it is properly updated. Initially it will just mirror bbNext for blocks with fall-through jump kinds
- https://github.com/dotnet/runtime/pull/93772
- https://github.com/dotnet/runtime/pull/94239
- https://github.com/dotnet/runtime/issues/95355
- [x] Start allowing the fall through target to diverge from bbNext. Might be best to do this gradually, working front-to-back through the phases, and then restoring correspondence. Eventually we'll be restoring right at block layout. Main work here is root out places that implicitly rely on bbNext ordering having some important semantic. Note the bbNext order can still reflect likely layout order (e.g., it can agree with fall throughs after we renumber/etc.).
- https://github.com/dotnet/runtime/pull/97488
- [x] Start removing / conditionalizing the logic that reverses branches and/or introduces new blocks to preserve implicit fall-through behavior, upstream of the changes above
- https://github.com/dotnet/runtime/pull/97488
- https://github.com/dotnet/runtime/pull/99271
- [x] Revisit redundant branch optimization logic, now that implicit fallthrough is disallowed (see conversation here).
- https://github.com/dotnet/runtime/pull/97722
[ ] Defer block reordering (until layout).
- [ ] Disable any remaining bits of code in the jit that reorder blocks early. We likely will still want to run various flow graph simplification steps (combining blocks, removing empty blocks, etc.). But we should not need to reverse conditionals.
[ ] Make edge profile data reliable throughout the phases
- [x] Ensure that edge likelihoods are set for all flow edges, then ensure that successor edge likelihoods sum to 1.0.
- [x] #97740
- [x] #99024
- [x] #99367
- [x] #99541
- [x] #99628
- [x] Make access to successor edges cheaper/more explicit. For instance, replace direct BasicBlock references for bbJumpTarget with the appropriate FlowEdge. Consider (perhaps) linking FlowEdges in a successor list as well as predecessor list.
- [x] #98563
- [x] #98671
- [x] #98993
- [x] Look into automatic maintenance of pred and successor edge lists
- [x] #99362
- [x] #99561
- [x] Audit updates to likelihoods to make sure they are locally reasonable (likely we won't spot these until we start checking block weight consistency)
- [x] https://github.com/dotnet/runtime/pull/100899
- [x] https://github.com/dotnet/runtime/pull/100869
- [x] Be explicit about points where profile becomes inconsistent, and check for consistency
- [x] https://github.com/dotnet/runtime/pull/100899
- [x] https://github.com/dotnet/runtime/pull/101011
- [x] https://github.com/dotnet/runtime/pull/101259
- [x] https://github.com/dotnet/runtime/pull/101575
- [x] https://github.com/dotnet/runtime/pull/101739
- [x] https://github.com/dotnet/runtime/pull/101834
- [ ] Introduce a profile repair phase that we run (likely before LSRA/layout) to re-establish global consistency of block weights. Also looking at always running repair intially so we have iniital count consistency (that is, we are considering favoring consistency over accuracy)
- [x] As a part of this, find a solution to recovering block weights in graphs with irreducible loops (see https://github.com/dotnet/roslyn/issues/39814 and https://github.com/dotnet/runtime/issues/82964#issuecomment-1454245176)
- [x] https://github.com/dotnet/runtime/pull/99992
- [x] https://github.com/dotnet/runtime/pull/100385
- [x] https://github.com/dotnet/runtime/pull/100449
- [x] https://github.com/dotnet/runtime/pull/100456
- [ ] Possibly other deferred items from the profile synthesis work done in .NET 8 (see https://github.com/dotnet/runtime/issues/82964#issue-1609346906)
- [x] Remove the current min/max edge weight fields on FlowEdge and the code that sets them, update all customers to use new likelihood based weights.
- [x] https://github.com/dotnet/runtime/pull/99736
- [ ] (stretch) Change BB_UNITY_WEIGHT to be 1.0

Block Layout

[ ] Look into running existing layout after LSRA. Note there may be some tricky interactions, if say reversing a conditional perturbs the allocation for some reason
[x] Building on the work above, leverage block weights and successor edge likelihoods to build a good initial layout via something like a greedy RPO
- [x] https://github.com/dotnet/runtime/pull/101473
[ ] Implement some sort of layout score describing costs of a layout
[ ] (Possibly) find a way of estimating the optimal layout score
[ ] (stretch) Implement a scheme to improve layout based on lowering score; one such scheme is described in Near-optimal intraprocedural branch alignment
[ ] Consider removing Compiler::fgFindInsertPoint, and similar logic that attempts to maintain reasonable orderings before block layout is run (see comment).
[ ] Consider skipping loop compaction and relying on the new layout algorithm to place loop bodies contiguously.
[ ] Think about the interaction of layout and hot/cold splitting

cc @amanasifkhalid @dotnet/jit-contrib

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

Issue Details

### Overview The current block layout algorithm in the JIT is based local permutations of block order. It is complicated and likely far from optimal. We would like to improve the overall block layout algorithm used by the JIT, in particular adopting a glboal cost-minimizing approach to layout—for instance, one in the style of Young et. al.'s [Near-optimal intraprocedural branch alignment](https://dl.acm.org/doi/abs/10.1145/258915.258932). Additional complexities arise in our case because of various EH reporting requirements, so the JIT cannot freely reorder all blocks, but we should be able to apply the global ordering techniques within EH regions. Before we can tackle this problem there are several important (and sizeable) prerequisites, which we can lump together as "flow graph modernization." There are a lot of details here, but at a high level: * Update the flow graph to make fall-through behavior explicit for most phases (until layout). This means disallowing BBJ_NONE and adding explicit fall through successors for BBJ_COND and BBJ_SWITCH. More on this below. * Defer most block reordering work until late in the JIT phase pipeline (ideally, perhaps, waiting until after LSRA has run, so we can properly position any new blocks it introduces). * Leverage the work done in .NET 8 to make flow edges persistent and ensure that those edges accurately describe successor likelihoods. Possibly make successor edge enumeration a first-class concept. It is not yet clear how much progress we can make during .NET 9. The list of items below is preliminary and subject to change. #### Flow Graph Modernization - [ ] No implicit fall through (until layout) - [ ] Hide various fields on `BasicBlock` behind setters/getters (`bbNext`, `bbJumpKind`, `bbJumpTarget`, ...) - https://github.com/dotnet/runtime/pull/92908 - [ ] Introduce explicit fall through successor field and make sure it is properly updated. Initially it will just mirror `bbNext` for blocks with fall-through jump kinds - [ ] Start allowing the fall through target to diverge from `bbNext`. Might be best to do this gradually, working front-to-back through the phases, and then restoring correspondence. Eventually we'll be restoring right at block layout. Main work here is root out places that implicitly rely on `bbNext` ordering having some important semantic. Note the `bbNext` order can still reflect likely layout order (eg it can agree with fall throughs after we renumber/etc). - [ ] Start removing / conditionalizing the logic that reverses branches and/or introduces new blocks to preserve implicit fall-through behavior, upstream of the changes above - [ ] Defer block reordering (until layout). - [ ] Disable any remaining bits of code in the jit that reorder blocks early. We likely will still want to run various flow graph simplification steps (combining blocks, removing empty blocks, etc). But we should not need to reverse conditionals. - [ ] Make edge profile data reliable throughout the phases - [ ] Ensure that edge likelihoods are set for all flow edges, then ensure that successor edge likelihoods sum to 1.0. - [ ] Make access to successor edges cheaper/more explicit. For instance, replace direct `BasicBlock` references for `bbJumpTarget` with the appropriate `FlowEdge`. Consider (perhaps) linking `FlowEdges` in a successor list as well as predecessor list. - [ ] Look into automatic maintenance of pred and successor edge lists - [ ] Audit updates to likelihoods to make sure they are locally reasonable - [ ] Introduce a profile repair phase that we run (likely before LSRA/layout) to re-establish global consistency of block weights - [ ] As a part of this, find a solution to recovering block weights in graphs with irreducible loops #### Block Layout - [ ] Look into running existing layout after LSRA. Note there may be some tricky interactions, if say reversing a conditional perturbs the allocation for some reason - [ ] Building on the work above, leverage block weights and successor edge likelihoods to build a good initial layout via something like a greedy RPO - [ ] Implement some sort of layout score describing costs of a layout - [ ] (Possibly) find a way of estimating the optimal layout score - [ ] Implement a scheme to improve layout based on lowering score; one such scheme is described in [Near-optimal intraprocedural branch alignment](https://dl.acm.org/doi/abs/10.1145/258915.258932) - [ ] Think about the interaction of layout and hot/cold splitting cc @amanasifkhalid @dotnet/jit-contrib

Author:	AndyAyersMS
Assignees:	-
Labels:	`area-CodeGen-coreclr`
Milestone:	9.0.0

As a prerequisite for some of the block reordering work we'll likely need to change loop alignment to be more centralized. We currently identify the initial candidate blocks to place loop alignment instructions in during loop finding and apply some heuristics when computing loop side effects during VN. We will probably need to defer all of these decisions to happen after block reordering. I am also inclined to say that we should just recompute the loops at that point, instead of trying to maintain loop information -- we have a lot of code that works hard to maintain bbNatLoopNum all the way into the backend that we could remove. Since the block reordering is likely to need a DFS as well, the extra TP we'll end up paying is just for the loop identification, which is not that much (tpdiff).

Potential .NET 10 items

Block layout:

[ ] Implement 3-opt pass on top of the RPO-based layout, modeling layout cost with edge weights
[ ] Consider modeling cost of (un)conditional and forward/backward branches in layout cost for 3-opt
[ ] Consider running layout after LSRA
[ ] Consider running profile repair before layout, at least to ensure blocks with nontrivial flow into them are not marked as cold

Flowgraph Modernization:

[ ] Continue profile maintenance work up to block layout
[ ] Reconsider flow optimizations in Compiler::fgUpdateFlowGraph, particularly those that use block list pointers (bbNext and bbPrev) instead of control flow to make decisions; now that various implicit fallthrough invariants are gone, some of the transformations here might be underutilized or irrelevant
[ ] Also consider expanding fgUpdateFlowGraph's transformations to aid block layout. In particular, the old block layout would run Compiler::fgOptimizeBranch if it decided against moving a BBJ_ALWAYS that jumps to a BBJ_COND. We currently don't do any such pass, though if we decide not to compact the BBJ_ALWAYS, cloning its successor's condition can help us avoid "double-jumping" (comment).
[ ] Audit interactions between more aggressive block compaction and other phases, like loop inversion and cloning. More compaction can trigger various EH constraints and pessimize optimizations; for example, we might move a loop body up a try region until the loop header is the first block of the region, thus blocking loop cloning. Many of these invariants can probably be relaxed under some circumstances
[ ] Allow profile data to override the JIT's heuristics for cold blocks. In particular, the JIT assumes BBJ_THROW blocks are cold, so even if there is nontrivial flow into a throw block, fgMoveColdBlocks will do the "wrong" thing and move it to the end of the method. For methods that always throw, the performance impact of layout is probably trivial, though if we can get a close-to-optimal layout from the RPO pass, we'll avoid wasting time during 3-opt.
[ ] Consider removing the old layout code altogether. This will allow us to remove various other components of the JIT that prematurely order blocks, such as fgFindInsertPoint.
[ ] Continue any deferred items from .NET 9

cc @AndyAyersMS, feel free to add to this.

I think that's a good start. I'm going to move this issue to .NET 10 for now, later we can decide if we want to split off a new issue or just revise this one.

Let's split off a new issue for future work.

dotnet / runtime