[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

1 files changed, 155 insertions, 0 deletions

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<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"