Index: include/llvm/Analysis/MemorySSA.h
===================================================================
--- include/llvm/Analysis/MemorySSA.h
+++ include/llvm/Analysis/MemorySSA.h
@@ -563,6 +563,46 @@
     return getIncomingValue(Idx);
   }
 
+  // After deleting incoming position I, the order of incoming may be changed.
+  void unorderedDeleteIncoming(unsigned I) {
+    unsigned E = getNumOperands();
+    assert(I < E && "Cannot remove out of bounds Phi entry.");
+    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
+    // itself should be deleted.
+    assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
+                       "at least 2 values.");
+    setIncomingValue(I, getIncomingValue(E - 1));
+    setIncomingBlock(I, block_begin()[E - 1]);
+    setOperand(E - 1, nullptr);
+    block_begin()[E - 1] = nullptr;
+    setNumHungOffUseOperands(getNumOperands() - 1);
+  }
+
+  // After deleting incoming block BB, the incoming blocks order may be changed.
+  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (block_begin()[I] == BB) {
+        unorderedDeleteIncoming(I);
+        E = getNumOperands();
+        --I;
+      }
+    assert(getNumOperands() >= 1 &&
+           "Cannot remove all incoming blocks in a MemoryPhi.");
+  }
+
+  // After deleting incoming memory access MA, the incoming accesses order may
+  // be changed.
+  void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (getIncomingValue(I) == MA) {
+        unorderedDeleteIncoming(I);
+        E = getNumOperands();
+        --I;
+      }
+    assert(getNumOperands() >= 1 &&
+           "Cannot remove all incoming values in a MemoryPhi.");
+  }
+
   static bool classof(const Value *V) {
     return V->getValueID() == MemoryPhiVal;
   }
Index: include/llvm/Analysis/MemorySSAUpdater.h
===================================================================
--- include/llvm/Analysis/MemorySSAUpdater.h
+++ include/llvm/Analysis/MemorySSAUpdater.h
@@ -146,6 +146,15 @@
       removeMemoryAccess(MA);
   }
 
+  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
+  /// Assumption we make here: all uses of deleted defs and phi must either
+  /// occur in blocks about to be deleted (thus will be deleted as well), or
+  /// they occur in phis that will simply lose an incoming value.
+  /// Deleted blocks still have successor info, but their predecessor edged and
+  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
+  /// deleted after this call.
+  void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks);
+
   /// Get handle on MemorySSA.
   MemorySSA* getMemorySSA() const { return MSSA; }
 
Index: lib/Analysis/MemorySSA.cpp
===================================================================
--- lib/Analysis/MemorySSA.cpp
+++ lib/Analysis/MemorySSA.cpp
@@ -1573,6 +1573,7 @@
   assert(MA->use_empty() &&
          "Trying to remove memory access that still has uses");
   BlockNumbering.erase(MA);
+  BlockNumberingValid.erase(MA->getBlock());
   if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA))
     MUD->setDefiningAccess(nullptr);
   // Invalidate our walker's cache if necessary
Index: lib/Analysis/MemorySSAUpdater.cpp
===================================================================
--- lib/Analysis/MemorySSAUpdater.cpp
+++ lib/Analysis/MemorySSAUpdater.cpp
@@ -492,6 +492,38 @@
   MSSA->removeFromLists(MA);
 }
 
+void MemorySSAUpdater::removeBlocks(
+    const SmallPtrSetImpl<BasicBlock *> &DeadBlocks) {
+  // First delete all uses of BB in MemoryPhis.
+  for (BasicBlock *BB : DeadBlocks) {
+    if (TerminatorInst *TI = BB->getTerminator())
+      for (BasicBlock *Succ : TI->successors())
+        if (!DeadBlocks.count(Succ))
+          if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
+            MP->unorderedDeleteIncomingBlock(BB);
+            if (MP->getNumIncomingValues() == 1)
+              removeMemoryAccess(MP);
+          }
+    // Drop all references of all accesses in BB
+    if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
+      for (MemoryAccess &MA : *Acc)
+        MA.dropAllReferences();
+  }
+
+  // Next, delete all memory accesses in each block
+  for (BasicBlock *BB : DeadBlocks) {
+    MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
+    if (!Acc)
+      continue;
+    for (auto AB=Acc->begin(), AE=Acc->end(); AB!=AE;) {
+      MemoryAccess *MA = &*AB;
+      ++AB;
+      MSSA->removeFromLookups(MA);
+      MSSA->removeFromLists(MA);
+    }
+  }
+}
+
 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
     Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
     MemorySSA::InsertionPlace Point) {