[LAA] Rename and fix semantics of MaxSafeDepDistBytes to MinDepDistBytes

[michaelmaitland]

Summary

`MaxSafeDepDistBytes` was not correct based on its name an semantics
in instances when there was a non-unit stride loop. For example,

```
for (int k = 0; k < len; k+=3) {
  a[k] = a[k+4];
  a[k+2] = a[k+6];
}
```

Here, the smallest dependence distance is 24 bytes, but only vectorizing 8 bytes
is safe. `MaxSafeVectorWidthInBits` reported the correct number of bits
that could be vectorized as 64 bits.

The semantics of of `MaxSafeDepDistBytes` should be:
  The smallest dependence distance in bytes in the loop. This may not be
  the same as the maximum number of bytes that are safe to operate on
  simultaneously.

The name of this variable should reflect those semantics and
its docstring should be updated accordingly, `MinDepDistBytes`.

A debug message that used `MaxSafeDepDistBytes` to signify to the user
how many bytes could be accessed in parallel is updated to use
`MaxSafeVectorWidthInBits` instead. That way, the same message if
communicated to the user, just in different units.

This patch makes sure that when `MinDepDistBytes` is modified in a way
that should impact `MaxSafeVectorWidthInBits`, that we update the latter
accordingly. This patch also clarifies why `MaxSafeVectorWidthInBits`
does not to be updated when `MinDepDistBytes` is (i.e. in the case of a
forward dependency).

[michaelmaitland]

Fix typo

[michaelmaitland]

Last update had wrong diff.

[michaelmaitland]

Clarify how MinDepDistBytes intereacts with MaxSafeVectorWidthInBits

[michaelmaitland]

ping

[fhahn]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

202

Are there any uses outside of LAA remaining? If not, maybe make it private to prevent future potential mis-use?

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2014

This is the only non-NFC part of the patch, IIUC? Would it be possible to create a test case showing the new behavior?

[fhahn]

Thanks for the follow up!

[michaelmaitland]

Make getMinDepDistBytes private to DepChecker.

[fhahn]

Thanks for the update! It looks like there's some clang-format issue (as reported by the pre-commit checks), but overall looks good pending clarification about the test for the change in behavior

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2014

Would it be possible to add a test for the functional change here?

[michaelmaitland]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2014

I assume you mean the fact that we update MaxSafeVectorWidthInBits even if IsTrueDataDependence && EnableForwardingConflictDetection && couldPreventStoreLoadForward(Distance, TypeByteSize).

I am working on constructing a test case for this.

[michaelmaitland]

Add sanity check

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2014

@fhahn I've updated this diff that no longer update MaxSafeVectorWidthInBits even if IsTrueDataDependence && EnableForwardingConflictDetection && couldPreventStoreLoadForward(Distance, TypeByteSize). The reason for this is that if couldPreventStoreLoadForward returns true, then it must be the case that MinDepDistBytes was not updated, and therefore MaxSafeVectorWidthInBits will remain the same.

I've added an assert statement as a sanity check against any future changes.

[fhahn]

LGTM, thanks!

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2006

As MinDepDistBytesOld is only used in the assert, I think at the moment we would get a warning in release builds, so we probably either need (void) MinDepDistBytesOld; or wrap the declaration in an ifdef.

2014

Ok thanks! I think that is fine for now, as this keeps the logic in this part working as before.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

enum DepType {
       // indices used to access the same array, the MemoryDepChecker *is*
       // queried and the dependence list is complete.
       Forward,
       // Forward, but if vectorized, is likely to prevent store-to-load
       // forwarding.
       ForwardButPreventsForwarding,
       // Lexically backward.
       Backward,
-      // Backward, but the distance allows a vectorization factor of
-      // MaxSafeDepDistBytes.
+      // Backward, but the distance allows a vectorization factor of dependent
+      // on MinDepDistBytes.
       BackwardVectorizable,
       // Same, but may prevent store-to-load forwarding.
       BackwardVectorizableButPreventsForwarding
     };
 
     /// String version of the types.
     static const char *DepName[];
 
public:
   }
 
   /// Return true if the number of elements that are safe to operate on
   /// simultaneously is not bounded.
   bool isSafeForAnyVectorWidth() const {
     return MaxSafeVectorWidthInBits == UINT_MAX;
   }
 
