[PM] Support invalidation of inner analysis managers from a pass over the outer IR unit.

[chandlerc]

Summary

This never really got implemented, and was very hard to test before
a lot of the refactoring changes to make things more robust. But now we
can test it thoroughly and cleanly, especially at the CGSCC level.

The core idea is that when an inner analysis manager proxy receives the
invalidation event for the outer IR unit, it needs to walk the inner IR
units and propagate it to the inner analysis manager for each of those
units. For example, each function in the SCC needs to get an
invalidation event when the SCC gets one.

The function / module interaction is somewhat boring here. This really
becomes interesting in the face of analysis-backed IR units. This patch
effectively handles all of the CGSCC layer's needs -- both invalidating
SCC analysis and invalidating function analysis when an SCC gets
invalidated.

However, this second aspect doesn't really handle the
LoopAnalysisManager well at this point. That one will need some change
of design in order to fully integrate, because unlike the call graph,
the entire function behind a LoopAnalysis's results can vanish out from
under us, and we won't even have a cached API to access. I'd like to try
to separate solving the loop problems into a subsequent patch though in
order to keep this more focused so I've adapted them to the API and
updated the tests that immediately fail, but I've not added the level of
testing and validation at that layer that I have at the CGSCC layer.

An important aspect of this change is that the proxy for the
FunctionAnalysisManager at the SCC pass layer doesn't work like the
other proxies for an inner IR unit as it doesn't directly manage the
FunctionAnalysisManager and invalidation or clearing of it. This would
create an ever worsening problem of dual ownership of this
responsibility, split between the module-level FAM proxy and this
SCC-level FAM proxy. Instead, this patch changes the SCC-level FAM proxy
to work in terms of the module-level proxy and defer to it to handle
much of the updates. It only does SCC-specific invalidation. This will
become more important in subsequent patches that support more complex
invalidaiton scenarios.

[silvas]

nice to see this feature finally implemented!

[jlebar]

include/llvm/Analysis/CGSCCPassManager.h

168

Perhaps we could be more concrete:

If the proxy analysis itself is preserved, then we assume that the set of SCCs in the Module hasn't changed. Thus any pointers to SCCs in the CGSCCAnalysisManager are still valid, and we don't need to call \c clear on the CGSCCAnalysisManager.

173

What's an "inner set"? (Maybe this whole parenthetical can go.)

179

I don't understand this last sentence. This is already a template specialization, so "this template" is...the template we're specializing? Does each specialization of InnerAnalysisManagerProxy::Result::invalidate need to specialize as described here?

189

garph

447

Suggest rephrasing "does not mirror the proxy" -- it's hard to understand what you mean.

Perhaps just remove this para.

456

Starting from "Instead" is very hard to parse. Perhaps something like:

Instead, this layer is only responsible for SCC-local invalidation events. We work with the module's FunctionAnalysisManager to invalidate function analyses.

include/llvm/IR/PassManager.h

770

FWIW I don't think that "containing IR unit" is particularly helpful.

In my patch that rewrites these comments, I changed it to talk about the "larger" and "smaller" IR units:

/// \brief An analysis over a "larger" IR unit that provides access to an analysis manager over a "smaller" IR unit.
class InnerAnalysisManagerProxy {
  [...]
  /// \brief Handler for invalidation of the "larger" IR unit, \c IRUnitT.
  bool invalidate(...) {}
}

But we can go over this separately.

786

This comment makes sense -- maybe we simply don't need the one I commented on earlier that didn't make sense.

lib/Analysis/CGSCCPassManager.cpp

94

Comma before "and".

97

"if it's unavailable"

105

"when it's created", although maybe it's good enough to say "we can observe the new call graph."

110

comma before "so".

111

Do we in fact do this if the call graph is about to become invalid? The comment on the first if statement in this functions ays we go into the if if "the call graph is going to be invalidated". Maybe this whole comment is stale?

121

Suggest s/Otherwise/Return/ because the thing we're contrasting against is somewhat far away.

147

Would it be correct to rephrase this to say

rely on the FAMMP to invalidate the function analyses.

? If so, maybe we can say that? If not, I do not understand what this is trying to say.

155

s/hard-code/special-case/?

171

Suggest

entire SCC layer, which includes this proxy, is cleared.

lib/Analysis/LoopPassManager.cpp

33

• s/, there/, as there/
• s/making/, making/

But maybe even better would be to rephrase a bit:

If this proxy isn't marked as preserved, the set of Function objects in the module may have changed. We therefore can't call InnerAM->invalidate(), because any pointers to Functions it has may be stale. Instead, we call clear().

unittests/Analysis/CGSCCPassManagerTest.cpp

127

Any reason not to take an std::function as the argument?

129

Not anymore!

555

Any reason not to write these as independent TESTs? As-is I have to read carefully to see that you reset the SCCAnalysisRuns counter between tests, and it's not obvious whether you're (intentionally or unintentionally) carrying any additional state between the various blocks.

636

s/&/and/ because don't we already have enough meanings for "&" in C++? :)

645

Raw string?

[chandlerc]

Rebase and address code review comments.

[chandlerc]

Updated with fixes to hopefully everything (please let me know if I missed something). Responses in a few cases below.

include/llvm/Analysis/CGSCCPassManager.h

179

Sorry, I just kept a bunch of pointless documentation from the original template. Nuked this.

include/llvm/IR/PassManager.h

770

Sure, happy to try different sets of terminology and see what works best.

I can see why "containing" would be problematic. The code itself currently uses "inner" and "outer" which at least seem somewhat better and I've made the comments match that for now.

lib/Analysis/CGSCCPassManager.cpp

111

This comment is indeed stale.

unittests/Analysis/CGSCCPassManagerTest.cpp

127

It seems more idiomatic. In other, more interesting cases it can actually matter because we run out of implicit conversions. It also avoids spelling out the function type twice.

645

Would it be an improvement? I'm not sure...

Anyways, should be a separate patch and applied to all the textual modules here if we can rely on this feature and it is worth using.

[jlebar]

I am happy.

unittests/Analysis/CGSCCPassManagerTest.cpp

645

Personally I think it would be, if for no other reason than it's a lot easier to edit text inside of raw strings. (Also it's visually less noisy to read.)

But I'm fine doing that separately.

include/llvm/Analysis/CGSCCPassManager.h

: PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
                                         CGSCCUpdateResult &>> {
   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                         LazyCallGraph &CG, CGSCCUpdateResult &) {
     (void)AM.template getResult<AnalysisT>(C, CG);
     return PreservedAnalyses::all();
   }
 };
 
-extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
 /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
 typedef InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>
     CGSCCAnalysisManagerModuleProxy;
 
-extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
-                                                LazyCallGraph::SCC>;
+/// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
+/// it can have access to the call graph in order to walk all the SCCs when
+/// invalidating things.
+template <> class CGSCCAnalysisManagerModuleProxy::Result {
+public:
+  explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
+      : InnerAM(&InnerAM), G(&G) {}
+
+  /// \brief Accessor for the analysis manager.
+  CGSCCAnalysisManager &getManager() { return *InnerAM; }
+
+  /// \brief Handler for invalidation of the containing IR unit.
+  ///
+  /// If this analysis itself is preserved, then we assume that the set of \c
+  /// IR units that the inner analysis manager controls hasn't changed and
+  /// thus we don't need to invalidate *all* cached data associated with any
+  /// \c Module* in the \c CGSCCAnalysisManager.
+  ///
+  /// Regardless of whether this analysis is marked as preserved, all of the
+  /// analyses in the \c CGSCCAnalysisManager are potentially invalidated (for
+  /// the relevant inner set of their IR units) based on the set of preserved
+  /// analyses.
+  ///
+  /// Because this needs to understand the mapping from one IR unit to an
+  /// inner IR unit, this method isn't defined in the primary template.
+  /// Instead, each specialization of this template will need to provide an
+  /// explicit specialization of this method to handle that particular pair
+  /// of IR unit and inner CGSCCAnalysisManager.
+  bool invalidate(Module &M, const PreservedAnalyses &PA,
+                  ModuleAnalysisManager::Invalidator &Inv);
+
+private:
+  CGSCCAnalysisManager *InnerAM;
+  LazyCallGraph *G;
+};
+
+/// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
+/// so it can pass the lazy call garph to the result.
+template <>
+CGSCCAnalysisManagerModuleProxy::Result
+CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);
+
+// Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
+// template.
+extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
+
+extern template class OuterAnalysisManagerProxy<
+    ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
 /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
 typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
                                   LazyCallGraph &>
     ModuleAnalysisManagerCGSCCProxy;
 
 /// Support structure for SCC passes to communicate updates the call graph back
 /// to the CGSCC pass manager infrsatructure.
 ///
for (LazyCallGraph::RefSCC &InitialRC : CG.postorder_ref_sccs()) {
                         "current SCC: "
                      << *UR.UpdatedC << "\n";
           } while (UR.UpdatedC);
 
         } while (!CWorklist.empty());
       } while (!RCWorklist.empty());
     }
 
-    // By definition we preserve the proxy. We also preserve all analyses on
-    // SCCs. This precludes *any* invalidation of CGSCC analyses by the proxy,
-    // but that's OK because we've taken care to invalidate analyses in the
-    // CGSCC analysis manager incrementally above.
+    // By definition we preserve the call garph, all SCC analyses, and the
+    // analysis proxies by handling them above and in any nested pass managers.
+    PA.preserve<LazyCallGraphAnalysis>();
     PA.preserve<AllAnalysesOn<LazyCallGraph::SCC>>();
     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+    PA.preserve<FunctionAnalysisManagerModuleProxy>();
     return PA;
   }
 
 private:
   CGSCCPassT Pass;
   bool DebugLogging;
 };
 
 /// \brief A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename CGSCCPassT>
 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false) {
   return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass), DebugLogging);
 }
 
-extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
-                                                LazyCallGraph::SCC>;
 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
-typedef InnerAnalysisManagerProxy<FunctionAnalysisManager, LazyCallGraph::SCC,
-                                  LazyCallGraph &>
-    FunctionAnalysisManagerCGSCCProxy;
+///
+/// Note that this does not mirror the proxy from a \c FunctionAnalysisManager
+/// to a \c Module, and instead indirects through that proxy.
+///
+/// When a module pass runs and triggers invalidation, both the CGSCC and
+/// Function analysis manager proxies on the module get an invalidation event.
+/// We don't want to fully duplicate responsibility for most of the
+/// invalidation logic. Instead, this layer is only responsible for SCC-local
+/// invalidation events and works with the CGSCC proxy at the module layer to
+/// delegate module-wide invalidation to the direct \c FunctionAnalysisManager
+/// proxy at that layer.
+class FunctionAnalysisManagerCGSCCProxy
+    : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
+public:
+  class Result {
+  public:
+    explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
+
+    /// \brief Accessor for the analysis manager.
+    FunctionAnalysisManager &getManager() { return *FAM; }
+
+    bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
+                    CGSCCAnalysisManager::Invalidator &Inv);
+
+  private:
+    FunctionAnalysisManager *FAM;
+  };
+
+  /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
+  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
+
+private:
+  friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
+  static AnalysisKey Key;
+};
+
+// Ensure the \c FunctionAnalysisManagerCGSCCProxy is provided as an extern
+// template.
+extern template class InnerAnalysisManagerProxy<
+    FunctionAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
 
 extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
 typedef OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>
     CGSCCAnalysisManagerFunctionProxy;
 
 /// Helper to update the call graph after running a function pass.
 ///

include/llvm/Analysis/LoopPassManager.h

 /// \brief The loop analysis manager.
 ///
 /// See the documentation for the AnalysisManager template for detail
 /// documentation. This typedef serves as a convenient way to refer to this
 /// construct in the adaptors and proxies used to integrate this into the larger
 /// pass manager infrastructure.
 typedef AnalysisManager<Loop> LoopAnalysisManager;
 
-extern template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
 /// A proxy from a \c LoopAnalysisManager to a \c Function.
 typedef InnerAnalysisManagerProxy<LoopAnalysisManager, Function>
     LoopAnalysisManagerFunctionProxy;
 
+/// Specialization of the invalidate method for the \c
+/// LoopAnalysisManagerFunctionProxy's result.
+template <>
+bool LoopAnalysisManagerFunctionProxy::Result::invalidate(
+    Function &F, const PreservedAnalyses &PA,
+    FunctionAnalysisManager::Invalidator &Inv);
+
+// Ensure the \c LoopAnalysisManagerFunctionProxy is provided as an extern
+// template.
+extern template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
+
 extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop>;
 /// A proxy from a \c FunctionAnalysisManager to a \c Loop.
 typedef OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop>
     FunctionAnalysisManagerLoopProxy;
 
 /// Returns the minimum set of Analyses that all loop passes must preserve.
 PreservedAnalyses getLoopPassPreservedAnalyses();
 

