[MemorySSA] Repair AccessList invariants after insertion of new MemoryUseOrDef.

[bryant]

Summary

An invariant of AccessLists is that the defining access of a Use or Def is the nearest preceding Def node. For instance, within a BasicBlock:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryUse(n)
3 = MemoryDef(m)

1 is the nearest parent Def of 2 and 3, and m and n must be 1.

This patch simplifies the interfaces of createMemoryAccessBefore/After, and augments them to maintain this invariant.

Additionally, when inserting a new Def after an existing Def, there is currently no (clean) way to update the users of the old Def to use the new Def. So createDefiningAccess now permits the option of updating the users.

[bryant]

lib/Transforms/Utils/MemorySSA.cpp

1619

Not sure if this line (as well as the similar one above) should go away.

unittests/Transforms/Utils/MemorySSA.cpp

138

I'm unsure if this should be removed, since use replacement is already conducted inside createMemoryAccessAfter's call to createDefiningAccess.

[bryant]

Note that this depends on D26126 .

[bryant]

bryant created this revision.
bryant added reviewers: dberlin, george.burgess.iv.
bryant added a subscriber: llvm-commits.
bryant set the repository for this revision to rL LLVM.

An invariant of AccessLists is that the defining access of a Use or Def is the nearest preceding Def node.

False
This is correct for def's but not for uses.

For instance, within a BasicBlock:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryUse(n)
3 = MemoryDef(m)

1 is the nearest parent Def of 2 and 3, and m and n must be 1.

Given the above, this is incorrect.
n may be 0

IE the following is perfectly legal

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryUse(0)
3 = MemoryDef(1)

Thanks for clearing up my misunderstanding regarding MemoryUses.

This patch simplifies the interfaces of createMemoryAccessBefore/After, and augments them to maintain this invariant.

Additionally, when inserting a new Def after an existing Def, there is currently no (clean) way to update the users of the old Def to use the new Def.

RAUW works exactly to do this case.

I'm not so sure that it's sufficient. Suppose, for instance, that I wanted to insert a MemoryDef between 1 and 2 in the below AccessList:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
2 = MemoryDef(1)
3 = MemoryUse(1)

Invoking createMemoryAccess followed by RAUW of 1's uses with 4 would result in:

0 = MemoryDef(liveOnEntry)
1 = MemoryDef(0)
4 = MemoryDef(4)   ; <=======
2 = MemoryDef(4)
3 = MemoryUse(4)

So RAUW needs to happen before setting 4's defining access to 1, but this isn't possible with the current createDefiningAccess. What other options are there? RAUW with a bogus Def, create, then re-RAUW to the newly created Def? I feel like I'm missing something obvious, so clarification would be much appreciated.

[bryant]

Abandoning this in favor of https://reviews.llvm.org/D26661 . It's enough to be able to move MemoryUseOrDefs around in a semantics-preserving fashion.

include/llvm/Transforms/Utils/MemorySSA.h

public:
 
   ~MemoryAccess() override;
 
   BasicBlock *getBlock() const { return Block; }
 
   virtual void print(raw_ostream &OS) const = 0;
   virtual void dump() const;
 
+  void replaceAllUsesWith(MemoryAccess *);
+
   /// \brief The user iterators for a memory access
   typedef user_iterator iterator;
   typedef const_user_iterator const_iterator;
 
   /// \brief This iterator walks over all of the defs in a given
   /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For
   /// MemoryUse/MemoryDef, this walks the defining access.
   memoryaccess_def_iterator defs_begin();
public:
   /// Returns the new MemoryAccess.
   /// This should be called when a memory instruction is created that is being
   /// used to replace an existing memory instruction. It will *not* create PHI
   /// nodes, or verify the clobbering definition.  The clobbering definition
   /// must be non-null.
   /// Note: If a MemoryAccess already exists for I, this function will make it
   /// inaccessible and it *must* have removeMemoryAccess called on it.
   MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
-                                           MemoryAccess *Definition,
                                            MemoryUseOrDef *InsertPt);
   MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
