Index: include/llvm/Analysis/MemorySSA.h
===================================================================
--- include/llvm/Analysis/MemorySSA.h
+++ include/llvm/Analysis/MemorySSA.h
@@ -563,6 +563,40 @@
     return getIncomingValue(Idx);
   }
 
+  void deleteIncoming(const unsigned I) {
+    unsigned E = getNumOperands();
+    assert((I < E) && "Cannot remove out of bounds Phi entry.");
+    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);
+  }
+
+  void deleteIncomingBlock(const BasicBlock *BB) {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (block_begin()[I] == BB) {
+        deleteIncoming(I);
+        E = getNumOperands();
+        --I;
+      }
+    assert((getNumOperands() >= 1) &&
+           "Cannot remove all incoming blocks in a MemoryPhi.");
+  }
+
+  void deleteIncomingValue(const MemoryAccess *MA) {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (getIncomingValue(I) == MA) {
+        deleteIncoming(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,12 @@
       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.
+  void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks);
+
   /// Get handle on MemorySSA.
   MemorySSA* getMemorySSA() const { return MSSA; }
 
Index: lib/Analysis/MemorySSAUpdater.cpp
===================================================================
--- lib/Analysis/MemorySSAUpdater.cpp
+++ lib/Analysis/MemorySSAUpdater.cpp
@@ -492,6 +492,51 @@
   MSSA->removeFromLists(MA);
 }
 
+void MemorySSAUpdater::removeBlocks(
+    const SmallPtrSetImpl<BasicBlock *> &DeadBlocks) {
+
+  // First delete all uses of BB in MemoryPhis.
+  for (BasicBlock *BB : DeadBlocks) {
+    TerminatorInst *TI = BB->getTerminator();
+    if (TI)
+      for (BasicBlock *Succ : TI->successors()) {
+        if (!DeadBlocks.count(Succ))
+          if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
+            MP->deleteIncomingBlock(BB);
+            if (MP->getNumIncomingValues() == 1)
+              removeMemoryAccess(MP);
+          }
+      }
+  }
+
+  // Next, delete all memory accesses in each block (and their uses)
+  for (BasicBlock *BB : DeadBlocks) {
+    while (MemorySSA::AccessList *Accesses =
+               MSSA->getWritableBlockAccesses(BB)) {
+      MemoryAccess *MA = &*Accesses->begin();
+      // Not special casing MemoryPhis.
+      if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
+        if (MA->hasValueHandle())
+          ValueHandleBase::ValueIsDeleted(MA);
+
+        while (!MA->use_empty()) {
+          Use &U = *MA->use_begin();
+          MemoryAccess *User = dyn_cast<MemoryAccess>(U.getUser());
+          // If user won't be deleted, it must be a MemoryPhi losing a value.
+          // We should have addressed that in the pass above.
+          assert(DeadBlocks.count(User->getBlock()) &&
+                 "User must be deleted too.");
+          // So, the access using MA will be deleted anyway, replace use with
+          // LoE to clear MA's uses.
+          U.set(MSSA->getLiveOnEntryDef());
+        }
+      }
+      MSSA->removeFromLookups(MA);
+      MSSA->removeFromLists(MA);
+    }
+  }
+}
+
 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
     Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
     MemorySSA::InsertionPlace Point) {