[Dominators] Move InfoRec outside of DominatorTreeBase

[kuhar]

Summary

The InfoRec struct is used only during tree construction, so there is no point having it as a DominatorTreeBase member.

This patch moves it into the Calculate function instead and makes it pass it to its helper functions.

[kuhar]

Update patch to apply cleanly.

[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();
-    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;
 
-  // Info - Collection of information used during the computation of idoms.
-  DenseMap<NodeT *, InfoRec> Info;
-
   void reset() {
     DomTreeNodes.clear();
     IDoms.clear();
     this->Roots.clear();
     RootNode = nullptr;
     DFSInfoValid = false;
     SlowQueries = 0;
   }
public:
 
   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)),
-        Info(std::move(Arg.Info)) {
+        IDoms(std::move(Arg.IDoms)) {
     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);
-    Info = std::move(RHS.Info);
     RHS.wipe();
     return *this;
   }
 
   DominatorTreeBase(const DominatorTreeBase &) = delete;
   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
 
   /// compare - Return false if the other dominator tree base matches this
if (!DFSInfoValid)
       O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
     O << "\n";
 
     // The postdom tree can have a null root if there are no returns.
     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
   }
 
 protected:
+  // Information record used by Semi-NCA during tree construction.
+  struct SemiNCAInfo {
+    using NodePtr = NodeT *;
+    struct InfoRec {
+      unsigned DFSNum = 0;
+      unsigned Parent = 0;
+      unsigned Semi = 0;
+      NodePtr Label = nullptr;
+    };
+
+    std::vector<NodePtr> NumToNode;
+    DenseMap<NodePtr, InfoRec> NodeToInfo;
+  };
+
   template <class GraphT>
   friend typename GraphT::NodeRef Eval(
       DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      const std::vector<typename GraphT::NodeRef> &NumToNode,
+      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
       unsigned LastLinked);
 
   template <class GraphT>
   friend unsigned ReverseDFSPass(
       DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      std::vector<typename GraphT::NodeRef> &NumToNode, unsigned N);
+      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
+      unsigned N);
 
   template <class GraphT>
-  friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
-                          typename GraphT::NodeRef V,
-                          std::vector<typename GraphT::NodeRef> &NumToNode,
-                          unsigned N);
+  friend unsigned DFSPass(
+      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
+      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
 
   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;

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,
-                        std::vector<typename GraphT::NodeRef> &NumToNode,
-                        unsigned N) {
-  df_iterator_dom_storage<
-      typename GraphT::NodeRef,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
-      DFStorage(DT.Info);
+unsigned ReverseDFSPass(
+    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
+    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
+  using SNCAInfoTy = typename std::remove_reference<decltype(SNCA)>::type;
+  df_iterator_dom_storage<typename SNCAInfoTy::NodePtr,
+      typename SNCAInfoTy::InfoRec>
+      DFStorage(SNCA.NodeToInfo);
+
   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];
+    auto &BBInfo = SNCA.NodeToInfo[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;
-    NumToNode.push_back(BB); // NumToNode[n] = V;
+      BBInfo.Parent = SNCA.NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
+    SNCA.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,
-                 std::vector<typename GraphT::NodeRef> &NumToNode, unsigned N) {
-  df_iterator_dom_storage<
-      typename GraphT::NodeRef,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::InfoRec>
-      DFStorage(DT.Info);
+unsigned DFSPass(
+    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
+    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
+    unsigned N) {
+  using SNCAInfoTy = typename std::remove_reference<decltype(SNCA)>::type;
+  df_iterator_dom_storage<typename SNCAInfoTy::NodePtr,
+      typename SNCAInfoTy::InfoRec>
+      DFStorage(SNCA.NodeToInfo);
   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];
+    auto &BBInfo = SNCA.NodeToInfo[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;
-    NumToNode.push_back(BB); // NumToNode[n] = V;
+      BBInfo.Parent = SNCA.NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
+    SNCA.NumToNode.push_back(BB);  // NumToNode[n] = V;
   }
   return N;
 }
 
 template <class GraphT>
 typename GraphT::NodeRef Eval(
     DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef VIn,
-    const std::vector<typename GraphT::NodeRef> &NumToNode,
+    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
     unsigned LastLinked) {
   using NodePtr = typename GraphT::NodeRef;
 
-  auto &VInInfo = DT.Info[VIn];
+  auto &VInInfo = SNCA.NodeToInfo[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 = NumToNode[VInfo.Parent];
+    auto &VInfo = SNCA.NodeToInfo[V];
+    NodePtr VAncestor = SNCA.NumToNode[VInfo.Parent];
 
     // Process Ancestor first
     if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
       Work.push_back(VAncestor);
       continue;
     }
     Work.pop_back();
 
     // Update VInfo based on Ancestor info
     if (VInfo.Parent < LastLinked)
       continue;
 
-    auto &VAInfo = DT.Info[VAncestor];
+    auto &VAInfo = SNCA.NodeToInfo[VAncestor];
     NodePtr VAncestorLabel = VAInfo.Label;
     NodePtr VLabel = VInfo.Label;
-    if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
+    if (SNCA.NodeToInfo[VAncestorLabel].Semi < SNCA.NodeToInfo[VLabel].Semi)
       VInfo.Label = VAncestorLabel;
     VInfo.Parent = VAInfo.Parent;
   }
 
   return VInInfo.Label;
 }
 
 template <class FuncT, class NodeT>
 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};
