[NewPM] Add option to prevent rerunning function pipeline on functions in CGSCC adaptor
In a CGSCC pass manager, we may visit the same function multiple times
due to SCC mutations. In the inliner pipeline, this results in running
the function simplification pipeline on a function multiple times even
if it hasn't been changed since the last function simplification
pipeline run.
We use a newly introduced analysis to keep track of whether or not a
function has changed since the last time the function simplification
pipeline has run on it. If we see this analysis available for a function
in a CGSCCToFunctionPassAdaptor, we skip running the function passes on
the function. The analysis is queried at the end of the function passes
so that it's available after the first time the function simplification
pipeline runs on a function. This is a per-adaptor option so it doesn't
apply to every adaptor.
The goal of this is to improve compile times. However, currently we
can't turn this on by default at least for the higher optimization
levels since the function simplification pipeline is not robust enough
to be idempotent in many cases, resulting in performance regressions if
we stop running the function simplification pipeline on a function
multiple times. We may be able to turn this on for -O1 in the near
future, but turning this on for higher optimization levels would require
more investment in the function simplification pipeline.
Heavily inspired by D98103.
Example compile time improvements with flag turned on:
https://llvm-compile-time-tracker.com/compare.php?from=998dc4a5d3491d2ae8cbe742d2e13bc1b0cacc5f&to=5c27c913687d3d5559ef3ab42b5a3d513531d61c&stat=instructions
Reviewed By: asbirlea, nikic
Differential Revision: https://reviews.llvm.org/D113947
diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h
index b348b47..7cf172d 100644
--- a/llvm/include/llvm/Analysis/CGSCCPassManager.h
+++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h
@@ -478,11 +478,13 @@
using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>;
explicit CGSCCToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass,
- bool EagerlyInvalidate)
- : Pass(std::move(Pass)), EagerlyInvalidate(EagerlyInvalidate) {}
+ bool EagerlyInvalidate, bool NoRerun)
+ : Pass(std::move(Pass)), EagerlyInvalidate(EagerlyInvalidate),
+ NoRerun(NoRerun) {}
CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
- : Pass(std::move(Arg.Pass)), EagerlyInvalidate(Arg.EagerlyInvalidate) {}
+ : Pass(std::move(Arg.Pass)), EagerlyInvalidate(Arg.EagerlyInvalidate),
+ NoRerun(Arg.NoRerun) {}
friend void swap(CGSCCToFunctionPassAdaptor &LHS,
CGSCCToFunctionPassAdaptor &RHS) {
@@ -513,6 +515,7 @@
private:
std::unique_ptr<PassConceptT> Pass;
bool EagerlyInvalidate;
+ bool NoRerun;
};
/// A function to deduce a function pass type and wrap it in the
@@ -520,7 +523,8 @@
template <typename FunctionPassT>
CGSCCToFunctionPassAdaptor
createCGSCCToFunctionPassAdaptor(FunctionPassT &&Pass,
- bool EagerlyInvalidate = false) {
+ bool EagerlyInvalidate = false,
+ bool NoRerun = false) {
using PassModelT =
detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
FunctionAnalysisManager>;
@@ -529,9 +533,23 @@
return CGSCCToFunctionPassAdaptor(
std::unique_ptr<CGSCCToFunctionPassAdaptor::PassConceptT>(
new PassModelT(std::forward<FunctionPassT>(Pass))),
- EagerlyInvalidate);
+ EagerlyInvalidate, NoRerun);
}
+// A marker to determine if function passes should be run on a function within a
+// CGSCCToFunctionPassAdaptor. This is used to prevent running an expensive
+// function pass (manager) on a function multiple times if SCC mutations cause a
+// function to be visited multiple times and the function is not modified by
+// other SCC passes.
+class ShouldNotRunFunctionPassesAnalysis
+ : public AnalysisInfoMixin<ShouldNotRunFunctionPassesAnalysis> {
+public:
+ static AnalysisKey Key;
+ struct Result {};
+
+ Result run(Function &F, FunctionAnalysisManager &FAM) { return Result(); }
+};
+
/// A helper that repeats an SCC pass each time an indirect call is refined to
/// a direct call by that pass.
///
diff --git a/llvm/include/llvm/Transforms/IPO/Inliner.h b/llvm/include/llvm/Transforms/IPO/Inliner.h
index 2d99a25..a706094 100644
--- a/llvm/include/llvm/Transforms/IPO/Inliner.h
+++ b/llvm/include/llvm/Transforms/IPO/Inliner.h
@@ -132,11 +132,16 @@
/// before run is called, as part of pass pipeline building.
CGSCCPassManager &getPM() { return PM; }
- /// Allow adding module-level passes benefiting the contained CGSCC passes.
+ /// Add a module pass that runs before the CGSCC passes.
template <class T> void addModulePass(T Pass) {
MPM.addPass(std::move(Pass));
}
+ /// Add a module pass that runs after the CGSCC passes.
+ template <class T> void addLateModulePass(T Pass) {
+ AfterCGMPM.addPass(std::move(Pass));
+ }
+
void printPipeline(raw_ostream &OS,
function_ref<StringRef(StringRef)> MapClassName2PassName);
@@ -144,8 +149,10 @@
const InlineParams Params;
const InliningAdvisorMode Mode;
const unsigned MaxDevirtIterations;
+ // TODO: Clean this up so we only have one ModulePassManager.
CGSCCPassManager PM;
ModulePassManager MPM;
+ ModulePassManager AfterCGMPM;
};
} // end namespace llvm
diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp
index 3d2c5e8..c60b70a 100644
--- a/llvm/lib/Analysis/CGSCCPassManager.cpp
+++ b/llvm/lib/Analysis/CGSCCPassManager.cpp
@@ -43,6 +43,8 @@
cl::desc("Abort when the max iterations for devirtualization CGSCC repeat "
"pass is reached"));
+AnalysisKey ShouldNotRunFunctionPassesAnalysis::Key;
+
// Explicit instantiations for the core proxy templates.
template class AllAnalysesOn<LazyCallGraph::SCC>;
template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
@@ -540,6 +542,9 @@
Function &F = N->getFunction();
+ if (NoRerun && FAM.getCachedResult<ShouldNotRunFunctionPassesAnalysis>(F))
+ continue;
+
PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
if (!PI.runBeforePass<Function>(*Pass, F))
continue;
@@ -556,6 +561,8 @@
// function's analyses (that's the contract of a function pass), so
// directly handle the function analysis manager's invalidation here.
FAM.invalidate(F, EagerlyInvalidate ? PreservedAnalyses::none() : PassPA);
+ if (NoRerun)
+ (void)FAM.getResult<ShouldNotRunFunctionPassesAnalysis>(F);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
diff --git a/llvm/lib/Passes/PassBuilderPipelines.cpp b/llvm/lib/Passes/PassBuilderPipelines.cpp
index 39ba0f9..ac5dfdb 100644
--- a/llvm/lib/Passes/PassBuilderPipelines.cpp
+++ b/llvm/lib/Passes/PassBuilderPipelines.cpp
@@ -171,6 +171,13 @@
"eagerly-invalidate-analyses", cl::init(true), cl::Hidden,
cl::desc("Eagerly invalidate more analyses in default pipelines"));
+static cl::opt<bool> EnableNoRerunSimplificationPipeline(
+ "enable-no-rerun-simplification-pipeline", cl::init(false), cl::Hidden,
+ cl::desc(
+ "Prevent running the simplification pipeline on a function more "
+ "than once in the case that SCC mutations cause a function to be "
+ "visited multiple times as long as the function has not been changed"));
+
PipelineTuningOptions::PipelineTuningOptions() {
LoopInterleaving = true;
LoopVectorization = true;
@@ -736,10 +743,14 @@
// CGSCC walk.
MainCGPipeline.addPass(createCGSCCToFunctionPassAdaptor(
buildFunctionSimplificationPipeline(Level, Phase),
- PTO.EagerlyInvalidateAnalyses));
+ PTO.EagerlyInvalidateAnalyses, EnableNoRerunSimplificationPipeline));
MainCGPipeline.addPass(CoroSplitPass(Level != OptimizationLevel::O0));
+ if (EnableNoRerunSimplificationPipeline)
+ MIWP.addLateModulePass(createModuleToFunctionPassAdaptor(
+ InvalidateAnalysisPass<ShouldNotRunFunctionPassesAnalysis>()));
+
return MIWP;
}
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index dee4196..c2032b5 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -201,6 +201,7 @@
FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
FUNCTION_ANALYSIS("opt-remark-emit", OptimizationRemarkEmitterAnalysis())
FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
+FUNCTION_ANALYSIS("should-not-run-function-passes", ShouldNotRunFunctionPassesAnalysis())
FUNCTION_ANALYSIS("stack-safety-local", StackSafetyAnalysis())
FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
FUNCTION_ANALYSIS("targetir",
diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp
index 4d8e519..992c2b2 100644
--- a/llvm/lib/Transforms/IPO/Inliner.cpp
+++ b/llvm/lib/Transforms/IPO/Inliner.cpp
@@ -1109,6 +1109,8 @@
else
MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(
createDevirtSCCRepeatedPass(std::move(PM), MaxDevirtIterations)));
+
+ MPM.addPass(std::move(AfterCGMPM));
MPM.run(M, MAM);
// Discard the InlineAdvisor, a subsequent inlining session should construct
diff --git a/llvm/test/Other/no-rerun-function-simplification-pipeline.ll b/llvm/test/Other/no-rerun-function-simplification-pipeline.ll
new file mode 100644
index 0000000..f42ae9a
--- /dev/null
+++ b/llvm/test/Other/no-rerun-function-simplification-pipeline.ll
@@ -0,0 +1,35 @@
+; RUN: opt < %s -passes='default<O1>' -disable-output -debug-pass-manager=verbose 2>&1 | FileCheck %s --check-prefixes=CHECK,NORMAL
+; RUN: opt < %s -passes='default<O2>' -disable-output -debug-pass-manager=verbose 2>&1 | FileCheck %s --check-prefixes=CHECK,NORMAL
+; RUN: opt < %s -passes='default<O1>' -disable-output -debug-pass-manager=verbose -enable-no-rerun-simplification-pipeline=1 2>&1 | FileCheck %s --check-prefixes=CHECK,NORERUN
+; RUN: opt < %s -passes='default<O2>' -disable-output -debug-pass-manager=verbose -enable-no-rerun-simplification-pipeline=1 2>&1 | FileCheck %s --check-prefixes=CHECK,NORERUN
+
+; BDCE only runs once in the function simplification pipeline and nowhere else so we use that to check for reruns.
+
+; CHECK: PassManager{{.*}}SCC{{.*}} on (f1)
+; CHECK: Running pass: BDCEPass on f1
+; CHECK: PassManager{{.*}}SCC{{.*}} on (f2, f3)
+; CHECK: Running pass: BDCEPass on f2
+; CHECK-NOT: BDCEPass
+; CHECK: PassManager{{.*}}SCC{{.*}} on (f2)
+; NORMAL: Running pass: BDCEPass on f2
+; NORERUN-NOT: Running pass: BDCEPass on f2
+; CHECK: PassManager{{.*}}SCC{{.*}} on (f3)
+; CHECK: Running pass: BDCEPass on f3
+
+define void @f1(void()* %p) alwaysinline {
+ 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
+}
+
+attributes #0 = { nofree noreturn nosync nounwind readnone noinline }
\ No newline at end of file
