[Polly][PM][WIP] Polly pass registration

Summary:
This patch is a first attempt at registering Polly passes with the LLVM tools. Tool plugins are still unsupported, but this registration is usable from the tools if Polly is linked into them (albeit requiring minimal patches to those tools). Registration requires a small amount of machinery (the owning analysis proxies), necessary for injecting ScopAnalysisManager objects into the calling tools.

This patch is marked WIP because the registration is incomplete. Parsing manual pipelines is fully supported, but default pass injection into the O3 pipeline is lacking, mostly because there is opportunity for some redesign here, I believe. The first point of order would be insertion points. I think it makes sense to run before the vectorizers. Running Polly Early, however, is weird. Mostly because it actually is the default (which to me is unexpected), and because Polly runs it's own O1 pipeline. Why not instead insert it at an appropriate place somewhere after simplification happend? Running after the loop optimizers seems intuitive, but it also seems wasteful, since multiple consecutive loops might well be a single scop, and we don't need to run for all of them.

My second request for comments would be regarding all those smallish helper passes we have,  like PollyViewer, PollyPrinter, PollyImportJScop. Right now these are controlled by command line options, deciding whether they should be part of the Polly pipeline. What is your opinion on treating them like real passes, and have the user write an appropriate pipeline if they want to use any of them?

Reviewers: grosser, Meinersbur, bollu

Reviewed By: grosser

Subscribers: llvm-commits, pollydev

Tags: #polly

Differential Revision: https://reviews.llvm.org/D35458

llvm-svn: 309826

8 files changed, 343 insertions, 2 deletions

diff --git a/polly/include/polly/CodePreparation.h b/polly/include/polly/CodePreparation.h
new file mode 100644
index 00000000000..87ad17b00d9
--- /dev/null
+++ b/polly/include/polly/CodePreparation.h
@@ -0,0 +1,13 @@
+#ifndef POLLY_CODEPREPARATION_H
+#define POLLY_CODEPREPARATION_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace polly {
+struct CodePreparationPass : public llvm::PassInfoMixin<CodePreparationPass> {
+  llvm::PreservedAnalyses run(llvm::Function &F,
+                              llvm::FunctionAnalysisManager &FAM);
+};
+}
+
+#endif /* POLLY_CODEPREPARATION_H */
diff --git a/polly/include/polly/ScopPass.h b/polly/include/polly/ScopPass.h
index ca89989533c..d7ea4712712 100644
--- a/polly/include/polly/ScopPass.h
+++ b/polly/include/polly/ScopPass.h
@@ -77,6 +77,21 @@ private:
   ScopInfo *SI;
 };
 
+// A partial specialization of the require analysis template pass to handle
+// extra parameters
+template <typename AnalysisT>
+struct RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
+                           ScopStandardAnalysisResults &, SPMUpdater &>
+    : PassInfoMixin<
+          RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
+                              ScopStandardAnalysisResults &, SPMUpdater &>> {
+  PreservedAnalyses run(Scop &L, ScopAnalysisManager &AM,
+                        ScopStandardAnalysisResults &AR, SPMUpdater &) {
+    (void)AM.template getResult<AnalysisT>(L, AR);
+    return PreservedAnalyses::all();
+  }
+};
+
 template <>
 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
 InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
@@ -95,6 +110,40 @@ extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
 } // namespace llvm
 
 namespace polly {
+
+template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
+class OwningInnerAnalysisManagerProxy
+    : public InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT> {
+public:
+  OwningInnerAnalysisManagerProxy()
+      : InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>(InnerAM) {}
+  using Result = typename InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT,
+                                                    ExtraArgTs...>::Result;
+  Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
+             ExtraArgTs...) {
+    return Result(InnerAM);
+  }
+
+  AnalysisManagerT &getManager() { return InnerAM; }
+
+private:
+  friend AnalysisInfoMixin<
+      OwningInnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>>;
+
+  static AnalysisKey Key;
+
+  AnalysisManagerT InnerAM;
+};
+
+template <>
+OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
+OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
+    Function &F, FunctionAnalysisManager &FAM);
+extern template class OwningInnerAnalysisManagerProxy<ScopAnalysisManager,
+                                                      Function>;
+
+using OwningScopAnalysisManagerFunctionProxy =
+    OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
 using ScopPassManager =
     PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
                 SPMUpdater &>;
diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h
index 19aecc59f11..ccbdbf6c33d 100644
--- a/polly/include/polly/Support/ScopHelper.h
+++ b/polly/include/polly/Support/ScopHelper.h
@@ -315,6 +315,16 @@ void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT,
 ///
 void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P);
 
