[polly] Add accelerator code generation pass skeleton

[grosser]

Summary

Add a new pass to serve as basis for automatic accelerator mapping in Polly.
The pass structure and the analyses preserved are copied from
CodeGeneration.cpp, as we will rely on IslNodeBuilder and IslExprBuilder for
LLVM-IR code generation.

Polly's accelerator code generation is enabled with -polly-target=gpu.

I would like to use this commit as opportunity to thank Yabin Hu for his work in
the context of two Google summer of code projects during which he implemented
initial prototypes of the Polly accelerator code generation -- in parts this
code is already available in todays Polly (e.g., tools/GPURuntime). More will
come as part of the upcoming Polly ACC changes.

[Meinersbur]

Title: "sceleton" -> "skeleton" and missing "[Polly]".

PPCGCodeGenerationPass sounds like it would invoke PPCG. I'd remove PPCG from the name, keeping only ACC.

Any chance to make PPCGCodeGenerationPass an alternative to the optimizer pass, or even merge it, such that the CodeGeneration would see what it has been optimized and generate the relevant code, just like OpenMP code generation. This would avoid copy&paste code duplication.

[grosser]

In D22036#475020, @Meinersbur wrote:

Title: "sceleton" -> "skeleton" and missing "[Polly]".

Changed.

PPCGCodeGenerationPass sounds like it would invoke PPCG. I'd remove PPCG from the name, keeping only ACC.

It will, internally. If you prefer, I can still rename this pass to AcceleratorCodeGenerationPass.

Any chance to make PPCGCodeGenerationPass an alternative to the optimizer pass, or even merge it, such that the CodeGeneration would see what it has been optimized and generate the relevant code, just like OpenMP code generation. This would avoid copy&paste code duplication.

As we use PPCG it is difficult to split out the dependence analysis and scheduling changes, as both are inter-tangled and especially the GPU specific scheduling that is necessary is very different to the CPU specific schedule optimizations we perform today in Polly.

My current proposal would be to first integrate accelerator code generation as an independent transformation and -- after it has proven to work reliably -- start with integrating CPU and GPU mappings. I did some early experiments on this and it seems performing such an integration on the schedule tree level is feasible. However, it will be a lot easier to discuss when we have the relevant code working next to each other in the same repository.

Regarding code duplication, I expect little code duplication. Most of the code generation is in IslNodeGenerator / IslExprGenerator / ...
and we will just call these classes when the need arises. There will be two scheduler implementations Polly's CPU focused scheduler as well as PPCG's GPU focused scheduling strategies. As said earlier, I would prefer to wait with merging them until we have a stable code base we can use for experiments and testing.

Best,
Tobias

[Meinersbur]

In D22036#475026, @grosser wrote:

In D22036#475020, @Meinersbur wrote:

PPCGCodeGenerationPass sounds like it would invoke PPCG. I'd remove PPCG from the name, keeping only ACC.

It will, internally. If you prefer, I can still rename this pass to AcceleratorCodeGenerationPass.

I didn't even know that PPCG has an interface for this. I'll wait further comments until I see the larger code base. Rename at your own discretion.

lib/Support/RegisterPasses.cpp

90 ↗

