X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_ast_build.c;h=7bf8610299d099f12312e3074a54bf6103b21ca8;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=9c0894b06b74f7b9af9dab73456707934d7d1b54;hpb=d1fb914083bff444a77d4d8157f3948c1b3e7d57;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_ast_build.c b/isl_ast_build.c
index 9c0894b..7bf8610 100644
--- a/isl_ast_build.c
+++ b/isl_ast_build.c
@@ -7,6 +7,7 @@
  * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  */
 
+#include <isl_int.h>
 #include <isl/map.h>
 #include <isl/aff.h>
 #include <isl/map.h>
@@ -1017,6 +1018,30 @@ __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_int stride, __isl_take isl_aff *offset)
@@ -1028,6 +1053,35 @@ static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
 		goto error;
 
 	pos = build->depth;
+
+	if (isl_ast_build_has_stride(build, pos)) {
+		isl_int stride2, a, b, g;
+		isl_aff *offset2;
+
+		isl_int_init(stride2);
+		isl_int_init(a);
+		isl_int_init(b);
+		isl_int_init(g);
+
+		isl_vec_get_element(build->strides, pos, &stride2);
+		isl_int_gcdext(g, a, b, stride, stride2);
+		isl_int_mul(a, a, stride);
+		isl_int_divexact(a, a, g);
+		isl_int_divexact(stride2, stride2, g);
+		isl_int_mul(b, b, stride2);
+		isl_int_mul(stride, stride, stride2);
+
+		offset2 = isl_multi_aff_get_aff(build->offsets, pos);
+		offset2 = isl_aff_scale(offset2, a);
+		offset = isl_aff_scale(offset, b);
+		offset = isl_aff_add(offset, offset2);
+
+		isl_int_clear(stride2);
+		isl_int_clear(a);
+		isl_int_clear(b);
+		isl_int_clear(g);
+	}
+
 	build->strides = isl_vec_set_element(build->strides, pos, stride);
 	build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
 	if (!build->strides || !build->offsets)
@@ -1148,51 +1202,6 @@ __isl_give isl_ast_build *isl_ast_build_include_stride(
 	return build;
 }
 
-/* Compute x, y and g such that g = gcd(a,b) and a*x+b*y = g */
-static void euclid(isl_int a, isl_int b, isl_int *x, isl_int *y, isl_int *g)
-{
-	isl_int c, d, e, f, tmp;
-
-	isl_int_init(c);
-	isl_int_init(d);
-	isl_int_init(e);
-	isl_int_init(f);
-	isl_int_init(tmp);
-	isl_int_abs(c, a);
-	isl_int_abs(d, b);
-	isl_int_set_si(e, 1);
-	isl_int_set_si(f, 0);
-	while (isl_int_is_pos(d)) {
-		isl_int_tdiv_q(tmp, c, d);
-		isl_int_mul(tmp, tmp, f);
-		isl_int_sub(e, e, tmp);
-		isl_int_tdiv_q(tmp, c, d);
-		isl_int_mul(tmp, tmp, d);
-		isl_int_sub(c, c, tmp);
-		isl_int_swap(c, d);
-		isl_int_swap(e, f);
-	}
-	isl_int_set(*g, c);
-	if (isl_int_is_zero(a))
-		isl_int_set_si(*x, 0);
-	else if (isl_int_is_pos(a))
-		isl_int_set(*x, e);
-	else
-		isl_int_neg(*x, e);
-	if (isl_int_is_zero(b))
-		isl_int_set_si(*y, 0);
-	else {
-		isl_int_mul(tmp, a, *x);
-		isl_int_sub(tmp, c, tmp);
-		isl_int_divexact(*y, tmp, b);
-	}
-	isl_int_clear(c);
-	isl_int_clear(d);
-	isl_int_clear(e);
-	isl_int_clear(f);
-	isl_int_clear(tmp);
-}
-
 /* Information used inside detect_stride.
  *
  * "build" may be updated by detect_stride to include stride information.
@@ -1272,7 +1281,7 @@ static int detect_stride(__isl_take isl_constraint *c, void *user)
 	if (!isl_int_is_zero(stride) && !isl_int_is_one(stride)) {
 		isl_aff *aff;
 
-		euclid(v, stride, &a, &b, &gcd);
+		isl_int_gcdext(gcd, a, b, v, stride);
 
 		aff = isl_constraint_get_aff(c);
 		for (i = 0; i < n_div; ++i)