JIT optimization: loop unrolling

[JosephTremoulet]

(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

[JosephTremoulet]

This is also an important source of code quality disparity vs Jit64 in BenchI-MulMtx and BenchI-IniArray

[AndyAyersMS]

See also #4248

[ArtBlnd]

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?

[AndyAyersMS]

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

[ArtBlnd]

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-L3639

Thanks :>

[AndyAyersMS]

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 statement
• LPFLG_DO_WHILE -- loop must be bottom tested
• LPFLG_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.

[ArtBlnd]

Thanks :> Its helped a lot. I will try to fix it ASAP

[ArtBlnd]

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.

[ArtBlnd]

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 :>

[mikedn]

does vectorizing processes after loop optimizing?

The JIT does not do autovectorization.

[ArtBlnd]

Thanks @mikedn, is there any auto-vectorization plan exists?

[mikedn]

is there any auto-vectorization plan exists?

None that I've heard of.

[ArtBlnd]

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.

[mikedn]

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 LoopDsc and LoopSearch classes, 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

[ArtBlnd]

Can I ask what ASG gt node does? there is no comments on gtlist.h
btw, almost done!! stay turned!! :>