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

diff --git a/isl_union_map.c b/isl_union_map.c
index f8d48bb..0edaf55 100644
--- a/isl_union_map.c
+++ b/isl_union_map.c
@@ -1,27 +1,48 @@
 /*
- * Copyright 2010      INRIA Saclay
+ * 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/aff.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;
 
+	dim = isl_space_params(dim);
 	if (!dim)
 		return NULL;
 
@@ -36,17 +57,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 +82,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 +117,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 +148,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 +163,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 +188,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 +207,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 +247,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 +282,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 +330,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 +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);
@@ -369,46 +408,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(ctx, &umap->table, &copy_map, &map);
 
-	isl_hash_table_foreach(umap->dim->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 +469,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 +477,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 +531,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 +559,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 +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;
@@ -555,7 +686,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 +716,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 +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,
@@ -629,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);
 }
 
@@ -685,16 +869,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 +900,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 +1153,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 +1192,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 +1240,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 +1262,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 +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)
@@ -932,6 +1345,10 @@ static int range_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_in,
+				 map2->dim, isl_dim_in))
+		return 0;
+
 	map2 = isl_map_range_product(isl_map_copy(data->map),
 				     isl_map_copy(map2));
 
@@ -946,10 +1363,64 @@ __isl_give isl_union_map *isl_union_map_range_product(
 	return bin_op(umap1, umap2, &range_product_entry);
 }
 
+static int flat_range_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_in,
+				 map2->dim, isl_dim_in))
+		return 0;
+
+	map2 = isl_map_flat_range_product(isl_map_copy(data->map),
+					  isl_map_copy(map2));
+
+	data->res = isl_union_map_add_map(data->res, map2);
+
+	return 0;
+}
+
+__isl_give isl_union_map *isl_union_map_flat_range_product(
+	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
+{
+	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(
@@ -1155,32 +1626,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;
@@ -1211,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;
@@ -1280,7 +1762,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)));
@@ -1298,7 +1780,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,
@@ -1373,10 +1855,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;
 	}
@@ -1395,8 +1882,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;
@@ -1491,7 +1978,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);
 
@@ -1541,6 +2028,44 @@ static int union_map_forall(__isl_keep isl_union_map *umap,
 	return data.res;
 }
 
+struct isl_forall_user_data {
+	int res;
+	int (*fn)(__isl_keep isl_map *map, void *user);
+	void *user;
+};
+
+static int forall_user_entry(void **entry, void *user)
+{
+	struct isl_forall_user_data *data = user;
+	isl_map *map = *entry;
+
+	data->res = data->fn(map, data->user);
+	if (data->res < 0)
+		return -1;
+
+	if (!data->res)
+		return -1;
+
+	return 0;
+}
+
+/* Check if fn(map, user) returns true for all maps "map" in umap.
+ */
+static int union_map_forall_user(__isl_keep isl_union_map *umap,
+	int (*fn)(__isl_keep isl_map *map, void *user), void *user)
+{
+	struct isl_forall_user_data data = { 1, fn, user };
+
+	if (!umap)
+		return -1;
+
+	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
+				   &forall_user_entry, &data) < 0 && data.res)
+		return -1;
+
+	return data.res;
+}
+
 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
 {
 	return union_map_forall(umap, &isl_map_is_empty);
@@ -1554,16 +2079,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);
@@ -1586,7 +2111,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;
@@ -1614,6 +2141,232 @@ int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
 	return in;
 }
 
