[LazyCallGraph] Ignore empty RefSCCs rather than shift RefSCCs when removing dead functions

[aeubanks]

Summary

This is in preparation for D115545 which attempts to delete discardable functions if they are unused. With that change, shifting RefSCCs becomes noticeable in compile time. This change makes the LCG update negligible again.

[nikic]

LGTM

llvm/include/llvm/Analysis/LazyCallGraph.h

class postorder_ref_scc_iterator
 
     /// Nonce type to select the constructor for the end iterator.
     struct IsAtEndT {};
 
     LazyCallGraph *G;
     RefSCC *RC = nullptr;
 
     /// Build the begin iterator for a node.
-    postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {}
+    postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G), RC(getRC(G, 0)) {
+      incrementUntilNonEmptyRefSCC();
+    }
 
     /// Build the end iterator for a node. This is selected purely by overload.
     postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) : G(&G) {}
 
     /// Get the post-order RefSCC at the given index of the postorder walk,
     /// populating it if necessary.
     static RefSCC *getRC(LazyCallGraph &G, int Index) {
       if (Index == (int)G.PostOrderRefSCCs.size())
         // We're at the end.
         return nullptr;
 
       return G.PostOrderRefSCCs[Index];
     }
 
+    // Keep incrementing until RC is non-empty (or null).
+    void incrementUntilNonEmptyRefSCC() {
+      while (RC && RC->size() == 0)
+        increment();
+    }
+
+    void increment() {
+      assert(RC && "Cannot increment the end iterator!");
+      RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
+    }
+
   public:
     bool operator==(const postorder_ref_scc_iterator &Arg) const {
       return G == Arg.G && RC == Arg.RC;
     }
 
     reference operator*() const { return *RC; }
 
     using iterator_facade_base::operator++;
     postorder_ref_scc_iterator &operator++() {
-      assert(RC && "Cannot increment the end iterator!");
-      RC = getRC(*G, G->RefSCCIndices.find(RC)->second + 1);
+      increment();
+      incrementUntilNonEmptyRefSCC();
       return *this;
     }
   };
 
   /// Construct a graph for the given module.
   ///
   /// This sets up the graph and computes all of the entry points of the graph.
   /// No function definitions are scanned until their nodes in the graph are

llvm/lib/Analysis/LazyCallGraph.cpp

void LazyCallGraph::removeDeadFunction(Function &F) {
   RefSCC &RC = C.getOuterRefSCC();
 
   // This node must be the only member of its SCC as it has no callers, and
   // that SCC must be the only member of a RefSCC as it has no references.
   // Validate these properties first.
   assert(C.size() == 1 && "Dead functions must be in a singular SCC");
   assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC");
 
-  auto RCIndexI = RefSCCIndices.find(&RC);
-  int RCIndex = RCIndexI->second;
-  PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex);
-  RefSCCIndices.erase(RCIndexI);
-  for (int i = RCIndex, Size = PostOrderRefSCCs.size(); i < Size; ++i)
-    RefSCCIndices[PostOrderRefSCCs[i]] = i;
-
   // Finally clear out all the data structures from the node down through the
-  // components.
+  // components. postorder_ref_scc_iterator will skip empty RefSCCs, so no need
+  // to adjust LazyCallGraph data structures.
   N.clear();
   N.G = nullptr;
   N.F = nullptr;
   C.clear();
   RC.clear();
   RC.G = nullptr;
 
   // Nothing to delete as all the objects are allocated in stable bump pointer