-                                          MemoryAccess *Definition,
                                           MemoryAccess *InsertPt);
 
   /// \brief Remove a MemoryAccess from MemorySSA, including updating all
   /// definitions and uses.
   /// This should be called when a memory instruction that has a MemoryAccess
   /// associated with it is erased from the program.  For example, if a store or
   /// load is simply erased (not replaced), removeMemoryAccess should be called
   /// on the MemoryAccess for that store/load.
private:
   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 *);
+  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
+                                      bool ReplaceUses = false);
   MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
   void removeFromLookups(MemoryAccess *);
 
   void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *);
   void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
                   SmallPtrSet<BasicBlock *, 16> &Visited);
   AccessList *getOrCreateAccessList(const BasicBlock *);

lib/Transforms/Utils/MemorySSA.cpp

MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
   ValueToMemoryAccess[BB] = Phi;
   // Phi's always are placed at the front of the block.
   Accesses->push_front(Phi);
   BlockNumberingValid.erase(BB);
   return Phi;
 }
 
 MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
-                                               MemoryAccess *Definition) {
+                                               MemoryAccess *Definition,
+                                               bool ReplaceUses) {
   assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI");
   MemoryUseOrDef *NewAccess = createNewAccess(I);
   assert(
       NewAccess != nullptr &&
       "Tried to create a memory access for a non-memory touching instruction");
+  if (ReplaceUses && isa<MemoryDef>(NewAccess))
+    Definition->replaceAllUsesWith(NewAccess);
   NewAccess->setDefiningAccess(Definition);
   return NewAccess;
 }
 
 MemoryAccess *MemorySSA::createMemoryAccessInBB(Instruction *I,
                                                 MemoryAccess *Definition,
                                                 const BasicBlock *BB,
                                                 InsertionPlace Point) {
   MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
   auto *Accesses = getOrCreateAccessList(BB);
   if (Point == Beginning) {
     // It goes after any phi nodes
     auto AI = find_if(
         *Accesses, [](const MemoryAccess &MA) { return !isa<MemoryPhi>(MA); });
 
     Accesses->insert(AI, NewAccess);
   } else {
     Accesses->push_back(NewAccess);
   }
   BlockNumberingValid.erase(BB);
   return NewAccess;
 }
 
 MemoryUseOrDef *MemorySSA::createMemoryAccessBefore(Instruction *I,
-                                                    MemoryAccess *Definition,
                                                     MemoryUseOrDef *InsertPt) {
   assert(I->getParent() == InsertPt->getBlock() &&
          "New and old access must be in the same block");
-  MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
+  MemoryUseOrDef *NewAccess =
+      createDefinedAccess(I, InsertPt->getDefiningAccess());
   auto *Accesses = getOrCreateAccessList(InsertPt->getBlock());
   Accesses->insert(AccessList::iterator(InsertPt), NewAccess);
+  if (isa<MemoryDef>(NewAccess))
+    InsertPt->setDefiningAccess(NewAccess);
   BlockNumberingValid.erase(InsertPt->getBlock());
+  DEBUG(verifyMemorySSA());
   return NewAccess;
 }
 
 MemoryUseOrDef *MemorySSA::createMemoryAccessAfter(Instruction *I,
-                                                   MemoryAccess *Definition,
                                                    MemoryAccess *InsertPt) {
   assert(I->getParent() == InsertPt->getBlock() &&
          "New and old access must be in the same block");
-  MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
+  MemoryUseOrDef *NewAccess = createDefinedAccess(I, InsertPt, true);
   auto *Accesses = getOrCreateAccessList(InsertPt->getBlock());
   Accesses->insertAfter(AccessList::iterator(InsertPt), NewAccess);
   BlockNumberingValid.erase(InsertPt->getBlock());
+  DEBUG(verifyMemorySSA());
   return NewAccess;
 }
 
 /// \brief Helper function to create new memory accesses
 MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
   // The assume intrinsic has a control dependency which we model by claiming
   // that it writes arbitrarily. Ignore that fake memory dependency here.
   // FIXME: Replace this special casing with a more accurate modelling of
