Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -770,24 +770,12 @@ /// recalculate - compute a dominator tree for the given function template void recalculate(FT &F) { - typedef GraphTraits TraitsTy; reset(); this->Vertex.push_back(nullptr); if (!this->IsPostDominators) { - // Initialize root - NodeT *entry = TraitsTy::getEntryNode(&F); - addRoot(entry); - Calculate(*this, F); } else { - // Initialize the roots list - for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), - E = TraitsTy::nodes_end(&F); - I != E; ++I) - if (TraitsTy::child_begin(*I) == TraitsTy::child_end(*I)) - addRoot(*I); - Calculate>(*this, F); } } Index: include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- include/llvm/Support/GenericDomTreeConstruction.h +++ include/llvm/Support/GenericDomTreeConstruction.h @@ -25,6 +25,7 @@ #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/GenericDomTree.h" @@ -39,8 +40,10 @@ df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {} typedef typename BaseSet::iterator iterator; - std::pair insert(NodeRef N) { - return Storage.insert({N, InfoType()}); + std::pair insert(NodeRef To) { + auto Result = Storage.insert({To, InfoType()}); + + return Result; } void completed(NodeRef) {} @@ -55,7 +58,6 @@ typename GraphT::NodeRef, typename DominatorTreeBaseByGraphTraits::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; @@ -67,11 +69,6 @@ if (I.getPathLength() > 1) BBInfo.Parent = DT.Info[I.getPath(I.getPathLength() - 2)].DFSNum; DT.Vertex.push_back(BB); // Vertex[n] = V; - - if (IsChildOfArtificialExit) - BBInfo.Parent = 1; - - IsChildOfArtificialExit = false; } return N; } @@ -142,34 +139,78 @@ void Calculate(DominatorTreeBaseByGraphTraits> &DT, FuncT &F) { typedef GraphTraits GraphT; + typedef GraphTraits FuncGraphT; static_assert(std::is_pointer::value, "NodeRef should be pointer type"); typedef typename std::remove_pointer::type NodeType; unsigned N = 0; - bool MultipleRoots = (DT.Roots.size() > 1); - if (MultipleRoots) { + bool NeedFakeRoot = DT.isPostDominator(); + // If this is post dominators, push a fake node to start + if (NeedFakeRoot) { auto &BBInfo = DT.Info[nullptr]; BBInfo.DFSNum = BBInfo.Semi = ++N; BBInfo.Label = nullptr; - - DT.Vertex.push_back(nullptr); // Vertex[n] = V; + DT.Vertex.push_back(nullptr); // Vertex[n] = V; + } else { + // The root is the entry block of the CFG + DT.addRoot(FuncGraphT::getEntryNode(&F)); } // 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, DT.Roots[i], N); + if (DT.isPostDominator()) { + unsigned Total = 0; + for (auto I = FuncGraphT::nodes_begin(&F), E = FuncGraphT::nodes_end(&F); + I != E; ++I) { + ++Total; + // If it has no *successors*, it is definitely a root. + if (FuncGraphT::child_begin(*I) == FuncGraphT::child_end(*I)) { + N = ReverseDFSPass(DT, *I, N); + DT.Info[*I].Parent = 1; + DT.addRoot(*I); + } + } + // Accounting for the virtual exit, see if we had any unreachable nodes + if (Total + 1 != N ) { + // Make another DFS pass over all other nodes to find the unreachable + // blocks, and find the furthest paths we'll be able to make. block. + // Note that this looks N^2, but it's really 2N worst case, if every node + // is unreachable. This is because we are still going to only visit each + // unreachable node once, we may just visit it in two directions, + // depending on how lucky we get. + SmallPtrSet ConnectToExitBlock; + for (auto I = FuncGraphT::nodes_begin(&F), E = FuncGraphT::nodes_end(&F); + I != E; ++I) + if (!DT.Info.count(*I)) { + // Find the furthest away we can get by following successors, then + // follow them in reverse. This gives us some reasonable answer about + // the post-dom tree inside any infinite loop. In particular, it + // guarantees we get to the farthest away point along *some* + // path. This also matches GCC behavior. If we really wanted a + // totally complete picture of dominance inside this infinite loop, we + // could do it with SCC-like algorithms to find the lowest and highest + // points in the infinite loop. + auto *FurthestAway = *po_begin(*I); + ConnectToExitBlock.insert(FurthestAway); + N = ReverseDFSPass(DT, FurthestAway, N); + } + // Finally, now everything should be visited, and anything with parent == + // 0 should be connected to virtual exit. + for (auto *Node : ConnectToExitBlock) { + auto FindResult = DT.Info.find(Node); + assert(FindResult != DT.Info.end() && + "Everything should have been visited by now"); + if (FindResult->second.Parent == 0) { + FindResult->second.Parent = 1; + DT.addRoot(Node); + } + } + } } else { - N = DFSPass(DT, DT.Roots[0], N); + N = DFSPass(DT, GraphTraits::getEntryNode(&F), 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::size(&F)); - // When naively implemented, the Lengauer-Tarjan algorithm requires a separate // bucket for each vertex. However, this is unnecessary, because each vertex // is only placed into a single bucket (that of its semidominator), and each @@ -200,12 +241,13 @@ // initialize the semi dominator to point to the parent node WInfo.Semi = WInfo.Parent; - typedef GraphTraits > InvTraits; - for (typename InvTraits::ChildIteratorType CI = - InvTraits::child_begin(W), - E = InvTraits::child_end(W); CI != E; ++CI) { + typedef GraphTraits> InvTraits; + for (typename InvTraits::ChildIteratorType CI = InvTraits::child_begin(W), + E = InvTraits::child_end(W); + CI != E; ++CI) { typename InvTraits::NodeRef N = *CI; - if (DT.Info.count(N)) { // Only if this predecessor is reachable! + // Only if this predecessor is reachable. + if (DT.Info.count(N)) { unsigned SemiU = DT.Info[Eval(DT, N, i + 1)].Semi; if (SemiU < WInfo.Semi) WInfo.Semi = SemiU; @@ -239,13 +281,14 @@ WIDom = DT.IDoms[WIDom]; } - if (DT.Roots.empty()) return; + // Detect how many roots we need by checking which things ended up with null + // idoms. // 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. - typename GraphT::NodeRef Root = !MultipleRoots ? DT.Roots[0] : nullptr; + typename GraphT::NodeRef Root = NeedFakeRoot ? nullptr : DT.Roots[0]; DT.RootNode = (DT.DomTreeNodes[Root] =