[NewPM] Make pass adaptors less templatey

[aeubanks]

Summary

Currently PassBuilder.cpp is by far the file that takes longest to
compile. This is due to tons of templates being instantiated per pass.

Follow PassManager by using wrappers around passes to avoid making
the adaptors templated on the pass type. This allows us to move various
adaptors' run methods into .cpp files.

This reduces the compile time of PassBuilder.cpp on my machine from 66
to 39 seconds. It also reduces the size of opt from 685M to 676M.

[aeubanks]

add missed references

[dexonsmith]

This seems like a great improvement!

llvm/lib/Passes/StandardInstrumentations.cpp

476

Could / should these changes to use isIgnored be committed separately / ahead of time?

llvm/lib/Transforms/Scalar/LoopPassManager.cpp

89

Can adding this comment be pulled out to a separate commit? It seems unrelated to this change.

[aeubanks]

llvm/lib/Passes/StandardInstrumentations.cpp

476

it is related to this change but can be done ahead of time: https://reviews.llvm.org/D92625

llvm/lib/Transforms/Scalar/LoopPassManager.cpp

89

this seems fairly benign to me, but sure

[dexonsmith]

Once you've rebased on the other changes this LGTM.

llvm/lib/Passes/StandardInstrumentations.cpp

476

Thanks!

llvm/lib/Transforms/Scalar/LoopPassManager.cpp

89

Thanks, I don't think it needs review or anything, but I had to stare at the diff for a while to see what had happened to the braces... if you commit unrelated comment / whitespace changes separately then later when people look at the log / blame / etc. it'll be a bit cleaner (in this chunk, the "new" brace will be the closing one for FunctionToLoopPassAdaptor::run instead of this one here)

[aeubanks]

rebase

[rnk]

Just paged through this. Nice!

llvm/include/llvm/Analysis/CGSCCPassManager.h

 /// runs a CGSCC pass over each one.
 ///
 /// Designed to allow composition of a CGSCCPass(Manager) and
 /// a ModulePassManager. Note that this pass must be run with a module analysis
 /// manager as it uses the LazyCallGraph analysis. It will also run the
 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
 /// pass over the module to enable a \c FunctionAnalysisManager to be used
 /// within this run safely.
-template <typename CGSCCPassT>
 class ModuleToPostOrderCGSCCPassAdaptor
-    : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
+    : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor> {
 public:
-  explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
-      : Pass(std::move(Pass)) {}
+  using PassConceptT =
+      detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager,
+                          LazyCallGraph &, CGSCCUpdateResult &>;
 
-  // We have to explicitly define all the special member functions because MSVC
-  // refuses to generate them.
-  ModuleToPostOrderCGSCCPassAdaptor(
-      const ModuleToPostOrderCGSCCPassAdaptor &Arg)
-      : Pass(Arg.Pass) {}
+  explicit ModuleToPostOrderCGSCCPassAdaptor(std::unique_ptr<PassConceptT> Pass)
+      : Pass(std::move(Pass)) {}
 
   ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
       : Pass(std::move(Arg.Pass)) {}
 
   friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
                    ModuleToPostOrderCGSCCPassAdaptor &RHS) {
     std::swap(LHS.Pass, RHS.Pass);
   }
 
   ModuleToPostOrderCGSCCPassAdaptor &
   operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   /// Runs the CGSCC pass across every SCC in the module.
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
   static bool isRequired() { return true; }
 
 private:
-  CGSCCPassT Pass;
+  std::unique_ptr<PassConceptT> Pass;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename CGSCCPassT>
-ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
+ModuleToPostOrderCGSCCPassAdaptor
 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
-  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
+  using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
+                                       PreservedAnalyses, CGSCCAnalysisManager,
+                                       LazyCallGraph &, CGSCCUpdateResult &>;
+  return ModuleToPostOrderCGSCCPassAdaptor(
+      std::make_unique<PassModelT>(std::move(Pass)));
 }
 
 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
 ///
 /// 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

 /// Adaptor that maps from a SCC to its functions.
 ///
 /// Designed to allow composition of a FunctionPass(Manager) and
 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
 /// to a \c CGSCCAnalysisManager it will run the
 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
 /// within this run safely.
-template <typename FunctionPassT>
 class CGSCCToFunctionPassAdaptor
-    : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
+    : public PassInfoMixin<CGSCCToFunctionPassAdaptor> {
 public:
-  explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
-      : Pass(std::move(Pass)) {}
+  using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>;
 
-  // We have to explicitly define all the special member functions because MSVC
-  // refuses to generate them.
-  CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
-      : Pass(Arg.Pass) {}
+  explicit CGSCCToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass)
+      : Pass(std::move(Pass)) {}
 
   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
       : Pass(std::move(Arg.Pass)) {}
 
   friend void swap(CGSCCToFunctionPassAdaptor &LHS,
                    CGSCCToFunctionPassAdaptor &RHS) {
     std::swap(LHS.Pass, RHS.Pass);
   }
 
   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   /// Runs the function pass across every function in the module.
   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
-                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
-    // Setup the function analysis manager from its proxy.
-    FunctionAnalysisManager &FAM =
-        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
-
-    SmallVector<LazyCallGraph::Node *, 4> Nodes;
-    for (LazyCallGraph::Node &N : C)
-      Nodes.push_back(&N);
-
-    // The SCC may get split while we are optimizing functions due to deleting
-    // edges. If this happens, the current SCC can shift, so keep track of
-    // a pointer we can overwrite.
-    LazyCallGraph::SCC *CurrentC = &C;
-
-    LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
-                      << "\n");
-
-    PreservedAnalyses PA = PreservedAnalyses::all();
-    for (LazyCallGraph::Node *N : Nodes) {
-      // Skip nodes from other SCCs. These may have been split out during
-      // processing. We'll eventually visit those SCCs and pick up the nodes
-      // there.
-      if (CG.lookupSCC(*N) != CurrentC)
-        continue;
-
-      Function &F = N->getFunction();
-
-      PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
-      if (!PI.runBeforePass<Function>(Pass, F))
-        continue;
-
-      PreservedAnalyses PassPA;
-      {
-        TimeTraceScope TimeScope(Pass.name());
-        PassPA = Pass.run(F, FAM);
-      }
-
-      PI.runAfterPass<Function>(Pass, F, PassPA);
-
-      // We know that the function pass couldn't have invalidated any other
-      // function's analyses (that's the contract of a function pass), so
-      // directly handle the function analysis manager's invalidation here.
-      FAM.invalidate(F, PassPA);
-
-      // Then intersect the preserved set so that invalidation of module
-      // analyses will eventually occur when the module pass completes.
-      PA.intersect(std::move(PassPA));
-
-      // If the call graph hasn't been preserved, update it based on this
-      // function pass. This may also update the current SCC to point to
-      // a smaller, more refined SCC.
-      auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
-      if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
-        CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
-                                                              AM, UR, FAM);
-        assert(
-            CG.lookupSCC(*N) == CurrentC &&
-            "Current SCC not updated to the SCC containing the current node!");
-      }
-    }
-
-    // By definition we preserve the proxy. And we preserve all analyses on
-    // Functions. This precludes *any* invalidation of function analyses by the
-    // proxy, but that's OK because we've taken care to invalidate analyses in
-    // the function analysis manager incrementally above.
-    PA.preserveSet<AllAnalysesOn<Function>>();
-    PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
-
-    // We've also ensured that we updated the call graph along the way.
-    PA.preserve<LazyCallGraphAnalysis>();
-
-    return PA;
-  }
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR);
 
   static bool isRequired() { return true; }
 
 private:
-  FunctionPassT Pass;
+  std::unique_ptr<PassConceptT> Pass;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
-CGSCCToFunctionPassAdaptor<FunctionPassT>
+CGSCCToFunctionPassAdaptor
 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
-  return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
+  using PassModelT =
+      detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
+                        FunctionAnalysisManager>;
+  return CGSCCToFunctionPassAdaptor(
+      std::make_unique<PassModelT>(std::move(Pass)));
 }
 
 /// Checks -abort-on-max-devirt-iterations-reached to see if we should report an
 /// error.
 void maxDevirtIterationsReached();
 
 /// A helper that repeats an SCC pass each time an indirect call is refined to
 /// a direct call by that pass.
 ///
 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
 /// change shape, we may also want to repeat an SCC pass if it simply refines
 /// an indirect call to a direct call, even if doing so does not alter the
 /// shape of the graph. Note that this only pertains to direct calls to
 /// functions where IPO across the SCC may be able to compute more precise
 /// results. For intrinsics, we assume scalar optimizations already can fully
 /// reason about them.
 ///
 /// This repetition has the potential to be very large however, as each one
 /// might refine a single call site. As a consequence, in practice we use an
 /// upper bound on the number of repetitions to limit things.
