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 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

nit: . at the end of the comment.

lib/CodeGen/IslAst.cpp

628 ↗

(On Diff #102032)

nit: . at the end of the comment.

lib/CodeGen/PPCGCodeGeneration.cpp

2690 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

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

2690 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

Sure.

2336 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

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 ↗

(On Diff #102032)

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

362 ↗

(On Diff #102186)

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

?

94 ↗

(On Diff #102032)

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

[singam-sanjay]

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

[singam-sanjay]

lib/CodeGen/PPCGCodeGeneration.cpp

2690 ↗

(On Diff #102032)

@bollu ping.

[singam-sanjay]

lib/Support/RegisterPasses.cpp

326 ↗

(On Diff #102805)

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 ↗

(On Diff #102805)

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".

94 ↗

(On Diff #102032)

@grosser ping.

[grosser]

Hi Sanjay,

this looks already very good. Just a minor thing.

Best,
Tobias

lib/Support/RegisterPasses.cpp

362 ↗

(On Diff #102186)

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

[singam-sanjay]

lib/Support/RegisterPasses.cpp

362 ↗

(On Diff #102186)

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

362 ↗

(On Diff #102186)

@grosser ping

[grosser]

LGTM.

polly/trunk/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;
 

polly/trunk/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();
 }
 

polly/trunk/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);
   }

polly/trunk/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;
 }

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

if (containsInvalidKernelFunction(CurrentScop)) {
                  "kernel. Bailing out.\n";);
       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;
   }

polly/trunk/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));

polly/trunk/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 =