<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 --- - [LV][MemDeps][SCEV] Unable to prove that a dependence-distance is larger than the trip count"
href="https://llvm.org/bugs/show_bug.cgi?id=31098">31098</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>[LV][MemDeps][SCEV] Unable to prove that a dependence-distance is larger than the trip count
</td>
</tr>
<tr>
<th>Product</th>
<td>tools
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Windows NT
</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>opt
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>dorit.nuzman@intel.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>Consider the following example:
#include <stdlib.h>
class Complex {
private:
float real_;
float imaginary_;
…
};
void test(Complex *out, size_t size) {
size_t D = size / 2;
for (size_t offset = 0; offset < D; ++ offset)
{
… = out[offset];
… = out[offset + D];
out[offset] = …;
out[offset + D] = …;
}
}
In the above example, memory-dependence analysis fails to prove that an unknown
dependence distance 2*D (+/- 1) is larger than the loop trip count D. This is
because proving this property requires a bit of extra information, information
that the loop-vectorizer has: The vectorizer knows that if execution will enter
the vectorized loop then it must hold that the original trip-count is at least
equal to the selected Vectorization Factor (VF). Otherwise, either only the
scalar peel loop will get executed, or we skip both the vector and remainder
loops altogether. While we don’t know during legality analysis what the
selected VF will end up being, we do know that if the loop is vectorized it
will be at least 2. Just using this bit of information can help us resolve
things in the example in question:
- In the example the dependence-distances (dd) in bytes are:
8*D , 8*D + 4, and 8*D - 4;
The size of the elements is 4 bytes;
The loop backEdgeTakenCount is D-1;
In Dependence analysis we are trying to prove that:
abs(dd) > takenCount * 4:
So in our case we are trying to see if:
abs(8*D – 4) > 4D – 4
abs(8*D) > 4D – 4
abs(8*D + 4) > 4D – 4
Without further information on D we can’t prove the above;
We can’t even prove that dd isKnownNonNegative (to compute the abs).
- Knowing that the loopCount >= VF (as explained above), and assuming
conservatively a VF=2, gives us that:
D >= 2. With that we can prove everything we need.
So in summary, when we get an unknown distance, we don’t have to resort to
runtime tests, we can retry the prove the SCEV equations by providing a bit of
context to the SCEV tools. (Just need to figure out what's the best way to do
that...).
Thanks,
Dorit</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>