* Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
*/
+#include <limits.h>
#include <isl/aff.h>
#include <isl/set.h>
#include <isl/ilp.h>
#include <isl_ast_build_expr.h>
#include <isl_ast_build_private.h>
#include <isl_ast_graft_private.h>
-#include <isl_list_private.h>
/* Add the constraint to the list that "user" points to, if it is not
* a div constraint.
return graft;
}
-/* Eliminate the schedule dimension "pos" from "executed" and return
- * the result.
+/* Plug in all the know values of the current and outer dimensions
+ * in the domain of "executed". In principle, we only need to plug
+ * in the known value of the current dimension since the values of
+ * outer dimensions have been plugged in already.
+ * However, it turns out to be easier to just plug in all known values.
*/
-static __isl_give isl_union_map *eliminate(__isl_take isl_union_map *executed,
- int pos, __isl_keep isl_ast_build *build)
+static __isl_give isl_union_map *plug_in_values(
+ __isl_take isl_union_map *executed, __isl_keep isl_ast_build *build)
{
- isl_space *space;
- isl_map *elim;
-
- space = isl_ast_build_get_space(build, 1);
- space = isl_space_map_from_set(space);
- elim = isl_map_identity(space);
- elim = isl_map_eliminate(elim, isl_dim_in, pos, 1);
-
- executed = isl_union_map_apply_domain(executed,
- isl_union_map_from_map(elim));
-
- return executed;
+ return isl_ast_build_substitute_values_union_map_domain(build,
+ executed);
}
/* Check if the constraint "c" is a lower bound on dimension "pos",
* to be sorted before the lower bounds on "depth", which in
* turn are sorted before the upper bounds on "depth".
*/
-static int cmp_constraint(const void *a, const void *b, void *user)
+static int cmp_constraint(__isl_keep isl_constraint *a,
+ __isl_keep isl_constraint *b, void *user)
{
int *depth = user;
- isl_constraint * const *c1 = a;
- isl_constraint * const *c2 = b;
- int t1 = constraint_type(*c1, *depth);
- int t2 = constraint_type(*c2, *depth);
+ int t1 = constraint_type(a, *depth);
+ int t2 = constraint_type(b, *depth);
return t1 - t2;
}
if (isl_ast_build_has_stride(build, pos)) {
isl_aff *offset;
- isl_int stride;
-
- isl_int_init(stride);
+ isl_val *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_aff_sub(aff, isl_aff_copy(offset));
- aff = isl_aff_scale_down(aff, stride);
+ aff = isl_aff_scale_down_val(aff, isl_val_copy(stride));
aff = isl_aff_ceil(aff);
- aff = isl_aff_scale(aff, stride);
+ aff = isl_aff_scale_val(aff, stride);
aff = isl_aff_add(aff, offset);
-
- isl_int_clear(stride);
}
aff = isl_ast_build_compute_gist_aff(build, aff);
return pa;
}
-/* Return a list of "n" lower bounds on dimension "pos"
- * extracted from the "n" constraints starting at "constraint".
- * If "n" is zero, then we extract a lower bound from "domain" instead.
+/* Extract a lower bound on dimension "pos" from each constraint
+ * in "constraints" and return the list of lower bounds.
+ * If "constraints" has zero elements, then we extract a lower bound
+ * from "domain" instead.
*/
static __isl_give isl_pw_aff_list *lower_bounds(
- __isl_keep isl_constraint **constraint, int n, int pos,
+ __isl_keep isl_constraint_list *constraints, int pos,
__isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
{
isl_ctx *ctx;
isl_pw_aff_list *list;
- int i;
+ int i, n;
if (!build)
return NULL;
+ n = isl_constraint_list_n_constraint(constraints);
if (n == 0) {
isl_pw_aff *pa;
pa = exact_bound(domain, build, 0);
for (i = 0; i < n; ++i) {
isl_aff *aff;
+ isl_constraint *c;
- aff = lower_bound(constraint[i], pos, build);
+ c = isl_constraint_list_get_constraint(constraints, i);
+ aff = lower_bound(c, pos, build);
+ isl_constraint_free(c);
list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
}
return list;
}
-/* Return a list of "n" upper bounds on dimension "pos"
- * extracted from the "n" constraints starting at "constraint".
- * If "n" is zero, then we extract an upper bound from "domain" instead.
+/* Extract an upper bound on dimension "pos" from each constraint
+ * in "constraints" and return the list of upper bounds.
+ * If "constraints" has zero elements, then we extract an upper bound
+ * from "domain" instead.
*/
static __isl_give isl_pw_aff_list *upper_bounds(
- __isl_keep isl_constraint **constraint, int n, int pos,
+ __isl_keep isl_constraint_list *constraints, int pos,
__isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
{
isl_ctx *ctx;
isl_pw_aff_list *list;
- int i;
+ int i, n;
+ n = isl_constraint_list_n_constraint(constraints);
if (n == 0) {
isl_pw_aff *pa;
pa = exact_bound(domain, build, 1);
for (i = 0; i < n; ++i) {
isl_aff *aff;
+ isl_constraint *c;
- aff = isl_constraint_get_bound(constraint[i], isl_dim_set, pos);
+ c = isl_constraint_list_get_constraint(constraints, i);
+ aff = isl_constraint_get_bound(c, isl_dim_set, pos);
+ isl_constraint_free(c);
aff = isl_aff_floor(aff);
list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
}
return graft;
}
-/* Return the intersection of the "n" constraints starting at "constraint"
- * as a set.
+/* Return the intersection of constraints in "list" as a set.
*/
-static __isl_give isl_set *intersect_constraints(isl_ctx *ctx,
- __isl_keep isl_constraint **constraint, int n)
+static __isl_give isl_set *intersect_constraints(
+ __isl_keep isl_constraint_list *list)
{
- int i;
+ int i, n;
isl_basic_set *bset;
+ n = isl_constraint_list_n_constraint(list);
if (n < 1)
- isl_die(ctx, isl_error_internal,
+ isl_die(isl_constraint_list_get_ctx(list), isl_error_internal,
"expecting at least one constraint", return NULL);
bset = isl_basic_set_from_constraint(
- isl_constraint_copy(constraint[0]));
+ isl_constraint_list_get_constraint(list, 0));
for (i = 1; i < n; ++i) {
isl_basic_set *bset_i;
bset_i = isl_basic_set_from_constraint(
- isl_constraint_copy(constraint[i]));
+ isl_constraint_list_get_constraint(list, i));
bset = isl_basic_set_intersect(bset, bset_i);
}
__isl_take isl_aff *aff, void *user)
{
int *neg = user;
- isl_int v;
+ isl_val *v;
- isl_int_init(v);
- isl_aff_get_constant(aff, &v);
- *neg = isl_int_is_neg(v);
- isl_int_clear(v);
+ v = isl_aff_get_constant_val(aff);
+ *neg = isl_val_is_neg(v);
+ isl_val_free(v);
isl_set_free(set);
isl_aff_free(aff);
static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build)
{
int depth;
- isl_int v;
+ isl_val *v;
isl_ctx *ctx;
- isl_ast_expr *inc;
if (!build)
return NULL;
if (!isl_ast_build_has_stride(build, depth))
return isl_ast_expr_alloc_int_si(ctx, 1);
- isl_int_init(v);
- isl_ast_build_get_stride(build, depth, &v);
- inc = isl_ast_expr_alloc_int(ctx, v);
- isl_int_clear(v);
-
- return inc;
+ v = isl_ast_build_get_stride(build, depth);
+ return isl_ast_expr_from_val(v);
}
/* Should we express the loop condition as
/* Update "graft" based on "bounds" and "domain" for the generic,
* non-degenerate, case.
*
- * "constraints" contains the "n_lower" lower and "n_upper" upper bounds
+ * "c_lower" and "c_upper" contain the lower and upper bounds
* that the loop node should express.
* "domain" is the subset of the intersection of the constraints
* for which some code is executed.
*/
static __isl_give isl_ast_graft *refine_generic_bounds(
__isl_take isl_ast_graft *graft,
- __isl_keep isl_constraint **constraint, int n_lower, int n_upper,
+ __isl_take isl_constraint_list *c_lower,
+ __isl_take isl_constraint_list *c_upper,
__isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
{
int depth;
int use_list;
isl_set *upper_set = NULL;
isl_pw_aff_list *upper_list = NULL;
+ int n_lower, n_upper;
- if (!graft || !build)
- return isl_ast_graft_free(graft);
+ if (!graft || !c_lower || !c_upper || !build)
+ goto error;
depth = isl_ast_build_get_depth(build);
ctx = isl_ast_graft_get_ctx(graft);
+ n_lower = isl_constraint_list_n_constraint(c_lower);
+ n_upper = isl_constraint_list_n_constraint(c_upper);
+
use_list = use_upper_bound_list(ctx, n_upper, domain, depth);
- lower = lower_bounds(constraint, n_lower, depth, domain, build);
+ lower = lower_bounds(c_lower, depth, domain, build);
if (use_list)
- upper_list = upper_bounds(constraint + n_lower, n_upper, depth,
- domain, build);
+ upper_list = upper_bounds(c_upper, depth, domain, build);
else if (n_upper > 0)
- upper_set = intersect_constraints(ctx, constraint + n_lower,
- n_upper);
+ upper_set = intersect_constraints(c_upper);
else
upper_set = isl_set_universe(isl_set_get_space(domain));
isl_pw_aff_list_free(lower);
isl_pw_aff_list_free(upper_list);
isl_set_free(upper_set);
+ isl_constraint_list_free(c_lower);
+ isl_constraint_list_free(c_upper);
return graft;
+error:
+ isl_constraint_list_free(c_lower);
+ isl_constraint_list_free(c_upper);
+ return isl_ast_graft_free(graft);
}
-/* How many constraints in the "constraint" array, starting at position "first"
- * are of the give type? "n" represents the total number of elements
- * in the array.
+/* Internal data structure used inside count_constraints to keep
+ * track of the number of constraints that are independent of dimension "pos",
+ * the lower bounds in "pos" and the upper bounds in "pos".
*/
-static int count_constraints(isl_constraint **constraint, int n, int first,
- int pos, int type)
+struct isl_ast_count_constraints_data {
+ int pos;
+
+ int n_indep;
+ int n_lower;
+ int n_upper;
+};
+
+/* Increment data->n_indep, data->lower or data->upper depending
+ * on whether "c" is independenct of dimensions data->pos,
+ * a lower bound or an upper bound.
+ */
+static int count_constraints(__isl_take isl_constraint *c, void *user)
{
- int i;
+ struct isl_ast_count_constraints_data *data = user;
- constraint += first;
+ if (isl_constraint_is_lower_bound(c, isl_dim_set, data->pos))
+ data->n_lower++;
+ else if (isl_constraint_is_upper_bound(c, isl_dim_set, data->pos))
+ data->n_upper++;
+ else
+ data->n_indep++;
- for (i = 0; first + i < n; i++)
- if (constraint_type(constraint[i], pos) != type)
- break;
+ isl_constraint_free(c);
- return i;
+ return 0;
}
/* Update "graft" based on "bounds" and "domain" for the generic,
* where this guard is enforced.
*/
static __isl_give isl_ast_graft *refine_generic_split(
- __isl_take isl_ast_graft *graft, __isl_keep isl_constraint_list *list,
+ __isl_take isl_ast_graft *graft, __isl_take isl_constraint_list *list,
__isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
{
- isl_ctx *ctx;
isl_ast_build *for_build;
isl_set *guard;
- int n_indep, n_lower, n_upper;
- int pos;
- int n;
+ struct isl_ast_count_constraints_data data;
+ isl_constraint_list *lower;
+ isl_constraint_list *upper;
if (!list)
return isl_ast_graft_free(graft);
- pos = isl_ast_build_get_depth(build);
+ data.pos = isl_ast_build_get_depth(build);
- if (isl_sort(list->p, list->n, sizeof(isl_constraint *),
- &cmp_constraint, &pos) < 0)
+ list = isl_constraint_list_sort(list, &cmp_constraint, &data.pos);
+ if (!list)
return isl_ast_graft_free(graft);
- n = list->n;
- n_indep = count_constraints(list->p, n, 0, pos, 0);
- n_lower = count_constraints(list->p, n, n_indep, pos, 1);
- n_upper = count_constraints(list->p, n, n_indep + n_lower, pos, 2);
+ data.n_indep = data.n_lower = data.n_upper = 0;
+ if (isl_constraint_list_foreach(list, &count_constraints, &data) < 0) {
+ isl_constraint_list_free(list);
+ return isl_ast_graft_free(graft);
+ }
- if (n_indep == 0)
- return refine_generic_bounds(graft,
- list->p + n_indep, n_lower, n_upper, domain, build);
+ lower = isl_constraint_list_copy(list);
+ lower = isl_constraint_list_drop(lower, 0, data.n_indep);
+ upper = isl_constraint_list_copy(lower);
+ lower = isl_constraint_list_drop(lower, data.n_lower, data.n_upper);
+ upper = isl_constraint_list_drop(upper, 0, data.n_lower);
- ctx = isl_ast_graft_get_ctx(graft);
- guard = intersect_constraints(ctx, list->p, n_indep);
+ if (data.n_indep == 0) {
+ isl_constraint_list_free(list);
+ return refine_generic_bounds(graft, lower, upper,
+ domain, build);
+ }
+
+ list = isl_constraint_list_drop(list, data.n_indep,
+ data.n_lower + data.n_upper);
+ guard = intersect_constraints(list);
+ isl_constraint_list_free(list);
for_build = isl_ast_build_copy(build);
for_build = isl_ast_build_restrict_pending(for_build,
isl_set_copy(guard));
- graft = refine_generic_bounds(graft,
- list->p + n_indep, n_lower, n_upper, domain, for_build);
+ graft = refine_generic_bounds(graft, lower, upper, domain, for_build);
isl_ast_build_free(for_build);
graft = isl_ast_graft_add_guard(graft, guard, build);
return graft;
}
+/* Add the guard implied by the current stride constraint (if any),
+ * but not (necessarily) enforced by the generated AST to "graft".
+ */
+static __isl_give isl_ast_graft *add_stride_guard(
+ __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
+{
+ int depth;
+ isl_set *dom;
+
+ depth = isl_ast_build_get_depth(build);
+ if (!isl_ast_build_has_stride(build, depth))
+ return graft;
+
+ dom = isl_ast_build_get_stride_constraint(build);
+ dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
+ dom = isl_ast_build_compute_gist(build, dom);
+
+ graft = isl_ast_graft_add_guard(graft, dom, build);
+
+ return graft;
+}
+
/* Update "graft" based on "bounds" and "domain" for the generic,
* non-degenerate, case.
*
list = isl_constraint_list_from_basic_set(bounds);
graft = refine_generic_split(graft, list, domain, build);
+ graft = add_stride_guard(graft, build);
- isl_constraint_list_free(list);
return graft;
}
* it can be printed as an assignment of the single value to the loop
* "iterator".
*
- * If the current level is eliminated, we eliminate the current dimension
- * from the inverse schedule to make sure no inner dimensions depend
+ * If the current level is eliminated, we explicitly plug in the value
+ * for the current level found by isl_ast_build_set_loop_bounds in the
+ * inverse schedule. This ensures that if we are working on a slice
+ * of the domain based on information available in the inverse schedule
+ * and the build domain, that then this information is also reflected
+ * in the inverse schedule. This operation also eliminates the current
+ * dimension from the inverse schedule making sure no inner dimensions depend
* on the current dimension. Otherwise, we create a for node, marking
* it degenerate if appropriate. The initial for node is still incomplete
* and will be completed in either refine_degenerate or refine_generic.
if (degenerate < 0 || eliminated < 0)
executed = isl_union_map_free(executed);
if (eliminated)
- executed = eliminate(executed, depth, build);
+ executed = plug_in_values(executed, sub_build);
else
node = create_for(build, degenerate);
* are multiples of "m", reducing "m" if they are not.
* If "m" is reduced all the way down to "1", then the check has failed
* and we break out of the iteration.
- * "d" is an initialized isl_int that can be used internally.
*/
struct isl_check_scaled_data {
int depth;
- isl_int m, d;
+ isl_val *m;
};
/* If constraint "c" involves the input dimension data->depth,
for (i = 0; i < 4; ++i) {
n = isl_constraint_dim(c, t[i]);
for (j = 0; j < n; ++j) {
+ isl_val *d;
+
if (t[i] == isl_dim_in && j == data->depth)
continue;
if (!isl_constraint_involves_dims(c, t[i], j, 1))
continue;
- isl_constraint_get_coefficient(c, t[i], j, &data->d);
- isl_int_gcd(data->m, data->m, data->d);
- if (isl_int_is_one(data->m))
+ d = isl_constraint_get_coefficient_val(c, t[i], j);
+ data->m = isl_val_gcd(data->m, d);
+ if (isl_val_is_one(data->m))
break;
}
if (j < n)
struct isl_check_scaled_data data;
isl_ctx *ctx;
isl_aff *offset;
+ isl_val *d;
ctx = isl_ast_build_get_ctx(build);
if (!isl_options_get_ast_build_scale_strides(ctx))
if (!isl_ast_build_has_stride(build, data.depth))
return create_node_scaled(executed, bounds, domain, build);
- isl_int_init(data.m);
- isl_int_init(data.d);
-
offset = isl_ast_build_get_offset(build, data.depth);
- if (isl_ast_build_get_stride(build, data.depth, &data.m) < 0)
+ data.m = isl_ast_build_get_stride(build, data.depth);
+ if (!data.m)
offset = isl_aff_free(offset);
- offset = isl_aff_scale_down(offset, data.m);
- if (isl_aff_get_denominator(offset, &data.d) < 0)
+ offset = isl_aff_scale_down_val(offset, isl_val_copy(data.m));
+ d = isl_aff_get_denominator_val(offset);
+ if (!d)
executed = isl_union_map_free(executed);
- if (executed && isl_int_is_divisible_by(data.m, data.d))
- isl_int_divexact(data.m, data.m, data.d);
- else
- isl_int_set_si(data.m, 1);
+ if (executed && isl_val_is_divisible_by(data.m, d))
+ data.m = isl_val_div(data.m, d);
+ else {
+ data.m = isl_val_set_si(data.m, 1);
+ isl_val_free(d);
+ }
- if (!isl_int_is_one(data.m)) {
+ if (!isl_val_is_one(data.m)) {
if (isl_union_map_foreach_map(executed, &map_check_scaled,
&data) < 0 &&
- !isl_int_is_one(data.m))
+ !isl_val_is_one(data.m))
executed = isl_union_map_free(executed);
}
- if (!isl_int_is_one(data.m)) {
+ if (!isl_val_is_one(data.m)) {
isl_space *space;
isl_multi_aff *ma;
isl_aff *aff;
space = isl_space_map_from_set(space);
ma = isl_multi_aff_identity(space);
aff = isl_multi_aff_get_aff(ma, data.depth);
- aff = isl_aff_scale(aff, data.m);
+ aff = isl_aff_scale_val(aff, isl_val_copy(data.m));
ma = isl_multi_aff_set_aff(ma, data.depth, aff);
bounds = isl_basic_set_preimage_multi_aff(bounds,
umap = isl_union_map_from_map(map);
executed = isl_union_map_apply_domain(executed,
isl_union_map_copy(umap));
- build = isl_ast_build_scale_down(build, data.m, umap);
+ build = isl_ast_build_scale_down(build, isl_val_copy(data.m),
+ umap);
}
isl_aff_free(offset);
-
- isl_int_clear(data.d);
- isl_int_clear(data.m);
+ isl_val_free(data.m);
return create_node_scaled(executed, bounds, domain, build);
}
return list;
}
-struct isl_domain_follows_at_depth_data {
- int depth;
- isl_basic_set **piece;
-};
-
/* Does any element of i follow or coincide with any element of j
- * at the current depth (data->depth) for equal values of the outer
- * dimensions?
+ * at the current depth for equal values of the outer dimensions?
*/
-static int domain_follows_at_depth(int i, int j, void *user)
+static int domain_follows_at_depth(__isl_keep isl_basic_set *i,
+ __isl_keep isl_basic_set *j, void *user)
{
- struct isl_domain_follows_at_depth_data *data = user;
+ int depth = *(int *) user;
isl_basic_map *test;
int empty;
int l;
- test = isl_basic_map_from_domain_and_range(
- isl_basic_set_copy(data->piece[i]),
- isl_basic_set_copy(data->piece[j]));
- for (l = 0; l < data->depth; ++l)
+ test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
+ isl_basic_set_copy(j));
+ for (l = 0; l < depth; ++l)
test = isl_basic_map_equate(test, isl_dim_in, l,
isl_dim_out, l);
- test = isl_basic_map_order_ge(test, isl_dim_in, data->depth,
- isl_dim_out, data->depth);
+ test = isl_basic_map_order_ge(test, isl_dim_in, depth,
+ isl_dim_out, depth);
empty = isl_basic_map_is_empty(test);
isl_basic_map_free(test);
return empty < 0 ? -1 : !empty;
}
+/* Split up each element of "list" into a part that is related to "bset"
+ * according to "gt" and a part that is not.
+ * Return a list that consist of "bset" and all the pieces.
+ */
+static __isl_give isl_basic_set_list *add_split_on(
+ __isl_take isl_basic_set_list *list, __isl_take isl_basic_set *bset,
+ __isl_keep isl_basic_map *gt)
+{
+ int i, n;
+ isl_basic_set_list *res;
+
+ gt = isl_basic_map_copy(gt);
+ gt = isl_basic_map_intersect_domain(gt, isl_basic_set_copy(bset));
+ n = isl_basic_set_list_n_basic_set(list);
+ res = isl_basic_set_list_from_basic_set(bset);
+ for (i = 0; res && i < n; ++i) {
+ isl_basic_set *bset;
+ isl_set *set1, *set2;
+ isl_basic_map *bmap;
+ int empty;
+
+ bset = isl_basic_set_list_get_basic_set(list, i);
+ bmap = isl_basic_map_copy(gt);
+ bmap = isl_basic_map_intersect_range(bmap, bset);
+ bset = isl_basic_map_range(bmap);
+ empty = isl_basic_set_is_empty(bset);
+ if (empty < 0)
+ res = isl_basic_set_list_free(res);
+ if (empty) {
+ isl_basic_set_free(bset);
+ bset = isl_basic_set_list_get_basic_set(list, i);
+ res = isl_basic_set_list_add(res, bset);
+ continue;
+ }
+
+ res = isl_basic_set_list_add(res, isl_basic_set_copy(bset));
+ set1 = isl_set_from_basic_set(bset);
+ bset = isl_basic_set_list_get_basic_set(list, i);
+ set2 = isl_set_from_basic_set(bset);
+ set1 = isl_set_subtract(set2, set1);
+ set1 = isl_set_make_disjoint(set1);
+
+ res = isl_basic_set_list_concat(res,
+ isl_basic_set_list_from_set(set1));
+ }
+ isl_basic_map_free(gt);
+ isl_basic_set_list_free(list);
+ return res;
+}
+
static __isl_give isl_ast_graft_list *generate_sorted_domains(
__isl_keep isl_basic_set_list *domain_list,
__isl_keep isl_union_map *executed,
__isl_keep isl_ast_build *build);
-/* Generate code for the "n" schedule domains in "domain_list"
- * with positions specified by the entries of the "pos" array
+/* Internal data structure for add_nodes.
+ *
+ * "executed" and "build" are extra arguments to be passed to add_node.
+ * "list" collects the results.
+ */
+struct isl_add_nodes_data {
+ isl_union_map *executed;
+ isl_ast_build *build;
+
+ isl_ast_graft_list *list;
+};
+
+/* Generate code for the schedule domains in "scc"
* and add the results to "list".
*
- * The "n" domains form a strongly connected component in the ordering.
- * If n is larger than 1, then this means that we cannot determine a valid
- * ordering for the n domains in the component. This should be fairly
- * rare because the individual domains have been made disjoint first.
+ * The domains in "scc" form a strongly connected component in the ordering.
+ * If the number of domains in "scc" is larger than 1, then this means
+ * that we cannot determine a valid ordering for the domains in the component.
+ * This should be fairly rare because the individual domains
+ * have been made disjoint first.
* The problem is that the domains may be integrally disjoint but not
* rationally disjoint. For example, we may have domains
*
* This may happen in particular in case of unrolling since the domain
* of each slice is replaced by its simple hull.
*
- * We collect the basic sets in the component, call isl_set_make_disjoint
- * and try again. Note that we rely here on isl_set_make_disjoint also
- * making the basic sets rationally disjoint. If the basic sets
- * are rationally disjoint, then the ordering problem does not occur.
- * To see this, there can only be a problem if there are points
- * (i,a) and (j,b) in one set and (i,c) and (j,d) in the other with
- * a < c and b > d. This means that either the interval spanned
- * by a en b lies inside that spanned by c and or the other way around.
- * In either case, there is a point inside both intervals with the
- * convex combination in terms of a and b and in terms of c and d.
- * Taking the same combination of i and j gives a point in the intersection.
- */
-static __isl_give isl_ast_graft_list *add_nodes(
- __isl_take isl_ast_graft_list *list, int *pos, int n,
- __isl_keep isl_basic_set_list *domain_list,
- __isl_keep isl_union_map *executed,
- __isl_keep isl_ast_build *build)
+ * For each basic set i in "scc" and for each of the following basic sets j,
+ * we split off that part of the basic set i that shares the outer dimensions
+ * with j and lies before j in the current dimension.
+ * We collect all the pieces in a new list that replaces "scc".
+ */
+static int add_nodes(__isl_take isl_basic_set_list *scc, void *user)
{
- int i;
+ struct isl_add_nodes_data *data = user;
+ int i, n, depth;
isl_basic_set *bset;
- isl_set *set;
+ isl_basic_set_list *list;
+ isl_space *space;
+ isl_basic_map *gt;
+
+ n = isl_basic_set_list_n_basic_set(scc);
+ bset = isl_basic_set_list_get_basic_set(scc, 0);
+ if (n == 1) {
+ isl_basic_set_list_free(scc);
+ data->list = add_node(data->list,
+ isl_union_map_copy(data->executed), bset,
+ isl_ast_build_copy(data->build));
+ return data->list ? 0 : -1;
+ }
- bset = isl_basic_set_list_get_basic_set(domain_list, pos[0]);
- if (n == 1)
- return add_node(list, isl_union_map_copy(executed), bset,
- isl_ast_build_copy(build));
+ depth = isl_ast_build_get_depth(data->build);
+ space = isl_basic_set_get_space(bset);
+ space = isl_space_map_from_set(space);
+ gt = isl_basic_map_universe(space);
+ for (i = 0; i < depth; ++i)
+ gt = isl_basic_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
+ gt = isl_basic_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
- set = isl_set_from_basic_set(bset);
+ list = isl_basic_set_list_from_basic_set(bset);
for (i = 1; i < n; ++i) {
- bset = isl_basic_set_list_get_basic_set(domain_list, pos[i]);
- set = isl_set_union(set, isl_set_from_basic_set(bset));
+ bset = isl_basic_set_list_get_basic_set(scc, i);
+ list = add_split_on(list, bset, gt);
}
+ isl_basic_map_free(gt);
+ isl_basic_set_list_free(scc);
+ scc = list;
+ data->list = isl_ast_graft_list_concat(data->list,
+ generate_sorted_domains(scc, data->executed, data->build));
+ isl_basic_set_list_free(scc);
- set = isl_set_make_disjoint(set);
- if (isl_set_n_basic_set(set) == n)
- isl_die(isl_ast_graft_list_get_ctx(list), isl_error_internal,
- "unable to separate loop parts", goto error);
- domain_list = isl_basic_set_list_from_set(set);
- list = isl_ast_graft_list_concat(list,
- generate_sorted_domains(domain_list, executed, build));
- isl_basic_set_list_free(domain_list);
-
- return list;
-error:
- isl_set_free(set);
- return isl_ast_graft_list_free(list);
+ return data->list ? 0 : -1;
}
/* Sort the domains in "domain_list" according to the execution order
__isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
{
isl_ctx *ctx;
- isl_ast_graft_list *list;
- struct isl_domain_follows_at_depth_data data;
- struct isl_tarjan_graph *g;
- int i, n;
+ struct isl_add_nodes_data data;
+ int depth;
+ int n;
if (!domain_list)
return NULL;
ctx = isl_basic_set_list_get_ctx(domain_list);
n = isl_basic_set_list_n_basic_set(domain_list);
- list = isl_ast_graft_list_alloc(ctx, n);
+ data.list = isl_ast_graft_list_alloc(ctx, n);
if (n == 0)
- return list;
+ return data.list;
if (n == 1)
- return add_node(list, isl_union_map_copy(executed),
+ return add_node(data.list, isl_union_map_copy(executed),
isl_basic_set_list_get_basic_set(domain_list, 0),
isl_ast_build_copy(build));
- data.depth = isl_ast_build_get_depth(build);
- data.piece = domain_list->p;
- g = isl_tarjan_graph_init(ctx, n, &domain_follows_at_depth, &data);
- if (!g)
- goto error;
-
- i = 0;
- while (list && n) {
- int first;
-
- if (g->order[i] == -1)
- isl_die(ctx, isl_error_internal, "cannot happen",
- goto error);
- first = i;
- while (g->order[i] != -1) {
- ++i; --n;
- }
- list = add_nodes(list, g->order + first, i - first,
- domain_list, executed, build);
- ++i;
- }
-
- if (0)
-error: list = isl_ast_graft_list_free(list);
- isl_tarjan_graph_free(g);
+ depth = isl_ast_build_get_depth(build);
+ data.executed = executed;
+ data.build = build;
+ if (isl_basic_set_list_foreach_scc(domain_list,
+ &domain_follows_at_depth, &depth,
+ &add_nodes, &data) < 0)
+ data.list = isl_ast_graft_list_free(data.list);
- return list;
+ return data.list;
}
-struct isl_shared_outer_data {
- int depth;
- isl_basic_set **piece;
-};
-
-/* Do elements i and j share any values for the outer dimensions?
+/* Do i and j share any values for the outer dimensions?
*/
-static int shared_outer(int i, int j, void *user)
+static int shared_outer(__isl_keep isl_basic_set *i,
+ __isl_keep isl_basic_set *j, void *user)
{
- struct isl_shared_outer_data *data = user;
+ int depth = *(int *) user;
isl_basic_map *test;
int empty;
int l;
- test = isl_basic_map_from_domain_and_range(
- isl_basic_set_copy(data->piece[i]),
- isl_basic_set_copy(data->piece[j]));
- for (l = 0; l < data->depth; ++l)
+ test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
+ isl_basic_set_copy(j));
+ for (l = 0; l < depth; ++l)
test = isl_basic_map_equate(test, isl_dim_in, l,
isl_dim_out, l);
empty = isl_basic_map_is_empty(test);
return empty < 0 ? -1 : !empty;
}
-/* Call generate_sorted_domains on a list containing the elements
- * of "domain_list indexed by the first "n" elements of "pos".
+/* Internal data structure for generate_sorted_domains_wrap.
+ *
+ * "n" is the total number of basic sets
+ * "executed" and "build" are extra arguments to be passed
+ * to generate_sorted_domains.
+ *
+ * "single" is set to 1 by generate_sorted_domains_wrap if there
+ * is only a single component.
+ * "list" collects the results.
*/
-static __isl_give isl_ast_graft_list *generate_sorted_domains_part(
- __isl_keep isl_basic_set_list *domain_list, int *pos, int n,
- __isl_keep isl_union_map *executed,
- __isl_keep isl_ast_build *build)
-{
- int i;
- isl_ctx *ctx;
- isl_basic_set_list *slice;
+struct isl_ast_generate_parallel_domains_data {
+ int n;
+ isl_union_map *executed;
+ isl_ast_build *build;
+
+ int single;
isl_ast_graft_list *list;
+};
- ctx = isl_ast_build_get_ctx(build);
- slice = isl_basic_set_list_alloc(ctx, n);
- for (i = 0; i < n; ++i) {
- isl_basic_set *bset;
+/* Call generate_sorted_domains on "scc", fuse the result into a list
+ * with either zero or one graft and collect the these single element
+ * lists into data->list.
+ *
+ * If there is only one component, i.e., if the number of basic sets
+ * in the current component is equal to the total number of basic sets,
+ * then data->single is set to 1 and the result of generate_sorted_domains
+ * is not fused.
+ */
+static int generate_sorted_domains_wrap(__isl_take isl_basic_set_list *scc,
+ void *user)
+{
+ struct isl_ast_generate_parallel_domains_data *data = user;
+ isl_ast_graft_list *list;
- bset = isl_basic_set_copy(domain_list->p[pos[i]]);
- slice = isl_basic_set_list_add(slice, bset);
- }
+ list = generate_sorted_domains(scc, data->executed, data->build);
+ data->single = isl_basic_set_list_n_basic_set(scc) == data->n;
+ if (!data->single)
+ list = isl_ast_graft_list_fuse(list, data->build);
+ if (!data->list)
+ data->list = list;
+ else
+ data->list = isl_ast_graft_list_concat(data->list, list);
- list = generate_sorted_domains(slice, executed, build);
- isl_basic_set_list_free(slice);
+ isl_basic_set_list_free(scc);
+ if (!data->list)
+ return -1;
- return list;
+ return 0;
}
/* Look for any (weakly connected) components in the "domain_list"
* of domains that share some values of the outer dimensions.
* That is, domains in different components do not share any values
* of the outer dimensions. This means that these components
- * can be freely reorderd.
+ * can be freely reordered.
* Within each of the components, we sort the domains according
* to the execution order at the current depth.
*
- * We fuse the result of each call to generate_sorted_domains_part
- * into a list with either zero or one graft and collect these (at most)
+ * If there is more than one component, then generate_sorted_domains_wrap
+ * fuses the result of each call to generate_sorted_domains
+ * into a list with either zero or one graft and collects these (at most)
* single element lists into a bigger list. This means that the elements of the
* final list can be freely reordered. In particular, we sort them
* according to an arbitrary but fixed ordering to ease merging of
__isl_keep isl_basic_set_list *domain_list,
__isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
{
- int i, n;
- isl_ctx *ctx;
- isl_ast_graft_list *list;
- struct isl_shared_outer_data data;
- struct isl_tarjan_graph *g;
+ int depth;
+ struct isl_ast_generate_parallel_domains_data data;
if (!domain_list)
return NULL;
- n = isl_basic_set_list_n_basic_set(domain_list);
- if (n <= 1)
+ data.n = isl_basic_set_list_n_basic_set(domain_list);
+ if (data.n <= 1)
return generate_sorted_domains(domain_list, executed, build);
- ctx = isl_basic_set_list_get_ctx(domain_list);
-
- data.depth = isl_ast_build_get_depth(build);
- data.piece = domain_list->p;
- g = isl_tarjan_graph_init(ctx, n, &shared_outer, &data);
- if (!g)
- return NULL;
-
- i = 0;
- do {
- int first;
- isl_ast_graft_list *list_c;
-
- if (g->order[i] == -1)
- isl_die(ctx, isl_error_internal, "cannot happen",
- break);
- first = i;
- while (g->order[i] != -1) {
- ++i; --n;
- }
- if (first == 0 && n == 0) {
- isl_tarjan_graph_free(g);
- return generate_sorted_domains(domain_list,
- executed, build);
- }
- list_c = generate_sorted_domains_part(domain_list,
- g->order + first, i - first, executed, build);
- list_c = isl_ast_graft_list_fuse(list_c, build);
- if (first == 0)
- list = list_c;
- else
- list = isl_ast_graft_list_concat(list, list_c);
- ++i;
- } while (list && n);
-
- if (n > 0)
- list = isl_ast_graft_list_free(list);
-
- list = isl_ast_graft_list_sort_guard(list);
+ depth = isl_ast_build_get_depth(build);
+ data.list = NULL;
+ data.executed = executed;
+ data.build = build;
+ data.single = 0;
+ if (isl_basic_set_list_foreach_scc(domain_list, &shared_outer, &depth,
+ &generate_sorted_domains_wrap,
+ &data) < 0)
+ data.list = isl_ast_graft_list_free(data.list);
- isl_tarjan_graph_free(g);
+ if (!data.single)
+ data.list = isl_ast_graft_list_sort_guard(data.list);
- return list;
+ return data.list;
}
/* Internal data for separate_domain.
* found any yet.
* "n" is the corresponding size. If lower is NULL, then the value of n
* is undefined.
- *
- * "tmp" is a temporary initialized isl_int.
*/
struct isl_find_unroll_data {
isl_set *domain;
isl_aff *lower;
int *n;
- isl_int tmp;
};
/* Check if we can use "c" as a lower bound and if it is better than
__isl_keep isl_constraint *c)
{
isl_aff *aff, *lower;
- enum isl_lp_result res;
+ isl_val *max;
if (!isl_constraint_is_lower_bound(c, isl_dim_set, data->depth))
return 0;
aff = isl_aff_neg(aff);
aff = isl_aff_add_coefficient_si(aff, isl_dim_in, data->depth, 1);
aff = isl_aff_add_constant_si(aff, 1);
- res = isl_set_max(data->domain, aff, &data->tmp);
+ max = isl_set_max_val(data->domain, aff);
isl_aff_free(aff);
- if (res == isl_lp_error)
+ if (!max)
goto error;
- if (res == isl_lp_unbounded) {
+ if (isl_val_is_infty(max)) {
+ isl_val_free(max);
isl_aff_free(lower);
return 0;
}
- if (!data->lower || isl_int_cmp_si(data->tmp, *data->n) < 0) {
+ if (isl_val_cmp_si(max, INT_MAX) <= 0 &&
+ (!data->lower || isl_val_cmp_si(max, *data->n) < 0)) {
isl_aff_free(data->lower);
data->lower = lower;
- *data->n = isl_int_get_si(data->tmp);
+ *data->n = isl_val_get_num_si(max);
} else
isl_aff_free(lower);
+ isl_val_free(max);
return 1;
error:
struct isl_find_unroll_data data = { domain, depth, NULL, n };
isl_basic_set *hull;
- isl_int_init(data.tmp);
hull = isl_set_simple_hull(isl_set_copy(domain));
if (isl_basic_set_foreach_constraint(hull,
goto error;
isl_basic_set_free(hull);
- isl_int_clear(data.tmp);
if (!data.lower)
isl_die(isl_set_get_ctx(domain), isl_error_invalid,
return data.lower;
error:
isl_basic_set_free(hull);
- isl_int_clear(data.tmp);
return isl_aff_free(data.lower);
}
*
* "sep_class" contains the user-specified split into separation classes
* specialized to the current depth.
- * "done" contains the union of th separation domains that have already
+ * "done" contains the union of the separation domains that have already
* been handled.
+ * "atomic" contains the domain that has effectively been made atomic.
+ * This domain may be larger than the intersection of option[atomic]
+ * and the schedule domain.
*/
struct isl_codegen_domains {
isl_basic_set_list *list;
isl_map *sep_class;
isl_set *done;
+ isl_set *atomic;
};
/* Add domains to domains->list for each individual value of the current
/* Construct a single basic set that includes the intersection of
* the schedule domain, the atomic option domain and the class domain.
- * Add the resulting basic set to domains->list.
+ * Add the resulting basic set to domains->list and save a copy
+ * in domains->atomic for use in compute_partial_domains.
*
* We construct a single domain rather than trying to combine
* the schedule domains of individual domains because we are working
atomic_domain = isl_set_intersect(atomic_domain, isl_set_copy(domain));
empty = isl_set_is_empty(atomic_domain);
if (empty < 0 || empty) {
- isl_set_free(atomic_domain);
+ domains->atomic = atomic_domain;
return empty < 0 ? -1 : 0;
}
atomic_domain = isl_set_coalesce(atomic_domain);
bset = isl_set_unshifted_simple_hull(atomic_domain);
+ domains->atomic = isl_set_from_basic_set(isl_basic_set_copy(bset));
domains->list = isl_basic_set_list_add(domains->list, bset);
return 0;
* the result with the current "class_domain" to ensure that the domains
* are disjoint from those generated from other class domains.
*
+ * The domain that has been made atomic may be larger than specified
+ * by the user since it needs to be representable as a single basic set.
+ * This possibly larger domain is stored in domains->atomic by
+ * compute_atomic_domain.
+ *
* If anything is left after handling separate, unroll and atomic,
* we split it up into basic sets and append the basic sets to domains->list.
*/
domain = isl_set_intersect(domain, isl_set_copy(class_domain));
if (compute_atomic_domain(domains, domain) < 0)
- goto error;
- domain = isl_set_subtract(domain,
- isl_set_copy(domains->option[atomic]));
+ domain = isl_set_free(domain);
+ domain = isl_set_subtract(domain, domains->atomic);
domain = isl_set_coalesce(domain);
domain = isl_set_make_disjoint(domain);