[MemorySSA] Refactor CachingWalker.

[asbirlea]

Summary

Refactor caching walker to make creating a walker that skips the
starting access strightforward.

[george.burgess.iv]

Thanks for this!

lib/Analysis/MemorySSA.cpp

976

ClobberWalker is pretty big (nearly 2K). Can we instead make SkipSelfWalker carry around a pointer to MSSA->getWalker() (or just MSSA. I'm not picky)?

Since CachingWalker is opaque (modulo overrides from MemorySSAWalker) to everything that isn't in this file, I have no issue with adding "don't touch these unless ..." methods to its public API.

977

please clang-format this

979

nit: no trailing semi, please

1462

No trailing ;, please

2275

Please do the refactoring/dedup as a part of this patch, rather than as a follow up

[asbirlea]

Repurpose patch to refactor caching walker.

[george.burgess.iv]

This LGTM at a high level; just a handful of nits for you, and I think this should be good to submit

lib/Analysis/MemorySSA.cpp

959

nit: if we don't have commentary about SkipSelf elsewhere, can we please have a description of why it exists/what it's intended to do/etc.?

963

Since this is already a nested class, is this necessary?

I don't use friend often enough to know for sure

2233

nit: no else after return, please

2274

nit: if member functions are one or two lines like this, please define them in the class itself (unless there's some code ordering-related reason not to)

2275

Please also note whether SkipSelf was true/false in these debug printouts

2280

please clang-format (I think it prefers empty lines between functions)

[asbirlea]

Address comments.

[asbirlea]

lib/Analysis/MemorySSA.cpp

2280

clang-format doesn't care about this, but I added a line, seems better.

[george.burgess.iv]

Thanks!

lib/Analysis/MemorySSA.cpp

2280

Interesting -- TIL.

include/llvm/Analysis/MemorySSA.h

 /// Encapsulates MemorySSA, including all data associated with memory
 /// accesses.
 class MemorySSA {
 public:
   MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
   ~MemorySSA();
 
   MemorySSAWalker *getWalker();
+  MemorySSAWalker *getTransformWalker();
 
   /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
   /// access associated with it. If passed a basic block gets the memory phi
   /// node that exists for that block, if there is one. Otherwise, this will get
   /// a MemoryUseOrDef.
   MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
     return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
   }
void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
                                InsertionPlace);
   void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
                              AccessList::iterator);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
                                       const MemoryUseOrDef *Template = nullptr);
 
 private:
   class CachingWalker;
+  class SkipSelfWalker;
   class OptimizeUses;
 
   CachingWalker *getWalkerImpl();
   void buildMemorySSA();
   void optimizeUses();
 
   void prepareForMoveTo(MemoryAccess *, BasicBlock *);
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
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<CachingWalker> Walker;
+  std::unique_ptr<SkipSelfWalker> TransformWalker;
   unsigned NextID;
 };
 
 // Internal MemorySSA utils, for use by MemorySSA classes and walkers
 class MemorySSAUtil {
 protected:
   friend class GVNHoist;
   friend class MemorySSAWalker;

lib/Analysis/MemorySSA.cpp

 
 } // end anonymous namespace
 
 namespace llvm {
 
 /// 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.
-class MemorySSA::CachingWalker final : public MemorySSAWalker {
+class MemorySSA::CachingWalker : public MemorySSAWalker {
   ClobberWalker Walker;
 
+protected:
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
 
 public:
   CachingWalker(MemorySSA *, AliasAnalysis *, DominatorTree *);
   ~CachingWalker() override = default;
 
   using MemorySSAWalker::getClobberingMemoryAccess;
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
                                           const MemoryLocation &) override;
   void invalidateInfo(MemoryAccess *) override;
 
   void verify(const MemorySSA *MSSA) override {
     MemorySSAWalker::verify(MSSA);
     Walker.verify(MSSA);
   }
 };
 
+class MemorySSA::SkipSelfWalker final : public MemorySSA::CachingWalker {
+ public:
+  SkipSelfWalker(MemorySSA *MSSA, AliasAnalysis *AA, DominatorTree * DT)
+      : CachingWalker(MSSA,AA, DT) {};
+
+  using MemorySSA::CachingWalker::getClobberingMemoryAccess;
+
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
+};
+
 } // end namespace llvm
 
 void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal,
                                     bool RenameAllUses) {
   // Pass through values to our successors
   for (const BasicBlock *S : successors(BB)) {
     auto It = PerBlockAccesses.find(S);
     // Rename the phi nodes in our successor block
for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
     else
       Accesses->erase(AI);
     AI = Next;
   }
 }
 
 MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT)
     : AA(AA), DT(DT), F(Func), LiveOnEntryDef(nullptr), Walker(nullptr),
