diff --git a/llvm/include/llvm/IR/CFGDiff.h b/llvm/include/llvm/IR/CFGDiff.h
--- a/llvm/include/llvm/IR/CFGDiff.h
+++ b/llvm/include/llvm/IR/CFGDiff.h
@@ -82,10 +82,20 @@
   UpdateMapType SuccDelete;
   UpdateMapType PredInsert;
   UpdateMapType PredDelete;
+  // By default, it is assumed that, given a CFG and a set of updates, we wish
+  // to apply these updates. If UpdatedAreReverseApplied is set, the updates
+  // will be applied in reverse: deleted edges are considered re-added and
+  // inserted edges are considered deleted when returning children.
+  bool UpdatedAreReverseApplied;
   // Using a singleton empty vector for all node requests with no
   // children.
   SmallVector<NodePtr, 1> Empty;
 
+  // Keep the list of legalized updates for a deterministic order of updates
+  // when using a GraphDiff for incremental updates in the DominatorTree.
+  // The list is kept in reverse to allow popping from end.
+  SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
+
   void printMap(raw_ostream &OS, const UpdateMapType &M) const {
     for (auto Pair : M)
       for (auto Child : Pair.second) {
@@ -99,12 +109,17 @@
   }
 
 public:
-  GraphDiff() {}
-  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates) {
-    SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;
-    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
+  GraphDiff() : UpdatedAreReverseApplied(false) {}
+  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates,
+            bool ReverseApplyUpdates = false) {
+    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph,
+                                  /*ReverseResultOrder=*/true);
+    // The legalized updates are stored in reverse so we can pop_back when doing
+    // incremental updates.
     for (auto U : LegalizedUpdates) {
-      if (U.getKind() == cfg::UpdateKind::Insert) {
+      bool isInsert =
+          (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates;
+      if (isInsert) {
         SuccInsert[U.getFrom()].push_back(U.getTo());
         PredInsert[U.getTo()].push_back(U.getFrom());
       } else {
@@ -112,9 +127,47 @@
         PredDelete[U.getTo()].push_back(U.getFrom());
       }
     }
+    UpdatedAreReverseApplied = ReverseApplyUpdates;
+  }
+
+  iterator_range<typename SmallVectorImpl<cfg::Update<NodePtr>>::const_iterator>
+  getLegalizedUpdates() const {
+    return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end());
+  }
+
+  unsigned getNoLegalizedUpdates() const { return LegalizedUpdates.size(); }
+
+  cfg::Update<NodePtr> popUpdateForIncrementalUpdates() {
+    assert(!LegalizedUpdates.empty() && "No updates to apply!");
+    auto U = LegalizedUpdates.pop_back_val();
+    UpdateMapType *SuccMap, *PredMap;
+    bool isInsert =
+        (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied;
+    if (isInsert) {
+      SuccMap = &SuccInsert;
+      PredMap = &PredInsert;
+    } else {
+      SuccMap = &SuccDelete;
+      PredMap = &PredDelete;
+    }
+    auto &SuccList = (*SuccMap)[U.getFrom()];
+    assert(SuccList.back() == U.getTo());
+    SuccList.pop_back();
+    if (SuccList.empty())
+      SuccMap->erase(U.getFrom());
+
+    auto &PredList = (*PredMap)[U.getTo()];
+    assert(PredList.back() == U.getFrom());
+    PredList.pop_back();
+    if (PredList.empty())
+      PredMap->erase(U.getTo());
+    return U;
   }
 
   bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
+    // Used to filter nullptr in clang.
+    if (BB == nullptr)
+      return true;
     auto &DeleteChildren =
         (InverseEdge != InverseGraph) ? PredDelete : SuccDelete;
     auto It = DeleteChildren.find(BB);
diff --git a/llvm/include/llvm/Support/CFGUpdate.h b/llvm/include/llvm/Support/CFGUpdate.h
--- a/llvm/include/llvm/Support/CFGUpdate.h
+++ b/llvm/include/llvm/Support/CFGUpdate.h
@@ -62,7 +62,7 @@
 template <typename NodePtr>
 void LegalizeUpdates(ArrayRef<Update<NodePtr>> AllUpdates,
                      SmallVectorImpl<Update<NodePtr>> &Result,
-                     bool InverseGraph) {
+                     bool InverseGraph, bool ReverseResultOrder = false) {
   // Count the total number of inserions of each edge.
   // Each insertion adds 1 and deletion subtracts 1. The end number should be
   // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
@@ -104,11 +104,19 @@
       Operations[{U.getTo(), U.getFrom()}] = int(i);
   }
 
-  llvm::sort(Result,
+  if (!ReverseResultOrder)
+    llvm::
+        sort(Result,
              [&Operations](const Update<NodePtr> &A, const Update<NodePtr> &B) {
                return Operations[{A.getFrom(), A.getTo()}] >
                       Operations[{B.getFrom(), B.getTo()}];
              });
+  else
+    llvm::sort(Result, [&Operations](const Update<NodePtr> &A,
+                                     const Update<NodePtr> &B) {
+      return Operations[{A.getFrom(), A.getTo()}] <
+             Operations[{B.getFrom(), B.getTo()}];
+    });
 }
 
 } // end namespace cfg
diff --git a/llvm/lib/Analysis/MemorySSAUpdater.cpp b/llvm/lib/Analysis/MemorySSAUpdater.cpp
--- a/llvm/lib/Analysis/MemorySSAUpdater.cpp
+++ b/llvm/lib/Analysis/MemorySSAUpdater.cpp
@@ -781,24 +781,24 @@
 
 void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
                                     DominatorTree &DT) {
-  SmallVector<CFGUpdate, 4> RevDeleteUpdates;
+  SmallVector<CFGUpdate, 4> DeleteUpdates;
   SmallVector<CFGUpdate, 4> InsertUpdates;
   for (auto &Update : Updates) {
     if (Update.getKind() == DT.Insert)
       InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
     else
-      RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
+      DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
   }
 
-  if (!RevDeleteUpdates.empty()) {
+  if (!DeleteUpdates.empty()) {
     // Update for inserted edges: use newDT and snapshot CFG as if deletes had
     // not occurred.
     // FIXME: This creates a new DT, so it's more expensive to do mix
     // delete/inserts vs just inserts. We can do an incremental update on the DT
     // to revert deletes, than re-delete the edges. Teaching DT to do this, is
     // part of a pending cleanup.
-    DominatorTree NewDT(DT, RevDeleteUpdates);
-    GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
+    DominatorTree NewDT(DT, DeleteUpdates);
+    GraphDiff<BasicBlock *> GD(DeleteUpdates, /*ReverseApplyUpdates=*/true);
     applyInsertUpdates(InsertUpdates, NewDT, &GD);
   } else {
     GraphDiff<BasicBlock *> GD;
@@ -806,7 +806,7 @@
   }
 
   // Update for deleted edges
-  for (auto &Update : RevDeleteUpdates)
+  for (auto &Update : DeleteUpdates)
     removeEdge(Update.getFrom(), Update.getTo());
 }