+/* Represents a map that has a fixed value (v) for one of its
+ * range dimensions.
+ * The map in this structure is not reference counted, so it
+ * is only valid while the isl_union_map from which it was
+ * obtained is still alive.
+ */
+struct isl_fixed_map {
+	isl_int v;
+	isl_map *map;
+};
+
+static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
+	int n)
+{
+	int i;
+	struct isl_fixed_map *v;
+
+	v = isl_calloc_array(ctx, struct isl_fixed_map, n);
+	if (!v)
+		return NULL;
+	for (i = 0; i < n; ++i)
+		isl_int_init(v[i].v);
+	return v;
+}
+
+static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
+{
+	int i;
+
+	if (!v)
+		return;
+	for (i = 0; i < n; ++i)
+		isl_int_clear(v[i].v);
+	free(v);
+}
+
+/* Compare the "v" field of two isl_fixed_map structs.
+ */
+static int qsort_fixed_map_cmp(const void *p1, const void *p2)
+{
+	const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
+	const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
+
+	return isl_int_cmp(e1->v, e2->v);
+}
+
+/* Internal data structure used while checking whether all maps
+ * in a union_map have a fixed value for a given output dimension.
+ * v is the list of maps, with the fixed value for the dimension
+ * n is the number of maps considered so far
+ * pos is the output dimension under investigation
+ */
+struct isl_fixed_dim_data {
+	struct isl_fixed_map *v;
+	int n;
+	int pos;
+};
+
+static int fixed_at_pos(__isl_keep isl_map *map, void *user)
+{
+	struct isl_fixed_dim_data *data = user;
+
+	data->v[data->n].map = map;
+	return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
+				      &data->v[data->n++].v);
+}
+
+static int plain_injective_on_range(__isl_take isl_union_map *umap,
+	int first, int n_range);
+
+/* Given a list of the maps, with their fixed values at output dimension "pos",
+ * check whether the ranges of the maps form an obvious partition.
+ *
+ * We first sort the maps according to their fixed values.
+ * If all maps have a different value, then we know the ranges form
+ * a partition.
+ * Otherwise, we collect the maps with the same fixed value and
+ * check whether each such collection is obviously injective
+ * based on later dimensions.
+ */
+static int separates(struct isl_fixed_map *v, int n,
+	__isl_take isl_space *dim, int pos, int n_range)
+{
+	int i;
+
+	if (!v)
+		goto error;
+
+	qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
+
+	for (i = 0; i + 1 < n; ++i) {
+		int j, k;
+		isl_union_map *part;
+		int injective;
+
+		for (j = i + 1; j < n; ++j)
+			if (isl_int_ne(v[i].v, v[j].v))
+				break;
+
+		if (j == i + 1)
+			continue;
+
+		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));
+
+		injective = plain_injective_on_range(part, pos + 1, n_range);
+		if (injective < 0)
+			goto error;
+		if (!injective)
+			break;
+
+		i = j - 1;
+	}
+
+	isl_space_free(dim);
+	free_isl_fixed_map_array(v, n);
+	return i + 1 >= n;
+error:
+	isl_space_free(dim);
+	free_isl_fixed_map_array(v, n);
+	return -1;
+}
+
+/* Check whether the maps in umap have obviously distinct ranges.
+ * In particular, check for an output dimension in the range
+ * [first,n_range) for which all maps have a fixed value
+ * and then check if these values, possibly along with fixed values
+ * at later dimensions, entail distinct ranges.
+ */
+static int plain_injective_on_range(__isl_take isl_union_map *umap,
+	int first, int n_range)
+{
+	isl_ctx *ctx;
+	int n;
+	struct isl_fixed_dim_data data = { NULL };
+
+	ctx = isl_union_map_get_ctx(umap);
+
+	n = isl_union_map_n_map(umap);
+	if (!umap)
+		goto error;
+
+	if (n <= 1) {
+		isl_union_map_free(umap);
+		return 1;
+	}
+
+	if (first >= n_range) {
+		isl_union_map_free(umap);
+		return 0;
+	}
+
+	data.v = alloc_isl_fixed_map_array(ctx, n);
+	if (!data.v)
+		goto error;
+
+	for (data.pos = first; data.pos < n_range; ++data.pos) {
+		int fixed;
+		int injective;
+		isl_space *dim;
+
+		data.n = 0;
+		fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
+		if (fixed < 0)
+			goto error;
+		if (!fixed)
+			continue;
+		dim = isl_union_map_get_space(umap);
+		injective = separates(data.v, n, dim, data.pos, n_range);
+		isl_union_map_free(umap);
+		return injective;
+	}
+
+	free_isl_fixed_map_array(data.v, n);
+	isl_union_map_free(umap);
+
+	return 0;
+error:
+	free_isl_fixed_map_array(data.v, n);
+	isl_union_map_free(umap);
+	return -1;
+}
+
+/* Check whether the maps in umap that map to subsets of "ran"
+ * have obviously distinct ranges.
+ */
+static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
+{
+	isl_union_map *umap = user;
+
+	umap = isl_union_map_copy(umap);
+	umap = isl_union_map_intersect_range(umap,
+			isl_union_set_from_set(isl_set_copy(ran)));
+	return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
+}
+
+/* Check if the given union_map is obviously injective.
+ *
+ * In particular, we first check if all individual maps are obviously
+ * injective and then check if all the ranges of these maps are
+ * obviously disjoint.
+ */
+int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
+{
+	int in;
+	isl_union_map *univ;
+	isl_union_set *ran;
+
+	in = union_map_forall(umap, &isl_map_plain_is_injective);
+	if (in < 0)
+		return -1;
+	if (!in)
+		return 0;
+
+	univ = isl_union_map_universe(isl_union_map_copy(umap));
+	ran = isl_union_map_range(univ);
+
+	in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
+
+	isl_union_set_free(ran);
+
+	return in;
+}
+
 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
 {
 	int sv;
@@ -1643,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;
@@ -1674,14 +2469,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)
@@ -1716,15 +2511,13 @@ static int solutions_entry(void **entry, void *user)
 __isl_give isl_union_set *isl_union_set_solutions(
 	__isl_take isl_union_set *uset)
 {
-	isl_ctx *ctx;
-	isl_dim *dim;
 	isl_union_set *res = NULL;
 
 	if (!uset)
 		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;
 	}
@@ -1740,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;
+}