X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=26eb7d26505eeb8b8471cb5b6f563eb40078ba13;hb=0f12c7f0871b11aca0ceabd8934f54cddb5c4b39;hp=b91fc274602dcf84498af51f2e30b0c35525e0d9;hpb=21686238435b224acf7181c026b8fa2925bb0e4e;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_map.c b/isl_map.c
index b91fc27..26eb7d2 100644
--- a/isl_map.c
+++ b/isl_map.c
@@ -122,6 +122,8 @@ unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset)
 
 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
 {
+	if (!bset)
+		return 0;
 	return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div;
 }
 
@@ -255,25 +257,42 @@ __isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset)
 	return isl_space_copy(bset->dim);
 }
 
-__isl_give isl_local_space *isl_basic_map_get_local_space(
-	__isl_keep isl_basic_map *bmap)
+/* Extract the divs in "bmap" as a matrix.
+ */
+__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap)
 {
 	int i;
-	isl_local_space *ls;
+	isl_ctx *ctx;
+	isl_mat *div;
 	unsigned total;
+	unsigned cols;
 
 	if (!bmap)
 		return NULL;
 
-	total = isl_basic_map_total_dim(bmap);
-	ls = isl_local_space_alloc(isl_space_copy(bmap->dim), bmap->n_div);
-	if (!ls)
+	ctx = isl_basic_map_get_ctx(bmap);
+	total = isl_space_dim(bmap->dim, isl_dim_all);
+	cols = 1 + 1 + total + bmap->n_div;
+	div = isl_mat_alloc(ctx, bmap->n_div, cols);
+	if (!div)
 		return NULL;
 
 	for (i = 0; i < bmap->n_div; ++i)
-		isl_seq_cpy(ls->div->row[i], bmap->div[i], 2 + total);
+		isl_seq_cpy(div->row[i], bmap->div[i], cols);
+
+	return div;
+}
+
+__isl_give isl_local_space *isl_basic_map_get_local_space(
+	__isl_keep isl_basic_map *bmap)
+{
+	isl_mat *div;
+
+	if (!bmap)
+		return NULL;
 
-	return ls;
+	div = isl_basic_map_get_divs(bmap);
+	return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div);
 }
 
 __isl_give isl_local_space *isl_basic_set_get_local_space(
@@ -455,6 +474,14 @@ __isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set)
 	return isl_map_get_tuple_id(set, isl_dim_set);
 }
 
+/* Does the set tuple have a name?
+ */
+int isl_set_has_tuple_name(__isl_keep isl_set *set)
+{
+	return set ? isl_space_has_tuple_name(set->dim, isl_dim_set) : -1;
+}
+
+
 const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset)
 {
 	return bset ? isl_space_get_tuple_name(bset->dim, isl_dim_set) : NULL;
@@ -489,6 +516,14 @@ const char *isl_set_get_dim_name(__isl_keep isl_set *set,
 	return set ? isl_space_get_dim_name(set->dim, type, pos) : NULL;
 }
 
+/* Does the given dimension have a name?
+ */
+int isl_set_has_dim_name(__isl_keep isl_set *set,
+	enum isl_dim_type type, unsigned pos)
+{
+	return set ? isl_space_has_dim_name(set->dim, type, pos) : -1;
+}
+
 __isl_give isl_basic_map *isl_basic_map_set_dim_name(
 	__isl_take isl_basic_map *bmap,
 	enum isl_dim_type type, unsigned pos, const char *s)
@@ -499,7 +534,7 @@ __isl_give isl_basic_map *isl_basic_map_set_dim_name(
 	bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s);
 	if (!bmap->dim)
 		goto error;
-	return bmap;
+	return isl_basic_map_finalize(bmap);
 error:
 	isl_basic_map_free(bmap);
 	return NULL;
@@ -550,6 +585,12 @@ int isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap,
 	return bmap ? isl_space_has_dim_id(bmap->dim, type, pos) : -1;
 }
 
