MSSA Walker Pre-refactor

[george.burgess.iv]

Summary

This is a set of refactors split out from the new MSSA walker. This entire patch is NFC.

No reviewers, since this is basically one big refactor. If someone wants to explicitly LGTM it, they're welcome to, but the only reasons I'm putting this up here are:

• Some of the refactors here make little sense if we don't adopt the new walker (e.g. just committing all of this seems mildly pointless), and
• Reviewing the new walker is much easier if this code is split out

This is expected to be committed with the new MSSA walker (review coming soon). Specifically, the new walker will be applied on top of this patch.

If the new walker doesn't land, some of the tiny refactors here (e.g. adding // namespace llvm, etc.) will be committed separately; I'm just lazy and didn't feel like splitting them out further. :)

[• dberlin]

lib/Transforms/Utils/MemorySSA.cpp

551

I see you removed this - this is a utility being used as part of updating for another pass i haven't submitted yet.

856

This makes no sense unless the block we are talking about is the entry block.
Otherwise, how are they in the same block?

(if it is the entry block, the loop below will give the correct answer, no?)

[george.burgess.iv]

lib/Transforms/Utils/MemorySSA.cpp

551

Sounds good; will unremove. Thanks for the heads up.

856

This is just a refactor of the old (and the new changes locallyDominates to dominates, since the only user of locallyDominates that I could find was the current walker, so we'd probably readd isLiveOnEntryDef(Dominator) anyway, since it could save domtree stuff.).

If we don't want to kill locallyDominates, I'm happy to remove this, because yes, the below loop should catch this case.

[• dberlin]

If we think dominates is necessary, go for it.

[george.burgess.iv]

Committed with D21777 (as a part of r275940), as promised.

include/llvm/Transforms/Utils/MemorySSA.h

protected:
   friend class MemorySSAAnnotatedWriter;
   friend class MemorySSAPrinterLegacyPass;
   void verifyDefUses(Function &F) const;
   void verifyDomination(Function &F) const;
   void verifyOrdering(Function &F) const;
 
 private:
   class CachingWalker;
+
+  CachingWalker *getWalkerImpl();
   void buildMemorySSA();
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
 
   void
   determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
   void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
   MemoryUseOrDef *createNewAccess(Instruction *);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
-  MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
   void removeFromLookups(MemoryAccess *);
 
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *);
   void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
                   SmallPtrSet<BasicBlock *, 16> &Visited);
   AccessList *getOrCreateAccessList(const BasicBlock *);
   AliasAnalysis *AA;
   DominatorTree *DT;

lib/Transforms/Utils/MemorySSA.cpp

public:
   }
 
   virtual void emitInstructionAnnot(const Instruction *I,
                                     formatted_raw_ostream &OS) {
     if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
       OS << "; " << *MA << "\n";
   }
 };
