[NewPM] Don't skip SCCs not in current RefSCC

[aeubanks]

Summary

With D107249 I saw huge compile time regressions on a module (150s ->
5700s). This turned out to be due to a huge RefSCC in
the module. As we ran the function simplification pipeline on functions
in the SCCs in the RefSCC, some of those SCCs would be split out to
their RefSCC, a child of the current RefSCC. We'd skip the remaining
SCCs in the huge RefSCC because the current RefSCC is now the RefSCC
just split out, then revisit the original huge RefSCC from the
beginning. This happened many times because many functions in the
RefSCC were optimizable to the point of becoming their own RefSCC.

This patch makes it so we don't skip SCCs not in the current RefSCC so
that we split out all the child RefSCCs on the first iteration of
RefSCC. When we split out a RefSCC, we invalidate the original RefSCC
and add the remainder of the SCCs into a new RefSCC in
RCWorklist. This happens repeatedly until we finish visiting all
SCCs, at which point there is only one valid RefSCC in
RCWorklist from the original RefSCC containing all the SCCs that
were not split out, and we visit that.

For example, in the newly added test cgscc-refscc-mutation-order.ll,
we'd previously run instcombine in this order:
f1, f2, f1, f3, f1, f4, f1

Now it's:
f1, f2, f3, f4, f1

This can cause more passes to be run in some specific cases,
e.g. if f1<->f2 gets optimized to f1<-f2, we'd previously run f1, f2;
now we run f1, f2, f2.

This improves kimwitu++ compile times by a lot (12-15% for various -O3 configs):
https://llvm-compile-time-tracker.com/compare.php?from=2371c5a0e06d22b48da0427cebaf53a5e5c54635&to=00908f1d67400cab1ad7bcd7cacc7558d1672e97&stat=instructions

[aeubanks]

update

[asbirlea]

As discussed offline, the potential issue with this change is whether we encounter a pathological case in the "opposite direction".

Seeing how so far we have a concrete case where the current traversal order leads to the compile time explosion, and the benchmark in the compiler tracker also benefits from the change, I'm in favor of moving forward with the change and revisit if we encounter a benchmark exhibiting the high compile times after this patch.

llvm/include/llvm/Analysis/CGSCCPassManager.h

struct CGSCCUpdateResult {
   /// The set of invalidated SCCs which should be skipped if they are found
   /// in \c CWorklist.
   ///
   /// This is used to quickly prune out SCCs when they get deleted and happen
   /// to already be on the worklist. We use this primarily to avoid scanning
   /// the list and removing entries from it.
   SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
 
-  /// If non-null, the updated current \c RefSCC being processed.
-  ///
-  /// This is set when a graph refinement takes place and the "current" point
-  /// in the graph moves "down" or earlier in the post-order walk. This will
-  /// often cause the "current" RefSCC to be a newly created RefSCC object and
-  /// the old one to be added to the above worklist. When that happens, this
-  /// pointer is non-null and can be used to continue processing the "top" of
-  /// the post-order walk.
-  LazyCallGraph::RefSCC *UpdatedRC;
-
   /// If non-null, the updated current \c SCC being processed.
   ///
   /// This is set when a graph refinement takes place and the "current" point
   /// in the graph moves "down" or earlier in the post-order walk. This will
   /// often cause the "current" SCC to be a newly created SCC object and the
   /// old one to be added to the above worklist. When that happens, this
   /// pointer is non-null and can be used to continue processing the "top" of
   /// the post-order walk.

llvm/lib/Analysis/CGSCCPassManager.cpp

ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, ModuleAnalysisManager &AM) {
   // iterating off the worklists.
   SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
   SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
 
   SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
       InlinedInternalEdges;
 
   CGSCCUpdateResult UR = {
-      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
-      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges,
-      {}};
+      RCWorklist,           CWorklist, InvalidRefSCCSet,
+      InvalidSCCSet,        nullptr,   PreservedAnalyses::all(),
+      InlinedInternalEdges, {}};
 
   // Request PassInstrumentation from analysis manager, will use it to run
   // instrumenting callbacks for the passes later.
   PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
 
   PreservedAnalyses PA = PreservedAnalyses::all();
   CG.buildRefSCCs();
   for (auto RCI = CG.postorder_ref_scc_begin(),
do {
         if (InvalidSCCSet.count(C)) {
           LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
           continue;
         }
         if (LastUpdatedC == C) {
           LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
           continue;
         }
-        if (&C->getOuterRefSCC() != RC) {
-          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
-                               "RefSCC...\n");
-          continue;
-        }
+        // We used to also check if the current SCC is part of the current
+        // RefSCC and bail if it wasn't, since it should be in RCWorklist.
+        // However, this can cause compile time explosions in some cases on
+        // modules with a huge RefSCC. If a non-trivial amount of SCCs in the
+        // huge RefSCC can become their own child RefSCC, we create one child
+        // RefSCC, bail on the current RefSCC, visit the child RefSCC, revisit
+        // the huge RefSCC, and repeat. By visiting all SCCs in the original
+        // RefSCC we create all the child RefSCCs in one pass of the RefSCC,
+        // rather one pass of the RefSCC creating one child RefSCC at a time.
 
         // Ensure we can proxy analysis updates from the CGSCC analysis manager
         // into the the Function analysis manager by getting a proxy here.
         // This also needs to update the FunctionAnalysisManager, as this may be
         // the first time we see this SCC.
         CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
             FAM);
 
