X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_union_map.c;h=0edaf55831dd1e4a062b6a62135ddbf4c9cd03d7;hb=7bc3560a92635b5dcf7eb9e7329992fc935a1ce2;hp=f12fd97056d5dbb3027c2b127ffac5cbb1cb5ac3;hpb=f53869239275299d045f11ddbf71c9f590e73979;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_union_map.c b/isl_union_map.c
index f12fd97..0edaf55 100644
--- a/isl_union_map.c
+++ b/isl_union_map.c
@@ -1,7 +1,7 @@
 /*
  * 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,
@@ -12,17 +12,37 @@
 #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>
 #include <isl_union_map_private.h>
 #include <isl/union_set.h>
 
+/* Is this union set a parameter domain?
+ */
+int isl_union_set_is_params(__isl_keep isl_union_set *uset)
+{
+	isl_set *set;
+	int params;
+
+	if (!uset)
+		return -1;
+	if (uset->table.n != 1)
+		return 0;
+
+	set = isl_set_from_union_set(isl_union_set_copy(uset));
+	params = isl_set_is_params(set);
+	isl_set_free(set);
+	return params;
+}
+
 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim,
 	int size)
 {
 	isl_union_map *umap;
 
+	dim = isl_space_params(dim);
 	if (!dim)
 		return NULL;
 
@@ -329,6 +349,18 @@ __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
 	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);
@@ -401,24 +433,30 @@ __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
 	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;
 }
 
@@ -556,6 +594,84 @@ __isl_give isl_union_set *isl_union_set_subtract(
 	return isl_union_map_subtract(uset1, uset2);
 }
 
