Index: llvm/trunk/include/llvm/Analysis/CGSCCPassManager.h =================================================================== --- llvm/trunk/include/llvm/Analysis/CGSCCPassManager.h +++ llvm/trunk/include/llvm/Analysis/CGSCCPassManager.h @@ -334,6 +334,7 @@ InvalidSCCSet, nullptr, nullptr}; PreservedAnalyses PA = PreservedAnalyses::all(); + CG.buildRefSCCs(); for (auto RCI = CG.postorder_ref_scc_begin(), RCE = CG.postorder_ref_scc_end(); RCI != RCE;) { Index: llvm/trunk/include/llvm/Analysis/LazyCallGraph.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LazyCallGraph.h +++ llvm/trunk/include/llvm/Analysis/LazyCallGraph.h @@ -794,14 +794,10 @@ /// A post-order depth-first RefSCC iterator over the call graph. /// - /// This iterator triggers the Tarjan DFS-based formation of the RefSCC (and - /// SCC) DAG for the call graph, walking it lazily in depth-first post-order. - /// That is, it always visits RefSCCs for the target of a reference edge - /// prior to visiting the RefSCC for a source of the edge (when they are in - /// different RefSCCs). - /// - /// When forming each RefSCC, the call edges within it are used to form SCCs - /// within it, so iterating this also controls the lazy formation of SCCs. + /// This iterator walks the cached post-order sequence of RefSCCs. However, + /// it trades stability for flexibility. It is restricted to a forward + /// iterator but will survive mutations which insert new RefSCCs and continue + /// to point to the same RefSCC even if it moves in the post-order sequence. class postorder_ref_scc_iterator : public iterator_facade_base { @@ -825,12 +821,9 @@ /// populating it if necessary. static RefSCC *getRC(LazyCallGraph &G, int Index) { if (Index == (int)G.PostOrderRefSCCs.size()) - if (!G.buildNextRefSCCInPostOrder()) - // We're at the end. - return nullptr; + // We're at the end. + return nullptr; - assert(Index < (int)G.PostOrderRefSCCs.size() && - "Built the next post-order RefSCC without growing list!"); return G.PostOrderRefSCCs[Index]; } @@ -866,10 +859,18 @@ return edge_iterator(EntryEdges.end(), EntryEdges.end()); } + void buildRefSCCs(); + postorder_ref_scc_iterator postorder_ref_scc_begin() { + if (!EntryEdges.empty()) + assert(!PostOrderRefSCCs.empty() && + "Must form RefSCCs before iterating them!"); return postorder_ref_scc_iterator(*this); } postorder_ref_scc_iterator postorder_ref_scc_end() { + if (!EntryEdges.empty()) + assert(!PostOrderRefSCCs.empty() && + "Must form RefSCCs before iterating them!"); return postorder_ref_scc_iterator(*this, postorder_ref_scc_iterator::IsAtEndT()); } @@ -1045,18 +1046,6 @@ /// These are all of the RefSCCs which have no children. SmallVector LeafRefSCCs; - /// Stack of nodes in the DFS walk. - SmallVector, 4> DFSStack; - - /// Set of entry nodes not-yet-processed into RefSCCs. - SmallVector RefSCCEntryNodes; - - /// Stack of nodes the DFS has walked but not yet put into a RefSCC. - SmallVector PendingRefSCCStack; - - /// Counter for the next DFS number to assign. - int NextDFSNumber; - /// Helper to insert a new function, with an already looked-up entry in /// the NodeMap. Node &insertInto(Function &F, Node *&MappedN); @@ -1078,6 +1067,23 @@ return new (RefSCCBPA.Allocate()) RefSCC(std::forward(Args)...); } + /// Common logic for building SCCs from a sequence of roots. + /// + /// This is a very generic implementation of the depth-first walk and SCC + /// formation algorithm. It uses a generic sequence of roots and generic + /// callbacks for each step. This is designed to be used to implement both + /// the RefSCC formation and SCC formation with shared logic. + /// + /// Currently this is a relatively naive implementation of Tarjan's DFS + /// algorithm to form the SCCs. + /// + /// FIXME: We should consider newer variants such as Nuutila. + template + static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin, + GetEndT &&GetEnd, GetNodeT &&GetNode, + FormSCCCallbackT &&FormSCC); + /// Build the SCCs for a RefSCC out of a list of nodes. void buildSCCs(RefSCC &RC, node_stack_range Nodes); @@ -1098,13 +1104,6 @@ "Index does not point back at RC!"); return IndexIt->second; } - - /// Builds the next node in the post-order RefSCC walk of the call graph and - /// appends it to the \c PostOrderRefSCCs vector. - /// - /// Returns true if a new RefSCC was successfully constructed, and false if - /// there are no more RefSCCs to build in the graph. - bool buildNextRefSCCInPostOrder(); }; inline LazyCallGraph::Edge::Edge() : Value() {} Index: llvm/trunk/lib/Analysis/CGSCCPassManager.cpp =================================================================== --- llvm/trunk/lib/Analysis/CGSCCPassManager.cpp +++ llvm/trunk/lib/Analysis/CGSCCPassManager.cpp @@ -117,6 +117,7 @@ PA.allAnalysesInSetPreserved>(); // Ok, we have a graph, so we can propagate the invalidation down into it. + G->buildRefSCCs(); for (auto &RC : G->postorder_ref_sccs()) for (auto &C : RC) { Optional InnerPA; Index: llvm/trunk/lib/Analysis/LazyCallGraph.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyCallGraph.cpp +++ llvm/trunk/lib/Analysis/LazyCallGraph.cpp @@ -18,6 +18,7 @@ #include "llvm/IR/PassManager.h" #include "llvm/Support/Debug.h" #include "llvm/Support/GraphWriter.h" +#include using namespace llvm; @@ -114,7 +115,7 @@ } #endif -LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { +LazyCallGraph::LazyCallGraph(Module &M) { DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier() << "\n"); for (Function &F : M) @@ -138,19 +139,13 @@ visitReferences(Worklist, Visited, [&](Function &F) { addEdge(EntryEdges, EntryIndexMap, F, LazyCallGraph::Edge::Ref); }); - - for (const Edge &E : EntryEdges) - RefSCCEntryNodes.push_back(&E.getFunction()); } LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)), EntryEdges(std::move(G.EntryEdges)), EntryIndexMap(std::move(G.EntryIndexMap)), SCCBPA(std::move(G.SCCBPA)), - SCCMap(std::move(G.SCCMap)), LeafRefSCCs(std::move(G.LeafRefSCCs)), - DFSStack(std::move(G.DFSStack)), - RefSCCEntryNodes(std::move(G.RefSCCEntryNodes)), - NextDFSNumber(G.NextDFSNumber) { + SCCMap(std::move(G.SCCMap)), LeafRefSCCs(std::move(G.LeafRefSCCs)) { updateGraphPtrs(); } @@ -162,9 +157,6 @@ SCCBPA = std::move(G.SCCBPA); SCCMap = std::move(G.SCCMap); LeafRefSCCs = std::move(G.LeafRefSCCs); - DFSStack = std::move(G.DFSStack); - RefSCCEntryNodes = std::move(G.RefSCCEntryNodes); - NextDFSNumber = G.NextDFSNumber; updateGraphPtrs(); return *this; } @@ -828,8 +820,10 @@ assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); assert(G->lookupRefSCC(TargetN) != this && "Target must not be in this RefSCC."); +#ifdef EXPENSIVE_CEHCKS assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && "Target must be a descendant of the Source."); +#endif // Edges between RefSCCs are the same regardless of call or ref, so we can // just flip the edge here. @@ -848,8 +842,10 @@ assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); assert(G->lookupRefSCC(TargetN) != this && "Target must not be in this RefSCC."); +#ifdef EXPENSIVE_CEHCKS assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && "Target must be a descendant of the Source."); +#endif // Edges between RefSCCs are the same regardless of call or ref, so we can // just flip the edge here. @@ -883,8 +879,10 @@ RefSCC &TargetC = *G->lookupRefSCC(TargetN); assert(&TargetC != this && "Target must not be in this RefSCC."); +#ifdef EXPENSIVE_CEHCKS assert(TargetC.isDescendantOf(*this) && "Target must be a descendant of the Source."); +#endif // The only change required is to add this SCC to the parent set of the // callee. @@ -901,8 +899,10 @@ assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); RefSCC &SourceC = *G->lookupRefSCC(SourceN); assert(&SourceC != this && "Source must not be in this RefSCC."); +#ifdef EXPENSIVE_CEHCKS assert(SourceC.isDescendantOf(*this) && "Source must be a descendant of the Target."); +#endif SmallVector DeletedRefSCCs; @@ -1454,8 +1454,10 @@ return; } +#ifdef EXPENSIVE_CEHCKS assert(TargetRC.isDescendantOf(*this) && "Target must be a descendant of the Source."); +#endif // The only change required is to add this RefSCC to the parent set of the // target. This is a set and so idempotent if the edge already existed. TargetRC.Parents.insert(this); @@ -1467,13 +1469,17 @@ // Check that the RefSCC is still valid when we finish. auto ExitVerifier = make_scope_exit([this] { verify(); }); - // Check that we aren't breaking some invariants of the SCC graph. +#ifdef EXPENSIVE_CHECKS + // Check that we aren't breaking some invariants of the SCC graph. Note that + // this is quadratic in the number of edges in the call graph! SCC &SourceC = *G->lookupSCC(SourceN); SCC &TargetC = *G->lookupSCC(TargetN); if (&SourceC != &TargetC) assert(SourceC.isAncestorOf(TargetC) && "Call edge is not trivial in the SCC graph!"); -#endif +#endif // EXPENSIVE_CHECKS +#endif // NDEBUG + // First insert it into the source or find the existing edge. auto InsertResult = SourceN.EdgeIndexMap.insert( {&TargetN.getFunction(), SourceN.Edges.size()}); @@ -1497,13 +1503,16 @@ // Check that the RefSCC is still valid when we finish. auto ExitVerifier = make_scope_exit([this] { verify(); }); +#ifdef EXPENSIVE_CHECKS // Check that we aren't breaking some invariants of the RefSCC graph. RefSCC &SourceRC = *G->lookupRefSCC(SourceN); RefSCC &TargetRC = *G->lookupRefSCC(TargetN); if (&SourceRC != &TargetRC) assert(SourceRC.isAncestorOf(TargetRC) && "Ref edge is not trivial in the RefSCC graph!"); -#endif +#endif // EXPENSIVE_CHECKS +#endif // NDEBUG + // First insert it into the source or find the existing edge. auto InsertResult = SourceN.EdgeIndexMap.insert( {&TargetN.getFunction(), SourceN.Edges.size()}); @@ -1519,14 +1528,14 @@ } void LazyCallGraph::insertEdge(Node &SourceN, Function &Target, Edge::Kind EK) { - assert(SCCMap.empty() && DFSStack.empty() && + assert(SCCMap.empty() && "This method cannot be called after SCCs have been formed!"); return SourceN.insertEdgeInternal(Target, EK); } void LazyCallGraph::removeEdge(Node &SourceN, Function &Target) { - assert(SCCMap.empty() && DFSStack.empty() && + assert(SCCMap.empty() && "This method cannot be called after SCCs have been formed!"); return SourceN.removeEdgeInternal(Target); @@ -1544,13 +1553,6 @@ EntryIndexMap.erase(EII); } - // It's safe to just remove un-visited functions from the RefSCC entry list. - // FIXME: This is a linear operation which could become hot and benefit from - // an index map. - auto RENI = find(RefSCCEntryNodes, &F); - if (RENI != RefSCCEntryNodes.end()) - RefSCCEntryNodes.erase(RENI); - auto NI = NodeMap.find(&F); if (NI == NodeMap.end()) // Not in the graph at all! @@ -1559,22 +1561,13 @@ Node &N = *NI->second; NodeMap.erase(NI); - if (SCCMap.empty() && DFSStack.empty()) { - // No SCC walk has begun, so removing this is fine and there is nothing + if (SCCMap.empty()) { + // No SCCs have been formed, so removing this is fine and there is nothing // else necessary at this point but clearing out the node. N.clear(); return; } - // Check that we aren't going to break the DFS walk. - assert(all_of(DFSStack, - [&N](const std::pair &Element) { - return Element.first != &N; - }) && - "Tried to remove a function currently in the DFS stack!"); - assert(find(PendingRefSCCStack, &N) == PendingRefSCCStack.end() && - "Tried to remove a function currently pending to add to a RefSCC!"); - // Cannot remove a function which has yet to be visited in the DFS walk, so // if we have a node at all then we must have an SCC and RefSCC. auto CI = SCCMap.find(&N); @@ -1653,34 +1646,18 @@ } } -/// Build the internal SCCs for a RefSCC from a sequence of nodes. -/// -/// Appends the SCCs to the provided vector and updates the map with their -/// indices. Both the vector and map must be empty when passed into this -/// routine. -void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) { - assert(RC.SCCs.empty() && "Already built SCCs!"); - assert(RC.SCCIndices.empty() && "Already mapped SCC indices!"); - - for (Node *N : Nodes) { - assert(N->LowLink >= (*Nodes.begin())->LowLink && - "We cannot have a low link in an SCC lower than its root on the " - "stack!"); - - // This node will go into the next RefSCC, clear out its DFS and low link - // as we scan. - N->DFSNumber = N->LowLink = 0; - } +template +void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin, + GetEndT &&GetEnd, GetNodeT &&GetNode, + FormSCCCallbackT &&FormSCC) { + typedef decltype(GetBegin(std::declval())) EdgeItT; - // Each RefSCC contains a DAG of the call SCCs. To build these, we do - // a direct walk of the call edges using Tarjan's algorithm. We reuse the - // internal storage as we won't need it for the outer graph's DFS any longer. - - SmallVector, 16> DFSStack; + SmallVector, 16> DFSStack; SmallVector PendingSCCStack; // Scan down the stack and DFS across the call edges. - for (Node *RootN : Nodes) { + for (Node *RootN : Roots) { assert(DFSStack.empty() && "Cannot begin a new root with a non-empty DFS stack!"); assert(PendingSCCStack.empty() && @@ -1696,25 +1673,23 @@ RootN->DFSNumber = RootN->LowLink = 1; int NextDFSNumber = 2; - DFSStack.push_back({RootN, RootN->call_begin()}); + DFSStack.push_back({RootN, GetBegin(*RootN)}); do { Node *N; - call_edge_iterator I; + EdgeItT I; std::tie(N, I) = DFSStack.pop_back_val(); - auto E = N->call_end(); + auto E = GetEnd(*N); while (I != E) { - Node &ChildN = *I->getNode(); + Node &ChildN = GetNode(I); if (ChildN.DFSNumber == 0) { // We haven't yet visited this child, so descend, pushing the current // node onto the stack. DFSStack.push_back({N, I}); - assert(!lookupSCC(ChildN) && - "Found a node with 0 DFS number but already in an SCC!"); ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++; N = &ChildN; - I = N->call_begin(); - E = N->call_end(); + I = GetBegin(*N); + E = GetEnd(*N); continue; } @@ -1756,20 +1731,90 @@ })); // Form a new SCC out of these nodes and then clear them off our pending // stack. - RC.SCCs.push_back(createSCC(RC, SCCNodes)); - for (Node &N : *RC.SCCs.back()) { - N.DFSNumber = N.LowLink = -1; - SCCMap[&N] = RC.SCCs.back(); - } + FormSCC(SCCNodes); PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end()); } while (!DFSStack.empty()); } +} + +/// Build the internal SCCs for a RefSCC from a sequence of nodes. +/// +/// Appends the SCCs to the provided vector and updates the map with their +/// indices. Both the vector and map must be empty when passed into this +/// routine. +void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) { + assert(RC.SCCs.empty() && "Already built SCCs!"); + assert(RC.SCCIndices.empty() && "Already mapped SCC indices!"); + + for (Node *N : Nodes) { + assert(N->LowLink >= (*Nodes.begin())->LowLink && + "We cannot have a low link in an SCC lower than its root on the " + "stack!"); + + // This node will go into the next RefSCC, clear out its DFS and low link + // as we scan. + N->DFSNumber = N->LowLink = 0; + } + + // Each RefSCC contains a DAG of the call SCCs. To build these, we do + // a direct walk of the call edges using Tarjan's algorithm. We reuse the + // internal storage as we won't need it for the outer graph's DFS any longer. + buildGenericSCCs(Nodes, [](Node &N) { return N.call_begin(); }, + [](Node &N) { return N.call_end(); }, + [](call_edge_iterator I) -> Node & { + // For SCCs, all the nodes should already be formed. + return *I->getNode(); + }, + [this, &RC](node_stack_range Nodes) { + RC.SCCs.push_back(createSCC(RC, Nodes)); + for (Node &N : *RC.SCCs.back()) { + N.DFSNumber = N.LowLink = -1; + SCCMap[&N] = RC.SCCs.back(); + } + }); // Wire up the SCC indices. for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i) RC.SCCIndices[RC.SCCs[i]] = i; } +void LazyCallGraph::buildRefSCCs() { + if (EntryEdges.empty() || !PostOrderRefSCCs.empty()) + // RefSCCs are either non-existent or already built! + return; + + assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!"); + + SmallVector Roots; + for (Edge &E : *this) + Roots.push_back(&E.getNode(*this)); + + // The roots will be popped of a stack, so use reverse to get a less + // surprising order. This doesn't change any of the semantics anywhere. + std::reverse(Roots.begin(), Roots.end()); + + buildGenericSCCs( + Roots, [](Node &N) { return N.begin(); }, [](Node &N) { return N.end(); }, + [this](edge_iterator I) -> Node & { + // Form the node if we haven't yet. + return I->getNode(*this); + }, + [this](node_stack_range Nodes) { + RefSCC *NewRC = createRefSCC(*this); + buildSCCs(*NewRC, Nodes); + connectRefSCC(*NewRC); + + // Push the new node into the postorder list and remember its position + // in the index map. + bool Inserted = + RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second; + (void)Inserted; + assert(Inserted && "Cannot already have this RefSCC in the index map!"); + PostOrderRefSCCs.push_back(NewRC); + NewRC->verify(); + }); +} + // FIXME: We should move callers of this to embed the parent linking and leaf // tracking into their DFS in order to remove a full walk of all edges. void LazyCallGraph::connectRefSCC(RefSCC &RC) { @@ -1794,106 +1839,6 @@ LeafRefSCCs.push_back(&RC); } -bool LazyCallGraph::buildNextRefSCCInPostOrder() { - if (DFSStack.empty()) { - Node *N; - do { - // If we've handled all candidate entry nodes to the SCC forest, we're - // done. - if (RefSCCEntryNodes.empty()) - return false; - - N = &get(*RefSCCEntryNodes.pop_back_val()); - } while (N->DFSNumber != 0); - - // Found a new root, begin the DFS here. - N->LowLink = N->DFSNumber = 1; - NextDFSNumber = 2; - DFSStack.push_back({N, N->begin()}); - } - - for (;;) { - Node *N; - edge_iterator I; - std::tie(N, I) = DFSStack.pop_back_val(); - - assert(N->DFSNumber > 0 && "We should always assign a DFS number " - "before placing a node onto the stack."); - - auto E = N->end(); - while (I != E) { - Node &ChildN = I->getNode(*this); - if (ChildN.DFSNumber == 0) { - // We haven't yet visited this child, so descend, pushing the current - // node onto the stack. - DFSStack.push_back({N, N->begin()}); - - assert(!SCCMap.count(&ChildN) && - "Found a node with 0 DFS number but already in an SCC!"); - ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; - N = &ChildN; - I = N->begin(); - E = N->end(); - continue; - } - - // If the child has already been added to some child component, it - // couldn't impact the low-link of this parent because it isn't - // connected, and thus its low-link isn't relevant so skip it. - if (ChildN.DFSNumber == -1) { - ++I; - continue; - } - - // Track the lowest linked child as the lowest link for this node. - assert(ChildN.LowLink > 0 && "Must have a positive low-link number!"); - if (ChildN.LowLink < N->LowLink) - N->LowLink = ChildN.LowLink; - - // Move to the next edge. - ++I; - } - - // We've finished processing N and its descendents, put it on our pending - // SCC stack to eventually get merged into an SCC of nodes. - PendingRefSCCStack.push_back(N); - - // If this node is linked to some lower entry, continue walking up the - // stack. - if (N->LowLink != N->DFSNumber) { - assert(!DFSStack.empty() && - "We never found a viable root for an SCC to pop off!"); - continue; - } - - // Otherwise, form a new RefSCC from the top of the pending node stack. - int RootDFSNumber = N->DFSNumber; - // Find the range of the node stack by walking down until we pass the - // root DFS number. - auto RefSCCNodes = node_stack_range( - PendingRefSCCStack.rbegin(), - find_if(reverse(PendingRefSCCStack), [RootDFSNumber](const Node *N) { - return N->DFSNumber < RootDFSNumber; - })); - // Form a new RefSCC out of these nodes and then clear them off our pending - // stack. - RefSCC *NewRC = createRefSCC(*this); - buildSCCs(*NewRC, RefSCCNodes); - connectRefSCC(*NewRC); - PendingRefSCCStack.erase(RefSCCNodes.end().base(), - PendingRefSCCStack.end()); - - // Push the new node into the postorder list and return true indicating we - // successfully grew the postorder sequence by one. - bool Inserted = - RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second; - (void)Inserted; - assert(Inserted && "Cannot already have this RefSCC in the index map!"); - PostOrderRefSCCs.push_back(NewRC); - return true; - } -} - AnalysisKey LazyCallGraphAnalysis::Key; LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {} @@ -1935,6 +1880,7 @@ for (Function &F : M) printNode(OS, G.get(F)); + G.buildRefSCCs(); for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs()) printRefSCC(OS, C); Index: llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp +++ llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp @@ -300,6 +300,7 @@ EXPECT_EQ("d1", D3.begin()->getFunction().getName()); // Now lets look at the RefSCCs and SCCs. + CG.buildRefSCCs(); auto J = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &D = *J++; @@ -444,6 +445,7 @@ std::vector Nodes; // We should build a single RefSCC for the entire graph. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; EXPECT_EQ(CG.postorder_ref_scc_end(), I); @@ -528,6 +530,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; EXPECT_EQ(CG.postorder_ref_scc_end(), I); @@ -578,6 +581,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) dbgs() << "Formed RefSCC: " << RC << "\n"; @@ -723,6 +727,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) dbgs() << "Formed RefSCC: " << RC << "\n"; @@ -805,102 +810,6 @@ EXPECT_EQ(++I, E); } -TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { - LLVMContext Context; - // This is the same fundamental test as the previous, but we perform it - // having only partially walked the RefSCCs of the graph. - std::unique_ptr M = parseAssembly(Context, DiamondOfTriangles); - LazyCallGraph CG(*M); - - // Walk the RefSCCs until we find the one containing 'c1'. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); - LazyCallGraph::RefSCC &DRC = *I; - ASSERT_NE(&DRC, nullptr); - ++I; - ASSERT_NE(I, E); - LazyCallGraph::RefSCC &CRC = *I; - ASSERT_NE(&CRC, nullptr); - - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); - LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); - LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); - LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); - LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); - LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); - LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); - - auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); - // Make sure we connected the nodes. - for (LazyCallGraph::Edge E : D2) { - if (E.getNode() == &D3) - continue; - EXPECT_EQ(&C2, E.getNode()); - } - // And marked the D ref-SCC as no longer valid. - EXPECT_EQ(1u, MergedRCs.size()); - EXPECT_EQ(&DRC, MergedRCs[0]); - - // Make sure we have the correct nodes in the RefSCCs. - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); - - // Verify that the post-order walk reflects the updated but still incomplete - // structure. - auto J = CG.postorder_ref_scc_begin(); - EXPECT_NE(J, E); - EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J; - EXPECT_EQ(I, J); - - // Check that we can form the last two RefSCCs now, and even that we can do - // it with alternating iterators. - ++J; - EXPECT_NE(J, E); - LazyCallGraph::RefSCC &BRC = *J; - EXPECT_NE(&BRC, nullptr); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); - EXPECT_TRUE(BRC.isParentOf(CRC)); - ++I; - EXPECT_EQ(J, I); - EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - - // Increment I this time to form the new RefSCC, flopping back to the first - // iterator. - ++I; - EXPECT_NE(I, E); - LazyCallGraph::RefSCC &ARC = *I; - EXPECT_NE(&ARC, nullptr); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); - EXPECT_TRUE(ARC.isParentOf(CRC)); - ++J; - EXPECT_EQ(I, J); - EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J; - ++I; - EXPECT_EQ(E, I); - ++J; - EXPECT_EQ(E, J); -} - TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) { LLVMContext Context; // Another variation of the above test but with all the edges switched to @@ -910,6 +819,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) dbgs() << "Formed RefSCC: " << RC << "\n"; @@ -1016,6 +926,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) dbgs() << "Formed RefSCC: " << RC << "\n"; @@ -1092,6 +1003,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) dbgs() << "Formed RefSCC: " << RC << "\n"; @@ -1153,6 +1065,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) dbgs() << "Formed RefSCC: " << RC << "\n"; @@ -1276,177 +1189,6 @@ EXPECT_EQ(++I, E); } -TEST(LazyCallGraphTest, InlineAndDeleteFunctionMidTraversal) { - LLVMContext Context; - // This is the same fundamental test as the previous, but we perform it - // having only partially walked the RefSCCs of the graph. - // - // The ascii diagram is repeated here for easy reference. - // - // d1 | - // / \ | - // d3--d2 | - // / \ | - // b1 c1 | - // / \ / \ | - // b3--b2 c3--c2 | - // \ / | - // a1 | - // / \ | - // a3--a2 | - // - std::unique_ptr M = parseAssembly(Context, DiamondOfTriangles); - LazyCallGraph CG(*M); - - // Walk the RefSCCs until we find the one containing 'c1'. - auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); - ASSERT_NE(I, E); - LazyCallGraph::RefSCC &DRC = *I; - ASSERT_NE(&DRC, nullptr); - ++I; - ASSERT_NE(I, E); - LazyCallGraph::RefSCC &CRC = *I; - ASSERT_NE(&CRC, nullptr); - - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2"))); - ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3"))); - LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); - LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); - LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); - LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); - LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); - LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); - ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); - ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); - ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); - - // Delete d2 from the graph, as if it had been inlined. - // - // d1 | - // / / | - // d3--. | - // / \ | - // b1 c1 | - // / \ / \ | - // b3--b2 c3--c2 | - // \ / | - // a1 | - // / \ | - // a3--a2 | - - Function &D2F = D2.getFunction(); - CallInst *C1Call = nullptr, *D1Call = nullptr; - for (User *U : D2F.users()) { - CallInst *CI = dyn_cast(U); - ASSERT_TRUE(CI) << "Expected a call: " << *U; - if (CI->getParent()->getParent() == &C1.getFunction()) { - ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI; - C1Call = CI; - } else if (CI->getParent()->getParent() == &D1.getFunction()) { - ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI; - D1Call = CI; - } else { - FAIL() << "Found an unexpected call instruction: " << *CI; - } - } - ASSERT_NE(C1Call, nullptr); - ASSERT_NE(D1Call, nullptr); - ASSERT_EQ(&D2F, C1Call->getCalledFunction()); - ASSERT_EQ(&D2F, D1Call->getCalledFunction()); - C1Call->setCalledFunction(&D3.getFunction()); - D1Call->setCalledFunction(&D3.getFunction()); - ASSERT_EQ(0u, D2F.getNumUses()); - - // Insert new edges first. - CRC.insertTrivialCallEdge(C1, D3); - DRC.insertTrivialCallEdge(D1, D3); - - // Then remove the old ones. - LazyCallGraph::SCC &DC = *CG.lookupSCC(D2); - auto NewCs = DRC.switchInternalEdgeToRef(D1, D2); - EXPECT_EQ(&DC, CG.lookupSCC(D2)); - EXPECT_EQ(NewCs.end(), std::next(NewCs.begin())); - LazyCallGraph::SCC &NewDC = *NewCs.begin(); - EXPECT_EQ(&NewDC, CG.lookupSCC(D1)); - EXPECT_EQ(&NewDC, CG.lookupSCC(D3)); - auto NewRCs = DRC.removeInternalRefEdge(D1, D2); - EXPECT_EQ(&DRC, CG.lookupRefSCC(D2)); - EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin())); - LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin(); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); - EXPECT_FALSE(NewDRC.isParentOf(DRC)); - EXPECT_TRUE(CRC.isParentOf(DRC)); - EXPECT_TRUE(CRC.isParentOf(NewDRC)); - EXPECT_TRUE(DRC.isParentOf(NewDRC)); - CRC.removeOutgoingEdge(C1, D2); - EXPECT_FALSE(CRC.isParentOf(DRC)); - EXPECT_TRUE(CRC.isParentOf(NewDRC)); - EXPECT_TRUE(DRC.isParentOf(NewDRC)); - - // Now that we've updated the call graph, D2 is dead, so remove it. - CG.removeDeadFunction(D2F); - - // Check that the graph still looks the same. - EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); - EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1)); - EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); - EXPECT_TRUE(CRC.isParentOf(NewDRC)); - - // Verify that the post-order walk reflects the updated but still incomplete - // structure. - auto J = CG.postorder_ref_scc_begin(); - EXPECT_NE(J, E); - EXPECT_EQ(&NewDRC, &*J) << "Actual RefSCC: " << *J; - ++J; - EXPECT_NE(J, E); - EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J; - EXPECT_EQ(I, J); - - // Check that we can form the last two RefSCCs now, and even that we can do - // it with alternating iterators. - ++J; - EXPECT_NE(J, E); - LazyCallGraph::RefSCC &BRC = *J; - EXPECT_NE(&BRC, nullptr); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); - EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); - EXPECT_TRUE(BRC.isParentOf(NewDRC)); - ++I; - EXPECT_EQ(J, I); - EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; - - // Increment I this time to form the new RefSCC, flopping back to the first - // iterator. - ++I; - EXPECT_NE(I, E); - LazyCallGraph::RefSCC &ARC = *I; - EXPECT_NE(&ARC, nullptr); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); - EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); - EXPECT_TRUE(ARC.isParentOf(BRC)); - EXPECT_TRUE(ARC.isParentOf(CRC)); - ++J; - EXPECT_EQ(I, J); - EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J; - ++I; - EXPECT_EQ(E, I); - ++J; - EXPECT_EQ(E, J); -} - TEST(LazyCallGraphTest, InternalEdgeMutation) { LLVMContext Context; std::unique_ptr M = parseAssembly(Context, "define void @a() {\n" @@ -1467,6 +1209,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; EXPECT_EQ(CG.postorder_ref_scc_end(), I); @@ -1559,6 +1302,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); LazyCallGraph::RefSCC &RC = *I; EXPECT_EQ(E, std::next(I)); @@ -1633,6 +1377,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); LazyCallGraph::RefSCC &RC = *I; EXPECT_EQ(E, std::next(I)); @@ -1709,6 +1454,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; EXPECT_EQ(CG.postorder_ref_scc_end(), I); @@ -1801,6 +1547,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; EXPECT_EQ(CG.postorder_ref_scc_end(), I); @@ -1913,6 +1660,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; EXPECT_EQ(CG.postorder_ref_scc_end(), I); @@ -2043,6 +1791,7 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &RC = *I++; EXPECT_EQ(CG.postorder_ref_scc_end(), I); @@ -2122,6 +1871,7 @@ "}\n"); LazyCallGraph CG(*M); + CG.buildRefSCCs(); auto I = CG.postorder_ref_scc_begin(); LazyCallGraph::RefSCC &FRC = *I++; LazyCallGraph::RefSCC &GRC = *I++;