[MemorySSA] Use BatchAA for clobber walker

[nikic]

Summary

While MemorySSA use optimization was already using BatchAA, the publicly exposed MSSA walkers were using plain AAResults. This is not great, because it is expected that clobber walking will make repeated AA queries.

This patch makes the clobber API accept a BatchAAResults instance. The plain APIs are kept as wrappers and will create a BatchAAResults instance for the duration of the query. In the future, the explicit BatchAAResults arguments will be used to share AA results across queries, not just within one query.

[foad]

e.g. for NewGVN I think we should be able to use a single BatchAA instance for all queries.

@kmitropoulou it sounds like this could help with NewGVN compile time.

[nikic]

Ping :)

In D136164#3865041, @foad wrote:

e.g. for NewGVN I think we should be able to use a single BatchAA instance for all queries.

@kmitropoulou it sounds like this could help with NewGVN compile time.

Without looking too deeply into it, it's likely that the changes proposed by @kmitropoulou would actually prevent sharing BatchAA for all queries, because they introduce IR changes to the analysis phase, while NewGVN is generally designed to separate analysis and transformation.

[kmitropoulou]

In D136164#3882569, @nikic wrote:

Ping :)

In D136164#3865041, @foad wrote:

e.g. for NewGVN I think we should be able to use a single BatchAA instance for all queries.

@kmitropoulou it sounds like this could help with NewGVN compile time.

Without looking too deeply into it, it's likely that the changes proposed by @kmitropoulou would actually prevent sharing BatchAA for all queries, because they introduce IR changes to the analysis phase, while NewGVN is generally designed to separate analysis and transformation.

Load coercion does a similar thing to phi-of-ops transformation. Both transformations find optimizations opportunities during analysis. Both transformations emit new code after the analysis. The only difference is the point where the two transformations emit the new code. In case of phi-of-ops transformation, the new phi nodes are emitted in eliminateInstructions(),. In case of load coercion, the new code is emitted just before eliminateInstructions() for the reasons that are mentioned here: https://reviews.llvm.org/D124071#inline-1188926 .

[nikic]

Ping!

[asbirlea]

It seems unnecessary to force all uses to instantiate and pass the BatchAA.
Can this remain part of the ClobberWalkerBase instead? Default the calls to getClobberingMemoryAccess to instantiate a BatchAA internally and pass to the ClobberWalker.
Then, there can be an additional API added to override the above behavior when useful (known as safe): either passing a given BatchAA like current patch, or, keeping a BatchAA in the ClobberWalker itself instead of the AA, and being able to "set" it to not re-initialize it on each call (and perhaps "reset" to reseting each time).
What do you think?

[nikic]

In D136164#3900876, @asbirlea wrote:

It seems unnecessary to force all uses to instantiate and pass the BatchAA.
Can this remain part of the ClobberWalkerBase instead? Default the calls to getClobberingMemoryAccess to instantiate a BatchAA internally and pass to the ClobberWalker.
Then, there can be an additional API added to override the above behavior when useful (known as safe): either passing a given BatchAA like current patch, or, keeping a BatchAA in the ClobberWalker itself instead of the AA, and being able to "set" it to not re-initialize it on each call (and perhaps "reset" to reseting each time).
What do you think?

