[Polly] [Failing test case] Add test case that seems to fail due to invalid referencing of instructions across host and kernel modules.

[bollu]

• remove invariant load hoisting

[bollu]

• [NFC] make test case understandable

[bollu]

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

[bollu]

This is being solved in D36290, so I'm closing this.

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)
+  // @see IslNodeBuilder::materializeParameters
+  Loop *L = LI.getLoopFor(S.getEntry());
+
+  while (L != nullptr && S.contains(L))
+    L = L->getParentLoop();
+
+  while (L != nullptr) {
+    const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
+                                            SE.getUnknown(Builder.getInt64(1)),
+                                            L, SCEV::FlagAnyWrap);
+    Value *V = generateSCEV(OuterLIV);
+    OutsideLoopIterations[L] = SE.getUnknown(V);
+    L = L->getParentLoop();
+  }
+
+  for (const auto &I : OutsideLoopIterations)
+    SubtreeValues.insert(cast<SCEVUnknown>(I.second)->getValue());
+
+  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());
+    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());
 
Value *Slot = Builder.CreateGEP(
       Parameters, {Builder.getInt64(0), Builder.getInt64(Index)});
   Value *ParamTyped = Builder.CreatePointerCast(Param, Builder.getInt8PtrTy());
   Builder.CreateStore(ParamTyped, Slot);
 }
 
 Value *
 GPUNodeBuilder::createLaunchParameters(ppcg_kernel *Kernel, Function *F,
                                        SetVector<Value *> SubtreeValues) {
+
   const int NumArgs = F->arg_size();
   std::vector<int> ArgSizes(NumArgs);
 
   Type *ArrayTy = ArrayType::get(Builder.getInt8PtrTy(), 2 * NumArgs);
 
   BasicBlock *EntryBlock =
       &Builder.GetInsertBlock()->getParent()->getEntryBlock();
   auto AddressSpace = F->getParent()->getDataLayout().getAllocaAddrSpace();
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
+  %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
+
+}
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64) #2
+
+declare void @used_fn(...)
+
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind uwtable }
+attributes #2 = { nounwind }