-template <typename PassT>
-class DevirtSCCRepeatedPass
-    : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
+class DevirtSCCRepeatedPass : public PassInfoMixin<DevirtSCCRepeatedPass> {
 public:
-  explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
+  using PassConceptT =
+      detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager,
+                          LazyCallGraph &, CGSCCUpdateResult &>;
+
+  explicit DevirtSCCRepeatedPass(std::unique_ptr<PassConceptT> Pass,
+                                 int MaxIterations)
       : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
 
   /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
   /// whenever an indirect call is refined.
   PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
-                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
-    PreservedAnalyses PA = PreservedAnalyses::all();
-    PassInstrumentation PI =
-        AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
-
-    // The SCC may be refined while we are running passes over it, so set up
-    // a pointer that we can update.
-    LazyCallGraph::SCC *C = &InitialC;
-
-    // Struct to track the counts of direct and indirect calls in each function
-    // of the SCC.
-    struct CallCount {
-      int Direct;
-      int Indirect;
-    };
-
-    // Put value handles on all of the indirect calls and return the number of
-    // direct calls for each function in the SCC.
-    auto ScanSCC =
-        [](LazyCallGraph::SCC &C,
-           SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {
-          assert(CallHandles.empty() &&
-                 "Must start with a clear set of handles.");
-
-          SmallDenseMap<Function *, CallCount> CallCounts;
-          CallCount CountLocal = {0, 0};
-          for (LazyCallGraph::Node &N : C) {
-            CallCount &Count =
-                CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
-                    .first->second;
-            for (Instruction &I : instructions(N.getFunction()))
-              if (auto *CB = dyn_cast<CallBase>(&I)) {
-                if (CB->getCalledFunction()) {
-                  ++Count.Direct;
-                } else {
-                  ++Count.Indirect;
-                  CallHandles.insert({CB, WeakTrackingVH(CB)});
-                }
-              }
-          }
-
-          return CallCounts;
-        };
-
-    UR.IndirectVHs.clear();
-    // Populate the initial call handles and get the initial call counts.
-    auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
-
-    for (int Iteration = 0;; ++Iteration) {
-      if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
-        continue;
-
-      PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
-
-      if (UR.InvalidatedSCCs.count(C))
-        PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass, PassPA);
-      else
-        PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C, PassPA);
-
-      // If the SCC structure has changed, bail immediately and let the outer
-      // CGSCC layer handle any iteration to reflect the refined structure.
-      if (UR.UpdatedC && UR.UpdatedC != C) {
-        PA.intersect(std::move(PassPA));
-        break;
-      }
-
-      // Check that we didn't miss any update scenario.
-      assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
-      assert(C->begin() != C->end() && "Cannot have an empty SCC!");
-
-      // Check whether any of the handles were devirtualized.
-      bool Devirt = llvm::any_of(UR.IndirectVHs, [](auto &P) -> bool {
-        if (P.second) {
-          if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
-            if (CB->getCalledFunction()) {
-              LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");
-              return true;
-            }
-          }
-        }
-        return false;
-      });
-
-      // Rescan to build up a new set of handles and count how many direct
-      // calls remain. If we decide to iterate, this also sets up the input to
-      // the next iteration.
-      UR.IndirectVHs.clear();
-      auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);
-
-      // If we haven't found an explicit devirtualization already see if we
-      // have decreased the number of indirect calls and increased the number
-      // of direct calls for any function in the SCC. This can be fooled by all
-      // manner of transformations such as DCE and other things, but seems to
-      // work well in practice.
-      if (!Devirt)
-        // Iterate over the keys in NewCallCounts, if Function also exists in
-        // CallCounts, make the check below.
-        for (auto &Pair : NewCallCounts) {
-          auto &CallCountNew = Pair.second;
-          auto CountIt = CallCounts.find(Pair.first);
-          if (CountIt != CallCounts.end()) {
-            const auto &CallCountOld = CountIt->second;
-            if (CallCountOld.Indirect > CallCountNew.Indirect &&
-                CallCountOld.Direct < CallCountNew.Direct) {
-              Devirt = true;
-              break;
-            }
-          }
-        }
-
-      if (!Devirt) {
-        PA.intersect(std::move(PassPA));
-        break;
-      }
-
-      // Otherwise, if we've already hit our max, we're done.
-      if (Iteration >= MaxIterations) {
-        maxDevirtIterationsReached();
-        LLVM_DEBUG(
-            dbgs() << "Found another devirtualization after hitting the max "
-                      "number of repetitions ("
-                   << MaxIterations << ") on SCC: " << *C << "\n");
-        PA.intersect(std::move(PassPA));
-        break;
-      }
-
-      LLVM_DEBUG(
-          dbgs()
-          << "Repeating an SCC pass after finding a devirtualization in: " << *C
-          << "\n");
-
-      // Move over the new call counts in preparation for iterating.
-      CallCounts = std::move(NewCallCounts);
-
-      // Update the analysis manager with each run and intersect the total set
-      // of preserved analyses so we're ready to iterate.
-      AM.invalidate(*C, PassPA);
-
-      PA.intersect(std::move(PassPA));
-    }
-
-    // Note that we don't add any preserved entries here unlike a more normal
-    // "pass manager" because we only handle invalidation *between* iterations,
-    // not after the last iteration.
-    return PA;
-  }
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR);
 
 private:
-  PassT Pass;
+  std::unique_ptr<PassConceptT> Pass;
   int MaxIterations;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
-template <typename PassT>
-DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
-                                                         int MaxIterations) {
-  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
-}
-
-// Out-of-line implementation details for templates below this point.
-
 template <typename CGSCCPassT>
