Improve JIT loop optimizations (.NET 9)

[BruceForstall]

We plan to continue improving JIT optimization capabilities for loop code. An overview of many JIT optimization possibilities is here; this issue will focus on issues we choose to address in .NET 9.

Planned for .NET 9

Loop recognition and canonicalization

• (Q4 '23) Certain loops do not get recorded in optLoopTable #43713 Describes two cases where loops are missed due to various issues.
  • [JIT] Asm difference for F# and C# methods #58941 F# loops not recognized

Loop cloning

• Consider rebuilding loop table after loop cloning #62615 Consider rebuilding loop table after loop cloning

Induction variables

• RyuJIT: Index Variable Widening optimization for array accesses #7312 RyuJIT: Index Variable Widening optimization for array accesses
• RyuJIT: Implement induction variable analysis #93143 RyuJIT: Implement induction variable analysis
• (Q2'24) JIT: Add support for strength reduction #100913 JIT: Add support for strength reduction
  • JIT: Add a disabled-by-default implementation of strength reduction #104243
  • JIT: Prove some cases where strength reducing to GC pointers is ok #104679
  • JIT: Refine post-dominance check in strength reduction #104687
  • JIT: Improve strength reduction's prediction of loop reversal #104800
  • Add strength reduction benchmarks performance#4317
  • JIT: Add a pass to remove unused primary IVs #105107
  • JIT: Improve and fix StaysWithinManagedObject #105108
  • JIT: Enable strength reduction by default #105131
  • JIT: Switch StaysWithinManagedObject to peel offsets from VNs #105169

Pushed out of .NET 9

Loop cloning

• (Q4 '23) Loops aren't cloned for Spans #82946 Support loop cloning for Span
• Support loop cloning of class member arrays #77071 Support loop cloning of class member arrays
• Support loop cloning with non-int iteration variables #85552 Support loop cloning with non-int iteration variables

Multi-dimensional array improvements

• RyuJIT: support cloning loop nests with multi-dimensional array accesses #71674 RyuJIT: support cloning loop nests with multi-dimensional array accesses
• Improve hoisting, CSE, LSRA for MD array accesses #71676 Improve hoisting, CSE, LSRA for MD array accesses

Loop peeling

• (Stretch) Implement loop peeling #93142 Implement loop peeling

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch
See info in area-owners.md if you want to be subscribed.

Issue Details

---

We plan to continue improving JIT optimization capabilities for loop code. An overview of many JIT optimization possibilities is here; this issue will focus on issues we choose to address in .NET 9.

Planned for .NET 9

Loop recognition and canonicalization

• Certain loops do not get recorded in optLoopTable #43713 Describes two cases where loops are missed due to various issues.
  • [JIT] Asm difference for F# and C# methods #58941 F# loops not recognized

Loop cloning

• Loops aren't cloned for Spans #82946 Support loop cloning for Span
• Support loop cloning of class member arrays #77071 Support loop cloning of class member arrays
• Support loop cloning with non-int iteration variables #85552 Support loop cloning with non-int iteration variables
• Consider rebuilding loop table after loop cloning #62615 Consider rebuilding loop table after loop cloning

Multi-dimensional array improvements

• RyuJIT: support cloning loop nests with multi-dimensional array accesses #71674 RyuJIT: support cloning loop nests with multi-dimensional array accesses
• Improve hoisting, CSE, LSRA for MD array accesses #71676 Improve hoisting, CSE, LSRA for MD array accesses

Loop peeling

• Implement loop peeling #93142 Implement loop peeling

Induction variables

• RyuJIT: Index Variable Widening optimization for array accesses #7312 RyuJIT: Index Variable Widening optimization for array accesses
• RyuJIT: Implement induction variable analysis #93143 RyuJIT: Implement induction variable analysis

Author:	BruceForstall
Assignees:	-
Labels:	area-CodeGen-coreclr, User Story
Milestone:	9.0.0

[jakobbotsch]

With recent work we are close to having moved from the old lexical representation of loops to a more general graph-based one. Since I'll be out until New Year's, here's a more detailed list of work done and expected future work.

• Remove duplicated dominator and DFS implementations
  • JIT: Factor SSA's DFS and profile synthesis's loop finding #95251
  • JIT: Generalize check for full interruptibility #95299 (remove a dependency on old dominators)
  • JIT: Factor SSA's dominator tree computation #95507
  • JIT: Switch morph DFS to use general DFS #95726
  • Currently the old dominators are still used by optSetBlockWeights and by optFindAndScaleGeneralLoopBlocks, but should be switchable to the new dominator implementation relatively easily.
  • optFindAndScaleGeneralLoopBlocks also depends on dense reachability sets; in common cases (where the flow graph does not have irreducible loops) we may be able to replace them by loop containment checks. Eventually we'd like all of this to be replaced by profile synthesis.
• Port old loop-based optimizations to new representation
  • JIT: Port loop cloning to the new loop representation #95326
  • JIT: Port VN and loop hoisting to new loop representation #95589
  • JIT: Remove loop-related VN quirks #95729
  • JIT: Remove most loop-related hoisting quirks #95734
  • JIT: Port loop alignment to new loop representation #95836
  • Loop unrolling
    • This turns out to be hard if we also have to maintain the old loop table, so I am removing dependencies on the old loop table first; see below
• Switch loop optimizations to run on newly recognized loops
  • Remove remaining dependencies on old loop table to avoid maintaining it
    • JIT: Invalidate loop table after unrolling and dominators after MarkLocalVars #95854
    • JIT: Reuse (new) loop-finding DFS tree in SSA #95809
    • JIT: Compute new dominators earlier and invalidate old dominators #95925
    • JIT: Port loop unrolling to new loop representation #96454
    • JIT: Remove loop unrolling quirks #96477
    • Remove loop cloning quirks
      • JIT: Remove some small loop cloning quirks #96552
      • JIT: Remove unnecessary lexical preconditions in loop cloning #96553
      • JIT: Remove BBJ_RETURN loop cloning quirk #96555
      • JIT: Remove IV analysis quirk in loop cloning #96563
    • JIT: Invalidate old loop table immediately #96613
  • JIT: Create preheaders on new loops and delete old loop canonicalization #96647
  • JIT: Canonicalize newly recognized loops #96751
  • JIT: Clone newly recognized loops #96754
  • JIT: Unroll newly recognized loops #96752
  • JIT: Hoist in newly recognized loops #96753
  • JIT: Align newly recognized loops #96756
  • JIT: Port loop compaction to new loop representation #96995
  • JIT: Compact newly recognized loops #97149
  • JIT: Remove some loop flags #97314
• JIT: Factor reachability sets and base them on new DFS #96892
• JIT: Delete old DFS and dominator implementations #96927
• JIT: Remove old loop code #97232

Some stats from the loop representation switch over some of our win-x64 collections:

• 25.1% more hoisting in benchmarks.run_pgo, 5.7% more hoisting in realworld, 35.8% more hoisting in libraries_tests.run
• 7.3% more cloned loops in benchmarks.run_pgo, 6.8% more cloned loops in realworld, 6.7% more cloned loops in libraries_tests.run
• 5.0% (~700) more aligned loops aggregated over the collections

[JulieLeeMSFT]

.NET9 work is complete. Closing.

[JulieLeeMSFT]

Will move the pushed-out items to .NET 10 user story during .NET 10 planning.