X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_union_templ.c;h=cd55f4e910ec5f2f081a2d9b36899751a0e5b083;hb=ca90b151a05f17ccc1c3215ff24dc5d7b9198ff4;hp=8495cbf72dd3cef3974aadbf3d168a12a940aa9d;hpb=892fb27ee14523cdd277639f82a7842e993b486d;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_union_templ.c b/isl_union_templ.c
index 8495cbf..cd55f4e 100644
--- a/isl_union_templ.c
+++ b/isl_union_templ.c
@@ -1,7 +1,7 @@
 /*
  * Copyright 2010      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,
@@ -15,7 +15,10 @@
 
 struct UNION {
 	int ref;
-	isl_dim *dim;
+#ifdef HAS_TYPE
+	enum isl_fold type;
+#endif
+	isl_space *dim;
 
 	struct isl_hash_table	table;
 };
@@ -27,37 +30,56 @@ isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
 	return u ? u->dim->ctx : NULL;
 }
 
-__isl_give isl_dim *FN(UNION,get_dim)(__isl_keep UNION *u)
+__isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
 {
 	if (!u)
 		return NULL;
-	return isl_dim_copy(u->dim);
+	return isl_space_copy(u->dim);
 }
 
-static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_dim *dim, int size)
+#ifdef HAS_TYPE
+static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
+	enum isl_fold type, int size)
+#else
+static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
+#endif
 {
 	UNION *u;
 
-	u = isl_calloc_type(ctx, UNION);
+	dim = isl_space_params(dim);
+	if (!dim)
+		return NULL;
+
+	u = isl_calloc_type(dim->ctx, UNION);
 	if (!u)
 		return NULL;
 
 	u->ref = 1;
+#ifdef HAS_TYPE
+	u->type = type;
+#endif
 	u->dim = dim;
 	if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
 		goto error;
 
 	return u;
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	FN(UNION,free)(u);
 	return NULL;
 }
 
-__isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim)
+#ifdef HAS_TYPE
+__isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
+{
+	return FN(UNION,alloc)(dim, type, 16);
+}
+#else
+__isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
 {
 	return FN(UNION,alloc)(dim, 16);
 }
+#endif
 
 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
 {
@@ -97,9 +119,34 @@ int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
 static int has_dim(const void *entry, const void *val)
 {
 	PART *part = (PART *)entry;
-	isl_dim *dim = (isl_dim *)val;
+	isl_space *dim = (isl_space *)val;
 
-	return isl_dim_equal(part->dim, dim);
+	return isl_space_is_equal(part->dim, dim);
+}
+
+__isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
+	__isl_take isl_space *dim)
+{
+	uint32_t hash;
+	struct isl_hash_table_entry *entry;
+
+	if (!u || !dim)
+		goto error;
+
+	hash = isl_space_get_hash(dim);
+	entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
+				    &has_dim, dim, 0);
+	if (!entry)
+#ifdef HAS_TYPE
+		return FN(PART,ZERO)(dim, u->type);
+#else
+		return FN(PART,ZERO)(dim);
+#endif
+	isl_space_free(dim);
+	return FN(PART,copy)(entry->data);
+error:
+	isl_space_free(dim);
+	return NULL;
 }
 
 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
@@ -108,15 +155,23 @@ __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 	uint32_t hash;
 	struct isl_hash_table_entry *entry;
 
+	if (!part)
+		goto error;
+
+	if (DEFAULT_IS_ZERO && FN(PART,IS_ZERO)(part)) {
+		FN(PART,free)(part);
+		return u;
+	}
+
 	u = FN(UNION,cow)(u);
 
-	if (!part || !u)
+	if (!u)
 		goto error;
 
-	isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
+	isl_assert(u->dim->ctx, isl_space_match(part->dim, isl_dim_param, u->dim,
 					      isl_dim_param), goto error);
 
-	hash = isl_dim_get_hash(part->dim);
+	hash = isl_space_get_hash(part->dim);
 	entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 				    &has_dim, part->dim, 1);
 	if (!entry)
@@ -129,7 +184,7 @@ __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 		if (!entry->data)
 			goto error;
 		FN(PART,free)(part);
-		if (FN(PART,is_zero)(entry->data)) {
+		if (DEFAULT_IS_ZERO && FN(PART,IS_ZERO)(entry->data)) {
 			FN(PART,free)(entry->data);
 			isl_hash_table_remove(u->dim->ctx, &u->table, entry);
 		}
@@ -158,7 +213,11 @@ __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 	if (!u)
 		return NULL;
 
-	dup = FN(UNION,zero)(isl_dim_copy(u->dim));
+#ifdef HAS_TYPE
+	dup = FN(UNION,ZERO)(isl_space_copy(u->dim), u->type);
+#else
+	dup = FN(UNION,ZERO)(isl_space_copy(u->dim));
+#endif
 	if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 		goto error;
 	return dup;
@@ -185,22 +244,99 @@ static int free_u_entry(void **entry, void *user)
 	return 0;
 }
 
-void FN(UNION,free)(__isl_take UNION *u)
+void *FN(UNION,free)(__isl_take UNION *u)
 {
 	if (!u)
-		return;
+		return NULL;
 
 	if (--u->ref > 0)
-		return;
+		return NULL;
 
 	isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
 	isl_hash_table_clear(&u->table);
-	isl_dim_free(u->dim);
+	isl_space_free(u->dim);
 	free(u);
+	return NULL;
+}
+
+S(UNION,align) {
+	isl_reordering *exp;
+	UNION *res;
+};
+
+#ifdef ALIGN_DOMAIN
+static int align_entry(__isl_take PART *part, void *user)
+{
+	isl_reordering *exp;
+	S(UNION,align) *data = user;
+
+	exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
+				    FN(PART,get_domain_space)(part));
+
+	data->res = FN(FN(UNION,add),PARTS)(data->res,
+					    FN(PART,realign_domain)(part, exp));
+
+	return 0;
+}
+#else
+static int align_entry(__isl_take PART *part, void *user)
+{
+	isl_reordering *exp;
+	S(UNION,align) *data = user;
+
+	exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
+				    FN(PART,get_space)(part));
+
+	data->res = FN(FN(UNION,add),PARTS)(data->res,
+					    FN(PART,realign)(part, exp));
+
+	return 0;
+}
+#endif
+
+__isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
+	__isl_take isl_space *model)
+{
+	S(UNION,align) data = { NULL, NULL };
+
+	if (!u || !model)
+		goto error;
+
+	if (isl_space_match(u->dim, isl_dim_param, model, isl_dim_param)) {
+		isl_space_free(model);
+		return u;
+	}
+
+	data.exp = isl_parameter_alignment_reordering(u->dim, model);
+	if (!data.exp)
+		goto error;
+
+#ifdef HAS_TYPE
+	data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim),
+						u->type, u->table.n);
+#else
+	data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim), u->table.n);
+#endif
+	if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
+		goto error;
+
+	isl_reordering_free(data.exp);
+	FN(UNION,free)(u);
+	isl_space_free(model);
+	return data.res;
+error:
+	isl_reordering_free(data.exp);
+	FN(UNION,free)(u);
+	FN(UNION,free)(data.res);
+	isl_space_free(model);
+	return NULL;
 }
 
 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 {
+	u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
+	u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
+
 	u1 = FN(UNION,cow)(u1);
 
 	if (!u1 || !u2)
@@ -220,36 +356,103 @@ error:
 
 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 {
-	isl_dim *dim;
+	isl_space *dim;
 	UNION *u;
 
 	if (!part)
 		return NULL;
 
-	dim = FN(PART,get_dim)(part);
-	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));
-	u = FN(UNION,zero)(dim);
+	dim = FN(PART,get_space)(part);
+	dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
+	dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
+#ifdef HAS_TYPE
+	u = FN(UNION,ZERO)(dim, part->type);
+#else
+	u = FN(UNION,ZERO)(dim);
+#endif
 	u = FN(FN(UNION,add),PARTS)(u, part);
 
 	return u;
 }
 
 S(UNION,match_bin_data) {
-	UNION *upwqp2;
+	UNION *u2;
 	UNION *res;
+	__isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
 };
 
+/* Check if data->u2 has an element living in the same space as *entry.
+ * If so, call data->fn on the two elements and add the result to
+ * data->res.
+ */
+static int match_bin_entry(void **entry, void *user)
+{
+	S(UNION,match_bin_data) *data = user;
+	uint32_t hash;
+	struct isl_hash_table_entry *entry2;
+	isl_space *space;
+	PART *part = *entry;
+
+	space = FN(PART,get_space)(part);
+	hash = isl_space_get_hash(space);
+	entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
+				     hash, &has_dim, space, 0);
+	isl_space_free(space);
+	if (!entry2)
+		return 0;
+
+	part = FN(PART, copy)(part);
+	part = data->fn(part, FN(PART, copy)(entry2->data));
+
+	if (DEFAULT_IS_ZERO) {
+		int empty;
+
+		empty = FN(PART,IS_ZERO)(part);
+		if (empty < 0) {
+			FN(PART,free)(part);
+			return -1;
+		}
+		if (empty) {
+			FN(PART,free)(part);
+			return 0;
+		}
+	}
+
+	data->res = FN(FN(UNION,add),PARTS)(data->res, part);
+
+	return 0;
+}
+
+/* This function is currently only used from isl_polynomial.c
+ * and not from isl_fold.c.
+ */
+static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
+	__isl_take UNION *u2,
+	__isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
+	__attribute__ ((unused));
+/* For each pair of elements in "u1" and "u2" living in the same space,
+ * call "fn" and collect the results.
+ */
 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
