[Dominators] Move root-finding out of DomTreeBase and simplify it

[kuhar]

Summary

This patch moves root-finding logic from DominatorTreeBase to GenericDomTreeConstruction.h.
It makes the behavior simpler and more consistent by always adding a virtual root to PostDominatorTrees.

[kuhar]

Update the comment about virtual roots.

[kuhar]

Ping. I have patches depending on this one.

[hiraditya]

include/llvm/Support/GenericDomTree.h

216

s/NodeT */NodePtr

include/llvm/IR/Dominators.h

 extern template class DomTreeNodeBase<BasicBlock>;
 extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
 extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
 
 namespace DomTreeBuilder {
 using BBDomTree = DomTreeBase<BasicBlock>;
 using BBPostDomTree = PostDomTreeBase<BasicBlock>;
 
-extern template void Calculate<BBDomTree, Function>(BBDomTree &DT, Function &F);
-extern template void Calculate<BBPostDomTree, Function>(BBPostDomTree &DT,
-                                                        Function &F);
+extern template void Calculate<BBDomTree>(BBDomTree &DT);
+extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
 
 extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
                                            BasicBlock *To);
 extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
                                                BasicBlock *From,
                                                BasicBlock *To);
 
 extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,

include/llvm/Support/GenericDomTree.h

 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \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, depending on
-/// the implementation, e.g. NodeRef->getParent() return the parent node.
+/// on the graph's NodeRef. The NodeRef should be a pointer and,
+/// NodeRef->getParent() must return the parent node that is also a pointer.
 ///
 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
                                                        E = N->end();
        I != E; ++I)
     PrintDomTree<NodeT>(*I, O, Lev + 1);
 }
 
 namespace DomTreeBuilder {
 // The routines below are provided in a separate header but referenced here.
-template <typename DomTreeT, typename FuncT>
-void Calculate(DomTreeT &DT, FuncT &F);
+template <typename DomTreeT>
+void Calculate(DomTreeT &DT);
 
 template <class DomTreeT>
 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
 template <class DomTreeT>
 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To);
 
 template <typename DomTreeT>
 bool Verify(const DomTreeT &DT);
 }  // namespace DomTreeBuilder
 
 /// \brief 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());
+  static_assert(std::is_pointer<ParentPtr>::value,
+                "Currently NodeT's parent must be a pointer type");
+  using ParentType = typename std::remove_pointer<ParentPtr>::type;
+  static constexpr bool IsPostDominator = IsPostDom;
+
  protected:
   std::vector<NodeT *> Roots;
 
   using DomTreeNodeMapType =
      DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
   DomTreeNodeMapType DomTreeNodes;
   DomTreeNodeBase<NodeT> *RootNode;
-  using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
   ParentPtr Parent = nullptr;
 
   mutable bool DFSInfoValid = false;
   mutable unsigned int SlowQueries = 0;
 
   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
 
  public:
-  static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
-                "Currently DominatorTreeBase supports only pointer nodes");
-  using NodeType = NodeT;
-  using NodePtr = NodeT *;
-  static constexpr bool IsPostDominator = IsPostDom;
-
   DominatorTreeBase() {}
 
   DominatorTreeBase(DominatorTreeBase &&Arg)
       : Roots(std::move(Arg.Roots)),
         DomTreeNodes(std::move(Arg.DomTreeNodes)),
         RootNode(Arg.RootNode),
         Parent(Arg.Parent),
         DFSInfoValid(Arg.DFSInfoValid),
while (!WorkStack.empty()) {
       }
     }
 
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 
   /// recalculate - compute a dominator tree for the given function