(On Diff #62829)

"Enable" sounds like this would add accelerator code generation to the other optimizations, but effectively replaces them. Wouldn't an equivalent to -polly-vectorizer/-polly-code-generator be more appropriate?

[grosser]

In D22036#475040, @Meinersbur wrote:

In D22036#475026, @grosser wrote:

In D22036#475020, @Meinersbur wrote:

PPCGCodeGenerationPass sounds like it would invoke PPCG. I'd remove PPCG from the name, keeping only ACC.

It will, internally. If you prefer, I can still rename this pass to AcceleratorCodeGenerationPass.

I didn't even know that PPCG has an interface for this. I'll wait further comments until I see the larger code base. Rename at your own discretion.

PPCG does not, but the changes to use it as a library are very limited. I plan to first apply these changes in the Polly repository and -- after we gained some experience -- upstream them to the official ppcg.

OK. Then I will probably leave PPCG in the name for now.

lib/Support/RegisterPasses.cpp

90 ↗

(On Diff #62829)

I can use:

-polly-code-generator=cpu
-polly-code-generator=gpu
-polly-code-generator=none

if this is preferable.

The existing -polly-code-generator=isl does not really have a useful meaning since we dropped support for CLooG.

[grosser]

Use -polly-code-generator=gpu to activate GPU code generation

[grosser]

Second alternative: use -polly-target=gpu

[Meinersbur]

-polly-target=gpu is a good idea!

polly/trunk/include/polly/LinkAllPasses.h

 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 llvm::Pass *createPollyCanonicalizePass();
 llvm::Pass *createScopDetectionPass();
 llvm::Pass *createScopInfoRegionPassPass();
 llvm::Pass *createScopInfoWrapperPassPass();
 llvm::Pass *createIslAstInfoPass();
 llvm::Pass *createCodeGenerationPass();
+llvm::Pass *createPPCGCodeGenerationPass();
 llvm::Pass *createIslScheduleOptimizerPass();
 
 extern char &CodePreparationID;
 } // namespace polly
 
 namespace {
 struct PollyForcePassLinking {
   PollyForcePassLinking() {
PollyForcePassLinking() {
     polly::createDOTViewerPass();
     polly::createJSONExporterPass();
     polly::createJSONImporterPass();
     polly::createScopDetectionPass();
     polly::createScopInfoRegionPassPass();
     polly::createPollyCanonicalizePass();
     polly::createIslAstInfoPass();
     polly::createCodeGenerationPass();
+    polly::createPPCGCodeGenerationPass();
     polly::createIslScheduleOptimizerPass();
   }
 } PollyForcePassLinking; // Force link by creating a global definition.
 } // namespace
 
 namespace llvm {
 class PassRegistry;
 void initializeCodePreparationPass(llvm::PassRegistry &);
 void initializeDeadCodeElimPass(llvm::PassRegistry &);
 void initializeJSONExporterPass(llvm::PassRegistry &);
 void initializeJSONImporterPass(llvm::PassRegistry &);
 void initializeIslAstInfoPass(llvm::PassRegistry &);
 void initializeCodeGenerationPass(llvm::PassRegistry &);
+void initializePPCGCodeGenerationPass(llvm::PassRegistry &);
 void initializeIslScheduleOptimizerPass(llvm::PassRegistry &);
 void initializePollyCanonicalizePass(llvm::PassRegistry &);
 } // namespace llvm
 
 #endif

polly/trunk/lib/CMakeLists.txt

 set(LLVM_NO_RTTI 1)
 
 set(POLLY_JSON_FILES
     JSON/json_reader.cpp
     JSON/json_value.cpp
     JSON/json_writer.cpp
 )
 
 set(ISL_CODEGEN_FILES
     CodeGen/IslAst.cpp
     CodeGen/IslExprBuilder.cpp
     CodeGen/IslNodeBuilder.cpp
     CodeGen/CodeGeneration.cpp)
 
 if (GPU_CODEGEN)
-  set (GPGPU_CODEGEN_FILES)
+  set (GPGPU_CODEGEN_FILES
+       CodeGen/PPCGCodeGeneration.cpp
+       )
 endif (GPU_CODEGEN)
 
 # Compile ISL into a separate library.
 add_subdirectory(External)
 
 set(POLLY_HEADER_FILES)
 if (MSVC_IDE OR XCODE)
   file(GLOB_RECURSE POLLY_HEADER_FILES "${POLLY_SOURCE_DIR}/include/polly/*.h")

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

+//===------ PPCGCodeGeneration.cpp - Polly Accelerator Code Generation. ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Take a scop created by ScopInfo and map it to GPU code using the ppcg
+// GPU mapping strategy.
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/CodeGen/IslNodeBuilder.h"
+#include "polly/DependenceInfo.h"
+#include "polly/LinkAllPasses.h"
+#include "polly/ScopInfo.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
+
+#include "llvm/Support/Debug.h"
+
+using namespace polly;
+using namespace llvm;
+
+#define DEBUG_TYPE "polly-codegen-ppcg"
+
+namespace {
+class PPCGCodeGeneration : public ScopPass {
+public:
+  static char ID;
+
+  PPCGCodeGeneration() : ScopPass(ID) {}
+
+  bool runOnScop(Scop &S) override { return true; }
+
+  void printScop(raw_ostream &, Scop &) const override {}
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<RegionInfoPass>();
+    AU.addRequired<ScalarEvolutionWrapperPass>();
+    AU.addRequired<ScopDetection>();
+    AU.addRequired<ScopInfoRegionPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+
+    AU.addPreserved<AAResultsWrapperPass>();
+    AU.addPreserved<BasicAAWrapperPass>();
+    AU.addPreserved<LoopInfoWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addPreserved<PostDominatorTreeWrapperPass>();
+    AU.addPreserved<ScopDetection>();
+    AU.addPreserved<ScalarEvolutionWrapperPass>();
+    AU.addPreserved<SCEVAAWrapperPass>();
+
+    // FIXME: We do not yet add regions for the newly generated code to the
+    //        region tree.
+    AU.addPreserved<RegionInfoPass>();
+    AU.addPreserved<ScopInfoRegionPass>();
+  }
+};
+}
+
+char PPCGCodeGeneration::ID = 1;
+
+Pass *polly::createPPCGCodeGenerationPass() { return new PPCGCodeGeneration(); }
+
+INITIALIZE_PASS_BEGIN(PPCGCodeGeneration, "polly-codegen-ppcg",
+                      "Polly - Apply PPCG translation to SCOP", false, false)
+INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(ScopDetection);
+INITIALIZE_PASS_END(PPCGCodeGeneration, "polly-codegen-ppcg",
+                    "Polly - Apply PPCG translation to SCOP", false, false)

polly/trunk/lib/Support/RegisterPasses.cpp

 enum CodeGenChoice { CODEGEN_ISL, CODEGEN_NONE };
 static cl::opt<CodeGenChoice> CodeGenerator(
     "polly-code-generator", cl::desc("Select the code generator"),
     cl::values(clEnumValN(CODEGEN_ISL, "isl", "isl code generator"),
                clEnumValN(CODEGEN_NONE, "none", "no code generation"),
                clEnumValEnd),
     cl::Hidden, cl::init(CODEGEN_ISL), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+enum TargetChoice { TARGET_CPU, TARGET_GPU };
+static cl::opt<TargetChoice>
+    Target("polly-target", cl::desc("The hardware to target"),
+           cl::values(clEnumValN(TARGET_CPU, "cpu", "generate CPU code"),
+                      clEnumValN(TARGET_GPU, "gpu", "generate GPU code"),
+                      clEnumValEnd),
+           cl::init(TARGET_CPU), cl::ZeroOrMore, cl::cat(PollyCategory));
+
 VectorizerChoice polly::PollyVectorizerChoice;
 static cl::opt<polly::VectorizerChoice, true> Vectorizer(
     "polly-vectorizer", cl::desc("Select the vectorization strategy"),
     cl::values(
         clEnumValN(polly::VECTORIZER_NONE, "none", "No Vectorization"),
         clEnumValN(polly::VECTORIZER_POLLY, "polly",
                    "Polly internal vectorizer"),
         clEnumValN(polly::VECTORIZER_STRIPMINE, "stripmine",

 static cl::opt<bool>
     CFGPrinter("polly-view-cfg",
                cl::desc("Show the Polly CFG right after code generation"),
                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 namespace polly {
 void initializePollyPasses(PassRegistry &Registry) {
   initializeCodeGenerationPass(Registry);
+  initializePPCGCodeGenerationPass(Registry);
   initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
   initializeDependenceInfoPass(Registry);
   initializeDependenceInfoWrapperPassPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
void registerPollyPasses(llvm::legacy::PassManagerBase &PM) {
   PM.add(polly::createScopInfoRegionPassPass());
 
   if (ImportJScop)
     PM.add(polly::createJSONImporterPass());
 
   if (DeadCodeElim)
     PM.add(polly::createDeadCodeElimPass());
 
+  if (Target == TARGET_GPU) {
+    // GPU generation provides its own scheduling optimization strategy.
+  } else {
     switch (Optimizer) {
     case OPTIMIZER_NONE:
       break; /* Do nothing */
 
     case OPTIMIZER_ISL:
       PM.add(polly::createIslScheduleOptimizerPass());
       break;
     }
+  }
 
   if (ExportJScop)
     PM.add(polly::createJSONExporterPass());
 
+  if (Target == TARGET_GPU) {
+    PM.add(polly::createPPCGCodeGenerationPass());
+  } else {
     switch (CodeGenerator) {
     case CODEGEN_ISL:
       PM.add(polly::createCodeGenerationPass());
       break;
     case CODEGEN_NONE:
       break;
     }
+  }
 
   // FIXME: This dummy ModulePass keeps some programs from miscompiling,
   // probably some not correctly preserved analyses. It acts as a barrier to
   // force all analysis results to be recomputed.
   PM.add(createBarrierNoopPass());
 
   if (CFGPrinter)
     PM.add(llvm::createCFGPrinterPass());