Index: llvm/trunk/include/llvm/Support/GenericDomTree.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTree.h +++ llvm/trunk/include/llvm/Support/GenericDomTree.h @@ -770,22 +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 (auto *Node : nodes(&F)) - if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node)) - addRoot(Node); - Calculate>(*this, F); } } Index: llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/trunk/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); - } else { - N = DFSPass(DT, DT.Roots[0], N); + if (DT.isPostDominator()) { + unsigned Total = 0; + for (auto I : nodes(&F)) { + ++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. + // 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 : nodes(&F)) + 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. In theory, it would be nice to give + // the canonical backedge for the loop, but it's expensive. + 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, 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 @@ -234,13 +275,11 @@ WIDom = DT.IDoms[WIDom]; } - 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. - typename GraphT::NodeRef Root = !MultipleRoots ? DT.Roots[0] : nullptr; + typename GraphT::NodeRef Root = NeedFakeRoot ? nullptr : DT.Roots[0]; DT.RootNode = (DT.DomTreeNodes[Root] = Index: llvm/trunk/lib/Transforms/Scalar/ADCE.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/ADCE.cpp +++ llvm/trunk/lib/Transforms/Scalar/ADCE.cpp @@ -253,46 +253,23 @@ } } - // Mark blocks live if there is no path from the block to the - // return of the function or a successor for which this is true. - // This protects IDFCalculator which cannot handle such blocks. - for (auto &BBInfoPair : BlockInfo) { - auto &BBInfo = BBInfoPair.second; - if (BBInfo.terminatorIsLive()) - continue; - auto *BB = BBInfo.BB; - if (!PDT.getNode(BB)) { - markLive(BBInfo.Terminator); - continue; - } - for (auto *Succ : successors(BB)) - if (!PDT.getNode(Succ)) { - markLive(BBInfo.Terminator); - break; - } - } - - // Mark blocks live if there is no path from the block to the - // return of the function or a successor for which this is true. - // This protects IDFCalculator which cannot handle such blocks. - for (auto &BBInfoPair : BlockInfo) { - auto &BBInfo = BBInfoPair.second; - if (BBInfo.terminatorIsLive()) - continue; - auto *BB = BBInfo.BB; - if (!PDT.getNode(BB)) { - DEBUG(dbgs() << "Not post-dominated by return: " << BB->getName() + // Mark blocks live if there is no path from the block to a + // return of the function. + // We do this by seeing which of the postdomtree root children exit the + // program, and for all others, mark the subtree live. + for (auto &PDTChild : children(PDT.getRootNode())) { + auto *BB = PDTChild->getBlock(); + auto &Info = BlockInfo[BB]; + // Real function return + if (isa(Info.Terminator)) { + DEBUG(dbgs() << "post-dom root child is not a return: " << BB->getName() << '\n';); - markLive(BBInfo.Terminator); continue; } - for (auto *Succ : successors(BB)) - if (!PDT.getNode(Succ)) { - DEBUG(dbgs() << "Successor not post-dominated by return: " - << BB->getName() << '\n';); - markLive(BBInfo.Terminator); - break; - } + + // This child is something else, like an infinite loop. + for (auto DFNode : depth_first(PDTChild)) + markLive(BlockInfo[DFNode->getBlock()].Terminator); } // Treat the entry block as always live Index: llvm/trunk/test/Analysis/PostDominators/pr24415.ll =================================================================== --- llvm/trunk/test/Analysis/PostDominators/pr24415.ll +++ llvm/trunk/test/Analysis/PostDominators/pr24415.ll @@ -0,0 +1,18 @@ +; RUN: opt < %s -postdomtree -analyze | FileCheck %s +; RUN: opt < %s -passes='print' 2>&1 | FileCheck %s + +; Function Attrs: nounwind ssp uwtable +define void @foo() { + br label %1 + +;