[NewPM] Only invalidate modified functions' analyses in CGSCC passes

[aeubanks]

Summary

Previously, any change in any function in an SCC would cause all
analyses for all functions in the SCC to be invalidated. With this
change, we now manually invalidate analyses for functions we modify,
then let the pass manager know that all function analyses should be
preserved.

So far this only touches the inliner, argpromotion, funcattrs, and
updateCGAndAnalysisManager(), since they are the most used.

Slight compile time improvements:
http://llvm-compile-time-tracker.com/compare.php?from=326da4adcb8def2abdd530299d87ce951c0edec9&to=8942c7669f330082ef159f3c6c57c3c28484f4be&stat=instructions

[aeubanks]

I'm happy to split this up, I'd just like to know if this is reasonable.

check-llvm with expensive checks passes.

[mtrofin]

lgtm

[ychen]

I think we should be careful about letting passes invalidate analyses directly. IIUC the only interface for propagating invalidation from passes is PreservedAnalyses. Is there any way to enhance PreservedAnalyses to achieve the same effect?

[aeubanks]

It seems awkward to enhance PreservedAnalyses to only apply to specific functions when this patch is explicitly doing exactly what we want. If you have a clean way of modeling this inside PreservedAnalyses I'm happy to go with that, but so far I think this is the cleanest way.
Passes were already directly managing the analysis managers, e.g. the inliner and argpromo would remove entries for deleted functions. And updateCGAndAnalysisManager() would also handle analysis manager updates.

[ychen]

It seems awkward to enhance PreservedAnalyses to only apply to specific functions when this patch is explicitly doing exactly what we want. If you have a clean way of modeling this inside PreservedAnalyses I'm happy to go with that, but so far I think this is the cleanest way.

I was thinking something like PreservedAnalyses::abandon(IRUnit, AnalysisID) which only used to selectively invalidate inner IR units, but I've convinced myself that it may not worth it. Invalidating inner analyses through proxy should work well already.

Passes were already directly managing the analysis managers, e.g. the inliner and argpromo would remove entries for deleted functions. And updateCGAndAnalysisManager() would also handle analysis manager updates.

