Create LoopNestPass

[TaWeiTu]

Summary

Per http://llvm.org/OpenProjects.html#llvm_loopnest, the goal of this patch is to create facilities that allow implementing loop nest passes that run on top-level loop nests for the New Pass Manager.

Under the design, the loop nest passes will have a run method with the following signature:

PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM, LoopStandardAnalysisResults &AR, LNPMUpdater &U);

LNPMUpdater (short for loop nest pass manager updater) supports invalidating loop nests (markLoopNestAsDeleted), re-visiting the current loop nest (revisitCurrentLoopNest) and adding new top-level loop nests to the function (addNewLoopNests).

The loop nest passes can be grouped together by LoopNestPassManager, and then embedded into an FPM via FunctionToLoopNestPassAdaptor. Since both FunctionToLoopNestPassAdaptor and FunctionToLoopPassAdaptor require loop canonicalization passes to be run first, the LoopNestToLoopPassAdaptor is also introduced in the patch.
The intended usage of the adaptor is to group the loop passes together into an LPM first, and then embed the LPM into LoopNestPassManager. With this, the loop canonicalization phase will be run only once for both loop and loop nest passes. One example is as follows:

LoopPassManager LPM;
LPM.addPass(SomeLoopPass());
LoopNestPassManager LNPM;
LNPM.addPass(SomeLoopNestPass());
LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM)));
FunctionPassManager FPM;
FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));

Note that the loop nest pass should explicitly preserve the LoopNestAnalysis (or just returns PreservedAnalyses::all()) if it does not modify the loop structures. Otherwise, the LoopNest object will be re-built every time a loop nest gets revisited.

Currently, the LoopNestAnalysisManager is nothing but a wrapper around LoopAnalysisManager (the former holds a reference to the latter) that provides the APIs on LoopNest and forwards the requests to the internal LPM. That is, the loop nest analyses should still be implemented as loop analyses, and the run method of the analysis receives the root loop of the corresponding loop nest.
The reason behind the design is that we do not support updating the LoopNest object dynamically yet. That means the LoopNest object will be constantly invalidated by the loop nest passes and loop passes, and invalidating a LoopNest structure means that we have to invalidate all analyses associated with it. This is quite inefficient since the analyses might have the ability to be maintained online.

There is no LoopAnalysisManagerLoopNestProxy since the two analysis managers are essentially the same thing. However, LoopNestAnalysisManager still provides a getter getLoopAnalysisManager() to extract the internal LAM. The invalidate() method of LoopNestAnalysisManager comprises two steps: firstly, the "loop analyses" of loops in the subtree are invalidated (one can preserve all analyses on Loop to avoid this), and secondly, the loop analyses and loop nest analyses of the root loop are invalidated. This is similar to what the inner proxies offer.

Other facilities like parsing the pipeline, the proxies between analysis managers, are also implemented in this patch. The PassBuilderCallbacksTest has also been applied to loop-nest-related infrastructures. The actual functionalities of the components, however, are not tested yet. Still, embedding loop passes into LNPM seems to be working as I've modified some existing loop-pass related tests to verify the results. Also, all the existing unit-tests and regression-tests work, so at least this is not breaking anything now.

Though we definitely need more testing on the functionalities, I would like the submit the diff earlier to see what you think about the patch and the design. Fine-grained tests will be added later.

Please kindly provide feedback and comments on the patch. Thank you very much!

[TaWeiTu]

Fix several pre-merge checks.

[TaWeiTu]

Fix LOOP_NEST_ANALYSIS macro, clang-tidy warnings. Rebase.

[TaWeiTu]

Fix loop deletion and rotation tests.

[TaWeiTu]

This comment was removed by TaWeiTu.

[TaWeiTu]

Propagate the requirement of MemorySSA from loop passes to loop nest passes.

[TaWeiTu]

Fix LoopRotate/pr35210.ll (sync with commit b36c39260edcded47436f344e48f78cfbedac494).

[ychen]

I think this needs unit tests like LoopPassManagerTest.cpp (in that file or a similarly named file) to demonstrate the expected behavior: the expected usage comparing with LoopPass/LoopAnalysisPass, how the adaptor is used and the invalidation interaction within its pass manager and other pass managers.

[TaWeiTu]

Add basic unit-tests to test and demonstrate the functionality of loop-nest-pass-related infrastructure (LoopNestPassManagerTest.cpp). Still working on more tests.

I've also updated the description of the patch that contains the intended usage and more details about the implemented components.

[TaWeiTu]

Add tests about invalidating the analysis results and clearing the result cache.

[TaWeiTu]

Fix bug of holding dangling LoopNest references.

[TaWeiTu]

Test the functionality of addNewLoopNests().
Fix LoopNestAnalysis invalidation bugs.

[TaWeiTu]

Ping.

@ychen Thank you for your comment! I've added some unittests. Please let me know if there's anything unclear about the intended usage.

[ychen]

Hello, sorry for the late reply. I have some high-level questions

• What are existing and future loop passes/analyses that could benefit from using LoopNestPass?
• I'd feel more comfortable if existing loop pass/analysis managers could be extended to handle LoopNestPass, rather than have separate full-fledged managers. Implementation aside, this models the idea that loopnest is just a special kind of loop, not a fundamental different IR unit. Have you thought about the alternative design of adding new adaptors or extending existing loop managers to run/query/invalidate loopnest passes?
• I'm not sure how common loopnest analyses are or will be? What's your opinion?

[TaWeiTu]

@ychen Again, thanks for your comment!

1. Currently, LoopInterchange returns immediately if the loop is not a top-level one. The main purpose of the loop nest pass is to prevent situations like this and possibly save compiling time of uninteresting calls to run.
2. I agree with you that it would be better if the implementation can be extended from the existing ones, and yes, I've thought about and tried to incorporate the loop nest passes into the loop pass manager. Based on the discussion with @Whitney and @etiotto on the mailing list https://lists.llvm.org/pipermail/llvm-dev/2020-July/143528.html, the loop nest passes should run on LoopNest objects. I will try to explain the necessity (in my opinion) of each component in this patch on this basis:

• LNPMUpdater: different from LPMUpdater in what it does.
• FunctionToLoopNestPassAdaptor: FunctionToLoopPassAdaptorwith some modifications. IMO it's less confusing to implement it separately than adding a bunch of ifs.
• LoopNestPassManager: this one is a bit tricky. If we follow the convention that <IR>PassManager should be a <IR> pass (having the same run method that operates on the same object, LoopNest in this case), then I think it's better to implement it differently because we have to deal with the possible invalidation of LoopNest object, given the fundamental difference between LoopNest (being an analysis result) and Loop (being an IR unit). The alternative is to have it operating on Loop instead, but that will break the convention. I'm not sure whether the latter will be better, what's your opinion on that?
• LoopNestToLoopPassAdaptor: this is to prevent loop canonicalization passes from running twice as mentioned in the patch description.

In conclusion, I think it's possible to refactor the existing components to achieve the same goal, but IMO that would probably increase the complexity and readability of these components than having a separate implementation. I'm not sure if it's the right tradeoff.

3. The term "loop nest analyses" is just saying that they will only run on top-level loops. They are essentially the same as loop analyses. The LoopNestAnalysisManager only provides an API for getting the analysis results from the LoopNest objects. Having LOOP_NEST_ANALYSIS section in PassRegistry.def is just to distinguish between analyses that should be run on all loops and the ones that should only be run on top-level loops. I currently don't think of any loop analyses that fall into this category, though.

[fhahn]

In D84886#2212202, @TaWeiTu wrote:

@ychen Again, thanks for your comment!

1. Currently, LoopInterchange returns immediately if the loop is not a top-level one. The main purpose of the loop nest pass is to prevent situations like this and possibly save compiling time of uninteresting calls to run.

I think it would be good to convert 1 or 2 passes to use the new system and evaluate the potential benefits (reduced compile-time, better results).

[Whitney]

Examples of existing transformations that can be benefited from LoopNestPass: LoopInterchange, LoopUnrollAndJam, LoopIdiom, LoopDistribution, ...
And their corresponding cost model analyses can be benefited from LoopNestAnalysis, e.g. LoopCacheCost.

[TaWeiTu]

Hi @Whitney, @fhahn, @ychen, thank you all for your comments and suggestions! Sorry for the late reply.
I was trying to convert the LoopInterchange pass into a loop-nest pass. However, there seems to be no corresponding loop pass for the NPM.
Any particular reason for this?

[Whitney]

I was trying to convert the LoopInterchange pass into a loop-nest pass. However, there seems to be no corresponding loop pass for the NPM.
Any particular reason for this?

That's true, LoopInterchange pass is not already ported to the NPM, likely because no one needed it in the NPM. Maybe you want to convert another pass to loop-nest pass as the first loop-nest pass, or you will have to port it to NPM first.

[TaWeiTu]

Hi, thanks for your comments and suggestions!

I've thought about the suggestion by @ychen to extend the existing LoopPassManager to handle loop-nest passes instead of having a separate LoopNestPassManager, and I've uploaded a new patch D87045 that implements the basic functionalities of running loop-nest passes in LoopPassManager.
I've also added you as reviewers to the new patch, and I will work on the follow-up patches if you think that direction is better.

Meanwhile, I'll also be working on evaluating the benefits of using loop-nest passes, as @fhahn suggested. But as far as I understand, most passes that may potentially benefit from loop-nest passes require certain algorithmic changes that incorporate the information of perfectly-nested loops provided by the LoopNest object first. So it will probably take more time to investigate those passes and convert those passes using the new facilities.

clang/lib/CodeGen/BackendUtil.cpp

if (PassPlugin) {
           << PluginFN << toString(PassPlugin.takeError());
     }
   }
 #define HANDLE_EXTENSION(Ext)                                                  \
   get##Ext##PluginInfo().RegisterPassBuilderCallbacks(PB);
 #include "llvm/Support/Extension.def"
 
   LoopAnalysisManager LAM(CodeGenOpts.DebugPassManager);
+  LoopNestAnalysisManager LNAM(LAM, CodeGenOpts.DebugPassManager);
   FunctionAnalysisManager FAM(CodeGenOpts.DebugPassManager);
   CGSCCAnalysisManager CGAM(CodeGenOpts.DebugPassManager);
   ModuleAnalysisManager MAM(CodeGenOpts.DebugPassManager);
 
   // Register the AA manager first so that our version is the one used.
   FAM.registerPass([&] { return PB.buildDefaultAAPipeline(); });
 
   // Register the target library analysis directly and give it a customized
   // preset TLI.
   Triple TargetTriple(TheModule->getTargetTriple());
   std::unique_ptr<TargetLibraryInfoImpl> TLII(
       createTLII(TargetTriple, CodeGenOpts));
   FAM.registerPass([&] { return TargetLibraryAnalysis(*TLII); });
 
   // Register all the basic analyses with the managers.
   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
   PB.registerLoopAnalyses(LAM);
