Index: include/llvm/Transforms/Utils/Local.h
===================================================================
--- include/llvm/Transforms/Utils/Local.h
+++ include/llvm/Transforms/Utils/Local.h
@@ -51,6 +51,7 @@
 class LazyValueInfo;
 class LoadInst;
 class MDNode;
+class MemorySSAUpdater;
 class PHINode;
 class StoreInst;
 class TargetLibraryInfo;
@@ -141,7 +142,8 @@
 /// If that makes any of its operands trivially dead, delete them too,
 /// recursively. Return true if any instructions were deleted.
 bool RecursivelyDeleteTriviallyDeadInstructions(Value *V,
-                                        const TargetLibraryInfo *TLI = nullptr);
+                                        const TargetLibraryInfo *TLI = nullptr,
+                                        MemorySSAUpdater *MSSAUpdater = nullptr);
 
 /// Delete all of the instructions in `DeadInsts`, and all other instructions
 /// that deleting these in turn causes to be trivially dead.
@@ -153,7 +155,8 @@
 /// empty afterward.
 void RecursivelyDeleteTriviallyDeadInstructions(
     SmallVectorImpl<Instruction *> &DeadInsts,
-    const TargetLibraryInfo *TLI = nullptr);
+    const TargetLibraryInfo *TLI = nullptr,
+    MemorySSAUpdater *MSSAUpdater = nullptr);
 
 /// If the specified value is an effectively dead PHI node, due to being a
 /// def-use chain of single-use nodes that either forms a cycle or is terminated
@@ -380,7 +383,8 @@
 ///
 /// Returns true if any basic block was removed.
 bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
-                             DeferredDominance *DDT = nullptr);
+                             DeferredDominance *DDT = nullptr,
+                             MemorySSAUpdater *MSSAUpdater = nullptr);
 
 /// Combine the metadata of two instructions so that K can replace J
 ///
Index: lib/Transforms/Utils/Local.cpp
===================================================================
--- lib/Transforms/Utils/Local.cpp
+++ lib/Transforms/Utils/Local.cpp
@@ -31,6 +31,8 @@
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/BinaryFormat/Dwarf.h"
@@ -427,20 +429,22 @@
 /// instructions were deleted.
 bool
 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
-                                                 const TargetLibraryInfo *TLI) {
+                                                 const TargetLibraryInfo *TLI,
+                                                 MemorySSAUpdater *MSSAUpdater) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
     return false;
 
   SmallVector<Instruction*, 16> DeadInsts;
   DeadInsts.push_back(I);
-  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI);
+  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAUpdater);
 
   return true;
 }
 
 void llvm::RecursivelyDeleteTriviallyDeadInstructions(
-    SmallVectorImpl<Instruction *> &DeadInsts, const TargetLibraryInfo *TLI) {
+    SmallVectorImpl<Instruction *> &DeadInsts, const TargetLibraryInfo *TLI,
+    MemorySSAUpdater *MSSAUpdater) {
   // Process the dead instruction list until empty.
   while (!DeadInsts.empty()) {
     Instruction &I = *DeadInsts.pop_back_val();
@@ -467,6 +471,8 @@
         if (isInstructionTriviallyDead(OpI, TLI))
           DeadInsts.push_back(OpI);
     }
+    if (MSSAUpdater)
+      MSSAUpdater->removeMemoryAccess(&I);
 
     I.eraseFromParent();
   }
@@ -653,7 +659,7 @@
     DDT->deleteEdge(Pred, BB);
 }
 
-/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
+/// MergeBasicBlockIntoOnlyPred - DestBB is a blockewith one predecessor and its
 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 /// between them, moving the instructions in the predecessor into DestBB and
 /// deleting the predecessor block.
@@ -2054,7 +2060,8 @@
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
-                                   DeferredDominance *DDT) {
+                                   DeferredDominance *DDT,
+                                   MemorySSAUpdater *MSSAUpdater) {
   SmallPtrSet<BasicBlock*, 16> Reachable;
   bool Changed = markAliveBlocks(F, Reachable, DDT);
 
@@ -2065,6 +2072,21 @@
   assert(Reachable.size() < F.size());
   NumRemoved += F.size()-Reachable.size();
 
+  //FIXME: if the deletion order is important, build a vector, not a set.
+  // Reuse this set/vector in iteration below.
+  // Isn't iterator invalidated below?
+  SmallPtrSet<BasicBlock *, 16> DeadBlockSet;
+  for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
+    auto *BB = &*I;
+    if (Reachable.count(BB))
+      continue;
+    DeadBlockSet.insert(BB);
+  }
+
+  if (MSSAUpdater) {
+    MSSAUpdater->removeBlocks(DeadBlockSet);
+  }
+
   // Loop over all of the basic blocks that are not reachable, dropping all of
   // their internal references. Update DDT and LVI if available.
   std::vector <DominatorTree::UpdateType> Updates;