[llvm-bugs] [Bug 31543] New: Exponential expansion in IndVarSimplify/ScalarEvolutionExpander

[via llvm-bugs]

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

            Bug ID: 31543
           Summary: Exponential expansion in
                    IndVarSimplify/ScalarEvolutionExpander
           Product: tools
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: opt
          Assignee: unassignedbugs at nondot.org
          Reporter: jesper.antonsson at ericsson.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

Created attachment 17805
  --> https://llvm.org/bugs/attachment.cgi?id=17805&action=edit
reduced ll file that gives exponential expansion with opt

File size of output file and time taken by opt is an exponential function of a
loop iteration count for the attached file:

 opt -S -O1 -o foo.opt.ll foo.ll

alternatively, if -O1 is expanded and reduced:

 opt -S -instcombine -loop-rotate -licm -instcombine -indvars -o foo.opt.ll
foo.ll

It's IndVarSimplify::rewriteLoopExitValues() that calls ScalarEvolutionExpander
to calculate loop exit value, but the expansion becomes exponential.

If I change the loop iteration count on this line:

 %_tmp12 = icmp slt i16 %_tmp11, 6

The output ll file grows and compilation time lengthens exponentially. Some
sample values:

bound  file size of foo.opt.ll
6      4912
7      8944
8      17088
..
15     2065266

-- 
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/20170105/7b10b921/attachment.html>