[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

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index 121054b704858b4312b6df3e9f3e0d44641ff479..c8da2bec180d006f7153eb1575e1e1df6df936ce 100644 (file)
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -275,6 +275,22 @@ public:
     /// graph.
     void insertOutgoingEdge(Node &CallerN, Node &CalleeN);
 
+    /// \brief Insert an edge whose tail is in a descendant SCC and head is in
+    /// this SCC.
+    ///
+    /// There must be an existing path from the callee to the caller in this
+    /// case. NB! This is has the potential to be a very expensive function. It
+    /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs
+    /// to resolve that cycle. But finding all of the SCCs which participate in
+    /// the cycle can in the worst case require traversing every SCC in the
+    /// graph. Every attempt is made to avoid that, but passes must still
+    /// exercise caution calling this routine repeatedly.
+    ///
+    /// FIXME: We could possibly optimize this quite a bit for cases where the
+    /// caller and callee are very nearby in the graph. See comments in the
+    /// implementation for details, but that use case might impact users.
+    SmallVector<SCC *, 1> insertIncomingEdge(Node &CallerN, Node &CalleeN);
+
     /// \brief Remove an edge whose source is in this SCC and target is *not*.
     ///
     /// This removes an inter-SCC edge. All inter-SCC edges originating from

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index fbcacd8b0bf755241eaa7fe00ed82d844979b315..50b532c07d0781f2c354d4232732311e486d80f9 100644 (file)
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -202,6 +202,125 @@ void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) {
   CalleeC.ParentSCCs.insert(this);
 }
 
+SmallVector<LazyCallGraph::SCC *, 1>
+LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) {
+  // First insert it into the caller.
+  CallerN.insertEdgeInternal(CalleeN);
+
+  assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
+
+  SCC &CallerC = *G->SCCMap.lookup(&CallerN);
+  assert(&CallerC != this && "Caller must not be in this SCC.");
+  assert(CallerC.isDescendantOf(*this) &&
+         "Caller must be a descendant of the Callee.");
+
+  // The algorithm we use for merging SCCs based on the cycle introduced here
+  // is to walk the SCC inverted DAG formed by the parent SCC sets. The inverse
+  // graph has the same cycle properties as the actual DAG of the SCCs, and
+  // when forming SCCs lazily by a DFS, the bottom of the graph won't exist in
+  // many cases which should prune the search space.
+  //
+  // FIXME: We can get this pruning behavior even after the incremental SCC
+  // formation by leaving behind (conservative) DFS numberings in the nodes,
+  // and pruning the search with them. These would need to be cleverly updated
+  // during the removal of intra-SCC edges, but could be preserved
+  // conservatively.
+
+  // The set of SCCs that are connected to the caller, and thus will
+  // participate in the merged connected component.
+  SmallPtrSet<SCC *, 8> ConnectedSCCs;
+  ConnectedSCCs.insert(this);
+  ConnectedSCCs.insert(&CallerC);
+
+  // We build up a DFS stack of the parents chains.
+  SmallVector<std::pair<SCC *, SCC::parent_iterator>, 8> DFSSCCs;
+  SmallPtrSet<SCC *, 8> VisitedSCCs;
+  int ConnectedDepth = -1;
+  SCC *C = this;
+  parent_iterator I = parent_begin(), E = parent_end();
+  for (;;) {
+    while (I != E) {
+      SCC &ParentSCC = *I++;
+
+      // If we have already processed this parent SCC, skip it, and remember
+      // whether it was connected so we don't have to check the rest of the
+      // stack. This also handles when we reach a child of the 'this' SCC (the
+      // callee) which terminates the search.
+      if (ConnectedSCCs.count(&ParentSCC)) {
+        ConnectedDepth = std::max<int>(ConnectedDepth, DFSSCCs.size());
+        continue;
+      }
+      if (VisitedSCCs.count(&ParentSCC))
+        continue;
+
+      // We fully explore the depth-first space, adding nodes to the connected
+      // set only as we pop them off, so "recurse" by rotating to the parent.
+      DFSSCCs.push_back(std::make_pair(C, I));
+      C = &ParentSCC;
+      I = ParentSCC.parent_begin();
+      E = ParentSCC.parent_end();
+    }
+
+    // If we've found a connection anywhere below this point on the stack (and
+    // thus up the parent graph from the caller), the current node needs to be
+    // added to the connected set now that we've processed all of its parents.
+    if ((int)DFSSCCs.size() == ConnectedDepth) {
+      --ConnectedDepth; // We're finished with this connection.
+      ConnectedSCCs.insert(C);
+    } else {
+      // Otherwise remember that its parents don't ever connect.
+      assert(ConnectedDepth < (int)DFSSCCs.size() &&
+             "Cannot have a connected depth greater than the DFS depth!");
+      VisitedSCCs.insert(C);
+    }
+
+    if (DFSSCCs.empty())
+      break; // We've walked all the parents of the caller transitively.
+
+    // Pop off the prior node and position to unwind the depth first recursion.
+    std::tie(C, I) = DFSSCCs.pop_back_val();
+    E = C->parent_end();
+  }
+
+  // Now that we have identified all of the SCCs which need to be merged into
+  // a connected set with the inserted edge, merge all of them into this SCC.
+  // FIXME: This operation currently creates ordering stability problems
+  // because we don't use stably ordered containers for the parent SCCs or the
+  // connected SCCs.
+  unsigned NewNodeBeginIdx = Nodes.size();
+  for (SCC *C : ConnectedSCCs) {
+    if (C == this)
+      continue;
+    for (SCC *ParentC : C->ParentSCCs)
+      if (!ConnectedSCCs.count(ParentC))
+        ParentSCCs.insert(ParentC);
+    C->ParentSCCs.clear();
+
+    for (Node *N : *C) {
+      for (Node &ChildN : *N) {
+        SCC &ChildC = *G->SCCMap.lookup(&ChildN);
+        if (&ChildC != C)
+          ChildC.ParentSCCs.erase(C);
+      }
+      G->SCCMap[N] = this;
+      Nodes.push_back(N);
+    }
+    C->Nodes.clear();
+  }
+  for (auto I = Nodes.begin() + NewNodeBeginIdx, E = Nodes.end(); I != E; ++I)
+    for (Node &ChildN : **I) {
+      SCC &ChildC = *G->SCCMap.lookup(&ChildN);
+      if (&ChildC != this)
+        ChildC.ParentSCCs.insert(this);
+    }
+
+  // We return the list of SCCs which were merged so that callers can
+  // invalidate any data they have associated with those SCCs. Note that these
+  // SCCs are no longer in an interesting state (they are totally empty) but
+  // the pointers will remain stable for the life of the graph itself.
+  return SmallVector<SCC *, 1>(ConnectedSCCs.begin(), ConnectedSCCs.end());
+}
+
 void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) {
   // First remove it from the node.
   CallerN.removeEdgeInternal(CalleeN.getFunction());

diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp
index 40bccd217d177fdfc14e0e7907e633936556ed36..8c7b567afc9a4d0a1dcf121ff6cf557e279f41fc 100644 (file)
--- 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"