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 @@ -856,7 +856,7 @@ // split-off SCCs. // We know however that this will preserve any FAM proxy so go ahead and mark // that. - PreservedAnalyses PA; + auto PA = PreservedAnalyses::allInSet>(); PA.preserve(); AM.invalidate(*OldC, PA); diff --git a/llvm/lib/Passes/PassBuilderPipelines.cpp b/llvm/lib/Passes/PassBuilderPipelines.cpp --- a/llvm/lib/Passes/PassBuilderPipelines.cpp +++ b/llvm/lib/Passes/PassBuilderPipelines.cpp @@ -163,7 +163,7 @@ cl::ZeroOrMore, cl::desc("Enable non-trivial loop unswitching for -O3")); static cl::opt EnableEagerlyInvalidateAnalyses( - "eagerly-invalidate-analyses", cl::init(false), cl::Hidden, + "eagerly-invalidate-analyses", cl::init(true), cl::Hidden, cl::desc("Eagerly invalidate more analyses in default pipelines")); PipelineTuningOptions::PipelineTuningOptions() { diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp --- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -1016,11 +1016,12 @@ do { LocalChange = false; + FunctionAnalysisManager &FAM = + AM.getResult(C, CG).getManager(); + for (LazyCallGraph::Node &N : C) { Function &OldF = N.getFunction(); - FunctionAnalysisManager &FAM = - AM.getResult(C, CG).getManager(); // FIXME: This lambda must only be used with this function. We should // skip the lambda and just get the AA results directly. auto AARGetter = [&](Function &F) -> AAResults & { @@ -1043,6 +1044,13 @@ C.getOuterRefSCC().replaceNodeFunction(N, *NewF); FAM.clear(OldF, OldF.getName()); OldF.eraseFromParent(); + + PreservedAnalyses FuncPA; + FuncPA.preserveSet(); + for (auto *U : NewF->users()) { + auto *UserF = cast(U)->getParent()->getParent(); + FAM.invalidate(*UserF, FuncPA); + } } Changed |= LocalChange; @@ -1054,6 +1062,8 @@ PreservedAnalyses PA; // We've cleared out analyses for deleted functions. PA.preserve(); + // We've manually invalidated analyses for functions we've modified. + PA.preserveSet>(); return PA; } diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp --- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp @@ -249,7 +249,8 @@ /// Deduce readonly/readnone attributes for the SCC. template -static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) { +static void addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter, + SmallSetVector &Changed) { // Check if any of the functions in the SCC read or write memory. If they // write memory then they can't be marked readnone or readonly. bool ReadsMemory = false; @@ -264,7 +265,7 @@ switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes)) { case MAK_MayWrite: - return false; + return; case MAK_ReadOnly: ReadsMemory = true; break; @@ -280,11 +281,10 @@ // If the SCC contains both functions that read and functions that write, then // we cannot add readonly attributes. if (ReadsMemory && WritesMemory) - return false; + return; // Success! Functions in this SCC do not access memory, or only read memory. // Give them the appropriate attribute. - bool MadeChange = false; for (Function *F : SCCNodes) { if (F->doesNotAccessMemory()) @@ -298,7 +298,7 @@ if (F->doesNotReadMemory() && WritesMemory) continue; - MadeChange = true; + Changed.insert(F); // Clear out any existing attributes. AttrBuilder AttrsToRemove; @@ -327,8 +327,6 @@ else ++NumReadNone; } - - return MadeChange; } // Compute definitive function attributes for a function taking into account @@ -779,9 +777,8 @@ } /// Deduce returned attributes for the SCC. -static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) { - bool Changed = false; - +static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { // Check each function in turn, determining if an argument is always returned. for (Function *F : SCCNodes) { // We can infer and propagate function attributes only when we know that the @@ -821,11 +818,9 @@ auto *A = cast(RetArg); A->addAttr(Attribute::Returned); ++NumReturned; - Changed = true; + Changed.insert(F); } } - - return Changed; } /// If a callsite has arguments that are also arguments to the parent function, @@ -891,9 +886,8 @@ } /// Deduce nocapture attributes for the SCC. -static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) { - bool Changed = false; - +static void addArgumentAttrs(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { ArgumentGraph AG; // Check each function in turn, determining which pointer arguments are not @@ -905,7 +899,8 @@ if (!F->hasExactDefinition()) continue; - Changed |= addArgumentAttrsFromCallsites(*F); + if (addArgumentAttrsFromCallsites(*F)) + Changed.insert(F); // Functions that are readonly (or readnone) and nounwind and don't return // a value can't capture arguments. Don't analyze them. @@ -916,7 +911,7 @@ if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + Changed.insert(F); } } continue; @@ -935,7 +930,7 @@ // If it's trivially not captured, mark it nocapture now. A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + Changed.insert(F); } else { // If it's not trivially captured and not trivially not captured, // then it must be calling into another function in our SCC. Save @@ -959,7 +954,8 @@ Self.insert(&*A); Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self); if (R != Attribute::None) - Changed = addReadAttr(A, R); + if (addReadAttr(A, R)) + Changed.insert(F); } } } @@ -983,7 +979,7 @@ Argument *A = ArgumentSCC[0]->Definition; A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + Changed.insert(A->getParent()); } continue; } @@ -1025,7 +1021,7 @@ Argument *A = ArgumentSCC[i]->Definition; A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + Changed.insert(A->getParent()); } // We also want to compute readonly/readnone. With a small number of false @@ -1056,12 +1052,11 @@ if (ReadAttr != Attribute::None) { for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { Argument *A = ArgumentSCC[i]->Definition; - Changed = addReadAttr(A, ReadAttr); + if (addReadAttr(A, ReadAttr)) + Changed.insert(A->getParent()); } } } - - return Changed; } /// Tests whether a function is "malloc-like". @@ -1132,7 +1127,8 @@ } /// Deduce noalias attributes for the SCC. -static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) { +static void addNoAliasAttrs(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { // Check each function in turn, determining which functions return noalias // pointers. for (Function *F : SCCNodes) { @@ -1144,7 +1140,7 @@ // definition we'll get at link time is *exactly* the definition we see now. // For more details, see GlobalValue::mayBeDerefined. if (!F->hasExactDefinition()) - return false; + return; // We annotate noalias return values, which are only applicable to // pointer types. @@ -1152,10 +1148,9 @@ continue; if (!isFunctionMallocLike(F, SCCNodes)) - return false; + return; } - bool MadeChange = false; for (Function *F : SCCNodes) { if (F->returnDoesNotAlias() || !F->getReturnType()->isPointerTy()) @@ -1163,10 +1158,8 @@ F->setReturnDoesNotAlias(); ++NumNoAlias; - MadeChange = true; + Changed.insert(F); } - - return MadeChange; } /// Tests whether this function is known to not return null. @@ -1242,13 +1235,12 @@ } /// Deduce nonnull attributes for the SCC. -static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) { +static void addNonNullAttrs(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { // Speculative that all functions in the SCC return only nonnull // pointers. We may refute this as we analyze functions. bool SCCReturnsNonNull = true; - bool MadeChange = false; - // Check each function in turn, determining which functions return nonnull // pointers. for (Function *F : SCCNodes) { @@ -1260,7 +1252,7 @@ // definition we'll get at link time is *exactly* the definition we see now. // For more details, see GlobalValue::mayBeDerefined. if (!F->hasExactDefinition()) - return false; + return; // We annotate nonnull return values, which are only applicable to // pointer types. @@ -1276,7 +1268,7 @@ << " as nonnull\n"); F->addRetAttr(Attribute::NonNull); ++NumNonNullReturn; - MadeChange = true; + Changed.insert(F); } continue; } @@ -1294,11 +1286,9 @@ LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n"); F->addRetAttr(Attribute::NonNull); ++NumNonNullReturn; - MadeChange = true; + Changed.insert(F); } } - - return MadeChange; } namespace { @@ -1351,12 +1341,13 @@ InferenceDescriptors.push_back(AttrInference); } - bool run(const SCCNodeSet &SCCNodes); + void run(const SCCNodeSet &SCCNodes, SmallSetVector &Changed); }; /// Perform all the requested attribute inference actions according to the /// attribute predicates stored before. -bool AttributeInferer::run(const SCCNodeSet &SCCNodes) { +void AttributeInferer::run(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { SmallVector InferInSCC = InferenceDescriptors; // Go through all the functions in SCC and check corresponding attribute // assumptions for each of them. Attributes that are invalid for this SCC @@ -1365,7 +1356,7 @@ // No attributes whose assumptions are still valid - done. if (InferInSCC.empty()) - return false; + return; // Check if our attributes ever need scanning/can be scanned. llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) { @@ -1408,9 +1399,8 @@ } if (InferInSCC.empty()) - return false; + return; - bool Changed = false; for (Function *F : SCCNodes) // At this point InferInSCC contains only functions that were either: // - explicitly skipped from scan/inference, or @@ -1419,10 +1409,9 @@ for (auto &ID : InferInSCC) { if (ID.SkipFunction(*F)) continue; - Changed = true; + Changed.insert(F); ID.SetAttribute(*F); } - return Changed; } struct SCCNodesResult { @@ -1478,7 +1467,8 @@ /// Attempt to remove convergent function attribute when possible. /// /// Returns true if any changes to function attributes were made. -static bool inferConvergent(const SCCNodeSet &SCCNodes) { +static void inferConvergent(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { AttributeInferer AI; // Request to remove the convergent attribute from all functions in the SCC @@ -1501,7 +1491,7 @@ }, /* RequiresExactDefinition= */ false}); // Perform all the requested attribute inference actions. - return AI.run(SCCNodes); + AI.run(SCCNodes, Changed); } /// Infer attributes from all functions in the SCC by scanning every @@ -1510,7 +1500,9 @@ /// - addition of NoUnwind attribute /// /// Returns true if any changes to function attributes were made. -static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) { +static void +inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { AttributeInferer AI; if (!DisableNoUnwindInference) @@ -1559,19 +1551,20 @@ /* RequiresExactDefinition= */ true}); // Perform all the requested attribute inference actions. - return AI.run(SCCNodes); + AI.run(SCCNodes, Changed); } -static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) { +static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { // Try and identify functions that do not recurse. // If the SCC contains multiple nodes we know for sure there is recursion. if (SCCNodes.size() != 1) - return false; + return; Function *F = *SCCNodes.begin(); if (!F || !F->hasExactDefinition() || F->doesNotRecurse()) - return false; + return; // If all of the calls in F are identifiable and are to norecurse functions, F // is norecurse. This check also detects self-recursion as F is not currently @@ -1582,7 +1575,7 @@ Function *Callee = CB->getCalledFunction(); if (!Callee || Callee == F || !Callee->doesNotRecurse()) // Function calls a potentially recursive function. - return false; + return; } // Every call was to a non-recursive function other than this function, and @@ -1590,7 +1583,7 @@ // recurse. F->setDoesNotRecurse(); ++NumNoRecurse; - return true; + Changed.insert(F); } static bool instructionDoesNotReturn(Instruction &I) { @@ -1608,9 +1601,8 @@ } // Set the noreturn function attribute if possible. -static bool addNoReturnAttrs(const SCCNodeSet &SCCNodes) { - bool Changed = false; - +static void addNoReturnAttrs(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { for (Function *F : SCCNodes) { if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Attribute::Naked) || F->doesNotReturn()) @@ -1620,11 +1612,9 @@ // FIXME: this doesn't handle recursion or unreachable blocks. if (none_of(*F, basicBlockCanReturn)) { F->setDoesNotReturn(); - Changed = true; + Changed.insert(F); } } - - return Changed; } static bool functionWillReturn(const Function &F) { @@ -1657,19 +1647,16 @@ } // Set the willreturn function attribute if possible. -static bool addWillReturn(const SCCNodeSet &SCCNodes) { - bool Changed = false; - +static void addWillReturn(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { for (Function *F : SCCNodes) { if (!F || F->willReturn() || !functionWillReturn(*F)) continue; F->setWillReturn(); NumWillReturn++; - Changed = true; + Changed.insert(F); } - - return Changed; } // Return true if this is an atomic which has an ordering stronger than @@ -1728,7 +1715,8 @@ } // Infer the nosync attribute. -static bool addNoSyncAttr(const SCCNodeSet &SCCNodes) { +static void addNoSyncAttr(const SCCNodeSet &SCCNodes, + SmallSetVector &Changed) { AttributeInferer AI; AI.registerAttrInference(AttributeInferer::InferenceDescriptor{ Attribute::NoSync, @@ -1745,7 +1733,7 @@ ++NumNoSync; }, /* RequiresExactDefinition= */ true}); - return AI.run(SCCNodes); + AI.run(SCCNodes, Changed); } static SCCNodesResult createSCCNodeSet(ArrayRef Functions) { @@ -1779,32 +1767,33 @@ } template -static bool deriveAttrsInPostOrder(ArrayRef Functions, - AARGetterT &&AARGetter) { +static SmallSetVector +deriveAttrsInPostOrder(ArrayRef Functions, AARGetterT &&AARGetter) { SCCNodesResult Nodes = createSCCNodeSet(Functions); - bool Changed = false; // Bail if the SCC only contains optnone functions. if (Nodes.SCCNodes.empty()) - return Changed; + return {}; - Changed |= addArgumentReturnedAttrs(Nodes.SCCNodes); - Changed |= addReadAttrs(Nodes.SCCNodes, AARGetter); - Changed |= addArgumentAttrs(Nodes.SCCNodes); - Changed |= inferConvergent(Nodes.SCCNodes); - Changed |= addNoReturnAttrs(Nodes.SCCNodes); - Changed |= addWillReturn(Nodes.SCCNodes); + SmallSetVector Changed; + + addArgumentReturnedAttrs(Nodes.SCCNodes, Changed); + addReadAttrs(Nodes.SCCNodes, AARGetter, Changed); + addArgumentAttrs(Nodes.SCCNodes, Changed); + inferConvergent(Nodes.SCCNodes, Changed); + addNoReturnAttrs(Nodes.SCCNodes, Changed); + addWillReturn(Nodes.SCCNodes, Changed); // If we have no external nodes participating in the SCC, we can deduce some // more precise attributes as well. if (!Nodes.HasUnknownCall) { - Changed |= addNoAliasAttrs(Nodes.SCCNodes); - Changed |= addNonNullAttrs(Nodes.SCCNodes); - Changed |= inferAttrsFromFunctionBodies(Nodes.SCCNodes); - Changed |= addNoRecurseAttrs(Nodes.SCCNodes); + addNoAliasAttrs(Nodes.SCCNodes, Changed); + addNonNullAttrs(Nodes.SCCNodes, Changed); + inferAttrsFromFunctionBodies(Nodes.SCCNodes, Changed); + addNoRecurseAttrs(Nodes.SCCNodes, Changed); } - Changed |= addNoSyncAttr(Nodes.SCCNodes); + addNoSyncAttr(Nodes.SCCNodes, Changed); // Finally, infer the maximal set of attributes from the ones we've inferred // above. This is handling the cases where one attribute on a signature @@ -1812,7 +1801,8 @@ // the later is missing (or simply less sophisticated). for (Function *F : Nodes.SCCNodes) if (F) - Changed |= inferAttributesFromOthers(*F); + if (inferAttributesFromOthers(*F)) + Changed.insert(F); return Changed; } @@ -1835,14 +1825,24 @@ Functions.push_back(&N.getFunction()); } - if (deriveAttrsInPostOrder(Functions, AARGetter)) { - // We have not changed the call graph or removed/added functions. - PreservedAnalyses PA; - PA.preserve(); - return PA; + auto ChangedFunctions = deriveAttrsInPostOrder(Functions, AARGetter); + if (ChangedFunctions.empty()) { + return PreservedAnalyses::all(); } - return PreservedAnalyses::all(); + // Invalidate analyses for modified functions so that we don't have to + // invalidate all analyses for all functions in this SCC. + PreservedAnalyses FuncPA; + // We haven't changed the CFG for modified functions. + FuncPA.preserveSet(); + for (Function *Changed : ChangedFunctions) + FAM.invalidate(*Changed, FuncPA); + + // We have not changed the call graph or removed/added functions. + PreservedAnalyses PA; + PA.preserve(); + PA.preserveSet>(); + return PA; } namespace { @@ -1887,7 +1887,7 @@ Functions.push_back(I->getFunction()); } - return deriveAttrsInPostOrder(Functions, AARGetter); + return !deriveAttrsInPostOrder(Functions, AARGetter).empty(); } bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) { diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp --- a/llvm/lib/Transforms/IPO/Inliner.cpp +++ b/llvm/lib/Transforms/IPO/Inliner.cpp @@ -1011,6 +1011,10 @@ UR.InlinedInternalEdges.insert({&N, OldC}); } InlinedCallees.clear(); + + // Invalidate analyses for this function now so that we don't have to + // invalidate analyses for all functions in this SCC later. + FAM.invalidate(F, PreservedAnalyses::none()); } // Now that we've finished inlining all of the calls across this SCC, delete @@ -1054,10 +1058,12 @@ if (!Changed) return PreservedAnalyses::all(); + PreservedAnalyses PA; // 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(); + // We have already invalidated all analyses on modified functions. + PA.preserveSet>(); return PA; } diff --git a/llvm/test/Transforms/Inline/analysis-invalidation.ll b/llvm/test/Transforms/Inline/analysis-invalidation.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/Inline/analysis-invalidation.ll @@ -0,0 +1,17 @@ +; RUN: opt -passes=inline < %s -disable-output -debug-pass-manager 2>&1 | FileCheck %s + +; We shouldn't invalidate any function analyses on g since it's never modified. + +; CHECK-NOT: Invalidating{{.*}} on g +; CHECK: Invalidating{{.*}} on f +; CHECK-NOT: Invalidating{{.*}} on g + +define void @f() noinline { + call void @g() + ret void +} + +define void @g() alwaysinline { + call void @f() + ret void +} diff --git a/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll b/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll --- a/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll +++ b/llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll @@ -8,11 +8,11 @@ ; ; CHECK: Running pass: InlinerPass on (test1_f, test1_g, test1_h) ; CHECK: Running analysis: DominatorTreeAnalysis on test1_f -; CHECK: Running analysis: DominatorTreeAnalysis on test1_g ; 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: Running analysis: DominatorTreeAnalysis on test1_g ; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_g ; CHECK: Invalidating analysis: LoopAnalysis on test1_g ; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_g @@ -29,7 +29,6 @@ ; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on test1_h ; 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()