isl_vec *strides;
build = isl_ast_build_cow(build);
- if (!build)
+ if (!build || !build->domain)
goto error;
ctx = isl_ast_build_get_ctx(build);
return isl_ast_build_free(build);
}
+/* Return an isl_id called "c%d", with "%d" set to "i".
+ * If an isl_id with such a name already appears among the parameters
+ * in build->domain, then adjust the name to "c%d_%d".
+ */
+static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
+ __isl_keep isl_ast_build *build)
+{
+ int j;
+ char name[16];
+ isl_set *dom = build->domain;
+
+ snprintf(name, sizeof(name), "c%d", i);
+ j = 0;
+ while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
+ snprintf(name, sizeof(name), "c%d_%d", i, j++);
+ return isl_id_alloc(ctx, name, NULL);
+}
+
/* Create an isl_ast_build with "set" as domain.
*
* The input set is usually a parameter domain, but we currently allow it to
build->depth = n;
build->iterators = isl_id_list_alloc(ctx, n);
for (i = 0; i < n; ++i) {
- isl_id *id = isl_set_get_dim_id(set, isl_dim_set, i);
+ isl_id *id;
+ if (isl_set_has_dim_id(set, isl_dim_set, i))
+ id = isl_set_get_dim_id(set, isl_dim_set, i);
+ else
+ id = generate_name(ctx, i, build);
build->iterators = isl_id_list_add(build->iterators, id);
}
space = isl_set_get_space(set);
dup->strides = isl_vec_copy(build->strides);
dup->offsets = isl_multi_aff_copy(build->offsets);
dup->executed = isl_union_map_copy(build->executed);
+ dup->single_valued = build->single_valued;
dup->options = isl_union_map_copy(build->options);
dup->at_each_domain = build->at_each_domain;
dup->at_each_domain_user = build->at_each_domain_user;
+ dup->before_each_for = build->before_each_for;
+ dup->before_each_for_user = build->before_each_for_user;
+ dup->after_each_for = build->after_each_for;
+ dup->after_each_for_user = build->after_each_for_user;
dup->create_leaf = build->create_leaf;
dup->create_leaf_user = build->create_leaf_user;
return build;
}
+/* Set the "before_each_for" callback of "build" to "fn".
+ */
+__isl_give isl_ast_build *isl_ast_build_set_before_each_for(
+ __isl_take isl_ast_build *build,
+ __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
+ void *user), void *user)
+{
+ build = isl_ast_build_cow(build);
+
+ if (!build)
+ return NULL;
+
+ build->before_each_for = fn;
+ build->before_each_for_user = user;
+
+ return build;
+}
+
+/* Set the "after_each_for" callback of "build" to "fn".
+ */
+__isl_give isl_ast_build *isl_ast_build_set_after_each_for(
+ __isl_take isl_ast_build *build,
+ __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
+ __isl_keep isl_ast_build *build, void *user), void *user)
+{
+ build = isl_ast_build_cow(build);
+
+ if (!build)
+ return NULL;
+
+ build->after_each_for = fn;
+ build->after_each_for_user = user;
+
+ return build;
+}
+
/* Set the "create_leaf" callback of "build" to "fn".
*/
__isl_give isl_ast_build *isl_ast_build_set_create_leaf(
build->at_each_domain = NULL;
build->at_each_domain_user = NULL;
+ build->before_each_for = NULL;
+ build->before_each_for_user = NULL;
+ build->after_each_for = NULL;
+ build->after_each_for_user = NULL;
build->create_leaf = NULL;
build->create_leaf_user = NULL;
set = isl_set_compute_divs(set);
build->pending = isl_set_intersect(build->pending,
isl_set_copy(set));
- if (isl_ast_build_has_stride(build, build->depth))
+ if (isl_ast_build_has_stride(build, build->depth)) {
build->domain = isl_set_eliminate(build->domain,
isl_dim_set, build->depth, 1);
+ build->domain = isl_set_compute_divs(build->domain);
+ }
} else {
isl_basic_set *generated, *pending;
/* 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)
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)
static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
__isl_keep isl_ast_build *build)
{
- int i, j;
- char name[16];
+ int i;
isl_id_list *names;
- isl_set *dom = build->domain;
names = isl_id_list_alloc(ctx, n);
for (i = 0; i < n; ++i) {
isl_id *id;
- snprintf(name, sizeof(name), "c%d", first + i);
- j = 0;
- while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
- snprintf(name, sizeof(name), "c%d_%d", first + i, j++);
- id = isl_id_alloc(ctx, name, NULL);
+ id = generate_name(ctx, first + i, build);
names = isl_id_list_add(names, id);
}
return !involves;
}
+/* Plug in the known values (fixed affine expressions in terms of
+ * parameters and outer loop iterators) of all loop iterators
+ * in the domain of "umap".
+ *
+ * We simply precompose "umap" with build->values.
+ */
+__isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
+ __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
+{
+ isl_multi_aff *values;
+
+ if (!build)
+ return isl_union_map_free(umap);
+
+ values = isl_multi_aff_copy(build->values);
+ umap = isl_union_map_preimage_domain_multi_aff(umap, values);
+
+ return umap;
+}
+
/* Is the current dimension known to attain only a single value?
*/
int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
domain = isl_ast_build_eliminate_divs(build, domain);
return domain;
}
+
+/* Replace build->single_valued by "sv".
+ */
+__isl_give isl_ast_build *isl_ast_build_set_single_valued(
+ __isl_take isl_ast_build *build, int sv)
+{
+ if (!build)
+ return build;
+ if (build->single_valued == sv)
+ return build;
+ build = isl_ast_build_cow(build);
+ if (!build)
+ return build;
+ build->single_valued = sv;
+
+ return build;
+}