Revert "[DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff."

[bondhugula]

Summary

This reverts commit a90374988e4eb8c50d91e11f4e61cdbd5debb235 that
changes LLVM core dominance support and breaks the MLIR build. It looks
completely non-trivial to fix quickly.

[mehdi_amini]

Was reverted, can we drop this one?

[bondhugula]

Another revision performed this revert. Dropping.

clang/include/clang/Analysis/Analyses/Dominators.h

LLVM_DUMP_METHOD void dump() {
     }
   }
 };
 
 } // namespace clang
 
 namespace llvm {
 
+/// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
+/// if statement's condition is always false, it's 'then' branch is represented
+/// with a nullptr. This however will result in a nullpointer derefernece for
+/// dominator tree calculation.
+///
+/// To circumvent this, let's just crudely specialize the children getters
+/// used in LLVM's dominator tree builder.
+namespace DomTreeBuilder {
+
+using ClangCFGDomChildrenGetter =
+    SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
+        /*Inverse=*/false>;
+
+template <>
+template <>
+inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
+  auto RChildren = reverse(children<NodePtr>(N));
+  ResultTy Ret(RChildren.begin(), RChildren.end());
+  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+  return Ret;
+}
+
+using ClangCFGDomReverseChildrenGetter =
+    SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
+        /*Inverse=*/true>;
+
+template <>
+template <>
+inline ClangCFGDomReverseChildrenGetter::ResultTy
+ClangCFGDomReverseChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
+  auto IChildren = inverse_children<NodePtr>(N);
+  ResultTy Ret(IChildren.begin(), IChildren.end());
+  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+  return Ret;
+}
+
+using ClangCFGPostDomChildrenGetter =
+    SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
+        /*Inverse=*/false>;
+
+template <>
+template <>
+inline ClangCFGPostDomChildrenGetter::ResultTy
+ClangCFGPostDomChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
+  auto RChildren = reverse(children<NodePtr>(N));
+  ResultTy Ret(RChildren.begin(), RChildren.end());
+  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+  return Ret;
+}
+
+using ClangCFGPostDomReverseChildrenGetter =
+    SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
+        /*Inverse=*/true>;
+
+template <>
+template <>
+inline ClangCFGPostDomReverseChildrenGetter::ResultTy
+ClangCFGPostDomReverseChildrenGetter::Get(
+    clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
+  auto IChildren = inverse_children<NodePtr>(N);
+  ResultTy Ret(IChildren.begin(), IChildren.end());
+  Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
+  return Ret;
+}
+
+} // end of namespace DomTreeBuilder
+
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
 template <> struct GraphTraits<clang::DomTreeNode *> {
   using NodeRef = ::clang::DomTreeNode *;
   using ChildIteratorType = ::clang::DomTreeNode::iterator;
 

llvm/include/llvm/IR/CFGDiff.h

void print(raw_ostream &OS) const {
     OS << "\n";
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
 };
 
-namespace detail {
-template <typename Range>
-auto reverse_if_helper(Range &&R, std::integral_constant<bool, false>) {
-  return std::forward<Range>(R);
-}
-
-template <typename Range>
-auto reverse_if_helper(Range &&R, std::integral_constant<bool, true>) {
-  return llvm::reverse(std::forward<Range>(R));
-}
-
-template <bool B, typename Range> auto reverse_if(Range &&R) {
-  return reverse_if_helper(std::forward<Range>(R),
-                           std::integral_constant<bool, B>{});
-}
-} // namespace detail
-
 template <typename GraphT, bool InverseGraph = false, bool InverseEdge = false,
           typename GT = GraphTraits<GraphT>>
 struct CFGViewChildren {
   using DataRef = const GraphDiff<typename GT::NodeRef, InverseGraph> *;
   using NodeRef = std::pair<DataRef, typename GT::NodeRef>;
 
   template<typename Range>
   static auto makeChildRange(Range &&R, DataRef DR) {
     using Iter = WrappedPairNodeDataIterator<decltype(std::forward<Range>(R).begin()), NodeRef, DataRef>;
     return make_range(Iter(R.begin(), DR), Iter(R.end(), DR));
   }
 
   static auto children(NodeRef N) {
 
     // filter iterator init:
     auto R = make_range(GT::child_begin(N.second), GT::child_end(N.second));
-    auto RR = detail::reverse_if<!InverseEdge>(R);
     // This lambda is copied into the iterators and persists to callers, ensure
     // captures are by value or otherwise have sufficient lifetime.
-    auto First = make_filter_range(makeChildRange(RR, N.first), [N](NodeRef C) {
+    auto First = make_filter_range(makeChildRange(R, N.first), [N](NodeRef C) {
       return !C.first->ignoreChild(N.second, C.second, InverseEdge);
     });
 
     // new inserts iterator init:
     auto InsertVec = N.first->getAddedChildren(N.second, InverseEdge);
     auto Second = makeChildRange(InsertVec, N.first);
 
     auto CR = concat<NodeRef>(First, Second);

llvm/include/llvm/IR/Dominators.h

 extern template class cfg::Update<BasicBlock *>;
 
 namespace DomTreeBuilder {
 using BBDomTree = DomTreeBase<BasicBlock>;
 using BBPostDomTree = PostDomTreeBase<BasicBlock>;
 
 using BBUpdates = ArrayRef<llvm::cfg::Update<BasicBlock *>>;
 
-using BBDomTreeGraphDiff = GraphDiff<BasicBlock *, false>;
-using BBPostDomTreeGraphDiff = GraphDiff<BasicBlock *, true>;
-
 extern template void Calculate<BBDomTree>(BBDomTree &DT);
 extern template void CalculateWithUpdates<BBDomTree>(BBDomTree &DT,
                                                      BBUpdates U);
 
 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,
-                                             BBDomTreeGraphDiff &);
-extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT,
-                                                 BBPostDomTreeGraphDiff &);
+extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
+extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
 
 extern template bool Verify<BBDomTree>(const BBDomTree &DT,
                                        BBDomTree::VerificationLevel VL);
 extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
                                            BBPostDomTree::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
 using DomTreeNode = DomTreeNodeBase<BasicBlock>;

llvm/include/llvm/Support/GenericDomTree.h

 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
 #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/IR/CFGDiff.h"
 #include "llvm/Support/CFGUpdate.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <type_traits>
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
 template <typename DomTreeT>
 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
 template <typename DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
-                  GraphDiff<typename DomTreeT::NodePtr,
-                            DomTreeT::IsPostDominator> &PreViewCFG);
+                  ArrayRef<typename DomTreeT::UpdateType> Updates);
 
 template <typename DomTreeT>
 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
 /// Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
#endif
   /// cases.
   ///
   /// 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. The current
-  /// CFG and the reverse of these updates provides the pre-view of the CFG.
+  /// \param Updates An unordered sequence of updates to perform.
   ///
   void applyUpdates(ArrayRef<UpdateType> Updates) {
-    GraphDiff<NodePtr, IsPostDominator> PreViewCFG(
-        Updates, /*ReverseApplyUpdates=*/true);
-    DomTreeBuilder::ApplyUpdates(*this, PreViewCFG);
+    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.
   ///

llvm/include/llvm/Support/GenericDomTreeConstruction.h

 
 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;
-  using GraphDiffT = GraphDiff<NodePtr, IsPostDom>;
-  using GraphDiffNodePair = std::pair<const GraphDiffT *, NodePtr>;
-  using GraphDiffInvNodePair = std::pair<const GraphDiffT *, Inverse<NodePtr>>;
-  using GraphDiffNodePairIfDomT =
-      std::conditional_t<!IsPostDom, GraphDiffInvNodePair, GraphDiffNodePair>;
-  using GraphDiffNodePairIfPDomT =
-      std::conditional_t<IsPostDom, GraphDiffInvNodePair, GraphDiffNodePair>;
 
   // 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;
   using UpdateKind = typename DomTreeT::UpdateKind;
   struct BatchUpdateInfo {
-    // Note: Updates inside PreViewCFG are aleady legalized.
-    BatchUpdateInfo(GraphDiffT &PreViewCFG)
-        : PreViewCFG(PreViewCFG),
-          NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
+    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, SmallVector<NodePtrAndKind, 4>> FutureSuccessors;
+    DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FuturePredecessors;
     // Remembers if the whole tree was recalculated at some point during the
     // current batch update.
     bool IsRecalculated = false;
-    GraphDiffT &PreViewCFG;
-    const size_t NumLegalized;
   };
 
   BatchUpdateInfo *BatchUpdates;
   using BatchUpdatePtr = BatchUpdateInfo *;
-  std::unique_ptr<GraphDiffT> EmptyGD;
 
   // If BUI is a nullptr, then there's no batch update in progress.
-  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
-    if (!BatchUpdates)
-      EmptyGD = std::make_unique<GraphDiffT>();
-  }
+  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.
+          assert(llvm::find(Res, Child) != Res.end() &&
+                 "Expected child not found in the CFG");
+          Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
+          LLVM_DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
+                            << BlockNamePrinter(Child) << "\n");
+        } 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");
+          LLVM_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.
-      using DirectedNodeT =
-          std::conditional_t<Direction, Inverse<NodePtr>, NodePtr>;
-      using GraphDiffBBPair = std::pair<const GraphDiffT *, DirectedNodeT>;
-      const auto *GD = BatchUpdates ? &BatchUpdates->PreViewCFG : EmptyGD.get();
-      for (auto &Pair : children<GraphDiffBBPair>({GD, BB})) {
-        const NodePtr Succ = Pair.second;
+      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
         // ReverseChildren.
         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
           continue;
         }
 
