aboutsummaryrefslogtreecommitdiff
path: root/unittests/Analysis/LazyCallGraphTest.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'unittests/Analysis/LazyCallGraphTest.cpp')
-rw-r--r--unittests/Analysis/LazyCallGraphTest.cpp622
1 files changed, 274 insertions, 348 deletions
diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp
index 5bb9dec3449f..6955beb37109 100644
--- a/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/unittests/Analysis/LazyCallGraphTest.cpp
@@ -225,29 +225,29 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
// the IR, and everything in our module is an entry node, so just directly
// build variables for each node.
auto I = CG.begin();
- LazyCallGraph::Node &A1 = (I++)->getNode(CG);
+ LazyCallGraph::Node &A1 = (I++)->getNode();
EXPECT_EQ("a1", A1.getFunction().getName());
- LazyCallGraph::Node &A2 = (I++)->getNode(CG);
+ LazyCallGraph::Node &A2 = (I++)->getNode();
EXPECT_EQ("a2", A2.getFunction().getName());
- LazyCallGraph::Node &A3 = (I++)->getNode(CG);
+ LazyCallGraph::Node &A3 = (I++)->getNode();
EXPECT_EQ("a3", A3.getFunction().getName());
- LazyCallGraph::Node &B1 = (I++)->getNode(CG);
+ LazyCallGraph::Node &B1 = (I++)->getNode();
EXPECT_EQ("b1", B1.getFunction().getName());
- LazyCallGraph::Node &B2 = (I++)->getNode(CG);
+ LazyCallGraph::Node &B2 = (I++)->getNode();
EXPECT_EQ("b2", B2.getFunction().getName());
- LazyCallGraph::Node &B3 = (I++)->getNode(CG);
+ LazyCallGraph::Node &B3 = (I++)->getNode();
EXPECT_EQ("b3", B3.getFunction().getName());
- LazyCallGraph::Node &C1 = (I++)->getNode(CG);
+ LazyCallGraph::Node &C1 = (I++)->getNode();
EXPECT_EQ("c1", C1.getFunction().getName());
- LazyCallGraph::Node &C2 = (I++)->getNode(CG);
+ LazyCallGraph::Node &C2 = (I++)->getNode();
EXPECT_EQ("c2", C2.getFunction().getName());
- LazyCallGraph::Node &C3 = (I++)->getNode(CG);
+ LazyCallGraph::Node &C3 = (I++)->getNode();
EXPECT_EQ("c3", C3.getFunction().getName());
- LazyCallGraph::Node &D1 = (I++)->getNode(CG);
+ LazyCallGraph::Node &D1 = (I++)->getNode();
EXPECT_EQ("d1", D1.getFunction().getName());
- LazyCallGraph::Node &D2 = (I++)->getNode(CG);
+ LazyCallGraph::Node &D2 = (I++)->getNode();
EXPECT_EQ("d2", D2.getFunction().getName());
- LazyCallGraph::Node &D3 = (I++)->getNode(CG);
+ LazyCallGraph::Node &D3 = (I++)->getNode();
EXPECT_EQ("d3", D3.getFunction().getName());
EXPECT_EQ(CG.end(), I);
@@ -255,7 +255,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
// independent of order.
std::vector<std::string> Nodes;
- for (LazyCallGraph::Edge &E : A1)
+ for (LazyCallGraph::Edge &E : A1.populate())
Nodes.push_back(E.getFunction().getName());
std::sort(Nodes.begin(), Nodes.end());
EXPECT_EQ("a2", Nodes[0]);
@@ -263,43 +263,53 @@ TEST(LazyCallGraphTest, BasicGraphFormation) {
EXPECT_EQ("c3", Nodes[2]);
Nodes.clear();
- EXPECT_EQ(A2.end(), std::next(A2.begin()));
- EXPECT_EQ("a3", A2.begin()->getFunction().getName());
- EXPECT_EQ(A3.end(), std::next(A3.begin()));
- EXPECT_EQ("a1", A3.begin()->getFunction().getName());
+ A2.populate();
+ EXPECT_EQ(A2->end(), std::next(A2->begin()));
+ EXPECT_EQ("a3", A2->begin()->getFunction().getName());
+ A3.populate();
+ EXPECT_EQ(A3->end(), std::next(A3->begin()));
+ EXPECT_EQ("a1", A3->begin()->getFunction().getName());
- for (LazyCallGraph::Edge &E : B1)
+ for (LazyCallGraph::Edge &E : B1.populate())
Nodes.push_back(E.getFunction().getName());
std::sort(Nodes.begin(), Nodes.end());
EXPECT_EQ("b2", Nodes[0]);
EXPECT_EQ("d3", Nodes[1]);
Nodes.clear();
- EXPECT_EQ(B2.end(), std::next(B2.begin()));
- EXPECT_EQ("b3", B2.begin()->getFunction().getName());
- EXPECT_EQ(B3.end(), std::next(B3.begin()));
- EXPECT_EQ("b1", B3.begin()->getFunction().getName());
+ B2.populate();
+ EXPECT_EQ(B2->end(), std::next(B2->begin()));
+ EXPECT_EQ("b3", B2->begin()->getFunction().getName());
+ B3.populate();
+ EXPECT_EQ(B3->end(), std::next(B3->begin()));
+ EXPECT_EQ("b1", B3->begin()->getFunction().getName());
- for (LazyCallGraph::Edge &E : C1)
+ for (LazyCallGraph::Edge &E : C1.populate())
Nodes.push_back(E.getFunction().getName());
std::sort(Nodes.begin(), Nodes.end());
EXPECT_EQ("c2", Nodes[0]);
EXPECT_EQ("d2", Nodes[1]);
Nodes.clear();
- EXPECT_EQ(C2.end(), std::next(C2.begin()));
- EXPECT_EQ("c3", C2.begin()->getFunction().getName());
- EXPECT_EQ(C3.end(), std::next(C3.begin()));
- EXPECT_EQ("c1", C3.begin()->getFunction().getName());
-
- EXPECT_EQ(D1.end(), std::next(D1.begin()));
- EXPECT_EQ("d2", D1.begin()->getFunction().getName());
- EXPECT_EQ(D2.end(), std::next(D2.begin()));
- EXPECT_EQ("d3", D2.begin()->getFunction().getName());
- EXPECT_EQ(D3.end(), std::next(D3.begin()));
- EXPECT_EQ("d1", D3.begin()->getFunction().getName());
+ C2.populate();
+ EXPECT_EQ(C2->end(), std::next(C2->begin()));
+ EXPECT_EQ("c3", C2->begin()->getFunction().getName());
+ C3.populate();
+ EXPECT_EQ(C3->end(), std::next(C3->begin()));
+ EXPECT_EQ("c1", C3->begin()->getFunction().getName());
+
+ D1.populate();
+ EXPECT_EQ(D1->end(), std::next(D1->begin()));
+ EXPECT_EQ("d2", D1->begin()->getFunction().getName());
+ D2.populate();
+ EXPECT_EQ(D2->end(), std::next(D2->begin()));
+ EXPECT_EQ("d3", D2->begin()->getFunction().getName());
+ D3.populate();
+ EXPECT_EQ(D3->end(), std::next(D3->begin()));
+ EXPECT_EQ("d1", D3->begin()->getFunction().getName());
// Now lets look at the RefSCCs and SCCs.
+ CG.buildRefSCCs();
auto J = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &D = *J++;
@@ -401,32 +411,35 @@ TEST(LazyCallGraphTest, BasicGraphMutation) {
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"), LazyCallGraph::Edge::Call);
- EXPECT_EQ(1, std::distance(B.begin(), B.end()));
- LazyCallGraph::Node &C = B.begin()->getNode(CG);
- EXPECT_EQ(0, std::distance(C.begin(), C.end()));
-
- CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call);
- EXPECT_EQ(1, std::distance(C.begin(), C.end()));
- EXPECT_EQ(&B, C.begin()->getNode());
-
- CG.insertEdge(C, C.getFunction(), LazyCallGraph::Edge::Call);
- EXPECT_EQ(2, std::distance(C.begin(), C.end()));
- EXPECT_EQ(&B, C.begin()->getNode());
- EXPECT_EQ(&C, std::next(C.begin())->getNode());
-
- CG.removeEdge(C, B.getFunction());
- EXPECT_EQ(1, std::distance(C.begin(), C.end()));
- EXPECT_EQ(&C, C.begin()->getNode());
-
- 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()));
+ A.populate();
+ EXPECT_EQ(2, std::distance(A->begin(), A->end()));
+ B.populate();
+ EXPECT_EQ(0, std::distance(B->begin(), B->end()));
+
+ LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c"));
+ C.populate();
+ CG.insertEdge(B, C, LazyCallGraph::Edge::Call);
+ EXPECT_EQ(1, std::distance(B->begin(), B->end()));
+ EXPECT_EQ(0, std::distance(C->begin(), C->end()));
+
+ CG.insertEdge(C, B, LazyCallGraph::Edge::Call);
+ EXPECT_EQ(1, std::distance(C->begin(), C->end()));
+ EXPECT_EQ(&B, &C->begin()->getNode());
+
+ CG.insertEdge(C, C, LazyCallGraph::Edge::Call);
+ EXPECT_EQ(2, std::distance(C->begin(), C->end()));
+ EXPECT_EQ(&B, &C->begin()->getNode());
+ EXPECT_EQ(&C, &std::next(C->begin())->getNode());
+
+ CG.removeEdge(C, B);
+ EXPECT_EQ(1, std::distance(C->begin(), C->end()));
+ EXPECT_EQ(&C, &C->begin()->getNode());
+
+ CG.removeEdge(C, C);
+ EXPECT_EQ(0, std::distance(C->begin(), C->end()));
+
+ CG.removeEdge(B, C);
+ EXPECT_EQ(0, std::distance(B->begin(), B->end()));
}
TEST(LazyCallGraphTest, InnerSCCFormation) {
@@ -436,14 +449,18 @@ TEST(LazyCallGraphTest, InnerSCCFormation) {
// 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);
+ LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1"));
+ LazyCallGraph::Node &A1 = CG.get(lookupFunction(*M, "a1"));
+ A1.populate();
+ D1.populate();
+ CG.insertEdge(D1, 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.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &RC = *I++;
EXPECT_EQ(CG.postorder_ref_scc_end(), I);
@@ -528,6 +545,7 @@ TEST(LazyCallGraphTest, MultiArmSCC) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &RC = *I++;
EXPECT_EQ(CG.postorder_ref_scc_end(), I);
@@ -578,6 +596,7 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
dbgs() << "Formed RefSCC: " << RC << "\n";
@@ -610,13 +629,13 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
EXPECT_TRUE(DRC.isChildOf(CRC));
EXPECT_TRUE(DC.isChildOf(CC));
- EXPECT_EQ(2, std::distance(A.begin(), A.end()));
+ EXPECT_EQ(2, std::distance(A->begin(), A->end()));
ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call);
- EXPECT_EQ(3, std::distance(A.begin(), A.end()));
- const LazyCallGraph::Edge &NewE = A[D];
+ EXPECT_EQ(3, std::distance(A->begin(), A->end()));
+ const LazyCallGraph::Edge &NewE = (*A)[D];
EXPECT_TRUE(NewE);
EXPECT_TRUE(NewE.isCall());
- EXPECT_EQ(&D, NewE.getNode());
+ EXPECT_EQ(&D, &NewE.getNode());
// Only the parent and child tests sholud have changed. The rest of the graph
// remains the same.
@@ -680,7 +699,7 @@ TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
ARC.removeOutgoingEdge(A, D);
- EXPECT_EQ(2, std::distance(A.begin(), A.end()));
+ 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));
@@ -723,6 +742,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
dbgs() << "Formed RefSCC: " << RC << "\n";
@@ -750,7 +770,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
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()));
+ ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
// Add an edge to make the graph:
//
@@ -767,10 +787,10 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
// a3--a2 |
auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
// Make sure we connected the nodes.
- for (LazyCallGraph::Edge E : D2) {
- if (E.getNode() == &D3)
+ for (LazyCallGraph::Edge E : *D2) {
+ if (&E.getNode() == &D3)
continue;
- EXPECT_EQ(&C2, E.getNode());
+ EXPECT_EQ(&C2, &E.getNode());
}
// And marked the D ref-SCC as no longer valid.
EXPECT_EQ(1u, MergedRCs.size());
@@ -805,102 +825,6 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
EXPECT_EQ(++I, E);
}
-TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) {
- LLVMContext Context;
- // This is the same fundamental test as the previous, but we perform it
- // having only partially walked the RefSCCs of the graph.
- 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()));
-
- 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));
-
- // 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 &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
@@ -910,6 +834,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
dbgs() << "Formed RefSCC: " << RC << "\n";
@@ -937,7 +862,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {
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()));
+ ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
// Add an edge to make the graph:
//
@@ -954,10 +879,10 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {
// a3--a2 |
auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
// Make sure we connected the nodes.
- for (LazyCallGraph::Edge E : D2) {
- if (E.getNode() == &D3)
+ for (LazyCallGraph::Edge E : *D2) {
+ if (&E.getNode() == &D3)
continue;
- EXPECT_EQ(&C2, E.getNode());
+ EXPECT_EQ(&C2, &E.getNode());
}
// And marked the D ref-SCC as no longer valid.
EXPECT_EQ(1u, MergedRCs.size());
@@ -1016,6 +941,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
dbgs() << "Formed RefSCC: " << RC << "\n";
@@ -1035,8 +961,8 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) {
// 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());
+ 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());
@@ -1092,6 +1018,7 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
dbgs() << "Formed RefSCC: " << RC << "\n";
@@ -1108,8 +1035,8 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
// 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());
+ 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());
@@ -1153,6 +1080,7 @@ TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
dbgs() << "Formed RefSCC: " << RC << "\n";
@@ -1180,7 +1108,7 @@ TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
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()));
+ ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
// Delete d2 from the graph, as if it had been inlined.
//
@@ -1276,177 +1204,6 @@ TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
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(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;
- 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(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) {
LLVMContext Context;
std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
@@ -1467,6 +1224,7 @@ TEST(LazyCallGraphTest, InternalEdgeMutation) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &RC = *I++;
EXPECT_EQ(CG.postorder_ref_scc_end(), I);
@@ -1484,7 +1242,7 @@ TEST(LazyCallGraphTest, InternalEdgeMutation) {
// 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(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));
@@ -1559,6 +1317,7 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
LazyCallGraph::RefSCC &RC = *I;
EXPECT_EQ(E, std::next(I));
@@ -1633,6 +1392,7 @@ TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
LazyCallGraph::RefSCC &RC = *I;
EXPECT_EQ(E, std::next(I));
@@ -1709,6 +1469,7 @@ TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &RC = *I++;
EXPECT_EQ(CG.postorder_ref_scc_end(), I);
@@ -1801,6 +1562,7 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCall) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &RC = *I++;
EXPECT_EQ(CG.postorder_ref_scc_end(), I);
@@ -1913,6 +1675,7 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &RC = *I++;
EXPECT_EQ(CG.postorder_ref_scc_end(), I);
@@ -2043,6 +1806,7 @@ TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
LazyCallGraph CG(*M);
// Force the graph to be fully expanded.
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &RC = *I++;
EXPECT_EQ(CG.postorder_ref_scc_end(), I);
@@ -2122,6 +1886,7 @@ TEST(LazyCallGraphTest, HandleBlockAddress) {
"}\n");
LazyCallGraph CG(*M);
+ CG.buildRefSCCs();
auto I = CG.postorder_ref_scc_begin();
LazyCallGraph::RefSCC &FRC = *I++;
LazyCallGraph::RefSCC &GRC = *I++;
@@ -2134,4 +1899,165 @@ TEST(LazyCallGraphTest, HandleBlockAddress) {
EXPECT_TRUE(GRC.isParentOf(FRC));
}
+TEST(LazyCallGraphTest, ReplaceNodeFunction) {
+ LLVMContext Context;
+ // A graph with several different kinds of edges pointing at a particular
+ // function.
+ std::unique_ptr<Module> M =
+ parseAssembly(Context,
+ "define void @a(i8** %ptr) {\n"
+ "entry:\n"
+ " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
+ " ret void\n"
+ "}\n"
+ "define void @b(i8** %ptr) {\n"
+ "entry:\n"
+ " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
+ " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
+ " call void @d(i8** %ptr)"
+ " ret void\n"
+ "}\n"
+ "define void @c(i8** %ptr) {\n"
+ "entry:\n"
+ " call void @d(i8** %ptr)"
+ " call void @d(i8** %ptr)"
+ " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
+ " ret void\n"
+ "}\n"
+ "define void @d(i8** %ptr) {\n"
+ "entry:\n"
+ " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
+ " call void @c(i8** %ptr)"
+ " call void @d(i8** %ptr)"
+ " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
+ " ret void\n"
+ "}\n");
+ LazyCallGraph CG(*M);
+
+ // Force the graph to be fully expanded.
+ CG.buildRefSCCs();
+ auto I = CG.postorder_ref_scc_begin();
+ LazyCallGraph::RefSCC &RC1 = *I++;
+ LazyCallGraph::RefSCC &RC2 = *I++;
+ EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+
+ ASSERT_EQ(2, RC1.size());
+ LazyCallGraph::SCC &C1 = RC1[0];
+ LazyCallGraph::SCC &C2 = RC1[1];
+
+ LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
+ LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
+ LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
+ LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d"));
+ EXPECT_EQ(&C1, CG.lookupSCC(DN));
+ EXPECT_EQ(&C1, CG.lookupSCC(CN));
+ EXPECT_EQ(&C2, CG.lookupSCC(BN));
+ EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
+ EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
+ EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
+ EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
+
+ // Now we need to build a new function 'e' with the same signature as 'd'.
+ Function &D = DN.getFunction();
+ Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e");
+ D.getParent()->getFunctionList().insert(D.getIterator(), &E);
+
+ // Change each use of 'd' to use 'e'. This is particularly easy as they have
+ // the same type.
+ D.replaceAllUsesWith(&E);
+
+ // Splice the body of the old function into the new one.
+ E.getBasicBlockList().splice(E.begin(), D.getBasicBlockList());
+ // And fix up the one argument.
+ D.arg_begin()->replaceAllUsesWith(&*E.arg_begin());
+ E.arg_begin()->takeName(&*D.arg_begin());
+
+ // Now replace the function in the graph.
+ RC1.replaceNodeFunction(DN, E);
+
+ EXPECT_EQ(&E, &DN.getFunction());
+ EXPECT_EQ(&DN, &(*CN)[DN].getNode());
+ EXPECT_EQ(&DN, &(*BN)[DN].getNode());
+}
+
+TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) {
+ LLVMContext Context;
+ // A graph with a couple of RefSCCs.
+ std::unique_ptr<Module> M =
+ parseAssembly(Context,
+ "define void @a(i8** %ptr) {\n"
+ "entry:\n"
+ " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
+ " ret void\n"
+ "}\n"
+ "define void @b(i8** %ptr) {\n"
+ "entry:\n"
+ " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
+ " ret void\n"
+ "}\n"
+ "define void @c(i8** %ptr) {\n"
+ "entry:\n"
+ " call void @d(i8** %ptr)"
+ " ret void\n"
+ "}\n"
+ "define void @d(i8** %ptr) {\n"
+ "entry:\n"
+ " call void @c(i8** %ptr)"
+ " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
+ " ret void\n"
+ "}\n"
+ "define void @dead() {\n"
+ "entry:\n"
+ " ret void\n"
+ "}\n");
+ LazyCallGraph CG(*M);
+
+ // Insert spurious ref edges.
+ LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
+ LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
+ LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
+ LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));
+ LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead"));
+ AN.populate();
+ BN.populate();
+ CN.populate();
+ DN.populate();
+ DeadN.populate();
+ CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref);
+ CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref);
+ CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref);
+ CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref);
+
+ // Force the graph to be fully expanded.
+ CG.buildRefSCCs();
+ auto I = CG.postorder_ref_scc_begin();
+ LazyCallGraph::RefSCC &DeadRC = *I++;
+ LazyCallGraph::RefSCC &RC1 = *I++;
+ LazyCallGraph::RefSCC &RC2 = *I++;
+ EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+
+ ASSERT_EQ(2, RC1.size());
+ LazyCallGraph::SCC &C1 = RC1[0];
+ LazyCallGraph::SCC &C2 = RC1[1];
+
+ EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN));
+ EXPECT_EQ(&C1, CG.lookupSCC(DN));
+ EXPECT_EQ(&C1, CG.lookupSCC(CN));
+ EXPECT_EQ(&C2, CG.lookupSCC(BN));
+ EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
+ EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
+ EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
+ EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
+
+ // Now delete 'dead'. There are no uses of this function but there are
+ // spurious references.
+ CG.removeDeadFunction(DeadN.getFunction());
+
+ // The only observable change should be that the RefSCC is gone from the
+ // postorder sequence.
+ I = CG.postorder_ref_scc_begin();
+ EXPECT_EQ(&RC1, &*I++);
+ EXPECT_EQ(&RC2, &*I++);
+ EXPECT_EQ(CG.postorder_ref_scc_end(), I);
+}
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-10 03:03:11 +0000