diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h
--- a/llvm/include/llvm/Support/GenericDomTree.h
+++ b/llvm/include/llvm/Support/GenericDomTree.h
@@ -30,6 +30,7 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/CFGDiff.h"
 #include "llvm/Support/CFGUpdate.h"
+#include "llvm/Support/Handle.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
@@ -41,6 +42,8 @@
 
 namespace llvm {
 
+class GenericDominatorTreeBase;
+
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase;
 
@@ -49,93 +52,52 @@
 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:
+  BlockHandle TheBB;
+  GenericDomTreeNodeBase *IDom;
   unsigned Level;
-  SmallVector<DomTreeNodeBase *, 4> Children;
+  SmallVector<GenericDomTreeNodeBase *, 4> Children;
   mutable unsigned DFSNumIn = ~0;
   mutable unsigned DFSNumOut = ~0;
 
- public:
-  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
-      : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
+public:
+  GenericDomTreeNodeBase(BlockHandle BB, GenericDomTreeNodeBase *idom)
+      : TheBB(BB), IDom(idom), Level(idom ? idom->Level + 1 : 0) {}
 
-  using iterator = typename SmallVector<DomTreeNodeBase *, 4>::iterator;
+  using iterator = typename SmallVector<GenericDomTreeNodeBase *, 4>::iterator;
   using const_iterator =
-      typename SmallVector<DomTreeNodeBase *, 4>::const_iterator;
+      typename SmallVector<GenericDomTreeNodeBase *, 4>::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; }
+  BlockHandle 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
@@ -143,29 +105,74 @@
   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;
+  void UpdateLevel();
+};
 
-    SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
+/// Base class for the actual dominator tree node.
+template <class NodeT> class DomTreeNodeBase : public GenericDomTreeNodeBase {
+  using Wrapper = HandleWrapper<BlockHandle, NodeT *>;
 
-    while (!WorkStack.empty()) {
-      DomTreeNodeBase *Current = WorkStack.pop_back_val();
-      Current->Level = Current->IDom->Level + 1;
+  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>>;
 
-      for (DomTreeNodeBase *C : *Current) {
-        assert(C->IDom);
-        if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
-      }
-    }
+public:
+  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *IDom)
+      : GenericDomTreeNodeBase(Wrapper::wrapRef(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 Wrapper::unwrapRef(TheBB); }
+  DomTreeNodeBase *getIDom() const {
+    return static_cast<DomTreeNodeBase *>(IDom);
   }
 };
 
@@ -186,10 +193,8 @@
 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 {
@@ -220,13 +225,111 @@
 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<BlockHandle, 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(BlockHandle BB) const {
+    auto I = DomTreeNodes.find(BB);
+    if (I != DomTreeNodes.end())
+      return I->second.get();
+    return nullptr;
+  }
+
+  /// See getNode.
+  GenericDomTreeNodeBase *operator[](BlockHandle 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(BlockHandle A, BlockHandle B) const;
+
+  bool dominates(const GenericDomTreeNodeBase *A,
+                 const GenericDomTreeNodeBase *B) const;
+  bool dominatesBlock(BlockHandle A, BlockHandle B) const;
+
+  const GenericDomTreeNodeBase *
+  findNearestCommonDominator(const GenericDomTreeNodeBase *A,
+                             const GenericDomTreeNodeBase *B) const;
+  BlockHandle findNearestCommonDominatorBlock(BlockHandle A,
+                                              BlockHandle 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 {
+public:
+  using Wrapper = HandleWrapper<BlockHandle, NodeT *>;
+
   static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
                 "Currently DominatorTreeBase supports only pointer nodes");
   using NodeType = NodeT;
@@ -247,45 +350,13 @@
 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:
+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.
@@ -323,25 +394,7 @@
     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
@@ -349,10 +402,9 @@
   /// 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(
+            Wrapper::wrapRef(const_cast<NodeT *>(BB))));
   }
 
   /// See getNode.
@@ -367,8 +419,12 @@
   /// 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 {
@@ -386,124 +442,68 @@
     }
   }
 
-  /// 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 GenericDominatorTreeBase::dominates(A, B);
+  }
+  bool dominates(const NodeT *A, const NodeT *B) const {
+    if (A == 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(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];
   }
 
-  /// Find nearest common dominator basic block for basic block A and B. A and B
-  /// must have tree nodes.
-  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);
-    assert(NodeA && "A must be in the tree");
-    assert(NodeB && "B must be in the tree");
-
-    // 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 != NodeB) {
-      if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
-
-      NodeA = NodeA->IDom;
-    }
-
-    return NodeA->getBlock();
+  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
+    return isPostDominator() && !A->getBlock();
   }
 
+  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();
   }
 
   //===--------------------------------------------------------------------===//
