diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/LazyCallGraph.h | 8 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LazyCallGraph.cpp | 15 | ||||
| -rw-r--r-- | llvm/unittests/Analysis/LazyCallGraphTest.cpp | 53 |
3 files changed, 76 insertions, 0 deletions
diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h index df4fddf8669..121054b7048 100644 --- a/llvm/include/llvm/Analysis/LazyCallGraph.h +++ b/llvm/include/llvm/Analysis/LazyCallGraph.h @@ -267,6 +267,14 @@ public: /// of any SCCs. void insertIntraSCCEdge(Node &CallerN, Node &CalleeN); + /// \brief Insert an edge whose tail is in this SCC and head is in some + /// child SCC. + /// + /// There must be an existing path from the caller to the callee. This + /// operation is inexpensive and does not change the set of SCCs in the + /// graph. + void insertOutgoingEdge(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/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp index 276956b644d..fbcacd8b0bf 100644 --- a/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/llvm/lib/Analysis/LazyCallGraph.cpp @@ -187,6 +187,21 @@ void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) { // Nothing changes about this SCC or any other. } +void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) { + // First insert it into the caller. + CallerN.insertEdgeInternal(CalleeN); + + assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC."); + + SCC &CalleeC = *G->SCCMap.lookup(&CalleeN); + assert(&CalleeC != this && "Callee must not be in this SCC."); + assert(CalleeC.isDescendantOf(*this) && + "Callee must be a descendant of the Caller."); + + // The only change required is to add this SCC to the parent set of the callee. + CalleeC.ParentSCCs.insert(this); +} + void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) { // First remove it from the node. CallerN.removeEdgeInternal(CalleeN.getFunction()); diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp index 24ca2c9433d..039206a1d74 100644 --- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp @@ -452,6 +452,59 @@ TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { EXPECT_EQ(&SCC, CG1.lookupSCC(C)); } +TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { + std::unique_ptr<Module> M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " call void @c()\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " call void @d()\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::SCC &C : CG.postorder_sccs()) + (void)C; + + 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); + EXPECT_TRUE(AC.isAncestorOf(BC)); + EXPECT_TRUE(AC.isAncestorOf(CC)); + EXPECT_TRUE(AC.isAncestorOf(DC)); + EXPECT_TRUE(DC.isDescendantOf(AC)); + EXPECT_TRUE(DC.isDescendantOf(BC)); + EXPECT_TRUE(DC.isDescendantOf(CC)); + + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + AC.insertOutgoingEdge(A, D); + EXPECT_EQ(3, std::distance(A.begin(), A.end())); + EXPECT_TRUE(AC.isParentOf(DC)); + EXPECT_EQ(&AC, CG.lookupSCC(A)); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + EXPECT_EQ(&DC, CG.lookupSCC(D)); +} + TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { // A nice fully connected (including self-edges) SCC. std::unique_ptr<Module> M1 = parseAssembly( |
