[LAA] Introduce enum for vectorization safety status (NFC).

[fhahn]

Summary

This patch adds a VectorizationSafetyStatus enum, which will be extended
in a follow up patch to distinguish between 'safe with runtime checks'
and 'known unsafe' dependences.

[anemet]

Hi Florian, are you saying that in this case (known unsafe dep) we would still vectorize the loop (and always fail at run-time)?

[fhahn]

In D54892#1308227, @anemet wrote:

Hi Florian, are you saying that in this case (known unsafe dep) we would still vectorize the loop (and always fail at run-time)?

Without this patch, yes if the loop has at least one unknown dependence and a non-vectorizable dependence, as in the test case: %l2 - store %ad is unknown, as the they have non constant offsets, %lc - store %vc is known non vectorizable.

[anemet]

include/llvm/Analysis/LoopAccessAnalysis.h

212

What is the actual semantical difference between RuntimeChecksFeasible and ShouldRetryWithRuntimeCheck?

In other words, can't we just clear ShouldRetryWithRuntimeCheck when we see an unsafe known dep?

[Ayal]

lib/Analysis/LoopAccessAnalysis.cpp

1620

Right, but comment best be placed elsewhere.

1661

Suggest to add and call Dependence::isUnsafeForVectorization(Type) which will determine if there's a dependence that cannot be overcome by runtime checks. Perhaps find a better name - it implies but is not equivalent to !isSafeForVectorization(Type).

Then bail-out as soon as such a dependence is encountered; there's no point in continuing to RecordDependences.

This could alternatively be done here as follows, by leveraging ShouldRetryWithRuntimeCheck, which essentially already indicates if runtime checks may be useful (but then early bail-out is necessary):

if (!DepSafe && Type != Dependence::Unknown) {
  ShouldRetryWithRuntimeCheck = false;
  RecordDependences = false;
  Dependences.clear();
  LLVM_DEBUG(dbgs() << "Found unsafe dependence\n");
  return false;
}

[fhahn]

Thanks Adam and Ayal, responses inline. I would be happy to update the patch to do an early bailout, but I am not sure if that is desirable, as it might have a negative impact on the reports generated.

include/llvm/Analysis/LoopAccessAnalysis.h

212

At the moment, they refer to slightly different things: RuntimeChecksFeasible is true iff we did not find any dependences making RT ineffective, ShouldRetryWithRuntimeChecks is true iff we encountered an unknown dependence where RT checks might help. Additionally we only set ShouldRetryWithRuntimeChecks for some Unknown dependences. The reason I went with an additional flag was that it seemed easier to see what is going on.

Currently clearing ShouldRetryWithRuntimeCheck would not be enough I think, because we keep checking dependences and we could set ShouldRetryWithRuntimeChecks again for later dependences. Changing the code to bail out early would help (see discussion below)

lib/Analysis/LoopAccessAnalysis.cpp

1661

Suggest to add and call Dependence::isUnsafeForVectorization(Type) which will determine if there's a dependence that cannot be overcome by runtime checks. Perhaps find a better name - it implies but is not equivalent to !isSafeForVectorization(Type).

Thanks, I'll add a special function. One thing I just realized is that we only should do RT checks for some Unknown dependences. It might be worth adding a new type UnknownRTCheckable or something, to even better distinguish when RT checks are profitable.

Then bail-out as soon as such a dependence is encountered; there's no point in continuing to RecordDependences.

The reason I did not go for an early bailout is that we keep recording dependences even if we found some unsafe ones, I suppose for better reporting. If we go for an early bailout in this patch, this seems slightly inconsistent and it might be worth changing to an early bailout in case of unsafe deps too first?

[anemet]

include/llvm/Analysis/LoopAccessAnalysis.h

212

Even then I would prefer a single three-state value rather than a two booleans, e.g. something like: true, false and unfeasible/failed or some such.

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

212

Agreed it sounds like RetryWithRuntimeChecks could be enum'd to indicate

1. Should: unknown dependencies exist where RT checks might help;
2. Don't - Won'tHelpTo: dependencies exists which even RT checks cannot help; or
3. Don't - NoNeedTo: all's well w/o RT checks.

OTOH, if we encounter a dependence that prevents vectorization and can't bail out on the spot (see below), we could raise an UnsafeForVectorization flag instead. Or perhaps SafeForVectorization/areDepsSafe() should be/return the single three-state value, e.g., something like: Safe, Unsafe, SafeWithRT which correspond to (3), (2), (1) respectively? Start optimistically Safe, move to SafeWithRT only from Safe mode, keep Unsafe is sticky.

(BTW, isSafeForVectorization() seems to be dead and should be removed. The return value of areDepsSafe() is used instead.)

lib/Analysis/LoopAccessAnalysis.cpp

1661

Then bail-out as soon as such a dependence is encountered; there's no point in continuing to RecordDependences.

Ahh, that's true for LV, but not for LoopDistributor which would like to obtain all the dependencies in order to separate the unsafe ones...

[fhahn]

