[LCG] Switch one of the update methods for the LazyCallGraph to support

limited batch updates.

Specifically, allow removing multiple reference edges starting from
a common source node. There are a few constraints that play into
supporting this form of batching:

1) The way updates occur during the CGSCC walk, about the most we can
   functionally batch together are those with a common source node. This
   also makes the batching simpler to implement, so it seems
   a worthwhile restriction.
2) The far and away hottest function for large C++ files I measured
   (generated code for protocol buffers) showed a huge amount of time
   was spent removing ref edges specifically, so it seems worth focusing
   there.
3) The algorithm for removing ref edges is very amenable to this
   restricted batching. There are just both API and implementation
   special casing for the non-batch case that gets in the way. Once
   removed, supporting batches is nearly trivial.

This does modify the API in an interesting way -- now, we only preserve
the target RefSCC when the RefSCC structure is unchanged. In the face of
any splits, we create brand new RefSCC objects. However, all of the
users were OK with it that I could find. Only the unittest needed
interesting updates here.

How much does batching these updates help? I instrumented the compiler
when run over a very large generated source file for a protocol buffer
and found that the majority of updates are intrinsically updating one
function at a time. However, nearly 40% of the total ref edges removed
are removed as part of a batch of removals greater than one, so these
are the cases batching can help with.

When compiling the IR for this file with 'opt' and 'O3', this patch
reduces the total time by 8-9%.

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

llvm-svn: 310450

1 files changed, 94 insertions, 23 deletions

diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
index 9e7e128bcfb..cb8eb375605 100644
--- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp
@@ -1166,20 +1166,21 @@ TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
   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();
+  auto NewRCs = DRC.removeInternalRefEdge(D1, {&D2});
+  ASSERT_EQ(2u, NewRCs.size());
+  LazyCallGraph::RefSCC &NewDRC = *NewRCs[0];
   EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
   EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
-  EXPECT_FALSE(NewDRC.isParentOf(DRC));
-  EXPECT_TRUE(CRC.isParentOf(DRC));
+  LazyCallGraph::RefSCC &D2RC = *NewRCs[1];
+  EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2));
+  EXPECT_FALSE(NewDRC.isParentOf(D2RC));
+  EXPECT_TRUE(CRC.isParentOf(D2RC));
   EXPECT_TRUE(CRC.isParentOf(NewDRC));
-  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+  EXPECT_TRUE(D2RC.isParentOf(NewDRC));
   CRC.removeOutgoingEdge(C1, D2);
-  EXPECT_FALSE(CRC.isParentOf(DRC));
+  EXPECT_FALSE(CRC.isParentOf(D2RC));
   EXPECT_TRUE(CRC.isParentOf(NewDRC));
-  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+  EXPECT_TRUE(D2RC.isParentOf(NewDRC));
 
   // Now that we've updated the call graph, D2 is dead, so remove it.
   CG.removeDeadFunction(D2F);
@@ -1340,7 +1341,7 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) {
   // Remove the edge from b -> a, which should leave the 3 functions still in
   // a single connected component because of a -> b -> c -> a.
   SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
-      RC.removeInternalRefEdge(B, A);
+      RC.removeInternalRefEdge(B, {&A});
   EXPECT_EQ(0u, NewRCs.size());
   EXPECT_EQ(&RC, CG.lookupRefSCC(A));
   EXPECT_EQ(&RC, CG.lookupRefSCC(B));
@@ -1350,24 +1351,94 @@ TEST(LazyCallGraphTest, InternalEdgeRemoval) {
   EXPECT_EQ(&RC, &*J);
   EXPECT_EQ(E, std::next(J));
 
+  // Increment I before we actually mutate the structure so that it remains
+  // a valid iterator.
+  ++I;
+
   // Remove the edge from c -> a, which should leave 'a' in the original RefSCC
   // and form a new RefSCC for 'b' and 'c'.
-  NewRCs = RC.removeInternalRefEdge(C, A);
-  EXPECT_EQ(1u, NewRCs.size());
-  EXPECT_EQ(&RC, CG.lookupRefSCC(A));
-  EXPECT_EQ(1, std::distance(RC.begin(), RC.end()));
-  LazyCallGraph::RefSCC &RC2 = *CG.lookupRefSCC(B);
-  EXPECT_EQ(&RC2, CG.lookupRefSCC(C));
-  EXPECT_EQ(&RC2, NewRCs[0]);
+  NewRCs = RC.removeInternalRefEdge(C, {&A});
+  ASSERT_EQ(2u, NewRCs.size());
+  LazyCallGraph::RefSCC &BCRC = *NewRCs[0];
+  LazyCallGraph::RefSCC &ARC = *NewRCs[1];
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
+  EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end()));
+  EXPECT_EQ(&BCRC, CG.lookupRefSCC(B));
+  EXPECT_EQ(&BCRC, CG.lookupRefSCC(C));
   J = CG.postorder_ref_scc_begin();
   EXPECT_NE(I, J);