+__isl_give isl_id *isl_basic_set_get_dim_id(__isl_keep isl_basic_set *bset,
+	enum isl_dim_type type, unsigned pos)
+{
+	return bset ? isl_space_get_dim_id(bset->dim, type, pos) : NULL;
+}
+
 int isl_map_has_dim_id(__isl_keep isl_map *map,
 	enum isl_dim_type type, unsigned pos)
 {
@@ -1553,8 +1594,8 @@ void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
 }
 
 /* Eliminate the specified n dimensions starting at first from the
- * constraints using Fourier-Motzkin.  The dimensions themselves
- * are not removed.
+ * constraints, without removing the dimensions from the space.
+ * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
  */
 __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
 	enum isl_dim_type type, unsigned first, unsigned n)
@@ -1566,6 +1607,10 @@ __isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
 	if (n == 0)
 		return map;
 
+	if (first + n > isl_map_dim(map, type) || first + n < first)
+		isl_die(map->ctx, isl_error_invalid,
+			"index out of bounds", goto error);
+
 	map = isl_map_cow(map);
 	if (!map)
 		return NULL;
@@ -1582,8 +1627,8 @@ error:
 }
 
 /* Eliminate the specified n dimensions starting at first from the
- * constraints using Fourier-Motzkin.  The dimensions themselves
- * are not removed.
+ * constraints, without removing the dimensions from the space.
+ * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
  */
 __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
 	enum isl_dim_type type, unsigned first, unsigned n)
@@ -1592,8 +1637,8 @@ __isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
 }
 
 /* Eliminate the specified n dimensions starting at first from the
- * constraints using Fourier-Motzkin.  The dimensions themselves
- * are not removed.
+ * constraints, without removing the dimensions from the space.
+ * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
  */
 __isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
 	unsigned first, unsigned n)
@@ -2694,6 +2739,10 @@ __isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap,
 			bmap->n_div, bmap->n_eq, bmap->n_ineq);
 	if (isl_basic_map_is_rational(bmap))
 		res = isl_basic_map_set_rational(res);
+	if (isl_basic_map_plain_is_empty(bmap)) {
+		isl_basic_map_free(bmap);
+		return isl_basic_map_set_to_empty(res);
+	}
 	res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
 	return isl_basic_map_finalize(res);
 }
@@ -4928,6 +4977,25 @@ struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
 					isl_dim_set, dim, value);
 }
 
