<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 - [CompileTime][ScheduleDAGRRList] Quadratic behavior in popFromQueueImpl"
href="https://bugs.llvm.org/show_bug.cgi?id=41264">41264</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>[CompileTime][ScheduleDAGRRList] Quadratic behavior in popFromQueueImpl
</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>Common Code Generator Code
</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=21688" name="attach_21688" title="Script to trigger quadratic behavior in ScheduleDAGRRList">attachment 21688</a> <a href="attachment.cgi?id=21688&action=edit" title="Script to trigger quadratic behavior in ScheduleDAGRRList">[details]</a></span>
Script to trigger quadratic behavior in ScheduleDAGRRList
We do a linear scan in popFromQueueImpl. For certain inputs, where we have a
large number of available candidates (e.g. large number of stores for bottom up
scheduling), this can have a large impact on compile time.
For an input with 10000 stores, we spend 10 seconds ScheduleDAGRRList because
of that. The attached script can be used to generate such inputs. Note that
currently the compile time is dominated by DAGCombiner, which is tracked by
PR41263</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>