add generalized basis reduction based ILP solver

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

diff --git a/isl_map_simplify.c b/isl_map_simplify.c
index 5f06d84..38981aa 100644 (file)
--- a/isl_map_simplify.c
+++ b/isl_map_simplify.c
@@ -1173,7 +1173,9 @@ error:
 }
 
 
-/* Remove any div that is defined in terms of the given variable.
+/* Remove definition of any div that is defined in terms of the given variable.
+ * The div itself is not removed.  Functions such as
+ * eliminate_divs_ineq depend on the other divs remaining in place.
  */
 static struct isl_basic_map *remove_dependent_vars(struct isl_basic_map *bmap,
                                                                        int pos)
@@ -1186,9 +1188,7 @@ static struct isl_basic_map *remove_dependent_vars(struct isl_basic_map *bmap,
                        continue;
                if (isl_int_is_zero(bmap->div[i][1+1+pos]))
                        continue;
-               bmap = isl_basic_map_eliminate_vars(bmap, dim + i, 1);
-               if (!bmap)
-                       return NULL;
+               isl_int_set_si(bmap->div[i][0], 0);
        }
        return bmap;
 }
@@ -1861,8 +1861,8 @@ int isl_set_fast_is_disjoint(struct isl_set *set1, struct isl_set *set2)
  * Otherwise return -1.
  *
  * We first check that
- *     - the bounds are opposites of each other (expect for the constant
- *       term
+ *     - the bounds are opposites of each other (except for the constant
+ *       term)
  *     - the bounds do not reference any other div
  *     - no div is defined in terms of this div
  *
@@ -2277,9 +2277,9 @@ struct isl_basic_map *isl_basic_map_drop_redundant_divs(
                int pos, neg;
                int last_pos, last_neg;
                int redundant;
+               int defined;
 
-               if (!isl_int_is_zero(bmap->div[i][0]))
-                       continue;
+               defined = !isl_int_is_zero(bmap->div[i][0]);
                for (j = 0; j < bmap->n_eq; ++j)
                        if (!isl_int_is_zero(bmap->eq[j][1 + off + i]))
                                break;
@@ -2324,7 +2324,8 @@ struct isl_basic_map *isl_basic_map_drop_redundant_divs(
                isl_int_sub(bmap->ineq[last_pos][0],
                            bmap->ineq[last_pos][0], bmap->ineq[last_neg][0]);
                if (!redundant) {
-                       if (!ok_to_set_div_from_bound(bmap, i, last_pos)) {
+                       if (defined ||
+                           !ok_to_set_div_from_bound(bmap, i, last_pos)) {
                                pairs[i] = 0;
                                --n;
                                continue;
@@ -2356,3 +2357,34 @@ error:
        isl_basic_map_free(bmap);
        return NULL;
 }
+
+struct isl_basic_set *isl_basic_set_drop_redundant_divs(
+       struct isl_basic_set *bset)
+{
+       return (struct isl_basic_set *)
+           isl_basic_map_drop_redundant_divs((struct isl_basic_map *)bset);
+}
+
+struct isl_map *isl_map_drop_redundant_divs(struct isl_map *map)
+{
+       int i;
+
+       if (!map)
+               return NULL;
+       for (i = 0; i < map->n; ++i) {
+               map->p[i] = isl_basic_map_drop_redundant_divs(map->p[i]);
+               if (!map->p[i])
+                       goto error;
+       }
+       ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+       return map;
+error:
+       isl_map_free(map);
+       return NULL;
+}
+
+struct isl_set *isl_set_drop_redundant_divs(struct isl_set *set)
+{
+       return (struct isl_set *)
+           isl_map_drop_redundant_divs((struct isl_map *)set);
+}