X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=7496da78d82cb161c5239c2739a0416536256989;hb=d17afdd1f5e49c0c5dcf6a6e0687330dcdc8e6bf;hp=64a8833dd4355129edea2f64ecc78ac294f57caa;hpb=0742b6c276f6597faef113e9a975f2572b175f59;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index 64a8833..7496da7 100644 --- a/isl_map.c +++ b/isl_map.c @@ -11,44 +11,25 @@ */ #include -#include -#include +#include +#include #include #include "isl_dim_private.h" #include "isl_equalities.h" -#include +#include #include #include #include #include -#include "isl_map_private.h" #include "isl_map_piplib.h" #include #include "isl_sample.h" #include "isl_tab.h" #include #include - -/* Maps dst positions to src positions */ -struct isl_dim_map { - unsigned len; - int pos[1]; -}; - -static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len) -{ - int i; - struct isl_dim_map *dim_map; - dim_map = isl_alloc(ctx, struct isl_dim_map, - sizeof(struct isl_dim_map) + len * sizeof(int)); - if (!dim_map) - return NULL; - dim_map->len = 1 + len; - dim_map->pos[0] = 0; - for (i = 0; i < len; ++i) - dim_map->pos[1 + i] = -1; - return dim_map; -} +#include +#include +#include static unsigned n(struct isl_dim *dim, enum isl_dim_type type) { @@ -71,50 +52,6 @@ static unsigned pos(struct isl_dim *dim, enum isl_dim_type type) } } -static void isl_dim_map_dim_range(struct isl_dim_map *dim_map, - struct isl_dim *dim, enum isl_dim_type type, - unsigned first, unsigned n, unsigned dst_pos) -{ - int i; - unsigned src_pos; - - if (!dim_map || !dim) - return; - - src_pos = pos(dim, type); - for (i = 0; i < n; ++i) - dim_map->pos[1 + dst_pos + i] = src_pos + first + i; -} - -static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim, - enum isl_dim_type type, unsigned dst_pos) -{ - isl_dim_map_dim_range(dim_map, dim, type, 0, n(dim, type), dst_pos); -} - -static void isl_dim_map_div(struct isl_dim_map *dim_map, - struct isl_basic_map *bmap, unsigned dst_pos) -{ - int i; - unsigned src_pos; - - if (!dim_map || !bmap) - return; - - src_pos = 1 + isl_dim_total(bmap->dim); - for (i = 0; i < bmap->n_div; ++i) - dim_map->pos[1 + dst_pos + i] = src_pos + i; -} - -static void isl_dim_map_dump(struct isl_dim_map *dim_map) -{ - int i; - - for (i = 0; i < dim_map->len; ++i) - fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]); - fprintf(stderr, "\n"); -} - unsigned isl_basic_map_dim(const struct isl_basic_map *bmap, enum isl_dim_type type) { @@ -155,6 +92,12 @@ unsigned isl_basic_map_offset(struct isl_basic_map *bmap, } } +unsigned isl_basic_set_offset(struct isl_basic_set *bset, + enum isl_dim_type type) +{ + return isl_basic_map_offset(bset, type); +} + static unsigned map_offset(struct isl_map *map, enum isl_dim_type type) { return pos(map->dim, type); @@ -218,17 +161,17 @@ unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap) unsigned isl_map_n_in(const struct isl_map *map) { - return map->dim->n_in; + return map ? map->dim->n_in : 0; } unsigned isl_map_n_out(const struct isl_map *map) { - return map->dim->n_out; + return map ? map->dim->n_out : 0; } unsigned isl_map_n_param(const struct isl_map *map) { - return map->dim->nparam; + return map ? map->dim->nparam : 0; } int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set) @@ -254,6 +197,17 @@ int isl_basic_map_compatible_domain(struct isl_basic_map *bmap, return isl_dim_tuple_match(bmap->dim, isl_dim_in, bset->dim, isl_dim_set); } +int isl_map_compatible_range(__isl_keep isl_map *map, __isl_keep isl_set *set) +{ + int m; + if (!map || !set) + return -1; + m = isl_dim_match(map->dim, isl_dim_param, set->dim, isl_dim_param); + if (m < 0 || !m) + return m; + return isl_dim_tuple_match(map->dim, isl_dim_out, set->dim, isl_dim_set); +} + int isl_basic_map_compatible_range(struct isl_basic_map *bmap, struct isl_basic_set *bset) { @@ -300,6 +254,71 @@ struct isl_dim *isl_basic_set_get_dim(struct isl_basic_set *bset) return isl_dim_copy(bset->dim); } +__isl_give isl_local_space *isl_basic_map_get_local_space( + __isl_keep isl_basic_map *bmap) +{ + int i; + isl_local_space *ls; + unsigned total; + + if (!bmap) + return NULL; + + total = isl_basic_map_total_dim(bmap); + ls = isl_local_space_alloc(isl_dim_copy(bmap->dim), bmap->n_div); + if (!ls) + return NULL; + + for (i = 0; i < bmap->n_div; ++i) + isl_seq_cpy(ls->div->row[i], bmap->div[i], 2 + total); + + return ls; +} + +__isl_give isl_local_space *isl_basic_set_get_local_space( + __isl_keep isl_basic_set *bset) +{ + return isl_basic_map_get_local_space(bset); +} + +__isl_give isl_basic_map *isl_basic_map_from_local_space( + __isl_take isl_local_space *ls) +{ + int i; + int n_div; + isl_basic_map *bmap; + + if (!ls) + return NULL; + + n_div = isl_local_space_dim(ls, isl_dim_div); + bmap = isl_basic_map_alloc_dim(isl_local_space_get_dim(ls), + n_div, 0, 2 * n_div); + + for (i = 0; i < n_div; ++i) + if (isl_basic_map_alloc_div(bmap) < 0) + goto error; + + 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; + } + + isl_local_space_free(ls); + return bmap; +error: + isl_local_space_free(ls); + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_basic_set *isl_basic_set_from_local_space( + __isl_take isl_local_space *ls) +{ + return isl_basic_map_from_local_space(ls); +} + struct isl_dim *isl_map_get_dim(struct isl_map *map) { if (!map) @@ -330,6 +349,12 @@ error: return NULL; } +__isl_give isl_basic_set *isl_basic_set_set_tuple_name( + __isl_take isl_basic_set *bset, const char *s) +{ + return isl_basic_map_set_tuple_name(bset, isl_dim_set, s); +} + const char *isl_basic_map_get_tuple_name(__isl_keep isl_basic_map *bmap, enum isl_dim_type type) { @@ -373,6 +398,11 @@ __isl_give isl_set *isl_set_set_tuple_name(__isl_take isl_set *set, return (isl_set *)isl_map_set_tuple_name((isl_map *)set, isl_dim_set, s); } +const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset) +{ + return bset ? isl_dim_get_tuple_name(bset->dim, isl_dim_set) : NULL; +} + const char *isl_set_get_tuple_name(__isl_keep isl_set *set) { return set ? isl_dim_get_tuple_name(set->dim, isl_dim_set) : NULL; @@ -384,6 +414,12 @@ const char *isl_basic_map_get_dim_name(__isl_keep isl_basic_map *bmap, return bmap ? isl_dim_get_name(bmap->dim, type, pos) : NULL; } +const char *isl_basic_set_get_dim_name(__isl_keep isl_basic_set *bset, + enum isl_dim_type type, unsigned pos) +{ + return bset ? isl_dim_get_name(bset->dim, type, pos) : NULL; +} + const char *isl_map_get_dim_name(__isl_keep isl_map *map, enum isl_dim_type type, unsigned pos) { @@ -456,6 +492,11 @@ int isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap) return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL); } +int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset) +{ + return isl_basic_map_is_rational(bset); +} + static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx, struct isl_basic_map *bmap, unsigned extra, unsigned n_eq, unsigned n_ineq) @@ -1017,66 +1058,6 @@ error: return NULL; } -static void copy_constraint_dim_map(isl_int *dst, isl_int *src, - struct isl_dim_map *dim_map) -{ - int i; - - for (i = 0; i < dim_map->len; ++i) { - if (dim_map->pos[i] < 0) - isl_int_set_si(dst[i], 0); - else - isl_int_set(dst[i], src[dim_map->pos[i]]); - } -} - -static void copy_div_dim_map(isl_int *dst, isl_int *src, - struct isl_dim_map *dim_map) -{ - isl_int_set(dst[0], src[0]); - copy_constraint_dim_map(dst+1, src+1, dim_map); -} - -static struct isl_basic_map *add_constraints_dim_map(struct isl_basic_map *dst, - struct isl_basic_map *src, struct isl_dim_map *dim_map) -{ - int i; - - if (!src || !dst || !dim_map) - goto error; - - for (i = 0; i < src->n_eq; ++i) { - int i1 = isl_basic_map_alloc_equality(dst); - if (i1 < 0) - goto error; - copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map); - } - - for (i = 0; i < src->n_ineq; ++i) { - int i1 = isl_basic_map_alloc_inequality(dst); - if (i1 < 0) - goto error; - copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map); - } - - for (i = 0; i < src->n_div; ++i) { - int i1 = isl_basic_map_alloc_div(dst); - if (i1 < 0) - goto error; - copy_div_dim_map(dst->div[i1], src->div[i], dim_map); - } - - free(dim_map); - isl_basic_map_free(src); - - return dst; -error: - free(dim_map); - isl_basic_map_free(src); - isl_basic_map_free(dst); - return NULL; -} - struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1, struct isl_basic_set *bset2, unsigned pos) { @@ -1242,70 +1223,65 @@ static void swap_vars(struct isl_blk blk, isl_int *a, isl_seq_cpy(a, blk.data, b_len+a_len); } -struct isl_basic_set *isl_basic_set_swap_vars( - struct isl_basic_set *bset, unsigned n) +static __isl_give isl_basic_map *isl_basic_map_swap_vars( + __isl_take isl_basic_map *bmap, unsigned pos, unsigned n1, unsigned n2) { int i; struct isl_blk blk; - unsigned dim; - unsigned nparam; - if (!bset) + if (!bmap) goto error; - nparam = isl_basic_set_n_param(bset); - dim = isl_basic_set_n_dim(bset); - isl_assert(bset->ctx, n <= dim, goto error); + isl_assert(bmap->ctx, + pos + n1 + n2 <= 1 + isl_basic_map_total_dim(bmap), goto error); - if (n == dim) - return bset; + if (n1 == 0 || n2 == 0) + return bmap; - bset = isl_basic_set_cow(bset); - if (!bset) + bmap = isl_basic_map_cow(bmap); + if (!bmap) return NULL; - blk = isl_blk_alloc(bset->ctx, dim); + blk = isl_blk_alloc(bmap->ctx, n1 + n2); if (isl_blk_is_error(blk)) goto error; - for (i = 0; i < bset->n_eq; ++i) + for (i = 0; i < bmap->n_eq; ++i) swap_vars(blk, - bset->eq[i]+1+nparam, n, dim - n); + bmap->eq[i] + pos, n1, n2); - for (i = 0; i < bset->n_ineq; ++i) + for (i = 0; i < bmap->n_ineq; ++i) swap_vars(blk, - bset->ineq[i]+1+nparam, n, dim - n); + bmap->ineq[i] + pos, n1, n2); - for (i = 0; i < bset->n_div; ++i) + for (i = 0; i < bmap->n_div; ++i) swap_vars(blk, - bset->div[i]+1+1+nparam, n, dim - n); + bmap->div[i]+1 + pos, n1, n2); - isl_blk_free(bset->ctx, blk); + isl_blk_free(bmap->ctx, blk); - ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED); - bset = isl_basic_set_gauss(bset, NULL); - return isl_basic_set_finalize(bset); + ISL_F_CLR(bmap, ISL_BASIC_SET_NORMALIZED); + bmap = isl_basic_map_gauss(bmap, NULL); + return isl_basic_map_finalize(bmap); error: - isl_basic_set_free(bset); + isl_basic_map_free(bmap); return NULL; } -struct isl_set *isl_set_swap_vars(struct isl_set *set, unsigned n) +static __isl_give isl_basic_set *isl_basic_set_swap_vars( + __isl_take isl_basic_set *bset, unsigned n) { - int i; - set = isl_set_cow(set); - if (!set) - return NULL; + unsigned dim; + unsigned nparam; - for (i = 0; i < set->n; ++i) { - set->p[i] = isl_basic_set_swap_vars(set->p[i], n); - if (!set->p[i]) { - isl_set_free(set); - return NULL; - } - } - ISL_F_CLR(set, ISL_SET_NORMALIZED); - return set; + nparam = isl_basic_set_n_param(bset); + dim = isl_basic_set_n_dim(bset); + isl_assert(bset->ctx, n <= dim, goto error); + + return isl_basic_map_swap_vars(bset, 1 + nparam, n, dim - n); +error: + isl_basic_set_free(bset); + return NULL; } struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap) @@ -1414,12 +1390,14 @@ __isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set, __isl_give isl_basic_map *isl_basic_map_remove_divs( __isl_take isl_basic_map *bmap) { + if (!bmap) + return NULL; bmap = isl_basic_map_eliminate_vars(bmap, isl_dim_total(bmap->dim), bmap->n_div); if (!bmap) return NULL; bmap->n_div = 0; - return bmap; + return isl_basic_map_finalize(bmap); } __isl_give isl_basic_set *isl_basic_set_remove_divs( @@ -1429,30 +1407,35 @@ __isl_give isl_basic_set *isl_basic_set_remove_divs( (struct isl_basic_map *)bset); } -struct isl_set *isl_set_remove_divs(struct isl_set *set) +__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map) { int i; - if (!set) + if (!map) return NULL; - if (set->n == 0) - return set; + if (map->n == 0) + return map; - set = isl_set_cow(set); - if (!set) + map = isl_map_cow(map); + if (!map) return NULL; - for (i = 0; i < set->n; ++i) { - set->p[i] = isl_basic_set_remove_divs(set->p[i]); - if (!set->p[i]) + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_remove_divs(map->p[i]); + if (!map->p[i]) goto error; } - return set; + return map; error: - isl_set_free(set); + isl_map_free(map); return NULL; } +__isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set) +{ + return isl_map_remove_divs(set); +} + struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap, enum isl_dim_type type, unsigned first, unsigned n) { @@ -1460,7 +1443,7 @@ struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap, return NULL; isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), goto error); - if (n == 0) + if (n == 0 && !isl_dim_is_named_or_nested(bmap->dim, type)) return bmap; bmap = isl_basic_map_eliminate_vars(bmap, isl_basic_map_offset(bmap, type) - 1 + first, n); @@ -1518,6 +1501,9 @@ __isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims( if (!div_involves_vars(bmap, i, first, n)) continue; bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1); + if (!bmap) + return NULL; + i = bmap->n_div; } return bmap; @@ -1559,6 +1545,51 @@ __isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set, type, first, n); } +int isl_basic_set_involves_dims(__isl_keep isl_basic_set *bset, + enum isl_dim_type type, unsigned first, unsigned n) +{ + int i; + + if (!bset) + return -1; + + if (first + n > isl_basic_set_dim(bset, type)) + isl_die(bset->ctx, isl_error_invalid, + "index out of bounds", return -1); + + first += isl_basic_set_offset(bset, type); + for (i = 0; i < bset->n_eq; ++i) + if (isl_seq_first_non_zero(bset->eq[i] + first, n) >= 0) + return 1; + for (i = 0; i < bset->n_ineq; ++i) + if (isl_seq_first_non_zero(bset->ineq[i] + first, n) >= 0) + return 1; + + return 0; +} + +int isl_set_involves_dims(__isl_keep isl_set *set, + enum isl_dim_type type, unsigned first, unsigned n) +{ + int i; + + if (!set) + return -1; + + if (first + n > isl_set_dim(set, type)) + isl_die(set->ctx, isl_error_invalid, + "index out of bounds", return -1); + + for (i = 0; i < set->n; ++i) { + int involves = isl_basic_set_involves_dims(set->p[i], + type, first, n); + if (involves < 0 || !involves) + return involves; + } + + return 1; +} + /* Return true if the definition of the given div is unknown or depends * on unknown divs. */ @@ -1597,9 +1628,6 @@ __isl_give isl_basic_map *isl_basic_map_remove_unknown_divs( } return bmap; -error: - isl_basic_map_free(bmap); - return NULL; } __isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map) @@ -1934,17 +1962,7 @@ struct isl_set *isl_set_dup(struct isl_set *set) struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset) { - struct isl_set *set; - - if (!bset) - return NULL; - - set = isl_set_alloc_dim(isl_dim_copy(bset->dim), 1, ISL_MAP_DISJOINT); - if (!set) { - isl_basic_set_free(bset); - return NULL; - } - return isl_set_add_basic_set(set, bset); + return isl_map_from_basic_map(bset); } struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap) @@ -1955,10 +1973,6 @@ struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap) return NULL; map = isl_map_alloc_dim(isl_dim_copy(bmap->dim), 1, ISL_MAP_DISJOINT); - if (!map) { - isl_basic_map_free(bmap); - return NULL; - } return isl_map_add_basic_map(map, bmap); } @@ -2073,6 +2087,11 @@ struct isl_basic_map *isl_basic_map_intersect_range( isl_assert(bset->ctx, isl_basic_map_compatible_range(bmap, bset), goto error); + if (isl_basic_set_is_universe(bset)) { + isl_basic_set_free(bset); + return bmap; + } + bmap = isl_basic_map_cow(bmap); if (!bmap) goto error; @@ -2198,9 +2217,6 @@ struct isl_basic_set *isl_basic_set_intersect( static __isl_give isl_map *map_intersect_add_constraint( __isl_take isl_map *map1, __isl_take isl_map *map2) { - struct isl_basic_map *bmap1; - struct isl_basic_map *bmap2; - isl_assert(map1->ctx, map1->n == 1, goto error); isl_assert(map2->ctx, map1->n == 1, goto error); isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error); @@ -2215,7 +2231,7 @@ static __isl_give isl_map *map_intersect_add_constraint( map1 = isl_map_cow(map1); if (!map1) goto error; - if (isl_map_fast_is_empty(map1)) { + if (isl_map_plain_is_empty(map1)) { isl_map_free(map2); return map1; } @@ -2231,7 +2247,7 @@ static __isl_give isl_map *map_intersect_add_constraint( if (!map1->p[0]) goto error; - if (isl_basic_map_fast_is_empty(map1->p[0])) { + if (isl_basic_map_plain_is_empty(map1->p[0])) { isl_basic_map_free(map1->p[0]); map1->n = 0; } @@ -2254,11 +2270,13 @@ struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2) if (!map1 || !map2) goto error; - if (isl_map_fast_is_empty(map1)) { + if (isl_map_plain_is_empty(map1) && + isl_dim_equal(map1->dim, map2->dim)) { isl_map_free(map2); return map1; } - if (isl_map_fast_is_empty(map2)) { + if (isl_map_plain_is_empty(map2) && + isl_dim_equal(map1->dim, map2->dim)) { isl_map_free(map1); return map2; } @@ -2317,6 +2335,21 @@ struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2) (struct isl_map *)set2); } +/* The current implementation of isl_map_intersect accepts intersections + * with parameter domains, so we can just call that for now. + */ +__isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map, + __isl_take isl_set *params) +{ + return isl_map_intersect(map, params); +} + +__isl_give isl_set *isl_set_intersect_params(__isl_take isl_set *set, + __isl_take isl_set *params) +{ + return isl_map_intersect_params(set, params); +} + struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap) { struct isl_dim *dim; @@ -2371,7 +2404,9 @@ __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap, res = isl_basic_map_alloc_dim(res_dim, bmap->n_div, bmap->n_eq, bmap->n_ineq); - res = add_constraints_dim_map(res, bmap, dim_map); + if (isl_basic_map_is_rational(bmap)) + res = isl_basic_map_set_rational(res); + res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); return isl_basic_map_finalize(res); } @@ -2455,7 +2490,6 @@ __isl_give isl_basic_map *isl_basic_map_move_dims( enum isl_dim_type dst_type, unsigned dst_pos, enum isl_dim_type src_type, unsigned src_pos, unsigned n) { - int i; struct isl_dim_map *dim_map; struct isl_basic_map *res; enum isl_dim_type t; @@ -2523,7 +2557,7 @@ __isl_give isl_basic_map *isl_basic_map_move_dims( res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap), bmap->n_div, bmap->n_eq, bmap->n_ineq); - bmap = add_constraints_dim_map(res, bmap, dim_map); + bmap = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos, src_type, src_pos, n); @@ -2644,7 +2678,7 @@ static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap, res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap), bmap->n_div, bmap->n_eq, bmap->n_ineq); - res = add_constraints_dim_map(res, bmap, dim_map); + res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); return res; } @@ -2815,8 +2849,8 @@ struct isl_basic_map *isl_basic_map_apply_range( bmap1->n_div + bmap2->n_div + n, bmap1->n_eq + bmap2->n_eq, bmap1->n_ineq + bmap2->n_ineq); - bmap = add_constraints_dim_map(bmap, bmap1, dim_map1); - bmap = add_constraints_dim_map(bmap, bmap2, dim_map2); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2); bmap = add_divs(bmap, n); bmap = isl_basic_map_simplify(bmap); bmap = isl_basic_map_drop_redundant_divs(bmap); @@ -2911,8 +2945,8 @@ struct isl_basic_map *isl_basic_map_sum( isl_int_set_si(bmap->eq[j][1+pos+i], 1); isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1); } - bmap = add_constraints_dim_map(bmap, bmap1, dim_map1); - bmap = add_constraints_dim_map(bmap, bmap2, dim_map2); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2); bmap = add_divs(bmap, 2 * n_out); bmap = isl_basic_map_simplify(bmap); @@ -2994,6 +3028,11 @@ struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap) return isl_basic_map_finalize(bmap); } +__isl_give isl_basic_set *isl_basic_set_neg(__isl_take isl_basic_set *bset) +{ + return isl_basic_map_neg(bset); +} + /* Given a map A -> f(A), construct A -> -f(A). */ struct isl_map *isl_map_neg(struct isl_map *map) @@ -3049,7 +3088,7 @@ struct isl_basic_map *isl_basic_map_floordiv(struct isl_basic_map *bmap, result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim), bmap->n_div + n_out, bmap->n_eq, bmap->n_ineq + 2 * n_out); - result = add_constraints_dim_map(result, bmap, dim_map); + result = isl_basic_map_add_constraints_dim_map(result, bmap, dim_map); result = add_divs(result, n_out); for (i = 0; i < n_out; ++i) { int j; @@ -3332,12 +3371,12 @@ __isl_give isl_map *isl_map_lex_le_first(__isl_take isl_dim *dim, unsigned n) __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim) { - return map_lex_lte(isl_dim_map(set_dim), 0); + return map_lex_lte(isl_dim_map_from_set(set_dim), 0); } __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim) { - return map_lex_lte(isl_dim_map(set_dim), 1); + return map_lex_lte(isl_dim_map_from_set(set_dim), 1); } static __isl_give isl_map *map_lex_gte_first(__isl_take isl_dim *dims, @@ -3386,12 +3425,12 @@ __isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_dim *dim, unsigned n) __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim) { - return map_lex_gte(isl_dim_map(set_dim), 0); + return map_lex_gte(isl_dim_map_from_set(set_dim), 0); } __isl_give isl_map *isl_map_lex_ge(__isl_take isl_dim *set_dim) { - return map_lex_gte(isl_dim_map(set_dim), 1); + return map_lex_gte(isl_dim_map_from_set(set_dim), 1); } __isl_give isl_map *isl_set_lex_le_set(__isl_take isl_set *set1, @@ -3621,6 +3660,7 @@ struct isl_basic_map *isl_basic_map_overlying_set( bmap->extra += like->n_div; if (bmap->extra) { unsigned ltotal; + isl_int **div; ltotal = total - bmap->extra + like->extra; if (ltotal > total) ltotal = total; @@ -3628,10 +3668,10 @@ struct isl_basic_map *isl_basic_map_overlying_set( bmap->extra * (1 + 1 + total)); if (isl_blk_is_error(bmap->block2)) goto error; - bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *, - bmap->extra); - if (!bmap->div) + div = isl_realloc_array(ctx, bmap->div, isl_int *, bmap->extra); + if (!div) goto error; + bmap->div = div; for (i = 0; i < bmap->extra; ++i) bmap->div[i] = bmap->block2.data + i * (1 + 1 + total); for (i = 0; i < like->n_div; ++i) { @@ -3756,7 +3796,7 @@ error: return NULL; } -static __isl_give isl_basic_set *isl_basic_set_reset_dim( +__isl_give isl_basic_set *isl_basic_set_reset_dim( __isl_take isl_basic_set *bset, __isl_take isl_dim *dim) { return (isl_basic_set *)isl_basic_map_reset_dim((isl_basic_map *)bset, @@ -3815,8 +3855,19 @@ struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap) return domain; } +int isl_basic_map_may_be_set(__isl_keep isl_basic_map *bmap) +{ + if (!bmap) + return -1; + return isl_dim_may_be_set(bmap->dim); +} + struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap) { + if (!bmap) + return NULL; + if (isl_basic_map_may_be_set(bmap)) + return bmap; return isl_basic_map_domain(isl_basic_map_reverse(bmap)); } @@ -3826,7 +3877,6 @@ __isl_give isl_basic_map *isl_basic_map_domain_map( int i, k; isl_dim *dim; isl_basic_map *domain; - isl_basic_set *bset; int nparam, n_in, n_out; unsigned total; @@ -3865,7 +3915,6 @@ __isl_give isl_basic_map *isl_basic_map_range_map( int i, k; isl_dim *dim; isl_basic_map *range; - isl_basic_set *bset; int nparam, n_in, n_out; unsigned total; @@ -3898,6 +3947,13 @@ error: return NULL; } +int isl_map_may_be_set(__isl_keep isl_map *map) +{ + if (!map) + return -1; + return isl_dim_may_be_set(map->dim); +} + struct isl_set *isl_map_range(struct isl_map *map) { int i; @@ -3905,7 +3961,7 @@ struct isl_set *isl_map_range(struct isl_map *map) if (!map) goto error; - if (isl_map_dim(map, isl_dim_in) == 0) + if (isl_map_may_be_set(map)) return (isl_set *)map; map = isl_map_cow(map); @@ -4030,6 +4086,13 @@ __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set) return isl_map_reverse(isl_map_from_range(set)); } +__isl_give isl_basic_map *isl_basic_map_from_domain_and_range( + __isl_take isl_basic_set *domain, __isl_take isl_basic_set *range) +{ + return isl_basic_map_apply_range(isl_basic_map_from_domain(domain), + isl_basic_map_from_range(range)); +} + __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain, __isl_take isl_set *range) { @@ -4165,6 +4228,41 @@ struct isl_basic_set *isl_basic_set_universe(struct isl_dim *dim) return bset; } +__isl_give isl_basic_map *isl_basic_map_nat_universe(__isl_take isl_dim *dim) +{ + int i; + unsigned total = isl_dim_total(dim); + isl_basic_map *bmap; + + bmap= isl_basic_map_alloc_dim(dim, 0, 0, total); + for (i = 0; i < total; ++i) { + int k = isl_basic_map_alloc_inequality(bmap); + if (k < 0) + goto error; + isl_seq_clr(bmap->ineq[k], 1 + total); + isl_int_set_si(bmap->ineq[k][1 + i], 1); + } + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_basic_set *isl_basic_set_nat_universe(__isl_take isl_dim *dim) +{ + return isl_basic_map_nat_universe(dim); +} + +__isl_give isl_map *isl_map_nat_universe(__isl_take isl_dim *dim) +{ + return isl_map_from_basic_map(isl_basic_map_nat_universe(dim)); +} + +__isl_give isl_set *isl_set_nat_universe(__isl_take isl_dim *dim) +{ + return isl_map_nat_universe(dim); +} + __isl_give isl_basic_map *isl_basic_map_universe_like( __isl_keep isl_basic_map *model) { @@ -4264,7 +4362,7 @@ __isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map, { if (!bmap || !map) goto error; - if (isl_basic_map_fast_is_empty(bmap)) { + if (isl_basic_map_plain_is_empty(bmap)) { isl_basic_map_free(bmap); return map; } @@ -4684,7 +4782,7 @@ static __isl_give isl_map *basic_map_partial_lexopt( if (!dom) goto error; - if (isl_set_fast_is_empty(dom)) { + 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); @@ -4780,7 +4878,7 @@ static __isl_give isl_map *isl_map_partial_lexopt( if (!map || !dom) goto error; - if (isl_map_fast_is_empty(map)) { + if (isl_map_plain_is_empty(map)) { if (empty) *empty = dom; else @@ -4945,6 +5043,126 @@ __isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set) return (isl_set *)isl_map_lexmax((isl_map *)set); } +/* Construct a map that equates the two given dimensions in the given space. + */ +static __isl_give isl_map *equate(__isl_take isl_dim *dim, + enum isl_dim_type src_type, int src_pos, + enum isl_dim_type dst_type, int dst_pos) +{ + isl_basic_map *bmap; + int k; + + bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0); + k = isl_basic_map_alloc_equality(bmap); + if (k < 0) + goto error; + isl_seq_clr(bmap->eq[k], 1 + isl_basic_map_total_dim(bmap)); + src_pos += isl_basic_map_offset(bmap, src_type); + dst_pos += isl_basic_map_offset(bmap, dst_type); + isl_int_set_si(bmap->eq[k][src_pos], 1); + isl_int_set_si(bmap->eq[k][dst_pos], -1); + + return isl_map_from_basic_map(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* 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 + * because of the way isl_basic_set_foreach_lexmax works. + */ +static int update_dim_max(__isl_take isl_basic_set *dom, + __isl_take isl_aff_list *list, void *user) +{ + isl_ctx *ctx = isl_basic_set_get_ctx(dom); + isl_aff *aff; + isl_pw_aff **pwaff = user; + isl_pw_aff *pwaff_i; + + if (isl_aff_list_n_aff(list) != 1) + isl_die(ctx, isl_error_internal, + "expecting single element list", goto error); + + aff = isl_aff_list_get_aff(list, 0); + pwaff_i = isl_pw_aff_alloc(isl_set_from_basic_set(dom), aff); + + *pwaff = isl_pw_aff_add_disjoint(*pwaff, pwaff_i); + + isl_aff_list_free(list); + + return 0; +error: + isl_basic_set_free(dom); + isl_aff_list_free(list); + return -1; +} + +/* Given a one-dimensional basic set, compute the maximum of that + * dimension as an isl_pw_aff. + * + * The isl_pw_aff is constructed by having isl_basic_set_foreach_lexmax + * call update_dim_max on each leaf of the result. + */ +static __isl_give isl_pw_aff *basic_set_dim_max(__isl_keep isl_basic_set *bset) +{ + isl_dim *dim = isl_basic_set_get_dim(bset); + isl_pw_aff *pwaff; + int r; + + dim = isl_dim_domain(isl_dim_from_range(dim)); + pwaff = isl_pw_aff_empty(dim); + + r = isl_basic_set_foreach_lexmax(bset, &update_dim_max, &pwaff); + if (r < 0) + return isl_pw_aff_free(pwaff); + + return pwaff; +} + +/* Compute the maximum of the given set dimension as a function of the + * parameters, but independently of the other set dimensions. + * + * We first project the set onto the given dimension and then compute + * the "lexicographic" maximum in each basic set, combining the results + * using isl_pw_aff_max. + */ +__isl_give isl_pw_aff *isl_set_dim_max(__isl_take isl_set *set, int pos) +{ + int i; + isl_map *map; + isl_pw_aff *pwaff; + + map = isl_map_from_domain(set); + map = isl_map_add_dims(map, isl_dim_out, 1); + map = isl_map_intersect(map, + equate(isl_map_get_dim(map), isl_dim_in, pos, + isl_dim_out, 0)); + set = isl_map_range(map); + if (!set) + return NULL; + + if (set->n == 0) { + isl_dim *dim = isl_set_get_dim(set); + dim = isl_dim_domain(isl_dim_from_range(dim)); + isl_set_free(set); + return isl_pw_aff_empty(dim); + } + + pwaff = basic_set_dim_max(set->p[0]); + for (i = 1; i < set->n; ++i) { + isl_pw_aff *pwaff_i; + + pwaff_i = basic_set_dim_max(set->p[i]); + pwaff = isl_pw_aff_max(pwaff, pwaff_i); + } + + isl_set_free(set); + + return pwaff; +} + /* Apply a preimage specified by "mat" on the parameters of "bset". * bset is assumed to have only parameters and divs. */ @@ -5122,7 +5340,7 @@ static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset) if (i == bset->n_eq) return isl_basic_set_lexmin(bset); - eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i, + eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, i, bset->n_eq - i, 0, 1 + nparam); eq = isl_mat_cow(eq); T = isl_mat_variable_compression(isl_mat_copy(eq), &T2); @@ -5183,7 +5401,7 @@ error: return NULL; } -static int basic_map_divs_known(__isl_keep isl_basic_map *bmap) +int isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap) { int i; unsigned off; @@ -5209,7 +5427,7 @@ static int map_divs_known(__isl_keep isl_map *map) return -1; for (i = 0; i < map->n; ++i) { - int known = basic_map_divs_known(map->p[i]); + int known = isl_basic_map_divs_known(map->p[i]); if (known <= 0) return known; } @@ -5224,11 +5442,10 @@ static int map_divs_known(__isl_keep isl_map *map) */ struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap) { - int i; int known; struct isl_map *map; - known = basic_map_divs_known(bmap); + known = isl_basic_map_divs_known(bmap); if (known < 0) goto error; if (known) @@ -5236,7 +5453,7 @@ struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap) bmap = isl_basic_map_drop_redundant_divs(bmap); - known = basic_map_divs_known(bmap); + known = isl_basic_map_divs_known(bmap); if (known < 0) goto error; if (known) @@ -5408,6 +5625,20 @@ struct isl_map *isl_map_intersect_range( if (!map || !set) goto error; + if (!isl_dim_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_dim_size(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; + } + if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) && ISL_F_ISSET(set, ISL_MAP_DISJOINT)) ISL_FL_SET(flags, ISL_MAP_DISJOINT); @@ -5551,7 +5782,7 @@ struct isl_set *isl_map_deltas(struct isl_map *map) goto error); dim = isl_map_get_dim(map); dim = isl_dim_domain(dim); - result = isl_set_alloc_dim(dim, map->n, map->flags); + result = isl_set_alloc_dim(dim, map->n, 0); if (!result) goto error; for (i = 0; i < map->n; ++i) @@ -5564,6 +5795,87 @@ error: return NULL; } +/* + * returns [domain -> range] -> range - domain + */ +__isl_give isl_basic_map *isl_basic_map_deltas_map( + __isl_take isl_basic_map *bmap) +{ + int i, k; + isl_dim *dim; + isl_basic_map *domain; + int nparam, n; + unsigned total; + + if (!isl_dim_tuple_match(bmap->dim, isl_dim_in, bmap->dim, isl_dim_out)) + isl_die(bmap->ctx, isl_error_invalid, + "domain and range don't match", goto error); + + nparam = isl_basic_map_dim(bmap, isl_dim_param); + n = isl_basic_map_dim(bmap, isl_dim_in); + + dim = isl_dim_from_range(isl_dim_domain(isl_basic_map_get_dim(bmap))); + domain = isl_basic_map_universe(dim); + + bmap = isl_basic_map_from_domain(isl_basic_map_wrap(bmap)); + bmap = isl_basic_map_apply_range(bmap, domain); + bmap = isl_basic_map_extend_constraints(bmap, n, 0); + + total = isl_basic_map_total_dim(bmap); + + for (i = 0; i < n; ++i) { + k = isl_basic_map_alloc_equality(bmap); + if (k < 0) + goto error; + isl_seq_clr(bmap->eq[k], 1 + total); + isl_int_set_si(bmap->eq[k][1 + nparam + i], 1); + isl_int_set_si(bmap->eq[k][1 + nparam + n + i], -1); + isl_int_set_si(bmap->eq[k][1 + nparam + n + n + i], 1); + } + + bmap = isl_basic_map_gauss(bmap, NULL); + return isl_basic_map_finalize(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* + * returns [domain -> range] -> range - domain + */ +__isl_give isl_map *isl_map_deltas_map(__isl_take isl_map *map) +{ + int i; + isl_dim *domain_dim; + + if (!map) + return NULL; + + if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out)) + isl_die(map->ctx, isl_error_invalid, + "domain and range don't match", goto error); + + map = isl_map_cow(map); + if (!map) + return NULL; + + domain_dim = isl_dim_from_range(isl_dim_domain(isl_map_get_dim(map))); + map->dim = isl_dim_from_domain(isl_dim_wrap(map->dim)); + map->dim = isl_dim_join(map->dim, domain_dim); + if (!map->dim) + goto error; + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_deltas_map(map->p[i]); + if (!map->p[i]) + goto error; + } + ISL_F_CLR(map, ISL_MAP_NORMALIZED); + return map; +error: + isl_map_free(map); + return NULL; +} + static struct isl_basic_map *basic_map_identity(struct isl_dim *dims) { struct isl_basic_map *bmap; @@ -5594,60 +5906,51 @@ error: return NULL; } -struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim) +__isl_give isl_basic_map *isl_basic_map_identity(__isl_take isl_dim *dim) { - struct isl_dim *dim = isl_dim_map(set_dim); if (!dim) return NULL; + if (dim->n_in != dim->n_out) + isl_die(dim->ctx, isl_error_invalid, + "number of input and output dimensions needs to be " + "the same", goto error); return basic_map_identity(dim); +error: + isl_dim_free(dim); + return NULL; } struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model) { if (!model || !model->dim) return NULL; - isl_assert(model->ctx, - model->dim->n_in == model->dim->n_out, return NULL); - return basic_map_identity(isl_dim_copy(model->dim)); + return isl_basic_map_identity(isl_dim_copy(model->dim)); } -static struct isl_map *map_identity(struct isl_dim *dim) +__isl_give isl_map *isl_map_identity(__isl_take isl_dim *dim) { - struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT); - return isl_map_add_basic_map(map, basic_map_identity(isl_dim_copy(dim))); -} - -struct isl_map *isl_map_identity(struct isl_dim *set_dim) -{ - struct isl_dim *dim = isl_dim_map(set_dim); - if (!dim) - return NULL; - return map_identity(dim); + return isl_map_from_basic_map(isl_basic_map_identity(dim)); } struct isl_map *isl_map_identity_like(struct isl_map *model) { if (!model || !model->dim) return NULL; - isl_assert(model->ctx, - model->dim->n_in == model->dim->n_out, return NULL); - return map_identity(isl_dim_copy(model->dim)); + return isl_map_identity(isl_dim_copy(model->dim)); } struct isl_map *isl_map_identity_like_basic_map(struct isl_basic_map *model) { if (!model || !model->dim) return NULL; - isl_assert(model->ctx, - model->dim->n_in == model->dim->n_out, return NULL); - return map_identity(isl_dim_copy(model->dim)); + return isl_map_identity(isl_dim_copy(model->dim)); } __isl_give isl_map *isl_set_identity(__isl_take isl_set *set) { isl_dim *dim = isl_set_get_dim(set); isl_map *id; - id = isl_map_identity(dim); + id = isl_map_identity(isl_dim_map_from_set(dim)); return isl_map_intersect_range(id, set); } @@ -5760,7 +6063,7 @@ static int foreach_orthant(__isl_take isl_set *set, int *signs, int first, if (!set) return -1; - if (isl_set_fast_is_empty(set)) { + if (isl_set_plain_is_empty(set)) { isl_set_free(set); return 0; } @@ -5800,7 +6103,7 @@ int isl_set_foreach_orthant(__isl_keep isl_set *set, if (!set) return -1; - if (isl_set_fast_is_empty(set)) + if (isl_set_plain_is_empty(set)) return 0; nparam = isl_set_dim(set, isl_dim_param); @@ -5880,16 +6183,26 @@ int isl_map_is_empty(struct isl_map *map) return 1; } -int isl_map_fast_is_empty(struct isl_map *map) +int isl_map_plain_is_empty(__isl_keep isl_map *map) { return map ? map->n == 0 : -1; } -int isl_set_fast_is_empty(struct isl_set *set) +int isl_map_fast_is_empty(__isl_keep isl_map *map) +{ + return isl_map_plain_is_empty(map); +} + +int isl_set_plain_is_empty(struct isl_set *set) { return set ? set->n == 0 : -1; } +int isl_set_fast_is_empty(__isl_keep isl_set *set) +{ + return isl_set_plain_is_empty(set); +} + int isl_set_is_empty(struct isl_set *set) { return isl_map_is_empty((struct isl_map *)set); @@ -5974,7 +6287,7 @@ int isl_basic_set_is_universe(struct isl_basic_set *bset) return bset->n_eq == 0 && bset->n_ineq == 0; } -int isl_map_fast_is_universe(__isl_keep isl_map *map) +int isl_map_plain_is_universe(__isl_keep isl_map *map) { int i; @@ -5990,9 +6303,14 @@ int isl_map_fast_is_universe(__isl_keep isl_map *map) return 0; } +int isl_set_plain_is_universe(__isl_keep isl_set *set) +{ + return isl_map_plain_is_universe((isl_map *) set); +} + int isl_set_fast_is_universe(__isl_keep isl_set *set) { - return isl_map_fast_is_universe((isl_map *) set); + return isl_set_plain_is_universe(set); } int isl_basic_map_is_empty(struct isl_basic_map *bmap) @@ -6041,20 +6359,30 @@ int isl_basic_map_is_empty(struct isl_basic_map *bmap) return empty; } -int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap) +int isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap) { if (!bmap) return -1; return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY); } -int isl_basic_set_fast_is_empty(struct isl_basic_set *bset) +int isl_basic_map_fast_is_empty(__isl_keep isl_basic_map *bmap) +{ + return isl_basic_map_plain_is_empty(bmap); +} + +int isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset) { if (!bset) return -1; return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY); } +int isl_basic_set_fast_is_empty(__isl_keep isl_basic_set *bset) +{ + return isl_basic_set_plain_is_empty(bset); +} + int isl_basic_set_is_empty(struct isl_basic_set *bset) { return isl_basic_map_is_empty((struct isl_basic_map *)bset); @@ -6122,20 +6450,68 @@ struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset) __isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map) { - int i; + int i; + + if (!map) + return 0; + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_order_divs(map->p[i]); + if (!map->p[i]) + goto error; + } + + return map; +error: + isl_map_free(map); + return NULL; +} + +/* Apply the expansion computed by isl_merge_divs. + * The expansion itself is given by "exp" while the resulting + * list of divs is given by "div". + */ +__isl_give isl_basic_set *isl_basic_set_expand_divs( + __isl_take isl_basic_set *bset, __isl_take isl_mat *div, int *exp) +{ + int i, j; + int n_div; - if (!map) - return 0; + bset = isl_basic_set_cow(bset); + if (!bset || !div) + goto error; - for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_order_divs(map->p[i]); - if (!map->p[i]) + if (div->n_row < bset->n_div) + isl_die(isl_mat_get_ctx(div), isl_error_invalid, + "not an expansion", goto error); + + bset = isl_basic_map_extend_dim(bset, isl_dim_copy(bset->dim), + div->n_row - bset->n_div, 0, + 2 * (div->n_row - bset->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; + + j = n_div - 1; + for (i = div->n_row - 1; i >= 0; --i) { + if (j >= 0 && exp[j] == i) { + if (i != j) + isl_basic_map_swap_div(bset, i, j); + j--; + } else { + isl_seq_cpy(bset->div[i], div->row[i], div->n_col); + if (isl_basic_map_add_div_constraints(bset, i) < 0) + goto error; + } } - return map; + isl_mat_free(div); + return bset; error: - isl_map_free(map); + isl_basic_set_free(bset); + isl_mat_free(div); return NULL; } @@ -6493,7 +6869,7 @@ int isl_set_follows_at(__isl_keep isl_set *set1, return follows; } -static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap, +static int isl_basic_map_plain_has_fixed_var(__isl_keep isl_basic_map *bmap, unsigned pos, isl_int *val) { int i; @@ -6522,7 +6898,7 @@ static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap, return 0; } -static int isl_map_fast_has_fixed_var(struct isl_map *map, +static int isl_map_plain_has_fixed_var(__isl_keep isl_map *map, unsigned pos, isl_int *val) { int i; @@ -6535,12 +6911,12 @@ static int isl_map_fast_has_fixed_var(struct isl_map *map, if (map->n == 0) return 0; if (map->n == 1) - return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val); + return isl_basic_map_plain_has_fixed_var(map->p[0], pos, val); isl_int_init(v); isl_int_init(tmp); - fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v); + fixed = isl_basic_map_plain_has_fixed_var(map->p[0], pos, &v); for (i = 1; fixed == 1 && i < map->n; ++i) { - fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp); + fixed = isl_basic_map_plain_has_fixed_var(map->p[i], pos, &tmp); if (fixed == 1 && isl_int_ne(tmp, v)) fixed = 0; } @@ -6551,68 +6927,82 @@ static int isl_map_fast_has_fixed_var(struct isl_map *map, return fixed; } -static int isl_basic_set_fast_has_fixed_var(struct isl_basic_set *bset, +static int isl_basic_set_plain_has_fixed_var(__isl_keep isl_basic_set *bset, unsigned pos, isl_int *val) { - return isl_basic_map_fast_has_fixed_var((struct isl_basic_map *)bset, + return isl_basic_map_plain_has_fixed_var((struct isl_basic_map *)bset, pos, val); } -static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos, +static int isl_set_plain_has_fixed_var(__isl_keep isl_set *set, unsigned pos, isl_int *val) { - return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val); + return isl_map_plain_has_fixed_var((struct isl_map *)set, pos, val); } -int isl_basic_map_fast_is_fixed(struct isl_basic_map *bmap, +int isl_basic_map_plain_is_fixed(__isl_keep isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, isl_int *val) { if (pos >= isl_basic_map_dim(bmap, type)) return -1; - return isl_basic_map_fast_has_fixed_var(bmap, + return isl_basic_map_plain_has_fixed_var(bmap, isl_basic_map_offset(bmap, type) - 1 + pos, val); } -int isl_map_fast_is_fixed(struct isl_map *map, +int isl_map_plain_is_fixed(__isl_keep isl_map *map, enum isl_dim_type type, unsigned pos, isl_int *val) { if (pos >= isl_map_dim(map, type)) return -1; - return isl_map_fast_has_fixed_var(map, + return isl_map_plain_has_fixed_var(map, map_offset(map, type) - 1 + pos, val); } +int isl_map_fast_is_fixed(__isl_keep isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int *val) +{ + return isl_map_plain_is_fixed(map, type, pos, val); +} + /* Check if dimension dim has fixed value and if so and if val is not NULL, * then return this fixed value in *val. */ -int isl_basic_set_fast_dim_is_fixed(struct isl_basic_set *bset, unsigned dim, - isl_int *val) +int isl_basic_set_plain_dim_is_fixed(__isl_keep isl_basic_set *bset, + unsigned dim, isl_int *val) { - return isl_basic_set_fast_has_fixed_var(bset, + return isl_basic_set_plain_has_fixed_var(bset, isl_basic_set_n_param(bset) + dim, val); } /* Check if dimension dim has fixed value and if so and if val is not NULL, * then return this fixed value in *val. */ -int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val) +int isl_set_plain_dim_is_fixed(__isl_keep isl_set *set, + unsigned dim, isl_int *val) +{ + return isl_set_plain_has_fixed_var(set, isl_set_n_param(set) + dim, val); +} + +int isl_set_fast_dim_is_fixed(__isl_keep isl_set *set, + unsigned dim, isl_int *val) { - return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val); + return isl_set_plain_dim_is_fixed(set, dim, val); } /* Check if input variable in has fixed value and if so and if val is not NULL, * then return this fixed value in *val. */ -int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val) +int isl_map_plain_input_is_fixed(__isl_keep isl_map *map, + unsigned in, isl_int *val) { - return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val); + return isl_map_plain_has_fixed_var(map, isl_map_n_param(map) + in, val); } /* Check if dimension dim has an (obvious) fixed lower bound and if so * and if val is not NULL, then return this lower bound in *val. */ -int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset, - unsigned dim, isl_int *val) +int isl_basic_set_plain_dim_has_fixed_lower_bound( + __isl_keep isl_basic_set *bset, unsigned dim, isl_int *val) { int i, i_eq = -1, i_ineq = -1; isl_int *c; @@ -6653,7 +7043,7 @@ int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset, return 1; } -int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set, +int isl_set_plain_dim_has_fixed_lower_bound(__isl_keep isl_set *set, unsigned dim, isl_int *val) { int i; @@ -6666,14 +7056,14 @@ int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set, if (set->n == 0) return 0; if (set->n == 1) - return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0], + return isl_basic_set_plain_dim_has_fixed_lower_bound(set->p[0], dim, val); isl_int_init(v); isl_int_init(tmp); - fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0], + fixed = isl_basic_set_plain_dim_has_fixed_lower_bound(set->p[0], dim, &v); for (i = 1; fixed == 1 && i < set->n; ++i) { - fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i], + fixed = isl_basic_set_plain_dim_has_fixed_lower_bound(set->p[i], dim, &tmp); if (fixed == 1 && isl_int_ne(tmp, v)) fixed = 0; @@ -6690,11 +7080,22 @@ struct constraint { isl_int *c; }; +/* uset_gist depends on constraints without existentially quantified + * variables sorting first. + */ static int qsort_constraint_cmp(const void *p1, const void *p2) { const struct constraint *c1 = (const struct constraint *)p1; const struct constraint *c2 = (const struct constraint *)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); + + if (l1 != l2) + return l1 - l2; + return isl_seq_cmp(c1->c, c2->c, size); } @@ -6750,7 +7151,7 @@ struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset) (struct isl_basic_map *)bset); } -int isl_basic_map_fast_cmp(const __isl_keep isl_basic_map *bmap1, +int isl_basic_map_plain_cmp(const __isl_keep isl_basic_map *bmap1, const __isl_keep isl_basic_map *bmap2) { int i, cmp; @@ -6758,6 +7159,9 @@ int isl_basic_map_fast_cmp(const __isl_keep isl_basic_map *bmap1, if (bmap1 == bmap2) return 0; + if (ISL_F_ISSET(bmap1, ISL_BASIC_MAP_RATIONAL) != + ISL_F_ISSET(bmap2, ISL_BASIC_MAP_RATIONAL)) + return ISL_F_ISSET(bmap1, ISL_BASIC_MAP_RATIONAL) ? -1 : 1; if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2)) return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2); if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2)) @@ -6796,16 +7200,16 @@ int isl_basic_map_fast_cmp(const __isl_keep isl_basic_map *bmap1, return 0; } -int isl_basic_map_fast_is_equal(__isl_keep isl_basic_map *bmap1, +int isl_basic_map_plain_is_equal(__isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2) { - return isl_basic_map_fast_cmp(bmap1, bmap2) == 0; + return isl_basic_map_plain_cmp(bmap1, bmap2) == 0; } -int isl_basic_set_fast_is_equal(__isl_keep isl_basic_set *bset1, +int isl_basic_set_plain_is_equal(__isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2) { - return isl_basic_map_fast_is_equal((isl_basic_map *)bset1, + return isl_basic_map_plain_is_equal((isl_basic_map *)bset1, (isl_basic_map *)bset2); } @@ -6814,7 +7218,7 @@ static int qsort_bmap_cmp(const void *p1, const void *p2) const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1; const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2; - return isl_basic_map_fast_cmp(bmap1, bmap2); + return isl_basic_map_plain_cmp(bmap1, bmap2); } /* We normalize in place, but if anything goes wrong we need @@ -6843,7 +7247,7 @@ struct isl_map *isl_map_normalize(struct isl_map *map) if (!map) return NULL; for (i = map->n - 1; i >= 1; --i) { - if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i])) + if (!isl_basic_map_plain_is_equal(map->p[i-1], map->p[i])) continue; isl_basic_map_free(map->p[i-1]); for (j = i; j < map->n; ++j) @@ -6862,7 +7266,7 @@ struct isl_set *isl_set_normalize(struct isl_set *set) return (struct isl_set *)isl_map_normalize((struct isl_map *)set); } -int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2) +int isl_map_plain_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2) { int i; int equal; @@ -6883,7 +7287,7 @@ int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2) goto error; equal = map1->n == map2->n; for (i = 0; equal && i < map1->n; ++i) { - equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]); + equal = isl_basic_map_plain_is_equal(map1->p[i], map2->p[i]); if (equal < 0) goto error; } @@ -6896,12 +7300,22 @@ error: return -1; } -int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2) +int isl_map_fast_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2) +{ + return isl_map_plain_is_equal(map1, map2); +} + +int isl_set_plain_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2) { - return isl_map_fast_is_equal((struct isl_map *)set1, + return isl_map_plain_is_equal((struct isl_map *)set1, (struct isl_map *)set2); } +int isl_set_fast_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2) +{ + return isl_set_plain_is_equal(set1, set2); +} + /* Return an interval that ranges from min to max (inclusive) */ struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx, @@ -7019,8 +7433,8 @@ struct isl_basic_map *isl_basic_map_product( bmap1->n_div + bmap2->n_div, bmap1->n_eq + bmap2->n_eq, bmap1->n_ineq + bmap2->n_ineq); - bmap = add_constraints_dim_map(bmap, bmap1, dim_map1); - bmap = add_constraints_dim_map(bmap, bmap2, dim_map2); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2); bmap = isl_basic_map_simplify(bmap); return isl_basic_map_finalize(bmap); error: @@ -7029,6 +7443,22 @@ error: return NULL; } +__isl_give isl_basic_map *isl_basic_map_flat_product( + __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2) +{ + isl_basic_map *prod; + + prod = isl_basic_map_product(bmap1, bmap2); + prod = isl_basic_map_flatten(prod); + return prod; +} + +__isl_give isl_basic_set *isl_basic_set_flat_product( + __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) +{ + return isl_basic_map_flat_product(bset1, bset2); +} + __isl_give isl_basic_map *isl_basic_map_range_product( __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2) { @@ -7064,8 +7494,8 @@ __isl_give isl_basic_map *isl_basic_map_range_product( bmap1->n_div + bmap2->n_div, bmap1->n_eq + bmap2->n_eq, bmap1->n_ineq + bmap2->n_ineq); - bmap = add_constraints_dim_map(bmap, bmap1, dim_map1); - bmap = add_constraints_dim_map(bmap, bmap2, dim_map2); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1); + bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2); bmap = isl_basic_map_simplify(bmap); return isl_basic_map_finalize(bmap); error: @@ -7074,6 +7504,16 @@ error: return NULL; } +__isl_give isl_basic_map *isl_basic_map_flat_range_product( + __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2) +{ + isl_basic_map *prod; + + prod = isl_basic_map_range_product(bmap1, bmap2); + prod = isl_basic_map_flatten_range(prod); + return prod; +} + static __isl_give isl_map *map_product(__isl_take isl_map *map1, __isl_take isl_map *map2, __isl_give isl_dim *(*dim_product)(__isl_take isl_dim *left, @@ -7144,8 +7584,7 @@ __isl_give isl_map *isl_map_flat_product(__isl_take isl_map *map1, */ struct isl_set *isl_set_product(struct isl_set *set1, struct isl_set *set2) { - return (struct isl_set *)isl_map_product((struct isl_map *)set1, - (struct isl_map *)set2); + return isl_map_range_product(set1, set2); } __isl_give isl_set *isl_set_flat_product(__isl_take isl_set *set1, @@ -7163,6 +7602,18 @@ __isl_give isl_map *isl_map_range_product(__isl_take isl_map *map1, &isl_basic_map_range_product); } +/* Given two maps A -> B and C -> D, construct a map (A * C) -> (B, D) + */ +__isl_give isl_map *isl_map_flat_range_product(__isl_take isl_map *map1, + __isl_take isl_map *map2) +{ + isl_map *prod; + + prod = isl_map_range_product(map1, map2); + prod = isl_map_flatten_range(prod); + return prod; +} + uint32_t isl_basic_map_get_hash(__isl_keep isl_basic_map *bmap) { int i; @@ -7315,15 +7766,12 @@ __isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset) if (!bset) return NULL; - if (bset->n_div == 0) - return bset; - bset = isl_basic_set_cow(bset); if (!bset) return NULL; dim = isl_basic_set_get_dim(bset); - dim = isl_dim_add(dim, isl_dim_set, bset->n_div); + dim = isl_dim_lift(dim, bset->n_div); if (!dim) goto error; isl_dim_free(bset->dim); @@ -7349,8 +7797,6 @@ __isl_give isl_set *isl_set_lift(__isl_take isl_set *set) if (!set) return NULL; - if (set->n == 0 || set->p[0]->n_div == 0) - return set; set = isl_set_cow(set); if (!set) @@ -7358,7 +7804,7 @@ __isl_give isl_set *isl_set_lift(__isl_take isl_set *set) n_div = set->p[0]->n_div; dim = isl_set_get_dim(set); - dim = isl_dim_add(dim, isl_dim_set, n_div); + dim = isl_dim_lift(dim, n_div); if (!dim) goto error; isl_dim_free(set->dim); @@ -7394,11 +7840,11 @@ __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set) dim = isl_set_get_dim(set); if (set->n == 0 || set->p[0]->n_div == 0) { isl_set_free(set); - return isl_map_identity(dim); + return isl_map_identity(isl_dim_map_from_set(dim)); } n_div = set->p[0]->n_div; - dim = isl_dim_map(dim); + dim = isl_dim_map_from_set(dim); n_param = isl_dim_size(dim, isl_dim_param); n_set = isl_dim_size(dim, isl_dim_in); dim = isl_dim_extend(dim, n_param, n_set, n_set + n_div); @@ -7428,6 +7874,8 @@ __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set) } isl_set_free(set); + bmap = isl_basic_map_simplify(bmap); + bmap = isl_basic_map_finalize(bmap); return isl_map_from_basic_map(bmap); error: isl_set_free(set); @@ -7602,7 +8050,7 @@ int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset, * an equality that defines the output dimension in terms of * earlier dimensions. */ -int isl_basic_map_fast_is_single_valued(__isl_keep isl_basic_map *bmap) +int isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap) { int i, j; unsigned total; @@ -7633,10 +8081,8 @@ int isl_basic_map_fast_is_single_valued(__isl_keep isl_basic_map *bmap) /* Check if the given map is obviously single-valued. */ -int isl_map_fast_is_single_valued(__isl_keep isl_map *map) +int isl_map_plain_is_single_valued(__isl_keep isl_map *map) { - int sv; - if (!map) return -1; if (map->n == 0) @@ -7644,7 +8090,7 @@ int isl_map_fast_is_single_valued(__isl_keep isl_map *map) if (map->n >= 2) return 0; - return isl_basic_map_fast_is_single_valued(map->p[0]); + return isl_basic_map_plain_is_single_valued(map->p[0]); } /* Check if the given map is single-valued. @@ -7656,18 +8102,20 @@ int isl_map_fast_is_single_valued(__isl_keep isl_map *map) */ int isl_map_is_single_valued(__isl_keep isl_map *map) { + isl_dim *dim; isl_map *test; isl_map *id; int sv; - sv = isl_map_fast_is_single_valued(map); + sv = isl_map_plain_is_single_valued(map); if (sv < 0 || sv) return sv; test = isl_map_reverse(isl_map_copy(map)); test = isl_map_apply_range(test, isl_map_copy(map)); - id = isl_map_identity(isl_dim_range(isl_map_get_dim(map))); + dim = isl_dim_map_from_set(isl_dim_range(isl_map_get_dim(map))); + id = isl_map_identity(dim); sv = isl_map_is_subset(test, id); @@ -7677,6 +8125,32 @@ int isl_map_is_single_valued(__isl_keep isl_map *map) return sv; } +int isl_map_is_injective(__isl_keep isl_map *map) +{ + int in; + + map = isl_map_copy(map); + map = isl_map_reverse(map); + in = isl_map_is_single_valued(map); + isl_map_free(map); + + return in; +} + +/* Check if the given map is obviously injective. + */ +int isl_map_plain_is_injective(__isl_keep isl_map *map) +{ + int in; + + map = isl_map_copy(map); + map = isl_map_reverse(map); + in = isl_map_plain_is_single_valued(map); + isl_map_free(map); + + return in; +} + int isl_map_is_bijective(__isl_keep isl_map *map) { int sv; @@ -7685,12 +8159,7 @@ int isl_map_is_bijective(__isl_keep isl_map *map) if (sv < 0 || !sv) return sv; - map = isl_map_copy(map); - map = isl_map_reverse(map); - sv = isl_map_is_single_valued(map); - isl_map_free(map); - - return sv; + return isl_map_is_injective(map); } int isl_set_is_singleton(__isl_keep isl_set *set) @@ -7961,6 +8430,31 @@ __isl_give isl_basic_set *isl_basic_set_flatten(__isl_take isl_basic_set *bset) return (isl_basic_set *)isl_basic_map_flatten((isl_basic_map *)bset); } +__isl_give isl_basic_map *isl_basic_map_flatten_range( + __isl_take isl_basic_map *bmap) +{ + if (!bmap) + return NULL; + + if (!bmap->dim->nested[1]) + return bmap; + + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; + + bmap->dim = isl_dim_flatten_range(bmap->dim); + if (!bmap->dim) + goto error; + + bmap = isl_basic_map_finalize(bmap); + + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + __isl_give isl_map *isl_map_flatten(__isl_take isl_map *map) { int i; @@ -8002,57 +8496,39 @@ __isl_give isl_map *isl_set_flatten_map(__isl_take isl_set *set) dim = isl_set_get_dim(set); flat_dim = isl_dim_flatten(isl_dim_copy(dim)); - map = map_identity(isl_dim_join(isl_dim_reverse(dim), flat_dim)); + map = isl_map_identity(isl_dim_join(isl_dim_reverse(dim), flat_dim)); map = isl_map_intersect_domain(map, set); return map; } -/* Extend the given dim_map with mappings for the divs in bmap. - */ -static __isl_give struct isl_dim_map *extend_dim_map( - __isl_keep struct isl_dim_map *dim_map, - __isl_keep isl_basic_map *bmap) +__isl_give isl_map *isl_map_flatten_range(__isl_take isl_map *map) { int i; - struct isl_dim_map *res; - int offset; - offset = isl_basic_map_offset(bmap, isl_dim_div); - - res = isl_dim_map_alloc(bmap->ctx, dim_map->len - 1 + bmap->n_div); - if (!res) + if (!map) return NULL; - for (i = 0; i < dim_map->len; ++i) - res->pos[i] = dim_map->pos[i]; - for (i = 0; i < bmap->n_div; ++i) - res->pos[dim_map->len + i] = offset + i; - - return res; -} - -/* Extract a dim_map from a reordering. - * We essentially need to reverse the mapping, and add an offset - * of 1 for the constant term. - */ -__isl_give struct isl_dim_map *isl_dim_map_from_reordering( - __isl_keep isl_reordering *exp) -{ - int i; - struct isl_dim_map *dim_map; - - if (!exp) - return NULL; + if (!map->dim->nested[1]) + return map; - dim_map = isl_dim_map_alloc(exp->dim->ctx, isl_dim_total(exp->dim)); - if (!dim_map) + map = isl_map_cow(map); + if (!map) return NULL; - for (i = 0; i < exp->len; ++i) - dim_map->pos[1 + exp->pos[i]] = 1 + i; + 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_dim_flatten_range(map->dim); + if (!map->dim) + goto error; - return dim_map; + return map; +error: + isl_map_free(map); + return NULL; } /* Reorder the dimensions of "bmap" according to the given dim_map @@ -8069,7 +8545,7 @@ __isl_give isl_basic_map *isl_basic_map_realign(__isl_take isl_basic_map *bmap, res = isl_basic_map_alloc_dim(dim, bmap->n_div, bmap->n_eq, bmap->n_ineq); - res = add_constraints_dim_map(res, bmap, dim_map); + res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); res = isl_basic_map_finalize(res); return res; error: @@ -8095,7 +8571,7 @@ __isl_give isl_map *isl_map_realign(__isl_take isl_map *map, for (i = 0; i < map->n; ++i) { struct isl_dim_map *dim_map_i; - dim_map_i = extend_dim_map(dim_map, map->p[i]); + dim_map_i = isl_dim_map_extend(dim_map, map->p[i]); map->p[i] = isl_basic_map_realign(map->p[i], isl_dim_copy(r->dim), dim_map_i); @@ -8122,6 +8598,47 @@ __isl_give isl_set *isl_set_realign(__isl_take isl_set *set, return (isl_set *)isl_map_realign((isl_map *)set, r); } +__isl_give isl_map *isl_map_align_params(__isl_take isl_map *map, + __isl_take isl_dim *model) +{ + isl_ctx *ctx; + + if (!map || !model) + goto error; + + ctx = isl_dim_get_ctx(model); + if (!isl_dim_has_named_params(model)) + isl_die(ctx, isl_error_invalid, + "model has unnamed parameters", goto error); + if (!isl_dim_has_named_params(map->dim)) + isl_die(ctx, isl_error_invalid, + "relation has unnamed parameters", goto error); + if (!isl_dim_match(map->dim, isl_dim_param, model, isl_dim_param)) { + isl_reordering *exp; + + model = isl_dim_drop(model, isl_dim_in, + 0, isl_dim_size(model, isl_dim_in)); + model = isl_dim_drop(model, isl_dim_out, + 0, isl_dim_size(model, isl_dim_out)); + exp = isl_parameter_alignment_reordering(map->dim, model); + exp = isl_reordering_extend_dim(exp, isl_map_get_dim(map)); + map = isl_map_realign(map, exp); + } + + isl_dim_free(model); + return map; +error: + isl_dim_free(model); + isl_map_free(map); + return NULL; +} + +__isl_give isl_set *isl_set_align_params(__isl_take isl_set *set, + __isl_take isl_dim *model) +{ + return isl_map_align_params(set, 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, @@ -8283,3 +8800,155 @@ __isl_give isl_basic_set *isl_basic_set_from_constraint_matrices( isl_basic_map_from_constraint_matrices(dim, eq, ineq, c1, c2, c3, c4, isl_dim_in); } + +int isl_basic_map_can_zip(__isl_keep isl_basic_map *bmap) +{ + if (!bmap) + return -1; + + return isl_dim_can_zip(bmap->dim); +} + +int isl_map_can_zip(__isl_keep isl_map *map) +{ + if (!map) + return -1; + + return isl_dim_can_zip(map->dim); +} + +/* Given a basic map (A -> B) -> (C -> D), return the corresponding basic map + * (A -> C) -> (B -> D). + */ +__isl_give isl_basic_map *isl_basic_map_zip(__isl_take isl_basic_map *bmap) +{ + unsigned pos; + unsigned n1; + unsigned n2; + + if (!bmap) + return NULL; + + if (!isl_basic_map_can_zip(bmap)) + isl_die(bmap->ctx, isl_error_invalid, + "basic map cannot be zipped", goto error); + pos = isl_basic_map_offset(bmap, isl_dim_in) + + isl_dim_size(bmap->dim->nested[0], isl_dim_in); + n1 = isl_dim_size(bmap->dim->nested[0], isl_dim_out); + n2 = isl_dim_size(bmap->dim->nested[1], isl_dim_in); + bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2); + if (!bmap) + return NULL; + bmap->dim = isl_dim_zip(bmap->dim); + if (!bmap->dim) + goto error; + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* Given a map (A -> B) -> (C -> D), return the corresponding map + * (A -> C) -> (B -> D). + */ +__isl_give isl_map *isl_map_zip(__isl_take isl_map *map) +{ + int i; + + if (!map) + return NULL; + + if (!isl_map_can_zip(map)) + isl_die(map->ctx, isl_error_invalid, "map cannot be zipped", + goto error); + + map = isl_map_cow(map); + if (!map) + return NULL; + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_zip(map->p[i]); + if (!map->p[i]) + goto error; + } + + map->dim = isl_dim_zip(map->dim); + if (!map->dim) + goto error; + + return map; +error: + isl_map_free(map); + return NULL; +} + +/* Construct a basic map mapping the domain of the affine expression + * to a one-dimensional range prescribed by the affine expression. + */ +__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); + ls = isl_local_space_from_domain(ls); + ls = isl_local_space_add_dims(ls, isl_dim_out, 1); + 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 basic map mapping a domain in the given space to + * to an n-dimensional range, with n the number of elements in the list, + * where each coordinate in the range is prescribed by the + * corresponding affine expression. + * The domains of all affine expressions in the list are assumed to match + * domain_dim. + */ +__isl_give isl_basic_map *isl_basic_map_from_aff_list( + __isl_take isl_dim *domain_dim, __isl_take isl_aff_list *list) +{ + int i; + isl_dim *dim; + isl_basic_map *bmap; + + if (!list) + return NULL; + + dim = isl_dim_from_domain(domain_dim); + bmap = isl_basic_map_universe(dim); + + for (i = 0; i < list->n; ++i) { + isl_aff *aff; + isl_basic_map *bmap_i; + + aff = isl_aff_copy(list->p[i]); + bmap_i = isl_basic_map_from_aff(aff); + + bmap = isl_basic_map_flat_range_product(bmap, bmap_i); + } + + isl_aff_list_free(list); + return bmap; +}