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.

Sign up for GitHub

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

Jump to bottom

Loop opts should not be recomputing pred lists from scratch #49030

Closed
AndyAyersMS opened this issue Mar 2, 2021 · 11 comments · Fixed by #80769
Closed

Loop opts should not be recomputing pred lists from scratch #49030

AndyAyersMS opened this issue Mar 2, 2021 · 11 comments · Fixed by #80769
Assignees
@AndyAyersMS
Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI
Milestone
8.0.0

Comments

@AndyAyersMS
Copy link
Member

AndyAyersMS commented Mar 2, 2021 •
edited by BruceForstall
Loading

Several loop opts end up calling fgUpdateChangedFlowGraph when done, and this calls fgComputePreds, leaking previous pred lists and losing the profile weights carefully calculated earlier.

This seems wrong-headed; I think those optimizations should maintain pred lists and not rebuild them.

Removing the call to fgComputePreds shows a number of places in loop opts where pred lists are not properly updated, and more downstream failures from places unknown where BBF_JMP_TARGET is not properly set, so cleaning this up may be nontrivial.

category:cq
theme:loop-opt
skill-level:expert
cost:medium
impact:medium
@dotnet-issue-labeler dotnet-issue-labeler bot added the untriaged New issue has not been triaged by the area owner label Mar 2, 2021
@dotnet-issue-labeler
Copy link

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

@AndyAyersMS
Copy link
Member Author

See notes in #48850 for some context.

@AndyAyersMS
Copy link
Member Author

cc @BruceForstall

@AndyAyersMS AndyAyersMS removed the untriaged New issue has not been triaged by the area owner label Mar 2, 2021
@AndyAyersMS AndyAyersMS added the area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI label Mar 2, 2021
@BruceForstall BruceForstall self-assigned this Mar 3, 2021
@BruceForstall BruceForstall added this to the 6.0.0 milestone Mar 3, 2021
@BruceForstall
Copy link
Member

We used to always need to rebuild pred lists after renumbering blocks due to pred list ordering being dependent on block number, so presumably phases knew they could be sloppy and things would get cleaned up later. But with the new ensurePredListOrder()/reorderPredList(), that's no longer required, as renumbering also keeps preds lists properly ordered.

Maybe we need a pred list checker that runs fgComputePreds but doesn't update the IR, and compares the results against the existing flowgraph (does such a thing exist already?), then fgUpdateChangedFlowGraph can call the checker to verify that no preds need to be updated, and if that check fails, we know which phase caused the problem.

@AndyAyersMS
Copy link
Member Author

I get post-phase check failures about missing preds if I remove the call to fgComputePreds so I think the current checking may be sufficient?

The missing jump target flags might be harder to track down; it's not clear if we have agreement about when the jump target bit needs to be set, and we don't seem to check this post phase. It is checked in codegen.

@BruceForstall
Copy link
Member

BruceForstall commented Apr 13, 2021 •
edited
Loading

I'm thinking we should get rid of BBF_JMP_TARGET entirely and replace its use by BBF_HAS_LABEL for marking blocks that need labels. Then, add a pass over the blocks just before codegen that sets BBF_HAS_LABEL on all necessary blocks, like genPrepForEHCodegen does for EH constructs. Then, we wouldn't need to set and maintain the BBF_JMP_TARGET throughout compilation. We may lose a couple uninteresting asserts but would greatly simplify block maintenance.

@AndyAyersMS
Copy link
Member Author

Sounds good to me.

@BruceForstall
Copy link
Member

BBF_JMP_TARGET was removed with #51208

BruceForstall added a commit to BruceForstall/runtime that referenced this issue Apr 23, 2021
@BruceForstall
Don't recompute preds lists during loop cloning
46b4b6d 
Instead, add and modify the appropriate preds when the mechanical
cloning is performed. This will preserve existing profile data
on the edges.

Contributes to dotnet#49030

No x86/x64 SPMI asm diffs.
@BruceForstall BruceForstall mentioned this issue Apr 23, 2021
Merged
BruceForstall added a commit that referenced this issue Apr 24, 2021
@BruceForstall
Don't recompute preds lists during loop cloning (#51757)
51a116d 
Instead, add and modify the appropriate preds when the mechanical
cloning is performed. This will preserve existing profile data
on the edges.

Contributes to #49030

No x86/x64 SPMI asm diffs.
@JulieLeeMSFT
Copy link
Member

@BruceForstall Please link this issue with your Loop Optimization user story #43549.

@BruceForstall BruceForstall mentioned this issue Apr 29, 2021
Closed
25 tasks
@EgorBo EgorBo mentioned this issue May 8, 2021
Closed
@BruceForstall
Copy link
Member

Loop cloning stopped recomputing preds lists after optimization with #51757

@BruceForstall
Copy link
Member

