[DTU] Refine the interface and logic of applyUpdates

[NutshellySima]

Summary

This patch separates two semantics of applyUpdates:

1. User provides an accurate CFG diff and the dominator tree is updated according to the difference of the number of edge insertions and the number of edge deletions to infer the status of an edge before and after the update.
2. User provides a sequence of hints. Updates mentioned in this sequence might never happened and even duplicated.

Logic changes:

Previously, removing invalid updates is considered a side-effect of deduplication and is not guaranteed to be reliable. To handle the second semantic, applyUpdates does validity checking before deduplication, which can cause updates that have already been applied to be submitted again. Then, different calls to applyUpdates might cause unintended consequences, for example,

DTU(Lazy) and Edge A->B exists.
1. DTU.applyUpdates({{Delete, A, B}, {Insert, A, B}}) // User expects these 2 updates result in a no-op, but {Insert, A, B} is queued
2. Remove A->B
3. DTU.applyUpdates({{Delete, A, B}}) // DTU cancels this update with {Insert, A, B} mentioned above together (Unintended)

But by restricting the precondition that updates of an edge need to be strictly ordered as how CFG changes were made, we can infer the initial status of this edge to resolve this issue.

Interface changes:
The second semantic of applyUpdates is separated to applyUpdatesPermissive.
These changes enable DTU(Lazy) to use the first semantic if needed, which is quite useful in transforms/utils.

[NutshellySima]

Further explanation:
The motivation of this patch is that currently there can be bugs like that mentioned in summary.
But after inspecting that JT and other utils never submit updates that have been applied, we can get the information of whether a specific edge <From, To> exists in the previous CFG.
For example, if we observe a sequence of updates of an edge<From, To> to be

1. Insert --> 2. Delete --> 3. Delete --> 4. Insert --> 5. Delete

Because it is supposed that "never submit updates that have been applied", so we can infer from 1. Insert that <From, To> does not exist in the previous CFG. We can then inspect the current CFG to see if there is an edge<From, To>. If there is one, it is sure that an insertion happens. Otherwise, the 5 operations result in a no-op.

[brzycki]

llvm/lib/Analysis/DomTreeUpdater.cpp

284 ↗