+/// Split the entry block of a function to store the newly inserted
+///        allocations outside of all Scops.
+///
+/// @param DT DominatorTree to be updated.
+/// @param LI LoopInfo to be updated.
+/// @param RI RegionInfo to be updated.
+void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock,
+                              llvm::DominatorTree *DT, llvm::LoopInfo *LI,
+                              llvm::RegionInfo *RI);
+
 /// Wrapper for SCEVExpander extended to all Polly features.
 ///
 /// This wrapper will internally call the SCEVExpander but also makes sure that
diff --git a/polly/lib/Analysis/ScopPass.cpp b/polly/lib/Analysis/ScopPass.cpp
index c845bf2f482..eb03423352e 100644
--- a/polly/lib/Analysis/ScopPass.cpp
+++ b/polly/lib/Analysis/ScopPass.cpp
@@ -41,6 +41,8 @@ void ScopPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
 }
 
+template class OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
+
 namespace llvm {
 
 template class PassManager<Scop, ScopAnalysisManager,
@@ -130,6 +132,12 @@ bool ScopAnalysisManagerFunctionProxy::Result::invalidate(
 }
 
 template <>
+OwningScopAnalysisManagerFunctionProxy::Result
+OwningScopAnalysisManagerFunctionProxy::run(Function &F,
+                                            FunctionAnalysisManager &FAM) {
+  return Result(InnerAM, FAM.getResult<ScopInfoAnalysis>(F));
+}
+template <>
 ScopAnalysisManagerFunctionProxy::Result
 ScopAnalysisManagerFunctionProxy::run(Function &F,
                                       FunctionAnalysisManager &FAM) {
diff --git a/polly/lib/Support/PollyPasses.def b/polly/lib/Support/PollyPasses.def
new file mode 100644
index 00000000000..288ec9d6547
--- /dev/null
+++ b/polly/lib/Support/PollyPasses.def
@@ -0,0 +1,29 @@
+#ifndef FUNCTION_ANALYSIS
+#define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
+#endif
+FUNCTION_ANALYSIS("polly-detect", ScopAnalysis())
+FUNCTION_ANALYSIS("polly-function-scops", ScopInfoAnalysis())
+#undef FUNCTION_ANALYSIS
+
+#ifndef FUNCTION_PASS
+#define FUNCTION_PASS(NAME, CREATE_PASS)
+#endif
+FUNCTION_PASS("polly-prepare", CodePreparationPass())
+FUNCTION_PASS("print<polly-detect>", ScopAnalysisPrinterPass(errs()))
+FUNCTION_PASS("print<polly-function-scops>", ScopInfoPrinterPass(errs()))
+#undef FUNCTION_PASS
+
+#ifndef SCOP_ANALYSIS
+#define SCOP_ANALYSIS(NAME, CREATE_PASS)
+#endif
+SCOP_ANALYSIS("polly-ast", IslAstAnalysis())
+SCOP_ANALYSIS("polly-dependences", DependenceAnalysis())
+#undef SCOP_ANALYSIS
+
+#ifndef SCOP_PASS
+#define SCOP_PASS(NAME, CREATE_PASS)
+#endif
+SCOP_PASS("print<polly-ast>", IslAstPrinterPass(outs()))
+SCOP_PASS("print<polly-dependences>", DependenceInfoPrinterPass(outs()))
+SCOP_PASS("polly-codegen", CodeGenerationPass())
+#undef SCOP_PASS
diff --git a/polly/lib/Support/RegisterPasses.cpp b/polly/lib/Support/RegisterPasses.cpp
index 66199de797e..042b5cd5fdc 100644
--- a/polly/lib/Support/RegisterPasses.cpp
+++ b/polly/lib/Support/RegisterPasses.cpp
@@ -23,7 +23,9 @@
 #include "polly/Canonicalization.h"
 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/CodeGen/CodegenCleanup.h"
+#include "polly/CodeGen/IslAst.h"
 #include "polly/CodeGen/PPCGCodeGeneration.h"
+#include "polly/CodePreparation.h"
 #include "polly/DeLICM.h"
 #include "polly/DependenceInfo.h"
 #include "polly/FlattenSchedule.h"
@@ -37,6 +39,8 @@
 #include "polly/Support/DumpModulePass.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Verifier.h"
+#include "llvm/Passes/PassBuilder.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
@@ -430,6 +434,69 @@ registerPollyScalarOptimizerLatePasses(const llvm::PassManagerBuilder &Builder,
   PM.add(createCodegenCleanupPass());
 }
 
+static void buildDefaultPollyPipeline(FunctionPassManager &PM,
+                                      PassBuilder::OptimizationLevel Level) {
+  if (!polly::shouldEnablePolly())
+    return;
+  PassBuilder PB;
+  ScopPassManager SPM;
+
+  // TODO add utility passes for the various command line options, once they're
+  // ported
+  assert(!DumpBefore && "This option is not implemented");
+  assert(DumpBeforeFile.empty() && "This option is not implemented");
+
+  if (PollyDetectOnly)
+    return;
+
+  assert(!PollyViewer && "This option is not implemented");
+  assert(!PollyOnlyViewer && "This option is not implemented");
+  assert(!PollyPrinter && "This option is not implemented");
+  assert(!PollyOnlyPrinter && "This option is not implemented");
+  assert(!EnablePolyhedralInfo && "This option is not implemented");
+  assert(!EnableDeLICM && "This option is not implemented");
+  assert(!EnableSimplify && "This option is not implemented");
+  assert(!ImportJScop && "This option is not implemented");
+  assert(!DeadCodeElim && "This option is not implemented");
+  assert(!EnablePruneUnprofitable && "This option is not implemented");
+  if (Target == TARGET_CPU || Target == TARGET_HYBRID)
+    switch (Optimizer) {
+    case OPTIMIZER_NONE:
+      break; /* Do nothing */
+    case OPTIMIZER_ISL:
+      assert("ISL optimizer is not implemented");
+      break;
+    }
+
+  assert(!ExportJScop && "This option is not implemented");
+
+  if (Target == TARGET_CPU || Target == TARGET_HYBRID) {
+    switch (CodeGeneration) {
+    case CODEGEN_FULL:
+      SPM.addPass(polly::CodeGenerationPass());
+      break;
+    case CODEGEN_AST:
+    default: // Does it actually make sense to distinguish IslAst codegen?
+      break;
+    }
+  }
+#ifdef GPU_CODEGEN
+  else
+    assert("Hybrid Target with GPU support is not implemented");
+#endif
+
+  PM.addPass(CodePreparationPass());
+  PM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
+  PM.addPass(PB.buildFunctionSimplificationPipeline(
+      Level, PassBuilder::ThinLTOPhase::None)); // Cleanup
+
+  assert(!DumpAfter && "This option is not implemented");
+  assert(DumpAfterFile.empty() && "This option is not implemented");
+
+  if (CFGPrinter)
+    PM.addPass(llvm::CFGPrinterPass());
+}
+
 /// Register Polly to be available as an optimizer
 ///
 ///
@@ -478,4 +545,140 @@ static llvm::RegisterStandardPasses
 static llvm::RegisterStandardPasses RegisterPollyOptimizerScalarLate(
     llvm::PassManagerBuilder::EP_VectorizerStart,
     registerPollyScalarOptimizerLatePasses);
+
+static OwningScopAnalysisManagerFunctionProxy
+createScopAnalyses(FunctionAnalysisManager &FAM) {
+  OwningScopAnalysisManagerFunctionProxy Proxy;
+#define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
+  Proxy.getManager().registerPass([] { return CREATE_PASS; });
+
+#include "PollyPasses.def"
+
+  Proxy.getManager().registerPass(
+      [&FAM] { return FunctionAnalysisManagerScopProxy(FAM); });
+  return Proxy;
+}
+
+static void registerFunctionAnalyses(FunctionAnalysisManager &FAM) {
+#define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
+  FAM.registerPass([] { return CREATE_PASS; });
+
+#include "PollyPasses.def"
+
+  FAM.registerPass([&FAM] { return createScopAnalyses(FAM); });
+}
+
+static bool
+parseFunctionPipeline(StringRef Name, FunctionPassManager &FPM,
+                      ArrayRef<PassBuilder::PipelineElement> Pipeline) {
+  if (parseAnalysisUtilityPasses<OwningScopAnalysisManagerFunctionProxy>(
+          "polly-scop-analyses", Name, FPM))
+    return true;
+
+#define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
+  if (parseAnalysisUtilityPasses<                                              \
+          std::remove_reference<decltype(CREATE_PASS)>::type>(NAME, Name,      \
+                                                              FPM))            \
+    return true;
+
+#define FUNCTION_PASS(NAME, CREATE_PASS)                                       \
+  if (Name == NAME) {                                                          \
+    FPM.addPass(CREATE_PASS);                                                  \
+    return true;                                                               \
+  }
+
+#include "PollyPasses.def"
+  return false;
+}
+
+static bool parseScopPass(StringRef Name, ScopPassManager &SPM) {
+#define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
+  if (parseAnalysisUtilityPasses<                                              \
+          std::remove_reference<decltype(CREATE_PASS)>::type>(NAME, Name,      \
+                                                              SPM))            \
+    return true;
+
+#define SCOP_PASS(NAME, CREATE_PASS)                                           \
+  if (Name == NAME) {                                                          \
+    SPM.addPass(CREATE_PASS);                                                  \
+    return true;                                                               \
+  }
+
+#include "PollyPasses.def"
+
+  return false;
+}
+
+static bool parseScopPipeline(StringRef Name, FunctionPassManager &FPM,
+                              ArrayRef<PassBuilder::PipelineElement> Pipeline) {
+  if (Name != "scop")
+    return false;
+  if (!Pipeline.empty()) {
+    ScopPassManager SPM;
+    for (const auto &E : Pipeline)
+      if (!parseScopPass(E.Name, SPM))
+        return false;
+    FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
+  }
+  return true;
+}
+
+static bool isScopPassName(StringRef Name) {
+#define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
+  if (Name == "require<" NAME ">")                                             \
+    return true;                                                               \
+  if (Name == "invalidate<" NAME ">")                                          \
+    return true;
+
+#define SCOP_PASS(NAME, CREATE_PASS)                                           \
+  if (Name == NAME)                                                            \
+    return true;
+
+#include "PollyPasses.def"
+
+  return false;
+}
+
+static bool
+parseTopLevelPipeline(ModulePassManager &MPM,
+                      ArrayRef<PassBuilder::PipelineElement> Pipeline,
+                      bool VerifyEachPass, bool DebugLogging) {
+  std::vector<PassBuilder::PipelineElement> FullPipeline;
+  StringRef FirstName = Pipeline.front().Name;
+
+  if (!isScopPassName(FirstName))
+    return false;
+
+  FunctionPassManager FPM(DebugLogging);
+  ScopPassManager SPM(DebugLogging);
+
+  for (auto &Element : Pipeline) {
+    auto &Name = Element.Name;
+    auto &InnerPipeline = Element.InnerPipeline;
+    if (!InnerPipeline.empty()) // Scop passes don't have inner pipelines
+      return false;
+    if (!parseScopPass(Name, SPM))
+      return false;
+  }
+
+  FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
+  if (VerifyEachPass)
+    FPM.addPass(VerifierPass());
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  if (VerifyEachPass)
+    MPM.addPass(VerifierPass());
+
+  return true;
+}
+
+void RegisterPollyPasses(PassBuilder &PB) {
+  PB.registerAnalysisRegistrationCallback(registerFunctionAnalyses);
+  PB.registerPipelineParsingCallback(parseFunctionPipeline);
+  PB.registerPipelineParsingCallback(parseScopPipeline);
+  PB.registerParseTopLevelPipelineCallback(parseTopLevelPipeline);
+
+  if (PassPosition == POSITION_BEFORE_VECTORIZER)
+    PB.registerVectorizerStartEPCallback(buildDefaultPollyPipeline);
+  // FIXME else Error?
+}
 } // namespace polly
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index d3e1e9948d4..d2146cf1cd2 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -194,13 +194,19 @@ static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
   return NewBlock;
 }
 
