[LAA] Avoid generating RT checks for known deps preventing vectorization.

[fhahn]

Summary

If we found unsafe dependences other than 'unknown', we already know at
compile time that they are unsafe and the runtime checks should always
fail. So we can avoid generating them in those cases.

This should have no negative impact on performance as the runtime checks
that would be created previously should always fail. As a sanity check,
I measured the test-suite, spec2k and spec2k6 and there were no regressions.

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

222–226

When SafeWithRtChecks is added, in next patch, consider renaming the flag or method (slightly), as they will no longer mean exactly the same thing.

Consider renaming ShouldRetryWithRuntimeCheck to something like FoundDependenceForRuntimeCheck; or keep the original name but fold SafeWithRtChecks into the flag, i.e., when turning the flag on check if Status is not Unsafe, and when setting Status to Unsafe turn the flag off.

On second thought, now that Status includes SafeWithRtChecks, this flag seems redundant, and suffice to have

bool shouldRetryWithRuntimeCheck() const {
  return Status == VectorizationSafetyStatus::SafeWithRtChecks;
}

?

[fhahn]

include/llvm/Analysis/LoopAccessAnalysis.h

222–226

Currently, ShouldRetryWithRuntimeCheck is only set when we return Unknown for non-constant distances between dependences. There are other cases where we return Unknown, but do not set it.

By removing it, we would generate runtime checks in more cases. That might be beneficial, but I think should be done in a separate patch.

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

222–226

Agreed, there's no intent to generate runtime checks in more cases, and the ShouldRetryWithRuntimeCheck flag is only set when a dependence having non constant distance is encountered, w/o being unset when any other (unknown) dependence is encountered. In other words, ShouldRetryWithRuntimeCheck means FoundNonConstantDistanceDependence.

Ideally, SafeWithRtChecks would indicate that only (Safe or) Unknown dependences which can be overcome by RT checks exist, as documented above. This however is not easily determined - "ShouldRetry" may fail. Furthermore, isSafeForVectorization(DepType Type) has only the Type to consider, which does not even distinguish between non constant distance dependences and other RT-un/friendly Unknowns; hence the method returns SafeWithRtChecks for all Unknowns. In other words, SafeWithRtChecks means PossiblySafeWithRtChecks.

So conceptually Status has four possible states of interest:

1. Safe --> No need to Retry
2. PossiblySafeWithRtChecks without having found a non constant distance --> Don't Retry, not worth it(?)
3. PossiblySafeWithRtChecks having found a non constant distance --> Retry
4. Unsafe --> Don't Retry, no point

In order to determine the current Status, isDependent() communicates to isSafeForVectorization(DepType Type) a DepType. One possible option is to introduce another 'NonConstantDistance' member to DepType, but that might be intrusive. Another option is to have isDependent() return both a DepType and an indication whether a non constant distance dependence was observed, and determine the Status according to both.

In any case, areDepsSafe() can return a Status instead of a boolean; this could simplify the if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) (although this !CanVecMem seems redundant...).

[fhahn]

include/llvm/Analysis/LoopAccessAnalysis.h

222–226

Agreed. What do you think of proceeding in the following steps:

1. change SafeWithRtChecks to PossiblySafeWithRtChecks in this patch
2. in a follow up patch, add NonConstantDistance to DepType, drop the possibly from PossiblySafeWithRtChecks and return it for NonConstantDistance dependences and Unsafe otherwise
3. in another follow up patch, make areDepsSafe return a Status

IMO splitting it up makes sense, as the follow ups are structural improvements not directly related to the aim of this patch and it makes it easier to pin point where things went wrong, if there are problems.

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

222–226

Sure, this breakdown LGTM. Some comments:

1. When introducing PossiblySafeWithRtChecks, suggest to rename ShouldRetryWithRuntimeCheck to FoundNonConstantDistanceDependence. Or keep the name but turn the flag off whenever Status becomes Unsafe. The original motivation is to avoid having discrepancy between a flag and a method of exactly the same name, where the method no longer simply retrieves the flag.
2. When to introducing NonConstantDistance, if we return Unsafe for all other Unknown's we'll be restricting Retry only to cases where all dependences are (either Safe or) of non constant distance. Seems Retry may succeed for other Unknown dependences today, say of distinct types/strides (but not of distinct address spaces - consider these Unsafe?). Would be good btw to include tests for various Unknown combinations, and perhaps a TODO for cases that have only (Safe and) non-constant distance unknown dependences.
3. Changing the return type of areDepsSafe is indeed orthogonal.

[fhahn]

Rename to PossiblySafeWithRtChecks and FoundNonConstantDistanceDependence.

