ghost
commented
2 years ago Tagging subscribers to this area: @JulieLeeMSFT See info in area-owners.md if you want to be subscribed.
Issue Details
RyuJIT has several loop optimization phases that have various issues (both correctness and performance) and can be significantly improved. RyuJIT also lacks some loop optimizations that have been shown to benefit various use cases. This meta-issue collects various links to the most important identified issues in one place, so they can be easily seen without searching the entire GitHub issue database. This issue is long-term. Specific issues will be created to identify work that will be included in each release. Specific issues so far: - .NET 6 loop optimization work: https://github.com/dotnet/runtime/issues/43549 - .NET 7 loop optimization work: https://github.com/dotnet/runtime/issues/55235 If an item is implemented, it will be removed from this list (so this issue should only contain continuing loop optimization improvement opportunities). ## Existing Optimizations Below is a list of the existing loop-related RyuJIT phases and a short description of the improvement opportunities. ### Loop Recognition RyuJIT currently has lexical-based loop recognition and only recognizes natural loops. We should consider replacing it with a standard Tarjan SCC algorithm that classifies all loops. Then we can extend some loop optimizations to also work on non-natural loops. Even if we continue to use the current algorithm, we should verify that it catches the maximal set of natural loops; it is believed that it misses some natural loops. - [ ] https://github.com/dotnet/runtime/issues/43713 Describes two cases where loops are missed due to various issues. - [ ] https://github.com/dotnet/runtime/issues/58941 F# loops not recognized ### Multi-dimensional arrays Code generated for multi-dimensional array expressions is sub-optimal, and much worse than for single-dimensional arrays. https://github.com/dotnet/runtime/issues/60785 describes a set of problems and details improvements that should be made. ### Loop Cloning This optimization creates two copies of a loop: one with bounds checks and one without bounds checks and executes one of them at runtime based on some condition. Several issues have been identified with this optimizations. One recurring theme is unnecessary loop cloning where we first clone a loop and then eliminate range checks from both copies. - [ ] https://github.com/dotnet/runtime/issues/65206 - [ ] https://github.com/dotnet/runtime/issues/4929 RyuJIT's loop cloning optimization has questionable CQ - [ ] https://github.com/dotnet/runtime/issues/8558 JIT: examples where loop cloning is not useful - [ ] https://github.com/dotnet/runtime/issues/31831 Poor loop optimization in BilinearInterpol benchmark - [ ] https://github.com/dotnet/runtime/issues/48850 loop cloning and pgo. Remaining: use PGO data to influence cost/benefit analysis of deciding to clone a loop. - [ ] https://github.com/dotnet/runtime/issues/48740#issuecomment-786900421 Poor tracking of return blocks impacts loop cloning - [ ] https://github.com/dotnet/runtime/issues/48897 Support loop cloning with struct arrays - [ ] https://github.com/dotnet/runtime/issues/49102 Consider hoisting of class init checks for loop cloning and inversion ### Loop Unrolling The existing phase only does full unrolls, and only for SIMD loops: current heuristic is that the loop bounds test must be a SIMD element count. The impact of the optimization is currently very limited but in general it's a high-impact optimization with the right heuristics. - [ ] https://github.com/dotnet/runtime/issues/4248 Loop unrolling support in RyuJIT - [ ] https://github.com/dotnet/runtime/issues/8107 JIT optimization: loop unrolling ### Loop Invariant Code Hoisting This phase attempts to hoist code that will produce the same value on each iteration of the loop to the pre-header. There is at least one (and likely more) correctness issue: - [ ] https://github.com/dotnet/runtime/issues/6639 JIT: Loop hoisting re-ordering exceptions And multiple issues about limitations of the algorithm: - [ ] https://github.com/dotnet/runtime/issues/35735 JIT: limitations in hoisting (loop invariant code motion) - [ ] https://github.com/dotnet/runtime/issues/6554 JIT: Loop hoisting inhibited by phase-ordering issue - [ ] https://github.com/dotnet/runtime/issues/7265 RyuJIT: Loop hoist invariant struct field accesses - [ ] https://github.com/dotnet/runtime/issues/6666 RyuJIT: missed opportunity for LICM - [ ] https://github.com/dotnet/runtime/issues/29091#issuecomment-745543816 Indexer.Set of List is much slower than Array ### Loop optimization hygiene Loop optimizations need to work well with the rest of the compiler phases and IR invariants, such as with PGO. - [ ] https://github.com/dotnet/runtime/issues/49030 Loop opts should not be recomputing pred lists from scratch. Remaining phases to fix: optFindNaturalLoops, optUnrollLoops, fgInsertGCPolls. ## Missing Optimizations Several major optimizations are missing even though we have evidence of their effectiveness (at least on microbenchmarks). ### Induction Variable Widening Induction variable widening eliminates unnecessary widening converts from int32 sized induction variables to int64 size address mode register uses. On AMD64, this eliminates unnecessary `movsxd` instructions prior to array dereferencing. - [ ] https://github.com/dotnet/runtime/issues/7312 RyuJIT: Index Variable Widening optimization for array accesses ### Strength Reduction Strength reduction replaces expensive operations with equivalent but less expensive operations. - [ ] https://github.com/dotnet/runtime/issues/34938 Strength reduction for add operations performed power of 2 times - [ ] https://github.com/dotnet/runtime/issues/34810 ARM64: loop array indexing inefficiencies ### Loop Unswitching Loop unswitching moves a conditional from inside a loop to outside of it by duplicating the loop's body, and placing a version of the loop inside each of the `if` and `else` clauses of the conditional. It has elements of both Loop Cloning and Loop Invariant Code Motion. ## Benefits It's easy to show the benefit of improved loop optimizations on microbenchmarks. For example, the team has done analysis of JIT microbenchmarks (benchstones, SciMark, etc.) several years ago. The analysis contains estimates of perf improvement from several of these optimizations (each is low single digit %). Real code is also likely to have hot loops that will benefit from improved loop optimizations. The benchmarks and other metrics we will measure to show the benefits is TBD. category:planning theme:loop-opt skill-level:expert cost:large
| Author: | BruceForstall |
|---|---|
| Assignees: | - |
| Labels: | `area-CodeGen-coreclr` |
| Milestone: | Future |
RyuJIT has several loop optimization phases that have various issues (both correctness and performance) and can be significantly improved. RyuJIT also lacks some loop optimizations that have been shown to benefit various use cases. This meta-issue collects various links to the most important identified issues in one place, so they can be easily seen without searching the entire GitHub issue database. This issue is long-term. Specific issues will be created to identify work that will be included in each release.
Release-specific issues:
If an item is implemented, it will be removed from this list (so this issue should only contain continuing loop optimization improvement opportunities).
Existing Optimizations
Below is a list of the existing loop-related RyuJIT phases and a short description of the improvement opportunities.
Loop Recognition and Canonicalization
RyuJIT currently has lexical-based loop recognition and only recognizes natural loops. We should consider replacing it with a standard Tarjan SCC algorithm that classifies all loops. Then we can extend some loop optimizations to also work on non-natural loops.
Even if we continue to use the current algorithm, we should verify that it catches the maximal set of natural loops; it is believed that it misses some natural loops.
Multi-dimensional arrays
Multi-dimensional (MD) arrays are listed in this loop optimization issue because optimizing MD access is most valuable in the context of loop optimization. The first steps to improvement were implemented with https://github.com/dotnet/runtime/pull/70271. Follow-up work:
Loop Cloning
This optimization creates two copies of a loop: one with bounds checks and one without bounds checks and executes one of them at runtime based on some condition. Several issues have been identified with this optimizations. One recurring theme is unnecessary loop cloning where we first clone a loop and then eliminate range checks from both copies.
Loop Unrolling
The existing loop unrolling phase only does full unrolls, and only for SIMD loops: current heuristic is that the loop bounds test must be a SIMD element count. The impact of the optimization is currently very limited but in general it's a high-impact optimization with the right heuristics.
Loop Invariant Code Hoisting
This phase attempts to hoist code that will produce the same value on each iteration of the loop to the pre-header. There is at least one (and likely more) correctness issue:
And multiple issues about limitations of the algorithm:
Missing Optimizations
Several major optimizations are missing even though we have evidence of their effectiveness (at least on microbenchmarks).
Induction Variable Widening
Induction variable widening eliminates unnecessary widening converts from int32 sized induction variables to int64 size address mode register uses. On AMD64, this eliminates unnecessary
movsxdinstructions prior to array dereferencing. It is expected that better induction variable analysis would also allow for better arm64 post-increment addressing mode usage.Loop Unswitching
Loop unswitching moves a conditional from inside a loop to outside of it by duplicating the loop's body, and placing a version of the loop inside each of the
ifandelseclauses of the conditional. It has elements of both Loop Cloning and Loop Invariant Code Motion.Benefits
It's easy to show the benefit of improved loop optimizations on microbenchmarks. For example, the team has done analysis of JIT microbenchmarks (benchstones, SciMark, etc.) several years ago. The analysis contains estimates of perf improvement from several of these optimizations (each is low single digit %). Real code is also likely to have hot loops that will benefit from improved loop optimizations.
The benchmarks and other metrics we will measure to show the benefits is TBD.
category:planning theme:loop-opt skill-level:expert cost:large impact:medium