DomTree: Add TreeNode type alias

[nhaehnle]

Summary

This should help reduce churn later on when we clean up the template
parameter to be a CfgTraitsT instead of a NodeT.

Change-Id: Id12289d381efbc015f65fe5549564f67a31189f4

[RKSimon]

LGTM

[kuhar]

LGTM

[RKSimon]

@nhaehnle Sorry just trying to clean out my phab backlog - but whatever happened with this patch?

[arsenm]

In D83090#3821170, @RKSimon wrote:

@nhaehnle Sorry just trying to clean out my phab backlog - but whatever happened with this patch?

I believe @sameerds is adopting this series

[sameerds]

This change is not really on the path for what I am doing with convergence and uniformity. It relates to an old discussion about having a single interface to SSA-form IRs such as LLVM IR and MIR. Seems mostly harmless to commit if anyone has a use for it, but things like CycleInfo and the new UniformityAnalysis depend on SSAContext::DominatorTreeT instead. It's defined in SSAContext.h and MachineSSAContext.h for the two supported IRs.

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

 public:
   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());
+  using TreeNode = DomTreeNodeBase<NodeT>;
   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;
bool compare(const DominatorTreeBase &Other) const {
 
     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 {
-    return static_cast<DomTreeNodeBase<NodeT> *>(
-        GenericDominatorTreeBase::getNode(
-            CfgTraits::toGeneric(const_cast<NodeT *>(BB))));
+  TreeNode *getNode(const NodeT *BB) const {
+    return static_cast<TreeNode *>(GenericDominatorTreeBase::getNode(
   }
 
   /// See getNode.
-  DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
-    return getNode(BB);
-  }
+  TreeNode *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 static_cast<DomTreeNodeBase<NodeT> *>(RootNode);
-  }
-  const DomTreeNodeBase<NodeT> *getRootNode() const {
-    return static_cast<const DomTreeNodeBase<NodeT> *>(RootNode);
+  TreeNode *getRootNode() { return static_cast<TreeNode *>(RootNode); }
+  const TreeNode *getRootNode() const {
+    return static_cast<const TreeNode *>(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);
+    const TreeNode *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;
+    SmallVector<const TreeNode *, 8> WL;
     WL.push_back(RN);
 
     while (!WL.empty()) {
-      const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
+      const TreeNode *N = WL.pop_back_val();
       Result.push_back(N->getBlock());
       WL.append(N->begin(), N->end());
     }
   }
 
-  bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
-                         const DomTreeNodeBase<NodeT> *B) const {
+  bool properlyDominates(const TreeNode *A, const TreeNode *B) const {
     return GenericDominatorTreeBase::properlyDominates(A, B);
   }
   bool properlyDominates(const NodeT *A, const NodeT *B) const {
     if (A == B)
       return false;
     return GenericDominatorTreeBase::dominates(getNode(A), getNode(B));
   }
 
   /// 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 getNode(const_cast<NodeT *>(A)) != nullptr;
   }
-  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const {
-    return A != nullptr;
-  }
+  bool isReachableFromEntry(const TreeNode *A) const { return A != nullptr; }
 
-  bool dominates(const DomTreeNodeBase<NodeT> *A,
-                 const DomTreeNodeBase<NodeT> *B) const {
+  bool dominates(const TreeNode *A, const TreeNode *B) const {
     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));
   }
 
   NodeT *getRoot() const {
     assert(this->Roots.size() == 1 && "Should always have entry node!");
     return this->Roots[0];
   }
 
-  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
+  bool isVirtualRoot(const TreeNode *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> *>(
+  const TreeNode *findNearestCommonDominator(const TreeNode *A,
+                                             const TreeNode *B) const {
+    return static_cast<const TreeNode *>(
         GenericDominatorTreeBase::findNearestCommonDominator(A, B));
   }
   const NodeT *findNearestCommonDominator(const NodeT *A,
                                           const 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)));
+    const TreeNode *dom = static_cast<const TreeNode *>(
     return dom->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)));
