[llvm-bugs] [Bug 43134] New: Loop unroll by N iterations takes O(N^2) time in domtree updater

[via llvm-bugs]

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

            Bug ID: 43134
           Summary: Loop unroll by N iterations takes O(N^2) time in
                    domtree updater
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: efriedma at quicinc.com
                CC: alina.sbirlea at gmail.com, brzycki at gmail.com,
                    kubakuderski at gmail.com, llvm-bugs at lists.llvm.org

Testcase:

unsigned x() {
  unsigned z = 3;
  unsigned LIMIT = 16000;
  _Pragma("unroll(16384)") for (int i = 0; i < LIMIT; ++i)
    z *= z;
  return z;
}

The compile times look roughly like the following, with "clang -O2 -mllvm
-unroll-threshold=999999":

LIMIT=1000: 0.3s
LIMIT=2000: 1.0s
LIMIT=4000: 3.6s
LIMIT=8000: 14.3s
LIMIT=16000: 57.8s

This is obviously non-linear; I think it's roughly quadratic.  -ftime-report
says the time is spent in unrolling.  I "profiled" in a debugger, and it looks
like the time is spent updating the domtree.

Without the "-unroll-threshold", LLVM refuses to unroll the loop 16000 times,
but it will unroll 8000 times.

-- 
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/20190828/805c5769/attachment.html>