[Polly] [PPCGCodeGeneration] Handle 1-d pointers to scalars in array size.

[bollu]

Summary

• We try to multiply "offset"s together.
• Case when array is 1D and offset is 0 is not handled.
• Detect this case and return the size of the underlying object.
• Feels like a hack. @grosser: This is a hack, right?

[grosser]

Yes, this is a total hack. The underlying bugs are:

1. Scop::getAccessesOfType does not collect access relations on invariant accesses (which causes us to derive an empty "extent"

If we fix this, I expect this test case to work.

Now, in general we can likely not avoid zero size allocations (in rare corner cases). We may at some point allow them, but for now it is a good assertion that fires in case of such situations. We should see if Sanjay's problems are also resolved after fixing 1).

lib/CodeGen/PPCGCodeGeneration.cpp

740

Unrelated.

[grosser]

I mark this as requestion changes. Siddharth, can you check if my comment leads to a cleaner solution?

[bollu]

@grosser I'm not sure how to build up the correct access union map.

incorrect-version-of-get-accesses.cpp

__isl_give isl_union_map *
Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {
  isl_union_map *Accesses = isl_union_map_empty(getParamSpace());

  const auto shouldConsiderInvEquivClass =
      [&Predicate](const InvariantEquivClassTy &InvEquivClass) -> bool {
    for (MemoryAccess *MA : InvEquivClass.InvariantAccesses) {
      if (!Predicate(*MA))
        return false;
    }
    return true;
  };

  for (InvariantEquivClassTy &InvEquivClass : getInvariantAccesses()) {
    if (!shouldConsiderInvEquivClass(InvEquivClass))
      continue;

    for (MemoryAccess *MA : InvEquivClass.InvariantAccesses) {
      isl_map *AccessDomain = MA->getAccessRelation().release();
      // This is incorrect, naturally. We don't limit this access relation's domain.
      Accesses = isl_union_map_add_map(Accesses, AccessDomain);
    }
  }

  for (ScopStmt &Stmt : *this) {
    for (MemoryAccess *MA : Stmt) {
      if (!Predicate(*MA))
        continue;

      isl_set *Domain = Stmt.getDomain();
      isl_map *AccessDomain = MA->getAccessRelation().release();
      AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
      Accesses = isl_union_map_add_map(Accesses, AccessDomain);
    }
  }
  return isl_union_map_coalesce(Accesses);
}

However, the InvariantEquivClassTy doesn't seem to hold information on a per-memory access basis as to what the valid context is.
So, I'm not sure what to do.

[singam-sanjay]

@grosser How does solving 1. relate to D35630 ?

@bollu Does this patch help codegenerate cases where the SCOP's constants are essentially scalars but are considered arrays with zero elements ?

[grosser]

In D35721#818410, @singam-sanjay wrote:

@grosser How does solving 1. relate to D35630 ?

Not at all. I was referring to https://bugs.llvm.org/show_bug.cgi?id=33324

@bollu Does this patch help codegenerate cases where the SCOP's constants are essentially scalars but are considered arrays with zero elements ?

[bollu]

Abandoned in favour of D35795 which actually solves the problem.

lib/CodeGen/PPCGCodeGeneration.cpp

void GPUNodeBuilder::allocateDeviceArrays() {
   for (int i = 0; i < Prog->n_array; ++i) {
     gpu_array_info *Array = &Prog->array[i];
     auto *ScopArray = (ScopArrayInfo *)Array->user;
     std::string DevArrayName("p_dev_array_");
     DevArrayName.append(Array->name);
 
     Value *ArraySize = getArraySize(Array);
     Value *Offset = getArrayOffset(Array);
+
     if (Offset)
       ArraySize = Builder.CreateSub(
           ArraySize,
           Builder.CreateMul(Offset,
                             Builder.getInt64(ScopArray->getElemSizeInBytes())));
     Value *DevArray = createCallAllocateMemoryForDevice(ArraySize);
     DevArray->setName(DevArrayName);
     DeviceAllocations[ScopArray] = DevArray;
   }

 /// Check if one string is a prefix of another.
 ///
 /// @param String The string in which to look for the prefix.
 /// @param Prefix The prefix to look for.
 static bool isPrefix(std::string String, std::string Prefix) {
   return String.find(Prefix) == 0;
 }
 
+static bool isPwAffZero(__isl_keep isl_pw_aff *aff) {
+  isl_set *NonZeroSet = isl_pw_aff_non_zero_set(isl_pw_aff_copy(aff));
+  bool ZeroEverywhere = isl_set_is_empty(NonZeroSet);
+  isl_set_free(NonZeroSet);
+  // a pw_aff that is zero at one point and is a constant is necessarily zero
+  // everywhere.
+  return ZeroEverywhere;
+}
+
 Value *GPUNodeBuilder::getArraySize(gpu_array_info *Array) {
   isl_ast_build *Build = isl_ast_build_from_context(S.getContext());
   Value *ArraySize = ConstantInt::get(Builder.getInt64Ty(), Array->size);
 
   if (!gpu_array_is_scalar(Array)) {
     auto OffsetDimZero = isl_multi_pw_aff_get_pw_aff(Array->bound, 0);
-    isl_ast_expr *Res = isl_ast_build_expr_from_pw_aff(Build, OffsetDimZero);
 
+    // If the array is scalar, then it will be of the form:
+    // Number of dimensions: 1
+    // 0th dimension: [params] -> { [(0)] }
+    // In that case, just return the array size.
+    if (Array->n_index == 1 && isPwAffZero(OffsetDimZero)) {
+      isl_pw_aff_free(OffsetDimZero);
+      isl_ast_build_free(Build);
+      return ArraySize;
+    }
+
+    isl_ast_expr *Res = isl_ast_build_expr_from_pw_aff(Build, OffsetDimZero);
     for (unsigned int i = 1; i < Array->n_index; i++) {
       isl_pw_aff *Bound_I = isl_multi_pw_aff_get_pw_aff(Array->bound, i);
       isl_ast_expr *Expr = isl_ast_build_expr_from_pw_aff(Build, Bound_I);
       Res = isl_ast_expr_mul(Res, Expr);
     }
 
     Value *NumElements = ExprBuilder.create(Res);
     if (NumElements->getType() != ArraySize->getType())

test/GPGPU/size-of-pointer-to-scalar.ll

+; RUN: opt %loadPolly -polly-codegen-ppcg -polly-invariant-load-hoisting \
+; RUN: -S < %s | \
+; RUN: FileCheck -check-prefix=HOST-IR %s
+
+; REQUIRES: pollyacc
+
+; HOST-IR:  %p_dev_array_MemRef_begin = call i8* @polly_allocateMemoryForDevice(i64 4)
+; HOST-IR:  %p_dev_array_MemRef_end = call i8* @polly_allocateMemoryForDevice(i64 4)
+
+; Check that we do derive the correct size for `begin`, `end`.
+; There are 1 dimensional arrays with 1 element / pointers to scalars.
+
+; void checkScalarSize(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
+}
+