summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/lib/Analysis/CGSCCPassManager.cpp110
-rw-r--r--llvm/lib/Transforms/IPO/Inliner.cpp10
-rw-r--r--llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll28
-rw-r--r--llvm/unittests/Analysis/CGSCCPassManagerTest.cpp30
4 files changed, 144 insertions, 34 deletions
diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp
index 9d4521221f4..b0a7d306b26 100644
--- a/llvm/lib/Analysis/CGSCCPassManager.cpp
+++ b/llvm/lib/Analysis/CGSCCPassManager.cpp
@@ -196,13 +196,67 @@ FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C,
bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate(
LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
CGSCCAnalysisManager::Invalidator &Inv) {
- for (LazyCallGraph::Node &N : C)
- FAM->invalidate(N.getFunction(), PA);
+ // If literally everything is preserved, we're done.
+ if (PA.areAllPreserved())
+ return false; // This is still a valid proxy.
+
+ // If this proxy isn't marked as preserved, then even if the result remains
+ // valid, the key itself may no longer be valid, so we clear everything.
+ //
+ // Note that in order to preserve this proxy, a module pass must ensure that
+ // the FAM has been completely updated to handle the deletion of functions.
+ // Specifically, any FAM-cached results for those functions need to have been
+ // forcibly cleared. When preserved, this proxy will only invalidate results
+ // cached on functions *still in the module* at the end of the module pass.
+ auto PAC = PA.getChecker<FunctionAnalysisManagerCGSCCProxy>();
+ if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) {
+ for (LazyCallGraph::Node &N : C)
+ FAM->clear(N.getFunction());
+
+ return true;
+ }
+
+ // Directly check if the relevant set is preserved.
+ bool AreFunctionAnalysesPreserved =
+ PA.allAnalysesInSetPreserved<AllAnalysesOn<Function>>();
+
+ // Now walk all the functions to see if any inner analysis invalidation is
+ // necessary.
+ for (LazyCallGraph::Node &N : C) {
+ Function &F = N.getFunction();
+ Optional<PreservedAnalyses> FunctionPA;
+
+ // Check to see whether the preserved set needs to be pruned based on
+ // SCC-level analysis invalidation that triggers deferred invalidation
+ // registered with the outer analysis manager proxy for this function.
+ if (auto *OuterProxy =
+ FAM->getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F))
+ for (const auto &OuterInvalidationPair :
+ OuterProxy->getOuterInvalidations()) {
+ AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
+ const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
+ if (Inv.invalidate(OuterAnalysisID, C, PA)) {
+ if (!FunctionPA)
+ FunctionPA = PA;
+ for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
+ FunctionPA->abandon(InnerAnalysisID);
+ }
+ }
+
+ // Check if we needed a custom PA set, and if so we'll need to run the
+ // inner invalidation.
+ if (FunctionPA) {
+ FAM->invalidate(F, *FunctionPA);
+ continue;
+ }
+
+ // Otherwise we only need to do invalidation if the original PA set didn't
+ // preserve all function analyses.
+ if (!AreFunctionAnalysesPreserved)
+ FAM->invalidate(F, PA);
+ }
- // This proxy doesn't need to handle invalidation itself. Instead, the
- // module-level CGSCC proxy handles it above by ensuring that if the
- // module-level FAM proxy becomes invalid the entire SCC layer, which
- // includes this proxy, is cleared.
+ // Return false to indicate that this result is still a valid proxy.
return false;
}
@@ -236,7 +290,6 @@ incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
dbgs() << "Enqueuing the existing SCC in the worklist:" << *C << "\n";
SCC *OldC = C;
- (void)OldC;
// Update the current SCC. Note that if we have new SCCs, this must actually
// change the SCC.
@@ -245,6 +298,26 @@ incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
C = &*NewSCCRange.begin();
assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
+ // If we had a cached FAM proxy originally, we will want to create more of
+ // them for each SCC that was split off.
+ bool NeedFAMProxy =
+ AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(*OldC) != nullptr;
+
+ // We need to propagate an invalidation call to all but the newly current SCC
+ // because the outer pass manager won't do that for us after splitting them.
+ // FIXME: We should accept a PreservedAnalysis from the CG updater so that if
+ // there are preserved ananalyses we can avoid invalidating them here for
+ // split-off SCCs.
+ // We know however that this will preserve any FAM proxy so go ahead and mark
+ // that.
+ PreservedAnalyses PA;
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+ AM.invalidate(*OldC, PA);
+
+ // Ensure we have a proxy for the now-current SCC if needed.
+ if (NeedFAMProxy)
+ (void)AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G);
+
for (SCC &NewC :
reverse(make_range(std::next(NewSCCRange.begin()), NewSCCRange.end()))) {
assert(C != &NewC && "No need to re-visit the current SCC!");
@@ -252,6 +325,14 @@ incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
UR.CWorklist.insert(&NewC);
if (DebugLogging)
dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n";
+
+ // Ensure new SCCs have a FAM proxy if needed.
+ if (NeedFAMProxy)
+ (void)AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G);
+
+ // And propagate an invalidation to the new SCC as only the current will
+ // get one from the pass manager infrastructure.
+ AM.invalidate(NewC, PA);
}
return C;
}
@@ -349,14 +430,6 @@ LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
// For separate SCCs this is trivial.
RC->switchTrivialInternalEdgeToRef(N, TargetN);
} else {
- // Otherwise we may end up re-structuring the call graph. First,
- // invalidate any SCC analyses. We have to do this before we split
- // functions into new SCCs and lose track of where their analyses are
- // cached.
- // FIXME: We should accept a more precise preserved set here. For
- // example, it might be possible to preserve some function analyses
- // even as the SCC structure is changed.
- AM.invalidate(*C, PreservedAnalyses::none());
// Now update the call graph.
C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G,
N, C, AM, UR, DebugLogging);
@@ -424,13 +497,6 @@ LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
continue;
}
- // Otherwise we may end up re-structuring the call graph. First, invalidate
- // any SCC analyses. We have to do this before we split functions into new
- // SCCs and lose track of where their analyses are cached.
- // FIXME: We should accept a more precise preserved set here. For example,
- // it might be possible to preserve some function analyses even as the SCC
- // structure is changed.
- AM.invalidate(*C, PreservedAnalyses::none());
// Now update the call graph.
C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N,
C, AM, UR, DebugLogging);
diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp
index ad89e40661c..00ddb93df83 100644
--- a/llvm/lib/Transforms/IPO/Inliner.cpp
+++ b/llvm/lib/Transforms/IPO/Inliner.cpp
@@ -989,5 +989,13 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
// And delete the actual function from the module.
M.getFunctionList().erase(DeadF);
}
- return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+
+ if (!Changed)
+ return PreservedAnalyses::all();
+
+ // Even if we change the IR, we update the core CGSCC data structures and so
+ // can preserve the proxy to the function analysis manager.
+ PreservedAnalyses PA;
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+ return PA;
}
diff --git a/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll b/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll
index 82d321ccf22..f5892e80c31 100644
--- a/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll
+++ b/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll
@@ -11,17 +11,35 @@
; CHECK: Running analysis: FunctionAnalysisManagerCGSCCProxy on (test1_f, test1_g, test1_h)
; CHECK: Running analysis: DominatorTreeAnalysis on test1_f
; CHECK: Running analysis: DominatorTreeAnalysis on test1_g
-; CHECK: Invalidating all non-preserved analyses for: (test1_f, test1_g, test1_h)
+; CHECK: Invalidating all non-preserved analyses for: (test1_f)
; CHECK: Invalidating all non-preserved analyses for: test1_f
; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_f
+; CHECK: Invalidating analysis: LoopAnalysis on test1_f
+; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_f
+; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_f
+; CHECK: Invalidating all non-preserved analyses for: (test1_g, test1_h)
; CHECK: Invalidating all non-preserved analyses for: test1_g
; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_g
-; CHECK: Invalidating all non-preserved analyses for: test1_h
-; CHECK-NOT: Invalidating anaylsis:
-; CHECK: Running analysis: DominatorTreeAnalysis on test1_h
-; CHECK: Invalidating all non-preserved analyses for: (test1_g, test1_h)
+; CHECK: Invalidating analysis: LoopAnalysis on test1_g
+; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_g
+; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_g
; CHECK: Invalidating all non-preserved analyses for: test1_h
; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_h
+; CHECK: Invalidating analysis: LoopAnalysis on test1_h
+; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_h
+; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_h
+; CHECK-NOT: Invalidating analysis:
+; CHECK: Starting llvm::Function pass manager run.
+; CHECK-NEXT: Running pass: DominatorTreeVerifierPass on test1_g
+; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_g
+; CHECK-NEXT: Finished llvm::Function pass manager run.
+; CHECK-NEXT: Starting llvm::Function pass manager run.
+; CHECK-NEXT: Running pass: DominatorTreeVerifierPass on test1_h
+; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_h
+; CHECK-NEXT: Finished llvm::Function pass manager run.
+; CHECK-NOT: Invalidating analysis:
+; CHECK: Running pass: DominatorTreeVerifierPass on test1_f
+; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_f
; An external function used to control branches.
declare i1 @flag()
diff --git a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
index ab5d1862c23..6ab30732b82 100644
--- a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
+++ b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
@@ -680,6 +680,7 @@ TEST_F(CGSCCPassManagerTest, TestSCCPassCanPreserveFunctionAnalysis) {
LazyCallGraph &, CGSCCUpdateResult &) {
PreservedAnalyses PA;
PA.preserve<LazyCallGraphAnalysis>();
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
PA.preserve<TestFunctionAnalysis>();
return PA;
}));
@@ -719,12 +720,14 @@ TEST_F(CGSCCPassManagerTest,
CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
- // Now run a module pass that preserves the LazyCallGraph and proxy but not
+ // Now run a module pass that preserves the LazyCallGraph and proxies but not
// the Function analysis.
MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
PreservedAnalyses PA;
PA.preserve<LazyCallGraphAnalysis>();
PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+ PA.preserve<FunctionAnalysisManagerModuleProxy>();
return PA;
}));
@@ -741,7 +744,7 @@ TEST_F(CGSCCPassManagerTest,
EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
}
-// Check that by marking the function pass and FAM proxy as preserved, this
+// Check that by marking the function pass and proxies as preserved, this
// propagates all the way through.
TEST_F(CGSCCPassManagerTest,
TestModulePassCanPreserveFunctionAnalysisNestedInCGSCC) {
@@ -765,6 +768,7 @@ TEST_F(CGSCCPassManagerTest,
PreservedAnalyses PA;
PA.preserve<LazyCallGraphAnalysis>();
PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
PA.preserve<FunctionAnalysisManagerModuleProxy>();
PA.preserve<TestFunctionAnalysis>();
return PA;
@@ -1014,6 +1018,9 @@ TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
FunctionCount += IndirectResult.SCCDep.FunctionCount;
return PreservedAnalyses::all();
}));
+ CGPM.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
+
// Next, invalidate
// - both analyses for the (f) and (x) SCCs,
// - just the underlying (indirect) analysis for (g) SCC, and
@@ -1026,14 +1033,16 @@ TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
auto &IndirectResult = DoublyIndirectResult.IDep;
FunctionCount += IndirectResult.SCCDep.FunctionCount;
auto PA = PreservedAnalyses::none();
+ PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+ PA.preserveSet<AllAnalysesOn<Function>>();
if (C.getName() == "(g)")
PA.preserve<TestSCCAnalysis>();
else if (C.getName() == "(h3, h1, h2)")
PA.preserve<TestIndirectSCCAnalysis>();
return PA;
}));
- // Finally, use the analysis again on each function, forcing re-computation
- // for all of them.
+ // Finally, use the analysis again on each SCC (and function), forcing
+ // re-computation for all of them.
CGPM.addPass(
LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
LazyCallGraph &CG, CGSCCUpdateResult &) {
@@ -1043,6 +1052,8 @@ TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
FunctionCount += IndirectResult.SCCDep.FunctionCount;
return PreservedAnalyses::all();
}));
+ CGPM.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
// Create a second CGSCC pass manager. This will cause the module-level
// invalidation to occur, which will force yet another invalidation of the
@@ -1058,13 +1069,15 @@ TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
FunctionCount += IndirectResult.SCCDep.FunctionCount;
return PreservedAnalyses::all();
}));
+ CGPM2.addPass(createCGSCCToFunctionPassAdaptor(
+ RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
- // Add a requires pass to populate the module analysis and then our function
+ // Add a requires pass to populate the module analysis and then our CGSCC
// pass pipeline.
MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
// Now require the module analysis again (it will have been invalidated once)
- // and then use it again from a function pass manager.
+ // and then use it again from our second CGSCC pipeline..
MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
MPM.run(*M, MAM);
@@ -1080,6 +1093,11 @@ TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
EXPECT_EQ(3 * 4, IndirectSCCAnalysisRuns);
EXPECT_EQ(3 * 4, DoublyIndirectSCCAnalysisRuns);
+ // We run the indirect function analysis once per function the first time.
+ // Then we re-run it for every SCC but "(g)". Then we re-run it for every
+ // function again.
+ EXPECT_EQ(6 + 5 + 6, IndirectFunctionAnalysisRuns);
+
// Four passes count each of six functions once (via SCCs).
EXPECT_EQ(4 * 6, FunctionCount);
}
OpenPOWER on IntegriCloud