[Dominators] Remove requirement to use NodeRef->getParent().

[fhahn]

Summary

At the moment, DominatorTreeBase requires NodeRef->getParent to return a
pointer to the container containing all NodeRefs.

This prevents DominatorTreeBase being used for hierarchical structures
where NodeRef can have multiple sub-types, with different parents. This
for example is the case for VPlan, which has region blocks that can be
nested, and regular blocks. NodeRef::getParent() here returns the
containing region. The 'parent' to use for the dominator tree is a VPlan
though, which contains the hierarchical CFG.

To enable such uses cases, allow GraphTraits to provide a custom ParentPtrTy to
directly define what parent pointer to use and add a ::getParent helper, which
can be specialized.

The main motivation for this patch is using DominatorTreeBase across all
regions of a VPlan, see D140513 https://reviews.llvm.org/D140513.

[fhahn]

Simplify.

[kuhar]

llvm/include/llvm/Support/GenericDomTree.h

228–229

What do you think about making this a little bit more general, say: struct DominatorTreeNodeTraits and moving NodePtr/ParentType/GraphTraits (from D142162) there as well?

[fhahn]

llvm/include/llvm/Support/GenericDomTree.h

228–229

I updated D142162 to add a DomTreeNodeTraits class with a customization option. Is that along the lines you had in mind?

[fhahn]

Subsumed by more general D142162

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.
+/// either NodeRef->getParent() must return the parent node that is also a
+/// pointer or DomTreeBase::getParent needs to be specialized to return the
+/// parent for NodeRef.
 ///
 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
void ApplyUpdates(DomTreeT &DT,
                             DomTreeT::IsPostDominator> &PreViewCFG,
                   GraphDiff<typename DomTreeT::NodePtr,
                             DomTreeT::IsPostDominator> *PostViewCFG);
 
 template <typename DomTreeT>
 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
 }  // namespace DomTreeBuilder
 
+namespace detail {
+/// Helper trait to use custom GraphTraits<T>::ParentPtrTy if it exists or
+/// T::getParent's return type otherwise.
+template <typename T, typename = void> struct dt_get_parent_ptr_ty {
+  using type = decltype(std::declval<T>()->getParent());
+};
+
+template <typename T>
+struct dt_get_parent_ptr_ty<T,
+                            std::void_t<typename GraphTraits<T>::ParentPtrTy>> {
+  using type = typename GraphTraits<T>::ParentPtrTy;
+};
+
+} // namespace detail
+
 /// Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
 /// various graphs in the LLVM IR or in the code generator.
 template <typename NodeT, bool IsPostDom>
 class DominatorTreeBase {
  public:
   static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
                 "Currently DominatorTreeBase supports only pointer nodes");
   using NodeType = NodeT;
   using NodePtr = NodeT *;
-  using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
+  using ParentPtr = typename detail::dt_get_parent_ptr_ty<NodeT *>::type;
   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;
#endif
 
   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];
   }
 
+  ParentPtr getParent(NodeT *B) const { return B->getParent(); }
+
   /// 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() &&
+    assert(getParent(A) == getParent(B) &&
            "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 = *GraphTraits<NodeT *>::getEntryNode(A);
       if (A == &Entry || B == &Entry)
         return &Entry;
#endif
   /// tree doesn't know about.
   ///
   /// Note that for postdominators it automatically takes care of inserting
   /// a reverse edge internally (so there's no need to swap the parameters).
   ///
   void insertEdge(NodeT *From, NodeT *To) {
     assert(From);
     assert(To);
-    assert(From->getParent() == Parent);
-    assert(To->getParent() == Parent);
+    assert(getParent(From) == Parent);
+    assert(getParent(To) == Parent);
     DomTreeBuilder::InsertEdge(*this, From, To);
   }
 
   /// Inform the dominator tree about a CFG edge deletion and update the tree.
   ///
   /// This function has to be called just after making the update on the actual
   /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
   /// DEBUG mode. There cannot be any other updates that the
   /// dominator tree doesn't know about.
   ///
   /// Note that for postdominators it automatically takes care of deleting
   /// a reverse edge internally (so there's no need to swap the parameters).
   ///
   void deleteEdge(NodeT *From, NodeT *To) {
     assert(From);
     assert(To);
-    assert(From->getParent() == Parent);
-    assert(To->getParent() == Parent);
+    assert(getParent(From) == Parent);
+    assert(getParent(To) == Parent);
     DomTreeBuilder::DeleteEdge(*this, From, To);
   }
 
   /// Add a new node to the dominator tree information.
   ///
   /// This creates a new node as a child of DomBB dominator node, linking it
   /// into the children list of the immediate dominator.
   ///