X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=56b99d8f914edfeca6961f384f380150eb32e7a6;hb=114115c119981b025f38b5347b8fdd1cee0c1646;hp=76b3ae9bb3ef647b410887a1c57547c71d139672;hpb=4818f1dd86a3abe19f510be9c4c7483368aba15a;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index 76b3ae9..56b99d8 100644 --- a/isl_map.c +++ b/isl_map.c @@ -1,6 +1,7 @@ /* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay + * Copyright 2012 Ecole Normale Superieure * * Use of this software is governed by the GNU LGPLv2.1 license * @@ -8,6 +9,7 @@ * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France */ #include @@ -30,6 +32,7 @@ #include #include #include +#include static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type) { @@ -121,6 +124,8 @@ unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset) unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset) { + if (!bset) + return 0; return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div; } @@ -254,25 +259,42 @@ __isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset) return isl_space_copy(bset->dim); } -__isl_give isl_local_space *isl_basic_map_get_local_space( - __isl_keep isl_basic_map *bmap) +/* Extract the divs in "bmap" as a matrix. + */ +__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap) { int i; - isl_local_space *ls; + isl_ctx *ctx; + isl_mat *div; unsigned total; + unsigned cols; if (!bmap) return NULL; - total = isl_basic_map_total_dim(bmap); - ls = isl_local_space_alloc(isl_space_copy(bmap->dim), bmap->n_div); - if (!ls) + ctx = isl_basic_map_get_ctx(bmap); + total = isl_space_dim(bmap->dim, isl_dim_all); + cols = 1 + 1 + total + bmap->n_div; + div = isl_mat_alloc(ctx, bmap->n_div, cols); + if (!div) return NULL; for (i = 0; i < bmap->n_div; ++i) - isl_seq_cpy(ls->div->row[i], bmap->div[i], 2 + total); + isl_seq_cpy(div->row[i], bmap->div[i], cols); + + return div; +} + +__isl_give isl_local_space *isl_basic_map_get_local_space( + __isl_keep isl_basic_map *bmap) +{ + isl_mat *div; - return ls; + if (!bmap) + return NULL; + + div = isl_basic_map_get_divs(bmap); + return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div); } __isl_give isl_local_space *isl_basic_set_get_local_space( @@ -386,6 +408,13 @@ error: return NULL; } +/* Does the input or output tuple have a name? + */ +int isl_map_has_tuple_name(__isl_keep isl_map *map, enum isl_dim_type type) +{ + return map ? isl_space_has_tuple_name(map->dim, type) : -1; +} + const char *isl_map_get_tuple_name(__isl_keep isl_map *map, enum isl_dim_type type) { @@ -454,6 +483,14 @@ __isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set) return isl_map_get_tuple_id(set, isl_dim_set); } +/* Does the set tuple have a name? + */ +int isl_set_has_tuple_name(__isl_keep isl_set *set) +{ + return set ? isl_space_has_tuple_name(set->dim, isl_dim_set) : -1; +} + + const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset) { return bset ? isl_space_get_tuple_name(bset->dim, isl_dim_set) : NULL; @@ -476,6 +513,14 @@ const char *isl_basic_set_get_dim_name(__isl_keep isl_basic_set *bset, return bset ? isl_space_get_dim_name(bset->dim, type, pos) : NULL; } +/* Does the given dimension have a name? + */ +int isl_map_has_dim_name(__isl_keep isl_map *map, + enum isl_dim_type type, unsigned pos) +{ + return map ? isl_space_has_dim_name(map->dim, type, pos) : -1; +} + const char *isl_map_get_dim_name(__isl_keep isl_map *map, enum isl_dim_type type, unsigned pos) { @@ -488,6 +533,14 @@ const char *isl_set_get_dim_name(__isl_keep isl_set *set, return set ? isl_space_get_dim_name(set->dim, type, pos) : NULL; } +/* Does the given dimension have a name? + */ +int isl_set_has_dim_name(__isl_keep isl_set *set, + enum isl_dim_type type, unsigned pos) +{ + return set ? isl_space_has_dim_name(set->dim, type, pos) : -1; +} + __isl_give isl_basic_map *isl_basic_map_set_dim_name( __isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, const char *s) @@ -498,7 +551,7 @@ __isl_give isl_basic_map *isl_basic_map_set_dim_name( bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s); if (!bmap->dim) goto error; - return bmap; + return isl_basic_map_finalize(bmap); error: isl_basic_map_free(bmap); return NULL; @@ -549,6 +602,12 @@ int isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap, return bmap ? isl_space_has_dim_id(bmap->dim, type, pos) : -1; } +__isl_give isl_id *isl_basic_set_get_dim_id(__isl_keep isl_basic_set *bset, + enum isl_dim_type type, unsigned pos) +{ + return bset ? isl_space_get_dim_id(bset->dim, type, pos) : NULL; +} + int isl_map_has_dim_id(__isl_keep isl_map *map, enum isl_dim_type type, unsigned pos) { @@ -613,6 +672,12 @@ int isl_map_find_dim_by_name(__isl_keep isl_map *map, enum isl_dim_type type, return isl_space_find_dim_by_name(map->dim, type, name); } +int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type, + const char *name) +{ + return isl_map_find_dim_by_name(set, type, name); +} + int isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap) { if (!bmap) @@ -1546,8 +1611,8 @@ void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b) } /* Eliminate the specified n dimensions starting at first from the - * constraints using Fourier-Motzkin. The dimensions themselves - * are not removed. + * constraints, without removing the dimensions from the space. + * If the set is rational, the dimensions are eliminated using Fourier-Motzkin. */ __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map, enum isl_dim_type type, unsigned first, unsigned n) @@ -1559,6 +1624,10 @@ __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map, if (n == 0) return map; + if (first + n > isl_map_dim(map, type) || first + n < first) + isl_die(map->ctx, isl_error_invalid, + "index out of bounds", goto error); + map = isl_map_cow(map); if (!map) return NULL; @@ -1575,8 +1644,8 @@ error: } /* Eliminate the specified n dimensions starting at first from the - * constraints using Fourier-Motzkin. The dimensions themselves - * are not removed. + * constraints, without removing the dimensions from the space. + * If the set is rational, the dimensions are eliminated using Fourier-Motzkin. */ __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set, enum isl_dim_type type, unsigned first, unsigned n) @@ -1585,8 +1654,8 @@ __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set, } /* Eliminate the specified n dimensions starting at first from the - * constraints using Fourier-Motzkin. The dimensions themselves - * are not removed. + * constraints, without removing the dimensions from the space. + * If the set is rational, the dimensions are eliminated using Fourier-Motzkin. */ __isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set, unsigned first, unsigned n) @@ -1689,6 +1758,196 @@ static int div_involves_vars(__isl_keep isl_basic_map *bmap, int div, return 0; } +/* Try and add a lower and/or upper bound on "div" to "bmap" + * based on inequality "i". + * "total" is the total number of variables (excluding the divs). + * "v" is a temporary object that can be used during the calculations. + * If "lb" is set, then a lower bound should be constructed. + * If "ub" is set, then an upper bound should be constructed. + * + * The calling function has already checked that the inequality does not + * reference "div", but we still need to check that the inequality is + * of the right form. We'll consider the case where we want to construct + * a lower bound. The construction of upper bounds is similar. + * + * Let "div" be of the form + * + * q = floor((a + f(x))/d) + * + * We essentially check if constraint "i" is of the form + * + * b + f(x) >= 0 + * + * so that we can use it to derive a lower bound on "div". + * However, we allow a slightly more general form + * + * b + g(x) >= 0 + * + * with the condition that the coefficients of g(x) - f(x) are all + * divisible by d. + * Rewriting this constraint as + * + * 0 >= -b - g(x) + * + * adding a + f(x) to both sides and dividing by d, we obtain + * + * (a + f(x))/d >= (a-b)/d + (f(x)-g(x))/d + * + * Taking the floor on both sides, we obtain + * + * q >= floor((a-b)/d) + (f(x)-g(x))/d + * + * or + * + * (g(x)-f(x))/d + ceil((b-a)/d) + q >= 0 + * + * In the case of an upper bound, we construct the constraint + * + * (g(x)+f(x))/d + floor((b+a)/d) - q >= 0 + * + */ +static __isl_give isl_basic_map *insert_bounds_on_div_from_ineq( + __isl_take isl_basic_map *bmap, int div, int i, + unsigned total, isl_int v, int lb, int ub) +{ + int j; + + for (j = 0; (lb || ub) && j < total + bmap->n_div; ++j) { + if (lb) { + isl_int_sub(v, bmap->ineq[i][1 + j], + bmap->div[div][1 + 1 + j]); + lb = isl_int_is_divisible_by(v, bmap->div[div][0]); + } + if (ub) { + isl_int_add(v, bmap->ineq[i][1 + j], + bmap->div[div][1 + 1 + j]); + ub = isl_int_is_divisible_by(v, bmap->div[div][0]); + } + } + if (!lb && !ub) + return bmap; + + bmap = isl_basic_map_extend_constraints(bmap, 0, lb + ub); + if (lb) { + int k = isl_basic_map_alloc_inequality(bmap); + if (k < 0) + goto error; + for (j = 0; j < 1 + total + bmap->n_div; ++j) { + isl_int_sub(bmap->ineq[k][j], bmap->ineq[i][j], + bmap->div[div][1 + j]); + isl_int_cdiv_q(bmap->ineq[k][j], + bmap->ineq[k][j], bmap->div[div][0]); + } + isl_int_set_si(bmap->ineq[k][1 + total + div], 1); + } + if (ub) { + int k = isl_basic_map_alloc_inequality(bmap); + if (k < 0) + goto error; + for (j = 0; j < 1 + total + bmap->n_div; ++j) { + isl_int_add(bmap->ineq[k][j], bmap->ineq[i][j], + bmap->div[div][1 + j]); + isl_int_fdiv_q(bmap->ineq[k][j], + bmap->ineq[k][j], bmap->div[div][0]); + } + isl_int_set_si(bmap->ineq[k][1 + total + div], -1); + } + + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* This function is called right before "div" is eliminated from "bmap" + * using Fourier-Motzkin. + * Look through the constraints of "bmap" for constraints on the argument + * of the integer division and use them to construct constraints on the + * integer division itself. These constraints can then be combined + * during the Fourier-Motzkin elimination. + * Note that it is only useful to introduce lower bounds on "div" + * if "bmap" already contains upper bounds on "div" as the newly + * introduce lower bounds can then be combined with the pre-existing + * upper bounds. Similarly for upper bounds. + * We therefore first check if "bmap" contains any lower and/or upper bounds + * on "div". + * + * It is interesting to note that the introduction of these constraints + * can indeed lead to more accurate results, even when compared to + * deriving constraints on the argument of "div" from constraints on "div". + * Consider, for example, the set + * + * { [i,j,k] : 3 + i + 2j >= 0 and 2 * [(i+2j)/4] <= k } + * + * The second constraint can be rewritten as + * + * 2 * [(-i-2j+3)/4] + k >= 0 + * + * from which we can derive + * + * -i - 2j + 3 >= -2k + * + * or + * + * i + 2j <= 3 + 2k + * + * Combined with the first constraint, we obtain + * + * -3 <= 3 + 2k or k >= -3 + * + * If, on the other hand we derive a constraint on [(i+2j)/4] from + * the first constraint, we obtain + * + * [(i + 2j)/4] >= [-3/4] = -1 + * + * Combining this constraint with the second constraint, we obtain + * + * k >= -2 + */ +static __isl_give isl_basic_map *insert_bounds_on_div( + __isl_take isl_basic_map *bmap, int div) +{ + int i; + int check_lb, check_ub; + isl_int v; + unsigned total; + + if (!bmap) + return NULL; + + if (isl_int_is_zero(bmap->div[div][0])) + return bmap; + + total = isl_space_dim(bmap->dim, isl_dim_all); + + check_lb = 0; + check_ub = 0; + for (i = 0; (!check_lb || !check_ub) && i < bmap->n_ineq; ++i) { + int s = isl_int_sgn(bmap->ineq[i][1 + total + div]); + if (s > 0) + check_ub = 1; + if (s < 0) + check_lb = 1; + } + + if (!check_lb && !check_ub) + return bmap; + + isl_int_init(v); + + for (i = 0; bmap && i < bmap->n_ineq; ++i) { + if (!isl_int_is_zero(bmap->ineq[i][1 + total + div])) + continue; + + bmap = insert_bounds_on_div_from_ineq(bmap, div, i, total, v, + check_lb, check_ub); + } + + isl_int_clear(v); + + return bmap; +} + /* Remove all divs (recursively) involving any of the given dimensions * in their definitions. */ @@ -1707,6 +1966,7 @@ __isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims( for (i = bmap->n_div - 1; i >= 0; --i) { if (!div_involves_vars(bmap, i, first, n)) continue; + bmap = insert_bounds_on_div(bmap, i); bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1); if (!bmap) return NULL; @@ -1719,6 +1979,13 @@ error: return NULL; } +__isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims( + __isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return isl_basic_map_remove_divs_involving_dims(bset, type, first, n); +} + __isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map, enum isl_dim_type type, unsigned first, unsigned n) { @@ -1752,6 +2019,12 @@ __isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set, type, first, n); } +/* Does the desciption of "bmap" depend on the specified dimensions? + * We also check whether the dimensions appear in any of the div definitions. + * In principle there is no need for this check. If the dimensions appear + * in a div definition, they also appear in the defining constraints of that + * div. + */ int isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap, enum isl_dim_type type, unsigned first, unsigned n) { @@ -1771,6 +2044,12 @@ int isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap, for (i = 0; i < bmap->n_ineq; ++i) if (isl_seq_first_non_zero(bmap->ineq[i] + first, n) >= 0) return 1; + for (i = 0; i < bmap->n_div; ++i) { + if (isl_int_is_zero(bmap->div[i][0])) + continue; + if (isl_seq_first_non_zero(bmap->div[i] + 1 + first, n) >= 0) + return 1; + } return 0; } @@ -1844,6 +2123,9 @@ __isl_give isl_basic_map *isl_basic_map_remove_unknown_divs( if (!div_is_unknown(bmap, i)) continue; bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1); + if (!bmap) + return NULL; + i = bmap->n_div; } return bmap; @@ -2203,21 +2485,23 @@ __isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set, (struct isl_basic_map *)bset); } -void isl_set_free(struct isl_set *set) +void *isl_set_free(__isl_take isl_set *set) { int i; if (!set) - return; + return NULL; if (--set->ref > 0) - return; + return NULL; isl_ctx_deref(set->ctx); for (i = 0; i < set->n; ++i) isl_basic_set_free(set->p[i]); isl_space_free(set->dim); free(set); + + return NULL; } void isl_set_print_internal(struct isl_set *set, FILE *out, int indent) @@ -2429,6 +2713,12 @@ struct isl_basic_set *isl_basic_set_intersect( (struct isl_basic_map *)bset2); } +__isl_give isl_basic_set *isl_basic_set_intersect_params( + __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) +{ + return isl_basic_set_intersect(bset1, bset2); +} + /* Special case of isl_map_intersect, where both map1 and map2 * are convex, without any divs and such that either map1 or map2 * contains a single constraint. This constraint is then simply @@ -2628,8 +2918,9 @@ static __isl_give isl_basic_map *basic_map_space_reset( return bmap; } -__isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned pos, unsigned n) +__isl_give isl_basic_map *isl_basic_map_insert_dims( + __isl_take isl_basic_map *bmap, enum isl_dim_type type, + unsigned pos, unsigned n) { isl_space *res_dim; struct isl_basic_map *res; @@ -2666,16 +2957,27 @@ __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap, bmap->n_div, bmap->n_eq, bmap->n_ineq); if (isl_basic_map_is_rational(bmap)) res = isl_basic_map_set_rational(res); + if (isl_basic_map_plain_is_empty(bmap)) { + isl_basic_map_free(bmap); + return isl_basic_map_set_to_empty(res); + } res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); return isl_basic_map_finalize(res); } +__isl_give isl_basic_set *isl_basic_set_insert_dims( + __isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned pos, unsigned n) +{ + return isl_basic_map_insert_dims(bset, type, pos, n); +} + __isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned n) { if (!bmap) return NULL; - return isl_basic_map_insert(bmap, type, + return isl_basic_map_insert_dims(bmap, type, isl_basic_map_dim(bmap, type), n); } @@ -2722,7 +3024,7 @@ __isl_give isl_map *isl_map_insert_dims(__isl_take isl_map *map, goto error; for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_insert(map->p[i], type, pos, n); + map->p[i] = isl_basic_map_insert_dims(map->p[i], type, pos, n); if (!map->p[i]) goto error; } @@ -2970,7 +3272,7 @@ __isl_give isl_basic_map *isl_basic_map_project_out( isl_int *old; if (n == 0) - return bmap; + return basic_map_space_reset(bmap, type); if (!bmap) return NULL; @@ -3040,7 +3342,7 @@ __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map, return NULL; if (n == 0) - return map; + return map_space_reset(map, type); isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error); @@ -4900,6 +5202,25 @@ struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset, isl_dim_set, dim, value); } +static int remove_if_empty(__isl_keep isl_map *map, int i) +{ + int empty = isl_basic_map_plain_is_empty(map->p[i]); + + if (empty < 0) + return -1; + if (!empty) + return 0; + + isl_basic_map_free(map->p[i]); + if (i != map->n - 1) { + ISL_F_CLR(map, ISL_MAP_NORMALIZED); + map->p[i] = map->p[map->n - 1]; + } + map->n--; + + return 0; +} + struct isl_map *isl_map_fix_si(struct isl_map *map, enum isl_dim_type type, unsigned pos, int value) { @@ -4910,9 +5231,9 @@ struct isl_map *isl_map_fix_si(struct isl_map *map, return NULL; isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error); - for (i = 0; i < map->n; ++i) { + for (i = map->n - 1; i >= 0; --i) { map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value); - if (!map->p[i]) + if (remove_if_empty(map, i) < 0) goto error; } ISL_F_CLR(map, ISL_MAP_NORMALIZED); @@ -4969,9 +5290,9 @@ struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value) isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value); } -__isl_give isl_basic_map *isl_basic_map_lower_bound_si( - __isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned pos, int value) +static __isl_give isl_basic_map *basic_map_bound_si( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, int value, int upper) { int j; @@ -4985,8 +5306,13 @@ __isl_give isl_basic_map *isl_basic_map_lower_bound_si( if (j < 0) goto error; isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap)); - isl_int_set_si(bmap->ineq[j][pos], 1); - isl_int_set_si(bmap->ineq[j][0], -value); + if (upper) { + isl_int_set_si(bmap->ineq[j][pos], -1); + isl_int_set_si(bmap->ineq[j][0], value); + } else { + isl_int_set_si(bmap->ineq[j][pos], 1); + isl_int_set_si(bmap->ineq[j][0], -value); + } bmap = isl_basic_map_simplify(bmap); return isl_basic_map_finalize(bmap); error: @@ -4994,6 +5320,13 @@ error: return NULL; } +__isl_give isl_basic_map *isl_basic_map_lower_bound_si( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, int value) +{ + return basic_map_bound_si(bmap, type, pos, value, 0); +} + struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset, unsigned dim, isl_int value) { @@ -5014,8 +5347,8 @@ error: return NULL; } -__isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map, - enum isl_dim_type type, unsigned pos, int value) +static __isl_give isl_map *map_bound_si(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, int value, int upper) { int i; @@ -5025,8 +5358,8 @@ __isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map, isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error); for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_lower_bound_si(map->p[i], - type, pos, value); + map->p[i] = basic_map_bound_si(map->p[i], + type, pos, value, upper); if (!map->p[i]) goto error; } @@ -5037,6 +5370,18 @@ error: return NULL; } +__isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, int value) +{ + return map_bound_si(map, type, pos, value, 0); +} + +__isl_give isl_map *isl_map_upper_bound_si(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, int value) +{ + return map_bound_si(map, type, pos, value, 1); +} + __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set, enum isl_dim_type type, unsigned pos, int value) { @@ -5044,28 +5389,52 @@ __isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set, isl_map_lower_bound_si((struct isl_map *)set, type, pos, value); } -struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim, - isl_int value) +__isl_give isl_set *isl_set_upper_bound_si(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, int value) { - int i; + return isl_map_upper_bound_si(set, type, pos, value); +} - set = isl_set_cow(set); - if (!set) - return NULL; +/* Bound the given variable of "bmap" from below (or above is "upper" + * is set) to "value". + */ +static __isl_give isl_basic_map *basic_map_bound( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, isl_int value, int upper) +{ + int j; - isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error); - for (i = 0; i < set->n; ++i) { - set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value); - if (!set->p[i]) - goto error; + if (!bmap) + return NULL; + if (pos >= isl_basic_map_dim(bmap, type)) + isl_die(bmap->ctx, isl_error_invalid, + "index out of bounds", goto error); + pos += isl_basic_map_offset(bmap, type); + bmap = isl_basic_map_cow(bmap); + bmap = isl_basic_map_extend_constraints(bmap, 0, 1); + j = isl_basic_map_alloc_inequality(bmap); + if (j < 0) + goto error; + isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap)); + if (upper) { + isl_int_set_si(bmap->ineq[j][pos], -1); + isl_int_set(bmap->ineq[j][0], value); + } else { + isl_int_set_si(bmap->ineq[j][pos], 1); + isl_int_neg(bmap->ineq[j][0], value); } - return set; + bmap = isl_basic_map_simplify(bmap); + return isl_basic_map_finalize(bmap); error: - isl_set_free(set); + isl_basic_map_free(bmap); return NULL; } -struct isl_map *isl_map_reverse(struct isl_map *map) +/* Bound the given variable of "map" from below (or above is "upper" + * is set) to "value". + */ +static __isl_give isl_map *map_bound(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int value, int upper) { int i; @@ -5073,12 +5442,12 @@ struct isl_map *isl_map_reverse(struct isl_map *map) if (!map) return NULL; - map->dim = isl_space_reverse(map->dim); - if (!map->dim) - goto error; - for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_reverse(map->p[i]); - if (!map->p[i]) + if (pos >= isl_map_dim(map, type)) + isl_die(map->ctx, isl_error_invalid, + "index out of bounds", goto error); + for (i = map->n - 1; i >= 0; --i) { + map->p[i] = basic_map_bound(map->p[i], type, pos, value, upper); + if (remove_if_empty(map, i) < 0) goto error; } ISL_F_CLR(map, ISL_MAP_NORMALIZED); @@ -5088,13 +5457,81 @@ error: return NULL; } -static struct isl_map *isl_basic_map_partial_lexopt( - struct isl_basic_map *bmap, struct isl_basic_set *dom, - struct isl_set **empty, int max) +__isl_give isl_map *isl_map_lower_bound(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int value) { - if (!bmap) - goto error; - if (bmap->ctx->opt->pip == ISL_PIP_PIP) + return map_bound(map, type, pos, value, 0); +} + +__isl_give isl_map *isl_map_upper_bound(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return map_bound(map, type, pos, value, 1); +} + +__isl_give isl_set *isl_set_lower_bound(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return isl_map_lower_bound(set, type, pos, value); +} + +__isl_give isl_set *isl_set_upper_bound(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return isl_map_upper_bound(set, type, pos, value); +} + +struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim, + isl_int value) +{ + int i; + + set = isl_set_cow(set); + if (!set) + return NULL; + + isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error); + for (i = 0; i < set->n; ++i) { + set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value); + if (!set->p[i]) + goto error; + } + return set; +error: + isl_set_free(set); + return NULL; +} + +struct isl_map *isl_map_reverse(struct isl_map *map) +{ + int i; + + map = isl_map_cow(map); + if (!map) + return NULL; + + map->dim = isl_space_reverse(map->dim); + if (!map->dim) + goto error; + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_reverse(map->p[i]); + if (!map->p[i]) + goto error; + } + ISL_F_CLR(map, ISL_MAP_NORMALIZED); + return map; +error: + isl_map_free(map); + return NULL; +} + +static struct isl_map *isl_basic_map_partial_lexopt( + struct isl_basic_map *bmap, struct isl_basic_set *dom, + struct isl_set **empty, int max) +{ + if (!bmap) + goto error; + if (bmap->ctx->opt->pip == ISL_PIP_PIP) return isl_pip_basic_map_lexopt(bmap, dom, empty, max); else return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max); @@ -5188,58 +5625,93 @@ __isl_give isl_pw_multi_aff *isl_basic_map_lexmin_pw_multi_aff( return isl_basic_map_lexopt_pw_multi_aff(bmap, 0); } -/* Given a basic map "bmap", compute the lexicographically minimal - * (or maximal) image element for each domain element in dom. +#undef TYPE +#define TYPE isl_pw_multi_aff +#undef SUFFIX +#define SUFFIX _pw_multi_aff +#undef EMPTY +#define EMPTY isl_pw_multi_aff_empty +#undef ADD +#define ADD isl_pw_multi_aff_union_add +#include "isl_map_lexopt_templ.c" + +/* Given a map "map", compute the lexicographically minimal + * (or maximal) image element for each domain element in dom, + * in the form of an isl_pw_multi_aff. * Set *empty to those elements in dom that do not have an image element. * - * We first make sure the basic sets in dom are disjoint and then - * simply collect the results over each of the basic sets separately. - * We could probably improve the efficiency a bit by moving the union - * domain down into the parametric integer programming. + * We first compute the lexicographically minimal or maximal element + * in the first basic map. This results in a partial solution "res" + * and a subset "todo" of dom that still need to be handled. + * We then consider each of the remaining maps in "map" and successively + * update both "res" and "todo". */ -static __isl_give isl_map *basic_map_partial_lexopt( - __isl_take isl_basic_map *bmap, __isl_take isl_set *dom, - __isl_give isl_set **empty, int max) +static __isl_give isl_pw_multi_aff *isl_map_partial_lexopt_aligned_pw_multi_aff( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty, int max) { int i; - struct isl_map *res; + isl_pw_multi_aff *res; + isl_set *todo; - dom = isl_set_make_disjoint(dom); - if (!dom) + if (!map || !dom) goto error; - if (isl_set_plain_is_empty(dom)) { - res = isl_map_empty_like_basic_map(bmap); - *empty = isl_set_empty_like(dom); - isl_set_free(dom); - isl_basic_map_free(bmap); - return res; + if (isl_map_plain_is_empty(map)) { + if (empty) + *empty = dom; + else + isl_set_free(dom); + return isl_pw_multi_aff_from_map(map); } - res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap), - isl_basic_set_copy(dom->p[0]), empty, max); - - for (i = 1; i < dom->n; ++i) { - struct isl_map *res_i; - struct isl_set *empty_i; + res = basic_map_partial_lexopt_pw_multi_aff( + isl_basic_map_copy(map->p[0]), + isl_set_copy(dom), &todo, max); + + for (i = 1; i < map->n; ++i) { + isl_pw_multi_aff *res_i; + isl_set *todo_i; - res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap), - isl_basic_set_copy(dom->p[i]), &empty_i, max); + res_i = basic_map_partial_lexopt_pw_multi_aff( + isl_basic_map_copy(map->p[i]), + isl_set_copy(dom), &todo_i, max); - res = isl_map_union_disjoint(res, res_i); - *empty = isl_set_union_disjoint(*empty, empty_i); + if (max) + res = isl_pw_multi_aff_union_lexmax(res, res_i); + else + res = isl_pw_multi_aff_union_lexmin(res, res_i); + + todo = isl_set_intersect(todo, todo_i); } isl_set_free(dom); - isl_basic_map_free(bmap); + isl_map_free(map); + + if (empty) + *empty = todo; + else + isl_set_free(todo); + return res; error: - *empty = NULL; + if (empty) + *empty = NULL; isl_set_free(dom); - isl_basic_map_free(bmap); + isl_map_free(map); return NULL; } +#undef TYPE +#define TYPE isl_map +#undef SUFFIX +#define SUFFIX +#undef EMPTY +#define EMPTY isl_map_empty +#undef ADD +#define ADD isl_map_union_disjoint +#include "isl_map_lexopt_templ.c" + /* Given a map "map", compute the lexicographically minimal * (or maximal) image element for each domain element in dom. * Set *empty to those elements in dom that do not have an image element. @@ -5248,7 +5720,7 @@ error: * in the first basic map. This results in a partial solution "res" * and a subset "todo" of dom that still need to be handled. * We then consider each of the remaining maps in "map" and successively - * improve both "res" and "todo". + * update both "res" and "todo". * * Let res^k and todo^k be the results after k steps and let i = k + 1. * Assume we are computing the lexicographical maximum. @@ -5367,35 +5839,6 @@ error: return NULL; } -/* Given a map "map", compute the lexicographically minimal - * (or maximal) image element for each domain element in dom. - * Set *empty to those elements in dom that do not have an image element. - * - * Align parameters if needed and then call isl_map_partial_lexopt_aligned. - */ -static __isl_give isl_map *isl_map_partial_lexopt( - __isl_take isl_map *map, __isl_take isl_set *dom, - __isl_give isl_set **empty, int max) -{ - if (!map || !dom) - goto error; - if (isl_space_match(map->dim, isl_dim_param, dom->dim, isl_dim_param)) - return isl_map_partial_lexopt_aligned(map, dom, empty, max); - if (!isl_space_has_named_params(map->dim) || - !isl_space_has_named_params(dom->dim)) - isl_die(map->ctx, isl_error_invalid, - "unaligned unnamed parameters", goto error); - map = isl_map_align_params(map, isl_map_get_space(dom)); - dom = isl_map_align_params(dom, isl_map_get_space(map)); - return isl_map_partial_lexopt_aligned(map, dom, empty, max); -error: - if (empty) - *empty = NULL; - isl_set_free(dom); - isl_map_free(map); - return NULL; -} - __isl_give isl_map *isl_map_partial_lexmax( __isl_take isl_map *map, __isl_take isl_set *dom, __isl_give isl_set **empty) @@ -5463,31 +5906,6 @@ __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset) return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset); } -__isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max) -{ - struct isl_set *dom = NULL; - isl_space *dom_dim; - - if (!map) - goto error; - dom_dim = isl_space_domain(isl_space_copy(map->dim)); - dom = isl_set_universe(dom_dim); - return isl_map_partial_lexopt(map, dom, NULL, max); -error: - isl_map_free(map); - return NULL; -} - -__isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map) -{ - return isl_map_lexopt(map, 0); -} - -__isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map) -{ - return isl_map_lexopt(map, 1); -} - __isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set) { return (isl_set *)isl_map_lexmin((isl_map *)set); @@ -6258,7 +6676,7 @@ error: /* * returns range - domain */ -struct isl_set *isl_map_deltas(struct isl_map *map) +__isl_give isl_set *isl_map_deltas(__isl_take isl_map *map) { int i; isl_space *dim; @@ -6636,6 +7054,12 @@ int isl_basic_map_is_subset( return is_subset; } +int isl_basic_set_is_subset(__isl_keep isl_basic_set *bset1, + __isl_keep isl_basic_set *bset2) +{ + return isl_basic_map_is_subset(bset1, bset2); +} + int isl_basic_map_is_equal( struct isl_basic_map *bmap1, struct isl_basic_map *bmap2) { @@ -6889,7 +7313,7 @@ struct isl_map *isl_basic_map_union( { struct isl_map *map; if (!bmap1 || !bmap2) - return NULL; + goto error; isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim), goto error); @@ -7139,16 +7563,8 @@ struct isl_map *isl_map_remove_empty_parts(struct isl_map *map) if (!map) return NULL; - for (i = map->n-1; i >= 0; --i) { - if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY)) - continue; - isl_basic_map_free(map->p[i]); - if (i != map->n-1) { - ISL_F_CLR(map, ISL_MAP_NORMALIZED); - map->p[i] = map->p[map->n-1]; - } - map->n--; - } + for (i = map->n - 1; i >= 0; --i) + remove_if_empty(map, i); return map; } @@ -8049,6 +8465,11 @@ __isl_give isl_basic_map *isl_basic_map_range_product( if (!bmap1 || !bmap2) goto error; + if (!isl_space_match(bmap1->dim, isl_dim_param, + bmap2->dim, isl_dim_param)) + isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid, + "parameters don't match", goto error); + dim_result = isl_space_range_product(isl_space_copy(bmap1->dim), isl_space_copy(bmap2->dim)); @@ -8672,7 +9093,7 @@ int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset, return -1; bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset)); - tab = isl_tab_from_basic_set(bset); + tab = isl_tab_from_basic_set(bset, 0); if (!bound || !tab) goto error; @@ -8762,6 +9183,39 @@ int isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap) return 1; } +/* Check if the given basic map is single-valued. + * We simply compute + * + * M \circ M^-1 + * + * and check if the result is a subset of the identity mapping. + */ +int isl_basic_map_is_single_valued(__isl_keep isl_basic_map *bmap) +{ + isl_space *space; + isl_basic_map *test; + isl_basic_map *id; + int sv; + + sv = isl_basic_map_plain_is_single_valued(bmap); + if (sv < 0 || sv) + return sv; + + test = isl_basic_map_reverse(isl_basic_map_copy(bmap)); + test = isl_basic_map_apply_range(test, isl_basic_map_copy(bmap)); + + space = isl_basic_map_get_space(bmap); + space = isl_space_map_from_set(isl_space_range(space)); + id = isl_basic_map_identity(space); + + sv = isl_basic_map_is_subset(test, id); + + isl_basic_map_free(test); + isl_basic_map_free(id); + + return sv; +} + /* Check if the given map is obviously single-valued. */ int isl_map_plain_is_single_valued(__isl_keep isl_map *map) @@ -9275,14 +9729,21 @@ __isl_give isl_basic_map *isl_basic_map_realign(__isl_take isl_basic_map *bmap, __isl_take isl_space *dim, __isl_take struct isl_dim_map *dim_map) { isl_basic_map *res; + unsigned flags; bmap = isl_basic_map_cow(bmap); if (!bmap || !dim || !dim_map) goto error; + flags = bmap->flags; + ISL_FL_CLR(flags, ISL_BASIC_MAP_FINAL); + ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED); + ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED_DIVS); res = isl_basic_map_alloc_space(dim, bmap->n_div, bmap->n_eq, bmap->n_ineq); res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); + if (res) + res->flags = flags; res = isl_basic_map_finalize(res); return res; error: @@ -9376,6 +9837,60 @@ __isl_give isl_set *isl_set_align_params(__isl_take isl_set *set, return isl_map_align_params(set, model); } +/* Align the parameters of "bmap" to those of "model", introducing + * additional parameters if needed. + */ +__isl_give isl_basic_map *isl_basic_map_align_params( + __isl_take isl_basic_map *bmap, __isl_take isl_space *model) +{ + isl_ctx *ctx; + + if (!bmap || !model) + goto error; + + ctx = isl_space_get_ctx(model); + if (!isl_space_has_named_params(model)) + isl_die(ctx, isl_error_invalid, + "model has unnamed parameters", goto error); + if (!isl_space_has_named_params(bmap->dim)) + isl_die(ctx, isl_error_invalid, + "relation has unnamed parameters", goto error); + if (!isl_space_match(bmap->dim, isl_dim_param, model, isl_dim_param)) { + isl_reordering *exp; + struct isl_dim_map *dim_map; + + model = isl_space_drop_dims(model, isl_dim_in, + 0, isl_space_dim(model, isl_dim_in)); + model = isl_space_drop_dims(model, isl_dim_out, + 0, isl_space_dim(model, isl_dim_out)); + exp = isl_parameter_alignment_reordering(bmap->dim, model); + exp = isl_reordering_extend_space(exp, + isl_basic_map_get_space(bmap)); + dim_map = isl_dim_map_from_reordering(exp); + bmap = isl_basic_map_realign(bmap, + exp ? isl_space_copy(exp->dim) : NULL, + isl_dim_map_extend(dim_map, bmap)); + isl_reordering_free(exp); + free(dim_map); + } + + isl_space_free(model); + return bmap; +error: + isl_space_free(model); + isl_basic_map_free(bmap); + return NULL; +} + +/* Align the parameters of "bset" to those of "model", introducing + * additional parameters if needed. + */ +__isl_give isl_basic_set *isl_basic_set_align_params( + __isl_take isl_basic_set *bset, __isl_take isl_space *model) +{ + return isl_basic_map_align_params(bset, model); +} + __isl_give isl_mat *isl_basic_map_equalities_matrix( __isl_keep isl_basic_map *bmap, enum isl_dim_type c1, enum isl_dim_type c2, enum isl_dim_type c3, @@ -9573,6 +10088,7 @@ __isl_give isl_basic_map *isl_basic_map_zip(__isl_take isl_basic_map *bmap) isl_space_dim(bmap->dim->nested[0], isl_dim_in); n1 = isl_space_dim(bmap->dim->nested[0], isl_dim_out); n2 = isl_space_dim(bmap->dim->nested[1], isl_dim_in); + bmap = isl_basic_map_cow(bmap); bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2); if (!bmap) return NULL; @@ -9619,6 +10135,83 @@ error: return NULL; } +/* Can we apply isl_basic_map_curry to "bmap"? + * That is, does it have a nested relation in its domain? + */ +int isl_basic_map_can_curry(__isl_keep isl_basic_map *bmap) +{ + if (!bmap) + return -1; + + return isl_space_can_curry(bmap->dim); +} + +/* Can we apply isl_map_curry to "map"? + * That is, does it have a nested relation in its domain? + */ +int isl_map_can_curry(__isl_keep isl_map *map) +{ + if (!map) + return -1; + + return isl_space_can_curry(map->dim); +} + +/* Given a basic map (A -> B) -> C, return the corresponding basic map + * A -> (B -> C). + */ +__isl_give isl_basic_map *isl_basic_map_curry(__isl_take isl_basic_map *bmap) +{ + + if (!bmap) + return NULL; + + if (!isl_basic_map_can_curry(bmap)) + isl_die(bmap->ctx, isl_error_invalid, + "basic map cannot be curried", goto error); + bmap->dim = isl_space_curry(bmap->dim); + if (!bmap->dim) + goto error; + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* Given a map (A -> B) -> C, return the corresponding map + * A -> (B -> C). + */ +__isl_give isl_map *isl_map_curry(__isl_take isl_map *map) +{ + int i; + + if (!map) + return NULL; + + if (!isl_map_can_curry(map)) + isl_die(map->ctx, isl_error_invalid, "map cannot be curried", + goto error); + + map = isl_map_cow(map); + if (!map) + return NULL; + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_curry(map->p[i]); + if (!map->p[i]) + goto error; + } + + map->dim = isl_space_curry(map->dim); + if (!map->dim) + goto error; + + return map; +error: + isl_map_free(map); + return NULL; +} + /* Construct a basic map mapping the domain of the affine expression * to a one-dimensional range prescribed by the affine expression. */ @@ -9654,6 +10247,17 @@ error: return NULL; } +/* Construct a map mapping the domain of the affine expression + * to a one-dimensional range prescribed by the affine expression. + */ +__isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff) +{ + isl_basic_map *bmap; + + bmap = isl_basic_map_from_aff(aff); + return isl_map_from_basic_map(bmap); +} + /* Construct a basic map mapping the domain the multi-affine expression * to its range, with each dimension in the range equated to the * corresponding affine expression. @@ -9691,6 +10295,18 @@ __isl_give isl_basic_map *isl_basic_map_from_multi_aff( return bmap; } +/* Construct a map mapping the domain the multi-affine expression + * to its range, with each dimension in the range equated to the + * corresponding affine expression. + */ +__isl_give isl_map *isl_map_from_multi_aff(__isl_take isl_multi_aff *maff) +{ + isl_basic_map *bmap; + + bmap = isl_basic_map_from_multi_aff(maff); + return isl_map_from_basic_map(bmap); +} + /* Construct a basic map mapping a domain in the given space to * to an n-dimensional range, with n the number of elements in the list, * where each coordinate in the range is prescribed by the @@ -9731,11 +10347,78 @@ __isl_give isl_set *isl_set_equate(__isl_take isl_set *set, return isl_map_equate(set, type1, pos1, type2, pos2); } +/* Construct a basic map where the given dimensions are equal to each other. + */ +static __isl_give isl_basic_map *equator(__isl_take isl_space *space, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + isl_basic_map *bmap = NULL; + int i; + + if (!space) + return NULL; + + if (pos1 >= isl_space_dim(space, type1)) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "index out of bounds", goto error); + if (pos2 >= isl_space_dim(space, type2)) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "index out of bounds", goto error); + + if (type1 == type2 && pos1 == pos2) + return isl_basic_map_universe(space); + + bmap = isl_basic_map_alloc_space(isl_space_copy(space), 0, 1, 0); + i = isl_basic_map_alloc_equality(bmap); + if (i < 0) + goto error; + isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap)); + pos1 += isl_basic_map_offset(bmap, type1); + pos2 += isl_basic_map_offset(bmap, type2); + isl_int_set_si(bmap->eq[i][pos1], -1); + isl_int_set_si(bmap->eq[i][pos2], 1); + bmap = isl_basic_map_finalize(bmap); + isl_space_free(space); + return bmap; +error: + isl_space_free(space); + isl_basic_map_free(bmap); + return NULL; +} + +/* Add a constraint imposing that the given two dimensions are equal. + */ +__isl_give isl_basic_map *isl_basic_map_equate(__isl_take isl_basic_map *bmap, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + isl_basic_map *eq; + + eq = equator(isl_basic_map_get_space(bmap), type1, pos1, type2, pos2); + + bmap = isl_basic_map_intersect(bmap, eq); + + return bmap; +} + /* Add a constraint imposing that the given two dimensions are equal. */ __isl_give isl_map *isl_map_equate(__isl_take isl_map *map, enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) { + isl_basic_map *bmap; + + bmap = equator(isl_map_get_space(map), type1, pos1, type2, pos2); + + map = isl_map_intersect(map, isl_map_from_basic_map(bmap)); + + return map; +} + +/* Add a constraint imposing that the given two dimensions have opposite values. + */ +__isl_give isl_map *isl_map_oppose(__isl_take isl_map *map, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ isl_basic_map *bmap = NULL; int i; @@ -9756,7 +10439,7 @@ __isl_give isl_map *isl_map_equate(__isl_take isl_map *map, isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap)); pos1 += isl_basic_map_offset(bmap, type1); pos2 += isl_basic_map_offset(bmap, type2); - isl_int_set_si(bmap->eq[i][pos1], -1); + isl_int_set_si(bmap->eq[i][pos1], 1); isl_int_set_si(bmap->eq[i][pos2], 1); bmap = isl_basic_map_finalize(bmap); @@ -9769,9 +10452,10 @@ error: return NULL; } -/* Add a constraint imposing that the given two dimensions have opposite values. +/* Add a constraint imposing that the value of the first dimension is + * greater than that of the second. */ -__isl_give isl_map *isl_map_oppose(__isl_take isl_map *map, +__isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map, enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) { isl_basic_map *bmap = NULL; @@ -9787,15 +10471,22 @@ __isl_give isl_map *isl_map_oppose(__isl_take isl_map *map, isl_die(map->ctx, isl_error_invalid, "index out of bounds", goto error); - bmap = isl_basic_map_alloc_space(isl_map_get_space(map), 0, 1, 0); - i = isl_basic_map_alloc_equality(bmap); + if (type1 == type2 && pos1 == pos2) { + isl_space *space = isl_map_get_space(map); + isl_map_free(map); + return isl_map_empty(space); + } + + bmap = isl_basic_map_alloc_space(isl_map_get_space(map), 0, 0, 1); + i = isl_basic_map_alloc_inequality(bmap); if (i < 0) goto error; - isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap)); + isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap)); pos1 += isl_basic_map_offset(bmap, type1); pos2 += isl_basic_map_offset(bmap, type2); - isl_int_set_si(bmap->eq[i][pos1], 1); - isl_int_set_si(bmap->eq[i][pos2], 1); + isl_int_set_si(bmap->ineq[i][pos1], 1); + isl_int_set_si(bmap->ineq[i][pos2], -1); + isl_int_set_si(bmap->ineq[i][0], -1); bmap = isl_basic_map_finalize(bmap); map = isl_map_intersect(map, isl_map_from_basic_map(bmap)); @@ -9807,6 +10498,15 @@ error: return NULL; } +/* Add a constraint imposing that the value of the first dimension is + * smaller than that of the second. + */ +__isl_give isl_map *isl_map_order_lt(__isl_take isl_map *map, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + return isl_map_order_gt(map, type2, pos2, type1, pos1); +} + __isl_give isl_aff *isl_basic_map_get_div(__isl_keep isl_basic_map *bmap, int pos) { @@ -9936,14 +10636,8 @@ __isl_give isl_set *isl_set_substitute(__isl_take isl_set *set, for (i = set->n - 1; i >= 0; --i) { set->p[i] = isl_basic_set_substitute(set->p[i], type, pos, subs); - if (!set->p[i]) + if (remove_if_empty(set, i) < 0) goto error; - if (isl_basic_set_plain_is_empty(set->p[i])) { - isl_basic_set_free(set->p[i]); - if (i != set->n - 1) - set->p[i] = set->p[set->n - 1]; - set->n--; - } } return set;