+static int remove_if_empty(__isl_keep isl_map *map, int i)
+{
+	int empty = isl_basic_map_plain_is_empty(map->p[i]);
+
+	if (empty < 0)
+		return -1;
+	if (!empty)
+		return 0;
+
+	isl_basic_map_free(map->p[i]);
+	if (i != map->n - 1) {
+		ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+		map->p[i] = map->p[map->n - 1];
+	}
+	map->n--;
+
+	return 0;
+}
+
 struct isl_map *isl_map_fix_si(struct isl_map *map,
 		enum isl_dim_type type, unsigned pos, int value)
 {
@@ -4938,9 +5006,9 @@ struct isl_map *isl_map_fix_si(struct isl_map *map,
 		return NULL;
 
 	isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
-	for (i = 0; i < map->n; ++i) {
+	for (i = map->n - 1; i >= 0; --i) {
 		map->p[i] = isl_basic_map_fix_si(map->p[i], type, pos, value);
-		if (!map->p[i])
+		if (remove_if_empty(map, i) < 0)
 			goto error;
 	}
 	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
@@ -5102,6 +5170,92 @@ __isl_give isl_set *isl_set_upper_bound_si(__isl_take isl_set *set,
 	return isl_map_upper_bound_si(set, type, pos, value);
 }
 
+/* Bound the given variable of "bmap" from below (or above is "upper"
+ * is set) to "value".
+ */
+static __isl_give isl_basic_map *basic_map_bound(
+	__isl_take isl_basic_map *bmap,
+	enum isl_dim_type type, unsigned pos, isl_int value, int upper)
+{
+	int j;
+
+	if (!bmap)
+		return NULL;
+	if (pos >= isl_basic_map_dim(bmap, type))
+		isl_die(bmap->ctx, isl_error_invalid,
+			"index out of bounds", goto error);
+	pos += isl_basic_map_offset(bmap, type);
+	bmap = isl_basic_map_cow(bmap);
+	bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
+	j = isl_basic_map_alloc_inequality(bmap);
+	if (j < 0)
+		goto error;
+	isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
+	if (upper) {
+		isl_int_set_si(bmap->ineq[j][pos], -1);
+		isl_int_set(bmap->ineq[j][0], value);
+	} else {
+		isl_int_set_si(bmap->ineq[j][pos], 1);
+		isl_int_neg(bmap->ineq[j][0], value);
+	}
+	bmap = isl_basic_map_simplify(bmap);
+	return isl_basic_map_finalize(bmap);
+error:
+	isl_basic_map_free(bmap);
+	return NULL;
+}
+
+/* Bound the given variable of "map" from below (or above is "upper"
+ * is set) to "value".
+ */
+static __isl_give isl_map *map_bound(__isl_take isl_map *map,
+	enum isl_dim_type type, unsigned pos, isl_int value, int upper)
+{
+	int i;
+
+	map = isl_map_cow(map);
+	if (!map)
+		return NULL;
+
+	if (pos >= isl_map_dim(map, type))
+		isl_die(map->ctx, isl_error_invalid,
+			"index out of bounds", goto error);
+	for (i = map->n - 1; i >= 0; --i) {
+		map->p[i] = basic_map_bound(map->p[i], type, pos, value, upper);
+		if (remove_if_empty(map, i) < 0)
+			goto error;
+	}
+	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	return map;
+error:
+	isl_map_free(map);
+	return NULL;
+}
+
+__isl_give isl_map *isl_map_lower_bound(__isl_take isl_map *map,
+	enum isl_dim_type type, unsigned pos, isl_int value)
+{
+	return map_bound(map, type, pos, value, 0);
+}
+
+__isl_give isl_map *isl_map_upper_bound(__isl_take isl_map *map,
+	enum isl_dim_type type, unsigned pos, isl_int value)
+{
+	return map_bound(map, type, pos, value, 1);
+}
+
+__isl_give isl_set *isl_set_lower_bound(__isl_take isl_set *set,
+	enum isl_dim_type type, unsigned pos, isl_int value)
+{
+	return isl_map_lower_bound(set, type, pos, value);
+}
+
+__isl_give isl_set *isl_set_upper_bound(__isl_take isl_set *set,
+	enum isl_dim_type type, unsigned pos, isl_int value)
+{
+	return isl_map_upper_bound(set, type, pos, value);
+}
+
 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
 					isl_int value)
 {
@@ -6316,7 +6470,7 @@ error:
 /*
  * returns range - domain
  */
-struct isl_set *isl_map_deltas(struct isl_map *map)
+__isl_give isl_set *isl_map_deltas(__isl_take isl_map *map)
 {
 	int i;
 	isl_space *dim;
@@ -6694,6 +6848,12 @@ int isl_basic_map_is_subset(
 	return is_subset;
 }
 
+int isl_basic_set_is_subset(__isl_keep isl_basic_set *bset1,
+	__isl_keep isl_basic_set *bset2)
+{
+	return isl_basic_map_is_subset(bset1, bset2);
+}
+
 int isl_basic_map_is_equal(
 		struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
 {
@@ -6947,7 +7107,7 @@ struct isl_map *isl_basic_map_union(
 {
 	struct isl_map *map;
 	if (!bmap1 || !bmap2)
-		return NULL;
+		goto error;
 
 	isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim), goto error);
 
@@ -7197,16 +7357,8 @@ struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
 	if (!map)
 		return NULL;
 
-	for (i = map->n-1; i >= 0; --i) {
-		if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
-			continue;
-		isl_basic_map_free(map->p[i]);
-		if (i != map->n-1) {
-			ISL_F_CLR(map, ISL_MAP_NORMALIZED);
-			map->p[i] = map->p[map->n-1];
-		}
-		map->n--;
-	}
+	for (i = map->n - 1; i >= 0; --i)
+		remove_if_empty(map, i);
 
 	return map;
 }
@@ -8730,7 +8882,7 @@ int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset,
 		return -1;
 
 	bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset));
-	tab = isl_tab_from_basic_set(bset);
+	tab = isl_tab_from_basic_set(bset, 0);
 	if (!bound || !tab)
 		goto error;
 
@@ -8820,6 +8972,39 @@ int isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap)
 	return 1;
 }
 
+/* Check if the given basic map is single-valued.
+ * We simply compute
+ *
+ *	M \circ M^-1
+ *
+ * and check if the result is a subset of the identity mapping.
+ */
+int isl_basic_map_is_single_valued(__isl_keep isl_basic_map *bmap)
+{
+	isl_space *space;
+	isl_basic_map *test;
+	isl_basic_map *id;
+	int sv;
+
+	sv = isl_basic_map_plain_is_single_valued(bmap);
+	if (sv < 0 || sv)
+		return sv;
+
+	test = isl_basic_map_reverse(isl_basic_map_copy(bmap));
+	test = isl_basic_map_apply_range(test, isl_basic_map_copy(bmap));
+
+	space = isl_basic_map_get_space(bmap);
+	space = isl_space_map_from_set(isl_space_range(space));
+	id = isl_basic_map_identity(space);
+
+	sv = isl_basic_map_is_subset(test, id);
+
+	isl_basic_map_free(test);
+	isl_basic_map_free(id);
+
+	return sv;
+}
+
 /* Check if the given map is obviously single-valued.
  */
 int isl_map_plain_is_single_valued(__isl_keep isl_map *map)
@@ -9333,14 +9518,21 @@ __isl_give isl_basic_map *isl_basic_map_realign(__isl_take isl_basic_map *bmap,
 	__isl_take isl_space *dim, __isl_take struct isl_dim_map *dim_map)
 {
 	isl_basic_map *res;
+	unsigned flags;
 
 	bmap = isl_basic_map_cow(bmap);
 	if (!bmap || !dim || !dim_map)
 		goto error;
 
+	flags = bmap->flags;
+	ISL_FL_CLR(flags, ISL_BASIC_MAP_FINAL);
+	ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED);
+	ISL_FL_CLR(flags, ISL_BASIC_MAP_NORMALIZED_DIVS);
 	res = isl_basic_map_alloc_space(dim,
 			bmap->n_div, bmap->n_eq, bmap->n_ineq);
 	res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
+	if (res)
+		res->flags = flags;
 	res = isl_basic_map_finalize(res);
 	return res;
 error:
@@ -9631,6 +9823,7 @@ __isl_give isl_basic_map *isl_basic_map_zip(__isl_take isl_basic_map *bmap)
 		isl_space_dim(bmap->dim->nested[0], isl_dim_in);
 	n1 = isl_space_dim(bmap->dim->nested[0], isl_dim_out);
 	n2 = isl_space_dim(bmap->dim->nested[1], isl_dim_in);
+	bmap = isl_basic_map_cow(bmap);
 	bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2);
 	if (!bmap)
 		return NULL;