(On Diff #186620)

@NutshellySima it's probably me but I don't see how the comments match the code here. Let's take this example:

Strategy: Lazy
CFG: edge exists between A->B
Updates: {{Delete, A, B}, {Insert, A, B}}
U: {Delete, A, B}
Edge: {A,B}
isUpdateValid: true

In this case we will enqueue a deletion of edge A->B and not process the second update, the {Insert, A, B} because that Edge already exists in Seen. If a flush() is called immediately after the state of DTU is incorrect.

Am I missing something here that prevents this case?

llvm/unittests/Analysis/DomTreeUpdaterTest.cpp

793 ↗

(On Diff #186620)

Nit: please add a newline.

[NutshellySima]

1. I found I had assumed some extra limitations: Users need to apply updates in the same order they made to CFG (at least for the same pair of <From, To>). Because the only functionality the Update array applied by users is inferring the existence of a specific edge in the initial CFG.

2. This patch solves a current drawback of the DTU interface that when it sees both Insert and Delete of a pair of <From, To> in a single call to applyUpdates(), it will always choose one no matter whether they actually result in a no-op in this round. So, when DTU does no-ops finding (whose functionality is now equivalent to legalizeUpdates in DT), its result is not reliable. Though I don't see people submit both Insert and Delete updates of a single edge in a single call to applyUpdates(), it makes the semantic of CFG changes different in Eager and Lazy mode, so I think it's essential to get rid of this.

llvm/lib/Analysis/DomTreeUpdater.cpp

284 ↗

(On Diff #186620)

In the case you mentioned, isUpdateValid: true should be isUpdateValid: false.

isUpdateValid is a utility that inspects the current CFG and returns true when

1. U = {Delete, A, B} and there isn't any A -> B edge now.
2. U = {Insert, A, B} and there is at least an A -> B edge now.

So, when we see the first update {Delete, A, B}, first, we can infer that the initial CFG which DTU is in sync with has the edge <A, B>; Second, by inspecting the current CFG via isUpdateValid which returns false in this case, we can know that there is still <A, B> now.

So, we can now reach a conclusion that

1. If there are further actions different from Delete on this edge, they all result in a no-op. Because when you submit the second update {Insert, A, B}, the precondition is that in the CFG produced by (the initial CFG + the first update {Delete, A, B}) [no matter whether the first one is a fake update], edge <A, B> doesn't exist. (Because you cannot Insert an existent edge.) In the case you mentioned, we can infer that the first update actually happened and the second update actually happened too.
2. Otherwise (i.e., the whole Update array is made up of {Delete, A, B}s), they are all updates that never happened.

[brzycki]

llvm/lib/Analysis/DomTreeUpdater.cpp

284 ↗

(On Diff #186620)

Ah, got it! I was incorrectly reading isUpdateValid() while looking at the code yesterday.

I'm cautiously optimistic this will work. The real test will be the forthcoming patch to change all the *relaxed() calls and see if we have asserts or breaks.

[brzycki]

llvm/lib/Analysis/DomTreeUpdater.cpp

284 ↗

(On Diff #186620)

@NutshellySima it might be a good idea to add this reasoning to the comments of applyUpdates(). The interplay is subtle here and really needs to be documented.

[NutshellySima]

1. Add explanations and examples on why the invalid updates removing code works.
2. Add the precondition that the order of an edge in Updates needs to be ordered as CFG changes were made.
3. Separate applyUpdates into applyUpdatesAccurate and applyUpdatesHinted to decouple different semantics of applyUpdates from Eager/Lazy mode and enable DTU(Lazy) to accept unordered accurate updates.

Summary is also updated to explain why and how logic and interface of applyUpdates changes.

[NutshellySima]

I have also checked all code involving DTU.applyUpdates and is confident that the Updates array provided conforms to "Users need to apply updates in the same order they made to CFG for the same pair of <From, To>".

I would like to test this patch thoroughly before landing, but I don't know if there is other testing utilities besides ninja check-*.

[brzycki]

@NutshellySima I like the idea of the new naming scheme that makes usage more explicit.

I noticed there are no changes to JumpThreading.cpp, do they need to be altered in a separate patch or are you fine with all of applyUpdates implicitly becoming applyUpdatesHinted in Lazy mode?

I also find the name applyUpdatesHinted a bit confusing and had to read your comments above to understand Hinted meant "we check the CFG for validity". Maybe use applyUpdatesChecked or applyUpdatesValidated as an alternative name that makes it a bit more clear that extra work must be done for this set of updates.

[NutshellySima]

In D58170#1404240, @brzycki wrote:

@NutshellySima I like the idea of the new naming scheme that makes usage more explicit.

I noticed there are no changes to JumpThreading.cpp, do they need to be altered in a separate patch or are you fine with all of applyUpdates implicitly becoming applyUpdatesHinted in Lazy mode?

I also find the name applyUpdatesHinted a bit confusing and had to read your comments above to understand Hinted meant "we check the CFG for validity". Maybe use applyUpdatesChecked or applyUpdatesValidated as an alternative name that makes it a bit more clear that extra work must be done for this set of updates.

From my perspective, it is nice to decouple two different updates submitting methods (accurate/inaccurate) from the way to flush these changes (Eager/Lazy).
But concerning most Lazy strategy users use applyUpdatesChecked and most Eager strategy users use applyUpdatesAccurate, I think it is OK to use applyUpdates as an alias of applyUpdatesChecked under Lazy strategy. :)

I'll rename applyUpdatesHinted as applyUpdatesChecked later.

[kuhar]

I think the default for applyUpdates should be the strict mode; any code that relies on imprecise information about updates should make it clear by using some longer name, like applyUpdatesRelaxed.

[NutshellySima]

In D58170#1404415, @kuhar wrote:

I think the default for applyUpdates should be the strict mode; any code that relies on imprecise information about updates should make it clear by using some longer name, like applyUpdatesRelaxed.

I'm fine with making applyUpdates default to strict mode to make it consistent to other parts of the codebase and encourage people to use the strict one which does not have extra overhead on scanning the CFG.

But if the user follows the rules on using applyUpdatesRelaxed/Checked, DTU is also guaranteed to have precise information on updates.

[kuhar]

In D58170#1404458, @NutshellySima wrote:

In D58170#1404415, @kuhar wrote:

I think the default for applyUpdates should be the strict mode; any code that relies on imprecise information about updates should make it clear by using some longer name, like applyUpdatesRelaxed.

I'm fine with making applyUpdates default to strict mode to make it consistent to other parts of the codebase and encourage people to use the strict one which does not have extra overhead on scanning the CFG.

But if the user follows the rules on using applyUpdatesRelaxed/Checked, DTU is also guaranteed to have precise information on updates.

Agreed. Since this turned into yak shaving, how about appplyUpdatesPermissive? To me applyUpdatesRelaxed sounds similar to relaxed memory models, where you can have more interleaving, and applyUpdatesChecked implies that it does more checks, but is not necessarily functionally different.

[NutshellySima]

1. Rename applyUpdatesHinted to applyUpdatesPermissive; Remove applyUpdatesAccurate.
2. Default to strict mode.

[brzycki]

LGTM.

[NutshellySima]

Rebase.

llvm/trunk/include/llvm/Analysis/DomTreeUpdater.h

public:
   /// add up to a large number of updates between two queries on the
   /// DominatorTree. The incremental updater can reschedule the updates or
   /// decide to recalculate the dominator tree in order to speedup the updating
   /// process depending on the number of updates.
   ///
   /// Although GenericDomTree provides several update primitives,
   /// it is not encouraged to use these APIs directly.
 
-  /// Submit updates to all available trees. Under Eager UpdateStrategy with
-  /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
+  /// Submit updates to all available trees.
+  /// The Eager Strategy flushes updates immediately while the Lazy Strategy
+  /// queues the updates.
+  ///
+  /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
+  /// in sync with + all updates before that single update.
+  ///
+  /// CAUTION!
+  /// 1. It is required for the state of the LLVM IR to be updated
+  /// *before* submitting the updates because the internal update routine will
+  /// analyze the current state of the CFG to determine whether an update
+  /// is valid.
+  /// 2. It is illegal to submit any update that has already been submitted,
+  /// i.e., you are supposed not to insert an existent edge or delete a
+  /// nonexistent edge.
+  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
+
+  /// Submit updates to all available trees. It will also
   /// 1. discard duplicated updates,
   /// 2. remove invalid updates. (Invalid updates means deletion of an edge that
   /// still exists or insertion of an edge that does not exist.)
   /// The Eager Strategy flushes updates immediately while the Lazy Strategy
   /// queues the updates.
   ///
   /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
   /// in sync with + all updates before that single update.
   ///
   /// CAUTION!
   /// 1. It is required for the state of the LLVM IR to be updated
   /// *before* submitting the updates because the internal update routine will
   /// analyze the current state of the CFG to determine whether an update
   /// is valid.
   /// 2. It is illegal to submit any update that has already been submitted,
   /// i.e., you are supposed not to insert an existent edge or delete a
   /// nonexistent edge.
-  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
-                    bool ForceRemoveDuplicates = false);
+  /// 3. It is only legal to submit updates to an edge in the order CFG changes
+  /// are made. The order you submit updates on different edges is not
+  /// restricted.
+  void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates);
 
   /// Notify DTU that the entry block was replaced.
   /// Recalculate all available trees and flush all BasicBlocks
   /// awaiting deletion immediately.
   void recalculate(Function &F);
 
   /// \deprecated { Submit an edge insertion to all available trees. The Eager
   /// Strategy flushes this update immediately while the Lazy Strategy queues
public:
   /// Invalid update means inserting an edge that does not exist in the CFG.
   /// The Eager Strategy flushes this update immediately while the Lazy Strategy
   /// queues the update. It is only recommended to use this method when you
   /// want to discard an invalid update.
   /// CAUTION! It is illegal to submit any update that has already been
   /// submitted. }
   LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From,
                                                    BasicBlock *To),
-                            "Use applyUpdates() instead.");
+                            "Use applyUpdatesPermissive() instead.");
 
   /// \deprecated { Submit an edge deletion to all available trees. The Eager
   /// Strategy flushes this update immediately while the Lazy Strategy queues
   /// the update. An internal function checks if the edge doesn't exist in the
   /// CFG in DEBUG mode.
   /// CAUTION! This function has to be called *after* making the update on the
   /// actual CFG. It is illegal to submit any update that has already been
   /// submitted. }
   LLVM_ATTRIBUTE_DEPRECATED(void deleteEdge(BasicBlock *From, BasicBlock *To),
                             "Use applyUpdates() instead.");
 
   /// \deprecated { Submit an edge deletion to all available trees.
   /// Under either Strategy, an invalid update will be discard silently.
   /// Invalid update means deleting an edge that exists in the CFG.
   /// The Eager Strategy flushes this update immediately while the Lazy Strategy
   /// queues the update. It is only recommended to use this method when you
   /// want to discard an invalid update.
   /// CAUTION! It is illegal to submit any update that has already been
   /// submitted. }
   LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From,
                                                    BasicBlock *To),
