PM: Implement a basic loop pass manager

[bogner]

Summary

This creates the new-style LoopPassManager and wires it up with dummy
and print passes.

TODO:

• Is a BasicBlock name sufficient for Loop::getName(), or should we include the containing function's name as well?
• LoopAnalysisManagerFunctionProxy::run could use an assert to ensure that we don't run Loop Analyses before the proxy is created, but this can't work without a good model for invalidating the cache between functions. Note: this is an existing issue with FunctionAMModuleProxy as well.
• There is no LoopVerifierPass. This can be added later.

[chandlerc]

OMG, the delaays reviewing. So sorry.

Most of this is excellent. I think the tricky question is around handling the mutation of the loop nest correctly. I wonder if it'd be worthwhile to just rip handling of that out entirely in order to land the rest and then support mutation as a follow-up patch so we can look at the alternatives there without having so much boiler plate hanging in a patch?

include/llvm/Analysis/LoopInfo.h

473–478

I think this is fine, the caller can dig out more info as needed.

include/llvm/Analysis/LoopPassManager.h

41–44

This trait isn't really commented, but I see what you're using it for (at least I think so -- to stop the LoopPassManager when the current loop gets deleted?).

That technique feels a bit clumsy to me. What do you think about instead expanding the LoopPassManager to just be its own beast and have loop-specific logic where it halts the passes if the loop itself goes away, and logs helpfully? Maybe we could sink some of the boilerplate into a base class so it is reasonably easy to define a custom pass manager here?

214–218

Why not a worklist rather than explicit recursion? Either way, either inline the code or if still recursive use a lambda rather than a helper function?

232

Why a deque? It looks like we just push_back, so a vector (or smallvector) would seem more appropriate?

233

Some comment about the reverse?

236–237

It's a bit odd that you don't directly handle updates to the loop structure here. I feel like you could by potentially avoiding the queue above entirely and directly sinking this into the recursive walk over the LoopInfo so that as passes update LoopInfo, in turn your traversal is kept up-to-date.

As part of that, maybe check that passes preserve LoopInfo here?

[bogner]

This was superceded years ago...

include/llvm/Analysis/LoopInfo.h

     return DebugLoc();
   }
 
+  StringRef getName() const {
+    // TODO: Is the name of the header block sufficient, or should we have
+    // something like "<function> loop <header block>"?
+    if (BasicBlock *Header = getHeader())
+      if (Header->hasName())
+        return Header->getName();
+    return "<unnamed loop>";
+  }
+
 private:
   friend class LoopInfoBase<BasicBlock, Loop>;
   explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}

include/llvm/Analysis/LoopPassManager.h