Thanks, I'll update the patch in a bit to use a 3 value enum as suggested.

[fhahn]

Updated to add a StatusTy enum class with 3 values: Safe, SafeWithRTChecks and Unsafe. Please let me know if that is along the lines you were thinking. I am not sure about the naming in the patch and would appreciate any suggestions.

[fhahn]

I'll address the unused functions in a separate commit.

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

102

// Can vectorize safely without RT checks. All dependences are known to be safe.

104

// Can vectorize with RT checks to overcome unknown dependencies.

106

// Cannot vectorize due to known unsafe dependencies.
, "unknown" is considered SafeWithRtChecks, right?

197

Use this isSafeForVectorization() getter method where the SafeForVectorization flag was read before, below, instead of replacing it with (inlined) comparisons of Status == StatusTy::Safe.

This will also make it useful (though it could be made protected/private).

286

Perhaps use a more specific name; e.g., VectorizationSafetyStatus?

lib/Analysis/LoopAccessAnalysis.cpp

1232

Consider splitting into an NFC patch which has only Safe and Unsafe states, with the test showing it currently vectorizes; plus a separate patch adding SafeWithRtChecks state with updated test.

1321

Could this be done as follows, based on the numerical values of the enum, properly sorted as now?

if (Status < S)
  Status = S;

[fhahn]

Thanks, Ayal, I've addressed the comments and stripped the SafeWithRtChecks from this patch.

[fhahn]

include/llvm/Analysis/LoopAccessAnalysis.h

197

I'll address visibility and unused functions as follow up commits.

lib/Analysis/LoopAccessAnalysis.cpp

1321

Nice, I didn't know enum classes provide a default implementation for that.

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

100

Nice, I didn't know enum classes provide a default implementation for that.

Yeah, they have numerical values, which btw could also be specified.
Would be good to note that the order of elements in the enum is important.

209

This is redundant, as ShouldRetryWithRuntimeCheck implies Unsafe. I.e., can assert !(Should && Safe).
When SafeWithRtChecks is added, in next patch, consider renaming the flag or method (slightly), as they will no longer mean exactly the same thing.

lib/Analysis/LoopAccessAnalysis.cpp

1679

!isSafeForVectorization() ?

[fhahn]

Addressed comments, thanks!

include/llvm/Analysis/LoopAccessAnalysis.h

209

Yep, I dropped all changes to this function from this patch.

[Ayal]

LGTM, thanks.

include/llvm/Analysis/LoopAccessAnalysis.h

107

This comment is accurate once SafeWithRtChecks is added, in upcoming patch.

[fhahn]

include/llvm/Analysis/LoopAccessAnalysis.h

107

Thanks, I'll slightly tweak the comment before committing.

include/llvm/Analysis/LoopAccessAnalysis.h

 ///
 class MemoryDepChecker {
 public:
   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
   typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
   /// Set of potential dependent memory accesses.
   typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
 
   /// Dependece between memory access instructions.
   struct Dependence {
     /// The type of the dependence.
     enum DepType {
       // No dependence.
       NoDep,
       // We couldn't determine the direction or the distance.
       Unknown,
       // Lexically forward.
       //
       // FIXME: If we only have loop-independent forward dependences (e.g. a
       // read and write of A[i]), LAA will locally deem the dependence "safe"
       // without querying the MemoryDepChecker.  Therefore we can miss
       // enumerating loop-independent forward dependences in
       // getDependences.  Note that as soon as there are different
       // indices used to access the same array, the MemoryDepChecker *is*
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), SafeForVectorization(true),
-        RecordDependences(true) {}
+        ShouldRetryWithRuntimeCheck(false), RuntimeChecksFeasible(true),
+        SafeForVectorization(true), 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);
     ++AccessIdx;
   }
 
   /// Register the location (instructions are given increasing numbers)
   /// of a write access.
   void addAccess(LoadInst *LI) {
     Value *Ptr = LI->getPointerOperand();
     Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
     InstMap.push_back(LI);
     ++AccessIdx;
   }
 
-  /// Check whether the dependencies between the accesses are safe.
+  /// Check whether the dependencies between the accesses are safe and whether
+  /// runtime checks are feasible.
   ///
   /// Only checks sets with elements in \p CheckDeps.
   bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
                    const ValueToValueMap &Strides);
 
   /// No memory dependence was encountered that would inhibit
   /// vectorization.
   bool isSafeForVectorization() const { return SafeForVectorization; }
 
   /// The maximum number of bytes of a vector register we can vectorize
   /// 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; }
+  /// In some cases when the dependency check fails we can still vectorize
+  /// the loop with a dynamic array access check. If we already found
+  /// a dependence preventing vectorization, we do not retry with runtime
+  /// checks.
+  bool shouldRetryWithRuntimeCheck() {
+    return RuntimeChecksFeasible && ShouldRetryWithRuntimeCheck;
+  }
 
   /// 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:
   /// 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;
 