We currently have 17 calls to getClobberingMemoryAccess() and if my analysis is right, I believe 15 of those can reuse the BatchAA instance in some way (though this patch mostly doesn't do it). Given this, I think it makes more sense to always require BatchAA -- it makes reuse opportunities more obvious, and is not a particularly large burden if reuse is not possible. I'd agree if it were the other way around and BatchAA reuse was not possible in most cases.

[nikic]

@asbirlea Any thoughts on my last comment?

[asbirlea]

Makes sense to use BAA at call sites if the usage is such!

Regarding the internal walker APIs, please see the inline comments. I don't think we need to pass the BAA instance everywhere, that was the goal of the class fields.

llvm/lib/Analysis/MemorySSA.cpp

520

Keep a pointer to a BatchAA instance - set when Query is created. Prevents having to pass it through all the APIs.

560

Use class BAA.

627

Use class BAA.

770

Use class BAA.

938

Set class BAA here, the same as Query.

[nikic]

Use member in ClobberWalker, and add wrapper APIs that don't require BatchAAResults (and just create it internally). Something I previously missed was updating the unit tests, and creating the BatchAA instances there does get pretty annoying for no benefit.

This patch now only ensures that individual queries use BatchAA, but doesn't yet share BatchAA across multiple queries anywhere. I'll land that part separately.

[asbirlea]

lgtm.

llvm/include/llvm/Analysis/MemorySSA.h

public:
 
   /// By default, uses are *not* optimized during MemorySSA construction.
   /// Calling this method will attempt to optimize all MemoryUses, if this has
   /// not happened yet for this MemorySSA instance. This should be done if you
   /// plan to query the clobbering access for most uses, or if you walk the
   /// def-use chain of uses.
   void ensureOptimizedUses();
 
+  AliasAnalysis &getAA() { return *AA; }
+
 protected:
   // Used by Memory SSA dumpers and wrapper pass
   friend class MemorySSAPrinterLegacyPass;
   friend class MemorySSAUpdater;
 
   void verifyOrderingDominationAndDefUses(
       Function &F, VerificationLevel = VerificationLevel::Fast) const;
   void verifyDominationNumbers(const Function &F) const;
void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
                                InsertionPlace);
   void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
                              AccessList::iterator);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
                                       const MemoryUseOrDef *Template = nullptr,
                                       bool CreationMustSucceed = true);
 
 private:
-  template <class AliasAnalysisType> class ClobberWalkerBase;
-  template <class AliasAnalysisType> class CachingWalker;
-  template <class AliasAnalysisType> class SkipSelfWalker;
+  class ClobberWalkerBase;
+  class CachingWalker;
+  class SkipSelfWalker;
   class OptimizeUses;
 
-  CachingWalker<AliasAnalysis> *getWalkerImpl();
+  CachingWalker *getWalkerImpl();
   void buildMemorySSA(BatchAAResults &BAA);
 
   void prepareForMoveTo(MemoryAccess *, BasicBlock *);
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
 
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
   using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
 
private:
 
   // Domination mappings
   // Note that the numbering is local to a block, even though the map is
   // global.
   mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
   mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
 
   // Memory SSA building info
-  std::unique_ptr<ClobberWalkerBase<AliasAnalysis>> WalkerBase;
-  std::unique_ptr<CachingWalker<AliasAnalysis>> Walker;
-  std::unique_ptr<SkipSelfWalker<AliasAnalysis>> SkipWalker;
+  std::unique_ptr<ClobberWalkerBase> WalkerBase;
+  std::unique_ptr<CachingWalker> Walker;
+  std::unique_ptr<SkipSelfWalker> SkipWalker;
   unsigned NextID = 0;
   bool IsOptimized = false;
 };
 
 /// Enables verification of MemorySSA.
 ///
 /// The checks which this flag enables is exensive and disabled by default
 /// unless `EXPENSIVE_CHECKS` is defined.  The flag `-verify-memoryssa` can be
public:
   ///   store %b
   /// }
   /// 3 = MemoryPhi(2, 1)
   /// MemoryUse(3)
   /// load %a
   ///
   /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
   /// in the if (a) branch.
-  MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
+  MemoryAccess *getClobberingMemoryAccess(const Instruction *I,
+                                          BatchAAResults &AA) {
     MemoryAccess *MA = MSSA->getMemoryAccess(I);
     assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
-    return getClobberingMemoryAccess(MA);
+    return getClobberingMemoryAccess(MA, AA);
   }
 
   /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
   /// but takes a MemoryAccess instead of an Instruction.
-  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0;
+  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                                  BatchAAResults &AA) = 0;
 
   /// Given a potentially clobbering memory access and a new location,
   /// calling this will give you the nearest dominating clobbering MemoryAccess
   /// (by skipping non-aliasing def links).
   ///
   /// This version of the function is mainly used to disambiguate phi translated
   /// pointers, where the value of a pointer may have changed from the initial
   /// memory access. Note that this expects to be handed either a MemoryUse,
   /// or an already potentially clobbering access. Unlike the above API, if
   /// given a MemoryDef that clobbers the pointer as the starting access, it
   /// will return that MemoryDef, whereas the above would return the clobber
   /// starting from the use side of  the memory def.
   virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
