[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

@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

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

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

1413

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

[philip.pfaffe]

lib/CodeGen/PPCGCodeGeneration.cpp

419

You should update the doxygen accordingly

lib/CodeGen/PPCGCodeGeneration.cpp

private:
 
   /// 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 *>>
+  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;
+  // TODO: Populate this.
   SetVector<const Loop *> Loops;
   SubtreeReferences References = {
       LI, SE, S, ValueMap, SubtreeValues, SCEVs, getBlockGenerator()};
 
   for (const auto &I : IDToValue)
     SubtreeValues.insert(I.second);
 
   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) {
+    // Note: I do not understand why this condition exists in IslNodeBuilder
+    //       in the first place. I need to investigate this. Intuitively, I
+    //       don't understand why we would skip a loop if it contains the entry
+    //       BB of a Scop.
+    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);
for (long i = 0; i < Prog->n_array; i++) {
     } else {
       static const int UseGlobalMemory = 1;
       Args.push_back(Builder.getInt8PtrTy(UseGlobalMemory));
       MemoryType.push_back(
           ConstantAsMetadata::get(ConstantInt::get(Builder.getInt32Ty(), 1)));
     }
   }
 
+  // block generator copy, we try to look for SCEV.
   int NumHostIters = isl_space_dim(Kernel->space, isl_dim_set);
 
   for (long i = 0; i < NumHostIters; i++) {
     Args.push_back(Builder.getInt64Ty());
     MemoryType.push_back(
         ConstantAsMetadata::get(ConstantInt::get(Builder.getInt32Ty(), 0)));
   }
 

test/GPGPU/test.ll

+; RUN: opt %loadPolly -polly-codegen-ppcg -polly-acc-fail-on-verify-module-failure \
+; RUN: -disable-output < %s
+
+; ModuleID = 'reduced.ll'
+source_filename = "bugpoint-output-cb5513b.bc"
+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
+  %indvar = phi i32 [ %indvar.next, %for.end ], [ 0, %entry ]
+  br label %for2.body
+
+for2.body:                                             ; preds = %"65", %"64"
+  %indvar2 = phi i32 [ %indvar2.next, %for2.body ], [ 0, %for.init ]
+  %indvar2.sext = sext i32 %indvar2 to i64
+  %arr.slot = getelementptr i32, i32* %arr, i64 %indvar2.sext
+  store i32 %indvar, i32* %arr.slot, align 4
+  %exitcond = icmp eq i32 %indvar2, 10
+  %indvar2.next = add i32 %indvar2, 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"
+  %indvar.next = add i32 %indvar, 1
+  br label %for.init
+
+exit:                                             ; preds = %"69"
+  ret void
+
+}
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64) #2
+
+declare void @used_fn(...)
+
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind uwtable }
+attributes #2 = { nounwind }