+//===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This header provides classes for managing passes over loops in LLVM IR.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOPPASSMANAGER_H
+#define LLVM_ANALYSIS_LOOPPASSMANAGER_H
+
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/PassManager.h"
+#include <deque>
+
+namespace llvm {
+
+/// \brief The loop pass manager.
+///
+/// See the documentation for the PassManager template for details. It runs a
+/// sequency of loop passes over each loop that the manager is run over. This
+/// typedef serves as a convenient way to refer to this construct.
+typedef PassManager<Loop> LoopPassManager;
+
+/// \brief The loop analysis manager.
+///
+/// See the documentation for the AnalysisManager template for detail
+/// documentation. This typedef serves as a convenient way to refer to this
+/// construct in the adaptors and proxies used to integrate this into the larger
+/// pass manager infrastructure.
+typedef AnalysisManager<Loop> LoopAnalysisManager;
+
+template <> class IRUnitTraits<Loop> {
+public:
+  static bool hasBeenInvalidated(Loop &IR) { return IR.isInvalid(); }
+};
+
+/// \brief A function analysis which acts as a proxy for a loop analysis
+/// manager.
+///
+/// This primarily proxies invalidation information from the function analysis
+/// manager and function pass manager to a loop analysis manager. You should
+/// never use a loop analysis manager from within (transitively) a function
+/// pass manager unless your parent function pass has received a proxy result
+/// object for it.
+class LoopAnalysisManagerFunctionProxy {
+public:
+  class Result {
+  public:
+    explicit Result(LoopAnalysisManager &LAM) : LAM(&LAM) {}
+    // We have to explicitly define all the special member functions because
+    // MSVC refuses to generate them.
+    Result(const Result &Arg) : LAM(Arg.LAM) {}
+    Result(Result &&Arg) : LAM(std::move(Arg.LAM)) {}
+    Result &operator=(Result RHS) {
+      std::swap(LAM, RHS.LAM);
+      return *this;
+    }
+    ~Result();
+
+    /// \brief Accessor for the \c LoopAnalysisManager.
+    LoopAnalysisManager &getManager() { return *LAM; }
+
+    /// \brief Handler for invalidation of the function.
+    ///
+    /// If this analysis itself is preserved, then we assume that the function
+    /// hasn't changed and thus we don't need to invalidate *all* cached data
+    /// associated with a \c Loop* in the \c LoopAnalysisManager.
+    ///
+    /// Regardless of whether this analysis is marked as preserved, all of the
+    /// analyses in the \c LoopAnalysisManager are potentially invalidated based
+    /// on the set of preserved analyses.
+    bool invalidate(Function &F, const PreservedAnalyses &PA);
+
+  private:
+    LoopAnalysisManager *LAM;
+  };
+
+  static void *ID() { return (void *)&PassID; }
+
+  static StringRef name() { return "LoopAnalysisManagerFunctionProxy"; }
+
+  explicit LoopAnalysisManagerFunctionProxy(LoopAnalysisManager &LAM)
+      : LAM(&LAM) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  LoopAnalysisManagerFunctionProxy(const LoopAnalysisManagerFunctionProxy &Arg)
+      : LAM(Arg.LAM) {}
+  LoopAnalysisManagerFunctionProxy(LoopAnalysisManagerFunctionProxy &&Arg)
+      : LAM(std::move(Arg.LAM)) {}
+  LoopAnalysisManagerFunctionProxy &
+  operator=(LoopAnalysisManagerFunctionProxy RHS) {
+    std::swap(LAM, RHS.LAM);
+    return *this;
+  }
+
+  /// \brief Run the analysis pass and create our proxy result object.
+  ///
+  /// This doesn't do any interesting work, it is primarily used to insert our
+  /// proxy result object into the function analysis cache so that we can proxy
+  /// invalidation to the loop analysis manager.
+  ///
+  /// In debug builds, it will also assert that the analysis manager is empty as
+  /// no queries should arrive at the loop analysis manager prior to this
+  /// analysis being requested.
+  Result run(Function &F);
+
+private:
+  static char PassID;
+
+  LoopAnalysisManager *LAM;
+};
+
+/// \brief A loop analysis which acts as a proxy for a function analysis
+/// manager.
+///
+/// This primarily provides an accessor to a parent function analysis manager to
+/// loop passes. Only the const interface of the function analysis manager is
+/// provided to indicate that once inside of a loop analysis pass you cannot
+/// request a function analysis to actually run. Instead, the user must rely on
+/// the \c getCachedResult API.
+///
+/// This proxy *doesn't* manage the invalidation in any way. That is handled by
+/// the recursive return path of each layer of the pass manager and the
+/// returned PreservedAnalysis set.
+class FunctionAnalysisManagerLoopProxy {
+public:
+  /// \brief Result proxy object for \c FunctionAnalysisManagerLoopProxy.
+  class Result {
+  public:
+    explicit Result(const FunctionAnalysisManager &FAM) : FAM(&FAM) {}
+    // We have to explicitly define all the special member functions because
+    // MSVC refuses to generate them.
+    Result(const Result &Arg) : FAM(Arg.FAM) {}
+    Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
+    Result &operator=(Result RHS) {
+      std::swap(FAM, RHS.FAM);
+      return *this;
+    }
+
+    const FunctionAnalysisManager &getManager() const { return *FAM; }
+
+    /// \brief Handle invalidation by ignoring it, this pass is immutable.
+    bool invalidate(Function &) { return false; }
+
+  private:
+    const FunctionAnalysisManager *FAM;
+  };
+
+  static void *ID() { return (void *)&PassID; }
+
+  static StringRef name() { return "FunctionAnalysisManagerLoopProxy"; }
+
+  FunctionAnalysisManagerLoopProxy(const FunctionAnalysisManager &FAM)
+      : FAM(&FAM) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  FunctionAnalysisManagerLoopProxy(const FunctionAnalysisManagerLoopProxy &Arg)
+      : FAM(Arg.FAM) {}
+  FunctionAnalysisManagerLoopProxy(FunctionAnalysisManagerLoopProxy &&Arg)
+      : FAM(std::move(Arg.FAM)) {}
+  FunctionAnalysisManagerLoopProxy &
+  operator=(FunctionAnalysisManagerLoopProxy RHS) {
+    std::swap(FAM, RHS.FAM);
+    return *this;
+  }
+
+  /// \brief Run the analysis pass and create our proxy result object.
+  /// Nothing to see here, it just forwards the \c FAM reference into the
+  /// result.
+  Result run(Loop &) { return Result(*FAM); }
+
+private:
+  static char PassID;
+
+  const FunctionAnalysisManager *FAM;
+};
+
+/// \brief 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:
+  explicit FunctionToLoopPassAdaptor(LoopPassT Pass)
+      : Pass(std::move(Pass)) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  FunctionToLoopPassAdaptor(const FunctionToLoopPassAdaptor &Arg)
+      : Pass(Arg.Pass) {}
+  FunctionToLoopPassAdaptor(FunctionToLoopPassAdaptor &&Arg)
+      : Pass(std::move(Arg.Pass)) {}
+  friend void swap(FunctionToLoopPassAdaptor &LHS,
+                   FunctionToLoopPassAdaptor &RHS) {
+    using std::swap;
+    swap(LHS.Pass, RHS.Pass);
+  }
+  FunctionToLoopPassAdaptor &operator=(FunctionToLoopPassAdaptor RHS) {
+    swap(*this, RHS);
+    return *this;
+  }
+
+  void enqueueLoop(Loop *L, std::deque<Loop *> &LQ) {
+    LQ.push_back(L);
+    for (auto *NestedLoop : reverse(*L))
+      enqueueLoop(NestedLoop, LQ);
+  }
+
+  /// \brief Runs the loop passes across every loop in the function.
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager *AM) {
+    assert(AM && "We need analyses to compute the loop structure!");
+
+    // Setup the loop analysis manager from its proxy.
+    LoopAnalysisManager *LAM =
+        &AM->getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
+    // Get the loop structure for this function
+    LoopInfo &LI = AM->getResult<LoopAnalysis>(F);
+
+    PreservedAnalyses PA = PreservedAnalyses::all();
+
+    std::deque<Loop *> LQ;
+    for (auto *L : reverse(LI))
+      enqueueLoop(L, LQ);
+
+    for (auto *L : reverse(LQ)) {
+      PreservedAnalyses PassPA = Pass.run(*L, LAM);
+
+      // We know that the loop pass couldn't have invalidated any other loop's
+      // analyses (that's the contract of a loop pass), so directly handle the
+      // loop analysis manager's invalidation here.  Also, update the
+      // preserved analyses to reflect that once invalidated these can again
+      // be preserved.
+      PassPA = LAM->invalidate(*L, std::move(PassPA));
+
+      // Then intersect the preserved set so that invalidation of module
+      // analyses will eventually occur when the module pass completes.
+      PA.intersect(std::move(PassPA));
+    }
+
+    // By definition we preserve the proxy. 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.preserve<LoopAnalysisManagerFunctionProxy>();
+    return PA;
+  }
+
+  static StringRef name() { return "FunctionToLoopPassAdaptor"; }
+
+private:
+  LoopPassT Pass;
+};
+
+/// \brief A function to deduce a loop pass type and wrap it in the templated
+/// adaptor.
+template <typename LoopPassT>
+FunctionToLoopPassAdaptor<LoopPassT>
+createFunctionToLoopPassAdaptor(LoopPassT Pass) {
+  return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass));
+}
+}
+
+#endif // LLVM_ANALYSIS_LOOPPASSMANAGER_H

