[MemorySSA] Limit clobber walks.

[asbirlea]

Summary

This patch limits all getClobberingMemoryAccess() walks to MaxCheckLimit.

[george.burgess.iv]

Thanks for this!

Would it be straightforward to have a lit test (or similar) that sets memssa-check-limit to something super low and checks that this all does what we want (e.g. walk limit is cumulative across all walks on OptimizePhis, the walker trivially obeys it, ...)

lib/Analysis/MemorySSA.cpp

557

nit: please remove == 0

910

Was this intended to be unsigned &UpwardWalkLimit? Looks like we're passing it by ref everywhere else

923

Would it be better to make UpwardWalkLimit a member? This entire class is a container of query-specific state anyway.

[asbirlea]

Address comments.

I updated two existing tests to take a limit of 0. Let me know if this makes sense.

[asbirlea]

format.

[george.burgess.iv]

Thanks again!

[asbirlea]

Thank you for the review!

lib/Analysis/MemorySSA.cpp

template <class AliasAnalysisType> class ClobberWalker {
   };
 
   /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
   /// This will update Desc.Last as it walks. It will (optionally) also stop at
   /// StopAt.
   ///
   /// This does not test for whether StopAt is a clobber
   UpwardsWalkResult
-  walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
+  walkToPhiOrClobber(DefPath &Desc, unsigned &UpwardWalkLimit,
+                     const MemoryAccess *StopAt = nullptr,
                      const MemoryAccess *SkipStopAt = nullptr) const {
     assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
+    assert(UpwardWalkLimit > 0 && "Need a positive walk limit");
 
     for (MemoryAccess *Current : def_chain(Desc.Last)) {
       Desc.Last = Current;
       if (Current == StopAt || Current == SkipStopAt)
         return {Current, false, MayAlias};
 
       if (auto *MD = dyn_cast<MemoryDef>(Current)) {
         if (MSSA.isLiveOnEntryDef(MD))
           return {MD, true, MustAlias};
+
+        if (--UpwardWalkLimit == 0)
+          return {Current, true, MayAlias};
+
         ClobberAlias CA =
             instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA);
         if (CA.IsClobber)
           return {MD, true, CA.AR};
       }
     }
 
     assert(isa<MemoryPhi>(Desc.Last) &&
template <class AliasAnalysisType> class ClobberWalker {
   /// Get an access that keeps us from optimizing to the given phi.
   ///
   /// PausedSearches is an array of indices into the Paths array. Its incoming
   /// value is the indices of searches that stopped at the last phi optimization
   /// target. It's left in an unspecified state.
   ///
   /// If this returns None, NewPaused is a vector of searches that terminated
   /// at StopWhere. Otherwise, NewPaused is left in an unspecified state.
-  Optional<TerminatedPath>
-  getBlockingAccess(const MemoryAccess *StopWhere,
-                    SmallVectorImpl<ListIndex> &PausedSearches,
-                    SmallVectorImpl<ListIndex> &NewPaused,
-                    SmallVectorImpl<TerminatedPath> &Terminated) {
+  Optional<TerminatedPath> getBlockingAccess(
+      const MemoryAccess *StopWhere, SmallVectorImpl<ListIndex> &PausedSearches,
+      SmallVectorImpl<TerminatedPath> &Terminated, unsigned &UpwardWalkLimit) {
     assert(!PausedSearches.empty() && "No searches to continue?");
 
     // BFS vs DFS really doesn't make a difference here, so just do a DFS with
     // PausedSearches as our stack.
     while (!PausedSearches.empty()) {
       ListIndex PathIndex = PausedSearches.pop_back_val();
       DefPath &Node = Paths[PathIndex];
 
while (!PausedSearches.empty()) {
         continue;
 
       const MemoryAccess *SkipStopWhere = nullptr;
       if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
         assert(isa<MemoryDef>(Query->OriginalAccess));
         SkipStopWhere = Query->OriginalAccess;
       }
 
-      UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere,
+      UpwardsWalkResult Res = walkToPhiOrClobber(Node, UpwardWalkLimit,
+                                                 /*StopAt=*/StopWhere,
                                                  /*SkipStopAt=*/SkipStopWhere);
       if (Res.IsKnownClobber) {
         assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
+
         // If this wasn't a cache hit, we hit a clobber when walking. That's a
         // failure.
         TerminatedPath Term{Res.Result, PathIndex};
         if (!MSSA.dominates(Res.Result, StopWhere))
           return Term;
 
         // Otherwise, it's a valid thing to potentially optimize to.
         Terminated.push_back(Term);
template <class AliasAnalysisType> class ClobberWalker {
   ///     - If not, optimization isn't possible.
   ///     - Otherwise, walk from A to another clobber or phi, A'.
   ///       - If A' is a def, we're done.
   ///       - If A' is a phi, try to optimize it.
   ///
   /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path
   /// terminates when a MemoryAccess that clobbers said MemoryLocation is found.
   OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start,
-                             const MemoryLocation &Loc) {
+                             const MemoryLocation &Loc,
+                             unsigned &UpwardWalkLimit) {
     assert(Paths.empty() && VisitedPhis.empty() &&
            "Reset the optimization state.");
 
     Paths.emplace_back(Loc, Start, Phi, None);
     // Stores how many "valid" optimization nodes we had prior to calling
     // addSearches/getBlockingAccess. Necessary for caching if we had a blocker.
     auto PriorPathsSize = Paths.size();
 
while (true) {
       // optimization for the prior phi.
       assert(all_of(TerminatedPaths, [&](const TerminatedPath &P) {
         return MSSA.dominates(P.Clobber, Target);
       }));
 
       // FIXME: This is broken, because the Blocker may be reported to be
       // liveOnEntry, and we'll happily wait for that to disappear (read: never)
       // For the moment, this is fine, since we do nothing with blocker info.
-      if (Optional<TerminatedPath> Blocker = getBlockingAccess(
-              Target, PausedSearches, NewPaused, TerminatedPaths)) {
+      if (Optional<TerminatedPath> Blocker =
+              getBlockingAccess(Target, PausedSearches, NewPaused,
+                                TerminatedPaths, UpwardWalkLimit)) {
 
         // Find the node we started at. We can't search based on N->Last, since
         // we may have gone around a loop with a different MemoryLocation.
         auto Iter = find_if(def_path(Blocker->LastNode), [&](const DefPath &N) {
           return defPathIndex(N) < PriorPathsSize;
         });
         assert(Iter != def_path_iterator());
 
while (true) {
         MoveDominatedPathToEnd(TerminatedPaths);
         TerminatedPath Result = TerminatedPaths.pop_back_val();
         return {Result, std::move(TerminatedPaths)};
       }
 
       MemoryAccess *DefChainEnd = nullptr;
       SmallVector<TerminatedPath, 4> Clobbers;
       for (ListIndex Paused : NewPaused) {
-        UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]);
+        UpwardsWalkResult WR =
+            walkToPhiOrClobber(Paths[Paused], UpwardWalkLimit);
         if (WR.IsKnownClobber)
           Clobbers.push_back({WR.Result, Paused});
         else
           // Micro-opt: If we hit the end of the chain, save it.
           DefChainEnd = WR.Result;
       }
 
       if (!TerminatedPaths.empty()) {

 
 public:
   ClobberWalker(const MemorySSA &MSSA, AliasAnalysisType &AA, DominatorTree &DT)
       : MSSA(MSSA), AA(AA), DT(DT) {}
 
   AliasAnalysisType *getAA() { return &AA; }
   /// Finds the nearest clobber for the given query, optimizing phis if
   /// possible.
-  MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q) {
+  MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q,
+                            unsigned UpwardWalkLimit) {
     Query = &Q;
 
     MemoryAccess *Current = Start;
     // This walker pretends uses don't exist. If we're handed one, silently grab
     // its def. (This has the nice side-effect of ensuring we never cache uses)
     if (auto *MU = dyn_cast<MemoryUse>(Start))
       Current = MU->getDefiningAccess();
 
     DefPath FirstDesc(Q.StartingLoc, Current, Current, None);
     // Fast path for the overly-common case (no crazy phi optimization
     // necessary)
-    UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc);
+    UpwardsWalkResult WalkResult =
+        walkToPhiOrClobber(FirstDesc, UpwardWalkLimit);
     MemoryAccess *Result;
     if (WalkResult.IsKnownClobber) {
       Result = WalkResult.Result;
       Q.AR = WalkResult.AR;
     } else {
-      OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
-                                          Current, Q.StartingLoc);
+      OptznResult OptRes =
+          tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last), Current,
+                         Q.StartingLoc, UpwardWalkLimit);
       verifyOptResult(OptRes);
       resetPhiOptznState();
       Result = OptRes.PrimaryClobber.Clobber;
     }
 
 #ifdef EXPENSIVE_CHECKS
-    if (!Q.SkipSelfAccess)
+    if (!Q.SkipSelfAccess && UpwardWalkLimit > 0)
       checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
 #endif
     return Result;
   }
 
   void verify(const MemorySSA *MSSA) { assert(MSSA == &this->MSSA); }
 };
 
template <class AliasAnalysisType> class MemorySSA::ClobberWalkerBase {
   ClobberWalker<AliasAnalysisType> Walker;
   MemorySSA *MSSA;
 
 public:
   ClobberWalkerBase(MemorySSA *M, AliasAnalysisType *A, DominatorTree *D)
       : Walker(*M, *A, *D), MSSA(M) {}
 
   MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
-                                              const MemoryLocation &);
+                                              const MemoryLocation &,
+                                              unsigned &);
   // Second argument (bool), defines whether the clobber search should skip the
   // original queried access. If true, there will be a follow-up query searching
   // for a clobber access past "self". Note that the Optimized access is not
   // updated if a new clobber is found by this SkipSelf search. If this
   // additional query becomes heavily used we may decide to cache the result.
   // Walker instantiations will decide how to set the SkipSelf bool.
-  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, bool);
+  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, unsigned &, bool);
   void verify(const MemorySSA *MSSA) { Walker.verify(MSSA); }
 };
 
 /// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
 /// longer does caching on its own, but the name has been retained for the
 /// moment.
 template <class AliasAnalysisType>
 class MemorySSA::CachingWalker final : public MemorySSAWalker {
   ClobberWalkerBase<AliasAnalysisType> *Walker;
 
 public:
   CachingWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
       : MemorySSAWalker(M), Walker(W) {}
   ~CachingWalker() override = default;
 
   using MemorySSAWalker::getClobberingMemoryAccess;
 
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, UWL, false);
+  }
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
+                                          const MemoryLocation &Loc,
+                                          unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
+  }
+
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
-    return Walker->getClobberingMemoryAccessBase(MA, false);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, UpwardWalkLimit);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) override {
-    return Walker->getClobberingMemoryAccessBase(MA, Loc);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
   }
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
   }
 
   void verify(const MemorySSA *MSSA) override {
     MemorySSAWalker::verify(MSSA);
     Walker->verify(MSSA);
   }
 };
 
 template <class AliasAnalysisType>
 class MemorySSA::SkipSelfWalker final : public MemorySSAWalker {
   ClobberWalkerBase<AliasAnalysisType> *Walker;
 
 public:
   SkipSelfWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
       : MemorySSAWalker(M), Walker(W) {}
   ~SkipSelfWalker() override = default;
 
   using MemorySSAWalker::getClobberingMemoryAccess;
 
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, UWL, true);
+  }
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
+                                          const MemoryLocation &Loc,
+                                          unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
+  }
+
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
-    return Walker->getClobberingMemoryAccessBase(MA, true);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, UpwardWalkLimit);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) override {
-    return Walker->getClobberingMemoryAccessBase(MA, Loc);
+    unsigned UpwardWalkLimit = MaxCheckLimit;
+    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
   }
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
   }
 
   void verify(const MemorySSA *MSSA) override {

 /// their defining access at the thing that actually clobbers them.  Because it
 /// is a batch walker that touches everything, it does not operate like the
 /// other walkers.  This walker is basically performing a top-down SSA renaming
 /// pass, where the version stack is used as the cache.  This enables it to be
 /// significantly more time and memory efficient than using the regular walker,
 /// which is walking bottom-up.
 class MemorySSA::OptimizeUses {
 public:
-  OptimizeUses(MemorySSA *MSSA, MemorySSAWalker *Walker, BatchAAResults *BAA,
-               DominatorTree *DT)
+  OptimizeUses(MemorySSA *MSSA, CachingWalker<BatchAAResults> *Walker,
+               BatchAAResults *BAA, DominatorTree *DT)
       : MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
 
   void optimizeUses();
 
 private:
   /// This represents where a given memorylocation is in the stack.
   struct MemlocStackInfo {
     // This essentially is keeping track of versions of the stack. Whenever
struct MemlocStackInfo {
     Optional<AliasResult> AR;
   };
 
   void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
                            SmallVectorImpl<MemoryAccess *> &,
                            DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
 
   MemorySSA *MSSA;
-  MemorySSAWalker *Walker;
+  CachingWalker<BatchAAResults> *Walker;
   BatchAAResults *AA;
   DominatorTree *DT;
 };
 
 } // end namespace llvm
 
 /// Optimize the uses in a given block This is basically the SSA renaming
 /// algorithm, with one caveat: We are able to use a single stack for all
if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
                         << UpperBound - LocInfo.LowerBound
                         << " stores to disambiguate\n");
       // Because we did not walk, LastKill is no longer valid, as this may
       // have been a kill.
       LocInfo.LastKillValid = false;
       continue;
     }
     bool FoundClobberResult = false;
