X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=0478d727434301d6ae83fe91e9574257fbb98c9a;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=583a4a7cf0ac336d7a994331a6821bc05b141e67;hpb=0a9aac4830de19b5a45ce5d0fbd23c57583ab347;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index 583a4a7..0478d72 100644 --- a/isl_map.c +++ b/isl_map.c @@ -1,13 +1,15 @@ /* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay + * Copyright 2012-2013 Ecole Normale Superieure * - * Use of this software is governed by the GNU LGPLv2.1 license + * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * 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 @@ -16,7 +18,6 @@ #include #include "isl_space_private.h" #include "isl_equalities.h" -#include #include #include #include @@ -31,6 +32,7 @@ #include #include #include +#include static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type) { @@ -406,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) { @@ -504,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) { @@ -534,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; @@ -673,6 +690,76 @@ int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset) return isl_basic_map_is_rational(bset); } +/* Does "bmap" contain any rational points? + * + * If "bmap" has an equality for each dimension, equating the dimension + * to an integer constant, then it has no rational points, even if it + * is marked as rational. + */ +int isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap) +{ + int has_rational = 1; + unsigned total; + + if (!bmap) + return -1; + if (isl_basic_map_plain_is_empty(bmap)) + return 0; + if (!isl_basic_map_is_rational(bmap)) + return 0; + bmap = isl_basic_map_copy(bmap); + bmap = isl_basic_map_implicit_equalities(bmap); + if (!bmap) + return -1; + total = isl_basic_map_total_dim(bmap); + if (bmap->n_eq == total) { + int i, j; + for (i = 0; i < bmap->n_eq; ++i) { + j = isl_seq_first_non_zero(bmap->eq[i] + 1, total); + if (j < 0) + break; + if (!isl_int_is_one(bmap->eq[i][1 + j]) && + !isl_int_is_negone(bmap->eq[i][1 + j])) + break; + j = isl_seq_first_non_zero(bmap->eq[i] + 1 + j + 1, + total - j - 1); + if (j >= 0) + break; + } + if (i == bmap->n_eq) + has_rational = 0; + } + isl_basic_map_free(bmap); + + return has_rational; +} + +/* Does "map" contain any rational points? + */ +int isl_map_has_rational(__isl_keep isl_map *map) +{ + int i; + int has_rational; + + if (!map) + return -1; + for (i = 0; i < map->n; ++i) { + has_rational = isl_basic_map_has_rational(map->p[i]); + if (has_rational < 0) + return -1; + if (has_rational) + return 1; + } + return 0; +} + +/* Does "set" contain any rational points? + */ +int isl_set_has_rational(__isl_keep isl_set *set) +{ + return isl_map_has_rational(set); +} + /* Is this basic set a parameter domain? */ int isl_basic_set_is_params(__isl_keep isl_basic_set *bset) @@ -909,13 +996,13 @@ struct isl_map *isl_map_copy(struct isl_map *map) return map; } -void isl_basic_map_free(struct isl_basic_map *bmap) +void *isl_basic_map_free(__isl_take isl_basic_map *bmap) { if (!bmap) - return; + return NULL; if (--bmap->ref > 0) - return; + return NULL; isl_ctx_deref(bmap->ctx); free(bmap->div); @@ -925,11 +1012,13 @@ void isl_basic_map_free(struct isl_basic_map *bmap) isl_vec_free(bmap->sample); isl_space_free(bmap->dim); free(bmap); + + return NULL; } -void isl_basic_set_free(struct isl_basic_set *bset) +void *isl_basic_set_free(struct isl_basic_set *bset) { - isl_basic_map_free((struct isl_basic_map *)bset); + return isl_basic_map_free((struct isl_basic_map *)bset); } static int room_for_con(struct isl_basic_map *bmap, unsigned n) @@ -1056,6 +1145,13 @@ int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos) return isl_basic_map_drop_equality((struct isl_basic_map *)bset, pos); } +/* Turn inequality "pos" of "bmap" into an equality. + * + * In particular, we move the inequality in front of the equalities + * and move the last inequality in the position of the moved inequality. + * Note that isl_tab_make_equalities_explicit depends on this particular + * change in the ordering of the constraints. + */ void isl_basic_map_inequality_to_equality( struct isl_basic_map *bmap, unsigned pos) { @@ -1531,6 +1627,9 @@ static __isl_give isl_basic_set *isl_basic_set_swap_vars( unsigned dim; unsigned nparam; + if (!bset) + return NULL; + nparam = isl_basic_set_n_param(bset); dim = isl_basic_set_n_dim(bset); isl_assert(bset->ctx, n <= dim, goto error); @@ -1574,13 +1673,25 @@ struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset) isl_basic_map_set_to_empty((struct isl_basic_map *)bset); } -void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b) +/* Swap divs "a" and "b" in "bmap" (without modifying any of the constraints + * of "bmap"). + */ +static void swap_div(__isl_keep isl_basic_map *bmap, int a, int b) { - int i; - unsigned off = isl_space_dim(bmap->dim, isl_dim_all); isl_int *t = bmap->div[a]; bmap->div[a] = bmap->div[b]; bmap->div[b] = t; +} + +/* Swap divs "a" and "b" in "bmap" and adjust the constraints and + * div definitions accordingly. + */ +void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b) +{ + int i; + unsigned off = isl_space_dim(bmap->dim, isl_dim_all); + + swap_div(bmap, a, b); for (i = 0; i < bmap->n_eq; ++i) isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]); @@ -1594,8 +1705,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) @@ -1607,6 +1718,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; @@ -1623,8 +1738,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) @@ -1633,8 +1748,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) @@ -1737,6 +1852,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. */ @@ -1755,6 +2060,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; @@ -1767,6 +2073,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) { @@ -1912,6 +2225,14 @@ __isl_give isl_basic_map *isl_basic_map_remove_unknown_divs( return bmap; } +/* Remove all divs that are unknown or defined in terms of unknown divs. + */ +__isl_give isl_basic_set *isl_basic_set_remove_unknown_divs( + __isl_take isl_basic_set *bset) +{ + return isl_basic_map_remove_unknown_divs(bset); +} + __isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map) { int i; @@ -2266,21 +2587,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) @@ -2557,18 +2880,20 @@ static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1, __isl_take isl_map *map2) { unsigned flags = 0; - struct isl_map *result; + isl_map *result; int i, j; if (!map1 || !map2) goto error; - if (isl_map_plain_is_empty(map1) && + if ((isl_map_plain_is_empty(map1) || + isl_map_plain_is_universe(map2)) && isl_space_is_equal(map1->dim, map2->dim)) { isl_map_free(map2); return map1; } - if (isl_map_plain_is_empty(map2) && + if ((isl_map_plain_is_empty(map2) || + isl_map_plain_is_universe(map1)) && isl_space_is_equal(map1->dim, map2->dim)) { isl_map_free(map1); return map2; @@ -2600,10 +2925,9 @@ static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1, part = isl_basic_map_intersect( isl_basic_map_copy(map1->p[i]), isl_basic_map_copy(map2->p[j])); - if (isl_basic_map_is_empty(part)) - isl_basic_map_free(part); - else - result = isl_map_add_basic_map(result, part); + if (isl_basic_map_is_empty(part) < 0) + part = isl_basic_map_free(part); + result = isl_map_add_basic_map(result, part); if (!result) goto error; } @@ -2688,6 +3012,8 @@ static __isl_give isl_basic_map *basic_map_space_reset( { isl_space *space; + if (!bmap) + return NULL; if (!isl_space_is_named_or_nested(bmap->dim, type)) return bmap; @@ -2697,8 +3023,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; @@ -2737,22 +3064,30 @@ __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap, res = isl_basic_map_set_rational(res); if (isl_basic_map_plain_is_empty(bmap)) { isl_basic_map_free(bmap); + free(dim_map); 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); } -__isl_give isl_basic_set *isl_basic_set_add(__isl_take isl_basic_set *bset, +__isl_give isl_basic_set *isl_basic_set_add_dims(__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned n) { if (!bset) @@ -2795,7 +3130,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; } @@ -2905,6 +3240,8 @@ __isl_give isl_basic_map *isl_basic_map_move_dims( res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap), bmap->n_div, bmap->n_eq, bmap->n_ineq); bmap = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); + if (!bmap) + goto error; bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos, src_type, src_pos, n); @@ -3030,31 +3367,22 @@ static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap, return res; } -/* Turn the n dimensions of type type, starting at first - * into existentially quantified variables. +/* Insert "n" rows in the divs of "bmap". + * + * The number of columns is not changed, which means that the last + * dimensions of "bmap" are being reintepreted as the new divs. + * The space of "bmap" is not adjusted, however, which means + * that "bmap" is left in an inconsistent state. Removing "n" dimensions + * from the space of "bmap" is the responsibility of the caller. */ -__isl_give isl_basic_map *isl_basic_map_project_out( - __isl_take isl_basic_map *bmap, - enum isl_dim_type type, unsigned first, unsigned n) +static __isl_give isl_basic_map *insert_div_rows(__isl_take isl_basic_map *bmap, + int n) { int i; size_t row_size; isl_int **new_div; isl_int *old; - if (n == 0) - return basic_map_space_reset(bmap, type); - - if (!bmap) - return NULL; - - if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) - return isl_basic_map_remove_dims(bmap, type, first, n); - - isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), - goto error); - - bmap = move_last(bmap, type, first, n); bmap = isl_basic_map_cow(bmap); if (!bmap) return NULL; @@ -3064,10 +3392,10 @@ __isl_give isl_basic_map *isl_basic_map_project_out( bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2, (bmap->extra + n) * (1 + row_size)); if (!bmap->block2.data) - goto error; + return isl_basic_map_free(bmap); new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n); if (!new_div) - goto error; + return isl_basic_map_free(bmap); for (i = 0; i < n; ++i) { new_div[i] = bmap->block2.data + (bmap->extra + i) * (1 + row_size); @@ -3080,6 +3408,34 @@ __isl_give isl_basic_map *isl_basic_map_project_out( bmap->n_div += n; bmap->extra += n; + return bmap; +} + +/* Turn the n dimensions of type type, starting at first + * into existentially quantified variables. + */ +__isl_give isl_basic_map *isl_basic_map_project_out( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + if (n == 0) + return basic_map_space_reset(bmap, type); + + if (!bmap) + return NULL; + + if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) + return isl_basic_map_remove_dims(bmap, type, first, n); + + isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), + goto error); + + bmap = move_last(bmap, type, first, n); + bmap = isl_basic_map_cow(bmap); + bmap = insert_div_rows(bmap, n); + if (!bmap) + return NULL; + bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n); if (!bmap->dim) goto error; @@ -3950,6 +4306,11 @@ int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div) bmap->div[div]); } +int isl_basic_set_add_div_constraints(struct isl_basic_set *bset, unsigned div) +{ + return isl_basic_map_add_div_constraints(bset, div); +} + struct isl_basic_set *isl_basic_map_underlying_set( struct isl_basic_map *bmap) { @@ -3971,6 +4332,7 @@ struct isl_basic_set *isl_basic_map_underlying_set( bmap = isl_basic_map_finalize(bmap); return (struct isl_basic_set *)bmap; error: + isl_basic_map_free(bmap); return NULL; } @@ -4033,10 +4395,12 @@ struct isl_basic_map *isl_basic_map_overlying_set( bmap = isl_basic_map_extend_constraints(bmap, 0, 2 * like->n_div); for (i = 0; i < like->n_div; ++i) { + if (!bmap) + break; if (isl_int_is_zero(bmap->div[i][0])) continue; if (isl_basic_map_add_div_constraints(bmap, i) < 0) - goto error; + bmap = isl_basic_map_free(bmap); } } isl_basic_map_free(like); @@ -4204,14 +4568,26 @@ __isl_give isl_basic_set *isl_basic_set_params(__isl_take isl_basic_set *bset) return bset; } -/* Compute the parameter domain of the given set. +/* Construct a zero-dimensional basic set with the given parameter domain. */ -__isl_give isl_set *isl_set_params(__isl_take isl_set *set) +__isl_give isl_basic_set *isl_basic_set_from_params( + __isl_take isl_basic_set *bset) { isl_space *space; - unsigned n; - - if (isl_set_is_params(set)) + space = isl_basic_set_get_space(bset); + space = isl_space_set_from_params(space); + bset = isl_basic_set_reset_space(bset, space); + return bset; +} + +/* Compute the parameter domain of the given set. + */ +__isl_give isl_set *isl_set_params(__isl_take isl_set *set) +{ + isl_space *space; + unsigned n; + + if (isl_set_is_params(set)) return set; n = isl_set_dim(set, isl_dim_set); @@ -4829,21 +5205,23 @@ error: return NULL; } -void isl_map_free(struct isl_map *map) +void *isl_map_free(struct isl_map *map) { int i; if (!map) - return; + return NULL; if (--map->ref > 0) - return; + return NULL; isl_ctx_deref(map->ctx); for (i = 0; i < map->n; ++i) isl_basic_map_free(map->p[i]); isl_space_free(map->dim); free(map); + + return NULL; } struct isl_map *isl_map_extend(struct isl_map *base, @@ -4992,6 +5370,39 @@ static int remove_if_empty(__isl_keep isl_map *map, int i) return 0; } +/* Perform "fn" on each basic map of "map", where we may not be holding + * the only reference to "map". + * In particular, "fn" should be a semantics preserving operation + * that we want to apply to all copies of "map". We therefore need + * to be careful not to modify "map" in a way that breaks "map" + * in case anything goes wrong. + */ +__isl_give isl_map *isl_map_inline_foreach_basic_map(__isl_take isl_map *map, + __isl_give isl_basic_map *(*fn)(__isl_take isl_basic_map *bmap)) +{ + struct isl_basic_map *bmap; + int i; + + if (!map) + return NULL; + + for (i = map->n - 1; i >= 0; --i) { + bmap = isl_basic_map_copy(map->p[i]); + bmap = fn(bmap); + if (!bmap) + goto error; + isl_basic_map_free(map->p[i]); + map->p[i] = bmap; + if (remove_if_empty(map, i) < 0) + goto error; + } + + return map; +error: + isl_map_free(map); + return NULL; +} + struct isl_map *isl_map_fix_si(struct isl_map *map, enum isl_dim_type type, unsigned pos, int value) { @@ -5098,6 +5509,15 @@ __isl_give isl_basic_map *isl_basic_map_lower_bound_si( return basic_map_bound_si(bmap, type, pos, value, 0); } +/* Constrain the values of the given dimension to be no greater than "value". + */ +__isl_give isl_basic_map *isl_basic_map_upper_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, 1); +} + struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset, unsigned dim, isl_int value) { @@ -5396,58 +5816,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. @@ -5456,7 +5911,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. @@ -5575,35 +6030,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) @@ -5636,19 +6062,33 @@ __isl_give isl_set *isl_set_partial_lexmax( dom, empty); } +/* Compute the lexicographic minimum (or maximum if "max" is set) + * of "bmap" over its domain. + * + * Since we are not interested in the part of the domain space where + * there is no solution, we initialize the domain to those constraints + * of "bmap" that only involve the parameters and the input dimensions. + * This relieves the parametric programming engine from detecting those + * inequalities and transferring them to the context. More importantly, + * it ensures that those inequalities are transferred first and not + * intermixed with inequalities that actually split the domain. + */ __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max) { - struct isl_basic_set *dom = NULL; - isl_space *dom_dim; + int n_div; + int n_out; + isl_basic_map *copy; + isl_basic_set *dom; - if (!bmap) - goto error; - dom_dim = isl_space_domain(isl_space_copy(bmap->dim)); - dom = isl_basic_set_universe(dom_dim); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + n_out = isl_basic_map_dim(bmap, isl_dim_out); + copy = isl_basic_map_copy(bmap); + copy = isl_basic_map_drop_constraints_involving_dims(copy, + isl_dim_div, 0, n_div); + copy = isl_basic_map_drop_constraints_involving_dims(copy, + isl_dim_out, 0, n_out); + dom = isl_basic_map_domain(copy); return isl_basic_map_partial_lexopt(bmap, dom, NULL, max); -error: - isl_basic_map_free(bmap); - return NULL; } __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap) @@ -5671,41 +6111,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); -} - -__isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set) -{ - return (isl_set *)isl_map_lexmax((isl_map *)set); -} - /* Extract the first and only affine expression from list * and then add it to *pwaff with the given dom. * This domain is known to be disjoint from other domains @@ -5719,6 +6124,8 @@ static int update_dim_opt(__isl_take isl_basic_set *dom, isl_pw_aff **pwaff = user; isl_pw_aff *pwaff_i; + if (!list) + goto error; if (isl_aff_list_n_aff(list) != 1) isl_die(ctx, isl_error_internal, "expecting single element list", goto error); @@ -5975,6 +6382,72 @@ error: return NULL; } +/* Given a basic set "bset" that only involves parameters and existentially + * quantified variables, return the index of the first equality + * that only involves parameters. If there is no such equality then + * return bset->n_eq. + * + * This function assumes that isl_basic_set_gauss has been called on "bset". + */ +static int first_parameter_equality(__isl_keep isl_basic_set *bset) +{ + int i, j; + unsigned nparam, n_div; + + if (!bset) + return -1; + + nparam = isl_basic_set_dim(bset, isl_dim_param); + n_div = isl_basic_set_dim(bset, isl_dim_div); + + for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) { + if (!isl_int_is_zero(bset->eq[i][1 + nparam + j])) + ++i; + } + + return i; +} + +/* Compute an explicit representation for the existentially quantified + * variables in "bset" by computing the "minimal value" of the set + * variables. Since there are no set variables, the computation of + * the minimal value essentially computes an explicit representation + * of the non-empty part(s) of "bset". + * + * The input only involves parameters and existentially quantified variables. + * All equalities among parameters have been removed. + * + * Since the existentially quantified variables in the result are in general + * going to be different from those in the input, we first replace + * them by the minimal number of variables based on their equalities. + * This should simplify the parametric integer programming. + */ +static __isl_give isl_set *base_compute_divs(__isl_take isl_basic_set *bset) +{ + isl_morph *morph1, *morph2; + isl_set *set; + unsigned n; + + if (!bset) + return NULL; + if (bset->n_eq == 0) + return isl_basic_set_lexmin(bset); + + morph1 = isl_basic_set_parameter_compression(bset); + bset = isl_morph_basic_set(isl_morph_copy(morph1), bset); + bset = isl_basic_set_lift(bset); + morph2 = isl_basic_set_variable_compression(bset, isl_dim_set); + bset = isl_morph_basic_set(morph2, bset); + n = isl_basic_set_dim(bset, isl_dim_set); + bset = isl_basic_set_project_out(bset, isl_dim_set, 0, n); + + set = isl_basic_set_lexmin(bset); + + set = isl_morph_set(isl_morph_inverse(morph1), set); + + return set; +} + /* Project the given basic set onto its parameter domain, possibly introducing * new, explicit, existential variables in the constraints. * The input has parameters and (possibly implicit) existential variables. @@ -5986,34 +6459,39 @@ error: * among the parameters by performing a variable compression on * the parameters. Afterward, an inverse transformation is performed * and the equalities among the parameters are inserted back in. + * + * The variable compression on the parameters may uncover additional + * equalities that were only implicit before. We therefore check + * if there are any new parameter equalities in the result and + * if so recurse. The removal of parameter equalities is required + * for the parameter compression performed by base_compute_divs. */ static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset) { - int i, j; + int i; struct isl_mat *eq; struct isl_mat *T, *T2; struct isl_set *set; - unsigned nparam, n_div; + unsigned nparam; bset = isl_basic_set_cow(bset); if (!bset) return NULL; if (bset->n_eq == 0) - return isl_basic_set_lexmin(bset); - - isl_basic_set_gauss(bset, NULL); + return base_compute_divs(bset); - nparam = isl_basic_set_dim(bset, isl_dim_param); - n_div = isl_basic_set_dim(bset, isl_dim_div); + bset = isl_basic_set_gauss(bset, NULL); + if (!bset) + return NULL; + if (isl_basic_set_plain_is_empty(bset)) + return isl_set_from_basic_set(bset); - for (i = 0, j = n_div - 1; i < bset->n_eq && j >= 0; --j) { - if (!isl_int_is_zero(bset->eq[i][1 + nparam + j])) - ++i; - } + i = first_parameter_equality(bset); if (i == bset->n_eq) - return isl_basic_set_lexmin(bset); + return base_compute_divs(bset); + nparam = isl_basic_set_dim(bset, isl_dim_param); eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, i, bset->n_eq - i, 0, 1 + nparam); eq = isl_mat_cow(eq); @@ -6027,61 +6505,188 @@ static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset) } bset = basic_set_parameter_preimage(bset, T); - set = isl_basic_set_lexmin(bset); + i = first_parameter_equality(bset); + if (!bset) + set = NULL; + else if (i == bset->n_eq) + set = base_compute_divs(bset); + else + set = parameter_compute_divs(bset); set = set_parameter_preimage(set, T2); set = set_append_equalities(set, eq); return set; } -/* Compute an explicit representation for all the existentially - * quantified variables. - * The input and output dimensions are first turned into parameters. - * compute_divs then returns a map with the same parameters and - * no input or output dimensions and the dimension specification - * is reset to that of the input. +/* Insert the divs from "ls" before those of "bmap". + * + * The number of columns is not changed, which means that the last + * dimensions of "bmap" are being reintepreted as the divs from "ls". + * The caller is responsible for removing the same number of dimensions + * from the space of "bmap". */ -static struct isl_map *compute_divs(struct isl_basic_map *bmap) +static __isl_give isl_basic_map *insert_divs_from_local_space( + __isl_take isl_basic_map *bmap, __isl_keep isl_local_space *ls) { - struct isl_basic_set *bset; - struct isl_set *set; - struct isl_map *map; - isl_space *dim, *orig_dim = NULL; - unsigned nparam; - unsigned n_in; - unsigned n_out; + int i; + int n_div; + int old_n_div; - bmap = isl_basic_map_cow(bmap); + n_div = isl_local_space_dim(ls, isl_dim_div); + if (n_div == 0) + return bmap; + + old_n_div = bmap->n_div; + bmap = insert_div_rows(bmap, n_div); if (!bmap) return NULL; - nparam = isl_basic_map_dim(bmap, isl_dim_param); - n_in = isl_basic_map_dim(bmap, isl_dim_in); - n_out = isl_basic_map_dim(bmap, isl_dim_out); - dim = isl_space_set_alloc(bmap->ctx, nparam + n_in + n_out, 0); - if (!dim) + for (i = 0; i < n_div; ++i) { + isl_seq_cpy(bmap->div[i], ls->div->row[i], ls->div->n_col); + isl_seq_clr(bmap->div[i] + ls->div->n_col, old_n_div); + } + + return bmap; +} + +/* Replace the space of "bmap" by the space and divs of "ls". + * + * If "ls" has any divs, then we simplify the result since we may + * have discovered some additional equalities that could simplify + * the div expressions. + */ +static __isl_give isl_basic_map *basic_replace_space_by_local_space( + __isl_take isl_basic_map *bmap, __isl_take isl_local_space *ls) +{ + int n_div; + + bmap = isl_basic_map_cow(bmap); + if (!bmap || !ls) goto error; - orig_dim = bmap->dim; - bmap->dim = dim; - bset = (struct isl_basic_set *)bmap; + n_div = isl_local_space_dim(ls, isl_dim_div); + bmap = insert_divs_from_local_space(bmap, ls); + if (!bmap) + goto error; - set = parameter_compute_divs(bset); - map = (struct isl_map *)set; - map = isl_map_reset_space(map, orig_dim); + isl_space_free(bmap->dim); + bmap->dim = isl_local_space_get_space(ls); + if (!bmap->dim) + goto error; - return map; + isl_local_space_free(ls); + if (n_div > 0) + bmap = isl_basic_map_simplify(bmap); + bmap = isl_basic_map_finalize(bmap); + return bmap; error: isl_basic_map_free(bmap); + isl_local_space_free(ls); return NULL; } -int isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap) +/* Replace the space of "map" by the space and divs of "ls". + */ +static __isl_give isl_map *replace_space_by_local_space(__isl_take isl_map *map, + __isl_take isl_local_space *ls) { int i; - unsigned off; - if (!bmap) - return -1; + map = isl_map_cow(map); + if (!map || !ls) + goto error; + + for (i = 0; i < map->n; ++i) { + map->p[i] = basic_replace_space_by_local_space(map->p[i], + isl_local_space_copy(ls)); + if (!map->p[i]) + goto error; + } + isl_space_free(map->dim); + map->dim = isl_local_space_get_space(ls); + if (!map->dim) + goto error; + + isl_local_space_free(ls); + return map; +error: + isl_local_space_free(ls); + isl_map_free(map); + return NULL; +} + +/* Compute an explicit representation for the existentially + * quantified variables for which do not know any explicit representation yet. + * + * We first sort the existentially quantified variables so that the + * existentially quantified variables for which we already have an explicit + * representation are placed before those for which we do not. + * The input dimensions, the output dimensions and the existentially + * quantified variables for which we already have an explicit + * representation are then turned into parameters. + * compute_divs returns a map with the same parameters and + * no input or output dimensions and the dimension specification + * is reset to that of the input, including the existentially quantified + * variables for which we already had an explicit representation. + */ +static struct isl_map *compute_divs(struct isl_basic_map *bmap) +{ + struct isl_basic_set *bset; + struct isl_set *set; + struct isl_map *map; + isl_space *dim; + isl_local_space *ls; + unsigned nparam; + unsigned n_in; + unsigned n_out; + unsigned n_known; + int i; + + bmap = isl_basic_map_sort_divs(bmap); + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; + + for (n_known = 0; n_known < bmap->n_div; ++n_known) + if (isl_int_is_zero(bmap->div[n_known][0])) + break; + + nparam = isl_basic_map_dim(bmap, isl_dim_param); + n_in = isl_basic_map_dim(bmap, isl_dim_in); + n_out = isl_basic_map_dim(bmap, isl_dim_out); + dim = isl_space_set_alloc(bmap->ctx, + nparam + n_in + n_out + n_known, 0); + if (!dim) + goto error; + + ls = isl_basic_map_get_local_space(bmap); + ls = isl_local_space_drop_dims(ls, isl_dim_div, + n_known, bmap->n_div - n_known); + if (n_known > 0) { + for (i = n_known; i < bmap->n_div; ++i) + swap_div(bmap, i - n_known, i); + bmap->n_div -= n_known; + bmap->extra -= n_known; + } + bmap = isl_basic_map_reset_space(bmap, dim); + bset = (struct isl_basic_set *)bmap; + + set = parameter_compute_divs(bset); + map = (struct isl_map *)set; + map = replace_space_by_local_space(map, ls); + + return map; +error: + isl_basic_map_free(bmap); + return NULL; +} + +int isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap) +{ + int i; + unsigned off; + + if (!bmap) + return -1; off = isl_space_dim(bmap->dim, isl_dim_all); for (i = 0; i < bmap->n_div; ++i) { @@ -6214,12 +6819,23 @@ error: return NULL; } +/* Return the union of "map1" and "map2", where we assume for now that + * "map1" and "map2" are disjoint. Note that the basic maps inside + * "map1" or "map2" may not be disjoint from each other. + * Also note that this function is also called from isl_map_union, + * which takes care of handling the situation where "map1" and "map2" + * may not be disjoint. + * + * If one of the inputs is empty, we can simply return the other input. + * Similarly, if one of the inputs is universal, then it is equal to the union. + */ static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1, __isl_take isl_map *map2) { int i; unsigned flags = 0; struct isl_map *map = NULL; + int is_universe; if (!map1 || !map2) goto error; @@ -6233,6 +6849,22 @@ static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1, return map1; } + is_universe = isl_map_plain_is_universe(map1); + if (is_universe < 0) + goto error; + if (is_universe) { + isl_map_free(map2); + return map1; + } + + is_universe = isl_map_plain_is_universe(map2); + if (is_universe < 0) + goto error; + if (is_universe) { + isl_map_free(map1); + return map2; + } + isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error); if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) && @@ -6295,25 +6927,20 @@ struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2) isl_map_union((struct isl_map *)set1, (struct isl_map *)set2); } -static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map, - __isl_take isl_set *set) +/* Apply "fn" to pairs of elements from "map" and "set" and collect + * the results. + * + * "map" and "set" are assumed to be compatible and non-NULL. + */ +static __isl_give isl_map *map_intersect_set(__isl_take isl_map *map, + __isl_take isl_set *set, + __isl_give isl_basic_map *fn(__isl_take isl_basic_map *bmap, + __isl_take isl_basic_set *bset)) { unsigned flags = 0; struct isl_map *result; int i, j; - if (!map || !set) - goto error; - - if (!isl_space_match(map->dim, isl_dim_param, set->dim, isl_dim_param)) - isl_die(set->ctx, isl_error_invalid, - "parameters don't match", goto error); - - if (isl_space_dim(set->dim, isl_dim_set) != 0 && - !isl_map_compatible_range(map, set)) - isl_die(set->ctx, isl_error_invalid, - "incompatible spaces", goto error); - if (isl_set_plain_is_universe(set)) { isl_set_free(set); return map; @@ -6325,20 +6952,31 @@ static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map, result = isl_map_alloc_space(isl_space_copy(map->dim), map->n * set->n, flags); - if (!result) - goto error; - for (i = 0; i < map->n; ++i) + for (i = 0; result && i < map->n; ++i) for (j = 0; j < set->n; ++j) { result = isl_map_add_basic_map(result, - isl_basic_map_intersect_range( - isl_basic_map_copy(map->p[i]), - isl_basic_set_copy(set->p[j]))); + fn(isl_basic_map_copy(map->p[i]), + isl_basic_set_copy(set->p[j]))); if (!result) - goto error; + break; } + isl_map_free(map); isl_set_free(set); return result; +} + +static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map, + __isl_take isl_set *set) +{ + if (!map || !set) + goto error; + + if (!isl_map_compatible_range(map, set)) + isl_die(set->ctx, isl_error_invalid, + "incompatible spaces", goto error); + + return map_intersect_set(map, set, &isl_basic_map_intersect_range); error: isl_map_free(map); isl_set_free(set); @@ -6351,11 +6989,28 @@ __isl_give isl_map *isl_map_intersect_range(__isl_take isl_map *map, return isl_map_align_params_map_map_and(map, set, &map_intersect_range); } -struct isl_map *isl_map_intersect_domain( - struct isl_map *map, struct isl_set *set) +static __isl_give isl_map *map_intersect_domain(__isl_take isl_map *map, + __isl_take isl_set *set) +{ + if (!map || !set) + goto error; + + if (!isl_map_compatible_domain(map, set)) + isl_die(set->ctx, isl_error_invalid, + "incompatible spaces", goto error); + + return map_intersect_set(map, set, &isl_basic_map_intersect_domain); +error: + isl_map_free(map); + isl_set_free(set); + return NULL; +} + +__isl_give isl_map *isl_map_intersect_domain(__isl_take isl_map *map, + __isl_take isl_set *set) { - return isl_map_reverse( - isl_map_intersect_range(isl_map_reverse(map), set)); + return isl_map_align_params_map_map_and(map, set, + &map_intersect_domain); } static __isl_give isl_map *map_apply_domain(__isl_take isl_map *map1, @@ -6448,8 +7103,10 @@ struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap) for (i = 0; i < dim; ++i) { int j = isl_basic_map_alloc_equality( (struct isl_basic_map *)bset); - if (j < 0) - goto error; + if (j < 0) { + bset = isl_basic_set_free(bset); + break; + } isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset)); isl_int_set_si(bset->eq[j][1+nparam+i], 1); isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1); @@ -6574,7 +7231,7 @@ error: return NULL; } -__isl_give struct isl_basic_map *basic_map_identity(__isl_take isl_space *dims) +static __isl_give isl_basic_map *basic_map_identity(__isl_take isl_space *dims) { struct isl_basic_map *bmap; unsigned nparam; @@ -7036,10 +7693,13 @@ int isl_basic_map_is_empty(struct isl_basic_map *bmap) if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)) return 1; + if (isl_basic_map_is_universe(bmap)) + return 0; + if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) { struct isl_basic_map *copy = isl_basic_map_copy(bmap); copy = isl_basic_map_remove_redundancies(copy); - empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY); + empty = isl_basic_map_plain_is_empty(copy); isl_basic_map_free(copy); return empty; } @@ -7195,11 +7855,11 @@ __isl_give isl_basic_set *isl_basic_set_expand_divs( isl_die(isl_mat_get_ctx(div), isl_error_invalid, "not an expansion", goto error); + n_div = bset->n_div; bset = isl_basic_map_extend_space(bset, isl_space_copy(bset->dim), - div->n_row - bset->n_div, 0, - 2 * (div->n_row - bset->n_div)); + div->n_row - n_div, 0, + 2 * (div->n_row - n_div)); - n_div = bset->n_div; for (i = n_div; i < div->n_row; ++i) if (isl_basic_set_alloc_div(bset) < 0) goto error; @@ -7251,7 +7911,7 @@ struct isl_basic_map *isl_basic_map_align_divs( struct isl_basic_map *dst, struct isl_basic_map *src) { int i; - unsigned total = isl_space_dim(src->dim, isl_dim_all); + unsigned total; if (!dst || !src) goto error; @@ -7268,6 +7928,7 @@ struct isl_basic_map *isl_basic_map_align_divs( src->n_div, 0, 2 * src->n_div); if (!dst) return NULL; + total = isl_space_dim(src->dim, isl_dim_all); for (i = 0; i < src->n_div; ++i) { int j = find_div(dst, src, i); if (j < 0) { @@ -7455,19 +8116,20 @@ static enum isl_lp_result basic_set_maximal_difference_at( total = isl_basic_map_total_dim(bmap1); ctx = bmap1->ctx; obj = isl_vec_alloc(ctx, 1 + total); + if (!obj) + goto error2; isl_seq_clr(obj->block.data, 1 + total); isl_int_set_si(obj->block.data[1+nparam+pos], 1); isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1); - if (!obj) - goto error; res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one, opt, NULL, NULL); isl_basic_map_free(bmap1); isl_vec_free(obj); return res; error: - isl_basic_map_free(bmap1); isl_basic_map_free(bmap2); +error2: + isl_basic_map_free(bmap1); return isl_lp_error; } @@ -7805,13 +8467,13 @@ static int qsort_constraint_cmp(const void *p1, const void *p2) int l1, l2; unsigned size = isl_min(c1->size, c2->size); - l1 = isl_seq_last_non_zero(c1->c, size); - l2 = isl_seq_last_non_zero(c2->c, size); + l1 = isl_seq_last_non_zero(c1->c + 1, size); + l2 = isl_seq_last_non_zero(c2->c + 1, size); if (l1 != l2) return l1 - l2; - return isl_seq_cmp(c1->c, c2->c, size); + return isl_seq_cmp(c1->c + 1, c2->c + 1, size); } static struct isl_basic_map *isl_basic_map_sort_constraints( @@ -7856,7 +8518,8 @@ struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap) return bmap; bmap = isl_basic_map_remove_redundancies(bmap); bmap = isl_basic_map_sort_constraints(bmap); - ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED); + if (bmap) + ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED); return bmap; } @@ -7921,8 +8584,7 @@ int isl_basic_set_plain_cmp(const __isl_keep isl_basic_set *bset1, return isl_basic_map_plain_cmp(bset1, bset2); } -int isl_set_plain_cmp(const __isl_keep isl_set *set1, - const __isl_keep isl_set *set2) +int isl_set_plain_cmp(__isl_keep isl_set *set1, __isl_keep isl_set *set2) { int i, cmp; @@ -8255,6 +8917,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)); @@ -8822,7 +9489,9 @@ int isl_set_dim_is_bounded(__isl_keep isl_set *set, return isl_map_dim_is_bounded((isl_map *)set, type, pos); } -static int has_bound(__isl_keep isl_map *map, +/* Does "map" have a bound (according to "fn") for any of its basic maps? + */ +static int has_any_bound(__isl_keep isl_map *map, enum isl_dim_type type, unsigned pos, int (*fn)(__isl_keep isl_basic_map *bmap, enum isl_dim_type type, unsigned pos)) @@ -8844,13 +9513,53 @@ static int has_bound(__isl_keep isl_map *map, /* Return 1 if the specified dim is involved in any lower bound. */ +int isl_set_dim_has_any_lower_bound(__isl_keep isl_set *set, + enum isl_dim_type type, unsigned pos) +{ + return has_any_bound(set, type, pos, + &isl_basic_map_dim_has_lower_bound); +} + +/* Return 1 if the specified dim is involved in any upper bound. + */ +int isl_set_dim_has_any_upper_bound(__isl_keep isl_set *set, + enum isl_dim_type type, unsigned pos) +{ + return has_any_bound(set, type, pos, + &isl_basic_map_dim_has_upper_bound); +} + +/* Does "map" have a bound (according to "fn") for all of its basic maps? + */ +static int has_bound(__isl_keep isl_map *map, + enum isl_dim_type type, unsigned pos, + int (*fn)(__isl_keep isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos)) +{ + int i; + + if (!map) + return -1; + + for (i = 0; i < map->n; ++i) { + int bounded; + bounded = fn(map->p[i], type, pos); + if (bounded < 0 || !bounded) + return bounded; + } + + return 1; +} + +/* Return 1 if the specified dim has a lower bound (in each of its basic sets). + */ int isl_set_dim_has_lower_bound(__isl_keep isl_set *set, enum isl_dim_type type, unsigned pos) { return has_bound(set, type, pos, &isl_basic_map_dim_has_lower_bound); } -/* Return 1 if the specified dim is involved in any upper bound. +/* Return 1 if the specified dim has an upper bound (in each of its basic sets). */ int isl_set_dim_has_upper_bound(__isl_keep isl_set *set, enum isl_dim_type type, unsigned pos) @@ -9622,6 +10331,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, @@ -9750,7 +10513,8 @@ __isl_give isl_basic_map *isl_basic_map_from_constraint_matrices( isl_mat_free(eq); isl_mat_free(ineq); - return bmap; + bmap = isl_basic_map_simplify(bmap); + return isl_basic_map_finalize(bmap); error: isl_space_free(dim); isl_mat_free(eq); @@ -9819,6 +10583,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; @@ -9899,6 +10664,9 @@ __isl_give isl_basic_map *isl_basic_map_curry(__isl_take isl_basic_map *bmap) if (!isl_basic_map_can_curry(bmap)) isl_die(bmap->ctx, isl_error_invalid, "basic map cannot be curried", goto error); + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; bmap->dim = isl_space_curry(bmap->dim); if (!bmap->dim) goto error; @@ -9942,47 +10710,122 @@ error: return NULL; } -/* Construct a basic map mapping the domain of the affine expression - * to a one-dimensional range prescribed by the affine expression. +/* Can we apply isl_basic_map_uncurry to "bmap"? + * That is, does it have a nested relation in its domain? */ -__isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff) +int isl_basic_map_can_uncurry(__isl_keep isl_basic_map *bmap) { - int k; - int pos; - isl_local_space *ls; - isl_basic_map *bmap; - - if (!aff) - return NULL; + if (!bmap) + return -1; - ls = isl_aff_get_local_space(aff); - bmap = isl_basic_map_from_local_space(ls); - bmap = isl_basic_map_extend_constraints(bmap, 1, 0); - k = isl_basic_map_alloc_equality(bmap); - if (k < 0) - goto error; + return isl_space_can_uncurry(bmap->dim); +} - pos = isl_basic_map_offset(bmap, isl_dim_out); - isl_seq_cpy(bmap->eq[k], aff->v->el + 1, pos); - isl_int_neg(bmap->eq[k][pos], aff->v->el[0]); - isl_seq_cpy(bmap->eq[k] + pos + 1, aff->v->el + 1 + pos, - aff->v->size - (pos + 1)); +/* Can we apply isl_map_uncurry to "map"? + * That is, does it have a nested relation in its domain? + */ +int isl_map_can_uncurry(__isl_keep isl_map *map) +{ + if (!map) + return -1; - isl_aff_free(aff); - bmap = isl_basic_map_finalize(bmap); - return bmap; -error: - isl_aff_free(aff); - isl_basic_map_free(bmap); - return NULL; + return isl_space_can_uncurry(map->dim); } -/* Construct a map mapping the domain of the affine expression - * to a one-dimensional range prescribed by the affine expression. +/* Given a basic map A -> (B -> C), return the corresponding basic map + * (A -> B) -> C. */ -__isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff) +__isl_give isl_basic_map *isl_basic_map_uncurry(__isl_take isl_basic_map *bmap) { - isl_basic_map *bmap; + + if (!bmap) + return NULL; + + if (!isl_basic_map_can_uncurry(bmap)) + isl_die(bmap->ctx, isl_error_invalid, + "basic map cannot be uncurried", + return isl_basic_map_free(bmap)); + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; + bmap->dim = isl_space_uncurry(bmap->dim); + if (!bmap->dim) + return isl_basic_map_free(bmap); + return bmap; +} + +/* Given a map A -> (B -> C), return the corresponding map + * (A -> B) -> C. + */ +__isl_give isl_map *isl_map_uncurry(__isl_take isl_map *map) +{ + int i; + + if (!map) + return NULL; + + if (!isl_map_can_uncurry(map)) + isl_die(map->ctx, isl_error_invalid, "map cannot be uncurried", + return isl_map_free(map)); + + map = isl_map_cow(map); + if (!map) + return NULL; + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_uncurry(map->p[i]); + if (!map->p[i]) + return isl_map_free(map); + } + + map->dim = isl_space_uncurry(map->dim); + if (!map->dim) + return isl_map_free(map); + + return map; +} + +/* Construct a basic map mapping the domain of the affine expression + * to a one-dimensional range prescribed by the affine expression. + */ +__isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff) +{ + int k; + int pos; + isl_local_space *ls; + isl_basic_map *bmap; + + if (!aff) + return NULL; + + ls = isl_aff_get_local_space(aff); + bmap = isl_basic_map_from_local_space(ls); + bmap = isl_basic_map_extend_constraints(bmap, 1, 0); + k = isl_basic_map_alloc_equality(bmap); + if (k < 0) + goto error; + + pos = isl_basic_map_offset(bmap, isl_dim_out); + isl_seq_cpy(bmap->eq[k], aff->v->el + 1, pos); + isl_int_neg(bmap->eq[k][pos], aff->v->el[0]); + isl_seq_cpy(bmap->eq[k] + pos + 1, aff->v->el + 1 + pos, + aff->v->size - (pos + 1)); + + isl_aff_free(aff); + bmap = isl_basic_map_finalize(bmap); + return bmap; +error: + isl_aff_free(aff); + isl_basic_map_free(bmap); + 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); @@ -10183,31 +11026,59 @@ error: } /* Add a constraint imposing that the value of the first dimension is + * greater than or equal to that of the second. + */ +__isl_give isl_basic_map *isl_basic_map_order_ge(__isl_take isl_basic_map *bmap, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + isl_constraint *c; + isl_local_space *ls; + + if (!bmap) + return NULL; + + if (pos1 >= isl_basic_map_dim(bmap, type1)) + isl_die(bmap->ctx, isl_error_invalid, + "index out of bounds", return isl_basic_map_free(bmap)); + if (pos2 >= isl_basic_map_dim(bmap, type2)) + isl_die(bmap->ctx, isl_error_invalid, + "index out of bounds", return isl_basic_map_free(bmap)); + + if (type1 == type2 && pos1 == pos2) + return bmap; + + ls = isl_local_space_from_space(isl_basic_map_get_space(bmap)); + c = isl_inequality_alloc(ls); + c = isl_constraint_set_coefficient_si(c, type1, pos1, 1); + c = isl_constraint_set_coefficient_si(c, type2, pos2, -1); + bmap = isl_basic_map_add_constraint(bmap, c); + + return bmap; +} + +/* Construct a basic map where the value of the first dimension is * greater than that of the second. */ -__isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map, +static __isl_give isl_basic_map *greator(__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 (!map) + if (!space) return NULL; - if (pos1 >= isl_map_dim(map, type1)) - isl_die(map->ctx, isl_error_invalid, + 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_map_dim(map, type2)) - isl_die(map->ctx, isl_error_invalid, + 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) { - isl_space *space = isl_map_get_space(map); - isl_map_free(map); - return isl_map_empty(space); - } + if (type1 == type2 && pos1 == pos2) + return isl_basic_map_empty(space); - bmap = isl_basic_map_alloc_space(isl_map_get_space(map), 0, 0, 1); + bmap = isl_basic_map_alloc_space(space, 0, 0, 1); i = isl_basic_map_alloc_inequality(bmap); if (i < 0) goto error; @@ -10219,15 +11090,52 @@ __isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map, 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)); - - return map; + return bmap; error: + isl_space_free(space); isl_basic_map_free(bmap); - isl_map_free(map); return NULL; } +/* Add a constraint imposing that the value of the first dimension is + * greater than that of the second. + */ +__isl_give isl_basic_map *isl_basic_map_order_gt(__isl_take isl_basic_map *bmap, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + isl_basic_map *gt; + + gt = greator(isl_basic_map_get_space(bmap), type1, pos1, type2, pos2); + + bmap = isl_basic_map_intersect(bmap, gt); + + return bmap; +} + +/* Add a constraint imposing that the value of the first dimension is + * greater than that of the second. + */ +__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; + + bmap = greator(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 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) { @@ -10275,6 +11183,10 @@ __isl_give isl_aff *isl_basic_set_get_div(__isl_keep isl_basic_set *bset, * are replaced by * * a f + d g + * + * We currently require that "subs" is an integral expression. + * Handling rational expressions may require us to add stride constraints + * as we do in isl_basic_set_preimage_multi_aff. */ __isl_give isl_basic_set *isl_basic_set_substitute( __isl_take isl_basic_set *bset, @@ -10298,6 +11210,9 @@ __isl_give isl_basic_set *isl_basic_set_substitute( if (isl_local_space_dim(subs->ls, isl_dim_div) != 0) isl_die(ctx, isl_error_unsupported, "cannot handle divs yet", goto error); + if (!isl_int_is_one(subs->v->el[0])) + isl_die(ctx, isl_error_invalid, + "can only substitute integer expressions", goto error); pos += isl_basic_set_offset(bset, type); @@ -10366,3 +11281,505 @@ error: isl_set_free(set); return NULL; } + +/* Check if the range of "ma" is compatible with the domain or range + * (depending on "type") of "bmap". + * Return -1 if anything is wrong. + */ +static int check_basic_map_compatible_range_multi_aff( + __isl_keep isl_basic_map *bmap, enum isl_dim_type type, + __isl_keep isl_multi_aff *ma) +{ + int m; + isl_space *ma_space; + + ma_space = isl_multi_aff_get_space(ma); + m = isl_space_tuple_match(bmap->dim, type, ma_space, isl_dim_out); + isl_space_free(ma_space); + if (m >= 0 && !m) + isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, + "spaces don't match", return -1); + return m; +} + +/* Copy the divs from "ma" to "bmap", adding zeros for the "n_before" + * coefficients before the transformed range of dimensions, + * the "n_after" coefficients after the transformed range of dimensions + * and the coefficients of the other divs in "bmap". + */ +static int set_ma_divs(__isl_keep isl_basic_map *bmap, + __isl_keep isl_multi_aff *ma, int n_before, int n_after, int n_div) +{ + int i; + int n_param; + int n_set; + isl_local_space *ls; + + if (n_div == 0) + return 0; + + ls = isl_aff_get_domain_local_space(ma->p[0]); + if (!ls) + return -1; + + n_param = isl_local_space_dim(ls, isl_dim_param); + n_set = isl_local_space_dim(ls, isl_dim_set); + for (i = 0; i < n_div; ++i) { + int o_bmap = 0, o_ls = 0; + + isl_seq_cpy(bmap->div[i], ls->div->row[i], 1 + 1 + n_param); + o_bmap += 1 + 1 + n_param; + o_ls += 1 + 1 + n_param; + isl_seq_clr(bmap->div[i] + o_bmap, n_before); + o_bmap += n_before; + isl_seq_cpy(bmap->div[i] + o_bmap, + ls->div->row[i] + o_ls, n_set); + o_bmap += n_set; + o_ls += n_set; + isl_seq_clr(bmap->div[i] + o_bmap, n_after); + o_bmap += n_after; + isl_seq_cpy(bmap->div[i] + o_bmap, + ls->div->row[i] + o_ls, n_div); + o_bmap += n_div; + o_ls += n_div; + isl_seq_clr(bmap->div[i] + o_bmap, bmap->n_div - n_div); + if (isl_basic_set_add_div_constraints(bmap, i) < 0) + goto error; + } + + isl_local_space_free(ls); + return 0; +error: + isl_local_space_free(ls); + return -1; +} + +/* How many stride constraints does "ma" enforce? + * That is, how many of the affine expressions have a denominator + * different from one? + */ +static int multi_aff_strides(__isl_keep isl_multi_aff *ma) +{ + int i; + int strides = 0; + + for (i = 0; i < ma->n; ++i) + if (!isl_int_is_one(ma->p[i]->v->el[0])) + strides++; + + return strides; +} + +/* For each affine expression in ma of the form + * + * x_i = (f_i y + h_i)/m_i + * + * with m_i different from one, add a constraint to "bmap" + * of the form + * + * f_i y + h_i = m_i alpha_i + * + * with alpha_i an additional existentially quantified variable. + */ +static __isl_give isl_basic_map *add_ma_strides( + __isl_take isl_basic_map *bmap, __isl_keep isl_multi_aff *ma, + int n_before, int n_after) +{ + int i, k; + int div; + int total; + int n_param; + int n_in; + int n_div; + + total = isl_basic_map_total_dim(bmap); + n_param = isl_multi_aff_dim(ma, isl_dim_param); + n_in = isl_multi_aff_dim(ma, isl_dim_in); + n_div = isl_multi_aff_dim(ma, isl_dim_div); + for (i = 0; i < ma->n; ++i) { + int o_bmap = 0, o_ma = 1; + + if (isl_int_is_one(ma->p[i]->v->el[0])) + continue; + div = isl_basic_map_alloc_div(bmap); + k = isl_basic_map_alloc_equality(bmap); + if (div < 0 || k < 0) + goto error; + isl_int_set_si(bmap->div[div][0], 0); + isl_seq_cpy(bmap->eq[k] + o_bmap, + ma->p[i]->v->el + o_ma, 1 + n_param); + o_bmap += 1 + n_param; + o_ma += 1 + n_param; + isl_seq_clr(bmap->eq[k] + o_bmap, n_before); + o_bmap += n_before; + isl_seq_cpy(bmap->eq[k] + o_bmap, + ma->p[i]->v->el + o_ma, n_in); + o_bmap += n_in; + o_ma += n_in; + isl_seq_clr(bmap->eq[k] + o_bmap, n_after); + o_bmap += n_after; + isl_seq_cpy(bmap->eq[k] + o_bmap, + ma->p[i]->v->el + o_ma, n_div); + o_bmap += n_div; + o_ma += n_div; + isl_seq_clr(bmap->eq[k] + o_bmap, 1 + total - o_bmap); + isl_int_neg(bmap->eq[k][1 + total], ma->p[i]->v->el[0]); + total++; + } + + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* Replace the domain or range space (depending on "type) of "space" by "set". + */ +static __isl_give isl_space *isl_space_set(__isl_take isl_space *space, + enum isl_dim_type type, __isl_take isl_space *set) +{ + if (type == isl_dim_in) { + space = isl_space_range(space); + space = isl_space_map_from_domain_and_range(set, space); + } else { + space = isl_space_domain(space); + space = isl_space_map_from_domain_and_range(space, set); + } + + return space; +} + +/* Compute the preimage of the domain or range (depending on "type") + * of "bmap" under the function represented by "ma". + * In other words, plug in "ma" in the domain or range of "bmap". + * The result is a basic map that lives in the same space as "bmap" + * except that the domain or range has been replaced by + * the domain space of "ma". + * + * If bmap is represented by + * + * A(p) + S u + B x + T v + C(divs) >= 0, + * + * where u and x are input and output dimensions if type == isl_dim_out + * while x and v are input and output dimensions if type == isl_dim_in, + * and ma is represented by + * + * x = D(p) + F(y) + G(divs') + * + * then the result is + * + * A(p) + B D(p) + S u + B F(y) + T v + B G(divs') + C(divs) >= 0 + * + * The divs in the input set are similarly adjusted. + * In particular + * + * floor((a_i(p) + s u + b_i x + t v + c_i(divs))/n_i) + * + * becomes + * + * floor((a_i(p) + b_i D(p) + s u + b_i F(y) + t v + + * B_i G(divs') + c_i(divs))/n_i) + * + * If bmap is not a rational map and if F(y) involves any denominators + * + * x_i = (f_i y + h_i)/m_i + * + * then additional constraints are added to ensure that we only + * map back integer points. That is we enforce + * + * f_i y + h_i = m_i alpha_i + * + * with alpha_i an additional existentially quantified variable. + * + * We first copy over the divs from "ma". + * Then we add the modified constraints and divs from "bmap". + * Finally, we add the stride constraints, if needed. + */ +__isl_give isl_basic_map *isl_basic_map_preimage_multi_aff( + __isl_take isl_basic_map *bmap, enum isl_dim_type type, + __isl_take isl_multi_aff *ma) +{ + int i, k; + isl_space *space; + isl_basic_map *res = NULL; + int n_before, n_after, n_div_bmap, n_div_ma; + isl_int f, c1, c2, g; + int rational, strides; + + isl_int_init(f); + isl_int_init(c1); + isl_int_init(c2); + isl_int_init(g); + + ma = isl_multi_aff_align_divs(ma); + if (!bmap || !ma) + goto error; + if (check_basic_map_compatible_range_multi_aff(bmap, type, ma) < 0) + goto error; + + if (type == isl_dim_in) { + n_before = 0; + n_after = isl_basic_map_dim(bmap, isl_dim_out); + } else { + n_before = isl_basic_map_dim(bmap, isl_dim_in); + n_after = 0; + } + n_div_bmap = isl_basic_map_dim(bmap, isl_dim_div); + n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0; + + space = isl_multi_aff_get_domain_space(ma); + space = isl_space_set(isl_basic_map_get_space(bmap), type, space); + rational = isl_basic_map_is_rational(bmap); + strides = rational ? 0 : multi_aff_strides(ma); + res = isl_basic_map_alloc_space(space, n_div_ma + n_div_bmap + strides, + bmap->n_eq + strides, bmap->n_ineq + 2 * n_div_ma); + if (rational) + res = isl_basic_map_set_rational(res); + + for (i = 0; i < n_div_ma + n_div_bmap; ++i) + if (isl_basic_map_alloc_div(res) < 0) + goto error; + + if (set_ma_divs(res, ma, n_before, n_after, n_div_ma) < 0) + goto error; + + for (i = 0; i < bmap->n_eq; ++i) { + k = isl_basic_map_alloc_equality(res); + if (k < 0) + goto error; + isl_seq_preimage(res->eq[k], bmap->eq[i], ma, n_before, + n_after, n_div_ma, n_div_bmap, f, c1, c2, g, 0); + } + + for (i = 0; i < bmap->n_ineq; ++i) { + k = isl_basic_map_alloc_inequality(res); + if (k < 0) + goto error; + isl_seq_preimage(res->ineq[k], bmap->ineq[i], ma, n_before, + n_after, n_div_ma, n_div_bmap, f, c1, c2, g, 0); + } + + for (i = 0; i < bmap->n_div; ++i) { + if (isl_int_is_zero(bmap->div[i][0])) { + isl_int_set_si(res->div[n_div_ma + i][0], 0); + continue; + } + isl_seq_preimage(res->div[n_div_ma + i], bmap->div[i], ma, + n_before, n_after, n_div_ma, n_div_bmap, + f, c1, c2, g, 1); + } + + if (strides) + res = add_ma_strides(res, ma, n_before, n_after); + + isl_int_clear(f); + isl_int_clear(c1); + isl_int_clear(c2); + isl_int_clear(g); + isl_basic_map_free(bmap); + isl_multi_aff_free(ma); + res = isl_basic_set_simplify(res); + return isl_basic_map_finalize(res); +error: + isl_int_clear(f); + isl_int_clear(c1); + isl_int_clear(c2); + isl_int_clear(g); + isl_basic_map_free(bmap); + isl_multi_aff_free(ma); + isl_basic_map_free(res); + return NULL; +} + +/* Compute the preimage of "bset" under the function represented by "ma". + * In other words, plug in "ma" in "bset". The result is a basic set + * that lives in the domain space of "ma". + */ +__isl_give isl_basic_set *isl_basic_set_preimage_multi_aff( + __isl_take isl_basic_set *bset, __isl_take isl_multi_aff *ma) +{ + return isl_basic_map_preimage_multi_aff(bset, isl_dim_set, ma); +} + +/* Check if the range of "ma" is compatible with the domain or range + * (depending on "type") of "map". + * Return -1 if anything is wrong. + */ +static int check_map_compatible_range_multi_aff( + __isl_keep isl_map *map, enum isl_dim_type type, + __isl_keep isl_multi_aff *ma) +{ + int m; + isl_space *ma_space; + + ma_space = isl_multi_aff_get_space(ma); + m = isl_space_tuple_match(map->dim, type, ma_space, isl_dim_out); + isl_space_free(ma_space); + if (m >= 0 && !m) + isl_die(isl_map_get_ctx(map), isl_error_invalid, + "spaces don't match", return -1); + return m; +} + +/* Compute the preimage of the domain or range (depending on "type") + * of "map" under the function represented by "ma". + * In other words, plug in "ma" in the domain or range of "map". + * The result is a map that lives in the same space as "map" + * except that the domain or range has been replaced by + * the domain space of "ma". + * + * The parameters are assumed to have been aligned. + */ +static __isl_give isl_map *map_preimage_multi_aff(__isl_take isl_map *map, + enum isl_dim_type type, __isl_take isl_multi_aff *ma) +{ + int i; + isl_space *space; + + map = isl_map_cow(map); + ma = isl_multi_aff_align_divs(ma); + if (!map || !ma) + goto error; + if (check_map_compatible_range_multi_aff(map, type, ma) < 0) + goto error; + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_preimage_multi_aff(map->p[i], type, + isl_multi_aff_copy(ma)); + if (!map->p[i]) + goto error; + } + + space = isl_multi_aff_get_domain_space(ma); + space = isl_space_set(isl_map_get_space(map), type, space); + + isl_space_free(map->dim); + map->dim = space; + if (!map->dim) + goto error; + + isl_multi_aff_free(ma); + if (map->n > 1) + ISL_F_CLR(map, ISL_MAP_DISJOINT); + ISL_F_CLR(map, ISL_SET_NORMALIZED); + return map; +error: + isl_multi_aff_free(ma); + isl_map_free(map); + return NULL; +} + +/* Compute the preimage of the domain or range (depending on "type") + * of "map" under the function represented by "ma". + * In other words, plug in "ma" in the domain or range of "map". + * The result is a map that lives in the same space as "map" + * except that the domain or range has been replaced by + * the domain space of "ma". + */ +__isl_give isl_map *isl_map_preimage_multi_aff(__isl_take isl_map *map, + enum isl_dim_type type, __isl_take isl_multi_aff *ma) +{ + if (!map || !ma) + goto error; + + if (isl_space_match(map->dim, isl_dim_param, ma->space, isl_dim_param)) + return map_preimage_multi_aff(map, type, ma); + + if (!isl_space_has_named_params(map->dim) || + !isl_space_has_named_params(ma->space)) + isl_die(map->ctx, isl_error_invalid, + "unaligned unnamed parameters", goto error); + map = isl_map_align_params(map, isl_multi_aff_get_space(ma)); + ma = isl_multi_aff_align_params(ma, isl_map_get_space(map)); + + return map_preimage_multi_aff(map, type, ma); +error: + isl_multi_aff_free(ma); + return isl_map_free(map); +} + +/* Compute the preimage of "set" under the function represented by "ma". + * In other words, plug in "ma" "set". The result is a set + * that lives in the domain space of "ma". + */ +__isl_give isl_set *isl_set_preimage_multi_aff(__isl_take isl_set *set, + __isl_take isl_multi_aff *ma) +{ + return isl_map_preimage_multi_aff(set, isl_dim_set, ma); +} + +/* Compute the preimage of the domain of "map" under the function + * represented by "ma". + * In other words, plug in "ma" in the domain of "map". + * The result is a map that lives in the same space as "map" + * except that the domain has been replaced by the domain space of "ma". + */ +__isl_give isl_map *isl_map_preimage_domain_multi_aff(__isl_take isl_map *map, + __isl_take isl_multi_aff *ma) +{ + return isl_map_preimage_multi_aff(map, isl_dim_in, ma); +} + +/* Compute the preimage of "set" under the function represented by "pma". + * In other words, plug in "pma" in "set. The result is a set + * that lives in the domain space of "pma". + */ +static __isl_give isl_set *set_preimage_pw_multi_aff(__isl_take isl_set *set, + __isl_take isl_pw_multi_aff *pma) +{ + int i; + isl_set *res; + + if (!pma) + goto error; + + if (pma->n == 0) { + isl_pw_multi_aff_free(pma); + res = isl_set_empty(isl_set_get_space(set)); + isl_set_free(set); + return res; + } + + res = isl_set_preimage_multi_aff(isl_set_copy(set), + isl_multi_aff_copy(pma->p[0].maff)); + res = isl_set_intersect(res, isl_set_copy(pma->p[0].set)); + + for (i = 1; i < pma->n; ++i) { + isl_set *res_i; + + res_i = isl_set_preimage_multi_aff(isl_set_copy(set), + isl_multi_aff_copy(pma->p[i].maff)); + res_i = isl_set_intersect(res_i, isl_set_copy(pma->p[i].set)); + res = isl_set_union(res, res_i); + } + + isl_pw_multi_aff_free(pma); + isl_set_free(set); + return res; +error: + isl_pw_multi_aff_free(pma); + isl_set_free(set); + return NULL; +} + +__isl_give isl_set *isl_set_preimage_pw_multi_aff(__isl_take isl_set *set, + __isl_take isl_pw_multi_aff *pma) +{ + if (!set || !pma) + goto error; + + if (isl_space_match(set->dim, isl_dim_param, pma->dim, isl_dim_param)) + return set_preimage_pw_multi_aff(set, pma); + + if (!isl_space_has_named_params(set->dim) || + !isl_space_has_named_params(pma->dim)) + isl_die(set->ctx, isl_error_invalid, + "unaligned unnamed parameters", goto error); + set = isl_set_align_params(set, isl_pw_multi_aff_get_space(pma)); + pma = isl_pw_multi_aff_align_params(pma, isl_set_get_space(set)); + + return set_preimage_pw_multi_aff(set, pma); +error: + isl_pw_multi_aff_free(pma); + return isl_set_free(set); +}