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

• [x] (Q4 '23) https://github.com/dotnet/runtime/issues/43713 Describes two cases where loops are missed due to various issues.
  • [x] https://github.com/dotnet/runtime/issues/58941 F# loops not recognized

Loop cloning

• [x] https://github.com/dotnet/runtime/issues/62615 Consider rebuilding loop table after loop cloning

Induction variables

• [X] https://github.com/dotnet/runtime/issues/7312 RyuJIT: Index Variable Widening optimization for array accesses
• [X] https://github.com/dotnet/runtime/issues/93143 RyuJIT: Implement induction variable analysis
• [x] (Q2'24) https://github.com/dotnet/runtime/issues/100913 JIT: Add support for strength reduction
  • [x] https://github.com/dotnet/runtime/pull/104243
  • [x] https://github.com/dotnet/runtime/pull/104679
  • [x] https://github.com/dotnet/runtime/pull/104687
  • [x] https://github.com/dotnet/runtime/pull/104800
  • [x] https://github.com/dotnet/performance/pull/4317
  • [x] https://github.com/dotnet/runtime/pull/105107
  • [x] https://github.com/dotnet/runtime/pull/105108
  • [x] https://github.com/dotnet/runtime/pull/105131
  • [x] https://github.com/dotnet/runtime/pull/105169

Pushed out of .NET 9

Loop cloning

• [ ] (Q4 '23) https://github.com/dotnet/runtime/issues/82946 Support loop cloning for Span
• [ ] https://github.com/dotnet/runtime/issues/77071 Support loop cloning of class member arrays
• [ ] https://github.com/dotnet/runtime/issues/85552 Support loop cloning with non-int iteration variables

Multi-dimensional array improvements

• [ ] https://github.com/dotnet/runtime/issues/71674 RyuJIT: support cloning loop nests with multi-dimensional array accesses
• [ ] https://github.com/dotnet/runtime/issues/71676 Improve hoisting, CSE, LSRA for MD array accesses

Loop peeling

• [ ] (Stretch) https://github.com/dotnet/runtime/issues/93142 Implement loop peeling

[ghost]

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](https://github.com/dotnet/runtime/issues/65342); this issue will focus on issues we choose to address in .NET 9. # Planned for .NET 9 ## Loop recognition and canonicalization - [ ] 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 ## Loop cloning - [ ] https://github.com/dotnet/runtime/issues/82946 Support loop cloning for Span - [ ] https://github.com/dotnet/runtime/issues/77071 Support loop cloning of class member arrays - [ ] https://github.com/dotnet/runtime/issues/85552 Support loop cloning with non-int iteration variables - [ ] https://github.com/dotnet/runtime/issues/62615 Consider rebuilding loop table after loop cloning ## Multi-dimensional array improvements - [ ] https://github.com/dotnet/runtime/issues/71674 RyuJIT: support cloning loop nests with multi-dimensional array accesses - [ ] https://github.com/dotnet/runtime/issues/71676 Improve hoisting, CSE, LSRA for MD array accesses ## Loop peeling - [ ] https://github.com/dotnet/runtime/issues/93142 Implement loop peeling ## Induction variables - [ ] https://github.com/dotnet/runtime/issues/7312 RyuJIT: Index Variable Widening optimization for array accesses - [ ] https://github.com/dotnet/runtime/issues/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

  • 95251

  • 95299 (remove a dependency on old dominators)

  • 95507

  • 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

  • 95326

  • 95589

  • 95729

  • 95734

  • 95836

  • [x] 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

  • 95854

  • 95809

  • 95925

  • 96454

  • 96477

  • [x] Remove loop cloning quirks

    • 96552

    • 96553

    • 96555

    • 96563

  • 96613

  • 96647

  • 96751

  • 96754

  • 96752

  • 96753

  • 96756

  • 96995

  • 97149

  • 97314

• 96892

• 96927

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