Index: llvm/trunk/include/llvm/Analysis/MemorySSA.h
===================================================================
--- llvm/trunk/include/llvm/Analysis/MemorySSA.h
+++ llvm/trunk/include/llvm/Analysis/MemorySSA.h
@@ -578,10 +578,11 @@
     setNumHungOffUseOperands(getNumOperands() - 1);
   }
 
-  // After deleting incoming block BB, the incoming blocks order may be changed.
-  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
+  // After deleting entries that satisfy Pred, remaining entries may have
+  // changed order.
+  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
     for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
-      if (block_begin()[I] == BB) {
+      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
         unorderedDeleteIncoming(I);
         E = getNumOperands();
         --I;
@@ -590,17 +591,17 @@
            "Cannot remove all incoming blocks in a MemoryPhi.");
   }
 
+  // After deleting incoming block BB, the incoming blocks order may be changed.
+  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
+    unorderedDeleteIncomingIf(
+        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
+  }
+
   // 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.");
+    unorderedDeleteIncomingIf(
+        [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
   }
 
   static bool classof(const Value *V) {
Index: llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h
===================================================================
--- llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h
+++ llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h
@@ -124,6 +124,14 @@
   /// |------|        |------|
   void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
                                Instruction *Start);
+  /// BasicBlock Old had New, an empty BasicBlock, added directly before it,
+  /// and the predecessors in Preds that used to point to Old, now point to
+  /// New. If New is the only predecessor, move Old's Phi, if present, to New.
+  /// Otherwise, add a new Phi in New with appropriate incoming values, and
+  /// update the incoming values in Old's Phi node too, if present.
+  void
+  wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New,
+                                               ArrayRef<BasicBlock *> Preds);
 
   // The below are utility functions. Other than creation of accesses to pass
   // to insertDef, and removeAccess to remove accesses, you should generally
Index: llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp
===================================================================
--- llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp
+++ llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp
@@ -499,6 +499,35 @@
   return MA;
 }
 
+void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
+    BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds) {
+  assert(!MSSA->getWritableBlockAccesses(New) &&
+         "Access list should be null for a new block.");
+  MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
+  if (!Phi)
+    return;
+  if (pred_size(Old) == 1) {
+    assert(pred_size(New) == Preds.size() &&
+           "Should have moved all predecessors.");
+    MSSA->moveTo(Phi, New, MemorySSA::Beginning);
+  } else {
+    assert(!Preds.empty() && "Must be moving at least one predecessor to the "
+                             "new immediate predecessor.");
+    MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
+    SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
+    Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
+      if (PredsSet.count(B)) {
+        NewPhi->addIncoming(MA, B);
+        return true;
+      }
+      return false;
+    });
+    Phi->addIncoming(NewPhi, New);
+    if (onlySingleValue(NewPhi))
+      removeMemoryAccess(NewPhi);
+  }
+}
+
 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
   assert(!MSSA->isLiveOnEntryDef(MA) &&
          "Trying to remove the live on entry def");