include/llvm/IR/PassManager.h

 /// provides.
 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
 class InnerAnalysisManagerProxy
     : public AnalysisInfoMixin<
           InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>> {
 public:
   class Result {
   public:
-    explicit Result(AnalysisManagerT &AM) : AM(&AM) {}
-    Result(Result &&Arg) : AM(std::move(Arg.AM)) {
+    explicit Result(AnalysisManagerT &InnerAM) : InnerAM(&InnerAM) {}
+    Result(Result &&Arg) : InnerAM(std::move(Arg.InnerAM)) {
       // We have to null out the analysis manager in the moved-from state
       // because we are taking ownership of the responsibilty to clear the
       // analysis state.
-      Arg.AM = nullptr;
+      Arg.InnerAM = nullptr;
     }
     Result &operator=(Result &&RHS) {
-      AM = RHS.AM;
+      InnerAM = RHS.InnerAM;
       // We have to null out the analysis manager in the moved-from state
       // because we are taking ownership of the responsibilty to clear the
       // analysis state.
-      RHS.AM = nullptr;
+      RHS.InnerAM = nullptr;
       return *this;
     }
     ~Result() {
-      // AM is cleared in a moved from state where there is nothing to do.
-      if (!AM)
+      // InnerAM is cleared in a moved from state where there is nothing to do.
+      if (!InnerAM)
         return;
 
       // Clear out the analysis manager if we're being destroyed -- it means we
       // didn't even see an invalidate call when we got invalidated.
-      AM->clear();
+      InnerAM->clear();
     }
 
     /// \brief Accessor for the analysis manager.
-    AnalysisManagerT &getManager() { return *AM; }
+    AnalysisManagerT &getManager() { return *InnerAM; }
 
-    /// \brief Handler for invalidation of the module.
+    /// \brief Handler for invalidation of the containing IR unit.
     ///
     /// If this analysis itself is preserved, then we assume that the set of \c
-    /// Function objects in the \c Module hasn't changed and thus we don't need
-    /// to invalidate *all* cached data associated with a \c Function* in the \c
-    /// FunctionAnalysisManager.
+    /// IR units that the inner analysis manager controls hasn't changed and
+    /// thus we don't need to invalidate *all* cached data associated with any
+    /// \c IRUnitT* in the \c AnalysisManagerT.
     ///
     /// Regardless of whether this analysis is marked as preserved, all of the
-    /// analyses in the \c FunctionAnalysisManager are potentially invalidated
-    /// based on the set of preserved analyses.
+    /// analyses in the \c AnalysisManagerT are potentially invalidated (for
+    /// the relevant inner set of their IR units) based on the set of preserved
+    /// analyses.
+    ///
+    /// Because this needs to understand the mapping from one IR unit to an
+    /// inner IR unit, this method isn't defined in the primary template.
+    /// Instead, each specialization of this template will need to provide an
+    /// explicit specialization of this method to handle that particular pair
+    /// of IR unit and inner AnalysisManagerT.
     bool invalidate(
         IRUnitT &IR, const PreservedAnalyses &PA,
-        typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &) {
-      // If this proxy isn't marked as preserved, then we can't even invalidate
-      // individual function analyses, there may be an invalid set of Function
-      // objects in the cache making it impossible to incrementally preserve
-      // them. Just clear the entire manager.
-      if (!PA.preserved(InnerAnalysisManagerProxy::ID()))
-        AM->clear();
-
-      // Return false to indicate that this result is still a valid proxy.
-      return false;
-    }
+        typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv);
 
   private:
-    AnalysisManagerT *AM;
+    AnalysisManagerT *InnerAM;
   };
 
-  explicit InnerAnalysisManagerProxy(AnalysisManagerT &AM) : AM(&AM) {}
+  explicit InnerAnalysisManagerProxy(AnalysisManagerT &InnerAM)
+      : InnerAM(&InnerAM) {}
 
   /// \brief Run the analysis pass and create our proxy result object.
   ///
   /// This doesn't do any interesting work, it is primarily used to insert our
   /// proxy result object into the module analysis cache so that we can proxy
   /// invalidation to the function analysis manager.
   ///
   /// In debug builds, it will also assert that the analysis manager is empty
   /// as no queries should arrive at the function analysis manager prior to
   /// this analysis being requested.
-  Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &,
+  Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
              ExtraArgTs...) {
-    return Result(*AM);
+    return Result(*InnerAM);
   }
 
 private:
   friend AnalysisInfoMixin<
       InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>>;
   static AnalysisKey Key;
 
-  AnalysisManagerT *AM;
+  AnalysisManagerT *InnerAM;
 };
 
 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
 AnalysisKey
     InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key;
 
-extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
-                                                Module>;
 /// Provide the \c FunctionAnalysisManager to \c Module proxy.
 typedef InnerAnalysisManagerProxy<FunctionAnalysisManager, Module>
     FunctionAnalysisManagerModuleProxy;
 
+/// Specialization of the invalidate method for the \c
+/// FunctionAnalysisManagerModuleProxy's result.
+template <>
+bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
+    Module &M, const PreservedAnalyses &PA,
+    ModuleAnalysisManager::Invalidator &Inv);
+
+// Ensure the \c FunctionAnalysisManagerModuleProxy is provided as an extern
+// template.
+extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
+                                                Module>;
+
 /// \brief A function analysis which acts as a proxy for a module analysis
 /// manager.
 ///
 /// This primarily provides an accessor to a parent module analysis manager to
 /// function passes. Only the const interface of the module analysis manager is
 /// provided to indicate that once inside of a function analysis pass you
 /// cannot request a module analysis to actually run. Instead, the user must
 /// rely on the \c getCachedResult API.

lib/Analysis/CGSCCPassManager.cpp

 //===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/IR/CallSite.h"
 
 using namespace llvm;
 
+// Explicit template instantiations and specialization defininitions for core
+// template typedefs.
 namespace llvm {
 
 // Explicit instantiations for the core proxy templates.
 template class AllAnalysesOn<LazyCallGraph::SCC>;
 template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
 template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
                            LazyCallGraph &, CGSCCUpdateResult &>;
 template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
 template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
-                                         LazyCallGraph::SCC>;
+                                         LazyCallGraph::SCC, LazyCallGraph &>;
 template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
-                                         LazyCallGraph::SCC>;
+                                         LazyCallGraph::SCC, LazyCallGraph &>;
 template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
 
 /// Explicitly specialize the pass manager run method to handle call graph
 /// updates.
 template <>
 PreservedAnalyses
 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
             CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
   PA.preserve<AllAnalysesOn<LazyCallGraph::SCC>>();
 
   if (DebugLogging)
     dbgs() << "Finished CGSCC pass manager run.\n";
 
   return PA;
 }
 
+bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
+    Module &M, const PreservedAnalyses &PA,
+    ModuleAnalysisManager::Invalidator &Inv) {
+  // If this proxy or the call graph is going to be invalidated, we also need
+  // to clear all the keys coming from that analysis.
+  //
+  // We also directly invalidate the FAM's module proxy if necessary and if
+  // that proxy isn't preserved we can't preserve this proxy either. We rely on
+  // it to handle module -> function analysis invalidation in the face of
+  // structural changes and so if unavailable we conservatively clear the
+  // entire SCC layer as well rather than trying to do invaliadtion ourselves.
+  if (!PA.preserved<CGSCCAnalysisManagerModuleProxy>() ||
+      Inv.invalidate<LazyCallGraphAnalysis>(M, PA) ||
+      Inv.invalidate<FunctionAnalysisManagerModuleProxy>(M, PA)) {
+    InnerAM->clear();
+
+    // And the proxy itself should be marked as invalid so that we can observe
+    // the new call graph if and when created. This isn't strictly necessary
+    // because we cheat above, but is still useful.
+    return true;
+  }
+
+  // Ok, we have a graph so we can propagate the invalidation down into it.
+  // Note that we do this even if the call graph is about to become invalid so
+  // that we trigger any secondary invalidation within the cached results for
+  // this inner analysis manager before we remove those results entirely. As an
+  // example, we want to first propagate the invalidation to any function
+  // analysis results that could be cached via a CGSCC proxy before we remove
+  // that proxy.
+  for (auto &RC : G->postorder_ref_sccs())
+    for (auto &C : RC)
+      InnerAM->invalidate(C, PA);
+
+  // Otherwise false to indicate that this result is still a valid proxy.
+  return false;
+}
+
+template <>
+CGSCCAnalysisManagerModuleProxy::Result
+CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) {
+  // Force the Function analysis manager to also be available so that it can
+  // be accessed in an SCC analysis and proxied onward to function passes.
+  // FIXME: It is pretty awkward to just drop the result here and assert that
+  // we can find it again later.
+  (void)AM.getResult<FunctionAnalysisManagerModuleProxy>(M);
+
+  return Result(*InnerAM, AM.getResult<LazyCallGraphAnalysis>(M));
+}
+
+AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key;
+
+FunctionAnalysisManagerCGSCCProxy::Result
+FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C,
+                                       CGSCCAnalysisManager &AM,
+                                       LazyCallGraph &CG) {
+  // Collect the FunctionAnalysisManager from the Module layer and use that to
+  // build the proxy result.
+  //
+  // This allows us to rely on the FunctionAnalysisMangaerModuleProxy to
+  // handle non-SCC parts of the invalidation of function analyses.
+  auto &MAM = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
+  Module &M = *C.begin()->getFunction().getParent();
+  auto *FAMProxy = MAM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M);
+  assert(FAMProxy && "The CGSCC pass manager requires that the FAM module "
+                     "proxy is run on the module prior to entering the CGSCC "
+                     "walk.");
+
+  // Note that we hard-code invalidation handling of this proxy in the CGSCC
+  // analysis manager's Module proxy. This avoids the need to do anything
+  // special here to recompute all of this if ever the FAM's module proxy goes
+  // away.
+  return Result(FAMProxy->getManager());
+}
+
+bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate(
+    LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
+    CGSCCAnalysisManager::Invalidator &Inv) {
+  for (LazyCallGraph::Node &N : C)
+    FAM->invalidate(N.getFunction(), 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 is cleared
+  // which will include this proxy.
+  return false;
+}
+
 } // End llvm namespace
 
 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
 /// added SCCs.
 ///
 /// The range of new SCCs must be in postorder already. The SCC they were split

lib/Analysis/LoopPassManager.cpp

 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
-// Explicit instantiations for core typedef'ed templates.
+// Explicit template instantiations and specialization defininitions for core
+// template typedefs.
 namespace llvm {
 template class PassManager<Loop>;
 template class AnalysisManager<Loop>;
 template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
 template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop>;
+
+template <>
+bool LoopAnalysisManagerFunctionProxy::Result::invalidate(
+    Function &F, const PreservedAnalyses &PA,
+    FunctionAnalysisManager::Invalidator &Inv) {
+  // If this proxy isn't marked as preserved, then we can't even invalidate
+  // individual function analyses, there may be an invalid set of Function
+  // objects in the cache making it impossible to incrementally preserve
+  // them. Just clear the entire manager.
+  if (!PA.preserved(LoopAnalysisManagerFunctionProxy::ID()))
+    InnerAM->clear();
+
+  // FIXME: Proper suppor for invalidation isn't yet implemented for the LPM.
+
+  // Return false to indicate that this result is still a valid proxy.
+  return false;
+}
 }
 
 PreservedAnalyses llvm::getLoopPassPreservedAnalyses() {
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<LoopAnalysis>();
   PA.preserve<ScalarEvolutionAnalysis>();
   // TODO: What we really want to do here is preserve an AA category, but that
   // concept doesn't exist yet.
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
   PA.preserve<SCEVAA>();
   return PA;
 }

lib/IR/PassManager.cpp

 //===- PassManager.cpp - Infrastructure for managing & running IR passes --===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/PassManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/LLVMContext.h"
 
 using namespace llvm;
 
-// Explicit template instantiations for core template typedefs.
+// Explicit template instantiations and specialization defininitions for core
+// template typedefs.
 namespace llvm {
 template class AllAnalysesOn<Module>;
 template class AllAnalysesOn<Function>;
 template class PassManager<Module>;
 template class PassManager<Function>;
 template class AnalysisManager<Module>;
 template class AnalysisManager<Function>;
 template class InnerAnalysisManagerProxy<FunctionAnalysisManager, Module>;
 template class OuterAnalysisManagerProxy<ModuleAnalysisManager, Function>;
+
+template <>
+bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
+    Module &M, const PreservedAnalyses &PA,
+    ModuleAnalysisManager::Invalidator &Inv) {
+  // 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.
+  if (!PA.preserved(FunctionAnalysisManagerModuleProxy::ID())) {
+    InnerAM->clear();
+    return true;
+  }
+
+  // Otherwise propagate the invalidation event to all the remaining IR units.
+  for (Function &F : M)
+    InnerAM->invalidate(F, PA);
+
+  // Return false to indicate that this result is still a valid proxy.
+  return false;
+}
 }
 
 AnalysisKey PreservedAnalyses::AllAnalysesKey;