-                                                  const MemoryLocation &) = 0;
+                                                  const MemoryLocation &,
+                                                  BatchAAResults &AA) = 0;
+
+  MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
+    BatchAAResults BAA(MSSA->getAA());
+    return getClobberingMemoryAccess(I, BAA);
+  }
+
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) {
+    BatchAAResults BAA(MSSA->getAA());
+    return getClobberingMemoryAccess(MA, BAA);
+  }
+
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
+                                          const MemoryLocation &Loc) {
+    BatchAAResults BAA(MSSA->getAA());
+    return getClobberingMemoryAccess(MA, Loc, BAA);
+  }
 
   /// Given a memory access, invalidate anything this walker knows about
   /// that access.
   /// This API is used by walkers that store information to perform basic cache
   /// invalidation.  This will be called by MemorySSA at appropriate times for
   /// the walker it uses or returns.
   virtual void invalidateInfo(MemoryAccess *) {}
 
 protected:
   friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
                           // constructor.
   MemorySSA *MSSA;
 };
 
 /// A MemorySSAWalker that does no alias queries, or anything else. It
 /// simply returns the links as they were constructed by the builder.
 class DoNothingMemorySSAWalker final : public MemorySSAWalker {
 public:
   // Keep the overrides below from hiding the Instruction overload of
   // getClobberingMemoryAccess.
   using MemorySSAWalker::getClobberingMemoryAccess;
 
-  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
-                                          const MemoryLocation &) override;
+                                          BatchAAResults &) override;
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                          const MemoryLocation &,
+                                          BatchAAResults &) override;
 };
 
 using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
 using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
 
 /// Iterator base class used to implement const and non-const iterators
 /// over the defining accesses of a MemoryAccess.
 template <class T>

llvm/lib/Analysis/MemorySSA.cpp

public:
   }
 };
 
 /// An assembly annotator class to print Memory SSA information in
 /// comments.
 class MemorySSAWalkerAnnotatedWriter : public AssemblyAnnotationWriter {
   MemorySSA *MSSA;
   MemorySSAWalker *Walker;
+  BatchAAResults BAA;
 
 public:
   MemorySSAWalkerAnnotatedWriter(MemorySSA *M)
-      : MSSA(M), Walker(M->getWalker()) {}
+      : MSSA(M), Walker(M->getWalker()), BAA(M->getAA()) {}
 
   void emitBasicBlockStartAnnot(const BasicBlock *BB,
                                 formatted_raw_ostream &OS) override {
     if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
       OS << "; " << *MA << "\n";
   }
 
   void emitInstructionAnnot(const Instruction *I,
                             formatted_raw_ostream &OS) override {
     if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
-      MemoryAccess *Clobber = Walker->getClobberingMemoryAccess(MA);
+      MemoryAccess *Clobber = Walker->getClobberingMemoryAccess(MA, BAA);
       OS << "; " << *MA;
       if (Clobber) {
         OS << " - clobbered by ";
         if (MSSA->isLiveOnEntryDef(Clobber))
           OS << LiveOnEntryStr;
         else
           OS << *Clobber;
       }
UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
       : IsCall(isa<CallBase>(Inst)), Inst(Inst), OriginalAccess(Access) {
     if (!IsCall)
       StartingLoc = MemoryLocation::get(Inst);
   }
 };
 
 } // end anonymous namespace
 
-template <typename AliasAnalysisType>
-static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysisType &AA,
+static bool isUseTriviallyOptimizableToLiveOnEntry(BatchAAResults &AA,
                                                    const Instruction *I) {
   // If the memory can't be changed, then loads of the memory can't be
   // clobbered.
   if (auto *LI = dyn_cast<LoadInst>(I)) {
     return I->hasMetadata(LLVMContext::MD_invariant_load) ||
            !isModSet(AA.getModRefInfoMask(MemoryLocation::get(LI)));
   }
   return false;
 }
 
 /// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing
 /// inbetween `Start` and `ClobberAt` can clobbers `Start`.
 ///
 /// This is meant to be as simple and self-contained as possible. Because it
 /// uses no cache, etc., it can be relatively expensive.
 ///
 /// \param Start     The MemoryAccess that we want to walk from.
 /// \param ClobberAt A clobber for Start.
 /// \param StartLoc  The MemoryLocation for Start.
 /// \param MSSA      The MemorySSA instance that Start and ClobberAt belong to.
 /// \param Query     The UpwardsMemoryQuery we used for our search.
 /// \param AA        The AliasAnalysis we used for our search.
 /// \param AllowImpreciseClobber Always false, unless we do relaxed verify.
 
