#include <string.h>
#include <strings.h>
+#include <isl_ctx_private.h>
#include <isl_map_private.h>
-#include <isl/ctx.h>
#include <isl/blk.h>
#include "isl_dim_private.h"
#include "isl_equalities.h"
#include "isl_tab.h"
#include <isl/vec.h>
#include <isl_mat_private.h>
-
-/* Maps dst positions to src positions */
-struct isl_dim_map {
- unsigned len;
- int pos[1];
-};
-
-static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len)
-{
- int i;
- struct isl_dim_map *dim_map;
- dim_map = isl_alloc(ctx, struct isl_dim_map,
- sizeof(struct isl_dim_map) + len * sizeof(int));
- if (!dim_map)
- return NULL;
- dim_map->len = 1 + len;
- dim_map->pos[0] = 0;
- for (i = 0; i < len; ++i)
- dim_map->pos[1 + i] = -1;
- return dim_map;
-}
+#include <isl_dim_map.h>
static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
{
}
}
-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;
-
- if (!dim_map || !dim)
- return;
-
- src_pos = pos(dim, type);
- 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,
- struct isl_basic_map *bmap, unsigned dst_pos)
-{
- int i;
- unsigned src_pos;
-
- if (!dim_map || !bmap)
- return;
-
- src_pos = 1 + isl_dim_total(bmap->dim);
- for (i = 0; i < bmap->n_div; ++i)
- dim_map->pos[1 + dst_pos + i] = src_pos + i;
-}
-
-static void isl_dim_map_dump(struct isl_dim_map *dim_map)
-{
- int i;
-
- for (i = 0; i < dim_map->len; ++i)
- fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]);
- fprintf(stderr, "\n");
-}
-
unsigned isl_basic_map_dim(const struct isl_basic_map *bmap,
enum isl_dim_type type)
{
}
}
+unsigned isl_basic_set_offset(struct isl_basic_set *bset,
+ enum isl_dim_type type)
+{
+ return isl_basic_map_offset(bset, type);
+}
+
static unsigned map_offset(struct isl_map *map, enum isl_dim_type type)
{
return pos(map->dim, type);
return NULL;
}
-static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
- struct isl_dim_map *dim_map)
-{
- int i;
-
- for (i = 0; i < dim_map->len; ++i) {
- if (dim_map->pos[i] < 0)
- isl_int_set_si(dst[i], 0);
- else
- isl_int_set(dst[i], src[dim_map->pos[i]]);
- }
-}
-
-static void copy_div_dim_map(isl_int *dst, isl_int *src,
- struct isl_dim_map *dim_map)
-{
- isl_int_set(dst[0], src[0]);
- copy_constraint_dim_map(dst+1, src+1, dim_map);
-}
-
-static struct isl_basic_map *add_constraints_dim_map(struct isl_basic_map *dst,
- struct isl_basic_map *src, struct isl_dim_map *dim_map)
-{
- int i;
-
- if (!src || !dst || !dim_map)
- goto error;
-
- for (i = 0; i < src->n_eq; ++i) {
- int i1 = isl_basic_map_alloc_equality(dst);
- if (i1 < 0)
- goto error;
- copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
- }
-
- for (i = 0; i < src->n_ineq; ++i) {
- int i1 = isl_basic_map_alloc_inequality(dst);
- if (i1 < 0)
- goto error;
- copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
- }
-
- for (i = 0; i < src->n_div; ++i) {
- int i1 = isl_basic_map_alloc_div(dst);
- if (i1 < 0)
- goto error;
- copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
- }
-
- free(dim_map);
- isl_basic_map_free(src);
-
- return dst;
-error:
- free(dim_map);
- isl_basic_map_free(src);
- isl_basic_map_free(dst);
- return NULL;
-}
-
struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
struct isl_basic_set *bset2, unsigned pos)
{
isl_seq_cpy(a, blk.data, b_len+a_len);
}
-struct isl_basic_set *isl_basic_set_swap_vars(
- struct isl_basic_set *bset, unsigned n)
+static __isl_give isl_basic_map *isl_basic_map_swap_vars(
+ __isl_take isl_basic_map *bmap, unsigned pos, unsigned n1, unsigned n2)
{
int i;
struct isl_blk blk;
- unsigned dim;
- unsigned nparam;
- if (!bset)
+ if (!bmap)
goto error;
- nparam = isl_basic_set_n_param(bset);
- dim = isl_basic_set_n_dim(bset);
- isl_assert(bset->ctx, n <= dim, goto error);
+ isl_assert(bmap->ctx,
+ pos + n1 + n2 <= 1 + isl_basic_map_total_dim(bmap), goto error);
- if (n == dim)
- return bset;
+ if (n1 == 0 || n2 == 0)
+ return bmap;
- bset = isl_basic_set_cow(bset);
- if (!bset)
+ bmap = isl_basic_map_cow(bmap);
+ if (!bmap)
return NULL;
- blk = isl_blk_alloc(bset->ctx, dim);
+ blk = isl_blk_alloc(bmap->ctx, n1 + n2);
if (isl_blk_is_error(blk))
goto error;
- for (i = 0; i < bset->n_eq; ++i)
+ for (i = 0; i < bmap->n_eq; ++i)
swap_vars(blk,
- bset->eq[i]+1+nparam, n, dim - n);
+ bmap->eq[i] + pos, n1, n2);
- for (i = 0; i < bset->n_ineq; ++i)
+ for (i = 0; i < bmap->n_ineq; ++i)
swap_vars(blk,
- bset->ineq[i]+1+nparam, n, dim - n);
+ bmap->ineq[i] + pos, n1, n2);
- for (i = 0; i < bset->n_div; ++i)
+ for (i = 0; i < bmap->n_div; ++i)
swap_vars(blk,
- bset->div[i]+1+1+nparam, n, dim - n);
+ bmap->div[i]+1 + pos, n1, n2);
- isl_blk_free(bset->ctx, blk);
+ isl_blk_free(bmap->ctx, blk);
- ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
- bset = isl_basic_set_gauss(bset, NULL);
- return isl_basic_set_finalize(bset);
+ ISL_F_CLR(bmap, ISL_BASIC_SET_NORMALIZED);
+ bmap = isl_basic_map_gauss(bmap, NULL);
+ return isl_basic_map_finalize(bmap);
+error:
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
+static __isl_give isl_basic_set *isl_basic_set_swap_vars(
+ __isl_take isl_basic_set *bset, unsigned n)
+{
+ unsigned dim;
+ unsigned nparam;
+
+ nparam = isl_basic_set_n_param(bset);
+ dim = isl_basic_set_n_dim(bset);
+ isl_assert(bset->ctx, n <= dim, goto error);
+
+ return isl_basic_map_swap_vars(bset, 1 + nparam, n, dim - n);
error:
isl_basic_set_free(bset);
return NULL;
}
-struct isl_set *isl_set_swap_vars(struct isl_set *set, unsigned n)
+static __isl_give isl_set *isl_set_swap_vars(__isl_take isl_set *set,
+ unsigned n)
{
int i;
set = isl_set_cow(set);
(struct isl_basic_map *)bset);
}
-struct isl_set *isl_set_remove_divs(struct isl_set *set)
+__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map)
{
int i;
- if (!set)
+ if (!map)
return NULL;
- if (set->n == 0)
- return set;
+ if (map->n == 0)
+ return map;
- set = isl_set_cow(set);
- if (!set)
+ map = isl_map_cow(map);
+ if (!map)
return NULL;
- for (i = 0; i < set->n; ++i) {
- set->p[i] = isl_basic_set_remove_divs(set->p[i]);
- if (!set->p[i])
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_remove_divs(map->p[i]);
+ if (!map->p[i])
goto error;
}
- return set;
+ return map;
error:
- isl_set_free(set);
+ isl_map_free(map);
return NULL;
}
+__isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set)
+{
+ return isl_map_remove_divs(set);
+}
+
struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap,
enum isl_dim_type type, unsigned first, unsigned n)
{
}
return bmap;
-error:
- isl_basic_map_free(bmap);
- return NULL;
}
__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
bmap->n_div, bmap->n_eq, bmap->n_ineq);
if (isl_basic_map_is_rational(bmap))
res = isl_basic_map_set_rational(res);
- res = add_constraints_dim_map(res, bmap, dim_map);
+ res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
return isl_basic_map_finalize(res);
}
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 = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
src_type, src_pos, 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);
+ res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
return res;
}
bmap1->n_div + bmap2->n_div + n,
bmap1->n_eq + bmap2->n_eq,
bmap1->n_ineq + bmap2->n_ineq);
- bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
- bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
bmap = add_divs(bmap, n);
bmap = isl_basic_map_simplify(bmap);
bmap = isl_basic_map_drop_redundant_divs(bmap);
isl_int_set_si(bmap->eq[j][1+pos+i], 1);
isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
}
- bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
- bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
bmap = add_divs(bmap, 2 * n_out);
bmap = isl_basic_map_simplify(bmap);
result = isl_basic_map_alloc_dim(isl_dim_copy(bmap->dim),
bmap->n_div + n_out,
bmap->n_eq, bmap->n_ineq + 2 * n_out);
- result = add_constraints_dim_map(result, bmap, dim_map);
+ result = isl_basic_map_add_constraints_dim_map(result, bmap, dim_map);
result = add_divs(result, n_out);
for (i = 0; i < n_out; ++i) {
int j;
bmap->extra += like->n_div;
if (bmap->extra) {
unsigned ltotal;
+ isl_int **div;
ltotal = total - bmap->extra + like->extra;
if (ltotal > total)
ltotal = total;
bmap->extra * (1 + 1 + total));
if (isl_blk_is_error(bmap->block2))
goto error;
- bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
- bmap->extra);
- if (!bmap->div)
+ div = isl_realloc_array(ctx, bmap->div, isl_int *, bmap->extra);
+ if (!div)
goto error;
+ bmap->div = div;
for (i = 0; i < bmap->extra; ++i)
bmap->div[i] = bmap->block2.data + i * (1 + 1 + total);
for (i = 0; i < like->n_div; ++i) {
if (!map)
goto error;
- if (isl_map_dim(map, isl_dim_in) == 0)
+ if (isl_map_dim(map, isl_dim_in) == 0 &&
+ !isl_dim_is_named_or_nested(map->dim, isl_dim_in))
return (isl_set *)map;
map = isl_map_cow(map);
if (i == bset->n_eq)
return isl_basic_set_lexmin(bset);
- eq = isl_mat_sub_alloc(bset->ctx, bset->eq, i, bset->n_eq - i,
+ eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, i, bset->n_eq - i,
0, 1 + nparam);
eq = isl_mat_cow(eq);
T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
goto error);
dim = isl_map_get_dim(map);
dim = isl_dim_domain(dim);
- result = isl_set_alloc_dim(dim, map->n, map->flags);
+ result = isl_set_alloc_dim(dim, map->n, 0);
if (!result)
goto error;
for (i = 0; i < map->n; ++i)
return NULL;
}
+/*
+ * returns [domain -> range] -> range - domain
+ */
+__isl_give isl_basic_map *isl_basic_map_deltas_map(
+ __isl_take isl_basic_map *bmap)
+{
+ int i, k;
+ isl_dim *dim;
+ isl_basic_map *domain;
+ isl_basic_set *bset;
+ int nparam, n;
+ unsigned total;
+
+ if (!isl_dim_tuple_match(bmap->dim, isl_dim_in, bmap->dim, isl_dim_out))
+ isl_die(bmap->ctx, isl_error_invalid,
+ "domain and range don't match", goto error);
+
+ nparam = isl_basic_map_dim(bmap, isl_dim_param);
+ n = isl_basic_map_dim(bmap, isl_dim_in);
+
+ dim = isl_dim_from_range(isl_dim_domain(isl_basic_map_get_dim(bmap)));
+ domain = isl_basic_map_universe(dim);
+
+ bmap = isl_basic_map_from_domain(isl_basic_map_wrap(bmap));
+ bmap = isl_basic_map_apply_range(bmap, domain);
+ bmap = isl_basic_map_extend_constraints(bmap, n, 0);
+
+ total = isl_basic_map_total_dim(bmap);
+
+ for (i = 0; i < n; ++i) {
+ k = isl_basic_map_alloc_equality(bmap);
+ if (k < 0)
+ goto error;
+ isl_seq_clr(bmap->eq[k], 1 + total);
+ isl_int_set_si(bmap->eq[k][1 + nparam + i], 1);
+ isl_int_set_si(bmap->eq[k][1 + nparam + n + i], -1);
+ isl_int_set_si(bmap->eq[k][1 + nparam + n + n + i], 1);
+ }
+
+ bmap = isl_basic_map_gauss(bmap, NULL);
+ return isl_basic_map_finalize(bmap);
+error:
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
+/*
+ * returns [domain -> range] -> range - domain
+ */
+__isl_give isl_map *isl_map_deltas_map(__isl_take isl_map *map)
+{
+ int i;
+ isl_dim *domain_dim;
+
+ if (!map)
+ return NULL;
+
+ if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
+ isl_die(map->ctx, isl_error_invalid,
+ "domain and range don't match", goto error);
+
+ map = isl_map_cow(map);
+ if (!map)
+ return NULL;
+
+ domain_dim = isl_dim_from_range(isl_dim_domain(isl_map_get_dim(map)));
+ map->dim = isl_dim_from_domain(isl_dim_wrap(map->dim));
+ map->dim = isl_dim_join(map->dim, domain_dim);
+ if (!map->dim)
+ goto error;
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_deltas_map(map->p[i]);
+ if (!map->p[i])
+ goto error;
+ }
+ ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+ return map;
+error:
+ isl_map_free(map);
+ return NULL;
+}
+
static struct isl_basic_map *basic_map_identity(struct isl_dim *dims)
{
struct isl_basic_map *bmap;
bmap1->n_div + bmap2->n_div,
bmap1->n_eq + bmap2->n_eq,
bmap1->n_ineq + bmap2->n_ineq);
- bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
- bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
bmap = isl_basic_map_simplify(bmap);
return isl_basic_map_finalize(bmap);
error:
bmap1->n_div + bmap2->n_div,
bmap1->n_eq + bmap2->n_eq,
bmap1->n_ineq + bmap2->n_ineq);
- bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
- bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
+ bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
bmap = isl_basic_map_simplify(bmap);
return isl_basic_map_finalize(bmap);
error:
return sv;
}
+int isl_map_is_injective(__isl_keep isl_map *map)
+{
+ int in;
+
+ map = isl_map_copy(map);
+ map = isl_map_reverse(map);
+ in = isl_map_is_single_valued(map);
+ isl_map_free(map);
+
+ return in;
+}
+
int isl_map_is_bijective(__isl_keep isl_map *map)
{
int sv;
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;
+ return isl_map_is_injective(map);
}
int isl_set_is_singleton(__isl_keep isl_set *set)
return map;
}
-/* Extend the given dim_map with mappings for the divs in bmap.
- */
-static __isl_give struct isl_dim_map *extend_dim_map(
- __isl_keep struct isl_dim_map *dim_map,
- __isl_keep isl_basic_map *bmap)
-{
- int i;
- struct isl_dim_map *res;
- int offset;
-
- offset = isl_basic_map_offset(bmap, isl_dim_div);
-
- res = isl_dim_map_alloc(bmap->ctx, dim_map->len - 1 + bmap->n_div);
- if (!res)
- return NULL;
-
- for (i = 0; i < dim_map->len; ++i)
- res->pos[i] = dim_map->pos[i];
- for (i = 0; i < bmap->n_div; ++i)
- res->pos[dim_map->len + i] = offset + i;
-
- return res;
-}
-
-/* Extract a dim_map from a reordering.
- * We essentially need to reverse the mapping, and add an offset
- * of 1 for the constant term.
- */
-__isl_give struct isl_dim_map *isl_dim_map_from_reordering(
- __isl_keep isl_reordering *exp)
-{
- int i;
- struct isl_dim_map *dim_map;
-
- if (!exp)
- return NULL;
-
- dim_map = isl_dim_map_alloc(exp->dim->ctx, isl_dim_total(exp->dim));
- if (!dim_map)
- return NULL;
-
- for (i = 0; i < exp->len; ++i)
- dim_map->pos[1 + exp->pos[i]] = 1 + i;
-
- return dim_map;
-}
-
/* Reorder the dimensions of "bmap" according to the given dim_map
* and set the dimension specification to "dim".
*/
res = isl_basic_map_alloc_dim(dim,
bmap->n_div, bmap->n_eq, bmap->n_ineq);
- res = add_constraints_dim_map(res, bmap, dim_map);
+ res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
res = isl_basic_map_finalize(res);
return res;
error:
for (i = 0; i < map->n; ++i) {
struct isl_dim_map *dim_map_i;
- dim_map_i = extend_dim_map(dim_map, map->p[i]);
+ dim_map_i = isl_dim_map_extend(dim_map, map->p[i]);
map->p[i] = isl_basic_map_realign(map->p[i],
isl_dim_copy(r->dim), dim_map_i);
isl_basic_map_from_constraint_matrices(dim, eq, ineq,
c1, c2, c3, c4, isl_dim_in);
}
+
+int isl_basic_map_can_zip(__isl_keep isl_basic_map *bmap)
+{
+ if (!bmap)
+ return -1;
+
+ return isl_dim_can_zip(bmap->dim);
+}
+
+int isl_map_can_zip(__isl_keep isl_map *map)
+{
+ if (!map)
+ return -1;
+
+ return isl_dim_can_zip(map->dim);
+}
+
+/* Given a basic map (A -> B) -> (C -> D), return the corresponding basic map
+ * (A -> C) -> (B -> D).
+ */
+__isl_give isl_basic_map *isl_basic_map_zip(__isl_take isl_basic_map *bmap)
+{
+ unsigned pos;
+ unsigned n1;
+ unsigned n2;
+
+ if (!bmap)
+ return NULL;
+
+ if (!isl_basic_map_can_zip(bmap))
+ isl_die(bmap->ctx, isl_error_invalid,
+ "basic map cannot be zipped", goto error);
+ pos = isl_basic_map_offset(bmap, isl_dim_in) +
+ isl_dim_size(bmap->dim->nested[0], isl_dim_in);
+ n1 = isl_dim_size(bmap->dim->nested[0], isl_dim_out);
+ n2 = isl_dim_size(bmap->dim->nested[1], isl_dim_in);
+ bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2);
+ if (!bmap)
+ return NULL;
+ bmap->dim = isl_dim_zip(bmap->dim);
+ if (!bmap->dim)
+ goto error;
+ return bmap;
+error:
+ isl_basic_map_free(bmap);
+ return NULL;
+}
+
+/* Given a map (A -> B) -> (C -> D), return the corresponding map
+ * (A -> C) -> (B -> D).
+ */
+__isl_give isl_map *isl_map_zip(__isl_take isl_map *map)
+{
+ int i;
+
+ if (!map)
+ return NULL;
+
+ if (!isl_map_can_zip(map))
+ isl_die(map->ctx, isl_error_invalid, "map cannot be zipped",
+ goto error);
+
+ map = isl_map_cow(map);
+ if (!map)
+ return NULL;
+
+ for (i = 0; i < map->n; ++i) {
+ map->p[i] = isl_basic_map_zip(map->p[i]);
+ if (!map->p[i])
+ goto error;
+ }
+
+ map->dim = isl_dim_zip(map->dim);
+ if (!map->dim)
+ goto error;
+
+ return map;
+error:
+ isl_map_free(map);
+ return NULL;
+}
projects / platform / upstream / isl.git / blobdiff