X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_coalesce.c;h=22524aa7b64a95d2c5a7b7202b655fb6a3d92d7e;hb=5548aa4b6deb6a95c5781f0547472a713cf01d74;hp=82bd88f5b71013ac7b1f86c6396cd8447bddf93e;hpb=c99c8c9459bb142dcba40d16efe4f88c4bbadd84;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_coalesce.c b/isl_coalesce.c
index 82bd88f..22524aa 100644
--- a/isl_coalesce.c
+++ b/isl_coalesce.c
@@ -11,8 +11,9 @@
  */
 
 #include "isl_map_private.h"
-#include "isl_seq.h"
+#include <isl/seq.h>
 #include "isl_tab.h"
+#include <isl_mat_private.h>
 
 #define STATUS_ERROR		-1
 #define STATUS_REDUNDANT	 1
@@ -270,7 +271,8 @@ static int check_facets(struct isl_map *map, int i, int j,
 	for (k = 0; k < map->p[i]->n_ineq; ++k) {
 		if (ineq_i[k] != STATUS_CUT)
 			continue;
-		tabs[i] = isl_tab_select_facet(tabs[i], n_eq + k);
+		if (isl_tab_select_facet(tabs[i], n_eq + k) < 0)
+			return -1;
 		for (l = 0; l < map->p[j]->n_ineq; ++l) {
 			int stat;
 			if (ineq_j[l] != STATUS_CUT)
@@ -395,7 +397,8 @@ static int is_extension(struct isl_map *map, int i, int j, int k,
 	snap = isl_tab_snap(tabs[i]);
 	tabs[i] = isl_tab_relax(tabs[i], n_eq + k);
 	snap2 = isl_tab_snap(tabs[i]);
-	tabs[i] = isl_tab_select_facet(tabs[i], n_eq + k);
+	if (isl_tab_select_facet(tabs[i], n_eq + k) < 0)
+		return -1;
 	super = contains(map, j, ineq_j, tabs[i]);
 	if (super) {
 		if (isl_tab_rollback(tabs[i], snap2) < 0)
@@ -582,7 +585,8 @@ static int can_wrap_in_facet(struct isl_map *map, int i, int j, int k,
 
 	snap = isl_tab_snap(tabs[i]);
 
-	tabs[i] = isl_tab_select_facet(tabs[i], map->p[i]->n_eq + k);
+	if (isl_tab_select_facet(tabs[i], map->p[i]->n_eq + k) < 0)
+		goto error;
 	if (isl_tab_detect_redundant(tabs[i]) < 0)
 		goto error;
 
@@ -643,7 +647,7 @@ static void set_is_redundant(struct isl_tab *tab, unsigned n_eq,
 	}
 }
 
-/* Given a pair of basic maps i and j such that j stick out
+/* Given a pair of basic maps i and j such that j sticks out
  * of i at n cut constraints, each time by at most one,
  * try to compute wrapping constraints and replace the two
  * basic maps by a single basic map.
@@ -653,7 +657,7 @@ static void set_is_redundant(struct isl_tab *tab, unsigned n_eq,
  * wrapped around their ridges, except those ridges determined
  * by any of the other cut constraints.
  * The intersections of cut constraints need to be ignored
- * as the result of wrapping on cur constraint around another
+ * as the result of wrapping one cut constraint around another
  * would result in a constraint cutting the union.
  * In each case, the facets are wrapped to include the union
  * of the two basic maps.
@@ -700,8 +704,8 @@ static int wrap_in_facets(struct isl_map *map, int i, int j,
 	wraps->n_row = 0;
 
 	for (k = 0; k < n; ++k) {
-		tabs[i] = isl_tab_select_facet(tabs[i],
-						map->p[i]->n_eq + cuts[k]);
+		if (isl_tab_select_facet(tabs[i], map->p[i]->n_eq + cuts[k]) < 0)
+			goto error;
 		if (isl_tab_detect_redundant(tabs[i]) < 0)
 			goto error;
 		set_is_redundant(tabs[i], map->p[i]->n_eq, cuts, n, k, 1);
@@ -719,7 +723,8 @@ static int wrap_in_facets(struct isl_map *map, int i, int j,
 
 		isl_seq_cpy(bound->el, map->p[i]->ineq[cuts[k]], 1 + total);
 		isl_int_add_ui(bound->el[0], bound->el[0], 1);
-		tabs[j] = isl_tab_add_eq(tabs[j], bound->el);
+		if (isl_tab_add_eq(tabs[j], bound->el) < 0)
+			goto error;
 		if (isl_tab_detect_redundant(tabs[j]) < 0)
 			goto error;
 
@@ -750,7 +755,7 @@ error:
 	return -1;
 }
 
-/* Given two basic sets i and j such that i has not cut equalities,
+/* Given two basic sets i and j such that i has no cut equalities,
  * check if relaxing all the cut inequalities of i by one turns
  * them into valid constraint for j and check if we can wrap in
  * the bits that are sticking out.
@@ -813,9 +818,7 @@ static int can_wrap_in_set(struct isl_map *map, int i, int j,
 	struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
 {
 	int changed = 0;
-	int k, l, m;
-	unsigned total = isl_basic_map_total_dim(map->p[i]);
-	struct isl_tab_undo *snap;
+	int k, m;
 	int n;
 	int *cuts = NULL;
 
@@ -934,6 +937,100 @@ static int check_adj_eq(struct isl_map *map, int i, int j,
 	return changed;
 }
 
+/* The two basic maps lie on adjacent hyperplanes.  In particular,
+ * basic map "i" has an equality that lies parallel to basic map "j".
+ * Check if we can wrap the facets around the parallel hyperplanes
+ * to include the other set.
+ *
+ * We perform basically the same operations as can_wrap_in_facet,
+ * except that we don't need to select a facet of one of the sets.
+ *				_
+ *	\\			\\
+ *	 \\		=>	 \\
+ *	  \			  \|
+ *
+ * We only allow one equality of "i" to be adjacent to an equality of "j"
+ * to avoid coalescing
+ *
+ *	[m, n] -> { [x, y] -> [x, 1 + y] : x >= 1 and y >= 1 and
+ *					    x <= 10 and y <= 10;
+ *		    [x, y] -> [1 + x, y] : x >= 1 and x <= 20 and
+ *					    y >= 5 and y <= 15 }
+ *
+ * to
+ *
+ *	[m, n] -> { [x, y] -> [x2, y2] : x >= 1 and 10y2 <= 20 - x + 10y and
+ *					4y2 >= 5 + 3y and 5y2 <= 15 + 4y and
+ *					y2 <= 1 + x + y - x2 and y2 >= y and
+ *					y2 >= 1 + x + y - x2 }
+ */
+static int check_eq_adj_eq(struct isl_map *map, int i, int j,
+	struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
+{
+	int k;
+	int changed = 0;
+	struct isl_mat *wraps = NULL;
+	struct isl_set *set_i = NULL;
+	struct isl_set *set_j = NULL;
+	struct isl_vec *bound = NULL;
+	unsigned total = isl_basic_map_total_dim(map->p[i]);
+
+	if (count(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ) != 1)
+		return 0;
+
+	for (k = 0; k < 2 * map->p[i]->n_eq ; ++k)
+		if (eq_i[k] == STATUS_ADJ_EQ)
+			break;
+
+	set_i = set_from_updated_bmap(map->p[i], tabs[i]);
+	set_j = set_from_updated_bmap(map->p[j], tabs[j]);
+	wraps = isl_mat_alloc(map->ctx, 2 * (map->p[i]->n_eq + map->p[j]->n_eq) +
+					map->p[i]->n_ineq + map->p[j]->n_ineq,
+					1 + total);
+	bound = isl_vec_alloc(map->ctx, 1 + total);
+	if (!set_i || !set_j || !wraps || !bound)
+		goto error;
+
+	if (k % 2 == 0)
+		isl_seq_neg(bound->el, map->p[i]->eq[k / 2], 1 + total);
+	else
+		isl_seq_cpy(bound->el, map->p[i]->eq[k / 2], 1 + total);
+	isl_int_add_ui(bound->el[0], bound->el[0], 1);
+
+	isl_seq_cpy(wraps->row[0], bound->el, 1 + total);
+	wraps->n_row = 1;
+
+	if (add_wraps(wraps, map->p[j], tabs[j], bound->el, set_i) < 0)
+		goto error;
+	if (!wraps->n_row)
+		goto unbounded;
+
+	isl_int_sub_ui(bound->el[0], bound->el[0], 1);
+	isl_seq_neg(bound->el, bound->el, 1 + total);
+
+	isl_seq_cpy(wraps->row[wraps->n_row], bound->el, 1 + total);
+	wraps->n_row++;
+
+	if (add_wraps(wraps, map->p[i], tabs[i], bound->el, set_j) < 0)
+		goto error;
+	if (!wraps->n_row)
+		goto unbounded;
+
+	changed = fuse(map, i, j, tabs, eq_i, ineq_i, eq_j, ineq_j, wraps);
+
+	if (0) {
+error:		changed = -1;
+	}
+unbounded:
+
+	isl_mat_free(wraps);
+	isl_set_free(set_i);
+	isl_set_free(set_j);
+	isl_vec_free(bound);
+
+	return changed;
+}
+
 /* Check if the union of the given pair of basic maps
  * can be represented by a single basic map.
  * If so, replace the pair by the single basic map and return 1.
@@ -956,7 +1053,7 @@ static int check_adj_eq(struct isl_map *map, int i, int j,
  *	adj_ineq	the given constraint is adjacent (on the outside)
  *			to an inequality of the other basic map
  *
- * We consider six cases in which we can replace the pair by a single
+ * We consider seven cases in which we can replace the pair by a single
  * basic map.  We ignore all "redundant" constraints.
  *
  *	1. all constraints of one basic map are valid
@@ -994,11 +1091,15 @@ static int check_adj_eq(struct isl_map *map, int i, int j,
  *	   Moreover, the facets corresponding to the cut constraints and
  *	   the pieces of the other basic map at offset one from these cut
  *	   constraints can be wrapped around their ridges to include
- *	   the unione of the two basic maps
+ *	   the union of the two basic maps
  *		=> the pair can be replaced by a basic map consisting
  *		   of the valid constraints in both basic maps together
  *		   with all wrapping constraints
  *
+ *	7. the two basic maps live in adjacent hyperplanes.  In principle
+ *	   such sets can always be combined through wrapping, but we impose
+ *	   that there is only one such pair, to avoid overeager coalescing.
+ *
  * Throughout the computation, we maintain a collection of tableaus
  * corresponding to the basic maps.  When the basic maps are dropped
  * or combined, the tableaus are modified accordingly.
@@ -1013,24 +1114,32 @@ static int coalesce_pair(struct isl_map *map, int i, int j,
 	int *ineq_j = NULL;
 
 	eq_i = eq_status_in(map, i, j, tabs);
+	if (!eq_i)
+		goto error;
 	if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ERROR))
 		goto error;
 	if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_SEPARATE))
 		goto done;
 
 	eq_j = eq_status_in(map, j, i, tabs);
+	if (!eq_j)
+		goto error;
 	if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ERROR))
 		goto error;
 	if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_SEPARATE))
 		goto done;
 
 	ineq_i = ineq_status_in(map, i, j, tabs);
+	if (!ineq_i)
+		goto error;
 	if (any(ineq_i, map->p[i]->n_ineq, STATUS_ERROR))
 		goto error;
 	if (any(ineq_i, map->p[i]->n_ineq, STATUS_SEPARATE))
 		goto done;
 
 	ineq_j = ineq_status_in(map, j, i, tabs);
+	if (!ineq_j)
+		goto error;
 	if (any(ineq_j, map->p[j]->n_ineq, STATUS_ERROR))
 		goto error;
 	if (any(ineq_j, map->p[j]->n_ineq, STATUS_SEPARATE))
@@ -1044,9 +1153,12 @@ static int coalesce_pair(struct isl_map *map, int i, int j,
 		   all(ineq_j, map->p[j]->n_ineq, STATUS_VALID)) {
 		drop(map, i, tabs);
 		changed = 1;
-	} else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ) ||
-		   any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_EQ)) {
-		/* ADJ EQ PAIR */
+	} else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ)) {
+		changed = check_eq_adj_eq(map, i, j, tabs,
+					eq_i, ineq_i, eq_j, ineq_j);
+	} else if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_EQ)) {
+		changed = check_eq_adj_eq(map, j, i, tabs,
+					eq_j, ineq_j, eq_i, ineq_i);
 	} else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) ||
 		   any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) {
 		changed = check_adj_eq(map, i, j, tabs,
@@ -1132,7 +1244,8 @@ struct isl_map *isl_map_coalesce(struct isl_map *map)
 		if (!tabs[i])
 			goto error;
 		if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT))
-			tabs[i] = isl_tab_detect_implicit_equalities(tabs[i]);
+			if (isl_tab_detect_implicit_equalities(tabs[i]) < 0)
+				goto error;
 		if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT))
 			if (isl_tab_detect_redundant(tabs[i]) < 0)
 				goto error;