[fhahn]

include/llvm/Analysis/LoopAccessAnalysis.h

222–226

When to introducing NonConstantDistance, if we return Unsafe for all other Unknown's we'll be restricting Retry only to cases where all dependences are (either Safe or) of non constant distance. Seems Retry may succeed for other Unknown dependences today, say of distinct types/strides (but not of distinct address spaces - consider these Unsafe?). Would be good btw to include tests for various Unknown combinations, and perhaps a TODO for cases that have only (Safe and) non-constant distance unknown dependences.

Yep, before making that change, we have to make sure we do not miss any cases where runtime checks could be succeed. I'll put up a patch once I did that.

[Ayal]

This LGTM, thanks.

include/llvm/Analysis/LoopAccessAnalysis.h

public:
 
   /// Type to keep track of the status of the dependence check. The order of
   /// the elements is important and has to be from most permissive to least
   /// permissive.
   enum class VectorizationSafetyStatus {
     // Can vectorize safely without RT checks. All dependences are known to be
     // safe.
     Safe,
-    // Cannot vectorize due to unsafe or unknown dependencies.
+    // Can possibly vectorize with RT checks to overcome unknown dependencies.
+    PossiblySafeWithRtChecks,
+    // Cannot vectorize due to known unsafe dependencies.
     Unsafe,
   };
 
   /// Dependece between memory access instructions.
   struct Dependence {
     /// The type of the dependence.
     enum DepType {
       // No dependence.
struct Dependence {
     /// Print the dependence.  \p Instr is used to map the instruction
     /// indices to instructions.
     void print(raw_ostream &OS, unsigned Depth,
                const SmallVectorImpl<Instruction *> &Instrs) const;
   };
 
   MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
       : PSE(PSE), InnermostLoop(L), AccessIdx(0), MaxSafeRegisterWidth(-1U),
-        ShouldRetryWithRuntimeCheck(false),
+        FoundNonConstantDistanceDependence(false),
         Status(VectorizationSafetyStatus::Safe), RecordDependences(true) {}
 
   /// Register the location (instructions are given increasing numbers)
   /// of a write access.
   void addAccess(StoreInst *SI) {
     Value *Ptr = SI->getPointerOperand();
     Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
     InstMap.push_back(SI);
public:
   /// the accesses safely with.
   uint64_t getMaxSafeDepDistBytes() { 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 getMaxSafeRegisterWidth() const { return MaxSafeRegisterWidth; }
 
   /// In same cases when the dependency check fails we can still
   /// vectorize the loop with a dynamic array access check.
-  bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; }
+  bool shouldRetryWithRuntimeCheck() const {
+    return FoundNonConstantDistanceDependence &&
+           Status == VectorizationSafetyStatus::PossiblySafeWithRtChecks;
+  }
 
   /// Returns the memory dependences.  If null is returned we exceeded
   /// the MaxDependences threshold and this information is not
   /// available.
   const SmallVectorImpl<Dependence> *getDependences() const {
     return RecordDependences ? &Dependences : nullptr;
   }
 
private:
   /// 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 MaxSafeRegisterWidth;
 
   /// If we see a non-constant dependence distance we can still try to
   /// vectorize this loop with runtime checks.
-  bool ShouldRetryWithRuntimeCheck;
+  bool FoundNonConstantDistanceDependence;
 
   /// Result of the dependence checks, indicating whether the checked
-  /// dependences are safe for vectorization or not.
+  /// dependences are safe for vectorization, require RT checks or are known to
+  /// be unsafe.
   VectorizationSafetyStatus Status;
 
   //// True if Dependences reflects the dependences in the
   //// loop.  If false we exceeded MaxDependences and
   //// Dependences is invalid.
   bool RecordDependences;
 
   /// Memory dependences collected during the analysis.  Only valid if
private:
   /// 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.
   bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
 
   /// Updates the current safety status with \p S. We can go from Safe to
-  /// to Unsafe.
+  /// either PossiblySafeWithRtChecks or Unsafe and from
+  /// PossiblySafeWithRtChecks to Unsafe.
   void mergeInStatus(VectorizationSafetyStatus S);
 };
 
 /// Holds information about the memory runtime legality checks to verify
 /// that a group of pointers do not overlap.
 class RuntimePointerChecking {
 public:
   struct PointerInfo {

lib/Analysis/LoopAccessAnalysis.cpp

void RuntimePointerChecking::groupChecks(
   //
   // Here grouping gives a check of (5000, 5000 + 1000 * m) against
   // (0, 10000) which is always false. However, if m is 1, there is no
   // dependence. Not grouping the checks for a[i] and a[i + 9000] allows
   // us to perform an accurate check in this case.
   //
   // The above case requires that we have an UnknownDependence between
   // accesses to the same underlying object. This cannot happen unless
-  // ShouldRetryWithRuntimeCheck is set, and therefore UseDependencies
+  // FoundNonConstantDistanceDependence is set, and therefore UseDependencies
   // is also false. In this case we will use the fallback path and create
   // separate checking groups for all pointers.
 
   // If we don't have the dependency partitions, construct a new
   // checking pointer group for each pointer. This is also required
   // for correctness, because in this case we can have checking between
   // pointers to the same underlying object.
   if (!UseDependencies) {
public:
   void buildDependenceSets() {
     processMemAccesses();
   }
 
   /// Initial processing of memory accesses determined that we need to
   /// perform dependency checking.
   ///
   /// Note that this can later be cleared if we retry memcheck analysis without
-  /// dependency checking (i.e. ShouldRetryWithRuntimeCheck).
+  /// dependency checking (i.e. FoundNonConstantDistanceDependence).
   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
 
   /// We decided that no dependence analysis would be used.  Reset the state.
   void resetDepChecks(MemoryDepChecker &DepChecker) {
     CheckDeps.clear();
     DepChecker.clearDependences();
   }
 
private:
   /// dependence check.
   MemoryDepChecker::DepCandidates &DepCands;
 
   /// Initial processing of memory accesses determined that we may need
   /// to add memchecks.  Perform the analysis to determine the necessary checks.
   ///
   /// Note that, this is different from isDependencyCheckNeeded.  When we retry
   /// memcheck analysis without dependency checking
-  /// (i.e. ShouldRetryWithRuntimeCheck), isDependencyCheckNeeded is cleared
-  /// while this remains set if we have potentially dependent accesses.
+  /// (i.e. FoundNonConstantDistanceDependence), isDependencyCheckNeeded is
+  /// cleared while this remains set if we have potentially dependent accesses.
   bool IsRTCheckAnalysisNeeded;
 
   /// The SCEV predicate containing all the SCEV-related assumptions.
   PredicatedScalarEvolution &PSE;
 };
 
 } // end anonymous namespace
 

 MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
   switch (Type) {
   case NoDep:
   case Forward:
   case BackwardVectorizable:
     return VectorizationSafetyStatus::Safe;
 
   case Unknown:
+    return VectorizationSafetyStatus::PossiblySafeWithRtChecks;
   case ForwardButPreventsForwarding:
   case Backward:
   case BackwardVectorizableButPreventsForwarding:
     return VectorizationSafetyStatus::Unsafe;
   }
   llvm_unreachable("unexpected DepType!");
 }
 
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   if (!C) {
     if (TypeByteSize == DL.getTypeAllocSize(BTy) &&
         isSafeDependenceDistance(DL, *(PSE.getSE()),
                                  *(PSE.getBackedgeTakenCount()), *Dist, Stride,
                                  TypeByteSize))
       return Dependence::NoDep;
 
     LLVM_DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
-    ShouldRetryWithRuntimeCheck = true;
+    FoundNonConstantDistanceDependence = true;
     return Dependence::Unknown;
   }
 
   const APInt &Val = C->getAPInt();
   int64_t Distance = Val.getSExtValue();
 
   // Attempt to prove strided accesses independent.
   if (std::abs(Distance) > 0 && Stride > 1 && ATy == BTy &&

test/Transforms/LoopVectorize/runtime-check.ll

for.body:
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond = icmp eq i64 %iv.next, %n
   br i1 %exitcond, label %loopexit, label %for.body
 
 loopexit:
   ret void
 }
 
-; Check we do generate unnecessary runtime checks. They will always fail.
+; Check we do not generate runtime checks if we found a known dependence preventing
+; vectorization. In this case, it is a read of c[i-1] followed by a write of c[i].
+; The runtime checks would always fail.
 
 ; void test_runtime_check2(float *a, float b, unsigned offset, unsigned offset2, unsigned n, float *c) {
 ;   for (unsigned i = 1; i < n; i++) {
 ;     a[i+o1] += a[i+o2] + b;
 ;     c[i] = c[i-1] + b;
 ;   }
 ; }
 ;
 ; CHECK-LABEL: test_runtime_check2
-; CHECK:      <4 x float>
+; CHECK-NOT:      <4 x float>
 define void @test_runtime_check2(float* %a, float %b, i64 %offset, i64 %offset2, i64 %n, float* %c) {
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
   %ind.sum = add i64 %iv, %offset
   %arr.idx = getelementptr inbounds float, float* %a, i64 %ind.sum