[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 ↗

(On Diff #52973)

Removing this causes a lot more changes in unit tests.

test/ScopInfo/multidim_fixedsize_multi_offset.ll

12 ↗

(On Diff #52973)

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 ↗

(On Diff #52973)

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 ↗

(On Diff #52973)

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

[Meinersbur]

test/ScopInfo/multidim_fixedsize_multi_offset.ll

12 ↗

(On Diff #52973)

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 ↗

(On Diff #52973)

constant length -> constant size

338 ↗

(On Diff #52973)

indicies -> indices

343 ↗

(On Diff #52973)

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 ↗

(On Diff #52973)

through

test/ScopInfo/process_added_dimensions.ll

3–4 ↗

(On Diff #52973)

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

polly/trunk/include/polly/ScopInfo.h

private:
   /// @brief Assemble the access relation from all availbale information.
   ///
   /// In particular, used the information passes in the constructor and the
   /// parent ScopStmt set by setStatment().
   ///
   /// @param SAI Info object for the accessed array.
   void buildAccessRelation(const ScopArrayInfo *SAI);
 
+  /// @brief Carry index overflows of dimensions with constant size to the next
+  ///        higher dimension.
+  ///
+  /// For dimensions that have constant size, modulo the index by the size and
+  /// add up the carry (floored division) to the next higher dimension. This is
+  /// how overflow is defined in row-major order.
+  /// It happens e.g. when ScalarEvolution computes the offset to the base
+  /// pointer and would algebraically sum up all lower dimensions' indices of
+  /// constant size.
+  ///
+  /// Example:
+  ///   float (*A)[4];
+  ///   A[1][6] -> A[2][2]
+  void wrapConstantDimensions();
+
 public:
   /// @brief Create a new MemoryAccess.
   ///
   /// @param Stmt       The parent statement.
   /// @param AccessInst The instruction doing the access.
   /// @param BaseAddr   The accessed array's address.
   /// @param ElemType   The type of the accessed array elements.
   /// @param AccType    Whether read or write access.

polly/trunk/lib/Analysis/ScopInfo.cpp

 
 const ScopArrayInfo *ScopArrayInfo::getFromId(isl_id *Id) {
   void *User = isl_id_get_user(Id);
   const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
   isl_id_free(Id);
   return SAI;
 }
 
+void MemoryAccess::wrapConstantDimensions() {
+  auto *SAI = getScopArrayInfo();
+  auto *ArraySpace = SAI->getSpace();
+  auto *Ctx = isl_space_get_ctx(ArraySpace);
+  unsigned DimsArray = SAI->getNumberOfDimensions();
+
+  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(ArraySpace);
+
+  // Begin with last dimension, to iteratively carry into higher dimensions.
+  for (int i = DimsArray - 1; i > 0; i--) {
+    auto *DimSize = SAI->getDimensionSize(i);
+    auto *DimSizeCst = dyn_cast<SCEVConstant>(DimSize);
+
+    // This transformation is not applicable to dimensions with dynamic size.
+    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);
+
+    // Compute: index % size
+    // Modulo must apply in the divide of the previous iteration, if any.
+    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));
+
+    // Compute: floor(index / size)
+    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));
+
+    // Apply Modulo and Divide.
+    DivModAff = isl_multi_aff_set_aff(DivModAff, i, Modulo);
+    DivModAff = isl_multi_aff_set_aff(DivModAff, i - 1, Divide);
+  }
+
+  // Apply all modulo/divides on the accesses.
+  AccessRelation =
+      isl_map_apply_range(AccessRelation, isl_map_from_multi_aff(DivModAff));
+  AccessRelation = isl_map_detect_equalities(AccessRelation);
+  isl_local_space_free(LArraySpace);
+}
+
 void MemoryAccess::updateDimensionality() {
   auto *SAI = getScopArrayInfo();
   auto *ArraySpace = SAI->getSpace();
   auto *AccessSpace = isl_space_range(isl_map_get_space(AccessRelation));
   auto *Ctx = isl_space_get_ctx(AccessSpace);
 
   auto DimsArray = isl_space_dim(ArraySpace, isl_dim_set);
   auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set);
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);
   }
 
+  // We currently do this only if we added at least one dimension, which means
+  // some dimension's indices have not been specified, an indicator that some
+  // index values have been added together.
+  // TODO: Investigate general usefulness; Effect on unit tests is to make index
+  // expressions more complicated.
+  if (DimsMissing)
+    wrapConstantDimensions();
+
   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

polly/trunk/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 through 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

polly/trunk/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