X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=335fad03e26b30fa379d4f149a6fefb5112093fc;hb=89ee10a4972925da0f1f909eef916f161acd692d;hp=c7d49cc81ac9f976726827e2b38f623e7974cbb0;hpb=51e5423a14fcb9bdaa495bedb87301ca7f3d7817;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index c7d49cc..335fad0 100644 --- a/isl_map.c +++ b/isl_map.c @@ -12,21 +12,21 @@ #include #include -#include "isl_ctx.h" -#include "isl_blk.h" +#include +#include #include "isl_dim_private.h" #include "isl_equalities.h" -#include "isl_list.h" -#include "isl_lp.h" -#include "isl_seq.h" -#include "isl_set.h" -#include "isl_map.h" +#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 "isl_vec.h" +#include #include /* Maps dst positions to src positions */ @@ -1410,15 +1410,6 @@ __isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set, return isl_set_eliminate(set, isl_dim_set, first, n); } -/* Project out n dimensions starting at first using Fourier-Motzkin */ -struct isl_set *isl_set_remove_dims(struct isl_set *set, - unsigned first, unsigned n) -{ - set = isl_set_eliminate_dims(set, first, n); - set = isl_set_drop_dims(set, first, n); - return set; -} - __isl_give isl_basic_map *isl_basic_map_remove_divs( __isl_take isl_basic_map *bmap) { @@ -1461,7 +1452,7 @@ error: return NULL; } -struct isl_basic_map *isl_basic_map_remove(struct isl_basic_map *bmap, +struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap, enum isl_dim_type type, unsigned first, unsigned n) { if (!bmap) @@ -1483,14 +1474,99 @@ error: return NULL; } -__isl_give isl_basic_set *isl_basic_set_remove(__isl_take isl_basic_set *bset, +/* Return true if the definition of the given div (recursively) involves + * any of the given variables. + */ +static int div_involves_vars(__isl_keep isl_basic_map *bmap, int div, + unsigned first, unsigned n) +{ + int i; + unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div); + + if (isl_int_is_zero(bmap->div[div][0])) + return 0; + if (isl_seq_first_non_zero(bmap->div[div] + 1 + first, n) >= 0) + return 1; + + for (i = bmap->n_div - 1; i >= 0; --i) { + if (isl_int_is_zero(bmap->div[div][1 + div_offset + i])) + continue; + if (div_involves_vars(bmap, i, first, n)) + return 1; + } + + return 0; +} + +/* Remove all divs (recursively) involving any of the given dimensions + * in their definitions. + */ +__isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + int i; + + if (!bmap) + return NULL; + isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), + goto error); + first += isl_basic_map_offset(bmap, type); + + for (i = bmap->n_div - 1; i >= 0; --i) { + if (!div_involves_vars(bmap, i, first, n)) + continue; + bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1); + } + + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map, + enum isl_dim_type type, unsigned first, unsigned n) +{ + int i; + + if (!map) + return NULL; + if (map->n == 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_remove_divs_involving_dims(map->p[i], + type, first, n); + if (!map->p[i]) + goto error; + } + return map; +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return (isl_set *)isl_map_remove_divs_involving_dims((isl_map *)set, + type, first, n); +} + +__isl_give isl_basic_set *isl_basic_set_remove_dims( + __isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned first, unsigned n) { return (isl_basic_set *) - isl_basic_map_remove((isl_basic_map *)bset, type, first, n); + isl_basic_map_remove_dims((isl_basic_map *)bset, type, first, n); } -struct isl_map *isl_map_remove(struct isl_map *map, +struct isl_map *isl_map_remove_dims(struct isl_map *map, enum isl_dim_type type, unsigned first, unsigned n) { int i; @@ -1516,27 +1592,17 @@ error: return NULL; } -__isl_give isl_set *isl_set_remove(__isl_take isl_set *bset, +__isl_give isl_set *isl_set_remove_dims(__isl_take isl_set *bset, enum isl_dim_type type, unsigned first, unsigned n) { - return (isl_set *)isl_map_remove((isl_map *)bset, type, first, n); + return (isl_set *)isl_map_remove_dims((isl_map *)bset, type, first, n); } /* Project out n inputs starting at first using Fourier-Motzkin */ struct isl_map *isl_map_remove_inputs(struct isl_map *map, unsigned first, unsigned n) { - return isl_map_remove(map, isl_dim_in, first, n); -} - -/* Project out n dimensions starting at first using Fourier-Motzkin */ -struct isl_basic_set *isl_basic_set_remove_dims(struct isl_basic_set *bset, - unsigned first, unsigned n) -{ - unsigned nparam = isl_basic_set_n_param(bset); - bset = isl_basic_set_eliminate_vars(bset, nparam + first, n); - bset = isl_basic_set_drop_dims(bset, first, n); - return bset; + return isl_map_remove_dims(map, isl_dim_in, first, n); } static void dump_term(struct isl_basic_map *bmap, @@ -2529,7 +2595,7 @@ __isl_give isl_basic_map *isl_basic_map_project_out( return NULL; if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) - return isl_basic_map_remove(bmap, type, first, n); + return isl_basic_map_remove_dims(bmap, type, first, n); isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), goto error); @@ -3427,7 +3493,9 @@ struct isl_basic_set *isl_basic_map_underlying_set( if (!bmap) goto error; if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && - bmap->n_div == 0 && !isl_dim_get_tuple_name(bmap->dim, isl_dim_out)) + bmap->n_div == 0 && + !isl_dim_is_named_or_nested(bmap->dim, isl_dim_in) && + !isl_dim_is_named_or_nested(bmap->dim, isl_dim_out)) return (struct isl_basic_set *)bmap; bmap = isl_basic_map_cow(bmap); if (!bmap) @@ -5503,12 +5571,54 @@ error: return NULL; } +/* Construct the half-space x_pos >= 0. + */ +static __isl_give isl_basic_set *nonneg_halfspace(__isl_take isl_dim *dim, + int pos) +{ + int k; + isl_basic_set *nonneg; + + nonneg = isl_basic_set_alloc_dim(dim, 0, 0, 1); + k = isl_basic_set_alloc_inequality(nonneg); + if (k < 0) + goto error; + isl_seq_clr(nonneg->ineq[k], 1 + isl_basic_set_total_dim(nonneg)); + isl_int_set_si(nonneg->ineq[k][pos], 1); + + return isl_basic_set_finalize(nonneg); +error: + isl_basic_set_free(nonneg); + return NULL; +} + +/* Construct the half-space x_pos <= -1. + */ +static __isl_give isl_basic_set *neg_halfspace(__isl_take isl_dim *dim, int pos) +{ + int k; + isl_basic_set *neg; + + neg = isl_basic_set_alloc_dim(dim, 0, 0, 1); + k = isl_basic_set_alloc_inequality(neg); + if (k < 0) + goto error; + isl_seq_clr(neg->ineq[k], 1 + isl_basic_set_total_dim(neg)); + isl_int_set_si(neg->ineq[k][0], -1); + isl_int_set_si(neg->ineq[k][pos], -1); + + return isl_basic_set_finalize(neg); +error: + isl_basic_set_free(neg); + return NULL; +} + __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set, enum isl_dim_type type, unsigned first, unsigned n) { int i; - isl_basic_set *nonneg = NULL; - isl_basic_set *neg = NULL; + isl_basic_set *nonneg; + isl_basic_set *neg; if (!set) return NULL; @@ -5518,35 +5628,84 @@ __isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set, isl_assert(set->ctx, first + n <= isl_set_dim(set, type), goto error); for (i = 0; i < n; ++i) { - int k; - - neg = NULL; - nonneg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1); - k = isl_basic_set_alloc_inequality(nonneg); - if (k < 0) - goto error; - isl_seq_clr(nonneg->ineq[k], 1 + isl_basic_set_total_dim(nonneg)); - isl_int_set_si(nonneg->ineq[k][pos(set->dim, type) + first + i], 1); - - neg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1); - k = isl_basic_set_alloc_inequality(neg); - if (k < 0) - goto error; - isl_seq_clr(neg->ineq[k], 1 + isl_basic_set_total_dim(neg)); - isl_int_set_si(neg->ineq[k][0], -1); - isl_int_set_si(neg->ineq[k][pos(set->dim, type) + first + i], -1); + nonneg = nonneg_halfspace(isl_set_get_dim(set), + pos(set->dim, type) + first + i); + neg = neg_halfspace(isl_set_get_dim(set), + pos(set->dim, type) + first + i); set = isl_set_intersect(set, isl_basic_set_union(nonneg, neg)); } return set; error: - isl_basic_set_free(nonneg); - isl_basic_set_free(neg); isl_set_free(set); return NULL; } +static int foreach_orthant(__isl_take isl_set *set, int *signs, int first, + int len, int (*fn)(__isl_take isl_set *orthant, int *signs, void *user), + void *user) +{ + isl_set *half; + + if (!set) + return -1; + if (isl_set_fast_is_empty(set)) { + isl_set_free(set); + return 0; + } + if (first == len) + return fn(set, signs, user); + + signs[first] = 1; + half = isl_set_from_basic_set(nonneg_halfspace(isl_set_get_dim(set), + 1 + first)); + half = isl_set_intersect(half, isl_set_copy(set)); + if (foreach_orthant(half, signs, first + 1, len, fn, user) < 0) + goto error; + + signs[first] = -1; + half = isl_set_from_basic_set(neg_halfspace(isl_set_get_dim(set), + 1 + first)); + half = isl_set_intersect(half, set); + return foreach_orthant(half, signs, first + 1, len, fn, user); +error: + isl_set_free(set); + return -1; +} + +/* Call "fn" on the intersections of "set" with each of the orthants + * (except for obviously empty intersections). The orthant is identified + * by the signs array, with each entry having value 1 or -1 according + * to the sign of the corresponding variable. + */ +int isl_set_foreach_orthant(__isl_keep isl_set *set, + int (*fn)(__isl_take isl_set *orthant, int *signs, void *user), + void *user) +{ + unsigned nparam; + unsigned nvar; + int *signs; + int r; + + if (!set) + return -1; + if (isl_set_fast_is_empty(set)) + return 0; + + nparam = isl_set_dim(set, isl_dim_param); + nvar = isl_set_dim(set, isl_dim_set); + + signs = isl_alloc_array(set->ctx, int, nparam + nvar); + + r = foreach_orthant(isl_set_copy(set), signs, 0, nparam + nvar, + fn, user); + + free(signs); + + return r; +} + int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2) { return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2); @@ -7592,6 +7751,19 @@ __isl_give isl_set *isl_set_flatten(__isl_take isl_set *set) return (isl_set *)isl_map_flatten((isl_map *)set); } +__isl_give isl_map *isl_set_flatten_map(__isl_take isl_set *set) +{ + isl_dim *dim, *flat_dim; + isl_map *map; + + 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_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( @@ -7839,6 +8011,22 @@ error: return NULL; } +__isl_give isl_mat *isl_basic_set_equalities_matrix( + __isl_keep isl_basic_set *bset, enum isl_dim_type c1, + enum isl_dim_type c2, enum isl_dim_type c3, enum isl_dim_type c4) +{ + return isl_basic_map_equalities_matrix((isl_basic_map *)bset, + c1, c2, c3, c4, isl_dim_in); +} + +__isl_give isl_mat *isl_basic_set_inequalities_matrix( + __isl_keep isl_basic_set *bset, enum isl_dim_type c1, + enum isl_dim_type c2, enum isl_dim_type c3, enum isl_dim_type c4) +{ + return isl_basic_map_inequalities_matrix((isl_basic_map *)bset, + c1, c2, c3, c4, isl_dim_in); +} + __isl_give isl_basic_set *isl_basic_set_from_constraint_matrices( __isl_take isl_dim *dim, __isl_take isl_mat *eq, __isl_take isl_mat *ineq, enum isl_dim_type c1,