[NPM] Do not run function simplification pipeline unnecessarily

[mtrofin]

Summary

The CGSCC pass manager interplay with the FunctionAnalysisManagerCGSCCProxy is 'special' in the sense that the former will rerun the latter if there are changes to a SCC structure; that being said, some of the functions in the SCC may be unchanged. In that case, the function simplification pipeline will be re-run, which impacts compile time[1].

This patch allows the function simplification pipeline be skipped if it was already run and the function was not modified since.

The behavior is currently disabled by default. This is because, currently, the rerunning of the function simplification pipeline on an unchanged function may still result in changes. The patch simplifies investigating and fixing those cases where repeated function pass runs do actually positively impact code quality, while offering an easy workaround for those impacted negatively by compile time regressions, and not impacting mainline scenarios.

[1] A compile time tracker run with the option enabled.

[mtrofin]

added a test

[mtrofin]

updated patch

[asbirlea]

Restating summary of offline discussion:
Up until now, the repetition of simplification passes has hidden phase ordering issues or the need to rerun certain passes. Turning this flag on will improve compile time and resolve potential exponential compile-time increases, but will also reveal all the cases where the pass pipeline needs to be adjusted to not miss optimizations that were previously done on the follow-up optimization runs.

Thank you for pushing this!

[mtrofin]

gentle reminder - thanks!

[aeubanks]

nit with the summary, I think of "[NFC]" as more of refactoring types of changes, this adds new functionality under a flag

llvm/lib/Analysis/CGSCCPassManager.cpp

552

adding a comment here would be good

906

can this be !FunctionPass?

llvm/lib/Passes/PassBuilder.cpp

18

unused?

llvm/test/Other/new-pass-manager-cgscc-fct-proxy.ll

39

also check if we rerun SROA on f3?

40

typo

[mtrofin]

feedback

llvm/lib/Analysis/CGSCCPassManager.cpp

906

then we wouldn't invalidate when updateCGAndAnalysisManagerForFunctionPass is called. CoroSplit calls it, for instance.

[mtrofin]

test

[mtrofin]

addressed remaining 2 items

[fhahn]

Do you have any data on whether there are any binary differences for a set of programs/benchmarks with this enabled compared to disabled?

[mtrofin]

In D98103#2684255, @fhahn wrote:

Do you have any data on whether there are any binary differences for a set of programs/benchmarks with this enabled compared to disabled?

There are, in the strict sense of binary diff. I did not try it on benchmarks.

[fhahn]

In D98103#2684272, @mtrofin wrote:

In D98103#2684255, @fhahn wrote:

Do you have any data on whether there are any binary differences for a set of programs/benchmarks with this enabled compared to disabled?

There are, in the strict sense of binary diff. I did not try it on benchmarks.

Interesting. But then doesn't this indicate that the passes were not run unnecessarily? Just curious why this happens, e.g. are some changes not reported properly?

[mtrofin]

In D98103#2684278, @fhahn wrote:

In D98103#2684272, @mtrofin wrote:

In D98103#2684255, @fhahn wrote:

Do you have any data on whether there are any binary differences for a set of programs/benchmarks with this enabled compared to disabled?

There are, in the strict sense of binary diff. I did not try it on benchmarks.

Interesting. But then doesn't this indicate that the passes were not run unnecessarily? Just curious why this happens, e.g. are some changes not reported properly?

I believe it's what @asbirlea pointed at: there are some optimization passes that, if re-run on an unchanged function, do find more work/changes; and/or optimization passes that should be re-run after others in the pipeline (maybe these are the same thing)

Maybe my choice of words - i.e. "unnecessarily" is not strictly correct; not sure what would concisely capture it though - maybe "unintentionally"?; in any case, the idea is that we arguably want to get to a place where 1) if the function isn't changed, and the function simplification passes were rerun, they are still unchanged, and 2) this flag is enabled by default.

[asbirlea]

I agree with @aeubanks on removing the NFC from the title. This is changing the functionality, even if it's under a disabled flag.

