Index: llvm/lib/Analysis/DomTreeUpdater.cpp
===================================================================
--- llvm/lib/Analysis/DomTreeUpdater.cpp
+++ llvm/lib/Analysis/DomTreeUpdater.cpp
@@ -12,11 +12,13 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Support/GenericDomTree.h"
 #include <algorithm>
 #include <functional>
+#include <utility>
 
 namespace llvm {
 
@@ -267,25 +269,37 @@
     return;
 
   if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
-    SmallVector<DominatorTree::UpdateType, 8> Seen;
-    for (const auto U : Updates)
-      // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
-      // on analysis.
-      if (llvm::none_of(
-              Seen,
-              [U](const DominatorTree::UpdateType S) { return S == U; }) &&
-          isUpdateValid(U) && !isSelfDominance(U)) {
-        Seen.push_back(U);
-        if (Strategy == UpdateStrategy::Lazy)
-          applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
+    SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
+    SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
+    for (const auto U : Updates) {
+      auto Edge = std::make_pair(U.getFrom(), U.getTo());
+      // Because it is illegal to submit updates that have already been applied,
+      // it is safe to infer the existence of an edge from the first update
+      // to this edge.
+      // If the first update to an edge is "Delete", it means that the edge
+      // existed before. If the first update to an edge is "Insert", it means
+      // that the edge didn't exist before.
+      if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
+        Seen.insert(Edge);
+        // If the update doesn't appear in the CFG, it means that
+        // either the change isn't made or relevant operations
+        // result in a no-op.
+        if (isUpdateValid(U)) {
+          if (isLazy())
+            applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
+          else
+            DeduplicatedUpdates.push_back(U);
+        }
       }
+    }
+
     if (Strategy == UpdateStrategy::Lazy)
       return;
 
     if (DT)
-      DT->applyUpdates(Seen);
+      DT->applyUpdates(DeduplicatedUpdates);
     if (PDT)
-      PDT->applyUpdates(Seen);
+      PDT->applyUpdates(DeduplicatedUpdates);
     return;
   }
 
Index: llvm/unittests/Analysis/DomTreeUpdaterTest.cpp
===================================================================
--- llvm/unittests/Analysis/DomTreeUpdaterTest.cpp
+++ llvm/unittests/Analysis/DomTreeUpdaterTest.cpp
@@ -724,3 +724,69 @@
   DTU.recalculate(*F);
   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 }
+
+TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) {
+  StringRef FuncName = "f";
+  StringRef ModuleString = R"(
+                           define i32 @f() {
+                           bb0:
+                              br label %bb1
+                           bb1:
+                              ret i32 1
+                           bb2:
+                              ret i32 1
+                           }
+                           )";
+  // Make the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+  Function *F = M->getFunction(FuncName);
+
+  // Make the DTU.
+  DominatorTree DT(*F);
+  DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
+  ASSERT_TRUE(DTU.getDomTree().verify());
+
+  Function::iterator FI = F->begin();
+  BasicBlock *BB0 = &*FI++;
+  BasicBlock *BB1 = &*FI++;
+  BasicBlock *BB2 = &*FI++;
+
+  // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+  BB0->getTerminator()->eraseFromParent();
+  BranchInst::Create(BB1, BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+
+  // Update the DTU and simulate duplicates.
+  DTU.applyUpdates({{DominatorTree::Delete, BB0, BB1},
+                    {DominatorTree::Delete, BB0, BB1},
+                    {DominatorTree::Insert, BB0, BB1},
+                    {DominatorTree::Insert, BB0, BB1},
+                    {DominatorTree::Insert, BB0, BB1}});
+
+  // The above operations result in a no-op.
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  // Update the DTU. Simulate an invalid update.
+  DTU.applyUpdates({{DominatorTree::Delete, BB0, BB1}});
+  ASSERT_FALSE(DTU.hasPendingUpdates());
+
+  // CFG Change: remove bb0 -> bb1.
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+  BB0->getTerminator()->eraseFromParent();
+
+  // Update the DTU and simulate invalid updates.
+  DTU.applyUpdates({{DominatorTree::Delete, BB0, BB1},
+                    {DominatorTree::Insert, BB0, BB1},
+                    {DominatorTree::Delete, BB0, BB1},
+                    {DominatorTree::Insert, BB0, BB1},
+                    {DominatorTree::Insert, BB0, BB1}});
+  ASSERT_TRUE(DTU.hasPendingUpdates());
+
+  // CFG Change: add bb0 -> bb2.
+  BranchInst::Create(BB2, BB0);
+  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+  DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}});
+  ASSERT_TRUE(DTU.getDomTree().verify());
+}
\ No newline at end of file