Add support for cloning loops with <= conditions
#60148
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
ghost
added
the
area-CodeGen-coreclr
|
Tagging subscribers to this area: @JulieLeeMSFT Issue DetailsLoop cloning currently only handles loops using There are perf wins and losses, with the usual existing issues for loop cloning.
Even so, there is one fewer bounds check than the baseline. We could remove one more,
|
Contributor
Author
|
Diffs are a code size regression, because loop cloning kicks in more, which is code expanding. benchmarks.run.windows.x64.checked.mch:Detail diffscoreclr_tests.pmi.windows.x64.checked.mch:Detail diffslibraries.crossgen2.windows.x64.checked.mch:Detail diffslibraries.pmi.windows.x64.checked.mch:Detail diffslibraries_tests.pmi.windows.x64.checked.mch:Detail diffs |
Contributor
Author
|
Note: I did touch the multi-dimensional code path, to make it more like the jagged array path, but multi-dimensional arrays are not supported in loop cloning, so that code isn't currently used. |
Contributor
Author
|
/azp run runtime-coreclr outerloop |
|
Azure Pipelines successfully started running 1 pipeline(s). |
Contributor
Author
|
@AndyAyersMS @dotnet/jit-contrib PTAL |
AndyAyersMS
approved these changes
Oct 7, 2021
Member
AndyAyersMS
left a comment
AndyAyersMS
left a comment
There was a problem hiding this comment.
LGTM.
Do we have good "negative" tests for cloning -- ones where the fast path conditions are almost but not quite satisfied?
Contributor
Author
I don't think so. In fact, I'm not sure we have tests where none of the conditions succeed (versus some subset). It's something that should be added. |
src/coreclr/jit/loopcloning.cpp
Outdated
Member
There was a problem hiding this comment.
Do you think some of the other common cases might be this simple? For example limit <= (arrLen - cns) or reverse loops: for (int i = arrLen - 1; i >= 0; i--), or native integer as the tpye for (nuint i = (nuint)(arrLen - 1); i != nuint.MaxValue; i--), etc
Not asking they be handled in this PR or anything; just wondering if they might be "low hanging fruit".
Contributor
Author
There was a problem hiding this comment.
I doubt that other cases would be this simple. However, "count down" loops have been mentioned before as something to consider, and there are plenty of other generalizations that we could look into. This particular generalization came up because I saw it in some benchmarks I was investigating, so I knew there was code out there that would benefit.
Member
There was a problem hiding this comment.
Thanks. I know we have a couple places in the BCL where we are using ref arithmetic, Unsafe, and other tricks to workaround the other scenarios not working
So supporting them, while not a priority, would allow us to simplify some core perf-critical code and make it more readable/maintainable.
Contributor
interested in reading about the rationale on why is it a good change despite the 78.57% regression in top case? |
Contributor
Author
It's a code size regression, not necessarily a run-time regression. Loop cloning literally duplicates the body of a loop, making a "fast path" with fewer bounds checks, and a "slow path" with all the bounds checks. In the best case, the "loop choice conditions" are quick, the "fast path loop" is entered, and the missing bounds checks makes the loop run faster. |
jakobbotsch
approved these changes
Oct 8, 2021
Loop cloning currently only handles loops using `<` limit comparison, e.g., in loops like `for (i = c; i < n; i++)`. This change allows for loop cloning for loops using `<=`. This happens frequently in the BenchF benchmarks (which maybe had their origin long ago in 1-based array Fortran code?), and some in the BenchI benchmarks. In real world code, it happens in Visual Basic code. There are perf wins and losses, with the usual existing issues for loop cloning. For one case, BenchI.XPosMatrix, I see a loss due to various things, including: 1. Unfortunate register allocation and/or missing copy prop, leading to lots of unnecessary copies. 2. Hitting jcc erratum 3. CSE leads to un-contained array length load in array bounds check Even so, there is one fewer bounds check than the baseline. We could remove one more, but a limitation in recognizing multi-dimensional jagged array components prevents loop cloning from recognizing a legal-to-remove bounds check (dotnet#54074).
This change activated existing unused code that statically determined
a loop choice condition was false, leading to aborting the loop
cloning (and at runtime to an almost certain exception). (The test
case was `for (i = 1; i <= a.Length; i++) { a[i] = 1; }`)
If any choice condition is false, we shouldn't also check if all conditions
are true (that value is unreliable in this case).
There are no SPMI asm diffs from this change.
BruceForstall
force-pushed
the
SupportCloningLessEqualLoops
branch
from
cda27b2 to
f046668
Compare
Contributor
Author
|
/azp run runtime-coreclr outerloop, runtime-coreclr jitstress |
|
Azure Pipelines successfully started running 2 pipeline(s). |
Contributor
|
arm64 improvements - |
Contributor
|
@DrewScoggins - I am wondering why this one was not flagged by auto filer? |
Contributor
|
x64 regressions |
ghost
locked as resolved and limited conversation to collaborators
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
6 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Loop cloning currently only handles loops using
<limit comparison,e.g., in loops like
for (i = c; i < n; i++). This change allowsfor loop cloning for loops using
<=. This happens frequently in the BenchFbenchmarks (which maybe had their origin long ago in 1-based array Fortran code?),
and some in the BenchI benchmarks. In real world code, it happens
in Visual Basic code.
There are perf wins and losses, with the usual existing issues for loop cloning.
For one case, BenchI.XPosMatrix, I see a loss due to various things, including:
unnecessary copies.
Even so, there is one fewer bounds check than the baseline. We could remove one more,
but a limitation in recognizing multi-dimensional jagged array components prevents loop
cloning from recognizing a legal-to-remove bounds check (#54074).