[Polly] Allow overflow of indices with constant dimensions size

[Meinersbur]

Summary

Allow overflow of indices into the next higher dimension if it has constant length. E.g.

float A[32][2];
((float*)A)[5];

is effectively the same as

A[2][1];

This can happen since r265379 as a side effect if ScopDetection recognizes an access as affine, but ScopInfo rejects the GetElementPtr.

[Meinersbur]

Not meant as fix for PR27195. It does not fix the vec-delin.ll test case. The uploaded test case delinearization-fixed-size.ll seems unrelated to the first one. Tobias already partially fixed that latter in r265379.

lib/Analysis/ScopInfo.cpp

343

Removing this causes a lot more changes in unit tests.

test/ScopInfo/multidim_fixedsize_multi_offset.ll

12

The scop was only rejected because the computed MemoryAccess was

{ [i0] -> MemRef_A[0, 2 + 2i0] }

which is unconditionally out of bounds.

test/ScopInfo/process_added_dimensions.ll

3–4

The unit test is accepted and I don't find anything wrong. Can somebody double-check?

Especially because there is no hoisted load, but MemRef_call[5, 5, 0] is the correct access (instead of MemRef_call[0, 0, 2240])

38

Stmt_for_cond40_preheader_5 would disappear without this change as %.pre160 is otherwise unused.

[Meinersbur]

test/ScopInfo/multidim_fixedsize_multi_offset.ll

12

Just to add that this is not wrong; The out of bounds conditions are added to the RTCs. That is, even if the computed linear are not completely out of bounds, only the executions where it is within the last dimension' bounds run the optimized version.

That is, r265379 is not only a 'partial fix', but a complete one; This patch only extents the context so more executions can run the optimized version.

[grosser]

Hi Michael,

very nice change. I just have some minor comments.

Best,
Tobias

lib/Analysis/ScopInfo.cpp

332

constant length -> constant size

338

indicies -> indices

343

This is a large and mostly independent piece of code. It would probably make sense to put this into its own function.

test/ScopInfo/multidim_fixedsize_multi_offset.ll

28

through

test/ScopInfo/process_added_dimensions.ll

3–4

Looks good to me.

[Meinersbur]

Apply tobias' hints; add more comments.

Will try with LNT before committing.

[• zinob]

What is the assume context? can we check them in the testcase?

[Meinersbur]

Contexts added if r266323.

[• zinob]

looks good to me

lib/Analysis/ScopInfo.cpp

void MemoryAccess::updateDimensionality() {
   // obvious again. If the base pointer was accessed with offsets not divisible
   // by the accesses element size, we will have choosen a smaller ArrayElemSize
   // that divides the offsets of all accesses to this base pointer.
   if (DimsAccess == 1) {
     isl_val *V = isl_val_int_from_si(Ctx, ArrayElemSize);
     AccessRelation = isl_map_floordiv_val(AccessRelation, V);
   }
 
+  // For dimensions that have constant length, modulo the index by the length
+  // and add up the carry to the next higher dimension. This is how overflow is
+  // defined in row-major order. This can happen when ScalarEvolution computes
+  // the offset to the base pointer and would algebraically sum up all lower
+  // dimensions' indices of constant length.
+  // We currently do this only if we added at least one dimension, which means
+  // some dimension's indicies have not been specified, an indicator that some
+  // index values have been added together.
+  auto *DivModAff = isl_multi_aff_identity(isl_space_map_from_domain_and_range(
+      isl_space_copy(ArraySpace), isl_space_copy(ArraySpace)));
+  auto *LArraySpace = isl_local_space_from_space(isl_space_copy(ArraySpace));
+  if (DimsMissing)
+    for (int i = DimsArray - 1; i > 0; i--) {
+      auto *DimSize = SAI->getDimensionSize(i);
+      auto *DimSizeCst = dyn_cast<SCEVConstant>(DimSize);
+      if (!DimSizeCst)
+        continue;
+
+      auto *DimSizeVal = isl_valFromAPInt(Ctx, DimSizeCst->getAPInt(), false);
+      auto *Var = isl_aff_var_on_domain(isl_local_space_copy(LArraySpace),
+                                        isl_dim_set, i);
+      auto *PrevVar = isl_aff_var_on_domain(isl_local_space_copy(LArraySpace),
+                                            isl_dim_set, i - 1);
+
+      auto *Modulo = isl_aff_copy(Var);
+      Modulo = isl_aff_mod_val(Modulo, isl_val_copy(DimSizeVal));
+      Modulo =
+          isl_aff_pullback_multi_aff(Modulo, isl_multi_aff_copy(DivModAff));
+
+      auto *Divide = Var;
+      Divide = isl_aff_div(
+          Divide,
+          isl_aff_val_on_domain(isl_local_space_copy(LArraySpace), DimSizeVal));
+      Divide = isl_aff_floor(Divide);
+      Divide = isl_aff_add(Divide, PrevVar);
+      Divide =
+          isl_aff_pullback_multi_aff(Divide, isl_multi_aff_copy(DivModAff));
+
+      DivModAff = isl_multi_aff_set_aff(DivModAff, i, Modulo);
+      DivModAff = isl_multi_aff_set_aff(DivModAff, i - 1, Divide);
+    }
+  AccessRelation =
+      isl_map_apply_range(AccessRelation, isl_map_from_multi_aff(DivModAff));
+  AccessRelation = isl_map_detect_equalities(AccessRelation);
+  isl_local_space_free(LArraySpace);
+
   if (!isAffine())
     computeBoundsOnAccessRelation(ArrayElemSize);
 
   // Introduce multi-element accesses in case the type loaded by this memory
   // access is larger than the canonical element type of the array.
   //
   // An access ((float *)A)[i] to an array char *A is modeled as
   // {[i] -> A[o] : 4 i <= o <= 4 i + 3

test/ScopInfo/multidim_fixedsize_multi_offset.ll

-; RUN: opt %loadPolly -polly-detect -analyze < %s | FileCheck %s -check-prefix=DETECT
 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ;
-; DETECT: Valid Region for Scop: for.cond => for.end
-; CHECK-NOT: Region: %for.cond---%for.end
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_for_body
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             { Stmt_for_body[i0] : 0 <= i0 <= 99 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             { Stmt_for_body[i0] -> [i0] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: +] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_for_body[i0] -> MemRef_A[i0, 0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: +] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_for_body[i0] -> MemRef_A[i0, 0] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: +] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_for_body[i0] -> MemRef_A[1 + i0, 0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: +] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_for_body[i0] -> MemRef_A[1 + i0, 0] };
+; CHECK-NEXT: }
 ;
 ;    void f(int A[][2]) {
 ;      int(*B)[2] = &A[0][0];
 ;      int(*C)[2] = &A[1][0];
 ;      for (int i = 0; i < 100; i++) {
 ;        B[i][0]++;
 ;        C[i][0]++;
 ;      }
 ;    }
 ;
