[Dominators] Introduce batch updates

[kuhar]

Summary

This patch introduces a way of informing the (Post)DominatorTree about multiple CFG updates that happened since the last tree update. This makes performing tree updates much easier, as it internally takes care of applying the updates in lockstep with the (virtual) updates to the CFG, which is done by reverse-applying future CFG updates.

The batch updater is able to remove redundant updates that cancel each other out. In the future, it should be also possible to reorder updates to reduce the amount of work needed to perform the updates.

[brzycki]

The work I am doing to preserve dominance over JumpThreading.cpp and Local.cpp will directly benefit from this new interface. When inserting/removing conditional branch or invoke terminators the only valid option was to perform DT->recalculate(*F) which is expensive. In the case of conditional branches this is also fairly frequent. Being able to queue both insertions and deletions also minimizes the fixup calls.

Kuba, I saw your comments saying the new interface is, in general, more efficient to apply a single batch update vs Insert/Delete. Is it worth the effort for callers to *not* call .applyUpdates() when we know our vector is of size = 1?

include/llvm/Support/GenericDomTreeConstruction.h

83

"using them to gets us" is confusing and grammatically incorrect. I think you meant to say something like "using them gets us a partial snapshot of the..."

[kuhar]

In D36167#830596, @brzycki wrote:

Kuba, I saw your comments saying the new interface is, in general, more efficient to apply a single batch update vs Insert/Delete. Is it worth the effort for callers to *not* call .applyUpdates() when we know our vector is of size = 1?

In that case, the batch updater would do a fair bit of set up work, so I'd recommend calling insert/deleteEdge directly. It should be possible to make this a special case in the batch updater, but I'm not sure if that'd make a real-world difference anywhere.

[kuhar]

Fix a bug with not hiding duplicate children.
Rebase the patch to ToT.

include/llvm/IR/Dominators.h

 extern template class DomTreeNodeBase<BasicBlock>;
 extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
 extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
 
 namespace DomTreeBuilder {
 using BBDomTree = DomTreeBase<BasicBlock>;
 using BBPostDomTree = PostDomTreeBase<BasicBlock>;
 
+extern template struct Update<BasicBlock *>;
+
+using BBUpdates = ArrayRef<Update<BasicBlock *>>;
+
 extern template void Calculate<BBDomTree>(BBDomTree &DT);
 extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
 
 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
                                            BasicBlock *To);
 extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
                                                BasicBlock *From,
                                                BasicBlock *To);
 
 extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
                                            BasicBlock *To);
 extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
                                                BasicBlock *From,
                                                BasicBlock *To);
 
+extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
+extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
+
 extern template bool Verify<BBDomTree>(const BBDomTree &DT);
 extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT);
 }  // namespace DomTreeBuilder
 
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;
 
 class BasicBlockEdge {
   const BasicBlock *Start;

include/llvm/Support/GenericDomTree.h

 ///
 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility>
 #include <vector>
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase;
 
 namespace DomTreeBuilder {
-template <class DomTreeT>
+template <typename DomTreeT>
 struct SemiNCAInfo;
 }  // namespace DomTreeBuilder
 
 /// \brief Base class for the actual dominator tree node.
 template <class NodeT> class DomTreeNodeBase {
   friend struct PostDominatorTree;
   friend class DominatorTreeBase<NodeT, false>;
   friend class DominatorTreeBase<NodeT, true>;
for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
     PrintDomTree<NodeT>(*I, O, Lev + 1);
 }
 
 namespace DomTreeBuilder {
 // The routines below are provided in a separate header but referenced here.
 template <typename DomTreeT>
 void Calculate(DomTreeT &DT);
 
-template <class DomTreeT>
+template <typename DomTreeT>
 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
-template <class DomTreeT>
+template <typename DomTreeT>
 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
+// UpdateKind and Update are used by the batch update API and it's easiest to
+// define them here.
+enum class UpdateKind : unsigned char { Insert, Delete };
+
+template <typename NodePtr>
+struct Update {
+  using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
+
+  NodePtr From;
+  NodeKindPair ToAndKind;
+
+  Update(UpdateKind Kind, NodePtr From, NodePtr To)
+      : From(From), ToAndKind(To, Kind) {}
+
+  UpdateKind getKind() const { return ToAndKind.getInt(); }
+  NodePtr getFrom() const { return From; }
+  NodePtr getTo() const { return ToAndKind.getPointer(); }
+  bool operator==(const Update &RHS) const {
+    return From == RHS.From && ToAndKind == RHS.ToAndKind;
+  }
+
+  friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
+    OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
+    U.getFrom()->printAsOperand(OS, false);
+    OS << " -> ";
+    U.getTo()->printAsOperand(OS, false);
+    return OS;
+  }
+};
+
+template <typename DomTreeT>
+void ApplyUpdates(DomTreeT &DT,
+                  ArrayRef<typename DomTreeT::UpdateType> Updates);
+
 template <typename DomTreeT>
 bool Verify(const DomTreeT &DT);
 }  // namespace DomTreeBuilder
 
 /// \brief Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
 /// various graphs in the LLVM IR or in the code generator.
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase {
  public:
   static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
                 "Currently DominatorTreeBase supports only pointer nodes");
   using NodeType = NodeT;
   using NodePtr = NodeT *;
   using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
   static_assert(std::is_pointer<ParentPtr>::value,
                 "Currently NodeT's parent must be a pointer type");
   using ParentType = typename std::remove_pointer<ParentPtr>::type;
   static constexpr bool IsPostDominator = IsPostDom;
 
+  using UpdateType = DomTreeBuilder::Update<NodePtr>;
+  using UpdateKind = DomTreeBuilder::UpdateKind;
+  static constexpr UpdateKind Insert = UpdateKind::Insert;
+  static constexpr UpdateKind Delete = UpdateKind::Delete;
+
  protected:
   // Dominators always have a single root, postdominators can have more.
   SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
 
   using DomTreeNodeMapType =
      DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
   DomTreeNodeMapType DomTreeNodes;
   DomTreeNodeBase<NodeT> *RootNode;
#endif
   bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
     return isPostDominator() && !A->getBlock();
   }
 
   //===--------------------------------------------------------------------===//
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...
 