I would argue that updateCGAndAnalysisManager() is kinda special (for coping with the CGSCCPM's complexity). I think the one in argpromo is not necessary since it already returns PreservedAnalyses::none(). inliner yes.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1631

Is the function CFG preserved?

[aeubanks]

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1631

Yes, will update.
Doing this causes globalaa-retained.ll to fail, which I believe is fixed by https://reviews.llvm.org/D101017

[aeubanks]

add test
use CFGAnalyses
uncovered another place in updateCGAndAnalysisManager() to change

depends on D101017

[aeubanks]

rebase

[nikic]

An unfortunate side-effect of this change is that NewPM uses even more memory. tramp3d-v4 is up 20% in max-rss (https://llvm-compile-time-tracker.com/compare.php?from=4ef1f90e4d564b872e3598ccef45adb740eb0f0d&to=d14d84af2f5ebb8ae2188ce6884a29a586dc0a40&stat=max-rss)

[aeubanks]

In D100917#2735651, @nikic wrote:

An unfortunate side-effect of this change is that NewPM uses even more memory. tramp3d-v4 is up 20% in max-rss (https://llvm-compile-time-tracker.com/compare.php?from=4ef1f90e4d564b872e3598ccef45adb740eb0f0d&to=d14d84af2f5ebb8ae2188ce6884a29a586dc0a40&stat=max-rss)

Hmm that is a concern. I'm not sure how we want to balance memory vs compile times. Any thoughts?

[mtrofin]

In D100917#2736702, @aeubanks wrote:

In D100917#2735651, @nikic wrote:

An unfortunate side-effect of this change is that NewPM uses even more memory. tramp3d-v4 is up 20% in max-rss (https://llvm-compile-time-tracker.com/compare.php?from=4ef1f90e4d564b872e3598ccef45adb740eb0f0d&to=d14d84af2f5ebb8ae2188ce6884a29a586dc0a40&stat=max-rss)

Hmm that is a concern. I'm not sure how we want to balance memory vs compile times. Any thoughts?

(Drive-by thought) - maybe this is because a bunch of analyses that are needed during function simplification aren't needed anymore after. We could quickly check by adding a pass at the end of all function simplification, module-wide, that clears all fct analyses, and see if the memory overhead is still there?

If that's the case, we could identify what's not needed after function simplification and scope it somehow in a less hacky way than my above suggestion.

[aeubanks]

Using valgrind's massif, I profiled using clang build build PassBuilder.cpp (it's one of the longest LLVM files to compile), and at peak memory usage:

without patch: 42.5% Clang AST, 11.6% misc, 5.6% BlockFrequencyInfo, 3.3% DomTree, 1.4% LazyCallGraph, 1.2% MemorySSA
with patch: 37.6% Clang AST, 12.7% misc, 4.9% BlockFrequencyInfo, 3.4% MemorySSA, 3.2% DomTree, 1.7% BlockProbabilityInfo (again), 1.2% LazyCallGraph
misc means anything below 0.3%
(I'm ignoring some LLVM non-analysis and Clang stuff)
assuming that the Clang AST is mostly constant between the two, it does look like my patch (https://reviews.llvm.org/D100917) does slightly increase memory usage, at least just for some random file (PassBuilder.cpp), and some files are likely to be much worse due to more SCCs. and there's no obvious large analysis to clear out

I'll look to see if we really need the Clang AST while running passes, although I'm not hopeful there

[aeubanks]

I rebased this and there are still major memory regressions for tramp3d-v4: https://llvm-compile-time-tracker.com/compare.php?from=f63405f6e3d30f33e715ef5ad09136127535a3fb&to=ae5555c1375e4afe90727f1c30dae1659d11a20d&stat=max-rss
Perhaps we can't land this in its current form. Will need to rethink an alternative to push ahead with D98103

llvm/lib/Transforms/IPO/ArgumentPromotion.cpp

PreservedAnalyses ArgumentPromotionPass::run(LazyCallGraph::SCC &C,
                                              LazyCallGraph &CG,
                                              CGSCCUpdateResult &UR) {
   bool Changed = false, LocalChange;
 
   // Iterate until we stop promoting from this SCC.
   do {
     LocalChange = false;
 
+    FunctionAnalysisManager &FAM =
+        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
+
     for (LazyCallGraph::Node &N : C) {
       Function &OldF = N.getFunction();
 
-      FunctionAnalysisManager &FAM =
-          AM.getResult<FunctionAnalysisManagerCGSCCProxy>(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 & {
         assert(&F == &OldF && "Called with an unexpected function!");
         return FAM.getResult<AAManager>(F);
       };
 
       const TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(OldF);
       Function *NewF =
           promoteArguments(&OldF, AARGetter, MaxElements, None, TTI);
       if (!NewF)
         continue;
       LocalChange = true;
 
       // Directly substitute the functions in the call graph. Note that this
       // requires the old function to be completely dead and completely
       // replaced by the new function. It does no call graph updates, it merely
       // swaps out the particular function mapped to a particular node in the
       // graph.
       C.getOuterRefSCC().replaceNodeFunction(N, *NewF);
       FAM.clear(OldF, OldF.getName());
       OldF.eraseFromParent();
+
+      for (auto *U : NewF->users()) {
+        auto *UserF = cast<CallBase>(U)->getParent()->getParent();
+        FAM.invalidate(*UserF, PreservedAnalyses::none());
+      }
     }
 
     Changed |= LocalChange;
   } while (LocalChange);
 
   if (!Changed)
     return PreservedAnalyses::all();
 
-  return PreservedAnalyses::none();
+  PreservedAnalyses PA;
+  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+  PA.preserveSet<AllAnalysesOn<Function>>();
+  return PA;
 }
 
 namespace {
 
 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
 struct ArgPromotion : public CallGraphSCCPass {
   // Pass identification, replacement for typeid
   static char ID;

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

 
 MemoryAccessKind llvm::computeFunctionBodyMemoryAccess(Function &F,
                                                        AAResults &AAR) {
   return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
 }
 
 /// Deduce readonly/readnone attributes for the SCC.
 template <typename AARGetterT>
-static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
+static void addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
+                         SmallSetVector<Function *, 8> &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;
   bool WritesMemory = false;
   for (Function *F : SCCNodes) {
     // Call the callable parameter to look up AA results for this function.
     AAResults &AAR = AARGetter(*F);
 
     // Non-exact function definitions may not be selected at link time, and an
     // alternative version that writes to memory may be selected.  See the
     // comment on GlobalValue::isDefinitionExact for more details.
     switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(),
                                       AAR, SCCNodes)) {
     case MAK_MayWrite:
-      return false;
+      return;
     case MAK_ReadOnly:
       ReadsMemory = true;
       break;
     case MAK_WriteOnly:
       WritesMemory = true;
       break;
     case MAK_ReadNone:
       // Nothing to do!
       break;
     }
   }
 
   // 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())
       // Already perfect!
       continue;
 
     if (F->onlyReadsMemory() && ReadsMemory)
       // No change.
       continue;
 
     if (F->doesNotReadMemory() && WritesMemory)
       continue;
 
-    MadeChange = true;
+    Changed.insert(F);
 
     // Clear out any existing attributes.
     AttrBuilder AttrsToRemove;
     AttrsToRemove.addAttribute(Attribute::ReadOnly);
     AttrsToRemove.addAttribute(Attribute::ReadNone);
     AttrsToRemove.addAttribute(Attribute::WriteOnly);
 
     if (!WritesMemory && !ReadsMemory) {
for (Function *F : SCCNodes) {
 
     if (WritesMemory && !ReadsMemory)
       ++NumWriteOnly;
     else if (ReadsMemory)
       ++NumReadOnly;
     else
       ++NumReadNone;
   }
-
-  return MadeChange;
 }
 
 namespace {
 
 /// For a given pointer Argument, this retains a list of Arguments of functions
 /// in the same SCC that the pointer data flows into. We use this to build an
 /// SCC of the arguments.
 struct ArgumentGraphNode {
default:
       return Attribute::None;
     }
   }
 
   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 }
 
 /// Deduce returned attributes for the SCC.
-static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
-  bool Changed = false;
-
+static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes,
+                                     SmallSetVector<Function *, 8> &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
     // definition we'll get at link time is *exactly* the definition we see now.
     // For more details, see GlobalValue::mayBeDerefined.
     if (!F->hasExactDefinition())
       continue;
 
auto FindRetArg = [&]() -> Value * {
 
       return RetArg;
     };
 
     if (Value *RetArg = FindRetArg()) {
       auto *A = cast<Argument>(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,
 /// try to propagate attributes from the callsite's arguments to the parent's
 /// arguments. This may be important because inlining can cause information loss
 /// when attribute knowledge disappears with the inlined call.
 static bool addArgumentAttrsFromCallsites(Function &F) {
   if (!EnableNonnullArgPropagation)
static bool addReadAttr(Argument *A, Attribute::AttrKind R) {
   A->removeAttr(Attribute::ReadOnly);
   A->removeAttr(Attribute::ReadNone);
   A->addAttr(R);
   R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
   return true;
 }
 
 /// Deduce nocapture attributes for the SCC.
-static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
-  bool Changed = false;
-
+static void addArgumentAttrs(const SCCNodeSet &SCCNodes,
+                             SmallSetVector<Function *, 8> &Changed) {
   ArgumentGraph AG;
 
   // Check each function in turn, determining which pointer arguments are not
   // captured.
   for (Function *F : SCCNodes) {
     // We can infer and propagate function attributes only when we know that the
     // definition we'll get at link time is *exactly* the definition we see now.
     // For more details, see GlobalValue::mayBeDerefined.
     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.
     if (F->onlyReadsMemory() && F->doesNotThrow() &&
         F->getReturnType()->isVoidTy()) {
       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
            ++A) {
         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
           A->addAttr(Attribute::NoCapture);
           ++NumNoCapture;
-          Changed = true;
+          Changed.insert(F);
         }
       }
       continue;
     }
 
     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
          ++A) {
       if (!A->getType()->isPointerTy())
         continue;
       bool HasNonLocalUses = false;
       if (!A->hasNoCaptureAttr()) {
         ArgumentUsesTracker Tracker(SCCNodes);
         PointerMayBeCaptured(&*A, &Tracker);
         if (!Tracker.Captured) {
           if (Tracker.Uses.empty()) {
             // 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
             // its particulars for Argument-SCC analysis later.
             ArgumentGraphNode *Node = AG[&*A];
             for (Argument *Use : Tracker.Uses) {
               Node->Uses.push_back(AG[Use]);
               if (Use != &*A)
                 HasNonLocalUses = true;
             }
           }
         }
         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
       }
       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
         // Can we determine that it's readonly/readnone without doing an SCC?
         // Note that we don't allow any calls at all here, or else our result
         // will be dependent on the iteration order through the functions in the
         // SCC.
         SmallPtrSet<Argument *, 8> Self;
         Self.insert(&*A);
         Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
         if (R != Attribute::None)
-          Changed = addReadAttr(A, R);
+          if (addReadAttr(A, R))
+            Changed.insert(F);
       }
     }
   }
 
   // The graph we've collected is partial because we stopped scanning for
   // argument uses once we solved the argument trivially. These partial nodes
   // show up as ArgumentGraphNode objects with an empty Uses list, and for
   // these nodes the final decision about whether they capture has already been
   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
   // captures.
 
   for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
     if (ArgumentSCC.size() == 1) {
       if (!ArgumentSCC[0]->Definition)
         continue; // synthetic root node
 
       // eg. "void f(int* x) { if (...) f(x); }"
       if (ArgumentSCC[0]->Uses.size() == 1 &&
           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
         Argument *A = ArgumentSCC[0]->Definition;
         A->addAttr(Attribute::NoCapture);
         ++NumNoCapture;
-        Changed = true;
+        Changed.insert(A->getParent());
       }
       continue;
     }
 
     bool SCCCaptured = false;
     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
          I != E && !SCCCaptured; ++I) {
       ArgumentGraphNode *Node = *I;
for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
     }
     if (SCCCaptured)
       continue;
 
     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
       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
     // negatives, we can assume that any pointer which is captured isn't going
     // to be provably readonly or readnone, since by definition we can't
     // analyze all uses of a captured pointer.
     //
     // The false negatives happen when the pointer is captured by a function
for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
       }
       ReadAttr = K;
       break;
     }
 
     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".
 ///
 /// A function is "malloc-like" if it returns either null or a pointer that
 /// doesn't alias any other pointer visible to the caller.
 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
   SmallSetVector<Value *, 8> FlowsToReturn;
for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
       return false;
   }
 
   return true;
 }
 
 /// Deduce noalias attributes for the SCC.