+}
+
+namespace {
+struct UpwardsMemoryQuery {
+  // True if our original query started off as a call
+  bool IsCall;
+  // The pointer location we started the query with. This will be empty if
+  // IsCall is true.
+  MemoryLocation StartingLoc;
+  // This is the instruction we were querying about.
+  const Instruction *Inst;
+  // Set of visited Instructions for this query.
+  DenseSet<MemoryAccessPair> Visited;
+  // Vector of visited call accesses for this query. This is separated out
+  // because you can always cache and lookup the result of call queries (IE when
+  // IsCall == true) for every call in the chain. The calls have no AA location
+  // associated with them with them, and thus, no context dependence.
+  SmallVector<const MemoryAccess *, 32> VisitedCalls;
+  // The MemoryAccess we actually got called with, used to test local domination
+  const MemoryAccess *OriginalAccess;
+
+  UpwardsMemoryQuery()
+      : IsCall(false), Inst(nullptr), OriginalAccess(nullptr) {}
+
+  UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
+      : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) {
+    if (!IsCall)
+      StartingLoc = MemoryLocation::get(Inst);
+  }
+};
+
+static bool instructionClobbersQuery(MemoryDef *MD, const MemoryLocation &Loc,
+                                     const UpwardsMemoryQuery &Query,
+                                     AliasAnalysis &AA) {
+  Instruction *DefMemoryInst = MD->getMemoryInst();
+  assert(DefMemoryInst && "Defining instruction not actually an instruction");
+
+  if (!Query.IsCall)
+    return AA.getModRefInfo(DefMemoryInst, Loc) & MRI_Mod;
+
+  ModRefInfo I = AA.getModRefInfo(DefMemoryInst, ImmutableCallSite(Query.Inst));
+  return I != MRI_NoModRef;
+}
+
+/// Cache for our caching MemorySSA walker.
+class WalkerCache {
+  DenseMap<ConstMemoryAccessPair, MemoryAccess *> Accesses;
+  DenseMap<const MemoryAccess *, MemoryAccess *> Calls;
+
+public:
+  MemoryAccess *lookup(const MemoryAccess *MA, const MemoryLocation &Loc,
+                       bool IsCall) const {
+    ++NumClobberCacheLookups;
+    MemoryAccess *R = IsCall ? Calls.lookup(MA) : Accesses.lookup({MA, Loc});
+    if (R)
+      ++NumClobberCacheHits;
+    return R;
+  }
+
+  bool insert(const MemoryAccess *MA, MemoryAccess *To,
+              const MemoryLocation &Loc, bool IsCall) {
+    // This is fine for Phis, since there are times where we can't optimize
+    // them.  Making a def its own clobber is never correct, though.
+    assert((MA != To || isa<MemoryPhi>(MA)) &&
+           "Something can't clobber itself!");
+
+    ++NumClobberCacheInserts;
+    bool Inserted;
+    if (IsCall)
+      Inserted = Calls.insert({MA, To}).second;
+    else
+      Inserted = Accesses.insert({{MA, Loc}, To}).second;
+
+    return Inserted;
+  }
 
+  bool remove(const MemoryAccess *MA, const MemoryLocation &Loc, bool IsCall) {
+    return IsCall ? Calls.erase(MA) : Accesses.erase({MA, Loc});
+  }
+
+  void clear() {
+    Accesses.clear();
+    Calls.clear();
+  }
+
+  bool contains(const MemoryAccess *MA) const {
+    for (auto &P : Accesses)
+      if (P.first.first == MA || P.second == MA)
+        return true;
+    for (auto &P : Calls)
+      if (P.first == MA || P.second == MA)
+        return true;
+    return false;
+  }
+};
+
+struct RenamePassData {
+  DomTreeNode *DTN;
+  DomTreeNode::const_iterator ChildIt;
+  MemoryAccess *IncomingVal;
+
+  RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
+                 MemoryAccess *M)
+      : DTN(D), ChildIt(It), IncomingVal(M) {}
+  void swap(RenamePassData &RHS) {
+    std::swap(DTN, RHS.DTN);
+    std::swap(ChildIt, RHS.ChildIt);
+    std::swap(IncomingVal, RHS.IncomingVal);
+  }
+};
+} // anonymous namespace
+
+namespace llvm {
 /// \brief A MemorySSAWalker that does AA walks and caching of lookups to
 /// disambiguate accesses.
 ///
 /// FIXME: The current implementation of this can take quadratic space in rare
 /// cases. This can be fixed, but it is something to note until it is fixed.
 ///
 /// In order to trigger this behavior, you need to store to N distinct locations
 /// (that AA can prove don't alias), perform M stores to other memory

 ///                                   ; MemoryLocation %b
 ///
 ///   ; For completeness' sake, loading %a or %b again would not cache *another*
 ///   ; M entries.
 ///   %r = add i32 %c, %d
 ///   ret i32 %r
 /// }
 class MemorySSA::CachingWalker final : public MemorySSAWalker {
+  WalkerCache Cache;
+  AliasAnalysis *AA;
+  DominatorTree *DT;
+
+  MemoryAccessPair UpwardsDFSWalk(MemoryAccess *, const MemoryLocation &,
+                                  UpwardsMemoryQuery &, bool);
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
+  void verifyRemoved(MemoryAccess *);
+
 public:
   CachingWalker(MemorySSA *, AliasAnalysis *, DominatorTree *);
   ~CachingWalker() override;
 
   MemoryAccess *getClobberingMemoryAccess(const Instruction *) override;
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
                                           MemoryLocation &) override;
   void invalidateInfo(MemoryAccess *) override;
-
-protected:
-  struct UpwardsMemoryQuery;
-  MemoryAccess *doCacheLookup(const MemoryAccess *, const UpwardsMemoryQuery &,
-                              const MemoryLocation &);
-
-  void doCacheInsert(const MemoryAccess *, MemoryAccess *,
-                     const UpwardsMemoryQuery &, const MemoryLocation &);
-
-  void doCacheRemove(const MemoryAccess *, const UpwardsMemoryQuery &,
-                     const MemoryLocation &);
-
-private:
-  MemoryAccessPair UpwardsDFSWalk(MemoryAccess *, const MemoryLocation &,
-                                  UpwardsMemoryQuery &, bool);
-  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
-  bool instructionClobbersQuery(const MemoryDef *, UpwardsMemoryQuery &,
-                                const MemoryLocation &Loc) const;
-  void verifyRemoved(MemoryAccess *);
-  SmallDenseMap<ConstMemoryAccessPair, MemoryAccess *>
-      CachedUpwardsClobberingAccess;
-  DenseMap<const MemoryAccess *, MemoryAccess *> CachedUpwardsClobberingCall;
-  AliasAnalysis *AA;
-  DominatorTree *DT;
 };
