[llvm-bugs] [Bug 42987] New: Excessive loop unrolling

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=42987

            Bug ID: 42987
           Summary: Excessive loop unrolling
           Product: clang
           Version: 6.0
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: C++
          Assignee: unassignedclangbugs at nondot.org
          Reporter: agner at agner.org
                CC: blitzrakete at gmail.com, dgregor at apple.com,
                    erik.pilkington at gmail.com, llvm-bugs at lists.llvm.org,
                    richard-llvm at metafoo.co.uk

I think we need to re-evaluate the advantages and disadvantages of loop
unrolling.

Clang is often unrolling loops excessively in cases where there is no advantage
in unrolling.

Loop unrolling is advantageous when the loop overhead is costly or when
expressions or branches that depend on the loop counter can be simplified. But
loop unrolling gives no advantage when the bottleneck lies elsewhere.

The limiting factor is likely to be the floating point/vector unit in the CPU
if a loop contains floating point or vector code. The loop overhead is often
reduced to an integer addition and a fused compare/branch instruction. 
The integer unit has plenty of resources to run the loop overhead
simultaneously with the floating point or vector code at zero extra cost.

The situation is no better if the instruction decoder is the bottleneck, which
is quite often the case. A tiny loop will fit into the micro-op cache or
loopback buffer of modern CPUs so that the loop will run on decoded
instructions only. A large unrolled loop is unlikely to fit into these buffers,
which means that the unrolled loop is slower.

Even if the unrolled loop is not slower when measured in isolation, it can slow
down other parts of the program because it consumes excessive amounts of code
cache.


A simple example:

const int size = 58;
double a[size], b[size], c[size];

void test () {
    for (int i = 0; i < size; i++) {
        a[i] = b[i] + c[i];    
    }
}

clang -O2 -m64 will unroll this loop completely up to size = 59

clang -O3 -m64 will unroll this loop completely up to size = 119

Clang is vectorizing the loop, which is a good thing, but there is no advantage
in unrolling further.

Literature: I have described the loopback buffer, micro-op cache, and other
details of different CPUs in the manual "The microarchitecture of Intel, AMD
and VIA CPUs" https://www.agner.org/optimize/microarchitecture.pdf

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190813/cbe7e7a5/attachment.html>