+  /// Inform the dominator tree about a sequence of CFG edge insertions and
+  /// deletions and perform a batch update on the tree.
+  ///
+  /// This function should be used when there were multiple CFG updates after
+  /// the last dominator tree update. It takes care of performing the updates
+  /// in sync with the CFG and optimizes away the redundant operations that
+  /// cancel each other.
+  /// The functions expects the sequence of updates to be balanced. Eg.:
+  ///  - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
+  ///    logically it results in a single insertions.
+  ///  - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
+  ///    sense to insert the same edge twice.
+  ///
+  /// What's more, the functions assumes that it's safe to ask every node in the
+  /// CFG about its children and inverse children. This implies that deletions
+  /// of CFG edges must not delete the CFG nodes before calling this function.
+  ///
+  /// Batch updates should be generally faster when performing longer sequences
+  /// of updates than calling insertEdge/deleteEdge manually multiple times, as
+  /// they can reorder the updates and remove redundant ones internally.
+  ///
+  /// Note that for postdominators it automatically takes care of applying
+  /// updates on reverse edges internally (so there's no need to swap the
+  /// From and To pointers when constructing DominatorTree::UpdateType).
+  /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
+  /// with the same template parameter T.
+  ///
+  /// \param Updates An unordered sequence of updates to perform.
+  ///
+  void applyUpdates(ArrayRef<UpdateType> Updates) {
+    DomTreeBuilder::ApplyUpdates(*this, Updates);
+  }
+
   /// Inform the dominator tree about a CFG edge insertion and update the tree.
   ///
   /// This function has to be called just before or just after making the update
   /// on the actual CFG. There cannot be any other updates that the dominator
   /// tree doesn't know about.
   ///
   /// Note that for postdominators it automatically takes care of inserting
   /// a reverse edge internally (so there's no need to swap the parameters).
   ///
   void insertEdge(NodeT *From, NodeT *To) {
     assert(From);
     assert(To);
     assert(From->getParent() == Parent);
     assert(To->getParent() == Parent);
     DomTreeBuilder::InsertEdge(*this, From, To);
   }
 
   /// Inform the dominator tree about a CFG edge deletion and update the tree.
   ///
   /// This function has to be called just after making the update on the actual
   /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
   /// DEBUG mode. There cannot be any other updates that the
   /// dominator tree doesn't know about.
   ///
-  /// However, it is fine to perform multiple CFG deletions that make different
-  /// subtrees forward-unreachable and to inform the DomTree about them all at
-  /// the same time, as the incremental algorithm doesn't walk the tree above
-  /// the NearestCommonDominator of a deleted edge
-  ///
   /// Note that for postdominators it automatically takes care of deleting
   /// a reverse edge internally (so there's no need to swap the parameters).
   ///
   void deleteEdge(NodeT *From, NodeT *To) {
     assert(From);
     assert(To);
     assert(From->getParent() == Parent);
     assert(To->getParent() == Parent);
void updateDFSNumbers() const {
     }
 
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 
   /// recalculate - compute a dominator tree for the given function
   void recalculate(ParentType &Func) {
-    reset();
     Parent = &Func;
     DomTreeBuilder::Calculate(*this);
   }
 
   /// verify - check parent and sibling property
   bool verify() const { return DomTreeBuilder::Verify(*this); }
 
  protected:

include/llvm/Support/GenericDomTreeConstruction.h

 ///   https://arxiv.org/pdf/1604.02711.pdf
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include <queue>
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTree.h"
 
 #define DEBUG_TYPE "dom-tree-builder"
 
 namespace llvm {
 namespace DomTreeBuilder {
 
-template <typename NodePtr, bool Inverse>
-struct ChildrenGetter {
-  static auto Get(NodePtr N) -> decltype(reverse(children<NodePtr>(N))) {
-    return reverse(children<NodePtr>(N));
-  }
-};
-
-template <typename NodePtr>
-struct ChildrenGetter<NodePtr, true> {
-  static auto Get(NodePtr N) -> decltype(inverse_children<NodePtr>(N)) {
-    return inverse_children<NodePtr>(N);
-  }
-};
-
 template <typename DomTreeT>
 struct SemiNCAInfo {
   using NodePtr = typename DomTreeT::NodePtr;
   using NodeT = typename DomTreeT::NodeType;
   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
     unsigned DFSNum = 0;
     unsigned Parent = 0;
     unsigned Semi = 0;
     NodePtr Label = nullptr;
     NodePtr IDom = nullptr;
     SmallVector<NodePtr, 2> ReverseChildren;
   };
 
   // Number to node mapping is 1-based. Initialize the mapping to start with
   // a dummy element.
   std::vector<NodePtr> NumToNode = {nullptr};
   DenseMap<NodePtr, InfoRec> NodeToInfo;
 
+  using UpdateT = typename DomTreeT::UpdateType;
+  struct BatchUpdateInfo {
+    SmallVector<UpdateT, 4> Updates;
+    using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
+
+    // In order to be able to walk a CFG that is out of sync with the CFG
+    // DominatorTree last knew about, use the list of updates to reconstruct
+    // previous CFG versions of the current CFG. For each node, we store a set
+    // of its virtually added/deleted future successors and predecessors.
+    // Note that these children are from the future relative to what the
+    // DominatorTree knows about -- using them to gets us some snapshot of the
+    // CFG from the past (relative to the state of the CFG).
+    DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FutureSuccessors;
+    DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FuturePredecessors;
+    // Remembers if the whole tree was recalculated at some point during the
+    // current batch update.
+    bool IsRecalculated = false;
+  };
+
+  BatchUpdateInfo *BatchUpdates;
+  using BatchUpdatePtr = BatchUpdateInfo *;
+
+  // If BUI is a nullptr, then there's no batch update in progress.
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
+
   void clear() {
     NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
     NodeToInfo.clear();
+    // Don't reset the pointer to BatchUpdateInfo here -- if there's an update
+    // in progress, we need this information to continue it.
   }
 
+  template <bool Inverse>
+  struct ChildrenGetter {
+    using ResultTy = SmallVector<NodePtr, 8>;
+
+    static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
+      auto RChildren = reverse(children<NodePtr>(N));
+      return ResultTy(RChildren.begin(), RChildren.end());
+    }
+
+    static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
+      auto IChildren = inverse_children<NodePtr>(N);
+      return ResultTy(IChildren.begin(), IChildren.end());
+    }
+
+    using Tag = std::integral_constant<bool, Inverse>;
+
+    // The function below is the core part of the batch updater. It allows the
+    // Depth Based Search algorithm to perform incremental updates in lockstep
+    // with updates to the CFG. We emulated lockstep CFG updates by getting its
+    // next snapshots by reverse-applying future updates.
+    static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
+      ResultTy Res = Get(N, Tag());
+      // If there's no batch update in progress, simply return node's children.
+      if (!BUI) return Res;
+
+      // CFG children are actually its *most current* children, and we have to
+      // reverse-apply the future updates to get the node's children at the
+      // point in time the update was performed.
+      auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
+                                                    : BUI->FutureSuccessors;
+      auto FCIt = FutureChildren.find(N);
+      if (FCIt == FutureChildren.end()) return Res;
+
+      for (auto ChildAndKind : FCIt->second) {
+        const NodePtr Child = ChildAndKind.getPointer();
+        const UpdateKind UK = ChildAndKind.getInt();
+
+        // Reverse-apply the future update.
+        if (UK == UpdateKind::Insert) {
+          // If there's an insertion in the future, it means that the edge must
+          // exist in the current CFG, but was not present in it before.
+          auto RIt = llvm::find(Res, Child);
+          assert(RIt != Res.end() && "Expected child not found in the CFG");
+          DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
+                       << BlockNamePrinter(Child) << "\n");
+          std::swap(*RIt, Res.back());
+          Res.pop_back();
+        } else {
+          // If there's an deletion in the future, it means that the edge cannot
+          // exist in the current CFG, but existed in it before.
+          assert(llvm::find(Res, Child) == Res.end() &&
+                 "Unexpected child found in the CFG");
+          DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
+                       << " -> " << BlockNamePrinter(Child) << "\n");
+          Res.push_back(Child);
+        }
+      }
+
+      return Res;
+    }
+  };
+
   NodePtr getIDom(NodePtr BB) const {
     auto InfoIt = NodeToInfo.find(BB);
     if (InfoIt == NodeToInfo.end()) return nullptr;
 
     return InfoIt->second.IDom;
   }
 
   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
