[DomTree] Replace ChildrenGetter with GraphTraits over GraphDiff.

[asbirlea]

Summary

This replaces the logic inChildrenGetter inside the DominatorTree with
GraphTraits over a GraphDiff object, an object which encapsulated the
view of the previous CFG.

The simplification step removing the extensions in clang which use DominatorTree and also filters for nullptr are deferred to a subsequent cleanup patch.

[asbirlea]

I sent this out to get some general feedback, but I'd like to be able to simplify the fact that this is replacing a for over ChildrenGetter with a for over children<type>(pair), plus 5 lines to set up the type and pair; one simplification is around getting the type inside children (GraphDiffBBPair) and another around having the BUI or not; for the latter I'm considering updating a few places such that BUI is never nullptr.

[dblaikie]

Couple of small nits, but I'll leave most of the review to someoen else here - I /think/ it's beyond my context/experience (but if necessary, poke me and I can look more/ask more questions/etc)

llvm/include/llvm/Support/GenericDomTreeConstruction.h

340–341

No need for make_pair if you're going to specify the types on the LHS, could write this as:

std::pair<...> GDNodePair(GDTmp, N);

(similarly two instances further down in this patch - make_pair or explicit type, not both)

Or you could use auto on the LHS given the types of the two parameters seem close enough that it's not too surprising what make_pair produces, maybe even just roll it all in together:

return !empty(children<GraphDiffBBPair>(std::make_pair(GDTmp, N)));

342–346

