<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 - quadratic compile time in -instsimplify"
href="https://bugs.llvm.org/show_bug.cgi?id=42771">42771</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>quadratic compile time in -instsimplify
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</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>jay.foad@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=22292" name="attach_22292" title="test case">attachment 22292</a> <a href="attachment.cgi?id=22292&action=edit" title="test case">[details]</a></span>
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 (<a href="https://reviews.llvm.org/rL207302">https://reviews.llvm.org/rL207302</a>) 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</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>