-  EXPECT_EQ(&RC2, &*J);
+  EXPECT_EQ(&BCRC, &*J);
+  ++J;
+  EXPECT_NE(I, J);
+  EXPECT_EQ(&ARC, &*J);
   ++J;
   EXPECT_EQ(I, J);
-  EXPECT_EQ(&RC, &*J);
+  EXPECT_EQ(E, J);
+}
+
+TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) {
+  LLVMContext Context;
+  // A nice fully connected (including self-edges) RefSCC.
+  std::unique_ptr<Module> M = parseAssembly(
+      Context, "define void @a(i8** %ptr) {\n"
+               "entry:\n"
+               "  store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
+               "  store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
+               "  store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
+               "  ret void\n"
+               "}\n"
+               "define void @b(i8** %ptr) {\n"
+               "entry:\n"
+               "  store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
+               "  store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
+               "  store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
+               "  ret void\n"
+               "}\n"
+               "define void @c(i8** %ptr) {\n"
+               "entry:\n"
+               "  store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
+               "  store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
+               "  store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
+               "  ret void\n"
+               "}\n");
+  LazyCallGraph CG = buildCG(*M);
+
+  // Force the graph to be fully expanded.
+  CG.buildRefSCCs();
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  LazyCallGraph::RefSCC &RC = *I;
+  EXPECT_EQ(E, std::next(I));
+
+  LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(A));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(B));
+  EXPECT_EQ(&RC, CG.lookupRefSCC(C));
+
+  // Increment I before we actually mutate the structure so that it remains
+  // a valid iterator.
   ++I;
-  EXPECT_EQ(E, I);
+
+  // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC.
+  SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
+      RC.removeInternalRefEdge(B, {&A, &C});
+
+  ASSERT_EQ(2u, NewRCs.size());
+  LazyCallGraph::RefSCC &BRC = *NewRCs[0];
+  LazyCallGraph::RefSCC &ACRC = *NewRCs[1];
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
+  EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end()));
+  EXPECT_EQ(&ACRC, CG.lookupRefSCC(A));
+  EXPECT_EQ(&ACRC, CG.lookupRefSCC(C));
+  auto J = CG.postorder_ref_scc_begin();
+  EXPECT_NE(I, J);
+  EXPECT_EQ(&BRC, &*J);
   ++J;
+  EXPECT_NE(I, J);
+  EXPECT_EQ(&ACRC, &*J);
+  ++J;
+  EXPECT_EQ(I, J);
   EXPECT_EQ(E, J);
 }
 
@@ -1420,7 +1491,7 @@ TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {
 
   // Remove the edge from a -> c which doesn't change anything.
   SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
-      RC.removeInternalRefEdge(AN, CN);
+      RC.removeInternalRefEdge(AN, {&CN});
   EXPECT_EQ(0u, NewRCs.size());
   EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
   EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
@@ -1435,8 +1506,8 @@ TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {
 
   // Remove the edge from b -> a and c -> b; again this doesn't change
   // anything.
-  NewRCs = RC.removeInternalRefEdge(BN, AN);
-  NewRCs = RC.removeInternalRefEdge(CN, BN);
+  NewRCs = RC.removeInternalRefEdge(BN, {&AN});
+  NewRCs = RC.removeInternalRefEdge(CN, {&BN});
   EXPECT_EQ(0u, NewRCs.size());
   EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
   EXPECT_EQ(&RC, CG.lookupRefSCC(BN));