<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 - [DAGCombiner] Large TokenFactors cause large amount of compile-time spent in CombineTo"
href="https://bugs.llvm.org/show_bug.cgi?id=41174">41174</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>[DAGCombiner] Large TokenFactors cause large amount of compile-time spent in CombineTo
</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>All
</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>Core LLVM classes
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>florian_hahn@apple.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=21637" name="attach_21637" title="Script to generate LL files to stress DAGCombiner's CombineTo">attachment 21637</a> <a href="attachment.cgi?id=21637&action=edit" title="Script to generate LL files to stress DAGCombiner's CombineTo">[details]</a></span>
Script to generate LL files to stress DAGCombiner's CombineTo
For inputs where DAGombiner creates large TokenFactors (e.g. large number of
loads/stores), CombineTo is very expensive. After combining a set of stores, we
have to remove them from the containing TokenFactor and recompute the
FoldingSetID, which requires iterating over all operands. About half of time
time in DAGCombiner is spent in CombineTo.
The attached generate_ll_combineto.py generates a sequence of sequential
stores, which can all be combined and it illustrates the increase in compile
time. Note that the script generates the worst-case scenario.
for i in `seq 5000 5000 40000`; do echo "=== $i === "; python
generate_ll_combineto.py $i | time bin/llc -O3 -o /dev/null; done
=== 5000 ===
bin/llc -o /dev/null 0.35s user 0.02s system 94% cpu 0.391 total
=== 10000 ===
bin/llc -o /dev/null 1.74s user 0.03s system 98% cpu 1.798 total
=== 15000 ===
bin/llc -o /dev/null 4.93s user 0.91s system 99% cpu 5.874 total
=== 20000 ===
bin/llc -o /dev/null 8.37s user 1.54s system 99% cpu 9.944 total
=== 25000 ===
bin/llc -o /dev/null 12.57s user 2.46s system 99% cpu 15.064 total
=== 30000 ===
bin/llc -o /dev/null 17.80s user 3.43s system 99% cpu 21.273 total
=== 35000 ===
bin/llc -o /dev/null 23.89s user 4.59s system 99% cpu 28.526 total
=== 40000 ===
bin/llc -o /dev/null 31.71s user 5.61s system 99% cpu 37.368 total</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>