lib/Passes/PassBuilder.cpp

 }
 
 void PassBuilder::crossRegisterProxies(LoopAnalysisManager &LAM,
                                        FunctionAnalysisManager &FAM,
                                        CGSCCAnalysisManager &CGAM,
                                        ModuleAnalysisManager &MAM) {
   MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
   MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); });
-  CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(FAM); });
   CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); });
   FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); });
   FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
   FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); });
   LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); });
 }
 
 bool PassBuilder::parseModulePassPipeline(ModulePassManager &MPM,

lib/Passes/PassRegistry.def

 MODULE_PASS("wholeprogramdevirt", WholeProgramDevirtPass())
 MODULE_PASS("verify", VerifierPass())
 #undef MODULE_PASS
 
 #ifndef CGSCC_ANALYSIS
 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)
 #endif
 CGSCC_ANALYSIS("no-op-cgscc", NoOpCGSCCAnalysis())
+CGSCC_ANALYSIS("fam-proxy", FunctionAnalysisManagerCGSCCProxy())
 #undef CGSCC_ANALYSIS
 
 #ifndef CGSCC_PASS
 #define CGSCC_PASS(NAME, CREATE_PASS)
 #endif
 CGSCC_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 CGSCC_PASS("function-attrs", PostOrderFunctionAttrsPass())
 CGSCC_PASS("no-op-cgscc", NoOpCGSCCPass())

test/Other/new-pass-manager.ll

 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes=no-op-cgscc %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-CGSCC-PASS
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes='cgscc(no-op-cgscc)' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-CGSCC-PASS
 ; CHECK-CGSCC-PASS: Starting llvm::Module pass manager run
 ; CHECK-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
-; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
+; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}CGSCCAnalysisManager{{.*}}>
+; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}FunctionAnalysisManager{{.*}}>
 ; CHECK-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-CGSCC-PASS-NEXT: Running an SCC pass across the RefSCC: [(foo)]
 ; CHECK-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
 ; CHECK-CGSCC-PASS-NEXT: Finished CGSCC pass manager run
 ; CHECK-CGSCC-PASS-NEXT: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \

 ; CHECK-REPEAT-MODULE-PASS-NEXT: Finished llvm::Module pass manager run
 ; CHECK-REPEAT-MODULE-PASS-NEXT: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes='cgscc(repeat<3>(no-op-cgscc))' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-REPEAT-CGSCC-PASS
 ; CHECK-REPEAT-CGSCC-PASS: Starting llvm::Module pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}CGSCCAnalysisManager{{.*}}>
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}FunctionAnalysisManager{{.*}}>
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running an SCC pass across the RefSCC: [(foo)]
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: RepeatedPass
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run

unittests/Analysis/CGSCCPassManagerTest.cpp

private:
   friend AnalysisInfoMixin<TestImmutableFunctionAnalysis>;
   static AnalysisKey Key;
 
   int &Runs;
 };
 
 AnalysisKey TestImmutableFunctionAnalysis::Key;
 
+struct LambdaModulePass : public PassInfoMixin<LambdaModulePass> {
+  template <typename T>
+  LambdaModulePass(T &&Arg) : Func(std::forward<T>(Arg)) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  LambdaModulePass(LambdaModulePass &&Arg) : Func(std::move(Arg.Func)) {}
+  LambdaModulePass &operator=(LambdaModulePass &&RHS) {
+    Func = std::move(RHS.Func);
+    return *this;
+  }
+
+  PreservedAnalyses run(Module &F, ModuleAnalysisManager &AM) {
+    return Func(F, AM);
+  }
+
+  std::function<PreservedAnalyses(Module &, ModuleAnalysisManager &)> Func;
+};
+
 struct LambdaSCCPass : public PassInfoMixin<LambdaSCCPass> {
   template <typename T> LambdaSCCPass(T &&Arg) : Func(std::forward<T>(Arg)) {}
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
   LambdaSCCPass(LambdaSCCPass &&Arg) : Func(std::move(Arg.Func)) {}
   LambdaSCCPass &operator=(LambdaSCCPass &&RHS) {
     Func = std::move(RHS.Func);
     return *this;
CGSCCPassManagerTest()
             "}\n"
             "define void @x() {\n"
             "entry:\n"
             "  ret void\n"
             "}\n")) {
     MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
     MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
     MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); });
-    CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(FAM); });
+    CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(); });
     CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); });
     FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); });
     FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
   }
 };
 
 TEST_F(CGSCCPassManagerTest, Basic) {
   int FunctionAnalysisRuns = 0;
   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
   int ImmutableFunctionAnalysisRuns = 0;
   FAM.registerPass([&] {
     return TestImmutableFunctionAnalysis(ImmutableFunctionAnalysisRuns);
   });
 
   int SCCAnalysisRuns = 0;
   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 
   int ModuleAnalysisRuns = 0;
   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 
   ModulePassManager MPM(/*DebugLogging*/ true);
   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
 
   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
+  FunctionPassManager FPM1(/*DebugLogging*/ true);
+  int FunctionPassRunCount1 = 0;
+  FPM1.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
+    ++FunctionPassRunCount1;
+    return PreservedAnalyses::none();
+  }));
+  CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
+
   int SCCPassRunCount1 = 0;
   int AnalyzedInstrCount1 = 0;
   int AnalyzedSCCFunctionCount1 = 0;
   int AnalyzedModuleFunctionCount1 = 0;
   CGPM1.addPass(
       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
         ++SCCPassRunCount1;
CGPM1.addPass(
 
           // Just ensure we get the immutable results.
           (void)FAM.getResult<TestImmutableFunctionAnalysis>(N.getFunction());
         }
 
         return PreservedAnalyses::all();
       }));
 
-  FunctionPassManager FPM1(/*DebugLogging*/ true);
-  int FunctionPassRunCount1 = 0;
-  FPM1.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
-    ++FunctionPassRunCount1;
-    return PreservedAnalyses::all();
+  FunctionPassManager FPM2(/*DebugLogging*/ true);
+  int FunctionPassRunCount2 = 0;
+  FPM2.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
+    ++FunctionPassRunCount2;
+    return PreservedAnalyses::none();
   }));
