[Dominators] Move number to node mapping out of DominatorTreeBase

[kuhar]

Summary

Number to node mapping in DominatorTreeBase is used only during calculation, so there is no point keeping is as a member variable. This patch moves this mapping to Calculate function and passes it to helper functions. It also makes the name more descriptive.

[kuhar]

Update patch to apply cleanly.

[• dberlin]

This is fine, but at the end of all these patches, can you please make it so there is only one structure storing state for building?

(i don't care whether this is by making genericdomtreebuilder a real class, or passing a single struct around)
I'm okay if the SNCAInfo is a pointer in that struct :)

[kuhar]

Update the diff to apply cleanly.

llvm/trunk/include/llvm/Support/GenericDomTree.h

template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
 
   /// \brief 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();
     IDoms.clear();
-    Vertex.clear();
     Info.clear();
     RootNode = nullptr;
   }
 
 protected:
   using DomTreeNodeMapType =
      DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
   DomTreeNodeMapType DomTreeNodes;
   DomTreeNodeBase<NodeT> *RootNode;
 
   mutable bool DFSInfoValid = false;
   mutable unsigned int SlowQueries = 0;
   // Information record used during immediate dominators computation.
   struct InfoRec {
     unsigned DFSNum = 0;
     unsigned Parent = 0;
     unsigned Semi = 0;
     NodeT *Label = nullptr;
 
     InfoRec() = default;
   };
 
   DenseMap<NodeT *, NodeT *> IDoms;
 
-  // Vertex - Map the DFS number to the NodeT*
-  std::vector<NodeT *> Vertex;
-
   // Info - Collection of information used during the computation of idoms.
   DenseMap<NodeT *, InfoRec> Info;
 
   void reset() {
     DomTreeNodes.clear();
     IDoms.clear();
     this->Roots.clear();
-    Vertex.clear();
     RootNode = nullptr;
     DFSInfoValid = false;
     SlowQueries = 0;
   }
 
   // NewBB is split and now it has one successor. Update dominator tree to
   // reflect this change.
   template <class N>
explicit DominatorTreeBase(bool isPostDom)
       : DominatorBase<NodeT>(isPostDom) {}
 
   DominatorTreeBase(DominatorTreeBase &&Arg)
       : DominatorBase<NodeT>(
             std::move(static_cast<DominatorBase<NodeT> &>(Arg))),
         DomTreeNodes(std::move(Arg.DomTreeNodes)),
         RootNode(std::move(Arg.RootNode)),
         DFSInfoValid(std::move(Arg.DFSInfoValid)),
-        SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)),
-        Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) {
+        SlowQueries(std::move(Arg.SlowQueries)),
+        IDoms(std::move(Arg.IDoms)),
+        Info(std::move(Arg.Info)) {
     Arg.wipe();
   }
 
   DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
     DominatorBase<NodeT>::operator=(
         std::move(static_cast<DominatorBase<NodeT> &>(RHS)));
     DomTreeNodes = std::move(RHS.DomTreeNodes);
     RootNode = std::move(RHS.RootNode);
     DFSInfoValid = std::move(RHS.DFSInfoValid);
     SlowQueries = std::move(RHS.SlowQueries);
     IDoms = std::move(RHS.IDoms);
-    Vertex = std::move(RHS.Vertex);
     Info = std::move(RHS.Info);
     RHS.wipe();
     return *this;
   }
 
   DominatorTreeBase(const DominatorTreeBase &) = delete;
   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
 
void print(raw_ostream &O) const {
     O << "\n";
 
     // The postdom tree can have a null root if there are no returns.
     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
   }
 
 protected:
   template <class GraphT>
-  friend typename GraphT::NodeRef
-  Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-       unsigned LastLinked);
+  friend typename GraphT::NodeRef Eval(
+      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
+      const std::vector<typename GraphT::NodeRef> &NumToNode,
 
   template <class GraphT>
-  friend unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                                 typename GraphT::NodeRef V, unsigned N);
+  friend unsigned ReverseDFSPass(
+      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
+      std::vector<typename GraphT::NodeRef> &NumToNode, unsigned N);
 
   template <class GraphT>
   friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                          typename GraphT::NodeRef V, unsigned N);
