diff options
Diffstat (limited to 'polly/lib/External/isl/isl_map.c')
| -rw-r--r-- | polly/lib/External/isl/isl_map.c | 510 |
1 files changed, 323 insertions, 187 deletions
diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c index b3c5c02922b..f92dd616697 100644 --- a/polly/lib/External/isl/isl_map.c +++ b/polly/lib/External/isl/isl_map.c @@ -322,6 +322,38 @@ __isl_give isl_local_space *isl_basic_set_get_local_space( return isl_basic_map_get_local_space(bset); } +/* For each known div d = floor(f/m), add the constraints + * + * f - m d >= 0 + * -(f-(n-1)) + m d >= 0 + * + * Do not finalize the result. + */ +static __isl_give isl_basic_map *add_known_div_constraints( + __isl_take isl_basic_map *bmap) +{ + int i; + unsigned n_div; + + if (!bmap) + return NULL; + n_div = isl_basic_map_dim(bmap, isl_dim_div); + if (n_div == 0) + return bmap; + bmap = isl_basic_map_cow(bmap); + bmap = isl_basic_map_extend_constraints(bmap, 0, 2 * n_div); + if (!bmap) + return NULL; + for (i = 0; i < n_div; ++i) { + if (isl_int_is_zero(bmap->div[i][0])) + continue; + if (isl_basic_map_add_div_constraints(bmap, i) < 0) + return isl_basic_map_free(bmap); + } + + return bmap; +} + __isl_give isl_basic_map *isl_basic_map_from_local_space( __isl_take isl_local_space *ls) { @@ -340,11 +372,9 @@ __isl_give isl_basic_map *isl_basic_map_from_local_space( if (isl_basic_map_alloc_div(bmap) < 0) goto error; - for (i = 0; i < n_div; ++i) { + for (i = 0; i < n_div; ++i) isl_seq_cpy(bmap->div[i], ls->div->row[i], ls->div->n_col); - if (isl_basic_map_add_div_constraints(bmap, i) < 0) - goto error; - } + bmap = add_known_div_constraints(bmap); isl_local_space_free(ls); return bmap; @@ -4441,11 +4471,13 @@ int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div) * * f - m d >= 0 * -(f-(n-1)) + m d >= 0 + * + * Remove duplicate constraints in case of some these div constraints + * already appear in "bmap". */ __isl_give isl_basic_map *isl_basic_map_add_known_div_constraints( __isl_take isl_basic_map *bmap) { - int i; unsigned n_div; if (!bmap) @@ -4453,17 +4485,8 @@ __isl_give isl_basic_map *isl_basic_map_add_known_div_constraints( n_div = isl_basic_map_dim(bmap, isl_dim_div); if (n_div == 0) return bmap; - bmap = isl_basic_map_cow(bmap); - bmap = isl_basic_map_extend_constraints(bmap, 0, 2 * n_div); - if (!bmap) - return NULL; - for (i = 0; i < n_div; ++i) { - if (isl_int_is_zero(bmap->div[i][0])) - continue; - if (isl_basic_map_add_div_constraints(bmap, i) < 0) - return isl_basic_map_free(bmap); - } + bmap = add_known_div_constraints(bmap); bmap = isl_basic_map_remove_duplicate_constraints(bmap, NULL, 0); bmap = isl_basic_map_finalize(bmap); return bmap; @@ -4703,6 +4726,11 @@ struct isl_set *isl_set_to_underlying_set(struct isl_set *set) return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set); } +/* Replace the space of "bmap" by "space". + * + * If the space of "bmap" is identical to "space" (including the identifiers + * of the input and output dimensions), then simply return the original input. + */ __isl_give isl_basic_map *isl_basic_map_reset_space( __isl_take isl_basic_map *bmap, __isl_take isl_space *space) { @@ -4711,6 +4739,12 @@ __isl_give isl_basic_map *isl_basic_map_reset_space( if (!bmap) goto error; equal = isl_space_is_equal(bmap->dim, space); + if (equal >= 0 && equal) + equal = isl_space_match(bmap->dim, isl_dim_in, + space, isl_dim_in); + if (equal >= 0 && equal) + equal = isl_space_match(bmap->dim, isl_dim_out, + space, isl_dim_out); if (equal < 0) goto error; if (equal) { @@ -6886,30 +6920,47 @@ error: return NULL; } -int isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap) +/* Does local variable "div" of "bmap" have an explicit representation? + */ +isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div) +{ + if (!bmap) + return isl_bool_error; + if (div < 0 || div >= isl_basic_map_dim(bmap, isl_dim_div)) + isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, + "position out of bounds", return isl_bool_error); + return !isl_int_is_zero(bmap->div[div][0]); +} + +/* Does "bmap" have an explicit representation for all local variables? + */ +isl_bool isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap) { int i; unsigned off; if (!bmap) - return -1; + return isl_bool_error; off = 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])) - return 0; + if (!isl_basic_map_div_is_known(bmap, i)) + return isl_bool_false; isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]), - return -1); + return isl_bool_error); } - return 1; + return isl_bool_true; } -static int map_divs_known(__isl_keep isl_map *map) +/* Do all basic maps in "map" have an explicit representation + * for all local variables? + */ +isl_bool isl_map_divs_known(__isl_keep isl_map *map) { int i; if (!map) - return -1; + return isl_bool_error; for (i = 0; i < map->n; ++i) { int known = isl_basic_map_divs_known(map->p[i]); @@ -6917,7 +6968,7 @@ static int map_divs_known(__isl_keep isl_map *map) return known; } - return 1; + return isl_bool_true; } /* If bmap contains any unknown divs, then compute explicit @@ -6962,7 +7013,7 @@ struct isl_map *isl_map_compute_divs(struct isl_map *map) if (map->n == 0) return map; - known = map_divs_known(map); + known = isl_map_divs_known(map); if (known < 0) { isl_map_free(map); return NULL; @@ -8789,8 +8840,23 @@ int isl_set_plain_dim_has_fixed_lower_bound(__isl_keep isl_set *set, return fixed; } -/* uset_gist depends on constraints without existentially quantified +/* Return -1 if the constraint "c1" should be sorted before "c2" + * and 1 if it should be sorted after "c2". + * Return 0 if the two constraints are the same (up to the constant term). + * + * In particular, if a constraint involves later variables than another + * then it is sorted after this other constraint. + * uset_gist depends on constraints without existentially quantified * variables sorting first. + * + * For constraints that have the same latest variable, those + * with the same coefficient for this latest variable (first in absolute value + * and then in actual value) are grouped together. + * This is useful for detecting pairs of constraints that can + * be chained in their printed representation. + * + * Finally, within a group, constraints are sorted according to + * their coefficients (excluding the constant term). */ static int sort_constraint_cmp(const void *p1, const void *p2, void *arg) { @@ -8798,6 +8864,7 @@ static int sort_constraint_cmp(const void *p1, const void *p2, void *arg) isl_int **c2 = (isl_int **) p2; int l1, l2; unsigned size = *(unsigned *) arg; + int cmp; l1 = isl_seq_last_non_zero(*c1 + 1, size); l2 = isl_seq_last_non_zero(*c2 + 1, size); @@ -8805,11 +8872,33 @@ static int sort_constraint_cmp(const void *p1, const void *p2, void *arg) if (l1 != l2) return l1 - l2; + cmp = isl_int_abs_cmp((*c1)[1 + l1], (*c2)[1 + l1]); + if (cmp != 0) + return cmp; + cmp = isl_int_cmp((*c1)[1 + l1], (*c2)[1 + l1]); + if (cmp != 0) + return -cmp; + return isl_seq_cmp(*c1 + 1, *c2 + 1, size); } -static struct isl_basic_map *isl_basic_map_sort_constraints( - struct isl_basic_map *bmap) +/* Return -1 if the constraint "c1" of "bmap" is sorted before "c2" + * by isl_basic_map_sort_constraints, 1 if it is sorted after "c2" + * and 0 if the two constraints are the same (up to the constant term). + */ +int isl_basic_map_constraint_cmp(__isl_keep isl_basic_map *bmap, + isl_int *c1, isl_int *c2) +{ + unsigned total; + + if (!bmap) + return -2; + total = isl_basic_map_total_dim(bmap); + return sort_constraint_cmp(&c1, &c2, &total); +} + +__isl_give isl_basic_map *isl_basic_map_sort_constraints( + __isl_take isl_basic_map *bmap) { unsigned total; @@ -10302,18 +10391,126 @@ static int div_may_involve_output(__isl_keep isl_basic_map *bmap, int div) return 0; } +/* Return the first integer division of "bmap" in the range + * [first, first + n[ that may depend on any output dimensions and + * that has a non-zero coefficient in "c" (where the first coefficient + * in "c" corresponds to integer division "first"). + */ +static int first_div_may_involve_output(__isl_keep isl_basic_map *bmap, + isl_int *c, int first, int n) +{ + int k; + + if (!bmap) + return -1; + + for (k = first; k < first + n; ++k) { + if (isl_int_is_zero(c[k])) + continue; + if (div_may_involve_output(bmap, k)) + return k; + } + + return first + n; +} + +/* Look for a pair of inequality constraints in "bmap" of the form + * + * -l + i >= 0 or i >= l + * and + * n + l - i >= 0 or i <= l + n + * + * with n < "m" and i the output dimension at position "pos". + * (Note that n >= 0 as otherwise the two constraints would conflict.) + * Furthermore, "l" is only allowed to involve parameters, input dimensions + * and earlier output dimensions, as well as integer divisions that do + * not involve any of the output dimensions. + * + * Return the index of the first inequality constraint or bmap->n_ineq + * if no such pair can be found. + */ +static int find_modulo_constraint_pair(__isl_keep isl_basic_map *bmap, + int pos, isl_int m) +{ + int i, j; + isl_ctx *ctx; + unsigned total; + unsigned n_div, o_div; + unsigned n_out, o_out; + int less; + + if (!bmap) + return -1; + + ctx = isl_basic_map_get_ctx(bmap); + total = isl_basic_map_total_dim(bmap); + n_out = isl_basic_map_dim(bmap, isl_dim_out); + o_out = isl_basic_map_offset(bmap, isl_dim_out); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + o_div = isl_basic_map_offset(bmap, isl_dim_div); + for (i = 0; i < bmap->n_ineq; ++i) { + if (!isl_int_abs_eq(bmap->ineq[i][o_out + pos], ctx->one)) + continue; + if (isl_seq_first_non_zero(bmap->ineq[i] + o_out + pos + 1, + n_out - (pos + 1)) != -1) + continue; + if (first_div_may_involve_output(bmap, bmap->ineq[i] + o_div, + 0, n_div) < n_div) + continue; + for (j = i + 1; j < bmap->n_ineq; ++j) { + if (!isl_int_abs_eq(bmap->ineq[j][o_out + pos], + ctx->one)) + continue; + if (!isl_seq_is_neg(bmap->ineq[i] + 1, + bmap->ineq[j] + 1, total)) + continue; + break; + } + if (j >= bmap->n_ineq) + continue; + isl_int_add(bmap->ineq[i][0], + bmap->ineq[i][0], bmap->ineq[j][0]); + less = isl_int_abs_lt(bmap->ineq[i][0], m); + isl_int_sub(bmap->ineq[i][0], + bmap->ineq[i][0], bmap->ineq[j][0]); + if (!less) + continue; + if (isl_int_is_one(bmap->ineq[i][o_out + pos])) + return i; + else + return j; + } + + return bmap->n_ineq; +} + /* Return the index of the equality of "bmap" that defines * the output dimension "pos" in terms of earlier dimensions. * The equality may also involve integer divisions, as long * as those integer divisions are defined in terms of * parameters or input dimensions. + * In this case, *div is set to the number of integer divisions and + * *ineq is set to the number of inequality constraints (provided + * div and ineq are not NULL). + * + * The equality may also involve a single integer division involving + * the output dimensions (typically only output dimension "pos") as + * long as the coefficient of output dimension "pos" is 1 or -1 and + * there is a pair of constraints i >= l and i <= l + n, with i referring + * to output dimension "pos", l an expression involving only earlier + * dimensions and n smaller than the coefficient of the integer division + * in the equality. In this case, the output dimension can be defined + * in terms of a modulo expression that does not involve the integer division. + * *div is then set to this single integer division and + * *ineq is set to the index of constraint i >= l. + * * Return bmap->n_eq if there is no such equality. * Return -1 on error. */ int isl_basic_map_output_defining_equality(__isl_keep isl_basic_map *bmap, - int pos) + int pos, int *div, int *ineq) { - int j, k; + int j, k, l; unsigned n_out, o_out; unsigned n_div, o_div; @@ -10325,20 +10522,37 @@ int isl_basic_map_output_defining_equality(__isl_keep isl_basic_map *bmap, n_div = isl_basic_map_dim(bmap, isl_dim_div); o_div = isl_basic_map_offset(bmap, isl_dim_div); + if (ineq) + *ineq = bmap->n_ineq; + if (div) + *div = n_div; for (j = 0; j < bmap->n_eq; ++j) { if (isl_int_is_zero(bmap->eq[j][o_out + pos])) continue; if (isl_seq_first_non_zero(bmap->eq[j] + o_out + pos + 1, n_out - (pos + 1)) != -1) continue; - for (k = 0; k < n_div; ++k) { - if (isl_int_is_zero(bmap->eq[j][o_div + k])) - continue; - if (div_may_involve_output(bmap, k)) - break; - } + k = first_div_may_involve_output(bmap, bmap->eq[j] + o_div, + 0, n_div); if (k >= n_div) return j; + if (!isl_int_is_one(bmap->eq[j][o_out + pos]) && + !isl_int_is_negone(bmap->eq[j][o_out + pos])) + continue; + if (first_div_may_involve_output(bmap, bmap->eq[j] + o_div, + k + 1, n_div - (k+1)) < n_div) + continue; + l = find_modulo_constraint_pair(bmap, pos, + bmap->eq[j][o_div + k]); + if (l < 0) + return -1; + if (l >= bmap->n_ineq) + continue; + if (div) + *div = k; + if (ineq) + *ineq = l; + return j; } return bmap->n_eq; @@ -10362,7 +10576,8 @@ isl_bool isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap) for (i = 0; i < n_out; ++i) { int eq; - eq = isl_basic_map_output_defining_equality(bmap, i); + eq = isl_basic_map_output_defining_equality(bmap, i, + NULL, NULL); if (eq < 0) return isl_bool_error; if (eq >= bmap->n_eq) @@ -10582,6 +10797,35 @@ isl_bool isl_set_is_wrapping(__isl_keep isl_set *set) return isl_space_is_wrapping(set->dim); } +/* Modify the space of "map" through a call to "change". + * If "can_change" is set (not NULL), then first call it to check + * if the modification is allowed, printing the error message "cannot_change" + * if it is not. + */ +static __isl_give isl_map *isl_map_change_space(__isl_take isl_map *map, + isl_bool (*can_change)(__isl_keep isl_map *map), + const char *cannot_change, + __isl_give isl_space *(*change)(__isl_take isl_space *space)) +{ + isl_bool ok; + isl_space *space; + + if (!map) + return NULL; + + ok = can_change ? can_change(map) : isl_bool_true; + if (ok < 0) + return isl_map_free(map); + if (!ok) + isl_die(isl_map_get_ctx(map), isl_error_invalid, cannot_change, + return isl_map_free(map)); + + space = change(isl_map_get_space(map)); + map = isl_map_reset_space(map, space); + + return map; +} + /* Is the domain of "map" a wrapped relation? */ isl_bool isl_map_domain_is_wrapping(__isl_keep isl_map *map) @@ -10620,27 +10864,11 @@ error: return NULL; } +/* Given a map A -> B, return the set (A -> B). + */ __isl_give isl_set *isl_map_wrap(__isl_take isl_map *map) { - int i; - - map = isl_map_cow(map); - if (!map) - return NULL; - - for (i = 0; i < map->n; ++i) { - map->p[i] = (isl_basic_map *)isl_basic_map_wrap(map->p[i]); - if (!map->p[i]) - goto error; - } - map->dim = isl_space_wrap(map->dim); - if (!map->dim) - goto error; - - return (isl_set *)map; -error: - isl_map_free(map); - return NULL; + return isl_map_change_space(map, NULL, NULL, &isl_space_wrap); } __isl_give isl_basic_map *isl_basic_set_unwrap(__isl_take isl_basic_set *bset) @@ -10661,35 +10889,13 @@ error: return NULL; } +/* Given a set (A -> B), return the map A -> B. + * Error out if "set" is not of the form (A -> B). + */ __isl_give isl_map *isl_set_unwrap(__isl_take isl_set *set) { - int i; - - if (!set) - return NULL; - - if (!isl_set_is_wrapping(set)) - isl_die(set->ctx, isl_error_invalid, "not a wrapping set", - goto error); - - set = isl_set_cow(set); - if (!set) - return NULL; - - for (i = 0; i < set->n; ++i) { - set->p[i] = (isl_basic_set *)isl_basic_set_unwrap(set->p[i]); - if (!set->p[i]) - goto error; - } - - set->dim = isl_space_unwrap(set->dim); - if (!set->dim) - goto error; - - return (isl_map *)set; -error: - isl_set_free(set); - return NULL; + return isl_map_change_space(set, &isl_set_is_wrapping, + "not a wrapping set", &isl_space_unwrap); } __isl_give isl_basic_map *isl_basic_map_reset(__isl_take isl_basic_map *bmap, @@ -10826,33 +11032,17 @@ error: return NULL; } +/* Remove any internal structure from the spaces of domain and range of "map". + */ __isl_give isl_map *isl_map_flatten(__isl_take isl_map *map) { - int i; - if (!map) return NULL; if (!map->dim->nested[0] && !map->dim->nested[1]) return map; - map = isl_map_cow(map); - if (!map) - return NULL; - - for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_flatten(map->p[i]); - if (!map->p[i]) - goto error; - } - map->dim = isl_space_flatten(map->dim); - if (!map->dim) - goto error; - - return map; -error: - isl_map_free(map); - return NULL; + return isl_map_change_space(map, NULL, NULL, &isl_space_flatten); } __isl_give isl_set *isl_set_flatten(__isl_take isl_set *set) @@ -10873,62 +11063,30 @@ __isl_give isl_map *isl_set_flatten_map(__isl_take isl_set *set) return map; } +/* Remove any internal structure from the space of the domain of "map". + */ __isl_give isl_map *isl_map_flatten_domain(__isl_take isl_map *map) { - int i; - if (!map) return NULL; if (!map->dim->nested[0]) return map; - map = isl_map_cow(map); - if (!map) - return NULL; - - for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_flatten_domain(map->p[i]); - if (!map->p[i]) - goto error; - } - map->dim = isl_space_flatten_domain(map->dim); - if (!map->dim) - goto error; - - return map; -error: - isl_map_free(map); - return NULL; + return isl_map_change_space(map, NULL, NULL, &isl_space_flatten_domain); } +/* Remove any internal structure from the space of the range of "map". + */ __isl_give isl_map *isl_map_flatten_range(__isl_take isl_map *map) { - int i; - if (!map) return NULL; if (!map->dim->nested[1]) return map; - map = isl_map_cow(map); - if (!map) - return NULL; - - for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_flatten_range(map->p[i]); - if (!map->p[i]) - goto error; - } - map->dim = isl_space_flatten_range(map->dim); - if (!map->dim) - goto error; - - return map; -error: - isl_map_free(map); - return NULL; + return isl_map_change_space(map, NULL, NULL, &isl_space_flatten_range); } /* Reorder the dimensions of "bmap" according to the given dim_map @@ -11305,6 +11463,7 @@ __isl_give isl_basic_map *isl_basic_map_zip(__isl_take isl_basic_map *bmap) bmap->dim = isl_space_zip(bmap->dim); if (!bmap->dim) goto error; + bmap = isl_basic_map_mark_final(bmap); return bmap; error: isl_basic_map_free(bmap); @@ -11385,6 +11544,7 @@ __isl_give isl_basic_map *isl_basic_map_curry(__isl_take isl_basic_map *bmap) bmap->dim = isl_space_curry(bmap->dim); if (!bmap->dim) goto error; + bmap = isl_basic_map_mark_final(bmap); return bmap; error: isl_basic_map_free(bmap); @@ -11396,33 +11556,30 @@ error: */ __isl_give isl_map *isl_map_curry(__isl_take isl_map *map) { - int i; - - if (!map) - return NULL; - - if (!isl_map_can_curry(map)) - isl_die(map->ctx, isl_error_invalid, "map cannot be curried", - goto error); + return isl_map_change_space(map, &isl_map_can_curry, + "map cannot be curried", &isl_space_curry); +} - map = isl_map_cow(map); +/* Can isl_map_range_curry be applied to "map"? + * That is, does it have a nested relation in its range, + * the domain of which is itself a nested relation? + */ +isl_bool isl_map_can_range_curry(__isl_keep isl_map *map) +{ if (!map) - return NULL; - - for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_curry(map->p[i]); - if (!map->p[i]) - goto error; - } + return isl_bool_error; - map->dim = isl_space_curry(map->dim); - if (!map->dim) - goto error; + return isl_space_can_range_curry(map->dim); +} - return map; -error: - isl_map_free(map); - return NULL; +/* Given a map A -> ((B -> C) -> D), return the corresponding map + * A -> (B -> (C -> D)). + */ +__isl_give isl_map *isl_map_range_curry(__isl_take isl_map *map) +{ + return isl_map_change_space(map, &isl_map_can_range_curry, + "map range cannot be curried", + &isl_space_range_curry); } /* Can we apply isl_basic_map_uncurry to "bmap"? @@ -11466,6 +11623,7 @@ __isl_give isl_basic_map *isl_basic_map_uncurry(__isl_take isl_basic_map *bmap) bmap->dim = isl_space_uncurry(bmap->dim); if (!bmap->dim) return isl_basic_map_free(bmap); + bmap = isl_basic_map_mark_final(bmap); return bmap; } @@ -11474,30 +11632,8 @@ __isl_give isl_basic_map *isl_basic_map_uncurry(__isl_take isl_basic_map *bmap) */ __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; + return isl_map_change_space(map, &isl_map_can_uncurry, + "map cannot be uncurried", &isl_space_uncurry); } /* Construct a basic map mapping the domain of the affine expression |