-  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+  PB.registerLoopNestAnalyses(LNAM);
+  PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
 
   ModulePassManager MPM(CodeGenOpts.DebugPassManager);
 
   if (!CodeGenOpts.DisableLLVMPasses) {
     bool IsThinLTO = CodeGenOpts.PrepareForThinLTO;
     bool IsLTO = CodeGenOpts.PrepareForLTO;
 
     if (CodeGenOpts.OptimizationLevel == 0) {

llvm/include/llvm/Analysis/LoopNestAnalysis.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LOOPNESTANALYSIS_H
 #define LLVM_ANALYSIS_LOOPNESTANALYSIS_H
 
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 using LoopVectorTy = SmallVector<Loop *, 8>;
 class LPMUpdater;
 
 /// This class represents a loop nest and can be used to query its properties.
 class LoopNest {
public:
   unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
 
   /// Return true if all loops in the loop nest are in simplify form.
   bool areAllLoopsSimplifyForm() const {
     return llvm::all_of(Loops,
                         [](const Loop *L) { return L->isLoopSimplifyForm(); });
   }
 
+  StringRef getName() const {
+    // FIXME: Choose a better name for loop nests so that they are
+    // distinguishable from the loops' names.
+    Loop &Root = getOutermostLoop();
+    return Root.getName();
+  }
+
+  /// Reconstruct the loop nest inplace.
+  void reconstructInplace(ScalarEvolution &SE);
+
 protected:
-  const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
+  unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
   LoopVectorTy Loops; // the loops in the nest (in breadth first order).
 };
 
 raw_ostream &operator<<(raw_ostream &, const LoopNest &);
 
 /// This analysis provides information for a loop nest. The analysis runs on
 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {

llvm/include/llvm/Analysis/LoopNestAnalysisManager.h

+//===- LoopNestAnalysisManager.h - LoopNest analysis management ---------*- C++
+//-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H
+#define LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H
+
+#include "llvm/Analysis/LoopNestAnalysis.h"
+#include "llvm/IR/PassManager.h"
+#include <type_traits>
+
+namespace llvm {
+
+class LNPMUpdater;
+
+/// The loop nest analysis manager.
+///
+/// The loop nest analyses should run on \Loop instead of LoopNests since
+/// \c LoopNest are constantly invalidated by both loop nest passes and loop
+/// passes. Generally speaking, the passes should update the analysis results
+/// dynamically when possible, and running on Loops prevent the analyses from
+/// being invalidated when the loop structures change.
+///
+/// \c LoopNestAnalysisManager is a wrapper around \c LoopAnalysisManager and
+/// provide all the public APIs that \c AnalysisManager has so that is seems to
+/// be operating on \c LoopNest. \c LoopNestAnalysisManager also provides the
+/// ability to construct \c LoopNest from the top-level \c Loop.
+///
+/// However, the result of \c LoopNestAnaysis (\c LoopNest) is maintained in a
+/// separate loop analysis manager. This prevents the loop passes from
+/// accidently invalidating the \c LoopNest object to which the top-level loop
+/// nest pass manager still holds reference.
+///
+/// The \c LoopNest object will be invalidated after the loop nest passes unless
+/// \c LoopNestAnalysis is explicitly marked as preserved.
+template <> class AnalysisManager<LoopNest, LoopStandardAnalysisResults &> {
+public:
+  class Invalidator {
+  public:
+    /// The following methods should never be called because the
+    /// invalidation in \c LoopNestAnalysisManager will be passed to the
+    /// internal \c LoopAnalysisManager. The only purpose of these methods is to
+    /// satisfy the requirements of being an \c AnalysisManager.
+    template <typename PassT>
+    bool invalidate(LoopNest &, const PreservedAnalyses &) {
+      assert(false && "This method should never be called.");
+      return false;
+    }
+
+    bool invalidate(AnalysisKey *, LoopNest &, const PreservedAnalyses &) {
+      assert(false && "This method should never be called.");
+      return false;
+    }
+  };
+
+  AnalysisManager(LoopAnalysisManager &LAM, bool DebugLogging = false)
+      : InternalLAM(LAM), LoopNestManager(DebugLogging) {}
+
+  bool empty() const { return InternalLAM.empty() && LoopNestManager.empty(); };
+
+  void clear(LoopNest &LN, llvm::StringRef Name) {
+    InternalLAM.clear(LN.getOutermostLoop(), Name);
+    LoopNestManager.clear(LN.getOutermostLoop(), Name);
+  }
+  void clear(Loop &L, llvm::StringRef Name) {
+    InternalLAM.clear(L, Name);
+    LoopNestManager.clear(L, Name);
+  }
+  void clear() {
+    InternalLAM.clear();
+    LoopNestManager.clear();
+  }
+
+  /// Get the result of an analysis pass for a given LoopNest.
+  ///
+  /// Runs the analysis if a cached result is not available.
+  template <typename PassT>
+  typename PassT::Result &getResult(LoopNest &LN,
+                                    LoopStandardAnalysisResults &LAR) {
+    return InternalLAM.getResult<PassT>(LN.getOutermostLoop(), LAR);
+  }
+  template <typename PassT>
+  typename PassT::Result &getResult(Loop &L, LoopStandardAnalysisResults &LAR) {
+    return InternalLAM.getResult<PassT>(L, LAR);
+  }
+
+  /// Get the cached result of an analysis pass for a given LoopNest.
+  ///
+  /// This method never runs the analysis.
+  ///
+  /// \returns null if there is no cached result.
+  template <typename PassT>
+  typename PassT::Result *getCachedResult(LoopNest &LN) const {
+    return InternalLAM.getCachedResult<PassT>(LN.getOutermostLoop());
+  }
+  template <typename PassT>
+  typename PassT::Result *getCachedResult(Loop &L) const {
+    return InternalLAM.getCachedResult<PassT>(L);
+  }
+
+  template <>
+  LoopNest &getResult<LoopNestAnalysis>(LoopNest &LN,
+                                        LoopStandardAnalysisResults &LAR) {
+    return LoopNestManager.getResult<LoopNestAnalysis>(LN.getOutermostLoop(),
+                                                       LAR);
+  }
+  template <>
+  LoopNest &getResult<LoopNestAnalysis>(Loop &L,
+                                        LoopStandardAnalysisResults &LAR) {
+    return LoopNestManager.getResult<LoopNestAnalysis>(L, LAR);
+  }
+  template <> LoopNest *getCachedResult<LoopNestAnalysis>(LoopNest &LN) const {
+    return LoopNestManager.getCachedResult<LoopNestAnalysis>(
+        LN.getOutermostLoop());
+  }
+  template <> LoopNest *getCachedResult<LoopNestAnalysis>(Loop &L) const {
+    return LoopNestManager.getCachedResult<LoopNestAnalysis>(L);
+  }
+
+  template <typename PassT>
+  void verifyNotInvalidated(LoopNest &LN,
+                            typename PassT::Result *Result) const {
+    InternalLAM.verifyNotInvalidated<PassT>(LN.getOutermostLoop(), Result);
+  }
+
+  template <typename PassBuilderT>
+  auto registerPass(PassBuilderT &&PassBuilder) -> typename std::enable_if<
+      !std::is_same<LoopNestAnalysis, decltype(PassBuilder())>::value &&
+          !std::is_same<PassInstrumentationAnalysis,
+                        decltype(PassBuilder())>::value,
+      bool>::type {
+    return InternalLAM.registerPass(std::forward<PassBuilderT>(PassBuilder));
+  }
+
+  /// Registration of LoopNestAnalysis should be forwarded to the loop nest
+  /// manager instead. The SFINAE expression is to ensure that PassBuilder() is
+  /// of type LoopNestAnalysis.
+  template <typename PassBuilderT>
+  auto registerPass(PassBuilderT &&PassBuilder) -> typename std::enable_if<
+      std::is_same<LoopNestAnalysis, decltype(PassBuilder())>::value ||
+          std::is_same<PassInstrumentationAnalysis,
+                       decltype(PassBuilder())>::value,
+      bool>::type {
+    return LoopNestManager.registerPass(
+        std::forward<PassBuilderT>(PassBuilder));
+  }
+
+  /// Invalidate the analysis results. Aside from the loop nest analyses of the
+  /// root loop, we have to invalidate the loop analyses of all the subtree as
+  /// well.
+  void invalidate(LoopNest &LN, const PreservedAnalyses &PA) {
+    Loop &L = LN.getOutermostLoop();
+    invalidateSubLoopAnalyses(L, PA);
+    InternalLAM.invalidate(L, PA);
+    LoopNestManager.invalidate(L, PA);
+  }
+  void invalidate(Loop &L, const PreservedAnalyses &PA) {
+    invalidateSubLoopAnalyses(L, PA);
+    InternalLAM.invalidate(L, PA);
+    LoopNestManager.invalidate(L, PA);
+  }
+
+  LoopAnalysisManager &getLoopAnalysisManager() { return InternalLAM; }
+
+private:
+  LoopAnalysisManager &InternalLAM;
+  LoopAnalysisManager LoopNestManager;
+  friend class InnerAnalysisManagerProxy<
+      AnalysisManager<LoopNest, LoopStandardAnalysisResults &>, Function>;
+
+  /// Invalidate the loop analyses of loops in the subtree rooted at \p L
+  /// (excluding \p L).
+  void invalidateSubLoopAnalyses(Loop &L, const PreservedAnalyses &PA);
+};
+
+using LoopNestAnalysisManager =
+    AnalysisManager<LoopNest, LoopStandardAnalysisResults &>;
+using LoopNestAnalysisManagerFunctionProxy =
+    InnerAnalysisManagerProxy<LoopNestAnalysisManager, Function>;
+
+/// A specialized result for the \c LoopNestAnalysisManagerFunctionProxy which
+/// retains a \c LoopInfo reference.
+///
+/// This allows it to collect loop nest objects for which analysis results may
+/// be cached in the \c LoopNestAnalysisManager.
+template <> class LoopNestAnalysisManagerFunctionProxy::Result {
+public:
+  explicit Result(LoopNestAnalysisManager &InnerAM, LoopInfo &LI)
+      : InnerAM(&InnerAM), LI(&LI), MSSAUsed(false) {}
+  Result(Result &&Arg)
+      : InnerAM(std::move(Arg.InnerAM)), LI(Arg.LI), MSSAUsed(Arg.MSSAUsed) {
+    // 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.InnerAM = nullptr;
+  }
+  Result &operator=(Result &&RHS) {
+    InnerAM = RHS.InnerAM;
+    LI = RHS.LI;
+    MSSAUsed = RHS.MSSAUsed;
+    // 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.InnerAM = nullptr;
+    return *this;
+  }
+  ~Result() {
+    // 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.
+    InnerAM->clear();
+  }
+
+  /// Mark MemorySSA as used so we can invalidate self if MSSA is invalidated.
+  void markMSSAUsed() { MSSAUsed = true; }
+
+  /// Accessor for the analysis manager.
+  LoopNestAnalysisManager &getManager() { return *InnerAM; }
+
+  /// Handler for invalidation of the proxy for a particular function.
+  ///
+  /// If the proxy, \c LoopInfo, and associated analyses are preserved, this
+  /// will merely forward the invalidation event to any cached loop analysis
+  /// results for loops within this function.
+  ///
+  /// If the necessary loop infrastructure is not preserved, this will forcibly
+  /// clear all of the cached analysis results that are keyed on the \c
+  /// LoopInfo for this function.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &Inv);
+
+private:
+  LoopNestAnalysisManager *InnerAM;
+  LoopInfo *LI;
+  bool MSSAUsed;
+};
+
+template <>
+LoopNestAnalysisManagerFunctionProxy::Result
+LoopNestAnalysisManagerFunctionProxy::run(Function &F,
+                                          FunctionAnalysisManager &AM);
+
+extern template class InnerAnalysisManagerProxy<LoopNestAnalysisManager,
+                                                Function>;
+extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
+                                                LoopStandardAnalysisResults &>;
+using FunctionAnalysisManagerLoopNestProxy =
+    OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
+                              LoopStandardAnalysisResults &>;
+
+} // namespace llvm
+
+#endif // LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H

llvm/include/llvm/Passes/PassBuilder.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_PASSES_PASSBUILDER_H
 #define LLVM_PASSES_PASSBUILDER_H
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/LoopNestAnalysisManager.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/Instrumentation.h"
+#include "llvm/Transforms/Scalar/LoopNestPassManager.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include <vector>
 
 namespace llvm {
 class StringRef;
 class AAManager;
 class TargetMachine;
 class ModuleSummaryIndex;
explicit PassBuilder(TargetMachine *TM = nullptr,
                        PassInstrumentationCallbacks *PIC = nullptr)
       : TM(TM), PTO(PTO), PGOOpt(PGOOpt), PIC(PIC) {}
 
   /// Cross register the analysis managers through their proxies.
   ///
   /// This is an interface that can be used to cross register each
   /// AnalysisManager with all the others analysis managers.
   void crossRegisterProxies(LoopAnalysisManager &LAM,
+                            LoopNestAnalysisManager &LNAM,
                             FunctionAnalysisManager &FAM,
                             CGSCCAnalysisManager &CGAM,
                             ModuleAnalysisManager &MAM);
 
   /// Registers all available module analysis passes.
   ///
   /// This is an interface that can be used to populate a \c
   /// ModuleAnalysisManager with all registered module analyses. Callers can
public:
 
   /// Registers all available loop analysis passes.
   ///
   /// This is an interface that can be used to populate a \c LoopAnalysisManager
   /// with all registered loop analyses. Callers can still manually register any
   /// additional analyses.
   void registerLoopAnalyses(LoopAnalysisManager &LAM);
 
+  /// Registers all available loop nest analysis passes.
+  ///
+  /// This is an interface that can be used to populate a \c
+  /// LoopNestAnalysisManager with all registered loop nest analyses. Callers
+  /// can still manually register any additional analyses.
+  void registerLoopNestAnalyses(LoopNestAnalysisManager &LNAM);
+
   /// Construct the core LLVM function canonicalization and simplification
   /// pipeline.
   ///
   /// This is a long pipeline and uses most of the per-function optimization
   /// passes in LLVM to canonicalize and simplify the IR. It is suitable to run
   /// repeatedly over the IR and is not expected to destroy important
   /// information about the semantics of the IR.
   ///
Error parsePassPipeline(CGSCCPassManager &CGPM, StringRef PipelineText,
                           bool VerifyEachPass = true,
                           bool DebugLogging = false);
   Error parsePassPipeline(FunctionPassManager &FPM, StringRef PipelineText,
                           bool VerifyEachPass = true,
                           bool DebugLogging = false);
   Error parsePassPipeline(LoopPassManager &LPM, StringRef PipelineText,
                           bool VerifyEachPass = true,
                           bool DebugLogging = false);
+  Error parsePassPipeline(LoopNestPassManager &LNPM, StringRef PipelineText,
+                          bool &UseMemorySSA, bool VerifyEachPass = true,
+                          bool DebugLogging = false);
   /// @}}
 
   /// Parse a textual alias analysis pipeline into the provided AA manager.
   ///
   /// The format of the textual AA pipeline is a comma separated list of AA
   /// pass names:
   ///
   ///   basic-aa,globals-aa,...
void registerAnalysisRegistrationCallback(
       const std::function<void(FunctionAnalysisManager &)> &C) {
     FunctionAnalysisRegistrationCallbacks.push_back(C);
   }
   void registerAnalysisRegistrationCallback(
       const std::function<void(LoopAnalysisManager &)> &C) {
     LoopAnalysisRegistrationCallbacks.push_back(C);
   }
   void registerAnalysisRegistrationCallback(
+      const std::function<void(LoopNestAnalysisManager &)> &C) {
+    LoopNestAnalysisRegistrationCallbacks.push_back(C);
+  }
+  void registerAnalysisRegistrationCallback(
       const std::function<void(ModuleAnalysisManager &)> &C) {
     ModuleAnalysisRegistrationCallbacks.push_back(C);
   }
   /// @}}
 
   /// {{@ Register pipeline parsing callbacks with this pass builder instance.
   /// Using these callbacks, callers can parse both a single pass name, as well
   /// as entire sub-pipelines, and populate the PassManager instance
void registerPipelineParsingCallback(
     FunctionPipelineParsingCallbacks.push_back(C);
   }
   void registerPipelineParsingCallback(
       const std::function<bool(StringRef Name, LoopPassManager &,
                                ArrayRef<PipelineElement>)> &C) {
     LoopPipelineParsingCallbacks.push_back(C);
   }
   void registerPipelineParsingCallback(
+      const std::function<bool(StringRef Name, LoopNestPassManager &,
+                               ArrayRef<PipelineElement>)> &C) {
+    LoopNestPipelineParsingCallbacks.push_back(C);
+  }
+  void registerPipelineParsingCallback(
       const std::function<bool(StringRef Name, ModulePassManager &,
                                ArrayRef<PipelineElement>)> &C) {
     ModulePipelineParsingCallbacks.push_back(C);
   }
   /// @}}
 
   /// Register a callback for a top-level pipeline entry.
   ///
private:
   Error parseModulePass(ModulePassManager &MPM, const PipelineElement &E,
                         bool VerifyEachPass, bool DebugLogging);
   Error parseCGSCCPass(CGSCCPassManager &CGPM, const PipelineElement &E,
                        bool VerifyEachPass, bool DebugLogging);
   Error parseFunctionPass(FunctionPassManager &FPM, const PipelineElement &E,
                           bool VerifyEachPass, bool DebugLogging);
   Error parseLoopPass(LoopPassManager &LPM, const PipelineElement &E,
                       bool VerifyEachPass, bool DebugLogging);
+  Error parseLoopNestPass(LoopNestPassManager &LNPM, const PipelineElement &E,
+                          bool &UseMemorySSA, bool VerifyEachPass,
+                          bool DebugLogging);
   bool parseAAPassName(AAManager &AA, StringRef Name);
 
   Error parseLoopPassPipeline(LoopPassManager &LPM,
                               ArrayRef<PipelineElement> Pipeline,
                               bool VerifyEachPass, bool DebugLogging);
+  Error parseLoopNestPassPipeline(LoopNestPassManager &LNPM,
+                                  ArrayRef<PipelineElement> Pipeline,
+                                  bool &UseMemorySSA, bool VerifyEachPass,
+                                  bool DebugLogging);
   Error parseFunctionPassPipeline(FunctionPassManager &FPM,
                                   ArrayRef<PipelineElement> Pipeline,
                                   bool VerifyEachPass, bool DebugLogging);
   Error parseCGSCCPassPipeline(CGSCCPassManager &CGPM,
                                ArrayRef<PipelineElement> Pipeline,
                                bool VerifyEachPass, bool DebugLogging);
   Error parseModulePassPipeline(ModulePassManager &MPM,
                                 ArrayRef<PipelineElement> Pipeline,
SmallVector<std::function<bool(StringRef, FunctionPassManager &,
       FunctionPipelineParsingCallbacks;
   // Loop callbacks
   SmallVector<std::function<void(LoopAnalysisManager &)>, 2>
       LoopAnalysisRegistrationCallbacks;
   SmallVector<std::function<bool(StringRef, LoopPassManager &,
                                  ArrayRef<PipelineElement>)>,
               2>
       LoopPipelineParsingCallbacks;
+  // LoopNest callbacks
+  SmallVector<std::function<void(LoopNestAnalysisManager &)>, 2>
+      LoopNestAnalysisRegistrationCallbacks;
+  SmallVector<std::function<bool(StringRef, LoopNestPassManager &,
+                                 ArrayRef<PipelineElement>)>,
+              2>
+      LoopNestPipelineParsingCallbacks;
   // AA callbacks
   SmallVector<std::function<bool(StringRef Name, AAManager &AA)>, 2>
       AAParsingCallbacks;
 };
 
 /// This utility template takes care of adding require<> and invalidate<>
 /// passes for an analysis to a given \c PassManager. It is intended to be used
 /// during parsing of a pass pipeline when parsing a single PipelineName.

llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h

+//===- LoopNestPassManager.h - Loop nest pass management -----------------*- C++
+//-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H
+#define LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H
+
+#include "llvm/ADT/PriorityWorklist.h"
+#include "llvm/Analysis/LoopNestAnalysis.h"
+#include "llvm/Analysis/LoopNestAnalysisManager.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+
+namespace llvm {
+
+class LNPMUpdater;
+
+template <>
+PreservedAnalyses
+PassManager<LoopNest, LoopNestAnalysisManager, LoopStandardAnalysisResults &,
+            LNPMUpdater &>::run(LoopNest &LN, LoopNestAnalysisManager &AM,
+                                LoopStandardAnalysisResults &AR,
+                                LNPMUpdater &U);
+
+extern template class PassManager<LoopNest, LoopNestAnalysisManager,
+                                  LoopStandardAnalysisResults &, LNPMUpdater &>;
+
+using LoopNestPassManager =
+    PassManager<LoopNest, LoopNestAnalysisManager,
+                LoopStandardAnalysisResults &, LNPMUpdater &>;
+
+/// A partial specialization of the require analysis template pass for loop
+/// nests to forward the extra parameters from a transformation's run method to
+/// the AnalysisManager's getResult.
+template <typename AnalysisT>
+struct RequireAnalysisPass<AnalysisT, LoopNest, LoopNestAnalysisManager,
+                           LoopStandardAnalysisResults &, LNPMUpdater &>
+    : PassInfoMixin<
+          RequireAnalysisPass<AnalysisT, LoopNest, LoopNestAnalysisManager,
+                              LoopStandardAnalysisResults &, LNPMUpdater &>> {
+  PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LNPMUpdater &) {
+    (void)AM.template getResult<AnalysisT>(LN, AR);
+    return PreservedAnalyses::all();
+  }
+};
+
+template <typename AnalysisT>
+using RequireAnalysisLoopNestPass =
+    RequireAnalysisPass<AnalysisT, LoopNest, LoopNestAnalysisManager,
+                        LoopStandardAnalysisResults &, LNPMUpdater &>;
+
+/// This class provides an interface for updating the loop nest pass manager
+/// based on mutations to the loop nest.
+///
+/// A reference to an instance of this class is passed as an argument to each
+/// LoopNest pass, and LoopNest passes should use it to update LNPM
+/// infrastructure if they modify the loop nest structure.
+class LNPMUpdater {
+public:
+  /// This can be queried by loop nest passes which run other loop nest passes
+  /// (like pass managers) to know whether the loop nest needs to be skipped due
+  /// to updates to the loop nest.
+  ///
+  /// If this returns true, the loop nest object may have been deleted, so
+  /// passes should take care not to touch the object.
+  bool skipCurrentLoopNest() const { return SkipCurrentLoopNest; }
+
+  void markLoopNestAsDeleted(LoopNest &LN, llvm::StringRef Name) {
+    LNAM.clear(LN, Name);
+    assert(&LN.getOutermostLoop() == CurrentLoopNest &&
+           "Cannot delete loop nests other than the current one");
+    SkipCurrentLoopNest = true;
+  }
+
+  /// Loop nest passes should use this method to indicate they have added new
+  /// loop nests to the current function.
+  ///
+  /// \p NewLoopNests must only contain top-level loops.
+  void addNewLoopNests(ArrayRef<Loop *> NewLoopNests) {
+    for (Loop *NewL : NewLoopNests) {
+#ifndef NDEBUG
+      assert(!NewL->getParentLoop() &&
+             "All of the new loops must be top-level!");
+#endif
+      Worklist.insert(NewL);
+    }
+  }
+
+  void revisitCurrentLoopNest() {
+    SkipCurrentLoopNest = true;
+    Worklist.insert(CurrentLoopNest);
+  }
+
+private:
+  template <typename LoopNestPassT> friend class FunctionToLoopNestPassAdaptor;
+
+  LNPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
+              LoopNestAnalysisManager &LNAM)
+      : Worklist(Worklist), LNAM(LNAM) {}
+
+  /// The \c FunctionToLoopNestPassAdaptor's worklist of loops to process.
+  SmallPriorityWorklist<Loop *, 4> &Worklist;
+
+  /// The analysis manager for use in the current loop nest;
+  LoopNestAnalysisManager &LNAM;
+
+  Loop *CurrentLoopNest;
+  bool SkipCurrentLoopNest;
+};
+
+/// Adaptor that maps from a function to its loop nests.
+///
+/// Designed to allow composition of a LoopNestPass(Manager) and a
+/// FunctionPassManager. Note that if this pass is constructed with a \c
+/// FunctionAnalysisManager it will run the \c
+/// LoopNestAnalysisManagerFunctionProxy analysis prior to running the loop
+/// passes over the function to enable a \c LoopNestAnalysisManager to be used
+/// within this run safely.
+template <typename LoopNestPassT>
+class FunctionToLoopNestPassAdaptor
+    : public PassInfoMixin<FunctionToLoopNestPassAdaptor<LoopNestPassT>> {
+public:
+  explicit FunctionToLoopNestPassAdaptor(LoopNestPassT Pass,
+                                         bool UseMemorySSA = false,
+                                         bool DebugLogging = false)
+      : Pass(std::move(Pass)), UseMemorySSA(UseMemorySSA),
+        LoopCanonicalizationFPM(
+            detail::getLoopCanonicalizationPasses(DebugLogging)) {}
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
+    PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
+
+    PreservedAnalyses PA = PreservedAnalyses::all();
+    // Before we even compute any loop nest 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.
+    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 nest passes.
+    LoopStandardAnalysisResults LAR =
+        detail::getLoopStandardAnalysisResults(F, AM, UseMemorySSA);
+
+    // Setup the loop nest 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 nest analyses cached in this
+    // manager have access to those analysis results and so it must invalidate
+    // itself when they go away.
+    auto &LNAMFP = AM.getResult<LoopNestAnalysisManagerFunctionProxy>(F);
+    if (UseMemorySSA)
+      LNAMFP.markMSSAUsed();
+    LoopNestAnalysisManager &LNAM = LNAMFP.getManager();
+
+    // The worklist of loop nests in the function. The loop nests are
+    // represented by their root loops and the actual LoopNest object will be
+    // constructed lazily when needed.
+    SmallPriorityWorklist<Loop *, 4> Worklist;
+    LNPMUpdater Updater(Worklist, LNAM);
+
+    // Append all outer-most loops in the function into the worklist.
+    for (Loop *L : LI.getTopLevelLoops())
+      Worklist.insert(L);
+
+    do {
+      Loop *L = Worklist.pop_back_val();
+
+      // Reset the update structure for this loop nest.
+      Updater.CurrentLoopNest = L;
+      Updater.SkipCurrentLoopNest = false;
+
+      // Construct the actual LoopNest object from the analysis manager.
+      LoopNest &LN = LNAM.getResult<LoopNestAnalysis>(*L, LAR);
+      // Check the PassInstrumentation's BeforePass callbacks before running the
+      // pass, skip its execution completely if asked to (callback returns
+      // false).
+      if (!PI.runBeforePass<LoopNest>(Pass, LN))
+        continue;
+
+      PreservedAnalyses PassPA;
+      {
+        TimeTraceScope TimeScope(Pass.name());
+        PassPA = Pass.run(LN, LNAM, LAR, Updater);
+      }
+
+      // Do not pass deleted LoopNest into the instrumentation.
+      if (Updater.skipCurrentLoopNest())
+        PI.runAfterPassInvalidated<LoopNest>(Pass, PassPA);
+      else
+        PI.runAfterPass<LoopNest>(Pass, LN, PassPA);
+
+      if (!Updater.skipCurrentLoopNest())
+        // We know that the loop nest pass couldn't have invalidated any other
+        // loop nest's analyses (that's the contract of a loop nest pass), so
+        // directly handle the loop nest analysis manager's invalidation here.
+        LNAM.invalidate(LN, PassPA);
+
+      // Then intersect the preserved set so that invalidation of loop nest
+      // analyses will eventually occur when the loop nest pass completes.
+      PA.intersect(std::move(PassPA));
+    } while (!Worklist.empty());
+
+    // By definition we preserve the proxy. We also preserve all analyses on
+    // LoopNests. This precludes *any* invalidation of loop nest analyses by the
+    // proxy, but that's OK because we've taken care to invalidate analyses in
+    // the loop nest analysis manager incrementally above.
+    PA.preserveSet<AllAnalysesOn<Loop>>();
+    PA.preserveSet<AllAnalysesOn<LoopNest>>();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    // We also preserve the set of standard analyses.
+    detail::preserveLoopStandardAnalysisResults(PA, UseMemorySSA);
+    detail::preserveAACategory(PA);
+    return PA;
+  }
+
+private:
+  LoopNestPassT Pass;
+  bool UseMemorySSA;
+  FunctionPassManager LoopCanonicalizationFPM;
+};
+
+/// A function to deduce a loop nest pass type and wrap it in the templated
+/// adaptor.
+template <typename LoopNestPassT>
+FunctionToLoopNestPassAdaptor<LoopNestPassT>
+createFunctionToLoopNestPassAdaptor(LoopNestPassT Pass,
+                                    bool UseMemorySSA = false,
+                                    bool DebugLogging = false) {
+  return FunctionToLoopNestPassAdaptor<LoopNestPassT>(
+      std::move(Pass), UseMemorySSA, DebugLogging);
+}
+
+/// Pass for printing a loop nest's property. This is similar to
+/// \c LoopNestPrinterPass in \file LoopNestAnalysis.h but implemented as a
+/// LoopNestPass.
+class PrintLoopNestPass : public PassInfoMixin<PrintLoopNestPass> {
+  raw_ostream &OS;
+  std::string Banner;
+
+public:
+  PrintLoopNestPass();
+  explicit PrintLoopNestPass(raw_ostream &OS, const std::string &Banner = "");
+
+  PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &,
+                        LoopStandardAnalysisResults &, LNPMUpdater &U);
+};
+
+/// Adaptor that maps from a loop nest to its loops.
+template <typename LoopPassT>
+class LoopNestToLoopPassAdaptor
+    : public PassInfoMixin<LoopNestToLoopPassAdaptor<LoopPassT>> {
+public:
+  explicit LoopNestToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {}
+
+  PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LNPMUpdater &U) {
+    PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(LN, AR);
+    PreservedAnalyses PA = PreservedAnalyses::all();
+
+    // Get the loop analysis manager from the loop nest analysis manager. No
+    // need to set up proxy here since currently the latter is simply a wrapper
+    // around the former.
+    LoopAnalysisManager &LAM = AM.getLoopAnalysisManager();
+
+    SmallPriorityWorklist<Loop *, 4> Worklist;
+
+    // Pass a callback to LPMUpdater to get informed of newly added top-level
+    // loops.
+    std::function<void(ArrayRef<Loop *>)> Callback =
+        [&U](ArrayRef<Loop *> NewLoops) {
+          // LLVM_DEBUG(dbgs() << "Adding top-level loops from loop passes\n");
+          U.addNewLoopNests(NewLoops);
+        };
+    LPMUpdater Updater(Worklist, LAM, Callback);
+    appendLoopNestToWorklist(LN.getOutermostLoop(), Worklist);
+
+    assert(!Worklist.empty() &&
+           "Worklist should be non-empty since we're running on a LoopNest");
+
+    // Save a copy of the root loop and its name here in case they are
+    // invalidated later.
+    const Loop *Root = &LN.getOutermostLoop();
+    const std::string LoopNestName = std::string(LN.getName());
+
+    do {
+      Loop *L = Worklist.pop_back_val();
+      Updater.CurrentL = L;
+      Updater.SkipCurrentLoop = false;
+
+#ifndef NDEBUG
+      // Save a parent loop pointer for asserts.
+      Updater.ParentL = L->getParentLoop();
+
+      // Verify the loop structure and LCSSA form.
+      L->verifyLoop();
+      assert(L->isRecursivelyLCSSAForm(AR.DT, AR.LI) &&
+             "Loops must remain in LCSSA form!");
+#endif
+
+      // Check the PassInstrumentation's BeforePass callbacks before running the
+      // loop pass.
+      if (!PI.runBeforePass<Loop>(Pass, *L))
+        continue;
+
+      PreservedAnalyses PassPA;
+      {
+        TimeTraceScope TimeScope(Pass.name());
+        PassPA = Pass.run(*L, LAM, AR, Updater);
+      }
+
+      // Do not pass deleted Loop into the instrumentation.
+      if (Updater.skipCurrentLoop())
+        PI.runAfterPassInvalidated<Loop>(Pass, PassPA);
+      else
+        PI.runAfterPass<Loop>(Pass, *L, PassPA);
+
+      if (!Updater.SkipCurrentLoop)
+        // Invalidate the loop analysis results here. Note that even if the loop
+        // nest structure had been modified by the loop pass, the
+        // LoopNestAnalysis will not be invalidated here.
+        LAM.invalidate(*L, PassPA);
+
+      PA.intersect(std::move(PassPA));
+    } while (!Worklist.empty());
+
+    // Since the loops are processed in post-order, at this point CurrentL in
+    // Updater should points to the root loop. If the root loop is marked as
+    // deleted, we should also delete the loop nest from the function.
+    assert(Updater.CurrentL == Root && "CurrentL should point to the root loop "
+                                       "after traversing the loop nest.");
+    if (Updater.skipCurrentLoop())
+      U.markLoopNestAsDeleted(LN, LoopNestName);
+
+    if (!Updater.skipCurrentLoop() &&
+        !PA.getChecker<LoopNestAnalysis>().preserved())
+      LN.reconstructInplace(AR.SE);
+
+    // We don't have to explicitly mark the loop standard analysis results as
+    // preserved here since this will eventually be handled by the \c
+    // FunctionToLoopNestPassAdaptor.
+    PA.preserveSet<AllAnalysesOn<Loop>>();
+    return PA;
+  }
+
+private:
+  LoopPassT Pass;
+};
+
+/// A function to deduce a loop pass type and wrap it in the templated
+/// adaptor that converts it to a loop nest pass.
+template <typename LoopPassT>
+LoopNestToLoopPassAdaptor<LoopPassT>
+createLoopNestToLoopPassAdaptor(LoopPassT Pass) {
+  return LoopNestToLoopPassAdaptor<LoopPassT>(std::move(Pass));
+}
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H

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

 
 /// 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;
+template <typename LoopPassT> class LoopNestToLoopPassAdaptor;
 
 /// 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 {
#endif
   /// manager.
   void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) {
 #ifndef NDEBUG
     for (Loop *NewL : NewSibLoops)
       assert(NewL->getParentLoop() == ParentL &&
              "All of the new loops must be siblings of the current loop!");
 #endif
 
+    // If the current loop is a top-level loop and the loop passes are wrapped
+    // inside of a loop nest pass, inform the loop nest pass manager that new
+    // top-level loops are added.
+    //
+    // Note that the loops are not inserted to the worklist in this case because
+    // those loops don't belong to the current loop nest.
+    if (!CurrentL->getParentLoop() && TopLevelLoopAdditionCallback)
+      (*TopLevelLoopAdditionCallback)(NewSibLoops);
+    else
       appendLoopsToWorklist(NewSibLoops, Worklist);
 
     // No need to skip the current loop or revisit it, as sibling loops
     // shouldn't impact anything.
   }
 
   /// Restart the current loop.
   ///
   /// Loop passes should call this method to indicate the current loop has been
   /// sufficiently changed that it should be re-visited from the begining of
   /// the loop pass pipeline rather than continuing.
   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;
