[Polly] [PPCGCodeGeneration] Deal with loops outside the Scop correctly in PPCGCodeGeneration.

[bollu]

Summary

A Scop with a loop outside it is not handled currently by
PPCGCodeGeneration. The test case is such that the Scop has only one inner loop
that is detected. This currently breaks codegen.

The fix is to reuse the existing mechanism in IslNodeBuilder within
`GPUNodeBuilder.

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

1413 ↗

(On Diff #109638)

@grosser - Can you explain to me why the other condition exists? (L->contains(S.getEntry()))

I removed this extra condition from IslNodeBuilder and all our checks pass. git blame is somewhat unhelpful, since it points to a commit where IslNodeBuilder was extracted out.

If you want to verify,

remove-extra-check.patch

diff --git a/lib/CodeGen/IslNodeBuilder.cpp b/lib/CodeGen/IslNodeBuilder.cpp
index ecc84f40..7474af4b 100644
--- a/lib/CodeGen/IslNodeBuilder.cpp
+++ b/lib/CodeGen/IslNodeBuilder.cpp
@@ -313,7 +313,7 @@ void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
   /// are considered local. This leaves only loops that are before the scop, but
   /// do not contain the scop itself.
   Loops.remove_if([this](const Loop *L) {
-    return S.contains(L) || L->contains(S.getEntry());
+    return S.contains(L); // || L->contains(S.getEntry());
   });

   // Contains Values that may need to be replaced with other values

[grosser]

Added a comment. Waiting for reply.

lib/CodeGen/PPCGCodeGeneration.cpp

1413 ↗

(On Diff #109638)

In fact, this seems to be exactly the loops we want to keep to fix the bug we are seeing. Did you run your test-case with the OpenMP code generation, I wonder if it suffers from the very same bug and your test case also fails. In case it does, I would suggest to add the test case, to drop the second condition, and to update the comment.

[bollu]

• [Works] [WIP] recreate whatever IslNodeBuilder does in PPCGCodeGeneration

[bollu]

• [NFC] remove copied code, add a comment explaining some dataflow

[bollu]

• [Polly] [WIP] [PPCGCodeGeneration] Deal with loops outside the Scop correctly in PPCGCodeGeneration.
• [WIP] try to reuse IslNodeBuilder machinery to reduce differences
• [Works] [WIP] recreate whatever IslNodeBuilder does in PPCGCodeGeneration
• [NFC] removing weird comments from code
• [NFC] remove copied code, add a comment explaining some dataflow
• [NFC] remove comment

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

1413 ↗

(On Diff #109638)

Writing this up for documentation: OpenMP succeeds because it populates the IslNodeBuilder::OutsideLoopIterations list at IslNodeBuilder::materialiseParameters.

It adds everything in OutsideLoopIterations at IslNodeBuilder::getReferencesInSubtree.

This is somewhat action-at-a-distance, but then, that's true of everything with mutation so I'm not sure how to structure it better.

[bollu]

• [NFC] whitespace cleanup

[bollu]

@grosser, @singam-sanjay - Review, please.

[grosser]

LGTM

lib/CodeGen/PPCGCodeGeneration.cpp

1416 ↗

(On Diff #109720)

Could you add a comment why which loops we exclude and why?

[philip.pfaffe]

lib/CodeGen/PPCGCodeGeneration.cpp

419 ↗

(On Diff #109720)

You should update the doxygen accordingly

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
 
   SetVector<const SCEV *> SCEVs;
   struct SubtreeReferences References = {
       LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator()};
 
   for (const auto &I : IDToValue)
     Values.insert(I.second);
 
+  // NOTE: this is populated in IslNodeBuilder::addParameters
   for (const auto &I : OutsideLoopIterations)
     Values.insert(cast<SCEVUnknown>(I.second)->getValue());
 
   isl_union_set *Schedule = isl_union_map_domain(getScheduleForAstNode(For));
   addReferencesFromStmtUnionSet(Schedule, References);
 
   for (const SCEV *Expr : SCEVs) {
     findValues(Expr, SE, Values);

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

private:
   /// @param Direction The direction in which to transfer data.
   void createDataTransfer(__isl_take isl_ast_node *TransferStmt,
                           enum DataDirection Direction);
 
   /// Find llvm::Values referenced in GPU kernel.
   ///
   /// @param Kernel The kernel to scan for llvm::Values
   ///
-  /// @returns A pair, whose first element contains the set of values
-  ///          referenced by the kernel, and whose second element contains the
-  ///          set of functions referenced by the kernel. All functions in the
-  ///          second set satisfy isValidFunctionInKernel.
-  std::pair<SetVector<Value *>, SetVector<Function *>>
+  /// @returns A tuple, whose:
+  ///          - First element contains the set of values referenced by the
+  ///            kernel
+  ///          - Second element contains the set of functions referenced by the
+  ///             kernel. All functions in the set satisfy
+  ///             `isValidFunctionInKernel`.
+  ///          - Third element contains loops that have induction variables
+  ///            which are used in the kernel, *and* these loops are *neither*
+  ///            in the scop, nor do they immediately surroung the Scop.
+  ///            See [Code generation of induction variables of loops outside
+  ///            Scops]
+  std::tuple<SetVector<Value *>, SetVector<Function *>, SetVector<const Loop *>>
   getReferencesInKernel(ppcg_kernel *Kernel);
 
   /// Compute the sizes of the execution grid for a given kernel.
   ///
   /// @param Kernel The kernel to compute grid sizes for.
   ///
   /// @returns A tuple with grid sizes for X and Y dimension
   std::tuple<Value *, Value *> getGridSizes(ppcg_kernel *Kernel);
if (F) {
              "this point if an invalid function "
              "were present in a kernel.");
       SubtreeFunctions.insert(F);
     }
   }
   return SubtreeFunctions;
 }
 
-std::pair<SetVector<Value *>, SetVector<Function *>>
+std::tuple<SetVector<Value *>, SetVector<Function *>, SetVector<const Loop *>>
 GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
   SetVector<Value *> SubtreeValues;
   SetVector<const SCEV *> SCEVs;
   SetVector<const Loop *> Loops;
   SubtreeReferences References = {
       LI, SE, S, ValueMap, SubtreeValues, SCEVs, getBlockGenerator()};
 
   for (const auto &I : IDToValue)
     SubtreeValues.insert(I.second);
 
+  // NOTE: this is populated in IslNodeBuilder::addParameters
+  // See [Code generation of induction variables of loops outside Scops].
+  for (const auto &I : OutsideLoopIterations)
+    SubtreeValues.insert(cast<SCEVUnknown>(I.second)->getValue());
+
   isl_ast_node_foreach_descendant_top_down(
       Kernel->tree, collectReferencesInGPUStmt, &References);
 
-  for (const SCEV *Expr : SCEVs)
+  for (const SCEV *Expr : SCEVs) {
     findValues(Expr, SE, SubtreeValues);
+    findLoops(Expr, Loops);
+  }
+
+  Loops.remove_if([this](const Loop *L) {
+    return S.contains(L) || L->contains(S.getEntry());
+  });
 
   for (auto &SAI : S.arrays())
     SubtreeValues.remove(SAI->getBasePtr());
 
   isl_space *Space = S.getParamSpace();
   for (long i = 0; i < isl_space_dim(Space, isl_dim_param); i++) {
     isl_id *Id = isl_space_get_dim_id(Space, isl_dim_param, i);
     assert(IDToValue.count(Id));
GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
   SetVector<Value *> ReplacedValues;
   for (Value *V : ValidSubtreeValues) {
     auto It = ValueMap.find(V);
     if (It == ValueMap.end())
       ReplacedValues.insert(V);
     else
       ReplacedValues.insert(It->second);
   }
-  return std::make_pair(ReplacedValues, ValidSubtreeFunctions);
+  return std::make_tuple(ReplacedValues, ValidSubtreeFunctions, Loops);
 }
 
 void GPUNodeBuilder::clearDominators(Function *F) {
   DomTreeNode *N = DT.getNode(&F->getEntryBlock());
   std::vector<BasicBlock *> Nodes;
   for (po_iterator<DomTreeNode *> I = po_begin(N), E = po_end(N); I != E; ++I)
     Nodes.push_back(I->getBlock());
 
else
     DeepestSequential =
         std::max(DeepestSequential, isl_space_dim(Kernel->space, isl_dim_set));
 
   Value *BlockDimX, *BlockDimY, *BlockDimZ;
   std::tie(BlockDimX, BlockDimY, BlockDimZ) = getBlockSizes(Kernel);
 
   SetVector<Value *> SubtreeValues;
   SetVector<Function *> SubtreeFunctions;
-  std::tie(SubtreeValues, SubtreeFunctions) = getReferencesInKernel(Kernel);
+  SetVector<const Loop *> Loops;
+  std::tie(SubtreeValues, SubtreeFunctions, Loops) =
+      getReferencesInKernel(Kernel);
 
   assert(Kernel->tree && "Device AST of kernel node is empty");
 
   Instruction &HostInsertPoint = *Builder.GetInsertPoint();
   IslExprBuilder::IDToValueTy HostIDs = IDToValue;
   ValueMapT HostValueMap = ValueMap;
   BlockGenerator::AllocaMapTy HostScalarMap = ScalarMap;
   ScalarMap.clear();
 
-  SetVector<const Loop *> Loops;
-
   // Create for all loops we depend on values that contain the current loop
   // iteration. These values are necessary to generate code for SCEVs that
   // depend on such loops. As a result we need to pass them to the subfunction.
   for (const Loop *L : Loops) {
     const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
                                             SE.getUnknown(Builder.getInt64(1)),
                                             L, SCEV::FlagAnyWrap);
     Value *V = generateSCEV(OuterLIV);

polly/trunk/test/GPGPU/loops-outside-scop.ll

+; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s -check-prefix=SCOP
+
+; There is no FileCheck because we want to make sure that this doesn't crash.
+; RUN: opt %loadPolly -polly-codegen-ppcg -polly-acc-fail-on-verify-module-failure \
+; RUN: -disable-output < %s
+
+; REQUIRES: pollyacc
+
+; Due to the existence of the `fence` call, We can only detect the inner loop
+; and not the outer loop. PPCGCodeGeneration had not implemented this case.
+; The fix was to pull the implementation from `IslNodeBuilder.
+
+; Make sure that we only capture the inner loop
+; SCOP:      Function: f
+; SCOP-NEXT: Region: %for2.body---%for2.body.fence
+; SCOP-NEXT: Max Loop Depth:  1
+
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @fn_to_fence(i32 *%val)
+
+; void f(int *arr, bool shouldcont) {
+;     for(int i = 0; ; i++) {
+;         for(int j = 0; j < 10; j++) {
+;             arr[j] = i;
+;         }
+;         fence(arr);
+;         if (!shouldcont) break;
+;     }
+; }
+
+
+; Function Attrs: nounwind uwtable
+define void @f(i32 *%arr, i1 %shouldcont) #1 {
+entry:
+  br label %for.init
+
+for.init:                                             ; preds = %for.end, %entry.split
+  %i = phi i32 [ %i.next, %for.end ], [ 0, %entry ]
+  br label %for2.body
+
+for2.body:                                             ; preds = %"65", %"64"
+  %j = phi i32 [ %j.next, %for2.body ], [ 0, %for.init ]
+  %j.sext = sext i32 %j to i64
+  %arr.slot = getelementptr i32, i32* %arr, i64 %j.sext
+  store i32 %i, i32* %arr.slot, align 4
+  %exitcond = icmp eq i32 %j, 10
+  %j.next = add i32 %j, 1
+  br i1 %exitcond, label %for2.body.fence, label %for2.body
+
+for2.body.fence:                                             ; preds = %"65"
+  call void @fn_to_fence(i32* %arr) #2
+  br i1 %shouldcont, label %for.end, label %exit
+for.end:                                             ; preds = %"69"
+  %i.next = add i32 %i, 1
+  br label %for.init
+
+exit:                                             ; preds = %"69"
+  ret void
+
+}
+
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind uwtable }
+attributes #2 = { nounwind }