-  template <class FT> void recalculate(FT &F) {
-    using TraitsTy = GraphTraits<FT *>;
+  void recalculate(ParentType &Func) {
     reset();
-    Parent = &F;
-
-    if (!IsPostDominator) {
-      // Initialize root
-      NodeT *entry = TraitsTy::getEntryNode(&F);
-      addRoot(entry);
-    } else {
-      // Initialize the roots list
-      for (auto *Node : nodes(&F))
-        if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
-          addRoot(Node);
-    }
-
-    DomTreeBuilder::Calculate(*this, F);
+    Parent = &Func;
+    DomTreeBuilder::Calculate(*this);
   }
 
   /// verify - check parent and sibling property
   bool verify() const { return DomTreeBuilder::Verify(*this); }
 
  protected:
   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
 

include/llvm/Support/GenericDomTreeConstruction.h

friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
 
       return O;
     }
   };
 
   // Custom DFS implementation which can skip nodes based on a provided
   // predicate. It also collects ReverseChildren so that we don't have to spend
   // time getting predecessors in SemiNCA.
-  template <bool Inverse, typename DescendCondition>
+  template <typename DescendCondition>
   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
                   unsigned AttachToNum) {
     assert(V);
     SmallVector<NodePtr, 64> WorkList = {V};
     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
 
     while (!WorkList.empty()) {
       const NodePtr BB = WorkList.pop_back_val();
       auto &BBInfo = NodeToInfo[BB];
 
       // Visited nodes always have positive DFS numbers.
       if (BBInfo.DFSNum != 0) continue;
       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
       BBInfo.Label = BB;
       NumToNode.push_back(BB);
 
-      for (const NodePtr Succ : ChildrenGetter<NodePtr, Inverse>::Get(BB)) {
+      for (const NodePtr Succ : ChildrenGetter<NodePtr, IsPostDom>::Get(BB)) {
         const auto SIT = NodeToInfo.find(Succ);
         // Don't visit nodes more than once but remember to collect
         // RerverseChildren.
         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
           continue;
         }
 
for (unsigned i = 2; i < NextDFSNum; ++i) {
       WInfo.IDom = WIDomCandidate;
     }
   }
 
   template <typename DescendCondition>
   unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
     unsigned Num = 0;
 
-    if (DT.Roots.size() > 1) {
+    // If the DT is a PostDomTree, always add a virtual root.
+    if (IsPostDom) {
       auto &BBInfo = NodeToInfo[nullptr];
       BBInfo.DFSNum = BBInfo.Semi = ++Num;
       BBInfo.Label = nullptr;
 
       NumToNode.push_back(nullptr);  // NumToNode[n] = V;
     }
 
-    if (DT.isPostDominator()) {
-      for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
-    } else {
-      assert(DT.Roots.size() == 1);
-      Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
-    }
+    const unsigned InitialNum = Num;
+    for (auto *Root : DT.Roots) Num = runDFS(Root, Num, DC, InitialNum);
 
     return Num;
   }
 
-  void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) {
+  static void FindAndAddRoots(DomTreeT &DT) {
+    assert(DT.Parent && "Parent pointer is not set");
+    using TraitsTy = GraphTraits<typename DomTreeT::ParentPtr>;
+
+    if (!IsPostDom) {
+      // Dominators have a single root that is the function's entry.
+      NodeT *entry = TraitsTy::getEntryNode(DT.Parent);
+      DT.addRoot(entry);
+    } else {
+      // Initialize the roots list for PostDominators.
+      for (auto *Node : nodes(DT.Parent))
+        if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node))
+          DT.addRoot(Node);
+    }
+  }
+
+  void calculateFromScratch(DomTreeT &DT) {
     // Step #0: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
-    const unsigned LastDFSNum = doFullDFSWalk(DT, AlwaysDescend);
+    FindAndAddRoots(DT);
+    doFullDFSWalk(DT, AlwaysDescend);
 
     runSemiNCA(DT);
 
     if (DT.Roots.empty()) return;
 
-    // Add a node for the root.  This node might be the actual root, if there is
-    // one exit block, or it may be the virtual exit (denoted by
-    // (BasicBlock *)0) which postdominates all real exits if there are multiple
-    // exit blocks, or an infinite loop.
-    // It might be that some blocks did not get a DFS number (e.g., blocks of
-    // infinite loops). In these cases an artificial exit node is required.
-    const bool MultipleRoots = DT.Roots.size() > 1 || (DT.isPostDominator() &&
-                                                       LastDFSNum != NumBlocks);
-    NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
+    // 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.DomTreeNodes[Root] =
                        llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
         .get();
     attachNewSubtree(DT, DT.RootNode);
   }
 
   void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
       const TreeNodePtr ToTN = DT.getNode(To);
       if (!ToTN) return true;
 
       DiscoveredConnectingEdges.push_back({From, ToTN});
       return false;
     };
 
     SemiNCAInfo SNCA;