include/llvm/IR/PassManager.h

 // Forward declare the analysis manager template.
 template <typename IRUnitT> class AnalysisManager;
 
+template <typename IRUnitT> class IRUnitTraits {
+public:
+  static bool hasBeenInvalidated(IRUnitT &IR) { return false; }
+};
+
 /// \brief Manages a sequence of passes over units of IR.
 ///
 /// A pass manager contains a sequence of passes to run over units of IR. It is

       // context and it isn't yet clear what the right pattern is for yielding
       // in the new pass manager so it is currently omitted.
       //IR.getContext().yield();
+
+      if (IRUnitTraits<IRUnitT>::hasBeenInvalidated(IR)) {
+        if (DebugLogging)
+          dbgs() << IR.getName() << " is invalid. Skipping remaining passes.\n";
+        break;
+      }
     }
 
     if (DebugLogging)

include/llvm/Passes/PassBuilder.h

 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/LoopPassManager.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {

   /// still manually register any additional analyses.
   void registerFunctionAnalyses(FunctionAnalysisManager &FAM);
 
+  /// \brief 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);
+
   /// \brief Parse a textual pass pipeline description into a \c ModulePassManager.
   ///
   /// The format of the textual pass pipeline description looks something like:

   bool parseModulePassName(ModulePassManager &MPM, StringRef Name);
   bool parseCGSCCPassName(CGSCCPassManager &CGPM, StringRef Name);
   bool parseFunctionPassName(FunctionPassManager &FPM, StringRef Name);
+  bool parseLoopPassName(LoopPassManager &LPM, StringRef Name);
+  bool parseLoopPassPipeline(LoopPassManager &LPM, StringRef &PipelineText,
+                             bool VerifyEachPass, bool DebugLogging);
   bool parseFunctionPassPipeline(FunctionPassManager &FPM,
                                  StringRef &PipelineText, bool VerifyEachPass,
                                  bool DebugLogging);

   bool parseModulePassPipeline(ModulePassManager &MPM, StringRef &PipelineText,
                                bool VerifyEachPass, bool DebugLogging);
 };
-
 }
 
 #endif

