X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=26eb7d26505eeb8b8471cb5b6f563eb40078ba13;hb=46736fc916f931e773864fe5656a551d03874040;hp=58ac0ffe133843c830cb07e876d7cc0166502ec7;hpb=75688a45544b4487feaf63e423cb520be5312dbe;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index 58ac0ff..26eb7d2 100644 --- a/isl_map.c +++ b/isl_map.c @@ -122,6 +122,8 @@ unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset) unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset) { + if (!bset) + return 0; return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div; } @@ -255,25 +257,42 @@ __isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset) return isl_space_copy(bset->dim); } -__isl_give isl_local_space *isl_basic_map_get_local_space( - __isl_keep isl_basic_map *bmap) +/* Extract the divs in "bmap" as a matrix. + */ +__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap) { int i; - isl_local_space *ls; + isl_ctx *ctx; + isl_mat *div; unsigned total; + unsigned cols; if (!bmap) return NULL; - total = isl_basic_map_total_dim(bmap); - ls = isl_local_space_alloc(isl_space_copy(bmap->dim), bmap->n_div); - if (!ls) + ctx = isl_basic_map_get_ctx(bmap); + total = isl_space_dim(bmap->dim, isl_dim_all); + cols = 1 + 1 + total + bmap->n_div; + div = isl_mat_alloc(ctx, bmap->n_div, cols); + if (!div) return NULL; for (i = 0; i < bmap->n_div; ++i) - isl_seq_cpy(ls->div->row[i], bmap->div[i], 2 + total); + isl_seq_cpy(div->row[i], bmap->div[i], cols); + + return div; +} + +__isl_give isl_local_space *isl_basic_map_get_local_space( + __isl_keep isl_basic_map *bmap) +{ + isl_mat *div; - return ls; + if (!bmap) + return NULL; + + div = isl_basic_map_get_divs(bmap); + return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div); } __isl_give isl_local_space *isl_basic_set_get_local_space( @@ -455,6 +474,14 @@ __isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set) return isl_map_get_tuple_id(set, isl_dim_set); } +/* Does the set tuple have a name? + */ +int isl_set_has_tuple_name(__isl_keep isl_set *set) +{ + return set ? isl_space_has_tuple_name(set->dim, isl_dim_set) : -1; +} + + const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset) { return bset ? isl_space_get_tuple_name(bset->dim, isl_dim_set) : NULL; @@ -507,7 +534,7 @@ __isl_give isl_basic_map *isl_basic_map_set_dim_name( bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s); if (!bmap->dim) goto error; - return bmap; + return isl_basic_map_finalize(bmap); error: isl_basic_map_free(bmap); return NULL; @@ -558,6 +585,12 @@ int isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap, return bmap ? isl_space_has_dim_id(bmap->dim, type, pos) : -1; } +__isl_give isl_id *isl_basic_set_get_dim_id(__isl_keep isl_basic_set *bset, + enum isl_dim_type type, unsigned pos) +{ + return bset ? isl_space_get_dim_id(bset->dim, type, pos) : NULL; +} + int isl_map_has_dim_id(__isl_keep isl_map *map, enum isl_dim_type type, unsigned pos) { @@ -1561,8 +1594,8 @@ void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b) } /* Eliminate the specified n dimensions starting at first from the - * constraints using Fourier-Motzkin. The dimensions themselves - * are not removed. + * constraints, without removing the dimensions from the space. + * If the set is rational, the dimensions are eliminated using Fourier-Motzkin. */ __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map, enum isl_dim_type type, unsigned first, unsigned n) @@ -1574,6 +1607,10 @@ __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map, if (n == 0) return map; + if (first + n > isl_map_dim(map, type) || first + n < first) + isl_die(map->ctx, isl_error_invalid, + "index out of bounds", goto error); + map = isl_map_cow(map); if (!map) return NULL; @@ -1590,8 +1627,8 @@ error: } /* Eliminate the specified n dimensions starting at first from the - * constraints using Fourier-Motzkin. The dimensions themselves - * are not removed. + * constraints, without removing the dimensions from the space. + * If the set is rational, the dimensions are eliminated using Fourier-Motzkin. */ __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set, enum isl_dim_type type, unsigned first, unsigned n) @@ -1600,8 +1637,8 @@ __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set, } /* Eliminate the specified n dimensions starting at first from the - * constraints using Fourier-Motzkin. The dimensions themselves - * are not removed. + * constraints, without removing the dimensions from the space. + * If the set is rational, the dimensions are eliminated using Fourier-Motzkin. */ __isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set, unsigned first, unsigned n) @@ -2702,6 +2739,10 @@ __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap, bmap->n_div, bmap->n_eq, bmap->n_ineq); if (isl_basic_map_is_rational(bmap)) res = isl_basic_map_set_rational(res); + if (isl_basic_map_plain_is_empty(bmap)) { + isl_basic_map_free(bmap); + return isl_basic_map_set_to_empty(res); + } res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map); return isl_basic_map_finalize(res); } @@ -6429,7 +6470,7 @@ error: /* * returns range - domain */ -struct isl_set *isl_map_deltas(struct isl_map *map) +__isl_give isl_set *isl_map_deltas(__isl_take isl_map *map) { int i; isl_space *dim; @@ -7066,7 +7107,7 @@ struct isl_map *isl_basic_map_union( { struct isl_map *map; if (!bmap1 || !bmap2) - return NULL; + goto error; isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim), goto error); @@ -8931,6 +8972,39 @@ int isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap) return 1; } +/* Check if the given basic map is single-valued. + * We simply compute + * + * M \circ M^-1 + * + * and check if the result is a subset of the identity mapping. + */ +int isl_basic_map_is_single_valued(__isl_keep isl_basic_map *bmap) +{ + isl_space *space; + isl_basic_map *test; + isl_basic_map *id; + int sv; + + sv = isl_basic_map_plain_is_single_valued(bmap); + if (sv < 0 || sv) + return sv; + + test = isl_basic_map_reverse(isl_basic_map_copy(bmap)); + test = isl_basic_map_apply_range(test, isl_basic_map_copy(bmap)); + + space = isl_basic_map_get_space(bmap); + space = isl_space_map_from_set(isl_space_range(space)); + id = isl_basic_map_identity(space); + + sv = isl_basic_map_is_subset(test, id); + + isl_basic_map_free(test); + isl_basic_map_free(id); + + return sv; +} + /* Check if the given map is obviously single-valued. */ int isl_map_plain_is_single_valued(__isl_keep isl_map *map) @@ -9749,6 +9823,7 @@ __isl_give isl_basic_map *isl_basic_map_zip(__isl_take isl_basic_map *bmap) isl_space_dim(bmap->dim->nested[0], isl_dim_in); n1 = isl_space_dim(bmap->dim->nested[0], isl_dim_out); n2 = isl_space_dim(bmap->dim->nested[1], isl_dim_in); + bmap = isl_basic_map_cow(bmap); bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2); if (!bmap) return NULL; @@ -9795,6 +9870,83 @@ error: return NULL; } +/* Can we apply isl_basic_map_curry to "bmap"? + * That is, does it have a nested relation in its domain? + */ +int isl_basic_map_can_curry(__isl_keep isl_basic_map *bmap) +{ + if (!bmap) + return -1; + + return isl_space_can_curry(bmap->dim); +} + +/* Can we apply isl_map_curry to "map"? + * That is, does it have a nested relation in its domain? + */ +int isl_map_can_curry(__isl_keep isl_map *map) +{ + if (!map) + return -1; + + return isl_space_can_curry(map->dim); +} + +/* Given a basic map (A -> B) -> C, return the corresponding basic map + * A -> (B -> C). + */ +__isl_give isl_basic_map *isl_basic_map_curry(__isl_take isl_basic_map *bmap) +{ + + if (!bmap) + return NULL; + + if (!isl_basic_map_can_curry(bmap)) + isl_die(bmap->ctx, isl_error_invalid, + "basic map cannot be curried", goto error); + bmap->dim = isl_space_curry(bmap->dim); + if (!bmap->dim) + goto error; + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* Given a map (A -> B) -> C, return the corresponding map + * A -> (B -> C). + */ +__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); + + map = isl_map_cow(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; + } + + map->dim = isl_space_curry(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. */ @@ -9830,6 +9982,17 @@ error: return NULL; } +/* Construct a map mapping the domain of the affine expression + * to a one-dimensional range prescribed by the affine expression. + */ +__isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff) +{ + isl_basic_map *bmap; + + bmap = isl_basic_map_from_aff(aff); + return isl_map_from_basic_map(bmap); +} + /* Construct a basic map mapping the domain the multi-affine expression * to its range, with each dimension in the range equated to the * corresponding affine expression. @@ -9867,6 +10030,18 @@ __isl_give isl_basic_map *isl_basic_map_from_multi_aff( return bmap; } +/* Construct a map mapping the domain the multi-affine expression + * to its range, with each dimension in the range equated to the + * corresponding affine expression. + */ +__isl_give isl_map *isl_map_from_multi_aff(__isl_take isl_multi_aff *maff) +{ + isl_basic_map *bmap; + + bmap = isl_basic_map_from_multi_aff(maff); + return isl_map_from_basic_map(bmap); +} + /* 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 @@ -9907,11 +10082,78 @@ __isl_give isl_set *isl_set_equate(__isl_take isl_set *set, return isl_map_equate(set, type1, pos1, type2, pos2); } +/* Construct a basic map where the given dimensions are equal to each other. + */ +static __isl_give isl_basic_map *equator(__isl_take isl_space *space, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + isl_basic_map *bmap = NULL; + int i; + + if (!space) + return NULL; + + if (pos1 >= isl_space_dim(space, type1)) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "index out of bounds", goto error); + if (pos2 >= isl_space_dim(space, type2)) + isl_die(isl_space_get_ctx(space), isl_error_invalid, + "index out of bounds", goto error); + + if (type1 == type2 && pos1 == pos2) + return isl_basic_map_universe(space); + + bmap = isl_basic_map_alloc_space(isl_space_copy(space), 0, 1, 0); + i = isl_basic_map_alloc_equality(bmap); + if (i < 0) + goto error; + isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap)); + pos1 += isl_basic_map_offset(bmap, type1); + pos2 += isl_basic_map_offset(bmap, type2); + isl_int_set_si(bmap->eq[i][pos1], -1); + isl_int_set_si(bmap->eq[i][pos2], 1); + bmap = isl_basic_map_finalize(bmap); + isl_space_free(space); + return bmap; +error: + isl_space_free(space); + isl_basic_map_free(bmap); + return NULL; +} + +/* Add a constraint imposing that the given two dimensions are equal. + */ +__isl_give isl_basic_map *isl_basic_map_equate(__isl_take isl_basic_map *bmap, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + isl_basic_map *eq; + + eq = equator(isl_basic_map_get_space(bmap), type1, pos1, type2, pos2); + + bmap = isl_basic_map_intersect(bmap, eq); + + return bmap; +} + /* Add a constraint imposing that the given two dimensions are equal. */ __isl_give isl_map *isl_map_equate(__isl_take isl_map *map, enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) { + isl_basic_map *bmap; + + bmap = equator(isl_map_get_space(map), type1, pos1, type2, pos2); + + map = isl_map_intersect(map, isl_map_from_basic_map(bmap)); + + return map; +} + +/* Add a constraint imposing that the given two dimensions have opposite values. + */ +__isl_give isl_map *isl_map_oppose(__isl_take isl_map *map, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ isl_basic_map *bmap = NULL; int i; @@ -9932,7 +10174,7 @@ __isl_give isl_map *isl_map_equate(__isl_take isl_map *map, isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap)); pos1 += isl_basic_map_offset(bmap, type1); pos2 += isl_basic_map_offset(bmap, type2); - isl_int_set_si(bmap->eq[i][pos1], -1); + isl_int_set_si(bmap->eq[i][pos1], 1); isl_int_set_si(bmap->eq[i][pos2], 1); bmap = isl_basic_map_finalize(bmap); @@ -9945,9 +10187,10 @@ error: return NULL; } -/* Add a constraint imposing that the given two dimensions have opposite values. +/* Add a constraint imposing that the value of the first dimension is + * greater than that of the second. */ -__isl_give isl_map *isl_map_oppose(__isl_take isl_map *map, +__isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map, enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) { isl_basic_map *bmap = NULL; @@ -9963,15 +10206,22 @@ __isl_give isl_map *isl_map_oppose(__isl_take isl_map *map, isl_die(map->ctx, isl_error_invalid, "index out of bounds", goto error); - bmap = isl_basic_map_alloc_space(isl_map_get_space(map), 0, 1, 0); - i = isl_basic_map_alloc_equality(bmap); + if (type1 == type2 && pos1 == pos2) { + isl_space *space = isl_map_get_space(map); + isl_map_free(map); + return isl_map_empty(space); + } + + bmap = isl_basic_map_alloc_space(isl_map_get_space(map), 0, 0, 1); + i = isl_basic_map_alloc_inequality(bmap); if (i < 0) goto error; - isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap)); + isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap)); pos1 += isl_basic_map_offset(bmap, type1); pos2 += isl_basic_map_offset(bmap, type2); - isl_int_set_si(bmap->eq[i][pos1], 1); - isl_int_set_si(bmap->eq[i][pos2], 1); + isl_int_set_si(bmap->ineq[i][pos1], 1); + isl_int_set_si(bmap->ineq[i][pos2], -1); + isl_int_set_si(bmap->ineq[i][0], -1); bmap = isl_basic_map_finalize(bmap); map = isl_map_intersect(map, isl_map_from_basic_map(bmap)); @@ -9983,6 +10233,15 @@ error: return NULL; } +/* Add a constraint imposing that the value of the first dimension is + * smaller than that of the second. + */ +__isl_give isl_map *isl_map_order_lt(__isl_take isl_map *map, + enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2) +{ + return isl_map_order_gt(map, type2, pos2, type1, pos1); +} + __isl_give isl_aff *isl_basic_map_get_div(__isl_keep isl_basic_map *bmap, int pos) {