+  template <typename LoopPassT> friend class llvm::LoopNestToLoopPassAdaptor;
 
   /// 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;
   bool SkipCurrentLoop;
 
 #ifndef NDEBUG
   // In debug builds we also track the parent loop to implement asserts even in
   // the face of loop deletion.
   Loop *ParentL;
 #endif
 
+  // The updater should use the callback to inform the loop nest pass manager
+  // that new top-level loops are added.
+  //
+  // FIXME: There's probably a better way to do this (except declaring both
+  // LPMUpdater and LNPMUpdater in the same file).
+  Optional<std::function<void(ArrayRef<Loop *>)>> TopLevelLoopAdditionCallback;
+
   LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
-             LoopAnalysisManager &LAM)
-      : Worklist(Worklist), LAM(LAM) {}
+             LoopAnalysisManager &LAM,
+             Optional<std::function<void(ArrayRef<Loop *>)>> Callback = None)
+      : Worklist(Worklist), LAM(LAM), TopLevelLoopAdditionCallback(Callback) {}
 };
 
+// Collections of helper functions that are used by both loop pass manager and
+// loop nest pass manager.
+namespace detail {
+
+/// Helper function for preserving the standard analyses on loops.
+inline void preserveLoopStandardAnalysisResults(PreservedAnalyses &PA,
+                                                bool UseMemorySSA) {
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LoopAnalysis>();
+  PA.preserve<ScalarEvolutionAnalysis>();
+  if (UseMemorySSA)
+    PA.preserve<MemorySSAAnalysis>();
+}
+
+/// Helper function for preserving AA category.
+inline void preserveAACategory(PreservedAnalyses &PA) {
+  // 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>();
+}
+
+/// Helper function for getting the analysis results needed by loop and loop
+/// nest passes.
+inline LoopStandardAnalysisResults
+getLoopStandardAnalysisResults(Function &F, FunctionAnalysisManager &AM,
+                               bool UseMemorySSA) {
+  MemorySSA *MSSA =
+      UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) : 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),
+                                     MSSA};
+  return LAR;
+}
+
+/// Helper function for constructing loop canonicalization passes for loop pass
+/// manager and loop nest pass manager.
+inline FunctionPassManager getLoopCanonicalizationPasses(bool DebugLogging) {
+  FunctionPassManager FPM(DebugLogging);
+  FPM.addPass(LoopSimplifyPass());
+  FPM.addPass(LCSSAPass());
+  return FPM;
+}
+
+} // namespace detail
+
 /// 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:
   explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false,
                                      bool DebugLogging = false)
-      : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging),
-        UseMemorySSA(UseMemorySSA) {
-    LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
-    LoopCanonicalizationFPM.addPass(LCSSAPass());
-  }
+      : Pass(std::move(Pass)),
+        LoopCanonicalizationFPM(
+            detail::getLoopCanonicalizationPasses(DebugLogging)),
+        UseMemorySSA(UseMemorySSA) {}
 
   /// 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;
-    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),
-                                       MSSA};
+    // Get the analysis results needed by loop nest passes.
+    LoopStandardAnalysisResults LAR =
+        detail::getLoopStandardAnalysisResults(F, AM, UseMemorySSA);
 
     // 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)
#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 (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>();
+    detail::preserveLoopStandardAnalysisResults(PA, UseMemorySSA);
+    detail::preserveAACategory(PA);
     return PA;
   }
 
   static bool isRequired() { return true; }
 
 private:
   LoopPassT Pass;
 

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 /// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling,
 /// loop deletion, and LICM, we largely want to work forward across the CFG so
 /// that we visit defs before uses and can propagate simplifications from one
 /// loop nest into the next. Calls appendReversedLoopsToWorklist with the
 /// already reversed loops in LI.
 /// FIXME: Consider changing the order in LoopInfo.
 void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &);
 
+/// Utility that implements appending of all loops in a loop nest (rooted at \p
+/// Root) onto a worklist. Since appendLoopsToWorklist(Loop &) only pushes
+/// subloops, the root loop will be pushed into the worklist first in this
+/// function.
+void appendLoopNestToWorklist(Loop &Root, SmallPriorityWorklist<Loop *, 4> &);
+
 /// Recursively clone the specified loop and all of its children,
 /// mapping the blocks with the specified map.
 Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
                 LoopInfo *LI, LPPassManager *LPM);
 
 /// Add code that checks at runtime if the accessed arrays in \p PointerChecks
 /// overlap.
 ///

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   LazyValueInfo.cpp
   LegacyDivergenceAnalysis.cpp
   Lint.cpp
   Loads.cpp
   LoopAccessAnalysis.cpp
   LoopAnalysisManager.cpp
   LoopCacheAnalysis.cpp
   LoopNestAnalysis.cpp
+  LoopNestAnalysisManager.cpp
   LoopUnrollAnalyzer.cpp
   LoopInfo.cpp
   LoopPass.cpp
   MLInlineAdvisor.cpp
   MemDepPrinter.cpp
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp

llvm/lib/Analysis/LoopNestAnalysis.cpp

while (SubLoops->size() == 1) {
     CurrentLoop = InnerLoop;
     SubLoops = &CurrentLoop->getSubLoops();
     ++CurrentDepth;
   }
 
   return CurrentDepth;
 }
 
+void LoopNest::reconstructInplace(ScalarEvolution &SE) {
+  LLVM_DEBUG(dbgs() << "Reconstructing loop-nest: " << getName() << "\n");
+  assert(!Loops.empty() && "Loop nest should contain the root loop.");
+  Loop *Root = Loops[0];
+  MaxPerfectDepth = getMaxPerfectDepth(*Root, SE);
+  Loops.clear();
+  for (Loop *L : breadth_first(Root))
+    Loops.push_back(L);
+}
+
 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
                                 ScalarEvolution &SE) {
   // The inner loop must be the only outer loop's child.
   if ((OuterLoop.getSubLoops().size() != 1) ||
       (InnerLoop.getParentLoop() != &OuterLoop))
     return false;
 
   // We expect loops in normal form which have a preheader, header, latch...
raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
   OS << ", Loops: ( ";
   for (const Loop *L : LN.getLoops())
     OS << L->getName() << " ";
   OS << ")";
 
   return OS;
 }
 
+AnalysisKey LoopNestAnalysis::Key;
+
+LoopNest LoopNestAnalysis::run(Loop &L, LoopAnalysisManager &AM,
+                               LoopStandardAnalysisResults &AR) {
+  return LoopNest(L, AR.SE);
+}
+
 //===----------------------------------------------------------------------===//
 // LoopNestPrinterPass implementation
 //
 
 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &U) {
   if (auto LN = LoopNest::getLoopNest(L, AR.SE))
     OS << *LN << "\n";
 
   return PreservedAnalyses::all();
 }

llvm/lib/Analysis/LoopNestAnalysisManager.cpp

+//===- LoopNestAnalysisManager.cpp - LoopNest analysis management ---------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopNestAnalysisManager.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/PassManagerImpl.h"
+
+using namespace llvm;
+
+namespace llvm {
+
+template class AnalysisManager<LoopNest>;
+template class InnerAnalysisManagerProxy<LoopNestAnalysisManager, Function>;
+template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
+                                         LoopStandardAnalysisResults &>;
+
+bool LoopNestAnalysisManagerFunctionProxy::Result::invalidate(
+    Function &F, const PreservedAnalyses &PA,
+    FunctionAnalysisManager::Invalidator &Inv) {
+  // If literally everything is preserved, we're done.
+  if (PA.areAllPreserved())
+    return false; // This is still a valid proxy.
+
+  std::vector<Loop *> TopLevelLoops = LI->getTopLevelLoops();
+  SmallVector<Loop *, 4> PreOrderLoops = LI->getLoopsInReverseSiblingPreorder();
+
+  auto PAC = PA.getChecker<LoopNestAnalysisManagerFunctionProxy>();
+  bool InvalidateMemorySSAAnalysis = false;
+  if (MSSAUsed)
+    InvalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA);
+  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
+      Inv.invalidate<AAManager>(F, PA) ||
+      Inv.invalidate<AssumptionAnalysis>(F, PA) ||
+      Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
+      Inv.invalidate<LoopAnalysis>(F, PA) ||
+      Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
+      InvalidateMemorySSAAnalysis) {
+    // Note that the LoopInfo may be stale at this point, however the loop
+    // objects themselves remain the only viable keys that could be in the
+    // analysis manager's cache. So we just walk the keys and forcibly clear
+    // those results. Note that the order doesn't matter here as this will
+    // just directly destroy the results without calling methods on them.
+    //
+    // Though we're dealing with loop nests here, the analysis results can
+    // still be cleared via the root loops.
+    //
+    // Note that not only do we invalidate loop nest analyses on the root
+    // loops, the loop anlayses on the subloops should also be cleared because
+    // they depend on the standard analysis results as well.
+    for (Loop *L : PreOrderLoops)
+      InnerAM->clear(*L, "<possibly invalidated loop>");
+    InnerAM = nullptr;
+    return true;
+  }
+
+  // Directly check if the relevant set is preserved.
+  bool AreLoopNestAnalysesPreserved =
+      PA.allAnalysesInSetPreserved<AllAnalysesOn<LoopNest>>();
+
+  // getTopLevelLoops() returns loops in "reversed" order. Reverse the list
+  // again for correctness.
+  for (Loop *L : reverse(TopLevelLoops)) {
+    Optional<PreservedAnalyses> LoopNestPA;
+
+    // Check to see whether the preserved set needs to be pruned based on
+    // function-level analysis invalidation that triggers deferred invalidation
+    // registered with the outer analysis manager proxy for this loop nest.
+    if (auto *OuterProxy =
+            InnerAM->getCachedResult<FunctionAnalysisManagerLoopNestProxy>(
+                *L)) {
+      for (const auto &OuterInvalidationPair :
+           OuterProxy->getOuterInvalidations()) {
+        AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
+        const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
+        if (Inv.invalidate(OuterAnalysisID, F, PA)) {
+          if (!LoopNestPA)
+            LoopNestPA = PA;
+          for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
+            LoopNestPA->abandon(InnerAnalysisID);
+        }
+      }
+    }
+
+    // Check if we needed a custom PA set, and if so we'll need to run the
+    // inner invalidation.
+    if (LoopNestPA) {
+      InnerAM->invalidate(*L, *LoopNestPA);
+      continue;
+    }
+
+    // Otherwise we only need to do invalidation if the original PA set didn't
+    // preserve all loop nest analyses.
+    if (!AreLoopNestAnalysesPreserved)
+      InnerAM->invalidate(*L, PA);
+  }
+
+  // Return false to indicate that this result is still a valid proxy.
+  return false;
+}
+
+template <>
+LoopNestAnalysisManagerFunctionProxy::Result
+LoopNestAnalysisManagerFunctionProxy::run(Function &F,
+                                          FunctionAnalysisManager &AM) {
+  return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));
+}
+
+void LoopNestAnalysisManager::invalidateSubLoopAnalyses(
+    Loop &Root, const PreservedAnalyses &PA) {
+  // We can return immediately if all the loop analyses are preserved.
+  if (PA.areAllPreserved() ||
+      PA.allAnalysesInSetPreserved<AllAnalysesOn<Loop>>())
+    return;
+
+  // Collect the loops in the subtree in post-order by performing DFS without
+  // recursion using a stack.
+  SmallVector<Loop *, 4> DFSStack(Root.begin(), Root.end()), SubLoops;
+  while (!DFSStack.empty()) {
+    Loop *L = DFSStack.pop_back_val();
+    SubLoops.push_back(L);
+    DFSStack.append(L->begin(), L->end());
+  }
+
+  // Visit the loops in reversed post-order and invalidate them.
+  for (Loop *L : reverse(SubLoops)) {
+    InternalLAM.invalidate(*L, PA);
+  }
+}
+
+} // namespace llvm

llvm/lib/LTO/LTOBackend.cpp

 // internally by the LTO class but can also be used independently, for example
 // to implement a standalone ThinLTO backend.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/LTO/LTOBackend.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/LoopNestAnalysisManager.h"
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Bitcode/BitcodeReader.h"
 #include "llvm/Bitcode/BitcodeWriter.h"
 #include "llvm/IR/LLVMRemarkStreamer.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/PassManager.h"
static void runNewPMPasses(const Config &Conf, Module &Mod, TargetMachine *TM,
 
   // Parse a custom AA pipeline if asked to.
   if (auto Err = PB.parseAAPipeline(AA, "default"))
     report_fatal_error("Error parsing default AA pipeline");
 
   RegisterPassPlugins(Conf.PassPlugins, PB);
 
   LoopAnalysisManager LAM(Conf.DebugPassManager);
+  LoopNestAnalysisManager LNAM(LAM, Conf.DebugPassManager);
   FunctionAnalysisManager FAM(Conf.DebugPassManager);
   CGSCCAnalysisManager CGAM(Conf.DebugPassManager);
   ModuleAnalysisManager MAM(Conf.DebugPassManager);
 
   // Register the AA manager first so that our version is the one used.
   FAM.registerPass([&] { return std::move(AA); });
 
   // Register all the basic analyses with the managers.
   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
   PB.registerLoopAnalyses(LAM);
-  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+  PB.registerLoopNestAnalyses(LNAM);
+  PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
 
   ModulePassManager MPM(Conf.DebugPassManager);
   // FIXME (davide): verify the input.
 
   PassBuilder::OptimizationLevel OL;
 
   switch (OptLevel) {
   default:
static void runNewPMCustomPasses(const Config &Conf, Module &Mod,
   if (!AAPipelineDesc.empty())
     if (auto Err = PB.parseAAPipeline(AA, AAPipelineDesc))
       report_fatal_error("unable to parse AA pipeline description '" +
                          AAPipelineDesc + "': " + toString(std::move(Err)));
 
   RegisterPassPlugins(Conf.PassPlugins, PB);
 
   LoopAnalysisManager LAM;
+  LoopNestAnalysisManager LNAM(LAM);
   FunctionAnalysisManager FAM;
   CGSCCAnalysisManager CGAM;
   ModuleAnalysisManager MAM;
 
   // Register the AA manager first so that our version is the one used.
   FAM.registerPass([&] { return std::move(AA); });
 
   // Register all the basic analyses with the managers.
   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
   PB.registerLoopAnalyses(LAM);
-  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+  PB.registerLoopNestAnalyses(LNAM);
+  PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
 
   ModulePassManager MPM;
 
   // Always verify the input.
   MPM.addPass(VerifierPass());
 
   // Now, add all the passes we've been requested to.
   if (auto Err = PB.parsePassPipeline(MPM, PipelineDesc))

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h"
 #include "llvm/Transforms/Scalar/LoopDataPrefetch.h"
 #include "llvm/Transforms/Scalar/LoopDeletion.h"
 #include "llvm/Transforms/Scalar/LoopDistribute.h"
 #include "llvm/Transforms/Scalar/LoopFuse.h"
 #include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
 #include "llvm/Transforms/Scalar/LoopInstSimplify.h"
 #include "llvm/Transforms/Scalar/LoopLoadElimination.h"
+#include "llvm/Transforms/Scalar/LoopNestPassManager.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Scalar/LoopPredication.h"
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
 #include "llvm/Transforms/Scalar/LoopSink.h"
 #include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
 #include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
 #include "llvm/Transforms/Scalar/LoopUnrollPass.h"

 public:
   struct Result {};
   Result run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &) {
     return Result();
   }
   static StringRef name() { return "NoOpLoopAnalysis"; }
 };
 
+/// No-op loop nest pass which does nothing.
+struct NoOpLoopNestPass : PassInfoMixin<NoOpLoopNestPass> {
+  PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &,
+                        LoopStandardAnalysisResults &, LNPMUpdater &) {
+    return PreservedAnalyses::all();
+  }
+  static StringRef name() { return "NoOpLoopNestPass"; }
+};
+
+/// No-op loop nest analysis.
+class NoOpLoopNestAnalysis : public AnalysisInfoMixin<NoOpLoopNestAnalysis> {
+  friend AnalysisInfoMixin<NoOpLoopNestAnalysis>;
+  static AnalysisKey Key;
+
+public:
+  struct Result {};
+  Result run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &) {
+    return Result();
+  }
+  static StringRef name() { return "NoOpLoopNestAnalysis"; }
+};
+
 AnalysisKey NoOpModuleAnalysis::Key;
 AnalysisKey NoOpCGSCCAnalysis::Key;
 AnalysisKey NoOpFunctionAnalysis::Key;
+AnalysisKey NoOpLoopNestAnalysis::Key;
 AnalysisKey NoOpLoopAnalysis::Key;
 
 } // namespace
 
 void PassBuilder::invokePeepholeEPCallbacks(
     FunctionPassManager &FPM, PassBuilder::OptimizationLevel Level) {
   for (auto &C : PeepholeEPCallbacks)
     C(FPM, Level);

 #define LOOP_ANALYSIS(NAME, CREATE_PASS)                                       \
   LAM.registerPass([&] { return CREATE_PASS; });
 #include "PassRegistry.def"
 
   for (auto &C : LoopAnalysisRegistrationCallbacks)
     C(LAM);
 }
 
+void PassBuilder::registerLoopNestAnalyses(LoopNestAnalysisManager &LNAM) {
+#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS)                                  \
+  LNAM.registerPass([&] { return CREATE_PASS; });
+#include "PassRegistry.def"
+
+  for (auto &C : LoopNestAnalysisRegistrationCallbacks)
+    C(LNAM);
+}
+
 // TODO: Investigate the cost/benefit of tail call elimination on debugging.
 FunctionPassManager PassBuilder::buildO1FunctionSimplificationPipeline(
     OptimizationLevel Level, ThinLTOPhase Phase, bool DebugLogging) {
 
   FunctionPassManager FPM(DebugLogging);
 
   // Form SSA out of local memory accesses after breaking apart aggregates into
   // scalars.
#define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
     return true;
 #include "PassRegistry.def"
 
   return callbacksAcceptPassName<FunctionPassManager>(Name, Callbacks);
 }
 
 template <typename CallbacksT>
+static bool isLoopNestPassName(StringRef Name, CallbacksT &Callbacks) {
+  // Explicitly handle pass manager names.
+  if (Name == "loop-nest" || Name == "loop-nest-mssa")
+    return true;
+
+  // Explicitly handle custom-parsed pass names.
+  if (parseRepeatPassName(Name))
+    return true;
+
+#define LOOP_NEST_PASS(NAME, CREATE_PASS)                                      \
+  if (Name == NAME)                                                            \
+    return true;
+#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)                  \
+  if (checkParametrizedPassName(Name, NAME))                                   \
+    return true;
+#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS)                                  \
+  if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
+    return true;
+#include "PassRegistry.def"
+
+  return callbacksAcceptPassName<LoopNestPassManager>(Name, Callbacks);
+}
+
+template <typename CallbacksT>
 static bool isLoopPassName(StringRef Name, CallbacksT &Callbacks) {
   // Explicitly handle pass manager names.
   if (Name == "loop" || Name == "loop-mssa")
     return true;
 
   // Explicitly handle custom-parsed pass names.
   if (parseRepeatPassName(Name))
     return true;
if (Name == "function") {
       FunctionPassManager NestedFPM(DebugLogging);
       if (auto Err = parseFunctionPassPipeline(NestedFPM, InnerPipeline,
                                                VerifyEachPass, DebugLogging))
         return Err;
       // Add the nested pass manager with the appropriate adaptor.
       FPM.addPass(std::move(NestedFPM));
       return Error::success();
     }
+    if (Name == "loop-nest" || Name == "loop-nest-mssa") {
+      LoopNestPassManager LNPM(DebugLogging);
+      // Because the LoopStandardAnalysisResults can only be constructed at
+      // FunctionToLoopNestPassAdaptor but not at LoopNestToLoopPassAdaptor,
+      // UseMemorySSA should depends on the loop passes as well.
+      // Memory SSA is needed if either the loop nest explicitly requires
+      // it or at least one of the loop passes wrapped inside the loop nest pass
+      // requires it.
+      bool UseMemorySSA = (Name == "loop-nest-mssa");
+      if (auto Err = parseLoopNestPassPipeline(
+              LNPM, InnerPipeline, UseMemorySSA, VerifyEachPass, DebugLogging))
+        return Err;
+      FPM.addPass(createFunctionToLoopNestPassAdaptor(
+          std::move(LNPM), UseMemorySSA, DebugLogging));
+      return Error::success();
+    }
     if (Name == "loop" || Name == "loop-mssa") {
       LoopPassManager LPM(DebugLogging);
       if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass,
                                            DebugLogging))
         return Err;
       // Add the nested pass manager with the appropriate adaptor.
       bool UseMemorySSA = (Name == "loop-mssa");
       FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM), UseMemorySSA,
#define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)                       \
   if (checkParametrizedPassName(Name, NAME)) {                                 \
     auto Params = parsePassParameters(PARSER, Name, NAME);                     \
     if (!Params)                                                               \
       return Params.takeError();                                               \
     FPM.addPass(createFunctionToLoopPassAdaptor(CREATE_PASS(Params.get()),     \
                                                 false, DebugLogging));         \
     return Error::success();                                                   \
   }
+#define LOOP_NEST_PASS(NAME, CREATE_PASS)                                      \
+  if (Name == NAME) {                                                          \
+    FPM.addPass(createFunctionToLoopNestPassAdaptor(CREATE_PASS, false,        \
+                                                    DebugLogging));            \
+    return Error::success();                                                   \
+  }
+#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)                  \
+  if (checkParametrizedPassName(Name, NAME)) {                                 \
+    auto Params = parsePassParameters(PARSER, Name, NAME);                     \
+    if (!Params)                                                               \
+      return Params.takeError();                                               \
+    FPM.addPass(createFunctionToLoopNestPassAdaptor(CREATE_PASS(Params.get()), \
+                                                    false, DebugLogging));     \
+    return Error::success();                                                   \
+  }
 #include "PassRegistry.def"
 
   for (auto &C : FunctionPipelineParsingCallbacks)
     if (C(Name, FPM, InnerPipeline))
       return Error::success();
   return make_error<StringError>(
       formatv("unknown function pass '{0}'", Name).str(),
       inconvertibleErrorCode());
 }
 