if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
     NewDefTarget = onlySingleValue(MP);
     assert((NewDefTarget || MP->use_empty()) &&
            "We can't delete this memory phi");
   } else {
     NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
   }
 
   // Re-point the uses at our defining access
-  if (!MA->use_empty()) {
-    // Reset optimized on users of this store, and reset the uses.
-    // A few notes:
-    // 1. This is a slightly modified version of RAUW to avoid walking the
-    // uses twice here.
-    // 2. If we wanted to be complete, we would have to reset the optimized
-    // flags on users of phi nodes if doing the below makes a phi node have all
-    // the same arguments. Instead, we prefer users to removeMemoryAccess those
-    // phi nodes, because doing it here would be N^3.
-    if (MA->hasValueHandle())
-      ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
-    // Note: We assume MemorySSA is not used in metadata since it's not really
-    // part of the IR.
-
-    while (!MA->use_empty()) {
-      Use &U = *MA->use_begin();
-      if (MemoryUse *MU = dyn_cast<MemoryUse>(U.getUser()))
-        MU->resetOptimized();
-      U.set(NewDefTarget);
-    }
-  }
+  MA->replaceAllUsesWith(NewDefTarget);
 
   // The call below to erase will destroy MA, so we can't change the order we
   // are doing things here
   removeFromLookups(MA);
 }
 
 void MemorySSA::print(raw_ostream &OS) const {
   MemorySSAAnnotatedWriter Writer(this);
void MemoryUse::print(raw_ostream &OS) const {
   OS << ')';
 }
 
 void MemoryAccess::dump() const {
   print(dbgs());
   dbgs() << "\n";
 }
 
+void MemoryAccess::replaceAllUsesWith(MemoryAccess *NewDef) {
+  if (!use_empty()) {
+    // Reset optimized on users of this store, and reset the uses.
+    // A few notes:
+    // 1. This is a slightly modified version of RAUW to avoid walking the
+    // uses twice here.
+    // 2. If we wanted to be complete, we would have to reset the optimized
+    // flags on users of phi nodes if doing the below makes a phi node have all
+    // the same arguments. Instead, we prefer users to removeMemoryAccess those
+    // phi nodes, because doing it here would be N^3.
+    if (hasValueHandle())
+      ValueHandleBase::ValueIsRAUWd(this, NewDef);
+    // Note: We assume MemorySSA is not used in metadata since it's not really
+    // part of the IR.
+
+    while (!use_empty()) {
+      Use &U = *use_begin();
+      if (MemoryUse *MU = dyn_cast<MemoryUse>(U.getUser()))
+        MU->resetOptimized();
+      U.set(NewDef);
+    }
+  }
+}
+
 char MemorySSAPrinterLegacyPass::ID = 0;
 
 MemorySSAPrinterLegacyPass::MemorySSAPrinterLegacyPass() : FunctionPass(ID) {
   initializeMemorySSAPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
 }
 
 void MemorySSAPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();

unittests/Transforms/Utils/MemorySSA.cpp

TEST_F(MemorySSATest, MoveAStore) {
   B.CreateLoad(PointerArg);
   setupAnalyses();
   MemorySSA &MSSA = *Analyses->MSSA;
 
   // Move the store
   SideStore->moveBefore(Entry->getTerminator());
   MemoryAccess *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
   MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
-  MemoryAccess *NewStoreAccess = MSSA.createMemoryAccessAfter(
-      SideStore, EntryStoreAccess, EntryStoreAccess);
+  MemoryAccess *NewStoreAccess =
+      MSSA.createMemoryAccessAfter(SideStore, EntryStoreAccess);
   EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);
   MSSA.removeMemoryAccess(SideStoreAccess);
   MSSA.verifyMemorySSA();
 }
 
 TEST_F(MemorySSATest, RemoveAPhi) {
   // We create a diamond where there is a store on one side, and then a load
   // after the merge point.  This enables us to test a bunch of different
   // removal cases.