Introduce a hybrid target to generate code for either the GPU or CPU

[singam-sanjay]

Summary

Introduce a "hybrid" -polly-target option to optimise code for either the GPU or CPU.

When this target is selected, PPCGCodeGeneration will attempt first to optimise a Scop. If the Scop isn't modified, it is then sent to the passes that form the CPU pipeline, i.e. IslScheduleOptimizerPass, IslAstInfoWrapperPass and CodeGeneration.

In case the Scop is modified, it is marked to be skipped by the subsequent CPU optimisation passes.

[singam-sanjay]

I'll soon be adding a test-case. Do you have suggestions for kernels that would not be optimised by PPCGCodeGen but by IslScheduleOptimizer ?

[bollu]

@singam-sanjay: nitpick: polly-update-format changes the format of the file in a couple of places. For next time, could you please update the diff after running ninja/make polly-update-format? I've made a couple of stylistic comments that are upto personal choice :)

include/polly/ScopInfo.h

1624

nit: can this be done in the constructor to maintain uniformity? Perhaps we could change the stuff that's constant to use the initialisation syntax in another patch?

2336

nit: can this be called multiple times on a Scop? If not, can we check for this invariant with:

invariant-only-called-once.cpp

void markAsToBeSkipped() {
    assert(!SkipScop && "scop is marked as to be skipped multiple times.");
    SkipScop = true;
}

lib/CodeGen/CodeGeneration.cpp

271

nit: . at the end of the comment.

lib/CodeGen/IslAst.cpp

628

nit: . at the end of the comment.

lib/CodeGen/PPCGCodeGeneration.cpp

2690

nit: can we continue to use S instead of CurrentScop as is done by S->hasInvariantAccesses()?

We could remove the take-a-reference in another patch.

lib/Support/RegisterPasses.cpp

94

nit: I feel uncomfortable due to the mix of ALL_CAPS with SOME_Caps. This is better done in a separate patch, but can we consider Target_ rather than TARGET_ as the prefix?

[singam-sanjay]

In D34054#777908, @bollu wrote:

@singam-sanjay: nitpick: polly-update-format changes the format of the file in a couple of places. For next time, could you please update the diff after running ninja/make polly-update-format? I've made a couple of stylistic comments that are upto personal choice :)

Thanks for pointing it out !

Do you find any reason that this might not work ?

include/polly/ScopInfo.h

1624

Instead of using the SkipScop, can I set isOptimised to true and skip the Scop in the CPU optimization passes by checking`(S.isOptimized()==true)` ?

lib/CodeGen/PPCGCodeGeneration.cpp

2622

TODO: prevent code-gen when (GPUNodeBuilder::BuildSuccessful==true) && (NodeBuilder.DeepestSequential <= NodeBuilder.DeepestParallel)

2690

TODO : markAsToBeSkipped only when (PPCGGen->tree != NULL) && (GPUNodeBuilder::BuildSuccessful==true) && (NodeBuilder.DeepestSequential <= NodeBuilder.DeepestParallel)
ALONG WITH : "prevent code-gen when (GPUNodeBuilder::BuildSuccessful==true) && (NodeBuilder.DeepestSequential <= NodeBuilder.DeepestParallel)"

I have pointed out in this polly-dev post that code-generating instructions required to launch the kernel, even when the PTX kernel isn't available, will invalidate Analysis information regarding the CurrentScop making it impossible for subsequent CPU opt passes to do anything. So, marking the Scop to be skipped is a safe thing to do, but we would've lost optimization opportunities.

[singam-sanjay]

include/polly/ScopInfo.h

1624

Sure.

2336

I can think of justifications for both cases, calling markAsToBeSkipped once Vs. many times.

Call only once : if a Scop is marked to be skipped by a previous pass, the subsequent passes needn't process the Scop and have to check with isToBeSkipped before marking it themselves.

Call multiple times : A Scop might be marked multiple times within a pass, like GPUNodeBuilder::BuildSuccessful.

What do you think is more consistent ?

lib/CodeGen/PPCGCodeGeneration.cpp

2690

nit: can we continue to use S instead of CurrentScop as is done by S->hasInvariantAccesses()?

Sure. I thought using CurrentScop might be more appropriate because the Scop was passed through CurrentScop and not S and this is communicating information relevant to not just this pass.

We could remove the take-a-reference in another patch.

I didn't understand this.

lib/Support/RegisterPasses.cpp

