Revert "[Dominators] Add the DomTreeUpdater class"

Temporary revert because of a failing test on some buildbots.

This reverts commit r336114.

llvm-svn: 336117

6 files changed, 0 insertions, 1450 deletions

diff --git a/llvm/include/llvm/IR/DomTreeUpdater.h b/llvm/include/llvm/IR/DomTreeUpdater.h
deleted file mode 100644
index 24111dc2338..00000000000
--- a/llvm/include/llvm/IR/DomTreeUpdater.h
+++ /dev/null
@@ -1,242 +0,0 @@
-//===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines the DomTreeUpdater class, which provides a uniform way to
-// update dominator tree related data structures.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_DOMTREEUPDATER_H
-#define LLVM_DOMTREEUPDATER_H
-
-#include "llvm/Analysis/PostDominators.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/ValueHandle.h"
-#include "llvm/Support/GenericDomTree.h"
-#include <vector>
-
-namespace llvm {
-class DomTreeUpdater {
-public:
-  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
-
-  explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
-  DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
-      : DT(&DT_), Strategy(Strategy_) {}
-  DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
-      : PDT(&PDT_), Strategy(Strategy_) {}
-  DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
-                 UpdateStrategy Strategy_)
-      : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
-
-  ~DomTreeUpdater() { flush(); }
-
-  /// Returns the UpdateStrategy of the class instance.
-  UpdateStrategy getUpdateStrategy() const { return Strategy; };
-
-  /// Returns true if it holds a DominatorTree.
-  bool hasDomTree() const { return DT != nullptr; }
-
-  /// Returns true if it holds a PostDominatorTree.
-  bool hasPostDomTree() const { return PDT != nullptr; }
-
-  /// Returns true if there is BasicBlock awaiting deletion.
-  /// The deletion will only happen until a flush event and
-  /// all available trees are up-to-date.
-  /// Returns false under Eager UpdateStrategy.
-  bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); }
-
-  /// Returns true if DelBB is awaiting deletion.
-  /// Returns false under Eager UpdateStrategy.
-  bool isBBPendingDeletion(BasicBlock *DelBB) const;
-
-  /// Returns true if either of DT or PDT is valid and the tree has at
-  /// least one update pending. If DT or PDT is nullptr it is treated
-  /// as having no pending updates. This function does not check
-  /// whether there is BasicBlock awaiting deletion.
-  /// Returns false under Eager UpdateStrategy.
-  bool hasPendingUpdates() const;
-
-  /// Returns true if there are DominatorTree updates queued.
-  /// Returns false under Eager UpdateStrategy.
-  bool hasPendingDomTreeUpdates() const;
-
-  /// Returns true if there are PostDominatorTree updates queued.
-  /// Returns false under Eager UpdateStrategy.
-  bool hasPendingPostDomTreeUpdates() const;
-
-  /// Apply updates on all available trees. Under Eager UpdateStrategy with
-  /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
-  /// discard duplicated updates and self-dominance updates. The Eager
-  /// Strategy applies the updates immediately while the Lazy Strategy
-  /// queues the updates. It is required for the state of
-  /// the LLVM IR to be updated *before* applying the Updates because the
-  /// internal update routine will analyze the current state of the relationship
-  /// between a pair of (From, To) BasicBlocks to determine whether a single
-  /// update needs to be discarded.
-  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
-                    bool ForceRemoveDuplicates = false);
-
-  /// Notify all available trees on an edge insertion. Under either Strategy,
-  /// self-dominance update will be removed. The Eager Strategy applies
-  /// the update immediately while the Lazy Strategy queues the update.
-  /// It is recommended to only use this method when you have exactly one
-  /// insertion (and no deletions). It is recommended to use applyUpdates() in
-  /// all other cases. This function has to be called *after* making the update
-  /// on the actual CFG. An internal functions checks if the edge exists in the
-  /// CFG in DEBUG mode.
-  void insertEdge(BasicBlock *From, BasicBlock *To);
-
-  /// Notify all available trees on an edge insertion.
-  /// Under either Strategy, these updates will be discard silently in the
-  /// following sequence
-  /// 1. Invalid - Inserting an edge that does not exist in the CFG.
-  /// 2. Self-dominance update.
-  /// The Eager Strategy applies the update immediately while the Lazy Strategy
-  /// queues the update. It is recommended to only use this method when you have
-  /// exactly one insertion (and no deletions) and want to discard an invalid
-  /// update. Returns true if the update is valid.
-  bool insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
-
-  /// Notify all available trees on an edge deletion. Under either Strategy,
-  /// self-dominance update will be removed. The Eager Strategy applies
-  /// the update immediately while the Lazy Strategy queues the update.
-  /// It is recommended to only use this method when you have exactly one
-  /// deletion (and no insertions). It is recommended to use applyUpdates() in
-  /// all other cases. This function has to be called *after* making the update
-  /// on the actual CFG. An internal functions checks if the edge doesn't exist
-  /// in the CFG in DEBUG mode.
-  void deleteEdge(BasicBlock *From, BasicBlock *To);
-
-  /// Notify all available trees on an edge deletion.
-  /// Under either Strategy, these updates will be discard silently in the
-  /// following sequence:
-  /// 1. Invalid - Deleting an edge that still exists in the CFG.
-  /// 2. Self-dominance update.
-  /// The Eager Strategy applies the update immediately while the Lazy Strategy
-  /// queues the update. It is recommended to only use this method when you have
-  /// exactly one deletion (and no insertions) and want to discard an invalid
-  /// update. Returns true if the update is valid.
-  bool deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
-
-  /// 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.
-  void deleteBB(BasicBlock *DelBB);
-
-  /// Delete DelBB. DelBB will be removed from its Parent and
-  /// erased from available trees if it exists. Then the callback will
-  /// be called. Finally, DelBB will be 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.
-  /// Multiple callbacks can be queued for one DelBB under Lazy UpdateStrategy.
-  void callbackDeleteBB(BasicBlock *DelBB,
-                        function_ref<void(BasicBlock *)> Callback);
-
-  /// Recalculate all available trees.
-  /// Under Lazy Strategy, available trees will only be recalculated if there
-  /// are pending updates or there is BasicBlock awaiting deletion. Returns true
-  /// if at least one tree is recalculated.
-  bool recalculate(Function &F);
-
-  /// Flush DomTree updates and return DomTree.
-  /// It also flush out of date updates applied by all available trees
-  /// and flush Deleted BBs if both trees are up-to-date.
-  /// It must only be called when it has a DomTree.
-  DominatorTree &getDomTree();
-
-  /// Flush PostDomTree updates and return PostDomTree.
-  /// It also flush out of date updates applied by all available trees
-  /// and flush Deleted BBs if both trees are up-to-date.
-  /// It must only be called when it has a PostDomTree.
-  PostDominatorTree &getPostDomTree();
-
-  /// Apply all pending updates to available trees and flush all BasicBlocks
-  /// awaiting deletion.
-  /// Does nothing under Eager UpdateStrategy.
-  void flush();
-
-  /// Debug method to help view the internal state of this class.
-  LLVM_DUMP_METHOD void dump() const;
-
-private:
-  class CallBackOnDeletion final : public CallbackVH {
-  public:
-    CallBackOnDeletion(BasicBlock *V, function_ref<void(BasicBlock *)> Callback)
-        : CallbackVH(V), DelBB(V), Callback_(Callback) {}
-
-  private:
-    BasicBlock *DelBB = nullptr;
-    function_ref<void(BasicBlock *)> Callback_;
-
-    void deleted() override {
-      Callback_(DelBB);
-      CallbackVH::deleted();
-    }
-  };
-
-  SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
-  size_t PendDTUpdateIndex = 0;
-  size_t PendPDTUpdateIndex = 0;
-  DominatorTree *DT = nullptr;
-  PostDominatorTree *PDT = nullptr;
-  const UpdateStrategy Strategy;
-  SmallPtrSet<BasicBlock *, 8> DeletedBBs;
-  std::vector<CallBackOnDeletion> Callbacks;
-  bool IsRecalculatingDomTree = false;
-  bool IsRecalculatingPostDomTree = false;
-
-  /// First remove all the instructions of DelBB and then make sure DelBB has a
-  /// valid terminator instruction which is necessary to have when DelBB still
-  /// 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.
-  void tryFlushDeletedBB();
-
-  /// Drop all updates applied by all available trees and delete BasicBlocks if
-  /// all available trees are up-to-date.
-  void dropOutOfDateUpdates();
-
-  /// Erase Basic Block node that has been unlinked from Function
-  /// in the DomTree and PostDomTree.
-  void eraseDelBBNode(BasicBlock *DelBB);
-
-  /// Returns true if the update appears in the LLVM IR.
-  /// It is used to check whether an update is valid in
-  /// insertEdge/deleteEdge or is unnecessary in the batch update.
-  bool isUpdateValid(DominatorTree::UpdateType Update) const;
-
-  /// Returns true if the update is self dominance.
-  bool isSelfDominance(DominatorTree::UpdateType Update) const;
-};
-} // namespace llvm
-
-#endif // LLVM_DOMTREEUPDATER_H
diff --git a/llvm/include/llvm/module.modulemap b/llvm/include/llvm/module.modulemap
index 52c85f8b4e4..72d9ec52050 100644
--- a/llvm/include/llvm/module.modulemap
+++ b/llvm/include/llvm/module.modulemap
@@ -196,8 +196,6 @@ module LLVM_intrinsic_gen {
   module IR_CFG { header "IR/CFG.h" export * }
   module IR_ConstantRange { header "IR/ConstantRange.h" export * }
   module IR_Dominators { header "IR/Dominators.h" export * }
-  module Analysis_PostDominators { header "Analysis/PostDominators.h" export * }
-  module IR_DomTreeUpdater { header "IR/DomTreeUpdater.h" export * }
   module IR_IRBuilder { header "IR/IRBuilder.h" export * }
   module IR_PassManager { header "IR/PassManager.h" export * }
   module IR_PredIteratorCache { header "IR/PredIteratorCache.h" export * }
diff --git a/llvm/lib/IR/CMakeLists.txt b/llvm/lib/IR/CMakeLists.txt
index 0a78a0f8d81..6284e2175a6 100644
--- a/llvm/lib/IR/CMakeLists.txt
+++ b/llvm/lib/IR/CMakeLists.txt
@@ -21,7 +21,6 @@ add_llvm_library(LLVMCore
   DiagnosticInfo.cpp
   DiagnosticPrinter.cpp
   Dominators.cpp
-  DomTreeUpdater.cpp
   Function.cpp
   GVMaterializer.cpp
   Globals.cpp
diff --git a/llvm/lib/IR/DomTreeUpdater.cpp b/llvm/lib/IR/DomTreeUpdater.cpp
deleted file mode 100644
index 83126f524b1..00000000000
--- a/llvm/lib/IR/DomTreeUpdater.cpp
+++ /dev/null
@@ -1,511 +0,0 @@
-//===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements the DomTreeUpdater class, which provides a uniform way
-// to update dominator tree related data structures.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/IR/DomTreeUpdater.h"
-#include "llvm/Analysis/PostDominators.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/Support/GenericDomTree.h"
-#include <algorithm>
-
-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();
-
-  // Discard updates by inspecting the current state of successors of From.
-  // Since isUpdateValid() must be called *after* the Terminator of From is
-  // altered we can determine if the update is unnecessary for batch updates
-  // or invalid for a single update.
-  const bool HasEdge = llvm::any_of(
-      successors(From), [To](const BasicBlock *B) { return B == To; });
-
-  // If the IR does not match the update,
-  // 1. In batch updates, this update is unnecessary.
-  // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
-  // Edge does not exist in IR.
-  if (Kind == DominatorTree::Insert && !HasEdge)
-    return false;
-
-  // Edge exists in IR.
-  if (Kind == DominatorTree::Delete && HasEdge)
-    return false;
-
-  return true;
-}
-
-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(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;
-    const auto E = PendUpdates.end();
-    assert(I < E && "Iterator range invalid; there should be DomTree updates.");
-    DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
-    PendDTUpdateIndex = PendUpdates.size();
-  }
-}
-
-void DomTreeUpdater::flush() {
-  applyDomTreeUpdates();
-  applyPostDomTreeUpdates();
-  dropOutOfDateUpdates();
-}
-
-void DomTreeUpdater::applyPostDomTreeUpdates() {
-  // No pending PostDomTreeUpdates.
-  if (Strategy != UpdateStrategy::Lazy || !PDT)
-    return;
-
-  // Only apply updates not are applied by PostDomTree.
-  if (hasPendingPostDomTreeUpdates()) {
-    const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
-    const auto E = PendUpdates.end();
-    assert(I < E &&
-           "Iterator range invalid; there should be PostDomTree updates.");
-    PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
-    PendPDTUpdateIndex = PendUpdates.size();
-  }
-}
-
-void DomTreeUpdater::tryFlushDeletedBB() {
-  if (!hasPendingUpdates())
-    forceFlushDeletedBB();
-}
-
-bool DomTreeUpdater::forceFlushDeletedBB() {
-  if (DeletedBBs.empty())
-    return false;
-
-  for (auto *BB : DeletedBBs) {
-    BB->removeFromParent();
-    eraseDelBBNode(BB);
-    delete BB;
-  }
-  DeletedBBs.clear();
-  Callbacks.clear();
-  return true;
-}
-
-bool DomTreeUpdater::recalculate(Function &F) {
-  if (!DT && !PDT)
-    return false;
-
-  if (Strategy == UpdateStrategy::Eager) {
-    if (DT)
-      DT->recalculate(F);
-    if (PDT)
-      PDT->recalculate(F);
-    return true;
-  }
-
-  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
-  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
-
-  // Because all trees are going to be up-to-date after recalculation,
-  // flush awaiting deleted BasicBlocks.
-  if (forceFlushDeletedBB() || hasPendingUpdates()) {
-    if (DT)
-      DT->recalculate(F);
-    if (PDT)
-      PDT->recalculate(F);
-
-    // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
-    IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
-    PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
-    dropOutOfDateUpdates();
-    return true;
-  }
-
-  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
-  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
-  return false;
-}
-
-bool DomTreeUpdater::hasPendingUpdates() const {
-  return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
-}
-
-bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
-  if (!DT)
-    return false;
-  return PendUpdates.size() != PendDTUpdateIndex;
-}
-
-bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
-  if (!PDT)
-    return false;
-  return PendUpdates.size() != PendPDTUpdateIndex;
-}
-
-bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
-  if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
-    return false;
-  return DeletedBBs.count(DelBB) != 0;
-}
-
-// The DT and PDT require the nodes related to updates
-// are not deleted when update functions are called.
-// So BasicBlock deletions must be pended when the
-// UpdateStrategy is Lazy. When the UpdateStrategy is
-// Eager, the BasicBlock will be deleted immediately.
-void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
-  validateDeleteBB(DelBB);
-  if (Strategy == UpdateStrategy::Lazy) {
-    DeletedBBs.insert(DelBB);
-    return;
-  }
-
-  DelBB->removeFromParent();
-  eraseDelBBNode(DelBB);
-  delete DelBB;
-}
-
-void DomTreeUpdater::callbackDeleteBB(
-    BasicBlock *DelBB, function_ref<void(BasicBlock *)> Callback) {
-  validateDeleteBB(DelBB);
-  if (Strategy == UpdateStrategy::Lazy) {
-    Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
-    DeletedBBs.insert(DelBB);
-    return;
-  }
-
-  DelBB->removeFromParent();
-  eraseDelBBNode(DelBB);
-  Callback(DelBB);
-  delete DelBB;
-}
-
-void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
-  if (DT && !IsRecalculatingDomTree)
-    if (DT->getNode(DelBB))
-      DT->eraseNode(DelBB);
-
-  if (PDT && !IsRecalculatingPostDomTree)
-    if (PDT->getNode(DelBB))
-      PDT->eraseNode(DelBB);
-}
-
-void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
-  assert(DelBB && "Invalid push_back of nullptr DelBB.");
-  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
-  // DelBB is unreachable and all its instructions are dead.
-  while (!DelBB->empty()) {
-    Instruction &I = DelBB->back();
-    // Replace used instructions with an arbitrary value (undef).
-    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) {
-  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());
-      }
-    if (Strategy == UpdateStrategy::Lazy)
-      return;
-
-    if (DT)
-      DT->applyUpdates(Seen);
-    if (PDT)
-      PDT->applyUpdates(Seen);
-    return;
-  }
-
-  if (DT)
-    DT->applyUpdates(Updates);
-  if (PDT)
-    PDT->applyUpdates(Updates);
-}
-
-DominatorTree &DomTreeUpdater::getDomTree() {
-  assert(DT && "Invalid acquisition of a null DomTree");
-  applyDomTreeUpdates();
-  dropOutOfDateUpdates();
-  return *DT;
-}
-
-PostDominatorTree &DomTreeUpdater::getPostDomTree() {
-  assert(PDT && "Invalid acquisition of a null PostDomTree");
-  applyPostDomTreeUpdates();
-  dropOutOfDateUpdates();
-  return *PDT;
-}
-
-void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
-
-#ifndef NDEBUG
-  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
-         "Inserted edge does not appear in the CFG");
-#endif
-
-  // Won't affect DomTree and PostDomTree; discard update.
-  if (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);
-}
-
-bool DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
-  if (!isUpdateValid({DominatorTree::Insert, From, To}))
-    return false;
-
-  if (From == To)
-    return true;
-
-  if (Strategy == UpdateStrategy::Eager) {
-    if (DT)
-      DT->insertEdge(From, To);
-    if (PDT)
-      PDT->insertEdge(From, To);
-    return true;
-  }
-
-  applyLazyUpdate(DominatorTree::Insert, From, To);
-  return true;
-}
-
-void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
-
-#ifndef NDEBUG
-  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
-         "Deleted edge still exists in the CFG!");
-#endif
-
-  // 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);
-}
-
-bool DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
-  if (!isUpdateValid({DominatorTree::Delete, From, To}))
-    return false;
-
-  if (From == To)
-    return true;
-
-  if (Strategy == UpdateStrategy::Eager) {
-    if (DT)
-      DT->deleteEdge(From, To);
-    if (PDT)
-      PDT->deleteEdge(From, To);
-    return true;
-  }
-
-  applyLazyUpdate(DominatorTree::Delete, From, To);
-  return true;
-}
-
-void DomTreeUpdater::dropOutOfDateUpdates() {
-  if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
-    return;
-
-  tryFlushDeletedBB();
-
-  // Drop all updates applied by both trees.
-  if (!DT)
-    PendDTUpdateIndex = PendUpdates.size();
-  if (!PDT)
-    PendPDTUpdateIndex = PendUpdates.size();
-
-  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
-  const auto B = PendUpdates.begin();
-  const auto E = PendUpdates.begin() + dropIndex;
-  assert(B <= E && "Iterator out of range.");
-  PendUpdates.erase(B, E);
-  // Calculate current index.
-  PendDTUpdateIndex -= dropIndex;
-  PendPDTUpdateIndex -= dropIndex;
-}
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
-  raw_ostream &OS = llvm::dbgs();
-
-  OS << "Available Trees: ";
-  if (DT || PDT) {
-    if (DT)
-      OS << "DomTree ";
-    if (PDT)
-      OS << "PostDomTree ";
-    OS << "\n";
-  } else
-    OS << "None\n";
-
-  OS << "UpdateStrategy: ";
-  if (Strategy == UpdateStrategy::Eager) {
-    OS << "Eager\n";
-    return;
-  } else
-    OS << "Lazy\n";
-  int Index = 0;
-
-  auto printUpdates =
-      [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
-          ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
-        if (begin == end)
-          OS << "  None\n";
-        Index = 0;
-        for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
-          auto U = *It;
-          OS << "  " << Index << " : ";
-          ++Index;
-          if (U.getKind() == DominatorTree::Insert)
-            OS << "Insert, ";
-          else
-            OS << "Delete, ";
-          BasicBlock *From = U.getFrom();
-          if (From) {
-            auto S = From->getName();
-            if (!From->hasName())
-              S = "(no name)";
-            OS << S << "(" << From << "), ";
-          } else {
-            OS << "(badref), ";
-          }
-          BasicBlock *To = U.getTo();
-          if (To) {
-            auto S = To->getName();
-            if (!To->hasName())
-              S = "(no_name)";
-            OS << S << "(" << To << ")\n";
-          } else {
-            OS << "(badref)\n";
-          }
-        }
-      };
-
-  if (DT) {
-    const auto I = PendUpdates.begin() + PendDTUpdateIndex;
-    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
-           "Iterator out of range.");
-    OS << "Applied but not cleared DomTreeUpdates:\n";
-    printUpdates(PendUpdates.begin(), I);
-    OS << "Pending DomTreeUpdates:\n";
-    printUpdates(I, PendUpdates.end());
-  }
-
-  if (PDT) {
-    const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
-    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
-           "Iterator out of range.");
-    OS << "Applied but not cleared PostDomTreeUpdates:\n";
-    printUpdates(PendUpdates.begin(), I);
-    OS << "Pending PostDomTreeUpdates:\n";
-    printUpdates(I, PendUpdates.end());
-  }
-
-  OS << "Pending DeletedBBs:\n";
-  Index = 0;
-  for (auto BB : DeletedBBs) {
-    OS << "  " << Index << " : ";
-    ++Index;
-    if (BB->hasName())
-      OS << BB->getName() << "(";
-    else
-      OS << "(no_name)(";
-    OS << BB << ")\n";
-  }
-
-  OS << "Pending Callbacks:\n";
-  Index = 0;
-  for (auto BB : Callbacks) {
-    OS << "  " << Index << " : ";
-    ++Index;
-    if (BB->hasName())
-      OS << BB->getName() << "(";
-    else
-      OS << "(no_name)(";
-    OS << BB << ")\n";
-  }
-}
-#endif
-} // namespace llvm
diff --git a/llvm/unittests/IR/CMakeLists.txt b/llvm/unittests/IR/CMakeLists.txt
index 58ebf159c3e..17aba85e621 100644
--- a/llvm/unittests/IR/CMakeLists.txt
+++ b/llvm/unittests/IR/CMakeLists.txt
@@ -18,7 +18,6 @@ add_llvm_unittest(IRTests
   DeferredDominanceTest.cpp
   DominatorTreeTest.cpp
   DominatorTreeBatchUpdatesTest.cpp
-  DomTreeUpdaterTest.cpp
   FunctionTest.cpp
   PassBuilderCallbacksTest.cpp
   IRBuilderTest.cpp
diff --git a/llvm/unittests/IR/DomTreeUpdaterTest.cpp b/llvm/unittests/IR/DomTreeUpdaterTest.cpp
deleted file mode 100644
index a6d768920bc..00000000000
--- a/llvm/unittests/IR/DomTreeUpdaterTest.cpp
+++ /dev/null
@@ -1,693 +0,0 @@
-//==- llvm/unittests/IR/DomTreeUpdaterTest.cpp - DomTreeUpdater unit tests ===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/IR/DomTreeUpdater.h"
-#include "llvm/Analysis/PostDominators.h"
-#include "llvm/AsmParser/Parser.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Dominators.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/Module.h"
-#include "llvm/Support/SourceMgr.h"
-#include "gtest/gtest.h"
-#include <algorithm>
-
-using namespace llvm;
-
-static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
-                                              StringRef ModuleStr) {
-  SMDiagnostic Err;
-  std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
-  assert(M && "Bad LLVM IR?");
-  return M;
-}
-
-TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
-  StringRef FuncName = "f";
-  StringRef ModuleString = R"(
-                          define i32 @f(i32 %i, i32 *%p) {
-                          bb0:
-                             store i32 %i, i32 *%p
-                             switch i32 %i, label %bb1 [
-                               i32 1, label %bb2
-                               i32 2, label %bb3
-                             ]
-                          bb1:
-                             ret i32 1
-                          bb2:
-                             ret i32 2
-                          bb3:
-                             ret i32 3
-                          })";
-  // Make the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-  Function *F = M->getFunction(FuncName);
-
-  // Make the DomTreeUpdater.
-  DominatorTree DT(*F);
-  PostDominatorTree PDT(*F);
-  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
-
-  ASSERT_TRUE(DTU.hasDomTree());
-  ASSERT_TRUE(DTU.hasPostDomTree());
-  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Eager);
-  ASSERT_TRUE(DTU.getDomTree().verify());
-  ASSERT_TRUE(DTU.getPostDomTree().verify());
-  ASSERT_FALSE(DTU.hasPendingUpdates());
-
-  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.";
-
-  ASSERT_FALSE(DTU.insertEdgeRelaxed(BB0, BB0));
-  ASSERT_TRUE(DTU.deleteEdgeRelaxed(BB0, BB0));
-
-  // 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.
-  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
-  BB3->removePredecessor(BB0);
-  for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
-    if (i->getCaseSuccessor() == BB3) {
-      SI->removeCase(i);
-      break;
-    }
-  }
-  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);
-  ASSERT_FALSE(DTU.hasPendingUpdates());
-
-  // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
-  ASSERT_FALSE(DTU.insertEdgeRelaxed(BB1, BB2));
-  // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
-  ASSERT_FALSE(DTU.deleteEdgeRelaxed(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,
-                       [&F](BasicBlock *BB) { ASSERT_NE(BB->getParent(), F); });
-
-  ASSERT_TRUE(DT.verify());
-  ASSERT_TRUE(PDT.verify());
-  ASSERT_FALSE(DTU.hasPendingUpdates());
-
-  // Unnecessary flush() test
-  DTU.flush();
-  EXPECT_TRUE(DT.verify());
-  EXPECT_TRUE(PDT.verify());
-
-  // Remove all case branch to BB2 to test Eager recalculation.
-  // Code section from llvm::ConstantFoldTerminator
-  for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
-    if (i->getCaseSuccessor() == BB2) {
-      // Remove this entry.
-      BB2->removePredecessor(BB0);
-      i = SI->removeCase(i);
-      e = SI->case_end();
-    } else
-      ++i;
-  }
-  ASSERT_FALSE(DT.verify());
-  ASSERT_FALSE(PDT.verify());
-  DTU.recalculate(*F);
-  ASSERT_TRUE(DT.verify());
-  ASSERT_TRUE(PDT.verify());
-}
-
-TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
-  StringRef FuncName = "f";
-  StringRef ModuleString = R"(
-                           define i32 @f() {
-                           bb0:
-                              br label %bb1
-                            bb1:
-                              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);
-  PostDominatorTree PDT(*F);
-  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
-  ASSERT_TRUE(DTU.hasDomTree());
-  ASSERT_TRUE(DTU.hasPostDomTree());
-  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Eager);
-  ASSERT_TRUE(DT.verify());
-  ASSERT_TRUE(PDT.verify());
-
-  Function::iterator FI = F->begin();
-  BasicBlock *BB0 = &*FI++;
-  BasicBlock *BB1 = &*FI++;
-
-  // 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);
-
-  ASSERT_TRUE(DTU.insertEdgeRelaxed(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);
-  NewEntry->getTerminator()->eraseFromParent();
-  BranchInst::Create(BB1, NewEntry);
-  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
-
-  // Update the DTU. At this point bb0 now has no predecessors but is still a
-  // Child of F.
-  DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
-                    {DominatorTree::Insert, NewEntry, BB1}});
-  ASSERT_TRUE(DT.verify());
-  ASSERT_TRUE(PDT.verify());
-
-  // Now remove bb0 from F.
-  ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
-  EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
-  DTU.deleteBB(BB0);
-  ASSERT_TRUE(DT.verify());
-  ASSERT_TRUE(PDT.verify());
-}
-
-TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
-  StringRef FuncName = "f";
-  StringRef ModuleString = R"(
-                           define i32 @f(i32 %i, i32 *%p) {
-                            bb0:
-                              store i32 %i, i32 *%p
-                              switch i32 %i, label %bb1 [
-                                i32 0, label %bb2
-                                i32 1, label %bb2
-                                i32 2, label %bb3
-                              ]
-                            bb1:
-                              ret i32 1
-                            bb2:
-                              ret i32 2
-                            bb3:
-                              ret i32 3
-                           }
-                           )";
-  // 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, DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.hasDomTree());
-  ASSERT_FALSE(DTU.hasPostDomTree());
-  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.getDomTree().verify());
-
-  Function::iterator FI = F->begin();
-  BasicBlock *BB0 = &*FI++;
-  BasicBlock *BB1 = &*FI++;
-  BasicBlock *BB2 = &*FI++;
-  BasicBlock *BB3 = &*FI++;
-
-  // Test discards of self-domination update.
-  DTU.deleteEdge(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);
-  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
-  // updates to the DominatorTrees. This code will crash if it is placed before
-  // the BranchInst::Create() call above. After a deletion of a BasicBlock. Only
-  // an explicit flush event can trigger the flushing of deleteBBs. Because some
-  // passes using Lazy UpdateStrategy rely on this behavior.
-
-  ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
-  EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
-  EXPECT_FALSE(DTU.hasPendingDeletedBB());
-  DTU.deleteBB(BB3);
-  EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
-  EXPECT_TRUE(DTU.hasPendingDeletedBB());
-  ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
-  EXPECT_EQ(BB3->getParent(), F);
-  DTU.recalculate(*F);
-
-  EXPECT_FALSE(DTU.hasPendingDeletedBB());
-}
-
-TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
-  StringRef FuncName = "f";
-  StringRef ModuleString = R"(
-                           define i32 @f(i32 %i, i32 *%p) {
-                            bb0:
-                              store i32 %i, i32 *%p
-                              switch i32 %i, label %bb1 [
-                                i32 2, label %bb2
-                                i32 3, label %bb3
-                              ]
-                            bb1:
-                              br label %bb3
-                            bb2:
-                              br label %bb3
-                            bb3:
-                              ret i32 3
-                           }
-                           )";
-  // 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, DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.hasDomTree());
-  ASSERT_FALSE(DTU.hasPostDomTree());
-  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.getDomTree().verify());
-
-  Function::iterator FI = F->begin();
-  BasicBlock *BB0 = &*FI++;
-  BasicBlock *BB1 = &*FI++;
-  BasicBlock *BB2 = &*FI++;
-  BasicBlock *BB3 = &*FI++;
-
-  // There are several CFG locations where we have:
-  //
-  //   pred1..predN
-  //    |        |
-  //    +> curr <+    converted into:   pred1..predN curr
-  //        |                            |        |
-  //        v                            +> succ <+
-  //       succ
-  //
-  // There is a specific shape of this we have to be careful of:
-  //
-  //   pred1..predN
-  //   ||        |
-  //   |+> 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.insertEdge(Pred1, Succ)
-  // while in the latter case we must *NOT* have DTU.insertEdge(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".
-  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".
-  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 call DTU.insertEdge(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);
-  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";
-  StringRef ModuleString = R"(
-                           define i32 @f(i32 %i, i32 *%p) {
-                            bb0:
-                              store i32 %i, i32 *%p
-                              switch i32 %i, label %bb1 [
-                                i32 0, label %bb2
-                                i32 1, label %bb2
-                                i32 2, label %bb3
-                              ]
-                            bb1:
-                              ret i32 1
-                            bb2:
-                              ret i32 2
-                            bb3:
-                              ret i32 3
-                           }
-                           )";
-  // Make the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-  Function *F = M->getFunction(FuncName);
-
-  // Make the DTU.
-  DominatorTree DT(*F);
-  PostDominatorTree PDT(*F);
-  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.hasDomTree());
-  ASSERT_TRUE(DTU.hasPostDomTree());
-  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.getDomTree().verify());
-  ASSERT_TRUE(DTU.getPostDomTree().verify());
-
-  Function::iterator FI = F->begin();
-  BasicBlock *BB0 = &*FI++;
-  BasicBlock *BB1 = &*FI++;
-  BasicBlock *BB2 = &*FI++;
-  BasicBlock *BB3 = &*FI++;
-  // Test discards of self-domination update.
-  DTU.deleteEdge(BB0, BB0);
-
-  // 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});
-
-  // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
-  Updates.push_back({DominatorTree::Insert, BB1, BB2});
-  // Unnecessary 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);
-
-  // 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 DTU.flushDomTree is
-  // called. 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
-  // updates to the DominatorTree. This code will crash if it is placed before
-  // the BranchInst::Create() call above.
-  bool CallbackFlag = false;
-  ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
-  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);
-  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());
-  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
-  ASSERT_FALSE(DTU.hasPendingDeletedBB());
-  ASSERT_EQ(CallbackFlag, true);
-}
-
-TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {
-  StringRef FuncName = "f";
-  StringRef ModuleString = R"(
-                           define i32 @f() {
-                           bb0:
-                              br label %bb1
-                            bb1:
-                              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);
-  PostDominatorTree PDT(*F);
-  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.hasDomTree());
-  ASSERT_TRUE(DTU.hasPostDomTree());
-  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.getDomTree().verify());
-  ASSERT_TRUE(DTU.getPostDomTree().verify());
-
-  Function::iterator FI = F->begin();
-  BasicBlock *BB0 = &*FI++;
-  BasicBlock *BB1 = &*FI++;
-
-  // 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);
-
-  // Insert the new edge between new_entry -> bb0. Without this the
-  // recalculate() call below will not actually recalculate the DT as there
-  // are no changes pending and no blocks deleted.
-  DTU.insertEdge(NewEntry, BB0);
-
-  // Changing the Entry BB requires a full recalculation.
-  DTU.recalculate(*F);
-  ASSERT_TRUE(DTU.getDomTree().verify());
-  ASSERT_TRUE(DTU.getPostDomTree().verify());
-
-  // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
-  EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
-  NewEntry->getTerminator()->eraseFromParent();
-  BranchInst::Create(BB1, NewEntry);
-  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
-
-  // Update the DTU. At this point bb0 now has no predecessors but is still a
-  // Child of F.
-  DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
-                    {DominatorTree::Insert, NewEntry, BB1}});
-  DTU.flush();
-  ASSERT_TRUE(DT.verify());
-  ASSERT_TRUE(PDT.verify());
-
-  // Now remove bb0 from F.
-  ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
-  EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
-  DTU.deleteBB(BB0);
-  EXPECT_TRUE(DTU.isBBPendingDeletion(BB0));
-  ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
-  EXPECT_EQ(BB0->getParent(), F);
-
-  // Perform a full recalculation of the DTU. It is not necessary here but we
-  // do this to test the case when there are no pending DT updates but there are
-  // pending deleted BBs.
-  ASSERT_TRUE(DTU.hasPendingDeletedBB());
-  DTU.recalculate(*F);
-  ASSERT_FALSE(DTU.hasPendingDeletedBB());
-}
-
-TEST(DomTreeUpdater, LazyUpdateStepTest) {
-  // This test focus on testing a DTU holding both trees applying multiple
-  // updates and DT/PDT not flushed together.
-  StringRef FuncName = "f";
-  StringRef ModuleString = R"(
-                           define i32 @f(i32 %i, i32 *%p) {
-                            bb0:
-                              store i32 %i, i32 *%p
-                              switch i32 %i, label %bb1 [
-                                i32 0, label %bb1
-                                i32 1, label %bb2
-                                i32 2, label %bb3
-                                i32 3, label %bb1
-                              ]
-                            bb1:
-                              ret i32 1
-                            bb2:
-                              ret i32 2
-                            bb3:
-                              ret i32 3
-                           }
-                           )";
-  // Make the module.
-  LLVMContext Context;
-  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
-  Function *F = M->getFunction(FuncName);
-
-  // Make the DomTreeUpdater.
-  DominatorTree DT(*F);
-  PostDominatorTree PDT(*F);
-  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
-
-  ASSERT_TRUE(DTU.hasDomTree());
-  ASSERT_TRUE(DTU.hasPostDomTree());
-  ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy);
-  ASSERT_TRUE(DTU.getDomTree().verify());
-  ASSERT_TRUE(DTU.getPostDomTree().verify());
-  ASSERT_FALSE(DTU.hasPendingUpdates());
-
-  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.
-  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->getCaseIndex() == 2) {
-      SI->removeCase(i);
-      break;
-    }
-  }
-  EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
-  // 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);
-
-  // Only flush DomTree.
-  ASSERT_TRUE(DTU.getDomTree().verify());
-  ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
-  ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
-
-  ASSERT_EQ(BB3->getParent(), F);
-  DTU.deleteBB(BB3);
-
-  Updates.clear();
-
-  // Remove all case branch to BB2 to test Eager recalculation.
-  // Code section from llvm::ConstantFoldTerminator
-  for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
-    if (i->getCaseSuccessor() == BB2) {
-      // Remove this entry.
-      BB2->removePredecessor(BB0);
-      i = SI->removeCase(i);
-      e = SI->case_end();
-      Updates.push_back({DominatorTree::Delete, BB0, BB2});
-    } else
-      ++i;
-  }
-
-  DTU.applyUpdates(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());
-}