-template <typename AliasAnalysisType>
 LLVM_ATTRIBUTE_UNUSED static void
 checkClobberSanity(const MemoryAccess *Start, MemoryAccess *ClobberAt,
                    const MemoryLocation &StartLoc, const MemorySSA &MSSA,
-                   const UpwardsMemoryQuery &Query, AliasAnalysisType &AA,
+                   const UpwardsMemoryQuery &Query, BatchAAResults &AA,
                    bool AllowImpreciseClobber = false) {
   assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?");
 
   if (MSSA.isLiveOnEntryDef(Start)) {
     assert(MSSA.isLiveOnEntryDef(ClobberAt) &&
            "liveOnEntry must clobber itself");
     return;
   }
checkClobberSanity(const MemoryAccess *Start, MemoryAccess *ClobberAt,
   assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
          "ClobberAt never acted as a clobber");
 }
 
 namespace {
 
 /// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up
 /// in one class.
-template <class AliasAnalysisType> class ClobberWalker {
+class ClobberWalker {
   /// Save a few bytes by using unsigned instead of size_t.
   using ListIndex = unsigned;
 
   /// Represents a span of contiguous MemoryDefs, potentially ending in a
   /// MemoryPhi.
   struct DefPath {
     MemoryLocation Loc;
     // Note that, because we always walk in reverse, Last will always dominate
     // First. Also note that First and Last are inclusive.
     MemoryAccess *First;
     MemoryAccess *Last;
     Optional<ListIndex> Previous;
 
     DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last,
             Optional<ListIndex> Previous)
         : Loc(Loc), First(First), Last(Last), Previous(Previous) {}
 
     DefPath(const MemoryLocation &Loc, MemoryAccess *Init,
             Optional<ListIndex> Previous)
         : DefPath(Loc, Init, Init, Previous) {}
   };
 
   const MemorySSA &MSSA;
-  AliasAnalysisType &AA;
   DominatorTree &DT;
+  BatchAAResults *AA;
   UpwardsMemoryQuery *Query;
   unsigned *UpwardWalkLimit;
 
   // Phi optimization bookkeeping:
   // List of DefPath to process during the current phi optimization walk.
   SmallVector<DefPath, 32> Paths;
   // List of visited <Access, Location> pairs; we can skip paths already
   // visited with the same memory location.
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,
                      const MemoryAccess *SkipStopAt = nullptr) const {
     assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
     assert(UpwardWalkLimit && "Need a valid walk limit");
     bool LimitAlreadyReached = false;
     // (*UpwardWalkLimit) may be 0 here, due to the loop in tryOptimizePhi. Set
     // it to 1. This will not do any alias() calls. It either returns in the
     // first iteration in the loop below, or is set back to 0 if all def chains
     // are free of MemoryDefs.
for (MemoryAccess *Current : def_chain(Desc.Last)) {
 
       if (auto *MD = dyn_cast<MemoryDef>(Current)) {
         if (MSSA.isLiveOnEntryDef(MD))
           return {MD, true};
 
         if (!--*UpwardWalkLimit)
           return {Current, true};
 
-        if (instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA))
+        if (instructionClobbersQuery(MD, Desc.Loc, Query->Inst, *AA))
           return {MD, true};
       }
     }
 
     if (LimitAlreadyReached)
       *UpwardWalkLimit = 0;
 
     assert(isa<MemoryPhi>(Desc.Last) &&
class ClobberWalker {
   /// 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 std::nullopt, 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) {
     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()) {
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) {
     assert(Paths.empty() && VisitedPhis.empty() &&
            "Reset the optimization state.");
 
     Paths.emplace_back(Loc, Start, Phi, std::nullopt);
     // 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();
 
class ClobberWalker {
   }
 
   void resetPhiOptznState() {
     Paths.clear();
     VisitedPhis.clear();
   }
 
 public:
-  ClobberWalker(const MemorySSA &MSSA, AliasAnalysisType &AA, DominatorTree &DT)
-      : MSSA(MSSA), AA(AA), DT(DT) {}
+  ClobberWalker(const MemorySSA &MSSA, DominatorTree &DT)
+      : MSSA(MSSA), DT(DT) {}
 
-  AliasAnalysisType *getAA() { return &AA; }
   /// Finds the nearest clobber for the given query, optimizing phis if
   /// possible.
-  MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q,
-                            unsigned &UpWalkLimit) {
+  MemoryAccess *findClobber(BatchAAResults &BAA, MemoryAccess *Start,
+                            UpwardsMemoryQuery &Q, unsigned &UpWalkLimit) {
+    AA = &BAA;
     Query = &Q;
     UpwardWalkLimit = &UpWalkLimit;
     // Starting limit must be > 0.
     if (!UpWalkLimit)
       UpWalkLimit++;
 
     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 (WalkResult.IsKnownClobber) {
                                           Current, Q.StartingLoc);
       verifyOptResult(OptRes);
       resetPhiOptznState();
       Result = OptRes.PrimaryClobber.Clobber;
     }
 
 #ifdef EXPENSIVE_CHECKS
     if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
-      checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
+      checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, BAA);
 #endif
     return Result;
   }
 };
 
 struct RenamePassData {
   DomTreeNode *DTN;
   DomTreeNode::const_iterator ChildIt;
void swap(RenamePassData &RHS) {
     std::swap(IncomingVal, RHS.IncomingVal);
   }
 };
 
 } // end anonymous namespace
 
 namespace llvm {
 
-template <class AliasAnalysisType> class MemorySSA::ClobberWalkerBase {
-  ClobberWalker<AliasAnalysisType> Walker;
+class MemorySSA::ClobberWalkerBase {
+  ClobberWalker Walker;
   MemorySSA *MSSA;
 
 public:
-  ClobberWalkerBase(MemorySSA *M, AliasAnalysisType *A, DominatorTree *D)
-      : Walker(*M, *A, *D), MSSA(M) {}
+  ClobberWalkerBase(MemorySSA *M, DominatorTree *D) : Walker(*M, *D), MSSA(M) {}
 
   MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
                                               const MemoryLocation &,
-                                              unsigned &);
+                                              BatchAAResults &, unsigned &);
   // Third 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 *, unsigned &, bool,
+  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, BatchAAResults &,
+                                              unsigned &, bool,
                                               bool UseInvariantGroup = true);
 };
 
 /// 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;
