[NFCI]MemDepAnalysis] Introduce global limit on a number of instructions to be traversed during single query

[lebedev.ri]

Summary

As we have seen/established in D84108, the cut-off thresholds for Memory Dependence Analysis may need tuning.
In particular, currently they are:

• scan up to 100 instructions per block. IMO this may be a bit low. (rL179713, changed from 500)
• Scan up to 1000 (*sic*) blocks. That seems to be somewhat high.. (D16123)
• There is no cumulative limit on scanned instructions, so one query can end up scanning up to 100 instructions/block * 1k blocks = 100k instructions. Just as @nikic noted in https://reviews.llvm.org/D84108#2174113, that is indeed kinda just insane.

For now, this patch simply adds said cut-off option, but the limit is presently unset.
D84609 will be lowering the limits.

[lebedev.ri]

Not needed unless D84609 proceeds.

llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

public:
   void invalidateCachedPredecessors();
 
   /// Returns the instruction on which a memory location depends.
   ///
   /// If isLoad is true, this routine ignores may-aliases with read-only
   /// operations.  If isLoad is false, this routine ignores may-aliases
   /// with reads from read-only locations. If possible, pass the query
   /// instruction as well; this function may take advantage of the metadata
-  /// annotated to the query instruction to refine the result. \p Limit
+  /// annotated to the query instruction to refine the result. \p LocalLimit
   /// can be used to set the maximum number of instructions that will be
-  /// examined to find the pointer dependency. On return, it will be set to
-  /// the number of instructions left to examine. If a null pointer is passed
-  /// in, the limit will default to the value of -memdep-block-scan-limit.
+  /// examined in a single block to find the pointer dependency. On return,
+  /// it will be set to the number of instructions left to examine.
+  /// If a null pointer is passed in, the limit will default to the value
+  /// of -memdep-block-scan-limit.
+  /// \p GlobalLimit can be used to set the total maximum number of instructions
+  ///    that will be examined to find the pointer dependency.
   ///
   /// Note that this is an uncached query, and thus may be inefficient.
   MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad,
                                         BasicBlock::iterator ScanIt,
                                         BasicBlock *BB,
                                         Instruction *QueryInst = nullptr,
-                                        unsigned *Limit = nullptr);
+                                        unsigned *LocalLimit = nullptr,
+                                        unsigned *GlobalLimit = nullptr);
 
   MemDepResult
   getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad,
                                  BasicBlock::iterator ScanIt, BasicBlock *BB,
-                                 Instruction *QueryInst, unsigned *Limit);
+                                 Instruction *QueryInst, unsigned *LocalLimit,
+                                 unsigned *GlobalLimit);
 
   /// This analysis looks for other loads and stores with invariant.group
   /// metadata and the same pointer operand. Returns Unknown if it does not
   /// find anything, and Def if it can be assumed that 2 instructions load or
   /// store the same value and NonLocal which indicate that non-local Def was
   /// found, which can be retrieved by calling getNonLocalPointerDependency
   /// with the same queried instruction.
   MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB);
 
   /// Release memory in caches.
   void releaseMemory();
 
 private:
   MemDepResult getCallDependencyFrom(CallBase *Call, bool isReadOnlyCall,
                                      BasicBlock::iterator ScanIt,
                                      BasicBlock *BB);
-  bool getNonLocalPointerDepFromBB(Instruction *QueryInst,
-                                   const PHITransAddr &Pointer,
-                                   const MemoryLocation &Loc, bool isLoad,
-                                   BasicBlock *BB,
-                                   SmallVectorImpl<NonLocalDepResult> &Result,
-                                   DenseMap<BasicBlock *, Value *> &Visited,
-                                   bool SkipFirstBlock = false,
-                                   bool IsIncomplete = false);
+  bool getNonLocalPointerDepFromBB(
+      Instruction *QueryInst, const PHITransAddr &Pointer,
+      const MemoryLocation &Loc, bool isLoad, BasicBlock *BB,
+      DenseMap<BasicBlock *, Value *> &Visited, unsigned *GlobalLimit,
+      bool SkipFirstBlock = false, bool IsIncomplete = false);
   MemDepResult GetNonLocalInfoForBlock(Instruction *QueryInst,
                                        const MemoryLocation &Loc, bool isLoad,
                                        BasicBlock *BB, NonLocalDepInfo *Cache,
-                                       unsigned NumSortedEntries);
+                                       unsigned NumSortedEntries,
+                                       unsigned *GlobalLimit);
 
   void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
 
   void verifyRemoved(Instruction *Inst) const;
 };
 
 /// An analysis that produces \c MemoryDependenceResults for a function.
 ///

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

 // alias analysis information, and tries to provide a lazy, caching interface to
 // a common kind of alias information query.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/PHITransAddr.h"

 STATISTIC(NumCacheNonLocalPtr,
           "Number of fully cached non-local ptr responses");
 STATISTIC(NumCacheDirtyNonLocalPtr,
           "Number of cached, but dirty, non-local ptr responses");
 STATISTIC(NumUncacheNonLocalPtr, "Number of uncached non-local ptr responses");
 STATISTIC(NumCacheCompleteNonLocalPtr,
           "Number of block queries that were completely cached");
 