-static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
+static void addNoAliasAttrs(const SCCNodeSet &SCCNodes,
+                            SmallSetVector<Function *, 8> &Changed) {
   // Check each function in turn, determining which functions return noalias
   // pointers.
   for (Function *F : SCCNodes) {
     // Already noalias.
     if (F->returnDoesNotAlias())
       continue;
 
     // We can infer and propagate function attributes only when we know that the
     // 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.
     if (!F->getReturnType()->isPointerTy())
       continue;
 
     if (!isFunctionMallocLike(F, SCCNodes))
-      return false;
+      return;
   }
 
-  bool MadeChange = false;
   for (Function *F : SCCNodes) {
     if (F->returnDoesNotAlias() ||
         !F->getReturnType()->isPointerTy())
       continue;
 
     F->setReturnDoesNotAlias();
     ++NumNoAlias;
-    MadeChange = true;
+    Changed.insert(F);
   }
-
-  return MadeChange;
 }
 
 /// Tests whether this function is known to not return null.
 ///
 /// Requires that the function returns a pointer.
 ///
 /// Returns true if it believes the function will not return a null, and sets
 /// \p Speculative based on whether the returned conclusion is a speculative
for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
     };
     llvm_unreachable("should have either continued or returned");
   }
 
   return true;
 }
 
 /// Deduce nonnull attributes for the SCC.