For additional context, with the flag enabled we're seeing performance regressions which indicate optimizations are being missed and picked up by the subsequent runs of the optimization pass.
The purpose of this initial patch is to stage the transition by first introducing the flag, then focus on understanding where the missed optimizations occur so we can fix (for lack of a better word) the NPM pass pipeline.
When the flag is eventually flipped, it's possible the compile-time benefits also disappear due to the introduction of additional optimization passes, but the current pathological cases of high compile times due to repeating (truly unnecessary) optimizations, should remain resolved.

[aeubanks]

some comments on the summary

• we should clarify that this is under a flag and is not currently changing any defaults. [2] says that, but we should make sure it's very clear somewhere besides a footer
• the simplification pipeline is known to not be idempotent (and it would be very hard to make it so without majorly regressing compile times), so should not have a code quality effect is not true at all. but we should note that in a perfect world this wouldn't change code quality if the function simplification were perfect
• the function passes will be re-run -> the function simplification pipeline will be re-run is a bit clearer, same with This patch allows the function passes be skipped if they were run once and a function was not modified since.

llvm/lib/Analysis/CGSCCPassManager.cpp

557–558

I don't think this is necessarily true. ArgumentPromotion is a CGSCC pass that changes functions but doesn't change the call graph so it doesn't need to call updateCGAndAnalysisManagerForCGSCCPass(). It handles invalidating analyses itself.
Same with PostOrderFunctionAttrsPass, but it just invalidates everything if anything has changed.

588

nit: /*FunctionPass*/ true, /*InvalidateSA*/ false

906

I feel like I'm missing something obvious, why is this invalidate here necessary? Can we just see what the passes invalidate?

llvm/test/Other/new-pass-manager-cgscc-fct-proxy.ll

39

sorry, I also meant to check that we don't rerun it in NOREPS

40

still typo CHCEK-NEXT

[mtrofin]

In D98103#2684402, @asbirlea wrote:

I agree with @aeubanks on removing the NFC from the title. This is changing the functionality, even if it's under a disabled flag.

For additional context, with the flag enabled we're seeing performance regressions which indicate optimizations are being missed and picked up by the subsequent runs of the optimization pass.
The purpose of this initial patch is to stage the transition by first introducing the flag, then focus on understanding where the missed optimizations occur so we can fix (for lack of a better word) the NPM pass pipeline.
When the flag is eventually flipped, it's possible the compile-time benefits also disappear due to the introduction of additional optimization passes, but the current pathological cases of high compile times due to repeating (truly unnecessary) optimizations, should remain resolved.

llvm/lib/Analysis/CGSCCPassManager.cpp

557–558

ArgumentPromotion outright deletes the function and clears the AM. I made the comment more general.

906

When passes call into here, I we can assume FunctionStatusAnalysis can be invalidated because something changed.

But this is also entered from line 596, which happens after the function simplification pipeline finishes. The last thing that the pipeline does is it caches a FunctionStatusAnalysis::Result. Well, so next thing that would happen is we'd yank it here - unless we indicate this is the one case we don't want that to happen.

llvm/test/Other/new-pass-manager-cgscc-fct-proxy.ll

39

oh - we still run it there. I think there's one more inlining happening in f3.

[mtrofin]

fixups

[aeubanks]

llvm/lib/Analysis/CGSCCPassManager.cpp

906

How would it be yanked? The RequireAnalysis pass after the function simplification pipeline preserves all analyses.
Removing these two lines and running check-llvm still passes.

[mtrofin]

llvm/lib/Analysis/CGSCCPassManager.cpp

906

Well, removing these 2 lines then doesn't invalidate FunctionAnalysisStatus ever :)

[aeubanks]

Talking offline with mtrofin, IMO in an ideal world:

• the analysis should be invalidatable like a typical stateful analysis result (I hadn't noticed the analysis here was immutable, that's why I was confused, plus the invalidate vs clear distinction)
• the logic around InvalidateSA shouldn't be necessary, the existing invalidation infra should handle it
• all CGSCC passes specify that they preserve all function analyses and only manually invalidate function analyses on functions that they have modified
  • this wouldn't happen in updateCGAndAnalysisManagerForPass() since that's mostly just for keeping the call graph up to date, passes that don't change the call graph won't call that (e.g. PostOrderFunctionAttrsPass)
  • this could save some compile time in general since right now we're invalidating function analysis results for all functions in an SCC if any function has changed

[mtrofin]

updated post consolidation of pass invalidation

[aeubanks]

