aboutsummaryrefslogtreecommitdiff
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Analysis/CGSCCPassManager.h17
-rw-r--r--llvm/include/llvm/IR/PassManager.h23
-rw-r--r--llvm/lib/Analysis/CGSCCPassManager.cpp57
-rw-r--r--llvm/unittests/Analysis/CGSCCPassManagerTest.cpp166
4 files changed, 248 insertions, 15 deletions
diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h
index a15a9e1..32868cb 100644
--- a/llvm/include/llvm/Analysis/CGSCCPassManager.h
+++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h
@@ -577,12 +577,17 @@ public:
// analyses will eventually occur when the module pass completes.
PA.intersect(std::move(PassPA));
- // Update the call graph based on this function pass. This may also
- // update the current SCC to point to a smaller, more refined SCC.
- CurrentC = &updateCGAndAnalysisManagerForFunctionPass(
- CG, *CurrentC, *N, AM, UR, DebugLogging);
- assert(CG.lookupSCC(*N) == CurrentC &&
- "Current SCC not updated to the SCC containing the current node!");
+ // 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, DebugLogging);
+ 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
diff --git a/llvm/include/llvm/IR/PassManager.h b/llvm/include/llvm/IR/PassManager.h
index ab9b1e8..3931756 100644
--- a/llvm/include/llvm/IR/PassManager.h
+++ b/llvm/include/llvm/IR/PassManager.h
@@ -1070,10 +1070,27 @@ public:
const AnalysisManagerT &getManager() const { return *AM; }
- /// \brief Handle invalidation by ignoring it; this pass is immutable.
+ /// When invalidation occurs, remove any registered invalidation events.
bool invalidate(
- IRUnitT &, const PreservedAnalyses &,
- typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &) {
+ IRUnitT &IRUnit, const PreservedAnalyses &PA,
+ typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv) {
+ // Loop over the set of registered outer invalidation mappings and if any
+ // of them map to an analysis that is now invalid, clear it out.
+ SmallVector<AnalysisKey *, 4> DeadKeys;
+ for (auto &KeyValuePair : OuterAnalysisInvalidationMap) {
+ AnalysisKey *OuterID = KeyValuePair.first;
+ auto &InnerIDs = KeyValuePair.second;
+ InnerIDs.erase(llvm::remove_if(InnerIDs, [&](AnalysisKey *InnerID) {
+ return Inv.invalidate(InnerID, IRUnit, PA); }),
+ InnerIDs.end());
+ if (InnerIDs.empty())
+ DeadKeys.push_back(OuterID);
+ }
+
+ for (auto OuterID : DeadKeys)
+ OuterAnalysisInvalidationMap.erase(OuterID);
+
+ // The proxy itself remains valid regardless of anything else.
return false;
}
diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp
index b0a7d30..8205bba 100644
--- a/llvm/lib/Analysis/CGSCCPassManager.cpp
+++ b/llvm/lib/Analysis/CGSCCPassManager.cpp
@@ -262,6 +262,51 @@ bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate(
} // End llvm namespace
+/// When a new SCC is created for the graph and there might be function
+/// analysis results cached for the functions now in that SCC two forms of
+/// updates are required.
+///
+/// First, a proxy from the SCC to the FunctionAnalysisManager needs to be
+/// created so that any subsequent invalidation events to the SCC are
+/// propagated to the function analysis results cached for functions within it.
+///
+/// Second, if any of the functions within the SCC have analysis results with
+/// outer analysis dependencies, then those dependencies would point to the
+/// *wrong* SCC's analysis result. We forcibly invalidate the necessary
+/// function analyses so that they don't retain stale handles.
+static void updateNewSCCFunctionAnalyses(LazyCallGraph::SCC &C,
+ LazyCallGraph &G,
+ CGSCCAnalysisManager &AM) {
+ // Get the relevant function analysis manager.
+ auto &FAM =
+ AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, G).getManager();
+
+ // Now walk the functions in this SCC and invalidate any function analysis
+ // results that might have outer dependencies on an SCC analysis.
+ for (LazyCallGraph::Node &N : C) {
+ Function &F = N.getFunction();
+
+ auto *OuterProxy =
+ FAM.getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F);
+ if (!OuterProxy)
+ // No outer analyses were queried, nothing to do.
+ continue;
+
+ // Forcibly abandon all the inner analyses with dependencies, but
+ // invalidate nothing else.
+ auto PA = PreservedAnalyses::all();
+ for (const auto &OuterInvalidationPair :
+ OuterProxy->getOuterInvalidations()) {
+ const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
+ for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
+ PA.abandon(InnerAnalysisID);
+ }
+
+ // Now invalidate anything we found.
+ FAM.invalidate(F, PA);
+ }
+}
+
namespace {
/// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c
/// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly
@@ -314,9 +359,9 @@ incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
AM.invalidate(*OldC, PA);
- // Ensure we have a proxy for the now-current SCC if needed.
+ // Ensure the now-current SCC's function analyses are updated.
if (NeedFAMProxy)
- (void)AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G);
+ updateNewSCCFunctionAnalyses(*C, G, AM);
for (SCC &NewC :
reverse(make_range(std::next(NewSCCRange.begin()), NewSCCRange.end()))) {
@@ -326,12 +371,12 @@ incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
if (DebugLogging)
dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n";
- // Ensure new SCCs have a FAM proxy if needed.
+ // Ensure new SCCs' function analyses are updated.
if (NeedFAMProxy)
- (void)AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G);
+ updateNewSCCFunctionAnalyses(*C, G, AM);
- // And propagate an invalidation to the new SCC as only the current will
- // get one from the pass manager infrastructure.
+ // Also propagate a normal invalidation to the new SCC as only the current
+ // will get one from the pass manager infrastructure.
AM.invalidate(NewC, PA);
}
return C;
diff --git a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
index 6ab3073..929c375 100644
--- a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
+++ b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
@@ -1101,4 +1101,170 @@ TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
// Four passes count each of six functions once (via SCCs).
EXPECT_EQ(4 * 6, FunctionCount);
}
+
+TEST_F(CGSCCPassManagerTest, TestAnalysisInvalidationCGSCCUpdate) {
+ int ModuleAnalysisRuns = 0;
+ MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
+
+ int SCCAnalysisRuns = 0, IndirectSCCAnalysisRuns = 0,
+ DoublyIndirectSCCAnalysisRuns = 0;
+ CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
+ CGAM.registerPass(
+ [&] { return TestIndirectSCCAnalysis(IndirectSCCAnalysisRuns); });
+ CGAM.registerPass([&] {
+ return TestDoublyIndirectSCCAnalysis(DoublyIndirectSCCAnalysisRuns);
+ });
+
+ int FunctionAnalysisRuns = 0, IndirectFunctionAnalysisRuns = 0;
+ FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
+ FAM.registerPass([&] {
+ return TestIndirectFunctionAnalysis(IndirectFunctionAnalysisRuns);
+ });
+
+ ModulePassManager MPM(/*DebugLogging*/ true);
+
+ CGSCCPassManager CGPM(/*DebugLogging*/ true);
+ // First just use the analysis to get the function count and preserve
+ // everything.
+ using RequireTestIndirectFunctionAnalysisPass =
+ RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>;
+ using RequireTestDoublyIndirectSCCAnalysisPass =
+ RequireAnalysisPass<TestDoublyIndirectSCCAnalysis, LazyCallGraph::SCC,
+ CGSCCAnalysisManager, LazyCallGraph &,
+ CGSCCUpdateResult &>;
+ CGPM.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
+ CGPM.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireTestIndirectFunctionAnalysisPass()));
+
+ // Next, we inject an SCC pass that invalidates everything for the `(h3, h1,
+ // h2)` SCC but also deletes the call edge from `h2` to `h3` and updates the
+ // CG. This should successfully invalidate (and force to be re-run) all the
+ // analyses for that SCC and for the functions.
+ CGPM.addPass(
+ LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+ LazyCallGraph &CG, CGSCCUpdateResult &UR) {
+ (void)AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
+ if (C.getName() != "(h3, h1, h2)")
+ return PreservedAnalyses::all();
+
+ // Build the preserved set.
+ auto PA = PreservedAnalyses::none();
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+ PA.preserve<TestIndirectSCCAnalysis>();
+ PA.preserve<TestDoublyIndirectSCCAnalysis>();
+
+ // Delete the call from `h2` to `h3`.
+ auto &H2N = *llvm::find_if(
+ C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; });
+ auto &H2F = H2N.getFunction();
+ auto &H3F = *cast<CallInst>(H2F.begin()->begin())->getCalledFunction();
+ assert(H3F.getName() == "h3" && "Wrong called function!");
+ H2F.begin()->begin()->eraseFromParent();
+ // Insert a bitcast of `h3` so that we retain a ref edge to it.
+ (void)CastInst::CreatePointerCast(&H3F,
+ Type::getInt8PtrTy(H2F.getContext()),
+ "dummy", &*H2F.begin()->begin());
+
+ // Now update the call graph.
+ auto &NewC = updateCGAndAnalysisManagerForFunctionPass(
+ CG, C, H2N, AM, UR, /*DebugLogging*/ true);
+ assert(&NewC != &C && "Should get a new SCC due to update!");
+
+ return PA;
+ }));
+ // Now use the analysis again on each SCC and function, forcing
+ // re-computation for all of them.
+ CGPM.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
+ CGPM.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireTestIndirectFunctionAnalysisPass()));
+
+ // Create another CGSCC pipeline that requires all the analyses again.
+ CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+ CGPM2.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
+ CGPM2.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireTestIndirectFunctionAnalysisPass()));
+
+ // Next we inject an SCC pass that finds the `(h2)` SCC, adds a call to `h3`
+ // back to `h2`, and then invalidates everything for what will then be the
+ // `(h3, h1, h2)` SCC again.
+ CGSCCPassManager CGPM3(/*DebugLogging*/ true);
+ CGPM3.addPass(
+ LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+ LazyCallGraph &CG, CGSCCUpdateResult &UR) {
+ (void)AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
+ if (C.getName() != "(h2)")
+ return PreservedAnalyses::all();
+
+ // Build the preserved set.
+ auto PA = PreservedAnalyses::none();
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+ PA.preserve<TestIndirectSCCAnalysis>();
+ PA.preserve<TestDoublyIndirectSCCAnalysis>();
+
+ // Delete the bitcast of `h3` that we added earlier.
+ auto &H2N = *C.begin();
+ auto &H2F = H2N.getFunction();
+ auto &H3F = *cast<Function>(cast<BitCastInst>(H2F.begin()->begin())->getOperand(0));
+ assert(H3F.getName() == "h3" && "Wrong called function!");
+ H2F.begin()->begin()->eraseFromParent();
+ // And insert a call to `h3`.
+ (void)CallInst::Create(&H3F, {}, "", &*H2F.begin()->begin());
+
+ // Now update the call graph.
+ auto &NewC = updateCGAndAnalysisManagerForFunctionPass(
+ CG, C, H2N, AM, UR, /*DebugLogging*/ true);
+ assert(&NewC != &C && "Should get a new SCC due to update!");
+
+ return PA;
+ }));
+ // Now use the analysis again on each SCC and function, forcing
+ // re-computation for all of them.
+ CGPM3.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
+ CGPM3.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireTestIndirectFunctionAnalysisPass()));
+
+ // Create a second CGSCC pass manager. This will cause the module-level
+ // invalidation to occur, which will force yet another invalidation of the
+ // indirect SCC-level analysis as the module analysis it depends on gets
+ // invalidated.
+ CGSCCPassManager CGPM4(/*DebugLogging*/ true);
+ CGPM4.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
+ CGPM4.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireTestIndirectFunctionAnalysisPass()));
+
+ // Add a requires pass to populate the module analysis and then one of our
+ // CGSCC pipelines. Repeat for all four CGSCC pipelines.
+ MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
+ MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+ MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
+ MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+ MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
+ MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
+ MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
+ MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM4)));
+ MPM.run(*M, MAM);
+
+ // We run over four SCCs the first time. But then we split an SCC into three.
+ // And then we merge those three back into one.
+ EXPECT_EQ(4 + 3 + 1, SCCAnalysisRuns);
+ // The module analysis pass should be run three times.
+ EXPECT_EQ(3, ModuleAnalysisRuns);
+ // We run over four SCCs the first time. Then over the two new ones. Then the
+ // entire module is invalidated causing a full run over all seven. Then we
+ // fold three SCCs back to one, and then run over the whole module again.
+ EXPECT_EQ(4 + 2 + 7 + 1 + 4, IndirectSCCAnalysisRuns);
+ EXPECT_EQ(4 + 2 + 7 + 1 + 4, DoublyIndirectSCCAnalysisRuns);
+
+ // First we run over all six functions. Then we re-run it over three when we
+ // split their SCCs. Then we re-run over the whole module. Then we re-run
+ // over three functions merged back into a single SCC, and then over the
+ // whole module again.
+ EXPECT_EQ(6 + 2 + 6 + 3 + 6, FunctionAnalysisRuns);
+
+ // Re run the function analysis twice over the entire module, and then re-run
+ // it over the `(h3, h1, h2)` SCC due to invalidation. Then we re-un over
+ // three functions merged back into a single SCC, and then over the whole
+ // module.
+ EXPECT_EQ(6 + 2 + 6 + 3 + 6, IndirectFunctionAnalysisRuns);
+}
}
generated by cgit v1.1 at 2025-08-02 19:36:00 +0000