Index: llvm/trunk/include/llvm/Analysis/LazyCallGraph.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LazyCallGraph.h +++ llvm/trunk/include/llvm/Analysis/LazyCallGraph.h @@ -180,6 +180,7 @@ private: friend class LazyCallGraph::Node; + friend class LazyCallGraph::RefSCC; PointerIntPair, 1, Kind> Value; @@ -197,6 +198,7 @@ class Node { friend class LazyCallGraph; friend class LazyCallGraph::SCC; + friend class LazyCallGraph::RefSCC; LazyCallGraph *G; Function &F; @@ -226,6 +228,11 @@ /// Internal helper to remove the edge to the given function. void removeEdgeInternal(Function &ChildF); + void clear() { + Edges.clear(); + EdgeIndexMap.clear(); + } + /// Print the name of this node's function. friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) { return OS << N.F.getName(); @@ -461,6 +468,12 @@ /// formRefSCCFast on the graph itself. RefSCC(LazyCallGraph &G); + void clear() { + Parents.clear(); + SCCs.clear(); + SCCIndices.clear(); + } + /// Print a short description useful for debugging or logging. /// /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if @@ -502,6 +515,10 @@ void verify(); #endif + /// Handle any necessary parent set updates after inserting a trivial ref + /// or call edge. + void handleTrivialEdgeInsertion(Node &SourceN, Node &TargetN); + public: typedef pointee_iterator::const_iterator> iterator; typedef iterator_range range; @@ -711,6 +728,28 @@ SmallVector removeInternalRefEdge(Node &SourceN, Node &TargetN); + /// A convenience wrapper around the above to handle trivial cases of + /// inserting a new call edge. + /// + /// This is trivial whenever the target is in the same SCC as the source or + /// the edge is an outgoing edge to some descendant SCC. In these cases + /// there is no change to the cyclic structure of SCCs or RefSCCs. + /// + /// To further make calling this convenient, it also handles inserting + /// already existing edges. + void insertTrivialCallEdge(Node &SourceN, Node &TargetN); + + /// A convenience wrapper around the above to handle trivial cases of + /// inserting a new ref edge. + /// + /// This is trivial whenever the target is in the same RefSCC as the source + /// or the edge is an outgoing edge to some descendant RefSCC. In these + /// cases there is no change to the cyclic structure of the RefSCCs. + /// + /// To further make calling this convenient, it also handles inserting + /// already existing edges. + void insertTrivialRefEdge(Node &SourceN, Node &TargetN); + ///@} }; @@ -833,8 +872,9 @@ /// call graph. They can be used to update the core node-graph during /// a node-based inorder traversal that precedes any SCC-based traversal. /// - /// Once you begin manipulating a call graph's SCCs, you must perform all - /// mutation of the graph via the SCC methods. + /// Once you begin manipulating a call graph's SCCs, most mutation of the + /// graph must be performed via a RefSCC method. There are some exceptions + /// below. /// Update the call graph after inserting a new edge. void insertEdge(Node &Caller, Function &Callee, Edge::Kind EK); @@ -855,6 +895,28 @@ ///@} ///@{ + /// \name General Mutation API + /// + /// There are a very limited set of mutations allowed on the graph as a whole + /// once SCCs have started to be formed. These routines have strict contracts + /// but may be called at any point. + + /// Remove a dead function from the call graph (typically to delete it). + /// + /// Note that the function must have an empty use list, and the call graph + /// must be up-to-date prior to calling this. That means it is by itself in + /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural + /// changes result from calling this routine other than potentially removing + /// entry points into the call graph. + /// + /// If SCC formation has begun, this function must not be part of the current + /// DFS in order to call this safely. Typically, the function will have been + /// fully visited by the DFS prior to calling this routine. + void removeDeadFunction(Function &F); + + ///@} + + ///@{ /// \name Static helpers for code doing updates to the call graph. /// /// These helpers are used to implement parts of the call graph but are also Index: llvm/trunk/lib/Analysis/LazyCallGraph.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyCallGraph.cpp +++ llvm/trunk/lib/Analysis/LazyCallGraph.cpp @@ -1302,6 +1302,19 @@ assert(!IsLeaf && "This SCC cannot be a leaf as it already had child " "SCCs before we removed this edge."); #endif + // And connect both this RefSCC and all the new ones to the correct parents. + // The easiest way to do this is just to re-analyze the old parent set. + SmallVector OldParents(Parents.begin(), Parents.end()); + Parents.clear(); + for (RefSCC *ParentRC : OldParents) + for (SCC *ParentC : ParentRC->SCCs) + for (Node &ParentN : *ParentC) + for (Edge &E : ParentN) { + assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); + RefSCC &RC = *G->lookupRefSCC(*E.getNode()); + RC.Parents.insert(ParentRC); + } + // If this SCC stopped being a leaf through this edge removal, remove it from // the leaf SCC list. Note that this DTRT in the case where this was never // a leaf. @@ -1316,6 +1329,69 @@ return Result; } +void LazyCallGraph::RefSCC::handleTrivialEdgeInsertion(Node &SourceN, + Node &TargetN) { + // The only trivial case that requires any graph updates is when we add new + // ref edge and may connect different RefSCCs along that path. This is only + // because of the parents set. Every other part of the graph remains constant + // after this edge insertion. + assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); + RefSCC &TargetRC = *G->lookupRefSCC(TargetN); + if (&TargetRC == this) { + + return; + } + + assert(TargetRC.isDescendantOf(*this) && + "Target must be a descendant of the Source."); + // 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); +} + +void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN, + Node &TargetN) { +#ifndef NDEBUG + // Check that the RefSCC is still valid when we finish. + auto ExitVerifier = make_scope_exit([this] { verify(); }); +#endif + // First insert it into the source or find the existing edge. + auto InsertResult = SourceN.EdgeIndexMap.insert( + {&TargetN.getFunction(), SourceN.Edges.size()}); + if (!InsertResult.second) { + // Already an edge, just update it. + Edge &E = SourceN.Edges[InsertResult.first->second]; + if (E.isCall()) + return; // Nothing to do! + E.setKind(Edge::Call); + } else { + // Create the new edge. + SourceN.Edges.emplace_back(TargetN, Edge::Call); + } + + // Now that we have the edge, handle the graph fallout. + handleTrivialEdgeInsertion(SourceN, TargetN); +} + +void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) { +#ifndef NDEBUG + // Check that the RefSCC is still valid when we finish. + auto ExitVerifier = make_scope_exit([this] { verify(); }); +#endif + // First insert it into the source or find the existing edge. + auto InsertResult = SourceN.EdgeIndexMap.insert( + {&TargetN.getFunction(), SourceN.Edges.size()}); + if (!InsertResult.second) + // Already an edge, we're done. + return; + + // Create the new edge. + SourceN.Edges.emplace_back(TargetN, Edge::Ref); + + // Now that we have the edge, handle the graph fallout. + handleTrivialEdgeInsertion(SourceN, TargetN); +} + void LazyCallGraph::insertEdge(Node &SourceN, Function &Target, Edge::Kind EK) { assert(SCCMap.empty() && DFSStack.empty() && "This method cannot be called after SCCs have been formed!"); @@ -1330,6 +1406,93 @@ return SourceN.removeEdgeInternal(Target); } +void LazyCallGraph::removeDeadFunction(Function &F) { + // FIXME: This is unnecessarily restrictive. We should be able to remove + // functions which recursively call themselves. + assert(F.use_empty() && + "This routine should only be called on trivially dead functions!"); + + auto EII = EntryIndexMap.find(&F); + if (EII != EntryIndexMap.end()) { + EntryEdges[EII->second] = Edge(); + 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! + return; + + 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 + // 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); + assert(CI != SCCMap.end() && + "Tried to remove a node without an SCC after DFS walk started!"); + SCC &C = *CI->second; + SCCMap.erase(CI); + RefSCC &RC = C.getOuterRefSCC(); + + // This node must be the only member of its SCC as it has no callers, and + // that SCC must be the only member of a RefSCC as it has no references. + // Validate these properties first. + assert(C.size() == 1 && "Dead functions must be in a singular SCC"); + assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC"); + assert(RC.Parents.empty() && "Cannot have parents of a dead RefSCC!"); + + // Now remove this RefSCC from any parents sets and the leaf list. + for (Edge &E : N) + if (Node *TargetN = E.getNode()) + if (RefSCC *TargetRC = lookupRefSCC(*TargetN)) + TargetRC->Parents.erase(&RC); + // FIXME: This is a linear operation which could become hot and benefit from + // an index map. + auto LRI = find(LeafRefSCCs, &RC); + if (LRI != LeafRefSCCs.end()) + LeafRefSCCs.erase(LRI); + + auto RCIndexI = RefSCCIndices.find(&RC); + int RCIndex = RCIndexI->second; + PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex); + RefSCCIndices.erase(RCIndexI); + for (int i = RCIndex, Size = PostOrderRefSCCs.size(); i < Size; ++i) + RefSCCIndices[PostOrderRefSCCs[i]] = i; + + // Finally clear out all the data structures from the node down through the + // components. + N.clear(); + C.clear(); + RC.clear(); + + // Nothing to delete as all the objects are allocated in stable bump pointer + // allocators. +} + LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) { return *new (MappedN = BPA.Allocate()) Node(*this, F); } @@ -1500,7 +1663,7 @@ IsLeaf = false; } - // For the SCCs where we fine no child SCCs, add them to the leaf list. + // For the SCCs where we find no child SCCs, add them to the leaf list. if (IsLeaf) LeafRefSCCs.push_back(&RC); } Index: llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp +++ llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp @@ -9,6 +9,7 @@ #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Instructions.h" #include "llvm/IR/Function.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" @@ -1105,6 +1106,323 @@ EXPECT_EQ(++I, End); } +TEST(LazyCallGraphTest, InlineAndDeleteFunction) { + LLVMContext Context; + // We want to ensure we can delete nodes from relatively complex graphs and + // so use the diamond of triangles graph defined above. + // + // 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); + + // 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())); + + // 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(&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(&NewDRC, CG.lookupRefSCC(D1)); + EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3)); + EXPECT_TRUE(CRC.isParentOf(NewDRC)); + + // Verify the post-order walk hasn't changed. + auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); + ASSERT_NE(I, E); + EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I; + 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, 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"