+struct isl_map *isl_map_intersect_range(
+ struct isl_map *map, struct isl_set *set)
+{
+ unsigned flags = 0;
+ struct isl_map *result;
+ int i, j;
+
+ if (!map || !set)
+ goto error;
+
+ if (ISL_F_ISSET(map, ISL_MAP_DISJOINT) &&
+ ISL_F_ISSET(set, ISL_MAP_DISJOINT))
+ ISL_FL_SET(flags, ISL_MAP_DISJOINT);
+
+ result = isl_map_alloc_dim(isl_dim_copy(map->dim),
+ map->n * set->n, flags);
+ if (!result)
+ goto error;
+ for (i = 0; i < map->n; ++i)
+ for (j = 0; j < set->n; ++j) {
+ result = isl_map_add(result,
+ isl_basic_map_intersect_range(
+ isl_basic_map_copy(map->p[i]),
+ isl_basic_set_copy(set->p[j])));
+ if (!result)
+ goto error;
+ }
+ isl_map_free(map);
+ isl_set_free(set);
+ return result;
+error:
+ isl_map_free(map);
+ isl_set_free(set);
+ return NULL;
+}
+
+struct isl_map *isl_map_intersect_domain(
+ struct isl_map *map, struct isl_set *set)
+{
+ return isl_map_reverse(
+ isl_map_intersect_range(isl_map_reverse(map), set));
+}
+
+struct isl_map *isl_map_apply_domain(
+ struct isl_map *map1, struct isl_map *map2)
+{
+ if (!map1 || !map2)
+ goto error;
+ map1 = isl_map_reverse(map1);
+ map1 = isl_map_apply_range(map1, map2);
+ return isl_map_reverse(map1);
+error:
+ isl_map_free(map1);
+ isl_map_free(map2);
+ return NULL;
+}
+
+struct isl_map *isl_map_apply_range(
+ struct isl_map *map1, struct isl_map *map2)
+{
+ struct isl_dim *dim_result;
+ struct isl_map *result;
+ int i, j;
+ unsigned nparam;
+ unsigned n_in;
+ unsigned n_out;
+
+ if (!map1 || !map2)
+ goto error;
+
+ dim_result = isl_dim_join(isl_dim_copy(map1->dim),
+ isl_dim_copy(map2->dim));
+
+ result = isl_map_alloc_dim(dim_result, map1->n * map2->n, 0);
+ if (!result)
+ goto error;
+ for (i = 0; i < map1->n; ++i)
+ for (j = 0; j < map2->n; ++j) {
+ result = isl_map_add(result,
+ isl_basic_map_apply_range(
+ isl_basic_map_copy(map1->p[i]),
+ isl_basic_map_copy(map2->p[j])));
+ if (!result)
+ goto error;
+ }
+ isl_map_free(map1);
+ isl_map_free(map2);
+ if (result && result->n <= 1)
+ ISL_F_SET(result, ISL_MAP_DISJOINT);
+ return result;
+error:
+ isl_map_free(map1);
+ isl_map_free(map2);
+ return NULL;
+}
+
+/*
+ * returns range - domain
+ */
+struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
+{
+ struct isl_basic_set *bset;
+ unsigned dim;
+ unsigned nparam;
+ int i;
+
+ if (!bmap)
+ goto error;
+ dim = isl_basic_map_n_in(bmap);
+ nparam = isl_basic_map_n_param(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);
+ bset = isl_basic_set_swap_vars(bset, 2*dim);
+ for (i = 0; i < dim; ++i) {
+ int j = isl_basic_map_alloc_equality(
+ (struct isl_basic_map *)bset);
+ if (j < 0)
+ goto error;
+ isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
+ isl_int_set_si(bset->eq[j][1+nparam+i], 1);
+ isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
+ isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
+ }
+ return isl_basic_set_project_out(bset, 2*dim, 0);
+error:
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
+/*
+ * returns range - domain
+ */
+struct isl_set *isl_map_deltas(struct isl_map *map)
+{
+ int i;
+ 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);
+ if (!result)
+ goto error;
+ for (i = 0; i < map->n; ++i)
+ result = isl_set_add(result,
+ isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
+ isl_map_free(map);
+ return result;
+error:
+ isl_map_free(map);
+ return NULL;
+}
+
+static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
+{
+ struct isl_basic_map *bmap;
+ unsigned nparam;
+ unsigned dim;
+ int i;
+
+ if (!dims)
+ return NULL;
+
+ nparam = dims->nparam;
+ dim = dims->n_out;
+ bmap = isl_basic_map_alloc_dim(dims, 0, dim, 0);
+ if (!bmap)
+ goto error;
+
+ for (i = 0; i < dim; ++i) {
+ int 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][1+nparam+i], 1);
+ isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
+ }
+ return isl_basic_map_finalize(bmap);
+error:
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
+struct isl_basic_map *isl_basic_map_identity(struct isl_dim *set_dim)
+{
+ struct isl_dim *dim = isl_dim_map(set_dim);
+ if (!dim)
+ return NULL;
+ return basic_map_identity(dim);
+}
+
+struct isl_basic_map *isl_basic_map_identity_like(struct isl_basic_map *model)
+{
+ if (!model || !model->dim)
+ return NULL;
+ isl_assert(model->ctx,
+ model->dim->n_in == model->dim->n_out, return NULL);
+ return basic_map_identity(isl_dim_copy(model->dim));
+}
+
+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)));
+}
+
+struct isl_map *isl_map_identity(struct isl_dim *set_dim)
+{
+ struct isl_dim *dim = isl_dim_map(set_dim);
+ if (!dim)
+ return NULL;
+ return map_identity(dim);
+}
+
+struct isl_map *isl_map_identity_like(struct isl_basic_map *model)
+{
+ if (!model || !model->dim)
+ return NULL;
+ isl_assert(model->ctx,
+ model->dim->n_in == model->dim->n_out, return NULL);
+ return map_identity(isl_dim_copy(model->dim));
+}
+
+int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
+{
+ return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
+}
+
+int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2)
+{
+ return isl_map_is_subset(
+ (struct isl_map *)set1, (struct isl_map *)set2);
+}
+
+int isl_basic_map_is_subset(
+ struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
+{
+ int is_subset;
+ struct isl_map *map1;
+ struct isl_map *map2;
+
+ if (!bmap1 || !bmap2)
+ return -1;
+
+ map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
+ map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
+
+ is_subset = isl_map_is_subset(map1, map2);
+
+ isl_map_free(map1);
+ isl_map_free(map2);
+
+ return is_subset;
+}
+
+int isl_basic_map_is_equal(
+ struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
+{
+ int is_subset;
+
+ if (!bmap1 || !bmap2)
+ return -1;
+ is_subset = isl_basic_map_is_subset(bmap1, bmap2);
+ if (is_subset != 1)
+ return is_subset;
+ is_subset = isl_basic_map_is_subset(bmap2, bmap1);
+ return is_subset;
+}
+
+int isl_basic_set_is_equal(
+ struct isl_basic_set *bset1, struct isl_basic_set *bset2)
+{
+ return isl_basic_map_is_equal(
+ (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
+}
+
+int isl_map_is_empty(struct isl_map *map)
+{
+ int i;
+ int is_empty;
+
+ if (!map)
+ return -1;
+ for (i = 0; i < map->n; ++i) {
+ is_empty = isl_basic_map_is_empty(map->p[i]);
+ if (is_empty < 0)
+ return -1;
+ if (!is_empty)
+ return 0;
+ }
+ return 1;
+}
+
+int isl_map_fast_is_empty(struct isl_map *map)
+{
+ return map->n == 0;
+}
+
+int isl_set_is_empty(struct isl_set *set)
+{
+ return isl_map_is_empty((struct isl_map *)set);
+}
+
+int isl_map_is_subset(struct isl_map *map1, struct isl_map *map2)
+{
+ int i;
+ 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;
+
+ 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;
+}
+
+int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
+{
+ int is_subset;
+
+ if (!map1 || !map2)
+ return -1;
+ is_subset = isl_map_is_subset(map1, map2);
+ if (is_subset != 1)
+ return is_subset;
+ is_subset = isl_map_is_subset(map2, map1);
+ return is_subset;
+}
+
+int isl_basic_map_is_strict_subset(
+ struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
+{
+ int is_subset;
+
+ if (!bmap1 || !bmap2)
+ return -1;
+ is_subset = isl_basic_map_is_subset(bmap1, bmap2);
+ if (is_subset != 1)
+ return is_subset;
+ is_subset = isl_basic_map_is_subset(bmap2, bmap1);
+ if (is_subset == -1)
+ return is_subset;
+ return !is_subset;
+}
+
+int isl_basic_map_is_universe(struct isl_basic_map *bmap)
+{
+ if (!bmap)
+ return -1;
+ return bmap->n_eq == 0 && bmap->n_ineq == 0;
+}
+
+int isl_basic_set_is_universe(struct isl_basic_set *bset)
+{
+ if (!bset)
+ return -1;
+ return bset->n_eq == 0 && bset->n_ineq == 0;
+}
+
+int isl_basic_map_is_empty(struct isl_basic_map *bmap)
+{
+ struct isl_basic_set *bset = NULL;
+ struct isl_vec *sample = NULL;
+ int empty;
+ unsigned total;
+
+ if (!bmap)
+ return -1;
+
+ if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
+ return 1;
+
+ 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);
+ empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
+ isl_basic_map_free(copy);
+ return empty;
+ }
+
+ total = 1 + isl_basic_map_total_dim(bmap);
+ if (bmap->sample && bmap->sample->size == total) {
+ int contains = basic_map_contains(bmap, bmap->sample);
+ if (contains < 0)
+ return -1;
+ if (contains)
+ return 0;
+ }
+ isl_vec_free(bmap->sample);
+ bmap->sample = NULL;
+ bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
+ if (!bset)
+ return -1;
+ sample = isl_basic_set_sample(bset);
+ if (!sample)
+ return -1;
+ empty = sample->size == 0;
+ isl_vec_free(bmap->sample);
+ bmap->sample = sample;
+ if (empty)
+ ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
+
+ return empty;
+}
+
+int isl_basic_map_fast_is_empty(struct isl_basic_map *bmap)
+{
+ if (!bmap)
+ return -1;
+ return ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY);
+}
+
+int isl_basic_set_fast_is_empty(struct isl_basic_set *bset)
+{
+ if (!bset)
+ return -1;
+ return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY);
+}
+
+int isl_basic_set_is_empty(struct isl_basic_set *bset)
+{
+ return isl_basic_map_is_empty((struct isl_basic_map *)bset);
+}
+
+struct isl_map *isl_basic_map_union(
+ struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
+{
+ struct isl_map *map;
+ if (!bmap1 || !bmap2)
+ return NULL;
+
+ isl_assert(map1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
+
+ 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);
+ return map;
+error:
+ isl_basic_map_free(bmap1);
+ isl_basic_map_free(bmap2);
+ return NULL;
+}
+
+struct isl_set *isl_basic_set_union(
+ struct isl_basic_set *bset1, struct isl_basic_set *bset2)
+{
+ return (struct isl_set *)isl_basic_map_union(
+ (struct isl_basic_map *)bset1,
+ (struct isl_basic_map *)bset2);
+}
+
+/* Order divs such that any div only depends on previous divs */
+static struct isl_basic_map *order_divs(struct isl_basic_map *bmap)
+{
+ int i;
+ unsigned off = isl_dim_total(bmap->dim);
+
+ for (i = 0; i < bmap->n_div; ++i) {
+ int pos;
+ pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
+ bmap->n_div-i);
+ if (pos == -1)
+ continue;
+ swap_div(bmap, i, i + pos);
+ --i;
+ }
+ return bmap;
+}
+
+/* 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.
+ *
+ * Returns -1 if no corresponding div was found and the position
+ * of the corresponding div in dst otherwise.
+ */
+static int find_div(struct isl_basic_map *dst,
+ struct isl_basic_map *src, unsigned div)
+{
+ int i;
+
+ unsigned total = isl_dim_total(src->dim);
+
+ isl_assert(dst->ctx, div <= dst->n_div, return -1);
+ for (i = div; i < dst->n_div; ++i)
+ if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total+div) &&
+ isl_seq_first_non_zero(dst->div[i]+1+1+total+div,
+ dst->n_div - div) == -1)
+ return i;
+ return -1;
+}
+
+struct isl_basic_map *isl_basic_map_align_divs(
+ struct isl_basic_map *dst, struct isl_basic_map *src)
+{
+ int i;
+ unsigned total = isl_dim_total(src->dim);
+
+ if (!dst || !src)
+ goto error;
+
+ if (src->n_div == 0)
+ return dst;
+
+ for (i = 0; i < src->n_div; ++i)
+ isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error);
+
+ src = order_divs(src);
+ dst = isl_basic_map_cow(dst);
+ dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim),
+ src->n_div, 0, 2 * src->n_div);
+ if (!dst)
+ return NULL;
+ for (i = 0; i < src->n_div; ++i) {
+ int j = find_div(dst, src, i);
+ if (j < 0) {
+ j = isl_basic_map_alloc_div(dst);
+ if (j < 0)
+ 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)
+ goto error;
+ }
+ if (j != i)
+ swap_div(dst, i, j);
+ }
+ return dst;
+error:
+ isl_basic_map_free(dst);
+ return NULL;
+}
+
+struct isl_basic_set *isl_basic_set_align_divs(
+ struct isl_basic_set *dst, struct isl_basic_set *src)
+{
+ return (struct isl_basic_set *)isl_basic_map_align_divs(
+ (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
+}
+
+struct isl_map *isl_map_align_divs(struct isl_map *map)
+{
+ int i;
+
+ map = isl_map_compute_divs(map);
+ map = isl_map_cow(map);
+ if (!map)
+ return NULL;
+
+ for (i = 1; i < map->n; ++i)
+ map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
+ for (i = 1; i < map->n; ++i)
+ map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
+
+ ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+ return map;
+}
+
+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);
+
+ assert(bmap);
+
+ if (!map)
+ 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;