Index: include/llvm/Analysis/LazyCallGraph.h =================================================================== --- include/llvm/Analysis/LazyCallGraph.h +++ include/llvm/Analysis/LazyCallGraph.h @@ -730,27 +730,39 @@ struct IsAtEndT {}; LazyCallGraph *G; - RefSCC *C; + RefSCC *RC; - // Build the begin iterator for a node. - postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G) { - C = G.getNextRefSCCInPostOrder(); - } + /// Build the begin iterator for a node. + postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {} - // Build the end iterator for a node. This is selected purely by overload. + /// Build the end iterator for a node. This is selected purely by overload. postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) - : G(&G), C(nullptr) {} + : G(&G), RC(nullptr) {} + + /// Get the post-order RefSCC at the given index of the postorder walk, + /// 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; + + assert(Index < (int)G.PostOrderRefSCCs.size() && + "Built the next post-order RefSCC without growing list!"); + return G.PostOrderRefSCCs[Index]; + } public: bool operator==(const postorder_ref_scc_iterator &Arg) const { - return G == Arg.G && C == Arg.C; + return G == Arg.G && RC == Arg.RC; } - reference operator*() const { return *C; } + reference operator*() const { return *RC; } using iterator_facade_base::operator++; postorder_ref_scc_iterator &operator++() { - C = G->getNextRefSCCInPostOrder(); + assert(RC && "Cannot increment the end iterator!"); + RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1); return *this; } }; @@ -897,6 +909,18 @@ /// Allocator that holds all the call graph RefSCCs. SpecificBumpPtrAllocator RefSCCBPA; + /// The post-order sequence of RefSCCs. + /// + /// This list is lazily formed the first time we walk the graph. + SmallVector PostOrderRefSCCs; + + /// A map from RefSCC to the index for it in the postorder sequence of + /// RefSCCs. + /// + /// Only RefSCCs which have been created while walking the graph are in the + /// map. + DenseMap RefSCCIndices; + /// The leaf RefSCCs of the graph. /// /// These are all of the RefSCCs which have no children. @@ -944,8 +968,12 @@ /// and updates the root leaf list. void connectRefSCC(RefSCC &RC); - /// Retrieve the next node in the post-order RefSCC walk of the call graph. - RefSCC *getNextRefSCCInPostOrder(); + /// 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: lib/Analysis/LazyCallGraph.cpp =================================================================== --- lib/Analysis/LazyCallGraph.cpp +++ lib/Analysis/LazyCallGraph.cpp @@ -802,6 +802,12 @@ SmallVector LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { assert(G->lookupRefSCC(TargetN) == this && "Target must be in this SCC."); + RefSCC &SourceC = *G->lookupRefSCC(SourceN); + assert(&SourceC != this && "Source must not be in this SCC."); + assert(SourceC.isDescendantOf(*this) && + "Source must be a descendant of the Target."); + + SmallVector DeletedRefSCCs; #ifndef NDEBUG // In a debug build, verify the RefSCC is valid to start with and when this @@ -810,87 +816,67 @@ auto VerifyOnExit = make_scope_exit([&]() { verify(); }); #endif - // We store the RefSCCs found to be connected in postorder so that we can use - // that when merging. We also return this to the caller to allow them to - // invalidate information pertaining to these RefSCCs. - SmallVector Connected; + int SourceIdx = G->RefSCCIndices[&SourceC]; + int TargetIdx = G->RefSCCIndices[this]; + assert(SourceIdx < TargetIdx && + "Postorder list doesn't see edge as incoming!"); + + // Compute the RefSCCs which (transitively) reach the source. + auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl &Set) { + Set.insert(&SourceC); + auto IsConnected = [&](RefSCC &RC) { + for (SCC &C : RC) + for (Node &N : C) + for (Edge &E : N.calls()) { + assert(E.getNode() && "Must have formed a node within an SCC!"); + if (Set.count(G->lookupRefSCC(*E.getNode()))) + return true; + } - RefSCC &SourceC = *G->lookupRefSCC(SourceN); - assert(&SourceC != this && "Source must not be in this SCC."); - assert(SourceC.isDescendantOf(*this) && - "Source must be a descendant of the Target."); + return false; + }; - // The algorithm we use for merging SCCs based on the cycle introduced here - // is to walk the RefSCC inverted DAG formed by the parent sets. The inverse - // graph has the same cycle properties as the actual DAG of the RefSCCs, and - // when forming RefSCCs lazily by a DFS, the bottom of the graph won't exist - // in many cases which should prune the search space. - // - // FIXME: We can get this pruning behavior even after the incremental RefSCC - // formation by leaving behind (conservative) DFS numberings in the nodes, - // and pruning the search with them. These would need to be cleverly updated - // during the removal of intra-SCC edges, but could be preserved - // conservatively. - // - // FIXME: This operation currently creates ordering stability problems - // because we don't use stably ordered containers for the parent SCCs. - - // The set of RefSCCs that are connected to the parent, and thus will - // participate in the merged connected component. - SmallPtrSet ConnectedSet; - ConnectedSet.insert(this); - - // We build up a DFS stack of the parents chains. - SmallVector, 8> DFSStack; - SmallPtrSet Visited; - int ConnectedDepth = -1; - DFSStack.push_back({&SourceC, SourceC.parent_begin()}); - do { - auto DFSPair = DFSStack.pop_back_val(); - RefSCC *C = DFSPair.first; - parent_iterator I = DFSPair.second; - auto E = C->parent_end(); + for (RefSCC *RC : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1, + G->PostOrderRefSCCs.begin() + TargetIdx + 1)) + if (IsConnected(*RC)) + Set.insert(RC); + }; - while (I != E) { - RefSCC &Parent = *I++; - - // If we have already processed this parent SCC, skip it, and remember - // whether it was connected so we don't have to check the rest of the - // stack. This also handles when we reach a child of the 'this' SCC (the - // callee) which terminates the search. - if (ConnectedSet.count(&Parent)) { - assert(ConnectedDepth < (int)DFSStack.size() && - "Cannot have a connected depth greater than the DFS depth!"); - ConnectedDepth = DFSStack.size(); - continue; - } - if (Visited.count(&Parent)) - continue; + // Use a normal worklist to find which SCCs the target connects to. We still + // bound the search based on the range in the postorder list we care about, + // but because this is forward connectivity we just "recurse" through the + // edges. + auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl &Set) { + Set.insert(this); + SmallVector Worklist; + Worklist.push_back(this); + do { + RefSCC &RC = *Worklist.pop_back_val(); + for (SCC &C : RC) + for (Node &N : C) + for (Edge &E : N) { + assert(E.getNode() && "Must have formed a node!"); + RefSCC &EdgeRC = *G->lookupRefSCC(*E.getNode()); + if (G->RefSCCIndices.find(&EdgeRC)->second <= SourceIdx) + // Not in the postorder sequence between source and target. + continue; + + if (Set.insert(&EdgeRC).second) + Worklist.push_back(&EdgeRC); + } + } while (!Worklist.empty()); + }; - // We fully explore the depth-first space, adding nodes to the connected - // set only as we pop them off, so "recurse" by rotating to the parent. - DFSStack.push_back({C, I}); - C = &Parent; - I = C->parent_begin(); - E = C->parent_end(); - } + // Use a generic helper to update the postorder sequence of SCCs and return + // a range of any SCCs connected into a cycle by inserting this edge. This + // routine will also take care of updating the indices into the postorder + // sequence. + auto MergeRange = updatePostorderSequenceForEdgeInsertion( + SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices, + ComputeSourceConnectedSet, ComputeTargetConnectedSet); - // If we've found a connection anywhere below this point on the stack (and - // thus up the parent graph from the caller), the current node needs to be - // added to the connected set now that we've processed all of its parents. - if ((int)DFSStack.size() == ConnectedDepth) { - --ConnectedDepth; // We're finished with this connection. - bool Inserted = ConnectedSet.insert(C).second; - (void)Inserted; - assert(Inserted && "Cannot insert a refSCC multiple times!"); - Connected.push_back(C); - } else { - // Otherwise remember that its parents don't ever connect. - assert(ConnectedDepth < (int)DFSStack.size() && - "Cannot have a connected depth greater than the DFS depth!"); - Visited.insert(C); - } - } while (!DFSStack.empty()); + // Build a set so we can do fast tests for whether a merge is occuring. + SmallPtrSet MergeSet(MergeRange.begin(), MergeRange.end()); // Now that we have identified all of the SCCs which need to be merged into // a connected set with the inserted edge, merge all of them into this SCC. @@ -899,21 +885,21 @@ // ensures a merged postorder SCC list. SmallVector MergedSCCs; int SCCIndex = 0; - for (RefSCC *C : reverse(Connected)) { - assert(C != this && + for (RefSCC *RC : reverse(MergeRange)) { + assert(RC != this && "This RefSCC should terminate the DFS without being reached."); // Merge the parents which aren't part of the merge into the our parents. - for (RefSCC *ParentC : C->Parents) - if (!ConnectedSet.count(ParentC)) - Parents.insert(ParentC); - C->Parents.clear(); + for (RefSCC *ParentRC : RC->Parents) + if (!MergeSet.count(ParentRC)) + Parents.insert(ParentRC); + RC->Parents.clear(); // Walk the inner SCCs to update their up-pointer and walk all the edges to // update any parent sets. // FIXME: We should try to find a way to avoid this (rather expensive) edge // walk by updating the parent sets in some other manner. - for (SCC &InnerC : *C) { + for (SCC &InnerC : *RC) { InnerC.OuterRefSCC = this; SCCIndices[&InnerC] = SCCIndex++; for (Node &N : InnerC) { @@ -922,9 +908,9 @@ assert(E.getNode() && "Cannot have a null node within a visited SCC!"); RefSCC &ChildRC = *G->lookupRefSCC(*E.getNode()); - if (ConnectedSet.count(&ChildRC)) + if (MergeSet.count(&ChildRC)) continue; - ChildRC.Parents.erase(C); + ChildRC.Parents.erase(RC); ChildRC.Parents.insert(this); } } @@ -933,19 +919,26 @@ // Now merge in the SCCs. We can actually move here so try to reuse storage // the first time through. if (MergedSCCs.empty()) - MergedSCCs = std::move(C->SCCs); + MergedSCCs = std::move(RC->SCCs); else - MergedSCCs.append(C->SCCs.begin(), C->SCCs.end()); - C->SCCs.clear(); + MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end()); + RC->SCCs.clear(); + DeletedRefSCCs.push_back(RC); } - // Finally append our original SCCs to the merged list and move it into - // place. + // Append our original SCCs to the merged list and move it into place. for (SCC &InnerC : *this) SCCIndices[&InnerC] = SCCIndex++; MergedSCCs.append(SCCs.begin(), SCCs.end()); SCCs = std::move(MergedSCCs); + // Remove the merged away RefSCCs from the post order sequence. + int IndexOffset = MergeRange.end() - MergeRange.begin(); + auto EraseEnd = + G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end()); + for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end())) + G->RefSCCIndices[RC] -= IndexOffset; + // At this point we have a merged RefSCC with a post-order SCCs list, just // connect the nodes to form the new edge. SourceN.insertEdgeInternal(TargetN, Edge::Ref); @@ -954,7 +947,7 @@ // invalidate any data they have associated with those SCCs. Note that these // SCCs are no longer in an interesting state (they are totally empty) but // the pointers will remain stable for the life of the graph itself. - return Connected; + return DeletedRefSCCs; } void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) { @@ -1218,6 +1211,25 @@ for (int i = 1; i < PostOrderNumber; ++i) Result.push_back(G->createRefSCC(*G)); + // Insert the resulting postorder sequence into the global graph postorder + // sequence before the current RefSCC in that sequnece. The idea being that + // this RefSCC is the target of the reference edge removed, and thus has + // a direct or indirect edge to every other RefSCC formed and so must be at + // the end of any postorder traversal. + // + // FIXME: It'd be nice to change the APIs so that we returned an iterator + // range over the global postorder sequence and generally use that sequence + // rather than building a separate result vector here. + if (!Result.empty()) { + int Idx = G->RefSCCIndices.find(this)->second; + G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, + Result.begin(), Result.end()); + for (int i = Idx, Size = G->PostOrderRefSCCs.size(); i < Size; ++i) + G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i; + assert(G->PostOrderRefSCCs[G->RefSCCIndices.find(this)->second] == this && + "Failed to update this RefSCC's index after insertion!"); + } + for (SCC *C : SCCs) { auto PostOrderI = PostOrderMapping.find(&*C->begin()); assert(PostOrderI != PostOrderMapping.end() && @@ -1486,14 +1498,14 @@ LeafRefSCCs.push_back(&RC); } -LazyCallGraph::RefSCC *LazyCallGraph::getNextRefSCCInPostOrder() { +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 nullptr; + return false; N = &get(*RefSCCEntryNodes.pop_back_val()); } while (N->DFSNumber != 0); @@ -1575,9 +1587,14 @@ PendingRefSCCStack.erase(RefSCCNodes.end().base(), PendingRefSCCStack.end()); - // We return the new node here. This essentially suspends the DFS walk - // until another RefSCC is requested. - return NewRC; + // Push the new node into the post-order list and return true indicating we + // successfully grew the post-order sequece 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; } } Index: unittests/Analysis/LazyCallGraphTest.cpp =================================================================== --- unittests/Analysis/LazyCallGraphTest.cpp +++ unittests/Analysis/LazyCallGraphTest.cpp @@ -220,6 +220,7 @@ EXPECT_FALSE(D.isChildOf(D)); EXPECT_FALSE(D.isAncestorOf(D)); EXPECT_FALSE(D.isDescendantOf(D)); + EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin()); LazyCallGraph::RefSCC &C = *J++; ASSERT_EQ(1, C.size()); @@ -235,6 +236,7 @@ EXPECT_FALSE(C.isChildOf(D)); EXPECT_TRUE(C.isAncestorOf(D)); EXPECT_FALSE(C.isDescendantOf(D)); + EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin())); LazyCallGraph::RefSCC &B = *J++; ASSERT_EQ(1, B.size()); @@ -252,6 +254,7 @@ EXPECT_FALSE(B.isDescendantOf(D)); EXPECT_FALSE(B.isAncestorOf(C)); EXPECT_FALSE(C.isAncestorOf(B)); + EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2)); LazyCallGraph::RefSCC &A = *J++; ASSERT_EQ(1, A.size()); @@ -269,8 +272,10 @@ EXPECT_TRUE(A.isAncestorOf(B)); EXPECT_TRUE(A.isAncestorOf(C)); EXPECT_TRUE(A.isAncestorOf(D)); + EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3)); EXPECT_EQ(CG.postorder_ref_scc_end(), J); + EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4)); } static Function &lookupFunction(Module &M, StringRef Name) { @@ -478,7 +483,7 @@ // Force the graph to be fully expanded. for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - (void)RC; + dbgs() << "Formed RefSCC: " << RC << "\n"; LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); @@ -599,7 +604,7 @@ // Force the graph to be fully expanded. for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) - (void)RC; + dbgs() << "Formed RefSCC: " << RC << "\n"; LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); @@ -668,6 +673,16 @@ // And that ancestry tests have been updated. EXPECT_TRUE(ARC.isParentOf(CRC)); EXPECT_TRUE(BRC.isParentOf(CRC)); + + // And verify the post-order walk reflects the updated structure. + auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); + ASSERT_NE(I, E); + EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I; + ASSERT_NE(++I, E); + EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I; + ASSERT_NE(++I, E); + EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; + EXPECT_EQ(++I, E); } TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { @@ -726,16 +741,30 @@ EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); - // Check that we can form the last two RefSCCs now in a coherent way. - ++I; - EXPECT_NE(I, E); - LazyCallGraph::RefSCC &BRC = *I; + // 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); @@ -743,8 +772,13 @@ 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, InternalEdgeMutation) { @@ -855,9 +889,9 @@ LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto I = CG.postorder_ref_scc_begin(); - LazyCallGraph::RefSCC &RC = *I++; - EXPECT_EQ(CG.postorder_ref_scc_end(), I); + auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); + LazyCallGraph::RefSCC &RC = *I; + EXPECT_EQ(E, std::next(I)); LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); @@ -874,6 +908,10 @@ EXPECT_EQ(&RC, CG.lookupRefSCC(A)); EXPECT_EQ(&RC, CG.lookupRefSCC(B)); EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + auto J = CG.postorder_ref_scc_begin(); + EXPECT_EQ(I, J); + EXPECT_EQ(&RC, &*J); + EXPECT_EQ(E, std::next(J)); // Remove the edge from c -> a, which should leave 'a' in the original RefSCC // and form a new RefSCC for 'b' and 'c'. @@ -881,9 +919,19 @@ EXPECT_EQ(1u, NewRCs.size()); EXPECT_EQ(&RC, CG.lookupRefSCC(A)); EXPECT_EQ(1, std::distance(RC.begin(), RC.end())); - LazyCallGraph::RefSCC *RC2 = CG.lookupRefSCC(B); - EXPECT_EQ(RC2, CG.lookupRefSCC(C)); - EXPECT_EQ(RC2, NewRCs[0]); + LazyCallGraph::RefSCC &RC2 = *CG.lookupRefSCC(B); + EXPECT_EQ(&RC2, CG.lookupRefSCC(C)); + EXPECT_EQ(&RC2, NewRCs[0]); + J = CG.postorder_ref_scc_begin(); + EXPECT_NE(I, J); + EXPECT_EQ(&RC2, &*J); + ++J; + EXPECT_EQ(I, J); + EXPECT_EQ(&RC, &*J); + ++I; + EXPECT_EQ(E, I); + ++J; + EXPECT_EQ(E, J); } TEST(LazyCallGraphTest, InternalCallEdgeToRef) {