[Polly] [PPCGCodeGeneration] Skip arrays with empty extent.

[bollu]

Summary

Invariant load hoisted scalars, and arrays whose size we can
statically compute to be 0 do not need to be allocated as arrays.

Invariant load hoisted scalars are sent to the kernel directly as
parameters. Earlier, we used to allocate 0 bytes of memory for these.
Now, since we don't track them as arrays, this problem does not occur
anymore.

[bollu]

test/GPGPU/invariant-load-of-scalar.ll

39 ↗

(On Diff #107887)

I test it this way because checking for the entire line is too long. Is there some way to split a test into multiple lines? the FileCheck page on LLVM doesn't indicate any.

The actual test would be:

@FUNC_checkPrivatization_SCOP_0_KERNEL_0(i8 addrspace(1)* %MemRef_A, i32 %tmp, i32 %tmp2, i32 %polly.access.begin.load, i32 %polly.access.end.load)

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

2808 ↗

(On Diff #107887)

Not sure if make_filter_range makes the code cleaner or not.

2808 ↗

(On Diff #107887)

I wanted to take a const ScopArrayInfo *SAI (because it's a filter), but unfortunately getExtent(ScopArrayInfo *Array) is not const, even though it could be.

@grosser - may I change it to const in a later NFC patch?

[philip.pfaffe]

test/GPGPU/invariant-load-of-scalar.ll

39 ↗

(On Diff #107887)

FileCheck has CHECK-SAME for checking mulitple things on the same line.

[singam-sanjay]

How are invariant loads to pointers turned into scalar accesses ? Do we need -polly-invariant-load-hoisting for that ?

lib/CodeGen/PPCGCodeGeneration.cpp

2803 ↗

(On Diff #107887)

Nitpick:
Otherwise, this will cause Polly to consider the following kinds of
(Or)
Otherwise, the following kinds of empty arrays would be considered:

[grosser]

Otherwise. this LGTM.

test/GPGPU/invariant-load-of-scalar.ll

35 ↗

(On Diff #107887)

Rather then checking for the absence of a very specific string, I would check that allocateMemoryForDevice is called exactly X times. This is more robust, instead of array order or names change.

39 ↗

(On Diff #107887)

Just break the line with "\" at the end of the line (or make it more than 80 characters)

[bollu]

@singam-sanjay: Yep, all of this needs invariant load hoisting.

[bollu]

• [NFC wrt patch] refine test case to be more readable and less breakable

[grosser]

test/GPGPU/invariant-load-of-scalar.ll

35 ↗

(On Diff #107887)

I suggest to just check for:

HOST-IR-NOT: polly_allocateMemoryForDevice

We do not want ANY other memory location. This is more robust than checking for specific names.

[bollu]

• [NFC wrt patch] make CHECK-NOT more general

[grosser]

Very cool. I think this one is now good to

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

void setArrayBounds(gpu_array_info &PPCGArray, ScopArrayInfo *Array) {
     PPCGArray.bound =
         isl_multi_pw_aff_from_pw_aff_list(BoundsSpace, BoundsList);
     assert(PPCGArray.bound && "PPCGArray.bound was not constructed correctly.");
   }
 
   /// Create the arrays for @p PPCGProg.
   ///
   /// @param PPCGProg The program to compute the arrays for.
-  void createArrays(gpu_prog *PPCGProg) {
+  void createArrays(gpu_prog *PPCGProg,
+                    const SmallVector<ScopArrayInfo *, 4> &ValidSAIs) {
     int i = 0;
-    for (auto &Array : S->arrays()) {
+    for (auto &Array : ValidSAIs) {
       std::string TypeName;
       raw_string_ostream OS(TypeName);
 
       OS << *Array->getElementType();
       TypeName = OS.str();
 
       gpu_array_info &PPCGArray = PPCGProg->array[i];
 
gpu_prog *createPPCGProg(ppcg_scop *PPCGScop) {
     // this needs to be set when live range reordering is enabled.
     // NOTE: I believe that is conservatively correct. I'm not sure
     //       what the semantics of this is.
     // Quoting PPCG/gpu.h: "Order dependences on non-scalars."
     PPCGProg->array_order =
         isl_union_map_empty(isl_set_get_space(PPCGScop->context));
     PPCGProg->n_stmts = std::distance(S->begin(), S->end());
     PPCGProg->stmts = getStatements();
-    PPCGProg->n_array = std::distance(S->array_begin(), S->array_end());
+
+    // Only consider arrays that have a non-empty extent.
+    // Otherwise, this will cause us to consider the following kinds of
+    // empty arrays:
+    //     1. Invariant loads that are represented by SAI objects.
+    //     2. Arrays with statically known zero size.
+    auto ValidSAIsRange =
+        make_filter_range(S->arrays(), [this](ScopArrayInfo *SAI) -> bool {
+          return !isl::manage(getExtent(SAI)).is_empty();
+        });
+    SmallVector<ScopArrayInfo *, 4> ValidSAIs(ValidSAIsRange.begin(),
+                                              ValidSAIsRange.end());
+
+    PPCGProg->n_array =
+        ValidSAIs.size(); // std::distance(S->array_begin(), S->array_end());
     PPCGProg->array = isl_calloc_array(S->getIslCtx(), struct gpu_array_info,
                                        PPCGProg->n_array);
 
-    createArrays(PPCGProg);
+    createArrays(PPCGProg, ValidSAIs);
 
     PPCGProg->may_persist = compute_may_persist(PPCGProg);
     return PPCGProg;
   }
 
   struct PrintGPUUserData {
     struct cuda_info *CudaInfo;
     struct gpu_prog *PPCGProg;

polly/trunk/test/GPGPU/invariant-load-of-scalar.ll

+; RUN: opt %loadPolly -polly-scops -polly-invariant-load-hoisting \
+; RUN: -analyze < %s | \
+; RUN: FileCheck -check-prefix=SCOP %s
+
+; RUN: opt %loadPolly -polly-codegen-ppcg -polly-invariant-load-hoisting \
+; RUN: -S < %s | \
+; RUN: FileCheck -check-prefix=HOST-IR %s
+
+
+; RUN: opt %loadPolly -polly-codegen-ppcg -polly-invariant-load-hoisting \
+; RUN: -disable-output -polly-acc-dump-kernel-ir < %s | \
+; RUN: FileCheck -check-prefix=KERNEL-IR %s
+
+; REQUIRES: pollyacc
+
+; Check that we offload invariant loads of scalars correctly.
+
+; Check that invariant loads are present.
+; SCOP:      Function: checkPrivatization
+; SCOP-NEXT: Region: %entry.split---%for.end
+; SCOP-NEXT: Max Loop Depth:  1
+; SCOP-NEXT: Invariant Accesses: {
+; SCOP-NEXT:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOP-NEXT:             [tmp, tmp2] -> { Stmt_entry_split[] -> MemRef_begin[0] };
+; SCOP-NEXT:         Execution Context: [tmp, tmp2] -> {  :  }
+; SCOP-NEXT:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOP-NEXT:             [tmp, tmp2] -> { Stmt_for_body[i0] -> MemRef_end[0] };
+; SCOP-NEXT:         Execution Context: [tmp, tmp2] -> {  :  }
+; SCOP-NEXT: }
+;
+
+; Check that we do not actually allocate arrays for %begin, %end, since they are
+; invariant load hoisted.
+; HOST-IR: %p_dev_array_MemRef_A = call i8* @polly_allocateMemoryForDevice(i64 %35)
+; HOST-IR-NOT: call i8* @polly_allocateMemoryForDevice
+
+; Check that we send the invariant loaded scalars as parameters to the
+; kernel function.
+; KERNEL-IR: define ptx_kernel void @FUNC_checkPrivatization_SCOP_0_KERNEL_0
+; KERNEL-IR-SAME: (i8 addrspace(1)* %MemRef_A, i32 %tmp,
+; KERNEL-IR-SAME: i32 %tmp2, i32 %polly.access.begin.load,
+; KERNEL-IR-SAME: i32 %polly.access.end.load)
+
+
+; void checkScalarPointerOffload(int A[], int *begin, int *end) {
+;     for(int i = *begin; i < *end; i++) {
+;         A[i] = 10;
+;     }
+; }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.12.0"
+
+define void @checkPrivatization(i32* %A, i32* %begin, i32* %end) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %tmp = load i32, i32* %begin, align 4
+  %tmp21 = load i32, i32* %end, align 4
+  %cmp3 = icmp slt i32 %tmp, %tmp21
+  br i1 %cmp3, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry.split
+  %tmp1 = sext i32 %tmp to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %indvars.iv4 = phi i64 [ %tmp1, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv4
+  store i32 10, i32* %arrayidx, align 4
+  %indvars.iv.next = add i64 %indvars.iv4, 1
+  %tmp2 = load i32, i32* %end, align 4
+  %tmp3 = sext i32 %tmp2 to i64
+  %cmp = icmp slt i64 %indvars.iv.next, %tmp3
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split
+  ret void
+}
+