llvm/lib/Analysis/CGSCCPassManager.cpp

588

this can go back to the original code

llvm/lib/Passes/PassBuilder.cpp

1033

do we need to add a pass to invalidate FunctionStatusAnalysis after the inliner pipeline so that CGSCC pipelines after the inliner pipeline aren't skipped?

[mtrofin]

feedback

llvm/lib/Passes/PassBuilder.cpp

1033

done

[aeubanks]

llvm/lib/Passes/PassBuilder.cpp

1033

We already have InvalidateAnalysisPass<FunctionStatusAnalysis> for that.
It'd be nice if we could add it inside buildInlinerPipeline() since it's logically part of the inliner pipeline, but we only use it in one place so maybe it doesn't matter so much

[mtrofin]

Using InvalidateAnalysisPass

[mtrofin]

llvm/lib/Passes/PassBuilder.cpp

1033

done for the InvalidateAnalysisPass, thanks for pointing it out!

I want to rationalize a bit better things in the module inliner wrapper pass, so the invalidation of the status analysis should fall in in that patch.

[aeubanks]

looks good, just some nits on comments

llvm/lib/Analysis/CGSCCPassManager.cpp

558–559

this is no longer relevant

llvm/lib/Passes/PassBuilder.cpp

1033

actually, maybe having a bool param in createCGSCCToFunctionPassAdaptor on whether to check for FunctionStatusAnalysis is better than adding the invalidation pass
maybe we could even have the adaptor run the RequireAnalysisPass (or some manual version of it)

just something to consider, not blocking

[mtrofin]

Comment

[mtrofin]

updated test

[aeubanks]

reopening because this was reverted

llvm/include/llvm/Analysis/CGSCCPassManager.h

PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                         LazyCallGraph &CG, CGSCCUpdateResult &UR);
 
   static bool isRequired() { return true; }
 
 private:
   std::unique_ptr<PassConceptT> Pass;
 };
 
+/// A 'signaling' analysis to indicate whether a function has been changed. It
+/// is meant to control the runs of the function pass(es) managed by the
+/// FunctionAnalysisManagerCGSCCProxy.
+class FunctionStatusAnalysis
+    : public AnalysisInfoMixin<FunctionStatusAnalysis> {
+public:
+  static AnalysisKey Key;
+  struct Result {};
+
+  Result run(Function &F, FunctionAnalysisManager &FAM) { return Result(); }
+};
+
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
 CGSCCToFunctionPassAdaptor
 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
   using PassModelT =
       detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
                         FunctionAnalysisManager>;

