[GPGPU] Collect parameter dimension used in MemoryAccesses

[grosser]

Summary

When using -polly-ignore-integer-wrapping and -polly-acc-codegen-managed-memory
we add parameter dimensions lazily to the domains, which results in PPCG not
including parameter dimensions that are only used in memory accesses in the
kernel space. To make sure these parameters are still passed to the kernel, we
collect these parameter dimensions and align the kernel's parameter space
before code-generating it.

[bollu]

I would like to discuss the isl::space ParamSpace issue before LGTM'ing this patch.

include/polly/CodeGen/IslNodeBuilder.h

47

Please see the comment about using isl::space * here to broadcast the fact that this is an optional member of the struct.

lib/CodeGen/IslNodeBuilder.cpp

231–237

Nit: Change the auto to MemoryAccess? It would not be obvious to someone who does not work on Polly that a statement iterator gives MemoryAccess.

306

We abuse the fact that nullptr operations just propagate nullptr in ISL. I'm trying to think of neater ways to express this. I _really_ abusing nullptr this way since it is quite literally dependent on the ISL implementation.

For now, we can make it a isl::space * to express the fact that it a choice. Ideally, we could somehow split the different "visitors" so that ISLNodeBuilder would not use the parameter visitor but GPUNodeBuilder could.

test/GPGPU/memory-only-referenced-from-access.ll

50

Please remove the metadata which is not required.

[grosser]

Address Siddharth's comments

[bollu]

Thanks! Other than nits, LGTM.

include/polly/CodeGen/IslNodeBuilder.h

47

Could you add a comment here stating why this is obvious, and maybe a FIXME for a nicer design?

lib/CodeGen/PPCGCodeGeneration.cpp

1446

Unintended space?
LI, SE,

[grosser]

Committed in r311239. I forgot to add the phab URL, hence I close it manually.

lib/CodeGen/IslNodeBuilder.cpp

231–237

This is an unrelated change. I will do it ahead of the commit.

lib/CodeGen/PPCGCodeGeneration.cpp

1446

That's a clang-format artifact. Seems the formatting choice is not totally optimal here. I leave it as it is, as I see now way to work around it.

include/polly/CodeGen/IslNodeBuilder.h

 #include "polly/CodeGen/LoopGenerators.h"
 #include "polly/ScopInfo.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "isl/ctx.h"
 #include "isl/union_map.h"
+
+#include "isl-noexceptions.h"
+
 #include <utility>
 #include <vector>
 
 using namespace polly;
 using namespace llvm;
 
 struct isl_ast_node;
 struct isl_ast_build;
 struct isl_union_map;
 
 struct SubtreeReferences {
   LoopInfo &LI;
   ScalarEvolution &SE;
   Scop &S;
   ValueMapT &GlobalMap;
   SetVector<Value *> &Values;
   SetVector<const SCEV *> &SCEVs;
   BlockGenerator &BlockGen;
+  isl::space *ParamSpace;
 };
 
 /// Extract the out-of-scop values and SCEVs referenced from a ScopStmt.
 ///
 /// This includes the SCEVUnknowns referenced by the SCEVs used in the
 /// statement and the base pointers of the memory accesses. For scalar
 /// statements we force the generation of alloca memory locations and list
 /// these locations in the set of out-of-scop values as well.
 ///
+/// We also collect an isl::space that includes all parameter dimensions
+/// used in the statement's memory accesses, in case the ParamSpace pointer
+/// is non-null.
+///
 /// @param Stmt             The statement for which to extract the information.
 /// @param UserPtr          A void pointer that can be casted to a
 ///                         SubtreeReferences structure.
 /// @param CreateScalarRefs Should the result include allocas of scalar
 ///                         references?
 isl_stat addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr,
                                bool CreateScalarRefs = true);
 

lib/CodeGen/IslNodeBuilder.cpp

if (Stmt->isBlockStmt())
     findReferencesInBlock(References, Stmt, Stmt->getBasicBlock());
   else {
     assert(Stmt->isRegionStmt() &&
            "Stmt was neither block nor region statement");
     for (BasicBlock *BB : Stmt->getRegion()->blocks())
       findReferencesInBlock(References, Stmt, BB);
   }
 
   for (auto &Access : *Stmt) {
+    if (References.ParamSpace) {
+      isl::space ParamSpace = Access->getLatestAccessRelation().get_space();
+      (*References.ParamSpace) =
+          References.ParamSpace->align_params(ParamSpace);
+    }
+
     if (Access->isLatestArrayKind()) {
       auto *BasePtr = Access->getScopArrayInfo()->getBasePtr();
       if (Instruction *OpInst = dyn_cast<Instruction>(BasePtr))
         if (Stmt->getParent()->contains(OpInst))
           continue;
 
       References.Values.insert(BasePtr);
       continue;

 }
 
 void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
                                             SetVector<Value *> &Values,
                                             SetVector<const Loop *> &Loops) {
 
   SetVector<const SCEV *> SCEVs;
   struct SubtreeReferences References = {
-      LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator()};
+      LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator(), nullptr};
 
   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());
 