while (!WorkList.empty()) {
 
       // Visited nodes always have positive DFS numbers.
       if (BBInfo.DFSNum != 0) continue;
       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
       BBInfo.Label = BB;
       NumToNode.push_back(BB);
 
       constexpr bool Direction = IsReverse != IsPostDom;  // XOR.
-      for (const NodePtr Succ : ChildrenGetter<NodePtr, Direction>::Get(BB)) {
+      for (const NodePtr Succ :
+           ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
         const auto SIT = NodeToInfo.find(Succ);
         // Don't visit nodes more than once but remember to collect
         // RerverseChildren.
         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
           continue;
         }
 
void addVirtualRoot() {
     BBInfo.Label = nullptr;
 
     NumToNode.push_back(nullptr);  // NumToNode[1] = nullptr;
   }
 
   // For postdominators, nodes with no forward successors are trivial roots that
   // are always selected as tree roots. Roots with forward successors correspond
   // to CFG nodes within infinite loops.
-  static bool HasForwardSuccessors(const NodePtr N) {
+  static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
     assert(N && "N must be a valid node");
-    using TraitsTy = GraphTraits<typename DomTreeT::ParentPtr>;
-    return TraitsTy::child_begin(N) != TraitsTy::child_end(N);
+    return !ChildrenGetter<false>::Get(N, BUI).empty();
   }
 
   static NodePtr GetEntryNode(const DomTreeT &DT) {
     assert(DT.Parent && "Parent not set");
     return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
   }
 
   // Finds all roots without relaying on the set of roots already stored in the
   // tree.
   // We define roots to be some non-redundant set of the CFG nodes
-  static RootsT FindRoots(const DomTreeT &DT) {
+  static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
     assert(DT.Parent && "Parent pointer is not set");
     RootsT Roots;
 
     // For dominators, function entry CFG node is always a tree root node.
     if (!IsPostDom) {
       Roots.push_back(GetEntryNode(DT));
       return Roots;
     }
 
-    SemiNCAInfo SNCA;
+    SemiNCAInfo SNCA(BUI);
 
     // PostDominatorTree always has a virtual root.
     SNCA.addVirtualRoot();
     unsigned Num = 1;
 
     DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
 
     // Step #1: Find all the trivial roots that are going to will definitely
     // remain tree roots.
     unsigned Total = 0;
+    // It may happen that there are some new nodes in the CFG that are result of
+    // the ongoing batch update, but we cannot really pretend that they don't
+    // exist -- we won't see any outgoing or incoming edges to them, so it's
+    // fine to discover them here, as they would end up appearing in the CFG at
+    // some point anyway.
     for (const NodePtr N : nodes(DT.Parent)) {
       ++Total;
       // If it has no *successors*, it is definitely a root.
-      if (!HasForwardSuccessors(N)) {
+      if (!HasForwardSuccessors(N, BUI)) {
         Roots.push_back(N);
         // Run DFS not to walk this part of CFG later.
         Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
         DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
                      << "\n");
         DEBUG(dbgs() << "Last visited node: "
                      << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
       }
static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
     DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
     DEBUG(dbgs() << "Discovered CFG nodes:\n");
     DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
           << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
 
     assert((Total + 1 == Num) && "Everything should have been visited");
 
     // Step #3: If we found some non-trivial roots, make them non-redundant.
-    if (HasNonTrivialRoots) RemoveRedundantRoots(DT, Roots);
+    if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
 
     DEBUG(dbgs() << "Found roots: ");
     DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " ");
     DEBUG(dbgs() << "\n");
 
     return Roots;
   }
 
   // This function only makes sense for postdominators.
   // We define roots to be some set of CFG nodes where (reverse) DFS walks have
   // to start in order to visit all the CFG nodes (including the
   // reverse-unreachable ones).
   // When the search for non-trivial roots is done it may happen that some of
   // the non-trivial roots are reverse-reachable from other non-trivial roots,
   // which makes them redundant. This function removes them from the set of
   // input roots.
-  static void RemoveRedundantRoots(const DomTreeT &DT, RootsT &Roots) {
+  static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
+                                   RootsT &Roots) {
     assert(IsPostDom && "This function is for postdominators only");
     DEBUG(dbgs() << "Removing redundant roots\n");
 
-    SemiNCAInfo SNCA;
+    SemiNCAInfo SNCA(BUI);
 
     for (unsigned i = 0; i < Roots.size(); ++i) {
       auto &Root = Roots[i];
       // Trivial roots are always non-redundant.
-      if (!HasForwardSuccessors(Root)) continue;
+      if (!HasForwardSuccessors(Root, BUI)) continue;
       DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
                    << " remains a root\n");
       SNCA.clear();
       // Do a forward walk looking for the other roots.
       const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
       // Skip the start node and begin from the second one (note that DFS uses
       // 1-based indexing).
       for (unsigned x = 2; x <= Num; ++x) {
if (!IsPostDom) {
       return;
     }
 
     addVirtualRoot();
     unsigned Num = 1;
     for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
   }
 
-  void calculateFromScratch(DomTreeT &DT) {
+  static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
+    auto *Parent = DT.Parent;
+    DT.reset();
+    DT.Parent = Parent;
+    SemiNCAInfo SNCA(nullptr);  // Since we are rebuilding the whole tree,
+                                // there's no point doing it incrementally.
+
     // Step #0: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
-    DT.Roots = FindRoots(DT);
-    doFullDFSWalk(DT, AlwaysDescend);
+    DT.Roots = FindRoots(DT, nullptr);
+    SNCA.doFullDFSWalk(DT, AlwaysDescend);
 
-    runSemiNCA(DT);
+    SNCA.runSemiNCA(DT);
+    if (BUI) {
+      BUI->IsRecalculated = true;
+      DEBUG(dbgs() << "DomTree recalculated, skipping future batch updates\n");
+    }
 
     if (DT.Roots.empty()) return;
 
     // Add a node for the root. If the tree is a PostDominatorTree it will be
     // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
     // all real exits (including multiple exit blocks, infinite loops).
     NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
 
     DT.RootNode = (DT.DomTreeNodes[Root] =
                        llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
         .get();
-    attachNewSubtree(DT, DT.RootNode);
+    SNCA.attachNewSubtree(DT, DT.RootNode);
   }
 
   void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
     // Attach the first unreachable block to AttachTo.
     NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
     // Loop over all of the discovered blocks in the function...
     for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
       NodePtr W = NumToNode[i];
std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
         DecreasingLevel>
         Bucket;  // Queue of tree nodes sorted by level in descending order.
     SmallDenseSet<TreeNodePtr, 8> Affected;
     SmallDenseSet<TreeNodePtr, 8> Visited;
     SmallVector<TreeNodePtr, 8> AffectedQueue;
     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
   };
 
-  static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
+  static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
+                         const NodePtr From, const NodePtr To) {
     assert((From || IsPostDom) &&
            "From has to be a valid CFG node or a virtual root");
     assert(To && "Cannot be a nullptr");
     DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
                  << BlockNamePrinter(To) << "\n");
     TreeNodePtr FromTN = DT.getNode(From);
 
     if (!FromTN) {
       // Ignore edges from unreachable nodes for (forward) dominators.
       if (!IsPostDom) return;
 
       // The unreachable node becomes a new root -- a tree node for it.
       TreeNodePtr VirtualRoot = DT.getNode(nullptr);
       FromTN =
           (DT.DomTreeNodes[From] = VirtualRoot->addChild(
                llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
               .get();
       DT.Roots.push_back(From);
     }
 
     DT.DFSInfoValid = false;
 
     const TreeNodePtr ToTN = DT.getNode(To);
     if (!ToTN)
-      InsertUnreachable(DT, FromTN, To);
+      InsertUnreachable(DT, BUI, FromTN, To);
     else
-      InsertReachable(DT, FromTN, ToTN);
+      InsertReachable(DT, BUI, FromTN, ToTN);
   }
 
   // Determines if some existing root becomes reverse-reachable after the
   // insertion. Rebuilds the whole tree if that situation happens.
-  static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const TreeNodePtr From,
+  static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
+                                         const TreeNodePtr From,
                                          const TreeNodePtr To) {
     assert(IsPostDom && "This function is only for postdominators");
     // Destination node is not attached to the virtual root, so it cannot be a
     // root.
     if (!DT.isVirtualRoot(To->getIDom())) return false;
 
     auto RIt = llvm::find(DT.Roots, To->getBlock());
     if (RIt == DT.Roots.end())
       return false;  // To is not a root, nothing to update.
 
     DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
                  << " is no longer a root\n\t\tRebuilding the tree!!!\n");
 
-    DT.recalculate(*DT.Parent);
+    CalculateFromScratch(DT, BUI);
     return true;
   }
 
   // Updates the set of roots after insertion or deletion. This ensures that
   // roots are the same when after a series of updates and when the tree would
   // be built from scratch.
-  static void UpdateRootsAfterUpdate(DomTreeT &DT) {
+  static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
     assert(IsPostDom && "This function is only for postdominators");
 
     // The tree has only trivial roots -- nothing to update.
-    if (std::none_of(DT.Roots.begin(), DT.Roots.end(), HasForwardSuccessors))
+    if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
+          return HasForwardSuccessors(N, BUI);
+        }))
       return;
 
     // Recalculate the set of roots.
