* 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>
/* 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)
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)
{
isl_aff *aff;
isl_set *set;
- isl_int stride;
+ isl_val *stride;
int pos;
if (!build)
if (!isl_ast_build_has_stride(build, pos))
return isl_set_universe(isl_ast_build_get_space(build, 1));
- isl_int_init(stride);
-
- isl_ast_build_get_stride(build, pos, &stride);
+ stride = isl_ast_build_get_stride(build, pos);
aff = isl_ast_build_get_offset(build, pos);
aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
- aff = isl_aff_mod(aff, stride);
+ aff = isl_aff_mod_val(aff, stride);
set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
- isl_int_clear(stride);
-
return set;
}
isl_multi_aff *ma;
int pos;
isl_aff *aff, *offset;
- isl_int stride;
+ isl_val *stride;
if (!build)
return NULL;
if (!isl_ast_build_has_stride(build, pos))
return ma;
- isl_int_init(stride);
offset = isl_ast_build_get_offset(build, pos);
- isl_ast_build_get_stride(build, pos, &stride);
+ stride = isl_ast_build_get_stride(build, pos);
aff = isl_multi_aff_get_aff(ma, pos);
- aff = isl_aff_scale(aff, stride);
+ aff = isl_aff_scale_val(aff, stride);
aff = isl_aff_add(aff, offset);
ma = isl_multi_aff_set_aff(ma, pos, aff);
- isl_int_clear(stride);
return ma;
}
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.
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)
* We therefore only need to update stride, offset and the options.
*/
__isl_give isl_ast_build *isl_ast_build_scale_down(
- __isl_take isl_ast_build *build, isl_int m,
+ __isl_take isl_ast_build *build, __isl_take isl_val *m,
__isl_take isl_union_map *umap)
{
isl_aff *aff;
- isl_int v;
+ isl_val *v;
int depth;
build = isl_ast_build_cow(build);
- if (!build || !umap)
+ if (!build || !umap || !m)
goto error;
depth = build->depth;
- isl_int_init(v);
- if (isl_vec_get_element(build->strides, depth, &v) < 0)
- build->strides = isl_vec_free(build->strides);
- isl_int_divexact(v, v, m);
- build->strides = isl_vec_set_element(build->strides, depth, v);
- isl_int_clear(v);
+ v = isl_vec_get_element_val(build->strides, depth);
+ v = isl_val_div(v, isl_val_copy(m));
+ build->strides = isl_vec_set_element_val(build->strides, depth, v);
aff = isl_multi_aff_get_aff(build->offsets, depth);
- aff = isl_aff_scale_down(aff, m);
+ aff = isl_aff_scale_down_val(aff, m);
build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
build->options = isl_union_map_apply_domain(build->options, umap);
if (!build->strides || !build->offsets || !build->options)
return build;
error:
+ isl_val_free(m);
isl_union_map_free(umap);
return isl_ast_build_free(build);
}
*
* with a an integer, return s through *stride.
*/
-int isl_ast_build_get_stride(__isl_keep isl_ast_build *build, int pos,
- isl_int *stride)
+__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
+ int pos)
{
if (!build)
- return -1;
-
- isl_vec_get_element(build->strides, pos, stride);
+ return NULL;
- return 0;
+ return isl_vec_get_element_val(build->strides, pos);
}
/* Given that the dimension at position "pos" takes on values