[MemorySSA] Extend walker API taking in a MemoryLocation to take in a Stop access.

[asbirlea]

Summary

draft

[nikic]

llvm/lib/Analysis/MemorySSA.cpp

966

I would make assert(!Stop || MSSA.dominates(Stop, Start)) a precondition for specifying the stop access. I don't think the intended semantics of a non-dominating stop point are clear, and I don't see an immediate use-case.

llvm/include/llvm/Analysis/MemorySSA.h

public:
   ///
   /// 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;
+  virtual MemoryAccess *
+  getClobberingMemoryAccess(MemoryAccess *, const MemoryLocation &,
+                            MemoryAccess *S = nullptr) = 0;
 
   /// 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;
+                                          const MemoryLocation &,
+                                          MemoryAccess *S = nullptr) 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:
   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,
-                            unsigned &UpWalkLimit) {
+                            unsigned &UpWalkLimit,
+                            MemoryAccess *Stop = nullptr) {
     Query = &Q;
     UpwardWalkLimit = &UpWalkLimit;
     // Starting limit must be > 0.
     if (!UpWalkLimit)
       UpWalkLimit++;
 
     MemoryAccess *Current = Start;
+    MemoryAccess *StopAt =
+        (Stop && MSSA.dominates(Stop, Start)) ? Stop : nullptr;
     // 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, StopAt);
     MemoryAccess *Result;
-    if (WalkResult.IsKnownClobber) {
+    if (WalkResult.IsKnownClobber || (StopAt && WalkResult.Result == StopAt)) {
       Result = WalkResult.Result;
       Q.AR = WalkResult.AR;
     } else {
       OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
                                           Current, Q.StartingLoc);
       verifyOptResult(OptRes);
       resetPhiOptznState();
       Result = OptRes.PrimaryClobber.Clobber;
     }
 
 #ifdef EXPENSIVE_CHECKS
-    if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
+    if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0 && !StopAt)
       checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
 #endif
     return Result;
   }
 };
 
 struct RenamePassData {
   DomTreeNode *DTN;
template <class AliasAnalysisType> class MemorySSA::ClobberWalkerBase {
   MemorySSA *MSSA;
 
 public:
   ClobberWalkerBase(MemorySSA *M, AliasAnalysisType *A, DominatorTree *D)
       : Walker(*M, *A, *D), MSSA(M) {}
 
   MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
                                               const MemoryLocation &,
-                                              unsigned &);
+                                              MemoryAccess *, 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);
 };
public:
 
   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 *Stop, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, Stop, UWL);
   }
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
     return getClobberingMemoryAccess(MA, UpwardWalkLimit);
   }
-  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
-                                          const MemoryLocation &Loc) override {
+  MemoryAccess *
+  getClobberingMemoryAccess(MemoryAccess *MA, const MemoryLocation &Loc,
+                            MemoryAccess *Stop = nullptr) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
-    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
+    return getClobberingMemoryAccess(MA, Loc, Stop, 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;
 
 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 *Stop, unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, Loc, Stop, UWL);
   }
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
     return getClobberingMemoryAccess(MA, UpwardWalkLimit);
   }
-  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
-                                          const MemoryLocation &Loc) override {
+  MemoryAccess *
+  getClobberingMemoryAccess(MemoryAccess *MA, const MemoryLocation &Loc,
+                            MemoryAccess *Stop = nullptr) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
-    return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
+    return getClobberingMemoryAccess(MA, Loc, Stop, UpwardWalkLimit);
   }
 
   void invalidateInfo(MemoryAccess *MA) override {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
       MUD->resetOptimized();
   }
 };
 

 /// 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,
-    unsigned &UpwardWalkLimit) {
+    MemoryAccess *StopAccess, 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, UpwardWalkLimit);
+      Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit, StopAccess);
   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 *
 DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
     return Use->getDefiningAccess();
   return MA;
 }
 
 MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
-    MemoryAccess *StartingAccess, const MemoryLocation &) {
+    MemoryAccess *StartingAccess, const MemoryLocation &, MemoryAccess *Stop) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
     return Use->getDefiningAccess();
   return StartingAccess;
 }
 
 void MemoryPhi::deleteMe(DerivedUser *Self) {
   delete static_cast<MemoryPhi *>(Self);
 }
 
 void MemoryDef::deleteMe(DerivedUser *Self) {
   delete static_cast<MemoryDef *>(Self);
 }
 
 void MemoryUse::deleteMe(DerivedUser *Self) {
   delete static_cast<MemoryUse *>(Self);
 }