PM: Implement a basic loop pass manager

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

This version doesn't support modifying the loop nest at all. It will
be far easier to discuss and evaluate the approaches to that with this
in place so that the boilerplate is out of the way.

llvm-svn: 261831

4 files changed, 184 insertions, 2 deletions

diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index 38234207d9a..72669289b08 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -42,6 +42,7 @@ add_llvm_library(LLVMAnalysis
   LoopUnrollAnalyzer.cpp
   LoopInfo.cpp
   LoopPass.cpp
+  LoopPassManager.cpp
   MemDepPrinter.cpp
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
diff --git a/llvm/lib/Analysis/LoopPassManager.cpp b/llvm/lib/Analysis/LoopPassManager.cpp
new file mode 100644
index 00000000000..b1d1140d11b
--- /dev/null
+++ b/llvm/lib/Analysis/LoopPassManager.cpp
@@ -0,0 +1,45 @@
+//===- 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;
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index bf646104230..f043c92fd4f 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -107,6 +107,24 @@ private:
 
 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) {
@@ -127,6 +145,12 @@ void PassBuilder::registerFunctionAnalyses(FunctionAnalysisManager &FAM) {
 #include "PassRegistry.def"
 }
 
+void PassBuilder::registerLoopAnalyses(LoopAnalysisManager &LAM) {
+#define LOOP_ANALYSIS(NAME, CREATE_PASS) \
+  LAM.registerPass([&] { return CREATE_PASS; });
+#include "PassRegistry.def"
+}
+
 #ifndef NDEBUG
 static bool isModulePassName(StringRef Name) {
 #define MODULE_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
@@ -159,6 +183,16 @@ static bool isFunctionPassName(StringRef Name) {
   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) {                                                          \
@@ -220,6 +254,27 @@ bool PassBuilder::parseFunctionPassName(FunctionPassManager &FPM,
   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::parseAAPassName(AAManager &AA, StringRef Name) {
 #define FUNCTION_ALIAS_ANALYSIS(NAME, CREATE_PASS)                             \
   if (Name == NAME) {                                                          \
@@ -231,6 +286,45 @@ bool PassBuilder::parseAAPassName(AAManager &AA, StringRef Name) {
   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,
@@ -251,6 +345,20 @@ bool PassBuilder::parseFunctionPassPipeline(FunctionPassManager &FPM,
 
       // 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(",)");
@@ -411,7 +519,7 @@ bool PassBuilder::parsePassPipeline(ModulePassManager &MPM,
 
   // 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) ||
@@ -423,7 +531,7 @@ bool PassBuilder::parsePassPipeline(ModulePassManager &MPM,
 
   // 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) ||
@@ -433,6 +541,20 @@ bool PassBuilder::parsePassPipeline(ModulePassManager &MPM,
     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;
 }
 
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index 9feba877ed3..1721fa1bc23 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -96,3 +96,17 @@ FUNCTION_PASS("sroa", SROA())
 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