-PreservedAnalyses
-ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::run(Module &M,
-                                                   ModuleAnalysisManager &AM) {
-  // Setup the CGSCC analysis manager from its proxy.
-  CGSCCAnalysisManager &CGAM =
-      AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
-
-  // Get the call graph for this module.
-  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
-
-  // Get Function analysis manager from its proxy.
-  FunctionAnalysisManager &FAM =
-      AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M)->getManager();
-
-  // We keep worklists to allow us to push more work onto the pass manager as
-  // the passes are run.
-  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
-  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
-
-  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
-  // iterating off the worklists.
-  SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
-  SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
-
-  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
-      InlinedInternalEdges;
-
-  CGSCCUpdateResult UR = {
-      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
-      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges,
-      {}};
-
-  // Request PassInstrumentation from analysis manager, will use it to run
-  // instrumenting callbacks for the passes later.
-  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
-
-  PreservedAnalyses PA = PreservedAnalyses::all();
-  CG.buildRefSCCs();
-  for (auto RCI = CG.postorder_ref_scc_begin(),
-            RCE = CG.postorder_ref_scc_end();
-       RCI != RCE;) {
-    assert(RCWorklist.empty() &&
-           "Should always start with an empty RefSCC worklist");
-    // The postorder_ref_sccs range we are walking is lazily constructed, so
-    // we only push the first one onto the worklist. The worklist allows us
-    // to capture *new* RefSCCs created during transformations.
-    //
-    // We really want to form RefSCCs lazily because that makes them cheaper
-    // to update as the program is simplified and allows us to have greater
-    // cache locality as forming a RefSCC touches all the parts of all the
-    // functions within that RefSCC.
-    //
-    // We also eagerly increment the iterator to the next position because
-    // the CGSCC passes below may delete the current RefSCC.
-    RCWorklist.insert(&*RCI++);
-
-    do {
-      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
-      if (InvalidRefSCCSet.count(RC)) {
-        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
-        continue;
-      }
-
-      assert(CWorklist.empty() &&
-             "Should always start with an empty SCC worklist");
-
-      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
-                        << "\n");
-
-      // The top of the worklist may *also* be the same SCC we just ran over
-      // (and invalidated for). Keep track of that last SCC we processed due
-      // to SCC update to avoid redundant processing when an SCC is both just
-      // updated itself and at the top of the worklist.
-      LazyCallGraph::SCC *LastUpdatedC = nullptr;
-
-      // Push the initial SCCs in reverse post-order as we'll pop off the
-      // back and so see this in post-order.
-      for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
-        CWorklist.insert(&C);
-
-      do {
-        LazyCallGraph::SCC *C = CWorklist.pop_back_val();
-        // Due to call graph mutations, we may have invalid SCCs or SCCs from
-        // other RefSCCs in the worklist. The invalid ones are dead and the
-        // other RefSCCs should be queued above, so we just need to skip both
-        // scenarios here.
-        if (InvalidSCCSet.count(C)) {
-          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
-          continue;
-        }
-        if (LastUpdatedC == C) {
-          LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
-          continue;
-        }
-        if (&C->getOuterRefSCC() != RC) {
-          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
-                               "RefSCC...\n");
-          continue;
-        }
-
-        // Ensure we can proxy analysis updates from the CGSCC analysis manager
-        // into the the Function analysis manager by getting a proxy here.
-        // This also needs to update the FunctionAnalysisManager, as this may be
-        // the first time we see this SCC.
-        CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
-            FAM);
-
-        // Each time we visit a new SCC pulled off the worklist,
-        // a transformation of a child SCC may have also modified this parent
-        // and invalidated analyses. So we invalidate using the update record's
-        // cross-SCC preserved set. This preserved set is intersected by any
-        // CGSCC pass that handles invalidation (primarily pass managers) prior
-        // to marking its SCC as preserved. That lets us track everything that
-        // might need invalidation across SCCs without excessive invalidations
-        // on a single SCC.
-        //
-        // This essentially allows SCC passes to freely invalidate analyses
-        // of any ancestor SCC. If this becomes detrimental to successfully
-        // caching analyses, we could force each SCC pass to manually
-        // invalidate the analyses for any SCCs other than themselves which
-        // are mutated. However, that seems to lose the robustness of the
-        // pass-manager driven invalidation scheme.
-        CGAM.invalidate(*C, UR.CrossSCCPA);
-
-        do {
-          // Check that we didn't miss any update scenario.
-          assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
-          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
-          assert(&C->getOuterRefSCC() == RC &&
-                 "Processing an SCC in a different RefSCC!");
-
-          LastUpdatedC = UR.UpdatedC;
-          UR.UpdatedRC = nullptr;
-          UR.UpdatedC = nullptr;
-
-          // Check the PassInstrumentation's BeforePass callbacks before
-          // running the pass, skip its execution completely if asked to
-          // (callback returns false).
-          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
-            continue;
-
-          PreservedAnalyses PassPA;
-          {
-            TimeTraceScope TimeScope(Pass.name());
-            PassPA = Pass.run(*C, CGAM, CG, UR);
-          }
-
-          if (UR.InvalidatedSCCs.count(C))
-            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass, PassPA);
-          else
-            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C, PassPA);
-
-          // Update the SCC and RefSCC if necessary.
-          C = UR.UpdatedC ? UR.UpdatedC : C;
-          RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
-
-          if (UR.UpdatedC) {
-            // If we're updating the SCC, also update the FAM inside the proxy's
-            // result.
-            CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
-                FAM);
-          }
-
-          // If the CGSCC pass wasn't able to provide a valid updated SCC,
-          // the current SCC may simply need to be skipped if invalid.
-          if (UR.InvalidatedSCCs.count(C)) {
-            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
-            break;
-          }
-          // Check that we didn't miss any update scenario.
-          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
-
-          // We handle invalidating the CGSCC analysis manager's information
-          // for the (potentially updated) SCC here. Note that any other SCCs
-          // whose structure has changed should have been invalidated by
-          // whatever was updating the call graph. This SCC gets invalidated
-          // late as it contains the nodes that were actively being
-          // processed.
-          CGAM.invalidate(*C, PassPA);
-
-          // Then intersect the preserved set so that invalidation of module
-          // analyses will eventually occur when the module pass completes.
-          // Also intersect with the cross-SCC preserved set to capture any
-          // cross-SCC invalidation.
-          UR.CrossSCCPA.intersect(PassPA);
-          PA.intersect(std::move(PassPA));
-
-          // The pass may have restructured the call graph and refined the
-          // current SCC and/or RefSCC. We need to update our current SCC and
-          // RefSCC pointers to follow these. Also, when the current SCC is
-          // refined, re-run the SCC pass over the newly refined SCC in order
-          // to observe the most precise SCC model available. This inherently
-          // cannot cycle excessively as it only happens when we split SCCs
-          // apart, at most converging on a DAG of single nodes.
-          // FIXME: If we ever start having RefSCC passes, we'll want to
-          // iterate there too.
-          if (UR.UpdatedC)
-            LLVM_DEBUG(dbgs()
-                       << "Re-running SCC passes after a refinement of the "
-                          "current SCC: "
-                       << *UR.UpdatedC << "\n");
-
-          // Note that both `C` and `RC` may at this point refer to deleted,
-          // invalid SCC and RefSCCs respectively. But we will short circuit
-          // the processing when we check them in the loop above.
-        } while (UR.UpdatedC);
-      } while (!CWorklist.empty());
-
-      // We only need to keep internal inlined edge information within
-      // a RefSCC, clear it to save on space and let the next time we visit
-      // any of these functions have a fresh start.
-      InlinedInternalEdges.clear();
-    } while (!RCWorklist.empty());
-  }
-
-  // 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.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
-  PA.preserve<LazyCallGraphAnalysis>();
-  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
-  PA.preserve<FunctionAnalysisManagerModuleProxy>();
-  return PA;
+DevirtSCCRepeatedPass createDevirtSCCRepeatedPass(CGSCCPassT Pass,
+                                                  int MaxIterations) {
+  using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
+                                       PreservedAnalyses, CGSCCAnalysisManager,
+                                       LazyCallGraph &, CGSCCUpdateResult &>;
+  return DevirtSCCRepeatedPass(std::make_unique<PassModelT>(std::move(Pass)),
+                               MaxIterations);
 }
 
 // Clear out the debug logging macro.
 #undef DEBUG_TYPE
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H

llvm/include/llvm/IR/PassManager.h

 /// For example, a function pass is not permitted to add functions to the
 /// module.
 /// FIXME: Make the above true for all of LLVM's actual passes, some still
 /// violate this principle.
 ///
 /// Note that although function passes can access module analyses, module
 /// analyses are not invalidated while the function passes are running, so they
 /// may be stale.  Function analyses will not be stale.
-template <typename FunctionPassT>
 class ModuleToFunctionPassAdaptor
-    : public PassInfoMixin<ModuleToFunctionPassAdaptor<FunctionPassT>> {
+    : public PassInfoMixin<ModuleToFunctionPassAdaptor> {
 public:
-  explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
+  using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>;
+
+  explicit ModuleToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass)
       : Pass(std::move(Pass)) {}
 
   /// Runs the function pass across every function in the module.
-  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
-    FunctionAnalysisManager &FAM =
-        AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
-
-    // Request PassInstrumentation from analysis manager, will use it to run
-    // instrumenting callbacks for the passes later.
-    PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
-
-    PreservedAnalyses PA = PreservedAnalyses::all();
-    for (Function &F : M) {
-      if (F.isDeclaration())
-        continue;
-
-      // Check the PassInstrumentation's BeforePass callbacks before running the
-      // pass, skip its execution completely if asked to (callback returns
-      // false).
-      if (!PI.runBeforePass<Function>(Pass, F))
-        continue;
-
-      PreservedAnalyses PassPA;
-      {
-        TimeTraceScope TimeScope(Pass.name(), F.getName());
-        PassPA = Pass.run(F, FAM);
-      }
-
-      PI.runAfterPass(Pass, F, PassPA);
-
-      // We know that the function pass couldn't have invalidated any other
-      // function's analyses (that's the contract of a function pass), so
-      // directly handle the function analysis manager's invalidation here.
-      FAM.invalidate(F, PassPA);
-
-      // Then intersect the preserved set so that invalidation of module
-      // analyses will eventually occur when the module pass completes.
-      PA.intersect(std::move(PassPA));
-    }
-
-    // The FunctionAnalysisManagerModuleProxy is preserved because (we assume)
-    // the function passes we ran didn't add or remove any functions.
-    //
-    // We also preserve all analyses on Functions, because we did all the
-    // invalidation we needed to do above.
-    PA.preserveSet<AllAnalysesOn<Function>>();
-    PA.preserve<FunctionAnalysisManagerModuleProxy>();
-    return PA;
-  }
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
   static bool isRequired() { return true; }
 
 private:
-  FunctionPassT Pass;
+  std::unique_ptr<PassConceptT> Pass;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
-ModuleToFunctionPassAdaptor<FunctionPassT>
+ModuleToFunctionPassAdaptor
 createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
-  return ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
+  using PassModelT =
+      detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
+                        FunctionAnalysisManager>;
+
+  return ModuleToFunctionPassAdaptor(
+      std::make_unique<PassModelT>(std::move(Pass)));
 }
 
 /// A utility pass template to force an analysis result to be available.
 ///
 /// If there are extra arguments at the pass's run level there may also be
 /// extra arguments to the analysis manager's \c getResult routine. We can't
 /// guess how to effectively map the arguments from one to the other, and so
 /// this specialization just ignores them.

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PassInstrumentation.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
+#include <memory>
 
 namespace llvm {
 
 // Forward declarations of an update tracking API used in the pass manager.
 class LPMUpdater;
 
 // Explicit specialization and instantiation declarations for the pass manager.
 // See the comments on the definition of the specialization for details on how

 };
 
 /// An alias template to easily name a require analysis loop pass.
 template <typename AnalysisT>
 using RequireAnalysisLoopPass =
     RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
                         LoopStandardAnalysisResults &, LPMUpdater &>;
 