-                            "Use applyUpdates() instead.");
+                            "Use applyUpdatesPermissive() instead.");
 
   /// Delete DelBB. DelBB will be removed from its Parent and
   /// erased from available trees if it exists and finally get deleted.
   /// Under Eager UpdateStrategy, DelBB will be processed immediately.
   /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
   /// all available trees are up-to-date. Assert if any instruction of DelBB is
   /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
   /// will be queued until flush() is called.
private:
   /// has to be inside of its parent Function while awaiting deletion under Lazy
   /// UpdateStrategy to prevent other routines from asserting the state of the
   /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
   void validateDeleteBB(BasicBlock *DelBB);
 
   /// Returns true if at least one BasicBlock is deleted.
   bool forceFlushDeletedBB();
 
-  /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
-  /// UpdateStrategy. Returns true if the update is queued for update.
-  bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
-                       BasicBlock *To);
-
   /// Helper function to apply all pending DomTree updates.
   void applyDomTreeUpdates();
 
   /// Helper function to apply all pending PostDomTree updates.
   void applyPostDomTreeUpdates();
 
   /// Helper function to flush deleted BasicBlocks if all available
   /// trees are up-to-date.

llvm/trunk/lib/Analysis/DomTreeUpdater.cpp

 //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the DomTreeUpdater class, which provides a uniform way
 // to update dominator tree related data structures.
 //
 //===----------------------------------------------------------------------===//
 
 #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 {
 
 bool DomTreeUpdater::isUpdateValid(
     const DominatorTree::UpdateType Update) const {
   const auto *From = Update.getFrom();
   const auto *To = Update.getTo();
   const auto Kind = Update.getKind();

 }
 
 bool DomTreeUpdater::isSelfDominance(
     const DominatorTree::UpdateType Update) const {
   // Won't affect DomTree and PostDomTree.
   return Update.getFrom() == Update.getTo();
 }
 
-bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
-                                     BasicBlock *From, BasicBlock *To) {
-  assert((DT || PDT) &&
-         "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
-  assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
-         "Call applyLazyUpdate() with Eager strategy error");
-  // Analyze pending updates to determine if the update is unnecessary.
-  const DominatorTree::UpdateType Update = {Kind, From, To};
-  const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
-                                                ? DominatorTree::Insert
-                                                : DominatorTree::Delete,
-                                            From, To};
-  // Only check duplicates in updates that are not applied by both trees.
-  auto I =
-      PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
-  const auto E = PendUpdates.end();
-
-  assert(I <= E && "Iterator out of range.");
-
-  for (; I != E; ++I) {
-    if (Update == *I)
-      return false; // Discard duplicate updates.
-
-    if (Invert == *I) {
-      // Update and Invert are both valid (equivalent to a no-op). Remove
-      // Invert from PendUpdates and discard the Update.
-      PendUpdates.erase(I);
-      return false;
-    }
-  }
-
-  PendUpdates.push_back(Update); // Save the valid update.
-  return true;
-}
-
 void DomTreeUpdater::applyDomTreeUpdates() {
   // No pending DomTreeUpdates.
   if (Strategy != UpdateStrategy::Lazy || !DT)
     return;
 
   // Only apply updates not are applied by DomTree.
   if (hasPendingDomTreeUpdates()) {
     const auto I = PendUpdates.begin() + PendDTUpdateIndex;
if (!I.use_empty())
       I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
     DelBB->getInstList().pop_back();
   }
   // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
   // Child of Function F it must contain valid IR.
   new UnreachableInst(DelBB->getContext(), DelBB);
 }
 
