[LCG] Special case when removing a ref edge from a RefSCC leaves

that RefSCC still connected.

This is common and can be handled much more efficiently. As soon as we
know we've covered every node in the RefSCC with the DFS, we can simply
reset our state and return. This avoids numerous data structure updates
and other complexity.

On top of other changes, this appears to get new PM back to parity with
the old PM for a large protocol buffer message source code. The dense
map updates are very hot in this function.

llvm-svn: 310451

1 files changed, 29 insertions, 12 deletions

diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp
index 17e96e75840..a1555b4c4f3 100644
--- a/llvm/lib/Analysis/LazyCallGraph.cpp
+++ b/llvm/lib/Analysis/LazyCallGraph.cpp
@@ -1157,6 +1157,11 @@ LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN,
     Worklist.append(C->Nodes.begin(), C->Nodes.end());
   }
 
+  // Track the number of nodes in this RefSCC so that we can quickly recognize
+  // an important special case of the edge removal not breaking the cycle of
+  // this RefSCC.
+  const int NumRefSCCNodes = Worklist.size();
+
   auto MarkNodeForSCCNumber = [&PostOrderMapping](Node &N, int Number) {
     N.DFSNumber = N.LowLink = -1;
     PostOrderMapping[&N] = Number;
@@ -1238,31 +1243,43 @@ LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN,
       int RootDFSNumber = N->DFSNumber;
       // Find the range of the node stack by walking down until we pass the
       // root DFS number.
-      auto RefSCCNodes = make_range(
-          PendingRefSCCStack.rbegin(),
-          find_if(reverse(PendingRefSCCStack), [RootDFSNumber](const Node *N) {
-            return N->DFSNumber < RootDFSNumber;
-          }));
+      auto RefSCCNodes =
+          make_range(find_if(reverse(PendingRefSCCStack),
+                             [RootDFSNumber](const Node *N) {
+                               return N->DFSNumber < RootDFSNumber;
+                             })
+                         .base(),
+                     PendingRefSCCStack.end());
+
+      // If we find a cycle containing all nodes originally in this RefSCC then
+      // the removal hasn't changed the structure at all. This is an important
+      // special case and we can directly exit the entire routine more
+      // efficiently as soon as we discover it.
+      if (std::distance(RefSCCNodes.begin(), RefSCCNodes.end()) ==
+          NumRefSCCNodes) {
+        // Mark the DFS as over in the nodes.
+        for (Node *N : RefSCCNodes)
+          N->DFSNumber = N->LowLink = -1;
+        // Return the empty result immediately.
+        return Result;
+      }
 
       // Mark the postorder number for these nodes and clear them off the
       // stack. We'll use the postorder number to pull them into RefSCCs at the
-      // end. FIXME: Fuse with the loop above.
+      // end.
       int RefSCCNumber = PostOrderNumber++;
       for (Node *N : RefSCCNodes)
         MarkNodeForSCCNumber(*N, RefSCCNumber);
 
-      PendingRefSCCStack.erase(RefSCCNodes.end().base(),
-                               PendingRefSCCStack.end());
+      PendingRefSCCStack.erase(RefSCCNodes.begin(), PendingRefSCCStack.end());
     } while (!DFSStack.empty());
 
     assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
     assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
   } while (!Worklist.empty());
 
-  // If we only ever needed one post-order number, we reformed a ref-cycle for
-  // every node so the RefSCC remains unchanged.
-  if (PostOrderNumber == 1)
-    return Result;
+  assert(PostOrderNumber > 1 &&
+         "Should never finish the DFS when the existing RefSCC remains valid!");
 
   // Otherwise we create a collection of new RefSCC nodes and build
   // a radix-sort style map from postorder number to these new RefSCCs. We then