Description
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)
- Hide various fields on
BasicBlock
behind setters/getters (bbNext
,bbJumpKind
,bbJumpTarget
, ...) - 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 onbbNext
ordering having some important semantic. Note thebbNext
order can still reflect likely layout order (e.g., 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
- Revisit redundant branch optimization logic, now that implicit fallthrough is disallowed (see conversation here).
- Hide various fields on
- 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 forbbJumpTarget
with the appropriateFlowEdge
. Consider (perhaps) linkingFlowEdges
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 (likely we won't spot these until we start checking block weight consistency)
- Be explicit about points where profile becomes inconsistent, and check for consistency
- JIT: revise how synthesis treats handler regions #100899
- JIT: Move profile checking back until just before inlining #101011
- JIT: fix stress issue with profile consistency #101259
- Allow JIT to know if dynamic pgo is active #101575
- JIT: synthesize PGO if no schema, when dynamic PGO is active #101739
- JIT: profile checking through inlining #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)
- As a part of this, find a solution to recovering block weights in graphs with irreducible loops (see Async statemachine for methods with loop generate irreducible CFGs roslyn#39814 and Profile Synthesis Work Items #82964 (comment))
- Possibly other deferred items from the profile synthesis work done in .NET 8 (see Profile Synthesis Work Items #82964 (comment))
- 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. - (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
- 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
- (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
Metadata
Assignees
Labels
Type
Projects
Status
Done