[LAA] Fix estimation of number of memchecks

[sbaranga]

Summary

We need to add a runtime memcheck for pair of accesses (x,y) where at least one of x and y
are writes.

Assuming we have w writes and r reads, currently this number is estimated as being
w* (w+r-1). This estimation will count (write,write) pairs twice and will overestimate
the number of checks required.

This change adds a getNumberOfChecks method to RuntimePointerCheck, which
will count the number of runtime checks needed (similar in implementation to
needsAnyChecking) and uses it to produce the correct number of runtime checks.

[mzolotukhin]

A minor comment inline:

lib/Analysis/LoopAccessAnalysis.cpp

1212–1213

Would it be more readable if we write this as

CanDoRt = !NeedRTCheck || canCheckPtrAtRT(...)

?

[anemet]

With this change I don't think there is a reason to cache NumComparisons anymore. What do you think?

Specifically I mean:

include/llvm/Analysis/LoopAccessAnalysis.h

390–395

I think that this guy should now forward to getNumberOfChecks() and probably take a partition (by default nullptr) parameter.

469–470

To avoid confusion we should probably remove this.

lib/Analysis/LoopAccessAnalysis.cpp

228–234

I don't think there is a reason for this function to return NumComparisons now. It should probably return NeedRTCheck instead (used in the caller).

[sbaranga]

Removed the caching of getNumberOfCheck and updated the API to not return it as part of canCheckPtrAtRT.
Removed some dead code (NumReadPtrChecks and NumWritePtrChecks are no longer needed).

NeedRTCheck is now returned by canCheckPtrAtRT. I've also changed the logic that computes NeedRTChecks according to Michaels comment to make it more readable, and that change ended up being in canCheckPtrAtRT.

[sbaranga]

lib/Analysis/LoopAccessAnalysis.cpp

1212–1213

Yes, that looks better. I've included the change in the new revision.

[sbaranga]

In D10217#183190, @anemet wrote:

With this change I don't think there is a reason to cache NumComparisons anymore. What do you think?

Specifically I mean:

Yes, that makes sense. I've removed it in the newer revision. I've also found some other code that was made dead by the interface changes and removed it as well.

[mzolotukhin]

The patch LGTM.

Minor nitpicks:

lib/Analysis/LoopAccessAnalysis.cpp

356

This looks a bit confusing (probably, because of the variable names) - why do we need a RT check if we can't add them? A comment would be helpful here.

1223–1224

The debug message no longer needs "if needed" part.

And by the way, why do we need this change? To me the original and changed versions seem equivalent except that we won't print any message if NeedRTCheck==false and CanDoRT==true .

[anemet]

Very nice! LGTM.

lib/Analysis/LoopAccessAnalysis.cpp

1216–1219

Looks like you only use NumComparison in the DEBUG message now. With a release compiler this will probably give you a warning.

[sbaranga]

Thanks both! I'll commit this on Monday (with the fixed remaining issues).

lib/Analysis/LoopAccessAnalysis.cpp

1223–1224

Good point. I'll remove this from the final version.

[sbaranga]

Removed NumComparisons and replaced it with a call to
getNumberOfChecks().

Added comments to explain the NeedRTCheck logic.

Keep the original behaviour of the
"We can perform a memory runtime check if needed" debug
message.

include/llvm/Analysis/LoopAccessAnalysis.h

struct RuntimePointerCheck {
     /// case omit checks between pointers belonging to the same partition.
     bool needsChecking(unsigned I, unsigned J,
                        const SmallVectorImpl<int> *PtrPartition) const;
 