+STATISTIC(NumBlockInstructionsScannedMax,
+          "Maxmimal number of per-block instructions scanned in non-local "
+          "memory dependency analysis");
+STATISTIC(NumBlocksScannedMax, "Maxmimal number of blocks scanned in non-local "
+                               "memory dependency analysis");
+STATISTIC(NumInstructionsScannedMax, "Maxmimal number of instructions scanned "
+                                     "in non-local memory dependency analysis");
+
 // Limit for the number of instructions to scan in a block.
 
 static cl::opt<unsigned> BlockScanLimit(
     "memdep-block-scan-limit", cl::Hidden, cl::init(100),
     cl::desc("The number of instructions to scan in a block in memory "
              "dependency analysis (default = 100)"));
 
 static cl::opt<unsigned>
     BlockNumberLimit("memdep-block-number-limit", cl::Hidden, cl::init(1000),
                      cl::desc("The number of blocks to scan during memory "
                               "dependency analysis (default = 1000)"));
 
-// Limit on the number of memdep results to process.
-static const unsigned int NumResultsLimit = 100;
+// In each of BlockNumberLimit block we are willing to scan up to BlockScanLimit
+// instructions, but the total count of instructions scanned in all blocks is
+// at most TotalInstructionCountLimit.
+// This is related to the NumInstructionsScannedMax statistic.
+static cl::opt<unsigned> TotalInstructionCountLimit(
+    "memdep-total-instruction-count-limit", cl::Hidden, cl::init(100000),
+    cl::desc("The number of instructions we are allowed to scan during memory "
+             "dependency analysis (default = 100000)"));
+
+static cl::opt<unsigned> NumResultsLimit(
+    "memdep-num-results-limit", cl::Hidden, cl::init(100),
+    cl::desc(
+        "Limit on the number of memdep results to process (default = 100)"));
 
 /// This is a helper function that removes Val from 'Inst's set in ReverseMap.
 ///
 /// If the set becomes empty, remove Inst's entry.
 template <typename KeyTy>
 static void
 RemoveFromReverseMap(DenseMap<Instruction *, SmallPtrSet<KeyTy, 4>> &ReverseMap,
                      Instruction *Inst, KeyTy Val) {
if (Inst->mayReadFromMemory())
     return ModRefInfo::Ref;
   return ModRefInfo::NoModRef;
 }
 
 /// Private helper for finding the local dependencies of a call site.
 MemDepResult MemoryDependenceResults::getCallDependencyFrom(
     CallBase *Call, bool isReadOnlyCall, BasicBlock::iterator ScanIt,
     BasicBlock *BB) {
-  unsigned Limit = getDefaultBlockScanLimit();
+  unsigned LocalLimit = getDefaultBlockScanLimit();
 
   // Walk backwards through the block, looking for dependencies.
   while (ScanIt != BB->begin()) {
     Instruction *Inst = &*--ScanIt;
     // Debug intrinsics don't cause dependences and should not affect Limit
     if (isa<DbgInfoIntrinsic>(Inst))
       continue;
 
     // Limit the amount of scanning we do so we don't end up with quadratic
     // running time on extreme testcases.
-    --Limit;
-    if (!Limit)
+    --LocalLimit;
+    if (!LocalLimit)
       return MemDepResult::getUnknown();
 
     // If this inst is a memory op, get the pointer it accessed
     MemoryLocation Loc;
     ModRefInfo MR = GetLocation(Inst, Loc, TLI);
     if (Loc.Ptr) {
       // A simple instruction.
       if (isModOrRefSet(AA.getModRefInfo(Call, Loc)))
if (auto *SI = dyn_cast<StoreInst>(Inst))
     return SI->isVolatile();
   if (auto *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
     return AI->isVolatile();
   return false;
 }
 
 MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
-    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
+    BasicBlock *BB, Instruction *QueryInst, unsigned *LocalLimit,
+    unsigned *GlobalLimit) {
   MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
   if (QueryInst != nullptr) {
     if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
       InvariantGroupDependency = getInvariantGroupPointerDependency(LI, BB);
 
       if (InvariantGroupDependency.isDef())
         return InvariantGroupDependency;
     }
   }
   MemDepResult SimpleDep = getSimplePointerDependencyFrom(
-      MemLoc, isLoad, ScanIt, BB, QueryInst, Limit);
+      MemLoc, isLoad, ScanIt, BB, QueryInst, LocalLimit, GlobalLimit);
   if (SimpleDep.isDef())
     return SimpleDep;
   // Non-local invariant group dependency indicates there is non local Def
   // (it only returns nonLocal if it finds nonLocal def), which is better than
   // local clobber and everything else.
   if (InvariantGroupDependency.isNonLocal())
     return InvariantGroupDependency;
 
NonLocalDefsCache.try_emplace(
       LI, NonLocalDepResult(ClosestDependency->getParent(),
                             MemDepResult::getDef(ClosestDependency), nullptr));
   ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
   return MemDepResult::getNonLocal();
 }
 
 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
