isl_map_convex_hull: handle non full-dimensional pairs of basic sets

diff --git a/isl_convex_hull.c b/isl_convex_hull.c
index 834d278..23a7981 100644 (file)
--- a/isl_convex_hull.c
+++ b/isl_convex_hull.c
@@ -1280,6 +1280,8 @@ error:
 }
 
 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.
@@ -1287,6 +1289,9 @@ static struct isl_basic_set *uset_convex_hull_wrap(struct isl_set *set);
  * 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.
@@ -1294,9 +1299,17 @@ static struct isl_basic_set *uset_convex_hull_wrap(struct isl_set *set);
 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);
 

diff --git a/isl_test.c b/isl_test.c
index 36dc39f..d6b6f1b 100644 (file)
--- a/isl_test.c
+++ b/isl_test.c
@@ -482,6 +482,9 @@ void test_convex_hull_case(struct isl_ctx *ctx, const char *name)
 
 void test_convex_hull(struct isl_ctx *ctx)
 {
+       const char *str1, *str2;
+       isl_set *set1, *set2;
+
        test_convex_hull_case(ctx, "convex0");
        test_convex_hull_case(ctx, "convex1");
        test_convex_hull_case(ctx, "convex2");
@@ -498,6 +501,17 @@ void test_convex_hull(struct isl_ctx *ctx)
        test_convex_hull_case(ctx, "convex13");
        test_convex_hull_case(ctx, "convex14");
        test_convex_hull_case(ctx, "convex15");
+
+       str1 = "{ [i0, i1, i2] : (i2 = 1 and i0 = 0 and i1 >= 0) or "
+              "(i0 = 1 and i1 = 0 and i2 = 1) or "
+              "(i0 = 0 and i1 = 0 and i2 = 0) }";
+       str2 = "{ [i0, i1, i2] : i0 >= 0 and i2 >= i0 and i2 <= 1 and i1 >= 0 }";
+       set1 = isl_set_read_from_str(ctx, str1, -1);
+       set2 = isl_set_read_from_str(ctx, str2, -1);
+       set1 = isl_set_from_basic_set(isl_set_convex_hull(set1));
+       assert(isl_set_is_equal(set1, set2));
+       isl_set_free(set1);
+       isl_set_free(set2);
 }
 
 void test_gist_case(struct isl_ctx *ctx, const char *name)