-void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
-                                  bool ForceRemoveDuplicates) {
+void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
   if (!DT && !PDT)
     return;
 
-  if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
-    SmallVector<DominatorTree::UpdateType, 8> Seen;
+  if (Strategy == UpdateStrategy::Lazy) {
     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());
-      }
-    if (Strategy == UpdateStrategy::Lazy)
-      return;
+      if (!isSelfDominance(U))
+        PendUpdates.push_back(U);
+
+  }
 
-    if (DT)
-      DT->applyUpdates(Seen);
-    if (PDT)
-      PDT->applyUpdates(Seen);
+    DT->applyUpdates(Updates);
+    PDT->applyUpdates(Updates);
+}
+
+void DomTreeUpdater::applyUpdatesPermissive(
+    ArrayRef<DominatorTree::UpdateType> Updates) {
+  if (!DT && !PDT)
     return;
+
+  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
+    // and updates to an edge need to be strictly ordered,
+    // 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.
+    //
+    // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
+    // because
+    // 1. it is illegal to submit updates that have already been applied,
+    // i.e., user cannot delete an nonexistent edge,
+    // 2. updates to an edge need to be strictly ordered,
+    // So, initially edge A -> B existed.
+    // We can then safely ignore future updates to this edge and directly
+    // inspect the current CFG:
+    // a. If the edge still exists, because the user cannot insert an existent
+    // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
+    // resulted in a no-op. DTU won't submit any update in this case.
+    // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
+    // actually happened but {Insert, A, B} was an invalid update which never
+    // happened. DTU will submit {Delete, A, B} in this case.
+    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())
+          PendUpdates.push_back(U);
+        else
+          DeduplicatedUpdates.push_back(U);
+      }
+    }
   }
 
+  if (Strategy == UpdateStrategy::Lazy)
+    return;
+
   if (DT)
-    DT->applyUpdates(Updates);
+    DT->applyUpdates(DeduplicatedUpdates);
   if (PDT)
-    PDT->applyUpdates(Updates);
+    PDT->applyUpdates(DeduplicatedUpdates);
 }
 
 DominatorTree &DomTreeUpdater::getDomTree() {
   assert(DT && "Invalid acquisition of a null DomTree");
   applyDomTreeUpdates();
   dropOutOfDateUpdates();
   return *DT;
 }
#endif
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->insertEdge(From, To);
     if (PDT)
       PDT->insertEdge(From, To);
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Insert, From, To);
+  PendUpdates.push_back({DominatorTree::Insert, From, To});
 }
 
 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
   if (!isUpdateValid({DominatorTree::Insert, From, To}))
     return;
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->insertEdge(From, To);
     if (PDT)
       PDT->insertEdge(From, To);
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Insert, From, To);
+  PendUpdates.push_back({DominatorTree::Insert, From, To});
 }
 
 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
 
 #ifndef NDEBUG
   assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
          "Deleted edge still exists in the CFG!");
 #endif
 
   if (!DT && !PDT)
     return;
 
   // Won't affect DomTree and PostDomTree; discard update.
   if (From == To)
     return;
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->deleteEdge(From, To);
     if (PDT)
       PDT->deleteEdge(From, To);
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Delete, From, To);
+  PendUpdates.push_back({DominatorTree::Delete, From, To});
 }
 
 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
   if (From == To)
     return;
 
   if (!DT && !PDT)
     return;
 
   if (!isUpdateValid({DominatorTree::Delete, From, To}))
     return;
 
   if (Strategy == UpdateStrategy::Eager) {
     if (DT)
       DT->deleteEdge(From, To);
     if (PDT)
       PDT->deleteEdge(From, To);
     return;
   }
 