94

nit: I feel uncomfortable due to the mix of ALL_CAPS with SOME_Caps. This is better done in a separate patch, but can we consider Target_ rather than TARGET_ as the prefix

I felt it was better to keep the "TARGET_" uniform. Using "Target_" could be inconsistent for enums because they're generally ALL_CAPS and camel case is used to declare llvm::cl variables and template types e.g. DumpAfter and TargetChoice rsply.

SOME_Caps is better since "Hybrid" isn't a short-form any word and also conveys its distinction visually from plain "CPU" and "GPU" targets. 😁

I'll change it if you still feel the need.

[singam-sanjay]

1. Punctuation consistency in comments.
2. Align code to LLVM's C/C++ format.
3. Initialized SkipScop at constructor like all other members.
4. Include code for GPU targeting only when GPU_CODEGEN is defined.

[grosser]

Hi Sanjay,

the general direction of this patch looks good. I just have some minor comments!

Best,
Tobias

lib/Support/RegisterPasses.cpp

94

Enums are written UPPERCASE here. See CODEGEN_FULL, CODEGEN_NONE above. Please change.

348

I feel as if we have a some code duplication here. Would it make sense to write it as:

if (GPU || Hybrid)
  PPCG

if (CPU || Hybrid)
  ScheduleOptimizer
   IslAst
  Codegen

?

[singam-sanjay]

1. Rename TARGET_Hybrid to TARGET_HYBRID
2. Reduce code redundancy.

[singam-sanjay]

lib/CodeGen/PPCGCodeGeneration.cpp

2690

@bollu ping.

[singam-sanjay]

lib/Support/RegisterPasses.cpp

94

@grosser ping.

326

F.Y.I.
The JSCOP exported here would either be the original Scop in case of TARGET_GPU and the IslScheduleOptimised Scop in case of TARGET_CPU.

330

F.Y.I.
The previous behaviour is still preserved here for TARGET_CPU, TARGET_GPU and TARGET_HYBRID when the Scop is optimised by IslScheduleOptimizer.

The Schedule exported however seems to remain the same when PPCGCodeGen transforms the Scop when TARGET_HYBRID, with the exception of the boundary of the associated Region being "polly.merge_new_and_old".

[grosser]

Hi Sanjay,

this looks already very good. Just a minor thing.

Best,
Tobias

lib/Support/RegisterPasses.cpp

348

Instead of adding here ppcg again, can you just broaden the condition that calls the first createPPCGCodeGenerationPass

[singam-sanjay]

lib/Support/RegisterPasses.cpp

348

I'm adding PPCGCodeGen here to preserve the order in which passes were sequenced when Target==TARGET_GPU. If you look at the the code on the left, createJSONExporterPass is sequenced to run before createPPCGCodeGenerationPass.

To sequence JSON Exporter after all transformation passes,

1. A Scop's StmtSet must be updated by PPCGCodeGeneration as well, because JSONExporter uses ScopStsmts and not isl_schedule_tree to generate the file.
   • We should also annotate the ScopStmts to differentiate those that run on the GPU from those that run on the CPU.
2. Scop::getNameStr must return the original name of the Scop, and not the one based on its Module's changing boundary basic blocks during IRBuilding. I have addressed this in D34565

If we're able to do this, we can finally export the JSCOP of even the Schedule produced by ppcg.

[singam-sanjay]

Update diff to include changes till https://llvm.org/svn/llvm-project/polly/trunk@306540

[singam-sanjay]

lib/Support/RegisterPasses.cpp

348

@grosser ping

[grosser]

LGTM.

include/polly/ScopInfo.h

private:
   bool HasErrorBlock;
 
   /// Max loop depth.
   unsigned MaxLoopDepth;
 
   /// Number of copy statements.
   unsigned CopyStmtsNum;
 
+  /// Flag to indicate if the Scop is to be skipped.
+  bool SkipScop;
+
   typedef std::list<ScopStmt> StmtSet;
   /// The statements in this Scop.
   StmtSet Stmts;
 
   /// Parameters of this Scop
   ParameterSetTy Parameters;
 
   /// Mapping from parameters to their ids.
public:
   bool hasInvariantAccesses() { return !InvariantEquivClasses.empty(); }
 
   /// Mark the SCoP as optimized by the scheduler.
   void markAsOptimized() { IsOptimized = true; }
 
   /// Check if the SCoP has been optimized by the scheduler.
   bool isOptimized() const { return IsOptimized; }
 