@@ -638,13 +638,14 @@
     } else {
       assert(Roots.size() == 1);
       NodeT *OldRoot = Roots.front();
-      auto &OldNode = DomTreeNodes[OldRoot];
-      OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
+      auto &OldNode = DomTreeNodes[Wrapper::wrapRef(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
@@ -681,7 +682,7 @@
       IDom->Children.erase(I);
     }
 
-    DomTreeNodes.erase(BB);
+    DomTreeNodes.erase(Wrapper::wrapRef(BB));
 
     if (!IsPostDom) return;
 
@@ -725,53 +726,6 @@
   }
 
 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;
@@ -802,27 +756,28 @@
   }
 
   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();
+    BlockHandle bbRef = Wrapper::wrapRef(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();
+    BlockHandle bbRef = Wrapper::wrapRef(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
@@ -881,34 +836,6 @@
       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>
@@ -917,33 +844,6 @@
 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
diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
--- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -53,6 +53,7 @@
 
 template <typename DomTreeT>
 struct SemiNCAInfo {
+  using Wrapper = typename DomTreeT::Wrapper;
   using NodePtr = typename DomTreeT::NodePtr;
   using NodeT = typename DomTreeT::NodeType;
   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
@@ -137,7 +138,7 @@
     // immediate dominator.
     NodePtr IDom = getIDom(BB);
 
-    assert(IDom || DT.DomTreeNodes[nullptr]);
+    assert(IDom || DT.DomTreeNodes[BlockHandle{}]);
     TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
 
     // Add a new tree node for this NodeT, and link it as a child of
@@ -593,7 +594,7 @@
     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) {
@@ -604,7 +605,8 @@
       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[Wrapper::wrapRef(W)])
+        continue; // Haven't calculated this node yet?
 
       NodePtr ImmDom = getIDom(W);
 
@@ -1142,7 +1144,7 @@
     std::swap(*ChIt, IDom->Children.back());
     IDom->Children.pop_back();
 
-    DT.DomTreeNodes.erase(TN->getBlock());
+    DT.DomTreeNodes.erase(Wrapper::wrapRef(TN->getBlock()));
   }
 
   //~~
@@ -1268,7 +1270,8 @@
     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.
@@ -1301,7 +1304,8 @@
   // 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;
 
@@ -1356,7 +1360,8 @@
     // 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()) {
@@ -1469,7 +1474,8 @@
   // 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;
@@ -1503,7 +1509,8 @@
   // 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;
diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt
--- a/llvm/lib/Support/CMakeLists.txt
+++ b/llvm/lib/Support/CMakeLists.txt
@@ -124,6 +124,7 @@
   FoldingSet.cpp
   FormattedStream.cpp
   FormatVariadic.cpp
+  GenericDomTree.cpp
   GlobPattern.cpp
   GraphWriter.cpp
   Hashing.cpp
diff --git a/llvm/lib/Support/GenericDomTree.cpp b/llvm/lib/Support/GenericDomTree.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/lib/Support/GenericDomTree.cpp
@@ -0,0 +1,278 @@
+//===- 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<BlockHandle, 4> OtherChildren;
+  for (const GenericDomTreeNodeBase *I : *Other) {
+    BlockHandle Nd = I->getBlock();
+    OtherChildren.insert(Nd);
+  }
+
+  for (const GenericDomTreeNodeBase *I : *this) {
+    BlockHandle 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) {
+    BlockHandle 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(BlockHandle A,
+                                                      BlockHandle 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(BlockHandle A,
+                                              BlockHandle 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 of A and B.
+const GenericDomTreeNodeBase *
+GenericDominatorTreeBase::findNearestCommonDominator(
+    const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const {
+  if (A == RootNode || B == RootNode)
+    return RootNode;
+
+  assert(A && "A muset be in the tree");
+  assert(B && "B muset be in the tree");
+
+  // 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;
+}
+
+BlockHandle
+GenericDominatorTreeBase::findNearestCommonDominatorBlock(BlockHandle A,
+                                                          BlockHandle B) const {
+  assert(A && B && "Pointers are not valid");
+
+  const GenericDomTreeNodeBase *Dom =
+      findNearestCommonDominator(getNode(A), getNode(B));
+
+  return Dom ? Dom->getBlock() : BlockHandle();
+}
+
+/// 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;
+}
diff --git a/llvm/lib/Transforms/Scalar/ADCE.cpp b/llvm/lib/Transforms/Scalar/ADCE.cpp
--- a/llvm/lib/Transforms/Scalar/ADCE.cpp
+++ b/llvm/lib/Transforms/Scalar/ADCE.cpp
@@ -295,7 +295,7 @@
   // 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
diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp
--- a/llvm/lib/Transforms/Scalar/NewGVN.cpp
+++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp
@@ -511,7 +511,7 @@
   unsigned int NumFuncArgs = 0;
 
   // RPOOrdering of basic blocks
-  DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
+  DenseMap<const GenericDomTreeNodeBase *, unsigned> RPOOrdering;
 
   // Congruence class info.
 
@@ -3388,8 +3388,10 @@
   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];
                  });
   }