X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_convex_hull.c;h=17212c36d5c94d000ac28547d59a0dc1e249293b;hb=c9c6724ca91df2ef1819e5c9f55a8ceef2588daa;hp=58c8014cc3f82cc9494b909c7918390feca4fa54;hpb=cf06bf41b213f72dd4a6d8ac8d13e6b7d36b7bda;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_convex_hull.c b/isl_convex_hull.c
index 58c8014..17212c3 100644
--- a/isl_convex_hull.c
+++ b/isl_convex_hull.c
@@ -869,13 +869,18 @@ static int isl_basic_set_is_bounded(struct isl_basic_set *bset)
 	struct isl_tab *tab;
 	int bounded;
 
+	if (!bset)
+		return -1;
+	if (isl_basic_set_fast_is_empty(bset))
+		return 1;
+
 	tab = isl_tab_from_recession_cone(bset);
 	bounded = isl_tab_cone_is_bounded(tab);
 	isl_tab_free(tab);
 	return bounded;
 }
 
-static int isl_set_is_bounded(struct isl_set *set)
+int isl_set_is_bounded(__isl_keep isl_set *set)
 {
 	int i;
 
@@ -1086,7 +1091,7 @@ error:
  * (including the "positivity constraint" 1 >= 0) and \alpha_{ij}
  * strictly positive numbers.  For simplicity we impose \alpha_{ij} >= 1.
  * We first set up an LP with as variables the \alpha{ij}.
- * In this formulateion, for each polyhedron i,
+ * In this formulation, for each polyhedron i,
  * the first constraint is the positivity constraint, followed by pairs
  * of variables for the equalities, followed by variables for the inequalities.
  * We then simply pick a feasible solution and compute s using (*).
@@ -1137,7 +1142,7 @@ static struct isl_vec *valid_direction(
 				bset1->ctx->one, dir->block.data,
 				sample->block.data[n++], bset1->ineq[i], 1 + d);
 	isl_vec_free(sample);
-	isl_seq_normalize(bset1->ctx, dir->block.data + 1, dir->size - 1);
+	isl_seq_normalize(bset1->ctx, dir->el, dir->size);
 	isl_basic_set_free(bset1);
 	isl_basic_set_free(bset2);
 	return dir;
@@ -1279,18 +1284,47 @@ error:
 	return NULL;
 }
 
+static struct isl_basic_set *uset_convex_hull_wrap(struct isl_set *set);
+static struct isl_basic_set *modulo_affine_hull(
+	struct isl_set *set, struct isl_basic_set *affine_hull);
+
 /* Compute the convex hull of a pair of basic sets without any parameters or
  * integer divisions.
  *
+ * This function is called from uset_convex_hull_unbounded, which
+ * means that the complete convex hull is unbounded.  Some pairs
+ * of basic sets may still be bounded, though.
+ * They may even lie inside a lower dimensional space, in which
+ * case they need to be handled inside their affine hull since
+ * the main algorithm assumes that the result is full-dimensional.
+ *
  * If the convex hull of the two basic sets would have a non-trivial
  * lineality space, we first project out this lineality space.
  */
 static struct isl_basic_set *convex_hull_pair(struct isl_basic_set *bset1,
 	struct isl_basic_set *bset2)
 {
-	struct isl_basic_set *lin;
+	isl_basic_set *lin, *aff;
+	int bounded1, bounded2;
+
+	aff = isl_set_affine_hull(isl_basic_set_union(isl_basic_set_copy(bset1),
+						    isl_basic_set_copy(bset2)));
+	if (!aff)
+		goto error;
+	if (aff->n_eq != 0) 
+		return modulo_affine_hull(isl_basic_set_union(bset1, bset2), aff);
+	isl_basic_set_free(aff);
+
+	bounded1 = isl_basic_set_is_bounded(bset1);
+	bounded2 = isl_basic_set_is_bounded(bset2);
+
+	if (bounded1 < 0 || bounded2 < 0)
+		goto error;
+
+	if (bounded1 && bounded2)
+		uset_convex_hull_wrap(isl_basic_set_union(bset1, bset2));
 
-	if (isl_basic_set_is_bounded(bset1) || isl_basic_set_is_bounded(bset2))
+	if (bounded1 || bounded2)
 		return convex_hull_pair_pointed(bset1, bset2);
 
 	lin = induced_lineality_space(isl_basic_set_copy(bset1),
@@ -1790,7 +1824,7 @@ error:
  * convex hull of the transformed set and then add the equalities back
  * (after performing the inverse transformation.
  */
-static struct isl_basic_set *modulo_affine_hull(struct isl_ctx *ctx,
+static struct isl_basic_set *modulo_affine_hull(
 	struct isl_set *set, struct isl_basic_set *affine_hull)
 {
 	struct isl_mat *T;
@@ -1849,7 +1883,7 @@ struct isl_basic_map *isl_map_convex_hull(struct isl_map *map)
 	if (!affine_hull)
 		goto error;
 	if (affine_hull->n_eq != 0)
-		bset = modulo_affine_hull(ctx, set, affine_hull);
+		bset = modulo_affine_hull(set, affine_hull);
 	else {
 		isl_basic_set_free(affine_hull);
 		bset = uset_convex_hull(set);
@@ -2021,7 +2055,7 @@ static int is_bound(struct sh_data *data, struct isl_set *set, int j,
 
 	isl_int_clear(opt);
 
-	return res == isl_lp_ok ? 1 :
+	return (res == isl_lp_ok || res == isl_lp_empty) ? 1 :
 	       res == isl_lp_unbounded ? 0 : -1;
 }
 
@@ -2142,11 +2176,11 @@ static struct isl_basic_set *add_bounds(struct isl_basic_set *bset,
 	for (j = 0; j < set->p[i]->n_eq; ++j) {
 		for (k = 0; k < 2; ++k) {
 			isl_seq_neg(set->p[i]->eq[j], set->p[i]->eq[j], 1+dim);
-			add_bound(bset, data, set, i, set->p[i]->eq[j]);
+			bset = add_bound(bset, data, set, i, set->p[i]->eq[j]);
 		}
 	}
 	for (j = 0; j < set->p[i]->n_ineq; ++j)
-		add_bound(bset, data, set, i, set->p[i]->ineq[j]);
+		bset = add_bound(bset, data, set, i, set->p[i]->ineq[j]);
 	return bset;
 }