[LAA-memchecks 2/3] Move number of memcheck threshold checking to LV

[anemet]

Summary

Now the analysis won't "fail" if the memchecks exceed the threshold. It
is the transform pass' responsibility to perform the check.

This allows the transform pass to further analyze/eliminate the
memchecks. E.g. in Loop distribution we only need to check pointers
that end up in different partitions.

Note that there is a slight change of functionality here. The logic in
analyzeLoop is that if dependence checking fails due to non-constant
distance between the pointers, another attempt is made to prove safety
of the dependences purely using run-time checks.

Before this patch we could fail the loop due to exceeding the memcheck
threshold after the first step, now we only check the threshold in the
client after the full analysis. There is no measurable compile-time
effect but I wanted to record this here.

[hfinkel]

LGTM.

[anemet]

r231817

include/llvm/Analysis/LoopAccessAnalysis.h

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; }
+
   /// 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;
 
   unsigned NumLoads;

lib/Analysis/LoopAccessAnalysis.cpp

void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
 
   // 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.
-  unsigned NumComparisons = 0;
   bool CanDoRT = false;
   if (NeedRTCheck)
     CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop,
                                        Strides);
 
   DEBUG(dbgs() << "LAA: We need to do " << NumComparisons <<
         " pointer comparisons.\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 (NumComparisons > RuntimeMemoryCheckThreshold) {
-    emitAnalysis(LoopAccessReport()
-                 << NumComparisons << " exceeds limit of "
-                 << RuntimeMemoryCheckThreshold
-                 << " dependent memory operations checked at runtime");
-    DEBUG(dbgs() << "LAA: Too many memory checks needed.\n");
-    PtrRtCheck.reset();
-    CanVecMem = false;
-    return;
-  }
-
   PtrRtCheck.Need = NeedRTCheck;
 
   CanVecMem = true;
   if (Accesses.isDependencyCheckNeeded()) {
     DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
     CanVecMem = DepChecker.areDepsSafe(
         DependentAccesses, Accesses.getDependenciesToCheck(), Strides);
     MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes();
if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
         emitAnalysis(LoopAccessReport()
                      << "cannot check memory dependencies at runtime");
         DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
         PtrRtCheck.reset();
         CanVecMem = false;
         return;
       }
 
-      // Check that we did not collect too many pointers.
-      if (NumComparisons > RuntimeMemoryCheckThreshold) {
-        emitAnalysis(LoopAccessReport()
-                     << NumComparisons << " exceeds limit of "
-                     << RuntimeMemoryCheckThreshold
-                     << " dependent memory operations checked at runtime");
-        DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
-        PtrRtCheck.reset();
-        CanVecMem = false;
-        return;
-      }
-
       CanVecMem = true;
     }
   }
 
   if (!CanVecMem)
     emitAnalysis(LoopAccessReport() <<
                  "unsafe dependent memory operations in loop");
 
LoopAccessInfo::addRuntimeCheck(Instruction *Loc) const {
   return std::make_pair(FirstInst, Check);
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const DataLayout *DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT,
                                const ValueToValueMap &Strides)
-    : DepChecker(SE, DL, L), TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA),
-      DT(DT), NumLoads(0), NumStores(0), MaxSafeDepDistBytes(-1U),
-      CanVecMem(false) {
+    : DepChecker(SE, DL, L), NumComparisons(0), TheLoop(L), SE(SE), DL(DL),
+      TLI(TLI), AA(AA), DT(DT), NumLoads(0), NumStores(0),
+      MaxSafeDepDistBytes(-1U), CanVecMem(false) {
   if (canAnalyzeLoop())
     analyzeLoop(Strides);
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   if (CanVecMem) {
     if (PtrRtCheck.empty())
       OS.indent(Depth) << "Memory dependences are safe\n";

lib/Transforms/Vectorize/LoopVectorize.cpp

void LoopVectorizationLegality::collectLoopUniforms() {
   }
 }
 
 bool LoopVectorizationLegality::canVectorizeMemory() {
   LAI = &LAA->getInfo(TheLoop, Strides);
   auto &OptionalReport = LAI->getReport();
   if (OptionalReport)
     emitAnalysis(VectorizationReport(*OptionalReport));
-  return LAI->canVectorizeMemory();
+  if (!LAI->canVectorizeMemory())
+    return false;
+
+  if (LAI->getNumRuntimePointerChecks() >
+      VectorizerParams::RuntimeMemoryCheckThreshold) {
+    emitAnalysis(VectorizationReport()
+                 << LAI->getNumRuntimePointerChecks() << " exceeds limit of "
+                 << VectorizerParams::RuntimeMemoryCheckThreshold
+                 << " dependent memory operations checked at runtime");
+    DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
+    return false;
+  }
+  return true;
 }
 
 static bool hasMultipleUsesOf(Instruction *I,
                               SmallPtrSetImpl<Instruction *> &Insts) {
   unsigned NumUses = 0;
   for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) {
     if (Insts.count(dyn_cast<Instruction>(*Use)))
       ++NumUses;