Allow overflow of indices with constant dim-sizes.
Allow overflow of indices into the next higher dimension if it has
constant size. 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.
Differential Revision: http://reviews.llvm.org/D18878
llvm-svn: 265942
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index d0e7187..ed9479d 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -289,6 +289,58 @@
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();
@@ -331,6 +383,14 @@
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);