DomTree: Extract (mostly) read-only logic into type-erased base classes

[nhaehnle]

Summary

Avoid having to instantiate and compile a subset of the dominator tree logic
separately for each node type. More importantly, this allows generic
algorithms to be built on top of dominator trees without writing them as
templates -- such algorithms can now use opaque CfgBlockRef and
CfgInterface instead.

A type-erased implementation of dominator trees could be written in
terms of CfgInterface as well, but doing so would change the current
trade-off: it would slightly reduce code size at the cost of a slight
runtime overhead.

This patch does not change the trade-off, as it only does type-erasure
where basic blocks can be treated in a fully opaque way, i.e. it only
moves methods that don't require iteration over CFG successors and
predecessors.

Change-Id: Ib860dc04cf8bb093d8ed00be7def40d662213672

[arsenm]

llvm/include/llvm/Support/GenericDomTree.h

82–83

Iterating over "generic" seems like a strange naming choice? The generic_children range is a bit better, but this should probably match

[nhaehnle]

• rename generic_{begin,end,children} back without the generic_ prefix and refer explictly to base class methods in NewGVN, which wants to mutate the order of dominator tree node children directly

[nhaehnle]

llvm/include/llvm/Support/GenericDomTree.h

82–83

Okay, so the reason why I originally did this was that NewGVN wants to change the order of children (for what seems like dubious reasons, but I didn't want to touch *that* too), and providing non-const iteration from DomTreeNodeBase<T> is problematic. A cleaner way is to have NewGVN explicitly refer to the base class begin/end methods.

[kuhar]

Overall, this seems like a good idea to me. The amount of templated code started growing out of hand some time ago, to the point where it's really hard to make logically changes, especially in the generic updater code.

This part of the code is *very* performance sensitive and definitely needs benchmarking before moving forward. Have you tried doing some performance evaluation on this change? I suggest compiling a few mid to large size programs (e.g., sqlite, webassembly, opt, clang, rippled) and compiling them into whole-program bitcode, and then running opt -O3 on this bitcode. This is pretty easy with gllvm; I can dig up my old instruction if that would help.

Nit: please fix the linter warnings.

[nhaehnle]

In D83089#2134858, @kuhar wrote:

This part of the code is *very* performance sensitive and definitely needs benchmarking before moving forward. Have you tried doing some performance evaluation on this change? I suggest compiling a few mid to large size programs (e.g., sqlite, webassembly, opt, clang, rippled) and compiling them into whole-program bitcode, and then running opt -O3 on this bitcode. This is pretty easy with gllvm; I can dig up my old instruction if that would help.

I've done this now: used gllvm to extract bitcode of Z3, then run perf stat opt -O3 z3.bc -o z3.out.bc. 3 runs on both my branch and the underlying master:

Underlying master:
 1.441.691.613.522      cycles:u                  #    3,948 GHz                      (83,34%)
 1.511.470.542.186      instructions:u            #    1,05  insn per cycle
 1.445.040.063.358      cycles:u                  #    3,832 GHz                      (83,33%)
 1.511.151.342.715      instructions:u            #    1,05  insn per cycle
 1.445.488.489.379      cycles:u                  #    3,851 GHz                      (83,34%)
 1.510.528.339.517      instructions:u            #    1,04  insn per cycle

My branch:
 1.447.208.247.196      cycles:u                  #    3,920 GHz                      (83,33%)
 1.506.361.797.982      instructions:u            #    1,04  insn per cycle
 1.451.415.961.317      cycles:u                  #    3,913 GHz                      (83,33%)
 1.505.605.385.713      instructions:u            #    1,04  insn per cycle
 1.445.005.341.369      cycles:u                  #    3,908 GHz                      (83,33%)
 1.506.364.033.713      instructions:u            #    1,04  insn per cycle

So the results are a bit unintuitive: lower number of instructions overall on my branch, slightly higher average number of cycles.

[kuhar]

Thanks for checking this. I dug up some old whole-program bitcode and uploaded it here in case it helps with future code reviews: https://drive.google.com/drive/folders/1VJpym19cW-8BVgdtl2MsD3zB4CoEQ93O?usp=sharing

I did a quick experiment I run the trunk and your patch on a few binaries from each project and got the number below. I only set the performance governor to performance but didn't do anything fancy to fix the clocks, disable SMT, or any core pinning. My machine has two Xeon 6154 Skylake CPUs.

	Branch	Avg. [s]	Std	Run 1 [s]	Run 2 [s]	Run 3 [s]	Run 4 [s]	Run 5 [s]	Delta [%]
sqlite3.bc	trunk	15.922	0.1011	15.82	15.82	15.98	15.94	16.05
	nicolai	15.958	0.0522	15.97	16.03	15.97	15.93	15.89	0.23%
llvm-as.bc	trunk	207.868	2.7855	209.82	210.73	206.72	203.69	208.38
	nicolai	207.01	1.7279	209.37	205.98	207.75	207.12	204.83	-0.41%
wasm-as.bc	trunk	43.596	0.2885	43.08	43.73	43.72	43.72	43.73
	nicolai	43.696	0.1689	43.82	43.49	43.91	43.66	43.6	0.23%
wasm-opt.bc	trunk	46.956	0.1383	47.06	47.14	46.91	46.82	46.85
	nicolai	46.998	0.4558	46.46	46.59	47.29	47.13	47.52	0.09%

Seems performance-neutral to me.

[nhaehnle]

v6:
- style change: iDom -> idom; it's arguable whether this is really
  invalid, since it is actually standard camelCase, but clang-tidy
  complains about it so... *shrug*
- rename {to,from}Generic -> {wrap,unwrap}Ref

[nhaehnle]

v9:

• rebase on factored-out Handle infrastructure

[sameerds]

Not sure what the recent interest is, in this review. Is there new work that will benefit from the effort in getting this through?

[arsenm]

In D83089#3933146, @sameerds wrote:

Not sure what the recent interest is, in this review. Is there new work that will benefit from the effort in getting this through?

I thought you had something else to replace this already. I'm looking to clean up the hundreds of open reviews I'm subscribed to

[sameerds]

I am okay with abandoning this.

llvm/include/llvm/CodeGen/MachineDominators.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
 #define LLVM_CODEGEN_MACHINEDOMINATORS_H
 
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineCfgTraits.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/GenericDomTree.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
 #include <cassert>
 #include <memory>
 #include <vector>
 

llvm/include/llvm/Support/GenericDomTree.h

 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// This file defines a set of templates that efficiently compute a dominator
 /// tree over a generic graph. This is used typically in LLVM for fast
 /// dominance queries on the CFG, but is fully generic w.r.t. the underlying
 /// graph types.
 ///
 /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements
-/// on the graph's NodeRef. The NodeRef should be a pointer and,
-/// NodeRef->getParent() must return the parent node that is also a pointer.
+/// on the graph's NodeRef:
+///  * The NodeRef should be a pointer.
+///  * NodeRef->getParent() must return the parent node that is also a pointer.
+///  * CfgTraitsFor<NodeType> must be implemented, though a partial
+///    implementation without the "value" parts of CfgTraits is sufficient.
 ///
-/// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
+/// FIXME: Should GenericDomTree be implemented entirely in terms of CfgTraits?
 ///
 //===----------------------------------------------------------------------===//
 
 #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/CFGUpdate.h"
+#include "llvm/Support/CfgTraits.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
+class GenericDominatorTreeBase;
+
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase;
 
 namespace DomTreeBuilder {
 template <typename DomTreeT>
 struct SemiNCAInfo;
 }  // namespace DomTreeBuilder
 
-/// Base class for the actual dominator tree node.
-template <class NodeT> class DomTreeNodeBase {
-  friend class PostDominatorTree;
-  friend class DominatorTreeBase<NodeT, false>;
-  friend class DominatorTreeBase<NodeT, true>;
-  friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
-  friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
+/// Type-erased base class for dominator tree nodes. Can be used for generic
+/// read-only queries on a dominator tree.
+class GenericDomTreeNodeBase {
+  friend GenericDominatorTreeBase;
+  template <typename NodeT, bool IsPostDom> friend class DominatorTreeBase;
+  template <typename DomTreeT> friend struct DomTreeBuilder::SemiNCAInfo;
 
-  NodeT *TheBB;
-  DomTreeNodeBase *IDom;
+protected:
+  CfgBlockRef TheBB;
+  GenericDomTreeNodeBase *IDom;
   unsigned Level;
-  std::vector<DomTreeNodeBase *> Children;
+  std::vector<GenericDomTreeNodeBase *> Children;
   mutable unsigned DFSNumIn = ~0;
   mutable unsigned DFSNumOut = ~0;
 
- public:
-  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
+  GenericDomTreeNodeBase(CfgBlockRef BB, GenericDomTreeNodeBase *iDom)
       : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
 
-  using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
+  using iterator = typename std::vector<GenericDomTreeNodeBase *>::iterator;
   using const_iterator =
-      typename std::vector<DomTreeNodeBase *>::const_iterator;
+      typename std::vector<GenericDomTreeNodeBase *>::const_iterator;
 
   iterator begin() { return Children.begin(); }
   iterator end() { return Children.end(); }
   const_iterator begin() const { return Children.begin(); }
   const_iterator end() const { return Children.end(); }
 
-  DomTreeNodeBase *const &back() const { return Children.back(); }
-  DomTreeNodeBase *&back() { return Children.back(); }
+  GenericDomTreeNodeBase *const &back() const { return Children.back(); }
 
   iterator_range<iterator> children() { return make_range(begin(), end()); }
   iterator_range<const_iterator> children() const {
     return make_range(begin(), end());
   }
 
-  NodeT *getBlock() const { return TheBB; }
-  DomTreeNodeBase *getIDom() const { return IDom; }
+  CfgBlockRef getBlock() const { return TheBB; }
+  GenericDomTreeNodeBase *getIDom() const { return IDom; }
   unsigned getLevel() const { return Level; }
 
-  std::unique_ptr<DomTreeNodeBase> addChild(
-      std::unique_ptr<DomTreeNodeBase> C) {
-    Children.push_back(C.get());
-    return C;
-  }
-
   bool isLeaf() const { return Children.empty(); }
   size_t getNumChildren() const { return Children.size(); }
 
   void clearAllChildren() { Children.clear(); }
 
-  bool compare(const DomTreeNodeBase *Other) const {
-    if (getNumChildren() != Other->getNumChildren())
-      return true;
-
-    if (Level != Other->Level) return true;
-
-    SmallPtrSet<const NodeT *, 4> OtherChildren;
-    for (const DomTreeNodeBase *I : *Other) {
-      const NodeT *Nd = I->getBlock();
-      OtherChildren.insert(Nd);
-    }
-
-    for (const DomTreeNodeBase *I : *this) {
-      const NodeT *N = I->getBlock();
-      if (OtherChildren.count(N) == 0)
-        return true;
-    }
-    return false;
-  }
-
-  void setIDom(DomTreeNodeBase *NewIDom) {
-    assert(IDom && "No immediate dominator?");
-    if (IDom == NewIDom) return;
-
-    auto I = find(IDom->Children, this);
-    assert(I != IDom->Children.end() &&
-           "Not in immediate dominator children set!");
-    // I am no longer your child...
-    IDom->Children.erase(I);
-
-    // Switch to new dominator
-    IDom = NewIDom;
-    IDom->Children.push_back(this);
-
-    UpdateLevel();
-  }
+  bool compare(const GenericDomTreeNodeBase *Other) const;
+  void setIDom(GenericDomTreeNodeBase *NewIDom);
 
   /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
   /// in the dominator tree. They are only guaranteed valid if
   /// updateDFSNumbers() has been called.
   unsigned getDFSNumIn() const { return DFSNumIn; }
   unsigned getDFSNumOut() const { return DFSNumOut; }
 
+  std::unique_ptr<GenericDomTreeNodeBase>
+  addChild(std::unique_ptr<GenericDomTreeNodeBase> C) {
+    Children.push_back(C.get());
+    return C;
+  }
+
 private:
   // Return true if this node is dominated by other. Use this only if DFS info
   // is valid.
-  bool DominatedBy(const DomTreeNodeBase *other) const {
+  bool DominatedBy(const GenericDomTreeNodeBase *other) const {
     return this->DFSNumIn >= other->DFSNumIn &&
            this->DFSNumOut <= other->DFSNumOut;
   }
 
-  void UpdateLevel() {
-    assert(IDom);
-    if (Level == IDom->Level + 1) return;
-
-    SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
-
-    while (!WorkStack.empty()) {
-      DomTreeNodeBase *Current = WorkStack.pop_back_val();
-      Current->Level = Current->IDom->Level + 1;
-
-      for (DomTreeNodeBase *C : *Current) {
-        assert(C->IDom);
-        if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
-      }
-    }
+  void UpdateLevel();
+};
+
+/// Base class for the actual dominator tree node.
+template <class NodeT> class DomTreeNodeBase : public GenericDomTreeNodeBase {
+  using CfgTraits = typename CfgTraitsFor<NodeT>::CfgTraits;
+
+  friend class PostDominatorTree;
+  friend class DominatorTreeBase<NodeT, false>;
+  friend class DominatorTreeBase<NodeT, true>;
+  friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
+  friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
+
+public:
+  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *IDom)
+      : GenericDomTreeNodeBase(CfgTraits::toGeneric(BB), IDom) {}
+
+  struct const_iterator;
+
+  using const_iterator_base = iterator_adaptor_base<
+      const_iterator, GenericDomTreeNodeBase::const_iterator,
+      typename std::iterator_traits<
+          GenericDomTreeNodeBase::const_iterator>::iterator_category,
+      // value_type
+      DomTreeNodeBase *,
+      typename std::iterator_traits<
+          GenericDomTreeNodeBase::const_iterator>::difference_type,
+      // pointer (not really usable, but we need to put something here)
+      DomTreeNodeBase *const *,
+      // reference (not a true reference, because operator* doesn't return one)
+      DomTreeNodeBase *>;
+
+  struct const_iterator : const_iterator_base {
+    const_iterator() = default;
+    explicit const_iterator(GenericDomTreeNodeBase::const_iterator it)
+        : const_iterator_base(it) {}
+
+    auto operator*() const { return static_cast<DomTreeNodeBase *>(*this->I); }
+  };
+
+  auto begin() const { return const_iterator{GenericDomTreeNodeBase::begin()}; }
+  auto end() const { return const_iterator{GenericDomTreeNodeBase::end()}; }
+
+  DomTreeNodeBase *back() const {
+    return static_cast<DomTreeNodeBase *>(Children.back());
+
+  iterator_range<const_iterator> children() const {
+    return make_range(begin(), end());
+
+  NodeT *getBlock() const { return CfgTraits::fromGeneric(TheBB); }
+  DomTreeNodeBase *getIDom() const {
+    return static_cast<DomTreeNodeBase *>(IDom);
   }
 };
 
 template <class NodeT>
 raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
   if (Node->getBlock())
     Node->getBlock()->printAsOperand(O, false);
   else
     O << " <<exit node>>";
 
   O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
     << Node->getLevel() << "]\n";
 
   return O;
 }
 
 template <class NodeT>
 void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
                   unsigned Lev) {
   O.indent(2 * Lev) << "[" << Lev << "] " << N;
-  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
-                                                       E = N->end();
-       I != E; ++I)
-    PrintDomTree<NodeT>(*I, O, Lev + 1);
+  for (const DomTreeNodeBase<NodeT> *Child : N->children())
+    PrintDomTree<NodeT>(Child, 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 <typename DomTreeT>

 template <typename DomTreeT>
 void ApplyUpdates(DomTreeT &DT,
                   ArrayRef<typename DomTreeT::UpdateType> Updates);
 
 template <typename DomTreeT>
 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
+/// Type-erased dominator tree base class.
+///
+/// This base class of all dominator trees can be used for read-only queries
+/// on a dominator tree.
+class GenericDominatorTreeBase {
+protected:
+  DenseMap<CfgBlockRef, std::unique_ptr<GenericDomTreeNodeBase>> DomTreeNodes;
+  GenericDomTreeNodeBase *RootNode = nullptr;
+
+  mutable bool DFSInfoValid = false;
+  mutable unsigned int SlowQueries = 0;
+
+  // Disallow copying
+  GenericDominatorTreeBase(const GenericDominatorTreeBase &) = delete;
+  GenericDominatorTreeBase &
+  operator=(const GenericDominatorTreeBase &) = delete;
+
+public:
+  GenericDominatorTreeBase() {}
+
+  GenericDominatorTreeBase(GenericDominatorTreeBase &&Arg)
+      : DomTreeNodes(std::move(Arg.DomTreeNodes)), RootNode(Arg.RootNode),
+        DFSInfoValid(Arg.DFSInfoValid), SlowQueries(Arg.SlowQueries) {
+    Arg.wipe();
+  }
+
+  GenericDominatorTreeBase &operator=(GenericDominatorTreeBase &&RHS) {
+    DomTreeNodes = std::move(RHS.DomTreeNodes);
+    RootNode = RHS.RootNode;
+    DFSInfoValid = RHS.DFSInfoValid;
+    SlowQueries = RHS.SlowQueries;
+    RHS.wipe();
+    return *this;
+  }
+
+  void reset();
+
+  bool compare(const GenericDominatorTreeBase &Other) const;
+
+  /// getNode - return the (Post)DominatorTree node for the specified basic
+  /// block.  This is the same as using operator[] on this class.  The result
+  /// may (but is not required to) be null for a forward (backwards)
+  /// statically unreachable block.
+  GenericDomTreeNodeBase *getNode(CfgBlockRef BB) const {
+    auto I = DomTreeNodes.find(BB);
+    if (I != DomTreeNodes.end())
+      return I->second.get();
+    return nullptr;
+  }
+
+  /// See getNode.
+  GenericDomTreeNodeBase *operator[](CfgBlockRef BB) const {
+    return getNode(BB);
+  }
+
+  /// getRootNode - This returns the entry node for the CFG of the function.  If
+  /// this tree represents the post-dominance relations for a function, however,
+  /// this root may be a node with the block == NULL.  This is the case when
+  /// there are multiple exit nodes from a particular function.  Consumers of
+  /// post-dominance information must be capable of dealing with this
+  /// possibility.
+  GenericDomTreeNodeBase *getRootNode() { return RootNode; }
+  const GenericDomTreeNodeBase *getRootNode() const { return RootNode; }
+
+  bool isReachableFromEntry(const GenericDomTreeNodeBase *A) const { return A; }
+
+  bool properlyDominates(const GenericDomTreeNodeBase *A,
+                         const GenericDomTreeNodeBase *B) const;
+  bool properlyDominatesBlock(CfgBlockRef A, CfgBlockRef B) const;
+
+  bool dominates(const GenericDomTreeNodeBase *A,
+                 const GenericDomTreeNodeBase *B) const;
+  bool dominatesBlock(CfgBlockRef A, CfgBlockRef B) const;
+
+  const GenericDomTreeNodeBase *
+  findNearestCommonDominator(const GenericDomTreeNodeBase *A,
+                             const GenericDomTreeNodeBase *B) const;
+  CfgBlockRef findNearestCommonDominatorBlock(CfgBlockRef A,
+                                              CfgBlockRef B) const;
+
+  void updateDFSNumbers() const;
+
+private:
+  /// Wipe this tree's state without releasing any resources.
+  ///
+  /// This is essentially a post-move helper only. It leaves the object in an
+  /// assignable and destroyable state, but otherwise invalid.
+  void wipe() {
+    DomTreeNodes.clear();
+    RootNode = nullptr;
+  }
+
+  bool dominatedBySlowTreeWalk(const GenericDomTreeNodeBase *A,
+                               const GenericDomTreeNodeBase *B) const;
+};
+
 /// 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:
+class DominatorTreeBase : public GenericDominatorTreeBase {
+  using CfgTraits = typename CfgTraitsFor<NodeT>::CfgTraits;
+
   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 = std::remove_pointer_t<ParentPtr>;
   static constexpr bool IsPostDominator = IsPostDom;
 
   using UpdateType = cfg::Update<NodePtr>;
   using UpdateKind = cfg::UpdateKind;
   static constexpr UpdateKind Insert = UpdateKind::Insert;
   static constexpr UpdateKind Delete = UpdateKind::Delete;
 
   enum class VerificationLevel { Fast, Basic, Full };
 
 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 = nullptr;
   ParentPtr Parent = nullptr;
 
-  mutable bool DFSInfoValid = false;
-  mutable unsigned int SlowQueries = 0;
-
   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
 
- public:
   DominatorTreeBase() {}
 
-  DominatorTreeBase(DominatorTreeBase &&Arg)
-      : Roots(std::move(Arg.Roots)),
-        DomTreeNodes(std::move(Arg.DomTreeNodes)),
-        RootNode(Arg.RootNode),
-        Parent(Arg.Parent),
-        DFSInfoValid(Arg.DFSInfoValid),
-        SlowQueries(Arg.SlowQueries) {
-    Arg.wipe();
-  }
-
-  DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
-    Roots = std::move(RHS.Roots);
-    DomTreeNodes = std::move(RHS.DomTreeNodes);
-    RootNode = RHS.RootNode;
-    Parent = RHS.Parent;
-    DFSInfoValid = RHS.DFSInfoValid;
-    SlowQueries = RHS.SlowQueries;
-    RHS.wipe();
-    return *this;
-  }
-
-  DominatorTreeBase(const DominatorTreeBase &) = delete;
-  DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
-
   /// Iteration over roots.
   ///
   /// This may include multiple blocks if we are computing post dominators.
   /// For forward dominators, this will always be a single block (the entry
   /// block).
   using root_iterator = typename SmallVectorImpl<NodeT *>::iterator;
   using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator;
 
bool compare(const DominatorTreeBase &Other) const {
     if (Parent != Other.Parent) return true;
 
     if (Roots.size() != Other.Roots.size())
       return true;
 
     if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
       return true;
 
-    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
-    if (DomTreeNodes.size() != OtherDomTreeNodes.size())
-      return true;
-
-    for (const auto &DomTreeNode : DomTreeNodes) {
-      NodeT *BB = DomTreeNode.first;
-      typename DomTreeNodeMapType::const_iterator OI =
-          OtherDomTreeNodes.find(BB);
-      if (OI == OtherDomTreeNodes.end())
-        return true;
-
-      DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
-      DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
-
-      if (MyNd.compare(&OtherNd))
-        return true;
-    }
-
-    return false;
+    return GenericDominatorTreeBase::compare(Other);
   }
 
   /// getNode - return the (Post)DominatorTree node for the specified basic
   /// block.  This is the same as using operator[] on this class.  The result
   /// may (but is not required to) be null for a forward (backwards)
   /// statically unreachable block.
   DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
-    auto I = DomTreeNodes.find(BB);
-    if (I != DomTreeNodes.end())
-      return I->second.get();
-    return nullptr;
+    return static_cast<DomTreeNodeBase<NodeT> *>(
+        GenericDominatorTreeBase::getNode(
+            CfgTraits::toGeneric(const_cast<NodeT *>(BB))));
   }
 
   /// See getNode.
   DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
     return getNode(BB);
   }
 
   /// getRootNode - This returns the entry node for the CFG of the function.  If
   /// this tree represents the post-dominance relations for a function, however,
   /// this root may be a node with the block == NULL.  This is the case when
   /// there are multiple exit nodes from a particular function.  Consumers of
   /// post-dominance information must be capable of dealing with this
   /// possibility.
   ///
-  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
-  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
+  DomTreeNodeBase<NodeT> *getRootNode() {
+    return static_cast<DomTreeNodeBase<NodeT> *>(RootNode);
+  }
+  const DomTreeNodeBase<NodeT> *getRootNode() const {
+    return static_cast<const DomTreeNodeBase<NodeT> *>(RootNode);
+  }
 
   /// Get all nodes dominated by R, including R itself.
   void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
     Result.clear();
     const DomTreeNodeBase<NodeT> *RN = getNode(R);
     if (!RN)
       return; // If R is unreachable, it will not be present in the DOM tree.
     SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
     WL.push_back(RN);
 
     while (!WL.empty()) {
       const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
       Result.push_back(N->getBlock());
       WL.append(N->begin(), N->end());
     }
   }
 
-  /// properlyDominates - Returns true iff A dominates B and A != B.
-  /// Note that this is not a constant time operation!
-  ///
   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
                          const DomTreeNodeBase<NodeT> *B) const {
-    if (!A || !B)
-      return false;
+    return GenericDominatorTreeBase::properlyDominates(A, B);
+  }
+  bool properlyDominates(const NodeT *A, const NodeT *B) const {
     if (A == B)
       return false;
-    return dominates(A, B);
+    return GenericDominatorTreeBase::dominates(getNode(A), getNode(B));
   }
 