-    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
+    BasicBlock *BB, Instruction *QueryInst, unsigned *LocalLimit,
+    unsigned *GlobalLimit) {
   bool isInvariantLoad = false;
 
-  unsigned DefaultLimit = getDefaultBlockScanLimit();
-  if (!Limit)
-    Limit = &DefaultLimit;
+  unsigned DefaultLocalLimit = getDefaultBlockScanLimit();
+  unsigned DefaultGlobalLimit = getDefaultBlockScanLimit();
+  if (!LocalLimit)
+    LocalLimit = &DefaultLocalLimit;
+  if (!GlobalLimit)
+    GlobalLimit = &DefaultGlobalLimit;
+
+  auto _ = make_scope_exit([&, Orig = *LocalLimit]() {
+    NumBlockInstructionsScannedMax.updateMax(Orig - *LocalLimit);
+  });
 
   // We must be careful with atomic accesses, as they may allow another thread
   //   to touch this location, clobbering it. We are conservative: if the
   //   QueryInst is not a simple (non-atomic) memory access, we automatically
   //   return getClobber.
   // If it is simple, we know based on the results of
   // "Compiler testing via a theory of sound optimisations in the C11/C++11
   //   memory model" in PLDI 2013, that a non-atomic location can only be
while (ScanIt != BB->begin()) {
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
       // Debug intrinsics don't (and can't) cause dependencies.
       if (isa<DbgInfoIntrinsic>(II))
         continue;
 
     // Limit the amount of scanning we do so we don't end up with quadratic
     // running time on extreme testcases.
-    --*Limit;
-    if (!*Limit)
+    if (!*LocalLimit || !*GlobalLimit)
       return MemDepResult::getUnknown();
+    --*LocalLimit;
+    --*GlobalLimit;
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       // If we reach a lifetime begin or end marker, then the query ends here
       // because the value is undefined.
       if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
         // FIXME: This only considers queries directly on the invariant-tagged
         // pointer, not on query pointers that are indexed off of them.  It'd
         // be nice to handle that at some point (the right approach is to use
void MemoryDependenceResults::getNonLocalPointerDependency(
   const DataLayout &DL = FromBB->getModule()->getDataLayout();
   PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, &AC);
 
   // This is the set of blocks we've inspected, and the pointer we consider in
   // each block.  Because of critical edges, we currently bail out if querying
   // a block with multiple different pointers.  This can happen during PHI
   // translation.
   DenseMap<BasicBlock *, Value *> Visited;
-  if (getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
-                                   Result, Visited, true))
+  unsigned GlobalLimit = TotalInstructionCountLimit;
+  auto _ = make_scope_exit([&, Orig = GlobalLimit]() {
+    NumInstructionsScannedMax.updateMax(Orig - GlobalLimit);
+  });
+  bool Success =
+      getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
+                                  Result, Visited, &GlobalLimit, true);
+  if (Success)
     return;
   Result.clear();
   Result.push_back(NonLocalDepResult(FromBB, MemDepResult::getUnknown(),
                                      const_cast<Value *>(Loc.Ptr)));
 }
 
 /// Compute the memdep value for BB with Pointer/PointeeSize using either
 /// cached information in Cache or by doing a lookup (which may use dirty cache
 /// info if available).
 ///
 /// If we do a lookup, add the result to the cache.
 MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
     Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