BruceForstall commented May 10, 2021 •
edited by AndyAyersMS
Loading

Remaining phases calling fgUpdateChangedFlowGraph that recompute preds lists:

@BruceForstall BruceForstall modified the milestones: 6.0.0, 7.0.0 Jul 6, 2021
@BruceForstall BruceForstall mentioned this issue Jul 6, 2021
Closed
5 tasks
@BruceForstall BruceForstall mentioned this issue Feb 15, 2022
Open
24 tasks
@BruceForstall BruceForstall removed this from the 7.0.0 milestone May 26, 2022
@BruceForstall BruceForstall added this to the 8.0.0 milestone May 26, 2022
@AndyAyersMS AndyAyersMS mentioned this issue Jan 4, 2023
Closed
AndyAyersMS added a commit to AndyAyersMS/runtime that referenced this issue Jan 13, 2023
@AndyAyersMS
JIT: maintain pred lists during loop unrolling
6bebcb1 
We now update pred lists during loop unrolling, rather than recomputing
them from scratch.

There are several parts to the fix: first, `optRedirectBlock' now has
a new ability to add pred references for the flow from a newly cloned
block, be it either to a remapped successor or a non-remapped successor.
Along with this we no longer copy over the block ref count in `CloneBlockState`.
These changes allow us to create the right pred links and ref counts in the
interior of a cloned subgraph.

Second, we now scrub block references from the original loop body blocks
instead of just setting their ref counts to zero.

Finally, we fix up references for exterior flow into and out of the unroll
complex.

Addresses one of the cases mentioned in dotnet#49030.
@AndyAyersMS AndyAyersMS mentioned this issue Jan 13, 2023
Merged
AndyAyersMS added a commit that referenced this issue Jan 18, 2023
@AndyAyersMS
JIT: maintain pred lists during loop unrolling (#80625)
e2d192a 
We now update pred lists during loop unrolling, rather than recomputing
them from scratch.

There are several parts to the fix: first, `optRedirectBlock' now has
a new ability to add pred references for the flow from a newly cloned
block, be it either to a remapped successor or a non-remapped successor.
Along with this we no longer copy over the block ref count in `CloneBlockState`.
These changes allow us to create the right pred links and ref counts in the
interior of a cloned subgraph.

Second, we now scrub block references from the original loop body blocks
instead of just setting their ref counts to zero.

Finally, we fix up references for exterior flow into and out of the unroll
complex.

Addresses one of the cases mentioned in #49030.
AndyAyersMS added a commit to AndyAyersMS/runtime that referenced this issue Jan 18, 2023
@AndyAyersMS
JIT: fix remaining phases that were rebuilding pred edges
63ff3a1 
Loop canonicalization now maintains pred edges. GC poll insertion was already
maintaining the edges but was rebuilding them anyways.

Now pred lists are never rebuilt.

Also revise `fgUpdateChangedFlowGraph` so that it no longer has the
ability to remove or rebuild.

Fixes dotnet#49030.
@AndyAyersMS AndyAyersMS mentioned this issue Jan 18, 2023
Merged
@ghost ghost added the in-pr There is an active PR which will close this issue when it is merged label Jan 18, 2023
AndyAyersMS added a commit that referenced this issue Jan 18, 2023
@AndyAyersMS
JIT: fix remaining phases that were rebuilding pred edges (#80769)
7f3f5ef 
Loop canonicalization now maintains pred edges. GC poll insertion was already
maintaining the edges but was rebuilding them anyways.

Now pred lists are never rebuilt.

Also revise `fgUpdateChangedFlowGraph` so that it no longer has the
ability to remove or rebuild.

Fixes #49030.
Also fixes #80772.
@ghost ghost removed the in-pr There is an active PR which will close this issue when it is merged label Jan 18, 2023
mdh1418 pushed a commit to mdh1418/runtime that referenced this issue Jan 24, 2023
@AndyAyersMS @mdh1418
JIT: fix remaining phases that were rebuilding pred edges (dotnet#80769)
416ca81 
Loop canonicalization now maintains pred edges. GC poll insertion was already
maintaining the edges but was rebuilding them anyways.

Now pred lists are never rebuilt.

Also revise `fgUpdateChangedFlowGraph` so that it no longer has the
ability to remove or rebuild.

Fixes dotnet#49030.
Also fixes dotnet#80772.
@ghost ghost locked as resolved and limited conversation to collaborators Feb 18, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@AndyAyersMS AndyAyersMS

Labels
area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI
Projects
.NET Core CodeGen
Archived in project
Milestone
8.0.0
Development

Successfully merging a pull request may close this issue.

JIT: fix remaining phases that were rebuilding pred edges AndyAyersMS/runtime
3 participants
@AndyAyersMS @BruceForstall @JulieLeeMSFT