lib/CodeGen/PPCGCodeGeneration.cpp

private:
   ///          - 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 *>>
+  std::tuple<SetVector<Value *>, SetVector<Function *>, SetVector<const Loop *>,
+             isl::space>
   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::tuple<SetVector<Value *>, SetVector<Function *>, SetVector<const Loop *>>
+std::tuple<SetVector<Value *>, SetVector<Function *>, SetVector<const Loop *>,
+           isl::space>
 GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
   SetVector<Value *> SubtreeValues;
   SetVector<const SCEV *> SCEVs;
   SetVector<const Loop *> Loops;
+  isl::space ParamSpace = isl::space(S.getIslCtx(), 0, 0).params();
   SubtreeReferences References = {
-      LI, SE, S, ValueMap, SubtreeValues, SCEVs, getBlockGenerator()};
+      LI,         SE, S, ValueMap, SubtreeValues, SCEVs, getBlockGenerator(),
+      &ParamSpace};
 
   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());
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_tuple(ReplacedValues, ValidSubtreeFunctions, Loops);
+  return std::make_tuple(ReplacedValues, ValidSubtreeFunctions, Loops,
+                         ParamSpace);
 }
 
 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());
 
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;
   SetVector<const Loop *> Loops;
-  std::tie(SubtreeValues, SubtreeFunctions, Loops) =
+  isl::space ParamSpace;
+  std::tie(SubtreeValues, SubtreeFunctions, Loops, ParamSpace) =
       getReferencesInKernel(Kernel);
 
+  // Add parameters that appear only in the access function to the kernel
+  // space. This is important to make sure that all isl_ids are passed as
+  // parameters to the kernel, even though we may not have all parameters
+  // in the context to improve compile time.
+  Kernel->space = isl_space_align_params(Kernel->space, ParamSpace.release());
+
   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();
 

test/GPGPU/memory-only-referenced-from-access.ll

+; RUN: opt %loadPolly -polly-codegen-ppcg -polly-acc-dump-kernel-ir \
+; RUN: -polly-invariant-load-hoisting -polly-ignore-aliasing \
+; RUN: -polly-process-unprofitable -polly-ignore-parameter-bounds \
+; RUN: -polly-acc-fail-on-verify-module-failure \
+; RUN: -polly-acc-codegen-managed-memory \
+; RUN: -disable-output < %s | \
+; RUN: FileCheck %s
+
+; REQUIRES: pollyacc
+
+; Verify that we correctly generate a kernel even if certain invariant load
+; hoisted parameters appear only in memory accesses, but not domain elements.
+
+; CHECK: @FUNC_quux_SCOP_0_KERNEL_0(i8 addrspace(1)* %MemRef_tmp4, i32 %tmp3, i32 %tmp, i32 %tmp31, i32 %tmp2)
+
+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"
+
+%struct.hoge = type { i8*, i64, i64, [1 x %struct.widget] }
+%struct.widget = type { i64, i64, i64 }
+
+@global = external unnamed_addr global %struct.hoge, align 32
+
+define void @quux(i32* noalias %arg, i32* noalias %arg1) {
+bb:
+  %tmp = load i32, i32* %arg, align 4
+  %tmp2 = sext i32 %tmp to i64
+  %tmp3 = load i32, i32* %arg1, align 4
+  %tmp4 = load [0 x double]*, [0 x double]** bitcast (%struct.hoge* @global to [0 x double]**), align 32
+  br label %bb5
+
+bb5:                                              ; preds = %bb5, %bb
+  %tmp6 = phi i32 [ %tmp11, %bb5 ], [ 0, %bb ]
+  %tmp7 = sext i32 %tmp6 to i64
+  %tmp8 = sub nsw i64 %tmp7, %tmp2
+  %tmp9 = getelementptr [0 x double], [0 x double]* %tmp4, i64 0, i64 %tmp8
+  store double undef, double* %tmp9, align 8
+  %tmp10 = icmp eq i32 %tmp6, %tmp3
+  %tmp11 = add i32 %tmp6, 1
+  br i1 %tmp10, label %bb12, label %bb5
+
+bb12:                                             ; preds = %bb5
+  ret void
+}