[llvm-bugs] [Bug 37588] New: DSE slow with many allocas and calls

[via llvm-bugs]

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

            Bug ID: 37588
           Summary: DSE slow with many allocas and calls
           Product: libraries
           Version: 6.0
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: nikita.ppv at gmail.com
                CC: llvm-bugs at lists.llvm.org

Original report for rustc at https://github.com/rust-lang/rust/issues/50994.

DSE for an a function with many allocas and end BB with many calls is very
slow, showing approximately quadratic scaling.

Two test cases extracted from the above issue:

https://gist.githubusercontent.com/nikic/46d6a41e968efabb45d76b3dc5e51589/raw/aadf233e6c145f5179751fa8ef9bfdf4fe466774/main1000.ll

https://gist.githubusercontent.com/nikic/46d6a41e968efabb45d76b3dc5e51589/raw/aadf233e6c145f5179751fa8ef9bfdf4fe466774/main2000.ll

Calling opt -S -dse mainXXXX.ll takes 1.5s for 1000 rust println calls, 6.7s
for 2000 calls and 33s for 4000 calls.

The main issue is this loop:
https://github.com/llvm-mirror/llvm/blob/10826be2a677d7babbc0c0640e94bf75fc808893/lib/Transforms/Scalar/DeadStoreElimination.cpp#L840-L845

It checks each potentially dead stack object (i.e. each alloca in this case)
against each call being made in the end BB, which is quadratic. This is made
worse by getModRefInfo() for an ImmutableCallSite being a quite expensive
operation (due to reliance on PointerMayBeCaptured).

-- 
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/20180525/592a060d/attachment-0001.html>