-static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
+static void addNonNullAttrs(const SCCNodeSet &SCCNodes,
+                            SmallSetVector<Function *, 8> &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) {
     // Already nonnull.
     if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
                                         Attribute::NonNull))
       continue;
 
     // We can infer and propagate function attributes only when we know that the
     // 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.
     if (!F->getReturnType()->isPointerTy())
       continue;
 
     bool Speculative = false;
     if (isReturnNonNull(F, SCCNodes, Speculative)) {
       if (!Speculative) {
         // Mark the function eagerly since we may discover a function
         // which prevents us from speculating about the entire SCC
         LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
                           << " as nonnull\n");
         F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
         ++NumNonNullReturn;
-        MadeChange = true;
+        Changed.insert(F);
       }
       continue;
     }
     // At least one function returns something which could be null, can't
     // speculate any more.
     SCCReturnsNonNull = false;
   }
 
   if (SCCReturnsNonNull) {
     for (Function *F : SCCNodes) {
       if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
                                           Attribute::NonNull) ||
           !F->getReturnType()->isPointerTy())
         continue;
 
       LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
       F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
       ++NumNonNullReturn;
-      MadeChange = true;
+      Changed.insert(F);
     }
   }
-
-  return MadeChange;
 }
 
 namespace {
 
 /// Collects a set of attribute inference requests and performs them all in one
 /// go on a single SCC Node. Inference involves scanning function bodies
 /// looking for instructions that violate attribute assumptions.
 /// As soon as all the bodies are fine we are free to set the attribute.

 private:
   SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
 
 public:
   void registerAttrInference(InferenceDescriptor AttrInference) {
     InferenceDescriptors.push_back(AttrInference);
   }
 
-  bool run(const SCCNodeSet &SCCNodes);
+  void run(const SCCNodeSet &SCCNodes, SmallSetVector<Function *, 8> &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<Function *, 8> &Changed) {
   SmallVector<InferenceDescriptor, 4> 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
   // will be removed from InferInSCC.
   for (Function *F : SCCNodes) {
 
     // 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) {
       if (ID.SkipFunction(*F))
         return false;
 
       // Remove from further inference (invalidate) when visiting a function
       // that has no instructions to scan/has an unsuitable definition.
for (Instruction &I : instructions(*F)) {
       });
 
       if (InferInThisFunc.empty())
         break;
     }
   }
 
   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
     //   - verified to have no instructions that break attribute assumptions.
     // Hence we just go and force the attribute for all non-skipped functions.
     for (auto &ID : InferInSCC) {
       if (ID.SkipFunction(*F))
         continue;
-      Changed = true;
+      Changed.insert(F);
       ID.SetAttribute(*F);
     }
