[LLVMbugs] [Bug 20058] New: High loop unroll counts can result in long compile times

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=20058

            Bug ID: 20058
           Summary: High loop unroll counts can result in long compile
                    times
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: meheff at google.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Compilation can take a long time with high loop counts and is looks to be
quadratic with loop count.  The addition of loop unroll pragmas
(http://reviews.llvm.org/D4147, not yet submitted) will make it more likely
that users will encounter this bad behavior.

Attached is the IR from the following simple C code:

void loop(int *a)
{
  for (int i = 0; i < 1000000; i++) {
    a[i]++;
  }
}

I measured ~2s to unroll this loop 16K times with release build at head, ~10s
to unroll roll it 32K times, and ~50s for 64K, so it appears to be growing (at
least) quadratically.  Profiling suggests time is being taken in somewhere
beneath llvm::UnrollLoop -> FoldBlockIntoPredecessor ->
llvm::ScalarEvolution::forgetLoop.

Run:
opt loop.ll -loop-rotate -loop-unroll -unroll-count 16000 -unroll-allow-partial
-unroll-threshold=10000000

-- 
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/20140616/5afc1866/attachment.html>