-template <typename LoopPassT> class FunctionToLoopPassAdaptor;
+class FunctionToLoopPassAdaptor;
 
 /// This class provides an interface for updating the loop pass manager based
 /// on mutations to the loop nest.
 ///
 /// A reference to an instance of this class is passed as an argument to each
 /// Loop pass, and Loop passes should use it to update LPM infrastructure if
 /// they modify the loop nest structure.
 class LPMUpdater {
void revisitCurrentLoop() {
     // Tell the currently in-flight pipeline to stop running.
     SkipCurrentLoop = true;
 
     // And insert ourselves back into the worklist.
     Worklist.insert(CurrentL);
   }
 
 private:
-  template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor;
+  friend class llvm::FunctionToLoopPassAdaptor;
 
   /// The \c FunctionToLoopPassAdaptor's worklist of loops to process.
   SmallPriorityWorklist<Loop *, 4> &Worklist;
 
   /// The analysis manager for use in the current loop nest.
   LoopAnalysisManager &LAM;
 
   Loop *CurrentL;

 
 /// Adaptor that maps from a function to its loops.
 ///
 /// Designed to allow composition of a LoopPass(Manager) and a
 /// FunctionPassManager. Note that if this pass is constructed with a \c
 /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
 /// analysis prior to running the loop passes over the function to enable a \c
 /// LoopAnalysisManager to be used within this run safely.
-template <typename LoopPassT>
 class FunctionToLoopPassAdaptor
-    : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
+    : public PassInfoMixin<FunctionToLoopPassAdaptor> {
 public:
-  explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false,
+  using PassConceptT =
+      detail::PassConcept<Loop, LoopAnalysisManager,
+                          LoopStandardAnalysisResults &, LPMUpdater &>;
+
+  explicit FunctionToLoopPassAdaptor(std::unique_ptr<PassConceptT> Pass,
+                                     bool UseMemorySSA = false,
                                      bool UseBlockFrequencyInfo = false,
                                      bool DebugLogging = false)
       : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging),
         UseMemorySSA(UseMemorySSA),
         UseBlockFrequencyInfo(UseBlockFrequencyInfo) {
     LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
     LoopCanonicalizationFPM.addPass(LCSSAPass());
   }
 
   /// Runs the loop passes across every loop in the function.
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
-    // Before we even compute any loop analyses, first run a miniature function
-    // pass pipeline to put loops into their canonical form. Note that we can
-    // directly build up function analyses after this as the function pass
-    // manager handles all the invalidation at that layer.
-    PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
-
-    PreservedAnalyses PA = PreservedAnalyses::all();
-    // Check the PassInstrumentation's BeforePass callbacks before running the
-    // canonicalization pipeline.
-    if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
-      PA = LoopCanonicalizationFPM.run(F, AM);
-      PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
-    }
-
-    // Get the loop structure for this function
-    LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
-
-    // If there are no loops, there is nothing to do here.
-    if (LI.empty())
-      return PA;
-
-    // Get the analysis results needed by loop passes.
-    MemorySSA *MSSA = UseMemorySSA
-                          ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
-                          : nullptr;
-    BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
-                                  ? (&AM.getResult<BlockFrequencyAnalysis>(F))
-                                  : nullptr;
-    LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
-                                       AM.getResult<AssumptionAnalysis>(F),
-                                       AM.getResult<DominatorTreeAnalysis>(F),
-                                       AM.getResult<LoopAnalysis>(F),
-                                       AM.getResult<ScalarEvolutionAnalysis>(F),
-                                       AM.getResult<TargetLibraryAnalysis>(F),
-                                       AM.getResult<TargetIRAnalysis>(F),
-                                       BFI,
-                                       MSSA};
-
-    // Setup the loop analysis manager from its proxy. It is important that
-    // this is only done when there are loops to process and we have built the
-    // LoopStandardAnalysisResults object. The loop analyses cached in this
-    // manager have access to those analysis results and so it must invalidate
-    // itself when they go away.
-    auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
-    if (UseMemorySSA)
-      LAMFP.markMSSAUsed();
-    LoopAnalysisManager &LAM = LAMFP.getManager();
-
-    // A postorder worklist of loops to process.
-    SmallPriorityWorklist<Loop *, 4> Worklist;
-
-    // Register the worklist and loop analysis manager so that loop passes can
-    // update them when they mutate the loop nest structure.
-    LPMUpdater Updater(Worklist, LAM);
-
-    // Add the loop nests in the reverse order of LoopInfo. See method
-    // declaration.
-    appendLoopsToWorklist(LI, Worklist);
-
-#ifndef NDEBUG
-    PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
-      if (isSpecialPass(PassID, {"PassManager"}))
-        return;
-      assert(any_isa<const Loop *>(IR));
-      const Loop *L = any_cast<const Loop *>(IR);
-      assert(L && "Loop should be valid for printing");
-
-      // Verify the loop structure and LCSSA form before visiting the loop.
-      L->verifyLoop();
-      assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
-             "Loops must remain in LCSSA form!");
-    });
-#endif
-
-    do {
-      Loop *L = Worklist.pop_back_val();
-
-      // Reset the update structure for this loop.
-      Updater.CurrentL = L;
-      Updater.SkipCurrentLoop = false;
-
-#ifndef NDEBUG
-      // Save a parent loop pointer for asserts.
-      Updater.ParentL = L->getParentLoop();
-#endif
-      // Check the PassInstrumentation's BeforePass callbacks before running the
-      // pass, skip its execution completely if asked to (callback returns
-      // false).
-      if (!PI.runBeforePass<Loop>(Pass, *L))
-        continue;
-
-      PreservedAnalyses PassPA;
-      {
-        TimeTraceScope TimeScope(Pass.name());
-        PassPA = Pass.run(*L, LAM, LAR, Updater);
-      }
-
-      // Do not pass deleted Loop into the instrumentation.
-      if (Updater.skipCurrentLoop())
-        PI.runAfterPassInvalidated<Loop>(Pass, PassPA);
-      else
-        PI.runAfterPass<Loop>(Pass, *L, PassPA);
-
-      // FIXME: We should verify the set of analyses relevant to Loop passes
-      // are preserved.
-
-      // If the loop hasn't been deleted, we need to handle invalidation here.
-      if (!Updater.skipCurrentLoop())
-        // We know that the loop pass couldn't have invalidated any other
-        // loop's analyses (that's the contract of a loop pass), so directly
-        // handle the loop analysis manager's invalidation here.
-        LAM.invalidate(*L, PassPA);
-
-      // Then intersect the preserved set so that invalidation of module
-      // analyses will eventually occur when the module pass completes.
-      PA.intersect(std::move(PassPA));
-    } while (!Worklist.empty());
-
-#ifndef NDEBUG
-    PI.popBeforeNonSkippedPassCallback();
-#endif
-
-    // By definition we preserve the proxy. We also preserve all analyses on
-    // Loops. This precludes *any* invalidation of loop analyses by the proxy,
-    // but that's OK because we've taken care to invalidate analyses in the
-    // loop analysis manager incrementally above.
-    PA.preserveSet<AllAnalysesOn<Loop>>();
-    PA.preserve<LoopAnalysisManagerFunctionProxy>();
-    // We also preserve the set of standard analyses.
-    PA.preserve<DominatorTreeAnalysis>();
-    PA.preserve<LoopAnalysis>();
-    PA.preserve<ScalarEvolutionAnalysis>();
-    if (UseBlockFrequencyInfo && F.hasProfileData())
-      PA.preserve<BlockFrequencyAnalysis>();
-    if (UseMemorySSA)
-      PA.preserve<MemorySSAAnalysis>();
-    // FIXME: What we really want to do here is preserve an AA category, but
-    // that concept doesn't exist yet.
-    PA.preserve<AAManager>();
-    PA.preserve<BasicAA>();
-    PA.preserve<GlobalsAA>();
-    PA.preserve<SCEVAA>();
-    return PA;
-  }
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   static bool isRequired() { return true; }
 
 private:
-  LoopPassT Pass;
+  std::unique_ptr<PassConceptT> Pass;
 
   FunctionPassManager LoopCanonicalizationFPM;
 
   bool UseMemorySSA = false;
   bool UseBlockFrequencyInfo = false;
 };
 
 /// A function to deduce a loop pass type and wrap it in the templated
 /// adaptor.
 template <typename LoopPassT>
