Index: llvm/trunk/include/llvm/Support/GenericDomTree.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTree.h +++ llvm/trunk/include/llvm/Support/GenericDomTree.h @@ -660,7 +660,7 @@ friend void Calculate(DominatorTreeBaseByGraphTraits> &DT, FuncT &F); - void addRoot(NodeT *BB) { this->Roots.push_back(BB); } + void addRoot(NodeT *BB) { this->Roots.push_back(BB); } public: /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking Index: llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h @@ -76,229 +76,222 @@ llvm::make_unique>(BB, IDomNode))) .get(); } -}; -} // namespace DomTreeBuilder -// External storage for depth first iterator that reuses the info lookup map -// domtree already has. We don't have a set, but a map instead, so we are -// converting the one argument insert calls. -template struct df_iterator_dom_storage { -public: - using BaseSet = DenseMap; - df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {} - - using iterator = typename BaseSet::iterator; - std::pair insert(NodeRef N) { - return Storage.insert({N, InfoType()}); - } - void completed(NodeRef) {} + // External storage for depth first iterator that reuses the info lookup map + // SemiNCAInfo already has. We don't have a set, but a map instead, so we are + // converting the one argument insert calls. + struct df_iterator_dom_storage { + public: + using BaseSet = decltype(NodeToInfo); + df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {} + + using iterator = typename BaseSet::iterator; + std::pair insert(NodePtr N) { + return Storage.insert({N, InfoRec()}); + } + void completed(NodePtr) {} -private: - BaseSet &Storage; -}; + private: + BaseSet &Storage; + }; -template ::type> -unsigned ReverseDFSPass(NodePtr V, DomTreeBuilder::SemiNCAInfo &SNCA, - unsigned N) { - using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo; - df_iterator_dom_storage DFStorage( - SNCA.NodeToInfo); - - bool IsChildOfArtificialExit = (N != 0); - for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage); - I != E; ++I) { - NodePtr BB = *I; - 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 = SNCA.NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum; - SNCA.NumToNode.push_back(BB); // NumToNode[n] = V; + df_iterator_dom_storage getStorage() { return {NodeToInfo}; } - if (IsChildOfArtificialExit) - BBInfo.Parent = 1; + unsigned runReverseDFS(NodePtr V, unsigned N) { + auto DFStorage = getStorage(); - IsChildOfArtificialExit = false; - } - return N; -} + bool IsChildOfArtificialExit = (N != 0); + for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage); + I != E; ++I) { + NodePtr BB = *I; + auto &BBInfo = 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 = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum; + NumToNode.push_back(BB); // NumToNode[n] = V; -template ::type> -unsigned DFSPass(NodePtr V, DomTreeBuilder::SemiNCAInfo &SNCA, unsigned N) { - using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo; - df_iterator_dom_storage DFStorage( - SNCA.NodeToInfo); - - for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage); - I != E; ++I) { - NodePtr BB = *I; - 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 = SNCA.NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum; - SNCA.NumToNode.push_back(BB); // NumToNode[n] = V; - } - return N; -} + if (IsChildOfArtificialExit) + BBInfo.Parent = 1; -template ::type> -NodePtr Eval(NodePtr VIn, DomTreeBuilder::SemiNCAInfo &SNCA, - unsigned LastLinked) { - auto &VInInfo = SNCA.NodeToInfo[VIn]; - if (VInInfo.DFSNum < LastLinked) - return VIn; - - SmallVector Work; - SmallPtrSet Visited; - - if (VInInfo.Parent >= LastLinked) - Work.push_back(VIn); - - while (!Work.empty()) { - NodePtr V = Work.back(); - 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; + IsChildOfArtificialExit = false; } - Work.pop_back(); - - // Update VInfo based on Ancestor info - if (VInfo.Parent < LastLinked) - continue; - - auto &VAInfo = SNCA.NodeToInfo[VAncestor]; - NodePtr VAncestorLabel = VAInfo.Label; - NodePtr VLabel = VInfo.Label; - if (SNCA.NodeToInfo[VAncestorLabel].Semi < SNCA.NodeToInfo[VLabel].Semi) - VInfo.Label = VAncestorLabel; - VInfo.Parent = VAInfo.Parent; + return N; } - return VInInfo.Label; -} + unsigned runDFS(NodePtr V, unsigned N) { + auto DFStorage = getStorage(); -template -void Calculate(DominatorTreeBaseByGraphTraits> &DT, - FuncT &F) { - using GraphT = GraphTraits; - using NodePtr = typename GraphT::NodeRef; - static_assert(std::is_pointer::value, - "NodePtr should be a pointer type"); - using NodeType = typename std::remove_pointer::type; + for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage); + I != E; ++I) { + NodePtr BB = *I; + auto &BBInfo = 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 = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum; + NumToNode.push_back(BB); // NumToNode[n] = V; + } + return N; + } - unsigned N = 0; - DomTreeBuilder::SemiNCAInfo SNCA(DT); - SNCA.NumToNode.push_back(nullptr); - - bool MultipleRoots = (DT.Roots.size() > 1); - if (MultipleRoots) { - auto &BBInfo = SNCA.NodeToInfo[nullptr]; - BBInfo.DFSNum = BBInfo.Semi = ++N; - BBInfo.Label = nullptr; + NodePtr eval(NodePtr VIn, unsigned LastLinked) { + auto &VInInfo = NodeToInfo[VIn]; + if (VInInfo.DFSNum < LastLinked) + return VIn; - SNCA.NumToNode.push_back(nullptr); // NumToNode[n] = V; - } + SmallVector Work; + SmallPtrSet Visited; - // 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(DT.Roots.size()); - i != e; ++i) - N = ReverseDFSPass(DT.Roots[i], SNCA, N); - } else { - N = DFSPass(DT.Roots[0], SNCA, N); - } + if (VInInfo.Parent >= LastLinked) + Work.push_back(VIn); - // 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::size(&F)); - - // Initialize IDoms to spanning tree parents. - for (unsigned i = 1; i <= N; ++i) { - const NodePtr V = SNCA.NumToNode[i]; - auto &VInfo = SNCA.NodeToInfo[V]; - VInfo.IDom = SNCA.NumToNode[VInfo.Parent]; - } + while (!Work.empty()) { + NodePtr V = Work.back(); + auto &VInfo = NodeToInfo[V]; + NodePtr VAncestor = NumToNode[VInfo.Parent]; - // Step #2: Calculate the semidominators of all vertices. - for (unsigned i = N; i >= 2; --i) { - 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(W)) - if (SNCA.NodeToInfo.count(N)) { // Only if this predecessor is reachable! - unsigned SemiU = SNCA.NodeToInfo[Eval(N, SNCA, i + 1)].Semi; - if (SemiU < WInfo.Semi) - WInfo.Semi = SemiU; + // Process Ancestor first + if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) { + Work.push_back(VAncestor); + continue; } - } - + Work.pop_back(); - // 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 = SNCA.NumToNode[i]; - auto &WInfo = SNCA.NodeToInfo[W]; - const unsigned SDomNum = SNCA.NodeToInfo[SNCA.NumToNode[WInfo.Semi]].DFSNum; - NodePtr WIDomCandidate = WInfo.IDom; - while (SNCA.NodeToInfo[WIDomCandidate].DFSNum > SDomNum) - WIDomCandidate = SNCA.NodeToInfo[WIDomCandidate].IDom; + // Update VInfo based on Ancestor info + if (VInfo.Parent < LastLinked) + continue; + + auto &VAInfo = NodeToInfo[VAncestor]; + NodePtr VAncestorLabel = VAInfo.Label; + NodePtr VLabel = VInfo.Label; + if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi) + VInfo.Label = VAncestorLabel; + VInfo.Parent = VAInfo.Parent; + } - WInfo.IDom = WIDomCandidate; + return VInInfo.Label; } - if (DT.Roots.empty()) return; + template + void runSemiNCA(unsigned NumBlocks) { + unsigned N = 0; + NumToNode.push_back(nullptr); - // 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; + bool MultipleRoots = (DT.Roots.size() > 1); + if (MultipleRoots) { + auto &BBInfo = NodeToInfo[nullptr]; + BBInfo.DFSNum = BBInfo.Semi = ++N; + BBInfo.Label = nullptr; - DT.RootNode = - (DT.DomTreeNodes[Root] = - llvm::make_unique>(Root, nullptr)) - .get(); + NumToNode.push_back(nullptr); // NumToNode[n] = V; + } - // Loop over all of the reachable blocks in the function... - for (unsigned i = 2; i <= N; ++i) { - NodePtr W = SNCA.NumToNode[i]; + // 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(DT.Roots.size()); + i != e; ++i) + N = runReverseDFS(DT.Roots[i], N); + } else { + N = runDFS(DT.Roots[0], N); + } - // Don't replace this with 'count', the insertion side effect is important - if (DT.DomTreeNodes[W]) - continue; // Haven't calculated this node yet? + // 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 != NumBlocks); + + // Initialize IDoms to spanning tree parents. + for (unsigned i = 1; i <= N; ++i) { + const NodePtr V = NumToNode[i]; + auto &VInfo = NodeToInfo[V]; + VInfo.IDom = NumToNode[VInfo.Parent]; + } - NodePtr ImmDom = SNCA.getIDom(W); + // Step #2: Calculate the semidominators of all vertices. + for (unsigned i = N; i >= 2; --i) { + NodePtr W = NumToNode[i]; + auto &WInfo = NodeToInfo[W]; + + // Initialize the semi dominator to point to the parent node. + WInfo.Semi = WInfo.Parent; + for (const auto &N : inverse_children(W)) + if (NodeToInfo.count(N)) { // Only if this predecessor is reachable! + unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi; + if (SemiU < WInfo.Semi) + WInfo.Semi = SemiU; + } + } - assert(ImmDom || DT.DomTreeNodes[nullptr]); + // 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]; + auto &WInfo = NodeToInfo[W]; + const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum; + NodePtr WIDomCandidate = WInfo.IDom; + while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum) + WIDomCandidate = NodeToInfo[WIDomCandidate].IDom; - // Get or calculate the node for the immediate dominator - DomTreeNodeBase *IDomNode = SNCA.getNodeForBlock(ImmDom); + WInfo.IDom = WIDomCandidate; + } - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DT.DomTreeNodes[W] = IDomNode->addChild( - llvm::make_unique>(W, IDomNode)); + 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>(Root, nullptr)) + .get(); + + // Loop over all of the reachable blocks in the function... + for (unsigned i = 2; i <= N; ++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 = getIDom(W); + + assert(ImmDom || DT.DomTreeNodes[nullptr]); + + // Get or calculate the node for the immediate dominator + TreeNodePtr IDomNode = 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>(W, IDomNode)); + } + + DT.updateDFSNumbers(); } +}; +} // namespace DomTreeBuilder + +template +void Calculate(DominatorTreeBaseByGraphTraits> &DT, + FuncT &F) { + using NodePtr = typename GraphTraits::NodeRef; + static_assert(std::is_pointer::value, + "NodePtr should be a pointer type"); - DT.updateDFSNumbers(); + DomTreeBuilder::SemiNCAInfo::type> + SNCA(DT); + SNCA.template runSemiNCA(GraphTraits::size(&F)); } -} // namespace DomTreeBuilder +} // namespace llvm #endif