X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=62eb10822a65f293bbf5d60b342e7ded35fca18a;hb=0f3b90553d7323805e5b881c0b9e4e5579b011c6;hp=275037f5eb31d9fb64a13cd7f5d2789483f5f9fb;hpb=ab0e5110e98945ee69a65fba78bde953834f8fae;p=platform%2Fupstream%2Fisl.git diff --git a/isl_map.c b/isl_map.c index 275037f..62eb108 100644 --- a/isl_map.c +++ b/isl_map.c @@ -1,8 +1,20 @@ +/* + * Copyright 2008-2009 Katholieke Universiteit Leuven + * Copyright 2010 INRIA Saclay + * + * Use of this software is governed by the GNU LGPLv2.1 license + * + * Written by Sven Verdoolaege, K.U.Leuven, Departement + * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium + * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, + * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France + */ + #include #include #include "isl_ctx.h" #include "isl_blk.h" -#include "isl_dim.h" +#include "isl_dim_private.h" #include "isl_equalities.h" #include "isl_list.h" #include "isl_lp.h" @@ -43,6 +55,7 @@ static unsigned n(struct isl_dim *dim, enum isl_dim_type type) case isl_dim_in: return dim->n_in; case isl_dim_out: return dim->n_out; case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out; + default: return 0; } } @@ -52,11 +65,13 @@ static unsigned pos(struct isl_dim *dim, enum isl_dim_type type) case isl_dim_param: return 1; case isl_dim_in: return 1 + dim->nparam; case isl_dim_out: return 1 + dim->nparam + dim->n_in; + default: return 0; } } -static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim, - enum isl_dim_type type, unsigned dst_pos) +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; @@ -65,8 +80,14 @@ static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim, return; src_pos = pos(dim, type); - for (i = 0; i < n(dim, type); ++i) - dim_map->pos[1 + dst_pos + i] = src_pos + i; + 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, @@ -95,23 +116,26 @@ static void isl_dim_map_dump(struct isl_dim_map *dim_map) unsigned isl_basic_map_dim(const struct isl_basic_map *bmap, enum isl_dim_type type) { + if (!bmap) + return 0; switch (type) { case isl_dim_param: case isl_dim_in: case isl_dim_out: return isl_dim_size(bmap->dim, type); case isl_dim_div: return bmap->n_div; case isl_dim_all: return isl_basic_map_total_dim(bmap); + default: return 0; } } unsigned isl_map_dim(const struct isl_map *map, enum isl_dim_type type) { - return n(map->dim, type); + return map ? n(map->dim, type) : 0; } unsigned isl_set_dim(const struct isl_set *set, enum isl_dim_type type) { - return n(set->dim, type); + return set ? n(set->dim, type) : 0; } unsigned isl_basic_map_offset(struct isl_basic_map *bmap, @@ -123,6 +147,7 @@ unsigned isl_basic_map_offset(struct isl_basic_map *bmap, case isl_dim_in: return 1 + dim->nparam; case isl_dim_out: return 1 + dim->nparam + dim->n_in; case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out; + default: return 0; } } @@ -139,12 +164,12 @@ unsigned isl_basic_set_dim(const struct isl_basic_set *bset, unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset) { - return bset->dim->n_out; + return isl_basic_set_dim(bset, isl_dim_set); } unsigned isl_basic_set_n_param(const struct isl_basic_set *bset) { - return bset->dim->nparam; + return isl_basic_set_dim(bset, isl_dim_param); } unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset) @@ -154,12 +179,12 @@ unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset) unsigned isl_set_n_dim(const struct isl_set *set) { - return set->dim->n_out; + return isl_set_dim(set, isl_dim_set); } unsigned isl_set_n_param(const struct isl_set *set) { - return set->dim->nparam; + return isl_set_dim(set, isl_dim_param); } unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap) @@ -184,7 +209,7 @@ unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap) unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap) { - return isl_dim_total(bmap->dim) + bmap->n_div; + return bmap ? isl_dim_total(bmap->dim) + bmap->n_div : 0; } unsigned isl_map_n_in(const struct isl_map *map) @@ -250,6 +275,66 @@ struct isl_dim *isl_set_get_dim(struct isl_set *set) return isl_dim_copy(set->dim); } +__isl_give isl_basic_map *isl_basic_map_set_dim_name( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, const char *s) +{ + if (!bmap) + return NULL; + bmap->dim = isl_dim_set_name(bmap->dim, type, pos, s); + if (!bmap->dim) + goto error; + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, const char *s) +{ + int i; + + if (!map) + return NULL; + + map->dim = isl_dim_set_name(map->dim, type, pos, s); + if (!map->dim) + goto error; + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_set_dim_name(map->p[i], type, pos, s); + if (!map->p[i]) + goto error; + } + + return map; +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_basic_set *isl_basic_set_set_dim_name( + __isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned pos, const char *s) +{ + return (isl_basic_set *)isl_basic_map_set_dim_name( + (isl_basic_map *)bset, type, pos, s); +} + +__isl_give isl_set *isl_set_set_dim_name(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, const char *s) +{ + return (isl_set *)isl_map_set_dim_name((isl_map *)set, type, pos, s); +} + +int isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap) +{ + if (!bmap) + return -1; + return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL); +} + 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) @@ -257,39 +342,28 @@ static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx, int i; size_t row_size = 1 + isl_dim_total(bmap->dim) + extra; + bmap->ctx = ctx; + isl_ctx_ref(ctx); + bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size); - if (isl_blk_is_error(bmap->block)) { - free(bmap); - return NULL; - } + if (isl_blk_is_error(bmap->block)) + goto error; bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq); - if (!bmap->ineq) { - isl_blk_free(ctx, bmap->block); - free(bmap); - return NULL; - } + if (!bmap->ineq) + goto error; if (extra == 0) { bmap->block2 = isl_blk_empty(); bmap->div = NULL; } else { bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size)); - if (isl_blk_is_error(bmap->block2)) { - free(bmap->ineq); - isl_blk_free(ctx, bmap->block); - free(bmap); - return NULL; - } + if (isl_blk_is_error(bmap->block2)) + goto error; bmap->div = isl_alloc_array(ctx, isl_int *, extra); - if (!bmap->div) { - isl_blk_free(ctx, bmap->block2); - free(bmap->ineq); - isl_blk_free(ctx, bmap->block); - free(bmap); - return NULL; - } + if (!bmap->div) + goto error; } for (i = 0; i < n_ineq + n_eq; ++i) @@ -298,8 +372,6 @@ static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx, for (i = 0; i < extra; ++i) bmap->div[i] = bmap->block2.data + i * (1 + row_size); - bmap->ctx = ctx; - isl_ctx_ref(ctx); bmap->ref = 1; bmap->flags = 0; bmap->c_size = n_eq + n_ineq; @@ -343,7 +415,7 @@ struct isl_basic_map *isl_basic_map_alloc_dim(struct isl_dim *dim, if (!dim) return NULL; - bmap = isl_alloc_type(dim->ctx, struct isl_basic_map); + bmap = isl_calloc_type(dim->ctx, struct isl_basic_map); if (!bmap) goto error; bmap->dim = dim; @@ -446,7 +518,10 @@ struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap) bmap->ref++; return bmap; } - return isl_basic_map_dup(bmap); + bmap = isl_basic_map_dup(bmap); + if (bmap) + ISL_F_SET(bmap, ISL_BASIC_SET_FINAL); + return bmap; } struct isl_map *isl_map_copy(struct isl_map *map) @@ -640,42 +715,56 @@ int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos) return isl_basic_map_drop_inequality((struct isl_basic_map *)bset, pos); } -__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset, +__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap, isl_int *eq) { int k; - bset = isl_basic_set_extend_constraints(bset, 1, 0); - if (!bset) + bmap = isl_basic_map_extend_constraints(bmap, 1, 0); + if (!bmap) return NULL; - k = isl_basic_set_alloc_equality(bset); + k = isl_basic_map_alloc_equality(bmap); if (k < 0) goto error; - isl_seq_cpy(bset->eq[k], eq, 1 + isl_basic_set_total_dim(bset)); - return bset; + isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap)); + return bmap; error: - isl_basic_set_free(bset); + isl_basic_map_free(bmap); return NULL; } -__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset, +__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset, + isl_int *eq) +{ + return (isl_basic_set *) + isl_basic_map_add_eq((isl_basic_map *)bset, eq); +} + +__isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap, isl_int *ineq) { int k; - bset = isl_basic_set_extend_constraints(bset, 0, 1); - if (!bset) + bmap = isl_basic_map_extend_constraints(bmap, 0, 1); + if (!bmap) return NULL; - k = isl_basic_set_alloc_inequality(bset); + k = isl_basic_map_alloc_inequality(bmap); if (k < 0) goto error; - isl_seq_cpy(bset->ineq[k], ineq, 1 + isl_basic_set_total_dim(bset)); - return bset; + isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap)); + return bmap; error: - isl_basic_set_free(bset); + isl_basic_map_free(bmap); return NULL; } +__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset, + isl_int *ineq) +{ + return (isl_basic_set *) + isl_basic_map_add_ineq((isl_basic_map *)bset, ineq); +} + int isl_basic_map_alloc_div(struct isl_basic_map *bmap) { if (!bmap) @@ -953,10 +1042,13 @@ struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base, return NULL; dim = isl_dim_alloc(base->ctx, nparam, n_in, n_out); if (!dim) - return NULL; + goto error; bmap = isl_basic_map_extend_dim(base, dim, extra, n_eq, n_ineq); return bmap; +error: + isl_basic_map_free(base); + return NULL; } struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base, @@ -991,7 +1083,8 @@ struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap) bmap->ref--; bmap = isl_basic_map_dup(bmap); } - ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL); + if (bmap) + ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL); return bmap; } @@ -1066,8 +1159,7 @@ struct isl_basic_set *isl_basic_set_swap_vars( isl_blk_free(bset->ctx, blk); ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED); - return bset; - + return isl_basic_set_gauss(bset, NULL); error: isl_basic_set_free(bset); return NULL; @@ -1103,13 +1195,15 @@ struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap) if (bmap->n_eq > 0) isl_basic_map_free_equality(bmap, bmap->n_eq-1); else { - isl_basic_map_alloc_equality(bmap); + i = isl_basic_map_alloc_equality(bmap); if (i < 0) goto error; } isl_int_set_si(bmap->eq[i][0], 1); isl_seq_clr(bmap->eq[i]+1, total); ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY); + isl_vec_free(bmap->sample); + bmap->sample = NULL; return isl_basic_map_finalize(bmap); error: isl_basic_map_free(bmap); @@ -1142,38 +1236,56 @@ 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 + * constraints using Fourier-Motzkin. The dimensions themselves * are not removed. */ -struct isl_set *isl_set_eliminate_dims(struct isl_set *set, - unsigned first, unsigned n) +__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map, + enum isl_dim_type type, unsigned first, unsigned n) { int i; - unsigned nparam; - if (!set) + if (!map) return NULL; if (n == 0) - return set; + return map; - set = isl_set_cow(set); - if (!set) + map = isl_map_cow(map); + if (!map) return NULL; - isl_assert(set->ctx, first+n <= isl_set_n_dim(set), goto error); - nparam = isl_set_n_param(set); + isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error); + first += pos(map->dim, type) - 1; - for (i = 0; i < set->n; ++i) { - set->p[i] = isl_basic_set_eliminate_vars(set->p[i], - nparam + first, n); - if (!set->p[i]) + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_eliminate_vars(map->p[i], first, n); + if (!map->p[i]) goto error; } - return set; + return map; error: - isl_set_free(set); + isl_map_free(map); return NULL; } +/* Eliminate the specified n dimensions starting at first from the + * constraints using Fourier-Motzkin. The dimensions themselves + * are not removed. + */ +__isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return (isl_set *)isl_map_eliminate((isl_map *)set, type, first, n); +} + +/* Eliminate the specified n dimensions starting at first from the + * constraints using Fourier-Motzkin. The dimensions themselves + * are not removed. + */ +__isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set, + unsigned first, unsigned n) +{ + 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) @@ -1239,6 +1351,13 @@ error: return NULL; } +__isl_give isl_basic_set *isl_basic_set_remove(__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); +} + struct isl_map *isl_map_remove(struct isl_map *map, enum isl_dim_type type, unsigned first, unsigned n) { @@ -1265,6 +1384,12 @@ error: return NULL; } +__isl_give isl_set *isl_set_remove(__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); +} + /* 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) @@ -1530,7 +1655,7 @@ struct isl_set *isl_set_dup(struct isl_set *set) if (!dup) return NULL; for (i = 0; i < set->n; ++i) - dup = isl_set_add(dup, isl_basic_set_copy(set->p[i])); + dup = isl_set_add_basic_set(dup, isl_basic_set_copy(set->p[i])); return dup; } @@ -1546,7 +1671,7 @@ struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset) isl_basic_set_free(bset); return NULL; } - return isl_set_add(set, bset); + return isl_set_add_basic_set(set, bset); } struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap) @@ -1561,12 +1686,13 @@ struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap) isl_basic_map_free(bmap); return NULL; } - return isl_map_add(map, bmap); + return isl_map_add_basic_map(map, bmap); } -struct isl_set *isl_set_add(struct isl_set *set, struct isl_basic_set *bset) +__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set, + __isl_take isl_basic_set *bset) { - return (struct isl_set *)isl_map_add((struct isl_map *)set, + return (struct isl_set *)isl_map_add_basic_map((struct isl_map *)set, (struct isl_basic_map *)bset); } @@ -1645,10 +1771,10 @@ struct isl_basic_map *isl_basic_map_intersect_domain( isl_basic_map_compatible_domain(bmap, bset), goto error); bmap = isl_basic_map_cow(bmap); - bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim), - bset->n_div, bset->n_eq, bset->n_ineq); if (!bmap) goto error; + bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim), + bset->n_div, bset->n_eq, bset->n_ineq); dim = isl_dim_reverse(isl_dim_copy(bset->dim)); bmap_domain = isl_basic_map_from_basic_set(bset, dim); bmap = add_constraints(bmap, bmap_domain, 0, 0); @@ -1677,10 +1803,10 @@ struct isl_basic_map *isl_basic_map_intersect_range( isl_basic_map_compatible_range(bmap, bset), goto error); bmap = isl_basic_map_cow(bmap); - bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim), - bset->n_div, bset->n_eq, bset->n_ineq); if (!bmap) goto error; + bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim), + bset->n_div, bset->n_eq, bset->n_ineq); bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim)); bmap = add_constraints(bmap, bmap_range, 0, 0); @@ -1692,7 +1818,7 @@ error: return NULL; } -static int basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec) +int isl_basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec) { int i; unsigned total; @@ -1727,7 +1853,7 @@ static int basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec) int isl_basic_set_contains(struct isl_basic_set *bset, struct isl_vec *vec) { - return basic_map_contains((struct isl_basic_map *)bset, vec); + return isl_basic_map_contains((struct isl_basic_map *)bset, vec); } struct isl_basic_map *isl_basic_map_intersect( @@ -1752,22 +1878,24 @@ struct isl_basic_map *isl_basic_map_intersect( isl_dim_equal(bmap1->dim, bmap2->dim), goto error); if (bmap1->sample && - basic_map_contains(bmap1, bmap1->sample) > 0 && - basic_map_contains(bmap2, bmap1->sample) > 0) + isl_basic_map_contains(bmap1, bmap1->sample) > 0 && + isl_basic_map_contains(bmap2, bmap1->sample) > 0) sample = isl_vec_copy(bmap1->sample); else if (bmap2->sample && - basic_map_contains(bmap1, bmap2->sample) > 0 && - basic_map_contains(bmap2, bmap2->sample) > 0) + isl_basic_map_contains(bmap1, bmap2->sample) > 0 && + isl_basic_map_contains(bmap2, bmap2->sample) > 0) sample = isl_vec_copy(bmap2->sample); bmap1 = isl_basic_map_cow(bmap1); - bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim), - bmap2->n_div, bmap2->n_eq, bmap2->n_ineq); if (!bmap1) goto error; + bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim), + bmap2->n_div, bmap2->n_eq, bmap2->n_ineq); bmap1 = add_constraints(bmap1, bmap2, 0, 0); - if (sample) { + if (!bmap1) + isl_vec_free(sample); + else if (sample) { isl_vec_free(bmap1->sample); bmap1->sample = sample; } @@ -1791,6 +1919,61 @@ struct isl_basic_set *isl_basic_set_intersect( (struct isl_basic_map *)bset2); } +/* Special case of isl_map_intersect, where both map1 and map2 + * are convex, without any divs and such that either map1 or map2 + * contains a single constraint. This constraint is then simply + * added to the other map. + */ +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); + isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error); + + if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1) + return isl_map_intersect(map2, map1); + + isl_assert(map2->ctx, + map2->p[0]->n_eq + map2->p[0]->n_ineq == 1, goto error); + + map1 = isl_map_cow(map1); + if (!map1) + goto error; + if (isl_map_fast_is_empty(map1)) { + isl_map_free(map2); + return map1; + } + map1->p[0] = isl_basic_map_cow(map1->p[0]); + if (map2->p[0]->n_eq == 1) + map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]); + else + map1->p[0] = isl_basic_map_add_ineq(map1->p[0], + map2->p[0]->ineq[0]); + + map1->p[0] = isl_basic_map_simplify(map1->p[0]); + map1->p[0] = isl_basic_map_finalize(map1->p[0]); + if (!map1->p[0]) + goto error; + + if (isl_basic_map_fast_is_empty(map1->p[0])) { + isl_basic_map_free(map1->p[0]); + map1->n = 0; + } + + isl_map_free(map2); + + return map1; +error: + isl_map_free(map1); + isl_map_free(map2); + return NULL; +} + struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2) { unsigned flags = 0; @@ -1800,6 +1983,21 @@ 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)) { + isl_map_free(map2); + return map1; + } + if (isl_map_fast_is_empty(map2)) { + isl_map_free(map1); + return map2; + } + + if (map1->n == 1 && map2->n == 1 && + map1->p[0]->n_div == 0 && map2->p[0]->n_div == 0 && + isl_dim_equal(map1->dim, map2->dim) && + (map1->p[0]->n_eq + map1->p[0]->n_ineq == 1 || + map2->p[0]->n_eq + map2->p[0]->n_ineq == 1)) + return map_intersect_add_constraint(map1, map2); isl_assert(map1->ctx, isl_dim_match(map1->dim, isl_dim_param, map2->dim, isl_dim_param), goto error); if (isl_dim_total(map1->dim) == @@ -1828,7 +2026,7 @@ struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2) if (isl_basic_map_is_empty(part)) isl_basic_map_free(part); else - result = isl_map_add(result, part); + result = isl_map_add_basic_map(result, part); if (!result) goto error; } @@ -1866,92 +2064,430 @@ struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap) return isl_basic_map_from_basic_set(bset, dim); } -/* Turn final n dimensions into existentially quantified variables. - */ -struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset, - enum isl_dim_type type, unsigned first, unsigned n) +__isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, unsigned n) { - int i; - size_t row_size; - isl_int **new_div; - isl_int *old; + struct isl_dim *res_dim; + struct isl_basic_map *res; + struct isl_dim_map *dim_map; + unsigned total, off; + enum isl_dim_type t; - if (!bset) + if (n == 0) + return bmap; + + if (!bmap) return NULL; - isl_assert(bset->ctx, type == isl_dim_set, goto error); - isl_assert(bset->ctx, first + n == isl_basic_set_n_dim(bset), goto error); + res_dim = isl_dim_insert(isl_basic_map_get_dim(bmap), type, pos, n); - if (n == 0) - return bset; + total = isl_basic_map_total_dim(bmap) + n; + dim_map = isl_dim_map_alloc(bmap->ctx, total); + off = 0; + for (t = isl_dim_param; t <= isl_dim_out; ++t) { + if (t != type) { + isl_dim_map_dim(dim_map, bmap->dim, t, off); + } else { + unsigned size = isl_basic_map_dim(bmap, t); + isl_dim_map_dim_range(dim_map, bmap->dim, t, + 0, pos, off); + isl_dim_map_dim_range(dim_map, bmap->dim, t, + pos, size - pos, off + pos + n); + } + off += isl_dim_size(res_dim, t); + } + isl_dim_map_div(dim_map, bmap, off); - bset = isl_basic_set_cow(bset); + 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); + res = isl_basic_map_simplify(res); + return isl_basic_map_finalize(res); +} - row_size = 1 + isl_dim_total(bset->dim) + bset->extra; - old = bset->block2.data; - bset->block2 = isl_blk_extend(bset->ctx, bset->block2, - (bset->extra + n) * (1 + row_size)); - if (!bset->block2.data) - goto error; - new_div = isl_alloc_array(ctx, isl_int *, bset->extra + n); - if (!new_div) - goto error; - for (i = 0; i < n; ++i) { - new_div[i] = bset->block2.data + - (bset->extra + i) * (1 + row_size); - isl_seq_clr(new_div[i], 1 + row_size); - } - for (i = 0; i < bset->extra; ++i) - new_div[n + i] = bset->block2.data + (bset->div[i] - old); - free(bset->div); - bset->div = new_div; - bset->n_div += n; - bset->extra += n; - bset->dim = isl_dim_drop_outputs(bset->dim, - isl_basic_set_n_dim(bset) - n, n); - if (!bset->dim) - goto error; - bset = isl_basic_set_simplify(bset); - bset = isl_basic_set_drop_redundant_divs(bset); - return isl_basic_set_finalize(bset); +__isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned n) +{ + if (!bmap) + return NULL; + return isl_basic_map_insert(bmap, type, + isl_basic_map_dim(bmap, type), n); +} + +__isl_give isl_basic_set *isl_basic_set_add(__isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned n) +{ + if (!bset) + return NULL; + isl_assert(bset->ctx, type != isl_dim_in, goto error); + return (isl_basic_set *)isl_basic_map_add((isl_basic_map *)bset, type, n); error: isl_basic_set_free(bset); return NULL; } -/* Turn final n dimensions into existentially quantified variables. - */ -__isl_give isl_set *isl_set_project_out(__isl_take isl_set *set, - enum isl_dim_type type, unsigned first, unsigned n) +__isl_give isl_map *isl_map_insert(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, unsigned n) { int i; - if (!set) + if (n == 0) + return map; + + map = isl_map_cow(map); + if (!map) return NULL; - isl_assert(set->ctx, type == isl_dim_set, goto error); - isl_assert(set->ctx, first + n == isl_set_n_dim(set), goto error); + map->dim = isl_dim_insert(map->dim, type, pos, n); + if (!map->dim) + goto error; + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_insert(map->p[i], type, pos, n); + if (!map->p[i]) + goto error; + } + + return map; +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_map *isl_map_add(__isl_take isl_map *map, + enum isl_dim_type type, unsigned n) +{ + if (!map) + return NULL; + return isl_map_insert(map, type, isl_map_dim(map, type), n); +} + +__isl_give isl_set *isl_set_add(__isl_take isl_set *set, + enum isl_dim_type type, unsigned n) +{ + if (!set) + return NULL; + isl_assert(set->ctx, type != isl_dim_in, goto error); + return (isl_set *)isl_map_add((isl_map *)set, type, n); +error: + isl_set_free(set); + return NULL; +} + +__isl_give isl_basic_map *isl_basic_map_move_dims( + __isl_take isl_basic_map *bmap, + 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; + unsigned total, off; + + if (!bmap) + return NULL; if (n == 0) - return set; + return bmap; - set = isl_set_cow(set); + isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type), + goto error); + + if (dst_type == src_type && dst_pos == src_pos) + return bmap; + + isl_assert(bmap->ctx, dst_type != src_type, goto error); + + if (pos(bmap->dim, dst_type) + dst_pos == + pos(bmap->dim, src_type) + src_pos + + ((src_type < dst_type) ? n : 0)) { + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; + + bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos, + src_type, src_pos, n); + if (!bmap->dim) + goto error; + + bmap = isl_basic_map_finalize(bmap); + + return bmap; + } + + total = isl_basic_map_total_dim(bmap); + dim_map = isl_dim_map_alloc(bmap->ctx, total); + + off = 0; + for (t = isl_dim_param; t <= isl_dim_out; ++t) { + unsigned size = isl_dim_size(bmap->dim, t); + if (t == dst_type) { + isl_dim_map_dim_range(dim_map, bmap->dim, t, + 0, dst_pos, off); + off += dst_pos; + isl_dim_map_dim_range(dim_map, bmap->dim, src_type, + src_pos, n, off); + off += n; + isl_dim_map_dim_range(dim_map, bmap->dim, t, + dst_pos, size - dst_pos, off); + off += size - dst_pos; + } else if (t == src_type) { + isl_dim_map_dim_range(dim_map, bmap->dim, t, + 0, src_pos, off); + off += src_pos; + isl_dim_map_dim_range(dim_map, bmap->dim, t, + src_pos + n, size - src_pos - n, off); + off += size - src_pos - n; + } else { + isl_dim_map_dim(dim_map, bmap->dim, t, off); + off += size; + } + } + isl_dim_map_div(dim_map, bmap, off + n); + + 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->dim = isl_dim_move(bmap->dim, dst_type, dst_pos, + src_type, src_pos, n); + if (!bmap->dim) + goto error; + + ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED); + bmap = isl_basic_map_gauss(bmap, NULL); + bmap = isl_basic_map_finalize(bmap); + + return bmap; +error: + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset, + enum isl_dim_type dst_type, unsigned dst_pos, + enum isl_dim_type src_type, unsigned src_pos, unsigned n) +{ + return (isl_basic_set *)isl_basic_map_move_dims( + (isl_basic_map *)bset, dst_type, dst_pos, src_type, src_pos, n); +} + +__isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set, + enum isl_dim_type dst_type, unsigned dst_pos, + enum isl_dim_type src_type, unsigned src_pos, unsigned n) +{ if (!set) + return NULL; + isl_assert(set->ctx, dst_type != isl_dim_in, goto error); + return (isl_set *)isl_map_move_dims((isl_map *)set, dst_type, dst_pos, + src_type, src_pos, n); +error: + isl_set_free(set); + return NULL; +} + +__isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map, + enum isl_dim_type dst_type, unsigned dst_pos, + enum isl_dim_type src_type, unsigned src_pos, unsigned n) +{ + int i; + + if (!map) + return NULL; + if (n == 0) + return map; + + isl_assert(map->ctx, src_pos + n <= isl_map_dim(map, src_type), + goto error); + + if (dst_type == src_type && dst_pos == src_pos) + return map; + + isl_assert(map->ctx, dst_type != src_type, goto error); + + map = isl_map_cow(map); + if (!map) + return NULL; + + map->dim = isl_dim_move(map->dim, dst_type, dst_pos, src_type, src_pos, n); + if (!map->dim) goto error; - set->dim = isl_dim_drop_outputs(set->dim, first, n); - for (i = 0; i < set->n; ++i) { - set->p[i] = isl_basic_set_project_out(set->p[i], type, first, n); - if (!set->p[i]) + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_move_dims(map->p[i], + dst_type, dst_pos, + src_type, src_pos, n); + if (!map->p[i]) goto error; } - ISL_F_CLR(set, ISL_SET_NORMALIZED); - return set; + return map; error: - isl_set_free(set); + isl_map_free(map); return NULL; } +/* Move the specified dimensions to the last columns right before + * the divs. Don't change the dimension specification of bmap. + * That's the responsibility of the caller. + */ +static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + struct isl_dim_map *dim_map; + struct isl_basic_map *res; + enum isl_dim_type t; + unsigned total, off; + + if (!bmap) + return NULL; + if (pos(bmap->dim, type) + first + n == 1 + isl_dim_total(bmap->dim)) + return bmap; + + total = isl_basic_map_total_dim(bmap); + dim_map = isl_dim_map_alloc(bmap->ctx, total); + + off = 0; + for (t = isl_dim_param; t <= isl_dim_out; ++t) { + unsigned size = isl_dim_size(bmap->dim, t); + if (t == type) { + isl_dim_map_dim_range(dim_map, bmap->dim, t, + 0, first, off); + off += first; + isl_dim_map_dim_range(dim_map, bmap->dim, t, + first, n, total - bmap->n_div - n); + isl_dim_map_dim_range(dim_map, bmap->dim, t, + first + n, size - (first + n), off); + off += size - (first + n); + } else { + isl_dim_map_dim(dim_map, bmap->dim, t, off); + off += size; + } + } + isl_dim_map_div(dim_map, bmap, off + n); + + 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); + return res; +} + +/* Turn the n dimensions of type type, starting at first + * into existentially quantified variables. + */ +__isl_give isl_basic_map *isl_basic_map_project_out( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned first, unsigned n) +{ + int i; + size_t row_size; + isl_int **new_div; + isl_int *old; + + if (n == 0) + return bmap; + + if (!bmap) + return NULL; + + if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) + return isl_basic_map_remove(bmap, type, first, n); + + isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type), + goto error); + + bmap = move_last(bmap, type, first, n); + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; + + row_size = 1 + isl_dim_total(bmap->dim) + bmap->extra; + old = bmap->block2.data; + bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2, + (bmap->extra + n) * (1 + row_size)); + if (!bmap->block2.data) + goto error; + new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n); + if (!new_div) + goto error; + for (i = 0; i < n; ++i) { + new_div[i] = bmap->block2.data + + (bmap->extra + i) * (1 + row_size); + isl_seq_clr(new_div[i], 1 + row_size); + } + for (i = 0; i < bmap->extra; ++i) + new_div[n + i] = bmap->block2.data + (bmap->div[i] - old); + free(bmap->div); + bmap->div = new_div; + bmap->n_div += n; + bmap->extra += n; + + bmap->dim = isl_dim_drop(bmap->dim, type, first, n); + if (!bmap->dim) + goto error; + bmap = isl_basic_map_simplify(bmap); + bmap = isl_basic_map_drop_redundant_divs(bmap); + return isl_basic_map_finalize(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + +/* Turn the n dimensions of type type, starting at first + * into existentially quantified variables. + */ +struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return (isl_basic_set *)isl_basic_map_project_out( + (isl_basic_map *)bset, type, first, n); +} + +/* Turn the n dimensions of type type, starting at first + * into existentially quantified variables. + */ +__isl_give isl_map *isl_map_project_out(__isl_take isl_map *map, + enum isl_dim_type type, unsigned first, unsigned n) +{ + int i; + + if (!map) + return NULL; + + if (n == 0) + return map; + + isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error); + + map = isl_map_cow(map); + if (!map) + return NULL; + + map->dim = isl_dim_drop(map->dim, type, first, n); + if (!map->dim) + goto error; + + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n); + if (!map->p[i]) + goto error; + } + + return map; +error: + isl_map_free(map); + return NULL; +} + +/* Turn the n dimensions of type type, starting at first + * into existentially quantified variables. + */ +__isl_give isl_set *isl_set_project_out(__isl_take isl_set *set, + enum isl_dim_type type, unsigned first, unsigned n) +{ + return (isl_set *)isl_map_project_out((isl_map *)set, type, first, n); +} + static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n) { int i, j; @@ -2138,7 +2674,7 @@ struct isl_map *isl_map_sum(struct isl_map *map1, struct isl_map *map2) if (isl_basic_map_is_empty(part)) isl_basic_map_free(part); else - result = isl_map_add(result, part); + result = isl_map_add_basic_map(result, part); if (!result) goto error; } @@ -2151,6 +2687,12 @@ error: return NULL; } +__isl_give isl_set *isl_set_sum(__isl_take isl_set *set1, + __isl_take isl_set *set2) +{ + return (isl_set *)isl_map_sum((isl_map *)set1, (isl_map *)set2); +} + /* Given a basic map A -> f(A), construct A -> -f(A). */ struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap) @@ -2198,6 +2740,11 @@ error: return NULL; } +__isl_give isl_set *isl_set_neg(__isl_take isl_set *set) +{ + return (isl_set *)isl_map_neg((isl_map *)set); +} + /* Given a basic map A -> f(A) and an integer d, construct a basic map * A -> floor(f(A)/d). */ @@ -2320,6 +2867,29 @@ error: return NULL; } +/* Add a constraint to "bmap" expressing i_pos <= o_pos + */ +static __isl_give isl_basic_map *var_less_or_equal( + __isl_take isl_basic_map *bmap, unsigned pos) +{ + int i; + unsigned nparam; + unsigned n_in; + + i = isl_basic_map_alloc_inequality(bmap); + if (i < 0) + goto error; + nparam = isl_basic_map_n_param(bmap); + n_in = isl_basic_map_n_in(bmap); + isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap)); + isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1); + isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1); + return isl_basic_map_finalize(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + /* Add a constraints to "bmap" expressing i_pos > o_pos */ static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos) @@ -2343,6 +2913,29 @@ error: return NULL; } +/* Add a constraint to "bmap" expressing i_pos >= o_pos + */ +static __isl_give isl_basic_map *var_more_or_equal( + __isl_take isl_basic_map *bmap, unsigned pos) +{ + int i; + unsigned nparam; + unsigned n_in; + + i = isl_basic_map_alloc_inequality(bmap); + if (i < 0) + goto error; + nparam = isl_basic_map_n_param(bmap); + n_in = isl_basic_map_n_in(bmap); + isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap)); + isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1); + isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1); + return isl_basic_map_finalize(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal) { int i; @@ -2355,7 +2948,7 @@ struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal) return isl_basic_map_finalize(bmap); } -/* Return a relation on pairs of sets of dimension "dim" expressing i_pos < o_pos +/* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos] */ struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos) { @@ -2371,6 +2964,21 @@ struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos) return isl_basic_map_finalize(bmap); } +/* Return a relation on of dimension "dim" expressing i_[0..pos] <<= o_[0..pos] + */ +__isl_give isl_basic_map *isl_basic_map_less_or_equal_at( + __isl_take isl_dim *dim, unsigned pos) +{ + int i; + isl_basic_map *bmap; + + bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1); + for (i = 0; i < pos; ++i) + bmap = var_equal(bmap, i); + bmap = var_less_or_equal(bmap, pos); + return isl_basic_map_finalize(bmap); +} + /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos */ struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos) @@ -2387,28 +2995,62 @@ struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos) return isl_basic_map_finalize(bmap); } -static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal) +/* Return a relation on of dimension "dim" expressing i_[0..pos] >>= o_[0..pos] + */ +__isl_give isl_basic_map *isl_basic_map_more_or_equal_at( + __isl_take isl_dim *dim, unsigned pos) +{ + int i; + isl_basic_map *bmap; + + bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1); + for (i = 0; i < pos; ++i) + bmap = var_equal(bmap, i); + bmap = var_more_or_equal(bmap, pos); + return isl_basic_map_finalize(bmap); +} + +static __isl_give isl_map *map_lex_lte_first(__isl_take isl_dim *dims, + unsigned n, int equal) { struct isl_map *map; - unsigned dim; int i; - if (!dims) - return NULL; - dim = dims->n_out; - map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT); + map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT); - for (i = 0; i < dim; ++i) - map = isl_map_add(map, + for (i = 0; i + 1 < n; ++i) + map = isl_map_add_basic_map(map, isl_basic_map_less_at(isl_dim_copy(dims), i)); - if (equal) - map = isl_map_add(map, - isl_basic_map_equal(isl_dim_copy(dims), dim)); + if (n > 0) { + if (equal) + map = isl_map_add_basic_map(map, + isl_basic_map_less_or_equal_at(dims, n - 1)); + else + map = isl_map_add_basic_map(map, + isl_basic_map_less_at(dims, n - 1)); + } else + isl_dim_free(dims); - isl_dim_free(dims); return map; } +static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal) +{ + if (!dims) + return NULL; + return map_lex_lte_first(dims, dims->n_out, equal); +} + +__isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_dim *dim, unsigned n) +{ + return map_lex_lte_first(dim, n, 0); +} + +__isl_give isl_map *isl_map_lex_le_first(__isl_take isl_dim *dim, unsigned n) +{ + return map_lex_lte_first(dim, n, 1); +} + __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim) { return map_lex_lte(isl_dim_map(set_dim), 0); @@ -2419,28 +3061,47 @@ __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim) return map_lex_lte(isl_dim_map(set_dim), 1); } -static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal) +static __isl_give isl_map *map_lex_gte_first(__isl_take isl_dim *dims, + unsigned n, int equal) { struct isl_map *map; - unsigned dim; int i; - if (!dims) - return NULL; - dim = dims->n_out; - map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT); + map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT); - for (i = 0; i < dim; ++i) - map = isl_map_add(map, + for (i = 0; i + 1 < n; ++i) + map = isl_map_add_basic_map(map, isl_basic_map_more_at(isl_dim_copy(dims), i)); - if (equal) - map = isl_map_add(map, - isl_basic_map_equal(isl_dim_copy(dims), dim)); + if (n > 0) { + if (equal) + map = isl_map_add_basic_map(map, + isl_basic_map_more_or_equal_at(dims, n - 1)); + else + map = isl_map_add_basic_map(map, + isl_basic_map_more_at(dims, n - 1)); + } else + isl_dim_free(dims); - isl_dim_free(dims); return map; } +static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal) +{ + if (!dims) + return NULL; + return map_lex_gte_first(dims, dims->n_out, equal); +} + +__isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_dim *dim, unsigned n) +{ + return map_lex_gte_first(dim, n, 0); +} + +__isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_dim *dim, unsigned n) +{ + return map_lex_gte_first(dim, n, 1); +} + __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim) { return map_lex_gte(isl_dim_map(set_dim), 0); @@ -2501,27 +3162,43 @@ error: * * f - m d >= n */ -static int add_div_constraints(struct isl_basic_map *bmap, unsigned div) +int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap, + unsigned pos, isl_int *div) { int i, j; unsigned total = isl_basic_map_total_dim(bmap); - unsigned div_pos = 1 + total - bmap->n_div + div; i = isl_basic_map_alloc_inequality(bmap); if (i < 0) return -1; - isl_seq_cpy(bmap->ineq[i], bmap->div[div]+1, 1+total); - isl_int_neg(bmap->ineq[i][div_pos], bmap->div[div][0]); + isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total); + isl_int_neg(bmap->ineq[i][1 + pos], div[0]); j = isl_basic_map_alloc_inequality(bmap); if (j < 0) return -1; isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total); - isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]); + isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][1 + pos]); isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1); return j; } +int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset, + unsigned pos, isl_int *div) +{ + return isl_basic_map_add_div_constraints_var((isl_basic_map *)bset, + pos, div); +} + +int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div) +{ + unsigned total = isl_basic_map_total_dim(bmap); + unsigned div_pos = total - bmap->n_div + div; + + return isl_basic_map_add_div_constraints_var(bmap, div_pos, + bmap->div[div]); +} + struct isl_basic_set *isl_basic_map_underlying_set( struct isl_basic_map *bmap) { @@ -2603,7 +3280,7 @@ struct isl_basic_map *isl_basic_map_overlying_set( for (i = 0; i < like->n_div; ++i) { if (isl_int_is_zero(bmap->div[i][0])) continue; - if (add_div_constraints(bmap, i) < 0) + if (isl_basic_map_add_div_constraints(bmap, i) < 0) goto error; } } @@ -2722,16 +3399,17 @@ struct isl_set *isl_map_range(struct isl_map *map) if (!map) goto error; + if (isl_map_dim(map, isl_dim_in) == 0) + return (isl_set *)map; + map = isl_map_cow(map); if (!map) goto error; set = (struct isl_set *) map; - if (set->dim->n_in != 0) { - set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in); - if (!set->dim) - goto error; - } + set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in); + if (!set->dim) + goto error; for (i = 0; i < map->n; ++i) { set->p[i] = isl_basic_map_range(map->p[i]); if (!set->p[i]) @@ -2775,6 +3453,18 @@ struct isl_map *isl_map_from_range(struct isl_set *set) return (struct isl_map *)set; } +__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_map *isl_map_from_domain_and_range(__isl_take isl_set *domain, + __isl_take isl_set *range) +{ + return isl_map_product(isl_map_from_domain(domain), + isl_map_from_range(range)); +} + struct isl_set *isl_set_from_map(struct isl_map *map) { int i; @@ -2963,7 +3653,7 @@ struct isl_map *isl_map_universe(struct isl_dim *dim) if (!dim) return NULL; map = isl_map_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT); - map = isl_map_add(map, isl_basic_map_universe(dim)); + map = isl_map_add_basic_map(map, isl_basic_map_universe(dim)); return map; } @@ -2973,7 +3663,7 @@ struct isl_set *isl_set_universe(struct isl_dim *dim) if (!dim) return NULL; set = isl_set_alloc_dim(isl_dim_copy(dim), 1, ISL_MAP_DISJOINT); - set = isl_set_add(set, isl_basic_set_universe(dim)); + set = isl_set_add_basic_set(set, isl_basic_set_universe(dim)); return set; } @@ -2993,11 +3683,12 @@ struct isl_map *isl_map_dup(struct isl_map *map) return NULL; dup = isl_map_alloc_dim(isl_dim_copy(map->dim), map->n, map->flags); for (i = 0; i < map->n; ++i) - dup = isl_map_add(dup, isl_basic_map_copy(map->p[i])); + dup = isl_map_add_basic_map(dup, isl_basic_map_copy(map->p[i])); return dup; } -struct isl_map *isl_map_add(struct isl_map *map, struct isl_basic_map *bmap) +__isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map, + __isl_take isl_basic_map *bmap) { if (!bmap || !map) goto error; @@ -3067,8 +3758,8 @@ struct isl_set *isl_set_extend(struct isl_set *base, nparam, 0, dim); } -static struct isl_basic_map *isl_basic_map_fix_pos(struct isl_basic_map *bmap, - unsigned pos, int value) +static struct isl_basic_map *isl_basic_map_fix_pos_si( + struct isl_basic_map *bmap, unsigned pos, int value) { int j; @@ -3087,14 +3778,47 @@ error: return NULL; } +static __isl_give isl_basic_map *isl_basic_map_fix_pos( + __isl_take isl_basic_map *bmap, unsigned pos, isl_int value) +{ + int j; + + bmap = isl_basic_map_cow(bmap); + bmap = isl_basic_map_extend_constraints(bmap, 1, 0); + j = isl_basic_map_alloc_equality(bmap); + if (j < 0) + goto error; + isl_seq_clr(bmap->eq[j] + 1, isl_basic_map_total_dim(bmap)); + isl_int_set_si(bmap->eq[j][pos], -1); + isl_int_set(bmap->eq[j][0], value); + bmap = isl_basic_map_simplify(bmap); + return isl_basic_map_finalize(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + struct isl_basic_map *isl_basic_map_fix_si(struct isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, int value) { if (!bmap) return NULL; isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error); - return isl_basic_map_fix_pos(bmap, isl_basic_map_offset(bmap, type) + pos, - value); + return isl_basic_map_fix_pos_si(bmap, + isl_basic_map_offset(bmap, type) + pos, value); +error: + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + if (!bmap) + return NULL; + isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error); + return isl_basic_map_fix_pos(bmap, + isl_basic_map_offset(bmap, type) + pos, value); error: isl_basic_map_free(bmap); return NULL; @@ -3108,6 +3832,14 @@ struct isl_basic_set *isl_basic_set_fix_si(struct isl_basic_set *bset, type, pos, value); } +__isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return (struct isl_basic_set *) + isl_basic_map_fix((struct isl_basic_map *)bset, + type, pos, value); +} + struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap, unsigned input, int value) { @@ -3144,6 +3876,41 @@ error: return NULL; } +__isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, int value) +{ + return (struct isl_set *) + isl_map_fix_si((struct isl_map *)set, type, pos, value); +} + +__isl_give isl_map *isl_map_fix(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + int i; + + map = isl_map_cow(map); + if (!map) + return NULL; + + isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error); + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_fix(map->p[i], type, pos, value); + if (!map->p[i]) + goto error; + } + ISL_F_CLR(map, ISL_MAP_NORMALIZED); + return map; +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_set *isl_set_fix(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, isl_int value) +{ + return (struct isl_set *)isl_map_fix((isl_map *)set, type, pos, value); +} + struct isl_map *isl_map_fix_input_si(struct isl_map *map, unsigned input, int value) { @@ -3156,6 +3923,31 @@ struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value) isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value); } +__isl_give isl_basic_map *isl_basic_map_lower_bound_si( + __isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, int value) +{ + int j; + + if (!bmap) + return NULL; + isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error); + pos += isl_basic_map_offset(bmap, type); + bmap = isl_basic_map_cow(bmap); + bmap = isl_basic_map_extend_constraints(bmap, 0, 1); + j = isl_basic_map_alloc_inequality(bmap); + if (j < 0) + goto error; + isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap)); + isl_int_set_si(bmap->ineq[j][pos], 1); + isl_int_set_si(bmap->ineq[j][0], -value); + bmap = isl_basic_map_simplify(bmap); + return isl_basic_map_finalize(bmap); +error: + isl_basic_map_free(bmap); + return NULL; +} + struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset, unsigned dim, isl_int value) { @@ -3176,6 +3968,36 @@ error: return NULL; } +__isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map, + enum isl_dim_type type, unsigned pos, int value) +{ + int i; + + map = isl_map_cow(map); + if (!map) + return NULL; + + isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error); + for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_lower_bound_si(map->p[i], + type, pos, value); + if (!map->p[i]) + goto error; + } + ISL_F_CLR(map, ISL_MAP_NORMALIZED); + return map; +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, int value) +{ + return (struct isl_set *) + isl_map_lower_bound_si((struct isl_map *)set, type, pos, value); +} + struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim, isl_int value) { @@ -3220,77 +4042,301 @@ error: return NULL; } -static struct isl_map *isl_basic_map_partial_lexopt( - struct isl_basic_map *bmap, struct isl_basic_set *dom, - struct isl_set **empty, int max) +static struct isl_map *isl_basic_map_partial_lexopt( + struct isl_basic_map *bmap, struct isl_basic_set *dom, + struct isl_set **empty, int max) +{ + if (!bmap) + goto error; + if (bmap->ctx->opt->pip == ISL_PIP_PIP) + return isl_pip_basic_map_lexopt(bmap, dom, empty, max); + else + return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max); +error: + isl_basic_map_free(bmap); + isl_basic_set_free(dom); + if (empty) + *empty = NULL; + return NULL; +} + +struct isl_map *isl_basic_map_partial_lexmax( + struct isl_basic_map *bmap, struct isl_basic_set *dom, + struct isl_set **empty) +{ + return isl_basic_map_partial_lexopt(bmap, dom, empty, 1); +} + +struct isl_map *isl_basic_map_partial_lexmin( + struct isl_basic_map *bmap, struct isl_basic_set *dom, + struct isl_set **empty) +{ + return isl_basic_map_partial_lexopt(bmap, dom, empty, 0); +} + +struct isl_set *isl_basic_set_partial_lexmin( + struct isl_basic_set *bset, struct isl_basic_set *dom, + struct isl_set **empty) +{ + return (struct isl_set *) + isl_basic_map_partial_lexmin((struct isl_basic_map *)bset, + dom, empty); +} + +struct isl_set *isl_basic_set_partial_lexmax( + struct isl_basic_set *bset, struct isl_basic_set *dom, + struct isl_set **empty) +{ + return (struct isl_set *) + isl_basic_map_partial_lexmax((struct isl_basic_map *)bset, + dom, empty); +} + +/* Given a basic map "bmap", compute the lexicograhically minimal + * (or maximal) image element for each domain element in dom. + * Set *empty to those elements in dom that do not have an image element. + * + * We first make sure the basic sets in dom are disjoint and then + * simply collect the results over each of the basic sets separately. + * We could probably improve the efficiency a bit by moving the union + * domain down into the parametric integer programming. + */ +static __isl_give isl_map *basic_map_partial_lexopt( + __isl_take isl_basic_map *bmap, __isl_take isl_set *dom, + __isl_give isl_set **empty, int max) +{ + int i; + struct isl_map *res; + + dom = isl_set_make_disjoint(dom); + if (!dom) + goto error; + + if (isl_set_fast_is_empty(dom)) { + res = isl_map_empty_like_basic_map(bmap); + *empty = isl_set_empty_like(dom); + isl_set_free(dom); + isl_basic_map_free(bmap); + return res; + } + + res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap), + isl_basic_set_copy(dom->p[0]), empty, max); + + for (i = 1; i < dom->n; ++i) { + struct isl_map *res_i; + struct isl_set *empty_i; + + res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap), + isl_basic_set_copy(dom->p[i]), &empty_i, max); + + res = isl_map_union_disjoint(res, res_i); + *empty = isl_set_union_disjoint(*empty, empty_i); + } + + isl_set_free(dom); + isl_basic_map_free(bmap); + return res; +error: + *empty = NULL; + isl_set_free(dom); + isl_basic_map_free(bmap); + return NULL; +} + +/* Given a map "map", compute the lexicograhically minimal + * (or maximal) image element for each domain element in dom. + * Set *empty to those elements in dom that do not have an image element. + * + * We first compute the lexicographically minimal or maximal element + * in the first basic map. This results in a partial solution "res" + * and a subset "todo" of dom that still need to be handled. + * We then consider each of the remaining maps in "map" and successively + * improve both "res" and "todo". + * + * Let res^k and todo^k be the results after k steps and let i = k + 1. + * Assume we are computing the lexicographical maximum. + * We first intersect basic map i with a relation that maps elements + * to elements that are lexicographically larger than the image elements + * in res^k and the compute the maximum image element of this intersection. + * The result ("better") corresponds to those image elements in basic map i + * that are better than what we had before. The remainder ("keep") are the + * domain elements for which the image element in res_k was better. + * We also compute the lexicographical maximum of basic map i in todo^k. + * res^i is the result of the operation + better + those elements in + * res^k that we should keep + * todo^i is the remainder of the maximum operation on todo^k. + */ +static __isl_give isl_map *isl_map_partial_lexopt( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty, int max) { - if (!bmap) + int i; + struct isl_map *res; + struct isl_set *todo; + + if (!map || !dom) goto error; - if (bmap->ctx->pip == ISL_PIP_PIP) - return isl_pip_basic_map_lexopt(bmap, dom, empty, max); + + if (isl_map_fast_is_empty(map)) { + if (empty) + *empty = dom; + else + isl_set_free(dom); + return map; + } + + res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]), + isl_set_copy(dom), &todo, max); + + for (i = 1; i < map->n; ++i) { + struct isl_map *lt; + struct isl_map *better; + struct isl_set *keep; + struct isl_map *res_i; + struct isl_set *todo_i; + struct isl_dim *dim = isl_map_get_dim(res); + + dim = isl_dim_range(dim); + if (max) + lt = isl_map_lex_lt(dim); + else + lt = isl_map_lex_gt(dim); + lt = isl_map_apply_range(isl_map_copy(res), lt); + lt = isl_map_intersect(lt, + isl_map_from_basic_map(isl_basic_map_copy(map->p[i]))); + better = isl_map_partial_lexopt(lt, + isl_map_domain(isl_map_copy(res)), + &keep, max); + + res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]), + todo, &todo_i, max); + + res = isl_map_intersect_domain(res, keep); + res = isl_map_union_disjoint(res, res_i); + res = isl_map_union_disjoint(res, better); + todo = todo_i; + } + + isl_set_free(dom); + isl_map_free(map); + + if (empty) + *empty = todo; else - return isl_tab_basic_map_partial_lexopt(bmap, dom, empty, max); + isl_set_free(todo); + + return res; error: - isl_basic_map_free(bmap); - isl_basic_set_free(dom); if (empty) *empty = NULL; + isl_set_free(dom); + isl_map_free(map); return NULL; } -struct isl_map *isl_basic_map_partial_lexmax( - struct isl_basic_map *bmap, struct isl_basic_set *dom, - struct isl_set **empty) +__isl_give isl_map *isl_map_partial_lexmax( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty) { - return isl_basic_map_partial_lexopt(bmap, dom, empty, 1); + return isl_map_partial_lexopt(map, dom, empty, 1); } -struct isl_map *isl_basic_map_partial_lexmin( - struct isl_basic_map *bmap, struct isl_basic_set *dom, - struct isl_set **empty) +__isl_give isl_map *isl_map_partial_lexmin( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty) { - return isl_basic_map_partial_lexopt(bmap, dom, empty, 0); + return isl_map_partial_lexopt(map, dom, empty, 0); } -struct isl_set *isl_basic_set_partial_lexmin( - struct isl_basic_set *bset, struct isl_basic_set *dom, - struct isl_set **empty) +__isl_give isl_set *isl_set_partial_lexmin( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty) { return (struct isl_set *) - isl_basic_map_partial_lexmin((struct isl_basic_map *)bset, + isl_map_partial_lexmin((struct isl_map *)set, dom, empty); } -struct isl_set *isl_basic_set_partial_lexmax( - struct isl_basic_set *bset, struct isl_basic_set *dom, - struct isl_set **empty) +__isl_give isl_set *isl_set_partial_lexmax( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty) { return (struct isl_set *) - isl_basic_map_partial_lexmax((struct isl_basic_map *)bset, + isl_map_partial_lexmax((struct isl_map *)set, dom, empty); } -__isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap) +__isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max) { struct isl_basic_set *dom = NULL; - struct isl_map *min; struct isl_dim *dom_dim; if (!bmap) goto error; dom_dim = isl_dim_domain(isl_dim_copy(bmap->dim)); dom = isl_basic_set_universe(dom_dim); - return isl_basic_map_partial_lexmin(bmap, dom, NULL); + return isl_basic_map_partial_lexopt(bmap, dom, NULL, max); error: isl_basic_map_free(bmap); return NULL; } +__isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap) +{ + return isl_basic_map_lexopt(bmap, 0); +} + +__isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap) +{ + return isl_basic_map_lexopt(bmap, 1); +} + __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset) { return (isl_set *)isl_basic_map_lexmin((isl_basic_map *)bset); } +__isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset) +{ + return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset); +} + +__isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max) +{ + struct isl_set *dom = NULL; + struct isl_dim *dom_dim; + + if (!map) + goto error; + dom_dim = isl_dim_domain(isl_dim_copy(map->dim)); + dom = isl_set_universe(dom_dim); + return isl_map_partial_lexopt(map, dom, NULL, max); +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map) +{ + return isl_map_lexopt(map, 0); +} + +__isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map) +{ + return isl_map_lexopt(map, 1); +} + +__isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set) +{ + return (isl_set *)isl_map_lexmin((isl_map *)set); +} + +__isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set) +{ + return (isl_set *)isl_map_lexmax((isl_map *)set); +} + static struct isl_map *isl_map_reset_dim(struct isl_map *map, struct isl_dim *dim) { @@ -3422,6 +4468,9 @@ static struct isl_basic_set *basic_set_append_equalities( } isl_mat_free(eq); + bset = isl_basic_set_gauss(bset, NULL); + bset = isl_basic_set_finalize(bset); + return bset; error: isl_mat_free(eq); @@ -3497,6 +4546,13 @@ static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset) 0, 1 + nparam); eq = isl_mat_cow(eq); T = isl_mat_variable_compression(isl_mat_copy(eq), &T2); + if (T && T->n_col == 0) { + isl_mat_free(T); + isl_mat_free(T2); + isl_mat_free(eq); + bset = isl_basic_set_set_to_empty(bset); + return isl_set_from_basic_set(bset); + } bset = basic_set_parameter_preimage(bset, T); set = isl_basic_set_lexmin(bset); @@ -3590,6 +4646,7 @@ 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); if (known < 0) @@ -3605,7 +4662,7 @@ struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap) if (known) return isl_map_from_basic_map(bmap); - struct isl_map *map = compute_divs(bmap); + map = compute_divs(bmap); return map; error: isl_basic_map_free(bmap); @@ -3716,13 +4773,13 @@ struct isl_map *isl_map_union_disjoint( if (!map) goto error; for (i = 0; i < map1->n; ++i) { - map = isl_map_add(map, + map = isl_map_add_basic_map(map, isl_basic_map_copy(map1->p[i])); if (!map) goto error; } for (i = 0; i < map2->n; ++i) { - map = isl_map_add(map, + map = isl_map_add_basic_map(map, isl_basic_map_copy(map2->p[i])); if (!map) goto error; @@ -3781,7 +4838,7 @@ struct isl_map *isl_map_intersect_range( goto error; for (i = 0; i < map->n; ++i) for (j = 0; j < set->n; ++j) { - result = isl_map_add(result, + result = isl_map_add_basic_map(result, isl_basic_map_intersect_range( isl_basic_map_copy(map->p[i]), isl_basic_set_copy(set->p[j]))); @@ -3836,7 +4893,7 @@ struct isl_map *isl_map_apply_range( goto error; for (i = 0; i < map1->n; ++i) for (j = 0; j < map2->n; ++j) { - result = isl_map_add(result, + result = isl_map_add_basic_map(result, isl_basic_map_apply_range( isl_basic_map_copy(map1->p[i]), isl_basic_map_copy(map2->p[j]))); @@ -3859,6 +4916,7 @@ error: */ struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap) { + isl_dim *dims; struct isl_basic_set *bset; unsigned dim; unsigned nparam; @@ -3871,7 +4929,9 @@ struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap) isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error); bset = isl_basic_set_from_basic_map(bmap); bset = isl_basic_set_cow(bset); - bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0); + dims = isl_basic_set_get_dim(bset); + dims = isl_dim_add(dims, isl_dim_set, dim); + bset = isl_basic_set_extend_dim(bset, dims, 0, dim, 0); bset = isl_basic_set_swap_vars(bset, 2*dim); for (i = 0; i < dim; ++i) { int j = isl_basic_map_alloc_equality( @@ -3895,18 +4955,20 @@ error: struct isl_set *isl_map_deltas(struct isl_map *map) { int i; + isl_dim *dim; struct isl_set *result; if (!map) return NULL; isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error); - result = isl_set_alloc(map->ctx, isl_map_n_param(map), - isl_map_n_in(map), map->n, map->flags); + dim = isl_map_get_dim(map); + dim = isl_dim_domain(dim); + result = isl_set_alloc_dim(dim, map->n, map->flags); if (!result) goto error; for (i = 0; i < map->n; ++i) - result = isl_set_add(result, + result = isl_set_add_basic_set(result, isl_basic_map_deltas(isl_basic_map_copy(map->p[i]))); isl_map_free(map); return result; @@ -3965,7 +5027,7 @@ struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model) static struct isl_map *map_identity(struct isl_dim *dim) { struct isl_map *map = isl_map_alloc_dim(dim, 1, ISL_MAP_DISJOINT); - return isl_map_add(map, basic_map_identity(isl_dim_copy(dim))); + 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) @@ -4024,15 +5086,53 @@ error: return NULL; } -int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2) +__isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set, + enum isl_dim_type type, unsigned first, unsigned n) { - return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2); + int i; + isl_basic_set *nonneg = NULL; + isl_basic_set *neg = NULL; + + if (!set) + return NULL; + if (n == 0) + return 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); + + 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; } -int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2) +int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2) { - return isl_map_is_subset( - (struct isl_map *)set1, (struct isl_map *)set2); + return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2); } int isl_basic_map_is_subset( @@ -4096,39 +5196,17 @@ int isl_map_is_empty(struct isl_map *map) int isl_map_fast_is_empty(struct isl_map *map) { - return map->n == 0; + return map ? map->n == 0 : -1; } -int isl_set_is_empty(struct isl_set *set) +int isl_set_fast_is_empty(struct isl_set *set) { - return isl_map_is_empty((struct isl_map *)set); + return set ? set->n == 0 : -1; } -int isl_map_is_subset(struct isl_map *map1, struct isl_map *map2) +int isl_set_is_empty(struct isl_set *set) { - int is_subset = 0; - struct isl_map *diff; - - if (!map1 || !map2) - return -1; - - if (isl_map_is_empty(map1)) - return 1; - - if (isl_map_is_empty(map2)) - return 0; - - if (isl_map_fast_is_universe(map2)) - return 1; - - diff = isl_map_subtract(isl_map_copy(map1), isl_map_copy(map2)); - if (!diff) - return -1; - - is_subset = isl_map_is_empty(diff); - isl_map_free(diff); - - return is_subset; + return isl_map_is_empty((struct isl_map *)set); } int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2) @@ -4202,6 +5280,11 @@ int isl_map_fast_is_universe(__isl_keep isl_map *map) return map->n == 1 && isl_basic_map_is_universe(map->p[0]); } +int isl_set_fast_is_universe(__isl_keep isl_set *set) +{ + return isl_map_fast_is_universe((isl_map *) set); +} + int isl_basic_map_is_empty(struct isl_basic_map *bmap) { struct isl_basic_set *bset = NULL; @@ -4217,7 +5300,7 @@ int isl_basic_map_is_empty(struct isl_basic_map *bmap) if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) { struct isl_basic_map *copy = isl_basic_map_copy(bmap); - copy = isl_basic_map_convex_hull(copy); + copy = isl_basic_map_remove_redundancies(copy); empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY); isl_basic_map_free(copy); return empty; @@ -4225,7 +5308,7 @@ int isl_basic_map_is_empty(struct isl_basic_map *bmap) total = 1 + isl_basic_map_total_dim(bmap); if (bmap->sample && bmap->sample->size == total) { - int contains = basic_map_contains(bmap, bmap->sample); + int contains = isl_basic_map_contains(bmap, bmap->sample); if (contains < 0) return -1; if (contains) @@ -4279,8 +5362,8 @@ struct isl_map *isl_basic_map_union( map = isl_map_alloc_dim(isl_dim_copy(bmap1->dim), 2, 0); if (!map) goto error; - map = isl_map_add(map, bmap1); - map = isl_map_add(map, bmap2); + map = isl_map_add_basic_map(map, bmap1); + map = isl_map_add_basic_map(map, bmap2); return map; error: isl_basic_map_free(bmap1); @@ -4300,7 +5383,12 @@ struct isl_set *isl_basic_set_union( struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap) { int i; - unsigned off = isl_dim_total(bmap->dim); + unsigned off; + + if (!bmap) + return NULL; + + off = isl_dim_total(bmap->dim); for (i = 0; i < bmap->n_div; ++i) { int pos; @@ -4322,6 +5410,25 @@ struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset) isl_basic_map_order_divs((struct isl_basic_map *)bset); } +__isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map) +{ + 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; +} + /* Look for a div in dst that corresponds to the div "div" in src. * The divs before "div" in src and dst are assumed to be the same. * @@ -4373,7 +5480,7 @@ struct isl_basic_map *isl_basic_map_align_divs( goto error; isl_seq_cpy(dst->div[j], src->div[i], 1+1+total+i); isl_seq_clr(dst->div[j]+1+1+total+i, dst->n_div - i); - if (add_div_constraints(dst, j) < 0) + if (isl_basic_map_add_div_constraints(dst, j) < 0) goto error; } if (j != i) @@ -4419,168 +5526,6 @@ struct isl_set *isl_set_align_divs(struct isl_set *set) return (struct isl_set *)isl_map_align_divs((struct isl_map *)set); } -static struct isl_map *add_cut_constraint(struct isl_map *dst, - struct isl_basic_map *src, isl_int *c, - unsigned len, int oppose) -{ - struct isl_basic_map *copy = NULL; - int is_empty; - int k; - unsigned total; - - copy = isl_basic_map_copy(src); - copy = isl_basic_map_cow(copy); - if (!copy) - goto error; - copy = isl_basic_map_extend_constraints(copy, 0, 1); - k = isl_basic_map_alloc_inequality(copy); - if (k < 0) - goto error; - if (oppose) - isl_seq_neg(copy->ineq[k], c, len); - else - isl_seq_cpy(copy->ineq[k], c, len); - total = 1 + isl_basic_map_total_dim(copy); - isl_seq_clr(copy->ineq[k]+len, total - len); - isl_inequality_negate(copy, k); - copy = isl_basic_map_simplify(copy); - copy = isl_basic_map_finalize(copy); - is_empty = isl_basic_map_is_empty(copy); - if (is_empty < 0) - goto error; - if (!is_empty) - dst = isl_map_add(dst, copy); - else - isl_basic_map_free(copy); - return dst; -error: - isl_basic_map_free(copy); - isl_map_free(dst); - return NULL; -} - -static struct isl_map *subtract(struct isl_map *map, struct isl_basic_map *bmap) -{ - int i, j, k; - unsigned flags = 0; - struct isl_map *rest = NULL; - unsigned max; - unsigned total = isl_basic_map_total_dim(bmap); - - map = isl_map_cow(map); - - if (!map || !bmap) - goto error; - - if (ISL_F_ISSET(map, ISL_MAP_DISJOINT)) - ISL_FL_SET(flags, ISL_MAP_DISJOINT); - - max = map->n * (2 * bmap->n_eq + bmap->n_ineq); - rest = isl_map_alloc_dim(isl_dim_copy(map->dim), max, flags); - if (!rest) - goto error; - - for (i = 0; i < map->n; ++i) { - map->p[i] = isl_basic_map_align_divs(map->p[i], bmap); - if (!map->p[i]) - goto error; - } - - for (j = 0; j < map->n; ++j) - map->p[j] = isl_basic_map_cow(map->p[j]); - - for (i = 0; i < bmap->n_eq; ++i) { - for (j = 0; j < map->n; ++j) { - rest = add_cut_constraint(rest, - map->p[j], bmap->eq[i], 1+total, 0); - if (!rest) - goto error; - - rest = add_cut_constraint(rest, - map->p[j], bmap->eq[i], 1+total, 1); - if (!rest) - goto error; - - map->p[j] = isl_basic_map_extend_constraints(map->p[j], - 1, 0); - if (!map->p[j]) - goto error; - k = isl_basic_map_alloc_equality(map->p[j]); - if (k < 0) - goto error; - isl_seq_cpy(map->p[j]->eq[k], bmap->eq[i], 1+total); - isl_seq_clr(map->p[j]->eq[k]+1+total, - map->p[j]->n_div - bmap->n_div); - } - } - - for (i = 0; i < bmap->n_ineq; ++i) { - for (j = 0; j < map->n; ++j) { - rest = add_cut_constraint(rest, - map->p[j], bmap->ineq[i], 1+total, 0); - if (!rest) - goto error; - - map->p[j] = isl_basic_map_extend_constraints(map->p[j], - 0, 1); - if (!map->p[j]) - goto error; - k = isl_basic_map_alloc_inequality(map->p[j]); - if (k < 0) - goto error; - isl_seq_cpy(map->p[j]->ineq[k], bmap->ineq[i], 1+total); - isl_seq_clr(map->p[j]->ineq[k]+1+total, - map->p[j]->n_div - bmap->n_div); - } - } - - isl_map_free(map); - return rest; -error: - isl_map_free(map); - isl_map_free(rest); - return NULL; -} - -struct isl_map *isl_map_subtract(struct isl_map *map1, struct isl_map *map2) -{ - int i; - if (!map1 || !map2) - goto error; - - isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error); - - if (isl_map_is_empty(map2)) { - isl_map_free(map2); - return map1; - } - - map1 = isl_map_compute_divs(map1); - map2 = isl_map_compute_divs(map2); - if (!map1 || !map2) - goto error; - - map1 = isl_map_remove_empty_parts(map1); - map2 = isl_map_remove_empty_parts(map2); - - for (i = 0; map1 && i < map2->n; ++i) - map1 = subtract(map1, map2->p[i]); - - isl_map_free(map2); - return map1; -error: - isl_map_free(map1); - isl_map_free(map2); - return NULL; -} - -struct isl_set *isl_set_subtract(struct isl_set *set1, struct isl_set *set2) -{ - return (struct isl_set *) - isl_map_subtract( - (struct isl_map *)set1, (struct isl_map *)set2); -} - struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map) { if (!set || !map) @@ -4641,8 +5586,8 @@ struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set) isl_map_copy_basic_map((struct isl_map *)set); } -struct isl_map *isl_map_drop_basic_map(struct isl_map *map, - struct isl_basic_map *bmap) +__isl_give isl_map *isl_map_drop_basic_map(__isl_take isl_map *map, + __isl_keep isl_basic_map *bmap) { int i; @@ -4662,11 +5607,9 @@ struct isl_map *isl_map_drop_basic_map(struct isl_map *map, map->n--; return map; } - isl_basic_map_free(bmap); return map; error: isl_map_free(map); - isl_basic_map_free(bmap); return NULL; } @@ -4677,19 +5620,13 @@ struct isl_set *isl_set_drop_basic_set(struct isl_set *set, (struct isl_basic_map *)bset); } -/* Given two _disjoint_ basic sets bset1 and bset2, check whether - * for any common value of the parameters and dimensions preceding dim - * in both basic sets, the values of dimension pos in bset1 are - * smaller or larger than those in bset2. - * - * Returns - * 1 if bset1 follows bset2 - * -1 if bset1 precedes bset2 - * 0 if bset1 and bset2 are incomparable - * -2 if some error occurred. +/* Given two basic sets bset1 and bset2, compute the maximal difference + * between the values of dimension pos in bset1 and those in bset2 + * for any common value of the parameters and dimensions preceding pos. */ -int isl_basic_set_compare_at(struct isl_basic_set *bset1, - struct isl_basic_set *bset2, int pos) +static enum isl_lp_result basic_set_maximal_difference_at( + __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2, + int pos, isl_int *opt) { struct isl_dim *dims; struct isl_basic_map *bmap1 = NULL; @@ -4699,12 +5636,10 @@ int isl_basic_set_compare_at(struct isl_basic_set *bset1, unsigned total; unsigned nparam; unsigned dim1, dim2; - isl_int num, den; enum isl_lp_result res; - int cmp; if (!bset1 || !bset2) - return -2; + return isl_lp_error; nparam = isl_basic_set_n_param(bset1); dim1 = isl_basic_set_n_dim(bset1); @@ -4730,28 +5665,122 @@ int isl_basic_set_compare_at(struct isl_basic_set *bset1, isl_int_set_si(obj->block.data[1+nparam+pos+(dim1-pos)], -1); if (!obj) goto error; - isl_int_init(num); - isl_int_init(den); - res = isl_basic_map_solve_lp(bmap1, 0, obj->block.data, ctx->one, - &num, &den, NULL); + res = isl_basic_map_solve_lp(bmap1, 1, obj->block.data, ctx->one, + opt, NULL, NULL); + isl_basic_map_free(bmap1); + isl_vec_free(obj); + return res; +error: + isl_basic_map_free(bmap1); + isl_basic_map_free(bmap2); + return isl_lp_error; +} + +/* Given two _disjoint_ basic sets bset1 and bset2, check whether + * for any common value of the parameters and dimensions preceding pos + * in both basic sets, the values of dimension pos in bset1 are + * smaller or larger than those in bset2. + * + * Returns + * 1 if bset1 follows bset2 + * -1 if bset1 precedes bset2 + * 0 if bset1 and bset2 are incomparable + * -2 if some error occurred. + */ +int isl_basic_set_compare_at(struct isl_basic_set *bset1, + struct isl_basic_set *bset2, int pos) +{ + isl_int opt; + enum isl_lp_result res; + int cmp; + + isl_int_init(opt); + + res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt); + if (res == isl_lp_empty) cmp = 0; - else if (res == isl_lp_ok && isl_int_is_pos(num)) + else if ((res == isl_lp_ok && isl_int_is_pos(opt)) || + res == isl_lp_unbounded) cmp = 1; - else if ((res == isl_lp_ok && isl_int_is_neg(num)) || + else if (res == isl_lp_ok && isl_int_is_neg(opt)) + cmp = -1; + else + cmp = -2; + + isl_int_clear(opt); + return cmp; +} + +/* Given two basic sets bset1 and bset2, check whether + * for any common value of the parameters and dimensions preceding pos + * there is a value of dimension pos in bset1 that is larger + * than a value of the same dimension in bset2. + * + * Return + * 1 if there exists such a pair + * 0 if there is no such pair, but there is a pair of equal values + * -1 otherwise + * -2 if some error occurred. + */ +int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1, + __isl_keep isl_basic_set *bset2, int pos) +{ + isl_int opt; + enum isl_lp_result res; + int cmp; + + isl_int_init(opt); + + res = basic_set_maximal_difference_at(bset1, bset2, pos, &opt); + + if (res == isl_lp_empty) + cmp = -1; + else if ((res == isl_lp_ok && isl_int_is_pos(opt)) || res == isl_lp_unbounded) + cmp = 1; + else if (res == isl_lp_ok && isl_int_is_neg(opt)) cmp = -1; + else if (res == isl_lp_ok) + cmp = 0; else cmp = -2; - isl_int_clear(num); - isl_int_clear(den); - isl_basic_map_free(bmap1); - isl_vec_free(obj); + + isl_int_clear(opt); return cmp; -error: - isl_basic_map_free(bmap1); - isl_basic_map_free(bmap2); - return -2; +} + +/* Given two sets set1 and set2, check whether + * for any common value of the parameters and dimensions preceding pos + * there is a value of dimension pos in set1 that is larger + * than a value of the same dimension in set2. + * + * Return + * 1 if there exists such a pair + * 0 if there is no such pair, but there is a pair of equal values + * -1 otherwise + * -2 if some error occurred. + */ +int isl_set_follows_at(__isl_keep isl_set *set1, + __isl_keep isl_set *set2, int pos) +{ + int i, j; + int follows = -1; + + if (!set1 || !set2) + return -2; + + for (i = 0; i < set1->n; ++i) + for (j = 0; j < set2->n; ++j) { + int f; + f = isl_basic_set_follows_at(set1->p[i], set2->p[j], pos); + if (f == 1 || f == -2) + return f; + if (f > follows) + follows = f; + } + + return follows; } static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap, @@ -4986,13 +6015,20 @@ error: return NULL; } +__isl_give isl_basic_set *isl_basic_set_sort_constraints( + __isl_take isl_basic_set *bset) +{ + return (struct isl_basic_set *)isl_basic_map_sort_constraints( + (struct isl_basic_map *)bset); +} + struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap) { if (!bmap) return NULL; if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED)) return bmap; - bmap = isl_basic_map_convex_hull(bmap); + bmap = isl_basic_map_remove_redundancies(bmap); bmap = isl_basic_map_sort_constraints(bmap); ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED); return bmap; @@ -5004,8 +6040,8 @@ struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset) (struct isl_basic_map *)bset); } -static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1, - const struct isl_basic_map *bmap2) +int isl_basic_map_fast_cmp(const __isl_keep isl_basic_map *bmap1, + const __isl_keep isl_basic_map *bmap2) { int i, cmp; unsigned total; @@ -5050,12 +6086,19 @@ static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1, return 0; } -static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1, - struct isl_basic_map *bmap2) +int isl_basic_map_fast_is_equal(__isl_keep isl_basic_map *bmap1, + __isl_keep isl_basic_map *bmap2) { return isl_basic_map_fast_cmp(bmap1, bmap2) == 0; } +int isl_basic_set_fast_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, + (isl_basic_map *)bset2); +} + static int qsort_bmap_cmp(const void *p1, const void *p2) { const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1; @@ -5307,7 +6350,7 @@ struct isl_map *isl_map_product(struct isl_map *map1, struct isl_map *map2) if (isl_basic_map_is_empty(part)) isl_basic_map_free(part); else - result = isl_map_add(result, part); + result = isl_map_add_basic_map(result, part); if (!result) goto error; } @@ -5458,6 +6501,73 @@ int isl_set_foreach_basic_set(__isl_keep isl_set *set, return 0; } +__isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset) +{ + struct isl_dim *dim; + + 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); + if (!dim) + goto error; + isl_dim_free(bset->dim); + bset->dim = dim; + bset->n_div = 0; + + bset = isl_basic_set_finalize(bset); + + return bset; +error: + isl_basic_set_free(bset); + return NULL; +} + +__isl_give isl_set *isl_set_lift(__isl_take isl_set *set) +{ + int i; + struct isl_dim *dim; + unsigned n_div; + + set = isl_set_align_divs(set); + + if (!set) + return NULL; + if (set->n == 0 || set->p[0]->n_div == 0) + return set; + + set = isl_set_cow(set); + if (!set) + return NULL; + + n_div = set->p[0]->n_div; + dim = isl_set_get_dim(set); + dim = isl_dim_add(dim, isl_dim_set, n_div); + if (!dim) + goto error; + isl_dim_free(set->dim); + set->dim = dim; + + for (i = 0; i < set->n; ++i) { + set->p[i] = isl_basic_set_lift(set->p[i]); + if (!set->p[i]) + goto error; + } + + return set; +error: + isl_set_free(set); + return NULL; +} + __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set) { struct isl_dim *dim; @@ -5546,3 +6656,255 @@ int isl_set_size(__isl_keep isl_set *set) return size; } + +int isl_basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos) +{ + int i; + int lower, upper; + + if (!bmap) + return -1; + + isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1); + + pos += isl_basic_map_offset(bmap, type); + + for (i = 0; i < bmap->n_eq; ++i) + if (!isl_int_is_zero(bmap->eq[i][pos])) + return 1; + + lower = upper = 0; + for (i = 0; i < bmap->n_ineq; ++i) { + int sgn = isl_int_sgn(bmap->ineq[i][pos]); + if (sgn > 0) + lower = 1; + if (sgn < 0) + upper = 1; + } + + return lower && upper; +} + +int isl_map_dim_is_bounded(__isl_keep isl_map *map, + enum isl_dim_type type, unsigned pos) +{ + int i; + + if (!map) + return -1; + + for (i = 0; i < map->n; ++i) { + int bounded; + bounded = isl_basic_map_dim_is_bounded(map->p[i], type, pos); + if (bounded < 0 || !bounded) + return bounded; + } + + return 1; +} + +/* Return 1 if the specified dim is involved in both an upper bound + * and a lower bound. + */ +int isl_set_dim_is_bounded(__isl_keep isl_set *set, + enum isl_dim_type type, unsigned pos) +{ + return isl_map_dim_is_bounded((isl_map *)set, type, pos); +} + +/* For each of the "n" variables starting at "first", determine + * the sign of the variable and put the results in the first "n" + * elements of the array "signs". + * Sign + * 1 means that the variable is non-negative + * -1 means that the variable is non-positive + * 0 means the variable attains both positive and negative values. + */ +int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset, + unsigned first, unsigned n, int *signs) +{ + isl_vec *bound = NULL; + struct isl_tab *tab = NULL; + struct isl_tab_undo *snap; + int i; + + if (!bset || !signs) + return -1; + + bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset)); + tab = isl_tab_from_basic_set(bset); + if (!bound || !tab) + goto error; + + isl_seq_clr(bound->el, bound->size); + isl_int_set_si(bound->el[0], -1); + + snap = isl_tab_snap(tab); + for (i = 0; i < n; ++i) { + int empty; + + isl_int_set_si(bound->el[1 + first + i], -1); + if (isl_tab_add_ineq(tab, bound->el) < 0) + goto error; + empty = tab->empty; + isl_int_set_si(bound->el[1 + first + i], 0); + if (isl_tab_rollback(tab, snap) < 0) + goto error; + + if (empty) { + signs[i] = 1; + continue; + } + + isl_int_set_si(bound->el[1 + first + i], 1); + if (isl_tab_add_ineq(tab, bound->el) < 0) + goto error; + empty = tab->empty; + isl_int_set_si(bound->el[1 + first + i], 0); + if (isl_tab_rollback(tab, snap) < 0) + goto error; + + signs[i] = empty ? -1 : 0; + } + + isl_tab_free(tab); + isl_vec_free(bound); + return 0; +error: + isl_tab_free(tab); + isl_vec_free(bound); + return -1; +} + +int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset, + enum isl_dim_type type, unsigned first, unsigned n, int *signs) +{ + if (!bset || !signs) + return -1; + isl_assert(bset->ctx, first + n <= isl_basic_set_dim(bset, type), + return -1); + + first += pos(bset->dim, type) - 1; + return isl_basic_set_vars_get_sign(bset, first, n, signs); +} + +/* Check if the given 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_map_is_single_valued(__isl_keep isl_map *map) +{ + isl_map *test; + isl_map *id; + int 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))); + + sv = isl_map_is_subset(test, id); + + isl_map_free(test); + isl_map_free(id); + + return sv; +} + +int isl_map_is_bijective(__isl_keep isl_map *map) +{ + int sv; + + sv = isl_map_is_single_valued(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; +} + +int isl_set_is_singleton(__isl_keep isl_set *set) +{ + return isl_map_is_single_valued((isl_map *)set); +} + +int isl_map_is_translation(__isl_keep isl_map *map) +{ + int ok; + isl_set *delta; + + delta = isl_map_deltas(isl_map_copy(map)); + ok = isl_set_is_singleton(delta); + isl_set_free(delta); + + return ok; +} + +static int unique(isl_int *p, unsigned pos, unsigned len) +{ + if (isl_seq_first_non_zero(p, pos) != -1) + return 0; + if (isl_seq_first_non_zero(p + pos + 1, len - pos - 1) != -1) + return 0; + return 1; +} + +int isl_basic_set_is_box(__isl_keep isl_basic_set *bset) +{ + int i, j; + unsigned nvar; + unsigned ovar; + + if (!bset) + return -1; + + if (isl_basic_set_dim(bset, isl_dim_div) != 0) + return 0; + + nvar = isl_basic_set_dim(bset, isl_dim_set); + ovar = isl_dim_offset(bset->dim, isl_dim_set); + for (j = 0; j < nvar; ++j) { + int lower = 0, upper = 0; + for (i = 0; i < bset->n_eq; ++i) { + if (isl_int_is_zero(bset->eq[i][1 + ovar + j])) + continue; + if (!unique(bset->eq[i] + 1 + ovar, j, nvar)) + return 0; + break; + } + if (i < bset->n_eq) + continue; + for (i = 0; i < bset->n_ineq; ++i) { + if (isl_int_is_zero(bset->ineq[i][1 + ovar + j])) + continue; + if (!unique(bset->ineq[i] + 1 + ovar, j, nvar)) + return 0; + if (isl_int_is_pos(bset->ineq[i][1 + ovar + j])) + lower = 1; + else + upper = 1; + } + if (!lower || !upper) + return 0; + } + + return 1; +} + +int isl_set_is_box(__isl_keep isl_set *set) +{ + if (!set) + return -1; + if (set->n != 1) + return 0; + + return isl_basic_set_is_box(set->p[0]); +}