+  ClobberWalkerBase *Walker;
 
 public:
-  CachingWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
+  CachingWalker(MemorySSA *M, ClobberWalkerBase *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, BatchAAResults &BAA,
+                                          unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc,
-                                          unsigned &UWL) {
-    return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
+                                          BatchAAResults &BAA, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
   }
   // This method is not accessible outside of this file.
-  MemoryAccess *getClobberingMemoryAccessWithoutInvariantGroup(MemoryAccess *MA,
-                                                               unsigned &UWL) {
-    return Walker->getClobberingMemoryAccessBase(MA, UWL, false, false);
+  MemoryAccess *getClobberingMemoryAccessWithoutInvariantGroup(
+      MemoryAccess *MA, BatchAAResults &BAA, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, false, false);
   }
 
-  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
+                                          BatchAAResults &BAA) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
-    return getClobberingMemoryAccess(MA, UpwardWalkLimit);
+    return getClobberingMemoryAccess(MA, BAA, UpwardWalkLimit);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
-                                          const MemoryLocation &Loc) override {
+                                          const MemoryLocation &Loc,
+                                          BatchAAResults &BAA) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
-    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
+    return getClobberingMemoryAccess(MA, Loc, BAA, UpwardWalkLimit);
   }
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
   }
 };
 
-template <class AliasAnalysisType>
 class MemorySSA::SkipSelfWalker final : public MemorySSAWalker {
-  ClobberWalkerBase<AliasAnalysisType> *Walker;
+  ClobberWalkerBase *Walker;
 
 public:
-  SkipSelfWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
+  SkipSelfWalker(MemorySSA *M, ClobberWalkerBase *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, BatchAAResults &BAA,
+                                          unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, BAA, UWL, true);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc,
-                                          unsigned &UWL) {
-    return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
+                                          BatchAAResults &BAA, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, BAA, UWL);
   }
 