-	__isl_take UNION *u2, int (*fn)(void **, void *))
+	__isl_take UNION *u2,
+	__isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 {
-	S(UNION,match_bin_data) data = { u2, NULL };
+	S(UNION,match_bin_data) data = { NULL, NULL, fn };
+
+	u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
+	u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 
 	if (!u1 || !u2)
 		goto error;
 
-	data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->table.n);
-	if (isl_hash_table_foreach(u1->dim->ctx, &u1->table, fn, &data) < 0)
+	data.u2 = u2;
+#ifdef HAS_TYPE
+	data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->type, u1->table.n);
+#else
+	data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->table.n);
+#endif
+	if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
+				    &match_bin_entry, &data) < 0)
 		goto error;
 
 	FN(UNION,free)(u1);
@@ -262,7 +465,100 @@ error:
 	return NULL;
 }
 
-S(UNION,match_set_data) {
+#ifndef NO_SUB
+/* Subtract "u2" from "u1" and return the result.
+ */
+__isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
+{
+	return match_bin_op(u1, u2, &FN(PART,sub));
+}
+#endif
+
+S(UNION,any_set_data) {
+	isl_set *set;
+	UNION *res;
+	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
+};
+
+static int any_set_entry(void **entry, void *user)
+{
+	S(UNION,any_set_data) *data = user;
+	PW *pw = *entry;
+
+	pw = FN(PW,copy)(pw);
+	pw = data->fn(pw, isl_set_copy(data->set));
+
+	if (DEFAULT_IS_ZERO) {
+		int empty;
+
+		empty = FN(PW,IS_ZERO)(pw);
+		if (empty < 0) {
+			FN(PW,free)(pw);
+			return -1;
+		}
+		if (empty) {
+			FN(PW,free)(pw);
+			return 0;
+		}
+	}
+
+	data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
+
+	return 0;
+}
+
+/* Update each element of "u" by calling "fn" on the element and "set".
+ */
+static __isl_give UNION *any_set_op(__isl_take UNION *u,
+	__isl_take isl_set *set,
+	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
+{
+	S(UNION,any_set_data) data = { NULL, NULL, fn };
+
+	u = FN(UNION,align_params)(u, isl_set_get_space(set));
+	set = isl_set_align_params(set, FN(UNION,get_space)(u));
+
+	if (!u || !set)
+		goto error;
+
+	data.set = set;
+#ifdef HAS_TYPE
+	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
+#else
+	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
+#endif
+	if (isl_hash_table_foreach(u->dim->ctx, &u->table,
+				   &any_set_entry, &data) < 0)
+		goto error;
+
+	FN(UNION,free)(u);
+	isl_set_free(set);
+	return data.res;
+error:
+	FN(UNION,free)(u);
+	isl_set_free(set);
+	FN(UNION,free)(data.res);
+	return NULL;
+}
+
+/* Intersect the domain of "u" with the parameter domain "context".
+ */
+__isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
+	__isl_take isl_set *set)
+{
+	return any_set_op(u, set, &FN(PW,intersect_params));
+}
+
+/* Compute the gist of the domain of "u" with respect to
+ * the parameter domain "context".
+ */
+__isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
+	__isl_take isl_set *set)
+{
+	return any_set_op(u, set, &FN(PW,gist_params));
+}
+
+S(UNION,match_domain_data) {
 	isl_union_set *uset;
 	UNION *res;
 	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
@@ -271,37 +567,46 @@ S(UNION,match_set_data) {
 static int set_has_dim(const void *entry, const void *val)
 {
 	isl_set *set = (isl_set *)entry;
-	isl_dim *dim = (isl_dim *)val;
+	isl_space *dim = (isl_space *)val;
 
-	return isl_dim_equal(set->dim, dim);
+	return isl_space_is_equal(set->dim, dim);
 }
 
-static int match_set_entry(void **entry, void *user)
+/* Find the set in data->uset that live in the same space as the domain
+ * of *entry, apply data->fn to *entry and this set (if any), and add
+ * the result to data->res.
+ */
+static int match_domain_entry(void **entry, void *user)
 {
-	S(UNION,match_set_data) *data = user;
+	S(UNION,match_domain_data) *data = user;
 	uint32_t hash;
 	struct isl_hash_table_entry *entry2;
-	isl_dim *dim;
 	PW *pw = *entry;
-	int empty;
+	isl_space *space;
 
-	hash = isl_dim_get_hash(pw->dim);
+	space = FN(PW,get_domain_space)(pw);
+	hash = isl_space_get_hash(space);
 	entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
-				     hash, &set_has_dim, pw->dim, 0);
+				     hash, &set_has_dim, space, 0);
+	isl_space_free(space);
 	if (!entry2)
 		return 0;
 
 	pw = FN(PW,copy)(pw);
 	pw = data->fn(pw, isl_set_copy(entry2->data));
 
-	empty = FN(PW,is_zero)(pw);
-	if (empty < 0) {
-		FN(PW,free)(pw);
-		return -1;
-	}
-	if (empty) {
-		FN(PW,free)(pw);
-		return 0;
+	if (DEFAULT_IS_ZERO) {
+		int empty;
+
+		empty = FN(PW,IS_ZERO)(pw);
+		if (empty < 0) {
+			FN(PW,free)(pw);
+			return -1;
+		}
+		if (empty) {
+			FN(PW,free)(pw);
+			return 0;
+		}
 	}
 
 	data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
@@ -309,18 +614,30 @@ static int match_set_entry(void **entry, void *user)
 	return 0;
 }
 
-static __isl_give UNION *match_set_op(__isl_take UNION *u,
+/* Apply fn to each pair of PW in u and set in uset such that
+ * the set lives in the same space as the domain of PW
+ * and collect the results.
+ */
+static __isl_give UNION *match_domain_op(__isl_take UNION *u,
 	__isl_take isl_union_set *uset,
 	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 {
-	S(UNION,match_set_data) data = { uset, NULL, fn };
+	S(UNION,match_domain_data) data = { NULL, NULL, fn };
+
+	u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
+	uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
 
 	if (!u || !uset)
 		goto error;
 
-	data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->table.n);
+	data.uset = uset;
+#ifdef HAS_TYPE
+	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
+#else
+	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
+#endif
 	if (isl_hash_table_foreach(u->dim->ctx, &u->table,
-				   &match_set_entry, &data) < 0)
+				   &match_domain_entry, &data) < 0)
 		goto error;
 
 	FN(UNION,free)(u);
@@ -333,33 +650,50 @@ error:
 	return NULL;
 }
 
