<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - DSE slow with many allocas and calls"
href="https://bugs.llvm.org/show_bug.cgi?id=37588">37588</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>DSE slow with many allocas and calls
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>6.0
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Scalar Optimizations
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>nikita.ppv@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>Original report for rustc at <a href="https://github.com/rust-lang/rust/issues/50994">https://github.com/rust-lang/rust/issues/50994</a>.
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:
<a href="https://gist.githubusercontent.com/nikic/46d6a41e968efabb45d76b3dc5e51589/raw/aadf233e6c145f5179751fa8ef9bfdf4fe466774/main1000.ll">https://gist.githubusercontent.com/nikic/46d6a41e968efabb45d76b3dc5e51589/raw/aadf233e6c145f5179751fa8ef9bfdf4fe466774/main1000.ll</a>
<a href="https://gist.githubusercontent.com/nikic/46d6a41e968efabb45d76b3dc5e51589/raw/aadf233e6c145f5179751fa8ef9bfdf4fe466774/main2000.ll">https://gist.githubusercontent.com/nikic/46d6a41e968efabb45d76b3dc5e51589/raw/aadf233e6c145f5179751fa8ef9bfdf4fe466774/main2000.ll</a>
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:
<a href="https://github.com/llvm-mirror/llvm/blob/10826be2a677d7babbc0c0640e94bf75fc808893/lib/Transforms/Scalar/DeadStoreElimination.cpp#L840-L845">https://github.com/llvm-mirror/llvm/blob/10826be2a677d7babbc0c0640e94bf75fc808893/lib/Transforms/Scalar/DeadStoreElimination.cpp#L840-L845</a>
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).</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>