X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map_simplify.c;h=5cb6bfb45d064458c19dab11a210bb4cab20d663;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=9cebefb8a01fb0ca05dde4b57b2b58888706f573;hpb=2f6c5a1dd4aacefe809fac3a1a82729f26f9906f;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map_simplify.c b/isl_map_simplify.c index 9cebefb..5cb6bfb 100644 --- a/isl_map_simplify.c +++ b/isl_map_simplify.c @@ -1042,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. @@ -1060,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])) @@ -1241,6 +1271,10 @@ 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); @@ -1329,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; } @@ -1416,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; @@ -1446,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) @@ -1707,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". @@ -1752,6 +1964,14 @@ 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); @@ -1819,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. @@ -1842,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); @@ -1921,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); @@ -1993,6 +2221,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); + if (!map) + goto error; for (i = 0; i < map->n; ++i) context = isl_basic_map_align_divs(context, map->p[i]); for (i = map->n - 1; i >= 0; --i) { @@ -2016,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, @@ -2166,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) { @@ -2188,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) { @@ -2195,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);