-    DT.Roots = FindRoots(DT);
+    DT.Roots = FindRoots(DT, BUI);
     for (const NodePtr R : DT.Roots) {
       const TreeNodePtr TN = DT.getNode(R);
       // A CFG node was selected as a tree root, but the corresponding tree node
       // is not connected to the virtual root. This is because the incremental
       // algorithm does not really know or use the set of roots and can make a
       // different (implicit) decision about which nodes within an infinite loop
       // becomes a root.
       if (DT.isVirtualRoot(TN->getIDom())) {
         DEBUG(dbgs() << "Root " << BlockNamePrinter(R)
                      << " is not virtual root's child\n"
                      << "The entire tree needs to be rebuilt\n");
         // It should be possible to rotate the subtree instead of recalculating
         // the whole tree, but this situation happens extremely rarely in
         // practice.
-        DT.recalculate(*DT.Parent);
+        CalculateFromScratch(DT, BUI);
         return;
       }
     }
   }
 
   // Handles insertion to a node already in the dominator tree.
-  static void InsertReachable(DomTreeT &DT, const TreeNodePtr From,
-                              const TreeNodePtr To) {
+  static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
+                              const TreeNodePtr From, const TreeNodePtr To) {
     DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
                  << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
-    if (IsPostDom && UpdateRootsBeforeInsertion(DT, From, To)) return;
+    if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
     // DT.findNCD expects both pointers to be valid. When From is a virtual
     // root, then its CFG block pointer is a nullptr, so we have to 'compute'
     // the NCD manually.
     const NodePtr NCDBlock =
         (From->getBlock() && To->getBlock())
             ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
             : nullptr;
     assert(NCDBlock || DT.isPostDominator());
while (!II.Bucket.empty()) {
       const TreeNodePtr CurrentNode = II.Bucket.top().second;
       II.Bucket.pop();
       DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
                    << BlockNamePrinter(CurrentNode) << "\n");
       II.Visited.insert(CurrentNode);
       II.AffectedQueue.push_back(CurrentNode);
 
       // Discover and collect affected successors of the current node.
-      VisitInsertion(DT, CurrentNode, CurrentNode->getLevel(), NCD, II);
+      VisitInsertion(DT, BUI, CurrentNode, CurrentNode->getLevel(), NCD, II);
     }
 
     // Finish by updating immediate dominators and levels.
-    UpdateInsertion(DT, NCD, II);
+    UpdateInsertion(DT, BUI, NCD, II);
   }
 
   // Visits an affected node and collect its affected successors.