+struct isl_union_map_gen_bin_set_data {
+	isl_set *set;
+	isl_union_map *res;
+};
+
+static int intersect_params_entry(void **entry, void *user)
+{
+	struct isl_union_map_gen_bin_set_data *data = user;
+	isl_map *map = *entry;
+	int empty;
+
+	map = isl_map_copy(map);
+	map = isl_map_intersect_params(map, isl_set_copy(data->set));
+
+	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;
+}
+
+static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
+	__isl_take isl_set *set, int (*fn)(void **, void *))
+{
+	struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
+
+	umap = isl_union_map_align_params(umap, isl_set_get_space(set));
+	set = isl_set_align_params(set, isl_union_map_get_space(umap));
+
+	if (!umap || !set)
+		goto error;
+
+	data.set = set;
+	data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
+				       umap->table.n);
+	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
+				   fn, &data) < 0)
+		goto error;
+
+	isl_union_map_free(umap);
+	isl_set_free(set);
+	return data.res;
+error:
+	isl_union_map_free(umap);
+	isl_set_free(set);
+	isl_union_map_free(data.res);
+	return NULL;
+}
+
+__isl_give isl_union_map *isl_union_map_intersect_params(
+	__isl_take isl_union_map *umap, __isl_take isl_set *set)
+{
+	return gen_bin_set_op(umap, set, &intersect_params_entry);
+}
+
+__isl_give isl_union_set *isl_union_set_intersect_params(
+	__isl_take isl_union_set *uset, __isl_take isl_set *set)
+{
+	return isl_union_map_intersect_params(uset, set);
+}
+
+static __isl_give isl_union_map *union_map_intersect_params(
+	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
+{
+	return isl_union_map_intersect_params(umap,
+						isl_set_from_union_set(uset));
+}
+
+static __isl_give isl_union_map *union_map_gist_params(
+	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
+{
+	return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
+}
+
 struct isl_union_map_match_bin_data {
 	isl_union_map *umap2;
 	isl_union_map *res;
@@ -629,10 +745,61 @@ __isl_give isl_union_map *isl_union_map_intersect(
 	return match_bin_op(umap1, umap2, &isl_map_intersect);
 }
 
+/* Compute the intersection of the two union_sets.
+ * As a special case, if exactly one of the two union_sets
+ * is a parameter domain, then intersect the parameter domain
+ * of the other one with this set.
+ */
 __isl_give isl_union_set *isl_union_set_intersect(
 	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
 {
+	int p1, p2;
+
+	p1 = isl_union_set_is_params(uset1);
+	p2 = isl_union_set_is_params(uset2);
+	if (p1 < 0 || p2 < 0)
+		goto error;
+	if (!p1 && p2)
+		return union_map_intersect_params(uset1, uset2);
+	if (p1 && !p2)
+		return union_map_intersect_params(uset2, uset1);
 	return isl_union_map_intersect(uset1, uset2);
+error:
+	isl_union_set_free(uset1);
+	isl_union_set_free(uset2);
+	return NULL;
+}
+
+static int gist_params_entry(void **entry, void *user)
+{
+	struct isl_union_map_gen_bin_set_data *data = user;
+	isl_map *map = *entry;
+	int empty;
+
+	map = isl_map_copy(map);
+	map = isl_map_gist_params(map, isl_set_copy(data->set));
+
+	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;
+}
+
+__isl_give isl_union_map *isl_union_map_gist_params(
+	__isl_take isl_union_map *umap, __isl_take isl_set *set)
+{
+	return gen_bin_set_op(umap, set, &gist_params_entry);
+}
+
+__isl_give isl_union_set *isl_union_set_gist_params(
+	__isl_take isl_union_set *uset, __isl_take isl_set *set)
+{
+	return isl_union_map_gist_params(uset, set);
 }
 
 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
@@ -644,6 +811,8 @@ __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
 	__isl_take isl_union_set *context)
 {
+	if (isl_union_set_is_params(context))
+		return union_map_gist_params(uset, context);
 	return isl_union_map_gist(uset, context);
 }
 
@@ -731,12 +900,204 @@ static int intersect_domain_entry(void **entry, void *user)
 	return 0;
 }
 
+/* Intersect the domain of "umap" with "uset".
+ * If "uset" is a parameters domain, then intersect the parameter
+ * domain of "umap" with this set.
+ */
 __isl_give isl_union_map *isl_union_map_intersect_domain(
 	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
 {
+	if (isl_union_set_is_params(uset))
+		return union_map_intersect_params(umap, uset);
 	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;
+	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);
+	if (!entry2)
+		return 0;
+
+	map = isl_map_copy(map);
+	map = isl_map_gist_domain(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 domain "uset".
+ * If "uset" is a parameters domain, then compute the gist
+ * with respect to this parameter domain.
+ */
+__isl_give isl_union_map *isl_union_map_gist_domain(
+	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
+{
+	if (isl_union_set_is_params(uset))
+		return union_map_gist_params(umap, uset);
+	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;
@@ -936,10 +1297,47 @@ __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
 	return bin_op(umap1, umap2, &product_entry);
 }
 
+static int set_product_entry(void **entry, void *user)
+{
+	struct isl_union_map_bin_data *data = user;
+	isl_set *set2 = *entry;
+
+	set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
+
+	data->res = isl_union_set_add_set(data->res, set2);
+
+	return 0;
+}
+
 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
 	__isl_take isl_union_set *uset2)
 {
-	return isl_union_map_product(uset1, uset2);
+	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)
@@ -1264,6 +1662,37 @@ __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
 	return cond_un_op(umap, &reverse_entry);
 }
 
+static int params_entry(void **entry, void *user)
+{
+	isl_map *map = *entry;
+	isl_union_set **res = user;
+
+	*res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
+
+	return 0;
+}
+
+/* Compute the parameter domain of the given union map.
+ */
+__isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
+{
+	int empty;
+
+	empty = isl_union_map_is_empty(umap);
+	if (empty < 0)
+		return isl_union_map_free(umap);
+	if (empty)
+		return isl_set_empty(isl_union_map_get_space(umap));
+	return isl_set_from_union_set(cond_un_op(umap, &params_entry));
+}
+
+/* Compute the parameter domain of the given union set.
+ */
+__isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
+{
+	return isl_union_map_params(uset);
+}
+
 static int domain_entry(void **entry, void *user)
 {
 	isl_map *map = *entry;
@@ -1430,6 +1859,11 @@ static int is_subset_entry(void **entry, void *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;
 	}
@@ -1847,10 +2281,10 @@ static int plain_injective_on_range(__isl_take isl_union_map *umap,
 
 	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;
@@ -1962,6 +2396,48 @@ __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
 	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;
@@ -2057,3 +2533,84 @@ error:
 	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;
+}