<html>
<head>
<base href="https://llvm.org/bugs/" />
</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 --- - Loop rotate is breaking SCEV when ran before induction variable substitution"
href="https://llvm.org/bugs/show_bug.cgi?id=25005">25005</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Loop rotate is breaking SCEV when ran before induction variable substitution
</td>
</tr>
<tr>
<th>Product</th>
<td>new-bugs
</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>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>new bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>mehdi.amini@apple.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=14963" name="attach_14963" title="Sample C++">attachment 14963</a> <a href="attachment.cgi?id=14963&action=edit" title="Sample C++">[details]</a></span>
Sample C++
Playing with the LTO pipeline, I obtained at some point a 4000 times speedup on
SingleSource/Benchmarks/Shootout/nestedloop.c (basically the loop is fully
eliminated).
A quick hack to run loop-rotate after indvars (or vice-versa) showed that there
is potential for improvement in multiple SPEC benchmarks as well.
Taking as a basic example this loop nest:
for i=0; i<n; ++i
for j=0; i<m; ++j
++result
Here is what's going on if I understand correctly:
Loop rotation will turn:
while(j < m) {
++result
}
into:
if (m > 0) {
do {
++result
} while (j < m)
}
Induction variable simplication is able to do:
if (m > 0) {
do {
// nothing important
} while (j < m)
result += m;
}
The problem is that from the point of view of the enclosing loop it will be:
do {
if (m > 0) {
do {
// nothing important
} while (j < m)
result += m;
}
// result = result + max(0, m) <--- SCEV can't figure this out
} while (i < n)
There is a test in the body of the enclosing loop, SCEV doesn't know how to
join the result value at the exit of the test.
We would want SCEV to figure out that the join after the branch is possible
with a "max" as shown in the comment above in the code snippet.</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>