[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 ↗

(On Diff #175220)

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 ↗

(On Diff #175220)

Right, but comment best be placed elsewhere.

1661 ↗

(On Diff #175220)

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 ↗

(On Diff #175220)

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 ↗

(On Diff #175220)

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 ↗

(On Diff #175220)

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 ↗

(On Diff #175220)

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 ↗

(On Diff #175220)

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 ↗

(On Diff #178179)

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

104 ↗

(On Diff #178179)

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

106 ↗

(On Diff #178179)

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

206 ↗

(On Diff #178179)

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).

287 ↗

(On Diff #178179)

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

lib/Analysis/LoopAccessAnalysis.cpp

1233 ↗

(On Diff #178179)

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.

1323 ↗

(On Diff #178179)

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

206 ↗

(On Diff #178179)

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

lib/Analysis/LoopAccessAnalysis.cpp

1323 ↗

(On Diff #178179)

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

[Ayal]

include/llvm/Analysis/LoopAccessAnalysis.h

100 ↗

(On Diff #178567)

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.

221 ↗

(On Diff #178567)

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 ↗

(On Diff #178567)

!isSafeForVectorization() ?

[fhahn]

Addressed comments, thanks!

include/llvm/Analysis/LoopAccessAnalysis.h

221 ↗

(On Diff #178567)

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

[Ayal]

LGTM, thanks.

include/llvm/Analysis/LoopAccessAnalysis.h

107 ↗

(On Diff #178762)

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

[fhahn]

include/llvm/Analysis/LoopAccessAnalysis.h

107 ↗

(On Diff #178762)

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

llvm/trunk/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;
 
+  /// 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.
+    Unsafe,
+  };
+
   /// 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,
Dependence(unsigned Source, unsigned Destination, DepType Type)
         : Source(Source), Destination(Destination), Type(Type) {}
 
     /// Return the source instruction of the dependence.
     Instruction *getSource(const LoopAccessInfo &LAI) const;
     /// Return the destination instruction of the dependence.
     Instruction *getDestination(const LoopAccessInfo &LAI) const;
 
     /// Dependence types that don't prevent vectorization.
-    static bool isSafeForVectorization(DepType Type);
+    static VectorizationSafetyStatus isSafeForVectorization(DepType Type);
 
     /// Lexically forward dependence.
     bool isForward() const;
     /// Lexically backward dependence.
     bool isBackward() const;
 
     /// May be a lexically backward dependence type (includes Unknown).
     bool isPossiblyBackward() const;
 
     /// 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),
+        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);
     ++AccessIdx;
public:
   /// Check whether the dependencies between the accesses are safe.
   ///
   /// 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; }
+  bool isSafeForVectorization() const {
+    return Status == VectorizationSafetyStatus::Safe;
+  }
 
   /// 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; }
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;
 
-  /// No memory dependence was encountered that would inhibit
-  /// vectorization.
-  bool SafeForVectorization;
+  /// Result of the dependence checks, indicating whether the checked
+  /// dependences are safe for vectorization or not.
+  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
   /// RecordDependences is true.
Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
                                   const ValueToValueMap &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.
   bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
+
+  /// Updates the current safety status with \p S. We can go from Safe to
+  /// 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 {
     /// Holds the pointer value that we need to check.

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
 
   // Otherwise compute the distance with SCEV between the base pointers.
   const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
   const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
   const SCEV *X = SE.getAddExpr(PtrSCEVA, BaseDelta);
   return X == PtrSCEVB;
 }
 
-bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
+MemoryDepChecker::VectorizationSafetyStatus
+MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
   switch (Type) {
   case NoDep:
   case Forward:
   case BackwardVectorizable:
-    return true;
+    return VectorizationSafetyStatus::Safe;
 
   case Unknown:
   case ForwardButPreventsForwarding:
   case Backward:
   case BackwardVectorizableButPreventsForwarding:
-    return false;
+    return VectorizationSafetyStatus::Unsafe;
   }
   llvm_unreachable("unexpected DepType!");
 }
 
 bool MemoryDepChecker::Dependence::isBackward() const {
   switch (Type) {
   case NoDep:
   case Forward:
bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
 
   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
       MaxVFWithoutSLForwardIssues !=
           VectorizerParams::MaxVectorWidth * TypeByteSize)
     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
   return false;
 }
 
+void MemoryDepChecker::mergeInStatus(VectorizationSafetyStatus S) {
+  if (Status < S)
+    Status = S;
+}
+
 /// 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):
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);
+            mergeInStatus(Dependence::isSafeForVectorization(Type));
 
             // 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)
+            if (!RecordDependences && !isSafeForVectorization())
               return false;
           }
         ++OI;
       }
       AI++;
     }
   }
 
   LLVM_DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n");
-  return SafeForVectorization;
+  return isSafeForVectorization();
 }
 
 SmallVector<Instruction *, 4>
 MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
   MemAccessInfo Access(Ptr, isWrite);
   auto &IndexVector = Accesses.find(Access)->second;
 
   SmallVector<Instruction *, 4> Insts;

llvm/trunk/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.
+
+; 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>
+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 = !{}