Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JIT: Flow Graph Modernization and Improved Block Layout #93020

Closed
37 of 51 tasks
AndyAyersMS opened this issue Oct 4, 2023 · 5 comments
Closed
37 of 51 tasks

JIT: Flow Graph Modernization and Improved Block Layout #93020

AndyAyersMS opened this issue Oct 4, 2023 · 5 comments
Assignees
Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI User Story A single user-facing feature. Can be grouped under an epic.
Milestone

Comments

@AndyAyersMS
Copy link
Member

AndyAyersMS commented Oct 4, 2023

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

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

@AndyAyersMS AndyAyersMS added the area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI label Oct 4, 2023
@AndyAyersMS AndyAyersMS added this to the 9.0.0 milestone Oct 4, 2023
@ghost
Copy link

ghost commented Oct 4, 2023

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. 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, ...)
    • 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
  • 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

amanasifkhalid added a commit that referenced this issue Oct 6, 2023
@JulieLeeMSFT JulieLeeMSFT added the User Story A single user-facing feature. Can be grouped under an epic. label Oct 6, 2023
amanasifkhalid added a commit that referenced this issue Nov 28, 2023
Next step for #93020, per conversation on #93772. Replacing BBJ_NONE with BBJ_ALWAYS to the next block helps limit our use of implicit fall-through (though we still expect BBJ_COND to fall through when its false branch is taken; #93772 should eventually address this).

I've added a small peephole optimization to skip emitting unconditional branches to the next block during codegen.
@jakobbotsch
Copy link
Member

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).

amanasifkhalid added a commit that referenced this issue Jan 1, 2024
…96265)

