diff options
| -rw-r--r-- | include/llvm/Analysis/LazyCallGraph.h | 16 | ||||
| -rw-r--r-- | lib/Analysis/LazyCallGraph.cpp | 119 | ||||
| -rw-r--r-- | unittests/Analysis/LazyCallGraphTest.cpp | 155 |
3 files changed, 290 insertions, 0 deletions
diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h index 121054b704..c8da2bec18 100644 --- a/include/llvm/Analysis/LazyCallGraph.h +++ b/include/llvm/Analysis/LazyCallGraph.h @@ -275,6 +275,22 @@ public: /// graph. void insertOutgoingEdge(Node &CallerN, Node &CalleeN); + /// \brief Insert an edge whose tail is in a descendant SCC and head is in + /// this SCC. + /// + /// There must be an existing path from the callee to the caller in this + /// case. NB! This is has the potential to be a very expensive function. It + /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs + /// to resolve that cycle. But finding all of the SCCs which participate in + /// the cycle can in the worst case require traversing every SCC in the + /// graph. Every attempt is made to avoid that, but passes must still + /// exercise caution calling this routine repeatedly. + /// + /// FIXME: We could possibly optimize this quite a bit for cases where the + /// caller and callee are very nearby in the graph. See comments in the + /// implementation for details, but that use case might impact users. + SmallVector<SCC *, 1> insertIncomingEdge(Node &CallerN, Node &CalleeN); + /// \brief Remove an edge whose source is in this SCC and target is *not*. /// /// This removes an inter-SCC edge. All inter-SCC edges originating from diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index fbcacd8b0b..50b532c07d 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -202,6 +202,125 @@ void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) { CalleeC.ParentSCCs.insert(this); } +SmallVector<LazyCallGraph::SCC *, 1> +LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) { + // First insert it into the caller. + CallerN.insertEdgeInternal(CalleeN); + + assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC."); + + SCC &CallerC = *G->SCCMap.lookup(&CallerN); + assert(&CallerC != this && "Caller must not be in this SCC."); + assert(CallerC.isDescendantOf(*this) && + "Caller must be a descendant of the Callee."); + + // The algorithm we use for merging SCCs based on the cycle introduced here + // is to walk the SCC inverted DAG formed by the parent SCC sets. The inverse + // graph has the same cycle properties as the actual DAG of the SCCs, and + // when forming SCCs 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 SCC + // 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. + + // The set of SCCs that are connected to the caller, and thus will + // participate in the merged connected component. + SmallPtrSet<SCC *, 8> ConnectedSCCs; + ConnectedSCCs.insert(this); + ConnectedSCCs.insert(&CallerC); + + // We build up a DFS stack of the parents chains. + SmallVector<std::pair<SCC *, SCC::parent_iterator>, 8> DFSSCCs; + SmallPtrSet<SCC *, 8> VisitedSCCs; + int ConnectedDepth = -1; + SCC *C = this; + parent_iterator I = parent_begin(), E = parent_end(); + for (;;) { + while (I != E) { + SCC &ParentSCC = *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 (ConnectedSCCs.count(&ParentSCC)) { + ConnectedDepth = std::max<int>(ConnectedDepth, DFSSCCs.size()); + continue; + } + if (VisitedSCCs.count(&ParentSCC)) + continue; + + // 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. + DFSSCCs.push_back(std::make_pair(C, I)); + C = &ParentSCC; + I = ParentSCC.parent_begin(); + E = ParentSCC.parent_end(); + } + + // 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)DFSSCCs.size() == ConnectedDepth) { + --ConnectedDepth; // We're finished with this connection. + ConnectedSCCs.insert(C); + } else { + // Otherwise remember that its parents don't ever connect. + assert(ConnectedDepth < (int)DFSSCCs.size() && + "Cannot have a connected depth greater than the DFS depth!"); + VisitedSCCs.insert(C); + } + + if (DFSSCCs.empty()) + break; // We've walked all the parents of the caller transitively. + + // Pop off the prior node and position to unwind the depth first recursion. + std::tie(C, I) = DFSSCCs.pop_back_val(); + E = C->parent_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. + // FIXME: This operation currently creates ordering stability problems + // because we don't use stably ordered containers for the parent SCCs or the + // connected SCCs. + unsigned NewNodeBeginIdx = Nodes.size(); + for (SCC *C : ConnectedSCCs) { + if (C == this) + continue; + for (SCC *ParentC : C->ParentSCCs) + if (!ConnectedSCCs.count(ParentC)) + ParentSCCs.insert(ParentC); + C->ParentSCCs.clear(); + + for (Node *N : *C) { + for (Node &ChildN : *N) { + SCC &ChildC = *G->SCCMap.lookup(&ChildN); + if (&ChildC != C) + ChildC.ParentSCCs.erase(C); + } + G->SCCMap[N] = this; + Nodes.push_back(N); + } + C->Nodes.clear(); + } + for (auto I = Nodes.begin() + NewNodeBeginIdx, E = Nodes.end(); I != E; ++I) + for (Node &ChildN : **I) { + SCC &ChildC = *G->SCCMap.lookup(&ChildN); + if (&ChildC != this) + ChildC.ParentSCCs.insert(this); + } + + // We return the list of SCCs which were merged so that callers can + // 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 SmallVector<SCC *, 1>(ConnectedSCCs.begin(), ConnectedSCCs.end()); +} + void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) { // First remove it from the node. CallerN.removeEdgeInternal(CalleeN.getFunction()); diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp index 40bccd217d..8c7b567afc 100644 --- a/unittests/Analysis/LazyCallGraphTest.cpp +++ b/unittests/Analysis/LazyCallGraphTest.cpp @@ -426,6 +426,161 @@ TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { EXPECT_EQ(&DC, CG.lookupSCC(D)); } +TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { + // We want to ensure we can add edges even across complex diamond graphs, so + // we 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<Module> M = parseAssembly(DiamondOfTriangles); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + for (LazyCallGraph::SCC &C : CG.postorder_sccs()) + (void)C; + + 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::SCC &AC = *CG.lookupSCC(A1); + LazyCallGraph::SCC &BC = *CG.lookupSCC(B1); + LazyCallGraph::SCC &CC = *CG.lookupSCC(C1); + LazyCallGraph::SCC &DC = *CG.lookupSCC(D1); + ASSERT_EQ(&AC, CG.lookupSCC(A2)); + ASSERT_EQ(&AC, CG.lookupSCC(A3)); + ASSERT_EQ(&BC, CG.lookupSCC(B2)); + ASSERT_EQ(&BC, CG.lookupSCC(B3)); + ASSERT_EQ(&CC, CG.lookupSCC(C2)); + ASSERT_EQ(&CC, CG.lookupSCC(C3)); + ASSERT_EQ(&DC, CG.lookupSCC(D2)); + ASSERT_EQ(&DC, CG.lookupSCC(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 | + CC.insertIncomingEdge(D2, C2); + // Make sure we connected the nodes. + EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); + + // Make sure we have the correct nodes in the SCC sets. + EXPECT_EQ(&AC, CG.lookupSCC(A1)); + EXPECT_EQ(&AC, CG.lookupSCC(A2)); + EXPECT_EQ(&AC, CG.lookupSCC(A3)); + EXPECT_EQ(&BC, CG.lookupSCC(B1)); + EXPECT_EQ(&BC, CG.lookupSCC(B2)); + EXPECT_EQ(&BC, CG.lookupSCC(B3)); + EXPECT_EQ(&CC, CG.lookupSCC(C1)); + EXPECT_EQ(&CC, CG.lookupSCC(C2)); + EXPECT_EQ(&CC, CG.lookupSCC(C3)); + EXPECT_EQ(&CC, CG.lookupSCC(D1)); + EXPECT_EQ(&CC, CG.lookupSCC(D2)); + EXPECT_EQ(&CC, CG.lookupSCC(D3)); + + // And that ancestry tests have been updated. + EXPECT_TRUE(AC.isParentOf(BC)); + EXPECT_TRUE(AC.isParentOf(CC)); + EXPECT_FALSE(AC.isAncestorOf(DC)); + EXPECT_FALSE(BC.isAncestorOf(DC)); + EXPECT_FALSE(CC.isAncestorOf(DC)); +} + +TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { + // This is the same fundamental test as the previous, but we perform it + // having only partially walked the SCCs of the graph. + std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); + LazyCallGraph CG(*M); + + // Walk the SCCs until we find the one containing 'c1'. + auto SCCI = CG.postorder_scc_begin(), SCCE = CG.postorder_scc_end(); + ASSERT_NE(SCCI, SCCE); + LazyCallGraph::SCC &DC = *SCCI; + ASSERT_NE(&DC, nullptr); + ++SCCI; + ASSERT_NE(SCCI, SCCE); + LazyCallGraph::SCC &CC = *SCCI; + ASSERT_NE(&CC, 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(&CC, CG.lookupSCC(C1)); + ASSERT_EQ(&CC, CG.lookupSCC(C2)); + ASSERT_EQ(&CC, CG.lookupSCC(C3)); + ASSERT_EQ(&DC, CG.lookupSCC(D1)); + ASSERT_EQ(&DC, CG.lookupSCC(D2)); + ASSERT_EQ(&DC, CG.lookupSCC(D3)); + ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); + + CC.insertIncomingEdge(D2, C2); + EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); + + // Make sure we have the correct nodes in the SCC sets. + EXPECT_EQ(&CC, CG.lookupSCC(C1)); + EXPECT_EQ(&CC, CG.lookupSCC(C2)); + EXPECT_EQ(&CC, CG.lookupSCC(C3)); + EXPECT_EQ(&CC, CG.lookupSCC(D1)); + EXPECT_EQ(&CC, CG.lookupSCC(D2)); + EXPECT_EQ(&CC, CG.lookupSCC(D3)); + + // Check that we can form the last two SCCs now in a coherent way. + ++SCCI; + EXPECT_NE(SCCI, SCCE); + LazyCallGraph::SCC &BC = *SCCI; + EXPECT_NE(&BC, nullptr); + EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b1")))); + EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b2")))); + EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b3")))); + ++SCCI; + EXPECT_NE(SCCI, SCCE); + LazyCallGraph::SCC &AC = *SCCI; + EXPECT_NE(&AC, nullptr); + EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a1")))); + EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a2")))); + EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a3")))); + ++SCCI; + EXPECT_EQ(SCCI, SCCE); +} + TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { std::unique_ptr<Module> M = parseAssembly( "define void @a() {\n" |