From febf86d7e3c6ebab9f1974ea369919811c2eda28 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 4 May 2014 09:38:32 +0000 Subject: [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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207935 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/Analysis/LazyCallGraphTest.cpp | 155 +++++++++++++++++++++++++++++++ 1 file changed, 155 insertions(+) (limited to 'unittests') diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp index 40bccd217d..8c7b567afc 100644 --- a/unittests/Analysis/LazyCallGraphTest.cpp +++ b/unittests/Analysis/LazyCallGraphTest.cpp @@ -426,6 +426,161 @@ TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { 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" -- cgit v1.2.3