isl_map_transitive_closure: break early if input map doesn't compose with itself

[platform/upstream/isl.git] / isl_transitive_closure.c

diff --git a/isl_transitive_closure.c b/isl_transitive_closure.c
index afb7398..ba7153b 100644 (file)
--- a/isl_transitive_closure.c
+++ b/isl_transitive_closure.c
@@ -556,6 +556,7 @@ static __isl_give isl_map *construct_extended_path(__isl_take isl_dim *dim,
                if (j < d) {
                        path = isl_map_apply_range(path,
                                path_along_delta(isl_dim_copy(dim), delta));
+                       path = isl_map_coalesce(path);
                } else {
                        isl_basic_set_free(delta);
                        ++n;
@@ -609,6 +610,7 @@ static __isl_give isl_map *construct_component(__isl_take isl_dim *dim,
 {
        struct isl_set *domain = NULL;
        struct isl_set *range = NULL;
+       struct isl_set *overlap;
        struct isl_map *app = NULL;
        struct isl_map *path = NULL;
 
@@ -616,6 +618,20 @@ static __isl_give isl_map *construct_component(__isl_take isl_dim *dim,
        domain = isl_set_coalesce(domain);
        range = isl_map_range(isl_map_copy(map));
        range = isl_set_coalesce(range);
+       overlap = isl_set_intersect(isl_set_copy(domain), isl_set_copy(range));
+       if (isl_set_is_empty(overlap) == 1) {
+               isl_set_free(domain);
+               isl_set_free(range);
+               isl_set_free(overlap);
+               isl_dim_free(dim);
+
+               map = isl_map_copy(map);
+               map = isl_map_add(map, isl_dim_in, 1);
+               map = isl_map_add(map, isl_dim_out, 1);
+               map = set_path_length(map, 1, 1);
+               return map;
+       }
+       isl_set_free(overlap);
        app = isl_map_from_domain_and_range(domain, range);
        app = isl_map_add(app, isl_dim_in, 1);
        app = isl_map_add(app, isl_dim_out, 1);
@@ -716,31 +732,28 @@ error:
  *
  *     R_1 \circ R_2
  *
- * is non-empty and that moreover, it is non-empty on the set
- * of elements that do not get mapped to the same set of elements
- * by both "R_1 \circ R_2" and "R_2 \circ R_1".
- * For elements that do get mapped to the same elements by these
- * two compositions, R_1 and R_2 are commutative, so if these
- * elements are the only ones for which R_1 \circ R_2 is non-empty,
- * then you may just as well apply R_1 first.
+ * is a subset of
+ *
+ *     R_2 \circ R_1
+ *
+ * If so, then there is no reason for R_1 to immediately follow R_2
+ * in any path.
  */
 static int basic_map_follows(__isl_keep isl_basic_map *bmap1,
        __isl_keep isl_basic_map *bmap2)
 {
        struct isl_map *map12 = NULL;
        struct isl_map *map21 = NULL;
-       struct isl_map *d = NULL;
-       struct isl_set *dom = NULL;
-       int empty;
+       int subset;
 
        map21 = isl_map_from_basic_map(
                        isl_basic_map_apply_range(
                                isl_basic_map_copy(bmap2),
                                isl_basic_map_copy(bmap1)));
-       empty = isl_map_is_empty(map21);
-       if (empty < 0)
+       subset = isl_map_is_empty(map21);
+       if (subset < 0)
                goto error;
-       if (empty) {
+       if (subset) {
                isl_map_free(map21);
                return 0;
        }
@@ -749,18 +762,13 @@ static int basic_map_follows(__isl_keep isl_basic_map *bmap1,
                        isl_basic_map_apply_range(
                                isl_basic_map_copy(bmap1),
                                isl_basic_map_copy(bmap2)));
-       d = isl_map_subtract(isl_map_copy(map12), isl_map_copy(map21));
-       d = isl_map_union(d,
-               isl_map_subtract(isl_map_copy(map21), isl_map_copy(map12)));
-       dom = isl_map_domain(d);
 
-       map21 = isl_map_intersect_domain(map21, dom);
-       empty = isl_map_is_empty(map21);
+       subset = isl_map_is_subset(map21, map12);
 
        isl_map_free(map12);
        isl_map_free(map21);
 
-       return empty < 0 ? -1 : !empty;
+       return subset < 0 ? -1 : !subset;
 error:
        isl_map_free(map21);
        return -1;