-FunctionToLoopPassAdaptor<LoopPassT>
+FunctionToLoopPassAdaptor
 createFunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false,
                                 bool UseBlockFrequencyInfo = false,
                                 bool DebugLogging = false) {
-  return FunctionToLoopPassAdaptor<LoopPassT>(
-      std::move(Pass), UseMemorySSA, UseBlockFrequencyInfo, DebugLogging);
+  using PassModelT =
+      detail::PassModel<Loop, LoopPassT, PreservedAnalyses, LoopAnalysisManager,
+                        LoopStandardAnalysisResults &, LPMUpdater &>;
+  return FunctionToLoopPassAdaptor(
+      std::make_unique<PassModelT>(std::move(Pass)), UseMemorySSA,
+      UseBlockFrequencyInfo, DebugLogging);
 }
 
 /// Pass for printing a loop's contents as textual IR.
 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
   raw_ostream &OS;
   std::string Banner;
 
 public:

llvm/lib/Analysis/CGSCCPassManager.cpp

PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
   PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
 
   if (DebugLogging)
     dbgs() << "Finished CGSCC pass manager run.\n";
 
   return PA;
 }
 
+PreservedAnalyses
+ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, ModuleAnalysisManager &AM) {
+  // Setup the CGSCC analysis manager from its proxy.
+  CGSCCAnalysisManager &CGAM =
+      AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
+
+  // Get the call graph for this module.
+  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
+
+  // Get Function analysis manager from its proxy.
+  FunctionAnalysisManager &FAM =
+      AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M)->getManager();
+
+  // We keep worklists to allow us to push more work onto the pass manager as
+  // the passes are run.
+  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
+  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
+
+  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
+  // iterating off the worklists.
+  SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
+  SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
+
+  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
+      InlinedInternalEdges;
+
+  CGSCCUpdateResult UR = {
+      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
+      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges,
+      {}};
+
+  // Request PassInstrumentation from analysis manager, will use it to run
+  // instrumenting callbacks for the passes later.
+  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
+
+  PreservedAnalyses PA = PreservedAnalyses::all();
+  CG.buildRefSCCs();
+  for (auto RCI = CG.postorder_ref_scc_begin(),
+            RCE = CG.postorder_ref_scc_end();
+       RCI != RCE;) {
+    assert(RCWorklist.empty() &&
+           "Should always start with an empty RefSCC worklist");
+    // The postorder_ref_sccs range we are walking is lazily constructed, so
+    // we only push the first one onto the worklist. The worklist allows us
+    // to capture *new* RefSCCs created during transformations.
+    //
+    // We really want to form RefSCCs lazily because that makes them cheaper
+    // to update as the program is simplified and allows us to have greater
+    // cache locality as forming a RefSCC touches all the parts of all the
+    // functions within that RefSCC.
+    //
+    // We also eagerly increment the iterator to the next position because
+    // the CGSCC passes below may delete the current RefSCC.
+    RCWorklist.insert(&*RCI++);
+
+    do {
+      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
+      if (InvalidRefSCCSet.count(RC)) {
+        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
+        continue;
+      }
+
+      assert(CWorklist.empty() &&
+             "Should always start with an empty SCC worklist");
+
+      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
+                        << "\n");
+
+      // The top of the worklist may *also* be the same SCC we just ran over
+      // (and invalidated for). Keep track of that last SCC we processed due
+      // to SCC update to avoid redundant processing when an SCC is both just
+      // updated itself and at the top of the worklist.
+      LazyCallGraph::SCC *LastUpdatedC = nullptr;
+
+      // Push the initial SCCs in reverse post-order as we'll pop off the
+      // back and so see this in post-order.
+      for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
+        CWorklist.insert(&C);
+
+      do {
+        LazyCallGraph::SCC *C = CWorklist.pop_back_val();
+        // Due to call graph mutations, we may have invalid SCCs or SCCs from
+        // other RefSCCs in the worklist. The invalid ones are dead and the
+        // other RefSCCs should be queued above, so we just need to skip both
+        // scenarios here.
+        if (InvalidSCCSet.count(C)) {
+          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
+          continue;
+        }
+        if (LastUpdatedC == C) {
+          LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
+          continue;
+        }
+        if (&C->getOuterRefSCC() != RC) {
+          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
+                               "RefSCC...\n");
+          continue;
+        }
+
+        // Ensure we can proxy analysis updates from the CGSCC analysis manager
+        // into the the Function analysis manager by getting a proxy here.
+        // This also needs to update the FunctionAnalysisManager, as this may be
+        // the first time we see this SCC.
+        CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
+            FAM);
+
+        // Each time we visit a new SCC pulled off the worklist,
+        // a transformation of a child SCC may have also modified this parent
+        // and invalidated analyses. So we invalidate using the update record's
+        // cross-SCC preserved set. This preserved set is intersected by any
+        // CGSCC pass that handles invalidation (primarily pass managers) prior
+        // to marking its SCC as preserved. That lets us track everything that
+        // might need invalidation across SCCs without excessive invalidations
+        // on a single SCC.
+        //
+        // This essentially allows SCC passes to freely invalidate analyses
+        // of any ancestor SCC. If this becomes detrimental to successfully
+        // caching analyses, we could force each SCC pass to manually
+        // invalidate the analyses for any SCCs other than themselves which
+        // are mutated. However, that seems to lose the robustness of the
+        // pass-manager driven invalidation scheme.
+        CGAM.invalidate(*C, UR.CrossSCCPA);
+
+        do {
+          // Check that we didn't miss any update scenario.
+          assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
+          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
+          assert(&C->getOuterRefSCC() == RC &&
+                 "Processing an SCC in a different RefSCC!");
+
+          LastUpdatedC = UR.UpdatedC;
+          UR.UpdatedRC = nullptr;
+          UR.UpdatedC = nullptr;
+
+          // Check the PassInstrumentation's BeforePass callbacks before
+          // running the pass, skip its execution completely if asked to
+          // (callback returns false).
+          if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
+            continue;
+
+          PreservedAnalyses PassPA;
+          {
+            TimeTraceScope TimeScope(Pass->name());
+            PassPA = Pass->run(*C, CGAM, CG, UR);
+          }
+
+          if (UR.InvalidatedSCCs.count(C))
+            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
+          else
+            PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
+
+          // Update the SCC and RefSCC if necessary.
+          C = UR.UpdatedC ? UR.UpdatedC : C;
+          RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
+
+          if (UR.UpdatedC) {
+            // If we're updating the SCC, also update the FAM inside the proxy's
+            // result.
+            CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
+                FAM);
+          }
+
+          // If the CGSCC pass wasn't able to provide a valid updated SCC,
+          // the current SCC may simply need to be skipped if invalid.
+          if (UR.InvalidatedSCCs.count(C)) {
+            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
+            break;
+          }
+          // Check that we didn't miss any update scenario.
+          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
+
+          // We handle invalidating the CGSCC analysis manager's information
+          // for the (potentially updated) SCC here. Note that any other SCCs
+          // whose structure has changed should have been invalidated by
+          // whatever was updating the call graph. This SCC gets invalidated
+          // late as it contains the nodes that were actively being
+          // processed.
+          CGAM.invalidate(*C, PassPA);
+
+          // Then intersect the preserved set so that invalidation of module
+          // analyses will eventually occur when the module pass completes.
+          // Also intersect with the cross-SCC preserved set to capture any
+          // cross-SCC invalidation.
+          UR.CrossSCCPA.intersect(PassPA);
+          PA.intersect(std::move(PassPA));
+
+          // The pass may have restructured the call graph and refined the
+          // current SCC and/or RefSCC. We need to update our current SCC and
+          // RefSCC pointers to follow these. Also, when the current SCC is
+          // refined, re-run the SCC pass over the newly refined SCC in order
+          // to observe the most precise SCC model available. This inherently
+          // cannot cycle excessively as it only happens when we split SCCs
+          // apart, at most converging on a DAG of single nodes.
+          // FIXME: If we ever start having RefSCC passes, we'll want to
+          // iterate there too.
+          if (UR.UpdatedC)
+            LLVM_DEBUG(dbgs()
+                       << "Re-running SCC passes after a refinement of the "
+                          "current SCC: "
+                       << *UR.UpdatedC << "\n");
+
+          // Note that both `C` and `RC` may at this point refer to deleted,
+          // invalid SCC and RefSCCs respectively. But we will short circuit
+          // the processing when we check them in the loop above.
+        } while (UR.UpdatedC);
+      } while (!CWorklist.empty());
+
+      // We only need to keep internal inlined edge information within
+      // a RefSCC, clear it to save on space and let the next time we visit
+      // any of these functions have a fresh start.
+      InlinedInternalEdges.clear();
+    } while (!RCWorklist.empty());
+  }
+
+  // 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.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
+  PA.preserve<LazyCallGraphAnalysis>();
+  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+  PA.preserve<FunctionAnalysisManagerModuleProxy>();
+  return PA;
+}
+
+PreservedAnalyses DevirtSCCRepeatedPass::run(LazyCallGraph::SCC &InitialC,
+                                             CGSCCAnalysisManager &AM,
+                                             LazyCallGraph &CG,
+                                             CGSCCUpdateResult &UR) {
+  PreservedAnalyses PA = PreservedAnalyses::all();
+  PassInstrumentation PI =
+      AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
+
+  // The SCC may be refined while we are running passes over it, so set up
+  // a pointer that we can update.
+  LazyCallGraph::SCC *C = &InitialC;
+
+  // Struct to track the counts of direct and indirect calls in each function
+  // of the SCC.
+  struct CallCount {
+    int Direct;
+    int Indirect;
+  };
+
+  // Put value handles on all of the indirect calls and return the number of
+  // direct calls for each function in the SCC.
+  auto ScanSCC = [](LazyCallGraph::SCC &C,
+                    SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {
+    assert(CallHandles.empty() && "Must start with a clear set of handles.");
+
+    SmallDenseMap<Function *, CallCount> CallCounts;
+    CallCount CountLocal = {0, 0};
+    for (LazyCallGraph::Node &N : C) {
+      CallCount &Count =
+          CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
+              .first->second;
+      for (Instruction &I : instructions(N.getFunction()))
+        if (auto *CB = dyn_cast<CallBase>(&I)) {
+          if (CB->getCalledFunction()) {
+            ++Count.Direct;
+          } else {
+            ++Count.Indirect;
+            CallHandles.insert({CB, WeakTrackingVH(CB)});
+          }
+        }
+    }
+
+    return CallCounts;
+  };
+
+  UR.IndirectVHs.clear();
+  // Populate the initial call handles and get the initial call counts.
+  auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
+
+  for (int Iteration = 0;; ++Iteration) {
+    if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
+      continue;
+
+    PreservedAnalyses PassPA = Pass->run(*C, AM, CG, UR);
+
+    if (UR.InvalidatedSCCs.count(C))
+      PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
+    else
+      PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
+
+    // If the SCC structure has changed, bail immediately and let the outer
+    // CGSCC layer handle any iteration to reflect the refined structure.
+    if (UR.UpdatedC && UR.UpdatedC != C) {
+      PA.intersect(std::move(PassPA));
+      break;
+    }
+
+    // Check that we didn't miss any update scenario.
+    assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
+    assert(C->begin() != C->end() && "Cannot have an empty SCC!");
+
+    // Check whether any of the handles were devirtualized.
+    bool Devirt = llvm::any_of(UR.IndirectVHs, [](auto &P) -> bool {
+      if (P.second) {
+        if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
+          if (CB->getCalledFunction()) {
+            LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");
+            return true;
+          }
+        }
+      }
+      return false;
+    });
+
+    // Rescan to build up a new set of handles and count how many direct
+    // calls remain. If we decide to iterate, this also sets up the input to
+    // the next iteration.
+    UR.IndirectVHs.clear();
+    auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);
+
+    // If we haven't found an explicit devirtualization already see if we
+    // have decreased the number of indirect calls and increased the number
+    // of direct calls for any function in the SCC. This can be fooled by all
+    // manner of transformations such as DCE and other things, but seems to
+    // work well in practice.
+    if (!Devirt)
+      // Iterate over the keys in NewCallCounts, if Function also exists in
+      // CallCounts, make the check below.
+      for (auto &Pair : NewCallCounts) {
+        auto &CallCountNew = Pair.second;
+        auto CountIt = CallCounts.find(Pair.first);
+        if (CountIt != CallCounts.end()) {
+          const auto &CallCountOld = CountIt->second;
+          if (CallCountOld.Indirect > CallCountNew.Indirect &&
+              CallCountOld.Direct < CallCountNew.Direct) {
+            Devirt = true;
+            break;
+          }
+        }
+      }
+
+    if (!Devirt) {
+      PA.intersect(std::move(PassPA));
+      break;
+    }
+
+    // Otherwise, if we've already hit our max, we're done.
+    if (Iteration >= MaxIterations) {
+      maxDevirtIterationsReached();
+      LLVM_DEBUG(
+          dbgs() << "Found another devirtualization after hitting the max "
+                    "number of repetitions ("
+                 << MaxIterations << ") on SCC: " << *C << "\n");
+      PA.intersect(std::move(PassPA));
+      break;
+    }
+
+    LLVM_DEBUG(
+        dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
+               << *C << "\n");
+
+    // Move over the new call counts in preparation for iterating.
+    CallCounts = std::move(NewCallCounts);
+
+    // Update the analysis manager with each run and intersect the total set
+    // of preserved analyses so we're ready to iterate.
+    AM.invalidate(*C, PassPA);
+
+    PA.intersect(std::move(PassPA));
+  }
+
+  // Note that we don't add any preserved entries here unlike a more normal
+  // "pass manager" because we only handle invalidation *between* iterations,
+  // not after the last iteration.
+  return PA;
+}
+
+PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,
+                                                  CGSCCAnalysisManager &AM,
+                                                  LazyCallGraph &CG,
+                                                  CGSCCUpdateResult &UR) {
+  // Setup the function analysis manager from its proxy.
+  FunctionAnalysisManager &FAM =
+      AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
+
+  SmallVector<LazyCallGraph::Node *, 4> Nodes;
+  for (LazyCallGraph::Node &N : C)
+    Nodes.push_back(&N);
+
+  // The SCC may get split while we are optimizing functions due to deleting
+  // edges. If this happens, the current SCC can shift, so keep track of
+  // a pointer we can overwrite.
+  LazyCallGraph::SCC *CurrentC = &C;
+
+  LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n");
+
+  PreservedAnalyses PA = PreservedAnalyses::all();
+  for (LazyCallGraph::Node *N : Nodes) {
+    // Skip nodes from other SCCs. These may have been split out during
+    // processing. We'll eventually visit those SCCs and pick up the nodes
+    // there.
+    if (CG.lookupSCC(*N) != CurrentC)
+      continue;
+
+    Function &F = N->getFunction();
+
+    PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
+    if (!PI.runBeforePass<Function>(*Pass, F))
+      continue;
+
+    PreservedAnalyses PassPA;
+    {
+      TimeTraceScope TimeScope(Pass->name());
+      PassPA = Pass->run(F, FAM);
+    }
+
+    PI.runAfterPass<Function>(*Pass, F, PassPA);
+
+    // We know that the function pass couldn't have invalidated any other
+    // function's analyses (that's the contract of a function pass), so
+    // directly handle the function analysis manager's invalidation here.
+    FAM.invalidate(F, PassPA);
+
+    // Then intersect the preserved set so that invalidation of module
+    // analyses will eventually occur when the module pass completes.
+    PA.intersect(std::move(PassPA));
+
+    // If the call graph hasn't been preserved, update it based on this
+    // function pass. This may also update the current SCC to point to
+    // a smaller, more refined SCC.
+    auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
+    if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
+      CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
+                                                            AM, UR, FAM);
+      assert(CG.lookupSCC(*N) == CurrentC &&
+             "Current SCC not updated to the SCC containing the current node!");
+    }
+  }
+
+  // By definition we preserve the proxy. And we preserve all analyses on
+  // Functions. This precludes *any* invalidation of function analyses by the
+  // proxy, but that's OK because we've taken care to invalidate analyses in
+  // the function analysis manager incrementally above.
+  PA.preserveSet<AllAnalysesOn<Function>>();
+  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+
+  // We've also ensured that we updated the call graph along the way.
+  PA.preserve<LazyCallGraphAnalysis>();
+
+  return PA;
+}
+
 bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
     Module &M, const PreservedAnalyses &PA,
     ModuleAnalysisManager::Invalidator &Inv) {
   // If literally everything is preserved, we're done.
   if (PA.areAllPreserved())
     return false; // This is still a valid proxy.
 
   // If this proxy or the call graph is going to be invalidated, we also need

llvm/lib/IR/PassManager.cpp

if (!AreFunctionAnalysesPreserved)
       InnerAM->invalidate(F, PA);
   }
 
   // Return false to indicate that this result is still a valid proxy.
   return false;
 }
 } // namespace llvm
 