-  CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
+  CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
+
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 
+  FunctionPassManager FPM3(/*DebugLogging*/ true);
+  int FunctionPassRunCount3 = 0;
+  FPM3.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
+    ++FunctionPassRunCount3;
+    return PreservedAnalyses::none();
+  }));
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM3)));
+
   MPM.run(*M, MAM);
 
+  EXPECT_EQ(4, SCCPassRunCount1);
+  EXPECT_EQ(6, FunctionPassRunCount1);
+  EXPECT_EQ(6, FunctionPassRunCount2);
+  EXPECT_EQ(6, FunctionPassRunCount3);
+
   EXPECT_EQ(1, ModuleAnalysisRuns);
   EXPECT_EQ(4, SCCAnalysisRuns);
   EXPECT_EQ(6, FunctionAnalysisRuns);
   EXPECT_EQ(6, ImmutableFunctionAnalysisRuns);
 
-  EXPECT_EQ(4, SCCPassRunCount1);
   EXPECT_EQ(14, AnalyzedInstrCount1);
   EXPECT_EQ(6, AnalyzedSCCFunctionCount1);
   EXPECT_EQ(4 * 6, AnalyzedModuleFunctionCount1);
 }
 
 // Test that an SCC pass which fails to preserve a module analysis does in fact
 // invalidate that module analysis.
 TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesModuleAnalysis) {
TEST_F(CGSCCPassManagerTest, TestFunctionPassInsideCGSCCInvalidatesModuleAnalysis) {
   MPM.run(*M, MAM);
 
   EXPECT_EQ(1, ModuleAnalysisRuns);
   EXPECT_TRUE(FoundModuleAnalysis1);
   EXPECT_TRUE(FoundModuleAnalysis2);
   EXPECT_FALSE(FoundModuleAnalysis3);
 }
 
+// Test that a Module pass which fails to preserve an SCC analysis in fact
+// invalidates that analysis.
+TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysis) {
+  int SCCAnalysisRuns = 0;
+  CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
+
+  {
+    // Initial module pass for the basic case where we preserve the CGSCC bits
+    // but not the SCC analysis and have to re-run it.
+    ModulePassManager MPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    CGSCCPassManager CGPM1(/*DebugLogging*/ true);
+    CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
+                                      CGSCCAnalysisManager, LazyCallGraph &,
+                                      CGSCCUpdateResult &>());
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
+
+    // Now run a module pass that preserves the LazyCallGraph and the proxy but
+    // not the SCC analysis.
+    MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
+      PreservedAnalyses PA;
+      PA.preserve<LazyCallGraphAnalysis>();
+      PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+      PA.preserve<FunctionAnalysisManagerModuleProxy>();
+      return PA;
+    }));
+
+    // And now a second CGSCC run which requires the SCC analysis again. This
+    // will trigger re-running it.
+    CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+    CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
+                                      CGSCCAnalysisManager, LazyCallGraph &,
+                                      CGSCCUpdateResult &>());
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+
+    MPM.run(*M, MAM);
+    // Two runs and four SCCs.
+    EXPECT_EQ(2 * 4, SCCAnalysisRuns);
+  }
+  {
+    // Next module pass checks that marking the SCC analysis preserved is
+    // sufficient. This should only run the analysis once for each SCC.
+    SCCAnalysisRuns = 0;
+    MAM.clear();
+    CGAM.clear();
+    ModulePassManager MPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    CGSCCPassManager CGPM1(/*DebugLogging*/ true);
+    CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
+                                      CGSCCAnalysisManager, LazyCallGraph &,
+                                      CGSCCUpdateResult &>());
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
+
+    // Now run a module pass that preserves each of the necessary components
+    // (but not everything).
+    MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
+      PreservedAnalyses PA;
+      PA.preserve<LazyCallGraphAnalysis>();
+      PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+      PA.preserve<FunctionAnalysisManagerModuleProxy>();
+      PA.preserve<TestSCCAnalysis>();
+      return PA;
+    }));
+
+    // And now a second CGSCC run which requires the SCC analysis again but find
+    // it in the cache.
+    CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+    CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
+                                      CGSCCAnalysisManager, LazyCallGraph &,
+                                      CGSCCUpdateResult &>());
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+
+    MPM.run(*M, MAM);
+    // Four SCCs
+    EXPECT_EQ(4, SCCAnalysisRuns);
+  }
+  {
+    // Final module pass checks that even when the analysis is preserved, if the
+    // SCC information isn't we still nuke things because the SCC keys could
+    // change.
+    SCCAnalysisRuns = 0;
+    MAM.clear();
+    CGAM.clear();
+    ModulePassManager MPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    CGSCCPassManager CGPM1(/*DebugLogging*/ true);
+    CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
+                                      CGSCCAnalysisManager, LazyCallGraph &,
+                                      CGSCCUpdateResult &>());
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
+
+    // Now run a module pass that preserves the analysis but not the call
+    // graph or proxy.
+    MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
+      PreservedAnalyses PA;
+      PA.preserve<TestSCCAnalysis>();
+      return PA;
+    }));
+
+    // And now a second CGSCC run which requires the SCC analysis again.
+    CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+    CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
+                                      CGSCCAnalysisManager, LazyCallGraph &,
+                                      CGSCCUpdateResult &>());
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+
+    MPM.run(*M, MAM);
+    // Two runs and four SCCs.
+    EXPECT_EQ(2 * 4, SCCAnalysisRuns);
+  }
+}
+
+// Test that an SCC pass which fails to preserve a Function analysis in fact
+// invalidates that analysis.
+TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesFunctionAnalysis) {
+  int FunctionAnalysisRuns = 0;
+  FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
+
+  // Create a very simple module with a single function & SCC to make testing
+  // these issues much easier.
+  std::unique_ptr<Module> M = parseIR("declare void @g()\n"
+                                      "declare void @h()\n"
+                                      "define void @f() {\n"
+                                      "entry:\n"
+                                      "  call void @g()\n"
+                                      "  call void @h()\n"
+                                      "  ret void\n"
+                                      "}\n");
+  {
+    // Initial SCC pass for the basic case where we preserve the CGSCC bits but
+    // not the SCC analysis and have to re-run it.
+    CGSCCPassManager CGPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    FunctionPassManager FPM1(/*DebugLogging*/ true);
+    FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
+
+    // Now run a module pass that preserves the LazyCallGraph and proxy but not
+    // the SCC analysis.
+    CGPM.addPass(
+        LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
+                          LazyCallGraph &, CGSCCUpdateResult &) {
+          PreservedAnalyses PA;
+          PA.preserve<LazyCallGraphAnalysis>();
+          return PA;
+        }));
+
+    // And now a second CGSCC run which requires the SCC analysis again. This
+    // will trigger re-running it.
+    FunctionPassManager FPM2(/*DebugLogging*/ true);
+    FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
+
+    ModulePassManager MPM(/*DebugLogging*/ true);
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+    MPM.run(*M, MAM);
+    EXPECT_EQ(2, FunctionAnalysisRuns);
+  }
+  {
+    // The next pass checks that marking the SCC analysis preserved is
+    // sufficient. This should only run the analysis once the SCC.
+    FunctionAnalysisRuns = 0;
+    CGAM.clear();
+    FAM.clear();
+    CGSCCPassManager CGPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    FunctionPassManager FPM1(/*DebugLogging*/ true);
+    FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
+
+    // Now run a module pass that preserves each of the necessary components
+    // (but
+    // not everything).
+    CGPM.addPass(
+        LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
+                          LazyCallGraph &, CGSCCUpdateResult &) {
+          PreservedAnalyses PA;
+          PA.preserve<LazyCallGraphAnalysis>();
+          PA.preserve<TestFunctionAnalysis>();
+          return PA;
+        }));
+
+    // And now a second CGSCC run which requires the SCC analysis again but find
+    // it in the cache.
+    FunctionPassManager FPM2(/*DebugLogging*/ true);
+    FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
+
+    ModulePassManager MPM(/*DebugLogging*/ true);
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+    MPM.run(*M, MAM);
+    EXPECT_EQ(1, FunctionAnalysisRuns);
+  }
+
+  // Note that there is no test for invalidating the call graph or other
+  // structure because there is no mechanism to do that from within a CGSCC
+  // pass. Instead, such a pass has to directly update the call graph
+  // structure.
+}
+
+// Test that a madule pass invalidates function analyses even when only the
+// CGSCC proxies are used and thus there isn't
+// a FunctionAnalysisManagerModuleProxy.
+TEST_F(CGSCCPassManagerTest,
+       TestModulePassInvalidatesFunctionAnalysisViaSCCProxy) {
+  MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
+
+  int FunctionAnalysisRuns = 0;
+  FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
+
+  // Check that when everything but the function analysis is preserved by
+  // a module pass it is invalidated in the second nested function pass.
+  {
+    ModulePassManager MPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    FunctionPassManager FPM1(/*DebugLogging*/ true);
+    FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGSCCPassManager CGPM1(/*DebugLogging*/ true);
+    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
+    // the Function analysis.
+    MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
+      PreservedAnalyses PA;
+      PA.preserve<LazyCallGraphAnalysis>();
+      PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+      return PA;
+    }));
+
+    // And now a second CGSCC run which requires the SCC analysis again. This
+    // will trigger re-running it.
+    FunctionPassManager FPM2(/*DebugLogging*/ true);
+    FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+    CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+
+    MPM.run(*M, MAM);
+    // Two runs and 6 functions.
+    EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
+  }
+  FunctionAnalysisRuns = 0;
+  FAM.clear();
+  MAM.clear();
+  CGAM.clear();
+
+  // Next check that by marking the function pass and FAM proxy as preserved,
+  // this propagates all the way through.
+  {
+    ModulePassManager MPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    FunctionPassManager FPM1(/*DebugLogging*/ true);
+    FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGSCCPassManager CGPM1(/*DebugLogging*/ true);
+    CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
+
+    // Now run a module pass that preserves the LazyCallGraph, the proxy, and
+    // the Function analysis.
+    MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
+      PreservedAnalyses PA;
+      PA.preserve<LazyCallGraphAnalysis>();
+      PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+      PA.preserve<FunctionAnalysisManagerModuleProxy>();
+      PA.preserve<TestFunctionAnalysis>();
+      return PA;
+    }));
+
+    // And now a second CGSCC run which requires the SCC analysis again. This
+    // will trigger re-running it.
+    FunctionPassManager FPM2(/*DebugLogging*/ true);
+    FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+    CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+
+    MPM.run(*M, MAM);
+    // One run and 6 functions.
+    EXPECT_EQ(6, FunctionAnalysisRuns);
+  }
+  FunctionAnalysisRuns = 0;
+  FAM.clear();
+  MAM.clear();
+  CGAM.clear();
+
+  // Next check that if the lazy call graph itself isn't preserved we still
+  // manage to invalidate everything.
+  {
+    ModulePassManager MPM(/*DebugLogging*/ true);
+
+    // First force the analysis to be run.
+    FunctionPassManager FPM1(/*DebugLogging*/ true);
+    FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGSCCPassManager CGPM1(/*DebugLogging*/ true);
+    CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
+
+    // Now run a module pass that preserves the LazyCallGraph but not the
+    // Function analysis.
+    MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
+      PreservedAnalyses PA;
+      return PA;
+    }));
+
+    // And now a second CGSCC run which requires the SCC analysis again. This
+    // will trigger re-running it.
+    FunctionPassManager FPM2(/*DebugLogging*/ true);
+    FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
+    CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+    CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+
+    MPM.run(*M, MAM);
+    // Two runs and 6 functions.
+    EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
+  }
+}
 }