-; This test case makes sure we do not miss parts of the array subscript
-; functions, which we previously did by only considering the first of a chain
-; of GEP instructions. Today, we detect this situation and do not delinearize
-; the relevant memory access. In the future, we may want to detect this
-; pattern and combine multiple GEP functions together.
+; Verify that the additional offset to A by accessing it though C is taken into
+; account.
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f([2 x i32]* %A) {
 entry:
   %arrayidx3 = getelementptr inbounds [2 x i32], [2 x i32]* %A, i64 1, i64 0
   %tmp = bitcast i32* %arrayidx3 to [2 x i32]*
   br label %for.cond

test/ScopInfo/process_added_dimensions.ll

-; RUN: opt %loadPolly -polly-detect -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 
-; This test case produces the following memory access which we try hoist:
-; { Stmt_for_cond40_preheader_5[i0] -> MemRef_call[0, 0, 2240] }. However, it
-; accesses an array of size "i32 MemRef_call[*][6][64]".  That is why we
-; should turn the whole SCoP into an invalid SCoP using corresponding bounds
-; checks. Otherwise, we derive the incorrect access.
-
-; CHECK: Valid Region for Scop: for.cond40.preheader.4 => for.end76
-; CHECK-NOT:     Region: %for.cond40.preheader.4---%for.end76
+; CHECK:      Invariant Accesses: {
+; CHECK-NEXT: }
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_for_cond40_preheader_4
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             { Stmt_for_cond40_preheader_4[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             { Stmt_for_cond40_preheader_4[i0] -> [i0, 0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_for_cond40_preheader_4[i0] -> MemRef_call[5, 5, 0] };
+; CHECK-NEXT:     Stmt_for_cond40_preheader_5
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             { Stmt_for_cond40_preheader_5[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             { Stmt_for_cond40_preheader_5[i0] -> [i0, 1] };
+; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             { Stmt_for_cond40_preheader_5[i0] -> MemRef_call[5, 5, 0] };
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             { Stmt_for_cond40_preheader_5[i0] -> MemRef__pre160[] };
+; CHECK-NEXT: }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare noalias i8* @malloc()
 
-define void @main() {
+define i32 @main() {
 entry:
   %call = tail call noalias i8* @malloc()
   %0 = bitcast i8* %call to [6 x [6 x [64 x i32]]]*
   %arrayidx51.5.phi.trans.insert = getelementptr inbounds i8, i8* %call, i64 8960
   %1 = bitcast i8* %arrayidx51.5.phi.trans.insert to i32*
   br label %for.cond40.preheader.4
 
 for.end76:                                        ; preds = %for.inc71.5
-  ret void
+  ret i32 %.pre160
 
 for.cond40.preheader.4:                           ; preds = %for.inc71.5, %entry
   %t.0131 = phi i32 [ 0, %entry ], [ %inc75, %for.inc71.5 ]
   %indvars.iv.next135 = add nuw nsw i64 0, 1
   %2 = trunc i64 %indvars.iv.next135 to i32
   %indvars.iv.next = add nuw nsw i64 0, 1
   %exitcond = icmp eq i64 %indvars.iv.next, 64
   %exitcond137 = icmp eq i32 %2, 6