X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=0704f5d5b551bbfb9ee9b7a4fd8702dc73505323;hb=02e7fd8c33c9f68d4ca56484ddba40d4706ef149;hp=d30f27a1e6db22a5e5189c926b63552bc7764cbf;hpb=b4ecaa0b8be9556b5f469c5dbf2016ee07b045e5;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_map.c b/isl_map.c
index d30f27a..0704f5d 100644
--- a/isl_map.c
+++ b/isl_map.c
@@ -690,6 +690,76 @@ int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
 	return isl_basic_map_is_rational(bset);
 }
 
+/* Does "bmap" contain any rational points?
+ *
+ * If "bmap" has an equality for each dimension, equating the dimension
+ * to an integer constant, then it has no rational points, even if it
+ * is marked as rational.
+ */
+int isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap)
+{
+	int has_rational = 1;
+	unsigned total;
+
+	if (!bmap)
+		return -1;
+	if (isl_basic_map_plain_is_empty(bmap))
+		return 0;
+	if (!isl_basic_map_is_rational(bmap))
+		return 0;
+	bmap = isl_basic_map_copy(bmap);
+	bmap = isl_basic_map_implicit_equalities(bmap);
+	if (!bmap)
+		return -1;
+	total = isl_basic_map_total_dim(bmap);
+	if (bmap->n_eq == total) {
+		int i, j;
+		for (i = 0; i < bmap->n_eq; ++i) {
+			j = isl_seq_first_non_zero(bmap->eq[i] + 1, total);
+			if (j < 0)
+				break;
+			if (!isl_int_is_one(bmap->eq[i][1 + j]) &&
+			    !isl_int_is_negone(bmap->eq[i][1 + j]))
+				break;
+			j = isl_seq_first_non_zero(bmap->eq[i] + 1 + j + 1,
+						    total - j - 1);
+			if (j >= 0)
+				break;
+		}
+		if (i == bmap->n_eq)
+			has_rational = 0;
+	}
+	isl_basic_map_free(bmap);
+
+	return has_rational;
+}
+
+/* Does "map" contain any rational points?
+ */
+int isl_map_has_rational(__isl_keep isl_map *map)
+{
+	int i;
+	int has_rational;
+
+	if (!map)
+		return -1;
+	for (i = 0; i < map->n; ++i) {
+		has_rational = isl_basic_map_has_rational(map->p[i]);
+		if (has_rational < 0)
+			return -1;
+		if (has_rational)
+			return 1;
+	}
+	return 0;
+}
+
+/* Does "set" contain any rational points?
+ */
+int isl_set_has_rational(__isl_keep isl_set *set)
+{
+	return isl_map_has_rational(set);
+}
+
 /* Is this basic set a parameter domain?
  */
 int isl_basic_set_is_params(__isl_keep isl_basic_set *bset)
@@ -946,9 +1016,9 @@ void *isl_basic_map_free(__isl_take isl_basic_map *bmap)
 	return NULL;
 }
 
-void isl_basic_set_free(struct isl_basic_set *bset)
+void *isl_basic_set_free(struct isl_basic_set *bset)
 {
-	isl_basic_map_free((struct isl_basic_map *)bset);
+	return isl_basic_map_free((struct isl_basic_map *)bset);
 }
 
 static int room_for_con(struct isl_basic_map *bmap, unsigned n)
@@ -2133,6 +2203,14 @@ __isl_give isl_basic_map *isl_basic_map_remove_unknown_divs(
 	return bmap;
 }
 
