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: unassignedb...@nondot.org
Reporter: nikita....@gmail.com
CC: llvm-bugs@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._______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