@@ -9677,6 +9870,83 @@ error:
 	return NULL;
 }
 
+/* Can we apply isl_basic_map_curry to "bmap"?
+ * That is, does it have a nested relation in its domain?
+ */
+int isl_basic_map_can_curry(__isl_keep isl_basic_map *bmap)
+{
+	if (!bmap)
+		return -1;
+
+	return isl_space_can_curry(bmap->dim);
+}
+
+/* Can we apply isl_map_curry to "map"?
+ * That is, does it have a nested relation in its domain?
+ */
+int isl_map_can_curry(__isl_keep isl_map *map)
+{
+	if (!map)
+		return -1;
+
+	return isl_space_can_curry(map->dim);
+}
+
+/* Given a basic map (A -> B) -> C, return the corresponding basic map
+ * A -> (B -> C).
+ */
+__isl_give isl_basic_map *isl_basic_map_curry(__isl_take isl_basic_map *bmap)
+{
+
+	if (!bmap)
+		return NULL;
+
+	if (!isl_basic_map_can_curry(bmap))
+		isl_die(bmap->ctx, isl_error_invalid,
+			"basic map cannot be curried", goto error);
+	bmap->dim = isl_space_curry(bmap->dim);
+	if (!bmap->dim)
+		goto error;
+	return bmap;
+error:
+	isl_basic_map_free(bmap);
+	return NULL;
+}
+
+/* Given a map (A -> B) -> C, return the corresponding map
+ * A -> (B -> C).
+ */
+__isl_give isl_map *isl_map_curry(__isl_take isl_map *map)
+{
+	int i;
+
+	if (!map)
+		return NULL;
+
+	if (!isl_map_can_curry(map))
+		isl_die(map->ctx, isl_error_invalid, "map cannot be curried",
+			goto error);
+
+	map = isl_map_cow(map);
+	if (!map)
+		return NULL;
+
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_curry(map->p[i]);
+		if (!map->p[i])
+			goto error;
+	}
+
+	map->dim = isl_space_curry(map->dim);
+	if (!map->dim)
+		goto error;
+
+	return map;
+error:
+	isl_map_free(map);
+	return NULL;
+}
+
 /* Construct a basic map mapping the domain of the affine expression
  * to a one-dimensional range prescribed by the affine expression.
  */