+  /// If we see a non-unknown unsafe dependence, there is no point in generating
+  /// runtime checks.
+  bool RuntimeChecksFeasible;
+
   /// No memory dependence was encountered that would inhibit
   /// vectorization.
   bool SafeForVectorization;
 
   //// 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
   /// RecordDependences is true.
   SmallVector<Dependence, 8> Dependences;
 
   /// Check whether there is a plausible dependence between the two

lib/Analysis/LoopAccessAnalysis.cpp

 bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
   switch (Type) {
   case NoDep:
   case Forward:
   case BackwardVectorizable:
     return true;
 
   case Unknown:
   case ForwardButPreventsForwarding:
   case Backward:
   case BackwardVectorizableButPreventsForwarding:
     return false;
   }
   llvm_unreachable("unexpected DepType!");
 }
 
 bool MemoryDepChecker::Dependence::isBackward() const {
bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
       MaxVFWithoutSLForwardIssues !=
           VectorizerParams::MaxVectorWidth * TypeByteSize)
     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
   return false;
 }
 
 /// Given a non-constant (unknown) dependence-distance \p Dist between two
 /// memory accesses, that have the same stride whose absolute value is given
 /// in \p Stride, and that have the same type size \p TypeByteSize,
 /// in a loop whose takenCount is \p BackedgeTakenCount, check if it is
 /// possible to prove statically that the dependence distance is larger
 /// than the range that the accesses will travel through the execution of
 /// the loop. If so, return true; false otherwise. This is useful for
 /// example in loops such as the following (PR31098):
 ///     for (i = 0; i < D; ++i) {
 ///                = out[i];
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
   MaxSafeRegisterWidth = std::min(MaxSafeRegisterWidth, MaxVFInBits);
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoList &CheckDeps,
                                    const ValueToValueMap &Strides) {
-
+  // Runtime checks are only feasible if only unknown dependences prevent
+  // vectorization.
   MaxSafeDepDistBytes = -1;
   SmallPtrSet<MemAccessInfo, 8> Visited;
   for (MemAccessInfo CurAccess : CheckDeps) {
     if (Visited.count(CurAccess))
       continue;
 
     // Get the relevant memory access set.
     EquivalenceClasses<MemAccessInfo>::iterator I =
while (AI != AE) {
             auto B = std::make_pair(&*OI, *I2);
 
             assert(*I1 != *I2);
             if (*I1 > *I2)
               std::swap(A, B);
 
             Dependence::DepType Type =
                 isDependent(*A.first, A.second, *B.first, B.second, Strides);
-            SafeForVectorization &= Dependence::isSafeForVectorization(Type);
+            bool DepSafe = Dependence::isSafeForVectorization(Type);
+            SafeForVectorization &= DepSafe;
+            // Runtime checks are only feasible, if all unsafe dependencies are
+            // unknown. For other unsafe deps, we already know they will fail
+            // the runtime checks at compile time.
+            RuntimeChecksFeasible &= Type == Dependence::Unknown || DepSafe;
 
             // Gather dependences unless we accumulated MaxDependences
             // dependences.  In that case return as soon as we find the first
             // unsafe dependence.  This puts a limit on this quadratic
             // algorithm.
             if (RecordDependences) {
               if (Type != Dependence::NoDep)
                 Dependences.push_back(Dependence(A.second, B.second, Type));
 
               if (Dependences.size() >= MaxDependences) {
                 RecordDependences = false;
                 Dependences.clear();
                 LLVM_DEBUG(dbgs()
                            << "Too many dependences, stopped recording\n");
               }
             }
-            if (!RecordDependences && !SafeForVectorization)
+            // We do not generate runtime checks for accesses with constant
+            // strides, so without investigating all dependences, we cannot
+            // be sure runtime checks are safe.
+            if (!RecordDependences && !SafeForVectorization) {
+              RuntimeChecksFeasible = false;
               return false;
             }
+          }
         ++OI;
       }
       AI++;
     }
   }
 
   LLVM_DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n");
   return SafeForVectorization;

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 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-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
+  %l1 = load float, float* %arr.idx, align 4
+  %ind.sum2 = add i64 %iv, %offset2
+  %arr.idx2 = getelementptr inbounds float, float* %a, i64 %ind.sum2
+  %l2 = load float, float* %arr.idx2, align 4
+  %m = fmul fast float %b, %l2
+  %ad = fadd fast float %l1, %m
+  store float %ad, float* %arr.idx, align 4
+  %c.ind = add i64 %iv, -1
+  %c.idx = getelementptr inbounds float, float* %c, i64 %c.ind
+  %lc = load float, float* %c.idx, align 4
+  %vc = fadd float %lc, 1.0
+  %c.idx2 = getelementptr inbounds float, float* %c, i64 %iv
+  store float %vc, float* %c.idx2
+  %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: !9 = !DILocation(line: 101, column: 1, scope: !{{.*}})
 
 !llvm.module.flags = !{!0, !1}
 !llvm.dbg.cu = !{!9}
 !0 = !{i32 2, !"Dwarf Version", i32 4}
 !1 = !{i32 2, !"Debug Info Version", i32 3}
 
 !2 = !{}