From 3ce8291da368d6c46c3d7f3a3f195562fe8a7a37 Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Thu, 1 May 2014 12:18:20 +0000
Subject: [PATCH] [LCG] Add the other simple edge insertion API to the call
 graph. This just connects an SCC to one of its descendants directly. Not much
 of an impact. The last one is the hard one -- connecting an SCC to one of its
 ancestors, and thereby forming a cycle such that we have to merge all the
 SCCs participating in the cycle.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207751 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/LazyCallGraph.h    |  8 ++++
 lib/Analysis/LazyCallGraph.cpp           | 15 +++++++
 unittests/Analysis/LazyCallGraphTest.cpp | 53 ++++++++++++++++++++++++
 3 files changed, 76 insertions(+)

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index df4fddf8669..121054b7048 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -267,6 +267,14 @@ public:
     /// of any SCCs.
     void insertIntraSCCEdge(Node &CallerN, Node &CalleeN);
 
+    /// \brief Insert an edge whose tail is in this SCC and head is in some
+    /// child SCC.
+    ///
+    /// There must be an existing path from the caller to the callee. This
+    /// operation is inexpensive and does not change the set of SCCs in the
+    /// graph.
+    void insertOutgoingEdge(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 276956b644d..fbcacd8b0bf 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -187,6 +187,21 @@ void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) {
   // Nothing changes about this SCC or any other.
 }
 
+void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) {
+  // First insert it into the caller.
+  CallerN.insertEdgeInternal(CalleeN);
+
+  assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
+
+  SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
+  assert(&CalleeC != this && "Callee must not be in this SCC.");
+  assert(CalleeC.isDescendantOf(*this) &&
+         "Callee must be a descendant of the Caller.");
+
+  // The only change required is to add this SCC to the parent set of the callee.
+  CalleeC.ParentSCCs.insert(this);
+}
+
 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 24ca2c9433d..039206a1d74 100644
--- a/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/unittests/Analysis/LazyCallGraphTest.cpp
@@ -452,6 +452,59 @@ TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) {
   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
 }
 
+TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) {
+  std::unique_ptr<Module> M = parseAssembly(
+      "define void @a() {\n"
+      "entry:\n"
+      "  call void @b()\n"
+      "  call void @c()\n"
+      "  ret void\n"
+      "}\n"
+      "define void @b() {\n"
+      "entry:\n"
+      "  call void @d()\n"
+      "  ret void\n"
+      "}\n"
+      "define void @c() {\n"
+      "entry:\n"
+      "  call void @d()\n"
+      "  ret void\n"
+      "}\n"
+      "define void @d() {\n"
+      "entry:\n"
+      "  ret void\n"
+      "}\n");
+  LazyCallGraph CG(*M);
+
+  // Force the graph to be fully expanded.
+  for (LazyCallGraph::SCC &C : CG.postorder_sccs())
+    (void)C;
+
+  LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
+  LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
+  LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
+  LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
+  LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
+  LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
+  EXPECT_TRUE(AC.isAncestorOf(BC));
+  EXPECT_TRUE(AC.isAncestorOf(CC));
+  EXPECT_TRUE(AC.isAncestorOf(DC));
+  EXPECT_TRUE(DC.isDescendantOf(AC));
+  EXPECT_TRUE(DC.isDescendantOf(BC));
+  EXPECT_TRUE(DC.isDescendantOf(CC));
+
+  EXPECT_EQ(2, std::distance(A.begin(), A.end()));
+  AC.insertOutgoingEdge(A, D);
+  EXPECT_EQ(3, std::distance(A.begin(), A.end()));
+  EXPECT_TRUE(AC.isParentOf(DC));
+  EXPECT_EQ(&AC, CG.lookupSCC(A));
+  EXPECT_EQ(&BC, CG.lookupSCC(B));
+  EXPECT_EQ(&CC, CG.lookupSCC(C));
+  EXPECT_EQ(&DC, CG.lookupSCC(D));
+}
+
 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
   // A nice fully connected (including self-edges) SCC.
   std::unique_ptr<Module> M1 = parseAssembly(
-- 
2.34.1