+  /// Mark the SCoP to be skipped by ScopPass passes.
+  void markAsToBeSkipped() { SkipScop = true; }
+
+  /// Check if the SCoP is to be skipped by ScopPass passes.
+  bool isToBeSkipped() const { return SkipScop; }
+
   /// Get the name of the entry and exit blocks of this Scop.
   ///
   /// These along with the function name can uniquely identify a Scop.
   ///
   /// @return std::pair whose first element is the entry name & second element
   ///         is the exit name.
   std::pair<std::string, std::string> getEntryExitStr() const;
 

lib/Analysis/ScopInfo.cpp

static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
   }
 
   return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
            ScopDetection::DetectionContext &DC)
     : SE(&ScalarEvolution), R(R), name(R.getNameStr()), IsOptimized(false),
-      HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false),
-      MaxLoopDepth(0), CopyStmtsNum(0), DC(DC),
+      SkipScop(false), HasSingleExitEdge(R.getExitingBlock()),
+      HasErrorBlock(false), MaxLoopDepth(0), CopyStmtsNum(0), DC(DC),
       IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr),
       Affinator(this, LI), AssumedContext(nullptr), InvalidContext(nullptr),
       Schedule(nullptr) {
   if (IslOnErrorAbort)
     isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
   buildContext();
 }
 

lib/CodeGen/CodeGeneration.cpp

public:
   IslAstInfo *AI;
   DominatorTree *DT;
   ScalarEvolution *SE;
   RegionInfo *RI;
   ///}
 
   /// Generate LLVM-IR for the SCoP @p S.
   bool runOnScop(Scop &S) override {
+    // Skip SCoPs in case they're already code-generated by PPCGCodeGeneration.
+    if (S.isToBeSkipped())
+      return false;
+
     AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     DL = &S.getFunction().getParent()->getDataLayout();
     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
     return CodeGen(S, *AI, *LI, *DT, *SE, *RI);
   }

lib/CodeGen/IslAst.cpp

PreservedAnalyses IslAstPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
   auto &Ast = SAM.getResult<IslAstAnalysis>(S, SAR);
   Ast.print(Stream);
   return PreservedAnalyses::all();
 }
 
 void IslAstInfoWrapperPass::releaseMemory() { Ast.reset(); }
 
 bool IslAstInfoWrapperPass::runOnScop(Scop &Scop) {
+
+  // Skip SCoPs in case they're already handled by PPCGCodeGeneration.
+  if (Scop.isToBeSkipped())
+    return false;
+
   const Dependences &D =
       getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
 
   Ast.reset(new IslAstInfo(Scop, D));
 
   DEBUG(printScop(dbgs(), Scop));
   return false;
 }

lib/CodeGen/PPCGCodeGeneration.cpp

