[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, 62 insertions, 55 deletions

diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp
index b81069559c7..ce8af755147 100644
--- a/llvm/lib/Analysis/CGSCCPassManager.cpp
+++ b/llvm/lib/Analysis/CGSCCPassManager.cpp
@@ -459,71 +459,78 @@ LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
       VisitRef(*F);
 
   // First remove all of the edges that are no longer present in this function.
-  // We have to build a list of dead targets first and then remove them as the
-  // data structures will all be invalidated by removing them.
-  SmallVector<PointerIntPair<Node *, 1, Edge::Kind>, 4> DeadTargets;
-  for (Edge &E : *N)
-    if (!RetainedEdges.count(&E.getNode()))
-      DeadTargets.push_back({&E.getNode(), E.getKind()});
-  for (auto DeadTarget : DeadTargets) {
-    Node &TargetN = *DeadTarget.getPointer();
-    bool IsCall = DeadTarget.getInt() == Edge::Call;
-    SCC &TargetC = *G.lookupSCC(TargetN);
-    RefSCC &TargetRC = TargetC.getOuterRefSCC();
-
-    if (&TargetRC != RC) {
-      RC->removeOutgoingEdge(N, TargetN);
-      if (DebugLogging)
-        dbgs() << "Deleting outgoing edge from '" << N << "' to '" << TargetN
-               << "'\n";
+  // The first step makes these edges uniformly ref edges and accumulates them
+  // into a separate data structure so removal doesn't invalidate anything.
+  SmallVector<Node *, 4> DeadTargets;
+  for (Edge &E : *N) {
+    if (RetainedEdges.count(&E.getNode()))
       continue;
-    }
-    if (DebugLogging)
-      dbgs() << "Deleting internal " << (IsCall ? "call" : "ref")
-             << " edge from '" << N << "' to '" << TargetN << "'\n";
 
-    if (IsCall) {
+    SCC &TargetC = *G.lookupSCC(E.getNode());
+    RefSCC &TargetRC = TargetC.getOuterRefSCC();
+    if (&TargetRC == RC && E.isCall()) {
       if (C != &TargetC) {
         // For separate SCCs this is trivial.
-        RC->switchTrivialInternalEdgeToRef(N, TargetN);
+        RC->switchTrivialInternalEdgeToRef(N, E.getNode());
       } else {
         // Now update the call graph.
-        C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G,
-                                   N, C, AM, UR, DebugLogging);
+        C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, E.getNode()),
+                                   G, N, C, AM, UR, DebugLogging);
       }
     }
 
-    auto NewRefSCCs = RC->removeInternalRefEdge(N, TargetN);
-    if (!NewRefSCCs.empty()) {
-      // Note that we don't bother to invalidate analyses as ref-edge
-      // connectivity is not really observable in any way and is intended
-      // exclusively to be used for ordering of transforms rather than for
-      // analysis conclusions.
-
-      // The RC worklist is in reverse postorder, so we first enqueue the
-      // current RefSCC as it will remain the parent of all split RefSCCs, then
-      // we enqueue the new ones in RPO except for the one which contains the
-      // source node as that is the "bottom" we will continue processing in the
-      // bottom-up walk.
-      UR.RCWorklist.insert(RC);
+    // Now that this is ready for actual removal, put it into our list.
+    DeadTargets.push_back(&E.getNode());
+  }
+  // Remove the easy cases quickly and actually pull them out of our list.
+  DeadTargets.erase(
+      llvm::remove_if(DeadTargets,
+                      [&](Node *TargetN) {
+                        SCC &TargetC = *G.lookupSCC(*TargetN);
+                        RefSCC &TargetRC = TargetC.getOuterRefSCC();
+
+                        // We can't trivially remove internal targets, so skip
+                        // those.
+                        if (&TargetRC == RC)
+                          return false;
+
+                        RC->removeOutgoingEdge(N, *TargetN);
+                        if (DebugLogging)
+                          dbgs() << "Deleting outgoing edge from '" << N
+                                 << "' to '" << TargetN << "'\n";
+                        return true;
+                      }),
+      DeadTargets.end());
+
+  // Now do a batch removal of the internal ref edges left.
+  auto NewRefSCCs = RC->removeInternalRefEdge(N, DeadTargets);
+  if (!NewRefSCCs.empty()) {
+    // The old RefSCC is dead, mark it as such.
+    UR.InvalidatedRefSCCs.insert(RC);
+
+    // Note that we don't bother to invalidate analyses as ref-edge
+    // connectivity is not really observable in any way and is intended
+    // exclusively to be used for ordering of transforms rather than for
+    // analysis conclusions.
+
+    // Update RC to the "bottom".
+    assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!");
+    RC = &C->getOuterRefSCC();
+    assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
+
+    // The RC worklist is in reverse postorder, so we enqueue the new ones in
+    // RPO except for the one which contains the source node as that is the
+    // "bottom" we will continue processing in the bottom-up walk.
+    assert(NewRefSCCs.front() == RC &&
+           "New current RefSCC not first in the returned list!");
+    for (RefSCC *NewRC :
+         reverse(make_range(std::next(NewRefSCCs.begin()), NewRefSCCs.end()))) {
+      assert(NewRC != RC && "Should not encounter the current RefSCC further "
+                            "in the postorder list of new RefSCCs.");
+      UR.RCWorklist.insert(NewRC);
       if (DebugLogging)
-        dbgs() << "Enqueuing the existing RefSCC in the update worklist: "
-               << *RC << "\n";
-      // Update the RC to the "bottom".
-      assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!");
-      RC = &C->getOuterRefSCC();
-      assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
-      assert(NewRefSCCs.front() == RC &&
-             "New current RefSCC not first in the returned list!");
-      for (RefSCC *NewRC : reverse(
-               make_range(std::next(NewRefSCCs.begin()), NewRefSCCs.end()))) {
-        assert(NewRC != RC && "Should not encounter the current RefSCC further "
-                              "in the postorder list of new RefSCCs.");
-        UR.RCWorklist.insert(NewRC);
-        if (DebugLogging)
-          dbgs() << "Enqueuing a new RefSCC in the update worklist: " << *NewRC
-                 << "\n";
-      }
+        dbgs() << "Enqueuing a new RefSCC in the update worklist: " << *NewRC
+               << "\n";
     }
   }