void addVirtualRoot() {
     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, BatchUpdatePtr BUI) {
     assert(N && "N must be a valid node");
-    GraphDiffT EmptyGD;
-    auto &GD = BUI ? BUI->PreViewCFG : EmptyGD;
-    return !llvm::empty(children<GraphDiffNodePair>({&GD, 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
while (!II.Bucket.empty()) {
         // Unlike regular Dijkstra, we have an inner loop to expand more
         // vertices. The first iteration is for the (affected) vertex popped
         // from II.Bucket and the rest are for vertices in
         // UnaffectedOnCurrentLevel, which may eventually expand to affected
         // vertices.
         //
         // Invariant: there is an optimal path from `To` to TN with the minimum
         // depth being CurrentLevel.
-        GraphDiffT EmptyGD;
-        auto &GD = BUI ? BUI->PreViewCFG : EmptyGD;
-        for (auto &Pair :
-             children<GraphDiffNodePairIfPDomT>({&GD, TN->getBlock()})) {
-          const NodePtr Succ = Pair.second;
+        for (const NodePtr Succ :
+             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();
 
           LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
                             << ", level = " << SuccLevel << "\n");
 
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
     LLVM_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 = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
-      GraphDiffT EmptyGD;
-      auto &GD = BUI ? BUI->PreViewCFG : EmptyGD;
-      for (auto &Pair : children<GraphDiffNodePairIfPDomT>({&GD, Of}))
-        if (Pair.second == SuccCandidate)
-          return true;
-      return false;
+      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.
     if (!FromTN) return;
#endif
   }
 
   // Checks if a node has proper support, as defined on the page 3 and later
   // explained on the page 7 of [2].
   static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
                                const TreeNodePtr TN) {
     LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
                       << "\n");
-    auto TNB = TN->getBlock();
-    GraphDiffT EmptyGD;
-    auto &GD = BUI ? BUI->PreViewCFG : EmptyGD;
-    for (auto &Pair : children<GraphDiffNodePairIfDomT>({&GD, TNB})) {
-      const NodePtr Pred = Pair.second;
+    for (const NodePtr Pred :
+         ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
       LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
       if (!DT.getNode(Pred)) continue;
 
-      const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
+      const NodePtr Support =
+          DT.findNearestCommonDominator(TN->getBlock(), Pred);
       LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
-      if (Support != TNB) {
+      if (Support != TN->getBlock()) {
         LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
                           << " is reachable from support "
                           << BlockNamePrinter(Support) << "\n");
         return true;
       }
     }
 
     return false;
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
 
     DT.DomTreeNodes.erase(TN->getBlock());
   }
 
   //~~
   //===--------------------- DomTree Batch Updater --------------------------===
   //~~
 
-  static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG) {
-    const size_t NumUpdates = PreViewCFG.getNumLegalizedUpdates();
+  static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
+    const size_t NumUpdates = Updates.size();
     if (NumUpdates == 0)
       return;
 
     // Take the fast path for a single update and avoid running the batch update
     // machinery.
     if (NumUpdates == 1) {
-      UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates();
+      const auto &Update = Updates.front();
       if (Update.getKind() == UpdateKind::Insert)
-        InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
+        DT.insertEdge(Update.getFrom(), Update.getTo());
       else
-        DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
+        DT.deleteEdge(Update.getFrom(), Update.getTo());
+
       return;
     }
 
-    BatchUpdateInfo BUI(PreViewCFG);
+    BatchUpdateInfo BUI;
+    LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
+    cfg::LegalizeUpdates<NodePtr>(Updates, BUI.Updates, IsPostDom);
+
+    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()].push_back({U.getTo(), U.getKind()});
+      BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
+    }
+
+#if 0
+    // FIXME: The LLVM_DEBUG macro only plays well with a modular
+    // build of LLVM when the header is marked as textual, but doing
+    // so causes redefinition errors.
+    LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
+    LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
+                                           : reverse(BUI.Updates)) {
+      dbgs() << "\t";
+      U.dump();
+      dbgs() << "\n";
+    });
+    LLVM_DEBUG(dbgs() << "\n");
+#endif
+
     // Recalculate the DominatorTree when the number of updates
     // exceeds a threshold, which usually makes direct updating slower than
     // recalculation. We select this threshold proportional to the
     // size of the DominatorTree. The constant is selected
     // by choosing the one with an acceptable performance on some real-world
     // inputs.
 
     // Make unittests of the incremental algorithm work
     if (DT.DomTreeNodes.size() <= 100) {
-      if (BUI.NumLegalized > DT.DomTreeNodes.size())
+      if (NumLegalized > DT.DomTreeNodes.size())
         CalculateFromScratch(DT, &BUI);
-    } else if (BUI.NumLegalized > DT.DomTreeNodes.size() / 40)
+    } else if (NumLegalized > DT.DomTreeNodes.size() / 40)
       CalculateFromScratch(DT, &BUI);
 
     // 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 < BUI.NumLegalized && !BUI.IsRecalculated; ++i)
