JIT: Flow Graph Modernization and Improved Block Layout #93020

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, ...)
    • JIT: Make BasicBlock::bbJumpKind private #92908
    • JIT: Make BasicBlock::bbPrev and bbNext private #93032
    • JIT: Make BasicBlock jump target private #93152
    • JIT: Set bbJumpKind and bbJumpDest during block initialization #93415
  • 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
    • JIT: Add explicit block fallthrough successor #93772
    • JIT: Remove BBJ_NONE #94239
    • Consider changing BBJ_CALLFINALLY/BBJ_ALWAYS representation of call to finally #95355
  • 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.).
    • JIT: Remove most fgConnectFallThrough calls #97488
  • Start removing / conditionalizing the logic that reverses branches and/or introduces new blocks to preserve implicit fall-through behavior, upstream of the changes above
    • JIT: Remove most fgConnectFallThrough calls #97488
    • JIT: Remove remaining BBJ_COND fallthrough fixups #99271
  • Revisit redundant branch optimization logic, now that implicit fallthrough is disallowed (see conversation here).
    • JIT: remove fallthrough limitations from redundant branch optimizer #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
  • Ensure that edge likelihoods are set for all flow edges, then ensure that successor edge likelihoods sum to 1.0.
    • JIT: Ensure edge likelihoods 1/N #97740
    • JIT: start checking sum of successor likelihoods #99024
    • JIT: profile checking through loop opts #99367
    • JIT: more likelihood checking #99541
    • JIT: enable edge checks throughout #99628
  • 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.
    • JIT: Use successor edges instead of block targets for BBJ_EHFINALLYRET #98563
    • JIT: Use successor edges instead of block targets for BBJ_SWITCH #98671
    • JIT: Use successor edges instead of block targets for remaining block kinds #98993
  • Look into automatic maintenance of pred and successor edge lists
    • JIT: Add helper method for updating bbTargetEdge #99362
    • JIT: Add fgRedirectTrueEdge, fgRedirectFalseEdge #99561
  • Audit updates to likelihoods to make sure they are locally reasonable (likely we won't spot these until we start checking block weight consistency)
    • JIT: revise how synthesis treats handler regions #100899
    • JIT: verify full profile consistency after importation #100869
  • 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))
    • JIT: initial work on general count reconstruction #99992
    • JIT: fix count reconstruction problem #100385
    • JIT: fix count reconstruction when a natural loop contains an improper loop #100449
    • JIT: initial profile repair #100456
  • 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.
    • JIT: Use likelihood-based edge weights #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
• Building on the work above, leverage block weights and successor edge likelihoods to build a good initial layout via something like a greedy RPO
  • JIT: Implement greedy RPO-based block layout #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