Revert "[LAA] Remove loop-invariant check added in 234cc40adc61."

This reverts commit a80053322b765eec93951e21db490c55521da2d8.

The new asserts exposed an underlying issue where the expanded bounds
could wrap, causing the parts of the code to incorrectly determine that
accesses do not overlap.

Reproducer below based on @mstorsjo's test case.

opt -passes='print<access-info>'

target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"

define i32 @j(ptr %P, i32 %x, i32 %y) {
entry:
  %gep.P.4 = getelementptr inbounds nuw i8, ptr %P, i32 4
  %gep.P.8 = getelementptr inbounds nuw i8, ptr %P, i32 8
  br label %loop

loop:
  %1 = phi i32 [ %x, %entry ], [ %sel, %loop.latch ]
  %iv = phi i32 [ %y, %entry ], [ %iv.next, %loop.latch ]
  %gep.iv = getelementptr inbounds i64, ptr %gep.P.8, i32 %iv
  %l = load i32, ptr %gep.iv, align 4
  %c.1 = icmp eq i32 %l, 3
  br i1 %c.1, label %loop.latch, label %if.then

if.then:                                          ; preds = %for.body
  store i64 0, ptr %gep.iv, align 4
  %l.2 = load i32, ptr %gep.P.4
  br label %loop.latch

loop.latch:
  %sel = phi i32 [ %l.2, %if.then ], [ %1, %loop ]
  %iv.next = add nsw i32 %iv, 1
  %c.2 = icmp slt i32 %iv.next, %sel
  br i1 %c.2, label %loop, label %exit

exit:
  %res = phi i32 [ %iv.next, %loop.latch ]
  ret i32 %res
}

1 files changed, 23 insertions, 58 deletions

diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 8d53a27..980f142 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -1937,6 +1937,27 @@ MemoryDepChecker::getDependenceDistanceStrideAndSize(
   LLVM_DEBUG(dbgs() << "LAA: Distance for " << *AInst << " to " << *BInst
                     << ": " << *Dist << "\n");
 
+  // Check if we can prove that Sink only accesses memory after Src's end or
+  // vice versa. At the moment this is limited to cases where either source or
+  // sink are loop invariant to avoid compile-time increases. This is not
+  // required for correctness.
+  if (SE.isLoopInvariant(Src, InnermostLoop) ||
+      SE.isLoopInvariant(Sink, InnermostLoop)) {
+    const auto &[SrcStart, SrcEnd] =
+        getStartAndEndForAccess(InnermostLoop, Src, ATy, PSE, PointerBounds);
+    const auto &[SinkStart, SinkEnd] =
+        getStartAndEndForAccess(InnermostLoop, Sink, BTy, PSE, PointerBounds);
+    if (!isa<SCEVCouldNotCompute>(SrcStart) &&
+        !isa<SCEVCouldNotCompute>(SrcEnd) &&
+        !isa<SCEVCouldNotCompute>(SinkStart) &&
+        !isa<SCEVCouldNotCompute>(SinkEnd)) {
+      if (SE.isKnownPredicate(CmpInst::ICMP_ULE, SrcEnd, SinkStart))
+        return MemoryDepChecker::Dependence::NoDep;
+      if (SE.isKnownPredicate(CmpInst::ICMP_ULE, SinkEnd, SrcStart))
+        return MemoryDepChecker::Dependence::NoDep;
+    }
+  }
+
   // Need accesses with constant strides and the same direction for further
   // dependence analysis. We don't want to vectorize "A[B[i]] += ..." and
   // similar code or pointer arithmetic that could wrap in the address space.
@@ -1982,45 +2003,12 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
                               const MemAccessInfo &B, unsigned BIdx) {
   assert(AIdx < BIdx && "Must pass arguments in program order");
 
-  // Check if we can prove that Sink only accesses memory after Src's end or
-  // vice versa. The helper is used to perform the checks only on the exit paths
-  // where it helps to improve the analysis result.
-  auto CheckCompletelyBeforeOrAfter = [&]() {
-    auto *APtr = A.getPointer();
-    auto *BPtr = B.getPointer();
-
-    Type *ATy = getLoadStoreType(InstMap[AIdx]);
-    Type *BTy = getLoadStoreType(InstMap[BIdx]);
-
-    const SCEV *Src = PSE.getSCEV(APtr);
-    const SCEV *Sink = PSE.getSCEV(BPtr);
-
-    const auto &[SrcStart, SrcEnd] =
-        getStartAndEndForAccess(InnermostLoop, Src, ATy, PSE, PointerBounds);
-    if (isa<SCEVCouldNotCompute>(SrcStart) || isa<SCEVCouldNotCompute>(SrcEnd))
-      return false;
-
-    const auto &[SinkStart, SinkEnd] =
-        getStartAndEndForAccess(InnermostLoop, Sink, BTy, PSE, PointerBounds);
-    if (isa<SCEVCouldNotCompute>(SinkStart) ||
-        isa<SCEVCouldNotCompute>(SinkEnd))
-      return false;
-
-    auto &SE = *PSE.getSE();
-    return SE.isKnownPredicate(CmpInst::ICMP_ULE, SrcEnd, SinkStart) ||
-           SE.isKnownPredicate(CmpInst::ICMP_ULE, SinkEnd, SrcStart);
-  };
-
   // Get the dependence distance, stride, type size and what access writes for
   // the dependence between A and B.
   auto Res =
       getDependenceDistanceStrideAndSize(A, InstMap[AIdx], B, InstMap[BIdx]);
-  if (std::holds_alternative<Dependence::DepType>(Res)) {
-    if (std::get<Dependence::DepType>(Res) == Dependence::Unknown &&
-        CheckCompletelyBeforeOrAfter())
-      return Dependence::NoDep;
+  if (std::holds_alternative<Dependence::DepType>(Res))
     return std::get<Dependence::DepType>(Res);
-  }
 
   auto &[Dist, StrideA, StrideB, TypeByteSize, AIsWrite, BIsWrite] =
       std::get<DepDistanceStrideAndSizeInfo>(Res);
@@ -2029,9 +2017,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   std::optional<uint64_t> CommonStride =
       StrideA == StrideB ? std::make_optional(StrideA) : std::nullopt;
   if (isa<SCEVCouldNotCompute>(Dist)) {
-    if (CheckCompletelyBeforeOrAfter())
-      return Dependence::NoDep;
-
     // TODO: Relax requirement that there is a common stride to retry with
     // non-constant distance dependencies.
     FoundNonConstantDistanceDependence |= CommonStride.has_value();
@@ -2083,8 +2068,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
         // Write to the same location with the same size.
         return Dependence::Forward;
       }
-      assert(!CheckCompletelyBeforeOrAfter() &&
-             "unexpectedly proved no dependence");
       LLVM_DEBUG(dbgs() << "LAA: possibly zero dependence difference but "
                            "different type sizes\n");
       return Dependence::Unknown;
@@ -2106,8 +2089,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
         // did not set it when strides were different but there is no inherent
         // reason to.
         FoundNonConstantDistanceDependence |= CommonStride.has_value();
-        if (CheckCompletelyBeforeOrAfter())
-          return Dependence::NoDep;
         return Dependence::Unknown;
       }
       if (!HasSameSize ||
@@ -2127,9 +2108,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   // Below we only handle strictly positive distances.
   if (MinDistance <= 0) {
     FoundNonConstantDistanceDependence |= CommonStride.has_value();
-    if (CheckCompletelyBeforeOrAfter())
-      return Dependence::NoDep;
-
     return Dependence::Unknown;
   }
 
@@ -2146,18 +2124,13 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   }
 
   if (!HasSameSize) {
-    if (CheckCompletelyBeforeOrAfter())
-      return Dependence::NoDep;
     LLVM_DEBUG(dbgs() << "LAA: ReadWrite-Write positive dependency with "
                          "different type sizes\n");
     return Dependence::Unknown;
   }
 
-  if (!CommonStride) {
-    if (CheckCompletelyBeforeOrAfter())
-      return Dependence::NoDep;
+  if (!CommonStride)
     return Dependence::Unknown;
-  }
 
   // Bail out early if passed-in parameters make vectorization not feasible.
   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
@@ -2205,10 +2178,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
       // dependence distance and the distance may be larger at runtime (and safe
       // for vectorization). Classify it as Unknown, so we re-try with runtime
       // checks.
-      //
-      if (CheckCompletelyBeforeOrAfter())
-        return Dependence::NoDep;
-
       return Dependence::Unknown;
     }
     LLVM_DEBUG(dbgs() << "LAA: Failure because of positive minimum distance "
@@ -2221,8 +2190,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   if (MinDistanceNeeded > MinDepDistBytes) {
     LLVM_DEBUG(dbgs() << "LAA: Failure because it needs at least "
                       << MinDistanceNeeded << " size in bytes\n");
-    assert(!CheckCompletelyBeforeOrAfter() &&
-           "unexpectedly proved no dependence");
     return Dependence::Backward;
   }
 
@@ -2270,8 +2237,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
     // For non-constant distances, we checked the lower bound of the dependence
     // distance and the distance may be larger at runtime (and safe for
     // vectorization). Classify it as Unknown, so we re-try with runtime checks.
-    assert(!CheckCompletelyBeforeOrAfter() &&
-           "unexpectedly proved no dependence");
     return Dependence::Unknown;
   }