Part of #93020. Previously, bbFalseTarget was hard-coded to match bbNext in BasicBlock::SetNext. We still require bbFalseTarget to point to the next block for BBJ_COND blocks, but I've removed the logic for updating bbFalseTarget from SetNext, and placed calls to SetFalseTarget wherever bbFalseTarget needs to be updated because the BBJ_COND block has been created or moved relative to its false successor. This helps set us up to start removing logic that enforces the block's false successor is the next block.
amanasifkhalid added a commit that referenced this issue Jan 3, 2024
…e target (#96431)

Next step for #93020. When doing hot/cold splitting, if the first cold block succeeds a BBJ_COND block (meaning the false target is the first cold block), we previously needed to insert a BBJ_ALWAYS block at the end of the hot section to unconditionally jump to the cold section. Since we will need to conditionally generate a jump to the false target depending on its location once bbFalseTarget can diverge from bbNext, this seemed like a nice opportunity to add that logic in, and instead generate a jump to the cold section by checking if a jump is needed to the false target, rather than by appending a BBJ_ALWAYS block to the hot section.
amanasifkhalid added a commit that referenced this issue Jan 16, 2024
Before finalizing the block layout with optOptimizeLayout, we call fgReorderBlocks in a few optimization passes that modify the flowgraph (though without the intent to actually reorder any blocks, by passing useProfile=false). Removing all of these early calls -- except for the one in optOptimizeFlow, which can probably be replaced by moving fgReorderBlocks's branch optimization logic to fgUpdateFlowGraph -- incurs relatively few diffs, and gets us closer to #93020's goal of deferring block reordering until late in the JIT's optimization phases.
amanasifkhalid added a commit that referenced this issue Jan 17, 2024
…imization phase (#96609)

Next step for #93020. Working backwards through the JIT flowgraph phases, this change allows bbFalseTarget to diverge from bbNext in Compiler::optOptimizeLayout and onwards.
tmds pushed a commit to tmds/runtime that referenced this issue Jan 23, 2024
Before finalizing the block layout with optOptimizeLayout, we call fgReorderBlocks in a few optimization passes that modify the flowgraph (though without the intent to actually reorder any blocks, by passing useProfile=false). Removing all of these early calls -- except for the one in optOptimizeFlow, which can probably be replaced by moving fgReorderBlocks's branch optimization logic to fgUpdateFlowGraph -- incurs relatively few diffs, and gets us closer to dotnet#93020's goal of deferring block reordering until late in the JIT's optimization phases.
tmds pushed a commit to tmds/runtime that referenced this issue Jan 23, 2024
…imization phase (dotnet#96609)

Next step for dotnet#93020. Working backwards through the JIT flowgraph phases, this change allows bbFalseTarget to diverge from bbNext in Compiler::optOptimizeLayout and onwards.
amanasifkhalid added a commit that referenced this issue Jan 29, 2024
Part of #93020. This change adds back in most of #97191 and #96609, except for any significant changes to the flowgraph optimization passes to reduce churn. With this change, the false target of a BBJ_COND can diverge from the next block until Compiler::optOptimizeLayout, in which we reestablish implicit fall-through with fgConnectFallThrough to preserve the existing block reordering behavior. Note that the deferral of these fall-through fixups causes diffs in the edge weights, which can alter the behavior of fgReorderBlocks, hence some of the size regressions
AndyAyersMS added a commit that referenced this issue May 4, 2024
Advance profile consistency check through inlining. Turns out there are
five reasons why inlining may make profile data inconsistent. Account
for these and add metrics.

Also add separate metrics for consistency before and after inlining,
since pre-inline phases are run on inlinees and so don't give us good
insight into overall consistency rates. And add some metrics for
inlining itself.

Contributes to #93020.

Co-authored-by: Aman Khalid <[email protected]>
michaelgsharp pushed a commit to michaelgsharp/runtime that referenced this issue May 9, 2024
When dynamic PGO is active we would like for all methods to have some
profile data, so we don't have to handle a mixture of profiled and unprofiled
methods during or after inlining.

But to reduce profiling overhead, the JIT will not instrument methods that have
straight-line control flow, or flow where all branches lead to throws (aka
"minimal profiling"). When the JIT tries to recover profile data for these methods
it won't get any data back. SO there is a fairly high volume of these profiled/unprofiled
mixtures today and they lead to various poor decisions in the JIT.

This change enables the JIT to see if dynamic PGO is active. The JIT does not yet
do anything with the information. A subsequent change will have the JIT synthesize
data for methods with no profile data in this case.

We could also solve this by creating a placeholder PGO schema for theswith no data, but it seems
simpler and less resource intensive to have the runtime tell the JIT that dynamic PGO
is active.

This also changes the JIT GUID for the new API surface.

Contributes to dotnet#93020.
michaelgsharp pushed a commit to michaelgsharp/runtime that referenced this issue May 9, 2024
Part of dotnet#93020. Compiler::fgDoReversePostOrderLayout reorders blocks based on a RPO of the flowgraph's successor edges. When reordering based on the RPO, we only reorder blocks within the same EH region to avoid breaking up their contiguousness. After establishing an RPO-based layout, we do another pass to move cold blocks to the ends of their regions in fgMoveColdBlocks.

The "greedy" part of this layout isn't all that greedy just yet. For now, we use edge likelihoods to make placement decisions only for BBJ_COND blocks' successors. I plan to extend this greediness to other multi-successor block kinds (BBJ_SWITCH, etc) in a follow-up so we can independently evaluate the value in doing so.

This new layout is disabled by default for now.
michaelgsharp pushed a commit to michaelgsharp/runtime that referenced this issue May 9, 2024
…101739)

If we know dynamic PGO is active, and we do not find a PGO schema for a method,
synthesize PGO data. The schema may be missing if the method was prejitted but
not covered by static PGO, or was considered too simple to need profiling (aka
minimal profiling).

This synthesis removes the possibility of a mixed PGO/no PGO situation. These
are problematic, especially in methods that do a lot of inlining. Now when
dynamic PGO is active all methods that get optimized will have some form of
PGO data.

Only run profile incorporation when optimizing. Reset BBOPT/pgo vars if we
switch away from optimization or have a min opts failover.

Contributes to dotnet#93020.
michaelgsharp pushed a commit to michaelgsharp/runtime that referenced this issue May 9, 2024
Advance profile consistency check through inlining. Turns out there are
five reasons why inlining may make profile data inconsistent. Account
for these and add metrics.

Also add separate metrics for consistency before and after inlining,
since pre-inline phases are run on inlinees and so don't give us good
insight into overall consistency rates. And add some metrics for
inlining itself.

Contributes to dotnet#93020.

Co-authored-by: Aman Khalid <[email protected]>
amanasifkhalid added a commit that referenced this issue May 21, 2024
…ayout (#102461)

Part of #93020. In #102343, we noticed the RPO-based layout sometimes makes suboptimal decisions in terms of placing a block's hottest predecessor before it -- in particular, this affects loops that aren't entered at the top. To address this, after establishing a baseline RPO layout, fgMoveBackwardJumpsToSuccessors will try to move backward unconditional jumps to right behind their targets to create fallthrough, if the predecessor block is sufficiently hot.
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
Instead of giving hander regions a fraction of the entry weight, give them a small
fixed weight. This is intended to combat the lack of profile propagation out of
handler regions, where there are currently sometimes weight discontinuities large
enough to cause profile check asserts.

Contributes to dotnet#93020.
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
Move the full profile check down past the importer. Attempt local repair
for cases where the importer alters BBJ_COND. If that is unable to guarantee
consistency, mark the PGO data as inconsistent.

If the importer alters BBJ_SWITCH don't attempt repair, just mark the profile
as inconsistent.

If in an OSR method the original method entry is a loop header, and that is
not the loop that triggered OSR, mark the profile as inconsistent.

If the importer re-imports a LEAVE, there are still orphaned blocks left from
the first importation, these can mess up profiles. In that case, mark the
profile as inconsistent.

Exempt blocks with EH preds (catches, etc) from inbound checking, as
profile data propagation along EH edges is not modelled.

Modify the post-phase checks to allow either small relative errors or small
absolute errors, so that flow out of EH regions though intermediaries (say
step blocks) does not trip the checker.

Ensure the initial pass of likelihood adjustments pays attention to
throws. And only mark throws as rare in the importer if we have not
synthesized profile data (which may in fact tell us the throw is not cold).

Contributes to dotnet#93020
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
Part of dotnet#93020. Removes FlowEdge::m_edgeWeightMin and FlowEdge::m_edgeWeightMax, and relies on block weights and edge likelihoods to determine edge weights via FlowEdge::getLikelyWeight.
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
…1011)

Fixes the following areas with proper profile updates:
* GDV chaining
* instrumentation-introduces flow
* OSR step blocks
* fgSplitEdge (used by instrumentation)

Adds checking bypasses for:
* callfinally pair tails
* original method entries in OSR methods

Contributes to dotnet#93020
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
When dynamic PGO is active we would like for all methods to have some
profile data, so we don't have to handle a mixture of profiled and unprofiled
methods during or after inlining.

But to reduce profiling overhead, the JIT will not instrument methods that have
straight-line control flow, or flow where all branches lead to throws (aka
"minimal profiling"). When the JIT tries to recover profile data for these methods
it won't get any data back. SO there is a fairly high volume of these profiled/unprofiled
mixtures today and they lead to various poor decisions in the JIT.

This change enables the JIT to see if dynamic PGO is active. The JIT does not yet
do anything with the information. A subsequent change will have the JIT synthesize
data for methods with no profile data in this case.

We could also solve this by creating a placeholder PGO schema for theswith no data, but it seems
simpler and less resource intensive to have the runtime tell the JIT that dynamic PGO
is active.

This also changes the JIT GUID for the new API surface.

Contributes to dotnet#93020.
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
Part of dotnet#93020. Compiler::fgDoReversePostOrderLayout reorders blocks based on a RPO of the flowgraph's successor edges. When reordering based on the RPO, we only reorder blocks within the same EH region to avoid breaking up their contiguousness. After establishing an RPO-based layout, we do another pass to move cold blocks to the ends of their regions in fgMoveColdBlocks.

The "greedy" part of this layout isn't all that greedy just yet. For now, we use edge likelihoods to make placement decisions only for BBJ_COND blocks' successors. I plan to extend this greediness to other multi-successor block kinds (BBJ_SWITCH, etc) in a follow-up so we can independently evaluate the value in doing so.

This new layout is disabled by default for now.
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
…101739)

If we know dynamic PGO is active, and we do not find a PGO schema for a method,
synthesize PGO data. The schema may be missing if the method was prejitted but
not covered by static PGO, or was considered too simple to need profiling (aka
minimal profiling).

This synthesis removes the possibility of a mixed PGO/no PGO situation. These
are problematic, especially in methods that do a lot of inlining. Now when
dynamic PGO is active all methods that get optimized will have some form of
PGO data.

Only run profile incorporation when optimizing. Reset BBOPT/pgo vars if we
switch away from optimization or have a min opts failover.

Contributes to dotnet#93020.
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
Advance profile consistency check through inlining. Turns out there are
five reasons why inlining may make profile data inconsistent. Account
for these and add metrics.

Also add separate metrics for consistency before and after inlining,
since pre-inline phases are run on inlinees and so don't give us good
insight into overall consistency rates. And add some metrics for
inlining itself.

Contributes to dotnet#93020.

Co-authored-by: Aman Khalid <[email protected]>
Ruihan-Yin pushed a commit to Ruihan-Yin/runtime that referenced this issue May 30, 2024
…ayout (dotnet#102461)

Part of dotnet#93020. In dotnet#102343, we noticed the RPO-based layout sometimes makes suboptimal decisions in terms of placing a block's hottest predecessor before it -- in particular, this affects loops that aren't entered at the top. To address this, after establishing a baseline RPO layout, fgMoveBackwardJumpsToSuccessors will try to move backward unconditional jumps to right behind their targets to create fallthrough, if the predecessor block is sufficiently hot.
@JulieLeeMSFT JulieLeeMSFT moved this to Team User Stories in .NET Core CodeGen Jun 5, 2024
@amanasifkhalid
Copy link
Member

amanasifkhalid commented Jul 22, 2024

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.

@AndyAyersMS
Copy link
Member Author

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.

@AndyAyersMS AndyAyersMS modified the milestones: 9.0.0, 10.0.0 Jul 22, 2024
@AndyAyersMS
Copy link
Member Author

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

@github-project-automation github-project-automation bot moved this from Team User Stories to Done in .NET Core CodeGen Jul 31, 2024
@github-actions github-actions bot locked and limited conversation to collaborators Aug 31, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI User Story A single user-facing feature. Can be grouped under an epic.
Projects
Status: Done
Development

No branches or pull requests

4 participants