-  applyLazyUpdate(DominatorTree::Delete, From, To);
+  PendUpdates.push_back({DominatorTree::Delete, From, To});
 }
 
 void DomTreeUpdater::dropOutOfDateUpdates() {
   if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
     return;
 
   tryFlushDeletedBB();
 

llvm/trunk/lib/Transforms/Scalar/CallSiteSplitting.cpp

if (IsMustTailCall) {
     // Remove superfluous `br` terminators from the end of the Split blocks
     // NOTE: Removing terminator removes the SplitBlock from the TailBB's
     // predecessors. Therefore we must get complete list of Splits before
     // attempting removal.
     SmallVector<BasicBlock *, 2> Splits(predecessors((TailBB)));
     assert(Splits.size() == 2 && "Expected exactly 2 splits!");
     for (unsigned i = 0; i < Splits.size(); i++) {
       Splits[i]->getTerminator()->eraseFromParent();
-      DTU.applyUpdates({{DominatorTree::Delete, Splits[i], TailBB}});
+      DTU.applyUpdatesPermissive({{DominatorTree::Delete, Splits[i], TailBB}});
     }
 
     // Erase the tail block once done with musttail patching
     DTU.deleteBB(TailBB);
     return;
   }
 
   auto *OriginalBegin = &*TailBB->begin();

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (State == LazyValueInfo::False) {
 
       // The condition can be modified by removePredecessor's PHI simplification
       // logic.
       Cond = SI->getCondition();
 
       ++NumDeadCases;
       Changed = true;
       if (--SuccessorsCount[Succ] == 0)
-        DTU.applyUpdates({{DominatorTree::Delete, BB, Succ}});
+        DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}});
       continue;
     }
     if (State == LazyValueInfo::True) {
       // This case always fires.  Arrange for the switch to be turned into an
       // unconditional branch by replacing the switch condition with the case
       // value.
       SI->setCondition(Case);
       NumDeadCases += SI->getNumCases();

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
       Succ->removePredecessor(BB, true);
       Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
 
     LLVM_DEBUG(dbgs() << "  In block '" << BB->getName()
                       << "' folding undef terminator: " << *BBTerm << '\n');
     BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
     BBTerm->eraseFromParent();
-    DTU->applyUpdates(Updates);
+    DTU->applyUpdatesPermissive(Updates);
     return true;
   }
 
   // If the terminator of this block is branching on a constant, simplify the
   // terminator to an unconditional branch.  This can occur due to threading in
   // other blocks.
   if (getKnownConstant(Condition, Preference)) {
     LLVM_DEBUG(dbgs() << "  In block '" << BB->getName()
if (CondBr && CondConst) {
         // including the guards/assumes themselves and the uses before the
         // guard/assume.
         else if (CondCmp->getParent() == BB) {
           auto *CI = Ret == LazyValueInfo::True ?
             ConstantInt::getTrue(CondCmp->getType()) :
             ConstantInt::getFalse(CondCmp->getType());
           ReplaceFoldableUses(CondCmp, CI);
         }
-        DTU->applyUpdates({{DominatorTree::Delete, BB, ToRemoveSucc}});
+        DTU->applyUpdatesPermissive(
+            {{DominatorTree::Delete, BB, ToRemoveSucc}});
         return true;
       }
 
       // We did not manage to simplify this branch, try to see whether
       // CondCmp depends on a known phi-select pattern.
       if (TryToUnfoldSelect(CondCmp, BB))
         return true;
     }
while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
     if (Implication) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
       RemoveSucc->removePredecessor(BB);
       BranchInst::Create(KeepSucc, BI);
       BI->eraseFromParent();
-      DTU->applyUpdates({{DominatorTree::Delete, BB, RemoveSucc}});
+      DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
 }
if (PredWithKnownDest == (size_t)pred_size(BB)) {
           Updates.push_back({DominatorTree::Delete, BB, SuccBB});
         }
       }
 
       // Finally update the terminator.
       Instruction *Term = BB->getTerminator();
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
-      DTU->applyUpdates(Updates);
+      DTU->applyUpdatesPermissive(Updates);
 
       // If the condition is now dead due to the removal of the old terminator,
       // erase it.
       if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
         if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
           CondInst->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   Instruction *PredTerm = PredBB->getTerminator();
   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
     if (PredTerm->getSuccessor(i) == BB) {
       BB->removePredecessor(PredBB, true);
       PredTerm->setSuccessor(i, NewBB);
     }
 
   // Enqueue required DT updates.
-  DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
+  DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, SuccBB},
                                {DominatorTree::Insert, PredBB, NewBB},
                                {DominatorTree::Delete, PredBB, BB}});
 
   // If there were values defined in BB that are used outside the block, then we
   // now have to update all uses of the value to use either the original value,
   // the cloned value, or some PHI derived value.  This can require arbitrary
   // PHI insertion, of which we are prepared to do, clean these up now.
   SSAUpdater SSAUpdate;
   SmallVector<Use*, 16> UsesToRename;
 
for (auto Pred : predecessors(NewBB)) {
       Updates.push_back({DominatorTree::Insert, Pred, NewBB});
       if (HasProfileData) // Update frequencies between Pred -> NewBB.
         NewBBFreq += FreqMap.lookup(Pred);
     }
     if (HasProfileData) // Apply the summed frequency to NewBB.
       BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
   }
 
-  DTU->applyUpdates(Updates);
+  DTU->applyUpdatesPermissive(Updates);
   return NewBBs[0];
 }
 
 bool JumpThreadingPass::doesBlockHaveProfileData(BasicBlock *BB) {
   const Instruction *TI = BB->getTerminator();
   assert(TI->getNumSuccessors() > 1 && "not a split");
 
   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
   }
 
   // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
   // that we nuked.
   BB->removePredecessor(PredBB, true);
 
   // Remove the unconditional branch at the end of the PredBB block.
   OldPredBranch->eraseFromParent();
-  DTU->applyUpdates(Updates);
+  DTU->applyUpdatesPermissive(Updates);
 
   ++NumDupes;
   return true;
 }
 
 // Pred is a predecessor of BB with an unconditional branch to BB. SI is
 // a Select instruction in Pred. BB has other predecessors and SI is used in
 // a PHI node in BB. SI has no other use.
void JumpThreadingPass::UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB,
   NewBB->getInstList().insert(NewBB->end(), PredTerm);
   // Create a conditional branch and update PHI nodes.
   BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
   SIUse->setIncomingValue(Idx, SI->getFalseValue());
   SIUse->addIncoming(SI->getTrueValue(), NewBB);
 
   // The select is now dead.
   SI->eraseFromParent();