lib/Analysis/CMakeLists.txt

   LoopAccessAnalysis.cpp
   LoopInfo.cpp
   LoopPass.cpp
+  LoopPassManager.cpp
   MemDepPrinter.cpp
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp

lib/Analysis/LoopPassManager.cpp

+//===- LoopPassManager.cpp - Loop pass management -------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopPassManager.h"
+
+using namespace llvm;
+
+char LoopAnalysisManagerFunctionProxy::PassID;
+
+LoopAnalysisManagerFunctionProxy::Result
+LoopAnalysisManagerFunctionProxy::run(Function &F) {
+  // TODO: In FunctionAnalysisManagerModuleProxy we assert that the
+  // AnalysisManager is empty, but if we do that here we run afoul of the fact
+  // that we still have results for previous functions alive. Should we be
+  // clearing those when we finish a function?
+  //assert(LAM->empty() && "Loop analyses ran prior to the function proxy!");
+  return Result(*LAM);
+}
+
+LoopAnalysisManagerFunctionProxy::Result::~Result() {
+  // Clear out the analysis manager if we're being destroyed -- it means we
+  // didn't even see an invalidate call when we got invalidated.
+  LAM->clear();
+}
+
+bool LoopAnalysisManagerFunctionProxy::Result::invalidate(
+    Function &F, const PreservedAnalyses &PA) {
+  // If this proxy isn't marked as preserved, then we can't even invalidate
+  // individual loop analyses, there may be an invalid set of Loops in the cache
+  // making it impossible to incrementally preserve them. Just clear the entire
+  // manager.
+  if (!PA.preserved(ID()))
+    LAM->clear();
+
+  // Return false to indicate that this result is still a valid proxy.
+  return false;
+}
+
+char FunctionAnalysisManagerLoopProxy::PassID;

lib/Passes/PassBuilder.cpp

 
 char NoOpFunctionAnalysis::PassID;
 
+/// \brief No-op loop pass which does nothing.
+struct NoOpLoopPass {
+  PreservedAnalyses run(Loop &L) { return PreservedAnalyses::all(); }
+  static StringRef name() { return "NoOpLoopPass"; }
+};
+
+/// \brief No-op loop analysis.
+struct NoOpLoopAnalysis {
+  struct Result {};
+  Result run(Loop &) { return Result(); }
+  static StringRef name() { return "NoOpLoopAnalysis"; }
+  static void *ID() { return (void *)&PassID; }
+private:
+  static char PassID;
+};
+
+char NoOpLoopAnalysis::PassID;
+
 } // End anonymous namespace.
 
 void PassBuilder::registerModuleAnalyses(ModuleAnalysisManager &MAM) {

 #include "PassRegistry.def"
 }
 
+void PassBuilder::registerLoopAnalyses(LoopAnalysisManager &LAM) {
+#define LOOP_ANALYSIS(NAME, CREATE_PASS) \
+  LAM.registerPass(CREATE_PASS);
+#include "PassRegistry.def"
+}
+
 #ifndef NDEBUG
 static bool isModulePassName(StringRef Name) {
 #define MODULE_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;

   return false;
 }
 
