[LCG] Add the necessary functionality to the LazyCallGraph to support inlining.

The basic inlining operation makes the following changes to the call graph:
1) Add edges that were previously transitive edges. This is always trivial and
   this patch gives the LCG helper methods to make this more convenient.
2) Remove the inlined edge. We had existing support for this, but it contained
   bugs that needed to be fixed. Testing in the same pattern as the inliner
   exposes these bugs very nicely.
3) Delete a function when it becomes dead because it is internal and all calls
   have been inlined. The LCG had no support at all for this operation, so this
   adds that support.

Two unittests have been added that exercise this specific mutation pattern to
the call graph. They were extremely effective in uncovering bugs. Sadly,
a large fraction of the code here is just to implement those unit tests, but
I think they're paying for themselves. =]

This was split out of a patch that actually uses the routines to
implement inlining in the new pass manager in order to isolate (with
unit tests) the logic that was entirely within the LCG.

Many thanks for the careful review from folks! There will be a few minor
follow-up patches based on the comments in the review as well.

Differential Revision: https://reviews.llvm.org/D24225

llvm-svn: 283982

1 files changed, 318 insertions, 0 deletions

diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
index 0ac9b6554c2..66cd9a1e485 100644
--- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
@@ -9,6 +9,7 @@
 
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
@@ -1105,6 +1106,323 @@ TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
   EXPECT_EQ(++I, End);
 }
 
+TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
+  LLVMContext Context;
+  // We want to ensure we can delete nodes from relatively complex graphs and
+  // so 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(Context, DiamondOfTriangles);
+  LazyCallGraph CG(*M);
+
+  // Force the graph to be fully expanded.
+  for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
+    dbgs() << "Formed RefSCC: " << RC << "\n";
+
+  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::RefSCC &ARC = *CG.lookupRefSCC(A1);
+  LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
+  LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
+  LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
+  ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
+  ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
+  ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
+  ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
+  ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
+
+  // Delete d2 from the graph, as if it had been inlined.
+  //
+  //         d1         |
+  //        / /         |
+  //       d3--.        |
+  //      /     \       |
+  //     b1     c1      |
+  //   /  \    /  \     |
+  //  b3--b2  c3--c2    |
+  //       \  /         |
+  //        a1          |
+  //       /  \         |
+  //      a3--a2        |
+
+  Function &D2F = D2.getFunction();
+  CallInst *C1Call = nullptr, *D1Call = nullptr;
+  for (User *U : D2F.users()) {
+    CallInst *CI = dyn_cast<CallInst>(U);
+    ASSERT_TRUE(CI) << "Expected a call: " << *U;
+    if (CI->getParent()->getParent() == &C1.getFunction()) {
+      ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
+      C1Call = CI;
+    } else if (CI->getParent()->getParent() == &D1.getFunction()) {
+      ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
+      D1Call = CI;
+    } else {
+      FAIL() << "Found an unexpected call instruction: " << *CI;
+    }
+  }
+  ASSERT_NE(C1Call, nullptr);
+  ASSERT_NE(D1Call, nullptr);
+  ASSERT_EQ(&D2F, C1Call->getCalledFunction());
+  ASSERT_EQ(&D2F, D1Call->getCalledFunction());
+  C1Call->setCalledFunction(&D3.getFunction());
+  D1Call->setCalledFunction(&D3.getFunction());
+  ASSERT_EQ(0u, D2F.getNumUses());
+
+  // Insert new edges first.
+  CRC.insertTrivialCallEdge(C1, D3);
+  DRC.insertTrivialCallEdge(D1, D3);
+
+  // Then remove the old ones.
+  LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);
+  auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);
+  EXPECT_EQ(&DC, CG.lookupSCC(D2));
+  EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
+  LazyCallGraph::SCC &NewDC = *NewCs.begin();
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
+  auto NewRCs = DRC.removeInternalRefEdge(D1, D2);
+  EXPECT_EQ(&DRC, CG.lookupRefSCC(D2));
+  EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin()));
+  LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin();
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_FALSE(NewDRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+  CRC.removeOutgoingEdge(C1, D2);
+  EXPECT_FALSE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+
+  // Now that we've updated the call graph, D2 is dead, so remove it.
+  CG.removeDeadFunction(D2F);
+
+  // Check that the graph still looks the same.
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+
+  // Verify the post-order walk hasn't changed.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
+  ASSERT_NE(++I, E);
+  EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
+  ASSERT_NE(++I, E);
+  EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
+  ASSERT_NE(++I, E);
+  EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
+  EXPECT_EQ(++I, E);
+}
+
+TEST(LazyCallGraphTest, InlineAndDeleteFunctionMidTraversal) {
+  LLVMContext Context;
+  // This is the same fundamental test as the previous, but we perform it
+  // having only partially walked the RefSCCs of the graph.
+  //
+  // 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(Context, DiamondOfTriangles);
+  LazyCallGraph CG(*M);
+
+  // Walk the RefSCCs until we find the one containing 'c1'.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  LazyCallGraph::RefSCC &DRC = *I;
+  ASSERT_NE(&DRC, nullptr);
+  ++I;
+  ASSERT_NE(I, E);
+  LazyCallGraph::RefSCC &CRC = *I;
+  ASSERT_NE(&CRC, 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(&CRC, CG.lookupRefSCC(C1));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D1));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
+  ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
+
+  // Delete d2 from the graph, as if it had been inlined.
+  //
+  //         d1         |
+  //        / /         |
+  //       d3--.        |
+  //      /     \       |
+  //     b1     c1      |
+  //   /  \    /  \     |
+  //  b3--b2  c3--c2    |
+  //       \  /         |
+  //        a1          |
+  //       /  \         |
+  //      a3--a2        |
+
+  Function &D2F = D2.getFunction();
+  CallInst *C1Call = nullptr, *D1Call = nullptr;
+  for (User *U : D2F.users()) {
+    CallInst *CI = dyn_cast<CallInst>(U);
+    ASSERT_TRUE(CI) << "Expected a call: " << *U;
+    if (CI->getParent()->getParent() == &C1.getFunction()) {
+      ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
+      C1Call = CI;
+    } else if (CI->getParent()->getParent() == &D1.getFunction()) {
+      ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
+      D1Call = CI;
+    } else {
+      FAIL() << "Found an unexpected call instruction: " << *CI;
+    }
+  }
+  ASSERT_NE(C1Call, nullptr);
+  ASSERT_NE(D1Call, nullptr);
+  ASSERT_EQ(&D2F, C1Call->getCalledFunction());
+  ASSERT_EQ(&D2F, D1Call->getCalledFunction());
+  C1Call->setCalledFunction(&D3.getFunction());
+  D1Call->setCalledFunction(&D3.getFunction());
+  ASSERT_EQ(0u, D2F.getNumUses());
+
+  // Insert new edges first.
+  CRC.insertTrivialCallEdge(C1, D3);
+  DRC.insertTrivialCallEdge(D1, D3);
+
+  // Then remove the old ones.
+  LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);
+  auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);
+  EXPECT_EQ(&DC, CG.lookupSCC(D2));
+  EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
+  LazyCallGraph::SCC &NewDC = *NewCs.begin();
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
+  auto NewRCs = DRC.removeInternalRefEdge(D1, D2);
+  EXPECT_EQ(&DRC, CG.lookupRefSCC(D2));
+  EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin()));
+  LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin();
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_FALSE(NewDRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+  CRC.removeOutgoingEdge(C1, D2);
+  EXPECT_FALSE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+
+  // Now that we've updated the call graph, D2 is dead, so remove it.
+  CG.removeDeadFunction(D2F);
+
+  // Check that the graph still looks the same.
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+
+  // Verify that the post-order walk reflects the updated but still incomplete
+  // structure.
+  auto J = CG.postorder_ref_scc_begin();
+  EXPECT_NE(J, E);
+  EXPECT_EQ(&NewDRC, &*J) << "Actual RefSCC: " << *J;
+  ++J;
+  EXPECT_NE(J, E);
+  EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J;
+  EXPECT_EQ(I, J);
+
+  // Check that we can form the last two RefSCCs now, and even that we can do
+  // it with alternating iterators.
+  ++J;
+  EXPECT_NE(J, E);
+  LazyCallGraph::RefSCC &BRC = *J;
+  EXPECT_NE(&BRC, nullptr);
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))));
+  EXPECT_TRUE(BRC.isParentOf(NewDRC));
+  ++I;
+  EXPECT_EQ(J, I);
+  EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
+
+  // Increment I this time to form the new RefSCC, flopping back to the first
+  // iterator.
+  ++I;
+  EXPECT_NE(I, E);
+  LazyCallGraph::RefSCC &ARC = *I;
+  EXPECT_NE(&ARC, nullptr);
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))));
+  EXPECT_TRUE(ARC.isParentOf(BRC));
+  EXPECT_TRUE(ARC.isParentOf(CRC));
+  ++J;
+  EXPECT_EQ(I, J);
+  EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J;
+  ++I;
+  EXPECT_EQ(E, I);
+  ++J;
+  EXPECT_EQ(E, J);
+}
+
 TEST(LazyCallGraphTest, InternalEdgeMutation) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"