-    BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
+    BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries,
+    unsigned *GlobalLimit) {
 
   bool isInvariantLoad = false;
 
   if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
     isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
 
   // Do a binary search to see if we already have an entry for this block in
   // the cache set.  If so, find it.
if (ExistingResult && ExistingResult->getResult().getInst()) {
     // Eliminating the dirty entry from 'Cache', so update the reverse info.
     ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
     RemoveFromReverseMap(ReverseNonLocalPtrDeps, &*ScanPos, CacheKey);
   } else {
     ++NumUncacheNonLocalPtr;
   }
 
   // Scan the block for the dependency.
-  MemDepResult Dep =
-      getPointerDependencyFrom(Loc, isLoad, ScanPos, BB, QueryInst);
+  MemDepResult Dep = getPointerDependencyFrom(
+      Loc, isLoad, ScanPos, BB, QueryInst, /*LocalLimit=*/nullptr, GlobalLimit);
 
   // Don't cache results for invariant load.
   if (isInvariantLoad)
     return Dep;
 
   // If we had a dirty entry for the block, update it.  Otherwise, just add
   // a new entry.
   if (ExistingResult)

 ///
 /// This function returns true on success, or false to indicate that it could
 /// not compute dependence information for some reason.  This should be treated
 /// as a clobber dependence on the first instruction in the predecessor block.
 bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
     Instruction *QueryInst, const PHITransAddr &Pointer,
     const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
     SmallVectorImpl<NonLocalDepResult> &Result,
-    DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock,
-    bool IsIncomplete) {
+    DenseMap<BasicBlock *, Value *> &Visited, unsigned *GlobalLimit,
+    bool SkipFirstBlock, bool IsIncomplete) {
   // Look up the cached info for Pointer.
   ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
 
   // Set up a temporary NLPI value. If the map doesn't yet have an entry for
   // CacheKey, this value will be inserted as the associated value. Otherwise,
   // it'll be ignored, and we'll have to check to see if the cached size and
   // aa tags are consistent with the current query.
   NonLocalPointerInfo InitialNLPI;
if (CacheInfo->Size != Loc.Size) {
         // information about blocks we have already visited. We therefore must
         // assume that the cache information is incomplete.
         IsIncomplete = true;
       } else {
         // This query's Size is less than the cached one. Conservatively restart
         // the query using the greater size.
         return getNonLocalPointerDepFromBB(
             QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
-            StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
+            StartBB, Result, Visited, GlobalLimit, SkipFirstBlock,
+            IsIncomplete);
       }
     }
 
     // If the query's AATags are inconsistent with the cached one,
     // conservatively throw out the cached data and restart the query with
     // no tag if needed.
     if (CacheInfo->AATags != Loc.AATags) {
       if (CacheInfo->AATags) {
         CacheInfo->Pair = BBSkipFirstBlockPair();
         CacheInfo->AATags = AAMDNodes();
         for (auto &Entry : CacheInfo->NonLocalDeps)
           if (Instruction *Inst = Entry.getResult().getInst())
             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
         CacheInfo->NonLocalDeps.clear();
         // The cache is cleared (in the above line) so we will have lost
         // information about blocks we have already visited. We therefore must
         // assume that the cache information is incomplete.
         IsIncomplete = true;
       }
       if (Loc.AATags)
         return getNonLocalPointerDepFromBB(
             QueryInst, Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result,
-            Visited, SkipFirstBlock, IsIncomplete);
+            Visited, GlobalLimit, SkipFirstBlock, IsIncomplete);
     }
   }
 
   NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
 
   // If we have valid cached information for exactly the block we are
   // investigating, just return it with no recomputation.
   // Don't use cached information for invariant loads since it is valid for
bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
   SmallVector<std::pair<BasicBlock *, PHITransAddr>, 16> PredList;
 
   // Keep track of the entries that we know are sorted.  Previously cached
   // entries will all be sorted.  The entries we add we only sort on demand (we
   // don't insert every element into its sorted position).  We know that we
   // won't get any reuse from currently inserted values, because we don't
   // revisit blocks after we insert info for them.
   unsigned NumSortedEntries = Cache->size();
-  unsigned WorklistEntries = BlockNumberLimit;
   bool GotWorklistLimit = false;
+  unsigned BlockBudget = BlockNumberLimit;
+  auto _ = make_scope_exit([&, Orig = BlockBudget]() {
+    NumBlocksScannedMax.updateMax(Orig - BlockBudget);
+  });
   LLVM_DEBUG(AssertSorted(*Cache));
 
   while (!Worklist.empty()) {
     BasicBlock *BB = Worklist.pop_back_val();
 
     // If we do process a large number of blocks it becomes very expensive and
     // likely it isn't worth worrying about
     if (Result.size() > NumResultsLimit) {
while (!Worklist.empty()) {
     if (!SkipFirstBlock) {
       // Analyze the dependency of *Pointer in FromBB.  See if we already have
       // been here.
       assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
 
       // Get the dependency info for Pointer in BB.  If we have cached
       // information, we will use it, otherwise we compute it.
       LLVM_DEBUG(AssertSorted(*Cache, NumSortedEntries));
-      MemDepResult Dep = GetNonLocalInfoForBlock(QueryInst, Loc, isLoad, BB,
-                                                 Cache, NumSortedEntries);
+      MemDepResult Dep = GetNonLocalInfoForBlock(
+          QueryInst, Loc, isLoad, BB, Cache, NumSortedEntries, GlobalLimit);
 
       // If we got a Def or Clobber, add this to the list of results.
       if (!Dep.isNonLocal()) {
         if (DT.isReachableFromEntry(BB)) {
           Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
           continue;
         }
       }
if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
         if (InsertRes.first->second != Pointer.getAddr()) {
           // Make sure to clean up the Visited map before continuing on to
           // PredTranslationFailure.
           for (unsigned i = 0; i < NewBlocks.size(); i++)
             Visited.erase(NewBlocks[i]);
           goto PredTranslationFailure;
         }
       }
-      if (NewBlocks.size() > WorklistEntries) {
+      if (NewBlocks.size() > BlockBudget) {
         // Make sure to clean up the Visited map before continuing on to
         // PredTranslationFailure.
         for (unsigned i = 0; i < NewBlocks.size(); i++)
           Visited.erase(NewBlocks[i]);
         GotWorklistLimit = true;
         goto PredTranslationFailure;
       }
-      WorklistEntries -= NewBlocks.size();
+      BlockBudget -= NewBlocks.size();
       Worklist.append(NewBlocks.begin(), NewBlocks.end());
       continue;
     }
 
     // We do need to do phi translation, if we know ahead of time we can't phi
     // translate this value, don't even try.
     if (!Pointer.IsPotentiallyPHITranslatable())
       goto PredTranslationFailure;
for (unsigned i = 0, n = PredList.size(); i < n; ++i) {
       // X = phi [x, bb1], [y, bb2].  PHI translating for bb1 doesn't *need*
       // to recurse here, pedantically speaking.
 
       // If getNonLocalPointerDepFromBB fails here, that means the cached
       // result conflicted with the Visited list; we have to conservatively
       // assume it is unknown, but this also does not block PRE of the load.
       if (!CanTranslate ||
           !getNonLocalPointerDepFromBB(QueryInst, PredPointer,
                                        Loc.getWithNewPtr(PredPtrVal), isLoad,
-                                      Pred, Result, Visited)) {
+                                       Pred, Result, Visited, GlobalLimit)) {
         // Add the entry to the Result list.
         NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
         Result.push_back(Entry);
 
         // Since we had a phi translation failure, the cache for CacheKey won't
         // include all of the entries that we need to immediately satisfy future
         // queries.  Mark this in NonLocalPointerDeps by setting the
         // BBSkipFirstBlockPair pointer to null.  This requires reuse of the