+PreservedAnalyses ModuleToFunctionPassAdaptor::run(Module &M,
+                                                   ModuleAnalysisManager &AM) {
+  FunctionAnalysisManager &FAM =
+      AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+
+  // Request PassInstrumentation from analysis manager, will use it to run
+  // instrumenting callbacks for the passes later.
+  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
+
+  PreservedAnalyses PA = PreservedAnalyses::all();
+  for (Function &F : M) {
+    if (F.isDeclaration())
+      continue;
+
+    // Check the PassInstrumentation's BeforePass callbacks before running the
+    // pass, skip its execution completely if asked to (callback returns
+    // false).
+    if (!PI.runBeforePass<Function>(*Pass, F))
+      continue;
+
+    PreservedAnalyses PassPA;
+    {
+      TimeTraceScope TimeScope(Pass->name(), F.getName());
+      PassPA = Pass->run(F, FAM);
+    }
+
+    PI.runAfterPass(*Pass, F, PassPA);
+
+    // We know that the function pass couldn't have invalidated any other
+    // function's analyses (that's the contract of a function pass), so
+    // directly handle the function analysis manager's invalidation here.
+    FAM.invalidate(F, PassPA);
+
+    // Then intersect the preserved set so that invalidation of module
+    // analyses will eventually occur when the module pass completes.
+    PA.intersect(std::move(PassPA));
+  }
+
+  // The FunctionAnalysisManagerModuleProxy is preserved because (we assume)
+  // the function passes we ran didn't add or remove any functions.
+  //
+  // We also preserve all analyses on Functions, because we did all the
+  // invalidation we needed to do above.
+  PA.preserveSet<AllAnalysesOn<Function>>();
+  PA.preserve<FunctionAnalysisManagerModuleProxy>();
+  return PA;
+}
+
 AnalysisSetKey CFGAnalyses::SetKey;
 
 AnalysisSetKey PreservedAnalyses::AllAnalysesKey;