-void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
+void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT,
+                                     LoopInfo *LI, RegionInfo *RI) {
   // Find first non-alloca instruction. Every basic block has a non-alloca
   // instruction, as every well formed basic block has a terminator.
   BasicBlock::iterator I = EntryBlock->begin();
   while (isa<AllocaInst>(I))
     ++I;
 
+  // splitBlock updates DT, LI and RI.
+  splitBlock(EntryBlock, &*I, DT, LI, RI);
+}
+
+void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
@@ -209,7 +215,7 @@ void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
   RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
 
   // splitBlock updates DT, LI and RI.
-  splitBlock(EntryBlock, &*I, DT, LI, RI);
+  polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI);
 }
 
 /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
diff --git a/polly/lib/Transform/CodePreparation.cpp b/polly/lib/Transform/CodePreparation.cpp
index 081244da810..299c14123df 100644
--- a/polly/lib/Transform/CodePreparation.cpp
+++ b/polly/lib/Transform/CodePreparation.cpp
@@ -16,6 +16,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "polly/CodePreparation.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopDetection.h"
 #include "polly/Support/ScopHelper.h"
@@ -57,6 +58,28 @@ public:
 };
 } // namespace
 
+PreservedAnalyses CodePreparationPass::run(Function &F,
+                                           FunctionAnalysisManager &FAM) {
+
+  // Find first non-alloca instruction. Every basic block has a non-alloca
+  // instruction, as every well formed basic block has a terminator.
+  auto &EntryBlock = F.getEntryBlock();
+  BasicBlock::iterator I = EntryBlock.begin();
+  while (isa<AllocaInst>(I))
+    ++I;
+
+  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
+  auto &LI = FAM.getResult<LoopAnalysis>(F);
+
+  // splitBlock updates DT, LI and RI.
+  splitEntryBlockForAlloca(&EntryBlock, &DT, &LI, nullptr);
+
+  PreservedAnalyses PA;
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LoopAnalysis>();
+  return PA;
+}
+
 void CodePreparation::clear() {}
 
 CodePreparation::~CodePreparation() { clear(); }