X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=unittests%2FAnalysis%2FLazyCallGraphTest.cpp;h=6caccb892395e32352d6d7317898ae2e60c5f896;hb=813f44a29fd0fd140127023222d0633e23783bcc;hp=3fbd3ec20f12a6acedf7837051dba4eb3174c3d6;hpb=e52aad42029beb74d50bc493df34b4971ed74b31;p=oota-llvm.git diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp index 3fbd3ec20f1..6caccb89239 100644 --- a/unittests/Analysis/LazyCallGraphTest.cpp +++ b/unittests/Analysis/LazyCallGraphTest.cpp @@ -22,38 +22,38 @@ using namespace llvm; namespace { std::unique_ptr parseAssembly(const char *Assembly) { - auto M = make_unique("Module", getGlobalContext()); - SMDiagnostic Error; - bool Parsed = - ParseAssemblyString(Assembly, M.get(), Error, M->getContext()) == M.get(); + std::unique_ptr M = + parseAssemblyString(Assembly, Error, getGlobalContext()); std::string ErrMsg; raw_string_ostream OS(ErrMsg); Error.print("", OS); // A failure here means that the test itself is buggy. - if (!Parsed) + if (!M) report_fatal_error(OS.str().c_str()); return M; } -// IR forming a call graph with a diamond of triangle-shaped SCCs: -// -// d1 -// / \ -// d3--d2 -// / \ -// b1 c1 -// / \ / \ -// b3--b2 c3--c2 -// \ / -// a1 -// / \ -// a3--a2 -// -// All call edges go up between SCCs, and clockwise around the SCC. +/* + IR forming a call graph with a diamond of triangle-shaped SCCs: + + d1 + / \ + d3--d2 + / \ + b1 c1 + / \ / \ + b3--b2 c3--c2 + \ / + a1 + / \ + a3--a2 + + All call edges go up between SCCs, and clockwise around the SCC. + */ static const char DiamondOfTriangles[] = "define void @a1() {\n" "entry:\n" @@ -214,6 +214,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ("d2", Nodes[1]); EXPECT_EQ("d3", Nodes[2]); Nodes.clear(); + EXPECT_FALSE(D.isParentOf(D)); + EXPECT_FALSE(D.isChildOf(D)); + EXPECT_FALSE(D.isAncestorOf(D)); + EXPECT_FALSE(D.isDescendantOf(D)); LazyCallGraph::SCC &C = *SCCI++; for (LazyCallGraph::Node *N : C) @@ -224,6 +228,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ("c2", Nodes[1]); EXPECT_EQ("c3", Nodes[2]); Nodes.clear(); + EXPECT_TRUE(C.isParentOf(D)); + EXPECT_FALSE(C.isChildOf(D)); + EXPECT_TRUE(C.isAncestorOf(D)); + EXPECT_FALSE(C.isDescendantOf(D)); LazyCallGraph::SCC &B = *SCCI++; for (LazyCallGraph::Node *N : B) @@ -234,6 +242,12 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ("b2", Nodes[1]); EXPECT_EQ("b3", Nodes[2]); Nodes.clear(); + EXPECT_TRUE(B.isParentOf(D)); + EXPECT_FALSE(B.isChildOf(D)); + EXPECT_TRUE(B.isAncestorOf(D)); + EXPECT_FALSE(B.isDescendantOf(D)); + EXPECT_FALSE(B.isAncestorOf(C)); + EXPECT_FALSE(C.isAncestorOf(B)); LazyCallGraph::SCC &A = *SCCI++; for (LazyCallGraph::Node *N : A) @@ -244,6 +258,12 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ("a2", Nodes[1]); EXPECT_EQ("a3", Nodes[2]); Nodes.clear(); + EXPECT_TRUE(A.isParentOf(B)); + EXPECT_TRUE(A.isParentOf(C)); + EXPECT_FALSE(A.isParentOf(D)); + EXPECT_TRUE(A.isAncestorOf(B)); + EXPECT_TRUE(A.isAncestorOf(C)); + EXPECT_TRUE(A.isAncestorOf(D)); EXPECT_EQ(CG.postorder_scc_end(), SCCI); } @@ -255,6 +275,54 @@ static Function &lookupFunction(Module &M, StringRef Name) { report_fatal_error("Couldn't find function!"); } +TEST(LazyCallGraphTest, BasicGraphMutation) { + std::unique_ptr 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" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); + LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_EQ(0, std::distance(B.begin(), B.end())); + + CG.insertEdge(B, lookupFunction(*M, "c")); + EXPECT_EQ(1, std::distance(B.begin(), B.end())); + LazyCallGraph::Node &C = *B.begin(); + EXPECT_EQ(0, std::distance(C.begin(), C.end())); + + CG.insertEdge(C, B.getFunction()); + EXPECT_EQ(1, std::distance(C.begin(), C.end())); + EXPECT_EQ(&B, &*C.begin()); + + CG.insertEdge(C, C.getFunction()); + EXPECT_EQ(2, std::distance(C.begin(), C.end())); + EXPECT_EQ(&B, &*C.begin()); + EXPECT_EQ(&C, &*std::next(C.begin())); + + CG.removeEdge(C, B.getFunction()); + EXPECT_EQ(1, std::distance(C.begin(), C.end())); + EXPECT_EQ(&C, &*C.begin()); + + CG.removeEdge(C, C.getFunction()); + EXPECT_EQ(0, std::distance(C.begin(), C.end())); + + CG.removeEdge(B, C.getFunction()); + EXPECT_EQ(0, std::distance(B.begin(), B.end())); +} + TEST(LazyCallGraphTest, MultiArmSCC) { // Two interlocking cycles. The really useful thing about this SCC is that it // will require Tarjan's DFS to backtrack and finish processing all of the @@ -305,6 +373,214 @@ TEST(LazyCallGraphTest, MultiArmSCC) { EXPECT_EQ(&SCC, CG.lookupSCC(E)); } +TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { + std::unique_ptr 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, 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 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 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 M = parseAssembly( "define void @a() {\n" @@ -338,6 +614,52 @@ TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { EXPECT_EQ(BC.parent_end(), BC.parent_begin()); } +TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { + std::unique_ptr M1 = parseAssembly( + "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 @a()\n" + " ret void\n" + "}\n"); + LazyCallGraph CG1(*M1); + + // Force the graph to be fully expanded. + auto SCCI = CG1.postorder_scc_begin(); + LazyCallGraph::SCC &SCC = *SCCI++; + EXPECT_EQ(CG1.postorder_scc_end(), SCCI); + + LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a")); + LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b")); + LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c")); + EXPECT_EQ(&SCC, CG1.lookupSCC(A)); + EXPECT_EQ(&SCC, CG1.lookupSCC(B)); + EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + + // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs. + SCC.insertIntraSCCEdge(A, C); + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_EQ(&SCC, CG1.lookupSCC(A)); + EXPECT_EQ(&SCC, CG1.lookupSCC(B)); + EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + + // Insert a self edge from 'a' back to 'a'. + SCC.insertIntraSCCEdge(A, A); + EXPECT_EQ(3, std::distance(A.begin(), A.end())); + EXPECT_EQ(&SCC, CG1.lookupSCC(A)); + EXPECT_EQ(&SCC, CG1.lookupSCC(B)); + EXPECT_EQ(&SCC, CG1.lookupSCC(C)); +} + TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { // A nice fully connected (including self-edges) SCC. std::unique_ptr M1 = parseAssembly(