-}
-
-namespace {
-struct RenamePassData {
-  DomTreeNode *DTN;
-  DomTreeNode::const_iterator ChildIt;
-  MemoryAccess *IncomingVal;
 
-  RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
-                 MemoryAccess *M)
-      : DTN(D), ChildIt(It), IncomingVal(M) {}
-  void swap(RenamePassData &RHS) {
-    std::swap(DTN, RHS.DTN);
-    std::swap(ChildIt, RHS.ChildIt);
-    std::swap(IncomingVal, RHS.IncomingVal);
-  }
-};
-}
-
-namespace llvm {
 /// \brief Rename a single basic block into MemorySSA form.
 /// Uses the standard SSA renaming algorithm.
 /// \returns The new incoming value.
 MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB,
                                      MemoryAccess *IncomingVal) {
   auto It = PerBlockAccesses.find(BB);
   // Skip most processing if the list is empty.
   if (It != PerBlockAccesses.end()) {
for (auto &BB : IDFBlocks) {
     Accesses->push_front(Phi);
   }
 
   // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
   // filled in with all blocks.
   SmallPtrSet<BasicBlock *, 16> Visited;
   renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
 
-  MemorySSAWalker *Walker = getWalker();
+  CachingWalker *Walker = getWalkerImpl();
 
   // Now optimize the MemoryUse's defining access to point to the nearest
   // dominating clobbering def.
   // This ensures that MemoryUse's that are killed by the same store are
   // immediate users of that store, one of the invariants we guarantee.
   for (auto DomNode : depth_first(DT)) {
     BasicBlock *BB = DomNode->getBlock();
     auto AI = PerBlockAccesses.find(BB);
void MemorySSA::buildMemorySSA() {
 
   // Mark the uses in unreachable blocks as live on entry, so that they go
   // somewhere.
   for (auto &BB : F)
     if (!Visited.count(&BB))
       markUnreachableAsLiveOnEntry(&BB);
 }
 
-MemorySSAWalker *MemorySSA::getWalker() {
+MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); }
+
+MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() {
   if (Walker)
     return Walker.get();
 
   Walker = make_unique<CachingWalker>(this, AA, DT);
   return Walker.get();
 }
 
 MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
   if (Def)
     MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++);
   else
     MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent());
   ValueToMemoryAccess.insert(std::make_pair(I, MUD));
   return MUD;
 }
 