     /// \brief Return true if any pointer requires run-time checking according
     /// to needsChecking.
     bool needsAnyChecking(const SmallVectorImpl<int> *PtrPartition) const;
 
+    /// \brief Returns the number of run-time checks required according to
+    /// needsChecking.
+    unsigned getNumberOfChecks(const SmallVectorImpl<int> *PtrPartition) const;
+
     /// \brief Print the list run-time memory checks necessary.
     ///
     /// If \p PtrPartition is set, it contains the partition number for
     /// pointers (-1 if the pointer belongs to multiple partitions).  In this
     /// case omit checks between pointers belonging to the same partition.
     void print(raw_ostream &OS, unsigned Depth = 0,
                const SmallVectorImpl<int> *PtrPartition = nullptr) const;
 
public:
   /// Return true we can analyze the memory accesses in the loop and there are
   /// no memory dependence cycles.
   bool canVectorizeMemory() const { return CanVecMem; }
 
   const RuntimePointerCheck *getRuntimePointerCheck() const {
     return &PtrRtCheck;
   }
 
   /// \brief Number of memchecks required to prove independence of otherwise
   /// may-alias pointers.
-  unsigned getNumRuntimePointerChecks() const { return NumComparisons; }
+  unsigned getNumRuntimePointerChecks(
+    const SmallVectorImpl<int> *PtrPartition = nullptr) const {
+    return PtrRtCheck.getNumberOfChecks(PtrPartition);
+  }
 
   /// Return true if the block BB needs to be predicated in order for the loop
   /// to be vectorized.
   static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
                                     DominatorTree *DT);
 
   /// Returns true if the value V is uniform within the loop.
   bool isUniform(Value *V) const;
private:
 
   /// We need to check that all of the pointers in this list are disjoint
   /// at runtime.
   RuntimePointerCheck PtrRtCheck;
 
   /// \brief the Memory Dependence Checker which can determine the
   /// loop-independent and loop-carried dependences between memory accesses.
   MemoryDepChecker DepChecker;
 
-  /// \brief Number of memchecks required to prove independence of otherwise
-  /// may-alias pointers
-  unsigned NumComparisons;
-
   Loop *TheLoop;
   ScalarEvolution *SE;
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
 
   unsigned NumLoads;

lib/Analysis/LoopAccessAnalysis.cpp

for (unsigned J = I + 1; J < NumPointers; ++J)
         OS << "\n";
         OS.indent(Depth + 2) << *Pointers[J];
         if (PtrPartition)
           OS << " (Partition: " << (*PtrPartition)[J] << ")";
         OS << "\n";
       }
 }
 
-bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking(
+unsigned LoopAccessInfo::RuntimePointerCheck::getNumberOfChecks(
     const SmallVectorImpl<int> *PtrPartition) const {
   unsigned NumPointers = Pointers.size();
+  unsigned CheckCount = 0;
 
   for (unsigned I = 0; I < NumPointers; ++I)
     for (unsigned J = I + 1; J < NumPointers; ++J)
       if (needsChecking(I, J, PtrPartition))
-        return true;
-  return false;
+        CheckCount++;
+  return CheckCount;
+}
+
+bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking(
+    const SmallVectorImpl<int> *PtrPartition) const {
+  return getNumberOfChecks(PtrPartition) != 0;
 }
 
 namespace {
 /// \brief Analyses memory accesses in a loop.
 ///
 /// Checks whether run time pointer checks are needed and builds sets for data
 /// dependence checking.
 class AccessAnalysis {
public:
 
   /// \brief Register a store.
   void addStore(AliasAnalysis::Location &Loc) {
     Value *Ptr = const_cast<Value*>(Loc.Ptr);
     AST.add(Ptr, AliasAnalysis::UnknownSize, Loc.AATags);
     Accesses.insert(MemAccessInfo(Ptr, true));
   }
 
   /// \brief Check whether we can check the pointers at runtime for
-  /// non-intersection.
+  /// non-intersection. Returns true when we have 0 pointers
+  /// (a check on 0 pointers for non-intersection will always return true).
   bool canCheckPtrAtRT(LoopAccessInfo::RuntimePointerCheck &RtCheck,
-                       unsigned &NumComparisons, ScalarEvolution *SE,
-                       Loop *TheLoop, const ValueToValueMap &Strides,
+                       bool &NeedRTCheck, ScalarEvolution *SE, Loop *TheLoop,
+                       const ValueToValueMap &Strides,
                        bool ShouldCheckStride = false);
 
   /// \brief Goes over all memory accesses, checks whether a RT check is needed
   /// and builds sets of dependent accesses.
   void buildDependenceSets() {
     processMemAccesses();
   }
 
   bool isRTCheckNeeded() { return IsRTCheckNeeded; }
static bool hasComputableBounds(ScalarEvolution *SE,
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
   if (!AR)
     return false;
 
   return AR->isAffine();
 }
 
 bool AccessAnalysis::canCheckPtrAtRT(
-    LoopAccessInfo::RuntimePointerCheck &RtCheck, unsigned &NumComparisons,
+    LoopAccessInfo::RuntimePointerCheck &RtCheck, bool &NeedRTCheck,
     ScalarEvolution *SE, Loop *TheLoop, const ValueToValueMap &StridesMap,
     bool ShouldCheckStride) {
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
   bool CanDoRT = true;
 
+  NeedRTCheck = false;
+  if (!IsRTCheckNeeded) return true;
+
   bool IsDepCheckNeeded = isDependencyCheckNeeded();
-  NumComparisons = 0;
 
   // We assign a consecutive id to access from different alias sets.
   // Accesses between different groups doesn't need to be checked.
   unsigned ASId = 1;
   for (auto &AS : AST) {
-    unsigned NumReadPtrChecks = 0;
-    unsigned NumWritePtrChecks = 0;
-
     // We assign consecutive id to access from different dependence sets.
     // Accesses within the same set don't need a runtime check.
     unsigned RunningDepId = 1;
     DenseMap<Value *, unsigned> DepSetId;
 
     for (auto A : AS) {
       Value *Ptr = A.getValue();
       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
       MemAccessInfo Access(Ptr, IsWrite);
 
-      if (IsWrite)
-        ++NumWritePtrChecks;
-      else
-        ++NumReadPtrChecks;
-
       if (hasComputableBounds(SE, StridesMap, Ptr) &&
           // When we run after a failing dependency check we have to make sure
           // we don't have wrapping pointers.
           (!ShouldCheckStride ||
            isStridedPtr(SE, Ptr, TheLoop, StridesMap) == 1)) {
         // The id of the dependence set.
         unsigned DepId;
 
for (auto A : AS) {
 
         DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
       } else {
         DEBUG(dbgs() << "LAA: Can't find bounds for ptr:" << *Ptr << '\n');
         CanDoRT = false;
       }
     }
 
-    if (IsDepCheckNeeded && CanDoRT && RunningDepId == 2)
-      NumComparisons += 0; // Only one dependence set.
-    else {
-      NumComparisons += (NumWritePtrChecks * (NumReadPtrChecks +
-                                              NumWritePtrChecks - 1));
-    }
-
     ++ASId;
   }
 
+  // We need a runtime check if there are any accesses that need checking.
+  // However, some accesses cannot be checked (for example because we
+  // can't determine their bounds). In these cases we would need a check
+  // but wouldn't be able to add it.
+  NeedRTCheck = !CanDoRT || RtCheck.needsAnyChecking(nullptr);
+
   // If the pointers that we would use for the bounds comparison have different
   // address spaces, assume the values aren't directly comparable, so we can't
   // use them for the runtime check. We also have to assume they could
   // overlap. In the future there should be metadata for whether address spaces
   // are disjoint.
   unsigned NumPointers = RtCheck.Pointers.size();
   for (unsigned i = 0; i < NumPointers; ++i) {
     for (unsigned j = i + 1; j < NumPointers; ++j) {
if (NumReadWrites == 1 && NumReads == 0) {
     DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
     CanVecMem = true;
     return;
   }
 
   // Build dependence sets and check whether we need a runtime pointer bounds
   // check.
   Accesses.buildDependenceSets();
-  bool NeedRTCheck = Accesses.isRTCheckNeeded();
 
   // Find pointers with computable bounds. We are going to use this information
   // to place a runtime bound check.
-  bool CanDoRT = false;
-  if (NeedRTCheck)
-    CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop,
-                                       Strides);
-
-  DEBUG(dbgs() << "LAA: We need to do " << NumComparisons <<
-        " pointer comparisons.\n");
-
-  // If we only have one set of dependences to check pointers among we don't
-  // need a runtime check.
-  if (NumComparisons == 0 && NeedRTCheck)
-    NeedRTCheck = false;
+  bool NeedRTCheck;
+  bool CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck,
+                                          NeedRTCheck, SE,
+                                          TheLoop, Strides);
+
+  DEBUG(dbgs() << "LAA: We need to do "
+               << PtrRtCheck.getNumberOfChecks(nullptr)
+               << " pointer comparisons.\n");
 
   // Check that we found the bounds for the pointer.
   if (CanDoRT)
     DEBUG(dbgs() << "LAA: We can perform a memory runtime check if needed.\n");
   else if (NeedRTCheck) {
     emitAnalysis(LoopAccessReport() << "cannot identify array bounds");
     DEBUG(dbgs() << "LAA: We can't vectorize because we can't find " <<
           "the array bounds.\n");
     PtrRtCheck.reset();
     CanVecMem = false;
     return;
   }
if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
       NeedRTCheck = true;
 
       // Clear the dependency checks. We assume they are not needed.
       Accesses.resetDepChecks(DepChecker);
 
       PtrRtCheck.reset();
       PtrRtCheck.Need = true;
 
-      CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE,
+      CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NeedRTCheck, SE,
                                          TheLoop, Strides, true);
+
       // Check that we found the bounds for the pointer.
-      if (!CanDoRT && NumComparisons > 0) {
+      if (NeedRTCheck && !CanDoRT) {
         emitAnalysis(LoopAccessReport()
                      << "cannot check memory dependencies at runtime");
         DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
         PtrRtCheck.reset();
         CanVecMem = false;
         return;
       }
 
std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck(
   return std::make_pair(FirstInst, Check);
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT, LoopInfo *LI,
                                const ValueToValueMap &Strides)
-    : DepChecker(SE, L), NumComparisons(0), TheLoop(L), SE(SE), DL(DL),
+    : DepChecker(SE, L), TheLoop(L), SE(SE), DL(DL),
       TLI(TLI), AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
       MaxSafeDepDistBytes(-1U), CanVecMem(false),
       StoreToLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
     analyzeLoop(Strides);
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {

test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll

+; RUN: opt -loop-accesses -analyze < %s | FileCheck %s
+
+; 3 reads and 3 writes should need 12 memchecks
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnueabi"
+
+; CHECK: Memory dependences are safe with run-time checks
+; Memory dependecies have labels starting from 0, so in
+; order to verify that we have n checks, we look for
+; (n-1): and not n:.
+
+; CHECK: Run-time memory checks:
+; CHECK-NEXT: 0:
+; CHECK: 11:
+; CHECK-NOT: 12:
+
+define void @testf(i16* %a,
+               i16* %b,
+               i16* %c,
+               i16* %d,
+               i16* %e,
+               i16* %f) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
+
+  %add = add nuw nsw i64 %ind, 1
+
+  %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
+  %loadA = load i16, i16* %arrayidxA, align 2
+
+  %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
+  %loadB = load i16, i16* %arrayidxB, align 2
+
+  %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %ind
+  %loadC = load i16, i16* %arrayidxC, align 2
+
+  %mul = mul i16 %loadB, %loadA
+  %mul1 = mul i16 %mul, %loadC
+
+  %arrayidxD = getelementptr inbounds i16, i16* %d, i64 %ind
+  store i16 %mul1, i16* %arrayidxD, align 2
+
+  %arrayidxE = getelementptr inbounds i16, i16* %e, i64 %ind
+  store i16 %mul, i16* %arrayidxE, align 2
+
+  %arrayidxF = getelementptr inbounds i16, i16* %f, i64 %ind
+  store i16 %mul1, i16* %arrayidxF, align 2
+
+  %exitcond = icmp eq i64 %add, 20
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}