Index: include/llvm/Analysis/MemorySSAUpdater.h
===================================================================
--- include/llvm/Analysis/MemorySSAUpdater.h
+++ include/llvm/Analysis/MemorySSAUpdater.h
@@ -221,14 +221,14 @@
   /// 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.
-  void removeMemoryAccess(MemoryAccess *);
+  void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false);
 
   /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
   /// This should be called when an instruction (load/store) is deleted from
   /// the program.
-  void removeMemoryAccess(const Instruction *I) {
+  void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) {
     if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
-      removeMemoryAccess(MA);
+      removeMemoryAccess(MA, OptimizePhis);
   }
 
   /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Index: lib/Analysis/MemorySSAUpdater.cpp
===================================================================
--- lib/Analysis/MemorySSAUpdater.cpp
+++ lib/Analysis/MemorySSAUpdater.cpp
@@ -1051,7 +1051,7 @@
   }
 }
 
-void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
+void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
   assert(!MSSA->isLiveOnEntryDef(MA) &&
          "Trying to remove the live on entry def");
   // We can only delete phi nodes if they have no uses, or we can replace all
@@ -1070,6 +1070,8 @@
     NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
   }
 
+  SmallSetVector<MemoryPhi *, 4> PhisToOptimize;
+
   // Re-point the uses at our defining access
   if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
     // Reset optimized on users of this store, and reset the uses.
@@ -1089,6 +1091,9 @@
       Use &U = *MA->use_begin();
       if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
         MUD->resetOptimized();
+      if (OptimizePhis)
+        if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
+          PhisToOptimize.insert(MP);
       U.set(NewDefTarget);
     }
   }
@@ -1097,6 +1102,11 @@
   // are doing things here
   MSSA->removeFromLookups(MA);
   MSSA->removeFromLists(MA);
+
+  // Optionally optimize Phi uses. This will recursively remove trivial phis.
+  for (MemoryPhi *MP : PhisToOptimize)
+    if (onlySingleValue(MP))
+      removeMemoryAccess(MP, true);
 }
 
 void MemorySSAUpdater::removeBlocks(