unittests/IR/PassManagerTest.cpp

 };
 
 struct TestPreservingModulePass : PassInfoMixin<TestPreservingModulePass> {
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &) {
     return PreservedAnalyses::all();
   }
 };
 
-struct TestMinPreservingModulePass
-    : PassInfoMixin<TestMinPreservingModulePass> {
-  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
-    PreservedAnalyses PA;
-
-    // Force running an analysis.
-    (void)AM.getResult<TestModuleAnalysis>(M);
-
-    PA.preserve<FunctionAnalysisManagerModuleProxy>();
-    return PA;
-  }
-};
-
 struct TestFunctionPass : PassInfoMixin<TestFunctionPass> {
   TestFunctionPass(int &RunCount, int &AnalyzedInstrCount,
                    int &AnalyzedFunctionCount,
                    bool OnlyUseCachedResults = false)
       : RunCount(RunCount), AnalyzedInstrCount(AnalyzedInstrCount),
         AnalyzedFunctionCount(AnalyzedFunctionCount),
         OnlyUseCachedResults(OnlyUseCachedResults) {}
 
TEST_F(PassManagerTest, BasicPreservedAnalyses) {
   EXPECT_TRUE(PA1.preserved<TestFunctionAnalysis>());
   EXPECT_TRUE(PA1.preserved<TestModuleAnalysis>());
   PA1.intersect(PA4);
   EXPECT_TRUE(PA1.preserved<TestFunctionAnalysis>());
   EXPECT_FALSE(PA1.preserved<TestModuleAnalysis>());
 }
 
 TEST_F(PassManagerTest, Basic) {
-  FunctionAnalysisManager FAM;
+  FunctionAnalysisManager FAM(/*DebugLogging*/ true);
   int FunctionAnalysisRuns = 0;
   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 
-  ModuleAnalysisManager MAM;
+  ModuleAnalysisManager MAM(/*DebugLogging*/ true);
   int ModuleAnalysisRuns = 0;
   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
   MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
   FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
 
   ModulePassManager MPM;
 
   // Count the runs over a Function.
   int FunctionPassRunCount1 = 0;
   int AnalyzedInstrCount1 = 0;
   int AnalyzedFunctionCount1 = 0;
   {
     // Pointless scoped copy to test move assignment.
-    ModulePassManager NestedMPM;
+    ModulePassManager NestedMPM(/*DebugLogging*/ true);
     FunctionPassManager FPM;
     {
       // Pointless scope to test move assignment.
-      FunctionPassManager NestedFPM;
+      FunctionPassManager NestedFPM(/*DebugLogging*/ true);
       NestedFPM.addPass(TestFunctionPass(
           FunctionPassRunCount1, AnalyzedInstrCount1, AnalyzedFunctionCount1));
       FPM = std::move(NestedFPM);
     }
     NestedMPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
     MPM = std::move(NestedMPM);
   }
 
   // Count the runs over a module.
   int ModulePassRunCount = 0;
   MPM.addPass(TestModulePass(ModulePassRunCount));
 
   // Count the runs over a Function in a separate manager.
   int FunctionPassRunCount2 = 0;
   int AnalyzedInstrCount2 = 0;
   int AnalyzedFunctionCount2 = 0;
   {
-    FunctionPassManager FPM;
+    FunctionPassManager FPM(/*DebugLogging*/ true);
     FPM.addPass(TestFunctionPass(FunctionPassRunCount2, AnalyzedInstrCount2,
                                  AnalyzedFunctionCount2));
     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
   }
 
   // A third function pass manager but with only preserving intervening passes
   // and with a function pass that invalidates exactly one analysis.
   MPM.addPass(TestPreservingModulePass());
   int FunctionPassRunCount3 = 0;
   int AnalyzedInstrCount3 = 0;
   int AnalyzedFunctionCount3 = 0;
   {
-    FunctionPassManager FPM;
+    FunctionPassManager FPM(/*DebugLogging*/ true);
     FPM.addPass(TestFunctionPass(FunctionPassRunCount3, AnalyzedInstrCount3,
                                  AnalyzedFunctionCount3));
     FPM.addPass(TestInvalidationFunctionPass("f"));
     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
   }
 
-  // A fourth function pass manager but with a minimal intervening passes.
-  MPM.addPass(TestMinPreservingModulePass());
+  // A fourth function pass manager but with only preserving intervening
+  // passes but triggering the module analysis.
+  MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
   int FunctionPassRunCount4 = 0;
   int AnalyzedInstrCount4 = 0;
   int AnalyzedFunctionCount4 = 0;
   {
     FunctionPassManager FPM;
     FPM.addPass(TestFunctionPass(FunctionPassRunCount4, AnalyzedInstrCount4,
                                  AnalyzedFunctionCount4));
     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
   }
 
-  // A fifth function pass manager but which uses only cached results.
+  // A fifth function pass manager which invalidates one function first but
+  // uses only cached results.
   int FunctionPassRunCount5 = 0;
   int AnalyzedInstrCount5 = 0;
   int AnalyzedFunctionCount5 = 0;
   {
-    FunctionPassManager FPM;
+    FunctionPassManager FPM(/*DebugLogging*/ true);
     FPM.addPass(TestInvalidationFunctionPass("f"));
     FPM.addPass(TestFunctionPass(FunctionPassRunCount5, AnalyzedInstrCount5,
                                  AnalyzedFunctionCount5,
                                  /*OnlyUseCachedResults=*/true));
     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
   }
 
   MPM.run(*M, MAM);
 
   // Validate module pass counters.
   EXPECT_EQ(1, ModulePassRunCount);
 
   // Validate all function pass counter sets are the same.
   EXPECT_EQ(3, FunctionPassRunCount1);
   EXPECT_EQ(5, AnalyzedInstrCount1);
   EXPECT_EQ(0, AnalyzedFunctionCount1);
   EXPECT_EQ(3, FunctionPassRunCount2);
   EXPECT_EQ(5, AnalyzedInstrCount2);
   EXPECT_EQ(0, AnalyzedFunctionCount2);
   EXPECT_EQ(3, FunctionPassRunCount3);
   EXPECT_EQ(5, AnalyzedInstrCount3);
   EXPECT_EQ(0, AnalyzedFunctionCount3);
   EXPECT_EQ(3, FunctionPassRunCount4);
   EXPECT_EQ(5, AnalyzedInstrCount4);
-  EXPECT_EQ(0, AnalyzedFunctionCount4);
+  EXPECT_EQ(9, AnalyzedFunctionCount4);
   EXPECT_EQ(3, FunctionPassRunCount5);
   EXPECT_EQ(2, AnalyzedInstrCount5); // Only 'g' and 'h' were cached.
-  EXPECT_EQ(0, AnalyzedFunctionCount5);
+  EXPECT_EQ(9, AnalyzedFunctionCount5);
 
   // Validate the analysis counters:
   //   first run over 3 functions, then module pass invalidates
   //   second run over 3 functions, nothing invalidates
   //   third run over 0 functions, but 1 function invalidated
   //   fourth run over 1 function
+  //   fifth run invalidates 1 function first, but runs over 0 functions
   EXPECT_EQ(7, FunctionAnalysisRuns);
 
   EXPECT_EQ(1, ModuleAnalysisRuns);
 }
 
 // A customized pass manager that passes extra arguments through the
 // infrastructure.
 typedef AnalysisManager<Function, int> CustomizedAnalysisManager;