[llvm-bugs] [Bug 42771] New: quadratic compile time in -instsimplify

[via llvm-bugs]

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

            Bug ID: 42771
           Summary: quadratic compile time in -instsimplify
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: jay.foad at gmail.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 22292
  --> https://bugs.llvm.org/attachment.cgi?id=22292&action=edit
test case

With the attached test case I get:

$ time ~/llvm-release/bin/opt -instsimplify stripped.ll -o /dev/null

real    0m0.849s
user    0m0.840s
sys     0m0.008s

This is a long time for running -instsimplify on about 8000 instructions! The
reason is that r207302 (https://reviews.llvm.org/rL207302) introduced this code
in instsimplifys' runImpl():

​              // RecursivelyDeleteTriviallyDeadInstruction can remove
​              // more than one instruction, so simply incrementing the
​              // iterator does not work. When instructions get deleted
​              // re-iterate instead.
​              BI = BB->begin(); BE = BB->end();

which causes the iteration over instructions in a basic block to take quadratic
time. On my test case, simply removing this line gives a ~30x speed-up:

$ time ~/llvm-release/bin/opt -instsimplify stripped.ll -o /dev/null

real    0m0.030s
user    0m0.025s
sys     0m0.004s

-- 
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/20190726/45764681/attachment-0001.html>