+Error PassBuilder::parseLoopNestPass(LoopNestPassManager &LNPM,
+                                     const PipelineElement &E,
+                                     bool &UseMemorySSA, bool VerifyEachPass,
+                                     bool DebugLogging) {
+  StringRef Name = E.Name;
+  const auto &InnerPipeline = E.InnerPipeline;
+
+  // First handle complex passes like the pass managers which carry pipelines.
+  if (!InnerPipeline.empty()) {
+    if (Name == "loop-nest") {
+      LoopNestPassManager NestedLNPM(DebugLogging);
+      if (auto Err =
+              parseLoopNestPassPipeline(NestedLNPM, InnerPipeline, UseMemorySSA,
+                                        VerifyEachPass, DebugLogging))
+        return Err;
+      // Add the nested pass manager with the appropriate adaptor.
+      LNPM.addPass(std::move(NestedLNPM));
+      return Error::success();
+    }
+    // Loop passes can be wrapped in a loop nest pass via \c
+    // LoopNestToLoopPassAdaptor.
+    if (Name == "loop" || Name == "loop-mssa") {
+      LoopPassManager LPM(DebugLogging);
+      if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass,
+                                           DebugLogging))
+        return Err;
+      // If the loop pass requires MemorySSA, the loop nest pass does as well.
+      UseMemorySSA |= (Name == "loop-mssa");
+      LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM)));
+      return Error::success();
+    }
+    if (auto Count = parseRepeatPassName(Name)) {
+      LoopNestPassManager NestedLNPM(DebugLogging);
+      if (auto Err =
+              parseLoopNestPassPipeline(NestedLNPM, InnerPipeline, UseMemorySSA,
+                                        VerifyEachPass, DebugLogging))
+        return Err;
+      LNPM.addPass(createRepeatedPass(*Count, std::move(NestedLNPM)));
+      return Error::success();
+    }
+
+    for (auto &C : LoopNestPipelineParsingCallbacks)
+      if (C(Name, LNPM, InnerPipeline))
+        return Error::success();
+
+    // Normal passes can't have pipelines.
+    return make_error<StringError>(
+        formatv("invalid use of '{0}' pass as loop pipeline", Name).str(),
+        inconvertibleErrorCode());
+  }
+
+// Now expand the basic registered passes from the .inc file.
+#define LOOP_NEST_PASS(NAME, CREATE_PASS)                                      \
+  if (Name == NAME) {                                                          \
+    LNPM.addPass(CREATE_PASS);                                                 \
+    return Error::success();                                                   \
+  }
+#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)                  \
+  if (checkParametrizedPassName(Name, NAME)) {                                 \
+    auto Params = parsePassParameters(PARSER, Name, NAME);                     \
+    if (!Params)                                                               \
+      return Params.takeError();                                               \
+    LNPM.addPass(CREATE_PASS(Params.get()));                                   \
+    return Error::success();                                                   \
+  }
+#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS)                                  \
+  if (Name == "require<" NAME ">") {                                           \
+    LNPM.addPass(RequireAnalysisPass<                                          \
+                 std::remove_reference<decltype(CREATE_PASS)>::type, LoopNest, \
+                 LoopNestAnalysisManager, LoopStandardAnalysisResults &,       \
+                 LNPMUpdater &>());                                            \
+    return Error::success();                                                   \
+  }                                                                            \
+  if (Name == "invalidate<" NAME ">") {                                        \
+    LNPM.addPass(InvalidateAnalysisPass<                                       \
+                 std::remove_reference<decltype(CREATE_PASS)>::type>());       \
+    return Error::success();                                                   \
+  }
+#include "PassRegistry.def"
+
+  for (auto &C : LoopNestPipelineParsingCallbacks)
+    if (C(Name, LNPM, InnerPipeline))
+      return Error::success();
+  return make_error<StringError>(
+      formatv("unknown loop nest pass '{0}'", Name).str(),
+      inconvertibleErrorCode());
+}
+
 Error PassBuilder::parseLoopPass(LoopPassManager &LPM, const PipelineElement &E,
                                  bool VerifyEachPass, bool DebugLogging) {
   StringRef Name = E.Name;
   auto &InnerPipeline = E.InnerPipeline;
 
   // First handle complex passes like the pass managers which carry pipelines.
   if (!InnerPipeline.empty()) {
     if (Name == "loop") {

 #include "PassRegistry.def"
 
   for (auto &C : AAParsingCallbacks)
     if (C(Name, AA))
       return true;
   return false;
 }
 
+Error PassBuilder::parseLoopNestPassPipeline(LoopNestPassManager &LNPM,
+                                             ArrayRef<PipelineElement> Pipeline,
+                                             bool &UseMemorySSA,
+                                             bool VerifyEachPass,
+                                             bool DebugLogging) {
+  for (const auto &Element : Pipeline) {
+    if (auto Err = parseLoopNestPass(LNPM, Element, UseMemorySSA,
+                                     VerifyEachPass, DebugLogging))
+      return Err;
+    // FIXME: No verifier support for LoopNest passes!
+  }
+  return Error::success();
+}
+
 Error PassBuilder::parseLoopPassPipeline(LoopPassManager &LPM,
                                          ArrayRef<PipelineElement> Pipeline,
                                          bool VerifyEachPass,
                                          bool DebugLogging) {
   for (const auto &Element : Pipeline) {
     if (auto Err = parseLoopPass(LPM, Element, VerifyEachPass, DebugLogging))
       return Err;
     // FIXME: No verifier support for Loop passes!
for (const auto &Element : Pipeline) {
     if (auto Err = parseCGSCCPass(CGPM, Element, VerifyEachPass, DebugLogging))
       return Err;
     // FIXME: No verifier support for CGSCC passes!
   }
   return Error::success();
 }
 
 void PassBuilder::crossRegisterProxies(LoopAnalysisManager &LAM,
+                                       LoopNestAnalysisManager &LNAM,
                                        FunctionAnalysisManager &FAM,
                                        CGSCCAnalysisManager &CGAM,
                                        ModuleAnalysisManager &MAM) {
   MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
   MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); });
   CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); });
   FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); });
   FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