llvm/lib/Passes/StandardInstrumentations.cpp

 PrintIRInstrumentation::popModuleDesc(StringRef PassID) {
   assert(!ModuleDescStack.empty() && "empty ModuleDescStack");
   PrintModuleDesc ModuleDesc = ModuleDescStack.pop_back_val();
   assert(std::get<2>(ModuleDesc).equals(PassID) && "malformed ModuleDescStack");
   return ModuleDesc;
 }
 
 void PrintIRInstrumentation::printBeforePass(StringRef PassID, Any IR) {
-  if (PassID.startswith("PassManager<") || PassID.contains("PassAdaptor<"))
+  if (isIgnored(PassID))
     return;
 
   // Saving Module for AfterPassInvalidated operations.
   // Note: here we rely on a fact that we do not change modules while
   // traversing the pipeline, so the latest captured module is good
   // for all print operations that has not happen yet.
   if (StoreModuleDesc && llvm::shouldPrintAfterPass(PassID))
     pushModuleDesc(PassID, IR);
 
   if (!llvm::shouldPrintBeforePass(PassID))
     return;
 
   SmallString<20> Banner = formatv("*** IR Dump Before {0} ***", PassID);
   unwrapAndPrint(dbgs(), IR, Banner, llvm::forcePrintModuleIR());
   return;
 }
 
 void PrintIRInstrumentation::printAfterPass(StringRef PassID, Any IR) {
-  if (PassID.startswith("PassManager<") || PassID.contains("PassAdaptor<"))
+  if (isIgnored(PassID))
     return;
 
   if (!llvm::shouldPrintAfterPass(PassID))
     return;
 
   if (StoreModuleDesc)
     popModuleDesc(PassID);
 
   SmallString<20> Banner = formatv("*** IR Dump After {0} ***", PassID);
   unwrapAndPrint(dbgs(), IR, Banner, llvm::forcePrintModuleIR());
 }
 
 void PrintIRInstrumentation::printAfterPassInvalidated(StringRef PassID) {
   if (!StoreModuleDesc || !llvm::shouldPrintAfterPass(PassID))
     return;
 
-  if (PassID.startswith("PassManager<") || PassID.contains("PassAdaptor<"))
+  if (isIgnored(PassID))
     return;
 
   const Module *M;
   std::string Extra;
   StringRef StoredPassID;
   std::tie(M, Extra, StoredPassID) = popModuleDesc(PassID);
   // Additional filtering (e.g. -filter-print-func) can lead to module
   // printing being skipped.
static std::string getBisectDescription(Any IR) {
   llvm_unreachable("Unknown wrapped IR type");
 }
 
 void OptBisectInstrumentation::registerCallbacks(
     PassInstrumentationCallbacks &PIC) {
   if (!isEnabled())
     return;
 
-  std::vector<StringRef> SpecialPasses = {"PassManager", "PassAdaptor"};
-
-  PIC.registerShouldRunOptionalPassCallback(
-      [this, SpecialPasses](StringRef PassID, Any IR) {
-        return isSpecialPass(PassID, SpecialPasses) ||
-               checkPass(PassID, getBisectDescription(IR));
-      });
+  PIC.registerShouldRunOptionalPassCallback([this](StringRef PassID, Any IR) {
+    return isIgnored(PassID) || checkPass(PassID, getBisectDescription(IR));
 }
 
 void PrintPassInstrumentation::registerCallbacks(
     PassInstrumentationCallbacks &PIC) {
   if (!DebugLogging)
     return;
 
   std::vector<StringRef> SpecialPasses = {"PassManager"};

llvm/lib/Transforms/Scalar/LoopPassManager.cpp

PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
   // be preserved, but unrolling should invalidate the parent loop's analyses.
   PA.preserveSet<AllAnalysesOn<Loop>>();
 
   if (DebugLogging)
     dbgs() << "Finished Loop pass manager run.\n";
 
   return PA;
 }
+} // namespace llvm
+
+PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
+                                                 FunctionAnalysisManager &AM) {
+  // Before we even compute any loop analyses, first run a miniature function
+  // pass pipeline to put loops into their canonical form. Note that we can
+  // directly build up function analyses after this as the function pass
+  // manager handles all the invalidation at that layer.
+  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
+
+  PreservedAnalyses PA = PreservedAnalyses::all();
+  // Check the PassInstrumentation's BeforePass callbacks before running the
+  // canonicalization pipeline.
+  if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
+    PA = LoopCanonicalizationFPM.run(F, AM);
+    PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
+  }
+
+  // Get the loop structure for this function
+  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
+
+  // If there are no loops, there is nothing to do here.
+  if (LI.empty())
+    return PA;
+
+  // Get the analysis results needed by loop passes.
+  MemorySSA *MSSA =
+      UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) : nullptr;
+  BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
+                                ? (&AM.getResult<BlockFrequencyAnalysis>(F))
+                                : nullptr;
+  LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
+                                     AM.getResult<AssumptionAnalysis>(F),
+                                     AM.getResult<DominatorTreeAnalysis>(F),
+                                     AM.getResult<LoopAnalysis>(F),
+                                     AM.getResult<ScalarEvolutionAnalysis>(F),
+                                     AM.getResult<TargetLibraryAnalysis>(F),
+                                     AM.getResult<TargetIRAnalysis>(F),
+                                     BFI,
+                                     MSSA};
+
+  // Setup the loop analysis manager from its proxy. It is important that
+  // this is only done when there are loops to process and we have built the
+  // LoopStandardAnalysisResults object. The loop analyses cached in this
+  // manager have access to those analysis results and so it must invalidate
+  // itself when they go away.
+  auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
+  if (UseMemorySSA)
+    LAMFP.markMSSAUsed();
+  LoopAnalysisManager &LAM = LAMFP.getManager();
+
+  // A postorder worklist of loops to process.
+  SmallPriorityWorklist<Loop *, 4> Worklist;
+
+  // Register the worklist and loop analysis manager so that loop passes can
+  // update them when they mutate the loop nest structure.
+  LPMUpdater Updater(Worklist, LAM);
+
+  // Add the loop nests in the reverse order of LoopInfo. See method
+  // declaration.
+  appendLoopsToWorklist(LI, Worklist);
+
+#ifndef NDEBUG
+  PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
+    if (isSpecialPass(PassID, {"PassManager"}))
+      return;
+    assert(any_isa<const Loop *>(IR));
+    const Loop *L = any_cast<const Loop *>(IR);
+    assert(L && "Loop should be valid for printing");
+
+    // Verify the loop structure and LCSSA form before visiting the loop.
+    L->verifyLoop();
+    assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
+           "Loops must remain in LCSSA form!");
+  });
+#endif
+
+  do {
+    Loop *L = Worklist.pop_back_val();
+
+    // Reset the update structure for this loop.
+    Updater.CurrentL = L;
+    Updater.SkipCurrentLoop = false;
+
+#ifndef NDEBUG
+    // Save a parent loop pointer for asserts.
+    Updater.ParentL = L->getParentLoop();
+#endif
+    // Check the PassInstrumentation's BeforePass callbacks before running the
+    // pass, skip its execution completely if asked to (callback returns
+    // false).
+    if (!PI.runBeforePass<Loop>(*Pass, *L))
+      continue;
+
+    PreservedAnalyses PassPA;
+    {
+      TimeTraceScope TimeScope(Pass->name());
+      PassPA = Pass->run(*L, LAM, LAR, Updater);
+    }
+
+    // Do not pass deleted Loop into the instrumentation.
+    if (Updater.skipCurrentLoop())
+      PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
+    else
+      PI.runAfterPass<Loop>(*Pass, *L, PassPA);
+
+    // FIXME: We should verify the set of analyses relevant to Loop passes
+    // are preserved.
+
+    // If the loop hasn't been deleted, we need to handle invalidation here.
+    if (!Updater.skipCurrentLoop())
+      // We know that the loop pass couldn't have invalidated any other
+      // loop's analyses (that's the contract of a loop pass), so directly
+      // handle the loop analysis manager's invalidation here.
+      LAM.invalidate(*L, PassPA);
+
+    // Then intersect the preserved set so that invalidation of module
+    // analyses will eventually occur when the module pass completes.
+    PA.intersect(std::move(PassPA));
+  } while (!Worklist.empty());
+
+#ifndef NDEBUG
+  PI.popBeforeNonSkippedPassCallback();
+#endif
+
+  // By definition we preserve the proxy. We also preserve all analyses on
+  // Loops. This precludes *any* invalidation of loop analyses by the proxy,
+  // but that's OK because we've taken care to invalidate analyses in the
+  // loop analysis manager incrementally above.
+  PA.preserveSet<AllAnalysesOn<Loop>>();
+  PA.preserve<LoopAnalysisManagerFunctionProxy>();
+  // We also preserve the set of standard analyses.
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LoopAnalysis>();
+  PA.preserve<ScalarEvolutionAnalysis>();
+  if (UseBlockFrequencyInfo && F.hasProfileData())
+    PA.preserve<BlockFrequencyAnalysis>();
+  if (UseMemorySSA)
+    PA.preserve<MemorySSAAnalysis>();
+  // FIXME: What we really want to do here is preserve an AA category, but
+  // that concept doesn't exist yet.
+  PA.preserve<AAManager>();
+  PA.preserve<BasicAA>();
+  PA.preserve<GlobalsAA>();
+  PA.preserve<SCEVAA>();
+  return PA;
 }
 
 PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
 PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
     : OS(OS), Banner(Banner) {}
 
 PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &,
                                      LoopStandardAnalysisResults &,
                                      LPMUpdater &) {
   printLoop(L, OS, Banner);
   return PreservedAnalyses::all();
 }