-  return Changed;
 }
 
 struct SCCNodesResult {
   SCCNodeSet SCCNodes;
   bool HasUnknownCall;
 };
 
 } // end anonymous namespace
if (SCCNodes.contains(Callee))
       return false;
 
   return true;
 }
 
 /// 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<Function *, 8> &Changed) {
   AttributeInferer AI;
 
   // Request to remove the convergent attribute from all functions in the SCC
   // if every callsite within the SCC is not convergent (except for calls
   // to functions within the SCC).
   // Note: Removal of the attr from the callsites will happen in
   // InstCombineCalls separately.
   AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
       Attribute::Convergent,
       // Skip non-convergent functions.
       [](const Function &F) { return !F.isConvergent(); },
       // Instructions that break non-convergent assumption.
       [SCCNodes](Instruction &I) {
         return InstrBreaksNonConvergent(I, SCCNodes);
       },
       [](Function &F) {
         LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
                           << "\n");
         F.setNotConvergent();
       },
       /* 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
 /// instruction for compliance to the attribute assumptions. Currently it
 /// does:
 ///   - 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<Function *, 8> &Changed) {
   AttributeInferer AI;
 
   if (!DisableNoUnwindInference)
     // Request to infer nounwind attribute for all the functions in the SCC if
     // every callsite within the SCC is not throwing (except for calls to
     // functions within the SCC). Note that nounwind attribute suffers from
     // derefinement - results may change depending on how functions are
     // optimized. Thus it can be inferred only from exact definitions.
AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
           LLVM_DEBUG(dbgs()
                      << "Adding nofree attr to fn " << F.getName() << "\n");
           F.setDoesNotFreeMemory();
           ++NumNoFree;
         },
         /* 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<Function *, 8> &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
   // marked norecurse, so any called from F to F will not be marked norecurse.
   for (auto &BB : *F)
     for (auto &I : BB.instructionsWithoutDebug())
       if (auto *CB = dyn_cast<CallBase>(&I)) {
         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
   // we have no indirect recursion as the SCC size is one. This function cannot
   // recurse.
   F->setDoesNotRecurse();
   ++NumNoRecurse;
-  return true;
+  Changed.insert(F);
 }
 
 static bool instructionDoesNotReturn(Instruction &I) {
   if (auto *CB = dyn_cast<CallBase>(&I))
     return CB->hasFnAttr(Attribute::NoReturn);
   return false;
 }
 
 // A basic block can only return if it terminates with a ReturnInst and does not
 // contain calls to noreturn functions.
 static bool basicBlockCanReturn(BasicBlock &BB) {
   if (!isa<ReturnInst>(BB.getTerminator()))
     return false;
   return none_of(BB, instructionDoesNotReturn);
 }
 
 // Set the noreturn function attribute if possible.
-static bool addNoReturnAttrs(const SCCNodeSet &SCCNodes) {
-  bool Changed = false;
-
+static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
+                             SmallSetVector<Function *, 8> &Changed) {
   for (Function *F : SCCNodes) {
     if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Attribute::Naked) ||
         F->doesNotReturn())
       continue;
 
     // The function can return if any basic blocks can return.
     // 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) {
   // Must-progress function without side-effects must return.
   if (F.mustProgress() && F.onlyReadsMemory())
     return true;
 
   // Can only analyze functions with a definition.
static bool functionWillReturn(const Function &F) {
   // If there are no loops, then the function is willreturn if all calls in
   // it are willreturn.
   return all_of(instructions(F), [](const Instruction &I) {
     return I.willReturn();
   });
 }
 
 // Set the willreturn function attribute if possible.
-static bool addWillReturn(const SCCNodeSet &SCCNodes) {
-  bool Changed = false;
-
+static void addWillReturn(const SCCNodeSet &SCCNodes,
+                          SmallSetVector<Function *, 8> &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
 // unordered.  Note that this is different than the predicate we use in
 // Attributor.  Here we chose to be conservative and consider monotonic
 // operations potentially synchronizing.  We generally don't do much with
 // monotonic operations, so this is simply risk reduction.
 static bool isOrderedAtomic(Instruction *I) {
static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) {
   if (Function *Callee = CB->getCalledFunction())
     if (SCCNodes.contains(Callee))
       return false;
 
   return true;
 }
 
 // Infer the nosync attribute.
-static bool addNoSyncAttr(const SCCNodeSet &SCCNodes) {
+static void addNoSyncAttr(const SCCNodeSet &SCCNodes,
+                          SmallSetVector<Function *, 8> &Changed) {
   AttributeInferer AI;
   AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
       Attribute::NoSync,
       // Skip already marked functions.
       [](const Function &F) { return F.hasNoSync(); },
       // Instructions that break nosync assumption.
       [&SCCNodes](Instruction &I) {
         return InstrBreaksNoSync(I, SCCNodes);
       },
       [](Function &F) {
         LLVM_DEBUG(dbgs()
                    << "Adding nosync attr to fn " << F.getName() << "\n");
         F.setNoSync();
         ++NumNoSync;
       },
       /* RequiresExactDefinition= */ true});