+  FAM.registerPass([&] { return LoopNestAnalysisManagerFunctionProxy(LNAM); });
+  LNAM.registerPass([&] { return FunctionAnalysisManagerLoopNestProxy(FAM); });
   FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); });
   LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); });
 }
 
 Error PassBuilder::parseModulePassPipeline(ModulePassManager &MPM,
                                            ArrayRef<PipelineElement> Pipeline,
                                            bool VerifyEachPass,
                                            bool DebugLogging) {
Error PassBuilder::parsePassPipeline(ModulePassManager &MPM,
   StringRef FirstName = Pipeline->front().Name;
 
   if (!isModulePassName(FirstName, ModulePipelineParsingCallbacks)) {
     if (isCGSCCPassName(FirstName, CGSCCPipelineParsingCallbacks)) {
       Pipeline = {{"cgscc", std::move(*Pipeline)}};
     } else if (isFunctionPassName(FirstName,
                                   FunctionPipelineParsingCallbacks)) {
       Pipeline = {{"function", std::move(*Pipeline)}};
+    } else if (isLoopNestPassName(FirstName,
+                                  LoopNestPipelineParsingCallbacks)) {
+      Pipeline = {{"function", {{"loop-nest", std::move(*Pipeline)}}}};
     } else if (isLoopPassName(FirstName, LoopPipelineParsingCallbacks)) {
       Pipeline = {{"function", {{"loop", std::move(*Pipeline)}}}};
     } else {
       for (auto &C : TopLevelPipelineParsingCallbacks)
         if (C(MPM, *Pipeline, VerifyEachPass, DebugLogging))
           return Error::success();
 
       // Unknown pass or pipeline name!
return make_error<StringError>(
         inconvertibleErrorCode());
 
   if (auto Err = parseFunctionPassPipeline(FPM, *Pipeline, VerifyEachPass,
                                            DebugLogging))
     return Err;
   return Error::success();
 }
 
+Error PassBuilder::parsePassPipeline(LoopNestPassManager &LNPM,
+                                     StringRef PipelineText, bool &UseMemorySSA,
+                                     bool VerifyEachPass, bool DebugLogging) {
+  auto Pipeline = parsePipelineText(PipelineText);
+  if (!Pipeline || Pipeline->empty())
+    return make_error<StringError>(
+        formatv("invalid pipeline '{0}'", PipelineText).str(),
+        inconvertibleErrorCode());
+
+  StringRef FirstName = Pipeline->front().Name;
+  if (!isLoopNestPassName(FirstName, LoopNestPipelineParsingCallbacks))
+    return make_error<StringError>(
+        formatv("unknown loop nest pass '{0}' in pipeline '{1}'", FirstName,
+                PipelineText)
+            .str(),
+        inconvertibleErrorCode());
+
+  if (auto Err = parseLoopNestPassPipeline(LNPM, *Pipeline, UseMemorySSA,
+                                           VerifyEachPass, DebugLogging))
+    return Err;
+  return Error::success();
+}
+
 // Primary pass pipeline description parsing routine for a \c LoopPassManager
 Error PassBuilder::parsePassPipeline(LoopPassManager &CGPM,
                                      StringRef PipelineText,
                                      bool VerifyEachPass, bool DebugLogging) {
   auto Pipeline = parsePipelineText(PipelineText);
   if (!Pipeline || Pipeline->empty())
     return make_error<StringError>(
         formatv("invalid pipeline '{0}'", PipelineText).str(),
#define MODULE_ANALYSIS(NAME, CREATE_PASS)                                     \
   if (PassName == NAME)                                                        \
     return true;
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
   if (PassName == NAME)                                                        \
     return true;
 #define LOOP_ANALYSIS(NAME, CREATE_PASS)                                       \
   if (PassName == NAME)                                                        \
     return true;
+#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS)                                  \
+  if (PassName == NAME)                                                        \
+    return true;
 #define CGSSC_ANALYSIS(NAME, CREATE_PASS)                                      \
   if (PassName == NAME)                                                        \
     return true;
 #include "PassRegistry.def"
   return false;
 }

llvm/lib/Passes/PassRegistry.def

 #define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)
 #endif
 LOOP_PASS_WITH_PARAMS("unswitch",
                            [](bool NonTrivial) {
                              return SimpleLoopUnswitchPass(NonTrivial);
                            },
                            parseLoopUnswitchOptions)
 #undef LOOP_PASS_WITH_PARAMS
+
+#ifndef LOOP_NEST_ANALYSIS
+#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS)
+#endif
+LOOP_NEST_ANALYSIS("loop-nest", LoopNestAnalysis())
+LOOP_NEST_ANALYSIS("no-op-loop-nest", NoOpLoopNestAnalysis())
+LOOP_NEST_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
+#undef LOOP_NEST_ANALYSIS
+
+#ifndef LOOP_NEST_PASS
+#define LOOP_NEST_PASS(NAME, CREATE_PASS)
+#endif
+LOOP_NEST_PASS("no-op-loop-nest", NoOpLoopNestPass())
+LOOP_NEST_PASS("print", PrintLoopNestPass())
+#undef LOOP_NEST_PASS
+
+#ifndef LOOP_NEST_PASS_WITH_PARAMS
+#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS)
+#endif
+#undef LOOP_NEST_PASS_WITH_PARAMS

llvm/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_component_library(LLVMScalarOpts
   LoopDeletion.cpp
   LoopDataPrefetch.cpp
   LoopDistribute.cpp
   LoopFuse.cpp
   LoopIdiomRecognize.cpp
   LoopInstSimplify.cpp
   LoopInterchange.cpp
   LoopLoadElimination.cpp
+  LoopNestPassManager.cpp
   LoopPassManager.cpp
   LoopPredication.cpp
   LoopRerollPass.cpp
   LoopRotation.cpp
   LoopSimplifyCFG.cpp
   LoopStrengthReduce.cpp
   LoopUnrollPass.cpp
   LoopUnrollAndJamPass.cpp

llvm/lib/Transforms/Scalar/LoopNestPassManager.cpp

+//===- LoopNestPassManager.cpp - Loop nest pass management ----------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/LoopNestPassManager.h"
+
+namespace llvm {
+
+template <>
+PreservedAnalyses
+PassManager<LoopNest, LoopNestAnalysisManager, LoopStandardAnalysisResults &,
+            LNPMUpdater &>::run(LoopNest &LN, LoopNestAnalysisManager &AM,
+                                LoopStandardAnalysisResults &AR,
+                                LNPMUpdater &U) {
+  PreservedAnalyses PA = PreservedAnalyses::all();
+
+  // Request PassInstrumentation from analysis manager, will use it to run
+  // instrumenting callbacks for the passes later.
+  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(LN, AR);
+
+  if (DebugLogging)
+    dbgs() << "Starting LoopNest pass manager run.\n";
+
+  for (unsigned I = 0, E = Passes.size(); I != E; ++I) {
+    auto *Pass = Passes[I].get();
+
+    // Check the PassInstrumentation's BeforePass callbacks before running the
+    // pass, skip its execution completely if asked to (callback returns
+    // false).
+    if (!PI.runBeforePass<LoopNest>(*Pass, LN))
+      continue;
+
+    PreservedAnalyses PassPA;
+    {
+      TimeTraceScope TimeScope(Pass->name(), LN.getName());
+      PassPA = Pass->run(LN, AM, AR, U);
+    }
+
+    // Do not pass deleted LoopNest into the instrumentation
+    if (U.skipCurrentLoopNest())
+      PI.runAfterPassInvalidated<LoopNest>(*Pass, PassPA);
+    else
+      PI.runAfterPass<LoopNest>(*Pass, LN, PassPA);
+
+    if (U.skipCurrentLoopNest()) {
+      PA.intersect(std::move(PassPA));
+      break;
+    }
+
+    // We shouldn't allow invalidating LoopNestAnalysis in AM since otherwise
+    // LN will be dangling. Currently the loop nest passes cannot explicitly
+    // update the LoopNest structure, so we must first check whether
+    // LoopNestAnalysis is preserved, and mark it as preserved
+    // regardlessly afterward. If the analysis is not preserved in the first
+    // place, we would have to manually reconstruct the LoopNest.
+    // FIXME: This is quite inefficient. Consider reimplementing LoopNest to
+    // allow dynamic modifications by the loop nest passes to avoid
+    // reconstructing it every time.
+    bool IsLoopNestPreserved =
+        PassPA.getChecker<LoopNestAnalysis>().preserved();
+
+    // No need to invalidate other loop nest analyses since they are running on
+    // Loop and hence can be updated dynamically.
+    PassPA.preserve<LoopNestAnalysis>();
+    AM.invalidate(LN, PassPA);
+
+    if (!IsLoopNestPreserved)
+      // The LoopNest structure had been altered, reconstruct it here.
+      LN.reconstructInplace(AR.SE);
+    PA.intersect(std::move(PassPA));
+  }
+
+  // Invalidation for the current loop nest should be handled above, and other
+  // loop nest analysis results shouldn't be impacted by runs over this loop
+  // nest. Therefore, the remaining analysis results in the AnalysisManager are
+  // preserved. We mark this with a set so that we don't need to inspect each
+  // one individually.
+  PA.preserveSet<AllAnalysesOn<LoopNest>>();
+  // All analyses on Loops are preserved as well.
+  PA.preserveSet<AllAnalysesOn<Loop>>();
+
+  if (DebugLogging)
+    dbgs() << "Finished LoopNest pass manager run.\n";
+
+  return PA;
+}
+
+template class PassManager<LoopNest, LoopNestAnalysisManager,
+                           LoopStandardAnalysisResults &, LNPMUpdater &>;
+
+PrintLoopNestPass::PrintLoopNestPass() : OS(dbgs()) {}
+PrintLoopNestPass::PrintLoopNestPass(raw_ostream &OS, const std::string &Banner)
+    : OS(OS), Banner(Banner) {}
+
+PreservedAnalyses PrintLoopNestPass::run(LoopNest &LN,
+                                         LoopNestAnalysisManager &,
+                                         LoopStandardAnalysisResults &,
+                                         LNPMUpdater &) {
+  OS << LN << "\n";
+  return PreservedAnalyses::all();
+}
+
+} // namespace llvm

llvm/lib/Transforms/Utils/LoopUtils.cpp

 llvm::appendLoopsToWorklist<Loop &>(Loop &L,
                                     SmallPriorityWorklist<Loop *, 4> &Worklist);
 
 void llvm::appendLoopsToWorklist(LoopInfo &LI,
                                  SmallPriorityWorklist<Loop *, 4> &Worklist) {
   appendReversedLoopsToWorklist(LI, Worklist);
 }
 
+void llvm::appendLoopNestToWorklist(
+    Loop &Root, SmallPriorityWorklist<Loop *, 4> &Worklist) {
+  Worklist.insert(&Root);
+  appendLoopsToWorklist(Root, Worklist);
+}
+
 Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
                       LoopInfo *LI, LPPassManager *LPM) {
   Loop &New = *LI->AllocateLoop();
   if (PL)
     PL->addChildLoop(&New);
   else
     LI->addTopLevelLoop(&New);
 

llvm/test/Transforms/LICM/assume.ll

 ; RUN: opt -licm -basic-aa < %s -S | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop-nest(loop(licm))' < %s -S | FileCheck %s
 
 define void @f_0(i1 %p) nounwind ssp {
 ; CHECK-LABEL: @f_0(
 entry:
   br label %for.body
 
 for.body:
   br i1 undef, label %if.then, label %for.cond.backedge

llvm/test/Transforms/LoopDeletion/invalidation.ll

 ; Ensure we don't run analyses over loops after they've been deleted. We run
 ; one version with a no-op loop pass to make sure that the loop doesn't get
 ; simplified away.
 ;
 ; RUN: opt < %s -passes='require<iv-users>,no-op-loop,require<iv-users>' -S \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK,BEFORE
+; RUN: opt < %s -passes='loop-nest(loop(require<iv-users>,no-op-loop,require<iv-users>))' -S \
+; RUN:     | FileCheck %s --check-prefixes=CHECK,BEFORE
 ; RUN: opt < %s -passes='require<iv-users>,loop-deletion,require<iv-users>' -S \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK,AFTER
+; RUN: opt < %s -passes='loop-nest(loop(require<iv-users>,loop-deletion,require<iv-users>))' -S \
+; RUN:     | FileCheck %s --check-prefixes=CHECK,AFTER
 
 
 define void @foo(i64 %n, i64 %m) nounwind {
 ; CHECK-LABEL: @foo(
 
 entry:
   br label %bb
 ; CHECK:       entry:

llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll

 ; RUN: opt < %s -loop-deletion -S | FileCheck %s
 ; RUN: opt < %s -passes='loop(loop-deletion)' -S | FileCheck %s
+; RUN: opt < %s -passes='loop-nest(loop(loop-deletion))' -S | FileCheck %s
 
 ; ScalarEvolution can prove the loop iteration is finite, even though
 ; it can't represent the exact trip count as an expression. That's
 ; good enough to let the loop be deleted.
 
 ; CHECK:      entry:
 ; CHECK-NEXT:   br label %return
 

llvm/test/Transforms/LoopNest/print.ll

+; RUN: opt -S -passes='loop-nest(print)' < %s 2>&1 >/dev/null | FileCheck %s
+
+; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.cond, Loops: ( for.cond )
+define i32 @f1(i32 %n) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %res.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %res.0, %i.0
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %res.0.lcssa = phi i32 [ %res.0, %for.cond ]
+  ret i32 %res.0.lcssa
+}
+
+; CHECH: IsPerfect=false, Depth=2, OutermostLoop: for.cond, Loops: ( for.cond for.cond1 for.cond5 )
+define i32 @f4(i32 %n) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc12, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc13, %for.inc12 ]
+  %res.0 = phi i32 [ 0, %entry ], [ %res.2.lcssa, %for.inc12 ]
+  %cmp = icmp slt i32 %i.0, %n
+  br i1 %cmp, label %for.body, label %for.end14
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %res.1 = phi i32 [ %res.0, %for.body ], [ %add, %for.inc ]
+  %cmp2 = icmp slt i32 %j.0, %n
+  br i1 %cmp2, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %add = add nsw i32 %res.1, %i.0
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  %res.1.lcssa = phi i32 [ %res.1, %for.cond1 ]
+  br label %for.cond5
+
+for.cond5:                                        ; preds = %for.inc9, %for.end
+  %res.2 = phi i32 [ %res.1.lcssa, %for.end ], [ %add8, %for.inc9 ]
+  %j4.0 = phi i32 [ 0, %for.end ], [ %inc10, %for.inc9 ]
+  %cmp6 = icmp slt i32 %j4.0, %n
+  br i1 %cmp6, label %for.body7, label %for.end11
+
+for.body7:                                        ; preds = %for.cond5
+  %add8 = add nsw i32 %res.2, %j4.0
+  br label %for.inc9
+
+for.inc9:                                         ; preds = %for.body7
+  %inc10 = add nsw i32 %j4.0, 1
+  br label %for.cond5
+
+for.end11:                                        ; preds = %for.cond5
+  %res.2.lcssa = phi i32 [ %res.2, %for.cond5 ]
+  br label %for.inc12
+
+for.inc12:                                        ; preds = %for.end11
+  %inc13 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end14:                                        ; preds = %for.cond
+  %res.0.lcssa = phi i32 [ %res.0, %for.cond ]
+  ret i32 %res.0.lcssa
+}

llvm/test/Transforms/LoopRotate/basic.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
 ; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 ; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop(loop-rotate)' < %s | FileCheck %s
 ; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop-mssa(loop-rotate)' -verify-memoryssa  < %s | FileCheck %s
+; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop-nest(loop(loop-rotate))' < %s | FileCheck %s
+; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop-nest(loop-mssa(loop-rotate))' -verify-memoryssa  < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin10.0.0"
 
 ; PR5319 - The "arrayidx" gep should be hoisted, not duplicated.  We should
 ; end up with one phi node.
 define void @test1() nounwind ssp {
 ; CHECK-LABEL: @test1(

llvm/test/Transforms/LoopRotate/freeze-crash.ll

 ; RUN: opt -loop-rotate -disable-output %s
 ; RUN: opt -passes=loop-rotate -disable-output %s
+; RUN: opt -passes='loop-nest(loop(loop-rotate))' -disable-output %s
 
 ; Make sure we don't crash on this test.
 define void @foo(i32* %arg) {
 bb:
   %tmp = load i32, i32* %arg, align 4
   br label %bb1
 
 bb1:                                              ; preds = %bb7, %bb

llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S < %s -loop-rotate -loop-rotate-multi=true | FileCheck %s
 ; RUN: opt -S < %s -passes='loop(loop-rotate)' -loop-rotate-multi=true | FileCheck %s
+; RUN: opt -S < %s -passes='loop-nest(loop(loop-rotate))' -loop-rotate-multi=true | FileCheck %s
 
 ; Test loop rotation with multiple exits, some of them - deoptimizing.
 ; We should end up with a latch which exit is non-deoptimizing, so we should rotate
 ; more than once.
 
 declare i32 @llvm.experimental.deoptimize.i32(...)
 
 define i32 @test_cond_with_one_deopt_exit(i32 * nonnull %a, i64 %x) {

llvm/test/Transforms/LoopRotate/pr35210.ll

 ;RUN: opt %s -passes='adce,loop(loop-rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate 2>&1 | FileCheck %s
 ;RUN: opt %s -passes='adce,loop-mssa(loop-rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate -verify-memoryssa 2>&1 | FileCheck %s --check-prefix=MSSA
+;RUN: opt %s -passes='adce,loop-nest(loop(loop-rotate)),adce' -S -debug-pass-manager -debug-only=loop-rotate 2>&1 | FileCheck %s --check-prefix=LN
+;RUN: opt %s -passes='adce,loop-nest-mssa(loop-mssa(loop-rotate)),adce' -S -debug-pass-manager -debug-only=loop-rotate -verify-memoryssa 2>&1 | FileCheck %s --check-prefix=LNMSSA
 ;REQUIRES: asserts
 
 ; This test is to make sure we invalidate the post dominator pass after loop rotate simplifies the loop latch.
 ; The adce passes are here to make sure post dominator analysis is required.
 
 ; CHECK: Starting llvm::Function pass manager run.
 ; CHECK-NEXT: Running pass: ADCEPass on f
 ; CHECK-NEXT: Running analysis: PostDominatorTreeAnalysis on f

 ; CHECK-NEXT: Running pass: LoopRotatePass on Loop at depth 1 containing: %bb<header><exiting>,%bb4<latch>
 ; CHECK-NEXT: Folding loop latch bb4 into bb
 ; CHECK-NEXT: Finished Loop pass manager run.
 ; CHECK-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f
 ; CHECK-NEXT: Running pass: ADCEPass on f
 ; CHECK-NEXT: Running analysis: PostDominatorTreeAnalysis on f
 ; CHECK-NEXT: Finished llvm::Function pass manager run.
 
+; LN: Starting llvm::Function pass manager run.
+; LN-NEXT: Running pass: ADCEPass on f
+; LN-NEXT: Running analysis: PostDominatorTreeAnalysis on f
+; LN-NEXT: Starting llvm::Function pass manager run.
+; LN-NEXT: Running pass: LoopSimplifyPass on f
+; LN-NEXT: Running analysis: LoopAnalysis on f
+; LN-NEXT: Running analysis: DominatorTreeAnalysis on f
+; LN-NEXT: Running analysis: AssumptionAnalysis on f
+; LN-NEXT: Running pass: LCSSAPass on f
+; LN-NEXT: Finished llvm::Function pass manager run.
+; LN-NEXT: Running analysis: AAManager on f
+; LN-NEXT: Running analysis: TargetLibraryAnalysis on f
+; LN-NEXT: Running analysis: ScalarEvolutionAnalysis on f
+; LN-NEXT: Running analysis: TargetIRAnalysis on f
+; LN-NEXT: Running analysis: InnerAnalysisManagerProxy{{.*}} on f
+; LN-NEXT: Running analysis: LoopNestAnalysis on Loop at depth 1 containing: %bb<header><exiting>,%bb4<latch>
+; LN-NEXT: Starting LoopNest pass manager run.
+; LN-NEXT: Starting Loop pass manager run.
+; LN-NEXT: Running pass: LoopRotatePass on Loop at depth 1 containing: %bb<header><exiting>,%bb4<latch>
+; LN-NEXT: Folding loop latch bb4 into bb
+; LN-NEXT: Finished Loop pass manager run.
+; LN-NEXT: Finished LoopNest pass manager run.
+; LN-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f
+; LN-NEXT: Running pass: ADCEPass on f
+; LN-NEXT: Running analysis: PostDominatorTreeAnalysis on f
+; LN-NEXT: Finished llvm::Function pass manager run.
+
 ; MSSA: Starting llvm::Function pass manager run.
 ; MSSA-NEXT: Running pass: ADCEPass on f
 ; MSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f
 ; MSSA-NEXT: Starting llvm::Function pass manager run.
 ; MSSA-NEXT: Running pass: LoopSimplifyPass on f
 ; MSSA-NEXT: Running analysis: LoopAnalysis on f
 ; MSSA-NEXT: Running analysis: DominatorTreeAnalysis on f
 ; MSSA-NEXT: Running analysis: AssumptionAnalysis on f

 ; MSSA-NEXT: Running pass: LoopRotatePass on Loop at depth 1 containing: %bb<header><exiting>,%bb4<latch>
 ; MSSA-NEXT: Folding loop latch bb4 into bb
 ; MSSA-NEXT: Finished Loop pass manager run.
 ; MSSA-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f
 ; MSSA-NEXT: Running pass: ADCEPass on f
 ; MSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f
 ; MSSA-NEXT: Finished llvm::Function pass manager run.
 
+; LNMSSA: Starting llvm::Function pass manager run.
+; LNMSSA-NEXT: Running pass: ADCEPass on f
+; LNMSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f
+; LNMSSA-NEXT: Starting llvm::Function pass manager run.
+; LNMSSA-NEXT: Running pass: LoopSimplifyPass on f
+; LNMSSA-NEXT: Running analysis: LoopAnalysis on f
+; LNMSSA-NEXT: Running analysis: DominatorTreeAnalysis on f
+; LNMSSA-NEXT: Running analysis: AssumptionAnalysis on f
+; LNMSSA-NEXT: Running pass: LCSSAPass on f
+; LNMSSA-NEXT: Finished llvm::Function pass manager run.
+; LNMSSA-NEXT: Running analysis: MemorySSAAnalysis on f
+; LNMSSA-NEXT: Running analysis: AAManager on f
+; LNMSSA-NEXT: Running analysis: TargetLibraryAnalysis on f
+; LNMSSA-NEXT: Running analysis: ScalarEvolutionAnalysis on f
+; LNMSSA-NEXT: Running analysis: TargetIRAnalysis on f
+; LNMSSA-NEXT: Running analysis: InnerAnalysisManagerProxy{{.*}} on f
+; LNMSSA-NEXT: Running analysis: LoopNestAnalysis on Loop at depth 1 containing: %bb<header><exiting>,%bb4<latch>
+; LNMSSA-NEXT: Starting LoopNest pass manager run.
+; LNMSSA-NEXT: Starting Loop pass manager run.
+; LNMSSA-NEXT: Running pass: LoopRotatePass on Loop at depth 1 containing: %bb<header><exiting>,%bb4<latch>
+; LNMSSA-NEXT: Folding loop latch bb4 into bb
+; LNMSSA-NEXT: Finished Loop pass manager run.
+; LNMSSA-NEXT: Finished LoopNest pass manager run.
+; LNMSSA-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f
+; LNMSSA-NEXT: Running pass: ADCEPass on f
+; LNMSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f
+; LNMSSA-NEXT: Finished llvm::Function pass manager run.
+
 ; CHECK-LABEL: define i8 @f() {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label %bb
 ; CHECK:       bb:                                               ; preds = %bb, %entry
 ; CHECK-NEXT:    %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ]
 ; CHECK-NEXT:    %tmp5 = icmp eq i8 %mode.0, 1
 ; CHECK-NEXT:    %indvar.next = add i8 %mode.0, 1
 ; CHECK-NEXT:    br i1 %tmp5, label %bb5, label %bb
 ; CHECK:       bb5:                                              ; preds = %bb
 ; CHECK-NEXT:    tail call void @raise_exception() #0
 ; CHECK-NEXT:    unreachable
 ; CHECK-NEXT:  }
 ; CHECK:       ; Function Attrs: noreturn
 ; CHECK:       declare void @raise_exception() #0
 ; CHECK:       attributes #0 = { noreturn }
 
+; LN-LABEL: define i8 @f() {
+; LN-NEXT:  entry:
+; LN-NEXT:    br label %bb
+; LN:       bb:                                               ; preds = %bb, %entry
+; LN-NEXT:    %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ]
+; LN-NEXT:    %tmp5 = icmp eq i8 %mode.0, 1
+; LN-NEXT:    %indvar.next = add i8 %mode.0, 1
+; LN-NEXT:    br i1 %tmp5, label %bb5, label %bb
+; LN:       bb5:                                              ; preds = %bb
+; LN-NEXT:    tail call void @raise_exception() #0
+; LN-NEXT:    unreachable
+; LN-NEXT:  }
+; LN:       ; Function Attrs: noreturn
+; LN:       declare void @raise_exception() #0
+; LN:       attributes #0 = { noreturn }
+
 ; MSSA-LABEL: define i8 @f() {
 ; MSSA-NEXT:  entry:
 ; MSSA-NEXT:    br label %bb
 ; MSSA:       bb:                                               ; preds = %bb, %entry
 ; MSSA-NEXT:    %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ]
 ; MSSA-NEXT:    %tmp5 = icmp eq i8 %mode.0, 1
 ; MSSA-NEXT:    %indvar.next = add i8 %mode.0, 1
 ; MSSA-NEXT:    br i1 %tmp5, label %bb5, label %bb
 ; MSSA:       bb5:                                              ; preds = %bb
 ; MSSA-NEXT:    tail call void @raise_exception() #0
 ; MSSA-NEXT:    unreachable
 ; MSSA-NEXT:  }
 ; MSSA:       ; Function Attrs: noreturn
 ; MSSA:       declare void @raise_exception() #0
 ; MSSA:       attributes #0 = { noreturn }
 
+; LNMSSA-LABEL: define i8 @f() {
+; LNMSSA-NEXT:  entry:
+; LNMSSA-NEXT:    br label %bb
+; LNMSSA:       bb:                                               ; preds = %bb, %entry
+; LNMSSA-NEXT:    %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ]
+; LNMSSA-NEXT:    %tmp5 = icmp eq i8 %mode.0, 1
+; LNMSSA-NEXT:    %indvar.next = add i8 %mode.0, 1
+; LNMSSA-NEXT:    br i1 %tmp5, label %bb5, label %bb
+; LNMSSA:       bb5:                                              ; preds = %bb
+; LNMSSA-NEXT:    tail call void @raise_exception() #0
+; LNMSSA-NEXT:    unreachable
+; LNMSSA-NEXT:  }
+; LNMSSA:       ; Function Attrs: noreturn
+; LNMSSA:       declare void @raise_exception() #0
+; LNMSSA:       attributes #0 = { noreturn }
+
 define i8 @f() {
 entry:
   br label %bb
 
 bb:                                               ; preds = %bb4, %entry
   %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb4 ]
   %tmp5 = icmp eq i8 %mode.0, 1
   br i1 %tmp5, label %bb5, label %bb4

llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp

codegen::setFunctionAttributes(TM->getTargetCPU(),
                                  TM->getTargetFeatureString(), *M);
 
   // Create pass pipeline
   //
 
   PassBuilder PB(TM.get());
 
   LoopAnalysisManager LAM;
+  LoopNestAnalysisManager LNAM(LAM);
   FunctionAnalysisManager FAM;
   CGSCCAnalysisManager CGAM;
   ModulePassManager MPM;
   ModuleAnalysisManager MAM;
 
   FAM.registerPass([&] { return PB.buildDefaultAAPipeline(); });
   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
   PB.registerLoopAnalyses(LAM);
-  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+  PB.registerLoopNestAnalyses(LNAM);
+  PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
 
   auto Err = PB.parsePassPipeline(MPM, PassPipeline, false, false);
   assert(!Err && "Should have been checked during fuzzer initialization");
   // Only fail with assert above, otherwise ignore the parsing error.
   consumeError(std::move(Err));
 
   // Run passes which we need to test
   //

llvm/tools/opt/NewPMDriver.cpp

 //===----------------------------------------------------------------------===//
 
 #include "NewPMDriver.h"
 #include "PassPrinters.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/LoopNestAnalysisManager.h"
 #include "llvm/Bitcode/BitcodeWriterPass.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Verifier.h"
#include "llvm/Support/Extension.def"
   if (!Passes.empty() && !DisableBasicAA) {
     if (auto Err = PB.parseAAPipeline(AA, "basic-aa")) {
       errs() << Arg0 << ": " << toString(std::move(Err)) << "\n";
       return false;
     }
   }
 
   LoopAnalysisManager LAM(DebugPM);
+  LoopNestAnalysisManager LNAM(LAM, DebugPM);
   FunctionAnalysisManager FAM(DebugPM);
   CGSCCAnalysisManager CGAM(DebugPM);
   ModuleAnalysisManager MAM(DebugPM);
 
   // Register the AA manager first so that our version is the one used.
   FAM.registerPass([&] { return std::move(AA); });
 
   // Register all the basic analyses with the managers.
   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
   PB.registerLoopAnalyses(LAM);
-  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+  PB.registerLoopNestAnalyses(LNAM);
+  PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
 
   ModulePassManager MPM(DebugPM);
   if (VK > VK_NoVerifier)
     MPM.addPass(VerifierPass());
   if (EnableDebugify)
     MPM.addPass(NewPMDebugifyPass());
 
   if (!PassPipeline.empty()) {

llvm/unittests/CodeGen/PassManagerTest.cpp

 TEST_F(PassManagerTest, Basic) {
   if (!TM)
     return;
 
   LLVMTargetMachine *LLVMTM = static_cast<LLVMTargetMachine *>(TM.get());
   M->setDataLayout(TM->createDataLayout());
 
   LoopAnalysisManager LAM(/*DebugLogging=*/true);
+  LoopNestAnalysisManager LNAM(LAM, /*DebugLogging=*/true);
   FunctionAnalysisManager FAM(/*DebugLogging=*/true);
   CGSCCAnalysisManager CGAM(/*DebugLogging=*/true);
   ModuleAnalysisManager MAM(/*DebugLogging=*/true);
   PassBuilder PB(TM.get());
   PB.registerModuleAnalyses(MAM);
   PB.registerFunctionAnalyses(FAM);
-  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+  PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
 
   FAM.registerPass([&] { return TestFunctionAnalysis(); });
   FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
   MAM.registerPass([&] { return MachineModuleAnalysis(LLVMTM); });
   MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
 
   MachineFunctionAnalysisManager MFAM;
   {

llvm/unittests/IR/PassBuilderCallbacksTest.cpp

static void invalidateLoop(Loop &L, LoopAnalysisManager &,
                              LoopStandardAnalysisResults &,
                              LPMUpdater &Updater) {
     Updater.markLoopAsDeleted(L, L.getName());
   }
   MockPassHandle() { setDefaults(); }
 };
 
 template <>
+struct MockPassHandle<LoopNest>
+    : MockPassHandleBase<MockPassHandle<LoopNest>, LoopNest,
+                         LoopNestAnalysisManager, LoopStandardAnalysisResults &,
+                         LNPMUpdater &> {
+  MOCK_METHOD4(run,
+               PreservedAnalyses(LoopNest &, LoopNestAnalysisManager &,
+                                 LoopStandardAnalysisResults &, LNPMUpdater &));
+
+  static void invalidateLoopNest(LoopNest &LN, LoopNestAnalysisManager &,
+                                 LoopStandardAnalysisResults &,
+                                 LNPMUpdater &Updater) {
+    Updater.markLoopNestAsDeleted(LN, LN.getName());
+  }
+
+  MockPassHandle() { setDefaults(); }
+};
+
+template <>
 struct MockPassHandle<Function>
     : MockPassHandleBase<MockPassHandle<Function>, Function> {
   MOCK_METHOD2(run, PreservedAnalyses(Function &, FunctionAnalysisManager &));
 
   MockPassHandle() { setDefaults(); }
 };
 
 template <>
struct MockAnalysisHandle<Loop>
 
   MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &,
                                   LoopAnalysisManager::Invalidator &));
 
   MockAnalysisHandle<Loop>() { this->setDefaults(); }
 };
 
 template <>
+struct MockAnalysisHandle<LoopNest>
+    : MockAnalysisHandleBase<MockAnalysisHandle<LoopNest>, Loop,
+                             LoopAnalysisManager,
+                             LoopStandardAnalysisResults &> {
+  MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &,
+                                                LoopStandardAnalysisResults &));
+
+  MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &,
+                                  LoopAnalysisManager::Invalidator &));
+
+  MockAnalysisHandle<LoopNest>() { this->setDefaults(); }
+};
+
+template <>
 struct MockAnalysisHandle<Function>
     : MockAnalysisHandleBase<MockAnalysisHandle<Function>, Function> {
   MOCK_METHOD2(run, Analysis::Result(Function &, FunctionAnalysisManager &));
 
   MOCK_METHOD3(invalidate, bool(Function &, const PreservedAnalyses &,
                                 FunctionAnalysisManager::Invalidator &));
 
   MockAnalysisHandle<Function>() { setDefaults(); }
template <> std::string getName(const StringRef &name) {
   return std::string(name);
 }
 
 template <> std::string getName(const llvm::Any &WrappedIR) {
   if (any_isa<const Module *>(WrappedIR))
     return any_cast<const Module *>(WrappedIR)->getName().str();
   if (any_isa<const Function *>(WrappedIR))
     return any_cast<const Function *>(WrappedIR)->getName().str();
+  if (any_isa<const LoopNest *>(WrappedIR))
+    return any_cast<const LoopNest *>(WrappedIR)->getName().str();
   if (any_isa<const Loop *>(WrappedIR))
     return any_cast<const Loop *>(WrappedIR)->getName().str();
   if (any_isa<const LazyCallGraph::SCC *>(WrappedIR))
     return any_cast<const LazyCallGraph::SCC *>(WrappedIR)->getName();
   return "<UNKNOWN>";
 }
 /// Define a custom matcher for objects which support a 'getName' method.
 ///
protected:
   LLVMContext Context;
   std::unique_ptr<Module> M;
 
   MockPassInstrumentationCallbacks CallbacksHandle;
 
   PassBuilder PB;
   ModulePassManager PM;
   LoopAnalysisManager LAM;
+  LoopNestAnalysisManager LNAM;
   FunctionAnalysisManager FAM;
   CGSCCAnalysisManager CGAM;
   ModuleAnalysisManager AM;
 
   MockPassHandle<IRUnitT> PassHandle;
   MockAnalysisHandle<IRUnitT> AnalysisHandle;
 
   static PreservedAnalyses getAnalysisResult(IRUnitT &U, AnalysisManagerT &AM,
PassBuilderCallbacksTest()
                   "  tail call void @bar()\n"
                   "  %cmp = icmp eq i32 %iv, %n\n"
                   "  br i1 %cmp, label %exit, label %loop\n"
                   "exit:\n"
                   "  ret void\n"
                   "}\n")),
         CallbacksHandle(),
         PB(nullptr, PipelineTuningOptions(), None, &CallbacksHandle.Callbacks),
-        PM(true), LAM(true), FAM(true), CGAM(true), AM(true) {
+        PM(true), LAM(true), LNAM(LAM, true), FAM(true), CGAM(true), AM(true) {
 
     EXPECT_TRUE(&CallbacksHandle.Callbacks ==
                 PB.getPassInstrumentationCallbacks());
 
     /// Register a callback for analysis registration.
     ///
     /// The callback is a function taking a reference to an AnalyisManager
     /// object. When called, the callee gets to register its own analyses with
PB.registerPipelineParsingCallback(
           return false;
         });
 
     /// Register builtin analyses and cross-register the analysis proxies
     PB.registerModuleAnalyses(AM);
     PB.registerCGSCCAnalyses(CGAM);
     PB.registerFunctionAnalyses(FAM);
     PB.registerLoopAnalyses(LAM);
-    PB.crossRegisterProxies(LAM, FAM, CGAM, AM);
+    PB.registerLoopNestAnalyses(LNAM);
+    PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, AM);
   }
 };
 
 using ModuleCallbacksTest = PassBuilderCallbacksTest<ModulePassManager>;
 using CGSCCCallbacksTest = PassBuilderCallbacksTest<CGSCCPassManager>;
 using FunctionCallbacksTest = PassBuilderCallbacksTest<FunctionPassManager>;
+using LoopNestCallbacksTest = PassBuilderCallbacksTest<LoopNestPassManager>;
 using LoopCallbacksTest = PassBuilderCallbacksTest<LoopPassManager>;
 
 /// Test parsing of the name of our mock pass for all IRUnits.
 ///
 /// The pass should by default run our mock analysis and then preserve it.
 TEST_F(ModuleCallbacksTest, Passes) {
   EXPECT_CALL(AnalysisHandle, run(HasName("<string>"), _));
   EXPECT_CALL(PassHandle, run(HasName("<string>"), _))
EXPECT_CALL(CallbacksHandle,
       .Times(0);
 
   StringRef PipelineText = "test-transform";
   ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded())
       << "Pipeline was: " << PipelineText;
   PM.run(*M, AM);
 }
 