+                          typename GraphT::NodeRef V,
+                          std::vector<typename GraphT::NodeRef> &NumToNode,
+                          unsigned N);
 
   template <class FuncT, class N>
   friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT,
-                        FuncT &F);
 
   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
     if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
       return Node;
 
     // Haven't calculated this node yet?  Get or calculate the node for the
     // immediate dominator.
     NodeT *IDom = getIDom(BB);
void updateDFSNumbers() const {
     SlowQueries = 0;
     DFSInfoValid = true;
   }
 
   /// recalculate - compute a dominator tree for the given function
   template <class FT> void recalculate(FT &F) {
     using TraitsTy = GraphTraits<FT *>;
     reset();
-    Vertex.push_back(nullptr);
 
     if (!this->IsPostDominators) {
       // Initialize root
       NodeT *entry = TraitsTy::getEntryNode(&F);
       addRoot(entry);
 
       Calculate<FT, NodeT *>(*this, F);
     } else {

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

public:
   void completed(NodeRef) {}
 
 private:
   BaseSet &Storage;
 };
 
 template <class GraphT>
 unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                        typename GraphT::NodeRef V, unsigned N) {
+                        typename GraphT::NodeRef V,
+                        std::vector<typename GraphT::NodeRef> &NumToNode,
+                        unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
       typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
       DFStorage(DT.Info);
   bool IsChildOfArtificialExit = (N != 0);
   for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
        I != E; ++I) {
     typename GraphT::NodeRef BB = *I;
     auto &BBInfo = DT.Info[BB];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = BB;
     // Set the parent to the top of the visited stack.  The stack includes us,
     // and is 1 based, so we subtract to account for both of these.
     if (I.getPathLength() > 1)
       BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum;
-    DT.Vertex.push_back(BB); // Vertex[n] = V;
+    NumToNode.push_back(BB); // NumToNode[n] = V;
 
     if (IsChildOfArtificialExit)
       BBInfo.Parent = 1;
 
     IsChildOfArtificialExit = false;
   }
   return N;
 }
 template <class GraphT>
 unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                 typename GraphT::NodeRef V, unsigned N) {
+                 typename GraphT::NodeRef V,
+                 std::vector<typename GraphT::NodeRef> &NumToNode, unsigned N) {
   df_iterator_dom_storage<
       typename GraphT::NodeRef,
       typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
       DFStorage(DT.Info);
   for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
        I != E; ++I) {
     typename GraphT::NodeRef BB = *I;
     auto &BBInfo = DT.Info[BB];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = BB;
     // Set the parent to the top of the visited stack.  The stack includes us,
     // and is 1 based, so we subtract to account for both of these.
     if (I.getPathLength() > 1)
       BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum;
-    DT.Vertex.push_back(BB); // Vertex[n] = V;
+    NumToNode.push_back(BB); // NumToNode[n] = V;
   }
   return N;
 }
 
 template <class GraphT>