-  return AI.run(SCCNodes);
+  AI.run(SCCNodes, Changed);
 }
 
 static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
   SCCNodesResult Res;
   Res.HasUnknownCall = false;
   for (Function *F : Functions) {
     if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {
       // Treat any function we're trying not to optimize as if it were an
if (!Res.HasUnknownCall) {
       }
     }
     Res.SCCNodes.insert(F);
   }
   return Res;
 }
 
 template <typename AARGetterT>
-static bool deriveAttrsInPostOrder(ArrayRef<Function *> Functions,
-                                   AARGetterT &&AARGetter) {
+static SmallSetVector<Function *, 8>
+deriveAttrsInPostOrder(ArrayRef<Function *> 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 {};
+
+  SmallSetVector<Function *, 8> Changed;
 
-  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);
+  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
   // implies another, but for implementation reasons the inference rule for
   // 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;
 }
 
 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
                                                   CGSCCAnalysisManager &AM,
                                                   LazyCallGraph &CG,
                                                   CGSCCUpdateResult &) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 
   // We pass a lambda into functions to wire them up to the analysis manager
   // for getting function analyses.
   auto AARGetter = [&](Function &F) -> AAResults & {
     return FAM.getResult<AAManager>(F);
   };
 
   SmallVector<Function *, 8> Functions;
   for (LazyCallGraph::Node &N : C) {
     Functions.push_back(&N.getFunction());
   }
 