-  /// The maximum number of bytes of a vector register we can vectorize
-  /// the accesses safely with.
-  uint64_t getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
-
   /// Return the number of elements that are safe to operate on
   /// simultaneously, multiplied by the size of the element in bits.
   uint64_t getMaxSafeVectorWidthInBits() const {
     return MaxSafeVectorWidthInBits;
   }
 
   /// In same cases when the dependency check fails we can still
   /// vectorize the loop with a dynamic array access check.
   bool shouldRetryWithRuntimeCheck() const {
     return FoundNonConstantDistanceDependence &&
            Status == VectorizationSafetyStatus::PossiblySafeWithRtChecks;
private:
   DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
 
   /// Memory access instructions in program order.
   SmallVector<Instruction *, 16> InstMap;
 
   /// The program order index to be used for the next instruction.
   unsigned AccessIdx = 0;
 
-  // We can access this many bytes in parallel safely.
-  uint64_t MaxSafeDepDistBytes = 0;
+  /// The smallest dependence distance in bytes in the loop. This may not be
+  /// the same as the maximum number of bytes that are safe to operate on
+  /// simultaneously.
+  uint64_t MinDepDistBytes = 0;
 
   /// Number of elements (from consecutive iterations) that are safe to
   /// operate on simultaneously, multiplied by the size of the element in bits.
   /// The size of the element is taken from the memory access that is most
   /// restrictive.
   uint64_t MaxSafeVectorWidthInBits = -1U;
 
   /// If we see a non-constant dependence distance we can still try to
private:
   /// accesses.
   ///
   /// Access \p A must happen before \p B in program order. The two indices
   /// identify the index into the program order map.
   ///
   /// This function checks  whether there is a plausible dependence (or the
   /// absence of such can't be proved) between the two accesses. If there is a
   /// plausible dependence but the dependence distance is bigger than one
-  /// element access it records this distance in \p MaxSafeDepDistBytes (if this
+  /// element access it records this distance in \p MinDepDistBytes (if this
   /// distance is smaller than any other distance encountered so far).
   /// Otherwise, this function returns true signaling a possible dependence.
   Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
                                   const MemAccessInfo &B, unsigned BIdx,
                                   const DenseMap<Value *, const SCEV *> &Strides);
 
   /// Check whether the data dependence could prevent store-load
   /// forwarding.
   ///
   /// \return false if we shouldn't vectorize at all or avoid larger
-  /// vectorization factors by limiting MaxSafeDepDistBytes.
+  /// vectorization factors by limiting MinDepDistBytes.
   bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
 
   /// Updates the current safety status with \p S. We can go from Safe to
   /// either PossiblySafeWithRtChecks or Unsafe and from
   /// PossiblySafeWithRtChecks to Unsafe.
   void mergeInStatus(VectorizationSafetyStatus S);
 };
 
private:
   /// loop-independent and loop-carried dependences between memory accesses.
   std::unique_ptr<MemoryDepChecker> DepChecker;
 
   Loop *TheLoop;
 
   unsigned NumLoads = 0;
   unsigned NumStores = 0;
 
-  uint64_t MaxSafeDepDistBytes = -1;
-
   /// Cache the result of analyzeLoop.
   bool CanVecMem = false;
   bool HasConvergentOp = false;
 
   /// Indicator that there are non vectorizable stores to a uniform address.
   bool HasDependenceInvolvingLoopInvariantAddress = false;
 
   /// List of stores to invariant addresses.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
   //   place. Vectorizing in such cases does not make sense.
   // Store-load forwarding distance.
 
   // After this many iterations store-to-load forwarding conflicts should not
   // cause any slowdowns.
   const uint64_t NumItersForStoreLoadThroughMemory = 8 * TypeByteSize;
   // Maximum vector factor.
   uint64_t MaxVFWithoutSLForwardIssues = std::min(
-      VectorizerParams::MaxVectorWidth * TypeByteSize, MaxSafeDepDistBytes);
+      VectorizerParams::MaxVectorWidth * TypeByteSize, MinDepDistBytes);
 
   // Compute the smallest VF at which the store and load would be misaligned.
   for (uint64_t VF = 2 * TypeByteSize; VF <= MaxVFWithoutSLForwardIssues;
        VF *= 2) {
     // If the number of vector iteration between the store and the load are
     // small we could incur conflicts.
     if (Distance % VF && Distance / VF < NumItersForStoreLoadThroughMemory) {
       MaxVFWithoutSLForwardIssues = (VF >> 1);
       break;
     }
   }
 
   if (MaxVFWithoutSLForwardIssues < 2 * TypeByteSize) {
     LLVM_DEBUG(
         dbgs() << "LAA: Distance " << Distance
                << " that could cause a store-load forwarding conflict\n");
     return true;
   }
 
