diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h --- a/llvm/include/llvm/Analysis/CGSCCPassManager.h +++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h @@ -272,16 +272,6 @@ /// the list and removing entries from it. SmallPtrSetImpl &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 diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp --- a/llvm/lib/Analysis/CGSCCPassManager.cpp +++ b/llvm/lib/Analysis/CGSCCPassManager.cpp @@ -164,9 +164,9 @@ 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. @@ -230,11 +230,15 @@ 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. @@ -264,11 +268,8 @@ // 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 @@ -290,7 +291,6 @@ // 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 @@ -1213,10 +1213,8 @@ 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; diff --git a/llvm/test/Other/cgscc-refscc-mutation-order.ll b/llvm/test/Other/cgscc-refscc-mutation-order.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Other/cgscc-refscc-mutation-order.ll @@ -0,0 +1,46 @@ +; 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 +} diff --git a/llvm/test/Transforms/Inline/cgscc-cycle-debug.ll b/llvm/test/Transforms/Inline/cgscc-cycle-debug.ll --- a/llvm/test/Transforms/Inline/cgscc-cycle-debug.ll +++ b/llvm/test/Transforms/Inline/cgscc-cycle-debug.ll @@ -18,7 +18,6 @@ ; 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)