llvm/lib/Analysis/CGSCCPassManager.cpp

 // template typedefs.
 namespace llvm {
 
 static cl::opt<bool> AbortOnMaxDevirtIterationsReached(
     "abort-on-max-devirt-iterations-reached",
     cl::desc("Abort when the max iterations for devirtualization CGSCC repeat "
              "pass is reached"));
 
+AnalysisKey FunctionStatusAnalysis::Key;
+
 // Explicit instantiations for the core proxy templates.
 template class AllAnalysesOn<LazyCallGraph::SCC>;
 template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
 template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
                            LazyCallGraph &, CGSCCUpdateResult &>;
 template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
 template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
                                          LazyCallGraph::SCC, LazyCallGraph &>;
PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,
   for (LazyCallGraph::Node *N : Nodes) {
     // Skip nodes from other SCCs. These may have been split out during
     // processing. We'll eventually visit those SCCs and pick up the nodes
     // there.
     if (CG.lookupSCC(*N) != CurrentC)
       continue;
 
     Function &F = N->getFunction();
+    // The expectation here is that FunctionStatusAnalysis was required at the
+    // end of the function passes pipeline managed by this adaptor. Then, if any
+    // CGSCC passes were re-run because CGSCCs changed (or devirtualization),
+    // and none changed F, then FunctionStatusAnalysis would still be cached
+    // here and we don't need to rerun the passes managed by this adaptor.
+    if (FAM.getCachedResult<FunctionStatusAnalysis>(F))
+      continue;
 
     PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
     if (!PI.runBeforePass<Function>(*Pass, F))
       continue;
 
     PreservedAnalyses PassPA;
     {
       TimeTraceScope TimeScope(Pass->name());
       PassPA = Pass->run(F, FAM);
for (LazyCallGraph::Node *N : Nodes) {
 
     // If the call graph hasn't been preserved, update it based on this
     // function pass. This may also update the current SCC to point to
     // a smaller, more refined SCC.
     auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
     if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
       CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
                                                             AM, UR, FAM);
       assert(CG.lookupSCC(*N) == CurrentC &&
              "Current SCC not updated to the SCC containing the current node!");
     }
   }
 
   // By definition we preserve the proxy. And we preserve all analyses on
   // Functions. This precludes *any* invalidation of function analyses by the
   // proxy, but that's OK because we've taken care to invalidate analyses in
   // the function analysis manager incrementally above.
incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
   return C;
 }
 
 static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
     LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
     CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
     FunctionAnalysisManager &FAM, bool FunctionPass) {
   using Node = LazyCallGraph::Node;
   using Edge = LazyCallGraph::Edge;
   using SCC = LazyCallGraph::SCC;
   using RefSCC = LazyCallGraph::RefSCC;
 
   RefSCC &InitialRC = InitialC.getOuterRefSCC();
   SCC *C = &InitialC;
   RefSCC *RC = &InitialRC;
   Function &F = N.getFunction();
 

llvm/lib/Passes/PassBuilder.cpp

 /// This file provides the implementation of the PassBuilder based on our
 /// static pass registry as well as related functionality. It also provides
 /// helpers to aid in analyzing, debugging, and testing passes and pass
 /// pipelines.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
static cl::opt<bool> PerformMandatoryInliningsFirst(
     "mandatory-inlining-first", cl::init(true), cl::Hidden, cl::ZeroOrMore,
     cl::desc("Perform mandatory inlinings module-wide, before performing "
              "inlining."));
 
 static cl::opt<bool> EnableO3NonTrivialUnswitching(
     "enable-npm-O3-nontrivial-unswitch", cl::init(true), cl::Hidden,
     cl::ZeroOrMore, cl::desc("Enable non-trivial loop unswitching for -O3"));
 
+static cl::opt<bool> DoNotRerunFunctionPasses(
+    "cgscc-npm-no-fp-rerun", cl::init(false),
+    cl::desc("Do not rerun function passes wrapped by the scc pass adapter, if "
+             "they were run already and the function hasn't changed."));
+
 PipelineTuningOptions::PipelineTuningOptions() {
   LoopInterleaving = true;
   LoopVectorization = true;
   SLPVectorization = false;
   LoopUnrolling = true;
   ForgetAllSCEVInLoopUnroll = ForgetSCEVInLoopUnroll;
   Coroutines = false;
   LicmMssaOptCap = SetLicmMssaOptCap;
PassBuilder::buildInlinerPipeline(OptimizationLevel Level,
   if (Level == OptimizationLevel::O2 || Level == OptimizationLevel::O3)
     MainCGPipeline.addPass(OpenMPOptCGSCCPass());
 
   for (auto &C : CGSCCOptimizerLateEPCallbacks)
     C(MainCGPipeline, Level);
 
   // Lastly, add the core function simplification pipeline nested inside the
   // CGSCC walk.
-  MainCGPipeline.addPass(createCGSCCToFunctionPassAdaptor(
-      buildFunctionSimplificationPipeline(Level, Phase)));
+  auto FSP = buildFunctionSimplificationPipeline(Level, Phase);
+  if (DoNotRerunFunctionPasses)
+    FSP.addPass(RequireAnalysisPass<FunctionStatusAnalysis, Function>());
+  MainCGPipeline.addPass(createCGSCCToFunctionPassAdaptor(std::move(FSP)));
 
   return MIWP;
 }
 
 ModulePassManager
 PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
                                                ThinOrFullLTOPhase Phase) {
   ModulePassManager MPM(DebugLogging);
if (PGOOpt && Phase != ThinOrFullLTOPhase::ThinLTOPostLink &&
       PGOOpt->CSAction == PGOOptions::CSIRInstr)
     MPM.addPass(PGOInstrumentationGenCreateVar(PGOOpt->CSProfileGenFile));
 
   // Synthesize function entry counts for non-PGO compilation.
   if (EnableSyntheticCounts && !PGOOpt)
     MPM.addPass(SyntheticCountsPropagation());
 
   MPM.addPass(buildInlinerPipeline(Level, Phase));
+  if (DoNotRerunFunctionPasses)
+    MPM.addPass(createModuleToFunctionPassAdaptor(
+        InvalidateAnalysisPass<FunctionStatusAnalysis>()));
 
   if (EnableMemProfiler && Phase != ThinOrFullLTOPhase::ThinLTOPreLink) {
     MPM.addPass(createModuleToFunctionPassAdaptor(MemProfilerPass()));
     MPM.addPass(ModuleMemProfilerPass());
   }
 
   return MPM;
 }

llvm/lib/Passes/PassRegistry.def

 FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
 FUNCTION_ANALYSIS("stack-safety-local", StackSafetyAnalysis())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 FUNCTION_ANALYSIS("verify", VerifierAnalysis())
 FUNCTION_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
 FUNCTION_ANALYSIS("divergence", DivergenceAnalysis())
+FUNCTION_ANALYSIS("func-status", FunctionStatusAnalysis())
 
 #ifndef FUNCTION_ALIAS_ANALYSIS
 #define FUNCTION_ALIAS_ANALYSIS(NAME, CREATE_PASS)                             \
   FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ALIAS_ANALYSIS("basic-aa", BasicAA())
 FUNCTION_ALIAS_ANALYSIS("cfl-anders-aa", CFLAndersAA())
 FUNCTION_ALIAS_ANALYSIS("cfl-steens-aa", CFLSteensAA())

llvm/test/Other/new-pass-manager-cgscc-fct-proxy.ll

+; RUN: opt %s -disable-verify -disable-output -passes='default<O2>' -debug-pass-manager -cgscc-npm-no-fp-rerun=1 \
+; RUN:  2>&1 | FileCheck %s -check-prefixes=CHECK,NOREPS
+; RUN: opt %s -disable-verify -disable-output -passes='default<O2>' -debug-pass-manager -cgscc-npm-no-fp-rerun=0 \
+; RUN:  2>&1 | FileCheck %s -check-prefixes=CHECK,REPS
+
+; Pre-attribute the functions to avoid the PostOrderFunctionAttrsPass cause
+; changes (and keep the test simple)
+attributes #0 = { nofree noreturn nosync nounwind readnone }
+
+define void @f1(void()* %p) {
+  call void %p()
+  ret void
+}
+
+define void @f2() #0 {
+  call void @f1(void()* @f2)
+  call void @f3()
+  ret void
+}
+
+define void @f3() #0 {
+  call void @f2()
+  ret void
+}
+
+; CHECK:          Starting CGSCC pass manager run
+; CHECK-NEXT:     Running pass: InlinerPass on (f1)
+; NOREPS:         Running analysis: FunctionStatusAnalysis on f1
+; CHECK:          Finished CGSCC pass manager run.
+
+; CHECK:          Starting CGSCC pass manager run
+; CHECK-NEXT:     Running pass: InlinerPass on (f2, f3)
+; NOREPS:         Running analysis: FunctionStatusAnalysis on f2
+; CHECK:          Finished CGSCC pass manager run.
+
+; CHECK:          Starting CGSCC pass manager run
+; CHECK-NEXT:     Running pass: InlinerPass on (f2)
+; REPS:           Running pass: SROA on f2
+; NOREPS-NOT:     Running pass: SROA on f2
+; CHECK:          Finished CGSCC pass manager run.
+
+; CHECK:          Starting CGSCC pass manager run.
+; CHECK-NEXT:     Running pass: InlinerPass on (f3)
+; CHECK:          Running pass: SROA on f3

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

CGSCCPassManagerTest()
             "  ret void\n"
             "}\n"
             "define void @f() {\n"
             "entry:\n"
             "  call void @g()\n"
             "  call void @h1()\n"
             "  ret void\n"
             "}\n")) {
+    FAM.registerPass([&] { return FunctionStatusAnalysis(); });
     FAM.registerPass([&] { return TargetLibraryAnalysis(); });
     MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
     MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
 
     // Register required pass instrumentation analysis.
     MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
     CGAM.registerPass([&] { return PassInstrumentationAnalysis(); });
     FAM.registerPass([&] { return PassInstrumentationAnalysis(); });