+/* Remove all divs that are unknown or defined in terms of unknown divs.
+ */
+__isl_give isl_basic_set *isl_basic_set_remove_unknown_divs(
+	__isl_take isl_basic_set *bset)
+{
+	return isl_basic_map_remove_unknown_divs(bset);
+}
+
 __isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
 {
 	int i;
@@ -2786,12 +2864,14 @@ static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1,
 	if (!map1 || !map2)
 		goto error;
 
-	if (isl_map_plain_is_empty(map1) &&
+	if ((isl_map_plain_is_empty(map1) ||
+	     isl_map_plain_is_universe(map2)) &&
 	    isl_space_is_equal(map1->dim, map2->dim)) {
 		isl_map_free(map2);
 		return map1;
 	}
-	if (isl_map_plain_is_empty(map2) &&
+	if ((isl_map_plain_is_empty(map2) ||
+	     isl_map_plain_is_universe(map1)) &&
 	    isl_space_is_equal(map1->dim, map2->dim)) {
 		isl_map_free(map1);
 		return map2;
@@ -4180,6 +4260,11 @@ int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
 							bmap->div[div]);
 }
 
+int isl_basic_set_add_div_constraints(struct isl_basic_set *bset, unsigned div)
+{
+	return isl_basic_map_add_div_constraints(bset, div);
+}
+
 struct isl_basic_set *isl_basic_map_underlying_set(
 		struct isl_basic_map *bmap)
 {
@@ -5059,21 +5144,23 @@ error:
 	return NULL;
 }
 
-void isl_map_free(struct isl_map *map)
+void *isl_map_free(struct isl_map *map)
 {
 	int i;
 
 	if (!map)
-		return;
+		return NULL;
 
 	if (--map->ref > 0)
-		return;
+		return NULL;
 
 	isl_ctx_deref(map->ctx);
 	for (i = 0; i < map->n; ++i)
 		isl_basic_map_free(map->p[i]);
 	isl_space_free(map->dim);
 	free(map);
+
+	return NULL;
 }
 
 struct isl_map *isl_map_extend(struct isl_map *base,
@@ -5328,6 +5415,15 @@ __isl_give isl_basic_map *isl_basic_map_lower_bound_si(
 	return basic_map_bound_si(bmap, type, pos, value, 0);
 }
 
+/* Constrain the values of the given dimension to be no greater than "value".
+ */
+__isl_give isl_basic_map *isl_basic_map_upper_bound_si(
+	__isl_take isl_basic_map *bmap,
+	enum isl_dim_type type, unsigned pos, int value)
+{
+	return basic_map_bound_si(bmap, type, pos, value, 1);
+}
+
 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
 	unsigned dim, isl_int value)
 {
@@ -6425,12 +6521,23 @@ error:
 	return NULL;
 }
 
+/* Return the union of "map1" and "map2", where we assume for now that
+ * "map1" and "map2" are disjoint.  Note that the basic maps inside
+ * "map1" or "map2" may not be disjoint from each other.
+ * Also note that this function is also called from isl_map_union,
+ * which takes care of handling the situation where "map1" and "map2"
+ * may not be disjoint.
+ *
+ * If one of the inputs is empty, we can simply return the other input.
+ * Similarly, if one of the inputs is universal, then it is equal to the union.
+ */
 static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1,
 	__isl_take isl_map *map2)
 {
 	int i;
 	unsigned flags = 0;
 	struct isl_map *map = NULL;
+	int is_universe;
 
 	if (!map1 || !map2)
 		goto error;
@@ -6444,6 +6551,22 @@ static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1,
 		return map1;
 	}
 
+	is_universe = isl_map_plain_is_universe(map1);
+	if (is_universe < 0)
+		goto error;
+	if (is_universe) {
+		isl_map_free(map2);
+		return map1;
+	}
+
+	is_universe = isl_map_plain_is_universe(map2);
+	if (is_universe < 0)
+		goto error;
+	if (is_universe) {
+		isl_map_free(map1);
+		return map2;
+	}
+
 	isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);
 
 	if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
@@ -6506,25 +6629,20 @@ struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
 		isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
 }
 