-typename GraphT::NodeRef Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                              typename GraphT::NodeRef VIn,
-                              unsigned LastLinked) {
+typename GraphT::NodeRef Eval(
+    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef VIn,
+    const std::vector<typename GraphT::NodeRef> &NumToNode,
   using NodePtr = typename GraphT::NodeRef;
 
   auto &VInInfo = DT.Info[VIn];
   if (VInInfo.DFSNum < LastLinked)
     return VIn;
 
   SmallVector<NodePtr, 32> Work;
   SmallPtrSet<NodePtr, 32> Visited;
 
   if (VInInfo.Parent >= LastLinked)
     Work.push_back(VIn);
 
   while (!Work.empty()) {
     NodePtr V = Work.back();
     auto &VInfo = DT.Info[V];
-    NodePtr VAncestor = DT.Vertex[VInfo.Parent];
+    NodePtr VAncestor = NumToNode[VInfo.Parent];
 
     // Process Ancestor first
     if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
       Work.push_back(VAncestor);
       continue;
     }
     Work.pop_back();
 
void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
                FuncT &F) {
   using GraphT = GraphTraits<NodeT>;
   using NodePtr = typename GraphT::NodeRef;
   static_assert(std::is_pointer<NodePtr>::value,
                 "NodeRef should be pointer type");
   using NodeType = typename std::remove_pointer<NodePtr>::type;
 
   unsigned N = 0;
+  std::vector<NodePtr> NumToNode = {nullptr};
+
   bool MultipleRoots = (DT.Roots.size() > 1);
   if (MultipleRoots) {
     auto &BBInfo = DT.Info[nullptr];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = nullptr;
 
-    DT.Vertex.push_back(nullptr);       // Vertex[n] = V;
+    NumToNode.push_back(nullptr); // NumToNode[n] = V;
   }
 
   // Step #1: Number blocks in depth-first order and initialize variables used
   // in later stages of the algorithm.
   if (DT.isPostDominator()){
     for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
          i != e; ++i)
-      N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], N);
+      N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], NumToNode, N);
   } else {
-    N = DFSPass<GraphT>(DT, DT.Roots[0], N);
+    N = DFSPass<GraphT>(DT, DT.Roots[0], NumToNode, N);
   }
 
   // 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.
   MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
 
   // Initialize IDoms to spanning tree parents.
   for (unsigned i = 1; i <= N; ++i) {
-    const NodePtr V = DT.Vertex[i];
-    DT.IDoms[V] = DT.Vertex[DT.Info[V].Parent];
+    const NodePtr V = NumToNode[i];
+    DT.IDoms[V] = NumToNode[DT.Info[V].Parent];
   }
 
   // Step #2: Calculate the semidominators of all vertices.
   for (unsigned i = N; i >= 2; --i) {
-    NodePtr W = DT.Vertex[i];
+    NodePtr W = NumToNode[i];
     auto &WInfo = DT.Info[W];
 
     // Initialize the semi dominator to point to the parent node.
     WInfo.Semi = WInfo.Parent;
     for (const auto &N : inverse_children<NodeT>(W))
       if (DT.Info.count(N)) { // Only if this predecessor is reachable!
-        unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
+        unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, NumToNode, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
   }
 
 
   // Step #3: Explicitly define the immediate dominator of each vertex.
   //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
   // Note that the parents were stored in IDoms and later got invalidated during
   // path compression in Eval.
   for (unsigned i = 2; i <= N; ++i) {
-    const NodePtr W = DT.Vertex[i];
+    const NodePtr W = NumToNode[i];
     const auto &WInfo = DT.Info[W];
-    const unsigned SDomNum = DT.Info[DT.Vertex[WInfo.Semi]].DFSNum;
+    const unsigned SDomNum = DT.Info[NumToNode[WInfo.Semi]].DFSNum;
     NodePtr WIDomCandidate = DT.IDoms[W];
     while (DT.Info[WIDomCandidate].DFSNum > SDomNum)
       WIDomCandidate = DT.IDoms[WIDomCandidate];
 
     DT.IDoms[W] = WIDomCandidate;
   }
 
   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.
   NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
 
   DT.RootNode =
       (DT.DomTreeNodes[Root] =
            llvm::make_unique<DomTreeNodeBase<NodeType>>(Root, nullptr))
           .get();
 
   // Loop over all of the reachable blocks in the function...
   for (unsigned i = 2; i <= N; ++i) {
-    NodePtr W = DT.Vertex[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?
 
     NodePtr ImmDom = DT.getIDom(W);
 
     assert(ImmDom || DT.DomTreeNodes[nullptr]);
 
     // Get or calculate the node for the immediate dominator
     DomTreeNodeBase<NodeType> *IDomNode = DT.getNodeForBlock(ImmDom);
 
     // Add a new tree node for this BasicBlock, and link it as a child of
     // IDomNode
     DT.DomTreeNodes[W] = IDomNode->addChild(
         llvm::make_unique<DomTreeNodeBase<NodeType>>(W, IDomNode));
   }
 
   // Free temporary memory used to construct idom's
   DT.IDoms.clear();
   DT.Info.clear();
-  DT.Vertex.clear();
-  DT.Vertex.shrink_to_fit();
 
   DT.updateDFSNumbers();
 }
 }
 
 #endif