-  if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
+  if (MaxVFWithoutSLForwardIssues < MinDepDistBytes &&
       MaxVFWithoutSLForwardIssues !=
           VectorizerParams::MaxVectorWidth * TypeByteSize)
-    MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
+    MinDepDistBytes = MaxVFWithoutSLForwardIssues;
   return false;
 }
 
 void MemoryDepChecker::mergeInStatus(VectorizationSafetyStatus S) {
   if (Status < S)
     Status = S;
 }
 
if (std::abs(Distance) > 0 && Stride > 1 && HasSameSize &&
       areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) {
     LLVM_DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
     return Dependence::NoDep;
   }
 
   // Negative distances are not plausible dependencies.
   if (Val.isNegative()) {
     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
+    // There is no need to update MaxSafeVectorWidthInBits after call to
+    // couldPreventStoreLoadForward, even if it changed MinDepDistBytes,
+    // since a forward dependency will allow vectorization using any width.
     if (IsTrueDataDependence && EnableForwardingConflictDetection &&
         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
          !HasSameSize)) {
       LLVM_DEBUG(dbgs() << "LAA: Forward but may prevent st->ld forwarding\n");
       return Dependence::ForwardButPreventsForwarding;
     }
 
     LLVM_DEBUG(dbgs() << "LAA: Dependence is negative\n");
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   uint64_t MinDistanceNeeded =
       TypeByteSize * Stride * (MinNumIter - 1) + TypeByteSize;
   if (MinDistanceNeeded > static_cast<uint64_t>(Distance)) {
     LLVM_DEBUG(dbgs() << "LAA: Failure because of positive distance "
                       << Distance << '\n');
     return Dependence::Backward;
   }
 
-  // Unsafe if the minimum distance needed is greater than max safe distance.
-  if (MinDistanceNeeded > MaxSafeDepDistBytes) {
+  // Unsafe if the minimum distance needed is greater than smallest dependence
+  // distance distance.
+  if (MinDistanceNeeded > MinDepDistBytes) {
     LLVM_DEBUG(dbgs() << "LAA: Failure because it needs at least "
                       << MinDistanceNeeded << " size in bytes\n");
     return Dependence::Backward;
   }
 
   // Positive distance bigger than max vectorization factor.
   // FIXME: Should use max factor instead of max distance in bytes, which could
   // not handle different types.
   // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
   //      void foo (int *A, char *B) {
   //        for (unsigned i = 0; i < 1024; i++) {
   //          A[i+2] = A[i] + 1;
   //          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);
+  MinDepDistBytes =
+      std::min(static_cast<uint64_t>(Distance), MinDepDistBytes);
 
   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
+  uint64_t MinDepDistBytesOld = MinDepDistBytes;
   if (IsTrueDataDependence && EnableForwardingConflictDetection &&
-      couldPreventStoreLoadForward(Distance, TypeByteSize))
+      couldPreventStoreLoadForward(Distance, TypeByteSize)) {
+    // Sanity check that we didn't update MinDepDistBytes when calling
+    // couldPreventStoreLoadForward
+    assert(MinDepDistBytes == MinDepDistBytesOld &&
+           "An update to MinDepDistBytes requires an update to "
+           "MaxSafeVectorWidthInBits");
     return Dependence::BackwardVectorizableButPreventsForwarding;
+  }
 