do {
         // are mutated. However, that seems to lose the robustness of the
         // pass-manager driven invalidation scheme.
         CGAM.invalidate(*C, UR.CrossSCCPA);
 
         do {
           // Check that we didn't miss any update scenario.
           assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
           assert(C->begin() != C->end() && "Cannot have an empty SCC!");
-          assert(&C->getOuterRefSCC() == RC &&
-                 "Processing an SCC in a different RefSCC!");
 
           LastUpdatedC = UR.UpdatedC;
-          UR.UpdatedRC = nullptr;
           UR.UpdatedC = nullptr;
 
           // Check the PassInstrumentation's BeforePass callbacks before
           // running the pass, skip its execution completely if asked to
           // (callback returns false).
           if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
             continue;
 
           PreservedAnalyses PassPA;
           {
             TimeTraceScope TimeScope(Pass->name());
             PassPA = Pass->run(*C, CGAM, CG, UR);
           }
 
           if (UR.InvalidatedSCCs.count(C))
             PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
           else
             PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
 
           // Update the SCC and RefSCC if necessary.
           C = UR.UpdatedC ? UR.UpdatedC : C;
-          RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
 
           if (UR.UpdatedC) {
             // If we're updating the SCC, also update the FAM inside the proxy's
             // result.
             CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
                 FAM);
           }
 
if (InitialSCCIndex < NewSCCIndex) {
       }
     }
   }
 
   assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
   assert(!UR.InvalidatedRefSCCs.count(RC) && "Invalidated the current RefSCC!");
   assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
 
-  // Record the current RefSCC and SCC for higher layers of the CGSCC pass
-  // manager now that all the updates have been applied.
-  if (RC != &InitialRC)
-    UR.UpdatedRC = RC;
+  // Record the current SCC for higher layers of the CGSCC pass manager now that
+  // all the updates have been applied.
   if (C != &InitialC)
     UR.UpdatedC = C;
 
   return *C;
 }
 
 LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
     LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,

llvm/test/Other/cgscc-refscc-mutation-order.ll

+; RUN: opt -passes='cgscc(function(instcombine))' -debug-pass-manager -disable-output < %s 2>&1 | FileCheck %s
+
+; We want to run passes on every SCC in a RefSCC without bailing even if one of the SCCs becomes a child SCC.
+
+; This prevents explosive behavior on huge RefSCCs where a non-trivial amount of
+; SCCs in the RefSCC become their own RefSCC as passes run on them. Otherwise we
+; end up visiting the huge RefSCC the number of times that an SCC is split out
+; rather than just twice.
+
+; CHECK: Running pass: InstCombinePass on f1
+; CHECK-NOT: InstCombinePass
+; CHECK: Running pass: InstCombinePass on f2
+; CHECK-NOT: InstCombinePass
+; CHECK: Running pass: InstCombinePass on f3
+; CHECK-NOT: InstCombinePass
+; CHECK: Running pass: InstCombinePass on f4
+; CHECK-NOT: InstCombinePass
+; CHECK: Running pass: InstCombinePass on f1
+; CHECK-NOT: InstCombinePass
+
+@a1 = alias void (), void ()* @f1
+@a2 = alias void (), void ()* @f2
+@a3 = alias void (), void ()* @f3
+@a4 = alias void (), void ()* @f4
+
+define void @f1() {
+  call void @a2()
+  call void @a3()
+  call void @a4()
+  ret void
+}
+
+define void @f2() {
+  call void @a1() readnone nounwind willreturn
+  ret void
+}
+
+define void @f3() {
+  call void @a1() readnone nounwind willreturn
+  ret void
+}
+
+define void @f4() {
+  call void @a1() readnone nounwind willreturn
+  ret void
+}

llvm/test/Transforms/Inline/cgscc-cycle-debug.ll

 ; CHECK: Running an SCC pass across the RefSCC: [(test1_a, test1_b, test1_c)]
 ; CHECK: Enqueuing the existing SCC in the worklist:(test1_b)
 ; CHECK: Enqueuing a newly formed SCC:(test1_c)
 ; CHECK: Enqueuing a new RefSCC in the update worklist: [(test1_b)]
 ; CHECK: Switch an internal ref edge to a call edge from 'test1_a' to 'test1_c'
 ; CHECK: Switch an internal ref edge to a call edge from 'test1_a' to 'test1_a'
 ; CHECK: Re-running SCC passes after a refinement of the current SCC: (test1_c, test1_a)
 ; CHECK: Skipping redundant run on SCC: (test1_c, test1_a)
-; CHECK: Skipping an SCC that is now part of some other RefSCC...
 
 declare void @external(i32 %seed)
 
 define void @test1_a(i32 %num) {
 entry:
   call void @test1_b(i32 %num)
   call void @external(i32 %num)
   ret void