-  static void VisitInsertion(DomTreeT &DT, const TreeNodePtr TN,
-                             const unsigned RootLevel, const TreeNodePtr NCD,
-                             InsertionInfo &II) {
+  static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
+                             const TreeNodePtr TN, const unsigned RootLevel,
+                             const TreeNodePtr NCD, InsertionInfo &II) {
     const unsigned NCDLevel = NCD->getLevel();
     DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n");
 
     assert(TN->getBlock());
     for (const NodePtr Succ :
-        ChildrenGetter<NodePtr, IsPostDom>::Get(TN->getBlock())) {
+         ChildrenGetter<IsPostDom>::Get(TN->getBlock(), BUI)) {
       const TreeNodePtr SuccTN = DT.getNode(Succ);
       assert(SuccTN && "Unreachable successor found at reachable insertion");
       const unsigned SuccLevel = SuccTN->getLevel();
 
       DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
                    << ", level = " << SuccLevel << "\n");
 
       // Succ dominated by subtree From -- not affected.
       // (Based on the lemma 2.5 from the second paper.)
       if (SuccLevel > RootLevel) {
         DEBUG(dbgs() << "\t\tDominated by subtree From\n");
         if (II.Visited.count(SuccTN) != 0) continue;
 
         DEBUG(dbgs() << "\t\tMarking visited not affected "
                      << BlockNamePrinter(Succ) << "\n");
         II.Visited.insert(SuccTN);
         II.VisitedNotAffectedQueue.push_back(SuccTN);
-        VisitInsertion(DT, SuccTN, RootLevel, NCD, II);
+        VisitInsertion(DT, BUI, SuccTN, RootLevel, NCD, II);
       } else if ((SuccLevel > NCDLevel + 1) && II.Affected.count(SuccTN) == 0) {
         DEBUG(dbgs() << "\t\tMarking affected and adding "
                      << BlockNamePrinter(Succ) << " to a Bucket\n");
         II.Affected.insert(SuccTN);
         II.Bucket.push({SuccLevel, SuccTN});
       }
     }
   }
 
   // Updates immediate dominators and levels after insertion.
-  static void UpdateInsertion(DomTreeT &DT, const TreeNodePtr NCD,
-                              InsertionInfo &II) {
+  static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
+                              const TreeNodePtr NCD, InsertionInfo &II) {
     DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
 
     for (const TreeNodePtr TN : II.AffectedQueue) {
       DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
                    << ") = " << BlockNamePrinter(NCD) << "\n");
       TN->setIDom(NCD);
     }
 
     UpdateLevelsAfterInsertion(II);
-    if (IsPostDom) UpdateRootsAfterUpdate(DT);
+    if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
   }
 
   static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
     DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n");
 
     for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
       DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
                    << BlockNamePrinter(TN->getIDom()) << ") "
                    << TN->getIDom()->getLevel() << " + 1\n");
       TN->UpdateLevel();
     }
   }
 
   // Handles insertion to previously unreachable nodes.
-  static void InsertUnreachable(DomTreeT &DT, const TreeNodePtr From,
-                                const NodePtr To) {
+  static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
+                                const TreeNodePtr From, const NodePtr To) {
     DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
                  << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
 
     // Collect discovered edges to already reachable nodes.
     SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
     // Discover and connect nodes that became reachable with the insertion.
-    ComputeUnreachableDominators(DT, To, From, DiscoveredEdgesToReachable);
+    ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
 
     DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
                  << " -> (prev unreachable) " << BlockNamePrinter(To) << "\n");
 
     DEBUG(DT.print(dbgs()));
 
     // Used the discovered edges and inset discovered connecting (incoming)
     // edges.
     for (const auto &Edge : DiscoveredEdgesToReachable) {
       DEBUG(dbgs() << "\tInserting discovered connecting edge "
                    << BlockNamePrinter(Edge.first) << " -> "
                    << BlockNamePrinter(Edge.second) << "\n");
-      InsertReachable(DT, DT.getNode(Edge.first), Edge.second);
+      InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
     }
   }
 
   // Connects nodes that become reachable with an insertion.
   static void ComputeUnreachableDominators(
-      DomTreeT &DT, const NodePtr Root, const TreeNodePtr Incoming,
+      DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
+      const TreeNodePtr Incoming,
       SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
           &DiscoveredConnectingEdges) {
     assert(!DT.getNode(Root) && "Root must not be reachable");
 
     // Visit only previously unreachable nodes.
     auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
                                                                   NodePtr To) {
       const TreeNodePtr ToTN = DT.getNode(To);
       if (!ToTN) return true;
 
       DiscoveredConnectingEdges.push_back({From, ToTN});
       return false;
     };
 
-    SemiNCAInfo SNCA;
+    SemiNCAInfo SNCA(BUI);
     SNCA.runDFS(Root, 0, UnreachableDescender, 0);
     SNCA.runSemiNCA(DT);
     SNCA.attachNewSubtree(DT, Incoming);
 
     DEBUG(dbgs() << "After adding unreachable nodes\n");
     DEBUG(DT.print(dbgs()));
   }
 
-  static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
+  static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
+                         const NodePtr From, const NodePtr To) {
     assert(From && To && "Cannot disconnect nullptrs");
     DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
                  << BlockNamePrinter(To) << "\n");
 
 #ifndef NDEBUG
     // Ensure that the edge was in fact deleted from the CFG before informing
     // the DomTree about it.
     // The check is O(N), so run it only in debug configuration.
-    auto IsSuccessor = [](const NodePtr SuccCandidate, const NodePtr Of) {
-      auto Successors = ChildrenGetter<NodePtr, IsPostDom>::Get(Of);
+    auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
+      auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
       return llvm::find(Successors, SuccCandidate) != Successors.end();
     };
     (void)IsSuccessor;
     assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
 #endif
 
     const TreeNodePtr FromTN = DT.getNode(From);
     // Deletion in an unreachable subtree -- nothing to do.
#endif
     if (ToTN == NCD) return;
 
     const TreeNodePtr ToIDom = ToTN->getIDom();
     DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
                  << BlockNamePrinter(ToIDom) << "\n");
 
     // To remains reachable after deletion.
     // (Based on the caption under Figure 4. from the second paper.)
-    if (FromTN != ToIDom || HasProperSupport(DT, ToTN))
-      DeleteReachable(DT, FromTN, ToTN);
+    if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
+      DeleteReachable(DT, BUI, FromTN, ToTN);
     else
-      DeleteUnreachable(DT, ToTN);
+      DeleteUnreachable(DT, BUI, ToTN);
 
-    if (IsPostDom) UpdateRootsAfterUpdate(DT);
+    if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
   }
 
   // Handles deletions that leave destination nodes reachable.
