<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 - MachineScheduler/PostRAScheduler have quadratic compile time complexity"
href="https://bugs.llvm.org/show_bug.cgi?id=50584">50584</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>MachineScheduler/PostRAScheduler have quadratic compile time complexity
</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>Common Code Generator Code
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>lebedev.ri@gmail.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>A continuation of <a class="bz_bug_link
bz_status_RESOLVED bz_closed"
title="RESOLVED FIXED - SCEV/IndVars has quadratic compile time complexity"
href="show_bug.cgi?id=50384">https://bugs.llvm.org/show_bug.cgi?id=50384</a>
Relevant tests:
<a href="https://www.dropbox.com/s/3awj7pibbag1du6/test-512.ll?dl=0">https://www.dropbox.com/s/3awj7pibbag1du6/test-512.ll?dl=0</a>
<a href="https://www.dropbox.com/s/el1f3awkfzxv8qz/test-1024.ll?dl=0">https://www.dropbox.com/s/el1f3awkfzxv8qz/test-1024.ll?dl=0</a>
where n is is LoopMicroOpBufferSize in X86ScheduleZnver3.td
(aka the desired unrolled loop size)
$ time ./bin/llc -time-passes -o /dev/null ../test-512.ll
===-------------------------------------------------------------------------===
... Pass execution timing report ...
===-------------------------------------------------------------------------===
Total Execution Time: 11.5713 seconds (11.5714 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- ---
Name ---
4.7281 ( 41.6%) 0.0011 ( 0.6%) 4.7292 ( 40.9%) 4.7294 ( 40.9%) Post
RA top-down list latency scheduler
3.1045 ( 27.3%) 0.0000 ( 0.0%) 3.1045 ( 26.8%) 3.1046 ( 26.8%)
Machine Instruction Scheduler
<...>
$ time ./bin/llc -time-passes -o /dev/null ../test-1024.ll
===-------------------------------------------------------------------------===
... Pass execution timing report ...
===-------------------------------------------------------------------------===
Total Execution Time: 60.8318 seconds (60.8329 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- ---
Name ---
31.6539 ( 52.3%) 0.0030 ( 0.9%) 31.6570 ( 52.0%) 31.6576 ( 52.0%) Post
RA top-down list latency scheduler
21.5208 ( 35.6%) 0.0080 ( 2.3%) 21.5288 ( 35.4%) 21.5294 ( 35.4%)
Machine Instruction Scheduler
<...>
So doubling the amount of unrolling (and thus doubling the IR size),
results in 6x increase in compile time, for those parameters.</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>