[GPGPU] Correctly initialize array order and fixed_element information

[grosser]

Summary

This information is necessary for PPCG to perform correct life range reordering.
With these changes applied we can live-range reorder some of the important
kernels in COSMO.

We also update and rename one test case, which previously could not be optimized
and now is optimized thanks to live-range reordering.

[bollu]

It's cool that invariant-load-hoisting-with-failing-scop.ll now succeeds, but that's not the purpose of the test case :)

The test case was supposed to check that when we set BuildSuccessful = 0 when we fail the "scalar store check" Link to check here, we try to set the RTC to 0.

We used to do this incorrectly by making assumptions on the CFG that invariant load hoisting would wreck.

That is, invariant load hoisting would edit the CFG in such a way that us "looking up" the runtime check in the CFG would error out.

The correct way to update this test case is to make the test case more complex so we have an actual store to a scalar.

lib/CodeGen/PPCGCodeGeneration.cpp

2804

Can you add a TODO, notifying that we can have fixed_element for pointers/arrays as well, and not just scalars? Eg. Only having A[0] accesses.

This would help with stuff that @philip.pfaffe was benchmarking (theoretically).

lib/External/ppcg/gpu.c

256

Consider adding an

assert(0 && "should not reach here, polly should early-exit");

after the return?

[grosser]

Add another test case to avoid us loosing test coverage

[grosser]

Add the TODO requested by Siddharth

[bollu]

Please add the comment I requested for cc->isLatestScalarKind() ? isl_bool_true : isl_bool_false; and the test cases. LGTM.

test/GPGPU/live-range-reordering-with-privatization.ll

32

Please add a comment to this test case explaining what it tests now.

; This test case now tests the ability to infer that `t` is local to each loop iteration, and can therefore be privatized.

test/GPGPU/scalar-writes-in-scop-requires-abort.ll

20

Could you please add the more descriptive comment I had written in the original test case?

comment

; This test case checks that we generate correct code if PPCGCodeGeneration
; decides a build is unsuccessful with invariant load hoisting enabled.
; There is a conditional branch which switches between the original code and
; the new code. We try to set this conditional branch to branch on false.
; However, invariant load hoisting changes the structure of the scop, so we
; need to change the way we *locate* this instruction.

[grosser]

Add the invariant loads to the test case and copy some more comments from
Siddharth's earlier test case over

lib/CodeGen/IslNodeBuilder.cpp

Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {
   Value *OverflowHappened =
       Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");
 
   if (PollyGenerateRTCPrint) {
     auto *F = Builder.GetInsertBlock()->getParent();
     RuntimeDebugBuilder::createCPUPrinter(
         Builder,
         "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
-            " __RTC: ",
-        RTC, " Overflow: ", OverflowHappened, "\n");
+            "RTC: ",
+        RTC, " Overflow: ", OverflowHappened,
+        "\n"
+        "  (0 failed, -1 succeeded)\n"
+        "  (if one or both are 0 falling back to original code, if both are -1 "
+        "executing Polly code)\n");
   }
 
   RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");
   ExprBuilder.setTrackOverflow(false);
 
   if (!isa<ConstantInt>(RTC))
     VersionedScops++;
 
   return RTC;
 }

lib/CodeGen/PPCGCodeGeneration.cpp

for (MemoryAccess *Acc : Stmt) {
       Space = isl_space_set_tuple_id(Space, isl_dim_in, Acc->getId().release());
       isl_map *Universe = isl_map_universe(Space);
       Access->tagged_access =
           isl_map_domain_product(Acc->getAccessRelation().release(), Universe);
       Access->exact_write = !Acc->isMayWrite();
       Access->ref_id = Acc->getId().release();
       Access->next = Accesses;
       Access->n_index = Acc->getScopArrayInfo()->getNumberOfDimensions();
+      // TODO: Also mark one-element accesses to arrays as fixed-element.
+      Access->fixed_element =
+          Acc->isLatestScalarKind() ? isl_bool_true : isl_bool_false;
       Accesses = Access;
     }
 
     return Accesses;
   }
 
   /// Collect the list of GPU statements.
   ///
