[LCG] Add the last (and most complex) of the edge insertion mutation
operations on the call graph. This one forms a cycle, and while not as
complex as removing an internal edge from an SCC, it involves
a reasonable amount of work to find all of the nodes newly connected in
a cycle.
Also somewhat alarming is the worst case complexity here: it might have
to walk roughly the entire SCC inverse DAG to insert a single edge. This
is carefully documented in the API (I hope).
llvm-svn: 207935
diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
index 40bccd2..8c7b567 100644
--- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
@@ -426,6 +426,161 @@
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<Module> 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<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);
+
+ 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<Module> M = parseAssembly(
"define void @a() {\n"