-static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map,
-	__isl_take isl_set *set)
+/* Apply "fn" to pairs of elements from "map" and "set" and collect
+ * the results.
+ *
+ * "map" and "set" are assumed to be compatible and non-NULL.
+ */
+static __isl_give isl_map *map_intersect_set(__isl_take isl_map *map,
+	__isl_take isl_set *set,
+	__isl_give isl_basic_map *fn(__isl_take isl_basic_map *bmap,
+		__isl_take isl_basic_set *bset))
 {
 	unsigned flags = 0;
 	struct isl_map *result;
 	int i, j;
 
-	if (!map || !set)
-		goto error;
-
-	if (!isl_space_match(map->dim, isl_dim_param, set->dim, isl_dim_param))
-		isl_die(set->ctx, isl_error_invalid,
-			"parameters don't match", goto error);
-
-	if (isl_space_dim(set->dim, isl_dim_set) != 0 &&
-	    !isl_map_compatible_range(map, set))
-		isl_die(set->ctx, isl_error_invalid,
-			"incompatible spaces", goto error);
-
 	if (isl_set_plain_is_universe(set)) {
 		isl_set_free(set);
 		return map;
@@ -6536,20 +6654,31 @@ static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map,
 
 	result = isl_map_alloc_space(isl_space_copy(map->dim),
 					map->n * set->n, flags);
-	if (!result)
-		goto error;
-	for (i = 0; i < map->n; ++i)
+	for (i = 0; result && i < map->n; ++i)
 		for (j = 0; j < set->n; ++j) {
 			result = isl_map_add_basic_map(result,
-			    isl_basic_map_intersect_range(
-				isl_basic_map_copy(map->p[i]),
-				isl_basic_set_copy(set->p[j])));
+					fn(isl_basic_map_copy(map->p[i]),
+					    isl_basic_set_copy(set->p[j])));
 			if (!result)
-				goto error;
+				break;
 		}
+
 	isl_map_free(map);
 	isl_set_free(set);
 	return result;
+}
+
+static __isl_give isl_map *map_intersect_range(__isl_take isl_map *map,
+	__isl_take isl_set *set)
+{
+	if (!map || !set)
+		goto error;
+
+	if (!isl_map_compatible_range(map, set))
+		isl_die(set->ctx, isl_error_invalid,
+			"incompatible spaces", goto error);
+
+	return map_intersect_set(map, set, &isl_basic_map_intersect_range);
 error:
 	isl_map_free(map);
 	isl_set_free(set);
@@ -6562,11 +6691,28 @@ __isl_give isl_map *isl_map_intersect_range(__isl_take isl_map *map,
 	return isl_map_align_params_map_map_and(map, set, &map_intersect_range);
 }
 
-struct isl_map *isl_map_intersect_domain(
-		struct isl_map *map, struct isl_set *set)
+static __isl_give isl_map *map_intersect_domain(__isl_take isl_map *map,
+	__isl_take isl_set *set)
+{
+	if (!map || !set)
+		goto error;
+
+	if (!isl_map_compatible_domain(map, set))
+		isl_die(set->ctx, isl_error_invalid,
+			"incompatible spaces", goto error);
+
+	return map_intersect_set(map, set, &isl_basic_map_intersect_domain);
+error:
+	isl_map_free(map);
+	isl_set_free(set);
+	return NULL;
+}
+
+__isl_give isl_map *isl_map_intersect_domain(__isl_take isl_map *map,
+	__isl_take isl_set *set)
 {
-	return isl_map_reverse(
-		isl_map_intersect_range(isl_map_reverse(map), set));
+	return isl_map_align_params_map_map_and(map, set,
+						&map_intersect_domain);
 }
 
 static __isl_give isl_map *map_apply_domain(__isl_take isl_map *map1,
@@ -7247,6 +7393,9 @@ int isl_basic_map_is_empty(struct isl_basic_map *bmap)
 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
 		return 1;
 
+	if (isl_basic_map_is_universe(bmap))
+		return 0;
+
 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
 		struct isl_basic_map *copy = isl_basic_map_copy(bmap);
 		copy = isl_basic_map_remove_redundancies(copy);
@@ -8132,8 +8281,7 @@ int isl_basic_set_plain_cmp(const __isl_keep isl_basic_set *bset1,
 	return isl_basic_map_plain_cmp(bset1, bset2);
 }
 
-int isl_set_plain_cmp(const __isl_keep isl_set *set1,
-	const __isl_keep isl_set *set2)
+int isl_set_plain_cmp(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
 {
 	int i, cmp;
 
@@ -10215,6 +10363,78 @@ error:
 	return NULL;
 }
 
+/* Can we apply isl_basic_map_uncurry to "bmap"?
+ * That is, does it have a nested relation in its domain?
+ */
+int isl_basic_map_can_uncurry(__isl_keep isl_basic_map *bmap)
+{
+	if (!bmap)
+		return -1;
+
+	return isl_space_can_uncurry(bmap->dim);
+}
+
+/* Can we apply isl_map_uncurry to "map"?
+ * That is, does it have a nested relation in its domain?
+ */
+int isl_map_can_uncurry(__isl_keep isl_map *map)
+{
+	if (!map)
+		return -1;
+
+	return isl_space_can_uncurry(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_uncurry(__isl_take isl_basic_map *bmap)
+{
+
+	if (!bmap)
+		return NULL;
+
+	if (!isl_basic_map_can_uncurry(bmap))
+		isl_die(bmap->ctx, isl_error_invalid,
+			"basic map cannot be uncurried",
+			return isl_basic_map_free(bmap));
+	bmap->dim = isl_space_uncurry(bmap->dim);
+	if (!bmap->dim)
+		return isl_basic_map_free(bmap);
+	return bmap;
+}
+
+/* Given a map A -> (B -> C), return the corresponding map
+ * (A -> B) -> C.
+ */
+__isl_give isl_map *isl_map_uncurry(__isl_take isl_map *map)
+{
+	int i;
+
+	if (!map)
+		return NULL;
+
+	if (!isl_map_can_uncurry(map))
+		isl_die(map->ctx, isl_error_invalid, "map cannot be uncurried",
+			return isl_map_free(map));
+
+	map = isl_map_cow(map);
+	if (!map)
+		return NULL;
+
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_uncurry(map->p[i]);
+		if (!map->p[i])
+			return isl_map_free(map);
+	}
+
+	map->dim = isl_space_uncurry(map->dim);
+	if (!map->dim)
+		return isl_map_free(map);
+
+	return map;
+}
+
 /* Construct a basic map mapping the domain of the affine expression
  * to a one-dimensional range prescribed by the affine expression.
  */
@@ -10456,6 +10676,37 @@ error:
 }
 
 /* Add a constraint imposing that the value of the first dimension is
+ * greater than or equal to that of the second.
+ */
+__isl_give isl_basic_map *isl_basic_map_order_ge(__isl_take isl_basic_map *bmap,
+	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
+{
+	isl_constraint *c;
+	isl_local_space *ls;
+
+	if (!bmap)
+		return NULL;
+
+	if (pos1 >= isl_basic_map_dim(bmap, type1))
+		isl_die(bmap->ctx, isl_error_invalid,
+			"index out of bounds", return isl_basic_map_free(bmap));
+	if (pos2 >= isl_basic_map_dim(bmap, type2))
+		isl_die(bmap->ctx, isl_error_invalid,
+			"index out of bounds", return isl_basic_map_free(bmap));
+
+	if (type1 == type2 && pos1 == pos2)
+		return bmap;
+
+	ls = isl_local_space_from_space(isl_basic_map_get_space(bmap));
+	c = isl_inequality_alloc(ls);
+	c = isl_constraint_set_coefficient_si(c, type1, pos1, 1);
+	c = isl_constraint_set_coefficient_si(c, type2, pos2, -1);
+	bmap = isl_basic_map_add_constraint(bmap, c);
+
+	return bmap;
+}
+
+/* Add a constraint imposing that the value of the first dimension is
  * greater than that of the second.
  */
 __isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map,