+/* Intersect the domain of "u" with "uset".
+ * If "uset" is a parameters domain, then intersect the parameter
+ * domain of "u" with this set.
+ */
 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 	__isl_take isl_union_set *uset)
 {
-	return match_set_op(u, uset, &FN(PW,intersect_domain));
+	if (isl_union_set_is_params(uset))
+		return FN(UNION,intersect_params)(u,
+						isl_set_from_union_set(uset));
+	return match_domain_op(u, uset, &FN(PW,intersect_domain));
 }
 
 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 	__isl_take isl_union_set *uset)
 {
-	return match_set_op(u, uset, &FN(PW,gist));
+	if (isl_union_set_is_params(uset))
+		return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
+	return match_domain_op(u, uset, &FN(PW,gist));
 }
 
+#ifndef NO_EVAL
 __isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
 	__isl_take isl_point *pnt)
 {
 	uint32_t hash;
 	struct isl_hash_table_entry *entry;
+	isl_space *space;
 	isl_qpolynomial *qp;
 
 	if (!u || !pnt)
 		goto error;
 
-	hash = isl_dim_get_hash(pnt->dim);
+	space = isl_space_copy(pnt->dim);
+	space = isl_space_from_domain(space);
+	space = isl_space_add_dims(space, isl_dim_out, 1);
+	if (!space)
+		goto error;
+	hash = isl_space_get_hash(space);
 	entry = isl_hash_table_find(u->dim->ctx, &u->table,
-				    hash, &has_dim, pnt->dim, 0);
+				    hash, &has_dim, space, 0);
+	isl_space_free(space);
 	if (!entry) {
-		qp = isl_qpolynomial_zero(isl_dim_copy(pnt->dim));
+		qp = isl_qpolynomial_zero_on_domain(isl_space_copy(pnt->dim));
 		isl_point_free(pnt);
 	} else {
 		qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
@@ -371,6 +705,7 @@ error:
 	isl_point_free(pnt);
 	return NULL;
 }
