/*
* Copyright 2010-2011 INRIA Saclay
*
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
* Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
#include <isl_map_private.h>
#include <isl/ctx.h>
#include <isl/hash.h>
+#include <isl/aff.h>
#include <isl/map.h>
#include <isl/set.h>
#include <isl_space_private.h>
{
isl_union_map *umap;
+ dim = isl_space_params(dim);
if (!dim)
return NULL;
umap->ref = 1;
umap->dim = dim;
if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
- goto error;
+ return isl_union_map_free(umap);
return umap;
-error:
- isl_space_free(dim);
- isl_union_map_free(umap);
- return NULL;
}
__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
return isl_union_map_from_map((isl_map *)set);
}
+__isl_give isl_union_map *isl_union_map_from_basic_map(
+ __isl_take isl_basic_map *bmap)
+{
+ return isl_union_map_from_map(isl_map_from_basic_map(bmap));
+}
+
+__isl_give isl_union_set *isl_union_set_from_basic_set(
+ __isl_take isl_basic_set *bset)
+{
+ return isl_union_map_from_basic_map(bset);
+}
+
struct isl_union_map_foreach_data
{
int (*fn)(__isl_take isl_map *map, void *user);
return isl_map_from_union_map(uset);
}
+/* Extract the map in "umap" that lives in the given space (ignoring
+ * parameters).
+ */
__isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
- __isl_take isl_space *dim)
+ __isl_take isl_space *space)
{
uint32_t hash;
struct isl_hash_table_entry *entry;
- if (!umap || !dim)
+ space = isl_space_drop_dims(space, isl_dim_param,
+ 0, isl_space_dim(space, isl_dim_param));
+ space = isl_space_align_params(space, isl_union_map_get_space(umap));
+ if (!umap || !space)
goto error;
- hash = isl_space_get_hash(dim);
+ hash = isl_space_get_hash(space);
entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
- &has_dim, dim, 0);
+ &has_dim, space, 0);
if (!entry)
- return isl_map_empty(dim);
- isl_space_free(dim);
+ return isl_map_empty(space);
+ isl_space_free(space);
return isl_map_copy(entry->data);
error:
- isl_space_free(dim);
+ isl_space_free(space);
return NULL;
}
return gen_bin_op(umap, uset, &intersect_domain_entry);
}
+/* Remove the elements of data->umap2 from the domain of *entry
+ * and add the result to data->res.
+ */
+static int subtract_domain_entry(void **entry, void *user)
+{
+ struct isl_union_map_gen_bin_data *data = user;
+ uint32_t hash;
+ struct isl_hash_table_entry *entry2;
+ isl_space *dim;
+ isl_map *map = *entry;
+ int empty;
+
+ dim = isl_map_get_space(map);
+ dim = isl_space_domain(dim);
+ hash = isl_space_get_hash(dim);
+ entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
+ hash, &has_dim, dim, 0);
+ isl_space_free(dim);
+
+ map = isl_map_copy(map);
+
+ if (!entry2) {
+ data->res = isl_union_map_add_map(data->res, map);
+ return 0;
+ }
+
+ map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
+
+ empty = isl_map_is_empty(map);
+ if (empty < 0) {
+ isl_map_free(map);
+ return -1;
+ }
+ if (empty) {
+ isl_map_free(map);
+ return 0;
+ }
+
+ data->res = isl_union_map_add_map(data->res, map);
+
+ return 0;
+}
+
+/* Remove the elements of "uset" from the domain of "umap".
+ */
+__isl_give isl_union_map *isl_union_map_subtract_domain(
+ __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
+{
+ return gen_bin_op(umap, dom, &subtract_domain_entry);
+}
+
+/* Remove the elements of data->umap2 from the range of *entry
+ * and add the result to data->res.
+ */
+static int subtract_range_entry(void **entry, void *user)
+{
+ struct isl_union_map_gen_bin_data *data = user;
+ uint32_t hash;
+ struct isl_hash_table_entry *entry2;
+ isl_space *space;
+ isl_map *map = *entry;
+ int empty;
+
+ space = isl_map_get_space(map);
+ space = isl_space_range(space);
+ hash = isl_space_get_hash(space);
+ entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
+ hash, &has_dim, space, 0);
+ isl_space_free(space);
+
+ map = isl_map_copy(map);
+
+ if (!entry2) {
+ data->res = isl_union_map_add_map(data->res, map);
+ return 0;
+ }
+
+ map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
+
+ empty = isl_map_is_empty(map);
+ if (empty < 0) {
+ isl_map_free(map);
+ return -1;
+ }
+ if (empty) {
+ isl_map_free(map);
+ return 0;
+ }
+
+ data->res = isl_union_map_add_map(data->res, map);
+
+ return 0;
+}
+
+/* Remove the elements of "uset" from the range of "umap".
+ */
+__isl_give isl_union_map *isl_union_map_subtract_range(
+ __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
+{
+ return gen_bin_op(umap, dom, &subtract_range_entry);
+}
+
static int gist_domain_entry(void **entry, void *user)
{
struct isl_union_map_gen_bin_data *data = user;
return gen_bin_op(umap, uset, &gist_domain_entry);
}
+static int gist_range_entry(void **entry, void *user)
+{
+ struct isl_union_map_gen_bin_data *data = user;
+ uint32_t hash;
+ struct isl_hash_table_entry *entry2;
+ isl_space *space;
+ isl_map *map = *entry;
+ int empty;
+
+ space = isl_map_get_space(map);
+ space = isl_space_range(space);
+ hash = isl_space_get_hash(space);
+ entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
+ hash, &has_dim, space, 0);
+ isl_space_free(space);
+ if (!entry2)
+ return 0;
+
+ map = isl_map_copy(map);
+ map = isl_map_gist_range(map, isl_set_copy(entry2->data));
+
+ empty = isl_map_is_empty(map);
+ if (empty < 0) {
+ isl_map_free(map);
+ return -1;
+ }
+
+ data->res = isl_union_map_add_map(data->res, map);
+
+ return 0;
+}
+
+/* Compute the gist of "umap" with respect to the range "uset".
+ */
+__isl_give isl_union_map *isl_union_map_gist_range(
+ __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
+{
+ return gen_bin_op(umap, uset, &gist_range_entry);
+}
+
static int intersect_range_entry(void **entry, void *user)
{
struct isl_union_map_gen_bin_data *data = user;
return bin_op(uset1, uset2, &set_product_entry);
}
+static int domain_product_entry(void **entry, void *user)
+{
+ struct isl_union_map_bin_data *data = user;
+ isl_map *map2 = *entry;
+
+ if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
+ map2->dim, isl_dim_out))
+ return 0;
+
+ map2 = isl_map_domain_product(isl_map_copy(data->map),
+ isl_map_copy(map2));
+
+ data->res = isl_union_map_add_map(data->res, map2);
+
+ return 0;
+}
+
+/* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
+ */
+__isl_give isl_union_map *isl_union_map_domain_product(
+ __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
+{
+ return bin_op(umap1, umap2, &domain_product_entry);
+}
+
static int range_product_entry(void **entry, void *user)
{
struct isl_union_map_bin_data *data = user;
entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
hash, &has_dim, map->dim, 0);
if (!entry2) {
+ int empty = isl_map_is_empty(map);
+ if (empty < 0)
+ return -1;
+ if (empty)
+ return 0;
data->is_subset = 0;
return -1;
}
ctx = isl_union_map_get_ctx(umap);
+ n = isl_union_map_n_map(umap);
if (!umap)
goto error;
- n = isl_union_map_n_map(umap);
if (n <= 1) {
isl_union_map_free(umap);
return 1;
return cond_un_op(umap, &zip_entry);
}
+static int uncurry_entry(void **entry, void *user)
+{
+ isl_map *map = *entry;
+ isl_union_map **res = user;
+
+ if (!isl_map_can_uncurry(map))
+ return 0;
+
+ *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
+
+ return 0;
+}
+
+/* Given a union map, take the maps of the form A -> (B -> C) and
+ * return the union of the corresponding maps (A -> B) -> C.
+ */
+__isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
+{
+ return cond_un_op(umap, &uncurry_entry);
+}
+
+static int curry_entry(void **entry, void *user)
+{
+ isl_map *map = *entry;
+ isl_union_map **res = user;
+
+ if (!isl_map_can_curry(map))
+ return 0;
+
+ *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
+
+ return 0;
+}
+
+/* Given a union map, take the maps of the form (A -> B) -> C and
+ * return the union of the corresponding maps A -> (B -> C).
+ */
+__isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
+{
+ return cond_un_op(umap, &curry_entry);
+}
+
static int lift_entry(void **entry, void *user)
{
isl_set *set = *entry;
isl_union_set_free(res);
return NULL;
}
+
+/* Internal data structure for isl_union_map_preimage_domain_multi_aff.
+ *
+ * "ma" is the function under which the preimage should be taken.
+ * "space" is the space of "ma".
+ * "res" collects the results.
+ */
+struct isl_union_map_preimage_domain_data {
+ isl_space *space;
+ isl_multi_aff *ma;
+ isl_union_map *res;
+};
+
+/* Compute the preimage of the domain of *entry under the function
+ * represented by data->ma, provided the domain space of *entry
+ * match the target space of data->ma, and add the result to data->res.
+ */
+static int preimage_domain_entry(void **entry, void *user)
+{
+ int m;
+ isl_map *map = *entry;
+ struct isl_union_map_preimage_domain_data *data = user;
+ int empty;
+
+ m = isl_space_tuple_match(map->dim, isl_dim_in,
+ data->space, isl_dim_out);
+ if (m < 0)
+ return -1;
+ if (!m)
+ return 0;
+
+ map = isl_map_copy(map);
+ map = isl_map_preimage_domain_multi_aff(map,
+ isl_multi_aff_copy(data->ma));
+
+ empty = isl_map_is_empty(map);
+ if (empty < 0 || empty) {
+ isl_map_free(map);
+ return empty < 0 ? -1 : 0;
+ }
+
+ data->res = isl_union_map_add_map(data->res, map);
+
+ return 0;
+}
+
+/* Compute the preimage of the domain of "umap" under the function
+ * represented by "ma".
+ * In other words, plug in "ma" in the domain of "umap".
+ * The result contains maps that live in the same spaces as the maps of "umap"
+ * with domain space equal to the target space of "ma",
+ * except that the domain has been replaced by the domain space of "ma".
+ */
+__isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff(
+ __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)
+{
+ isl_ctx *ctx;
+ isl_space *space;
+ struct isl_union_map_preimage_domain_data data;
+
+ if (!umap || !ma)
+ goto error;
+
+ ctx = isl_union_map_get_ctx(umap);
+ space = isl_union_map_get_space(umap);
+ data.space = isl_multi_aff_get_space(ma);
+ data.ma = ma;
+ data.res = isl_union_map_alloc(space, umap->table.n);
+ if (isl_hash_table_foreach(ctx, &umap->table, &preimage_domain_entry,
+ &data) < 0)
+ data.res = isl_union_map_free(data.res);
+
+ isl_space_free(data.space);
+ isl_union_map_free(umap);
+ isl_multi_aff_free(ma);
+ return data.res;
+error:
+ isl_union_map_free(umap);
+ isl_multi_aff_free(ma);
+ return NULL;
+}