X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_union_map.c;h=1528ebd858ad2f409e394641619fa6300492f63a;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=abe03fcc790768d200e20cf08d9e2e5188abc279;hpb=7f17911bba7c398741edde2ce03c64b6555afbec;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_union_map.c b/isl_union_map.c
index abe03fc..1528ebd 100644
--- a/isl_union_map.c
+++ b/isl_union_map.c
@@ -1,23 +1,42 @@
 /*
  * 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,
  * 91893 Orsay, France 
  */
 
+#define ISL_DIM_H
 #include <isl_map_private.h>
 #include <isl/ctx.h>
 #include <isl/hash.h>
 #include <isl/map.h>
 #include <isl/set.h>
-#include <isl_dim_private.h>
+#include <isl_space_private.h>
 #include <isl_union_map_private.h>
 #include <isl/union_set.h>
 
-static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_dim *dim,
+/* 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;
@@ -36,17 +55,17 @@ static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_dim *dim,
 
 	return umap;
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	isl_union_map_free(umap);
 	return NULL;
 }
 
-__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_dim *dim)
+__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
 {
 	return isl_union_map_alloc(dim, 16);
 }
 
-__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_dim *dim)
+__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
 {
 	return isl_union_map_empty(dim);
 }
@@ -61,16 +80,16 @@ isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
 	return uset ? uset->dim->ctx : NULL;
 }
 
-__isl_give isl_dim *isl_union_map_get_dim(__isl_keep isl_union_map *umap)
+__isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
 {
 	if (!umap)
 		return NULL;
-	return isl_dim_copy(umap->dim);
+	return isl_space_copy(umap->dim);
 }
 
-__isl_give isl_dim *isl_union_set_get_dim(__isl_keep isl_union_set *uset)
+__isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
 {
-	return isl_union_map_get_dim(uset);
+	return isl_union_map_get_space(uset);
 }
 
 static int free_umap_entry(void **entry, void *user)
@@ -96,7 +115,7 @@ __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
 	if (!umap)
 		return NULL;
 
-	dup = isl_union_map_empty(isl_dim_copy(umap->dim));
+	dup = isl_union_map_empty(isl_space_copy(umap->dim));
 	if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
 		goto error;
 	return dup;
@@ -127,8 +146,8 @@ static int align_entry(void **entry, void *user)
 	isl_reordering *exp;
 	struct isl_union_align *data = user;
 
-	exp = isl_reordering_extend_dim(isl_reordering_copy(data->exp),
-				    isl_map_get_dim(map));
+	exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
+				    isl_map_get_space(map));
 
 	data->res = isl_union_map_add_map(data->res,
 					isl_map_realign(isl_map_copy(map), exp));
@@ -142,23 +161,24 @@ static int align_entry(void **entry, void *user)
  * umap that do not appear in model.
  */
 __isl_give isl_union_map *isl_union_map_align_params(
-	__isl_take isl_union_map *umap, __isl_take isl_dim *model)
+	__isl_take isl_union_map *umap, __isl_take isl_space *model)
 {
 	struct isl_union_align data = { NULL, NULL };
 
 	if (!umap || !model)
 		goto error;
 
-	if (isl_dim_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
-		isl_dim_free(model);
+	if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
+		isl_space_free(model);
 		return umap;
 	}
 
+	model = isl_space_params(model);
 	data.exp = isl_parameter_alignment_reordering(umap->dim, model);
 	if (!data.exp)
 		goto error;
 
-	data.res = isl_union_map_alloc(isl_dim_copy(data.exp->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
 					umap->table.n);
 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 					&align_entry, &data) < 0)