+    unsigned UpwardWalkLimit = MaxCheckLimit;
     while (UpperBound > LocInfo.LowerBound) {
       if (isa<MemoryPhi>(VersionStack[UpperBound])) {
         // For phis, use the walker, see where we ended up, go there
-        Instruction *UseInst = MU->getMemoryInst();
-        MemoryAccess *Result = Walker->getClobberingMemoryAccess(UseInst);
+        MemoryAccess *Result =
+            Walker->getClobberingMemoryAccess(MU, UpwardWalkLimit);
         // We are guaranteed to find it or something is wrong
         while (VersionStack[UpperBound] != Result) {
           assert(UpperBound != 0);
           --UpperBound;
         }
         FoundClobberResult = true;
         break;
       }

 
 /// Walk the use-def chains starting at \p StartingAccess and find
 /// the MemoryAccess that actually clobbers Loc.
 ///
 /// \returns our clobbering memory access
 template <typename AliasAnalysisType>
 MemoryAccess *
 MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
-    MemoryAccess *StartingAccess, const MemoryLocation &Loc) {
+    MemoryAccess *StartingAccess, const MemoryLocation &Loc,
+    unsigned &UpwardWalkLimit) {
   if (isa<MemoryPhi>(StartingAccess))
     return StartingAccess;
 
   auto *StartingUseOrDef = cast<MemoryUseOrDef>(StartingAccess);
   if (MSSA->isLiveOnEntryDef(StartingUseOrDef))
     return StartingUseOrDef;
 
   Instruction *I = StartingUseOrDef->getMemoryInst();
MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
 
   // Unlike the other function, do not walk to the def of a def, because we are
   // handed something we already believe is the clobbering access.
   // We never set SkipSelf to true in Q in this method.
   MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef)
                                      ? StartingUseOrDef->getDefiningAccess()
                                      : StartingUseOrDef;
 