+TEST_F(LoopNestCallbacksTest, Passes) {
+  EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _));
+  EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _))
+      .WillOnce(WithArgs<0, 1, 2>(Invoke(getAnalysisResult)));
+  StringRef PipelineText = "test-transform";
+  ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded())
+      << "Pipeline was: " << PipelineText;
+  PM.run(*M, AM);
+}
+
+TEST_F(LoopNestCallbacksTest, InstrumentedPasses) {
+  CallbacksHandle.registerPassInstrumentation();
+  // Non-mock instrumentation not specifically mentioned below can be ignored.
+  CallbacksHandle.ignoreNonMockPassInstrumentation("<string>");
+  CallbacksHandle.ignoreNonMockPassInstrumentation("foo");
+  CallbacksHandle.ignoreNonMockPassInstrumentation("loop");
+
+  EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _));
+  EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _))
+      .WillOnce(WithArgs<0, 1, 2>(Invoke(getAnalysisResult)));
+
+  // PassInstrumentation calls should happen in-sequence, in the same order
+  // as passes/analyses are scheduled.
+  ::testing::Sequence PISequence;
+  EXPECT_CALL(CallbacksHandle,
+              runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(
+      CallbacksHandle,
+      runBeforeNonSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(
+      CallbacksHandle,
+      runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(
+      CallbacksHandle,
+      runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPass(HasNameRegex("MockPassHandle"), HasName("loop"), _))
+      .InSequence(PISequence);
+
+  // Our mock pass does not invalidate IR.
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPassInvalidated(HasNameRegex("MockPassHandle"), _))
+      .Times(0);
+
+  // No passes are skipped, so there should be no calls to
+  // runBeforeSkippedPass().
+  EXPECT_CALL(
+      CallbacksHandle,
+      runBeforeSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop")))
+      .Times(0);
+
+  StringRef PipelineText = "test-transform";
+  ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded())
+      << "Pipeline was: " << PipelineText;
+  PM.run(*M, AM);
+}
+
+TEST_F(LoopNestCallbacksTest, InstrumentedInvalidatingPasses) {
+  CallbacksHandle.registerPassInstrumentation();
+  // Non-mock instrumentation not specifically mentioned below can be ignored.
+  CallbacksHandle.ignoreNonMockPassInstrumentation("<string>");
+  CallbacksHandle.ignoreNonMockPassInstrumentation("foo");
+  CallbacksHandle.ignoreNonMockPassInstrumentation("loop");
+
+  EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _));
+  EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _))
+      .WillOnce(
+          DoAll(WithArgs<0, 1, 2, 3>(Invoke(PassHandle.invalidateLoopNest)),
+                WithArgs<0, 1, 2>(Invoke(getAnalysisResult))));
+
+  // PassInstrumentation calls should happen in-sequence, in the same order
+  // as passes/analyses are scheduled.
+  ::testing::Sequence PISequence;
+  EXPECT_CALL(CallbacksHandle,
+              runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(
+      CallbacksHandle,
+      runBeforeNonSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(
+      CallbacksHandle,
+      runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(
+      CallbacksHandle,
+      runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop")))
+      .InSequence(PISequence);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPassInvalidated(HasNameRegex("MockPassHandle"), _))
+      .InSequence(PISequence);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPassInvalidated(HasNameRegex("^PassManager"), _))
+      .InSequence(PISequence);
+
+  // Our mock pass invalidates IR, thus normal runAfterPass is never called.
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPass(HasNameRegex("MockPassHandle"), HasName("loop"), _))
+      .Times(0);
+
+  StringRef PipelineText = "test-transform";
+  ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded())
+      << "Pipeline was: " << PipelineText;
+  PM.run(*M, AM);
+}
+
+TEST_F(LoopNestCallbacksTest, InstrumentedSkippedPasses) {
+  CallbacksHandle.registerPassInstrumentation();
+  // Non-mock instrumentation run here can safely be ignored.
+  CallbacksHandle.ignoreNonMockPassInstrumentation("<string>");
+  CallbacksHandle.ignoreNonMockPassInstrumentation("foo");
+  CallbacksHandle.ignoreNonMockPassInstrumentation("loop");
+
+  // Skip the pass by returning false.
+  EXPECT_CALL(CallbacksHandle,
+              runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop")))
+      .WillOnce(Return(false));
+  EXPECT_CALL(
+      CallbacksHandle,
+      runBeforeSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop")))
+      .Times(1);
+
+  EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)).Times(0);
+  EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)).Times(0);
+
+  // As the pass is skipped there is no afterPass, beforeAnalysis/afterAnalysis
+  // as well.
+  EXPECT_CALL(CallbacksHandle,
+              runBeforeNonSkippedPass(HasNameRegex("MockPassHandle"), _))
+      .Times(0);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPass(HasNameRegex("MockPassHandle"), _, _))
+      .Times(0);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPassInvalidated(HasNameRegex("MockPassHandle"), _))
+      .Times(0);
+  EXPECT_CALL(CallbacksHandle,
+              runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), _))
+      .Times(0);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), _))
+      .Times(0);
+
+  StringRef PipelineText = "test-transform";
+  ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded())
+      << "Pipeline was: " << PipelineText;
+  PM.run(*M, AM);
+}
+
 TEST_F(LoopCallbacksTest, Passes) {
   EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _));
   EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _))
       .WillOnce(WithArgs<0, 1, 2>(Invoke(getAnalysisResult)));
 
   StringRef PipelineText = "test-transform";
   ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded())
       << "Pipeline was: " << PipelineText;

llvm/unittests/Transforms/Scalar/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Passes
   Support
   ScalarOpts
   TransformUtils
   )
 
 add_llvm_unittest(ScalarTests
   LICMTest.cpp
   LoopPassManagerTest.cpp
+  LoopNestPassManagerTest.cpp
   )
 
 target_link_libraries(ScalarTests PRIVATE LLVMTestingSupport)
 
 # Workaround for the gcc 6.1 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80916.
 if (CMAKE_COMPILER_IS_GNUCXX AND CMAKE_CXX_COMPILER_VERSION VERSION_GREATER 6.0 AND CMAKE_CXX_COMPILER_VERSION VERSION_LESS 9.0)
   set_source_files_properties(LoopPassManagerTest.cpp PROPERTIES COMPILE_FLAGS -Wno-unused-function)
 endif()