@@ -166,18 +186,18 @@ __isl_give isl_union_map *isl_union_map_align_params(
 
 	isl_reordering_free(data.exp);
 	isl_union_map_free(umap);
-	isl_dim_free(model);
+	isl_space_free(model);
 	return data.res;
 error:
 	isl_reordering_free(data.exp);
 	isl_union_map_free(umap);
 	isl_union_map_free(data.res);
-	isl_dim_free(model);
+	isl_space_free(model);
 	return NULL;
 }
 
 __isl_give isl_union_set *isl_union_set_align_params(
-	__isl_take isl_union_set *uset, __isl_take isl_dim *model)
+	__isl_take isl_union_set *uset, __isl_take isl_space *model)
 {
 	return isl_union_map_align_params(uset, model);
 }
@@ -185,8 +205,8 @@ __isl_give isl_union_set *isl_union_set_align_params(
 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
 	__isl_take isl_union_map *umap2)
 {
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	umap1 = isl_union_map_cow(umap1);
 
@@ -225,32 +245,33 @@ __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
 	return isl_union_map_copy(uset);
 }
 
-void isl_union_map_free(__isl_take isl_union_map *umap)
+void *isl_union_map_free(__isl_take isl_union_map *umap)
 {
 	if (!umap)
-		return;
+		return NULL;
 
 	if (--umap->ref > 0)
-		return;
+		return NULL;
 
 	isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 			       &free_umap_entry, NULL);
 	isl_hash_table_clear(&umap->table);
-	isl_dim_free(umap->dim);
+	isl_space_free(umap->dim);
 	free(umap);
+	return NULL;
 }
 
-void isl_union_set_free(__isl_take isl_union_set *uset)
+void *isl_union_set_free(__isl_take isl_union_set *uset)
 {
-	isl_union_map_free(uset);
+	return isl_union_map_free(uset);
 }
 
 static int has_dim(const void *entry, const void *val)
 {
 	isl_map *map = (isl_map *)entry;
-	isl_dim *dim = (isl_dim *)val;
+	isl_space *dim = (isl_space *)val;
 
-	return isl_dim_equal(map->dim, dim);
+	return isl_space_is_equal(map->dim, dim);
 }
 
 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
@@ -259,20 +280,25 @@ __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
 	uint32_t hash;
 	struct isl_hash_table_entry *entry;
 
+	if (!map || !umap)
+		goto error;
+
 	if (isl_map_plain_is_empty(map)) {
 		isl_map_free(map);
 		return umap;
 	}
 
+	if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
+		umap = isl_union_map_align_params(umap, isl_map_get_space(map));
+		map = isl_map_align_params(map, isl_union_map_get_space(umap));
+	}
+
 	umap = isl_union_map_cow(umap);
 
 	if (!map || !umap)
 		goto error;
 
-	isl_assert(map->ctx, isl_dim_match(map->dim, isl_dim_param, umap->dim,
-					   isl_dim_param), goto error);
-
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 				    &has_dim, map->dim, 1);
 	if (!entry)
@@ -302,15 +328,14 @@ __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
 
 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
 {
-	isl_dim *dim;
+	isl_space *dim;
 	isl_union_map *umap;
 
 	if (!map)
 		return NULL;
 
-	dim = isl_map_get_dim(map);
-	dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
-	dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
+	dim = isl_map_get_space(map);
+	dim = isl_space_params(dim);
 	umap = isl_union_map_empty(dim);
 	umap = isl_union_map_add_map(umap, map);
 
@@ -322,6 +347,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);
@@ -369,46 +406,60 @@ static int copy_map(void **entry, void *user)
 	return -1;
 }
 
-__isl_give isl_map *isl_union_map_copy_map(__isl_keep isl_union_map *umap)
+__isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
 {
+	isl_ctx *ctx;
 	isl_map *map = NULL;
 
-	if (!umap || umap->table.n == 0)
+	if (!umap)
 		return NULL;
+	ctx = isl_union_map_get_ctx(umap);
+	if (umap->table.n != 1)
+		isl_die(ctx, isl_error_invalid,
+			"union map needs to contain elements in exactly "
+			"one space", return isl_union_map_free(umap));
 
-	isl_hash_table_foreach(umap->dim->ctx, &umap->table, &copy_map, &map);
+	isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
+
+	isl_union_map_free(umap);
 
 	return map;
 }
 