+  typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo SNCA;
+  SNCA.NumToNode.push_back(nullptr);
 
   bool MultipleRoots = (DT.Roots.size() > 1);
   if (MultipleRoots) {
-    auto &BBInfo = DT.Info[nullptr];
+    auto &BBInfo = SNCA.NodeToInfo[nullptr];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = nullptr;
 
-    NumToNode.push_back(nullptr); // NumToNode[n] = V;
+    SNCA.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], NumToNode, N);
+      N = ReverseDFSPass<GraphT>(DT, DT.Roots[i], SNCA, N);
   } else {
-    N = DFSPass<GraphT>(DT, DT.Roots[0], NumToNode, N);
+    N = DFSPass<GraphT>(DT, DT.Roots[0], SNCA, 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 = NumToNode[i];
-    DT.IDoms[V] = NumToNode[DT.Info[V].Parent];
+    const NodePtr V = SNCA.NumToNode[i];
+    DT.IDoms[V] = SNCA.NumToNode[SNCA.NodeToInfo[V].Parent];
   }
 
   // Step #2: Calculate the semidominators of all vertices.
   for (unsigned i = N; i >= 2; --i) {
-    NodePtr W = NumToNode[i];
-    auto &WInfo = DT.Info[W];
+    NodePtr W = SNCA.NumToNode[i];
+    auto &WInfo = SNCA.NodeToInfo[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, NumToNode, i + 1)].Semi;
+      if (SNCA.NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
+        unsigned SemiU = SNCA.NodeToInfo[Eval<GraphT>(DT, N, SNCA, 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 = NumToNode[i];
-    const auto &WInfo = DT.Info[W];
-    const unsigned SDomNum = DT.Info[NumToNode[WInfo.Semi]].DFSNum;
+    const NodePtr W = SNCA.NumToNode[i];
+    const auto &WInfo = SNCA.NodeToInfo[W];
+    const unsigned SDomNum = SNCA.NodeToInfo[SNCA.NumToNode[WInfo.Semi]].DFSNum;
     NodePtr WIDomCandidate = DT.IDoms[W];
-    while (DT.Info[WIDomCandidate].DFSNum > SDomNum)
+    while (SNCA.NodeToInfo[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 = NumToNode[i];
+    NodePtr W = SNCA.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.updateDFSNumbers();
 }
 }
 
 #endif