diff options
Diffstat (limited to 'gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp')
| -rw-r--r-- | gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp | 932 |
1 files changed, 882 insertions, 50 deletions
diff --git a/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp index 224a9458cc8..5bb9dec3449 100644 --- a/gnu/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ b/gnu/llvm/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" @@ -120,6 +121,101 @@ static const char DiamondOfTriangles[] = " 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<Module> M = parseAssembly(Context, DiamondOfTriangles); @@ -220,6 +316,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { 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 +332,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { 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 +350,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { 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 +368,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { 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 +579,7 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) { // 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")); @@ -493,13 +594,21 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) { LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); EXPECT_TRUE(ARC.isParentOf(BRC)); + EXPECT_TRUE(AC.isParentOf(BC)); EXPECT_TRUE(ARC.isParentOf(CRC)); + EXPECT_TRUE(AC.isParentOf(CC)); EXPECT_FALSE(ARC.isParentOf(DRC)); + EXPECT_FALSE(AC.isParentOf(DC)); EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(AC.isAncestorOf(DC)); EXPECT_FALSE(DRC.isChildOf(ARC)); + EXPECT_FALSE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_TRUE(DC.isDescendantOf(AC)); EXPECT_TRUE(DRC.isChildOf(BRC)); + EXPECT_TRUE(DC.isChildOf(BC)); EXPECT_TRUE(DRC.isChildOf(CRC)); + EXPECT_TRUE(DC.isChildOf(CC)); EXPECT_EQ(2, std::distance(A.begin(), A.end())); ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); @@ -512,9 +621,13 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) { // Only the parent and child tests sholud have changed. The rest of the graph // remains the same. EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(AC.isParentOf(DC)); EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(AC.isAncestorOf(DC)); EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_TRUE(DC.isDescendantOf(AC)); EXPECT_EQ(&AC, CG.lookupSCC(A)); EXPECT_EQ(&BC, CG.lookupSCC(B)); EXPECT_EQ(&CC, CG.lookupSCC(C)); @@ -527,11 +640,15 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) { ARC.switchOutgoingEdgeToRef(A, D); EXPECT_FALSE(NewE.isCall()); - // Verify the graph remains the same. + // Verify the reference graph remains the same but the SCC graph is updated. EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_FALSE(AC.isParentOf(DC)); EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(AC.isAncestorOf(DC)); EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_FALSE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_TRUE(DC.isDescendantOf(AC)); EXPECT_EQ(&AC, CG.lookupSCC(A)); EXPECT_EQ(&BC, CG.lookupSCC(B)); EXPECT_EQ(&CC, CG.lookupSCC(C)); @@ -544,11 +661,15 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) { ARC.switchOutgoingEdgeToCall(A, D); EXPECT_TRUE(NewE.isCall()); - // Verify the graph remains the same. + // Verify the reference graph remains the same but the SCC graph is updated. EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(AC.isParentOf(DC)); EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(AC.isAncestorOf(DC)); EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_TRUE(DC.isDescendantOf(AC)); EXPECT_EQ(&AC, CG.lookupSCC(A)); EXPECT_EQ(&BC, CG.lookupSCC(B)); EXPECT_EQ(&CC, CG.lookupSCC(C)); @@ -563,9 +684,13 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) { // Now the parent and child tests fail again but the rest remains the same. EXPECT_FALSE(ARC.isParentOf(DRC)); + EXPECT_FALSE(AC.isParentOf(DC)); EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(AC.isAncestorOf(DC)); EXPECT_FALSE(DRC.isChildOf(ARC)); + EXPECT_FALSE(DC.isChildOf(AC)); EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_TRUE(DC.isDescendantOf(AC)); EXPECT_EQ(&AC, CG.lookupSCC(A)); EXPECT_EQ(&BC, CG.lookupSCC(B)); EXPECT_EQ(&CC, CG.lookupSCC(C)); @@ -599,7 +724,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) { // 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 +793,16 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) { // 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,15 +861,574 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { 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. + // 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 &BRC = *I; + 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(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<Module> 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<Module> 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(find(MergedRCs, &BRC), MergedRCs.end()); + EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); + EXPECT_NE(find(MergedRCs, &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<Module> 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 just of + // references. + 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(find(MergedRCs, &BRC), MergedRCs.end()); + EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end()); + EXPECT_NE(find(MergedRCs, &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, 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<Module> 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<CallInst>(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<Module> 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<CallInst>(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(CRC)); + 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; @@ -742,9 +1436,15 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { 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) { @@ -796,7 +1496,7 @@ TEST(LazyCallGraphTest, InternalEdgeMutation) { // Switch the call edge from 'b' to 'c' to a ref edge. This will break the // call cycle and cause us to form more SCCs. The RefSCC will remain the same // though. - RC.switchInternalEdgeToRef(B, C); + auto NewCs = RC.switchInternalEdgeToRef(B, C); EXPECT_EQ(&RC, CG.lookupRefSCC(A)); EXPECT_EQ(&RC, CG.lookupRefSCC(B)); EXPECT_EQ(&RC, CG.lookupRefSCC(C)); @@ -808,6 +1508,10 @@ TEST(LazyCallGraphTest, InternalEdgeMutation) { EXPECT_EQ(&*J++, CG.lookupSCC(A)); EXPECT_EQ(&*J++, CG.lookupSCC(C)); EXPECT_EQ(RC.end(), J); + // And the returned range must be the slice of this sequence containing new + // SCCs. + EXPECT_EQ(RC.begin(), NewCs.begin()); + EXPECT_EQ(std::prev(RC.end()), NewCs.end()); // Test turning the ref edge from A to C into a call edge. This will form an // SCC out of A and C. Since we previously had a call edge from C to A, the @@ -855,9 +1559,9 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) { 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 +1578,10 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) { 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 +1589,97 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) { 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, InternalNoOpEdgeRemoval) { + LLVMContext Context; + // A graph with a single cycle formed both from call and reference edges + // which makes the reference edges trivial to delete. The graph looks like: + // + // Reference edges: a -> b -> c -> a + // Call edges: a -> c -> b -> a + std::unique_ptr<Module> M = parseAssembly( + Context, "define void @a(i8** %ptr) {\n" + "entry:\n" + " call void @b(i8** %ptr)\n" + " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" + " ret void\n" + "}\n" + "define void @b(i8** %ptr) {\n" + "entry:\n" + " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" + " call void @c(i8** %ptr)\n" + " ret void\n" + "}\n" + "define void @c(i8** %ptr) {\n" + "entry:\n" + " call void @a(i8** %ptr)\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); + LazyCallGraph::RefSCC &RC = *I; + EXPECT_EQ(E, std::next(I)); + + LazyCallGraph::SCC &C = *RC.begin(); + EXPECT_EQ(RC.end(), std::next(RC.begin())); + + LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); + EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); + EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); + EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); + EXPECT_EQ(&C, CG.lookupSCC(AN)); + EXPECT_EQ(&C, CG.lookupSCC(BN)); + EXPECT_EQ(&C, CG.lookupSCC(CN)); + + // Remove the edge from a -> c which doesn't change anything. + SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = + RC.removeInternalRefEdge(AN, CN); + EXPECT_EQ(0u, NewRCs.size()); + EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); + EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); + EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); + EXPECT_EQ(&C, CG.lookupSCC(AN)); + EXPECT_EQ(&C, CG.lookupSCC(BN)); + EXPECT_EQ(&C, CG.lookupSCC(CN)); + 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 b -> a and c -> b; again this doesn't change + // anything. + NewRCs = RC.removeInternalRefEdge(BN, AN); + NewRCs = RC.removeInternalRefEdge(CN, BN); + EXPECT_EQ(0u, NewRCs.size()); + EXPECT_EQ(&RC, CG.lookupRefSCC(AN)); + EXPECT_EQ(&RC, CG.lookupRefSCC(BN)); + EXPECT_EQ(&RC, CG.lookupRefSCC(CN)); + EXPECT_EQ(&C, CG.lookupSCC(AN)); + EXPECT_EQ(&C, CG.lookupSCC(BN)); + EXPECT_EQ(&C, CG.lookupSCC(CN)); + J = CG.postorder_ref_scc_begin(); + EXPECT_EQ(I, J); + EXPECT_EQ(&RC, &*J); + EXPECT_EQ(E, std::next(J)); } TEST(LazyCallGraphTest, InternalCallEdgeToRef) { @@ -918,54 +1714,59 @@ TEST(LazyCallGraphTest, InternalCallEdgeToRef) { EXPECT_EQ(CG.postorder_ref_scc_end(), I); EXPECT_EQ(1, RC.size()); - LazyCallGraph::SCC &CallC = *RC.begin(); + LazyCallGraph::SCC &AC = *RC.begin(); - LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); - EXPECT_EQ(&CallC, CG.lookupSCC(A)); - EXPECT_EQ(&CallC, CG.lookupSCC(B)); - EXPECT_EQ(&CallC, CG.lookupSCC(C)); + LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); + EXPECT_EQ(&AC, CG.lookupSCC(AN)); + EXPECT_EQ(&AC, CG.lookupSCC(BN)); + EXPECT_EQ(&AC, CG.lookupSCC(CN)); // Remove the call edge from b -> a to a ref edge, which should leave the // 3 functions still in a single connected component because of a -> b -> // c -> a. - RC.switchInternalEdgeToRef(B, A); + auto NewCs = RC.switchInternalEdgeToRef(BN, AN); + EXPECT_EQ(NewCs.begin(), NewCs.end()); EXPECT_EQ(1, RC.size()); - EXPECT_EQ(&CallC, CG.lookupSCC(A)); - EXPECT_EQ(&CallC, CG.lookupSCC(B)); - EXPECT_EQ(&CallC, CG.lookupSCC(C)); + EXPECT_EQ(&AC, CG.lookupSCC(AN)); + EXPECT_EQ(&AC, CG.lookupSCC(BN)); + EXPECT_EQ(&AC, CG.lookupSCC(CN)); // Remove the edge from c -> a, which should leave 'a' in the original SCC // and form a new SCC for 'b' and 'c'. - RC.switchInternalEdgeToRef(C, A); + NewCs = RC.switchInternalEdgeToRef(CN, AN); + EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); EXPECT_EQ(2, RC.size()); - EXPECT_EQ(&CallC, CG.lookupSCC(A)); - LazyCallGraph::SCC &BCallC = *CG.lookupSCC(B); - EXPECT_NE(&BCallC, &CallC); - EXPECT_EQ(&BCallC, CG.lookupSCC(C)); - auto J = RC.find(CallC); - EXPECT_EQ(&CallC, &*J); + EXPECT_EQ(&AC, CG.lookupSCC(AN)); + LazyCallGraph::SCC &BC = *CG.lookupSCC(BN); + EXPECT_NE(&BC, &AC); + EXPECT_EQ(&BC, CG.lookupSCC(CN)); + auto J = RC.find(AC); + EXPECT_EQ(&AC, &*J); --J; - EXPECT_EQ(&BCallC, &*J); + EXPECT_EQ(&BC, &*J); EXPECT_EQ(RC.begin(), J); + EXPECT_EQ(J, NewCs.begin()); // Remove the edge from c -> b, which should leave 'b' in the original SCC // and form a new SCC for 'c'. It shouldn't change 'a's SCC. - RC.switchInternalEdgeToRef(C, B); + NewCs = RC.switchInternalEdgeToRef(CN, BN); + EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end())); EXPECT_EQ(3, RC.size()); - EXPECT_EQ(&CallC, CG.lookupSCC(A)); - EXPECT_EQ(&BCallC, CG.lookupSCC(B)); - LazyCallGraph::SCC &CCallC = *CG.lookupSCC(C); - EXPECT_NE(&CCallC, &CallC); - EXPECT_NE(&CCallC, &BCallC); - J = RC.find(CallC); - EXPECT_EQ(&CallC, &*J); + EXPECT_EQ(&AC, CG.lookupSCC(AN)); + EXPECT_EQ(&BC, CG.lookupSCC(BN)); + LazyCallGraph::SCC &CC = *CG.lookupSCC(CN); + EXPECT_NE(&CC, &AC); + EXPECT_NE(&CC, &BC); + J = RC.find(AC); + EXPECT_EQ(&AC, &*J); --J; - EXPECT_EQ(&BCallC, &*J); + EXPECT_EQ(&BC, &*J); --J; - EXPECT_EQ(&CCallC, &*J); + EXPECT_EQ(&CC, &*J); EXPECT_EQ(RC.begin(), J); + EXPECT_EQ(J, NewCs.begin()); } TEST(LazyCallGraphTest, InternalRefEdgeToCall) { @@ -1135,11 +1936,11 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { // Several call edges are initially present to force a particual post-order. // Remove them now, leaving an interleaved post-order pattern. - RC.switchInternalEdgeToRef(B3, C3); - RC.switchInternalEdgeToRef(C2, B3); - RC.switchInternalEdgeToRef(B2, C2); - RC.switchInternalEdgeToRef(C1, B2); - RC.switchInternalEdgeToRef(B1, C1); + RC.switchTrivialInternalEdgeToRef(B3, C3); + RC.switchTrivialInternalEdgeToRef(C2, B3); + RC.switchTrivialInternalEdgeToRef(B2, C2); + RC.switchTrivialInternalEdgeToRef(C1, B2); + RC.switchTrivialInternalEdgeToRef(B1, C1); // Check the initial post-order. We ensure this order with the extra edges // that are nuked above. @@ -1262,8 +2063,8 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { LazyCallGraph::SCC &GC = *CG.lookupSCC(G); // Remove the extra edges that were used to force a particular post-order. - RC.switchInternalEdgeToRef(C, D); - RC.switchInternalEdgeToRef(D, E); + RC.switchTrivialInternalEdgeToRef(C, D); + RC.switchTrivialInternalEdgeToRef(D, E); // Check the initial post-order. We ensure this order with the extra edges // that are nuked above. @@ -1302,4 +2103,35 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { EXPECT_EQ(&AC, &RC[4]); } +// Test for IR containing constants using blockaddress constant expressions. +// These are truly unique constructs: constant expressions with non-constant +// operands. +TEST(LazyCallGraphTest, HandleBlockAddress) { + LLVMContext Context; + std::unique_ptr<Module> M = + parseAssembly(Context, "define void @f() {\n" + "entry:\n" + " ret void\n" + "bb:\n" + " unreachable\n" + "}\n" + "define void @g(i8** %ptr) {\n" + "entry:\n" + " store i8* blockaddress(@f, %bb), i8** %ptr\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &FRC = *I++; + LazyCallGraph::RefSCC &GRC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); + LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); + EXPECT_EQ(&FRC, CG.lookupRefSCC(F)); + EXPECT_EQ(&GRC, CG.lookupRefSCC(G)); + EXPECT_TRUE(GRC.isParentOf(FRC)); +} + } |