-    SNCA.runDFS<IsPostDom>(Root, 0, UnreachableDescender, 0);
+    SNCA.runDFS(Root, 0, UnreachableDescender, 0);
     SNCA.runSemiNCA(DT);
     SNCA.attachNewSubtree(DT, Incoming);
 
     DEBUG(dbgs() << "After adding unreachable nodes\n");
     DEBUG(DT.print(dbgs()));
   }
 
   // Checks if the tree contains all reachable nodes in the input graph.
static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN,
     const unsigned Level = ToIDomTN->getLevel();
     auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
       return DT.getNode(To)->getLevel() > Level;
     };
 
     DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
 
     SemiNCAInfo SNCA;
-    SNCA.runDFS<IsPostDom>(ToIDom, 0, DescendBelow, 0);
+    SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
     DEBUG(dbgs() << "\tRunning Semi-NCA\n");
     SNCA.runSemiNCA(DT, Level);
     SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
   }
 
   // Checks if a node has proper support, as defined on the page 3 and later
   // explained on the page 7 of the second paper.
   static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) {
auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
       if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
         AffectedQueue.push_back(To);
 
       return false;
     };
 
     SemiNCAInfo SNCA;
     unsigned LastDFSNum =
-        SNCA.runDFS<IsPostDom>(ToTN->getBlock(), 0, DescendAndCollect, 0);
+        SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
 
     TreeNodePtr MinNode = ToTN;
 
     // Identify the top of the subtree to rebuilt by finding the NCD of all
     // the affected nodes.
     for (const NodePtr N : AffectedQueue) {
       const TreeNodePtr TN = DT.getNode(N);
       const NodePtr NCDBlock =
static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) {
     assert(PrevIDom);
     SNCA.clear();
 
     // Identify nodes that remain in the affected subtree.
     auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
       const TreeNodePtr ToTN = DT.getNode(To);
       return ToTN && ToTN->getLevel() > MinLevel;
     };
-    SNCA.runDFS<IsPostDom>(MinNode->getBlock(), 0, DescendBelow, 0);
+    SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
 
     DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom)
                  << "\nRunning Semi-NCA\n");
 
     // Rebuild the remaining part of affected subtree.
     SNCA.runSemiNCA(DT, MinLevel);
     SNCA.reattachExistingSubtree(DT, PrevIDom);
   }
for (auto &NodeToTN : DT.DomTreeNodes) {
         }
       }
     }
 
     return true;
   }
 };
 
-
-template <class DomTreeT, class FuncT>
-void Calculate(DomTreeT &DT, FuncT &F) {
+template <class DomTreeT>
+void Calculate(DomTreeT &DT) {
   SemiNCAInfo<DomTreeT> SNCA;
-  SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F));
+  SNCA.calculateFromScratch(DT);
 }
 
 template <class DomTreeT>
 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
                 typename DomTreeT::NodePtr To) {
   if (DT.isPostDominator()) std::swap(From, To);
   SemiNCAInfo<DomTreeT>::InsertEdge(DT, From, To);
 }

lib/IR/Dominators.cpp

 // GenericDomTreeConstruction.h.
 //
 //===----------------------------------------------------------------------===//
 
 template class llvm::DomTreeNodeBase<BasicBlock>;
 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
 
-template void
-llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree, Function>(
-    DomTreeBuilder::BBDomTree &DT, Function &F);
-template void
-llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree, Function>(
-    DomTreeBuilder::BBPostDomTree &DT, Function &F);
+template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
+    DomTreeBuilder::BBDomTree &DT);
+template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
+    DomTreeBuilder::BBPostDomTree &DT);
 
 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
     DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
 
 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
     DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);