llvm/unittests/Transforms/Scalar/LICMTest.cpp

 
 namespace llvm {
 
 TEST(LICMTest, TestSCEVInvalidationOnHoisting) {
   LLVMContext Ctx;
   ModulePassManager MPM;
   PassBuilder PB;
   LoopAnalysisManager LAM;
+  LoopNestAnalysisManager LNAM(LAM);
   FunctionAnalysisManager FAM;
   CGSCCAnalysisManager CGAM;
   ModuleAnalysisManager MAM;
 
   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
   PB.registerLoopAnalyses(LAM);
-  PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+  PB.registerLoopNestAnalyses(LNAM);
+  PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
 
   StringRef PipelineStr = "require<opt-remark-emit>,loop(licm)";
   ASSERT_THAT_ERROR(PB.parsePassPipeline(MPM, PipelineStr), Succeeded());
 
   SMDiagnostic Error;
   StringRef Text = R"(
     define void @foo(i64* %ptr) {
     entry:

llvm/unittests/Transforms/Scalar/LoopNestPassManagerTest.cpp

+//===- unittests/Transforms/Scalar/LoopNestPassManagerTest.cpp - LNPM Test ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/LoopNestPassManager.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
+#include "llvm/Analysis/LoopNestAnalysisManager.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/Regex.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+using namespace llvm;
+
+namespace {
+
+using testing::_;
+using testing::DoDefault;
+using testing::Invoke;
+using testing::InvokeWithoutArgs;
+using testing::Return;
+using testing::WithArgs;
+
+/// A CRTP base for analysis mock handles
+///
+/// This class reconciles mocking with the value semantics implementation of the
+/// AnalysisManager. Analysis mock handles should derive from this class and
+/// call \c setDefault() in their constroctur for wiring up the defaults defined
+/// by this base with their mock run() and invalidate() implementations.
+template <typename DerivedT, typename IRUnitT,
+          typename AnalysisManagerT = AnalysisManager<IRUnitT>,
+          typename... ExtraArgTs>
+class MockAnalysisHandleBase {
+public:
+  class Analysis : public AnalysisInfoMixin<Analysis> {
+    friend AnalysisInfoMixin<Analysis>;
+    friend MockAnalysisHandleBase;
+    static AnalysisKey Key;
+
+    DerivedT *Handle;
+
+    Analysis(DerivedT &Handle) : Handle(&Handle) {
+      static_assert(std::is_base_of<MockAnalysisHandleBase, DerivedT>::value,
+                    "Must pass the derived type to this template!");
+    }
+
+  public:
+    class Result {
+      friend MockAnalysisHandleBase;
+
+      DerivedT *Handle;
+
+      Result(DerivedT &Handle) : Handle(&Handle) {}
+
+    public:
+      // Forward invalidation events to the mock handle.
+      bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA,
+                      typename AnalysisManagerT::Invalidator &Inv) {
+        return Handle->invalidate(IR, PA, Inv);
+      }
+    };
+
+    Result run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs) {
+      return Handle->run(IR, AM, ExtraArgs...);
+    }
+  };
+
+  Analysis getAnalysis() { return Analysis(static_cast<DerivedT &>(*this)); }
+  typename Analysis::Result getResult() {
+    return typename Analysis::Result(static_cast<DerivedT &>(*this));
+  }
+  static StringRef getName() { return llvm::getTypeName<DerivedT>(); }
+
+protected:
+  // FIXME: MSVC seems unable to handle a lambda argument to Invoke from within
+  // the template, so we use a boring static function.
+  static bool invalidateCallback(IRUnitT &IR, const PreservedAnalyses &PA,
+                                 typename AnalysisManagerT::Invalidator &Inv) {
+    auto PAC = PA.template getChecker<Analysis>();
+    return !PAC.preserved() &&
+           !PAC.template preservedSet<AllAnalysesOn<IRUnitT>>();
+  }
+
+  /// Derived classes should call this in their constructor to set up default
+  /// mock actions. (We can't do this in our constructor because this has to
+  /// run after the DerivedT is constructed.)
+  void setDefaults() {
+    ON_CALL(static_cast<DerivedT &>(*this),
+            run(_, _, testing::Matcher<ExtraArgTs>(_)...))
+        .WillByDefault(Return(this->getResult()));
+    ON_CALL(static_cast<DerivedT &>(*this), invalidate(_, _, _))
+        .WillByDefault(Invoke(&invalidateCallback));
+  }
+};
+
+template <typename DerivedT, typename IRUnitT, typename AnalysisManagerT,
+          typename... ExtraArgTs>
+AnalysisKey MockAnalysisHandleBase<DerivedT, IRUnitT, AnalysisManagerT,
+                                   ExtraArgTs...>::Analysis::Key;
+
+/// A CRTP base for pass mock handles
+///
+/// This class reconciles mocking with the value semantics implementation of the
+/// PassManager. Pass mock handles should derive from this class and
+/// call \c setDefault() in their constroctur for wiring up the defaults defined
+/// by this base with their mock run() and invalidate() implementations.
+template <typename DerivedT, typename IRUnitT,
+          typename AnalysisManagerT = AnalysisManager<IRUnitT>,
+          typename... ExtraArgTs>
+class MockPassHandleBase {
+public:
+  class Pass : public PassInfoMixin<Pass> {
+    friend MockPassHandleBase;
+
+    DerivedT *Handle;
+
+    Pass(DerivedT &Handle) : Handle(&Handle) {
+      static_assert(std::is_base_of<MockPassHandleBase, DerivedT>::value,
+                    "Must pass the derived type to this template!");
+    }
+
+  public:
+    PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
+                          ExtraArgTs... ExtraArgs) {
+      return Handle->run(IR, AM, ExtraArgs...);
+    }
+  };
+
+  static StringRef getName() { return llvm::getTypeName<DerivedT>(); }
+
+  Pass getPass() { return Pass(static_cast<DerivedT &>(*this)); }
+
+protected:
+  /// Derived classes should call this in their constructor to set up default
+  /// mock actions. (We can't do this in our constructor because this has to
+  /// run after the DerivedT is constructed.)
+  void setDefaults() {
+    ON_CALL(static_cast<DerivedT &>(*this),
+            run(_, _, testing::Matcher<ExtraArgTs>(_)...))
+        .WillByDefault(Return(PreservedAnalyses::all()));
+  }
+};
+
+struct MockFunctionAnalysisHandle
+    : MockAnalysisHandleBase<MockFunctionAnalysisHandle, Function> {
+  MOCK_METHOD2(run, Analysis::Result(Function &, FunctionAnalysisManager &));
+
+  MOCK_METHOD3(invalidate, bool(Function &, const PreservedAnalyses &,
+                                FunctionAnalysisManager::Invalidator &));
+
+  MockFunctionAnalysisHandle() { setDefaults(); }
+};
+
+template <size_t I = static_cast<size_t>(-1)>
+struct MockLoopNestAnalysisHandleTemplate
+    : MockAnalysisHandleBase<MockLoopNestAnalysisHandleTemplate<I>, Loop,
+                             LoopAnalysisManager,
+                             LoopStandardAnalysisResults &> {
+  using Analysis = typename MockLoopNestAnalysisHandleTemplate::Analysis;
+  MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &,
+                                                LoopStandardAnalysisResults &));
+
+  MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &,
+                                  LoopAnalysisManager::Invalidator &));
+
+  MockLoopNestAnalysisHandleTemplate() { this->setDefaults(); }
+};
+
+using MockLoopNestAnalysisHandle = MockLoopNestAnalysisHandleTemplate<>;
+
+template <size_t I = static_cast<size_t>(-1)>
+struct MockLoopAnalysisHandleTemplate
+    : MockAnalysisHandleBase<MockLoopAnalysisHandleTemplate<I>, Loop,
+                             LoopAnalysisManager,
+                             LoopStandardAnalysisResults &> {
+  using Analysis = typename MockLoopAnalysisHandleTemplate::Analysis;
+  MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &,
+                                                LoopStandardAnalysisResults &));
+
+  MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &,
+                                  LoopAnalysisManager::Invalidator &));
+
+  MockLoopAnalysisHandleTemplate() { this->setDefaults(); }
+};
+
+using MockLoopAnalysisHandle = MockLoopAnalysisHandleTemplate<>;
+
+struct MockModulePassHandle : MockPassHandleBase<MockModulePassHandle, Module> {
+  MOCK_METHOD2(run, PreservedAnalyses(Module &, ModuleAnalysisManager &));
+
+  MockModulePassHandle() { setDefaults(); }
+};
+
+struct MockFunctionPassHandle
+    : MockPassHandleBase<MockFunctionPassHandle, Function> {
+  MOCK_METHOD2(run, PreservedAnalyses(Function &, FunctionAnalysisManager &));
+
+  MockFunctionPassHandle() { setDefaults(); }
+};
+
+struct MockLoopNestPassHandle
+    : MockPassHandleBase<MockLoopNestPassHandle, LoopNest,
+                         LoopNestAnalysisManager, LoopStandardAnalysisResults &,
+                         LNPMUpdater &> {
+  MOCK_METHOD4(run,
+               PreservedAnalyses(LoopNest &, LoopNestAnalysisManager &,
+                                 LoopStandardAnalysisResults &, LNPMUpdater &));
+
+  MockLoopNestPassHandle() { setDefaults(); }
+};
+
+struct MockLoopPassHandle
+    : MockPassHandleBase<MockLoopPassHandle, Loop, LoopAnalysisManager,
+                         LoopStandardAnalysisResults &, LPMUpdater &> {
+  MOCK_METHOD4(run,
+               PreservedAnalyses(Loop &, LoopAnalysisManager &,
+                                 LoopStandardAnalysisResults &, LPMUpdater &));
+
+  MockLoopPassHandle() { setDefaults(); }
+};
+
+/// Helper for HasName matcher that returns getName both for IRUnit and
+/// for IRUnit pointer wrapper into llvm::Any (wrapped by PassInstrumentation).
+template <typename IRUnitT> std::string getName(const IRUnitT &IR) {
+  return std::string(IR.getName());
+}
+
+/// Define a custom matcher for objects which support a 'getName' method.
+///
+/// LLVM often has IR objects or analysis objects which expose a name
+/// and in tests it is convenient to match these by name for readability.
+/// Usually, this name is either a StringRef or a plain std::string. This
+/// matcher supports any type exposing a getName() method of this form whose
+/// return value is compatible with an std::ostream. For StringRef, this uses
+/// the shift operator defined above.
+///
+/// It should be used as:
+///
+///   HasName("my_function")
+///
+/// No namespace or other qualification is required.
+MATCHER_P(HasName, Name, "") {
+  *result_listener << "has name '" << getName(arg) << "'";
+  return Name == getName(arg);
+}
+
+MATCHER_P(HasNameRegex, Name, "") {
+  *result_listener << "has name '" << getName(arg) << "'";
+  llvm::Regex R(Name);
+  return R.match(getName(arg));
+}
+
+std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+  SMDiagnostic Err;
+  return parseAssemblyString(IR, Err, C);
+}
+
+class LoopNestPassManagerTest : public ::testing::Test {
+protected:
+  LLVMContext Context;
+  std::unique_ptr<Module> M;
+
+  LoopAnalysisManager LAM;
+  LoopNestAnalysisManager LNAM;
+  FunctionAnalysisManager FAM;
+  ModuleAnalysisManager MAM;
+
+  MockLoopAnalysisHandle MLAHandle;
+  MockLoopNestAnalysisHandle MLNAHandle;
+
+  MockLoopPassHandle MLPHandle;
+  MockLoopNestPassHandle MLNPHandle;
+  MockFunctionPassHandle MFPHandle;
+  MockModulePassHandle MMPHandle;
+
+  static PreservedAnalyses
+  getLoopNestAnalysisResult(LoopNest &LN, LoopNestAnalysisManager &AM,
+                            LoopStandardAnalysisResults &AR, LNPMUpdater &) {
+    (void)AM.getResult<MockLoopNestAnalysisHandle::Analysis>(LN, AR);
+    return PreservedAnalyses::all();
+  }
+
+  static PreservedAnalyses
+  getLoopAnalysisResult(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &) {
+    (void)AM.getResult<MockLoopAnalysisHandle::Analysis>(L, AR);
+    return PreservedAnalyses::all();
+  }
+
+public:
+  LoopNestPassManagerTest()
+      : M(parseIR(
+            Context,
+            "define void @f(i1* %ptr) {\n"
+            "entry:\n"
+            "  br label %loop.f.0\n"
+            "loop.f.0:\n"
+            "  %cond.0 = load volatile i1, i1* %ptr\n"
+            "  br i1 %cond.0, label %loop.f.0.0.ph, label %end\n"
+            "loop.f.0.0.ph:\n"
+            "  br label %loop.f.0.0\n"
+            "loop.f.0.0:\n"
+            "  %cond.0.0 = load volatile i1, i1* %ptr\n"
+            "  br i1 %cond.0.0, label %loop.f.0.0, label %loop.f.0.1.ph\n"
+            "loop.f.0.1.ph:\n"
+            "  br label %loop.f.0.1\n"
+            "loop.f.0.1:\n"
+            "  %cond.0.1 = load volatile i1, i1* %ptr\n"
+            "  br i1 %cond.0.1, label %loop.f.0.1, label %loop.f.0.latch\n"
+            "loop.f.0.latch:\n"
+            "  br label %loop.f.0\n"
+            "end:\n"
+            "  ret void\n"
+            "}\n"
+            "\n"
+            "define void @g(i1* %ptr) {\n"
+            "entry:\n"
+            "  br label %loop.g.0\n"
+            "loop.g.0:\n"
+            "  %cond.0 = load volatile i1, i1* %ptr\n"
+            "  br i1 %cond.0, label %loop.g.0, label %loop.g.1.ph\n"
+            "loop.g.1.ph:\n"
+            "  br label %loop.g.1\n"
+            "loop.g.1:\n"
+            "  %cond.1 = load volatile i1, i1* %ptr\n"
+            "  br i1 %cond.1, label %loop.g.1.0.ph, label %end\n"
+            "loop.g.1.0.ph:\n"
+            "  br label %loop.g.1.0\n"
+            "loop.g.1.0:\n"
+            "  %cond.1.0 = load volatile i1, i1* %ptr\n"
+            "  br i1 %cond.1.0, label %loop.g.1.0, label %loop.g.1.latch\n"
+            "loop.g.1.latch:\n"
+            "  br label %loop.g.1\n"
+            "end:\n"
+            "  ret void\n"
+            "}\n")),
+        LAM(true), LNAM(LAM, true), FAM(true), MAM(true) {
+    // Register mock analysis.
+    LNAM.registerPass([&] { return MLNAHandle.getAnalysis(); });
+    LAM.registerPass([&] { return MLAHandle.getAnalysis(); });
+
+    // Register loop standard analyses.
+    FAM.registerPass([&] { return DominatorTreeAnalysis(); });
+    FAM.registerPass([&] { return LoopAnalysis(); });
+    FAM.registerPass([&] { return AAManager(); });
+    FAM.registerPass([&] { return AssumptionAnalysis(); });
+    FAM.registerPass([&] { return ScalarEvolutionAnalysis(); });
+    FAM.registerPass([&] { return TargetLibraryAnalysis(); });
+    FAM.registerPass([&] { return TargetIRAnalysis(); });
+    FAM.registerPass([&] { return MemorySSAAnalysis(); });
+
+    // Register loop nest analysis.
+    LNAM.registerPass([&] { return LoopNestAnalysis(); });
+
+    // Register pass instrumentation analysis.
+    LAM.registerPass([&] { return PassInstrumentationAnalysis(); });
+    LNAM.registerPass([&] { return PassInstrumentationAnalysis(); });
+    FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
+    MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
+
+    // Cross register analysis manager proxies.
+    MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
+    FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
+    FAM.registerPass(
+        [&] { return LoopNestAnalysisManagerFunctionProxy(LNAM); });
+    FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); });
+    LNAM.registerPass(
+        [&] { return FunctionAnalysisManagerLoopNestProxy(FAM); });
+    LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); });
+  }
+};
+
+// Make sure that the IR is parsed correctly.
+TEST_F(LoopNestPassManagerTest, ParseIR) {
+  Function &F = *M->begin();
+  ASSERT_THAT(F, HasName("f"));
+  auto FBBI = F.begin();
+  BasicBlock &FEntry = *FBBI++;
+  ASSERT_THAT(FEntry, HasName("entry"));
+  BasicBlock &LoopF0BB = *FBBI++;
+  ASSERT_THAT(LoopF0BB, HasName("loop.f.0"));
+  BasicBlock &LoopF00PHBB = *FBBI++;
+  ASSERT_THAT(LoopF00PHBB, HasName("loop.f.0.0.ph"));
+  BasicBlock &LoopF00BB = *FBBI++;
+  ASSERT_THAT(LoopF00BB, HasName("loop.f.0.0"));
+  BasicBlock &LoopF01PHBB = *FBBI++;
+  ASSERT_THAT(LoopF01PHBB, HasName("loop.f.0.1.ph"));
+  BasicBlock &LoopF01BB = *FBBI++;
+  ASSERT_THAT(LoopF01BB, HasName("loop.f.0.1"));
+  BasicBlock &LoopF0LatchBB = *FBBI++;
+  ASSERT_THAT(LoopF0LatchBB, HasName("loop.f.0.latch"));
+  BasicBlock &FEnd = *FBBI++;
+  ASSERT_THAT(FEnd, HasName("end"));
+  ASSERT_THAT(FBBI, F.end());
+
+  Function &G = *std::next(M->begin());
+  ASSERT_THAT(G, HasName("g"));
+  auto GBBI = G.begin();
+  BasicBlock &GEntry = *GBBI++;
+  ASSERT_THAT(GEntry, HasName("entry"));
+  BasicBlock &LoopG0BB = *GBBI++;
+  ASSERT_THAT(LoopG0BB, HasName("loop.g.0"));
+  BasicBlock &LoopG1PHBB = *GBBI++;
+  ASSERT_THAT(LoopG1PHBB, HasName("loop.g.1.ph"));
+  BasicBlock &LoopG1BB = *GBBI++;
+  ASSERT_THAT(LoopG1BB, HasName("loop.g.1"));
+  BasicBlock &LoopG10PHBB = *GBBI++;
+  ASSERT_THAT(LoopG10PHBB, HasName("loop.g.1.0.ph"));
+  BasicBlock &LoopG10BB = *GBBI++;
+  ASSERT_THAT(LoopG10BB, HasName("loop.g.1.0"));
+  BasicBlock &LoopG1Latch = *GBBI++;
+  ASSERT_THAT(LoopG1Latch, HasName("loop.g.1.latch"));
+  BasicBlock &GEnd = *GBBI++;
+  ASSERT_THAT(GEnd, HasName("end"));
+  ASSERT_THAT(GBBI, G.end());
+}
+
+TEST_F(LoopNestPassManagerTest, Basic) {
+  ModulePassManager MPM(true);
+  ::testing::InSequence MakeExpectationsSequenced;
+
+  // First we first visit all the top-level loop nests in both functions, then
+  // the subloops are visited by the loop passes and loop analyses. By
+  // definition, the top-level loops will be visited by both kinds of passes and
+  // analyses.
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.1.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.1"), _, _));
+
+  {
+    LoopPassManager LPM(true);
+    LPM.addPass(MLPHandle.getPass());
+    LoopNestPassManager LNPM(true);
+    LNPM.addPass(MLNPHandle.getPass());
+    LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM)));
+    FunctionPassManager FPM(true);
+    FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));
+    MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  }
+
+  // Next we reverse the order of loop pass and loop nest pass. The analyses are
+  // perserved and hence never run.
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+
+  {
+    LoopPassManager LPM(true);
+    LPM.addPass(MLPHandle.getPass());
+    LoopNestPassManager LNPM(true);
+    LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM)));
+    LNPM.addPass(MLNPHandle.getPass());
+    FunctionPassManager FPM(true);
+    FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));
+    MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  }
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _))
+      .WillOnce(Return(PreservedAnalyses::none()))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _))
+      .WillOnce(DoDefault())
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult))
+      .WillOnce(Return(PreservedAnalyses::none()));
+
+  {
+    LoopNestPassManager LNPM(true);
+    LNPM.addPass(MLNPHandle.getPass());
+    LNPM.addPass(MLNPHandle.getPass());
+    FunctionPassManager FPM(true);
+    FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));
+    MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  }
+
+  // Inner loops should not be visited by loop nest passes and analyses at all.
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0.0"), _, _, _)).Times(0);
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0.0"), _, _)).Times(0);
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0.1"), _, _, _)).Times(0);
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0.1"), _, _)).Times(0);
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1.0"), _, _, _)).Times(0);
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1.0"), _, _)).Times(0);
+
+  MPM.run(*M, MAM);
+}
+
+// Test that if the top-level loop is marked as deleted by the loop pass, the
+// adaptor should mark the loop nest as deleted as well.
+TEST_F(LoopNestPassManagerTest, DeletionOfTopLevelLoops) {
+  ::testing::InSequence MakeExpectationsSequenced;
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.0"), _, _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.1"), _, _, _));
+  // We mark the top-level loop as deleted in the loop pass, so the loop nest
+  // pass manager should skip the loop nest.
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0"), _, _, _))
+      .WillOnce(WithArgs<0, 3>(Invoke([&](Loop &L, LPMUpdater &U) {
+        U.markLoopAsDeleted(L, L.getName());
+        return PreservedAnalyses::all();
+      })));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)).Times(0);
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _));
+  // The inner loop is mark as deleted, but it does not affect whether the loop
+  // nest pass should be run.
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1.0"), _, _, _))
+      .WillOnce(WithArgs<0, 3>(Invoke([&](Loop &L, LPMUpdater &U) {
+        U.markLoopAsDeleted(L, L.getName());
+        return PreservedAnalyses::all();
+      })));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1"), _, _, _));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _));
+
+  ModulePassManager MPM(true);
+  LoopPassManager LPM(true);
+  LPM.addPass(MLPHandle.getPass());
+  LoopNestPassManager LNPM(true);
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM)));
+  LNPM.addPass(MLNPHandle.getPass());
+  FunctionPassManager FPM(true);
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+
+  MPM.run(*M, MAM);
+}
+
+TEST_F(LoopNestPassManagerTest, FunctionPassInvalidationOfLoopNestAnalyses) {
+  ::testing::Sequence FSequence, GSequence;
+
+  // First, force the analysis result to be computed for each loop nest.
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence);
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _)).InSequence(GSequence);
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)).InSequence(GSequence);
+
+  FunctionPassManager FPM(true);
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+
+  // No need to re-run if we require again from a fresh loop nest pass manager.
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+
+  // All analyses are invalidated (the proxy in particular). In this case the
+  // LoopAnalysisManager (LoopNestAnalysisManager) will be cleared, so the
+  // invalidation will not happen.
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _))
+      .InSequence(FSequence)
+      .WillOnce(Return(PreservedAnalyses::none()));
+
+  // Only the MockLoopNestAnalysisHandle::Analysis is invalidated.
+  PreservedAnalyses PA = getLoopPassPreservedAnalyses();
+  PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+  if (EnableMSSALoopDependency)
+    PA.preserve<MemorySSAAnalysis>();
+
+  EXPECT_CALL(MFPHandle, run(HasName("g"), _))
+      .InSequence(GSequence)
+      .WillOnce(Return(PA));
+  // The analysis result is not invalidated on loop.g.0, so no need to re-run.
+  EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.0"), _, _))
+      .InSequence(GSequence)
+      .WillOnce(Return(false));
+  EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.1"), _, _))
+      .InSequence(GSequence);
+
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence);
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)).InSequence(GSequence);
+
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+
+  ModulePassManager MPM(true);
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+
+  MPM.addPass(
+      createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor(
+          RequireAnalysisLoopNestPass<
+              MockLoopNestAnalysisHandle::Analysis>())));
+
+  MPM.run(*M, MAM);
+}
+
+TEST_F(LoopNestPassManagerTest, LoopNestPassInvalidationOfLoopAnalyses) {
+  ::testing::Sequence FSequence, G0Sequence, G1Sequence;
+
+  // First, force the analysis result to be computed for each loop.
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _))
+      .InSequence(FSequence);
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _))
+      .InSequence(FSequence);
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence);
+
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)).InSequence(G0Sequence);
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.1.0"), _, _))
+      .InSequence(G1Sequence);
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.1"), _, _)).InSequence(G1Sequence);
+
+  LoopNestPassManager LNPM(true);
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
+
+  // No need to re-run if we require again from a fresh loop pass manager.
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _))
+      .InSequence(FSequence)
+      .WillOnce(Return(PreservedAnalyses::none()));
+  EXPECT_CALL(MLAHandle, invalidate(HasName("loop.f.0.0"), _, _))
+      .InSequence(FSequence);
+  EXPECT_CALL(MLAHandle, invalidate(HasName("loop.f.0.1"), _, _))
+      .InSequence(FSequence)
+      .WillOnce(Return(false));
+  EXPECT_CALL(MLAHandle, invalidate(HasName("loop.f.0"), _, _))
+      .InSequence(FSequence);
+
+  // Only the MockLoopAnalysisHandle::Analysis is invalidated.
+  PreservedAnalyses PA = getLoopPassPreservedAnalyses();
+  if (EnableMSSALoopDependency)
+    PA.preserve<MemorySSAAnalysis>();
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _))
+      .InSequence(G0Sequence)
+      .WillOnce(Return(PA));
+  EXPECT_CALL(MLAHandle, invalidate(HasName("loop.g.0"), _, _))
+      .InSequence(G0Sequence);
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _))
+      .InSequence(G1Sequence);
+  LNPM.addPass(MLNPHandle.getPass());
+
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _))
+      .InSequence(FSequence);
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence);
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)).InSequence(G0Sequence);
+
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
+
+  ModulePassManager MPM(true);
+  MPM.addPass(createModuleToFunctionPassAdaptor(
+      createFunctionToLoopNestPassAdaptor(std::move(LNPM))));
+  MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(LoopNestPassManagerTest, ModulePassInvalidationOfLoopNestAnalyses) {
+  ModulePassManager MPM(true);
+  ::testing::InSequence MakeExpectationsSequenced;
+
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _));
+  MPM.addPass(
+      createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor(
+          RequireAnalysisLoopNestPass<
+              MockLoopNestAnalysisHandle::Analysis>())));
+  MPM.addPass(
+      createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor(
+          RequireAnalysisLoopNestPass<
+              MockLoopNestAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = getLoopPassPreservedAnalyses();
+    PA.preserve<FunctionAnalysisManagerModuleProxy>();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    if (EnableMSSALoopDependency)
+      PA.preserve<MemorySSAAnalysis>();
+    return PA;
+  }));
+
+  EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.0"), _, _))
+      .WillOnce(Return(false));
+  EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.1"), _, _));
+
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _));
+
+  MPM.addPass(MMPHandle.getPass());
+  MPM.addPass(
+      createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor(
+          RequireAnalysisLoopNestPass<
+              MockLoopNestAnalysisHandle::Analysis>())));
+  MPM.addPass(
+      createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor(
+          RequireAnalysisLoopNestPass<
+              MockLoopNestAnalysisHandle::Analysis>())));
+  EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = PreservedAnalyses::none();
+    PA.preserveSet<AllAnalysesOn<Function>>();
+    PA.preserveSet<AllAnalysesOn<LoopNest>>();
+    return PA;
+  }));
+
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _));
+  MPM.addPass(MMPHandle.getPass());
+  MPM.addPass(
+      createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor(
+          RequireAnalysisLoopNestPass<
+              MockLoopNestAnalysisHandle::Analysis>())));
+
+  MPM.run(*M, MAM);
+}
+
+// Test that if any of the bundled analyses provided in the LNPM's signature
+// become invalid, the analysis proxy itself becomes invalid and we clear all
+// loop nest analysis and loop analysis results.
+TEST_F(LoopNestPassManagerTest, InvalidationOfBoundedAnalyses) {
+  ModulePassManager MPM(true);
+  FunctionPassManager FPM(true);
+  ::testing::InSequence MakeExpectationsSequenced;
+
+  // First, force the analysis result to be computed for each loop nest.
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  // No need to re-run if we require again from a fresh loop nest pass manager.
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  // Preserving everything but the loop analyses themselves results in
+  // invalidation and running.
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    PreservedAnalyses PA = getLoopPassPreservedAnalyses();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    return PA;
+  }));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    PreservedAnalyses PA = getLoopPassPreservedAnalyses();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    PA.preserve<MockLoopNestAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    PreservedAnalyses PA = getLoopPassPreservedAnalyses();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    PA.preserve<MockLoopAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  // The rest don't invalidate analyses, they only trigger re-runs because we
+  // clear the cache completely.
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = PreservedAnalyses::none();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    // Abandon `AAManager`.
+    PA.abandon<AAManager>();
+    PA.preserve<AssumptionAnalysis>();
+    PA.preserve<DominatorTreeAnalysis>();
+    PA.preserve<LoopAnalysis>();
+    PA.preserve<LoopAnalysisManagerFunctionProxy>();
+    PA.preserve<ScalarEvolutionAnalysis>();
+    PA.preserve<MockLoopAnalysisHandle::Analysis>();
+    PA.preserve<MockLoopNestAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = PreservedAnalyses::none();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    PA.preserve<AAManager>();
+    // Not preserving `AssumptionAnalysis`.
+    PA.preserve<DominatorTreeAnalysis>();
+    PA.preserve<LoopAnalysis>();
+    PA.preserve<LoopAnalysisManagerFunctionProxy>();
+    PA.preserve<ScalarEvolutionAnalysis>();
+    PA.preserve<ScalarEvolutionAnalysis>();
+    PA.preserve<MockLoopAnalysisHandle::Analysis>();
+    PA.preserve<MockLoopNestAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  // Special case: AssumptionAnalysis will never be invalidated.
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = PreservedAnalyses::none();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    PA.preserve<AAManager>();
+    PA.preserve<AssumptionAnalysis>();
+    // Abandon `DominatorTreeAnalysis`.
+    PA.abandon<DominatorTreeAnalysis>();
+    PA.preserve<LoopAnalysis>();
+    PA.preserve<LoopAnalysisManagerFunctionProxy>();
+    PA.preserve<ScalarEvolutionAnalysis>();
+    PA.preserve<MockLoopAnalysisHandle::Analysis>();
+    PA.preserve<MockLoopNestAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = PreservedAnalyses::none();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    PA.preserve<AAManager>();
+    PA.preserve<AssumptionAnalysis>();
+    PA.preserve<DominatorTreeAnalysis>();
+    // Abandon the `LoopAnalysis`.
+    PA.abandon<LoopAnalysis>();
+    PA.preserve<LoopAnalysisManagerFunctionProxy>();
+    PA.preserve<ScalarEvolutionAnalysis>();
+    PA.preserve<MockLoopAnalysisHandle::Analysis>();
+    PA.preserve<MockLoopNestAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = PreservedAnalyses::none();
+    PA.preserve<AAManager>();
+    PA.preserve<AssumptionAnalysis>();
+    PA.preserve<DominatorTreeAnalysis>();
+    PA.preserve<LoopAnalysis>();
+    // Abandon the `LoopNestAnalysisManagerFunctionProxy`.
+    PA.abandon<LoopAnalysisManagerFunctionProxy>();
+    PA.preserve<ScalarEvolutionAnalysis>();
+    PA.preserve<MockLoopAnalysisHandle::Analysis>();
+    PA.preserve<MockLoopNestAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
+    auto PA = PreservedAnalyses::none();
+    PA.preserve<LoopNestAnalysisManagerFunctionProxy>();
+    PA.preserve<AAManager>();
+    PA.preserve<AssumptionAnalysis>();
+    PA.preserve<DominatorTreeAnalysis>();
+    PA.preserve<LoopAnalysis>();
+    PA.preserve<LoopAnalysisManagerFunctionProxy>();
+    // Abandon `ScalarEvolutionAnalysis`.
+    PA.abandon<ScalarEvolutionAnalysis>();
+    PA.preserve<MockLoopAnalysisHandle::Analysis>();
+    PA.preserve<MockLoopNestAnalysisHandle::Analysis>();
+    return PA;
+  }));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _));
+  FPM.addPass(MFPHandle.getPass());
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      RequireAnalysisLoopNestPass<MockLoopNestAnalysisHandle::Analysis>()));
+  FPM.addPass(
+      createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor(
+          RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
+
+  // The loop analyses and loop nest analyses will be run only on the first
+  // time. The results are cached in the remaining passes.
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.1.0"), _, _));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.g.1"), _, _));
+  EXPECT_CALL(MFPHandle, run(HasName("g"), _)).Times(9);
+
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  MPM.run(*M, MAM);
+}
+
+// Test that if a loop analysis is not preserved in the LoopNestPass, the
+// analysis results on the corresponding subtree will all be invalidated.
+TEST_F(LoopNestPassManagerTest, InvalidationOfLoopAnalysesInSubtree) {
+  ::testing::Sequence F0Sequence, G0Sequence, G1Sequence;
+
+  // Register two kinds of loop analyses.
+  enum : size_t { A, B };
+  MockLoopAnalysisHandleTemplate<A> MLAHandleA;
+  MockLoopAnalysisHandleTemplate<B> MLAHandleB;
+
+  LAM.registerPass([&] { return MLAHandleA.getAnalysis(); });
+  LAM.registerPass([&] { return MLAHandleB.getAnalysis(); });
+
+  // Force both kinds of analyses to be cached on all loops.
+  EXPECT_CALL(MLAHandleA, run(HasName("loop.f.0.0"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleA, run(HasName("loop.f.0.1"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleA, run(HasName("loop.f.0"), _, _))
+      .InSequence(F0Sequence);
+
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0.0"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0.1"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0"), _, _))
+      .InSequence(F0Sequence);
+
+  EXPECT_CALL(MLAHandleA, run(HasName("loop.g.0"), _, _))
+      .InSequence(G0Sequence);
+  EXPECT_CALL(MLAHandleA, run(HasName("loop.g.1.0"), _, _))
+      .InSequence(G1Sequence);
+  EXPECT_CALL(MLAHandleA, run(HasName("loop.g.1"), _, _))
+      .InSequence(G1Sequence);
+
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.g.0"), _, _))
+      .InSequence(G0Sequence);
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.g.1.0"), _, _))
+      .InSequence(G1Sequence);
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.g.1"), _, _))
+      .InSequence(G1Sequence);
+
+  LoopNestPassManager LNPM(true);
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<A>::Analysis>()));
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<B>::Analysis>()));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _))
+      .InSequence(G0Sequence);
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _))
+      .InSequence(G1Sequence);
+
+  LNPM.addPass(MLNPHandle.getPass());
+
+  // The analyses results should be cached and the analysis passes don't have to
+  // be executed again after the loop nest pass.
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<A>::Analysis>()));
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<B>::Analysis>()));
+
+  // The loop nest pass does not preserve loop analysis B on loop nest f.0,
+  // which means that analysis B will indeed be invalidated on loops f.0.0,
+  // f.0.1, and f.0.
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _))
+      .InSequence(F0Sequence)
+      .WillOnce(InvokeWithoutArgs([] {
+        PreservedAnalyses PA;
+        PA.preserveSet<AllAnalysesOn<Function>>();
+        PA.preserve<MockLoopAnalysisHandleTemplate<A>::Analysis>();
+        return PA;
+      }));
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0.0"), _, _))
+      .InSequence(F0Sequence);
+  // Returns false on purpose: the analysis pass should be skipped.
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0.1"), _, _))
+      .InSequence(F0Sequence)
+      .WillOnce(Return(false));
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0"), _, _))
+      .InSequence(F0Sequence);
+
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0.0"), _, _));
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0.1"), _, _));
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0"), _, _));
+
+  // On loop nest g.0, although both analysis A and B are preserved, the
+  // `invalidation` method will still be invoked since `AllAnalysesOn<Loop>` is
+  // not preserved. However, the analysis results are still valid so no need to
+  // re-run analysis passes in this case.
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _))
+      .InSequence(G0Sequence)
+      .WillOnce(InvokeWithoutArgs([] {
+        PreservedAnalyses PA;
+        PA.preserveSet<AllAnalysesOn<Function>>();
+        PA.preserve<MockLoopAnalysisHandleTemplate<A>::Analysis>();
+        PA.preserve<MockLoopAnalysisHandleTemplate<B>::Analysis>();
+        return PA;
+      }));
+
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.g.0"), _, _));
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.g.0"), _, _));
+
+  // On loop nest g.1, all loop analyses are marked as preserved. In this case,
+  // the `invalidation` method of the subloops will not be called.
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _))
+      .InSequence(G1Sequence)
+      .WillOnce(InvokeWithoutArgs([] {
+        PreservedAnalyses PA;
+        PA.preserveSet<AllAnalysesOn<Function>>();
+        PA.preserveSet<AllAnalysesOn<Loop>>();
+        return PA;
+      }));
+
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.g.1"), _, _)).Times(0);
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.g.1.0"), _, _)).Times(0);
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.g.1"), _, _)).Times(0);
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.g.1.0"), _, _)).Times(0);
+
+  LNPM.addPass(MLNPHandle.getPass());
+
+  // On loop nest f.0, only analysis pass B will be re-run.
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0.0"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0"), _, _))
+      .InSequence(F0Sequence);
+
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<A>::Analysis>()));
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<B>::Analysis>()));
+
+  // Invalidating loop analysis results in subloops will not affect each other.
+  // In other words, the invalidation will not be propagate to the loop nest
+  // pass manager since AllAnalysesOn<Loop> is preserved in the adaptor.
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.0"), _, _, _))
+      .InSequence(F0Sequence)
+      .WillOnce(InvokeWithoutArgs([] {
+        PreservedAnalyses PA;
+        PA.preserve<MockLoopAnalysisHandleTemplate<A>::Analysis>();
+        return PA;
+      }));
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0.0"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0.0"), _, _))
+      .InSequence(F0Sequence);
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.1"), _, _, _))
+      .InSequence(F0Sequence)
+      .WillOnce(InvokeWithoutArgs([] {
+        PreservedAnalyses PA;
+        PA.preserve<MockLoopAnalysisHandleTemplate<B>::Analysis>();
+        return PA;
+      }));
+  EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0.1"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0.1"), _, _))
+      .InSequence(F0Sequence);
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.f.0"), _, _, _))
+      .InSequence(F0Sequence);
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _))
+      .InSequence(G0Sequence);
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1.0"), _, _, _))
+      .InSequence(G1Sequence);
+  EXPECT_CALL(MLPHandle, run(HasName("loop.g.1"), _, _, _))
+      .InSequence(G1Sequence);
+
+  EXPECT_CALL(MLAHandleA, run(HasName("loop.f.0.1"), _, _))
+      .InSequence(F0Sequence);
+  EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0.0"), _, _))
+      .InSequence(F0Sequence);
+
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(MLPHandle.getPass()));
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<A>::Analysis>()));
+  LNPM.addPass(createLoopNestToLoopPassAdaptor(
+      RequireAnalysisLoopPass<MockLoopAnalysisHandleTemplate<B>::Analysis>()));
+
+  ModulePassManager MPM(true);
+  MPM.addPass(createModuleToFunctionPassAdaptor(
+      createFunctionToLoopNestPassAdaptor(std::move(LNPM))));
+
+  MPM.run(*M, MAM);
+}
+
+TEST_F(LoopNestPassManagerTest, RevisitCurrentLoopNest) {
+  M = parseIR(Context, "define void @f(i1* %ptr) {\n"
+                       "entry:\n"
+                       "  br label %loop.0\n"
+                       "loop.0:\n"
+                       "  %cond.0 = load volatile i1, i1* %ptr\n"
+                       "  br i1 %cond.0, label %loop.0, label %loop.1.ph\n"
+                       "loop.1.ph:\n"
+                       "  br label %loop.1\n"
+                       "loop.1:\n"
+                       "  %cond.1 = load volatile i1, i1* %ptr\n"
+                       "  br i1 %cond.1, label %loop.1, label %end\n"
+                       "end:\n"
+                       "  ret void\n"
+                       "}\n");
+  Function &F = *M->begin();
+  ASSERT_THAT(F, HasName("f"));
+  auto BBI = F.begin();
+  BasicBlock &EntryBB = *BBI++;
+  ASSERT_THAT(EntryBB, HasName("entry"));
+  BasicBlock &Loop0BB = *BBI++;
+  ASSERT_THAT(Loop0BB, HasName("loop.0"));
+  BasicBlock &Loop1PHBB = *BBI++;
+  ASSERT_THAT(Loop1PHBB, HasName("loop.1.ph"));
+  BasicBlock &Loop1BB = *BBI++;
+  ASSERT_THAT(Loop1BB, HasName("loop.1"));
+  BasicBlock &EndBB = *BBI++;
+  ASSERT_THAT(EndBB, HasName("end"));
+  ASSERT_THAT(BBI, F.end());
+
+  ModulePassManager MPM(true);
+  LoopNestPassManager LNPM(true);
+
+  ::testing::InSequence MakeExpectationsSequenced;
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.0"), _, _));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(WithArgs<3>(Invoke([&](LNPMUpdater &U) {
+        U.revisitCurrentLoopNest();
+        return PreservedAnalyses::all();
+      })));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.0"), _, _, _))
+      .Times(3)
+      .WillRepeatedly(Invoke(getLoopNestAnalysisResult));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.1"), _, _));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(WithArgs<3>(Invoke([&](LNPMUpdater &U) {
+        U.revisitCurrentLoopNest();
+        return PreservedAnalyses::all();
+      })));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .Times(3)
+      .WillRepeatedly(Invoke(getLoopNestAnalysisResult));
+
+  LNPM.addPass(MLNPHandle.getPass());
+  LNPM.addPass(MLNPHandle.getPass());
+  LNPM.addPass(MLNPHandle.getPass());
+
+  MPM.addPass(createModuleToFunctionPassAdaptor(
+      createFunctionToLoopNestPassAdaptor(std::move(LNPM))));
+  MPM.run(*M, MAM);
+}
+
+// Test the functionality of `addNewLoopNests()`. This includes adding loop
+// nests directly in loop nest passes, or indirectly via addition of top-level
+// loops in loop passes.
+TEST_F(LoopNestPassManagerTest, TopLevelLoopInsertion) {
+  M = parseIR(Context,
+              "define void @f(i1* %ptr) {\n"
+              "entry:\n"
+              "  br label %loop.0\n"
+              "loop.0:\n"
+              "  %cond.0 = load volatile i1, i1* %ptr\n"
+              "  br i1 %cond.0, label %loop.0.0.ph, label %loop.2.ph\n"
+              "loop.0.0.ph:\n"
+              "  br label %loop.0.0\n"
+              "loop.0.0:\n"
+              "  %cond.0.0 = load volatile i1, i1* %ptr\n"
+              "  br i1 %cond.0.0, label %loop.0.0, label %loop.0.2.ph\n"
+              "loop.0.2.ph:\n"
+              "  br label %loop.0.2\n"
+              "loop.0.2:\n"
+              "  %cond.0.2 = load volatile i1, i1* %ptr\n"
+              "  br i1 %cond.0.2, label %loop.0.2, label %loop.0.latch\n"
+              "loop.0.latch:\n"
+              "  br label %loop.0\n"
+              "loop.2.ph:\n"
+              "  br label %loop.2\n"
+              "loop.2:\n"
+              "  %cond.2 = load volatile i1, i1* %ptr\n"
+              "  br i1 %cond.2, label %loop.2, label %end\n"
+              "end:\n"
+              "  ret void\n"
+              "}\n");
+  // Build up variables referring into the IR so we can rewrite it below
+  // easily.
+  Function &F = *M->begin();
+  ASSERT_THAT(F, HasName("f"));
+  Argument &Ptr = *F.arg_begin();
+  auto BBI = F.begin();
+  BasicBlock &EntryBB = *BBI++;
+  ASSERT_THAT(EntryBB, HasName("entry"));
+  BasicBlock &Loop0BB = *BBI++;
+  ASSERT_THAT(Loop0BB, HasName("loop.0"));
+  BasicBlock &Loop00PHBB = *BBI++;
+  ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph"));
+  BasicBlock &Loop00BB = *BBI++;
+  ASSERT_THAT(Loop00BB, HasName("loop.0.0"));
+  BasicBlock &Loop02PHBB = *BBI++;
+  ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph"));
+  BasicBlock &Loop02BB = *BBI++;
+  ASSERT_THAT(Loop02BB, HasName("loop.0.2"));
+  BasicBlock &Loop0LatchBB = *BBI++;
+  ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch"));
+  BasicBlock &Loop2PHBB = *BBI++;
+  ASSERT_THAT(Loop2PHBB, HasName("loop.2.ph"));
+  BasicBlock &Loop2BB = *BBI++;
+  ASSERT_THAT(Loop2BB, HasName("loop.2"));
+  BasicBlock &EndBB = *BBI++;
+  ASSERT_THAT(EndBB, HasName("end"));
+  ASSERT_THAT(BBI, F.end());
+
+  ::testing::InSequence MakeExpectationsSequenced;
+  FunctionPassManager FPM(true);
+
+  // First we add loop.0.1 between loop.0.0 and loop.0.2. This should not
+  // trigger the addition of top-level loop.
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
+      .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM,
+                           LoopStandardAnalysisResults &AR, LPMUpdater &U) {
+        getLoopAnalysisResult(L, AM, AR, U);
+        auto *NewLoop01 = AR.LI.AllocateLoop();
+        L.getParentLoop()->addChildLoop(NewLoop01);
+        auto *NewLoop01PHBB =
+            BasicBlock::Create(Context, "loop.0.1.ph", &F, &Loop02PHBB);
+        auto *NewLoop01BB =
+            BasicBlock::Create(Context, "loop.0.1", &F, &Loop02PHBB);
+        BranchInst::Create(NewLoop01BB, NewLoop01PHBB);
+        auto *NewCond01 = new LoadInst(Type::getInt1Ty(Context), &Ptr,
+                                       "cond.0.1", true, NewLoop01BB);
+        BranchInst::Create(&Loop02PHBB, NewLoop01BB, NewCond01, NewLoop01BB);
+        Loop00BB.getTerminator()->replaceUsesOfWith(&Loop02PHBB, NewLoop01PHBB);
+        AR.DT.addNewBlock(NewLoop01PHBB, &Loop00BB);
+        auto *NewDTNode = AR.DT.addNewBlock(NewLoop01BB, NewLoop01PHBB);
+        AR.DT.changeImmediateDominator(AR.DT[&Loop02PHBB], NewDTNode);
+        EXPECT_TRUE(AR.DT.verify());
+        L.getParentLoop()->addBasicBlockToLoop(NewLoop01PHBB, AR.LI);
+        NewLoop01->addBasicBlockToLoop(NewLoop01BB, AR.LI);
+        L.getParentLoop()->verifyLoop();
+        U.addSiblingLoops({NewLoop01});
+        return getLoopPassPreservedAnalyses();
+      }));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.2"), _, _));
+
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(
+      createLoopNestToLoopPassAdaptor(MLPHandle.getPass())));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.0"), _, _));
+  // The previous pass does not preserve the analysis result.
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  // loop.0.1 is added later
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM,
+                           LoopStandardAnalysisResults &AR, LPMUpdater &U) {
+        getLoopAnalysisResult(L, AM, AR, U);
+        auto *NewLoop1 = AR.LI.AllocateLoop();
+        AR.LI.addTopLevelLoop(NewLoop1);
+        auto *NewLoop10 = AR.LI.AllocateLoop();
+        NewLoop1->addChildLoop(NewLoop10);
+        auto *NewLoop1PHBB =
+            BasicBlock::Create(Context, "loop.1.ph", &F, &Loop2PHBB);
+        auto *NewLoop1BB =
+            BasicBlock::Create(Context, "loop.1", &F, &Loop2PHBB);
+        auto *NewLoop10PHBB =
+            BasicBlock::Create(Context, "loop.1.0.ph", &F, &Loop2PHBB);
+        auto *NewLoop10BB =
+            BasicBlock::Create(Context, "loop.1.0", &F, &Loop2PHBB);
+        auto *NewLoop1LatchBB =
+            BasicBlock::Create(Context, "loop.1.latch", &F, &Loop2PHBB);
+        BranchInst::Create(NewLoop1BB, NewLoop1PHBB);
+        BranchInst::Create(NewLoop10BB, NewLoop10PHBB);
+        auto *NewCond1 = new LoadInst(Type::getInt1Ty(Context), &Ptr, "cond.1",
+                                      true, NewLoop1BB);
+        BranchInst::Create(NewLoop10PHBB, &Loop2PHBB, NewCond1, NewLoop1BB);
+        auto *NewCond10 = new LoadInst(Type::getInt1Ty(Context), &Ptr,
+                                       "cond.1.0", true, NewLoop10BB);
+        BranchInst::Create(NewLoop10BB, NewLoop1LatchBB, NewCond10,
+                           NewLoop10BB);
+        BranchInst::Create(NewLoop1BB, NewLoop1LatchBB);
+        Loop0BB.getTerminator()->replaceUsesOfWith(&Loop2PHBB, NewLoop1PHBB);
+
+        AR.DT.addNewBlock(NewLoop1PHBB, &Loop0BB);
+        AR.DT.addNewBlock(NewLoop1BB, NewLoop1PHBB);
+        AR.DT.addNewBlock(NewLoop10PHBB, NewLoop1BB);
+        AR.DT.addNewBlock(NewLoop10BB, NewLoop10PHBB);
+        AR.DT.addNewBlock(NewLoop1LatchBB, NewLoop10BB);
+        AR.DT.changeImmediateDominator(AR.DT[&Loop2PHBB], AR.DT[NewLoop1BB]);
+        EXPECT_TRUE(AR.DT.verify());
+        NewLoop1->addBasicBlockToLoop(NewLoop1BB, AR.LI);
+        NewLoop1->addBasicBlockToLoop(NewLoop10PHBB, AR.LI);
+        NewLoop10->addBasicBlockToLoop(NewLoop10BB, AR.LI);
+        NewLoop1->addBasicBlockToLoop(NewLoop1LatchBB, AR.LI);
+        NewLoop1->verifyLoop();
+        U.addSiblingLoops({NewLoop1});
+        auto PA = getLoopPassPreservedAnalyses();
+        PA.preserve<LoopNestAnalysis>();
+        return PA;
+      }));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.1"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.1.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.1.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.1"), _, _));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.2"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+
+  {
+    LoopNestPassManager LNPM(true);
+    LNPM.addPass(MLNPHandle.getPass());
+    LNPM.addPass(createLoopNestToLoopPassAdaptor(MLPHandle.getPass()));
+    FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));
+  }
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.0"), _, _));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(MLNPHandle.getPass()));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.1.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke([&](LoopNest &LN, LoopNestAnalysisManager &AM,
+                           LoopStandardAnalysisResults &AR, LNPMUpdater &U) {
+        getLoopNestAnalysisResult(LN, AM, AR, U);
+        auto *NewLoop3 = AR.LI.AllocateLoop();
+        auto *NewLoop4 = AR.LI.AllocateLoop();
+        auto *NewLoop40 = AR.LI.AllocateLoop();
+        auto *NewLoop41 = AR.LI.AllocateLoop();
+        AR.LI.addTopLevelLoop(NewLoop3);
+        AR.LI.addTopLevelLoop(NewLoop4);
+        NewLoop4->addChildLoop(NewLoop40);
+        NewLoop4->addChildLoop(NewLoop41);
+        auto *NewLoop3PHBB =
+            BasicBlock::Create(Context, "loop.3.ph", &F, &EndBB);
+        auto *NewLoop3BB = BasicBlock::Create(Context, "loop.3", &F, &EndBB);
+        auto *NewLoop4PHBB =
+            BasicBlock::Create(Context, "loop.4.ph", &F, &EndBB);
+        auto *NewLoop4BB = BasicBlock::Create(Context, "loop.4", &F, &EndBB);
+        auto *NewLoop40PHBB =
+            BasicBlock::Create(Context, "loop.4.0.ph", &F, &EndBB);
+        auto *NewLoop40BB = BasicBlock::Create(Context, "loop.4.0", &F, &EndBB);
+        auto *NewLoop41PHBB =
+            BasicBlock::Create(Context, "loop.4.1.ph", &F, &EndBB);
+        auto *NewLoop41BB = BasicBlock::Create(Context, "loop.4.1", &F, &EndBB);
+        auto *NewLoop4LatchBB =
+            BasicBlock::Create(Context, "loop.4.latch", &F, &EndBB);
+        BranchInst::Create(NewLoop4BB, NewLoop4PHBB);
+        BranchInst::Create(NewLoop40BB, NewLoop40PHBB);
+        BranchInst::Create(NewLoop41BB, NewLoop41PHBB);
+        BranchInst::Create(NewLoop4BB, NewLoop4LatchBB);
+        auto *NewCond4 = new LoadInst(Type::getInt1Ty(Context), &Ptr, "cond.4",
+                                      true, NewLoop4BB);
+        BranchInst::Create(NewLoop40PHBB, &EndBB, NewCond4, NewLoop4BB);
+        auto *NewCond40 = new LoadInst(Type::getInt1Ty(Context), &Ptr,
+                                       "cond.4.0", true, NewLoop40BB);
+        BranchInst::Create(NewLoop40BB, NewLoop41PHBB, NewCond40, NewLoop40BB);
+        auto *NewCond41 = new LoadInst(Type::getInt1Ty(Context), &Ptr,
+                                       "cond.4.1", true, NewLoop41BB);
+        BranchInst::Create(NewLoop41BB, NewLoop4LatchBB, NewCond41,
+                           NewLoop41BB);
+        BranchInst::Create(NewLoop3BB, NewLoop3PHBB);
+        auto *NewCond3 = new LoadInst(Type::getInt1Ty(Context), &Ptr, "cond.3",
+                                      true, NewLoop3BB);
+        BranchInst::Create(NewLoop3BB, NewLoop4PHBB, NewCond3, NewLoop3BB);
+        Loop2BB.getTerminator()->replaceUsesOfWith(&EndBB, NewLoop3PHBB);
+
+        AR.DT.addNewBlock(NewLoop3PHBB, &Loop2BB);
+        AR.DT.addNewBlock(NewLoop3BB, NewLoop3PHBB);
+        AR.DT.addNewBlock(NewLoop4PHBB, NewLoop3BB);
+        AR.DT.addNewBlock(NewLoop4BB, NewLoop4PHBB);
+        AR.DT.addNewBlock(NewLoop40PHBB, NewLoop4BB);
+        AR.DT.addNewBlock(NewLoop40BB, NewLoop40PHBB);
+        AR.DT.addNewBlock(NewLoop41PHBB, NewLoop40BB);
+        AR.DT.addNewBlock(NewLoop41BB, NewLoop41PHBB);
+        AR.DT.addNewBlock(NewLoop4LatchBB, NewLoop41BB);
+        AR.DT.changeImmediateDominator(AR.DT[&EndBB], AR.DT[NewLoop4BB]);
+        EXPECT_TRUE(AR.DT.verify());
+
+        NewLoop3->addBasicBlockToLoop(NewLoop3BB, AR.LI);
+        NewLoop4->addBasicBlockToLoop(NewLoop4BB, AR.LI);
+        NewLoop4->addBasicBlockToLoop(NewLoop40PHBB, AR.LI);
+        NewLoop4->addBasicBlockToLoop(NewLoop41PHBB, AR.LI);
+        NewLoop4->addBasicBlockToLoop(NewLoop4LatchBB, AR.LI);
+        NewLoop40->addBasicBlockToLoop(NewLoop40BB, AR.LI);
+        NewLoop41->addBasicBlockToLoop(NewLoop41BB, AR.LI);
+        NewLoop3->verifyLoop();
+        NewLoop4->verifyLoop();
+        U.addNewLoopNests({NewLoop3, NewLoop4});
+        auto PA = getLoopPassPreservedAnalyses();
+        PA.preserve<LoopNestAnalysis>();
+        return PA;
+      }));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.2"), _, _));
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.4"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.4"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.4.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.4.0"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.4.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.4.1"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.4"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.4"), _, _));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.3"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.3"), _, _));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.3"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLAHandle, run(HasName("loop.3"), _, _));
+
+  {
+    LoopNestPassManager LNPM(true);
+    LNPM.addPass(MLNPHandle.getPass());
+    LNPM.addPass(createLoopNestToLoopPassAdaptor(MLPHandle.getPass()));
+    FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM)));
+  }
+
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.4"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.3"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke(getLoopNestAnalysisResult));
+  EXPECT_CALL(MLNAHandle, run(HasName("loop.2"), _, _));
+
+  FPM.addPass(createFunctionToLoopNestPassAdaptor(MLNPHandle.getPass()));
+
+  EXPECT_CALL(MLPHandle, run(HasName("loop.4.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.4.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.4"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.3"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.1.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+  EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _))
+      .WillOnce(Invoke(getLoopAnalysisResult));
+
+  FPM.addPass(createFunctionToLoopPassAdaptor(MLPHandle.getPass()));
+
+  FPM.addPass(DominatorTreeVerifierPass());
+  FPM.addPass(LoopVerifierPass());
+  ModulePassManager MPM(true);
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+
+  MPM.run(*M, MAM);
+
+  // Finally check the correctness of the loop structure after the addition of
+  // new loops.
+  {
+    Function &F = *M->begin();
+    ASSERT_THAT(F, HasName("f"));
+    auto BBI = F.begin();
+    BasicBlock &EntryBB = *BBI++;
+    ASSERT_THAT(EntryBB, HasName("entry"));
+    BasicBlock &Loop0BB = *BBI++;
+    ASSERT_THAT(Loop0BB, HasName("loop.0"));
+    BasicBlock &Loop00PHBB = *BBI++;
+    ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph"));
+    BasicBlock &Loop00BB = *BBI++;
+    ASSERT_THAT(Loop00BB, HasName("loop.0.0"));
+    BasicBlock &Loop01PHBB = *BBI++;
+    ASSERT_THAT(Loop01PHBB, HasName("loop.0.1.ph"));
+    BasicBlock &Loop01BB = *BBI++;
+    ASSERT_THAT(Loop01BB, HasName("loop.0.1"));
+    BasicBlock &Loop02PHBB = *BBI++;
+    ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph"));
+    BasicBlock &Loop02BB = *BBI++;
+    ASSERT_THAT(Loop02BB, HasName("loop.0.2"));
+    BasicBlock &Loop0LatchBB = *BBI++;
+    ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch"));
+    BasicBlock &Loop1PHBB = *BBI++;
+    ASSERT_THAT(Loop1PHBB, HasName("loop.1.ph"));
+    BasicBlock &Loop1BB = *BBI++;
+    ASSERT_THAT(Loop1BB, HasName("loop.1"));
+    BasicBlock &Loop10PHBB = *BBI++;
+    ASSERT_THAT(Loop10PHBB, HasName("loop.1.0.ph"));
+    BasicBlock &Loop10BB = *BBI++;
+    ASSERT_THAT(Loop10BB, HasName("loop.1.0"));
+    BasicBlock &Loop1LatchBB = *BBI++;
+    ASSERT_THAT(Loop1LatchBB, HasName("loop.1.latch"));
+    BasicBlock &Loop2PHBB = *BBI++;
+    ASSERT_THAT(Loop2PHBB, HasName("loop.2.ph"));
+    BasicBlock &Loop2BB = *BBI++;
+    ASSERT_THAT(Loop2BB, HasName("loop.2"));
+    BasicBlock &Loop3PHBB = *BBI++;
+    ASSERT_THAT(Loop3PHBB, HasName("loop.3.ph"));
+    BasicBlock &Loop3BB = *BBI++;
+    ASSERT_THAT(Loop3BB, HasName("loop.3"));
+    BasicBlock &Loop4PHBB = *BBI++;
+    ASSERT_THAT(Loop4PHBB, HasName("loop.4.ph"));
+    BasicBlock &Loop4BB = *BBI++;
+    ASSERT_THAT(Loop4BB, HasName("loop.4"));
+    BasicBlock &Loop40PHBB = *BBI++;
+    ASSERT_THAT(Loop40PHBB, HasName("loop.4.0.ph"));
+    BasicBlock &Loop40BB = *BBI++;
+    ASSERT_THAT(Loop40BB, HasName("loop.4.0"));
+    BasicBlock &Loop41PHBB = *BBI++;
+    ASSERT_THAT(Loop41PHBB, HasName("loop.4.1.ph"));
+    BasicBlock &Loop41BB = *BBI++;
+    ASSERT_THAT(Loop41BB, HasName("loop.4.1"));
+    BasicBlock &Loop4LatchBB = *BBI++;
+    ASSERT_THAT(Loop4LatchBB, HasName("loop.4.latch"));
+    BasicBlock &EndBB = *BBI++;
+    ASSERT_THAT(EndBB, HasName("end"));
+    ASSERT_THAT(BBI, F.end());
+  }
+}
+
+} // namespace

polly/unittests/ScopPassManager/PassManagerTest.cpp

 using namespace polly;
 using namespace llvm;
 
 namespace {
 class ScopPassRegistry : public ::testing::Test {
 protected:
   ModuleAnalysisManager MAM;
   FunctionAnalysisManager FAM;
+  LoopNestAnalysisManager LNAM;
   LoopAnalysisManager LAM;
   CGSCCAnalysisManager CGAM;
   ScopAnalysisManager SAM;
   AAManager AM;
 
 public:
   ScopPassRegistry(ScopPassRegistry &&) = delete;
   ScopPassRegistry(const ScopPassRegistry &) = delete;
   ScopPassRegistry &operator=(ScopPassRegistry &&) = delete;
   ScopPassRegistry &operator=(const ScopPassRegistry &) = delete;
-  ScopPassRegistry() {
+  ScopPassRegistry() : LNAM(LAM) {
     PassBuilder PB;
 
     AM = PB.buildDefaultAAPipeline();
     PB.registerModuleAnalyses(MAM);
     PB.registerFunctionAnalyses(FAM);
     PB.registerLoopAnalyses(LAM);
+    PB.registerLoopNestAnalyses(LNAM);
     PB.registerCGSCCAnalyses(CGAM);
 
     FAM.registerPass([] { return ScopAnalysis(); });
     FAM.registerPass([] { return ScopInfoAnalysis(); });
     FAM.registerPass([this] { return ScopAnalysisManagerFunctionProxy(SAM); });
 
     // SAM.registerPass([] { return IslAstAnalysis(); });
     // SAM.registerPass([] { return DependenceAnalysis(); });
     SAM.registerPass([this] { return FunctionAnalysisManagerScopProxy(FAM); });
 
-    PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
+    PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM);
   }
 };
 
 TEST_F(ScopPassRegistry, PrintScops) {
   FunctionPassManager FPM;
   FPM.addPass(ScopAnalysisPrinterPass(errs()));
 }