for (auto &Array : ValidSAIs) {
       PPCGArray.dep_order = nullptr;
       PPCGArray.user = Array;
 
       PPCGArray.bound = nullptr;
       setArrayBounds(PPCGArray, Array);
       i++;
 
       collect_references(PPCGProg, &PPCGArray);
+      PPCGArray.only_fixed_element = only_fixed_element_accessed(&PPCGArray);
     }
   }
 
   /// Create an identity map between the arrays in the scop.
   ///
   /// @returns An identity map between the arrays in the scop.
   isl_union_map *getArrayIdentity() {
     isl_union_map *Maps = isl_union_map_empty(S->getParamSpace().release());
gpu_prog *createPPCGProg(ppcg_scop *PPCGScop) {
     PPCGProg->may_write = isl_union_map_copy(PPCGScop->may_writes);
     PPCGProg->must_write = isl_union_map_copy(PPCGScop->must_writes);
     PPCGProg->tagged_must_kill =
         isl_union_map_copy(PPCGScop->tagged_must_kills);
     PPCGProg->to_inner = getArrayIdentity();
     PPCGProg->to_outer = getArrayIdentity();
     // TODO: verify that this assignment is correct.
     PPCGProg->any_to_outer = nullptr;
-
-    // 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();
 
     // 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 !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, ValidSAIs);
 
+    PPCGProg->array_order = nullptr;
+    collect_order_dependences(PPCGProg);
+
     PPCGProg->may_persist = compute_may_persist(PPCGProg);
     return PPCGProg;
   }
 
   struct PrintGPUUserData {
     struct cuda_info *CudaInfo;
     struct gpu_prog *PPCGProg;
     std::vector<ppcg_kernel *> Kernels;

lib/External/ppcg/gpu.h

 __isl_give isl_schedule *map_to_device(struct gpu_gen *gen,
                                        __isl_take isl_schedule *schedule,
                                       int to_from_device);
 __isl_give isl_ast_node *generate_code(struct gpu_gen *gen,
                                        __isl_take isl_schedule *schedule);
 
 __isl_give isl_union_set *compute_may_persist(struct gpu_prog *prog);
 void collect_references(struct gpu_prog *prog, struct gpu_array_info *array);
+void collect_order_dependences(struct gpu_prog *prog);
+isl_bool only_fixed_element_accessed(struct gpu_array_info *array);
 #endif

lib/External/ppcg/gpu.c

static int is_read_only_scalar(struct gpu_array_info *array,
   isl_union_map_free(write);
 
   return empty;
 }
 
 /* Is "array" only accessed as individual, fixed elements?
  * That is, does each access to "array" access a single, fixed element?
  */
-static isl_bool only_fixed_element_accessed(struct gpu_array_info *array)
+isl_bool only_fixed_element_accessed(struct gpu_array_info *array)
 {
   int i;
 
   for (i = 0; i < array->n_ref; ++i)
     if (!array->refs[i]->fixed_element)
       return isl_bool_false;
 
   return isl_bool_true;

  * in compute_schedule because we do not support any array expansion.
  * Accesses to non-local arrays should not prevent a loop from being
  * considered coincident so we should indeed remove those constraints
  * from the order constraints.
  */
 static __isl_give isl_union_map *remove_independences(struct gpu_prog *prog,
   struct gpu_array_info *array, __isl_take isl_union_map *order)
 {
+  // We do not have independence information in Polly. Hence, make this
+  // function a no-op.
+  return order;
   int i;
 
   for (i = 0; i < prog->scop->pet->n_independence; ++i) {
     struct pet_independence *pi = prog->scop->pet->independences[i];
     if (isl_union_set_contains(pi->local, array->space))
       continue;
 
     order = isl_union_map_subtract(order,
             isl_union_map_copy(pi->filter));

test/GPGPU/live-range-reordering-with-privatization.ll

-; RUN: opt %loadPolly -analyze -polly-use-llvm-names -polly-scops \
-; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=SCOP
-
-; RUN: opt %loadPolly -S -polly-use-llvm-names -polly-codegen-ppcg \
-; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=HOST-IR
+  ; RUN: opt %loadPolly -polly-use-llvm-names -polly-scops \
+; RUN: -polly-invariant-load-hoisting -polly-codegen-ppcg \
+; RUN: -polly-acc-dump-code -disable-output \
+; RUN:   < %s | FileCheck %s -check-prefix=CODE
+
+; RUN: opt %loadPolly -polly-use-llvm-names -polly-scops \
+; RUN: -polly-invariant-load-hoisting -polly-codegen-ppcg \
+; RUN: -polly-acc-dump-kernel-ir -disable-output \
+; RUN:   < %s | FileCheck %s -check-prefix=KERNELIR
 
 ; REQUIRES: pollyacc
 
-; SCOP:      Function: f
-; 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, tmp1] -> { Stmt_if_end[i0] -> MemRef_end[0] };
-; SCOP-NEXT:         Execution Context: [tmp, tmp1] -> {  :  }
-; SCOP-NEXT:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
-; SCOP-NEXT:             [tmp, tmp1] -> { Stmt_for_body[i0] -> MemRef_control[0] };
-; SCOP-NEXT:         Execution Context: [tmp, tmp1] -> {  : tmp > 0 }
-; SCOP-NEXT: }
-
-; Check that we generate a correct "always false" branch.
-; HOST-IR:  br i1 false, label %polly.start, label %entry.split.pre_entry_bb
-
-; This test case checks that we generate correct code if PPCGCodeGeneration
-; decides a build is unsuccessful with invariant load hoisting enabled.
-;
-; There is a conditional branch which switches between the original code and
-; the new code. We try to set this conditional branch to branch on false.
-; However, invariant load hoisting changes the structure of the scop, so we
-; need to change the way we *locate* this instruction.
-;
 ;    void f(const int *end, int *arr, const int *control, const int *readarr) {
 ;      for (int i = 0; i < *end; i++) {
 ;        int t = 0;
 ;        if (*control > 3) {
 ;          t += readarr[i];
 ;        }
 ;        arr[i] = t;
 ;      }
 ;    }
-;
+
+; CODE: # kernel0
+; CODE-NEXT: for (int c0 = 0; c0 <= (tmp - 32 * b0 - 1) / 1048576; c0 += 1)
+; CODE-NEXT:   if (tmp >= 32 * b0 + t0 + 1048576 * c0 + 1) {
+; CODE-NEXT:     Stmt_for_body(32 * b0 + t0 + 1048576 * c0);
+; CODE-NEXT:     if (tmp1 >= 4)
+; CODE-NEXT:       Stmt_if_then(32 * b0 + t0 + 1048576 * c0);
+; CODE-NEXT:     Stmt_if_end(32 * b0 + t0 + 1048576 * c0);
+; CODE-NEXT:   }
+
+; KERNELIR: %private_array = alloca i32
 
 target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
 target triple = "i386-apple-macosx10.12.0"
 
 define void @f(i32* %end, i32* %arr, i32* %control, i32* %readarr) {
 entry:
   br label %entry.split
 

test/GPGPU/non-read-only-scalars.ll

 ; CODE-NEXT:   Stmt_bb4(t0);
 ; CODE-NEXT:   Stmt_bb10(t0);
 ; CODE-NEXT: }
 
 ; CODE: # kernel1
 ; CODE-NEXT: Stmt_bb17();
 
 ; CODE: # kernel2
-; CODE-NEXT: for (int c0 = 0; c0 <= 32; c0 += 1) {
-; CODE-NEXT:   Stmt_bb18(c0);
-; CODE-NEXT:   if (c0 <= 31)
-; CODE-NEXT:     Stmt_bb20(c0);
-; CODE-NEXT: }
+; CODE_NEXT: {
+; CODE_NEXT:   read();
+; CODE_NEXT:   for (int c0 = 0; c0 <= 32; c0 += 1) {
+; CODE_NEXT:     Stmt_bb18(c0);
+; CODE_NEXT:     if (c0 <= 31)
+; CODE_NEXT:       Stmt_bb20(c0);
+; CODE_NEXT:   }
+; CODE_NEXT:   write();
+; CODE_NEXT: }
+
 
 ; KERNEL-IR: define ptx_kernel void @FUNC_foo_SCOP_0_KERNEL_1(i8 addrspace(1)* %MemRef_sum_0__phi)
 ; KERNEL-IR:  store float 0.000000e+00, float* %sum.0.phiops
 ; KERNEL-IR:  [[REGA:%.+]] = addrspacecast i8 addrspace(1)* %MemRef_sum_0__phi to float*
 ; KERNEL-IR:  [[REGB:%.+]] = load float, float* %sum.0.phiops
 ; KERNEL-IR:  store float [[REGB]], float* [[REGA]]
 
 ; KERNEL-IR: define ptx_kernel void @FUNC_foo_SCOP_0_KERNEL_2(i8 addrspace(1)* %MemRef_A, i8 addrspace(1)* %MemRef_sum_0__phi, i8 addrspace(1)* %MemRef_sum_0)

test/GPGPU/scalar-writes-in-scop-requires-abort.ll

+; RUN: opt %loadPolly -S -polly-use-llvm-names -polly-scops  \
+; RUN: -polly-acc-dump-code -analyze \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=SCOP
+
+; RUN: opt %loadPolly -S -polly-use-llvm-names -polly-codegen-ppcg \
+; RUN: -polly-acc-dump-code \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=CODE
+
+; RUN: opt %loadPolly -S -polly-use-llvm-names -polly-codegen-ppcg \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=HOST-IR
+
+; REQUIRES: pollyacc
+
+; SCOP:      Invariant Accesses: {
+; SCOP-NEXT:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOP-NEXT:             { Stmt_loop[i0] -> MemRef_p[0] };
+; SCOP-NEXT:         Execution Context: {  :  }
+; SCOP-NEXT: }
+
+; CODE: # kernel0
+; CODE-NEXT: {
+; CODE-NEXT:   if (32 * b0 + t0 <= 1025) {
+; CODE-NEXT:     Stmt_loop(32 * b0 + t0);
+; CODE-NEXT:     write(0);
+; CODE-NEXT:   }
+; CODE-NEXT:   sync0();
+; CODE-NEXT: }
+
+; Check that we generate a correct "always false" branch.
+; HOST-IR:  br i1 false, label %polly.start, label %loop.pre_entry_bb
+
+; This test case checks that we generate correct code if PPCGCodeGeneration
+; decides a build is unsuccessful with invariant load hoisting enabled.
+;
+; There is a conditional branch which switches between the original code and
+; the new code. We try to set this conditional branch to branch on false.
+; However, invariant load hoisting changes the structure of the scop, so we
+; need to change the way we *locate* this instruction.
+
+target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
+target triple = "i386-apple-macosx10.12.0"
+
+define void @foo(float* %A, float* %p) {
+entry:
+  br label %loop
+
+loop:
+  %indvar = phi i64 [0, %entry], [%indvar.next, %loop]
+  %indvar.next = add i64 %indvar, 1
+  %invariant = load float, float* %p
+  %ptr = getelementptr float, float* %A, i64 %indvar
+  store float 42.0, float* %ptr
+  %cmp = icmp sle i64 %indvar, 1024
+  br i1 %cmp, label %loop, label %loop2
+
+loop2:
+  %indvar2 = phi i64 [0, %loop], [%indvar2.next, %loop2]
+  %indvar2f = phi float [%invariant, %loop], [%indvar2f, %loop2]
+  %indvar2.next = add i64 %indvar2, 1
+  store float %indvar2f, float* %A
+  %cmp2 = icmp sle i64 %indvar2, 1024
+  br i1 %cmp2, label %loop2, label %end
+
+end:
+  ret void
+}