-  uint64_t MaxVF = MaxSafeDepDistBytes / (TypeByteSize * Stride);
+  // An update to MinDepDistBytes requires an update to MaxSafeVectorWidthInBits
+  // since there is a backwards dependency.
+  uint64_t MaxVF = MinDepDistBytes / (TypeByteSize * Stride);
   LLVM_DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
                     << " with max VF = " << MaxVF << '\n');
   uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
   MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
                                    const DenseMap<Value *, const SCEV *> &Strides) {
 
-  MaxSafeDepDistBytes = -1;
+  MinDepDistBytes = -1;
   SmallPtrSet<MemAccessInfo, 8> Visited;
   for (MemAccessInfo CurAccess : CheckDeps) {
     if (Visited.count(CurAccess))
       continue;
 
     // Get the relevant memory access set.
     EquivalenceClasses<MemAccessInfo>::iterator I =
       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
   LLVM_DEBUG(
     dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n");
 
   CanVecMem = true;
   if (Accesses.isDependencyCheckNeeded()) {
     LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
     CanVecMem = DepChecker->areDepsSafe(
         DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides);
-    MaxSafeDepDistBytes = DepChecker->getMaxSafeDepDistBytes();
 
     if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
       LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
 
       // Clear the dependency checks. We assume they are not needed.
       Accesses.resetDepChecks(*DepChecker);
 
       PtrRtChecking->reset();
LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
   if (canAnalyzeLoop()) {
     analyzeLoop(AA, LI, TLI, DT);
   }
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   if (CanVecMem) {
     OS.indent(Depth) << "Memory dependences are safe";
-    if (MaxSafeDepDistBytes != -1ULL)
-      OS << " with a maximum dependence distance of " << MaxSafeDepDistBytes
-         << " bytes";
+    const MemoryDepChecker &DC = getDepChecker();
+    if (!DC.isSafeForAnyVectorWidth())
+      OS << " with a maximum safe vector width of "
+         << DC.getMaxSafeVectorWidthInBits() << " bits";
     if (PtrRtChecking->Need)
       OS << " with run-time checks";
     OS << "\n";
   }
 
   if (HasConvergentOp)
     OS.indent(Depth) << "Has convergent operation in loop\n";
 

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

 ; RUN: opt -S -disable-output -passes='print<access-info>' < %s 2>&1 | FileCheck %s
 
 
 ; In the function below some of the accesses are done as float types and some
 ; are done as i32 types. When doing dependence analysis the type should not
 ; matter if it can be determined that they are the same size.
 
 %int_pair = type { i32, i32 }
 
 ; 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:      Memory dependences are safe with a maximum safe vector width of 3200 bits
 ; CHECK-NEXT:      Dependences:
 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
 ; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
 ; CHECK-EMPTY:
 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
 ; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types_opaque_ptr.ll

 ; RUN: opt -S -disable-output -passes='print<access-info>' < %s 2>&1 | FileCheck %s
 
 ; In the function below some of the accesses are done as float types and some
 ; are done as i32 types. When doing dependence analysis the type should not
 ; matter if it can be determined that they are the same size.
 
 %int_pair = type { i32, i32 }
 
 ; 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:      Memory dependences are safe with a maximum safe vector width of 3200 bits
 ; CHECK-NEXT:      Dependences:
 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
 ; CHECK-NEXT:            store i32 %indvars.iv.i32, ptr %gep.iv, align 8
 ; CHECK-EMPTY:
 ; CHECK-NEXT:        Forward:
 ; CHECK-NEXT:            %ld.f32 = load float, ptr %gep.iv, align 8 ->
 ; CHECK-NEXT:            store float %val, ptr %gep.iv.min.100, align 8

llvm/test/Analysis/LoopAccessAnalysis/max_safe_dep_dist_non_unit_stride.ll

 ; RUN: opt -S -disable-output -passes='print<access-info>' < %s 2>&1 | FileCheck %s
 
 ; Generated from following C program:
 ; void foo(int len, int *a) {
 ;   for (int k = 0; k < len; k+=3) {
 ;     a[k] = a[k + 4];
 ;     a[k+2] = a[k+6];
 ;   }
 ; }
 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 safe vector width of 64 bits
 ; CHECK-NEXT:    Dependences:
 ; CHECK-NEXT:      BackwardVectorizable:
 ; CHECK-NEXT:          store i32 %0, ptr %arrayidx2, align 4 ->
 ; CHECK-NEXT:          %1 = load i32, ptr %arrayidx5, align 4
 ; CHECK-EMPTY:
 ; CHECK-NEXT:    Run-time memory checks:
 ; CHECK-NEXT:    Grouped accesses:
 ; CHECK-EMPTY:

llvm/test/Analysis/LoopAccessAnalysis/safe-with-dep-distance.ll

 ; RUN: opt -passes='print<access-info>' -disable-output  < %s 2>&1 | FileCheck %s
 
 ; Analyze this loop:
 ;   for (i = 0; i < n; i++)
 ;    A[i + 4] = A[i] * 2;
 
-; CHECK: Memory dependences are safe with a maximum dependence distance of 8 bytes
+; CHECK: Memory dependences are safe with a maximum safe vector width of 64 bits
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.10.0"
 
 @A = common global ptr null, align 8
 
 define void @f() {
 entry: