Index: include/llvm/Transforms/Utils/MemorySSA.h
===================================================================
--- include/llvm/Transforms/Utils/MemorySSA.h
+++ include/llvm/Transforms/Utils/MemorySSA.h
@@ -143,6 +143,8 @@
   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;
@@ -564,10 +566,8 @@
   /// 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
@@ -625,7 +625,8 @@
   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 *);
 
Index: lib/Transforms/Utils/MemorySSA.cpp
===================================================================
--- lib/Transforms/Utils/MemorySSA.cpp
+++ lib/Transforms/Utils/MemorySSA.cpp
@@ -1561,12 +1561,15 @@
 }
 
 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;
 }
@@ -1591,26 +1594,29 @@
 }
 
 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;
 }
 
@@ -1755,27 +1761,7 @@
   }
 
   // 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
@@ -2038,6 +2024,30 @@
   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) {
Index: unittests/Transforms/Utils/MemorySSA.cpp
===================================================================
--- unittests/Transforms/Utils/MemorySSA.cpp
+++ unittests/Transforms/Utils/MemorySSA.cpp
@@ -133,8 +133,8 @@
   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();