[LAA] Check accesses don't overlap early to determine NoDep (#92307)

Use getStartAndEndForAccess to compute the start and end of both src 
and sink (factored out to helper in bce3680f45b57f). If they do not
overlap (i.e. SrcEnd <= SinkStart || SinkEnd <= SrcStart), there is no
dependence, regardless of stride.

PR: https://github.com/llvm/llvm-project/pull/92307

1 files changed, 24 insertions, 4 deletions

diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index df01ad1..2a967f5 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -213,9 +213,7 @@ getStartAndEndForAccess(const Loop *Lp, const SCEV *PtrExpr, Type *AccessTy,
 
   if (SE->isLoopInvariant(PtrExpr, Lp)) {
     ScStart = ScEnd = PtrExpr;
-  } else {
-    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrExpr);
-    assert(AR && "Invalid addrec expression");
+  } else if (auto *AR = dyn_cast<SCEVAddRecExpr>(PtrExpr)) {
     const SCEV *Ex = PSE.getBackedgeTakenCount();
 
     ScStart = AR->getStart();
@@ -234,7 +232,9 @@ getStartAndEndForAccess(const Loop *Lp, const SCEV *PtrExpr, Type *AccessTy,
       ScStart = SE->getUMinExpr(ScStart, ScEnd);
       ScEnd = SE->getUMaxExpr(AR->getStart(), ScEnd);
     }
-  }
+  } else
+    return {SE->getCouldNotCompute(), SE->getCouldNotCompute()};
+
   assert(SE->isLoopInvariant(ScStart, Lp) && "ScStart needs to be invariant");
   assert(SE->isLoopInvariant(ScEnd, Lp)&& "ScEnd needs to be invariant");
 
@@ -256,6 +256,9 @@ void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr,
                                     bool NeedsFreeze) {
   const auto &[ScStart, ScEnd] =
       getStartAndEndForAccess(Lp, PtrExpr, AccessTy, PSE);
+  assert(!isa<SCEVCouldNotCompute>(ScStart) &&
+         !isa<SCEVCouldNotCompute>(ScEnd) &&
+         "must be able to compute both start and end expressions");
   Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, PtrExpr,
                         NeedsFreeze);
 }
@@ -1987,6 +1990,23 @@ getDependenceDistanceStrideAndSize(
                                    InnermostLoop))
     return MemoryDepChecker::Dependence::IndirectUnsafe;
 
+  // Check if we can prove that Sink only accesses memory after Src's end or
+  // vice versa.
+  const auto &[SrcStart, SrcEnd] =
+      getStartAndEndForAccess(InnermostLoop, Src, ATy, PSE);
+  const auto &[SinkStart, SinkEnd] =
+      getStartAndEndForAccess(InnermostLoop, Sink, BTy, PSE);
+
+  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. We don't want
   // to vectorize "A[B[i]] += ..." and similar code or pointer arithmetic that
   // could wrap in the address space.