-  static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN,
+  static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
+                              const TreeNodePtr FromTN,
                               const TreeNodePtr ToTN) {
     DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> "
                  << BlockNamePrinter(ToTN) << "\n");
     DEBUG(dbgs() << "\tRebuilding subtree\n");
 
     // Find the top of the subtree that needs to be rebuilt.
     // (Based on the lemma 2.6 from the second paper.)
     const NodePtr ToIDom =
         DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
     assert(ToIDom || DT.isPostDominator());
     const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
     assert(ToIDomTN);
     const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
     // Top of the subtree to rebuild is the root node. Rebuild the tree from
     // scratch.
     if (!PrevIDomSubTree) {
       DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
-      DT.recalculate(*DT.Parent);
+      CalculateFromScratch(DT, BUI);
       return;
     }
 
     // Only visit nodes in the subtree starting at To.
     const unsigned Level = ToIDomTN->getLevel();
     auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
       return DT.getNode(To)->getLevel() > Level;
     };
 
     DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
 
-    SemiNCAInfo SNCA;
+    SemiNCAInfo SNCA(BUI);
     SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
     DEBUG(dbgs() << "\tRunning Semi-NCA\n");
     SNCA.runSemiNCA(DT, Level);
     SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
   }
 
   // Checks if a node has proper support, as defined on the page 3 and later
   // explained on the page 7 of the second paper.
-  static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) {
+  static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
+                               const TreeNodePtr TN) {
     DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n");
     for (const NodePtr Pred :
-        ChildrenGetter<NodePtr, !IsPostDom>::Get(TN->getBlock())) {
+         ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
       DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
       if (!DT.getNode(Pred)) continue;
 
       const NodePtr Support =
           DT.findNearestCommonDominator(TN->getBlock(), Pred);
       DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
       if (Support != TN->getBlock()) {
         DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
                      << " is reachable from support "
                      << BlockNamePrinter(Support) << "\n");
         return true;
       }
     }
 
     return false;
   }
 
   // Handle deletions that make destination node unreachable.
   // (Based on the lemma 2.7 from the second paper.)
-  static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) {
+  static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
+                                const TreeNodePtr ToTN) {
     DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN)
                  << "\n");
     assert(ToTN);
     assert(ToTN->getBlock());
 
     if (IsPostDom) {
       // Deletion makes a region reverse-unreachable and creates a new root.
       // Simulate that by inserting an edge from the virtual root to ToTN and
       // adding it as a new root.
       DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
       DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) << "\n");
       DT.Roots.push_back(ToTN->getBlock());
-      InsertReachable(DT, DT.getNode(nullptr), ToTN);
+      InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
       return;
     }
 
     SmallVector<NodePtr, 16> AffectedQueue;
     const unsigned Level = ToTN->getLevel();
 
     // Traverse destination node's descendants with greater level in the tree
     // and collect visited nodes.
     auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
       const TreeNodePtr TN = DT.getNode(To);
       assert(TN);
       if (TN->getLevel() > Level) return true;
       if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
         AffectedQueue.push_back(To);
 
       return false;
     };
 
-    SemiNCAInfo SNCA;
+    SemiNCAInfo SNCA(BUI);
     unsigned LastDFSNum =
         SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
 
     TreeNodePtr MinNode = ToTN;
 
     // Identify the top of the subtree to rebuild by finding the NCD of all
     // the affected nodes.
     for (const NodePtr N : AffectedQueue) {
       const TreeNodePtr TN = DT.getNode(N);
       const NodePtr NCDBlock =
           DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
       assert(NCDBlock || DT.isPostDominator());
       const TreeNodePtr NCD = DT.getNode(NCDBlock);
       assert(NCD);
 
       DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
                    << " with NCD = " << BlockNamePrinter(NCD)
                    << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
       if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
     }
 
     // Root reached, rebuild the whole tree from scratch.
     if (!MinNode->getIDom()) {
       DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
-      DT.recalculate(*DT.Parent);
+      CalculateFromScratch(DT, BUI);
       return;
     }
 
     // Erase the unreachable subtree in reverse preorder to process all children
     // before deleting their parent.
     for (unsigned i = LastDFSNum; i > 0; --i) {
       const NodePtr N = SNCA.NumToNode[i];
       const TreeNodePtr TN = DT.getNode(N);
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
     assert(ChIt != IDom->Children.end());
     std::swap(*ChIt, IDom->Children.back());
     IDom->Children.pop_back();
 
     DT.DomTreeNodes.erase(TN->getBlock());
   }
 
   //~~