-  bool properlyDominates(const NodeT *A, const NodeT *B) const;
-
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
   bool isReachableFromEntry(const NodeT *A) const {
     assert(!this->isPostDominator() &&
            "This is not implemented for post dominators");
-    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
+    return getNode(const_cast<NodeT *>(A)) != nullptr;
+  }
+  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const {
+    return A != nullptr;
   }
 
-  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
-
-  /// dominates - Returns true iff A dominates B.  Note that this is not a
-  /// constant time operation!
-  ///
   bool dominates(const DomTreeNodeBase<NodeT> *A,
                  const DomTreeNodeBase<NodeT> *B) const {
-    // A node trivially dominates itself.
-    if (B == A)
-      return true;
-
-    // An unreachable node is dominated by anything.
-    if (!isReachableFromEntry(B))
-      return true;
-
-    // And dominates nothing.
-    if (!isReachableFromEntry(A))
-      return false;
-
-    if (B->getIDom() == A) return true;
-
-    if (A->getIDom() == B) return false;
-
-    // A can only dominate B if it is higher in the tree.
-    if (A->getLevel() >= B->getLevel()) return false;
-
-    // Compare the result of the tree walk and the dfs numbers, if expensive
-    // checks are enabled.
-#ifdef EXPENSIVE_CHECKS
-    assert((!DFSInfoValid ||
-            (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
-           "Tree walk disagrees with dfs numbers!");
-#endif
-
-    if (DFSInfoValid)
-      return B->DominatedBy(A);
-
-    // If we end up with too many slow queries, just update the
-    // DFS numbers on the theory that we are going to keep querying.
-    SlowQueries++;
-    if (SlowQueries > 32) {
-      updateDFSNumbers();
-      return B->DominatedBy(A);
-    }
-
-    return dominatedBySlowTreeWalk(A, B);
+    return GenericDominatorTreeBase::dominates(A, B);
+  bool dominates(const NodeT *A, const NodeT *B) const {
+    if (A == B)
+      return true;
+    return GenericDominatorTreeBase::dominates(getNode(A), getNode(B));
   }
 
-  bool dominates(const NodeT *A, const NodeT *B) const;
-
   NodeT *getRoot() const {
     assert(this->Roots.size() == 1 && "Should always have entry node!");
     return this->Roots[0];
   }
 
-  /// findNearestCommonDominator - Find nearest common dominator basic block
-  /// for basic block A and B. If there is no such block then return nullptr.
-  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
-    assert(A && B && "Pointers are not valid");
-    assert(A->getParent() == B->getParent() &&
-           "Two blocks are not in same function");
-
-    // If either A or B is a entry block then it is nearest common dominator
-    // (for forward-dominators).
-    if (!isPostDominator()) {
-      NodeT &Entry = A->getParent()->front();
-      if (A == &Entry || B == &Entry)
-        return &Entry;
-    }
-
-    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
-    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
-
-    if (!NodeA || !NodeB) return nullptr;
-
-    // Use level information to go up the tree until the levels match. Then
-    // continue going up til we arrive at the same node.
-    while (NodeA && NodeA != NodeB) {
-      if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
-
-      NodeA = NodeA->IDom;
-    }
+  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
+    return isPostDominator() && !A->getBlock();
 
-    return NodeA ? NodeA->getBlock() : nullptr;
+  const DomTreeNodeBase<NodeT> *
+  findNearestCommonDominator(const DomTreeNodeBase<NodeT> *A,
+                             const DomTreeNodeBase<NodeT> *B) const {
+    return static_cast<const DomTreeNodeBase<NodeT> *>(
+        GenericDominatorTreeBase::findNearestCommonDominator(A, B));
   }
-
   const NodeT *findNearestCommonDominator(const NodeT *A,
                                           const NodeT *B) const {
-    // Cast away the const qualifiers here. This is ok since
-    // const is re-introduced on the return type.
-    return findNearestCommonDominator(const_cast<NodeT *>(A),
-                                      const_cast<NodeT *>(B));
+    assert(A && B && "Pointers are not valid");
+    const DomTreeNodeBase<NodeT> *dom =
+        static_cast<const DomTreeNodeBase<NodeT> *>(
+            GenericDominatorTreeBase::findNearestCommonDominator(getNode(A),
+                                                                 getNode(B)));
+    return dom->getBlock();
   }
-
-  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
-    return isPostDominator() && !A->getBlock();
+  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
+    assert(A && B && "Pointers are not valid");
+    const DomTreeNodeBase<NodeT> *dom =
+        static_cast<const DomTreeNodeBase<NodeT> *>(
+            GenericDominatorTreeBase::findNearestCommonDominator(getNode(A),
+                                                                 getNode(B)));
+    return dom->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.
assert(!this->isPostDominator() &&
            "Cannot change root of post-dominator tree");
     DFSInfoValid = false;
     DomTreeNodeBase<NodeT> *NewNode = createNode(BB);
     if (Roots.empty()) {
       addRoot(BB);
     } else {
       assert(Roots.size() == 1);
       NodeT *OldRoot = Roots.front();
-      auto &OldNode = DomTreeNodes[OldRoot];
-      OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
+      auto &OldNode = DomTreeNodes[CfgTraits::toGeneric(OldRoot)];
+      OldNode = NewNode->addChild(std::move(OldNode));
       OldNode->IDom = NewNode;
       OldNode->UpdateLevel();
       Roots[0] = BB;
     }
-    return RootNode = NewNode;
+    RootNode = NewNode;
+    return static_cast<DomTreeNodeBase<NodeT> *>(RootNode);
   }
 
   /// changeImmediateDominator - This method is used to update the dominator
   /// tree information when a node's immediate dominator changes.
   ///
   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
                                 DomTreeNodeBase<NodeT> *NewIDom) {
     assert(N && NewIDom && "Cannot change null node pointers!");
void eraseNode(NodeT *BB) {
     if (IDom) {
       const auto I = find(IDom->Children, Node);
       assert(I != IDom->Children.end() &&
              "Not in immediate dominator children set!");
       // I am no longer your child...
       IDom->Children.erase(I);
     }
 
-    DomTreeNodes.erase(BB);
+    DomTreeNodes.erase(CfgTraits::toGeneric(BB));
 
     if (!IsPostDom) return;
 
     // Remember to update PostDominatorTree roots.
     auto RIt = llvm::find(Roots, BB);
     if (RIt != Roots.end()) {
       std::swap(*RIt, Roots.back());
       Roots.pop_back();
void print(raw_ostream &O) const {
     for (const NodePtr Block : Roots) {
       Block->printAsOperand(O, false);
       O << " ";
     }
     O << "\n";
   }
 
 public:
-  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
-  /// dominator tree in dfs order.
-  void updateDFSNumbers() const {
-    if (DFSInfoValid) {
-      SlowQueries = 0;
-      return;
-    }
-
-    SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
-                          typename DomTreeNodeBase<NodeT>::const_iterator>,
-                32> WorkStack;
-
-    const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
-    assert((!Parent || ThisRoot) && "Empty constructed DomTree");
-    if (!ThisRoot)
-      return;
-
-    // Both dominators and postdominators have a single root node. In the case
-    // case of PostDominatorTree, this node is a virtual root.
-    WorkStack.push_back({ThisRoot, ThisRoot->begin()});
-
-    unsigned DFSNum = 0;
-    ThisRoot->DFSNumIn = DFSNum++;
-
-    while (!WorkStack.empty()) {
-      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
-      const auto ChildIt = WorkStack.back().second;
-
-      // If we visited all of the children of this node, "recurse" back up the
-      // stack setting the DFOutNum.
-      if (ChildIt == Node->end()) {
-        Node->DFSNumOut = DFSNum++;
-        WorkStack.pop_back();
-      } else {
-        // Otherwise, recursively visit this child.
-        const DomTreeNodeBase<NodeT> *Child = *ChildIt;
-        ++WorkStack.back().second;
-
-        WorkStack.push_back({Child, Child->begin()});
-        Child->DFSNumIn = DFSNum++;
-      }
-    }
-
-    SlowQueries = 0;
-    DFSInfoValid = true;
-  }
-
   /// recalculate - compute a dominator tree for the given function
   void recalculate(ParentType &Func) {
     Parent = &Func;
     DomTreeBuilder::Calculate(*this);
   }
 
   void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
     Parent = &Func;
public:
   ///             constructed tree.
   ///             Takes O(N^2) time worst case, but is faster in practise (same
   ///             as tree construction).
   bool verify(VerificationLevel VL = VerificationLevel::Full) const {
     return DomTreeBuilder::Verify(*this, VL);
   }
 
   void reset() {
-    DomTreeNodes.clear();
+    GenericDominatorTreeBase::reset();
     Roots.clear();
-    RootNode = nullptr;
     Parent = nullptr;
-    DFSInfoValid = false;
-    SlowQueries = 0;
   }
 
 protected:
   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
 
   DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) {
-    return (DomTreeNodes[BB] = IDom->addChild(
-                std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom)))
-        .get();
+    CfgBlockRef bbRef = CfgTraits::toGeneric(BB);
+    return static_cast<DomTreeNodeBase<NodeT> *>(
+        (DomTreeNodes[bbRef] = IDom->addChild(
+             std::make_unique<GenericDomTreeNodeBase>(bbRef, IDom)))
+            .get());
   }
 
   DomTreeNodeBase<NodeT> *createNode(NodeT *BB) {
-    return (DomTreeNodes[BB] =
-                std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr))
-        .get();
+    CfgBlockRef bbRef = CfgTraits::toGeneric(BB);
+    return static_cast<DomTreeNodeBase<NodeT> *>(
+        (DomTreeNodes[bbRef] =
+             std::make_unique<GenericDomTreeNodeBase>(bbRef, nullptr))
+            .get());
   }
 
   // NewBB is split and now it has one successor. Update dominator tree to
   // reflect this change.
   template <class N>
   void Split(typename GraphTraits<N>::NodeRef NewBB) {
     using GraphT = GraphTraits<N>;
     using NodeRef = typename GraphT::NodeRef;
void Split(typename GraphTraits<N>::NodeRef NewBB) {
 
     // If NewBB strictly dominates other blocks, then it is now the immediate
     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
     if (NewBBDominatesNewBBSucc) {
       DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
       changeImmediateDominator(NewBBSuccNode, NewBBNode);
     }
   }
-
- private:
-  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
-                               const DomTreeNodeBase<NodeT> *B) const {
-    assert(A != B);
-    assert(isReachableFromEntry(B));
-    assert(isReachableFromEntry(A));
-
-    const unsigned ALevel = A->getLevel();
-    const DomTreeNodeBase<NodeT> *IDom;
-
-    // Don't walk nodes above A's subtree. When we reach A's level, we must
-    // either find A or be in some other subtree not dominated by A.
-    while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
-      B = IDom;  // Walk up the tree
-
-    return B == A;
-  }
-
-  /// Wipe this tree's state without releasing any resources.
-  ///
-  /// This is essentially a post-move helper only. It leaves the object in an
-  /// assignable and destroyable state, but otherwise invalid.
-  void wipe() {
-    DomTreeNodes.clear();
-    RootNode = nullptr;
-    Parent = nullptr;
-  }
 };
 
 template <typename T>
 using DomTreeBase = DominatorTreeBase<T, false>;
 
 template <typename T>
 using PostDomTreeBase = DominatorTreeBase<T, true>;
 