-  DTU->applyUpdates({{DominatorTree::Insert, NewBB, BB},
+  DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB},
                                {DominatorTree::Insert, Pred, NewBB}});
 
   // Update any other PHI nodes in BB.
   for (BasicBlock::iterator BI = BB->begin();
        PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
     if (Phi != SIUse)
       Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
 }
 
for (BasicBlock::iterator BI = BB->begin();
     Updates.push_back({DominatorTree::Insert, BB, SplitBB});
     Updates.push_back({DominatorTree::Insert, BB, NewBB});
     Updates.push_back({DominatorTree::Insert, NewBB, SplitBB});
     // BB's successors were moved to SplitBB, update DTU accordingly.
     for (auto *Succ : successors(SplitBB)) {
       Updates.push_back({DominatorTree::Delete, BB, Succ});
       Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
     }
-    DTU->applyUpdates(Updates);
+    DTU->applyUpdatesPermissive(Updates);
     return true;
   }
   return false;
 }
 
 /// Try to propagate a guard from the current BB into one of its predecessors
 /// in case if another branch of execution implies that the condition of this
 /// guard is always true. Currently we only process the simplest case that

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

for (auto *BB : Dead)
     for (BasicBlock *Pred : predecessors(BB))
       assert(Dead.count(Pred) && "All predecessors must be dead!");
 #endif
 
   SmallVector<DominatorTree::UpdateType, 4> Updates;
   DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
 
   if (DTU)
-    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive(Updates);
 
   for (BasicBlock *BB : BBs)
     if (DTU)
       DTU->deleteBB(BB);
     else
       BB->eraseFromParent();
 }
 
if (MemDep)
     MemDep->invalidateCachedPredecessors();
 
   // Finally, erase the old block and update dominator info.
   if (DTU) {
     assert(BB->getInstList().size() == 1 &&
            isa<UnreachableInst>(BB->getTerminator()) &&
            "The successor list of BB isn't empty before "
            "applying corresponding DTU updates.");
-    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive(Updates);
     DTU->deleteBB(BB);
   }
 
   else {
     BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
   }
   return true;
 }

llvm/trunk/lib/Transforms/Utils/Local.cpp

if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
       // Let the basic block know that we are letting go of it.  Based on this,
       // it will adjust it's PHI nodes.
       OldDest->removePredecessor(BB);
 
       // Replace the conditional branch with an unconditional one.
       Builder.CreateBr(Destination);
       BI->eraseFromParent();
       if (DTU)
-        DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}},
-                          /*ForceRemoveDuplicates*/ true);
+        DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, OldDest}});
       return true;
     }
 
     if (Dest2 == Dest1) {       // Conditional branch to same location?
       // This branch matches something like this:
       //     br bool %cond, label %Dest, label %Dest
       // and changes it into:  br label %Dest
 
for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
                           createBranchWeights(Weights));
         }
         // Remove this entry.
         BasicBlock *ParentBB = SI->getParent();
         DefaultDest->removePredecessor(ParentBB);
         i = SI->removeCase(i);
         e = SI->case_end();
         if (DTU)
-          DTU->applyUpdates({{DominatorTree::Delete, ParentBB, DefaultDest}},
-                            /*ForceRemoveDuplicates*/ true);
+          DTU->applyUpdatesPermissive(
+              {{DominatorTree::Delete, ParentBB, DefaultDest}});
         continue;
       }
 
       // Otherwise, check to see if the switch only branches to one destination.
       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
       // destinations.
       if (i->getCaseSuccessor() != TheOnlyDest)
         TheOnlyDest = nullptr;
if (TheOnlyDest) {
       }
 
       // Delete the old switch.
       Value *Cond = SI->getCondition();
       SI->eraseFromParent();
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
       if (DTU)
-        DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+        DTU->applyUpdatesPermissive(Updates);
       return true;
     }
 
     if (SI->getNumCases() == 1) {
       // Otherwise, we can fold this switch into a conditional branch
       // instruction if it has only one non-default destination.
       auto FirstCase = *SI->case_begin();
       Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
if (auto *BA =
       // have undefined behavior.  Replace the unconditional branch with an
       // 'unreachable' instruction.
       if (TheOnlyDest) {
         BB->getTerminator()->eraseFromParent();
         new UnreachableInst(BB->getContext(), BB);
       }
 
       if (DTU)
-        DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+        DTU->applyUpdatesPermissive(Updates);
       return true;
     }
   }
 
   return false;
 }
 
 //===----------------------------------------------------------------------===//
if (!recursivelySimplifyInstruction(PN))
       continue;
 
     // If recursive simplification ended up deleting the next PHI node we would
     // iterate to, then our iterator is invalid, restart scanning from the top
     // of the block.
     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
   }
   if (DTU)
