diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -1987,14 +1987,42 @@
   //          B[i+2] = B[i] + 1;
   //        }
   //      }
-  //
   // This case is currently unsafe according to the max safe distance. If we
   // analyze the two accesses on array B, the max safe dependence distance
   // is 2. Then we analyze the accesses on array A, the minimum distance needed
   // is 8, which is less than 2 and forbidden vectorization, But actually
   // both A and B could be vectorized by 2 iterations.
-  MaxSafeDepDistBytes =
-      std::min(static_cast<uint64_t>(Distance), MaxSafeDepDistBytes);
+  //
+  // Distance must be reduced by a factor of the stride of the loop induction
+  // variable, otherwise it is possible that MaxSafeDepDistBytes is too
+  // large. For example,
+  //   for (int k = 0; k < len; k+=3) {
+  //     a[k] = a[k + 4];
+  //     a[k+2] = a[k+6];
+  //   }
+  // without accounting for loop stride has MaxSafeDepDist=24 when it it must be
+  // 8.
+  auto Bounds = InnermostLoop->getBounds(SE);
+  if (!Bounds) {
+    LLVM_DEBUG(dbgs() << "LAA: Could not determine bounds of loop induction "
+                         "variable, so the MaxSafeDepDistBytes is unknown");
+    MaxSafeDepDistBytes = 0;
+    return Dependence::Unknown;
+  }
+  const SCEV *StepVal = SE.getSCEV(Bounds->getStepValue());
+  const SCEVConstant *StepValC = dyn_cast<SCEVConstant>(StepVal);
+  if (!StepValC) {
+    LLVM_DEBUG(dbgs() << "LAA: Could not determine step value of loop induction "
+                         "variable, so the MaxSafeDepDistBytes is unknown");
+    MaxSafeDepDistBytes = 0;
+    return Dependence::Unknown;
+  }
+
+  const APInt &LoopIVStrideAP = StepValC->getAPInt().abs();
+  uint64_t LoopIVStride = LoopIVStrideAP.getZExtValue();
+
+  MaxSafeDepDistBytes = std::min(static_cast<uint64_t>(Distance / LoopIVStride),
+                                 MaxSafeDepDistBytes);
 
   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
   if (IsTrueDataDependence && EnableForwardingConflictDetection &&
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/max_safe_dep_dist_non_unit_stride.ll b/llvm/test/Analysis/LoopAccessAnalysis/max_safe_dep_dist_non_unit_stride.ll
--- a/llvm/test/Analysis/LoopAccessAnalysis/max_safe_dep_dist_non_unit_stride.ll
+++ b/llvm/test/Analysis/LoopAccessAnalysis/max_safe_dep_dist_non_unit_stride.ll
@@ -10,7 +10,7 @@
 define void @foo(i32 noundef signext %len, ptr nocapture noundef %a) {
 ; CHECK-LABEL: Loop access info in function 'foo':
 ; CHECK-NEXT:  for.body:
-; CHECK-NEXT:    Memory dependences are safe with a maximum dependence distance of 24 bytes
+; CHECK-NEXT:    Memory dependences are safe with a maximum dependence distance of 8 bytes
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      BackwardVectorizable:
 ; CHECK-NEXT:          store i32 %2, ptr %arrayidx2, align 4 ->