[LAA] Check independence of strided accesses before forward case

This patch changes the order in which we attempt to prove the independence of
strided accesses. We previously did this after we knew the dependence distance
was positive. With this change, we check for independence before handling the
negative distance case. The patch prevents LAA from reporting forward
dependences for independent strided accesses.

This change was requested in the review of D19984.

llvm-svn: 270072

2 files changed, 56 insertions, 10 deletions

diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 9193e38b573..895c47e759f 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -1212,8 +1212,18 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
   unsigned TypeByteSize = DL.getTypeAllocSize(ATy);
 
-  // Negative distances are not plausible dependencies.
   const APInt &Val = C->getAPInt();
+  int64_t Distance = Val.getSExtValue();
+  unsigned Stride = std::abs(StrideAPtr);
+
+  // Attempt to prove strided accesses independent.
+  if (std::abs(Distance) > 0 && Stride > 1 && ATy == BTy &&
+      areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) {
+    DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
+    return Dependence::NoDep;
+  }
+
+  // Negative distances are not plausible dependencies.
   if (Val.isNegative()) {
     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
     if (IsTrueDataDependence && EnableForwardingConflictDetection &&
@@ -1244,15 +1254,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
     return Dependence::Unknown;
   }
 
-  unsigned Distance = (unsigned) Val.getZExtValue();
-
-  unsigned Stride = std::abs(StrideAPtr);
-  if (Stride > 1 &&
-      areStridedAccessesIndependent(Distance, Stride, TypeByteSize)) {
-    DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
-    return Dependence::NoDep;
-  }
-
   // Bail out early if passed-in parameters make vectorization not feasible.
   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
                            VectorizerParams::VectorizationFactor : 1);
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/independent-interleaved.ll b/llvm/test/Analysis/LoopAccessAnalysis/independent-interleaved.ll
new file mode 100644
index 00000000000..1be6ee6dc70
--- /dev/null
+++ b/llvm/test/Analysis/LoopAccessAnalysis/independent-interleaved.ll
@@ -0,0 +1,45 @@
+; RUN: opt < %s -store-to-load-forwarding-conflict-detection=false -loop-accesses -analyze | FileCheck %s
+
+; This test checks that we prove the strided accesses to be independent before
+; concluding that there is a forward dependence.
+
+; struct pair {
+;   int x;
+;   int y;
+; };
+;
+; int independent_interleaved(struct pair *p, int z, int n) {
+;   int s = 0;
+;   for (int i = 0; i < n; i++) {
+;     p[i].y = z;
+;     s += p[i].x;
+;   }
+;   return s;
+; }
+
+; CHECK:     for.body:
+; CHECK-NOT:     Forward:
+; CHECK-NOT:         store i32 %z, i32* %p_i.y, align 8 ->
+; CHECK-NOT:         %0 = load i32, i32* %p_i.x, align 8
+
+%pair = type { i32, i32 }
+define i32 @independent_interleaved(%pair *%p, i64 %n, i32 %z) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ %i.next, %for.body ], [ 0, %entry ]
+  %s = phi i32 [ %1, %for.body ], [ 0, %entry ]
+  %p_i.x = getelementptr inbounds %pair, %pair* %p, i64 %i, i32 0
+  %p_i.y = getelementptr inbounds %pair, %pair* %p, i64 %i, i32 1
+  store i32 %z, i32* %p_i.y, align 8
+  %0 = load i32, i32* %p_i.x, align 8
+  %1 = add nsw i32 %0, %s
+  %i.next = add nuw nsw i64 %i, 1
+  %cond = icmp slt i64 %i.next, %n
+  br i1 %cond, label %for.body, label %for.end
+
+for.end:
+  %2 = phi i32 [ %1, %for.body ]
+  ret i32 %2
+}