-  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
+                                          BatchAAResults &BAA) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
-    return getClobberingMemoryAccess(MA, UpwardWalkLimit);
+    return getClobberingMemoryAccess(MA, BAA, UpwardWalkLimit);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
-                                          const MemoryLocation &Loc) override {
+                                          const MemoryLocation &Loc,
+                                          BatchAAResults &BAA) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
-    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
+    return getClobberingMemoryAccess(MA, Loc, BAA, UpwardWalkLimit);
   }
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
   }
 };
 

 /// 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, CachingWalker<BatchAAResults> *Walker,
-               BatchAAResults *BAA, DominatorTree *DT)
+  OptimizeUses(MemorySSA *MSSA, CachingWalker *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 {
     bool LastKillValid;
   };
 
   void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
                            SmallVectorImpl<MemoryAccess *> &,
                            DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
 
   MemorySSA *MSSA;
-  CachingWalker<BatchAAResults> *Walker;
+  CachingWalker *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
for (MemoryAccess &MA : *Accesses) {
     unsigned UpwardWalkLimit = MaxCheckLimit;
     while (UpperBound > LocInfo.LowerBound) {
       if (isa<MemoryPhi>(VersionStack[UpperBound])) {
         // For phis, use the walker, see where we ended up, go there.
         // The invariant.group handling in MemorySSA is ad-hoc and doesn't
         // support updates, so don't use it to optimize uses.
         MemoryAccess *Result =
             Walker->getClobberingMemoryAccessWithoutInvariantGroup(
-                MU, UpwardWalkLimit);
+                MU, *AA, UpwardWalkLimit);
         // We are guaranteed to find it or something is wrong.
         while (VersionStack[UpperBound] != Result) {
           assert(UpperBound != 0);
           --UpperBound;
         }
         FoundClobberResult = true;
         break;
       }
void MemorySSA::buildMemorySSA(BatchAAResults &BAA) {
   // somewhere.
   for (auto &BB : F)
     if (!Visited.count(&BB))
       markUnreachableAsLiveOnEntry(&BB);
 }
 
 MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); }
 
-MemorySSA::CachingWalker<AliasAnalysis> *MemorySSA::getWalkerImpl() {
+MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() {
   if (Walker)
     return Walker.get();
 
   if (!WalkerBase)
-    WalkerBase =
-        std::make_unique<ClobberWalkerBase<AliasAnalysis>>(this, AA, DT);
+    WalkerBase = std::make_unique<ClobberWalkerBase>(this, DT);
 
-  Walker =
-      std::make_unique<CachingWalker<AliasAnalysis>>(this, WalkerBase.get());
+  Walker = std::make_unique<CachingWalker>(this, WalkerBase.get());
   return Walker.get();
 }
 
 MemorySSAWalker *MemorySSA::getSkipSelfWalker() {
   if (SkipWalker)
     return SkipWalker.get();
 
   if (!WalkerBase)
-    WalkerBase =
-        std::make_unique<ClobberWalkerBase<AliasAnalysis>>(this, AA, DT);
+    WalkerBase = std::make_unique<ClobberWalkerBase>(this, DT);
 
-  SkipWalker =
-      std::make_unique<SkipSelfWalker<AliasAnalysis>>(this, WalkerBase.get());
+  SkipWalker = std::make_unique<SkipSelfWalker>(this, WalkerBase.get());
   return SkipWalker.get();
  }
 
 
 // This is a helper function used by the creation routines. It places NewAccess
 // into the access and defs lists for a given basic block, at the given
 // insertion point.
 void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess,
bool MemorySSA::dominates(const MemoryAccess *Dominator,
   return dominates(Dominator, cast<MemoryAccess>(Dominatee.getUser()));
 }
 
 void MemorySSA::ensureOptimizedUses() {
   if (IsOptimized)
     return;
 
   BatchAAResults BatchAA(*AA);
-  ClobberWalkerBase<BatchAAResults> WalkerBase(this, &BatchAA, DT);
-  CachingWalker<BatchAAResults> WalkerLocal(this, &WalkerBase);
+  ClobberWalkerBase WalkerBase(this, DT);
+  CachingWalker WalkerLocal(this, &WalkerBase);
   OptimizeUses(this, &WalkerLocal, &BatchAA, DT).optimizeUses();
   IsOptimized = true;
 }
 
 void MemoryAccess::print(raw_ostream &OS) const {
   switch (getValueID()) {
   case MemoryPhiVal: return static_cast<const MemoryPhi *>(this)->print(OS);
   case MemoryDefVal: return static_cast<const MemoryDef *>(this)->print(OS);

 }
 
 MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
 
 /// 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 *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
     MemoryAccess *StartingAccess, const MemoryLocation &Loc,
-    unsigned &UpwardWalkLimit) {
+    BatchAAResults &BAA, unsigned &UpwardWalkLimit) {
   assert(!isa<MemoryUse>(StartingAccess) && "Use cannot be defining access");
 
   Instruction *I = nullptr;
   if (auto *StartingUseOrDef = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
     if (MSSA->isLiveOnEntryDef(StartingUseOrDef))
       return StartingUseOrDef;
 
     I = StartingUseOrDef->getMemoryInst();
MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
   Q.StartingLoc = Loc;
   Q.Inst = nullptr;
   Q.IsCall = false;
 
   // 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 *Clobber =
-      Walker.findClobber(StartingAccess, Q, UpwardWalkLimit);
+      Walker.findClobber(BAA, StartingAccess, Q, UpwardWalkLimit);
   LLVM_DEBUG({
     dbgs() << "Clobber starting at access " << *StartingAccess << "\n";
     if (I)
       dbgs() << "  for instruction " << *I << "\n";
     dbgs() << "  is " << *Clobber << "\n";
   });
   return Clobber;
 }
for (const User *Us : Ptr->users()) {
           getLoadStorePointerOperand(U) == Ptr && !U->isVolatile()) {
         MostDominatingInstruction = U;
       }
     }
   }
   return MostDominatingInstruction == &I ? nullptr : MostDominatingInstruction;
 }
 