-  if (deriveAttrsInPostOrder(Functions, AARGetter)) {
-    // We have not changed the call graph or removed/added functions.
-    PreservedAnalyses PA;
-    PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
-    return PA;
-  }
+  auto ChangedFunctions = deriveAttrsInPostOrder(Functions, AARGetter);
+  if (ChangedFunctions.empty()) {
+    return PreservedAnalyses::all();
+  }
+
+  for (Function *Changed : ChangedFunctions)
+    FAM.invalidate(*Changed, PreservedAnalyses::none());
+  PA.preserveSet<AllAnalysesOn<Function>>();
 
-  return PreservedAnalyses::all();
-}
-
 namespace {
 
 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
   // Pass identification, replacement for typeid
   static char ID;
 
   PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
     initializePostOrderFunctionAttrsLegacyPassPass(

 
 template <typename AARGetterT>
 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
   SmallVector<Function *, 8> Functions;
   for (CallGraphNode *I : SCC) {
     Functions.push_back(I->getFunction());
   }
 
-  return deriveAttrsInPostOrder(Functions, AARGetter);
+  return !deriveAttrsInPostOrder(Functions, AARGetter).empty();
 }
 
 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
   if (skipSCC(SCC))
     return false;
   return runImpl(SCC, LegacyAARGetter(*this));
 }
 

llvm/lib/Transforms/IPO/Inliner.cpp

if ((C != OldC || UR.CWorklist.count(OldC)) &&
         llvm::any_of(InlinedCallees, [&](Function *Callee) {
           return CG.lookupSCC(*CG.lookup(*Callee)) == OldC;
         })) {
       LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, "
                            "retaining this to avoid infinite inlining.\n");
       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
   // all of the trivially dead functions, updating the call graph and the CGSCC
   // pass manager in the process.
   //
   // Note that this walks a pointer set which has non-deterministic order but
   // that is OK as all we do is delete things and add pointers to unordered
for (Function *DeadF : DeadFunctions) {
     M.getFunctionList().remove(DeadF);
 
     ++NumDeleted;
   }
 
   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<FunctionAnalysisManagerCGSCCProxy>();
+  // We have already invalidated all analyses on modified functions.
+  PA.preserveSet<AllAnalysesOn<Function>>();
   return PA;
 }
 
 ModuleInlinerWrapperPass::ModuleInlinerWrapperPass(InlineParams Params,
                                                    bool Debugging,
                                                    bool MandatoryFirst,
                                                    InliningAdvisorMode Mode,
                                                    unsigned MaxDevirtIterations)