Probably write this as (if I'm understanding the code/intent correctly):

return !empty(children<GraphDiffBBPair>(GDNodePair));

[kuhar]

llvm/include/llvm/IR/CFGDiff.h

199 ↗

(On Diff #254638)

You can use two helper functions taking integral_constant<bool, true/false> tags -- should be less verbose

llvm/include/llvm/Support/GenericDomTreeConstruction.h

89

nit: Why pointer instead of keeping a reference?

202

nit: use using instead of typefef.

203

nit: can we use std::conditional_t<...> in c++14 to get rid of typename and ::type? Or does it make some buildbots unhappy?

204

nit: I don't find this name very informative. Maybe something like DirectedBB?

208

std::pair<const GraphDiffT *, NodePtr> GDNodePair(GDTmp, BB)

210

Won't children infer the template parameter based on the passes value? I don't get why the template argument type is a pair where the second argument is a directed nodeptr, but the runtime value is always a plain nodeptr. Couldn't the second pair type also be directed for GDNodePair?

211

Could this new code be a hoisted into a helper function?

1121

Could you add a comment next to the nullptr with the argument name?

1519

Does this care about the direction (pre- or post-) at all, or does it need some CFG view? Why is pre-view incorrect?

[kuhar]

llvm/include/llvm/Support/GenericDomTreeConstruction.h

211

Or alternatively, could the old ChildrenGetter be implemented with these 5 magic lines?

[asbirlea]

Address comments.

llvm/include/llvm/Support/GenericDomTreeConstruction.h

210

The directed nodeptr is the equivalent of a bool inside GraphDiff translating to what kind of children do you want; the second pair argument bears no info of that kind, only the actual NodePtr for which we desire the children.

211

I think it looks much cleaner after the latest update, let me know what you think.

1519

The purpose of this method was to update the DT assuming an additional list of updates (the argument given). In practice, the BUI argument is ignored in the CalculateFromScratch call below. Hence we need the additional changes to support this kind of updates inside CalculateFromScratch and the other methods.

[kuhar]

In D77341#1960854, @asbirlea wrote:

Address comments.

Thanks for the changes and explanations. It think with a few more tweaks this will be a good refactoring step towards phasing out BUI.

llvm/include/llvm/IR/CFGDiff.h

198 ↗

(On Diff #254943)

What benefit does an anonymous namespace in a header have over a named one, e.g., detail/impl? Doesn't it make it more difficult to deduplicate symbols across different translation units? Not sure what the best practices are in C++ now in this area.

llvm/include/llvm/Support/GenericDomTreeConstruction.h

339

This pattern repeats a few times. Could it be pushed into a helper function to get something like this?

return !empty(children<GraphDiffNodePair>(GetGraphDiffNodePair(BUI, N)));

[kuhar]

llvm/include/llvm/IR/CFGDiff.h

198 ↗

(On Diff #254943)

Found an article on this matter: https://wiki.sei.cmu.edu/confluence/display/cplusplus/DCL59-CPP.+Do+not+define+an+unnamed+namespace+in+a+header+file

[dblaikie]

llvm/include/llvm/IR/CFGDiff.h

198 ↗

(On Diff #254943)

Oh, yeah, sorry I didn't spot that - yeah, anonymous namespaces in header files are a no-go. This should be a detail (detail outnumbers impl 361 to 41 in the LLVM project) namespace within the llvm namespace as suggested.

[asbirlea]

llvm/include/llvm/Support/GenericDomTreeConstruction.h

339

My dilemma here is how to not allocate a GraphDiffT instance. There are 4 cases where the pattern is inside a static method and once in a class method. I used a stack var for the 4 cases and a unique_ptr for the class method.

Sure, I can do:

static auto getGDNPair(BUI, EmptyGD, N) {
return std::make_pair<>(BUI ? BUI->PreViewCFG : EmptyGD, N);
}
{
...
GraphDiffT EmptyGD;
return !empty(children<GraphDiffNodePair>(getGDNPair(BUI, &EmptyGD, N)));
}

But it felt like moving one line at the callsite to a oneline helper is not making things much better.

I was hoping for something more along the lines of:

return !empty(children<GraphDiffNodePair>({getGD(BUI), N});

Or, ensure BUI is always non-null, and simplify to:

return !empty(children<GraphDiffNodePair>({BUI->PreViewCFG, N});

Thoughts?

[asbirlea]

Name anonymous namespace.

[kuhar]

Looks good to me overall. I don't want to block it over the cosmetic issues like allocating the empty GD object.

llvm/include/llvm/Support/GenericDomTreeConstruction.h

339

Does allocating a GD have a big cost?

I think you could get away with returning a temporary GD object that would die as soon as the expression evaluation ends -- should be no different than placing it on the stack just before the function call.

Overall, I still don't understand why you try to avoid creating a wrapper function / struct that returns children, and call childredn<...>(...) directly. Either way, I being able to write:

return !empty(children<GraphDiffNodePair>({getGD(BUI), N});

or

return !empty(getChildren<GraphDiffNodePair>(BUI, N));

would definitely be concise and readable enough IMO.

[asbirlea]

Thank you for all the comments.

llvm/include/llvm/Support/GenericDomTreeConstruction.h

339

Does allocating a GD have a big cost?

AFAIU, dynamically allocating the object does, vs having a stack variable.

I'll do a follow-up cleanup attempt.

[stella.stamenova]

It looks like this broke the windows lldb buildbot:

lab.llvm.org:8011/builders/lldb-x64-windows-ninja/builds/15542

It already had a test failure, so you probably didn’t get the email.

[bondhugula]

@asbirlea This has broken the MLIR build. Could you please build with -DLLVM_ENABLE_PROJECTS=mlir?

FAILED: tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o 
/usr/lib64/ccache/clang++  -DGTEST_HAS_RTTI=0 -DMLIR_CUDA_CONVERSIONS_ENABLED=1 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/mlir/lib/Analysis -I/home/uday/llvm-project/mlir/lib/Analysis -I/usr/include/libxml2 -Iinclude -I/home/uday/llvm-project/llvm/include -I/home/uday/llvm-project/mlir/include -Itools/mlir/include -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wstring-conversion -fdiagnostics-color -ffunction-sections -fdata-sections -O2     -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o -MF tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o.d -o tools/mlir/lib/Analysis/CMakeFiles/MLIRAnalysis.dir/Dominance.cpp.o -c /home/uday/llvm-project/mlir/lib/Analysis/Dominance.cpp
In file included from /home/uday/llvm-project/mlir/lib/Analysis/Dominance.cpp:14:
In file included from /home/uday/llvm-project/mlir/include/mlir/Analysis/Dominance.h:12:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/RegionGraphTraits.h:18:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/Region.h:16:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/Block.h:16:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/BlockSupport.h:16:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/Value.h:16:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/Types.h:12:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/TypeSupport.h:17:
In file included from /home/uday/llvm-project/mlir/include/mlir/IR/StorageUniquerSupport.h:17:
In file included from /home/uday/llvm-project/mlir/include/mlir/Support/STLExtras.h:18:
In file included from /home/uday/llvm-project/llvm/include/llvm/ADT/STLExtras.h:20:
/home/uday/llvm-project/llvm/include/llvm/ADT/iterator.h:366:17: error: indirection requires pointer operand ('const mlir::PredecessorIterator' invalid)
    NR.second = *this->I;

[mehdi_amini]

llvm/include/llvm/Support/GenericDomTree.h

31

This looks like a layering violation to me here: I wouldn't expect a generic utility in Support to introduce a dependency on IR.

I speculatively reverted in https://github.com/llvm/llvm-project/commit/57d2d48399b63c0ef1dda490fdaf28efbb80c2c0 while we can figure it out.

[mehdi_amini]

In D77341#1973827, @bondhugula wrote:

@asbirlea This has broken the MLIR build. Could you please build with -DLLVM_ENABLE_PROJECTS=mlir?

If you use arcanist, you get pre-merge testing on Phabricator :)

[dblaikie]

llvm/include/llvm/Support/GenericDomTree.h

31

Yep - agreed on the layering violation. Thanks for the catch/revert!

I /think/ CFGDiff.h is independent of IR & shouldn't include IR/CFG.h and then can move into Support. Ah, yeah, when I did 30804d0a3fb23325c4b455108e59d00213b83891 & related work, that's what made it independent of IR.

Moved it over to Support in a838aadae3f20b9644e2ad553d3d558a91fd8fd7

[mehdi_amini]

llvm/include/llvm/Support/GenericDomTree.h

31

Thanks! Re-landed in 0445c64998d14b81f0d3a3182011fc5eae47fa71

[mehdi_amini]

llvm/include/llvm/Support/GenericDomTree.h

31

Actually reverted again as it breaks the MLIR build in a different way, I won't be able to look into this in more details right now.

(I ran ninja check but I forgot that check is not check-all...)

[nikic]

This change causes a 2.5% compile-time regression across the board, see http://llvm-compile-time-tracker.com/compare.php?from=37bcf2df01cfa47e4509a5d225a23e2ca95005e6&to=a90374988e4eb8c50d91e11f4e61cdbd5debb235&stat=instructions. Can you please try to find a cheaper way to approach this issue?

[asbirlea]

I'm working to update this revision to address the compile-time regression.
Re-opening so I can rebase and add misc fixes and will mark as changes planned until I address the compile-time issue.

[asbirlea]

Rebase.

[asbirlea]

Updated to include the part of the patch that's moving the Updates to a CFGDiff object. Splitting off from the clean-up work merging the two branches when BUI is null.
This patch does not exhibit the compile-time regression which caused it to be reverted previously.

[asbirlea]

Nit: re-add consts

[nikic]

Numbers for the new patch: https://llvm-compile-time-tracker.com/compare.php?from=c0308fd154f9a945608bd42630dc81dce5edfb40&to=e6e3534e77961cfa65d36828de5c75f36a25d009&stat=instructions

The regression is definitely smaller now, but still fairly large. E.g. > 2% on mafft.

[asbirlea]

Thank you for the testing. Could you help with with instructions on how to run the tracker myself?
My local testing showed a negligible regression for mafft and a negligible improvement on other benchmarks, so it looked like noise on average.

[nikic]

In D77341#2144974, @asbirlea wrote:

Thank you for the testing. Could you help with with instructions on how to run the tracker myself?
My local testing showed a negligible regression for mafft and a negligible improvement on other benchmarks, so it looked like noise on average.

The tracker just compiles test-suite under perf stat using the cached cmake configs. If I pick out the file with the largest regression (mafft constants.c in ReleaseThinLTO config with 18% regression) I can reproduce this locally as follows:

perf stat /home/nikic/llvm-project/build/bin/clang -DNDEBUG  -O3 -fomit-frame-pointer -flto=thin -DNDEBUG   -w -Werror=date-time -DLLVM -MD -MT MultiSource/Benchmarks/mafft/CMakeFiles/pairlocalalign.dir/constants.c.o -MF MultiSource/Benchmarks/mafft/CMakeFiles/pairlocalalign.dir/constants.c.o.d -o MultiSource/Benchmarks/mafft/CMakeFiles/pairlocalalign.dir/constants.c.o   -c ../MultiSource/Benchmarks/mafft/constants.c

This gives me 3.5M instructions before and 4.2M instructions after. Those particular numbers are for an assertion-enabled build (the numbers on the website are without assertions.)

[asbirlea]

The increase in number of instructions and cycles was caused by reversing the order in which the updates are applied by GraphDiff.
I'll look into re-adding some of the original cleanups in a follow-up patch.

[dblaikie]

In D77341#2171305, @asbirlea wrote:

The increase in number of instructions and cycles was caused by reversing the order in which the updates are applied by GraphDiff.
I'll look into re-adding some of the original cleanups in a follow-up patch.

Fascinating - and you were able to reproduce this by just reversing the order in the old code (using ChildrenGetter/building a vector and returning it - not using all the iterator adapters, etc) and that the performance problem was no longer present in the new code if you changed its order to match?

Huh. (again, sorry this has been such a slog :/)

[asbirlea]

Yes. The difference in perf in instructions and cycles count is due to reversing the update order.
I'm still not seeing meaningful changes in wall-time even with the update order reversed, but reliable wall-time testing is hard.

I do have changes that

• drop the GraphTraits usage entirely in favor of the getChildren() method in GraphDiff
• refactor the hashmaps in GraphDiff

but I plan to send those separately.

[nikic]

Numbers for the newest version: https://llvm-compile-time-tracker.com/compare.php?from=183342c0a9850e60dd7a004b651c83dfb3a7d25e&to=eabcf534fe8760d14c95b40f07c61450c819d643&stat=instructions

This is now a geomean 0.2% regressions, and I don't see any large outliers for individual files either (everything is below 2%). So this should be fine now, at least where compile-time impact is concerned :)

[asbirlea]

Great, thank you for confirming :-)

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, BBUpdates);
-extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
+extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT,
+                                             BBDomTreeGraphDiff &);
+extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT,
+                                                 BBPostDomTreeGraphDiff &);
 
 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/CFGDiff.h

 // Regular CFG, reverse edges, so children mean predecessors,
 // InverseGraph = false, InverseEdge = true.
 // 4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>
 //        : CFGViewPredecessors<true>
 // Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.
 
 namespace llvm {
 
+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
+
 // GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
 // utilities to skip edges marked as deleted and return a set of edges marked as
 // newly inserted. The current diff treats the CFG as a graph rather than a
 // multigraph. Added edges are pruned to be unique, and deleted edges will
 // remove all existing edges between two blocks.
 template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
   using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
   struct EdgesInsertedDeleted {
for (auto Pair : M)
       }
     OS << "\n";
   }
 
 public:
   GraphDiff() : UpdatedAreReverseApplied(false) {}
   GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates,
             bool ReverseApplyUpdates = false) {
-    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph,
-                                  /*ReverseResultOrder=*/true);
+    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph);
     // The legalized updates are stored in reverse so we can pop_back when doing
     // incremental updates.
     for (auto U : LegalizedUpdates) {
       unsigned IsInsert =
           (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates;
       Edges[IsInsert].Succ[U.getFrom()].push_back(U.getTo());
       Edges[IsInsert].Pred[U.getTo()].push_back(U.getFrom());
     }
getAddedChildren(const NodePtr BB, bool InverseEdge) const {
     auto &InsertChildren =
         (InverseEdge != InverseGraph) ? Edges[1].Pred : Edges[1].Succ;
     auto It = InsertChildren.find(BB);
     if (It == InsertChildren.end())
       return make_range(Empty.begin(), Empty.end());
     return make_range(It->second.begin(), It->second.end());
   }
 
+  using VectRet = SmallVector<NodePtr, 8>;
+
+  template <bool InverseEdge> VectRet getChildren(NodePtr N) const {
+    using DirectedNodeT =
+        std::conditional_t<InverseEdge, Inverse<NodePtr>, NodePtr>;
+    auto R = children<DirectedNodeT>(N);
+    auto CurrentCFGChildren = detail::reverse_if<!InverseEdge>(R);
+
+    VectRet UpdatedCFGChildren;
+    for (auto Child : CurrentCFGChildren)
+      if (Child && !ignoreChild(N, Child, InverseEdge))
+        UpdatedCFGChildren.push_back(Child);
+
+    auto AddedCFGChildren = getAddedChildren(N, InverseEdge);
+    UpdatedCFGChildren.insert(UpdatedCFGChildren.end(),
+                              AddedCFGChildren.begin(), AddedCFGChildren.end());
+    return UpdatedCFGChildren;
+  }
+
   void print(raw_ostream &OS) const {
     OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
           "===== (Note: notion of children/inverse_children depends on "
           "the direction of edges and the graph.)\n";
     OS << "Children to insert:\n\t";
     printMap(OS, Edges[1].Succ);
     OS << "Children to delete:\n\t";
     printMap(OS, Edges[0].Succ);
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(R, N.first), [N](NodeRef C) {
+    auto First = make_filter_range(makeChildRange(RR, 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/Support/GenericDomTree.h

 #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/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,
-                  ArrayRef<typename DomTreeT::UpdateType> Updates);
+                  GraphDiff<typename DomTreeT::NodePtr,
+                            DomTreeT::IsPostDominator> &PreViewCFG);
 
 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.
+  /// \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.
   ///
   void applyUpdates(ArrayRef<UpdateType> Updates) {
-    DomTreeBuilder::ApplyUpdates(*this, Updates);
+    GraphDiff<NodePtr, IsPostDominator> PreViewCFG(
+        Updates, /*ReverseApplyUpdates=*/true);
+    DomTreeBuilder::ApplyUpdates(*this, PreViewCFG);
   }
 
   /// 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>;
 
   // 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 {
-    SmallVector<UpdateT, 4> Updates;
-    using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
+    // Note: Updates inside PreViewCFG are aleady legalized.
+    BatchUpdateInfo(GraphDiffT &PreViewCFG)
+        : PreViewCFG(PreViewCFG),
+          NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
 
-    // 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) {}
+  SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {
+    if (!BatchUpdates)
+      EmptyGD = std::make_unique<GraphDiffT>();
+  }
 
   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 {
+  template <bool Inversed> 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>;
+    using Tag = std::integral_constant<bool, Inversed>;
 
     // 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;
+      if (!BUI)
+        return Get(N, Tag());
+      return BUI->PreViewCFG.template getChildren<Inversed>(N);
     }
   };
 
   NodePtr getIDom(NodePtr BB) const {
     auto InfoIt = NodeToInfo.find(BB);
     if (InfoIt == NodeToInfo.end()) return nullptr;
 
     return InfoIt->second.IDom;
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<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;
         }
 
         if (!Condition(BB, Succ)) continue;
 
         // It's fine to add Succ to the map, because we know that it will be
         // visited later.
         auto &SuccInfo = NodeToInfo[Succ];
         WorkList.push_back(Succ);
         SuccInfo.Parent = LastNum;
         SuccInfo.ReverseChildren.push_back(BB);
       }
struct SemiNCAInfo {
 
   // 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");
     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, 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));
#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");
-    for (const NodePtr Pred :
-         ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
+    auto TNB = TN->getBlock();
+    for (const NodePtr Pred : ChildrenGetter<!IsPostDom>::Get(TNB, BUI)) {
       LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
       if (!DT.getNode(Pred)) continue;
 
-      const NodePtr Support =
-          DT.findNearestCommonDominator(TN->getBlock(), Pred);
+      const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
       LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
-      if (Support != TN->getBlock()) {
+      if (Support != TNB) {
         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, ArrayRef<UpdateT> Updates) {
-    const size_t NumUpdates = Updates.size();
+  static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG) {
+    const size_t NumUpdates = PreViewCFG.getNumLegalizedUpdates();
     if (NumUpdates == 0)
       return;
 
     // Take the fast path for a single update and avoid running the batch update
     // machinery.
     if (NumUpdates == 1) {
-      const auto &Update = Updates.front();
+      UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates();
       if (Update.getKind() == UpdateKind::Insert)
-        DT.insertEdge(Update.getFrom(), Update.getTo());
+        InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
       else
-        DT.deleteEdge(Update.getFrom(), Update.getTo());
-
+        DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
       return;
     }
 
-    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
-
+    BatchUpdateInfo BUI(PreViewCFG);
     // 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 (NumLegalized > DT.DomTreeNodes.size())
+      if (BUI.NumLegalized > DT.DomTreeNodes.size())
         CalculateFromScratch(DT, &BUI);
-    } else if (NumLegalized > DT.DomTreeNodes.size() / 40)
+    } else if (BUI.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 < NumLegalized && !BUI.IsRecalculated; ++i)
+    for (size_t i = 0; i < BUI.NumLegalized && !BUI.IsRecalculated; ++i)
       ApplyNextUpdate(DT, BUI);
   }
 
   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
-    assert(!BUI.Updates.empty() && "No updates to apply!");
-    UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
+    // Popping the next update, will move the PreViewCFG to the next snapshot.
+    UpdateT CurrentUpdate = BUI.PreViewCFG.popUpdateForIncrementalUpdates();
 #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) {
-  // 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()});
-  }
-
+  // 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);
   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,
-                  ArrayRef<typename DomTreeT::UpdateType> Updates) {
-  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
+                  GraphDiff<typename DomTreeT::NodePtr,
+                            DomTreeT::IsPostDominator> &PreViewCFG) {
+  SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, PreViewCFG);
 }
 
 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::BBUpdates);
+    DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBDomTreeGraphDiff &);
 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
-    DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
+    DomTreeBuilder::BBPostDomTree &DT,
+    DomTreeBuilder::BBPostDomTreeGraphDiff &);
 
 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);