[llvm-bugs] [Bug 47746] New: MergeBlockIntoPredecessor in UnrollLoop is very slow for sufficiently complicated loops

[via llvm-bugs]

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

            Bug ID: 47746
           Summary: MergeBlockIntoPredecessor in UnrollLoop is very slow
                    for sufficiently complicated loops
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Transformation Utilities
          Assignee: unassignedbugs at nondot.org
          Reporter: ctetreau at quicinc.com
                CC: llvm-bugs at lists.llvm.org

UnrollLoop in Transforms/Utils/LoopUnroll.cpp calls MergeBlockIntoPredecessor
for each of the latch basic blocks. MergeBlockIntoPredecessor calls
RemoveRedundantDbgInstrs, which iterates over the instructions of the basic
block twice. For sufficiently complicated loops, this can cause extremely long
compile times.

We're seeing > 10 minute compile times on internal codebases. Unfortunately, I
cannot share any code for these cases. Running in a profiler, we're seeing ~98%
of the runtime inside of RemoveRedundantDbgInstrs. 

I believe it might be possible add a flag to MergeBlockIntoPredecessor skip the
call to RemoveRedundantDbgInstrs, then call RemoveRedundantDbgInstrs for each
basic block inside of simplifyLoopAfterUnroll, however I am not familiar enough
with this code to know for certain there will be no unintended consequences. I
experimented with this in my downstream, and it reduced the runtime from 10
minutes to 4 seconds.

-- 
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/20201006/97a24eb9/attachment.html>