X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_convex_hull.c;h=40cca1b74ed4fa4c51bc3e6645a6bcc1099cdc04;hb=a41dca96db00c891c58a4535bb8920b5ed70e682;hp=ac7982525d5046761ff87c44af8dcbb0e3fa763e;hpb=a49ca3fe0516ba6b190f60cb6233989121b29955;p=platform%2Fupstream%2Fisl.git diff --git a/isl_convex_hull.c b/isl_convex_hull.c index ac79825..40cca1b 100644 --- a/isl_convex_hull.c +++ b/isl_convex_hull.c @@ -7,12 +7,12 @@ * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium */ -#include "isl_lp.h" -#include "isl_map.h" +#include +#include #include "isl_map_private.h" -#include "isl_mat.h" -#include "isl_set.h" -#include "isl_seq.h" +#include +#include +#include #include "isl_equalities.h" #include "isl_tab.h" @@ -79,7 +79,7 @@ int isl_basic_set_constraint_is_redundant(struct isl_basic_set **bset, (struct isl_basic_map **)bset, c, opt_n, opt_d); } -/* Compute the convex hull of a basic map, by removing the redundant +/* Remove redundant * constraints. If the minimal value along the normal of a constraint * is the same if the constraint is removed, then the constraint is redundant. * @@ -87,7 +87,8 @@ int isl_basic_set_constraint_is_redundant(struct isl_basic_set **bset, * corresponding equality and the checked if the dimension was that * of a facet. */ -struct isl_basic_map *isl_basic_map_convex_hull(struct isl_basic_map *bmap) +__isl_give isl_basic_map *isl_basic_map_remove_redundancies( + __isl_take isl_basic_map *bmap) { struct isl_tab *tab; @@ -118,10 +119,11 @@ error: return NULL; } -struct isl_basic_set *isl_basic_set_convex_hull(struct isl_basic_set *bset) +__isl_give isl_basic_set *isl_basic_set_remove_redundancies( + __isl_take isl_basic_set *bset) { return (struct isl_basic_set *) - isl_basic_map_convex_hull((struct isl_basic_map *)bset); + isl_basic_map_remove_redundancies((struct isl_basic_map *)bset); } /* Check if the set set is bound in the direction of the affine @@ -425,6 +427,7 @@ isl_int *isl_set_wrap_facet(__isl_keep isl_set *set, if (res == isl_lp_ok) { isl_int_neg(num, num); isl_seq_combine(facet, num, facet, den, ridge, dim); + isl_seq_normalize(ctx, facet, dim); } isl_int_clear(num); isl_int_clear(den); @@ -473,7 +476,9 @@ static __isl_give isl_mat *initial_facet_constraint(__isl_keep isl_set *set) isl_seq_clr(bounds->row[0], dim); isl_int_set_si(bounds->row[0][1 + dim - 1], 1); is_bound = uset_is_bound(set, bounds->row[0], 1 + dim); - isl_assert(set->ctx, is_bound == 1, goto error); + if (is_bound < 0) + goto error; + isl_assert(set->ctx, is_bound, goto error); isl_seq_normalize(set->ctx, bounds->row[0], 1 + dim); bounds->n_row = 1; @@ -785,7 +790,7 @@ error: static struct isl_set *set_project_out(struct isl_ctx *ctx, struct isl_set *set, unsigned n) { - return isl_set_remove_dims(set, isl_set_n_dim(set) - n, n); + return isl_set_remove_dims(set, isl_dim_set, isl_set_n_dim(set) - n, n); } static struct isl_basic_set *convex_hull_0d(struct isl_set *set) @@ -864,8 +869,8 @@ static struct isl_basic_set *convex_hull_pair_elim(struct isl_basic_set *bset1, isl_int_set_si(hull->eq[k][2*(1+dim)+j], 1); } hull = isl_basic_set_set_rational(hull); - hull = isl_basic_set_remove_dims(hull, dim, 2*(1+dim)); - hull = isl_basic_set_convex_hull(hull); + hull = isl_basic_set_remove_dims(hull, isl_dim_set, dim, 2*(1+dim)); + hull = isl_basic_set_remove_redundancies(hull); isl_basic_set_free(bset1); isl_basic_set_free(bset2); return hull; @@ -894,6 +899,25 @@ int isl_basic_set_is_bounded(__isl_keep isl_basic_set *bset) return bounded; } +/* Is the image bounded for each value of the parameters and + * the domain variables? + */ +int isl_basic_map_image_is_bounded(__isl_keep isl_basic_map *bmap) +{ + unsigned nparam = isl_basic_map_dim(bmap, isl_dim_param); + unsigned n_in = isl_basic_map_dim(bmap, isl_dim_in); + int bounded; + + bmap = isl_basic_map_copy(bmap); + bmap = isl_basic_map_cow(bmap); + bmap = isl_basic_map_move_dims(bmap, isl_dim_param, nparam, + isl_dim_in, 0, n_in); + bounded = isl_basic_set_is_bounded((isl_basic_set *)bmap); + isl_basic_map_free(bmap); + + return bounded; +} + /* Is the set bounded for each value of the parameters? */ int isl_set_is_bounded(__isl_keep isl_set *set) @@ -1019,7 +1043,7 @@ static struct isl_basic_set *modulo_lineality(struct isl_set *set, Q = isl_mat_lin_to_aff(Q); set = isl_set_preimage(set, U); - set = isl_set_remove_dims(set, total - lin_dim, lin_dim); + set = isl_set_remove_dims(set, isl_dim_set, total - lin_dim, lin_dim); hull = uset_convex_hull(set); hull = isl_basic_set_preimage(hull, Q); @@ -1070,23 +1094,25 @@ static struct isl_basic_set *valid_direction_lp( if (k < 0) goto error; n = 0; - isl_int_set_si(lp->eq[k][n++], 0); + isl_int_set_si(lp->eq[k][n], 0); n++; /* positivity constraint 1 >= 0 */ - isl_int_set_si(lp->eq[k][n++], i == 0); + isl_int_set_si(lp->eq[k][n], i == 0); n++; for (j = 0; j < bset1->n_eq; ++j) { - isl_int_set(lp->eq[k][n++], bset1->eq[j][i]); - isl_int_neg(lp->eq[k][n++], bset1->eq[j][i]); + isl_int_set(lp->eq[k][n], bset1->eq[j][i]); n++; + isl_int_neg(lp->eq[k][n], bset1->eq[j][i]); n++; + } + for (j = 0; j < bset1->n_ineq; ++j) { + isl_int_set(lp->eq[k][n], bset1->ineq[j][i]); n++; } - for (j = 0; j < bset1->n_ineq; ++j) - isl_int_set(lp->eq[k][n++], bset1->ineq[j][i]); /* positivity constraint 1 >= 0 */ - isl_int_set_si(lp->eq[k][n++], -(i == 0)); + isl_int_set_si(lp->eq[k][n], -(i == 0)); n++; for (j = 0; j < bset2->n_eq; ++j) { - isl_int_neg(lp->eq[k][n++], bset2->eq[j][i]); - isl_int_set(lp->eq[k][n++], bset2->eq[j][i]); + isl_int_neg(lp->eq[k][n], bset2->eq[j][i]); n++; + isl_int_set(lp->eq[k][n], bset2->eq[j][i]); n++; + } + for (j = 0; j < bset2->n_ineq; ++j) { + isl_int_neg(lp->eq[k][n], bset2->ineq[j][i]); n++; } - for (j = 0; j < bset2->n_ineq; ++j) - isl_int_neg(lp->eq[k][n++], bset2->ineq[j][i]); } lp = isl_basic_set_gauss(lp, NULL); isl_basic_set_free(bset1); @@ -1146,7 +1172,7 @@ static struct isl_vec *valid_direction( isl_seq_clr(dir->block.data + 1, dir->size - 1); n = 1; /* positivity constraint 1 >= 0 */ - isl_int_set(dir->block.data[0], sample->block.data[n++]); + isl_int_set(dir->block.data[0], sample->block.data[n]); n++; for (i = 0; i < bset1->n_eq; ++i) { isl_int_sub(sample->block.data[n], sample->block.data[n], sample->block.data[n+1]); @@ -1930,6 +1956,19 @@ struct isl_basic_set *isl_set_convex_hull(struct isl_set *set) isl_map_convex_hull((struct isl_map *)set); } +__isl_give isl_basic_map *isl_map_polyhedral_hull(__isl_take isl_map *map) +{ + isl_basic_map *hull; + + hull = isl_map_convex_hull(map); + return isl_basic_map_remove_divs(hull); +} + +__isl_give isl_basic_set *isl_set_polyhedral_hull(__isl_take isl_set *set) +{ + return (isl_basic_set *)isl_map_polyhedral_hull((isl_map *)set); +} + struct sh_data_entry { struct isl_hash_table *table; struct isl_tab *tab; @@ -2285,7 +2324,7 @@ struct isl_basic_map *isl_map_simple_hull(struct isl_map *map) hull = isl_basic_map_overlying_set(bset, model); hull = isl_basic_map_intersect(hull, affine_hull); - hull = isl_basic_map_convex_hull(hull); + hull = isl_basic_map_remove_redundancies(hull); ISL_F_SET(hull, ISL_BASIC_MAP_NO_IMPLICIT); ISL_F_SET(hull, ISL_BASIC_MAP_ALL_EQUALITIES);