+    const TreeNode *dom = static_cast<const TreeNode *>(
     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
public:
   ///
   /// This creates a new node as a child of DomBB dominator node, linking it
   /// into the children list of the immediate dominator.
   ///
   /// \param BB New node in CFG.
   /// \param DomBB CFG node that is dominator for BB.
   /// \returns New dominator tree node that represents new CFG node.
   ///
-  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
+  TreeNode *addNewBlock(NodeT *BB, NodeT *DomBB) {
     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
-    DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
+    TreeNode *IDomNode = getNode(DomBB);
     assert(IDomNode && "Not immediate dominator specified for block!");
     DFSInfoValid = false;
     return createChild(BB, IDomNode);
   }
 
   /// Add a new node to the forward dominator tree and make it a new root.
   ///
   /// \param BB New node in CFG.
   /// \returns New dominator tree node that represents new CFG node.
   ///
-  DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
+  TreeNode *setNewRoot(NodeT *BB) {
     assert(getNode(BB) == nullptr && "Block already in dominator 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[CfgTraits::toGeneric(OldRoot)];
       OldNode = NewNode->addChild(std::move(OldNode));
       OldNode->IDom = NewNode;
       OldNode->UpdateLevel();
       Roots[0] = BB;
     }
     RootNode = NewNode;
-    return static_cast<DomTreeNodeBase<NodeT> *>(RootNode);
+    return static_cast<TreeNode *>(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) {
+  void changeImmediateDominator(TreeNode *N, TreeNode *NewIDom) {
     assert(N && NewIDom && "Cannot change null node pointers!");
     DFSInfoValid = false;
     N->setIDom(NewIDom);
   }
 
   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
     changeImmediateDominator(getNode(BB), getNode(NewBB));
   }
 
   /// eraseNode - Removes a node from the dominator tree. Block must not
   /// dominate any other blocks. Removes node from its immediate dominator's
   /// children list. Deletes dominator node associated with basic block BB.
   void eraseNode(NodeT *BB) {
-    DomTreeNodeBase<NodeT> *Node = getNode(BB);
+    TreeNode *Node = getNode(BB);
     assert(Node && "Removing node that isn't in dominator tree.");
     assert(Node->isLeaf() && "Node is not a leaf node.");
 
     DFSInfoValid = false;
 
     // Remove node from immediate dominator's children list.
-    DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
+    TreeNode *IDom = Node->getIDom();
     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);
     }
 
void reset() {
     GenericDominatorTreeBase::reset();
     Roots.clear();
     Parent = nullptr;
   }
 
 protected:
   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
 
-  DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) {
+  TreeNode *createChild(NodeT *BB, TreeNode *IDom) {
     CfgBlockRef bbRef = CfgTraits::toGeneric(BB);
-    return static_cast<DomTreeNodeBase<NodeT> *>(
+    return static_cast<TreeNode *>(
         (DomTreeNodes[bbRef] = IDom->addChild(
              std::make_unique<GenericDomTreeNodeBase>(bbRef, IDom)))
             .get());
   }
 
-  DomTreeNodeBase<NodeT> *createNode(NodeT *BB) {
+  TreeNode *createNode(NodeT *BB) {
     CfgBlockRef bbRef = CfgTraits::toGeneric(BB);
-    return static_cast<DomTreeNodeBase<NodeT> *>(
+    return static_cast<TreeNode *>(
         (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) {
     if (!NewBBIDom) return;
 
     for (i = i + 1; i < PredBlocks.size(); ++i) {
       if (isReachableFromEntry(PredBlocks[i]))
         NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
     }
 
     // Create the new dominator tree node... and set the idom of NewBB.
-    DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
+    TreeNode *NewBBNode = addNewBlock(NewBB, NewBBIDom);
 
     // 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);
+      TreeNode *NewBBSuccNode = getNode(NewBBSucc);
       changeImmediateDominator(NewBBSuccNode, NewBBNode);
     }
   }
 };
 
 template <typename T>
 using DomTreeBase = DominatorTreeBase<T, false>;
 
 template <typename T>
 using PostDomTreeBase = DominatorTreeBase<T, true>;
 
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_GENERICDOMTREE_H

llvm/include/llvm/Support/GenericDomTreeConstruction.h

 //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- 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

 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 TreeNodePtr = typename DomTreeT::TreeNode *;
   using RootsT = decltype(DomTreeT::Roots);
   static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
 
   // Information record used by Semi-NCA during tree construction.
   struct InfoRec {
     unsigned DFSNum = 0;
     unsigned Parent = 0;
     unsigned Semi = 0;