-MemoryAccess *MemorySSA::findDominatingDef(BasicBlock *UseBlock,
-                                           enum InsertionPlace Where) {
-  // Handle the initial case
-  if (Where == Beginning)
-    // The only thing that could define us at the beginning is a phi node
-    if (MemoryPhi *Phi = getMemoryAccess(UseBlock))
-      return Phi;
-
-  DomTreeNode *CurrNode = DT->getNode(UseBlock);
-  // Need to be defined by our dominator
-  if (Where == Beginning)
-    CurrNode = CurrNode->getIDom();
-  Where = End;
-  while (CurrNode) {
-    auto It = PerBlockAccesses.find(CurrNode->getBlock());
-    if (It != PerBlockAccesses.end()) {
-      auto &Accesses = It->second;
-      for (MemoryAccess &RA : reverse(*Accesses)) {
-        if (isa<MemoryDef>(RA) || isa<MemoryPhi>(RA))
-          return &RA;
-      }
-    }
-    CurrNode = CurrNode->getIDom();
-  }
-  return LiveOnEntryDef.get();
-}
-
 /// \brief Returns true if \p Replacer dominates \p Replacee .
 bool MemorySSA::dominatesUse(const MemoryAccess *Replacer,
                              const MemoryAccess *Replacee) const {
   if (isa<MemoryUseOrDef>(Replacee))
     return DT->dominates(Replacer->getBlock(), Replacee->getBlock());
   const auto *MP = cast<MemoryPhi>(Replacee);
   // For a phi node, the use occurs in the predecessor block of the phi node.
   // Since we may occur multiple times in the phi node, we have to check each
MemoryPhi *MemorySSA::getMemoryAccess(const BasicBlock *BB) const {
   return cast_or_null<MemoryPhi>(getMemoryAccess((const Value *)BB));
 }
 
 /// \brief Determine, for two memory accesses in the same block,
 /// whether \p Dominator dominates \p Dominatee.
 /// \returns True if \p Dominator dominates \p Dominatee.
 bool MemorySSA::locallyDominates(const MemoryAccess *Dominator,
                                  const MemoryAccess *Dominatee) const {
-
   assert((Dominator->getBlock() == Dominatee->getBlock()) &&
          "Asking for local domination when accesses are in different blocks!");
 
-  // A node dominates itself.
-  if (Dominatee == Dominator)
+  // A node dominates itself, and liveOnEntry dominates everything.
+  if (Dominatee == Dominator || isLiveOnEntryDef(Dominator))
     return true;
 
   // When Dominatee is defined on function entry, it is not dominated by another
   // memory access.
   if (isLiveOnEntryDef(Dominatee))
     return false;
 
-  // When Dominator is defined on function entry, it dominates the other memory
-  // access.
-  if (isLiveOnEntryDef(Dominator))
-    return true;
-
   // Get the access list for the block
   const AccessList *AccessList = getBlockAccesses(Dominator->getBlock());
   AccessList::const_reverse_iterator It(Dominator->getIterator());
 
   // If we hit the beginning of the access list before we hit dominatee, we must
-  // dominate it
+  // dominate it.
   return std::none_of(It, AccessList->rend(),
                       [&](const MemoryAccess &MA) { return &MA == Dominatee; });
 }
 
 const static char LiveOnEntryStr[] = "liveOnEntry";
 
 void MemoryDef::print(raw_ostream &OS) const {
   MemoryAccess *UO = getDefiningAccess();

 MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
 
 MemorySSA::CachingWalker::CachingWalker(MemorySSA *M, AliasAnalysis *A,
                                         DominatorTree *D)
     : MemorySSAWalker(M), AA(A), DT(D) {}
 
 MemorySSA::CachingWalker::~CachingWalker() {}
 
-struct MemorySSA::CachingWalker::UpwardsMemoryQuery {
-  // True if we saw a phi whose predecessor was a backedge
-  bool SawBackedgePhi;
-  // True if our original query started off as a call
-  bool IsCall;
-  // The pointer location we started the query with. This will be empty if
-  // IsCall is true.
-  MemoryLocation StartingLoc;
-  // This is the instruction we were querying about.
-  const Instruction *Inst;
-  // Set of visited Instructions for this query.
-  DenseSet<MemoryAccessPair> Visited;
-  // Vector of visited call accesses for this query. This is separated out
-  // because you can always cache and lookup the result of call queries (IE when
-  // IsCall == true) for every call in the chain. The calls have no AA location
-  // associated with them with them, and thus, no context dependence.
-  SmallVector<const MemoryAccess *, 32> VisitedCalls;
-  // The MemoryAccess we actually got called with, used to test local domination
-  const MemoryAccess *OriginalAccess;
-
-  UpwardsMemoryQuery()
-      : SawBackedgePhi(false), IsCall(false), Inst(nullptr),
-        OriginalAccess(nullptr) {}
-
-  UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
-      : SawBackedgePhi(false), IsCall(ImmutableCallSite(Inst)), Inst(Inst),
-        OriginalAccess(Access) {}
-};
-
 void MemorySSA::CachingWalker::invalidateInfo(MemoryAccess *MA) {
-
   // TODO: We can do much better cache invalidation with differently stored
   // caches.  For now, for MemoryUses, we simply remove them
   // from the cache, and kill the entire call/non-call cache for everything
   // else.  The problem is for phis or defs, currently we'd need to follow use
   // chains down and invalidate anything below us in the chain that currently
   // terminates at this access.
 
   // See if this is a MemoryUse, if so, just remove the cached info. MemoryUse
   // is by definition never a barrier, so nothing in the cache could point to
   // this use. In that case, we only need invalidate the info for the use
   // itself.
 
   if (MemoryUse *MU = dyn_cast<MemoryUse>(MA)) {
-    UpwardsMemoryQuery Q;
-    Instruction *I = MU->getMemoryInst();
-    Q.IsCall = bool(ImmutableCallSite(I));
-    Q.Inst = I;
-    if (!Q.IsCall)
-      Q.StartingLoc = MemoryLocation::get(I);
-    doCacheRemove(MA, Q, Q.StartingLoc);
+    UpwardsMemoryQuery Q(MU->getMemoryInst(), MU);
+    Cache.remove(MU, Q.StartingLoc, Q.IsCall);
   } else {
     // If it is not a use, the best we can do right now is destroy the cache.
-    CachedUpwardsClobberingCall.clear();
-    CachedUpwardsClobberingAccess.clear();
+    Cache.clear();
   }
 
 #ifdef EXPENSIVE_CHECKS
   // Run this only when expensive checks are enabled.
   verifyRemoved(MA);
 #endif
 }
 
-void MemorySSA::CachingWalker::doCacheRemove(const MemoryAccess *M,
-                                             const UpwardsMemoryQuery &Q,
-                                             const MemoryLocation &Loc) {
-  if (Q.IsCall)
-    CachedUpwardsClobberingCall.erase(M);
-  else
-    CachedUpwardsClobberingAccess.erase({M, Loc});
-}
-
-void MemorySSA::CachingWalker::doCacheInsert(const MemoryAccess *M,
-                                             MemoryAccess *Result,
-                                             const UpwardsMemoryQuery &Q,
-                                             const MemoryLocation &Loc) {
-  // This is fine for Phis, since there are times where we can't optimize them.
-  // Making a def its own clobber is never correct, though.
-  assert((Result != M || isa<MemoryPhi>(M)) &&
-         "Something can't clobber itself!");
-  ++NumClobberCacheInserts;
-  if (Q.IsCall)
-    CachedUpwardsClobberingCall[M] = Result;
-  else
-    CachedUpwardsClobberingAccess[{M, Loc}] = Result;
-}
-
-MemoryAccess *
-MemorySSA::CachingWalker::doCacheLookup(const MemoryAccess *M,
-                                        const UpwardsMemoryQuery &Q,
-                                        const MemoryLocation &Loc) {
-  ++NumClobberCacheLookups;
-  MemoryAccess *Result;
-
-  if (Q.IsCall)
-    Result = CachedUpwardsClobberingCall.lookup(M);
-  else
-    Result = CachedUpwardsClobberingAccess.lookup({M, Loc});
-
-  if (Result)
-    ++NumClobberCacheHits;
-  return Result;
-}
-
-bool MemorySSA::CachingWalker::instructionClobbersQuery(
-    const MemoryDef *MD, UpwardsMemoryQuery &Q,
-    const MemoryLocation &Loc) const {
-  Instruction *DefMemoryInst = MD->getMemoryInst();
-  assert(DefMemoryInst && "Defining instruction not actually an instruction");
-
-  if (!Q.IsCall)
-    return AA->getModRefInfo(DefMemoryInst, Loc) & MRI_Mod;
-
-  // If this is a call, mark it for caching
-  if (ImmutableCallSite(DefMemoryInst))
-    Q.VisitedCalls.push_back(MD);
-  ModRefInfo I = AA->getModRefInfo(DefMemoryInst, ImmutableCallSite(Q.Inst));
-  return I != MRI_NoModRef;
-}
-
 MemoryAccessPair MemorySSA::CachingWalker::UpwardsDFSWalk(
     MemoryAccess *StartingAccess, const MemoryLocation &Loc,
     UpwardsMemoryQuery &Q, bool FollowingBackedge) {
   MemoryAccess *ModifyingAccess = nullptr;
 
   auto DFI = df_begin(StartingAccess);
   for (auto DFE = df_end(StartingAccess); DFI != DFE;) {
     MemoryAccess *CurrAccess = *DFI;
     if (MSSA->isLiveOnEntryDef(CurrAccess))
       return {CurrAccess, Loc};
     // If this is a MemoryDef, check whether it clobbers our current query. This
     // needs to be done before consulting the cache, because the cache reports
     // the clobber for CurrAccess. If CurrAccess is a clobber for this query,
     // and we ask the cache for information first, then we might skip this
     // clobber, which is bad.
     if (auto *MD = dyn_cast<MemoryDef>(CurrAccess)) {
       // If we hit the top, stop following this path.
       // While we can do lookups, we can't sanely do inserts here unless we were
       // to track everything we saw along the way, since we don't know where we
       // will stop.
-      if (instructionClobbersQuery(MD, Q, Loc)) {
+      if (instructionClobbersQuery(MD, Loc, Q, *AA)) {
         ModifyingAccess = CurrAccess;
         break;
       }
     }
-    if (auto CacheResult = doCacheLookup(CurrAccess, Q, Loc))
+    if (auto CacheResult = Cache.lookup(CurrAccess, Loc, Q.IsCall))
       return {CacheResult, Loc};
 
     // We need to know whether it is a phi so we can track backedges.
     // Otherwise, walk all upward defs.
     if (!isa<MemoryPhi>(CurrAccess)) {
       ++DFI;
       continue;
     }
#endif
   // phi, we can add the last thing in the path to the cache, since that won't
   // be the result.
   if (DFI.getPath(N - 1) == ModifyingAccess)
     --N;
   for (; N > 1; --N) {
     MemoryAccess *CacheAccess = DFI.getPath(N - 1);
     BasicBlock *CurrBlock = CacheAccess->getBlock();
     if (!FollowingBackedge)
-      doCacheInsert(CacheAccess, ModifyingAccess, Q, Loc);
+      Cache.insert(CacheAccess, ModifyingAccess, Loc, Q.IsCall);
     if (DT->dominates(CurrBlock, OriginalBlock) &&
         (CurrBlock != OriginalBlock || !FollowingBackedge ||
          MSSA->locallyDominates(CacheAccess, StartingAccess)))
       break;
   }
 
   // Cache everything else on the way back. The caller should cache
   // StartingAccess for us.
   for (; N > 1; --N) {
     MemoryAccess *CacheAccess = DFI.getPath(N - 1);
-    doCacheInsert(CacheAccess, ModifyingAccess, Q, Loc);
+    Cache.insert(CacheAccess, ModifyingAccess, Loc, Q.IsCall);
   }
   assert(Q.Visited.size() < 1000 && "Visited too much");
 
   return {ModifyingAccess, Loc};
 }
 
 /// \brief Walk the use-def chains starting at \p MA and find
 /// the MemoryAccess that actually clobbers Loc.
MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess(
   // Conservatively, fences are always clobbers, so don't perform the walk if we
   // hit a fence.
   if (isa<FenceInst>(I))
     return StartingUseOrDef;
 
   UpwardsMemoryQuery Q;
   Q.OriginalAccess = StartingUseOrDef;
   Q.StartingLoc = Loc;
-  Q.Inst = StartingUseOrDef->getMemoryInst();
+  Q.Inst = I;
   Q.IsCall = false;
 
-  if (auto CacheResult = doCacheLookup(StartingUseOrDef, Q, Q.StartingLoc))
+  if (auto *CacheResult = Cache.lookup(StartingUseOrDef, Loc, Q.IsCall))
     return CacheResult;
 
   // 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.
   MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef)
                                      ? StartingUseOrDef->getDefiningAccess()
                                      : StartingUseOrDef;
 
   MemoryAccess *Clobber = getClobberingMemoryAccess(DefiningAccess, Q);
   // Only cache this if it wouldn't make Clobber point to itself.
   if (Clobber != StartingAccess)
-    doCacheInsert(Q.OriginalAccess, Clobber, Q, Q.StartingLoc);
+    Cache.insert(Q.OriginalAccess, Clobber, Q.StartingLoc, Q.IsCall);
   DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   DEBUG(dbgs() << *StartingUseOrDef << "\n");
   DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
   DEBUG(dbgs() << *Clobber << "\n");
   return Clobber;
 }
 
 MemoryAccess *
 MemorySSA::CachingWalker::getClobberingMemoryAccess(const Instruction *I) {
   // There should be no way to lookup an instruction and get a phi as the
   // access, since we only map BB's to PHI's. So, this must be a use or def.
   auto *StartingAccess = cast<MemoryUseOrDef>(MSSA->getMemoryAccess(I));
 
   // We can't sanely do anything with a FenceInst, they conservatively
   // clobber all memory, and have no locations to get pointers from to
   // try to disambiguate
   if (isa<FenceInst>(I))
     return StartingAccess;
 
-  UpwardsMemoryQuery Q;
-  Q.OriginalAccess = StartingAccess;
-  Q.IsCall = bool(ImmutableCallSite(I));
-  if (!Q.IsCall)
-    Q.StartingLoc = MemoryLocation::get(I);
-  Q.Inst = I;
-  if (auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc))
+  UpwardsMemoryQuery Q(I, StartingAccess);
+  if (auto *CacheResult = Cache.lookup(StartingAccess, Q.StartingLoc, Q.IsCall))
     return CacheResult;
 
   // 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))
     return DefiningAccess;
 
   MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q);
   // DFS won't cache a result for DefiningAccess. So, if DefiningAccess isn't
   // our clobber, be sure that it gets a cache entry, too.
   if (Result != DefiningAccess)
-    doCacheInsert(DefiningAccess, Result, Q, Q.StartingLoc);
-  doCacheInsert(Q.OriginalAccess, Result, Q, Q.StartingLoc);
+    Cache.insert(DefiningAccess, Result, Q.StartingLoc, Q.IsCall);
+  Cache.insert(Q.OriginalAccess, Result, Q.StartingLoc, Q.IsCall);
   // TODO: When this implementation is more mature, we may want to figure out
   // what this additional caching buys us. It's most likely A Good Thing.
   if (Q.IsCall)
     for (const MemoryAccess *MA : Q.VisitedCalls)
       if (MA != Result)
-        doCacheInsert(MA, Result, Q, Q.StartingLoc);
+        Cache.insert(MA, Result, Q.StartingLoc, Q.IsCall);
 
   DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
   DEBUG(dbgs() << *DefiningAccess << "\n");
   DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
   DEBUG(dbgs() << *Result << "\n");
 
   return Result;
 }
 
 // Verify that MA doesn't exist in any of the caches.
 void MemorySSA::CachingWalker::verifyRemoved(MemoryAccess *MA) {
-#ifndef NDEBUG
-  for (auto &P : CachedUpwardsClobberingAccess)
-    assert(P.first.first != MA && P.second != MA &&
-           "Found removed MemoryAccess in cache.");
-  for (auto &P : CachedUpwardsClobberingCall)
-    assert(P.first != MA && P.second != MA &&
-           "Found removed MemoryAccess in cache.");
-#endif // !NDEBUG
+  assert(!Cache.contains(MA) && "Found removed MemoryAccess in cache.");
 }
 
 MemoryAccess *
 DoNothingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
   MemoryAccess *MA = MSSA->getMemoryAccess(I);
   if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
     return Use->getDefiningAccess();
   return MA;
 }
 
 MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
     MemoryAccess *StartingAccess, MemoryLocation &) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
     return Use->getDefiningAccess();
   return StartingAccess;
 }
-}
+} // namespace llvm