Repository navigation
JIT optimization: loop unrolling #8107
Description
Activity
This is also an important source of code quality disparity vs Jit64 in
BenchI-MulMtxandBenchI-IniArraySee also #4248
I have some question
does it means current ryuJIT doesn't perform unrolling, rerolling loop for loop caching?
only specalized for full-unrolling, simd-vectorizing?Thanks.
[ADDED] Can I get some testcases that should be unrolled?
Yes, that's basically what it means. Logic for determining which loops to unroll is in optUnrollLoops(). Current heuristic is that the loop bounds test must be a SIMD element count.
An example where unrolling kicks in: SeekUnroll.cs
I meant can I have that should be unrolled and shouldn't be unrolled?
because the coreclr optimization theory is kinda different from LLVM, I saw some docs on this. and it seems DOES NOT optimizes non-natural loops. thats why I need case that shouldn't be unrolled.
if the loop doesn't unroll because its predicated as non-natural loop, it should be extended.
I need the bottom line that should be optimized or not.this will may help me to contribute on this.
also, is that SIMD check does with LPFLG_DONT_UNROLL flag which is on here?
https://github.com/dotnet/coreclr/blob/dd089b270c5d4833e615f2a926ea0a82d070e5de/src/jit/optimizer.cpp#L3636-L3639Thanks :>
Broadly speaking most loops should be unrollable. After all, it is a fairly mechanical operation.
In practice there are cases where the JIT can't properly represent the results of unrolling, and those loops are flagged by various critiera, eg:
LPFLG_DONT_UNROLL-- bail if loop was created by loop cloning or has an unclonable statementLPFLG_DO_WHILE-- loop must be bottom testedLPFLG_CONST-- loop iteration count is a known constant- Other bail-out checks done in
optUnrollLoops, for instance, the iteration variable is address exposed or a struct field, or too many returns (this one should probably never be hit anymore since the JIT now moves non-loop blocks out of loops). There are probably more.
A second set of criteria tries to determine when loop unrolling is beneficial. Unrolling is quite likely going to increase code size. So the JIT will try and estimate that size increase and have limits on how much growth it will allow. But the JIT does not have a good model for the benefit of unrolling a loop. To avoid being overly aggressive but still unroll in some cases where there is likely a benefit, it will currently insist the loop iteration count be a SIMD vector length.
If you want to contribute, there are a few broad areas:
- First, find or create a set of examples to use to evaluate the unrolling heuristics. Ideally we would have a good number of cases where unrolling is beneficial and a number of other cases where it is not beneficial.
- In the latter group you should distinguish between cases where unrolling ought to be beneficial but isn't because of other problems in the JIT (and make sure to open issues for those), and cases where unrolling is just going to increase code size with no performance benefit.
- Since you can unroll by hand you can use source level transformations to ballpark the potential benefits from unrolling (again subject to JIT limitations).
- Make sure to also include cases where the JIT can't unroll because of its various internal limitations.
- Second, remove correctness constraints and limitations that block unrolling so more kinds of loops can be unrolled.
- Third, add some realistic benefit heuristics and tune on your test suite plus our benchmarks and realistic applications.
- Fourth, support unrolling in more scenarios:
- high trip count loops (partial unrolls)
- fixed but unknown trip count loops
- search loops
If you're interested in developing better loop unrolling benefit heuristics, you might also look upstream at loop cloning, which also is lacking benefit heuristics (and has a number of other issues too).
It would be ideal if the utilities we develop for evaluating loop performance can be leveraged for other kinds of loop optimizations.
Also at some point, likely not too far into this program, you will discover that other parts of the JIT's loop optimization infrastructure will need upgrades.
Reacted by Junryoung Ju , Lucas Trzesniewski and Abel BraaksmaThanks :> Its helped a lot. I will try to fix it ASAP
I think we have to start with a very simple cases
here is most general case that should be unrolled.int[] arr = { 1, 2, 3, 4 }; int total = 0; for(int i = 0; i < 4; ++i) { total += arr[i]; }the loop backedge-count is constant. also there is realistic banefits on it.
here is current JIT generated assemblies here.
11: int[] val_1 = { 1, 2, 3, 4 }; 00007FFDF2F204B0 sub rsp,28h 00007FFDF2F204B4 vzeroupper 00007FFDF2F204B7 mov rcx,7FFE299931BAh 00007FFDF2F204C1 mov edx,4 00007FFDF2F204C6 call 00007FFE52A24400 00007FFDF2F204CB mov rdx,1B49308280Ch 00007FFDF2F204D5 mov ecx,dword ptr [rax+8] 00007FFDF2F204D8 lea r8,[rax+10h] 00007FFDF2F204DC vmovdqu xmm0,xmmword ptr [rdx] 00007FFDF2F204E1 vmovdqu xmmword ptr [r8],xmm0 12: int total = 0; 00007FFDF2F204E6 xor edx,edx 13: 14: for(int i = 0; i < 4; ++i) 00007FFDF2F204E8 xor r8d,r8d 00007FFDF2F204EB cmp ecx,4 00007FFDF2F204EE jl 00007FFDF2F20502 15: { 16: total += val_1[i]; 00007FFDF2F204F0 movsxd rcx,r8d 00007FFDF2F204F3 add edx,dword ptr [rax+rcx*4+10h] 14: for(int i = 0; i < 4; ++i) 00007FFDF2F204F7 inc r8d 00007FFDF2F204FA cmp r8d,4 00007FFDF2F204FE jl 00007FFDF2F204F0 00007FFDF2F20500 jmp 00007FFDF2F20512 00007FFDF2F20502 movsxd rcx,r8d 00007FFDF2F20505 add edx,dword ptr [rax+rcx*4+10h] 00007FFDF2F20509 inc r8d 00007FFDF2F2050C cmp r8d,4 00007FFDF2F20510 jl 00007FFDF2F20502 17: }loop didn't removed. also DIDN'T unrolled
current progress in.Current progress in for partial loop unrolling.
for(unsigned int i = 0; i < 256; ++i) { total += array[i]; }to
for(unsigned int i = 0; i < 64; ++i) { total += array[i]; total += array[i + 1]; total += array[i + 2]; total += array[i + 3]; }the partial unroll limit threshold is maximum to 64 bytes, normally 32 bytes.
btw, does vectorizing processes after loop optimizing?
Thanks :>does vectorizing processes after loop optimizing?
The JIT does not do autovectorization.
is there any auto-vectorization plan exists?
None that I've heard of.
Can I ask you something? @mikedn
Is IR simpify processes before the loop optimizations? such as this.
int total = 0; for(unsigned int i = 0; i < 4; ++i) { total += 2; total -= 1; }to
int total = 0; for(unsigned int i = 0; i < 4; ++i) { total += 1; }Also, how can I extract loop's body from LoopDsc.
Thanks.
Is IR simpify processes before the loop optimizations?
Some happens during global morph phase that runs before loop optimizations. Some happens after loop optimizations as part of SSA/VN based optimizations. That said, I don't think the JIT simplifies that particular code you have in your example.
Also, how can I extract loop's body from LoopDsc.
See the comments associated with
LoopDscandLoopSearchclasses, most notably the parts about loop body being a contiguous list of BBs, for example:We (currently) require the body of a loop to be a contiguous (in bbNext order) sequence of basic blocks
Can I ask what
ASGgt node does? there is no comments ongtlist.h
btw, almost done!! stay turned!! :>8 remaining items
Have you done any measurements to evaluate the impact of loop unrolling on current hardware?
Yes (In LLVM, I was working on SCEV, loop-deletion), and I've read all of intel optimization manual like a 3 times with a year.
I mean not a real instruction weight. on IL instruction. checking is that effective with partial unrolling is quite hard.Is there are any custom defined ADT (abstract data types) in coreclr? such as list, vector. or should I use std?
cuz I want to make a GenTree list without copying it.[ADDED] nvm, there was jitstd instead of it.
Is there are any way to clone block without changing? thanks :>
What do you mean by "without changing"?
I mean, CloneBlockState does change variant as invariant. I need copy without changing anything.
CloneBlockStatewon't change things unless you pass in the optional arguments.I'm currently working on new loop unrolling implements based on inner unrolled count.
with new unroll count theory. (base is same. but for partial unrolling)
not to implement partial unrolling and full unrolling separately. :>I want to know that every single
noway_assertcheck is needed when its initializing basic loop informations.here is example.
https://github.com/dotnet/coreclr/blob/b2031a14a3b110f8e712abdb0cd392c54cd2e839/src/jit/optimizer.cpp#L3617-L3627almost of all seems duplicated. should I try to remove it?
The SIMD support was also extended from just
Vector<T>.Countto also coverVector64<T>.Count,Vector128<T>.Count, andVector256<T>.Countin dotnet/coreclr#24991.However, that support is really only when using
Countas the upper bound of the loop. It would be beneficial to extend the support to cover simple auto-vectorization (https://github.com/dotnet/coreclr/issues/20486) and to also cover unrolling more complex loops (such as those containing already vectorized code).@tannergooding What kind of complex loops? just for example.
However, that support is really only when using Count as the upper bound of the loop.
That was done as a special case, for code that was trying to access individual vector elements in a loop (and that's likely driven by SIMD API limitations such as the lack of shuffles). It's not clear why do you think that loops having stride
Vector<T>.Countare somewhat special in terms of unrolling compared to other loops or why is this related to auto-vectorization.
(I'm creating tracking issues for some optimizations that RyuJit doesn't perform, so we'll have a place to reference/note when we see the lack of them affecting particular benchmarks)
There's code in the Jit today that goes by the name "loop unrolling", but it's only doing full unrolls, and only for SIMD loops. General loop unrolling (to balance ALU ops vs branching) is not performed by the jit at all today.
category:cq
theme:loop-opt
skill-level:expert
cost:extra-large