-template <typename AliasAnalysisType>
-MemoryAccess *
-MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
-    MemoryAccess *MA, unsigned &UpwardWalkLimit, bool SkipSelf,
-    bool UseInvariantGroup) {
+MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
+    MemoryAccess *MA, BatchAAResults &BAA, unsigned &UpwardWalkLimit,
+    bool SkipSelf, bool UseInvariantGroup) {
   auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
   // If this is a MemoryPhi, we can't do anything.
   if (!StartingAccess)
     return MA;
 
   if (UseInvariantGroup) {
     if (auto *I = getInvariantGroupClobberingInstruction(
             *StartingAccess->getMemoryInst(), MSSA->getDomTree())) {
MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
   // We can't sanely do anything with a fence, since they conservatively clobber
   // all memory, and have no locations to get pointers from to try to
   // disambiguate.
   if (!isa<CallBase>(I) && I->isFenceLike())
     return StartingAccess;
 
   UpwardsMemoryQuery Q(I, StartingAccess);
 
-  if (isUseTriviallyOptimizableToLiveOnEntry(*Walker.getAA(), I)) {
+  if (isUseTriviallyOptimizableToLiveOnEntry(BAA, I)) {
     MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
     StartingAccess->setOptimized(LiveOnEntry);
     return LiveOnEntry;
   }
 
   MemoryAccess *OptimizedAccess;
   if (!IsOptimized) {
     // Start with the thing we already think clobbers this location
     MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
 
     // 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);
       return DefiningAccess;
     }
 
-    OptimizedAccess = Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit);
+    OptimizedAccess =
+        Walker.findClobber(BAA, DefiningAccess, Q, UpwardWalkLimit);
     StartingAccess->setOptimized(OptimizedAccess);
   } 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) && UpwardWalkLimit) {
     assert(isa<MemoryDef>(Q.OriginalAccess));
     Q.SkipSelfAccess = true;
-    Result = Walker.findClobber(OptimizedAccess, Q, UpwardWalkLimit);
+    Result = Walker.findClobber(BAA, 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;
 }
 
 MemoryAccess *
-DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
+DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA,
+                                                    BatchAAResults &) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
     return Use->getDefiningAccess();
   return MA;
 }
 
 MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
-    MemoryAccess *StartingAccess, const MemoryLocation &) {
+    MemoryAccess *StartingAccess, const MemoryLocation &, BatchAAResults &) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
     return Use->getDefiningAccess();
   return StartingAccess;
 }
 
 void MemoryPhi::deleteMe(DerivedUser *Self) {
   delete static_cast<MemoryPhi *>(Self);
 }