Index: include/llvm/ADT/GraphTraits.h =================================================================== --- include/llvm/ADT/GraphTraits.h +++ include/llvm/ADT/GraphTraits.h @@ -51,6 +51,7 @@ // static unsigned size (GraphType *G) // Return total number of nodes in the graph // + // static bool isExit(NodeRef); // If anyone tries to use this class without having an appropriate @@ -63,6 +64,11 @@ typedef typename GraphType::UnknownGraphTypeError NodeRef; }; +template +bool isExit(GraphType Node) { + typedef GraphTraits GraphT; + return GraphT::child_begin(Node) == GraphT::child_end(Node); +} // Inverse - This class is used as a little marker class to tell the graph // iterator to iterate over the graph in a graph defined "Inverse" ordering. Index: include/llvm/Analysis/RegionInfoImpl.h =================================================================== --- include/llvm/Analysis/RegionInfoImpl.h +++ include/llvm/Analysis/RegionInfoImpl.h @@ -618,6 +618,9 @@ unsigned num_successors = BlockTraits::child_end(entry) - BlockTraits::child_begin(entry); + if (num_successors == 0) + return true; + if (num_successors <= 1 && exit == *(BlockTraits::child_begin(entry))) return true; Index: include/llvm/IR/CFG.h =================================================================== --- include/llvm/IR/CFG.h +++ include/llvm/IR/CFG.h @@ -21,6 +21,7 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" #include "llvm/Support/type_traits.h" @@ -178,6 +179,14 @@ static ChildIteratorType child_end(NodeRef N) { return succ_end(N); } }; + +template <> +inline bool isExit(BasicBlock *Node) { + typedef GraphTraits GraphT; + return GraphT::child_begin(Node) == GraphT::child_end(Node) + && !isa(Node->getTerminator()); +} + // Provide specializations of GraphTraits to be able to treat a function as a // graph of basic blocks... and to walk it in inverse order. Inverse order for // a function is considered to be when traversing the predecessor edges of a BB Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -778,22 +778,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: 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,88 @@ 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 : nodes(&F)) { + ++Total; + // If it has no *successors*, it is definitely a root. + if (isExit(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. + std::map BlocksToConnect; + 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); + NodeType *ConnectionPoint = nullptr; + for (auto Child : children(I)) + if (DT.Info.count(Child)) + ConnectionPoint = Child; + + BlocksToConnect[FurthestAway] = ConnectionPoint; + N = ReverseDFSPass(DT, FurthestAway, N); + } + // Finally, now everything should be visited, and anything with parent == + // 0 should be connected to virtual exit. + for (auto Pair : BlocksToConnect) { + auto *Node = Pair.first; + auto *Prev = Pair.second; + auto FindResult = DT.Info.find(Node); + assert(FindResult != DT.Info.end() && + "Everything should have been visited by now"); + if (FindResult->second.Parent == 0) { + if (DT.Info.count(Prev)) { + FindResult->second.Parent = DT.Info[Prev].DFSNum; + } else { + 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 @@ -234,13 +285,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: lib/Transforms/Scalar/ADCE.cpp =================================================================== --- lib/Transforms/Scalar/ADCE.cpp +++ 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: test/Analysis/PostDominators/pr24415.ll =================================================================== --- /dev/null +++ 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 + +;