Index: llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h @@ -32,6 +32,20 @@ namespace llvm { namespace DomTreeBuilder { +template +struct ChildrenGetter { + static auto Get(NodePtr N) -> decltype(reverse(children(N))) { + return reverse(children(N)); + } +}; + +template +struct ChildrenGetter { + static auto Get(NodePtr N) -> decltype(inverse_children(N)) { + return inverse_children(N); + } +}; + // Information record used by Semi-NCA during tree construction. template struct SemiNCAInfo { @@ -45,6 +59,7 @@ unsigned Semi = 0; NodePtr Label = nullptr; NodePtr IDom = nullptr; + SmallVector ReverseChildren; }; std::vector NumToNode; @@ -79,67 +94,50 @@ .get(); } - // 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; - }; + static bool AlwaysDescend(NodePtr, NodePtr) { return true; } - df_iterator_dom_storage getStorage() { return {NodeToInfo}; } + // 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 + unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, + unsigned AttachToNum) { + assert(V); + SmallVector WorkList = {V}; + if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum; - unsigned runReverseDFS(NodePtr V, unsigned N) { - auto DFStorage = getStorage(); - - bool IsChildOfArtificialExit = (N != 0); - for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage); - I != E; ++I) { - NodePtr BB = *I; + while (!WorkList.empty()) { + const NodePtr BB = WorkList.pop_back_val(); 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; - if (IsChildOfArtificialExit) - BBInfo.Parent = 1; + // Visited nodes always have positive DFS numbers. + if (BBInfo.DFSNum != 0) continue; + BBInfo.DFSNum = BBInfo.Semi = ++LastNum; + BBInfo.Label = BB; + NumToNode.push_back(BB); - IsChildOfArtificialExit = false; - } - return N; - } + for (const NodePtr Succ : ChildrenGetter::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; + } - unsigned runForwardDFS(NodePtr V, unsigned N) { - auto DFStorage = getStorage(); + if (!Condition(BB, Succ)) continue; - 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; + // It's fine to add Succ to the map, because we know that it will be + // visited later. + auto &SuccInfo = NodeToInfo[Succ]; + WorkList.push_back(Succ); + SuccInfo.Parent = LastNum; + SuccInfo.ReverseChildren.push_back(BB); + } } - return N; - } + + return LastNum; + }; NodePtr eval(NodePtr VIn, unsigned LastLinked) { auto &VInInfo = NodeToInfo[VIn]; @@ -181,31 +179,14 @@ template void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) { - unsigned N = 0; - NumToNode.push_back(nullptr); - - bool MultipleRoots = (DT.Roots.size() > 1); - if (MultipleRoots) { - auto &BBInfo = NodeToInfo[nullptr]; - BBInfo.DFSNum = BBInfo.Semi = ++N; - BBInfo.Label = nullptr; - - 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(DT.Roots.size()); - i != e; ++i) - N = runReverseDFS(DT.Roots[i], N); - } else { - N = runForwardDFS(DT.Roots[0], N); - } + const unsigned N = doFullDFSWalk(DT, AlwaysDescend); // 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); + const bool MultipleRoots = + DT.Roots.size() > 1 || (DT.isPostDominator() && N != NumBlocks); // Initialize IDoms to spanning tree parents. for (unsigned i = 1; i <= N; ++i) { @@ -221,7 +202,7 @@ // Initialize the semi dominator to point to the parent node. WInfo.Semi = WInfo.Parent; - for (const auto &N : inverse_children(W)) + for (const auto &N : WInfo.ReverseChildren) if (NodeToInfo.count(N)) { // Only if this predecessor is reachable! unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi; if (SemiU < WInfo.Semi) @@ -279,14 +260,27 @@ } } - void doFullDFSWalk(const DomTreeT &DT) { - NumToNode.push_back(nullptr); + template + unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { unsigned Num = 0; - for (auto *Root : DT.Roots) - if (!DT.isPostDominator()) - Num = runForwardDFS(Root, Num); - else - Num = runReverseDFS(Root, Num); + NumToNode.push_back(nullptr); + + if (DT.Roots.size() > 1) { + 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(Root, Num, DC, 1); + } else { + assert(DT.Roots.size() == 1); + Num = runDFS(DT.Roots[0], Num, DC, Num); + } + + return Num; } static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) { @@ -299,7 +293,7 @@ // Checks if the tree contains all reachable nodes in the input graph. bool verifyReachability(const DomTreeT &DT) { clear(); - doFullDFSWalk(DT); + doFullDFSWalk(DT, AlwaysDescend); for (auto &NodeToTN : DT.DomTreeNodes) { const TreeNodePtr TN = NodeToTN.second.get(); @@ -356,7 +350,7 @@ // NCD(From, To) == IDom(To) or To. bool verifyNCD(const DomTreeT &DT) { clear(); - doFullDFSWalk(DT); + doFullDFSWalk(DT, AlwaysDescend); for (auto &BlockToInfo : NodeToInfo) { auto &Info = BlockToInfo.second; @@ -440,8 +434,9 @@ if (!BB || TN->getChildren().empty()) continue; clear(); - NodeToInfo.insert({BB, {}}); - doFullDFSWalk(DT); + doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) { + return From != BB && To != BB; + }); for (TreeNodePtr Child : TN->getChildren()) if (NodeToInfo.count(Child->getBlock()) != 0) { @@ -473,8 +468,10 @@ const auto &Siblings = TN->getChildren(); for (const TreeNodePtr N : Siblings) { clear(); - NodeToInfo.insert({N->getBlock(), {}}); - doFullDFSWalk(DT); + NodePtr BBN = N->getBlock(); + doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) { + return From != BBN && To != BBN; + }); for (const TreeNodePtr S : Siblings) { if (S == N) continue;