+  //===--------------------- DomTree Batch Updater --------------------------===
+  //~~
+
+  static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
+    BatchUpdateInfo BUI;
+    LegalizeUpdates(Updates, BUI.Updates);
+
+    const size_t NumLegalized = BUI.Updates.size();
+    BUI.FutureSuccessors.reserve(NumLegalized);
+    BUI.FuturePredecessors.reserve(NumLegalized);
+
+    // Use the legalized future updates to initialize future successors and
+    // predecessors. Note that these sets will only decrease size over time, as
+    // the next CFG snapshots slowly approach the actual (current) CFG.
+    for (UpdateT &U : BUI.Updates) {
+      BUI.FutureSuccessors[U.getFrom()].insert({U.getTo(), U.getKind()});
+      BUI.FuturePredecessors[U.getTo()].insert({U.getFrom(), U.getKind()});
+    }
+
+    DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
+    DEBUG(if (NumLegalized < 32) for (const auto &U
+                                      : reverse(BUI.Updates)) dbgs()
+          << '\t' << U << "\n");
+    DEBUG(dbgs() << "\n");
+
+    // If the DominatorTree was recalculated at some point, stop the batch
+    // updates. Full recalculations ignore batch updates and look at the actual
+    // CFG.
+    for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
+      ApplyNextUpdate(DT, BUI);
+  }
+
+  // This function serves double purpose:
+  // a) It removes redundant updates, which makes it easier to reverse-apply
+  //    them when traversing CFG.
+  // b) It optimizes away updates that cancel each other out, as the end result
+  //    is the same.
+  //
+  // It relies on the property of the incremental updates that says that the
+  // order of updates doesn't matter. This allows us to reorder them and end up
+  // with the exact same DomTree every time.
+  //
+  // Following the same logic, the function doesn't care about the order of
+  // input updates, so it's OK to pass it an unordered sequence of updates, that
+  // doesn't make sense when applied sequentially, eg. performing double
+  // insertions or deletions and then doing an opposite update.
+  //
+  // In the future, it should be possible to schedule updates in way that
+  // minimizes the amount of work needed done during incremental updates.
+  static void LegalizeUpdates(ArrayRef<UpdateT> AllUpdates,
+                              SmallVectorImpl<UpdateT> &Result) {
+    DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n");
+    // Count the total number of inserions of each edge.
+    // Each insertion adds 1 and deletion subtracts 1. The end number should be
+    // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence
+    // of updates contains multiple updates of the same kind and we assert for
+    // that case.
+    SmallDenseMap<std::pair<NodePtr, NodePtr>, int, 4> Operations;
+    Operations.reserve(AllUpdates.size());
+
+    for (const auto &U : AllUpdates) {
+      NodePtr From = U.getFrom();
+      NodePtr To = U.getTo();
+      if (IsPostDom) std::swap(From, To);  // Reverse edge for postdominators.
+
+      Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1);
+    }
+
+    Result.clear();
+    Result.reserve(Operations.size());
+    for (auto &Op : Operations) {
+      const int NumInsertions = Op.second;
+      assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!");
+      if (NumInsertions == 0) continue;
+      const UpdateKind UK =
+          NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete;
+      Result.push_back({UK, Op.first.first, Op.first.second});
+    }
+
+    // Make the order consistent by not relying on pointer values within the
+    // set. Reuse the old Operations map.
+    // In the future, we should sort by something else to minimize the amount
+    // of work needed to perform the series of updates.
+    for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
+      const auto &U = AllUpdates[i];
+      if (!IsPostDom)
+        Operations[{U.getFrom(), U.getTo()}] = int(i);
+      else
+        Operations[{U.getTo(), U.getFrom()}] = int(i);
+    }
+
+    std::sort(Result.begin(), Result.end(),
+              [&Operations](const UpdateT &A, const UpdateT &B) {
+                return Operations[{A.getFrom(), A.getTo()}] >
+                       Operations[{B.getFrom(), B.getTo()}];
+              });
+  }
+
+  static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
+    assert(!BUI.Updates.empty() && "No updates to apply!");
+    UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
+    DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
+
+    // Move to the next snapshot of the CFG by removing the reverse-applied
+    // current update.
+    auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
+    FS.erase({CurrentUpdate.getTo(), CurrentUpdate.getKind()});
+    if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
+
+    auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
+    FP.erase({CurrentUpdate.getFrom(), CurrentUpdate.getKind()});
+    if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
+
+    if (CurrentUpdate.getKind() == UpdateKind::Insert)
+      InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
+    else
+      DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
+  }
+
+  //~~
   //===--------------- DomTree correctness verification ---------------------===
   //~~
 
   // Check if the tree has correct roots. A DominatorTree always has a single
   // root which is the function's entry node. A PostdDominatorTree can have
   // multiple roots - one for each node with no successors and for infinite
   // loops.
   bool verifyRoots(const DomTreeT &DT) {
if (!IsPostDom) {
 
       if (DT.getRoot() != GetEntryNode(DT)) {
         errs() << "Tree's root is not its parent's entry node!\n";
         errs().flush();
         return false;
       }
     }
 
-    RootsT ComputedRoots = FindRoots(DT);
+    RootsT ComputedRoots = FindRoots(DT, nullptr);
     if (DT.Roots.size() != ComputedRoots.size() ||
         !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
                              ComputedRoots.begin())) {
       errs() << "Tree has different roots than freshly computed ones!\n";
       errs() << "\tPDT roots: ";
       for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
       errs() << "\n\tComputed roots: ";
       for (const NodePtr N : ComputedRoots)
bool verifySiblingProperty(const DomTreeT &DT) {
     }
 
     return true;
   }
 };
 
 template <class DomTreeT>
 void Calculate(DomTreeT &DT) {
-  SemiNCAInfo<DomTreeT> SNCA;
-  SNCA.calculateFromScratch(DT);
+  SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
 }
 
 template <class DomTreeT>
 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To) {
   if (DT.isPostDominator()) std::swap(From, To);
-  SemiNCAInfo<DomTreeT>::InsertEdge(DT, From, To);
+  SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
 }
 
 template <class DomTreeT>
 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To) {
   if (DT.isPostDominator()) std::swap(From, To);
-  SemiNCAInfo<DomTreeT>::DeleteEdge(DT, From, To);
+  SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
+}
+
+template <class DomTreeT>
+void ApplyUpdates(DomTreeT &DT,
+                  ArrayRef<typename DomTreeT::UpdateType> Updates) {
+  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
 }
 
 template <class DomTreeT>
 bool Verify(const DomTreeT &DT) {
-  SemiNCAInfo<DomTreeT> SNCA;
+  SemiNCAInfo<DomTreeT> SNCA(nullptr);
   return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) &&
          SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) &&
          SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT);
 }
 
 }  // namespace DomTreeBuilder
 }  // namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif

lib/IR/Dominators.cpp

 // GenericDomTreeConstruction.h.
 //
 //===----------------------------------------------------------------------===//
 
 template class llvm::DomTreeNodeBase<BasicBlock>;
 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
 
+template struct llvm::DomTreeBuilder::Update<BasicBlock *>;
+
 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT);
 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT);
 
 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
 
