diff options
Diffstat (limited to 'llvm/unittests/Analysis/LazyCallGraphTest.cpp')
| -rw-r--r-- | llvm/unittests/Analysis/LazyCallGraphTest.cpp | 985 |
1 files changed, 781 insertions, 204 deletions
diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp index fb3eeb7..457c07d 100644 --- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp @@ -202,12 +202,13 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ(D3.end(), std::next(D3.begin())); EXPECT_EQ("d1", D3.begin()->getFunction().getName()); - // Now lets look at the SCCs. - auto SCCI = CG.postorder_scc_begin(); + // Now lets look at the RefSCCs and SCCs. + auto J = CG.postorder_ref_scc_begin(); - LazyCallGraph::SCC &D = *SCCI++; - for (LazyCallGraph::Node *N : D) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &D = *J++; + ASSERT_EQ(1, D.size()); + for (LazyCallGraph::Node &N : *D.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("d1", Nodes[0]); @@ -219,9 +220,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_FALSE(D.isAncestorOf(D)); EXPECT_FALSE(D.isDescendantOf(D)); - LazyCallGraph::SCC &C = *SCCI++; - for (LazyCallGraph::Node *N : C) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &C = *J++; + ASSERT_EQ(1, C.size()); + for (LazyCallGraph::Node &N : *C.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("c1", Nodes[0]); @@ -233,9 +235,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_TRUE(C.isAncestorOf(D)); EXPECT_FALSE(C.isDescendantOf(D)); - LazyCallGraph::SCC &B = *SCCI++; - for (LazyCallGraph::Node *N : B) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &B = *J++; + ASSERT_EQ(1, B.size()); + for (LazyCallGraph::Node &N : *B.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("b1", Nodes[0]); @@ -249,9 +252,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_FALSE(B.isAncestorOf(C)); EXPECT_FALSE(C.isAncestorOf(B)); - LazyCallGraph::SCC &A = *SCCI++; - for (LazyCallGraph::Node *N : A) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &A = *J++; + ASSERT_EQ(1, A.size()); + for (LazyCallGraph::Node &N : *A.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("a1", Nodes[0]); @@ -265,7 +269,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_TRUE(A.isAncestorOf(C)); EXPECT_TRUE(A.isAncestorOf(D)); - EXPECT_EQ(CG.postorder_scc_end(), SCCI); + EXPECT_EQ(CG.postorder_ref_scc_end(), J); } static Function &lookupFunction(Module &M, StringRef Name) { @@ -323,57 +327,130 @@ TEST(LazyCallGraphTest, BasicGraphMutation) { EXPECT_EQ(0, std::distance(B.begin(), B.end())); } +TEST(LazyCallGraphTest, InnerSCCFormation) { + std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); + LazyCallGraph CG(*M); + + // Now mutate the graph to connect every node into a single RefSCC to ensure + // that our inner SCC formation handles the rest. + CG.insertEdge(lookupFunction(*M, "d1"), lookupFunction(*M, "a1"), + LazyCallGraph::Edge::Ref); + + // Build vectors and sort them for the rest of the assertions to make them + // independent of order. + std::vector<std::string> Nodes; + + // We should build a single RefSCC for the entire graph. + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + // Now walk the four SCCs which should be in post-order. + auto J = RC.begin(); + LazyCallGraph::SCC &D = *J++; + for (LazyCallGraph::Node &N : D) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("d1", Nodes[0]); + EXPECT_EQ("d2", Nodes[1]); + EXPECT_EQ("d3", Nodes[2]); + Nodes.clear(); + + LazyCallGraph::SCC &B = *J++; + for (LazyCallGraph::Node &N : B) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("b1", Nodes[0]); + EXPECT_EQ("b2", Nodes[1]); + EXPECT_EQ("b3", Nodes[2]); + Nodes.clear(); + + LazyCallGraph::SCC &C = *J++; + for (LazyCallGraph::Node &N : C) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("c1", Nodes[0]); + EXPECT_EQ("c2", Nodes[1]); + EXPECT_EQ("c3", Nodes[2]); + Nodes.clear(); + + LazyCallGraph::SCC &A = *J++; + for (LazyCallGraph::Node &N : A) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("a1", Nodes[0]); + EXPECT_EQ("a2", Nodes[1]); + EXPECT_EQ("a3", Nodes[2]); + Nodes.clear(); + + EXPECT_EQ(RC.end(), J); +} + 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 - // children of each node in the SCC. + // children of each node in the SCC. Since this involves call edges, both + // Tarjan implementations will have to successfully navigate the structure. std::unique_ptr<Module> M = parseAssembly( - "define void @a() {\n" + "define void @f1() {\n" "entry:\n" - " call void @b()\n" - " call void @d()\n" + " call void @f2()\n" + " call void @f4()\n" " ret void\n" "}\n" - "define void @b() {\n" + "define void @f2() {\n" "entry:\n" - " call void @c()\n" + " call void @f3()\n" " ret void\n" "}\n" - "define void @c() {\n" + "define void @f3() {\n" "entry:\n" - " call void @a()\n" + " call void @f1()\n" " ret void\n" "}\n" - "define void @d() {\n" + "define void @f4() {\n" "entry:\n" - " call void @e()\n" + " call void @f5()\n" " ret void\n" "}\n" - "define void @e() {\n" + "define void @f5() {\n" "entry:\n" - " call void @a()\n" + " call void @f1()\n" " ret void\n" "}\n"); LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto SCCI = CG.postorder_scc_begin(); - LazyCallGraph::SCC &SCC = *SCCI++; - EXPECT_EQ(CG.postorder_scc_end(), SCCI); - - 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::Node &E = *CG.lookup(lookupFunction(*M, "e")); - EXPECT_EQ(&SCC, CG.lookupSCC(A)); - EXPECT_EQ(&SCC, CG.lookupSCC(B)); - EXPECT_EQ(&SCC, CG.lookupSCC(C)); - EXPECT_EQ(&SCC, CG.lookupSCC(D)); - EXPECT_EQ(&SCC, CG.lookupSCC(E)); + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1")); + LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2")); + LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3")); + LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4")); + LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4")); + EXPECT_EQ(&RC, CG.lookupRefSCC(N1)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N2)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N3)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N4)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N5)); + + ASSERT_EQ(1, RC.size()); + + LazyCallGraph::SCC &C = *RC.begin(); + EXPECT_EQ(&C, CG.lookupSCC(N1)); + EXPECT_EQ(&C, CG.lookupSCC(N2)); + EXPECT_EQ(&C, CG.lookupSCC(N3)); + EXPECT_EQ(&C, CG.lookupSCC(N4)); + EXPECT_EQ(&C, CG.lookupSCC(N5)); } -TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { +TEST(LazyCallGraphTest, OutgoingEdgeMutation) { std::unique_ptr<Module> M = parseAssembly( "define void @a() {\n" "entry:\n" @@ -398,8 +475,8 @@ TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { LazyCallGraph CG(*M); // Force the graph to be fully expanded. - for (LazyCallGraph::SCC &C : CG.postorder_sccs()) - (void)C; + for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) + (void)RC; LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); @@ -409,24 +486,95 @@ TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { 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)); + LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); + LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); + LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); + LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); + EXPECT_TRUE(ARC.isParentOf(BRC)); + EXPECT_TRUE(ARC.isParentOf(CRC)); + EXPECT_FALSE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_FALSE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_TRUE(DRC.isChildOf(BRC)); + EXPECT_TRUE(DRC.isChildOf(CRC)); EXPECT_EQ(2, std::distance(A.begin(), A.end())); - AC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); + ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); EXPECT_EQ(3, std::distance(A.begin(), A.end())); - EXPECT_TRUE(AC.isParentOf(DC)); + const LazyCallGraph::Edge &NewE = A[D]; + EXPECT_TRUE(NewE); + EXPECT_TRUE(NewE.isCall()); + EXPECT_EQ(&D, NewE.getNode()); + + // Only the parent and child tests sholud have changed. The rest of the graph + // remains the same. + EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); EXPECT_EQ(&AC, CG.lookupSCC(A)); EXPECT_EQ(&BC, CG.lookupSCC(B)); EXPECT_EQ(&CC, CG.lookupSCC(C)); EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + + ARC.switchOutgoingEdgeToRef(A, D); + EXPECT_FALSE(NewE.isCall()); + + // Verify the graph remains the same. + EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_EQ(&AC, CG.lookupSCC(A)); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + + ARC.switchOutgoingEdgeToCall(A, D); + EXPECT_TRUE(NewE.isCall()); + + // Verify the graph remains the same. + EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_EQ(&AC, CG.lookupSCC(A)); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + + ARC.removeOutgoingEdge(A, D); + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + + // Now the parent and child tests fail again but the rest remains the same. + EXPECT_FALSE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_FALSE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_EQ(&AC, CG.lookupSCC(A)); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); } -TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { +TEST(LazyCallGraphTest, IncomingEdgeInsertion) { // 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. @@ -447,8 +595,8 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { LazyCallGraph CG(*M); // Force the graph to be fully expanded. - for (LazyCallGraph::SCC &C : CG.postorder_sccs()) - (void)C; + for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) + (void)RC; LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); @@ -462,18 +610,18 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { 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)); + 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: @@ -489,47 +637,51 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { // a1 | // / \ | // a3--a2 | - CC.insertIncomingEdge(D2, C2, LazyCallGraph::Edge::Call); + auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); // Make sure we connected the nodes. - EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); + 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(&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)); + 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(AC.isParentOf(BC)); - EXPECT_TRUE(AC.isParentOf(CC)); - EXPECT_FALSE(AC.isAncestorOf(DC)); - EXPECT_FALSE(BC.isAncestorOf(DC)); - EXPECT_FALSE(CC.isAncestorOf(DC)); + EXPECT_TRUE(ARC.isParentOf(CRC)); + EXPECT_TRUE(BRC.isParentOf(CRC)); } -TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { +TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { // This is the same fundamental test as the previous, but we perform it - // having only partially walked the SCCs of the graph. + // having only partially walked the RefSCCs 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); + // 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"))); @@ -543,45 +695,55 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { 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(&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())); - CC.insertIncomingEdge(D2, C2, LazyCallGraph::Edge::Call); - 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); + 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 RefSCCs. + 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)); + + // Check that we can form the last two RefSCCs now in a coherent way. + ++I; + EXPECT_NE(I, E); + LazyCallGraph::RefSCC &BRC = *I; + 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_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(CRC)); + ++I; + EXPECT_EQ(E, I); } -TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { +TEST(LazyCallGraphTest, InternalEdgeMutation) { std::unique_ptr<Module> M = parseAssembly( "define void @a() {\n" "entry:\n" @@ -590,79 +752,138 @@ TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { "}\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 CG(*M); // Force the graph to be fully expanded. - for (LazyCallGraph::SCC &C : CG.postorder_sccs()) - (void)C; + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); 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(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + EXPECT_EQ(1, RC.size()); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); + + // Insert an edge from 'a' to 'c'. Nothing changes about the graph. + RC.insertInternalRefEdge(A, C); + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + EXPECT_EQ(1, RC.size()); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); + + // 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); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + auto J = RC.begin(); + // The SCCs must be in *post-order* which means successors before + // predecessors. At this point we have call edges from C to A and from A to + // B. The only valid postorder is B, A, C. + EXPECT_EQ(&*J++, CG.lookupSCC(B)); + EXPECT_EQ(&*J++, CG.lookupSCC(A)); + EXPECT_EQ(&*J++, CG.lookupSCC(C)); + EXPECT_EQ(RC.end(), J); + + // 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 + // C SCC should be preserved and have A merged into it while the A SCC should + // be invalidated. LazyCallGraph::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &BC = *CG.lookupSCC(B); - - EXPECT_EQ("b", A.begin()->getFunction().getName()); - EXPECT_EQ(B.end(), B.begin()); - EXPECT_EQ(&AC, &*BC.parent_begin()); - - AC.removeInterSCCEdge(A, B); - - EXPECT_EQ(A.end(), A.begin()); - EXPECT_EQ(B.end(), B.begin()); - EXPECT_EQ(BC.parent_end(), BC.parent_begin()); + LazyCallGraph::SCC &CC = *CG.lookupSCC(C); + auto InvalidatedSCCs = RC.switchInternalEdgeToCall(A, C); + ASSERT_EQ(1u, InvalidatedSCCs.size()); + EXPECT_EQ(&AC, InvalidatedSCCs[0]); + EXPECT_EQ(2, CC.size()); + EXPECT_EQ(&CC, CG.lookupSCC(A)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + J = RC.begin(); + EXPECT_EQ(&*J++, CG.lookupSCC(B)); + EXPECT_EQ(&*J++, CG.lookupSCC(C)); + EXPECT_EQ(RC.end(), J); } -TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { - std::unique_ptr<Module> M1 = parseAssembly( - "define void @a() {\n" +TEST(LazyCallGraphTest, InternalEdgeRemoval) { + // A nice fully connected (including self-edges) RefSCC. + std::unique_ptr<Module> M = parseAssembly( + "define void @a(i8** %ptr) {\n" "entry:\n" - " call void @b()\n" + " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" " ret void\n" "}\n" - "define void @b() {\n" + "define void @b(i8** %ptr) {\n" "entry:\n" - " call void @c()\n" + " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" " ret void\n" "}\n" - "define void @c() {\n" + "define void @c(i8** %ptr) {\n" "entry:\n" - " call void @a()\n" + " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" " ret void\n" "}\n"); - LazyCallGraph CG1(*M1); + LazyCallGraph CG(*M); // 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, LazyCallGraph::Edge::Call); - 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)); + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); - // Insert a self edge from 'a' back to 'a'. - SCC.insertIntraSCCEdge(A, A, LazyCallGraph::Edge::Call); - 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)); + 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(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + + // Remove the edge from b -> a, which should leave the 3 functions still in + // a single connected component because of a -> b -> c -> a. + SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = + RC.removeInternalRefEdge(B, A); + EXPECT_EQ(0u, NewRCs.size()); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + + // Remove the edge from c -> a, which should leave 'a' in the original RefSCC + // and form a new RefSCC for 'b' and 'c'. + NewRCs = RC.removeInternalRefEdge(C, A); + 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]); } -TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { - // A nice fully connected (including self-edges) SCC. - std::unique_ptr<Module> M1 = parseAssembly( +TEST(LazyCallGraphTest, InternalCallEdgeToRef) { + // A nice fully connected (including self-edges) SCC (and RefSCC) + std::unique_ptr<Module> M = parseAssembly( "define void @a() {\n" "entry:\n" " call void @a()\n" @@ -684,37 +905,393 @@ TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { " call void @c()\n" " ret void\n" "}\n"); - LazyCallGraph CG1(*M1); + LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto SCCI = CG1.postorder_scc_begin(); - LazyCallGraph::SCC &SCC = *SCCI++; - EXPECT_EQ(CG1.postorder_scc_end(), SCCI); + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); - 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)); + EXPECT_EQ(1, RC.size()); + LazyCallGraph::SCC &CallC = *RC.begin(); - // Remove the edge from b -> a, which should leave the 3 functions still in - // a single connected component because of a -> b -> c -> a. - SmallVector<LazyCallGraph::SCC *, 1> NewSCCs = SCC.removeIntraSCCEdge(B, A); - EXPECT_EQ(0u, NewSCCs.size()); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(&SCC, CG1.lookupSCC(B)); - EXPECT_EQ(&SCC, CG1.lookupSCC(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")); + EXPECT_EQ(&CallC, CG.lookupSCC(A)); + EXPECT_EQ(&CallC, CG.lookupSCC(B)); + EXPECT_EQ(&CallC, CG.lookupSCC(C)); + + // 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); + EXPECT_EQ(1, RC.size()); + EXPECT_EQ(&CallC, CG.lookupSCC(A)); + EXPECT_EQ(&CallC, CG.lookupSCC(B)); + EXPECT_EQ(&CallC, CG.lookupSCC(C)); // Remove the edge from c -> a, which should leave 'a' in the original SCC // and form a new SCC for 'b' and 'c'. - NewSCCs = SCC.removeIntraSCCEdge(C, A); - EXPECT_EQ(1u, NewSCCs.size()); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end())); - LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B); - EXPECT_EQ(SCC2, CG1.lookupSCC(C)); - EXPECT_EQ(SCC2, NewSCCs[0]); + RC.switchInternalEdgeToRef(C, A); + 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); + --J; + EXPECT_EQ(&BCallC, &*J); + EXPECT_EQ(RC.begin(), J); + + // 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); + 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); + --J; + EXPECT_EQ(&BCallC, &*J); + --J; + EXPECT_EQ(&CCallC, &*J); + EXPECT_EQ(RC.begin(), J); +} + +TEST(LazyCallGraphTest, InternalRefEdgeToCall) { + // Basic tests for making a ref edge a call. This hits the basics of the + // process only. + std::unique_ptr<Module> M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " call void @c()\n" + " store void()* @d, void()** undef\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " store void()* @c, void()** undef\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " store void()* @b, void()** undef\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " store void()* @a, void()** undef\n" + " ret void\n" + "}\n"); + 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); + + 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); + + // Check the initial post-order. Note that B and C could be flipped here (and + // in our mutation) without changing the nature of this test. + ASSERT_EQ(4, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&BC, &RC[1]); + EXPECT_EQ(&CC, &RC[2]); + EXPECT_EQ(&AC, &RC[3]); + + // Switch the ref edge from A -> D to a call edge. This should have no + // effect as it is already in postorder and no new cycles are formed. + auto MergedCs = RC.switchInternalEdgeToCall(A, D); + EXPECT_EQ(0u, MergedCs.size()); + ASSERT_EQ(4, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&BC, &RC[1]); + EXPECT_EQ(&CC, &RC[2]); + EXPECT_EQ(&AC, &RC[3]); + + // Switch B -> C to a call edge. This doesn't form any new cycles but does + // require reordering the SCCs. + MergedCs = RC.switchInternalEdgeToCall(B, C); + EXPECT_EQ(0u, MergedCs.size()); + ASSERT_EQ(4, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&CC, &RC[1]); + EXPECT_EQ(&BC, &RC[2]); + EXPECT_EQ(&AC, &RC[3]); + + // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. + MergedCs = RC.switchInternalEdgeToCall(C, B); + ASSERT_EQ(1u, MergedCs.size()); + EXPECT_EQ(&CC, MergedCs[0]); + ASSERT_EQ(3, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&BC, &RC[1]); + EXPECT_EQ(&AC, &RC[2]); + EXPECT_EQ(2, BC.size()); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&BC, CG.lookupSCC(C)); +} + +TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { + // Test for having a post-order prior to changing a ref edge to a call edge + // with SCCs connecting to the source and connecting to the target, but not + // connecting to both, interleaved between the source and target. This + // ensures we correctly partition the range rather than simply moving one or + // the other. + std::unique_ptr<Module> M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b1()\n" + " call void @c1()\n" + " ret void\n" + "}\n" + "define void @b1() {\n" + "entry:\n" + " call void @c1()\n" + " call void @b2()\n" + " ret void\n" + "}\n" + "define void @c1() {\n" + "entry:\n" + " call void @b2()\n" + " call void @c2()\n" + " ret void\n" + "}\n" + "define void @b2() {\n" + "entry:\n" + " call void @c2()\n" + " call void @b3()\n" + " ret void\n" + "}\n" + "define void @c2() {\n" + "entry:\n" + " call void @b3()\n" + " call void @c3()\n" + " ret void\n" + "}\n" + "define void @b3() {\n" + "entry:\n" + " call void @c3()\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @c3() {\n" + "entry:\n" + " store void()* @b1, void()** undef\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " store void()* @a, void()** undef\n" + " ret void\n" + "}\n"); + 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); + + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + 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 &D = *CG.lookup(lookupFunction(*M, "d")); + LazyCallGraph::SCC &AC = *CG.lookupSCC(A); + LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1); + LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2); + LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3); + LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1); + LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2); + LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3); + LazyCallGraph::SCC &DC = *CG.lookupSCC(D); + + // 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); + + // Check the initial post-order. We ensure this order with the extra edges + // that are nuked above. + ASSERT_EQ(8, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&C3C, &RC[1]); + EXPECT_EQ(&B3C, &RC[2]); + EXPECT_EQ(&C2C, &RC[3]); + EXPECT_EQ(&B2C, &RC[4]); + EXPECT_EQ(&C1C, &RC[5]); + EXPECT_EQ(&B1C, &RC[6]); + EXPECT_EQ(&AC, &RC[7]); + + // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does + // require reordering the SCCs in the face of tricky internal node + // structures. + auto MergedCs = RC.switchInternalEdgeToCall(C3, B1); + EXPECT_EQ(0u, MergedCs.size()); + ASSERT_EQ(8, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&B3C, &RC[1]); + EXPECT_EQ(&B2C, &RC[2]); + EXPECT_EQ(&B1C, &RC[3]); + EXPECT_EQ(&C3C, &RC[4]); + EXPECT_EQ(&C2C, &RC[5]); + EXPECT_EQ(&C1C, &RC[6]); + EXPECT_EQ(&AC, &RC[7]); +} + +TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { + // Test for having a postorder where between the source and target are all + // three kinds of other SCCs: + // 1) One connected to the target only that have to be shifted below the + // source. + // 2) One connected to the source only that have to be shifted below the + // target. + // 3) One connected to both source and target that has to remain and get + // merged away. + // + // To achieve this we construct a heavily connected graph to force + // a particular post-order. Then we remove the forcing edges and connect + // a cycle. + // + // Diagram for the graph we want on the left and the graph we use to force + // the ordering on the right. Edges ponit down or right. + // + // A | A | + // / \ | / \ | + // B E | B \ | + // |\ | | |\ | | + // | D | | C-D-E | + // | \| | | \| | + // C F | \ F | + // \ / | \ / | + // G | G | + // + // And we form a cycle by connecting F to B. + std::unique_ptr<Module> M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " call void @e()\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " call void @c()\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " call void @d()\n" + " call void @g()\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " call void @e()\n" + " call void @f()\n" + " ret void\n" + "}\n" + "define void @e() {\n" + "entry:\n" + " call void @f()\n" + " ret void\n" + "}\n" + "define void @f() {\n" + "entry:\n" + " store void()* @b, void()** undef\n" + " call void @g()\n" + " ret void\n" + "}\n" + "define void @g() {\n" + "entry:\n" + " store void()* @a, void()** undef\n" + " ret void\n" + "}\n"); + 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); + + 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::Node &E = *CG.lookup(lookupFunction(*M, "e")); + LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); + LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); + 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::SCC &EC = *CG.lookupSCC(E); + LazyCallGraph::SCC &FC = *CG.lookupSCC(F); + 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); + + // Check the initial post-order. We ensure this order with the extra edges + // that are nuked above. + ASSERT_EQ(7, RC.size()); + EXPECT_EQ(&GC, &RC[0]); + EXPECT_EQ(&FC, &RC[1]); + EXPECT_EQ(&EC, &RC[2]); + EXPECT_EQ(&DC, &RC[3]); + EXPECT_EQ(&CC, &RC[4]); + EXPECT_EQ(&BC, &RC[5]); + EXPECT_EQ(&AC, &RC[6]); + + // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, + // and has to place the C and E SCCs on either side of it: + // A A | + // / \ / \ | + // B E | E | + // |\ | \ / | + // | D | -> B | + // | \| / \ | + // C F C | | + // \ / \ / | + // G G | + auto MergedCs = RC.switchInternalEdgeToCall(F, B); + ASSERT_EQ(2u, MergedCs.size()); + EXPECT_EQ(&FC, MergedCs[0]); + EXPECT_EQ(&DC, MergedCs[1]); + EXPECT_EQ(3, BC.size()); + + // And make sure the postorder was updated. + ASSERT_EQ(5, RC.size()); + EXPECT_EQ(&GC, &RC[0]); + EXPECT_EQ(&CC, &RC[1]); + EXPECT_EQ(&BC, &RC[2]); + EXPECT_EQ(&EC, &RC[3]); + EXPECT_EQ(&AC, &RC[4]); } } |