-    DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}},
-                      /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive({{DominatorTree::Delete, Pred, BB}});
 }
 
 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 /// predecessor is known to have one successor (DestBB!). Eliminate the edge
 /// between them, moving the instructions in the predecessor into DestBB and
 /// deleting the predecessor block.
 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
                                        DomTreeUpdater *DTU) {
void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
   if (ReplaceEntryBB)
     DestBB->moveAfter(PredBB);
 
   if (DTU) {
     assert(PredBB->getInstList().size() == 1 &&
            isa<UnreachableInst>(PredBB->getTerminator()) &&
            "The successor list of PredBB isn't empty before "
            "applying corresponding DTU updates.");
-    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive(Updates);
     DTU->deleteBB(PredBB);
     // Recalculation of DomTree is needed when updating a forward DomTree and
     // the Entry BB is replaced.
     if (ReplaceEntryBB && DTU->hasDomTree()) {
       // The entry block was removed and there is no external interface for
       // the dominator tree to be notified of this change. In this corner-case
       // we recalculate the entire tree.
       DTU->recalculate(*(DestBB->getParent()));
bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
   // Clear the successor list of BB to match updates applying to DTU later.
   if (BB->getTerminator())
     BB->getInstList().pop_back();
   new UnreachableInst(BB->getContext(), BB);
   assert(succ_empty(BB) && "The successor list of BB isn't empty before "
                            "applying corresponding DTU updates.");
 
   if (DTU) {
-    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive(Updates);
     DTU->deleteBB(BB);
   } else {
     BB->eraseFromParent(); // Delete the old basic block.
   }
   return true;
 }
 
 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
   BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
   while (BBI != BBE) {
     if (!BBI->use_empty())
       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
     BB->getInstList().erase(BBI++);
     ++NumInstrsRemoved;
   }
   if (DTU)
-    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive(Updates);
   return NumInstrsRemoved;
 }
 
 /// changeToCall - Convert the specified invoke into a normal call.
 static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr) {
   SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
   SmallVector<OperandBundleDef, 1> OpBundles;
   II->getOperandBundlesAsDefs(OpBundles);
static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr) {
   BranchInst::Create(NormalDestBB, II);
 
   // Update PHI nodes in the unwind destination
   BasicBlock *BB = II->getParent();
   BasicBlock *UnwindDestBB = II->getUnwindDest();
   UnwindDestBB->removePredecessor(BB);
   II->eraseFromParent();
   if (DTU)
-    DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
-                      /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDestBB}});
 }
 
 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                                    BasicBlock *UnwindEdge) {
   BasicBlock *BB = CI->getParent();
 
   // Convert this function call into an invoke instruction.  First, split the
   // basic block.
if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
         if (II->use_empty() && II->onlyReadsMemory()) {
           // jump to the normal destination branch.
           BasicBlock *NormalDestBB = II->getNormalDest();
           BasicBlock *UnwindDestBB = II->getUnwindDest();
           BranchInst::Create(NormalDestBB, II);
           UnwindDestBB->removePredecessor(II->getParent());
           II->eraseFromParent();
           if (DTU)
-            DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
-                              /*ForceRemoveDuplicates*/ true);
+            DTU->applyUpdatesPermissive(
+                {{DominatorTree::Delete, BB, UnwindDestBB}});
         } else
           changeToCall(II, DTU);
         Changed = true;
       }
     } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
       // Remove catchpads which cannot be reached.
       struct CatchPadDenseMapInfo {
         static CatchPadInst *getEmptyKey() {
void llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) {
   }
 
   NewTI->takeName(TI);
   NewTI->setDebugLoc(TI->getDebugLoc());
   UnwindDest->removePredecessor(BB);
   TI->replaceAllUsesWith(NewTI);
   TI->eraseFromParent();
   if (DTU)
-    DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}},
-                      /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDest}});
 }
 
 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
                                    DomTreeUpdater *DTU,
if (DTU) {
                                "applying corresponding DTU updates.");
       ++I;
     } else {
       I = F.getBasicBlockList().erase(I);
     }
   }
 
   if (DTU) {
-    DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+    DTU->applyUpdatesPermissive(Updates);
     bool Deleted = false;
     for (auto *BB : DeadBlockSet) {
       if (DTU->isBBPendingDeletion(BB))
         --NumRemoved;
       else
         Deleted = true;
       DTU->deleteBB(BB);
     }

llvm/trunk/unittests/Analysis/DomTreeUpdaterTest.cpp

TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 
-  DTU.applyUpdates(
-      {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}},
-      /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdatesPermissive(
+      {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}});
+  ASSERT_FALSE(DTU.hasPendingUpdates());
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 
for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
     }
   }
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
   // contained Instructions and change the Terminator to "unreachable" when
   // queued for deletion.
   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
-  DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_FALSE(DTU.hasPendingUpdates());
 
   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
-  DTU.applyUpdates(
-      {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}},
-      /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdatesPermissive(
+      {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}});
 
   // DTU working with Eager UpdateStrategy does not need to flush.
   ASSERT_TRUE(DT.verify());
   ASSERT_TRUE(PDT.verify());
 
   // Test callback utils.
   ASSERT_EQ(BB3->getParent(), F);
   DTU.callbackDeleteBB(BB3,
TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
 
   // Add a block as the new function entry BB. We also link it to BB0.
   BasicBlock *NewEntry =
       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
   BranchInst::Create(BB0, NewEntry);
   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 
-  DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}},
-                   /*ForceRemoveDuplicates*/ true);
+  DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});
 
   // Changing the Entry BB requires a full recalculation of DomTree.
   DTU.recalculate(*F);
   ASSERT_TRUE(DT.verify());
   ASSERT_TRUE(PDT.verify());
 
   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
 
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
 
   // Test discards of self-domination update.
