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.
+  std::optional<Loop::LoopBounds> 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 &&
@@ -2775,6 +2803,11 @@
     OS << "\n";
   }
 
+  if (DepChecker->getMaxSafeVectorWidthInBits() != -1U)
+    OS.indent(Depth) << "The maximum number of bits that are safe to operate "
+                        "on in parallel is "
+                     << DepChecker->getMaxSafeVectorWidthInBits() << "\n";
+
   if (HasConvergentOp)
     OS.indent(Depth) << "Has convergent operation in loop\n";
 
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll b/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll
--- a/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll
+++ b/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll
@@ -10,6 +10,7 @@
 ; CHECK-LABEL: function 'backdep_type_size_equivalence':
 ; CHECK-NEXT:    loop:
 ; CHECK-NEXT:      Memory dependences are safe with a maximum dependence distance of 800 bytes
+; CHECK-NEXT:      The maximum number of bits that are safe to operate on in parallel is 3200
 ; CHECK-NEXT:      Dependences:
 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types_opaque_ptr.ll b/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types_opaque_ptr.ll
--- a/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types_opaque_ptr.ll
+++ b/llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types_opaque_ptr.ll
@@ -9,6 +9,7 @@
 ; CHECK-LABEL: function 'backdep_type_size_equivalence':
 ; CHECK-NEXT:    loop:
 ; CHECK-NEXT:      Memory dependences are safe with a maximum dependence distance of 800 bytes
+; CHECK-NEXT:      The maximum number of bits that are safe to operate on in parallel is 3200
 ; CHECK-NEXT:      Dependences:
 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
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,8 @@
 define void @foo(i64  %len, ptr %a) {
 ; CHECK-LABEL: Loop access info in function 'foo':
 ; CHECK-NEXT:  loop:
-; 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:    The maximum number of bits that are safe to operate on in parallel is 0
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      BackwardVectorizable:
 ; CHECK-NEXT:          store i32 %0, ptr %arrayidx2, align 4 ->
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll b/llvm/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll
--- a/llvm/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll
+++ b/llvm/test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll
@@ -232,7 +232,8 @@
 
 ; CHECK: function 'vectorizable_Read_Write':
 ; CHECK-NEXT:   for.body:
-; CHECK-NEXT:     Memory dependences are safe
+; CHECK-NEXT:     Memory dependences are safe with a maximum dependence distance of 8 bytes
+; CHECK-NEXT:     The maximum number of bits that are safe to operate on in parallel is 32
 ; CHECK-NEXT:     Dependences:
 ; CHECK-NEXT:       BackwardVectorizable:
 ; CHECK-NEXT:           %0 = load i32, ptr %arrayidx, align 4 ->
@@ -271,7 +272,8 @@
 
 ; CHECK: function 'vectorizable_Write_Read':
 ; CHECK-NEXT:   for.body:
-; CHECK-NEXT:     Memory dependences are safe
+; CHECK-NEXT:     Memory dependences are safe with a maximum dependence distance of 8 bytes
+; CHECK-NEXT:     The maximum number of bits that are safe to operate on in parallel is 32
 ; CHECK-NEXT:     Dependences:
 ; CHECK-NEXT:       BackwardVectorizable:
 ; CHECK-NEXT:           store i32 %0, ptr %arrayidx, align 4 ->
@@ -309,7 +311,8 @@
 
 ; CHECK: function 'vectorizable_Write_Write':
 ; CHECK-NEXT:   for.body:
-; CHECK-NEXT:     Memory dependences are safe
+; CHECK-NEXT:     Memory dependences are safe with a maximum dependence distance of 8 bytes
+; CHECK-NEXT:     The maximum number of bits that are safe to operate on in parallel is 32
 ; CHECK-NEXT:     Dependences:
 ; CHECK-NEXT:       BackwardVectorizable:
 ; CHECK-NEXT:           store i32 %0, ptr %arrayidx, align 4 -> 
@@ -388,7 +391,8 @@
 
 ; CHECK: function 'vectorizable_unscaled_Write_Read':
 ; CHECK-NEXT:   for.body:
-; CHECK-NEXT:     Memory dependences are safe
+; CHECK-NEXT:     Memory dependences are safe with a maximum dependence distance of 8 bytes
+; CHECK-NEXT:     The maximum number of bits that are safe to operate on in parallel is 32
 ; CHECK-NEXT:     Dependences:
 ; CHECK-NEXT:       BackwardVectorizable:
 ; CHECK-NEXT:           store i32 %0, ptr %arrayidx, align 4 ->