@@ -9712,6 +9982,17 @@ error:
 	return NULL;
 }
 
+/* Construct a map mapping the domain of the affine expression
+ * to a one-dimensional range prescribed by the affine expression.
+ */
+__isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff)
+{
+	isl_basic_map *bmap;
+
+	bmap = isl_basic_map_from_aff(aff);
+	return isl_map_from_basic_map(bmap);
+}
+
 /* Construct a basic map mapping the domain the multi-affine expression
  * to its range, with each dimension in the range equated to the
  * corresponding affine expression.
@@ -9749,6 +10030,18 @@ __isl_give isl_basic_map *isl_basic_map_from_multi_aff(
 	return bmap;
 }
 
+/* Construct a map mapping the domain the multi-affine expression
+ * to its range, with each dimension in the range equated to the
+ * corresponding affine expression.
+ */
+__isl_give isl_map *isl_map_from_multi_aff(__isl_take isl_multi_aff *maff)
+{
+	isl_basic_map *bmap;
+
+	bmap = isl_basic_map_from_multi_aff(maff);
+	return isl_map_from_basic_map(bmap);
+}
+
 /* Construct a basic map mapping a domain in the given space to
  * to an n-dimensional range, with n the number of elements in the list,
  * where each coordinate in the range is prescribed by the
@@ -9789,11 +10082,78 @@ __isl_give isl_set *isl_set_equate(__isl_take isl_set *set,
 	return isl_map_equate(set, type1, pos1, type2, pos2);
 }
 
+/* Construct a basic map where the given dimensions are equal to each other.
+ */
+static __isl_give isl_basic_map *equator(__isl_take isl_space *space,
+	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
+{
+	isl_basic_map *bmap = NULL;
+	int i;
+
+	if (!space)
+		return NULL;
+
+	if (pos1 >= isl_space_dim(space, type1))
+		isl_die(isl_space_get_ctx(space), isl_error_invalid,
+			"index out of bounds", goto error);
+	if (pos2 >= isl_space_dim(space, type2))
+		isl_die(isl_space_get_ctx(space), isl_error_invalid,
+			"index out of bounds", goto error);
+
+	if (type1 == type2 && pos1 == pos2)
+		return isl_basic_map_universe(space);
+
+	bmap = isl_basic_map_alloc_space(isl_space_copy(space), 0, 1, 0);
+	i = isl_basic_map_alloc_equality(bmap);
+	if (i < 0)
+		goto error;
+	isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
+	pos1 += isl_basic_map_offset(bmap, type1);
+	pos2 += isl_basic_map_offset(bmap, type2);
+	isl_int_set_si(bmap->eq[i][pos1], -1);
+	isl_int_set_si(bmap->eq[i][pos2], 1);
+	bmap = isl_basic_map_finalize(bmap);
+	isl_space_free(space);
+	return bmap;
+error:
+	isl_space_free(space);
+	isl_basic_map_free(bmap);
+	return NULL;
+}
+
+/* Add a constraint imposing that the given two dimensions are equal.
+ */
+__isl_give isl_basic_map *isl_basic_map_equate(__isl_take isl_basic_map *bmap,
+	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
+{
+	isl_basic_map *eq;
+
+	eq = equator(isl_basic_map_get_space(bmap), type1, pos1, type2, pos2);
+
+	bmap = isl_basic_map_intersect(bmap, eq);
+
+	return bmap;
+}
+
 /* Add a constraint imposing that the given two dimensions are equal.
  */
 __isl_give isl_map *isl_map_equate(__isl_take isl_map *map,
 	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
 {
+	isl_basic_map *bmap;
+
+	bmap = equator(isl_map_get_space(map), type1, pos1, type2, pos2);
+
+	map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
+
+	return map;
+}
+
+/* Add a constraint imposing that the given two dimensions have opposite values.
+ */
+__isl_give isl_map *isl_map_oppose(__isl_take isl_map *map,
+	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
+{
 	isl_basic_map *bmap = NULL;
 	int i;
 
@@ -9814,7 +10174,7 @@ __isl_give isl_map *isl_map_equate(__isl_take isl_map *map,
 	isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
 	pos1 += isl_basic_map_offset(bmap, type1);
 	pos2 += isl_basic_map_offset(bmap, type2);
-	isl_int_set_si(bmap->eq[i][pos1], -1);
+	isl_int_set_si(bmap->eq[i][pos1], 1);
 	isl_int_set_si(bmap->eq[i][pos2], 1);
 	bmap = isl_basic_map_finalize(bmap);
 
@@ -9827,9 +10187,10 @@ error:
 	return NULL;
 }
 
-/* Add a constraint imposing that the given two dimensions have opposite values.
+/* Add a constraint imposing that the value of the first dimension is
+ * greater than that of the second.
  */
-__isl_give isl_map *isl_map_oppose(__isl_take isl_map *map,
+__isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map,
 	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
 {
 	isl_basic_map *bmap = NULL;
@@ -9845,15 +10206,22 @@ __isl_give isl_map *isl_map_oppose(__isl_take isl_map *map,
 		isl_die(map->ctx, isl_error_invalid,
 			"index out of bounds", goto error);
 
-	bmap = isl_basic_map_alloc_space(isl_map_get_space(map), 0, 1, 0);
-	i = isl_basic_map_alloc_equality(bmap);
+	if (type1 == type2 && pos1 == pos2) {
+		isl_space *space = isl_map_get_space(map);
+		isl_map_free(map);
+		return isl_map_empty(space);
+	}
+
+	bmap = isl_basic_map_alloc_space(isl_map_get_space(map), 0, 0, 1);
+	i = isl_basic_map_alloc_inequality(bmap);
 	if (i < 0)
 		goto error;
-	isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
+	isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
 	pos1 += isl_basic_map_offset(bmap, type1);
 	pos2 += isl_basic_map_offset(bmap, type2);
-	isl_int_set_si(bmap->eq[i][pos1], 1);
-	isl_int_set_si(bmap->eq[i][pos2], 1);
+	isl_int_set_si(bmap->ineq[i][pos1], 1);
+	isl_int_set_si(bmap->ineq[i][pos2], -1);
+	isl_int_set_si(bmap->ineq[i][0], -1);
 	bmap = isl_basic_map_finalize(bmap);
 
 	map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
@@ -9865,6 +10233,15 @@ error:
 	return NULL;
 }
 
+/* Add a constraint imposing that the value of the first dimension is
+ * smaller than that of the second.
+ */
+__isl_give isl_map *isl_map_order_lt(__isl_take isl_map *map,
+	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
+{
+	return isl_map_order_gt(map, type2, pos2, type1, pos1);
+}
+
 __isl_give isl_aff *isl_basic_map_get_div(__isl_keep isl_basic_map *bmap,
 	int pos)
 {
@@ -9994,14 +10371,8 @@ __isl_give isl_set *isl_set_substitute(__isl_take isl_set *set,
 
 	for (i = set->n - 1; i >= 0; --i) {
 		set->p[i] = isl_basic_set_substitute(set->p[i], type, pos, subs);
-		if (!set->p[i])
+		if (remove_if_empty(set, i) < 0)
 			goto error;
-		if (isl_basic_set_plain_is_empty(set->p[i])) {
-			isl_basic_set_free(set->p[i]);
-			if (i != set->n - 1)
-				set->p[i] = set->p[set->n - 1];
-			set->n--;
-		}
 	}
 
 	return set;