+    for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
       ApplyNextUpdate(DT, BUI);
   }
 
   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
-    // Popping the next update, will move the PreViewCFG to the next snapshot.
-    UpdateT CurrentUpdate = BUI.PreViewCFG.popUpdateForIncrementalUpdates();
+    assert(!BUI.Updates.empty() && "No updates to apply!");
+    UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
 #if 0
     // FIXME: The LLVM_DEBUG macro only plays well with a modular
     // build of LLVM when the header is marked as textual, but doing
     // so causes redefinition errors.
     LLVM_DEBUG(dbgs() << "Applying update: ");
     LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
 #endif
 
+    // Move to the next snapshot of the CFG by removing the reverse-applied
+    // current update. Since updates are performed in the same order they are
+    // legalized it's sufficient to pop the last item here.
+    auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
+    assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
+           FS.back().getInt() == CurrentUpdate.getKind());
+    FS.pop_back();
+    if (FS.empty())
+      BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
+
+    auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
+    assert(FP.back().getPointer() == CurrentUpdate.getFrom() &&
+           FP.back().getInt() == CurrentUpdate.getKind());
+    FP.pop_back();
+    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 ---------------------===

 template <class DomTreeT>
 void Calculate(DomTreeT &DT) {
   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
 }
 
 template <typename DomTreeT>
 void CalculateWithUpdates(DomTreeT &DT,
                           ArrayRef<typename DomTreeT::UpdateType> Updates) {
-  // FIXME: Updated to use the PreViewCFG and behave the same as until now.
-  // This behavior is however incorrect; this actually needs the PostViewCFG.
-  GraphDiff<typename DomTreeT::NodePtr, DomTreeT::IsPostDominator> PreViewCFG(
-      Updates, /*ReverseApplyUpdates=*/true);
-  typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI(PreViewCFG);
+  // TODO: Move BUI creation in common method, reuse in ApplyUpdates.
+  typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI;
+  LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
+  cfg::LegalizeUpdates<typename DomTreeT::NodePtr>(Updates, BUI.Updates,
+                                                   DomTreeT::IsPostDominator);
+  const size_t NumLegalized = BUI.Updates.size();
+  BUI.FutureSuccessors.reserve(NumLegalized);
+  BUI.FuturePredecessors.reserve(NumLegalized);
+  for (auto &U : BUI.Updates) {
+    BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
+    BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
+  }
+
   SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, &BUI);
 }
 
 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, 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, nullptr, From, To);
 }
 
 template <class DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
-                  GraphDiff<typename DomTreeT::NodePtr,
-                            DomTreeT::IsPostDominator> &PreViewCFG) {
-  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, PreViewCFG);
+                  ArrayRef<typename DomTreeT::UpdateType> Updates) {
+  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
 }
 
 template <class DomTreeT>
 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
   SemiNCAInfo<DomTreeT> SNCA(nullptr);
 
   // Simplist check is to compare against a new tree. This will also
   // usefully print the old and new trees, if they are different.

llvm/lib/IR/Dominators.cpp

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::BBDomTreeGraphDiff &);
+    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
-    DomTreeBuilder::BBPostDomTree &DT,
-    DomTreeBuilder::BBPostDomTreeGraphDiff &);
+    DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
 
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
     const DomTreeBuilder::BBDomTree &DT,
     DomTreeBuilder::BBDomTree::VerificationLevel VL);
 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
     const DomTreeBuilder::BBPostDomTree &DT,
     DomTreeBuilder::BBPostDomTree::VerificationLevel VL);