add isl_union_map_intersect_range

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

diff --git a/isl_map_simplify.c b/isl_map_simplify.c
index 7326f3a..a82f239 100644 (file)
--- a/isl_map_simplify.c
+++ b/isl_map_simplify.c
@@ -12,6 +12,8 @@
 #include "isl_map_private.h"
 #include "isl_seq.h"
 #include "isl_tab.h"
+#include <isl_dim_private.h>
+#include <isl_mat_private.h>
 
 static void swap_equality(struct isl_basic_map *bmap, int a, int b)
 {
@@ -57,7 +59,7 @@ struct isl_basic_set *isl_basic_set_drop_dims(
 
        isl_assert(bset->ctx, first + n <= bset->dim->n_out, goto error);
 
-       if (n == 0)
+       if (n == 0 && !isl_dim_get_tuple_name(bset->dim, isl_dim_set))
                return bset;
 
        bset = isl_basic_set_cow(bset);
@@ -98,7 +100,7 @@ struct isl_set *isl_set_drop_dims(
 
        isl_assert(set->ctx, first + n <= set->dim->n_out, goto error);
 
-       if (n == 0)
+       if (n == 0 && !isl_dim_get_tuple_name(set->dim, isl_dim_set))
                return set;
        set = isl_set_cow(set);
        if (!set)
@@ -168,7 +170,7 @@ struct isl_basic_map *isl_basic_map_drop(struct isl_basic_map *bmap,
        dim = isl_basic_map_dim(bmap, type);
        isl_assert(bmap->ctx, first + n <= dim, goto error);
 
-       if (n == 0)
+       if (n == 0 && !isl_dim_get_tuple_name(bmap->dim, type))
                return bmap;
 
        bmap = isl_basic_map_cow(bmap);
@@ -227,7 +229,7 @@ struct isl_map *isl_map_drop(struct isl_map *map,
 
        isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
 
-       if (n == 0)
+       if (n == 0 && !isl_dim_get_tuple_name(map->dim, type))
                return map;
        map = isl_map_cow(map);
        if (!map)
@@ -391,6 +393,7 @@ static void eliminate_var_using_equality(struct isl_basic_map *bmap,
                if (progress)
                        *progress = 1;
                isl_seq_elim(bmap->eq[k], eq, 1+pos, 1+total, NULL);
+               isl_seq_normalize(bmap->ctx, bmap->eq[k], 1 + total);
        }
 
        for (k = 0; k < bmap->n_ineq; ++k) {
@@ -399,6 +402,7 @@ static void eliminate_var_using_equality(struct isl_basic_map *bmap,
                if (progress)
                        *progress = 1;
                isl_seq_elim(bmap->ineq[k], eq, 1+pos, 1+total, NULL);
+               isl_seq_normalize(bmap->ctx, bmap->ineq[k], 1 + total);
                ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
        }
 
@@ -527,7 +531,7 @@ static struct isl_basic_map *eliminate_divs_ineq(
                        continue;
                *progress = 1;
                bmap = isl_basic_map_eliminate_vars(bmap, (off-1)+d, 1);
-               if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
+               if (!bmap || ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
                        break;
                bmap = isl_basic_map_drop_div(bmap, d);
                if (!bmap)
@@ -645,13 +649,16 @@ static struct isl_basic_map *remove_duplicate_divs(
        int k, l, h;
        int bits;
        struct isl_blk eq;
-       unsigned total_var = isl_dim_total(bmap->dim);
-       unsigned total = total_var + bmap->n_div;
+       unsigned total_var;
+       unsigned total;
        struct isl_ctx *ctx;
 
-       if (bmap->n_div <= 1)
+       if (!bmap || bmap->n_div <= 1)
                return bmap;
 
+       total_var = isl_dim_total(bmap->dim);
+       total = total_var + bmap->n_div;
+
        ctx = bmap->ctx;
        for (k = bmap->n_div - 1; k >= 0; --k)
                if (!isl_int_is_zero(bmap->div[k][0]))
@@ -851,6 +858,8 @@ static struct isl_basic_map *normalize_divs(
        }
        isl_int_clear(v);
        pos = isl_alloc_array(bmap->ctx, int, T->n_row);
+       if (!pos)
+               goto error;
        /* We have to be careful because dropping equalities may reorder them */
        dropped = 0;
        for (j = bmap->n_div - 1; j >= 0; --j) {
@@ -1015,7 +1024,7 @@ static struct isl_basic_map *remove_duplicate_constraints(
        unsigned total = isl_basic_map_total_dim(bmap);
        isl_int sum;
 
-       if (bmap->n_ineq <= 1)
+       if (!bmap || bmap->n_ineq <= 1)
                return bmap;
 
        size = round_up(4 * (bmap->n_ineq+1) / 3 - 1);
@@ -1100,6 +1109,43 @@ struct isl_basic_set *isl_basic_set_simplify(struct isl_basic_set *bset)
 }
 
 
+int isl_basic_map_is_div_constraint(__isl_keep isl_basic_map *bmap,
+       isl_int *constraint, unsigned div)
+{
+       unsigned pos;
+
+       if (!bmap)
+               return -1;
+
+       pos = 1 + isl_dim_total(bmap->dim) + div;
+
+       if (isl_int_eq(constraint[pos], bmap->div[div][0])) {
+               int neg;
+               isl_int_sub(bmap->div[div][1],
+                               bmap->div[div][1], bmap->div[div][0]);
+               isl_int_add_ui(bmap->div[div][1], bmap->div[div][1], 1);
+               neg = isl_seq_is_neg(constraint, bmap->div[div]+1, pos);
+               isl_int_sub_ui(bmap->div[div][1], bmap->div[div][1], 1);
+               isl_int_add(bmap->div[div][1],
+                               bmap->div[div][1], bmap->div[div][0]);
+               if (!neg)
+                       return 0;
+               if (isl_seq_first_non_zero(constraint+pos+1,
+                                           bmap->n_div-div-1) != -1)
+                       return 0;
+       } else if (isl_int_abs_eq(constraint[pos], bmap->div[div][0])) {
+               if (!isl_seq_eq(constraint, bmap->div[div]+1, pos))
+                       return 0;
+               if (isl_seq_first_non_zero(constraint+pos+1,
+                                           bmap->n_div-div-1) != -1)
+                       return 0;
+       } else
+               return 0;
+
+       return 1;
+}
+
+
 /* If the only constraints a div d=floor(f/m)
  * appears in are its two defining constraints
  *
@@ -1120,27 +1166,7 @@ static int div_is_redundant(struct isl_basic_map *bmap, int div)
        for (i = 0; i < bmap->n_ineq; ++i) {
                if (isl_int_is_zero(bmap->ineq[i][pos]))
                        continue;
-               if (isl_int_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
-                       int neg;
-                       isl_int_sub(bmap->div[div][1],
-                                       bmap->div[div][1], bmap->div[div][0]);
-                       isl_int_add_ui(bmap->div[div][1], bmap->div[div][1], 1);
-                       neg = isl_seq_is_neg(bmap->ineq[i], bmap->div[div]+1, pos);
-                       isl_int_sub_ui(bmap->div[div][1], bmap->div[div][1], 1);
-                       isl_int_add(bmap->div[div][1],
-                                       bmap->div[div][1], bmap->div[div][0]);
-                       if (!neg)
-                               return 0;
-                       if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
-                                                   bmap->n_div-div-1) != -1)
-                               return 0;
-               } else if (isl_int_abs_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
-                       if (!isl_seq_eq(bmap->ineq[i], bmap->div[div]+1, pos))
-                               return 0;
-                       if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
-                                                   bmap->n_div-div-1) != -1)
-                               return 0;
-               } else
+               if (!isl_basic_map_is_div_constraint(bmap, bmap->ineq[i], div))
                        return 0;
        }
 
@@ -1287,6 +1313,8 @@ struct isl_basic_map *isl_basic_map_eliminate_vars(
                }
                bmap = isl_basic_map_extend_constraints(bmap,
                                0, n_lower * n_upper);
+               if (!bmap)
+                       goto error;
                for (i = bmap->n_ineq - 1; i >= 0; --i) {
                        int last;
                        if (isl_int_is_zero(bmap->ineq[i][1+d]))
@@ -1314,7 +1342,7 @@ struct isl_basic_map *isl_basic_map_eliminate_vars(
                        bmap = isl_basic_map_normalize_constraints(bmap);
                        bmap = remove_duplicate_constraints(bmap, NULL);
                        bmap = isl_basic_map_gauss(bmap, NULL);
-                       bmap = isl_basic_map_convex_hull(bmap);
+                       bmap = isl_basic_map_remove_redundancies(bmap);
                        if (!bmap)
                                goto error;
                        if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
@@ -1782,10 +1810,6 @@ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap,
        if (!bmap || !context)
                goto error;
 
-       if (isl_basic_map_is_universe(context)) {
-               isl_basic_map_free(context);
-               return bmap;
-       }
        if (isl_basic_map_is_universe(bmap)) {
                isl_basic_map_free(context);
                return bmap;
@@ -1801,8 +1825,8 @@ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap,
                return bmap;
        }
 
-       bmap = isl_basic_map_convex_hull(bmap);
-       context = isl_basic_map_convex_hull(context);
+       bmap = isl_basic_map_remove_redundancies(bmap);
+       context = isl_basic_map_remove_redundancies(context);
 
        if (context->n_eq)
                bmap = normalize_divs_in_context(bmap, context);
@@ -1831,10 +1855,6 @@ __isl_give isl_map *isl_map_gist_basic_map(__isl_take isl_map *map,
        if (!map || !context)
                goto error;;
 
-       if (isl_basic_map_is_universe(context)) {
-               isl_basic_map_free(context);
-               return map;
-       }
        if (isl_basic_map_fast_is_empty(context)) {
                struct isl_dim *dim = isl_dim_copy(map->dim);
                isl_basic_map_free(context);
@@ -1842,7 +1862,7 @@ __isl_give isl_map *isl_map_gist_basic_map(__isl_take isl_map *map,
                return isl_map_universe(dim);
        }
 
-       context = isl_basic_map_convex_hull(context);
+       context = isl_basic_map_remove_redundancies(context);
        map = isl_map_cow(map);
        if (!map || !context)
                goto error;;
@@ -1868,7 +1888,7 @@ error:
 __isl_give isl_map *isl_map_gist(__isl_take isl_map *map,
        __isl_take isl_map *context)
 {
-       return isl_map_gist_basic_map(map, isl_map_convex_hull(context));
+       return isl_map_gist_basic_map(map, isl_map_simple_hull(context));
 }
 
 struct isl_basic_set *isl_basic_set_gist(struct isl_basic_set *bset,