llvm/test/Other/change-printer.ll

 ; CHECK-SIMPLE-NEXT: ; ModuleID = {{.+}}
 ; CHECK-SIMPLE: *** IR Dump After VerifierPass (module) omitted because no change ***
 ; CHECK-SIMPLE: *** IR Dump After InstSimplifyPass *** (function: g)
 ; CHECK-SIMPLE-NEXT: define i32 @g()
 ; CHECK-SIMPLE: *** IR Pass PassManager{{.*}} (function: g) ignored ***
 ; CHECK-SIMPLE: *** IR Dump After InstSimplifyPass *** (function: f)
 ; CHECK-SIMPLE-NEXT: define i32 @f()
 ; CHECK-SIMPLE: *** IR Pass PassManager{{.*}} (function: f) ignored ***
-; CHECK-SIMPLE: *** IR Pass ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}> (module) ignored ***
+; CHECK-SIMPLE: *** IR Pass ModuleToFunctionPassAdaptor (module) ignored ***
 ; CHECK-SIMPLE: *** IR Dump After VerifierPass (module) omitted because no change ***
 ; CHECK-SIMPLE: *** IR Dump After PrintModulePass (module) omitted because no change ***
 ; CHECK-SIMPLE-NOT: *** IR
 
 ; CHECK-FUNC-FILTER: *** IR Dump At Start: ***
 ; CHECK-FUNC-FILTER-NEXT: ; ModuleID = {{.+}}
 ; CHECK-FUNC-FILTER: *** IR Dump After InstSimplifyPass (function: g) filtered out ***
 ; CHECK-FUNC-FILTER: *** IR Dump After InstSimplifyPass *** (function: f)

 ; CHECK-SIMPLE-BEFORE: *** IR Dump After InstSimplifyPass *** (function: g)
 ; CHECK-SIMPLE-BEFORE-NEXT: define i32 @g()
 ; CHECK-SIMPLE-BEFORE: *** IR Pass PassManager{{.*}} (function: g) ignored ***
 ; CHECK-SIMPLE-BEFORE: *** IR Dump Before InstSimplifyPass *** (function: f)
 ; CHECK-SIMPLE-BEFORE-NEXT: define i32 @f()
 ; CHECK-SIMPLE-BEFORE: *** IR Dump After InstSimplifyPass *** (function: f)
 ; CHECK-SIMPLE-BEFORE-NEXT: define i32 @f()
 ; CHECK-SIMPLE-BEFORE: *** IR Pass PassManager{{.*}} (function: f) ignored ***
-; CHECK-SIMPLE-BEFORE: *** IR Pass ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}> (module) ignored ***
+; CHECK-SIMPLE-BEFORE: *** IR Pass ModuleToFunctionPassAdaptor (module) ignored ***
 ; CHECK-SIMPLE-BEFORE: *** IR Dump After VerifierPass (module) omitted because no change ***
 ; CHECK-SIMPLE-BEFORE: *** IR Dump After PrintModulePass (module) omitted because no change ***
 ; CHECK-SIMPLE-BEFORE-NOT: *** IR
 
 ; CHECK-FUNC-FILTER-BEFORE: *** IR Dump At Start: ***
 ; CHECK-FUNC-FILTER-BEFORE-NEXT: ; ModuleID = {{.+}}
 ; CHECK-FUNC-FILTER-BEFORE: *** IR Dump After InstSimplifyPass (function: g) filtered out ***
 ; CHECK-FUNC-FILTER-BEFORE: *** IR Dump Before InstSimplifyPass *** (function: f)

llvm/test/Other/pass-pipeline-parsing.ll

 ; CHECK-NESTED-FP-LP: Finished Loop pass manager run
 ; CHECK-NESTED-FP-LP: Finished llvm::Function pass manager run
 ; CHECK-NESTED-FP-LP: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager -debug-pass-manager-verbose \
 ; RUN:     -passes='module(no-op-function,no-op-loop,no-op-cgscc,cgscc(no-op-function,no-op-loop),function(no-op-loop))' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-ADAPTORS
 ; CHECK-ADAPTORS: Starting llvm::Module pass manager run
-; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor<{{.*}}NoOpFunctionPass>
+; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor
 ; CHECK-ADAPTORS: Running pass: NoOpFunctionPass
-; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor<{{.*}}FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass>{{.*}}>
-; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass>
+; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor
+; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor
 ; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop
-; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}NoOpCGSCCPass>
+; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor
 ; CHECK-ADAPTORS: Running pass: NoOpCGSCCPass
-; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}LazyCallGraph{{.*}}>
+; CHECK-ADAPTORS: Running pass: ModuleToPostOrderCGSCCPassAdaptor
 ; CHECK-ADAPTORS: Starting CGSCC pass manager run
-; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}NoOpFunctionPass>
+; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor
 ; CHECK-ADAPTORS: Running pass: NoOpFunctionPass
-; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass>{{.*}}>
-; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass>
+; CHECK-ADAPTORS: Running pass: CGSCCToFunctionPassAdaptor
+; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor
 ; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop
 ; CHECK-ADAPTORS: Finished CGSCC pass manager run
-; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
+; CHECK-ADAPTORS: Running pass: ModuleToFunctionPassAdaptor
 ; CHECK-ADAPTORS: Starting llvm::Function pass manager run
-; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor<{{.*}}NoOpLoopPass>
+; CHECK-ADAPTORS: Running pass: FunctionToLoopPassAdaptor
 ; CHECK-ADAPTORS: Running pass: NoOpLoopPass on Loop at depth 1 containing: %loop
 ; CHECK-ADAPTORS: Finished llvm::Function pass manager run
 ; CHECK-ADAPTORS: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager \
 ; RUN:     -passes='cgscc(print)' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-PRINT-IN-CGSCC
 ; CHECK-PRINT-IN-CGSCC: Starting llvm::Module pass manager run