[llvm-bugs] [Bug 31098] New: [LV][MemDeps][SCEV] Unable to prove that a dependence-distance is larger than the trip count
via llvm-bugs
llvm-bugs at lists.llvm.org
Mon Nov 21 09:30:39 PST 2016
https://llvm.org/bugs/show_bug.cgi?id=31098
Bug ID: 31098
Summary: [LV][MemDeps][SCEV] Unable to prove that a
dependence-distance is larger than the trip count
Product: tools
Version: trunk
Hardware: PC
OS: Windows NT
Status: NEW
Severity: normal
Priority: P
Component: opt
Assignee: unassignedbugs at nondot.org
Reporter: dorit.nuzman at intel.com
CC: llvm-bugs at lists.llvm.org
Classification: Unclassified
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
--
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20161121/f4f8db30/attachment.html>
More information about the llvm-bugs
mailing list