<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 - LCSSA (Loop-Closed SSA Form Pass) (and hence LICM) is extremely slow"
href="https://bugs.llvm.org/show_bug.cgi?id=37202">37202</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>LCSSA (Loop-Closed SSA Form Pass) (and hence LICM) is extremely slow
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>All
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</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>sroland@vmware.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=20208" name="attach_20208" title="pathetic nested loop case bitcode">attachment 20208</a> <a href="attachment.cgi?id=20208&action=edit" title="pathetic nested loop case bitcode">[details]</a></span>
pathetic nested loop case bitcode
The loop-closed SSA Form Pass can be extremely slow.
I'm attaching a bitcode which takes roughly ~15 minutes to compile (opt -O2),
and nearly everything (roughly ~96%) of it is spent in (various) lcssa runs.
The bitcode is auto-generated by mesa llvmpipe, and I certainly don't claim the
shader causing it is doing anything useful (mostly the shader was just
consisting of deeply nested loops). We don't actually use all that many passes
in mesa llvmpipe, we're trying basically -sroa -early-cse -simplifycfg -licm
-reassociate -mem2reg -constprop -instcombine -gvn (note the public mesa code
has this a bit different as of now, omitting -early-cse and -licm before
-simplifycfg, but I think this order is better).
But licm comes with a whole bunch of other stuff, lcssa being one of it.
Note that when we last really looked at it, that was with llvm 3.3, and before
llvm 3.5 licm did not imply most of the stuff it does now (just -loops and
-loop-simplify). Our jit compilation is definitely faster than using opt -O2
for this case, with the reason basically being we only run one lcssa pass
instead of 6 (albeit from these 6 only 2 contributed most of the time), but it
still takes ~5 minutes to compile.
Probably licm with llvm 3.3 also didn't do as much as it can now, but it
doesn't seem to be possible to get some passes which can only do roughly what
licm of llvm 3.3 did, otherwise we'd try that. (In general for our jit needs in
llvmpipe, licm seems to be quite expensive, even if the structure of the shader
is a lot more sound than this case here, a pity since in general licm looks
potentially quite useful.)
>From the description, this looks somewhat similar to <a class="bz_bug_link
bz_status_NEW "
title="NEW - Forming and verifying LCSSA can take forever due to updater speed"
href="show_bug.cgi?id=31851">bug 31851</a> to me, but I
tried the bitcode there and from the -time-passes information the time spent
looked a lot more sane - while loop stuff was on the top, not specifically
lcssa, which was only accounting for 3.6%. The bitcode there also has ~16 times
more instructions, and compiles ~6 times faster for me, so the example I
attached is about ~100 times worse.
I've tested this with llvm 5.0, 6.0 and trunk, and it's basically all the same.
Most of the time spent seems to be in various ssa updater functions.</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>