-__isl_give isl_set *isl_union_set_copy_set(__isl_keep isl_union_set *uset)
+__isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
 {
-	return isl_union_map_copy_map(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_dim *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_dim_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_dim_free(dim);
+		return isl_map_empty(space);
+	isl_space_free(space);
 	return isl_map_copy(entry->data);
 error:
-	isl_dim_free(dim);
+	isl_space_free(space);
 	return NULL;
 }
 
 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
-	__isl_take isl_dim *dim)
+	__isl_take isl_space *dim)
 {
 	return (isl_set *)isl_union_map_extract_map(uset, dim);
 }
@@ -416,7 +467,7 @@ __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
 /* Check if umap contains a map in the given space.
  */
 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
-	__isl_keep isl_dim *dim)
+	__isl_keep isl_space *dim)
 {
 	uint32_t hash;
 	struct isl_hash_table_entry *entry;
@@ -424,14 +475,14 @@ __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
 	if (!umap || !dim)
 		return -1;
 
-	hash = isl_dim_get_hash(dim);
+	hash = isl_space_get_hash(dim);
 	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 				    &has_dim, dim, 0);
 	return !!entry;
 }
 
 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
-	__isl_keep isl_dim *dim)
+	__isl_keep isl_space *dim)
 {
 	return isl_union_map_contains(uset, dim);
 }
@@ -478,7 +529,7 @@ static int subtract_entry(void **entry, void *user)
 	struct isl_hash_table_entry *entry2;
 	isl_map *map = *entry;
 
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 				     hash, &has_dim, map->dim, 0);
 	map = isl_map_copy(map);
@@ -506,14 +557,14 @@ static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
 {
 	struct isl_union_map_gen_bin_data data = { NULL, NULL };
 
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
 
 	data.umap2 = umap2;
-	data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 				       umap1->table.n);
 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 				   fn, &data) < 0)
@@ -541,6 +592,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;
@@ -555,7 +684,7 @@ static int match_bin_entry(void **entry, void *user)
 	isl_map *map = *entry;
 	int empty;
 
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 				     hash, &has_dim, map->dim, 0);
 	if (!entry2)
@@ -585,14 +714,14 @@ static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
 {
 	struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
 
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
 
 	data.umap2 = umap2;
-	data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 				       umap1->table.n);
 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 				   &match_bin_entry, &data) < 0)
@@ -614,10 +743,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,
@@ -629,6 +809,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);
 }
 
@@ -685,16 +867,16 @@ static int intersect_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_dim *dim;
+	isl_space *dim;
 	isl_map *map = *entry;
 	int empty;
 
-	dim = isl_map_get_dim(map);
-	dim = isl_dim_domain(dim);
-	hash = isl_dim_get_hash(dim);
+	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_dim_free(dim);
+	isl_space_free(dim);
 	if (!entry2)
 		return 0;
 
@@ -716,27 +898,219 @@ 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;
 	uint32_t hash;
 	struct isl_hash_table_entry *entry2;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_map *map = *entry;
 	int empty;
 
-	dim = isl_map_get_dim(map);
-	dim = isl_dim_range(dim);
-	hash = isl_dim_get_hash(dim);
+	dim = isl_map_get_space(map);
+	dim = isl_space_range(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_dim_free(dim);
+	isl_space_free(dim);
 	if (!entry2)
 		return 0;
 
@@ -777,7 +1151,7 @@ static int apply_range_entry(void **entry, void *user)
 	isl_map *map2 = *entry;
 	int empty;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
 				 map2->dim, isl_dim_in))
 		return 0;
 
@@ -816,14 +1190,14 @@ static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
 {
 	struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
 
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
 
 	data.umap2 = umap2;
-	data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 				       umap1->table.n);
 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 				   &bin_entry, &data) < 0)
@@ -864,7 +1238,7 @@ static int map_lex_lt_entry(void **entry, void *user)
 	struct isl_union_map_bin_data *data = user;
 	isl_map *map2 = *entry;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
 				 map2->dim, isl_dim_out))
 		return 0;
 
