diff options
author | Sven Verdoolaege <skimo@kotnet.org> | 2011-08-21 10:38:41 +0200 |
---|---|---|
committer | Sven Verdoolaege <skimo@kotnet.org> | 2011-09-03 12:02:47 +0200 |
commit | d07eed3bf4d0e290118588ca80997a8035eaeb21 (patch) | |
tree | a91f34068f9540feeaf3fe687ca363968de9b5a2 /isl_space.c | |
parent | cd1939ed06617d00159e8e51b72a804b467e98b4 (diff) | |
download | isl-d07eed3bf4d0e290118588ca80997a8035eaeb21.tar.gz isl-d07eed3bf4d0e290118588ca80997a8035eaeb21.tar.bz2 isl-d07eed3bf4d0e290118588ca80997a8035eaeb21.zip |
rename isl_dim to isl_space
The old name was confusing because the name suggested that the object
represents a single dimension, while in fact it represents an entire space.
The documented isl_dim based names are for backward compatibility.
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
Diffstat (limited to 'isl_space.c')
-rw-r--r-- | isl_space.c | 1454 |
1 files changed, 1454 insertions, 0 deletions
diff --git a/isl_space.c b/isl_space.c new file mode 100644 index 00000000..a7d7d53a --- /dev/null +++ b/isl_space.c @@ -0,0 +1,1454 @@ +/* + * 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 <stdlib.h> +#include <isl_space_private.h> +#include <isl_id_private.h> +#include <isl_reordering.h> + +isl_ctx *isl_space_get_ctx(__isl_keep isl_space *dim) +{ + return dim ? dim->ctx : NULL; +} + +__isl_give isl_space *isl_space_alloc(isl_ctx *ctx, + unsigned nparam, unsigned n_in, unsigned n_out) +{ + isl_space *dim; + + dim = isl_alloc_type(ctx, struct isl_space); + if (!dim) + return NULL; + + dim->ctx = ctx; + isl_ctx_ref(ctx); + dim->ref = 1; + dim->nparam = nparam; + dim->n_in = n_in; + dim->n_out = n_out; + + dim->tuple_id[0] = NULL; + dim->tuple_id[1] = NULL; + + dim->nested[0] = NULL; + dim->nested[1] = NULL; + + dim->n_id = 0; + dim->ids = NULL; + + return dim; +} + +__isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx, + unsigned nparam, unsigned dim) +{ + return isl_space_alloc(ctx, nparam, 0, dim); +} + +static unsigned global_pos(__isl_keep isl_space *dim, + enum isl_dim_type type, unsigned pos) +{ + struct isl_ctx *ctx = dim->ctx; + + switch (type) { + case isl_dim_param: + isl_assert(ctx, pos < dim->nparam, + return isl_space_dim(dim, isl_dim_all)); + return pos; + case isl_dim_in: + isl_assert(ctx, pos < dim->n_in, + return isl_space_dim(dim, isl_dim_all)); + return pos + dim->nparam; + case isl_dim_out: + isl_assert(ctx, pos < dim->n_out, + return isl_space_dim(dim, isl_dim_all)); + return pos + dim->nparam + dim->n_in; + default: + isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all)); + } + return isl_space_dim(dim, isl_dim_all); +} + +/* Extend length of ids array to the total number of dimensions. + */ +static __isl_give isl_space *extend_ids(__isl_take isl_space *dim) +{ + isl_id **ids; + int i; + + if (isl_space_dim(dim, isl_dim_all) <= dim->n_id) + return dim; + + if (!dim->ids) { + dim->ids = isl_calloc_array(dim->ctx, + isl_id *, isl_space_dim(dim, isl_dim_all)); + if (!dim->ids) + goto error; + } else { + ids = isl_realloc_array(dim->ctx, dim->ids, + isl_id *, isl_space_dim(dim, isl_dim_all)); + if (!ids) + goto error; + dim->ids = ids; + for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); ++i) + dim->ids[i] = NULL; + } + + dim->n_id = isl_space_dim(dim, isl_dim_all); + + return dim; +error: + isl_space_free(dim); + return NULL; +} + +static __isl_give isl_space *set_id(__isl_take isl_space *dim, + enum isl_dim_type type, unsigned pos, __isl_take isl_id *id) +{ + dim = isl_space_cow(dim); + + if (!dim) + goto error; + + pos = global_pos(dim, type, pos); + if (pos == isl_space_dim(dim, isl_dim_all)) + goto error; + + if (pos >= dim->n_id) { + if (!id) + return dim; + dim = extend_ids(dim); + if (!dim) + goto error; + } + + dim->ids[pos] = id; + + return dim; +error: + isl_id_free(id); + isl_space_free(dim); + return NULL; +} + +static __isl_keep isl_id *get_id(__isl_keep isl_space *dim, + enum isl_dim_type type, unsigned pos) +{ + if (!dim) + return NULL; + + pos = global_pos(dim, type, pos); + if (pos == isl_space_dim(dim, isl_dim_all)) + return NULL; + if (pos >= dim->n_id) + return NULL; + return dim->ids[pos]; +} + +static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type) +{ + switch (type) { + case isl_dim_param: return 0; + case isl_dim_in: return dim->nparam; + case isl_dim_out: return dim->nparam + dim->n_in; + default: return 0; + } +} + +static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type) +{ + switch (type) { + case isl_dim_param: return dim->nparam; + 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; + } +} + +unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type) +{ + if (!dim) + return 0; + return n(dim, type); +} + +unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type) +{ + if (!dim) + return 0; + return offset(dim, type); +} + +static __isl_give isl_space *copy_ids(__isl_take isl_space *dst, + enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src, + enum isl_dim_type src_type) +{ + int i; + isl_id *id; + + if (!dst) + return NULL; + + for (i = 0; i < n(src, src_type); ++i) { + id = get_id(src, src_type, i); + if (!id) + continue; + dst = set_id(dst, dst_type, offset + i, isl_id_copy(id)); + if (!dst) + return NULL; + } + return dst; +} + +__isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim) +{ + isl_space *dup; + if (!dim) + return NULL; + dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out); + if (dim->tuple_id[0] && + !(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0]))) + goto error; + if (dim->tuple_id[1] && + !(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1]))) + goto error; + if (dim->nested[0] && !(dup->nested[0] = isl_space_copy(dim->nested[0]))) + goto error; + if (dim->nested[1] && !(dup->nested[1] = isl_space_copy(dim->nested[1]))) + goto error; + if (!dim->ids) + return dup; + dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param); + dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in); + dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out); + return dup; +error: + isl_space_free(dup); + return NULL; +} + +__isl_give isl_space *isl_space_cow(__isl_take isl_space *dim) +{ + if (!dim) + return NULL; + + if (dim->ref == 1) + return dim; + dim->ref--; + return isl_space_dup(dim); +} + +__isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim) +{ + if (!dim) + return NULL; + + dim->ref++; + return dim; +} + +void isl_space_free(__isl_take isl_space *dim) +{ + int i; + + if (!dim) + return; + + if (--dim->ref > 0) + return; + + isl_id_free(dim->tuple_id[0]); + isl_id_free(dim->tuple_id[1]); + + isl_space_free(dim->nested[0]); + isl_space_free(dim->nested[1]); + + for (i = 0; i < dim->n_id; ++i) + isl_id_free(dim->ids[i]); + free(dim->ids); + isl_ctx_deref(dim->ctx); + + free(dim); +} + +static int name_ok(isl_ctx *ctx, const char *s) +{ + char *p; + long dummy; + + dummy = strtol(s, &p, 0); + if (p != s) + isl_die(ctx, isl_error_invalid, "name looks like a number", + return 0); + + return 1; +} + +int isl_space_has_tuple_id(__isl_keep isl_space *dim, enum isl_dim_type type) +{ + if (!dim) + return -1; + if (type != isl_dim_in && type != isl_dim_out) + isl_die(dim->ctx, isl_error_invalid, + "only input, output and set tuples can have ids", + return -1); + return dim->tuple_id[type - isl_dim_in] != NULL; +} + +__isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *dim, + enum isl_dim_type type) +{ + if (!dim) + return NULL; + if (type != isl_dim_in && type != isl_dim_out) + isl_die(dim->ctx, isl_error_invalid, + "only input, output and set tuples can have ids", + return NULL); + if (!dim->tuple_id[type - isl_dim_in]) + isl_die(dim->ctx, isl_error_invalid, + "tuple has no id", return NULL); + return isl_id_copy(dim->tuple_id[type - isl_dim_in]); +} + +__isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *dim, + enum isl_dim_type type, __isl_take isl_id *id) +{ + dim = isl_space_cow(dim); + if (!dim || !id) + goto error; + if (type != isl_dim_in && type != isl_dim_out) + isl_die(dim->ctx, isl_error_invalid, + "only input, output and set tuples can have names", + goto error); + + isl_id_free(dim->tuple_id[type - isl_dim_in]); + dim->tuple_id[type - isl_dim_in] = id; + + return dim; +error: + isl_id_free(id); + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim, + enum isl_dim_type type) +{ + dim = isl_space_cow(dim); + if (!dim) + return NULL; + if (type != isl_dim_in && type != isl_dim_out) + isl_die(dim->ctx, isl_error_invalid, + "only input, output and set tuples can have names", + goto error); + + isl_id_free(dim->tuple_id[type - isl_dim_in]); + dim->tuple_id[type - isl_dim_in] = NULL; + + return dim; +error: + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *dim, + enum isl_dim_type type, unsigned pos, __isl_take isl_id *id) +{ + dim = isl_space_cow(dim); + if (!dim || !id) + goto error; + isl_id_free(get_id(dim, type, pos)); + return set_id(dim, type, pos, id); +error: + isl_id_free(id); + isl_space_free(dim); + return NULL; +} + +int isl_space_has_dim_id(__isl_keep isl_space *dim, + enum isl_dim_type type, unsigned pos) +{ + if (!dim) + return -1; + return get_id(dim, type, pos) != NULL; +} + +__isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *dim, + enum isl_dim_type type, unsigned pos) +{ + if (!dim) + return NULL; + if (!get_id(dim, type, pos)) + isl_die(dim->ctx, isl_error_invalid, + "dim has no id", return NULL); + return isl_id_copy(get_id(dim, type, pos)); +} + +__isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *dim, + enum isl_dim_type type, const char *s) +{ + isl_id *id; + + if (!dim) + return NULL; + + if (!s) + return isl_space_reset_tuple_id(dim, type); + + if (!name_ok(dim->ctx, s)) + goto error; + + id = isl_id_alloc(dim->ctx, s, NULL); + return isl_space_set_tuple_id(dim, type, id); +error: + isl_space_free(dim); + return NULL; +} + +const char *isl_space_get_tuple_name(__isl_keep isl_space *dim, + enum isl_dim_type type) +{ + isl_id *id; + if (!dim) + return NULL; + if (type != isl_dim_in && type != isl_dim_out) + return NULL; + id = dim->tuple_id[type - isl_dim_in]; + return id ? id->name : NULL; +} + +__isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *dim, + enum isl_dim_type type, unsigned pos, + const char *s) +{ + isl_id *id; + + if (!dim) + return NULL; + if (!name_ok(dim->ctx, s)) + goto error; + id = isl_id_alloc(dim->ctx, s, NULL); + return isl_space_set_dim_id(dim, type, pos, id); +error: + isl_space_free(dim); + return NULL; +} + +__isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *dim, + enum isl_dim_type type, unsigned pos) +{ + isl_id *id = get_id(dim, type, pos); + return id ? id->name : NULL; +} + +int isl_space_find_dim_by_id(__isl_keep isl_space *dim, enum isl_dim_type type, + __isl_keep isl_id *id) +{ + int i; + int offset; + int n; + + if (!dim || !id) + return -1; + + offset = isl_space_offset(dim, type); + n = isl_space_dim(dim, type); + for (i = 0; i < n && offset + i < dim->n_id; ++i) + if (dim->ids[offset + i] == id) + return i; + + return -1; +} + +static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim, + enum isl_dim_type type) +{ + if (!dim) + return NULL; + if (type == isl_dim_in) + return dim->tuple_id[0]; + if (type == isl_dim_out) + return dim->tuple_id[1]; + return NULL; +} + +static __isl_keep isl_space *nested(__isl_keep isl_space *dim, + enum isl_dim_type type) +{ + if (!dim) + return NULL; + if (type == isl_dim_in) + return dim->nested[0]; + if (type == isl_dim_out) + return dim->nested[1]; + return NULL; +} + +int isl_space_tuple_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type, + __isl_keep isl_space *dim2, enum isl_dim_type dim2_type) +{ + isl_id *id1, *id2; + isl_space *nested1, *nested2; + + if (!dim1 || !dim2) + return -1; + + if (n(dim1, dim1_type) != n(dim2, dim2_type)) + return 0; + id1 = tuple_id(dim1, dim1_type); + id2 = tuple_id(dim2, dim2_type); + if (!id1 ^ !id2) + return 0; + if (id1 && id1 != id2) + return 0; + nested1 = nested(dim1, dim1_type); + nested2 = nested(dim2, dim2_type); + if (!nested1 ^ !nested2) + return 0; + if (nested1 && !isl_space_is_equal(nested1, nested2)) + return 0; + return 1; +} + +static int match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type, + __isl_keep isl_space *dim2, enum isl_dim_type dim2_type) +{ + int i; + + if (!isl_space_tuple_match(dim1, dim1_type, dim2, dim2_type)) + return 0; + + if (!dim1->ids && !dim2->ids) + return 1; + + for (i = 0; i < n(dim1, dim1_type); ++i) { + if (get_id(dim1, dim1_type, i) != get_id(dim2, dim2_type, i)) + return 0; + } + return 1; +} + +int isl_space_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type, + __isl_keep isl_space *dim2, enum isl_dim_type dim2_type) +{ + return match(dim1, dim1_type, dim2, dim2_type); +} + +static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type, + unsigned first, unsigned n, __isl_keep isl_id **ids) +{ + int i; + + for (i = 0; i < n ; ++i) + ids[i] = get_id(dim, type, first + i); +} + +__isl_give isl_space *isl_space_extend(__isl_take isl_space *dim, + unsigned nparam, unsigned n_in, unsigned n_out) +{ + isl_id **ids = NULL; + + if (!dim) + return NULL; + if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out) + return dim; + + isl_assert(dim->ctx, dim->nparam <= nparam, goto error); + isl_assert(dim->ctx, dim->n_in <= n_in, goto error); + isl_assert(dim->ctx, dim->n_out <= n_out, goto error); + + dim = isl_space_cow(dim); + + if (dim->ids) { + ids = isl_calloc_array(dim->ctx, isl_id *, + nparam + n_in + n_out); + if (!ids) + goto error; + get_ids(dim, isl_dim_param, 0, dim->nparam, ids); + get_ids(dim, isl_dim_in, 0, dim->n_in, ids + nparam); + get_ids(dim, isl_dim_out, 0, dim->n_out, ids + nparam + n_in); + free(dim->ids); + dim->ids = ids; + dim->n_id = nparam + n_in + n_out; + } + dim->nparam = nparam; + dim->n_in = n_in; + dim->n_out = n_out; + + return dim; +error: + free(ids); + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_add_dims(__isl_take isl_space *dim, + enum isl_dim_type type, unsigned n) +{ + if (!dim) + return NULL; + dim = isl_space_reset(dim, type); + switch (type) { + case isl_dim_param: + dim = isl_space_extend(dim, + dim->nparam + n, dim->n_in, dim->n_out); + if (dim && dim->nested[0] && + !(dim->nested[0] = isl_space_add_dims(dim->nested[0], + isl_dim_param, n))) + goto error; + if (dim && dim->nested[1] && + !(dim->nested[1] = isl_space_add_dims(dim->nested[1], + isl_dim_param, n))) + goto error; + return dim; + case isl_dim_in: + return isl_space_extend(dim, + dim->nparam, dim->n_in + n, dim->n_out); + case isl_dim_out: + return isl_space_extend(dim, + dim->nparam, dim->n_in, dim->n_out + n); + default: + isl_die(dim->ctx, isl_error_invalid, + "cannot add dimensions of specified type", goto error); + } +error: + isl_space_free(dim); + return NULL; +} + +static int valid_dim_type(enum isl_dim_type type) +{ + switch (type) { + case isl_dim_param: + case isl_dim_in: + case isl_dim_out: + return 1; + default: + return 0; + } +} + +__isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *dim, + enum isl_dim_type type, unsigned pos, unsigned n) +{ + isl_id **ids = NULL; + + if (!dim) + return NULL; + if (n == 0) + return isl_space_reset(dim, type); + + if (!valid_dim_type(type)) + isl_die(dim->ctx, isl_error_invalid, + "cannot insert dimensions of specified type", + goto error); + + isl_assert(dim->ctx, pos <= isl_space_dim(dim, type), goto error); + + dim = isl_space_cow(dim); + if (!dim) + return NULL; + + if (dim->ids) { + enum isl_dim_type t; + int off; + int s[3]; + int *size = s - isl_dim_param; + ids = isl_calloc_array(dim->ctx, isl_id *, + dim->nparam + dim->n_in + dim->n_out + n); + if (!ids) + goto error; + off = 0; + size[isl_dim_param] = dim->nparam; + size[isl_dim_in] = dim->n_in; + size[isl_dim_out] = dim->n_out; + for (t = isl_dim_param; t <= isl_dim_out; ++t) { + if (t != type) { + get_ids(dim, t, 0, size[t], ids + off); + off += size[t]; + } else { + get_ids(dim, t, 0, pos, ids + off); + off += pos + n; + get_ids(dim, t, pos, size[t] - pos, ids + off); + off += size[t] - pos; + } + } + free(dim->ids); + dim->ids = ids; + dim->n_id = dim->nparam + dim->n_in + dim->n_out + n; + } + switch (type) { + case isl_dim_param: dim->nparam += n; break; + case isl_dim_in: dim->n_in += n; break; + case isl_dim_out: dim->n_out += n; break; + default: ; + } + dim = isl_space_reset(dim, type); + + return dim; +error: + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_move_dims(__isl_take isl_space *dim, + enum isl_dim_type dst_type, unsigned dst_pos, + enum isl_dim_type src_type, unsigned src_pos, unsigned n) +{ + int i; + + if (!dim) + return NULL; + if (n == 0) + return dim; + + isl_assert(dim->ctx, src_pos + n <= isl_space_dim(dim, src_type), + goto error); + + if (dst_type == src_type && dst_pos == src_pos) + return dim; + + isl_assert(dim->ctx, dst_type != src_type, goto error); + + dim = isl_space_reset(dim, src_type); + dim = isl_space_reset(dim, dst_type); + + dim = isl_space_cow(dim); + if (!dim) + return NULL; + + if (dim->ids) { + isl_id **ids; + enum isl_dim_type t; + int off; + int s[3]; + int *size = s - isl_dim_param; + ids = isl_calloc_array(dim->ctx, isl_id *, + dim->nparam + dim->n_in + dim->n_out); + if (!ids) + goto error; + off = 0; + size[isl_dim_param] = dim->nparam; + size[isl_dim_in] = dim->n_in; + size[isl_dim_out] = dim->n_out; + for (t = isl_dim_param; t <= isl_dim_out; ++t) { + if (t == dst_type) { + get_ids(dim, t, 0, dst_pos, ids + off); + off += dst_pos; + get_ids(dim, src_type, src_pos, n, ids + off); + off += n; + get_ids(dim, t, dst_pos, size[t] - dst_pos, + ids + off); + off += size[t] - dst_pos; + } else if (t == src_type) { + get_ids(dim, t, 0, src_pos, ids + off); + off += src_pos; + get_ids(dim, t, src_pos + n, + size[t] - src_pos - n, ids + off); + off += size[t] - src_pos - n; + } else { + get_ids(dim, t, 0, size[t], ids + off); + off += size[t]; + } + } + free(dim->ids); + dim->ids = ids; + dim->n_id = dim->nparam + dim->n_in + dim->n_out; + } + + switch (dst_type) { + case isl_dim_param: dim->nparam += n; break; + case isl_dim_in: dim->n_in += n; break; + case isl_dim_out: dim->n_out += n; break; + default: ; + } + + switch (src_type) { + case isl_dim_param: dim->nparam -= n; break; + case isl_dim_in: dim->n_in -= n; break; + case isl_dim_out: dim->n_out -= n; break; + default: ; + } + + if (dst_type != isl_dim_param && src_type != isl_dim_param) + return dim; + + for (i = 0; i < 2; ++i) { + if (!dim->nested[i]) + continue; + dim->nested[i] = isl_space_replace(dim->nested[i], + isl_dim_param, dim); + if (!dim->nested[i]) + goto error; + } + + return dim; +error: + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_join(__isl_take isl_space *left, + __isl_take isl_space *right) +{ + isl_space *dim; + + if (!left || !right) + goto error; + + isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param), + goto error); + isl_assert(left->ctx, + isl_space_tuple_match(left, isl_dim_out, right, isl_dim_in), + goto error); + + dim = isl_space_alloc(left->ctx, left->nparam, left->n_in, right->n_out); + if (!dim) + goto error; + + dim = copy_ids(dim, isl_dim_param, 0, left, isl_dim_param); + dim = copy_ids(dim, isl_dim_in, 0, left, isl_dim_in); + dim = copy_ids(dim, isl_dim_out, 0, right, isl_dim_out); + + if (dim && left->tuple_id[0] && + !(dim->tuple_id[0] = isl_id_copy(left->tuple_id[0]))) + goto error; + if (dim && right->tuple_id[1] && + !(dim->tuple_id[1] = isl_id_copy(right->tuple_id[1]))) + goto error; + if (dim && left->nested[0] && + !(dim->nested[0] = isl_space_copy(left->nested[0]))) + goto error; + if (dim && right->nested[1] && + !(dim->nested[1] = isl_space_copy(right->nested[1]))) + goto error; + + isl_space_free(left); + isl_space_free(right); + + return dim; +error: + isl_space_free(left); + isl_space_free(right); + return NULL; +} + +__isl_give isl_space *isl_space_product(__isl_take isl_space *left, + __isl_take isl_space *right) +{ + isl_space *dom1, *dom2, *nest1, *nest2; + + if (!left || !right) + goto error; + + isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param), + goto error); + + dom1 = isl_space_domain(isl_space_copy(left)); + dom2 = isl_space_domain(isl_space_copy(right)); + nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2)); + + dom1 = isl_space_range(left); + dom2 = isl_space_range(right); + nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2)); + + return isl_space_join(isl_space_reverse(nest1), nest2); +error: + isl_space_free(left); + isl_space_free(right); + return NULL; +} + +__isl_give isl_space *isl_space_range_product(__isl_take isl_space *left, + __isl_take isl_space *right) +{ + isl_space *dom, *ran1, *ran2, *nest; + + if (!left || !right) + goto error; + + isl_assert(left->ctx, match(left, isl_dim_param, right, isl_dim_param), + goto error); + if (!isl_space_tuple_match(left, isl_dim_in, right, isl_dim_in)) + isl_die(left->ctx, isl_error_invalid, + "domains need to match", goto error); + + dom = isl_space_domain(isl_space_copy(left)); + + ran1 = isl_space_range(left); + ran2 = isl_space_range(right); + nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2)); + + return isl_space_join(isl_space_reverse(dom), nest); +error: + isl_space_free(left); + isl_space_free(right); + return NULL; +} + +__isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *dim) +{ + isl_id **ids = NULL; + + if (!dim) + return NULL; + isl_assert(dim->ctx, dim->n_in == 0, goto error); + if (dim->n_out == 0 && !isl_space_is_named_or_nested(dim, isl_dim_out)) + return dim; + dim = isl_space_cow(dim); + if (!dim) + return NULL; + if (dim->ids) { + ids = isl_calloc_array(dim->ctx, isl_id *, + dim->nparam + dim->n_out + dim->n_out); + if (!ids) + goto error; + get_ids(dim, isl_dim_param, 0, dim->nparam, ids); + get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->nparam); + } + dim->n_in = dim->n_out; + if (ids) { + free(dim->ids); + dim->ids = ids; + dim->n_id = dim->nparam + dim->n_out + dim->n_out; + dim = copy_ids(dim, isl_dim_out, 0, dim, isl_dim_in); + } + isl_id_free(dim->tuple_id[0]); + dim->tuple_id[0] = isl_id_copy(dim->tuple_id[1]); + isl_space_free(dim->nested[0]); + dim->nested[0] = isl_space_copy(dim->nested[1]); + return dim; +error: + isl_space_free(dim); + return NULL; +} + +static __isl_give isl_space *set_ids(__isl_take isl_space *dim, + enum isl_dim_type type, + unsigned first, unsigned n, __isl_take isl_id **ids) +{ + int i; + + for (i = 0; i < n ; ++i) + dim = set_id(dim, type, first + i, ids[i]); + + return dim; +} + +__isl_give isl_space *isl_space_reverse(__isl_take isl_space *dim) +{ + unsigned t; + isl_space *nested; + isl_id **ids = NULL; + isl_id *id; + + if (!dim) + return NULL; + if (match(dim, isl_dim_in, dim, isl_dim_out)) + return dim; + + dim = isl_space_cow(dim); + if (!dim) + return NULL; + + id = dim->tuple_id[0]; + dim->tuple_id[0] = dim->tuple_id[1]; + dim->tuple_id[1] = id; + + nested = dim->nested[0]; + dim->nested[0] = dim->nested[1]; + dim->nested[1] = nested; + + if (dim->ids) { + ids = isl_alloc_array(dim->ctx, isl_id *, + dim->n_in + dim->n_out); + if (!ids) + goto error; + get_ids(dim, isl_dim_in, 0, dim->n_in, ids); + get_ids(dim, isl_dim_out, 0, dim->n_out, ids + dim->n_in); + } + + t = dim->n_in; + dim->n_in = dim->n_out; + dim->n_out = t; + + if (dim->ids) { + dim = set_ids(dim, isl_dim_out, 0, dim->n_out, ids); + dim = set_ids(dim, isl_dim_in, 0, dim->n_in, ids + dim->n_out); + free(ids); + } + + return dim; +error: + free(ids); + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *dim, + enum isl_dim_type type, unsigned first, unsigned num) +{ + int i; + + if (!dim) + return NULL; + + if (num == 0) + return isl_space_reset(dim, type); + + if (!valid_dim_type(type)) + isl_die(dim->ctx, isl_error_invalid, + "cannot drop dimensions of specified type", goto error); + + isl_assert(dim->ctx, first + num <= n(dim, type), goto error); + dim = isl_space_cow(dim); + if (!dim) + goto error; + if (dim->ids) { + dim = extend_ids(dim); + if (!dim) + goto error; + for (i = 0; i < num; ++i) + isl_id_free(get_id(dim, type, first + i)); + for (i = first+num; i < n(dim, type); ++i) + set_id(dim, type, i - num, get_id(dim, type, i)); + switch (type) { + case isl_dim_param: + get_ids(dim, isl_dim_in, 0, dim->n_in, + dim->ids + offset(dim, isl_dim_in) - num); + case isl_dim_in: + get_ids(dim, isl_dim_out, 0, dim->n_out, + dim->ids + offset(dim, isl_dim_out) - num); + default: + ; + } + dim->n_id -= num; + } + switch (type) { + case isl_dim_param: dim->nparam -= num; break; + case isl_dim_in: dim->n_in -= num; break; + case isl_dim_out: dim->n_out -= num; break; + default: ; + } + dim = isl_space_reset(dim, type); + if (type == isl_dim_param) { + if (dim && dim->nested[0] && + !(dim->nested[0] = isl_space_drop_dims(dim->nested[0], + isl_dim_param, first, num))) + goto error; + if (dim && dim->nested[1] && + !(dim->nested[1] = isl_space_drop_dims(dim->nested[1], + isl_dim_param, first, num))) + goto error; + } + return dim; +error: + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *dim, + unsigned first, unsigned n) +{ + if (!dim) + return NULL; + return isl_space_drop_dims(dim, isl_dim_in, first, n); +} + +__isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *dim, + unsigned first, unsigned n) +{ + if (!dim) + return NULL; + return isl_space_drop_dims(dim, isl_dim_out, first, n); +} + +__isl_give isl_space *isl_space_domain(__isl_take isl_space *dim) +{ + if (!dim) + return NULL; + dim = isl_space_drop_outputs(dim, 0, dim->n_out); + return isl_space_reverse(dim); +} + +__isl_give isl_space *isl_space_from_domain(__isl_take isl_space *dim) +{ + return isl_space_reverse(dim); +} + +__isl_give isl_space *isl_space_range(__isl_take isl_space *dim) +{ + if (!dim) + return NULL; + return isl_space_drop_inputs(dim, 0, dim->n_in); +} + +__isl_give isl_space *isl_space_from_range(__isl_take isl_space *dim) +{ + return dim; +} + +__isl_give isl_space *isl_space_as_set_space(__isl_take isl_space *dim) +{ + dim = isl_space_cow(dim); + if (!dim) + return NULL; + + dim->n_out += dim->n_in; + dim->n_in = 0; + dim = isl_space_reset(dim, isl_dim_in); + dim = isl_space_reset(dim, isl_dim_out); + + return dim; +} + +__isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim, + unsigned n_div) +{ + int i; + + if (!dim) + return NULL; + if (n_div == 0 && + dim->nparam == 0 && dim->n_in == 0 && dim->n_id == 0) + return isl_space_reset(isl_space_reset(dim, isl_dim_in), isl_dim_out); + dim = isl_space_cow(dim); + if (!dim) + return NULL; + dim->n_out += dim->nparam + dim->n_in + n_div; + dim->nparam = 0; + dim->n_in = 0; + + for (i = 0; i < dim->n_id; ++i) + isl_id_free(get_id(dim, isl_dim_out, i)); + dim->n_id = 0; + dim = isl_space_reset(dim, isl_dim_in); + dim = isl_space_reset(dim, isl_dim_out); + + return dim; +} + +int isl_space_is_equal(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2) +{ + if (!dim1 || !dim2) + return -1; + return match(dim1, isl_dim_param, dim2, isl_dim_param) && + isl_space_tuple_match(dim1, isl_dim_in, dim2, isl_dim_in) && + isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_out); +} + +int isl_space_compatible(__isl_keep isl_space *dim1, + __isl_keep isl_space *dim2) +{ + return dim1->nparam == dim2->nparam && + dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out; +} + +static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_space *dim) +{ + int i; + isl_id *id; + + if (!dim) + return hash; + + hash = isl_hash_builtin(hash, dim->nparam); + hash = isl_hash_builtin(hash, dim->n_in); + hash = isl_hash_builtin(hash, dim->n_out); + + for (i = 0; i < dim->nparam; ++i) { + id = get_id(dim, isl_dim_param, i); + hash = isl_hash_id(hash, id); + } + + id = tuple_id(dim, isl_dim_in); + hash = isl_hash_id(hash, id); + id = tuple_id(dim, isl_dim_out); + hash = isl_hash_id(hash, id); + + hash = isl_hash_dim(hash, dim->nested[0]); + hash = isl_hash_dim(hash, dim->nested[1]); + + return hash; +} + +uint32_t isl_space_get_hash(__isl_keep isl_space *dim) +{ + uint32_t hash; + + if (!dim) + return 0; + + hash = isl_hash_init(); + hash = isl_hash_dim(hash, dim); + + return hash; +} + +int isl_space_is_wrapping(__isl_keep isl_space *dim) +{ + if (!dim) + return -1; + + if (dim->n_in != 0 || dim->tuple_id[0] || dim->nested[0]) + return 0; + + return dim->nested[1] != NULL; +} + +__isl_give isl_space *isl_space_wrap(__isl_take isl_space *dim) +{ + isl_space *wrap; + + if (!dim) + return NULL; + + wrap = isl_space_alloc(dim->ctx, dim->nparam, 0, dim->n_in + dim->n_out); + + wrap = copy_ids(wrap, isl_dim_param, 0, dim, isl_dim_param); + wrap = copy_ids(wrap, isl_dim_set, 0, dim, isl_dim_in); + wrap = copy_ids(wrap, isl_dim_set, dim->n_in, dim, isl_dim_out); + + if (!wrap) + goto error; + + wrap->nested[1] = dim; + + return wrap; +error: + isl_space_free(dim); + return NULL; +} + +__isl_give isl_space *isl_space_unwrap(__isl_take isl_space *dim) +{ + isl_space *unwrap; + + if (!dim) + return NULL; + + if (!isl_space_is_wrapping(dim)) + isl_die(dim->ctx, isl_error_invalid, "not a wrapping dim", + goto error); + + unwrap = isl_space_copy(dim->nested[1]); + isl_space_free(dim); + + return unwrap; +error: + isl_space_free(dim); + return NULL; +} + +int isl_space_is_named_or_nested(__isl_keep isl_space *dim, enum isl_dim_type type) +{ + if (type != isl_dim_in && type != isl_dim_out) + return 0; + if (!dim) + return -1; + if (dim->tuple_id[type - isl_dim_in]) + return 1; + if (dim->nested[type - isl_dim_in]) + return 1; + return 0; +} + +int isl_space_may_be_set(__isl_keep isl_space *dim) +{ + if (!dim) + return -1; + if (isl_space_dim(dim, isl_dim_in) != 0) + return 0; + if (isl_space_is_named_or_nested(dim, isl_dim_in)) + return 0; + return 1; +} + +__isl_give isl_space *isl_space_reset(__isl_take isl_space *dim, + enum isl_dim_type type) +{ + if (!isl_space_is_named_or_nested(dim, type)) + return dim; + + dim = isl_space_cow(dim); + if (!dim) + return NULL; + + isl_id_free(dim->tuple_id[type - isl_dim_in]); + dim->tuple_id[type - isl_dim_in] = NULL; + isl_space_free(dim->nested[type - isl_dim_in]); + dim->nested[type - isl_dim_in] = NULL; + + return dim; +} + +__isl_give isl_space *isl_space_flatten(__isl_take isl_space *dim) +{ + if (!dim) + return NULL; + if (!dim->nested[0] && !dim->nested[1]) + return dim; + + if (dim->nested[0]) + dim = isl_space_reset(dim, isl_dim_in); + if (dim && dim->nested[1]) + dim = isl_space_reset(dim, isl_dim_out); + + return dim; +} + +__isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *dim) +{ + if (!dim) + return NULL; + if (!dim->nested[1]) + return dim; + + return isl_space_reset(dim, isl_dim_out); +} + +/* Replace the dimensions of the given type of dst by those of src. + */ +__isl_give isl_space *isl_space_replace(__isl_take isl_space *dst, + enum isl_dim_type type, __isl_keep isl_space *src) +{ + dst = isl_space_cow(dst); + + if (!dst || !src) + goto error; + + dst = isl_space_drop_dims(dst, type, 0, isl_space_dim(dst, type)); + dst = isl_space_add_dims(dst, type, isl_space_dim(src, type)); + dst = copy_ids(dst, type, 0, src, type); + + if (dst && type == isl_dim_param) { + int i; + for (i = 0; i <= 1; ++i) { + if (!dst->nested[i]) + continue; + dst->nested[i] = isl_space_replace(dst->nested[i], + type, src); + if (!dst->nested[i]) + goto error; + } + } + + return dst; +error: + isl_space_free(dst); + return NULL; +} + +/* Given a dimension specification "dim" of a set, create a dimension + * specification for the lift of the set. In particular, the result + * is of the form [dim -> local[..]], with n_local variables in the + * range of the wrapped map. + */ +__isl_give isl_space *isl_space_lift(__isl_take isl_space *dim, unsigned n_local) +{ + isl_space *local_dim; + + if (!dim) + return NULL; + + local_dim = isl_space_dup(dim); + local_dim = isl_space_drop_dims(local_dim, isl_dim_set, 0, dim->n_out); + local_dim = isl_space_add_dims(local_dim, isl_dim_set, n_local); + local_dim = isl_space_set_tuple_name(local_dim, isl_dim_set, "local"); + dim = isl_space_join(isl_space_from_domain(dim), + isl_space_from_range(local_dim)); + dim = isl_space_wrap(dim); + dim = isl_space_set_tuple_name(dim, isl_dim_set, "lifted"); + + return dim; +} + +int isl_space_can_zip(__isl_keep isl_space *dim) +{ + if (!dim) + return -1; + + return dim->nested[0] && dim->nested[1]; +} + +__isl_give isl_space *isl_space_zip(__isl_take isl_space *dim) +{ + isl_space *dom, *ran; + isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran; + + if (!isl_space_can_zip(dim)) + isl_die(dim->ctx, isl_error_invalid, "dim cannot be zipped", + goto error); + + if (!dim) + return 0; + dom = isl_space_unwrap(isl_space_domain(isl_space_copy(dim))); + ran = isl_space_unwrap(isl_space_range(dim)); + dom_dom = isl_space_domain(isl_space_copy(dom)); + dom_ran = isl_space_range(dom); + ran_dom = isl_space_domain(isl_space_copy(ran)); + ran_ran = isl_space_range(ran); + dom = isl_space_join(isl_space_from_domain(dom_dom), + isl_space_from_range(ran_dom)); + ran = isl_space_join(isl_space_from_domain(dom_ran), + isl_space_from_range(ran_ran)); + return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)), + isl_space_from_range(isl_space_wrap(ran))); +error: + isl_space_free(dim); + return NULL; +} + +int isl_space_has_named_params(__isl_keep isl_space *dim) +{ + int i; + unsigned off; + + if (!dim) + return -1; + if (dim->nparam == 0) + return 1; + off = isl_space_offset(dim, isl_dim_param); + if (off + dim->nparam > dim->n_id) + return 0; + for (i = 0; i < dim->nparam; ++i) + if (!dim->ids[off + i]) + return 0; + return 1; +} + +/* Align the initial parameters of dim1 to match the order in dim2. + */ +__isl_give isl_space *isl_space_align_params(__isl_take isl_space *dim1, + __isl_take isl_space *dim2) +{ + isl_reordering *exp; + + if (!isl_space_has_named_params(dim1) || !isl_space_has_named_params(dim2)) + isl_die(isl_space_get_ctx(dim1), isl_error_invalid, + "parameter alignment requires named parameters", + goto error); + + exp = isl_parameter_alignment_reordering(dim1, dim2); + isl_space_free(dim1); + isl_space_free(dim2); + if (!exp) + return NULL; + dim1 = isl_space_copy(exp->dim); + isl_reordering_free(exp); + return dim1; +error: + isl_space_free(dim1); + isl_space_free(dim2); + return NULL; +} |