[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

204

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

2011

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

2011

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

[michaelmaitland]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

2011

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

2011

@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

2009

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.

2011

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

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 smallest ddependence distance in bytes in the loop. This may not 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.
   uint64_t getMinDepDistBytes() { return MinDepDistBytes; }
 
   /// 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
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;
 
-  /// The smallest ddependence distance in bytes in the loop. This may not 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.
   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.
private:
   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 MinDepDistBytes.
-  bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
+  /// vectorization factors by limiting MinDepDistBytes and
+  /// MaxSafeVectorWidthInBits.
+  bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize,
+                                    uint64_t Stride);
 
   /// 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);
 };
 
 class RuntimePointerChecking;

llvm/lib/Analysis/LoopAccessAnalysis.cpp

bool MemoryDepChecker::Dependence::isForward() const {
   case Backward:
   case BackwardVectorizableButPreventsForwarding:
     return false;
   }
   llvm_unreachable("unexpected DepType!");
 }
 
 bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
-                                                    uint64_t TypeByteSize) {
+                                                    uint64_t TypeByteSize,
+                                                    uint64_t Stride) {
   // If loads occur at a distance that is not a multiple of a feasible vector
   // factor store-load forwarding does not take place.
   // Positive dependences might cause troubles because vectorizing them might
   // prevent store-load forwarding making vectorized code run a lot slower.
   //   a[i] = a[i-3] ^ a[i-8];
   //   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
   //   hence on your typical architecture store-load forwarding does not take
   //   place. Vectorizing in such cases does not make sense.
if (MaxVFWithoutSLForwardIssues < 2 * TypeByteSize) {
     LLVM_DEBUG(
         dbgs() << "LAA: Distance " << Distance
                << " that could cause a store-load forwarding conflict\n");
     return true;
   }
 
   if (MaxVFWithoutSLForwardIssues < MinDepDistBytes &&
       MaxVFWithoutSLForwardIssues !=
-          VectorizerParams::MaxVectorWidth * TypeByteSize)
+          VectorizerParams::MaxVectorWidth * TypeByteSize) {
     MinDepDistBytes = MaxVFWithoutSLForwardIssues;
+    // An update to MaxSafeDepDistBytes requires an update to
+    // MaxSafeVectorWidthInBits.
+    uint64_t MaxVF = MinDepDistBytes / (TypeByteSize * Stride);
+    uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
+    MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
+  }
   return false;
 }
 
 void MemoryDepChecker::mergeInStatus(VectorizationSafetyStatus S) {
   if (Status < S)
     Status = S;
 }
 
if (std::abs(Distance) > 0 && Stride > 1 && HasSameSize &&
     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);
     if (IsTrueDataDependence && EnableForwardingConflictDetection &&
-        (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
+        (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize,
+                                      Stride) ||
          !HasSameSize)) {
       LLVM_DEBUG(dbgs() << "LAA: Forward but may prevent st->ld forwarding\n");
       return Dependence::ForwardButPreventsForwarding;
     }
 
     LLVM_DEBUG(dbgs() << "LAA: Dependence is negative\n");
     return Dependence::Forward;
   }
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   // 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.
   MinDepDistBytes =
       std::min(static_cast<uint64_t>(Distance), MinDepDistBytes);
 
-  bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
-  if (IsTrueDataDependence && EnableForwardingConflictDetection &&
-      couldPreventStoreLoadForward(Distance, TypeByteSize))
-    return Dependence::BackwardVectorizableButPreventsForwarding;
-
+  // An update to MaxSafeDepDistBytes requires an update to
+  // MaxSafeVectorWidthInBits.
   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);
+
+  bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
+  if (IsTrueDataDependence && EnableForwardingConflictDetection &&
+      couldPreventStoreLoadForward(Distance, TypeByteSize, Stride))
+    return Dependence::BackwardVectorizableButPreventsForwarding;
+
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
                                    const DenseMap<Value *, const SCEV *> &Strides) {
 
   MinDepDistBytes = -1;