X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map_simplify.c;h=b3ceb80a58e542f36f7dc0938481718042c28a96;hb=32aabe2c05cbaa2df5907aee48d1874936266a29;hp=08c4eb88570a4075a76e2076377e45b0b150db99;hpb=f53869239275299d045f11ddbf71c9f590e73979;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map_simplify.c b/isl_map_simplify.c index 08c4eb8..b3ceb80 100644 --- a/isl_map_simplify.c +++ b/isl_map_simplify.c @@ -1,10 +1,12 @@ /* * Copyright 2008-2009 Katholieke Universiteit Leuven + * Copyright 2012 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 Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France */ #include @@ -370,6 +372,67 @@ struct isl_basic_set *isl_basic_set_normalize_constraints( (struct isl_basic_map *)bset); } +/* Remove any common factor in numerator and denominator of the div expression, + * not taking into account the constant term. + * That is, if the div is of the form + * + * floor((a + m f(x))/(m d)) + * + * then replace it by + * + * floor((floor(a/m) + f(x))/d) + * + * The difference {a/m}/d in the argument satisfies 0 <= {a/m}/d < 1/d + * and can therefore not influence the result of the floor. + */ +static void normalize_div_expression(__isl_keep isl_basic_map *bmap, int div) +{ + unsigned total = isl_basic_map_total_dim(bmap); + isl_ctx *ctx = bmap->ctx; + + if (isl_int_is_zero(bmap->div[div][0])) + return; + isl_seq_gcd(bmap->div[div] + 2, total, &ctx->normalize_gcd); + isl_int_gcd(ctx->normalize_gcd, ctx->normalize_gcd, bmap->div[div][0]); + if (isl_int_is_one(ctx->normalize_gcd)) + return; + isl_int_fdiv_q(bmap->div[div][1], bmap->div[div][1], + ctx->normalize_gcd); + isl_int_divexact(bmap->div[div][0], bmap->div[div][0], + ctx->normalize_gcd); + isl_seq_scale_down(bmap->div[div] + 2, bmap->div[div] + 2, + ctx->normalize_gcd, total); +} + +/* Remove any common factor in numerator and denominator of a div expression, + * not taking into account the constant term. + * That is, look for any div of the form + * + * floor((a + m f(x))/(m d)) + * + * and replace it by + * + * floor((floor(a/m) + f(x))/d) + * + * The difference {a/m}/d in the argument satisfies 0 <= {a/m}/d < 1/d + * and can therefore not influence the result of the floor. + */ +static __isl_give isl_basic_map *normalize_div_expressions( + __isl_take isl_basic_map *bmap) +{ + int i; + + if (!bmap) + return NULL; + if (bmap->n_div == 0) + return bmap; + + for (i = 0; i < bmap->n_div; ++i) + normalize_div_expression(bmap, i); + + return bmap; +} + /* Assumes divs have been ordered if keep_divs is set. */ static void eliminate_var_using_equality(struct isl_basic_map *bmap, @@ -418,10 +481,11 @@ static void eliminate_var_using_equality(struct isl_basic_map *bmap, * and we can keep the definition as long as the result * is still ordered. */ - if (last_div == -1 || (keep_divs && last_div < k)) + if (last_div == -1 || (keep_divs && last_div < k)) { isl_seq_elim(bmap->div[k]+1, eq, 1+pos, 1+total, &bmap->div[k][0]); - else + normalize_div_expression(bmap, k); + } else isl_seq_clr(bmap->div[k], 1 + total); ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED); } @@ -581,6 +645,8 @@ struct isl_basic_map *isl_basic_map_gauss( isl_int_set_si(bmap->div[div][1+1+last_var], 0); isl_int_set(bmap->div[div][0], bmap->eq[done][1+last_var]); + if (progress) + *progress = 1; ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED); } } @@ -651,6 +717,7 @@ static struct isl_basic_map *remove_duplicate_divs( unsigned total; struct isl_ctx *ctx; + bmap = isl_basic_map_order_divs(bmap); if (!bmap || bmap->n_div <= 1) return bmap; @@ -700,7 +767,7 @@ static struct isl_basic_map *remove_duplicate_divs( k = elim_for[l] - 1; isl_int_set_si(eq.data[1+total_var+k], -1); isl_int_set_si(eq.data[1+total_var+l], 1); - eliminate_div(bmap, eq.data, l, 0); + eliminate_div(bmap, eq.data, l, 1); isl_int_set_si(eq.data[1+total_var+k], 0); isl_int_set_si(eq.data[1+total_var+l], 0); } @@ -975,9 +1042,39 @@ static int ok_to_set_div_from_bound(struct isl_basic_map *bmap, return 1; } +/* Would an expression for div "div" based on inequality "ineq" of "bmap" + * be a better expression than the current one? + * + * If we do not have any expression yet, then any expression would be better. + * Otherwise we check if the last variable involved in the inequality + * (disregarding the div that it would define) is in an earlier position + * than the last variable involved in the current div expression. + */ +static int better_div_constraint(__isl_keep isl_basic_map *bmap, + int div, int ineq) +{ + unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all); + int last_div; + int last_ineq; + + if (isl_int_is_zero(bmap->div[div][0])) + return 1; + + if (isl_seq_last_non_zero(bmap->ineq[ineq] + total + div + 1, + bmap->n_div - (div + 1)) >= 0) + return 0; + + last_ineq = isl_seq_last_non_zero(bmap->ineq[ineq], total + div); + last_div = isl_seq_last_non_zero(bmap->div[div] + 1, + total + bmap->n_div); + + return last_ineq < last_div; +} + /* Given two constraints "k" and "l" that are opposite to each other, * except for the constant term, check if we can use them - * to obtain an expression for one of the hitherto unknown divs. + * to obtain an expression for one of the hitherto unknown divs or + * a "better" expression for a div for which we already have an expression. * "sum" is the sum of the constant terms of the constraints. * If this sum is strictly smaller than the coefficient of one * of the divs, then this pair can be used define the div. @@ -993,12 +1090,12 @@ static struct isl_basic_map *check_for_div_constraints( unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all); for (i = 0; i < bmap->n_div; ++i) { - if (!isl_int_is_zero(bmap->div[i][0])) - continue; if (isl_int_is_zero(bmap->ineq[k][total + i])) continue; if (isl_int_abs_ge(sum, bmap->ineq[k][total + i])) continue; + if (!better_div_constraint(bmap, i, k)) + continue; if (!ok_to_set_div_from_bound(bmap, i, k)) break; if (isl_int_is_pos(bmap->ineq[k][total + i])) @@ -1084,6 +1181,89 @@ static struct isl_basic_map *remove_duplicate_constraints( } +/* Eliminate knowns divs from constraints where they appear with + * a (positive or negative) unit coefficient. + * + * That is, replace + * + * floor(e/m) + f >= 0 + * + * by + * + * e + m f >= 0 + * + * and + * + * -floor(e/m) + f >= 0 + * + * by + * + * -e + m f + m - 1 >= 0 + * + * The first conversion is valid because floor(e/m) >= -f is equivalent + * to e/m >= -f because -f is an integral expression. + * The second conversion follows from the fact that + * + * -floor(e/m) = ceil(-e/m) = floor((-e + m - 1)/m) + * + * + * We skip integral divs, i.e., those with denominator 1, as we would + * risk eliminating the div from the div constraints. We do not need + * to handle those divs here anyway since the div constraints will turn + * out to form an equality and this equality can then be use to eliminate + * the div from all constraints. + */ +static __isl_give isl_basic_map *eliminate_unit_divs( + __isl_take isl_basic_map *bmap, int *progress) +{ + int i, j; + isl_ctx *ctx; + unsigned total; + + if (!bmap) + return NULL; + + ctx = isl_basic_map_get_ctx(bmap); + total = 1 + isl_space_dim(bmap->dim, isl_dim_all); + + for (i = 0; i < bmap->n_div; ++i) { + if (isl_int_is_zero(bmap->div[i][0])) + continue; + if (isl_int_is_one(bmap->div[i][0])) + continue; + for (j = 0; j < bmap->n_ineq; ++j) { + int s; + + if (!isl_int_is_one(bmap->ineq[j][total + i]) && + !isl_int_is_negone(bmap->ineq[j][total + i])) + continue; + + *progress = 1; + + s = isl_int_sgn(bmap->ineq[j][total + i]); + isl_int_set_si(bmap->ineq[j][total + i], 0); + if (s < 0) + isl_seq_combine(bmap->ineq[j], + ctx->negone, bmap->div[i] + 1, + bmap->div[i][0], bmap->ineq[j], + total + bmap->n_div); + else + isl_seq_combine(bmap->ineq[j], + ctx->one, bmap->div[i] + 1, + bmap->div[i][0], bmap->ineq[j], + total + bmap->n_div); + if (s < 0) { + isl_int_add(bmap->ineq[j][0], + bmap->ineq[j][0], bmap->div[i][0]); + isl_int_sub_ui(bmap->ineq[j][0], + bmap->ineq[j][0], 1); + } + } + } + + return bmap; +} + struct isl_basic_map *isl_basic_map_simplify(struct isl_basic_map *bmap) { int progress = 1; @@ -1091,8 +1271,14 @@ struct isl_basic_map *isl_basic_map_simplify(struct isl_basic_map *bmap) return NULL; while (progress) { progress = 0; + if (!bmap) + break; + if (isl_basic_map_plain_is_empty(bmap)) + break; bmap = isl_basic_map_normalize_constraints(bmap); + bmap = normalize_div_expressions(bmap); bmap = remove_duplicate_divs(bmap, &progress); + bmap = eliminate_unit_divs(bmap, &progress); bmap = eliminate_divs_eq(bmap, &progress); bmap = eliminate_divs_ineq(bmap, &progress); bmap = isl_basic_map_gauss(bmap, &progress); @@ -1146,6 +1332,12 @@ int isl_basic_map_is_div_constraint(__isl_keep isl_basic_map *bmap, return 1; } +int isl_basic_set_is_div_constraint(__isl_keep isl_basic_set *bset, + isl_int *constraint, unsigned div) +{ + return isl_basic_map_is_div_constraint(bset, constraint, div); +} + /* If the only constraints a div d=floor(f/m) * appears in are its two defining constraints @@ -1171,9 +1363,12 @@ static int div_is_redundant(struct isl_basic_map *bmap, int div) return 0; } - for (i = 0; i < bmap->n_div; ++i) + for (i = 0; i < bmap->n_div; ++i) { + if (isl_int_is_zero(bmap->div[i][0])) + continue; if (!isl_int_is_zero(bmap->div[i][1+pos])) return 0; + } return 1; } @@ -1258,6 +1453,9 @@ static struct isl_basic_map *remove_dependent_vars(struct isl_basic_map *bmap, { int i; + if (!bmap) + return NULL; + for (i = 0; i < bmap->n_div; ++i) { if (isl_int_is_zero(bmap->div[i][0])) continue; @@ -1288,6 +1486,8 @@ struct isl_basic_map *isl_basic_map_eliminate_vars( bmap = isl_basic_map_cow(bmap); for (d = pos + n - 1; d >= 0 && d >= pos; --d) bmap = remove_dependent_vars(bmap, d); + if (!bmap) + return NULL; for (d = pos + n - 1; d >= 0 && d >= total - bmap->n_div && d >= pos; --d) @@ -1369,6 +1569,49 @@ struct isl_basic_set *isl_basic_set_eliminate_vars( (struct isl_basic_map *)bset, pos, n); } +/* Eliminate the specified n dimensions starting at first from the + * constraints, without removing the dimensions from the space. + * If the set is rational, the dimensions are eliminated using Fourier-Motzkin. + * Otherwise, they are projected out and the original space is restored. + */ +__isl_give isl_basic_map *isl_basic_map_eliminate( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + isl_space *space; + + if (!bmap) + return NULL; + if (n == 0) + return bmap; + + if (first + n > isl_basic_map_dim(bmap, type) || first + n < first) + isl_die(bmap->ctx, isl_error_invalid, + "index out of bounds", goto error); + + if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) { + first += isl_basic_map_offset(bmap, type) - 1; + bmap = isl_basic_map_eliminate_vars(bmap, first, n); + return isl_basic_map_finalize(bmap); + } + + space = isl_basic_map_get_space(bmap); + bmap = isl_basic_map_project_out(bmap, type, first, n); + bmap = isl_basic_map_insert_dims(bmap, type, first, n); + bmap = isl_basic_map_reset_space(bmap, space); + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_basic_set *isl_basic_set_eliminate( + __isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return isl_basic_map_eliminate(bset, type, first, n); +} + /* Don't assume equalities are in order, because align_divs * may have changed the order of the divs. */ @@ -1506,11 +1749,181 @@ error: return bset; } +/* Does the (linear part of a) constraint "c" involve any of the "len" + * "relevant" dimensions? + */ +static int is_related(isl_int *c, int len, int *relevant) +{ + int i; + + for (i = 0; i < len; ++i) { + if (!relevant[i]) + continue; + if (!isl_int_is_zero(c[i])) + return 1; + } + + return 0; +} + +/* Drop constraints from "bset" that do not involve any of + * the dimensions marked "relevant". + */ +static __isl_give isl_basic_set *drop_unrelated_constraints( + __isl_take isl_basic_set *bset, int *relevant) +{ + int i, dim; + + dim = isl_basic_set_dim(bset, isl_dim_set); + for (i = 0; i < dim; ++i) + if (!relevant[i]) + break; + if (i >= dim) + return bset; + + for (i = bset->n_eq - 1; i >= 0; --i) + if (!is_related(bset->eq[i] + 1, dim, relevant)) + isl_basic_set_drop_equality(bset, i); + + for (i = bset->n_ineq - 1; i >= 0; --i) + if (!is_related(bset->ineq[i] + 1, dim, relevant)) + isl_basic_set_drop_inequality(bset, i); + + return bset; +} + +/* Update the groups in "group" based on the (linear part of a) constraint "c". + * + * In particular, for any variable involved in the constraint, + * find the actual group id from before and replace the group + * of the corresponding variable by the minimal group of all + * the variables involved in the constraint considered so far + * (if this minimum is smaller) or replace the minimum by this group + * (if the minimum is larger). + * + * At the end, all the variables in "c" will (indirectly) point + * to the minimal of the groups that they referred to originally. + */ +static void update_groups(int dim, int *group, isl_int *c) +{ + int j; + int min = dim; + + for (j = 0; j < dim; ++j) { + if (isl_int_is_zero(c[j])) + continue; + while (group[j] >= 0 && group[group[j]] != group[j]) + group[j] = group[group[j]]; + if (group[j] == min) + continue; + if (group[j] < min) { + if (min >= 0 && min < dim) + group[min] = group[j]; + min = group[j]; + } else + group[group[j]] = min; + } +} + +/* Drop constraints from "context" that are irrelevant for computing + * the gist of "bset". + * + * In particular, drop constraints in variables that are not related + * to any of the variables involved in the constraints of "bset" + * in the sense that there is no sequence of constraints that connects them. + * + * We construct groups of variables that collect variables that + * (indirectly) appear in some common constraint of "context". + * Each group is identified by the first variable in the group, + * except for the special group of variables that appear in "bset" + * (or are related to those variables), which is identified by -1. + * If group[i] is equal to i (or -1), then the group of i is i (or -1), + * otherwise the group of i is the group of group[i]. + * + * We first initialize the -1 group with the variables that appear in "bset". + * Then we initialize groups for the remaining variables. + * Then we iterate over the constraints of "context" and update the + * group of the variables in the constraint by the smallest group. + * Finally, we resolve indirect references to groups by running over + * the variables. + * + * After computing the groups, we drop constraints that do not involve + * any variables in the -1 group. + */ +static __isl_give isl_basic_set *drop_irrelevant_constraints( + __isl_take isl_basic_set *context, __isl_keep isl_basic_set *bset) +{ + isl_ctx *ctx; + int *group; + int dim; + int i, j; + int last; + + if (!context || !bset) + return isl_basic_set_free(context); + + dim = isl_basic_set_dim(bset, isl_dim_set); + ctx = isl_basic_set_get_ctx(bset); + group = isl_calloc_array(ctx, int, dim); + + if (!group) + goto error; + + for (i = 0; i < dim; ++i) { + for (j = 0; j < bset->n_eq; ++j) + if (!isl_int_is_zero(bset->eq[j][1 + i])) + break; + if (j < bset->n_eq) { + group[i] = -1; + continue; + } + for (j = 0; j < bset->n_ineq; ++j) + if (!isl_int_is_zero(bset->ineq[j][1 + i])) + break; + if (j < bset->n_ineq) + group[i] = -1; + } + + last = -1; + for (i = 0; i < dim; ++i) + if (group[i] >= 0) + last = group[i] = i; + if (last < 0) { + free(group); + return context; + } + + for (i = 0; i < context->n_eq; ++i) + update_groups(dim, group, context->eq[i] + 1); + for (i = 0; i < context->n_ineq; ++i) + update_groups(dim, group, context->ineq[i] + 1); + + for (i = 0; i < dim; ++i) + if (group[i] >= 0) + group[i] = group[group[i]]; + + for (i = 0; i < dim; ++i) + group[i] = group[i] == -1; + + context = drop_unrelated_constraints(context, group); + + free(group); + return context; +error: + free(group); + return isl_basic_set_free(context); +} + /* Remove all information from bset that is redundant in the context * of context. Both bset and context are assumed to be full-dimensional. * - * We first * remove the inequalities from "bset" + * We first remove the inequalities from "bset" * that are obviously redundant with respect to some inequality in "context". + * Then we remove those constraints from "context" that have become + * irrelevant for computing the gist of "bset". + * Note that this removal of constraints cannot be replaced by + * a factorization because factors in "bset" may still be connected + * to each other through constraints in "context". * * If there are any inequalities left, we construct a tableau for * the context and then add the inequalities of "bset". @@ -1551,10 +1964,18 @@ static __isl_give isl_basic_set *uset_gist_full(__isl_take isl_basic_set *bset, if (bset->n_ineq == 0) goto done; + context = drop_irrelevant_constraints(context, bset); + if (!context) + goto error; + if (isl_basic_set_is_universe(context)) { + isl_basic_set_free(context); + return bset; + } + context_ineq = context->n_ineq; combined = isl_basic_set_cow(isl_basic_set_copy(context)); combined = isl_basic_set_extend_constraints(combined, 0, bset->n_ineq); - tab = isl_tab_from_basic_set(combined); + tab = isl_tab_from_basic_set(combined, 0); for (i = 0; i < context_ineq; ++i) if (isl_tab_freeze_constraint(tab, i) < 0) goto error; @@ -1618,6 +2039,10 @@ error: * redundant in the context of the equalities and inequalities of * context are removed. * + * First of all, we drop those constraints from "context" + * that are irrelevant for computing the gist of "bset". + * Alternatively, we could factorize the intersection of "context" and "bset". + * * We first compute the integer affine hull of the intersection, * compute the gist inside this affine hull and then add back * those equalities that are not implied by the context. @@ -1641,6 +2066,8 @@ static __isl_give isl_basic_set *uset_gist(__isl_take isl_basic_set *bset, if (!bset || !context) goto error; + context = drop_irrelevant_constraints(context, bset); + bset = isl_basic_set_intersect(bset, isl_basic_set_copy(context)); if (isl_basic_set_plain_is_empty(bset)) { isl_basic_set_free(context); @@ -1720,6 +2147,8 @@ static struct isl_basic_map *normalize_divs_in_context( for (i = 0; i < context->n_eq; ++i) { int k; k = isl_basic_map_alloc_equality(bmap); + if (k < 0) + return isl_basic_map_free(bmap); isl_seq_cpy(bmap->eq[k], context->eq[i], 1 + total_context); isl_seq_clr(bmap->eq[k] + 1 + total_context, isl_basic_map_total_dim(bmap) - total_context); @@ -1743,10 +2172,8 @@ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap, return bmap; } if (isl_basic_map_plain_is_empty(context)) { - isl_space *dim = isl_space_copy(bmap->dim); - isl_basic_map_free(context); isl_basic_map_free(bmap); - return isl_basic_map_universe(dim); + return context; } if (isl_basic_map_plain_is_empty(bmap)) { isl_basic_map_free(context); @@ -1755,6 +2182,8 @@ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap, bmap = isl_basic_map_remove_redundancies(bmap); context = isl_basic_map_remove_redundancies(context); + if (!context) + goto error; if (context->n_eq) bmap = normalize_divs_in_context(bmap, context); @@ -1784,10 +2213,8 @@ __isl_give isl_map *isl_map_gist_basic_map(__isl_take isl_map *map, goto error;; if (isl_basic_map_plain_is_empty(context)) { - isl_space *dim = isl_space_copy(map->dim); - isl_basic_map_free(context); isl_map_free(map); - return isl_map_universe(dim); + return isl_map_from_basic_map(context); } context = isl_basic_map_remove_redundancies(context); @@ -1796,8 +2223,8 @@ __isl_give isl_map *isl_map_gist_basic_map(__isl_take isl_map *map, goto error;; isl_assert(map->ctx, isl_space_is_equal(map->dim, context->dim), goto error); map = isl_map_compute_divs(map); - for (i = 0; i < map->n; ++i) - context = isl_basic_map_align_divs(context, map->p[i]); + if (!map) + goto error; for (i = map->n - 1; i >= 0; --i) { map->p[i] = isl_basic_map_gist(map->p[i], isl_basic_map_copy(context)); @@ -1819,11 +2246,49 @@ error: return NULL; } +/* Return a map that has the same intersection with "context" as "map" + * and that as "simple" as possible. + * + * If "map" is already the universe, then we cannot make it any simpler. + * Similarly, if "context" is the universe, then we cannot exploit it + * to simplify "map" + * If "map" and "context" are identical to each other, then we can + * return the corresponding universe. + * + * If none of these cases apply, we have to work a bit harder. + */ static __isl_give isl_map *map_gist(__isl_take isl_map *map, __isl_take isl_map *context) { + int equal; + int is_universe; + + is_universe = isl_map_plain_is_universe(map); + if (is_universe >= 0 && !is_universe) + is_universe = isl_map_plain_is_universe(context); + if (is_universe < 0) + goto error; + if (is_universe) { + isl_map_free(context); + return map; + } + + equal = isl_map_plain_is_equal(map, context); + if (equal < 0) + goto error; + if (equal) { + isl_map *res = isl_map_universe(isl_map_get_space(map)); + isl_map_free(map); + isl_map_free(context); + return res; + } + context = isl_map_compute_divs(context); return isl_map_gist_basic_map(map, isl_map_simple_hull(context)); +error: + isl_map_free(map); + isl_map_free(context); + return NULL; } __isl_give isl_map *isl_map_gist(__isl_take isl_map *map, @@ -1846,6 +2311,15 @@ __isl_give isl_set *isl_set_gist_basic_set(__isl_take isl_set *set, (struct isl_basic_map *)context); } +__isl_give isl_set *isl_set_gist_params_basic_set(__isl_take isl_set *set, + __isl_take isl_basic_set *context) +{ + isl_space *space = isl_set_get_space(set); + isl_basic_set *dom_context = isl_basic_set_universe(space); + dom_context = isl_basic_set_intersect_params(dom_context, context); + return isl_set_gist_basic_set(set, dom_context); +} + __isl_give isl_set *isl_set_gist(__isl_take isl_set *set, __isl_take isl_set *context) { @@ -1853,6 +2327,22 @@ __isl_give isl_set *isl_set_gist(__isl_take isl_set *set, (struct isl_map *)context); } +__isl_give isl_map *isl_map_gist_domain(__isl_take isl_map *map, + __isl_take isl_set *context) +{ + isl_map *map_context = isl_map_universe(isl_map_get_space(map)); + map_context = isl_map_intersect_domain(map_context, context); + return isl_map_gist(map, map_context); +} + +__isl_give isl_map *isl_map_gist_range(__isl_take isl_map *map, + __isl_take isl_set *context) +{ + isl_map *map_context = isl_map_universe(isl_map_get_space(map)); + map_context = isl_map_intersect_range(map_context, context); + return isl_map_gist(map, map_context); +} + __isl_give isl_map *isl_map_gist_params(__isl_take isl_map *map, __isl_take isl_set *context) { @@ -1944,16 +2434,56 @@ int isl_basic_set_plain_is_disjoint(__isl_keep isl_basic_set *bset1, (struct isl_basic_map *)bset2); } +/* Are "map1" and "map2" obviously disjoint? + * + * If one of them is empty or if they live in different spaces (ignoring + * parameters), then they are clearly disjoint. + * + * If they have different parameters, then we skip any further tests. + * + * If they are obviously equal, but not obviously empty, then we will + * not be able to detect if they are disjoint. + * + * Otherwise we check if each basic map in "map1" is obviously disjoint + * from each basic map in "map2". + */ int isl_map_plain_is_disjoint(__isl_keep isl_map *map1, __isl_keep isl_map *map2) { int i, j; + int disjoint; + int intersect; + int match; if (!map1 || !map2) return -1; - if (isl_map_plain_is_equal(map1, map2)) - return 0; + disjoint = isl_map_plain_is_empty(map1); + if (disjoint < 0 || disjoint) + return disjoint; + + disjoint = isl_map_plain_is_empty(map2); + if (disjoint < 0 || disjoint) + return disjoint; + + match = isl_space_tuple_match(map1->dim, isl_dim_in, + map2->dim, isl_dim_in); + if (match < 0 || !match) + return match < 0 ? -1 : 1; + + match = isl_space_tuple_match(map1->dim, isl_dim_out, + map2->dim, isl_dim_out); + if (match < 0 || !match) + return match < 0 ? -1 : 1; + + match = isl_space_match(map1->dim, isl_dim_param, + map2->dim, isl_dim_param); + if (match < 0 || !match) + return match < 0 ? -1 : 0; + + intersect = isl_map_plain_is_equal(map1, map2); + if (intersect < 0 || intersect) + return intersect < 0 ? -1 : 0; for (i = 0; i < map1->n; ++i) { for (j = 0; j < map2->n; ++j) { @@ -1966,6 +2496,46 @@ int isl_map_plain_is_disjoint(__isl_keep isl_map *map1, return 1; } +/* Are "map1" and "map2" disjoint? + * + * They are disjoint if they are "obviously disjoint" or if one of them + * is empty. Otherwise, they are not disjoint if one of them is universal. + * If none of these cases apply, we compute the intersection and see if + * the result is empty. + */ +int isl_map_is_disjoint(__isl_keep isl_map *map1, __isl_keep isl_map *map2) +{ + int disjoint; + int intersect; + isl_map *test; + + disjoint = isl_map_plain_is_disjoint(map1, map2); + if (disjoint < 0 || disjoint) + return disjoint; + + disjoint = isl_map_is_empty(map1); + if (disjoint < 0 || disjoint) + return disjoint; + + disjoint = isl_map_is_empty(map2); + if (disjoint < 0 || disjoint) + return disjoint; + + intersect = isl_map_plain_is_universe(map1); + if (intersect < 0 || intersect) + return intersect < 0 ? -1 : 0; + + intersect = isl_map_plain_is_universe(map2); + if (intersect < 0 || intersect) + return intersect < 0 ? -1 : 0; + + test = isl_map_intersect(isl_map_copy(map1), isl_map_copy(map2)); + disjoint = isl_map_is_empty(test); + isl_map_free(test); + + return disjoint; +} + int isl_set_plain_is_disjoint(__isl_keep isl_set *set1, __isl_keep isl_set *set2) { @@ -1973,6 +2543,13 @@ int isl_set_plain_is_disjoint(__isl_keep isl_set *set1, (struct isl_map *)set2); } +/* Are "set1" and "set2" disjoint? + */ +int isl_set_is_disjoint(__isl_keep isl_set *set1, __isl_keep isl_set *set2) +{ + return isl_map_is_disjoint(set1, set2); +} + int isl_set_fast_is_disjoint(__isl_keep isl_set *set1, __isl_keep isl_set *set2) { return isl_set_plain_is_disjoint(set1, set2); @@ -2161,7 +2738,7 @@ static struct isl_basic_map *drop_more_redundant_divs( if (!vec) goto error; - tab = isl_tab_from_basic_map(bmap); + tab = isl_tab_from_basic_map(bmap, 0); while (n > 0) { int i, l, u; @@ -2379,7 +2956,7 @@ static struct isl_basic_map *coalesce_or_drop_more_redundant_divs( /* Remove divs that are not strictly needed. * In particular, if a div only occurs positively (or negatively) * in constraints, then it can simply be dropped. - * Also, if a div occurs only occurs in two constraints and if moreover + * Also, if a div occurs in only two constraints and if moreover * those two constraints are opposite to each other, except for the constant * term and if the sum of the constant terms is such that for any value * of the other values, there is always at least one integer value of the @@ -2387,6 +2964,10 @@ static struct isl_basic_map *coalesce_or_drop_more_redundant_divs( * the (absolute value) of the coefficent of the div in the constraints, * then we can also simply drop the div. * + * We skip divs that appear in equalities or in the definition of other divs. + * Divs that appear in the definition of other divs usually occur in at least + * 4 constraints, but the constraints may have been simplified. + * * If any divs are left after these simple checks then we move on * to more complicated cases in drop_more_redundant_divs. */ @@ -2413,6 +2994,11 @@ struct isl_basic_map *isl_basic_map_drop_redundant_divs( int defined; defined = !isl_int_is_zero(bmap->div[i][0]); + for (j = i; j < bmap->n_div; ++j) + if (!isl_int_is_zero(bmap->div[j][1 + 1 + off + i])) + break; + if (j < bmap->n_div) + continue; for (j = 0; j < bmap->n_eq; ++j) if (!isl_int_is_zero(bmap->eq[j][1 + off + i])) break;