-      NextID(0) {
+      TransformWalker(nullptr), NextID(0) {
   buildMemorySSA();
 }
 
 MemorySSA::~MemorySSA() {
   // Drop all our references
   for (const auto &Pair : PerBlockAccesses)
     for (MemoryAccess &MA : *Pair.second)
       MA.dropAllReferences();

 MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() {
   if (Walker)
     return Walker.get();
 
   Walker = llvm::make_unique<CachingWalker>(this, AA, DT);
   return Walker.get();
 }
 
+MemorySSAWalker *MemorySSA::getTransformWalker() {
+  if (TransformWalker)
+    return TransformWalker.get();
+
+  TransformWalker = llvm::make_unique<SkipSelfWalker>(this, AA, DT);
+  return TransformWalker.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,
                                         const BasicBlock *BB,
                                         InsertionPlace Point) {
   auto *Accesses = getOrCreateAccessList(BB);
   if (Point == Beginning) {
MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
 
   // If this is an already optimized use or def, return the optimized result.
   // Note: Currently, we store the optimized def result in a separate field,
   // since we can't use the defining access.
   if (StartingAccess->isOptimized())
     return StartingAccess->getOptimized();
 
   const Instruction *I = StartingAccess->getMemoryInst();
   // 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 (!ImmutableCallSite(I) && I->isFenceLike())
     return StartingAccess;
 
   UpwardsMemoryQuery Q(I, StartingAccess);
 
   if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) {
MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
   if (MSSA->isLiveOnEntryDef(Result))
     StartingAccess->setOptimizedAccessType(None);
   else if (Q.AR == MustAlias)
     StartingAccess->setOptimizedAccessType(MustAlias);
 
   return Result;
 }
 
 MemoryAccess *
+MemorySSA::SkipSelfWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
+  LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for: " << *MA << " is ");
+  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.
+  // Note: Currently, we store the optimized def result in a separate field,
+  // since we can't use the defining access.
+  if (StartingAccess->isOptimized()) {
+    if (!isa<MemoryDef>(StartingAccess))
+      return StartingAccess->getOptimized();
+    else
+      IsOptimized = true;
+  }
+
+  const Instruction *I = StartingAccess->getMemoryInst();
+  // 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 (!ImmutableCallSite(I) && I->isFenceLike())
+    return StartingAccess;
+
+  UpwardsMemoryQuery Q(I, StartingAccess);
+
+  if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) {
+    MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
+    StartingAccess->setOptimized(LiveOnEntry);
+    StartingAccess->setOptimizedAccessType(None);
+    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);
+      StartingAccess->setOptimizedAccessType(None);
+      return DefiningAccess;
+    }
+
+    OptimizedAccess = getClobberingMemoryAccess(DefiningAccess, Q);
+    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 (isa<MemoryPhi>(OptimizedAccess) &&
+      isa<MemoryDef>(StartingAccess)) {
+    Q.SkipSelfAccess = true;
+    Result = getClobberingMemoryAccess(OptimizedAccess, Q);
+  }
+  else
+    Result = OptimizedAccess;
+
+  LLVM_DEBUG(dbgs() << "***Optimized Memory SSA clobber for " << *I << " is ");
+  LLVM_DEBUG(dbgs() << *OptimizedAccess << "\n");
+  LLVM_DEBUG(dbgs() << "***Final Memory SSA clobber for " << *I << " is ");
+  LLVM_DEBUG(dbgs() << *Result << "\n");
+
+  return Result;
+}
+
+MemoryAccess *
 DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
   if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
     return Use->getDefiningAccess();
   return MA;
 }
 
 MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
     MemoryAccess *StartingAccess, const MemoryLocation &) {