[llvm-bugs] [Bug 31098] New: [LV][MemDeps][SCEV] Unable to prove that a dependence-distance is larger than the trip count

[via llvm-bugs]

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>