public:
   /// Generate code for a given GPU AST described by @p Root.
   ///
   /// @param Root An isl_ast_node pointing to the root of the GPU AST.
   /// @param Prog The GPU Program to generate code for.
   void generateCode(__isl_take isl_ast_node *Root, gpu_prog *Prog) {
     ScopAnnotator Annotator;
     Annotator.buildAliasScopes(*S);
 
     Region *R = &S->getRegion();
 
     simplifyRegion(R, DT, LI, RI);
 
     BasicBlock *EnteringBB = R->getEnteringBlock();
 
     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
     // Only build the run-time condition and parameters _after_ having
bool runOnScop(Scop &CurrentScop) override {
     // We currently do not support scops with invariant loads.
     if (S->hasInvariantAccesses())
       return false;
 
     auto PPCGScop = createPPCGScop();
     auto PPCGProg = createPPCGProg(PPCGScop);
     auto PPCGGen = generateGPU(PPCGScop, PPCGProg);
 
-    if (PPCGGen->tree)
+    if (PPCGGen->tree) {
       generateCode(isl_ast_node_copy(PPCGGen->tree), PPCGProg);
+      CurrentScop.markAsToBeSkipped();
+    }
 
     freeOptions(PPCGScop);
     freePPCGGen(PPCGGen);
     gpu_prog_free(PPCGProg);
     ppcg_scop_free(PPCGScop);
 
     return true;
   }

lib/Support/RegisterPasses.cpp

 enum CodeGenChoice { CODEGEN_FULL, CODEGEN_AST, CODEGEN_NONE };
 static cl::opt<CodeGenChoice> CodeGeneration(
     "polly-code-generation", cl::desc("How much code-generation to perform"),
     cl::values(clEnumValN(CODEGEN_FULL, "full", "AST and IR generation"),
                clEnumValN(CODEGEN_AST, "ast", "Only AST generation"),
                clEnumValN(CODEGEN_NONE, "none", "No code generation")),
     cl::Hidden, cl::init(CODEGEN_FULL), cl::ZeroOrMore, cl::cat(PollyCategory));
 
-enum TargetChoice { TARGET_CPU, TARGET_GPU };
+enum TargetChoice { TARGET_CPU, TARGET_GPU, TARGET_HYBRID };
 static cl::opt<TargetChoice>
     Target("polly-target", cl::desc("The hardware to target"),
            cl::values(clEnumValN(TARGET_CPU, "cpu", "generate CPU code")
 #ifdef GPU_CODEGEN
                           ,
-                      clEnumValN(TARGET_GPU, "gpu", "generate GPU code")
+                      clEnumValN(TARGET_GPU, "gpu", "generate GPU code"),
+                      clEnumValN(TARGET_HYBRID, "hybrid",
+                                 "generate GPU code (preferably) or CPU code")
 #endif
                           ),
            cl::init(TARGET_CPU), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 #ifdef GPU_CODEGEN
 static cl::opt<GPURuntime> GPURuntimeChoice(
     "polly-gpu-runtime", cl::desc("The GPU Runtime API to target"),
     cl::values(clEnumValN(GPURuntime::CUDA, "libcudart",
if (ImportJScop)
     PM.add(polly::createJSONImporterPass());
 
   if (DeadCodeElim)
     PM.add(polly::createDeadCodeElimPass());
 
   if (EnablePruneUnprofitable)
     PM.add(polly::createPruneUnprofitablePass());
 
-  if (Target == TARGET_GPU) {
-    // GPU generation provides its own scheduling optimization strategy.
-  } else {
+#ifdef GPU_CODEGEN
+  if (Target == TARGET_HYBRID)
+    PM.add(
+        polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
+#endif
+  if (Target == TARGET_CPU || Target == TARGET_HYBRID)
     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) {
-#ifdef GPU_CODEGEN
-    PM.add(
-        polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
-#endif
-  } else {
+  if (Target == TARGET_CPU || Target == TARGET_HYBRID)
     switch (CodeGeneration) {
     case CODEGEN_AST:
       PM.add(polly::createIslAstInfoWrapperPassPass());
       break;
     case CODEGEN_FULL:
       PM.add(polly::createCodeGenerationPass());
       break;
     case CODEGEN_NONE:
       break;
     }
-  }
+#ifdef GPU_CODEGEN
+  else
+    PM.add(
+        polly::createPPCGCodeGenerationPass(GPUArchChoice, GPURuntimeChoice));
+#endif
 
   // 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 (DumpAfter)
     PM.add(polly::createDumpModulePass("-after", true));
   for (auto &Filename : DumpAfterFile)
     PM.add(polly::createDumpModulePass(Filename, false));
 
   if (CFGPrinter)
     PM.add(llvm::createCFGPrinterLegacyPassPass());
 
-  if (Target == TARGET_GPU) {
+#ifdef GPU_CODEGEN
+  if (Target == TARGET_GPU || Target == TARGET_HYBRID) {
     // Invariant load hoisting not yet supported by GPU code generation.
     PollyInvariantLoadHoisting = false;
   }
+#endif
 }
 
 static bool shouldEnablePolly() {
   if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer)
     PollyTrackFailures = true;
 
   if (PollyOnlyPrinter || PollyPrinter || PollyOnlyViewer || PollyViewer ||
       ExportJScop || ImportJScop)

lib/Transform/ScheduleOptimizer.cpp

private:
   isl_schedule *LastSchedule;
 };
 } // namespace
 
 char IslScheduleOptimizer::ID = 0;
 
 bool IslScheduleOptimizer::runOnScop(Scop &S) {
 
+  // Skip SCoPs in case they're already optimised by PPCGCodeGeneration
+  if (S.isToBeSkipped())
+    return false;
+
   // Skip empty SCoPs but still allow code generation as it will delete the
   // loops present but not needed.
   if (S.getSize() == 0) {
     S.markAsOptimized();
     return false;
   }
 
   const Dependences &D =