-  DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});
+  DTU.applyUpdatesPermissive({{DominatorTree::Insert, BB0, BB0}});
   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 
   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
   // entries are discarded.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 
   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
   Updates.push_back({DominatorTree::Insert, BB1, BB2});
   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
   Updates.push_back({DominatorTree::Delete, BB0, BB1});
 
   // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
   BB0->getTerminator()->eraseFromParent();
   BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 
   // Verify. Updates to DTU must be applied *after* all changes to the CFG
   // (including block deletion).
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_TRUE(DTU.getDomTree().verify());
 
   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
   // contained Instructions and change the Terminator to "unreachable" when
   // queued for deletion. Its parent is still F until all the pending updates
   // are applied to all trees held by the DomTreeUpdater (DomTree/PostDomTree).
   // We don't defer this action because it can cause problems for other
   // transforms or analysis as it's part of the actual CFG. We only defer
TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
   //   ||        |
   //   |+> curr <+    converted into:   pred1..predN curr
   //   |    |                            |        |
   //   |    v                            +> succ <+
   //   +-> succ
   //
   // While the final CFG form is functionally identical the updates to
   // DTU are not. In the first case we must have
-  // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in the
-  // latter case we must *NOT* have DTU.applyUpdates({{DominatorTree::Insert,
-  // Pred1, Succ}}).
+  // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in
+  // the latter case we must *NOT* have
+  // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}).
 
   // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
   // remove bb2.
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
   BB0->getTerminator()->eraseFromParent();
   BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 
   // Test callback utils.
   std::vector<BasicBlock *> BasicBlocks;
   BasicBlocks.push_back(BB1);
   BasicBlocks.push_back(BB2);
   auto Eraser = [&](BasicBlock *BB) {
     BasicBlocks.erase(
         std::remove_if(BasicBlocks.begin(), BasicBlocks.end(),
                        [&](const BasicBlock *i) { return i == BB; }),
         BasicBlocks.end());
   };
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
-  // Remove bb2 from F. This has to happen before the call to applyUpdates() for
-  // DTU to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
-  // method converts bb2's TI into "unreachable".
+  // Remove bb2 from F. This has to happen before the call to
+  // applyUpdates() for DTU to detect there is no longer an edge between
+  // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable".
   ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
   DTU.callbackDeleteBB(BB2, Eraser);
   EXPECT_TRUE(DTU.isBBPendingDeletion(BB2));
   ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
   EXPECT_EQ(BB2->getParent(), F);
 
   // Queue up the DTU updates.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(4);
   Updates.push_back({DominatorTree::Delete, BB0, BB2});
   Updates.push_back({DominatorTree::Delete, BB2, BB3});
 
   // Handle the specific shape case next.
   // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
   BB0->getTerminator()->eraseFromParent();
   BranchInst::Create(BB3, BB0);
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 
-  // Remove bb1 from F. This has to happen before the call to applyUpdates() for
-  // DTU to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
-  // method converts bb1's TI into "unreachable".
+  // Remove bb1 from F. This has to happen before the call to
+  // applyUpdates() for DTU to detect there is no longer an edge between
+  // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable".
   ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
   DTU.callbackDeleteBB(BB1, Eraser);
   EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));
   ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
   EXPECT_EQ(BB1->getParent(), F);
 
   // Update the DTU. In this case we don't submit {DominatorTree::Insert, BB0,
   // BB3} because the edge previously existed at the start of this test when DT
   // was first created.
   Updates.push_back({DominatorTree::Delete, BB0, BB1});
   Updates.push_back({DominatorTree::Delete, BB1, BB3});
 
   // Verify everything.
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
   DTU.flush();
   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
   ASSERT_TRUE(DT.verify());
 }
 
 TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
   StringRef FuncName = "f";
TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
   DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; });
   EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
   ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
   EXPECT_EQ(BB3->getParent(), F);
 
   // Verify. Updates to DTU must be applied *after* all changes to the CFG
   // (including block deletion).
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   ASSERT_TRUE(DTU.getDomTree().verify());
   ASSERT_TRUE(DTU.hasPendingUpdates());
   ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
   ASSERT_TRUE(DTU.hasPendingDeletedBB());
   ASSERT_TRUE(DTU.getPostDomTree().verify());
   ASSERT_FALSE(DTU.hasPendingUpdates());
   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
TEST(DomTreeUpdater, LazyUpdateStepTest) {
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 
-  // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
-  // entries are discarded.
+  // Delete edge bb0 -> bb3.
   std::vector<DominatorTree::UpdateType> Updates;
   Updates.reserve(1);
   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 
   // CFG Change: remove edge bb0 -> bb3.
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u);
   BB3->removePredecessor(BB0);
   for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
if (i->getCaseSuccessor() == BB2) {
       BB2->removePredecessor(BB0);
       i = SI->removeCase(i);
       e = SI->case_end();
       Updates.push_back({DominatorTree::Delete, BB0, BB2});
     } else
       ++i;
   }
 
-  DTU.applyUpdates(Updates);
+  DTU.applyUpdatesPermissive(Updates);
   // flush PostDomTree
   ASSERT_TRUE(DTU.getPostDomTree().verify());
   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
   ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());
   // flush both trees
   DTU.flush();
   ASSERT_TRUE(DT.verify());
 }
TEST(DomTreeUpdater, NoTreeTest) {
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   // Test whether PendingDeletedBB is flushed after the recalculation.
   DTU.deleteBB(BB0);
   ASSERT_TRUE(DTU.hasPendingDeletedBB());
   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.applyUpdatesPermissive({{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.applyUpdatesPermissive({{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.applyUpdatesPermissive({{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());
+}