-// These two functions are declared out of line as a workaround for building
-// with old (< r147295) versions of clang because of pr11642.
-template <typename NodeT, bool IsPostDom>
-bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
-                                                    const NodeT *B) const {
-  if (A == B)
-    return true;
-
-  // Cast away the const qualifiers here. This is ok since
-  // this function doesn't actually return the values returned
-  // from getNode.
-  return dominates(getNode(const_cast<NodeT *>(A)),
-                   getNode(const_cast<NodeT *>(B)));
-}
-template <typename NodeT, bool IsPostDom>
-bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
-    const NodeT *A, const NodeT *B) const {
-  if (A == B)
-    return false;
-
-  // Cast away the const qualifiers here. This is ok since
-  // this function doesn't actually return the values returned
-  // from getNode.
-  return dominates(getNode(const_cast<NodeT *>(A)),
-                   getNode(const_cast<NodeT *>(B)));
-}
-
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_GENERICDOMTREE_H

llvm/include/llvm/Support/GenericDomTreeConstruction.h

 
 #define DEBUG_TYPE "dom-tree-builder"
 
 namespace llvm {
 namespace DomTreeBuilder {
 
 template <typename DomTreeT>
 struct SemiNCAInfo {
+  using CfgTraits = typename DomTreeT::CfgTraits;
   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 {
struct SemiNCAInfo {
 
   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
     if (TreeNodePtr Node = DT.getNode(BB)) return Node;
 
     // Haven't calculated this node yet?  Get or calculate the node for the
     // immediate dominator.
     NodePtr IDom = getIDom(BB);
 
-    assert(IDom || DT.DomTreeNodes[nullptr]);
+    assert(IDom || DT.DomTreeNodes[CfgBlockRef{}]);
     TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
 
     // Add a new tree node for this NodeT, and link it as a child of
     // IDomNode
     return DT.createChild(BB, IDomNode);
   }
 
   static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
     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.createNode(Root);
-    SNCA.attachNewSubtree(DT, DT.RootNode);
+    SNCA.attachNewSubtree(DT, DT.getRootNode());
   }
 
   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];
 
       // Don't replace this with 'count', the insertion side effect is important
-      if (DT.DomTreeNodes[W]) continue;  // Haven't calculated this node yet?
+      if (DT.DomTreeNodes[CfgTraits::toGeneric(W)])
+        continue; // Haven't calculated this node yet?
 
       NodePtr ImmDom = getIDom(W);
 
       // Get or calculate the node for the immediate dominator.
       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
 
       // Add a new tree node for this BasicBlock, and link it as a child of
       // IDomNode.
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
     const TreeNodePtr IDom = TN->getIDom();
     assert(IDom);
 
     auto ChIt = llvm::find(IDom->Children, TN);
     assert(ChIt != IDom->Children.end());
     std::swap(*ChIt, IDom->Children.back());
     IDom->Children.pop_back();
 
-    DT.DomTreeNodes.erase(TN->getBlock());
+    DT.DomTreeNodes.erase(CfgTraits::toGeneric(TN->getBlock()));
   }
 
   //~~
   //===--------------------- DomTree Batch Updater --------------------------===
   //~~
 
   static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
     const size_t NumUpdates = Updates.size();
#endif
 
   // Checks if the tree contains all reachable nodes in the input graph.
   // Running time: O(N).
   bool verifyReachability(const DomTreeT &DT) {
     clear();
     doFullDFSWalk(DT, AlwaysDescend);
 
     for (auto &NodeToTN : DT.DomTreeNodes) {
-      const TreeNodePtr TN = NodeToTN.second.get();
+      const TreeNodePtr TN =
+          static_cast<const TreeNodePtr>(NodeToTN.second.get());
       const NodePtr BB = TN->getBlock();
 
       // Virtual root has a corresponding virtual CFG node.
       if (DT.isVirtualRoot(TN)) continue;
 
       if (NodeToInfo.count(BB) == 0) {
         errs() << "DomTree node " << BlockNamePrinter(BB)
                << " not found by DFS walk!\n";
bool verifyReachability(const DomTreeT &DT) {
     return true;
   }
 
   // Check if for every parent with a level L in the tree all of its children
   // have level L + 1.
   // Running time: O(N).
   static bool VerifyLevels(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
-      const TreeNodePtr TN = NodeToTN.second.get();
+      const TreeNodePtr TN =
+          static_cast<const TreeNodePtr>(NodeToTN.second.get());
       const NodePtr BB = TN->getBlock();
       if (!BB) continue;
 
       const TreeNodePtr IDom = TN->getIDom();
       if (!IDom && TN->getLevel() != 0) {
         errs() << "Node without an IDom " << BlockNamePrinter(BB)
                << " has a nonzero level " << TN->getLevel() << "!\n";
         errs().flush();
if (Root->getDFSNumIn() != 0) {
       errs() << '\n';
       errs().flush();
       return false;
     }
 
     // For each tree node verify if children's DFS numbers cover their parent's
     // DFS numbers with no gaps.
     for (const auto &NodeToTN : DT.DomTreeNodes) {
-      const TreeNodePtr Node = NodeToTN.second.get();
+      const TreeNodePtr Node =
+          static_cast<const TreeNodePtr>(NodeToTN.second.get());
 
       // Handle tree leaves.
       if (Node->isLeaf()) {
         if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
           errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
           PrintNodeAndDFSNums(Node);
           errs() << '\n';
           errs().flush();
#endif
   // the input graph, such that V is reachable, the parent of W in the tree is
   // an ancestor of V in the tree.
   // Running time: O(N^2).
   //
   // This means that if a node gets disconnected from the graph, then all of
   // the nodes it dominated previously will now become unreachable.
   bool verifyParentProperty(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
-      const TreeNodePtr TN = NodeToTN.second.get();
+      const TreeNodePtr TN =
+          static_cast<const TreeNodePtr>(NodeToTN.second.get());
       const NodePtr BB = TN->getBlock();
       if (!BB || TN->isLeaf())
         continue;
 
       LLVM_DEBUG(dbgs() << "Verifying parent property of node "
                         << BlockNamePrinter(TN) << "\n");
       clear();
       doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
#endif
   // Check if the tree has sibling property: if a node V does not dominate a
   // node W for all siblings V and W in the tree.
   // Running time: O(N^3).
   //
   // This means that if a node gets disconnected from the graph, then all of its
   // siblings will now still be reachable.
   bool verifySiblingProperty(const DomTreeT &DT) {
     for (auto &NodeToTN : DT.DomTreeNodes) {
-      const TreeNodePtr TN = NodeToTN.second.get();
+      const TreeNodePtr TN =
+          static_cast<const TreeNodePtr>(NodeToTN.second.get());
       const NodePtr BB = TN->getBlock();
       if (!BB || TN->isLeaf())
         continue;
 
       for (const TreeNodePtr N : TN->children()) {
         clear();
         NodePtr BBN = N->getBlock();
         doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {

llvm/lib/Support/CMakeLists.txt

add_llvm_component_library(LLVMSupport
   ExtensibleRTTI.cpp
   FileCheck.cpp
   FileCollector.cpp
   FileUtilities.cpp
   FileOutputBuffer.cpp
   FoldingSet.cpp
   FormattedStream.cpp
   FormatVariadic.cpp
+  GenericDomTree.cpp
   GlobPattern.cpp
   GraphWriter.cpp
   Hashing.cpp
   InitLLVM.cpp
   IntEqClasses.cpp
   IntervalMap.cpp
   ItaniumManglingCanonicalizer.cpp
   JSON.cpp

llvm/lib/Support/GenericDomTree.cpp

+//===- GenericDomTree.cpp - Generic dominator trees for graphs --*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/GenericDomTree.h"
+
+#include "llvm/ADT/SmallSet.h"
+
+using namespace llvm;
+
+bool GenericDomTreeNodeBase::compare(
+    const GenericDomTreeNodeBase *Other) const {
+  if (getNumChildren() != Other->getNumChildren())
+    return true;
+
+  if (Level != Other->Level)
+    return true;
+
+  SmallSet<CfgBlockRef, 4> OtherChildren;
+  for (const GenericDomTreeNodeBase *I : *Other) {
+    CfgBlockRef Nd = I->getBlock();
+    OtherChildren.insert(Nd);
+  }
+
+  for (const GenericDomTreeNodeBase *I : *this) {
+    CfgBlockRef N = I->getBlock();
+    if (OtherChildren.count(N) == 0)
+      return true;
+  }
+  return false;
+}
+
+void GenericDomTreeNodeBase::setIDom(GenericDomTreeNodeBase *NewIDom) {
+  assert(IDom && "No immediate dominator?");
+  if (IDom == NewIDom)
+    return;
+
+  auto I = find(IDom->Children, this);
+  assert(I != IDom->Children.end() &&
+         "Not in immediate dominator children set!");
+  // I am no longer your child...
+  IDom->Children.erase(I);
+
+  // Switch to new dominator
+  IDom = NewIDom;
+  IDom->Children.push_back(this);
+
+  UpdateLevel();
+}
+
+void GenericDomTreeNodeBase::UpdateLevel() {
+  assert(IDom);
+  if (Level == IDom->Level + 1)
+    return;
+
+  SmallVector<GenericDomTreeNodeBase *, 64> WorkStack = {this};
+
+  while (!WorkStack.empty()) {
+    GenericDomTreeNodeBase *Current = WorkStack.pop_back_val();
+    Current->Level = Current->IDom->Level + 1;
+
+    for (GenericDomTreeNodeBase *C : *Current) {
+      assert(C->IDom);
+      if (C->Level != C->IDom->Level + 1)
+        WorkStack.push_back(C);
+    }
+  }
+}
+
+/// compare - Return false if the other dominator tree base matches this
+/// dominator tree base. Otherwise return true.
+bool GenericDominatorTreeBase::compare(
+    const GenericDominatorTreeBase &Other) const {
+  if (DomTreeNodes.size() != Other.DomTreeNodes.size())
+    return true;
+
+  for (const auto &DomTreeNode : DomTreeNodes) {
+    CfgBlockRef BB = DomTreeNode.first;
+    auto OI = Other.DomTreeNodes.find(BB);
+    if (OI == Other.DomTreeNodes.end())
+      return true;
+
+    GenericDomTreeNodeBase &MyNd = *DomTreeNode.second;
+    GenericDomTreeNodeBase &OtherNd = *OI->second;
+
+    if (MyNd.compare(&OtherNd))
+      return true;
+  }
+
+  return false;
+}
+
+void GenericDominatorTreeBase::reset() {
+  DomTreeNodes.clear();
+  RootNode = nullptr;
+  DFSInfoValid = false;
+  SlowQueries = 0;
+}
+
+/// properlyDominates - Returns true iff A dominates B and A != B.
+/// Note that this is not a constant time operation!
+bool GenericDominatorTreeBase::properlyDominates(
+    const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const {
+  if (!A || !B)
+    return false;
+  if (A == B)
+    return false;
+  return dominates(A, B);
+}
+
+bool GenericDominatorTreeBase::properlyDominatesBlock(CfgBlockRef A,
+                                                      CfgBlockRef B) const {
+  if (A == B)
+    return false;
+
+  return dominates(getNode(A), getNode(B));
+}
+
+/// dominates - Returns true iff A dominates B.  Note that this is not a
+/// constant time operation!
+bool GenericDominatorTreeBase::dominates(
+    const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const {
+  // A node trivially dominates itself.
+  if (B == A)
+    return true;
+
+  // An unreachable node is dominated by anything.
+  if (!isReachableFromEntry(B))
+    return true;
+
+  // And dominates nothing.
+  if (!isReachableFromEntry(A))
+    return false;
+
+  if (B->getIDom() == A)
+    return true;
+
+  if (A->getIDom() == B)
+    return false;
+
+  // A can only dominate B if it is higher in the tree.
+  if (A->getLevel() >= B->getLevel())
+    return false;
+
+  // Compare the result of the tree walk and the dfs numbers, if expensive
+  // checks are enabled.
+#ifdef EXPENSIVE_CHECKS
+  assert(
+      (!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
+      "Tree walk disagrees with dfs numbers!");
+#endif
+
+  if (DFSInfoValid)
+    return B->DominatedBy(A);
+
+  // If we end up with too many slow queries, just update the
+  // DFS numbers on the theory that we are going to keep querying.
+  SlowQueries++;
+  if (SlowQueries > 32) {
+    updateDFSNumbers();
+    return B->DominatedBy(A);
+  }
+
+  return dominatedBySlowTreeWalk(A, B);
+}
+
+bool GenericDominatorTreeBase::dominatesBlock(CfgBlockRef A,
+                                              CfgBlockRef B) const {
+  if (A == B)
+    return true;
+
+  // Cast away the const qualifiers here. This is ok since
+  // this function doesn't actually return the values returned
+  // from getNode.
+  return dominates(getNode(A), getNode(B));
+}
+
+/// findNearestCommonDominator - Find nearest common dominator basic block
+/// for basic block A and B. If there is no such block then return nullptr.
+const GenericDomTreeNodeBase *
+GenericDominatorTreeBase::findNearestCommonDominator(
+    const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const {
+  if (A == RootNode || B == RootNode)
+    return RootNode;
+
+  if (!A || !B)
+    return nullptr;
+
+  // Use level information to go up the tree until the levels match. Then
+  // continue going up til we arrive at the same node.
+  while (A != B) {
+    if (A->getLevel() < B->getLevel())
+      std::swap(A, B);
+
+    A = A->IDom;
+    assert(A != nullptr && "nodes in different dominator trees?");
+  }
+
+  return A;
+}
+
+CfgBlockRef
+GenericDominatorTreeBase::findNearestCommonDominatorBlock(CfgBlockRef A,
+                                                          CfgBlockRef B) const {
+  assert(A && B && "Pointers are not valid");
+
+  const GenericDomTreeNodeBase *Dom =
+      findNearestCommonDominator(getNode(A), getNode(B));
+
+  return Dom ? Dom->getBlock() : CfgBlockRef();
+}
+
+/// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
+/// dominator tree in dfs order.
+void GenericDominatorTreeBase::updateDFSNumbers() const {
+  if (DFSInfoValid) {
+    SlowQueries = 0;
+    return;
+  }
+
+  SmallVector<std::pair<const GenericDomTreeNodeBase *,
+                        GenericDomTreeNodeBase::const_iterator>,
+              32>
+      WorkStack;
+
+  const GenericDomTreeNodeBase *ThisRoot = getRootNode();
+  if (!ThisRoot)
+    return;
+
+  // Both dominators and postdominators have a single root node. In the case
+  // case of PostDominatorTree, this node is a virtual root.
+  WorkStack.push_back({ThisRoot, ThisRoot->begin()});
+
+  unsigned DFSNum = 0;
+  ThisRoot->DFSNumIn = DFSNum++;
+
+  while (!WorkStack.empty()) {
+    const GenericDomTreeNodeBase *Node = WorkStack.back().first;
+    const auto ChildIt = WorkStack.back().second;
+
+    // If we visited all of the children of this node, "recurse" back up the
+    // stack setting the DFOutNum.
+    if (ChildIt == Node->end()) {
+      Node->DFSNumOut = DFSNum++;
+      WorkStack.pop_back();
+    } else {
+      // Otherwise, recursively visit this child.
+      const GenericDomTreeNodeBase *Child = *ChildIt;
+      ++WorkStack.back().second;
+
+      WorkStack.push_back({Child, Child->begin()});
+      Child->DFSNumIn = DFSNum++;
+    }
+  }
+
+  SlowQueries = 0;
+  DFSInfoValid = true;
+}
+
+bool GenericDominatorTreeBase::dominatedBySlowTreeWalk(
+    const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const {
+  assert(A != B);
+  assert(isReachableFromEntry(B));
+  assert(isReachableFromEntry(A));
+
+  const unsigned ALevel = A->getLevel();
+  const GenericDomTreeNodeBase *IDom;
+
+  // Don't walk nodes above A's subtree. When we reach A's level, we must
+  // either find A or be in some other subtree not dominated by A.
+  while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
+    B = IDom; // Walk up the tree
+
+  return B == A;
+}

llvm/lib/Transforms/Scalar/ADCE.cpp

for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) {
         }
     }
   }
 
   // Mark blocks live if there is no path from the block to a
   // return of the function.
   // We do this by seeing which of the postdomtree root children exit the
   // program, and for all others, mark the subtree live.
-  for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
+  for (auto *PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
     auto *BB = PDTChild->getBlock();
     auto &Info = BlockInfo[BB];
     // Real function return
     if (isa<ReturnInst>(Info.Terminator)) {
       LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()
                         << '\n';);
       continue;
     }

llvm/lib/Transforms/Scalar/NewGVN.cpp

class NewGVN {
   mutable ArrayRecycler<Value *> ArgRecycler;
   mutable TarjanSCC SCCFinder;
   const SimplifyQuery SQ;
 
   // Number of function arguments, used by ranking
   unsigned int NumFuncArgs = 0;
 
   // RPOOrdering of basic blocks
-  DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
+  DenseMap<const GenericDomTreeNodeBase *, unsigned> RPOOrdering;
 
   // Congruence class info.
 
   // This class is called INITIAL in the paper. It is the class everything
   // startsout in, and represents any value. Being an optimistic analysis,
   // anything in the TOP class has the value TOP, which is indeterminate and
   // equivalent to everything.
   CongruenceClass *TOPClass = nullptr;
for (auto &B : RPOT) {
     auto *Node = DT->getNode(B);
     assert(Node && "RPO and Dominator tree should have same reachability");
     RPOOrdering[Node] = ++Counter;
   }
   // Sort dominator tree children arrays into RPO.
   for (auto &B : RPOT) {
     auto *Node = DT->getNode(B);
     if (Node->getNumChildren() > 1)
-      llvm::sort(Node->begin(), Node->end(),
-                 [&](const DomTreeNode *A, const DomTreeNode *B) {
+      llvm::sort(Node->GenericDomTreeNodeBase::begin(),
+                 Node->GenericDomTreeNodeBase::end(),
+                 [&](const GenericDomTreeNodeBase *A,
+                     const GenericDomTreeNodeBase *B) {
                    return RPOOrdering[A] < RPOOrdering[B];
                  });
   }
 
   // Now a standard depth first ordering of the domtree is equivalent to RPO.
   for (auto DTN : depth_first(DT->getRootNode())) {
     BasicBlock *B = DTN->getBlock();
     const auto &BlockRange = assignDFSNumbers(B, ICount);