+template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
+    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
+template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
+    DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
+
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
     const DomTreeBuilder::BBDomTree &DT);
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
     const DomTreeBuilder::BBPostDomTree &DT);
 
 bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &) {
   // Check whether the analysis, all analyses on functions, or the function's
void DominatorTree::verifyDomTree() const {
 
   DominatorTree OtherDT;
   OtherDT.recalculate(F);
   if (compare(OtherDT)) {
     errs() << "DominatorTree is not up to date!\nComputed:\n";
     print(errs());
     errs() << "\nActual:\n";
     OtherDT.print(errs());
+    errs() << "\nCFG:\n";
+    F.print(errs());
+    errs().flush();
     abort();
   }
 }
 
 //===----------------------------------------------------------------------===//
 //  DominatorTreeAnalysis and related pass implementations
 //===----------------------------------------------------------------------===//
 //

unittests/IR/CMakeLists.txt

set(IRSources
   AttributesTest.cpp
   BasicBlockTest.cpp
   CFGBuilder.cpp
   ConstantRangeTest.cpp
   ConstantsTest.cpp
   DebugInfoTest.cpp
   DebugTypeODRUniquingTest.cpp
   DominatorTreeTest.cpp
+  DominatorTreeBatchUpdatesTest.cpp
   FunctionTest.cpp
   PassBuilderCallbacksTest.cpp
   IRBuilderTest.cpp
   InstructionsTest.cpp
   IntrinsicsTest.cpp
   LegacyPassManagerTest.cpp
   MDBuilderTest.cpp
   MetadataTest.cpp

unittests/IR/DominatorTreeBatchUpdatesTest.cpp

+//===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <random>
+#include "CFGBuilder.h"
+#include "gtest/gtest.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/Support/GenericDomTreeConstruction.h"
+
+#define DEBUG_TYPE "batch-update-tests"
+
+using namespace llvm;
+
+namespace {
+const auto CFGInsert = CFGBuilder::ActionKind::Insert;
+const auto CFGDelete = CFGBuilder::ActionKind::Delete;
+
+struct PostDomTree : PostDomTreeBase<BasicBlock> {
+  PostDomTree(Function &F) { recalculate(F); }
+};
+
+using DomUpdate = DominatorTree::UpdateType;
+static_assert(
+    std::is_same<DomUpdate, PostDomTree::UpdateType>::value,
+    "Trees differing only in IsPostDom should have the same update types");
+using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
+using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
+const auto Insert = DominatorTree::Insert;
+const auto Delete = DominatorTree::Delete;
+
+std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B,
+                                    std::vector<CFGBuilder::Update> &In) {
+  std::vector<DomUpdate> Res;
+  Res.reserve(In.size());
+
+  for (const auto &CFGU : In)
+    Res.push_back({CFGU.Action == CFGInsert ? Insert : Delete,
+                   B.getOrAddBlock(CFGU.Edge.From),
+                   B.getOrAddBlock(CFGU.Edge.To)});
+  return Res;
+}
+}  // namespace
+
+TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
+  CFGHolder Holder;
+  CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
+
+  BasicBlock *A = Builder.getOrAddBlock("A");
+  BasicBlock *B = Builder.getOrAddBlock("B");
+  BasicBlock *C = Builder.getOrAddBlock("C");
+  BasicBlock *D = Builder.getOrAddBlock("D");
+
+  std::vector<DomUpdate> Updates = {
+      {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
+      {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
+  SmallVector<DomUpdate, 4> Legalized;
+  DomSNCA::LegalizeUpdates(Updates, Legalized);
+  DEBUG(dbgs() << "Legalized updates:\t");
+  DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
+  DEBUG(dbgs() << "\n");
+  EXPECT_EQ(Legalized.size(), 3UL);
+  EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end());
+  EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end());
+  EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end());
+}
+
+TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
+  CFGHolder Holder;
+  CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
+
+  BasicBlock *A = Builder.getOrAddBlock("A");
+  BasicBlock *B = Builder.getOrAddBlock("B");
+  BasicBlock *C = Builder.getOrAddBlock("C");
+  BasicBlock *D = Builder.getOrAddBlock("D");
+
+  std::vector<DomUpdate> Updates = {
+      {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
+      {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
+  SmallVector<DomUpdate, 4> Legalized;
+  PostDomSNCA::LegalizeUpdates(Updates, Legalized);
+  DEBUG(dbgs() << "Legalized postdom updates:\t");
+  DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
+  DEBUG(dbgs() << "\n");
+  EXPECT_EQ(Legalized.size(), 3UL);
+  EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end());
+  EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end());
+  EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end());
+}
+
+TEST(DominatorTreeBatchUpdates, SingleInsertion) {
+  CFGHolder Holder;
+  CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}});
+
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+
+  BasicBlock *B = Builder.getOrAddBlock("B");
+  BasicBlock *C = Builder.getOrAddBlock("C");
+  std::vector<DomUpdate> Updates = {{Insert, B, C}};
+
+  ASSERT_TRUE(Builder.applyUpdate());
+
+  DT.applyUpdates(Updates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(Updates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, SingleDeletion) {
+  CFGHolder Holder;
+  CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}},
+                     {{CFGDelete, {"B", "C"}}});
+
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+
+  BasicBlock *B = Builder.getOrAddBlock("B");
+  BasicBlock *C = Builder.getOrAddBlock("C");
+  std::vector<DomUpdate> Updates = {{Delete, B, C}};
+
+  ASSERT_TRUE(Builder.applyUpdate());
+
+  DT.applyUpdates(Updates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(Updates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, FewInsertion) {
+  std::vector<CFGBuilder::Update> CFGUpdates = {{CFGInsert, {"B", "C"}},
+                                                {CFGInsert, {"C", "B"}},
+                                                {CFGInsert, {"C", "D"}},
+                                                {CFGInsert, {"D", "E"}}};
+
+  CFGHolder Holder;
+  CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates);
+
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  BasicBlock *B = Builder.getOrAddBlock("B");
+  BasicBlock *C = Builder.getOrAddBlock("C");
+  BasicBlock *D = Builder.getOrAddBlock("D");
+  BasicBlock *E = Builder.getOrAddBlock("E");
+
+  std::vector<DomUpdate> Updates = {
+      {Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}};
+
+  while (Builder.applyUpdate())
+    ;
+
+  DT.applyUpdates(Updates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(Updates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, FewDeletions) {
+  std::vector<CFGBuilder::Update> CFGUpdates = {{CFGDelete, {"B", "C"}},
+                                                {CFGDelete, {"C", "B"}},
+                                                {CFGDelete, {"B", "D"}},
+                                                {CFGDelete, {"D", "E"}}};
+
+  CFGHolder Holder;
+  CFGBuilder Builder(
+      Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}},
+      CFGUpdates);
+
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  auto Updates = ToDomUpdates(Builder, CFGUpdates);
+
+  while (Builder.applyUpdate())
+    ;
+
+  DT.applyUpdates(Updates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(Updates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, InsertDelete) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
+      {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
+
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"2", "4"}},  {CFGInsert, {"12", "10"}},
+      {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
+      {CFGInsert, {"7", "5"}},  {CFGDelete, {"3", "8"}},
+      {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
+      {CFGDelete, {"3", "4"}},  {CFGDelete, {"8", "9"}},
+      {CFGDelete, {"11", "12"}}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, Updates);
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+  PostDomTree PDT(*Holder.F);
+  EXPECT_TRUE(PDT.verify());
+
+  while (B.applyUpdate())
+    ;
+
+  auto DomUpdates = ToDomUpdates(B, Updates);
+  DT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(DT.verify());
+  PDT.applyUpdates(DomUpdates);
+  EXPECT_TRUE(PDT.verify());
+}
+
+TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
+      {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
+
+  std::vector<CFGBuilder::Update> Updates = {
+      {CFGInsert, {"2", "4"}},  {CFGInsert, {"12", "10"}},
+      {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
+      {CFGInsert, {"7", "5"}},  {CFGDelete, {"3", "8"}},
+      {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
+      {CFGDelete, {"3", "4"}},  {CFGDelete, {"8", "9"}},
+      {CFGDelete, {"11", "12"}}};
+
+  std::mt19937 Generator(0);
+  for (unsigned i = 0; i < 16; ++i) {
+    std::shuffle(Updates.begin(), Updates.end(), Generator);
+    CFGHolder Holder;
+    CFGBuilder B(Holder.F, Arcs, Updates);
+    DominatorTree DT(*Holder.F);
+    EXPECT_TRUE(DT.verify());
+    PostDomTree PDT(*Holder.F);
+    EXPECT_TRUE(PDT.verify());
+
+    while (B.applyUpdate())
+      ;
+
+    auto DomUpdates = ToDomUpdates(B, Updates);
+    DT.applyUpdates(DomUpdates);
+    EXPECT_TRUE(DT.verify());
+    PDT.applyUpdates(DomUpdates);
+    EXPECT_TRUE(PDT.verify());
+  }
+}