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,15 @@ /// 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. + DenseMap RefSCCIndices; + /// The leaf RefSCCs of the graph. /// /// These are all of the RefSCCs which have no children. @@ -944,8 +965,22 @@ /// 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(); + /// Get the index of a RefSCC within the postorder traversal. + /// + /// Requires that this RefSCC is a valid one in the (perhaps partial) + /// postorder traversed part of the graph. + int getRefSCCIndex(RefSCC &RC) { + auto IndexIt = RefSCCIndices.find(&RC); + assert(IndexIt != RefSCCIndices.end() && "RefSCC doesn't have an index!"); + 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: lib/Analysis/LazyCallGraph.cpp =================================================================== --- lib/Analysis/LazyCallGraph.cpp +++ lib/Analysis/LazyCallGraph.cpp @@ -9,6 +9,7 @@ #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/ADT/ScopeExit.h" +#include "llvm/ADT/Sequence.h" #include "llvm/ADT/STLExtras.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/InstVisitor.h" @@ -801,7 +802,13 @@ SmallVector LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { - assert(G->lookupRefSCC(TargetN) == this && "Target must be in this SCC."); + 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."); + 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,110 +817,94 @@ 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; - - 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."); - - // 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(); - - 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; + 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. We do this by + // working backwards from the source using the parent set in each RefSCC, + // skipping any RefSCCs that don't fall in the postorder range. This has the + // advantage of walking the sparser parent edge (in high fan-out graphs) but + // more importantly this removes examining all forward edges in all RefSCCs + // within the postorder range which aren't in fact connected. Only connected + // RefSCCs (and their edges) are visited here. + auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl &Set) { + Set.insert(&SourceC); + SmallVector Worklist; + Worklist.push_back(&SourceC); + do { + RefSCC &RC = *Worklist.pop_back_val(); + for (RefSCC &ParentRC : RC.parents()) { + // Skip any RefSCCs outside the range of source to target in the + // postorder sequence. + int ParentIdx = G->getRefSCCIndex(ParentRC); + assert(ParentIdx > SourceIdx && "Parent cannot precede source in postorder!"); + if (ParentIdx > TargetIdx) + continue; + if (Set.insert(&ParentRC).second) + // First edge connecting to this parent, add it to our worklist. + Worklist.push_back(&ParentRC); } - if (Visited.count(&Parent)) - continue; + } 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 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->getRefSCCIndex(EdgeRC) <= SourceIdx) + // Not in the postorder sequence between source and target. + continue; + + if (Set.insert(&EdgeRC).second) + Worklist.push_back(&EdgeRC); + } + } while (!Worklist.empty()); + }; - // 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()); + // Use a generic helper to update the postorder sequence of RefSCCs and return + // a range of any RefSCCs connected into a cycle by inserting this edge. This + // routine will also take care of updating the indices into the postorder + // sequence. + iterator_range::iterator> MergeRange = + updatePostorderSequenceForEdgeInsertion( + SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices, + ComputeSourceConnectedSet, ComputeTargetConnectedSet); + + // 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. - // We walk the newly connected RefSCCs in the reverse postorder of the parent - // DAG walk above and merge in each of their SCC postorder lists. This - // ensures a merged postorder SCC list. SmallVector MergedSCCs; int SCCIndex = 0; - for (RefSCC *C : reverse(Connected)) { - assert(C != this && + for (RefSCC *RC : 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 +913,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 +924,28 @@ // 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. + for (RefSCC *RC : MergeRange) + G->RefSCCIndices.erase(RC); + 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 +954,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 +1218,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->getRefSCCIndex(*this); + G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, + Result.begin(), Result.end()); + for (int i : seq(Idx, G->PostOrderRefSCCs.size())) + G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i; + assert(G->PostOrderRefSCCs[G->getRefSCCIndex(*this)] == 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 +1505,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 +1594,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 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; } } Index: unittests/Analysis/LazyCallGraphTest.cpp =================================================================== --- unittests/Analysis/LazyCallGraphTest.cpp +++ unittests/Analysis/LazyCallGraphTest.cpp @@ -120,6 +120,101 @@ " ret void\n" "}\n"; +/* + IR forming a reference graph with a diamond of triangle-shaped RefSCCs + + d1 + / \ + d3--d2 + / \ + b1 c1 + / \ / \ + b3--b2 c3--c2 + \ / + a1 + / \ + a3--a2 + + All call edges go up between RefSCCs, and clockwise around the RefSCC. + */ +static const char DiamondOfTrianglesRefGraph[] = + "define void @a1() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @a2, void ()** %a\n" + " store void ()* @b2, void ()** %a\n" + " store void ()* @c3, void ()** %a\n" + " ret void\n" + "}\n" + "define void @a2() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @a3, void ()** %a\n" + " ret void\n" + "}\n" + "define void @a3() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @a1, void ()** %a\n" + " ret void\n" + "}\n" + "define void @b1() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @b2, void ()** %a\n" + " store void ()* @d3, void ()** %a\n" + " ret void\n" + "}\n" + "define void @b2() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @b3, void ()** %a\n" + " ret void\n" + "}\n" + "define void @b3() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @b1, void ()** %a\n" + " ret void\n" + "}\n" + "define void @c1() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @c2, void ()** %a\n" + " store void ()* @d2, void ()** %a\n" + " ret void\n" + "}\n" + "define void @c2() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @c3, void ()** %a\n" + " ret void\n" + "}\n" + "define void @c3() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @c1, void ()** %a\n" + " ret void\n" + "}\n" + "define void @d1() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @d2, void ()** %a\n" + " ret void\n" + "}\n" + "define void @d2() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @d3, void ()** %a\n" + " ret void\n" + "}\n" + "define void @d3() {\n" + "entry:\n" + " %a = alloca void ()*\n" + " store void ()* @d1, void ()** %a\n" + " ret void\n" + "}\n"; + TEST(LazyCallGraphTest, BasicGraphFormation) { LLVMContext Context; std::unique_ptr M = parseAssembly(Context, DiamondOfTriangles); @@ -220,6 +315,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 +331,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 +349,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 +367,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 +578,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 +699,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 +768,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 +836,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 +867,241 @@ 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 + // references rather than calls. + std::unique_ptr M = + parseAssembly(Context, DiamondOfTrianglesRefGraph); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) + dbgs() << "Formed RefSCC: " << RC << "\n"; + + LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); + LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); + LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3")); + LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); + LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); + LazyCallGraph::Node &B3 = *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")); + LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); + LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); + LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); + LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); + ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); + ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); + ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); + ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); + ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); + ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); + ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); + ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); + ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); + + // Add an edge to make the graph: + // + // d1 | + // / \ | + // d3--d2---. | + // / \ | | + // b1 c1 | | + // / \ / \ / | + // b3--b2 c3--c2 | + // \ / | + // a1 | + // / \ | + // a3--a2 | + 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 SCC sets. + EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); + 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)); + + // 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, IncomingEdgeInsertionLargeCallCycle) { + LLVMContext Context; + std::unique_ptr M = parseAssembly(Context, "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " call void @c()\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) + dbgs() << "Formed RefSCC: " << RC << "\n"; + + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); + LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); + LazyCallGraph::SCC &AC = *CG.lookupSCC(A); + LazyCallGraph::SCC &BC = *CG.lookupSCC(B); + LazyCallGraph::SCC &CC = *CG.lookupSCC(C); + LazyCallGraph::SCC &DC = *CG.lookupSCC(D); + LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); + LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); + LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); + LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); + + // Connect the top to the bottom forming a large RefSCC made up mostly of calls. + auto MergedRCs = ARC.insertIncomingRefEdge(D, A); + // Make sure we connected the nodes. + EXPECT_NE(D.begin(), D.end()); + EXPECT_EQ(&A, D.begin()->getNode()); + + // Check that we have the dead RCs, but ignore the order. + EXPECT_EQ(3u, MergedRCs.size()); + EXPECT_NE(std::find(MergedRCs.begin(), MergedRCs.end(), &BRC), MergedRCs.end()); + EXPECT_NE(std::find(MergedRCs.begin(), MergedRCs.end(), &CRC), MergedRCs.end()); + EXPECT_NE(std::find(MergedRCs.begin(), MergedRCs.end(), &DRC), MergedRCs.end()); + + // Make sure the nodes point to the right place now. + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); + + // Check that the SCCs are in postorder. + EXPECT_EQ(4, ARC.size()); + EXPECT_EQ(&DC, &ARC[0]); + EXPECT_EQ(&CC, &ARC[1]); + EXPECT_EQ(&BC, &ARC[2]); + EXPECT_EQ(&AC, &ARC[3]); + + // 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(&ARC, &*I) << "Actual RefSCC: " << *I; + EXPECT_EQ(++I, E); +} + +TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) { + LLVMContext Context; + std::unique_ptr M = + parseAssembly(Context, "define void @a() {\n" + "entry:\n" + " %p = alloca void ()*\n" + " store void ()* @b, void ()** %p\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " %p = alloca void ()*\n" + " store void ()* @c, void ()** %p\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " %p = alloca void ()*\n" + " store void ()* @d, void ()** %p\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) + dbgs() << "Formed RefSCC: " << RC << "\n"; + + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); + LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); + LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); + LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); + LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); + LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); + + // Connect the top to the bottom forming a large RefSCC made up mostly of calls. + auto MergedRCs = ARC.insertIncomingRefEdge(D, A); + // Make sure we connected the nodes. + EXPECT_NE(D.begin(), D.end()); + EXPECT_EQ(&A, D.begin()->getNode()); + + // Check that we have the dead RCs, but ignore the order. + EXPECT_EQ(3u, MergedRCs.size()); + EXPECT_NE(std::find(MergedRCs.begin(), MergedRCs.end(), &BRC), MergedRCs.end()); + EXPECT_NE(std::find(MergedRCs.begin(), MergedRCs.end(), &CRC), MergedRCs.end()); + EXPECT_NE(std::find(MergedRCs.begin(), MergedRCs.end(), &DRC), MergedRCs.end()); + + // Make sure the nodes point to the right place now. + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(B)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(C)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(D)); + + // And verify the post-order walk reflects the updated structure. + auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end(); + ASSERT_NE(I, End); + EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I; + EXPECT_EQ(++I, End); } TEST(LazyCallGraphTest, InternalEdgeMutation) { @@ -855,9 +1212,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 +1231,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 +1242,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) {