+static bool isLoopPassName(StringRef Name) {
+#define LOOP_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
+#define LOOP_ANALYSIS(NAME, CREATE_PASS)                                       \
+  if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
+    return true;
+#include "PassRegistry.def"
+
+  return false;
+}
+
 bool PassBuilder::parseModulePassName(ModulePassManager &MPM, StringRef Name) {
 #define MODULE_PASS(NAME, CREATE_PASS)                                         \
   if (Name == NAME) {                                                          \

   return false;
 }
 
+bool PassBuilder::parseLoopPassName(LoopPassManager &FPM,
+                                    StringRef Name) {
+#define LOOP_PASS(NAME, CREATE_PASS)                                           \
+  if (Name == NAME) {                                                          \
+    FPM.addPass(CREATE_PASS);                                                  \
+    return true;                                                               \
+  }
+#define LOOP_ANALYSIS(NAME, CREATE_PASS)                                       \
+  if (Name == "require<" NAME ">") {                                           \
+    FPM.addPass(RequireAnalysisPass<decltype(CREATE_PASS)>());                 \
+    return true;                                                               \
+  }                                                                            \
+  if (Name == "invalidate<" NAME ">") {                                        \
+    FPM.addPass(InvalidateAnalysisPass<decltype(CREATE_PASS)>());              \
+    return true;                                                               \
+  }
+#include "PassRegistry.def"
+
+  return false;
+}
+
+bool PassBuilder::parseLoopPassPipeline(LoopPassManager &LPM,
+                                        StringRef &PipelineText,
+                                        bool VerifyEachPass,
+                                        bool DebugLogging) {
+  for (;;) {
+    // Parse nested pass managers by recursing.
+    if (PipelineText.startswith("loop(")) {
+      LoopPassManager NestedLPM(DebugLogging);
+
+      // Parse the inner pipeline inte the nested manager.
+      PipelineText = PipelineText.substr(strlen("loop("));
+      if (!parseLoopPassPipeline(NestedLPM, PipelineText, VerifyEachPass,
+                                 DebugLogging) ||
+          PipelineText.empty())
+        return false;
+      assert(PipelineText[0] == ')');
+      PipelineText = PipelineText.substr(1);
+
+      // Add the nested pass manager with the appropriate adaptor.
+      LPM.addPass(std::move(NestedLPM));
+    } else {
+      // Otherwise try to parse a pass name.
+      size_t End = PipelineText.find_first_of(",)");
+      if (!parseLoopPassName(LPM, PipelineText.substr(0, End)))
+        return false;
+      // TODO: Ideally, we would run a LoopVerifierPass() here in the
+      // VerifyEachPass case, but we don't have such a verifier yet.
+
+      PipelineText = PipelineText.substr(End);
+    }
+
+    if (PipelineText.empty() || PipelineText[0] == ')')
+      return true;
+
+    assert(PipelineText[0] == ',');
+    PipelineText = PipelineText.substr(1);
+  }
+}
+
 bool PassBuilder::parseFunctionPassPipeline(FunctionPassManager &FPM,
                                             StringRef &PipelineText,
                                             bool VerifyEachPass,

 
       // Add the nested pass manager with the appropriate adaptor.
       FPM.addPass(std::move(NestedFPM));
+    } else if (PipelineText.startswith("loop(")) {
+      LoopPassManager NestedLPM(DebugLogging);
+
+      // Parse the inner pipeline inte the nested manager.
+      PipelineText = PipelineText.substr(strlen("loop("));
+      if (!parseLoopPassPipeline(NestedLPM, PipelineText, VerifyEachPass,
+                                 DebugLogging) ||
+          PipelineText.empty())
+        return false;
+      assert(PipelineText[0] == ')');
+      PipelineText = PipelineText.substr(1);
+
+      // Add the nested pass manager with the appropriate adaptor.
+      FPM.addPass(createFunctionToLoopPassAdaptor(std::move(NestedLPM)));
     } else {
       // Otherwise try to parse a pass name.
       size_t End = PipelineText.find_first_of(",)");

 
   // If this looks like a CGSCC pass, parse the whole thing as a CGSCC
   // pipeline.
-  if (isCGSCCPassName(FirstName)) {
+  if (PipelineText.startswith("cgscc(") || isCGSCCPassName(FirstName)) {
     CGSCCPassManager CGPM(DebugLogging);
     if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass,
                                 DebugLogging) ||

 
   // Similarly, if this looks like a Function pass, parse the whole thing as
   // a Function pipelien.
-  if (isFunctionPassName(FirstName)) {
+  if (PipelineText.startswith("function(") || isFunctionPassName(FirstName)) {
     FunctionPassManager FPM(DebugLogging);
     if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass,
                                    DebugLogging) ||

     return true;
   }
 
+  // If this looks like a Loop pass, parse the whole thing as a Loop pipeline.
+  if (PipelineText.startswith("loop(") || isLoopPassName(FirstName)) {
+    LoopPassManager LPM(DebugLogging);
+    if (!parseLoopPassPipeline(LPM, PipelineText, VerifyEachPass,
+                               DebugLogging) ||
+        !PipelineText.empty())
+      return false;
+    FunctionPassManager FPM(DebugLogging);
+    FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
+    MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+    return true;
+  }
+
+
   return false;
 }

lib/Passes/PassRegistry.def

 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 #undef FUNCTION_PASS
+
+#ifndef LOOP_ANALYSIS
+#define LOOP_ANALYSIS(NAME, CREATE_PASS)
+#endif
+LOOP_ANALYSIS("no-op-loop", NoOpLoopAnalysis())
+#undef LOOP_ANALYSIS
+
+#ifndef LOOP_PASS
+#define LOOP_PASS(NAME, CREATE_PASS)
+#endif
+LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())
+LOOP_PASS("no-op-loop", NoOpLoopPass())
+LOOP_PASS("print", PrintLoopPass(dbgs()))
+#undef LOOP_PASS

test/Other/loop-pass-ordering.ll

+; RUN: opt -disable-output -debug-pass-manager \
+; RUN:     -passes='no-op-loop' %s 2>&1 \
+; RUN:     | FileCheck %s
+
+;            @f()
+;           /    \
+;       loop.0   loop.1
+;      /      \        \
+; loop.0.0  loop.0.1  loop.1.0
+;
+; CHECK: Running pass: NoOpLoopPass on loop.1.0
+; CHECK: Running pass: NoOpLoopPass on loop.1
+; CHECK: Running pass: NoOpLoopPass on loop.0.0
+; CHECK: Running pass: NoOpLoopPass on loop.0.1
+; CHECK: Running pass: NoOpLoopPass on loop.0
+define void @f() {
+entry:
+  br label %loop.0
+loop.0:
+  br i1 undef, label %loop.0.0, label %loop.1
+loop.0.0:
+  br i1 undef, label %loop.0.0, label %loop.0.1
+loop.0.1:
+  br i1 undef, label %loop.0.1, label %loop.0
+loop.1:
+  br i1 undef, label %loop.1, label %loop.1.bb1
+loop.1.bb1:
+  br i1 undef, label %loop.1, label %loop.1.bb2
+loop.1.bb2:
+  br i1 undef, label %end, label %loop.1.0
+loop.1.0:
+  br i1 undef, label %loop.1.0, label %loop.1
+end:
+  ret void
+}

test/Other/pass-pipeline-parsing.ll

 ; CHECK-NESTED-MP-CG-FP: Finished pass manager
 ; CHECK-NESTED-MP-CG-FP: Finished pass manager
 
+; RUN: opt -disable-output -debug-pass-manager \
+; RUN:     -passes='no-op-loop,no-op-loop' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-TWO-NOOP-LOOP
+; CHECK-TWO-NOOP-LOOP: Starting pass manager
+; CHECK-TWO-NOOP-LOOP: Running pass: ModuleToFunctionPassAdaptor
+; CHECK-TWO-NOOP-LOOP: Starting pass manager
+; CHECK-TWO-NOOP-LOOP: Running pass: FunctionToLoopPassAdaptor
+; CHECK-TWO-NOOP-LOOP: Starting pass manager
+; CHECK-TWO-NOOP-LOOP: Running pass: NoOpLoopPass
+; CHECK-TWO-NOOP-LOOP: Running pass: NoOpLoopPass
+; CHECK-TWO-NOOP-LOOP: Finished pass manager
+; CHECK-TWO-NOOP-LOOP: Finished pass manager
+; CHECK-TWO-NOOP-LOOP: Finished pass manager
+
+; RUN: opt -disable-output -debug-pass-manager \
+; RUN:     -passes='module(function(loop(no-op-loop)))' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP
+; RUN: opt -disable-output -debug-pass-manager \
+; RUN:     -passes='function(loop(no-op-loop))' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP
+; RUN: opt -disable-output -debug-pass-manager \
+; RUN:     -passes='loop(no-op-loop)' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP
+; RUN: opt -disable-output -debug-pass-manager \
+; RUN:     -passes='no-op-loop' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP
+; CHECK-NESTED-FP-LP: Starting pass manager
+; CHECK-NESTED-FP-LP: Running pass: ModuleToFunctionPassAdaptor
+; CHECK-NESTED-FP-LP: Starting pass manager
+; CHECK-NESTED-FP-LP: Running pass: FunctionToLoopPassAdaptor
+; CHECK-NESTED-FP-LP: Starting pass manager
+; CHECK-NESTED-FP-LP: Running pass: NoOpLoopPass
+; CHECK-NESTED-FP-LP: Finished pass manager
+; CHECK-NESTED-FP-LP: Finished pass manager
+; CHECK-NESTED-FP-LP: Finished pass manager
+
+
 define void @f() {
- ret void
+entry:
+ br label %loop
+loop:
+ br label %loop
 }

tools/opt/NewPMDriver.cpp

 #include "NewPMDriver.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/LoopPassManager.h"
 #include "llvm/Bitcode/BitcodeWriterPass.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"

                            bool ShouldPreserveBitcodeUseListOrder) {
   PassBuilder PB(TM);
 
+  LoopAnalysisManager LAM(DebugPM);
   FunctionAnalysisManager FAM(DebugPM);
   CGSCCAnalysisManager CGAM(DebugPM);
   ModuleAnalysisManager MAM(DebugPM);

   PB.registerModuleAnalyses(MAM);
   PB.registerCGSCCAnalyses(CGAM);
   PB.registerFunctionAnalyses(FAM);
+  PB.registerLoopAnalyses(LAM);
 
   // Cross register the analysis managers through their proxies.
   MAM.registerPass(FunctionAnalysisManagerModuleProxy(FAM));

   CGAM.registerPass(ModuleAnalysisManagerCGSCCProxy(MAM));
   FAM.registerPass(CGSCCAnalysisManagerFunctionProxy(CGAM));
   FAM.registerPass(ModuleAnalysisManagerFunctionProxy(MAM));
+  FAM.registerPass(LoopAnalysisManagerFunctionProxy(LAM));
+  LAM.registerPass(FunctionAnalysisManagerLoopProxy(FAM));
 
   ModulePassManager MPM(DebugPM);
   if (VK > VK_NoVerifier)

unittests/Analysis/CMakeLists.txt

   CallGraphTest.cpp
   CFGTest.cpp
   LazyCallGraphTest.cpp
+  LoopPassManagerTest.cpp
   ScalarEvolutionTest.cpp
   MixedTBAATest.cpp
   ValueTrackingTest.cpp

unittests/Analysis/LoopPassManagerTest.cpp

+//===- llvm/unittest/Analysis/LoopPassManagerTest.cpp - LPM tests ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/Analysis/LoopPassManager.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/SourceMgr.h"
+
+using namespace llvm;
+
+namespace {
+
+class TestLoopAnalysis {
+  /// \brief Private static data to provide unique ID.
+  static char PassID;
+
+  int &Runs;
+
+public:
+  struct Result {
+    Result(int Count) : BlockCount(Count) {}
+    int BlockCount;
+  };
+
+  /// \brief Returns an opaque, unique ID for this pass type.
+  static void *ID() { return (void *)&PassID; }
+
+  /// \brief Returns the name of the analysis.
+  static StringRef name() { return "TestLoopAnalysis"; }
+
+  TestLoopAnalysis(int &Runs) : Runs(Runs) {}
+
+  /// \brief Run the analysis pass over the loop and return a result.
+  Result run(Loop &L, AnalysisManager<Loop> *AM) {
+    ++Runs;
+    int Count = 0;
+
+    for (auto I = L.block_begin(), E = L.block_end(); I != E; ++I)
+      ++Count;
+    return Result(Count);
+  }
+};
+
+char TestLoopAnalysis::PassID;
+
+class TestLoopPass {
+  std::vector<StringRef> &VisitedLoops;
+  int &AnalyzedBlockCount;
+  bool OnlyUseCachedResults;
+
+public:
+  TestLoopPass(std::vector<StringRef> &VisitedLoops, int &AnalyzedBlockCount,
+               bool OnlyUseCachedResults = false)
+      : VisitedLoops(VisitedLoops), AnalyzedBlockCount(AnalyzedBlockCount),
+        OnlyUseCachedResults(OnlyUseCachedResults) {}
+
+  PreservedAnalyses run(Loop &L, AnalysisManager<Loop> *AM) {
+    VisitedLoops.push_back(L.getName());
+
+    if (OnlyUseCachedResults) {
+      // Hack to force the use of the cached interface.
+      if (auto *AR = AM->getCachedResult<TestLoopAnalysis>(L))
+        AnalyzedBlockCount += AR->BlockCount;
+    } else {
+      // Typical path just runs the analysis as needed.
+      auto &AR = AM->getResult<TestLoopAnalysis>(L);
+      AnalyzedBlockCount += AR.BlockCount;
+    }
+
+    return PreservedAnalyses::all();
+  }
+
+  static StringRef name() { return "TestLoopPass"; }
+};
+
+// A test loop pass that invalidates the analysis for loops with the given name.
+class TestLoopInvalidatingPass {
+  StringRef Name;
+
+public:
+  TestLoopInvalidatingPass(StringRef LoopName) : Name(LoopName) {}
+
+  PreservedAnalyses run(Loop &L, AnalysisManager<Loop> *AM) {
+    return L.getName() == Name ? PreservedAnalyses::none()
+                               : PreservedAnalyses::all();
+  }
+
+  static StringRef name() { return "TestLoopInvalidatingPass"; }
+};
+
+
+// A test loop pass that deletes any loops with the given name.
+class TestLoopDeletingPass {
+  StringRef Name;
+
+public:
+  TestLoopDeletingPass(StringRef LoopName) : Name(LoopName) {}
+
+  PreservedAnalyses run(Loop &L, AnalysisManager<Loop> *AM) {
+    if (L.getName() != Name)
+      return PreservedAnalyses::all();
+
+    auto &FAM = AM->getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
+
+    Function *F = L.getHeader()->getParent();
+    auto *LI = FAM.getCachedResult<LoopAnalysis>(*F);
+
+    LI->markAsRemoved(&L);
+
+    PreservedAnalyses PA;
+    PA.preserve<DominatorTreeAnalysis>();
+    PA.preserve<LoopAnalysis>();
+    return PA;
+  }
+
+  static StringRef name() { return "TestLoopDeletingPass"; }
+};
+
+
+std::unique_ptr<Module> parseIR(const char *IR) {
+  LLVMContext &C = getGlobalContext();
+  SMDiagnostic Err;
+  return parseAssemblyString(IR, Err, C);
+}
+
+class LoopPassManagerTest : public ::testing::Test {
+protected:
+  std::unique_ptr<Module> M;
+
+public:
+  LoopPassManagerTest()
+      : M(parseIR("define void @f() {\n"
+                  "entry:\n"
+                  "  br label %loop.0\n"
+                  "loop.0:\n"
+                  "  br i1 undef, label %loop.0.0, label %end\n"
+                  "loop.0.0:\n"
+                  "  br i1 undef, label %loop.0.0, label %loop.0.1\n"
+                  "loop.0.1:\n"
+                  "  br i1 undef, label %loop.0.1, label %loop.0\n"
+                  "end:\n"
+                  "  ret void\n"
+                  "}\n"
+                  "\n"
+                  "define void @g() {\n"
+                  "entry:\n"
+                  "  br label %loop.g.0\n"
+                  "loop.g.0:\n"
+                  "  br i1 undef, label %loop.g.0, label %end\n"
+                  "end:\n"
+                  "  ret void\n"
+                  "}\n")) {}
+};
+
+#define EXPECT_N_ELEMENTS_EQ(N, EXPECTED, ACTUAL)                              \
+  do {                                                                         \
+    EXPECT_EQ(N##UL, ACTUAL.size());                                           \
+    for (int I = 0; I < N; ++I)                                                \
+      EXPECT_TRUE(EXPECTED[I] == ACTUAL[I]) << "Element " << I << " is "       \
+                                            << ACTUAL[I] << ". Expected "      \
+                                            << EXPECTED[I] << ".";             \
+  } while (0)
+
+TEST_F(LoopPassManagerTest, Basic) {
+  LoopAnalysisManager LAM(true);
+  int LoopAnalysisRuns = 0;
+  LAM.registerPass(TestLoopAnalysis(LoopAnalysisRuns));
+
+  FunctionAnalysisManager FAM(true);
+  FAM.registerPass(DominatorTreeAnalysis()); // Needed by LoopAnalysis
+  FAM.registerPass(LoopAnalysis());
+  FAM.registerPass(LoopAnalysisManagerFunctionProxy(LAM));
+  LAM.registerPass(FunctionAnalysisManagerLoopProxy(FAM));
+
+  ModuleAnalysisManager MAM(true);
+  MAM.registerPass(FunctionAnalysisManagerModuleProxy(FAM));
+  FAM.registerPass(ModuleAnalysisManagerFunctionProxy(MAM));
+
+  ModulePassManager MPM(true);
+  FunctionPassManager FPM(true);
+
+  // Visit all of the loops.
+  std::vector<StringRef> VisitedLoops1;
+  int AnalyzedBlockCount1 = 0;
+  {
+    LoopPassManager LPM;
+    LPM.addPass(TestLoopPass(VisitedLoops1, AnalyzedBlockCount1));
+
+    FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
+  }
+
+  // Only use cached analyses.
+  std::vector<StringRef> VisitedLoops2;
+  int AnalyzedBlockCount2 = 0;
+  {
+    LoopPassManager LPM;
+    LPM.addPass(TestLoopInvalidatingPass("loop.g.0"));
+    LPM.addPass(TestLoopPass(VisitedLoops2, AnalyzedBlockCount2,
+                             /*OnlyUseCachedResults=*/true));
+
+    FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
+  }
+
+  // Remove a Loop partway through our traversal.
+  std::vector<StringRef> VisitedLoops3;
+  int AnalyzedBlockCount3 = 0;
+  std::vector<StringRef> VisitedLoops4;
+  int AnalyzedBlockCount4 = 0;
+  {
+    LoopPassManager LPM;
+    LPM.addPass(TestLoopPass(VisitedLoops3, AnalyzedBlockCount3));
+    LPM.addPass(TestLoopDeletingPass("loop.0.0"));
+    LPM.addPass(TestLoopPass(VisitedLoops4, AnalyzedBlockCount4));
+
+    FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
+  }
+
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  MPM.run(*M, &MAM);
+
+  StringRef ExpectedLoops[] = {"loop.0.0", "loop.0.1", "loop.0", "loop.g.0"};
+
+  // Validate the counters and order of loops visited.
+  // loop.0 has 3 blocks whereas loop.0.0, loop.0.1, and loop.g.0 each have 1.
+  EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops1);
+  EXPECT_EQ(6, AnalyzedBlockCount1);
+
+  EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops2);
+  // The block from loop.g.0 won't be counted, since it wasn't cached.
+  EXPECT_EQ(5, AnalyzedBlockCount2);
+
+  // We recalculate the analysis for loop.g.0, so we visit everything again.
+  EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops3);
+  EXPECT_EQ(6, AnalyzedBlockCount3);
+  // Now loop.0.0 has been removed, so it won't be visited at all.
+  StringRef ExpectedLoops3[] = {"loop.0.1", "loop.0", "loop.g.0"};
+  EXPECT_N_ELEMENTS_EQ(3, ExpectedLoops3, VisitedLoops4);
+  EXPECT_EQ(5, AnalyzedBlockCount4);
+
+  // The first LPM runs the loop analysis for all four loops, the second uses
+  // cached results for everything, and the last uses cached results for all but
+  // loop.g.0.
+  EXPECT_EQ(5, LoopAnalysisRuns);
+}
+}