-  MemoryAccess *Clobber = Walker.findClobber(DefiningAccess, Q);
+  MemoryAccess *Clobber =
+      Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit);
   LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *StartingUseOrDef << "\n");
   LLVM_DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *Clobber << "\n");
   return Clobber;
 }
 
 template <typename AliasAnalysisType>
 MemoryAccess *
 MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
-    MemoryAccess *MA, bool SkipSelf) {
+    MemoryAccess *MA, unsigned &UpwardWalkLimit, bool SkipSelf) {
   auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
   // If this is a MemoryPhi, we can't do anything.
   if (!StartingAccess)
     return MA;
 
   bool IsOptimized = false;
 
   // If this is an already optimized use or def, return the optimized result.
if (!IsOptimized) {
     // At this point, DefiningAccess may be the live on entry def.
     // If it is, we will not get a better result.
     if (MSSA->isLiveOnEntryDef(DefiningAccess)) {
       StartingAccess->setOptimized(DefiningAccess);
       StartingAccess->setOptimizedAccessType(None);
       return DefiningAccess;
     }
 
-    OptimizedAccess = Walker.findClobber(DefiningAccess, Q);
+    OptimizedAccess = Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit);
     StartingAccess->setOptimized(OptimizedAccess);
     if (MSSA->isLiveOnEntryDef(OptimizedAccess))
       StartingAccess->setOptimizedAccessType(None);
     else if (Q.AR == MustAlias)
       StartingAccess->setOptimizedAccessType(MustAlias);
   } else
     OptimizedAccess = StartingAccess->getOptimized();
 
   LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *StartingAccess << "\n");
   LLVM_DEBUG(dbgs() << "Optimized Memory SSA clobber for " << *I << " is ");
   LLVM_DEBUG(dbgs() << *OptimizedAccess << "\n");
 
   MemoryAccess *Result;
   if (SkipSelf && isa<MemoryPhi>(OptimizedAccess) &&
-      isa<MemoryDef>(StartingAccess)) {
+      isa<MemoryDef>(StartingAccess) && UpwardWalkLimit) {
     assert(isa<MemoryDef>(Q.OriginalAccess));
     Q.SkipSelfAccess = true;
-    Result = Walker.findClobber(OptimizedAccess, Q);
+    Result = Walker.findClobber(OptimizedAccess, Q, UpwardWalkLimit);
   } else
     Result = OptimizedAccess;
 
   LLVM_DEBUG(dbgs() << "Result Memory SSA clobber [SkipSelf = " << SkipSelf);
   LLVM_DEBUG(dbgs() << "] for " << *I << " is " << *Result << "\n");
 
   return Result;
 }