+#endif
 
 static int coalesce_entry(void **entry, void *user)
 {
@@ -411,7 +746,7 @@ __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 {
 	isl_union_set *uset;
 
-	uset = isl_union_set_empty(FN(UNION,get_dim)(u));
+	uset = isl_union_set_empty(FN(UNION,get_space)(u));
 	if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 		goto error;
 
@@ -423,3 +758,111 @@ error:
 	FN(UNION,free)(u);
 	return NULL;
 }
+
+static int mul_isl_int(void **entry, void *user)
+{
+	PW **pw = (PW **)entry;
+	isl_int *v = user;
+
+	*pw = FN(PW,mul_isl_int)(*pw, *v);
+	if (!*pw)
+		return -1;
+
+	return 0;
+}
+
+__isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
+{
+	if (isl_int_is_one(v))
+		return u;
+
+	if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
+		UNION *zero;
+		isl_space *dim = FN(UNION,get_space)(u);
+#ifdef HAS_TYPE
+		zero = FN(UNION,ZERO)(dim, u->type);
+#else
+		zero = FN(UNION,ZERO)(dim);
+#endif
+		FN(UNION,free)(u);
+		return zero;
+	}
+
+	u = FN(UNION,cow)(u);
+	if (!u)
+		return NULL;
+
+#ifdef HAS_TYPE
+	if (isl_int_is_neg(v))
+		u->type = isl_fold_type_negate(u->type);
+#endif
+	if (isl_hash_table_foreach(u->dim->ctx, &u->table, &mul_isl_int, v) < 0)
+		goto error;
+
+	return u;
+error:
+	FN(UNION,free)(u);
+	return NULL;
+}
+
+S(UNION,plain_is_equal_data)
+{
+	UNION *u2;
+	int is_equal;
+};
+
+static int plain_is_equal_entry(void **entry, void *user)
+{
+	S(UNION,plain_is_equal_data) *data = user;
+	uint32_t hash;
+	struct isl_hash_table_entry *entry2;
+	PW *pw = *entry;
+
+	hash = isl_space_get_hash(pw->dim);
+	entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
+				     hash, &has_dim, pw->dim, 0);
+	if (!entry2) {
+		data->is_equal = 0;
+		return -1;
+	}
+
+	data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
+	if (data->is_equal < 0 || !data->is_equal)
+		return -1;
+
+	return 0;
+}
+
+int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
+{
+	S(UNION,plain_is_equal_data) data = { NULL, 1 };
+
+	if (!u1 || !u2)
+		return -1;
+	if (u1 == u2)
+		return 1;
+	if (u1->table.n != u2->table.n)
+		return 0;
+
+	u1 = FN(UNION,copy)(u1);
+	u2 = FN(UNION,copy)(u2);
+	u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
+	u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
+	if (!u1 || !u2)
+		goto error;
+
+	data.u2 = u2;
+	if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
+				   &plain_is_equal_entry, &data) < 0 &&
+	    data.is_equal)
+		goto error;
+
+	FN(UNION,free)(u1);
+	FN(UNION,free)(u2);
+
+	return data.is_equal;
+error:
+	FN(UNION,free)(u1);
+	FN(UNION,free)(u2);
+	return -1;
+}