@@ -886,7 +1260,7 @@ static int map_lex_le_entry(void **entry, void *user)
 	struct isl_union_map_bin_data *data = user;
 	isl_map *map2 = *entry;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
 				 map2->dim, isl_dim_out))
 		return 0;
 
@@ -921,10 +1295,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)
@@ -932,7 +1343,7 @@ static int range_product_entry(void **entry, void *user)
 	struct isl_union_map_bin_data *data = user;
 	isl_map *map2 = *entry;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_in,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
 				 map2->dim, isl_dim_in))
 		return 0;
 
@@ -955,7 +1366,7 @@ static int flat_range_product_entry(void **entry, void *user)
 	struct isl_union_map_bin_data *data = user;
 	isl_map *map2 = *entry;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_in,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
 				 map2->dim, isl_dim_in))
 		return 0;
 
@@ -973,10 +1384,41 @@ __isl_give isl_union_map *isl_union_map_flat_range_product(
 	return bin_op(umap1, umap2, &flat_range_product_entry);
 }
 
+static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
+	int (*fn)(void **, void *))
+{
+	isl_union_set *res;
+
+	if (!umap)
+		return NULL;
+
+	res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
+	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
+		goto error;
+
+	isl_union_map_free(umap);
+	return res;
+error:
+	isl_union_map_free(umap);
+	isl_union_set_free(res);
+	return NULL;
+}
+
+static int from_range_entry(void **entry, void *user)
+{
+	isl_map *set = *entry;
+	isl_union_set **res = user;
+
+	*res = isl_union_map_add_map(*res,
+					isl_map_from_range(isl_set_copy(set)));
+
+	return 0;
+}
+
 __isl_give isl_union_map *isl_union_map_from_range(
 	__isl_take isl_union_set *uset)
 {
-	return uset;
+	return cond_un_op(uset, &from_range_entry);
 }
 
 __isl_give isl_union_map *isl_union_map_from_domain(
@@ -1182,32 +1624,12 @@ __isl_give isl_union_set *isl_union_set_lexmax(
 	return isl_union_map_lexmax(uset);
 }
 
-static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
-	int (*fn)(void **, void *))
-{
-	isl_union_set *res;
-
-	if (!umap)
-		return NULL;
-
-	res = isl_union_map_alloc(isl_dim_copy(umap->dim), umap->table.n);
-	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
-		goto error;
-
-	isl_union_map_free(umap);
-	return res;
-error:
-	isl_union_map_free(umap);
-	isl_union_set_free(res);
-	return NULL;
-}
-
 static int universe_entry(void **entry, void *user)
 {
 	isl_map *map = *entry;
 	isl_union_map **res = user;
 
-	map = isl_map_universe(isl_map_get_dim(map));
+	map = isl_map_universe(isl_map_get_space(map));
 	*res = isl_union_map_add_map(*res, map);
 
 	return 0;
@@ -1238,6 +1660,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;
@@ -1307,7 +1760,7 @@ static int deltas_entry(void **entry, void *user)
 	isl_map *map = *entry;
 	isl_union_set **res = user;
 
-	if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
+	if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
 		return 0;
 
 	*res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
@@ -1325,7 +1778,7 @@ static int deltas_map_entry(void **entry, void *user)
 	isl_map *map = *entry;
 	isl_union_map **res = user;
 
-	if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
+	if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
 		return 0;
 
 	*res = isl_union_map_add_map(*res,
@@ -1400,10 +1853,15 @@ static int is_subset_entry(void **entry, void *user)
 	struct isl_hash_table_entry *entry2;
 	isl_map *map = *entry;
 
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	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;
 	}
@@ -1422,8 +1880,8 @@ int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
 
 	umap1 = isl_union_map_copy(umap1);
 	umap2 = isl_union_map_copy(umap2);
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
@@ -1518,7 +1976,7 @@ __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
 		goto error;
 
 	if (!sample)
-		sample = isl_basic_map_empty(isl_union_map_get_dim(umap));
+		sample = isl_basic_map_empty(isl_union_map_get_space(umap));
 
 	isl_union_map_free(umap);
 
@@ -1619,16 +2077,16 @@ int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
 static int is_subset_of_identity(__isl_keep isl_map *map)
 {
 	int is_subset;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_map *id;
 
 	if (!map)
 		return -1;
 
-	if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
+	if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
 		return 0;
 
-	dim = isl_map_get_dim(map);
+	dim = isl_map_get_space(map);
 	id = isl_map_identity(dim);
 
 	is_subset = isl_map_is_subset(map, id);
@@ -1651,7 +2109,9 @@ int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
 	int sv;
 
 	if (isl_union_map_n_map(umap) == 1) {
-		isl_map *map = isl_union_map_copy_map(umap);
+		isl_map *map;
+		umap = isl_union_map_copy(umap);
+		map = isl_map_from_union_map(umap);
 		sv = isl_map_is_single_valued(map);
 		isl_map_free(map);
 		return sv;
@@ -1760,7 +2220,7 @@ static int plain_injective_on_range(__isl_take isl_union_map *umap,
  * based on later dimensions.
  */
 static int separates(struct isl_fixed_map *v, int n,
-	__isl_take isl_dim *dim, int pos, int n_range)
+	__isl_take isl_space *dim, int pos, int n_range)
 {
 	int i;
 
@@ -1781,7 +2241,7 @@ static int separates(struct isl_fixed_map *v, int n,
 		if (j == i + 1)
 			continue;
 
-		part = isl_union_map_alloc(isl_dim_copy(dim), j - i);
+		part = isl_union_map_alloc(isl_space_copy(dim), j - i);
 		for (k = i; k < j; ++k)
 			part = isl_union_map_add_map(part,
 						     isl_map_copy(v[k].map));
@@ -1795,11 +2255,11 @@ static int separates(struct isl_fixed_map *v, int n,
 		i = j - 1;
 	}
 
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	free_isl_fixed_map_array(v, n);
 	return i + 1 >= n;
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	free_isl_fixed_map_array(v, n);
 	return -1;
 }
@@ -1819,10 +2279,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;
@@ -1840,7 +2300,7 @@ static int plain_injective_on_range(__isl_take isl_union_map *umap,
 	for (data.pos = first; data.pos < n_range; ++data.pos) {
 		int fixed;
 		int injective;
-		isl_dim *dim;
+		isl_space *dim;
 
 		data.n = 0;
 		fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
@@ -1848,7 +2308,7 @@ static int plain_injective_on_range(__isl_take isl_union_map *umap,
 			goto error;
 		if (!fixed)
 			continue;
-		dim = isl_union_map_get_dim(umap);
+		dim = isl_union_map_get_space(umap);
 		injective = separates(data.v, n, dim, data.pos, n_range);
 		isl_union_map_free(umap);
 		return injective;
@@ -1934,6 +2394,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;
@@ -1965,14 +2467,14 @@ __isl_give isl_union_set *isl_union_set_coefficients(
 	__isl_take isl_union_set *uset)
 {
 	isl_ctx *ctx;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_union_set *res;
 
 	if (!uset)
 		return NULL;
 
 	ctx = isl_union_set_get_ctx(uset);
-	dim = isl_dim_set_alloc(ctx, 0, 0);
+	dim = isl_space_set_alloc(ctx, 0, 0);
 	res = isl_union_map_alloc(dim, uset->table.n);
 	if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
 				   &coefficients_entry, &res) < 0)
@@ -2013,7 +2515,7 @@ __isl_give isl_union_set *isl_union_set_solutions(
 		return NULL;
 
 	if (uset->table.n == 0) {
-		res = isl_union_set_empty(isl_union_set_get_dim(uset));
+		res = isl_union_set_empty(isl_union_set_get_space(uset));
 		isl_union_set_free(uset);
 		return res;
 	}