1 files changed, 35 insertions, 164 deletions

diff --git a/polly/lib/External/isl/isl_ast_build.c b/polly/lib/External/isl/isl_ast_build.c
index 65ab6d51c3f..c7be0a97b65 100644
--- a/polly/lib/External/isl/isl_ast_build.c
+++ b/polly/lib/External/isl/isl_ast_build.c
@@ -10,6 +10,8 @@
  * B.P. 105 - 78153 Le Chesnay, France
  */
 
+#include <isl/val.h>
+#include <isl/space.h>
 #include <isl/map.h>
 #include <isl/aff.h>
 #include <isl/constraint.h>
@@ -93,7 +95,7 @@ static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
 	__isl_keep isl_ast_build *build)
 {
 	int j;
-	char name[16];
+	char name[23];
 	isl_set *dom = build->domain;
 
 	snprintf(name, sizeof(name), "c%d", i);
@@ -1180,9 +1182,14 @@ __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
 	dim = isl_set_dim(build->domain, isl_dim_set);
 	space = isl_space_drop_dims(space, isl_dim_set,
 				    build->depth, dim - build->depth);
-	for (i = build->depth - 1; i >= 0; --i)
-		if (isl_ast_build_has_affine_value(build, i))
+	for (i = build->depth - 1; i >= 0; --i) {
+		isl_bool affine = isl_ast_build_has_affine_value(build, i);
+
+		if (affine < 0)
+			return isl_space_free(space);
+		if (affine)
 			space = isl_space_drop_dims(space, isl_dim_set, i, 1);
+	}
 
 	return space;
 }
@@ -1254,30 +1261,6 @@ __isl_give isl_id *isl_ast_build_get_iterator_id(
 
 /* Set the stride and offset of the current dimension to the given
  * value and expression.
- *
- * If we had already found a stride before, then the two strides
- * are combined into a single stride.
- *
- * In particular, if the new stride information is of the form
- *
- *	i = f + s (...)
- *
- * and the old stride information is of the form
- *
- *	i = f2 + s2 (...)
- *
- * then we compute the extended gcd of s and s2
- *
- *	a s + b s2 = g,
- *
- * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
- * and the second with t2 = a s1/g.
- * This results in
- *
- *	i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
- *
- * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
- * is the combined stride.
  */
 static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
 	__isl_take isl_val *stride, __isl_take isl_aff *offset)
@@ -1290,25 +1273,6 @@ static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
 
 	pos = build->depth;
 
-	if (isl_ast_build_has_stride(build, pos)) {
-		isl_val *stride2, *a, *b, *g;
-		isl_aff *offset2;
-
-		stride2 = isl_vec_get_element_val(build->strides, pos);
-		g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
-					&a, &b);
-		a = isl_val_mul(a, isl_val_copy(stride));
-		a = isl_val_div(a, isl_val_copy(g));
-		stride2 = isl_val_div(stride2, g);
-		b = isl_val_mul(b, isl_val_copy(stride2));
-		stride = isl_val_mul(stride, stride2);
-
-		offset2 = isl_multi_aff_get_aff(build->offsets, pos);
-		offset2 = isl_aff_scale_val(offset2, a);
-		offset = isl_aff_scale_val(offset, b);
-		offset = isl_aff_add(offset, offset2);
-	}
-
 	build->strides = isl_vec_set_element_val(build->strides, pos, stride);
 	build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
 	if (!build->strides || !build->offsets)
@@ -1424,134 +1388,44 @@ __isl_give isl_ast_build *isl_ast_build_include_stride(
 	return build;
 }
 
-/* Information used inside detect_stride.
- *
- * "build" may be updated by detect_stride to include stride information.
- * "pos" is equal to build->depth.
- */
-struct isl_detect_stride_data {
-	isl_ast_build *build;
-	int pos;
-};
-
-/* Check if constraint "c" imposes any stride on dimension data->pos
- * and, if so, update the stride information in data->build.
- *
- * In order to impose a stride on the dimension, "c" needs to be an equality
- * and it needs to involve the dimension.  Note that "c" may also be
- * a div constraint and thus an inequality that we cannot use.
- *
- * Let c be of the form
- *
- *	h(p) + g * v * i + g * stride * f(alpha) = 0
- *
- * with h(p) an expression in terms of the parameters and outer dimensions
- * and f(alpha) an expression in terms of the existentially quantified
- * variables.  Note that the inner dimensions have been eliminated so
- * they do not appear in "c".
- *
- * If "stride" is not zero and not one, then it represents a non-trivial stride
- * on "i".  We compute a and b such that
- *
- *	a v + b stride = 1
- *
- * We have
- *
- *	g v i = -h(p) + g stride f(alpha)
- *
- *	a g v i = -a h(p) + g stride f(alpha)
- *
- *	a g v i + b g stride i = -a h(p) + g stride * (...)
- *
- *	g i = -a h(p) + g stride * (...)
- *
- *	i = -a h(p)/g + stride * (...)
- *
- * The expression "-a h(p)/g" can therefore be used as offset.
- */
-static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
-{
-	struct isl_detect_stride_data *data = user;
-	int i, n_div;
-	isl_ctx *ctx;
-	isl_val *v, *stride, *m;
-
-	if (!isl_constraint_is_equality(c) ||
-	    !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
-		isl_constraint_free(c);
-		return isl_stat_ok;
-	}
-
-	ctx = isl_constraint_get_ctx(c);
-	stride = isl_val_zero(ctx);
-	n_div = isl_constraint_dim(c, isl_dim_div);
-	for (i = 0; i < n_div; ++i) {
-		v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
-		stride = isl_val_gcd(stride, v);
-	}
-
-	v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
-	m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
-	stride = isl_val_div(stride, isl_val_copy(m));
-	v = isl_val_div(v, isl_val_copy(m));
-
-	if (!isl_val_is_zero(stride) && !isl_val_is_one(stride)) {
-		isl_aff *aff;
-		isl_val *gcd, *a, *b;
-
-		gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
-		isl_val_free(gcd);
-		isl_val_free(b);
-
-		aff = isl_constraint_get_aff(c);
-		for (i = 0; i < n_div; ++i)
-			aff = isl_aff_set_coefficient_si(aff,
-							 isl_dim_div, i, 0);
-		aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
-		a = isl_val_neg(a);
-		aff = isl_aff_scale_val(aff, a);
-		aff = isl_aff_scale_down_val(aff, m);
-		data->build = set_stride(data->build, stride, aff);
-	} else {
-		isl_val_free(stride);
-		isl_val_free(m);
-		isl_val_free(v);
-	}
-
-	isl_constraint_free(c);
-	return isl_stat_ok;
-}
-
 /* Check if the constraints in "set" imply any stride on the current
  * dimension and, if so, record the stride information in "build"
  * and return the updated "build".
  *
- * We compute the affine hull and then check if any of the constraints
- * in the hull imposes any stride on the current dimension.
- *
  * We assume that inner dimensions have been eliminated from "set"
  * by the caller.  This is needed because the common stride
  * may be imposed by different inner dimensions on different parts of
  * the domain.
+ * The assumption ensures that the lower bound does not depend
+ * on inner dimensions.
  */
 __isl_give isl_ast_build *isl_ast_build_detect_strides(
 	__isl_take isl_ast_build *build, __isl_take isl_set *set)
 {
-	isl_basic_set *hull;
-	struct isl_detect_stride_data data;
+	int pos;
+	isl_bool no_stride;
+	isl_val *stride;
+	isl_aff *offset;
+	isl_stride_info *si;
 
 	if (!build)
 		goto error;
 
-	data.build = build;
-	data.pos = isl_ast_build_get_depth(build);
-	hull = isl_set_affine_hull(set);
-
-	if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
-		data.build = isl_ast_build_free(data.build);
+	pos = isl_ast_build_get_depth(build);
+	si = isl_set_get_stride_info(set, pos);
+	stride = isl_stride_info_get_stride(si);
+	offset = isl_stride_info_get_offset(si);
+	isl_stride_info_free(si);
+	isl_set_free(set);
 
-	isl_basic_set_free(hull);
-	return data.build;
+	no_stride = isl_val_is_one(stride);
+	if (no_stride >= 0 && !no_stride)
+		return set_stride(build, stride, offset);
+	isl_val_free(stride);
+	isl_aff_free(offset);
+	if (no_stride < 0)
+		return isl_ast_build_free(build);
+	return build;
 error:
 	isl_set_free(set);
 	return NULL;
@@ -2088,23 +1962,20 @@ __isl_give isl_aff *isl_ast_build_get_offset(
  * Otherwise, it is set to the requested expression in terms of
  * outer dimensions and parameters.
  */
-int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
+isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
 	int pos)
 {
 	isl_aff *aff;
-	int involves;
+	isl_bool involves;
 
 	if (!build)
-		return -1;
+		return isl_bool_error;
 
 	aff = isl_multi_aff_get_aff(build->values, pos);
 	involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
 	isl_aff_free(aff);
 
-	if (involves < 0)
-		return -1;
-
-	return !involves;
+	return isl_bool_not(involves);
 }
 
 /* Plug in the known values (fixed affine expressions in terms of