isl_basic_map_gist: drop irrelevant constraints from the context
authorSven Verdoolaege <skimo@kotnet.org>
Sun, 18 Nov 2012 08:24:50 +0000 (18 09:24 +0100)
committerSven Verdoolaege <skimo@kotnet.org>
Tue, 20 Nov 2012 17:06:32 +0000 (20 18:06 +0100)
The context may contain constraints on variables that do not even
appear in the input basic map.  The constraints therefore cannot
be exploited to simplify the input and only serve to make some
of the internal computations more expensive, in particular the
computation of the affine hull of the intersection of input and context
and the emptiness checks used in the final determination of
the redundancy of a constraint.
It's therefore more efficient to remove those irrelevant constraints.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_map_simplify.c
test_inputs/codegen/cloog/jacobi-shared.c
test_inputs/codegen/cloog/mxm-shared.c
test_inputs/codegen/cloog/reservoir-liu-zhuge1.c
test_inputs/codegen/cloog/reservoir-mg-rprj3.c
test_inputs/codegen/cloog/vasilache.c
test_inputs/codegen/omega/lift2-0.c
test_inputs/codegen/omega/ts1d-mp-i_ts-m_b-0.c

index ea3a366..5042034 100644 (file)
@@ -1707,11 +1707,181 @@ error:
        return bset;
 }
 
+/* Does the (linear part of a) constraint "c" involve any of the "len"
+ * "relevant" dimensions?
+ */
+static int is_related(isl_int *c, int len, int *relevant)
+{
+       int i;
+
+       for (i = 0; i < len; ++i) {
+               if (!relevant[i])
+                       continue;
+               if (!isl_int_is_zero(c[i]))
+                       return 1;
+       }
+
+       return 0;
+}
+
+/* Drop constraints from "bset" that do not involve any of
+ * the dimensions marked "relevant".
+ */
+static __isl_give isl_basic_set *drop_unrelated_constraints(
+       __isl_take isl_basic_set *bset, int *relevant)
+{
+       int i, dim;
+
+       dim = isl_basic_set_dim(bset, isl_dim_set);
+       for (i = 0; i < dim; ++i)
+               if (!relevant[i])
+                       break;
+       if (i >= dim)
+               return bset;
+
+       for (i = bset->n_eq - 1; i >= 0; --i)
+               if (!is_related(bset->eq[i] + 1, dim, relevant))
+                       isl_basic_set_drop_equality(bset, i);
+
+       for (i = bset->n_ineq - 1; i >= 0; --i)
+               if (!is_related(bset->ineq[i] + 1, dim, relevant))
+                       isl_basic_set_drop_inequality(bset, i);
+
+       return bset;
+}
+
+/* Update the groups in "group" based on the (linear part of a) constraint "c".
+ *
+ * In particular, for any variable involved in the constraint,
+ * find the actual group id from before and replace the group
+ * of the corresponding variable by the minimal group of all
+ * the variables involved in the constraint considered so far
+ * (if this minimum is smaller) or replace the minimum by this group
+ * (if the minimum is larger).
+ *
+ * At the end, all the variables in "c" will (indirectly) point
+ * to the minimal of the groups that they referred to originally.
+ */
+static void update_groups(int dim, int *group, isl_int *c)
+{
+       int j;
+       int min = dim;
+
+       for (j = 0; j < dim; ++j) {
+               if (isl_int_is_zero(c[j]))
+                       continue;
+               while (group[j] >= 0 && group[group[j]] != group[j])
+                       group[j] = group[group[j]];
+               if (group[j] == min)
+                       continue;
+               if (group[j] < min) {
+                       if (min >= 0 && min < dim)
+                               group[min] = group[j];
+                       min = group[j];
+               } else
+                       group[group[j]] = min;
+       }
+}
+
+/* Drop constraints from "context" that are irrelevant for computing
+ * the gist of "bset".
+ *
+ * In particular, drop constraints in variables that are not related
+ * to any of the variables involved in the constraints of "bset"
+ * in the sense that there is no sequence of constraints that connects them.
+ *
+ * We construct groups of variables that collect variables that
+ * (indirectly) appear in some common constraint of "context".
+ * Each group is identified by the first variable in the group,
+ * except for the special group of variables that appear in "bset"
+ * (or are related to those variables), which is identified by -1.
+ * If group[i] is equal to i (or -1), then the group of i is i (or -1),
+ * otherwise the group of i is the group of group[i].
+ *
+ * We first initialize the -1 group with the variables that appear in "bset".
+ * Then we initialize groups for the remaining variables.
+ * Then we iterate over the constraints of "context" and update the
+ * group of the variables in the constraint by the smallest group.
+ * Finally, we resolve indirect references to groups by running over
+ * the variables.
+ *
+ * After computing the groups, we drop constraints that do not involve
+ * any variables in the -1 group.
+ */
+static __isl_give isl_basic_set *drop_irrelevant_constraints(
+       __isl_take isl_basic_set *context, __isl_keep isl_basic_set *bset)
+{
+       isl_ctx *ctx;
+       int *group;
+       int dim;
+       int i, j;
+       int last;
+
+       if (!context || !bset)
+               return isl_basic_set_free(context);
+
+       dim = isl_basic_set_dim(bset, isl_dim_set);
+       ctx = isl_basic_set_get_ctx(bset);
+       group = isl_calloc_array(ctx, int, dim);
+
+       if (!group)
+               goto error;
+
+       for (i = 0; i < dim; ++i) {
+               for (j = 0; j < bset->n_eq; ++j)
+                       if (!isl_int_is_zero(bset->eq[j][1 + i]))
+                               break;
+               if (j < bset->n_eq) {
+                       group[i] = -1;
+                       continue;
+               }
+               for (j = 0; j < bset->n_ineq; ++j)
+                       if (!isl_int_is_zero(bset->ineq[j][1 + i]))
+                               break;
+               if (j < bset->n_ineq)
+                       group[i] = -1;
+       }
+
+       last = -1;
+       for (i = 0; i < dim; ++i)
+               if (group[i] >= 0)
+                       last = group[i] = i;
+       if (last < 0) {
+               free(group);
+               return context;
+       }
+
+       for (i = 0; i < context->n_eq; ++i)
+               update_groups(dim, group, context->eq[i] + 1);
+       for (i = 0; i < context->n_ineq; ++i)
+               update_groups(dim, group, context->ineq[i] + 1);
+
+       for (i = 0; i < dim; ++i)
+               if (group[i] >= 0)
+                       group[i] = group[group[i]];
+
+       for (i = 0; i < dim; ++i)
+               group[i] = group[i] == -1;
+
+       context = drop_unrelated_constraints(context, group);
+
+       free(group);
+       return context;
+error:
+       free(group);
+       return isl_basic_set_free(context);
+}
+
 /* Remove all information from bset that is redundant in the context
  * of context.  Both bset and context are assumed to be full-dimensional.
  *
  * We first remove the inequalities from "bset"
  * that are obviously redundant with respect to some inequality in "context".
+ * Then we remove those constraints from "context" that have become
+ * irrelevant for computing the gist of "bset".
+ * Note that this removal of constraints cannot be replaced by
+ * a factorization because factors in "bset" may still be connected
+ * to each other through constraints in "context".
  *
  * If there are any inequalities left, we construct a tableau for
  * the context and then add the inequalities of "bset".
@@ -1752,6 +1922,14 @@ static __isl_give isl_basic_set *uset_gist_full(__isl_take isl_basic_set *bset,
        if (bset->n_ineq == 0)
                goto done;
 
+       context = drop_irrelevant_constraints(context, bset);
+       if (!context)
+               goto error;
+       if (isl_basic_set_is_universe(context)) {
+               isl_basic_set_free(context);
+               return bset;
+       }
+
        context_ineq = context->n_ineq;
        combined = isl_basic_set_cow(isl_basic_set_copy(context));
        combined = isl_basic_set_extend_constraints(combined, 0, bset->n_ineq);
@@ -1819,6 +1997,10 @@ error:
  * redundant in the context of the equalities and inequalities of
  * context are removed.
  *
+ * First of all, we drop those constraints from "context"
+ * that are irrelevant for computing the gist of "bset".
+ * Alternatively, we could factorize the intersection of "context" and "bset".
+ *
  * We first compute the integer affine hull of the intersection,
  * compute the gist inside this affine hull and then add back
  * those equalities that are not implied by the context.
@@ -1842,6 +2024,8 @@ static __isl_give isl_basic_set *uset_gist(__isl_take isl_basic_set *bset,
        if (!bset || !context)
                goto error;
 
+       context = drop_irrelevant_constraints(context, bset);
+
        bset = isl_basic_set_intersect(bset, isl_basic_set_copy(context));
        if (isl_basic_set_plain_is_empty(bset)) {
                isl_basic_set_free(context);
index c671cf9..4a718ea 100644 (file)
@@ -1,3 +1,3 @@
 if (2 * floord(h0 - 1, 2) + 1 == h0 && g2 + 29 >= (g2 - t1 + 32) % 32 && ((g2 - t1 + 32) % 32) + N >= g2 + 33)
-  for (int c0 = max(((t0 + 15) % 16) + 1, ((g1 + t0 + 13) % 16) - g1 + 3); c0 <= min(32, N - g1 - 1); c0 += 16)
+  for (int c0 = max(((g1 + t0 + 13) % 16) - g1 + 3, ((t0 + 15) % 16) + 1); c0 <= min(32, N - g1 - 1); c0 += 16)
     S1(g1 + c0 - 1, ((t1 + 31) % 32) + g2);
index 0a1af52..d98b699 100644 (file)
@@ -1,6 +1,6 @@
 if (g4 == 0 && N >= g0 + t1 + 1 && t1 <= 7) {
-  for (int c0 = t0; c0 <= min(N - g1 - 1, 127); c0 += 16)
+  for (int c0 = t0; c0 <= min(127, N - g1 - 1); c0 += 16)
     S1(g0 + t1, g1 + c0);
-} else if (g4 % 4 == 0 && N >= g0 + t1 + 1 && g4 >= 4 && t1 <= 7)
+} else if (g4 % 4 == 0 && t1 <= 7 && N >= g0 + t1 + 1 && g4 >= 4)
   for (int c0 = t0; c0 <= min(127, N - g1 - 1); c0 += 16)
     S1(g0 + t1, g1 + c0);
index 987c280..c693da2 100644 (file)
@@ -2,7 +2,7 @@ if (N >= 0 && M >= 0)
   for (int c1 = -4; c1 <= 3 * M + N; c1 += 1) {
     if (c1 >= 3 * M) {
       S2(M, -3 * M + c1);
-    } else if (3 * floord(c1 - 2, 3) + 2 == c1 && c1 + 1 >= 0 && 3 * M >= c1 + 4)
+    } else if (3 * floord(c1 - 2, 3) + 2 == c1 && 3 * M >= c1 + 4 && c1 + 1 >= 0)
       S1((c1 + 4) / 3, 0);
     for (int c3 = max(c1 + 3 * floord(-c1 - 1, 3) + 3, -3 * M + c1 + 3); c3 <= min(c1, N - 1); c3 += 3) {
       S2((c1 - c3) / 3, c3);
index fcd0025..992bfd5 100644 (file)
@@ -1,4 +1,4 @@
-if (N >= 3 && M >= 2)
+if (M >= 2 && N >= 3)
   for (int c1 = 2; c1 < O; c1 += 1) {
     for (int c5 = 2; c5 <= M; c5 += 1)
       S1(c1, 2, c5);
index 567e41f..d2e5c46 100644 (file)
@@ -10,7 +10,7 @@
     for (int c3 = 0; c3 < N; c3 += 1)
       for (int c5 = 0; c5 <= (N - 1) / 32; c5 += 1) {
         S7(c1, c3, c5, 32 * c5);
-        for (int c7 = 32 * c5 + 1; c7 <= min(N - 1, 32 * c5 + 31); c7 += 1) {
+        for (int c7 = 32 * c5 + 1; c7 <= min(32 * c5 + 31, N - 1); c7 += 1) {
           S6(c1, c3, c5, c7 - 1);
           S7(c1, c3, c5, c7);
         }
index 9658b92..181d6e5 100644 (file)
@@ -4,6 +4,6 @@ for (int c0 = 1; c0 <= 100; c0 += 1)
       for (int c3 = 1; c3 <= 100; c3 += 1)
         for (int c4 = 1; c4 <= 100; c4 += 1) {
           s1(c0, c1, c2, c3, c4);
-          if (c0 <= 60 && c0 >= 5)
+          if (c0 >= 5 && c0 <= 60)
             s0(c0, c1, c2, c3, c4);
         }
index c8526f0..819493d 100644 (file)
@@ -3,9 +3,9 @@
     for (int c2 = 0; c2 < N; c2 += 1)
       if (c2 == 0 && c1 >= 0 && T >= c1 + 1) {
         s0(1, c1, 0, 0, 0);
-      } else if (c2 + 1 == N && T >= c1 + 1 && c1 >= 0) {
+      } else if (c2 + 1 == N && c1 >= 0 && T >= c1 + 1) {
         s0(1, c1, N - 1, 0, 0);
-      } else if (c1 + 1 == 0 && c2 >= 0 && N >= c2 + 1)
+      } else if (c1 + 1 == 0 && N >= c2 + 1 && c2 >= 0)
         s0(1, -1, c2, 0, 0);
   for (int c1 = 0; c1 <= floord(T - 1, 500); c1 += 1) {
     for (int c3 = -((c1 + 9) / 8) + 2; c3 <= floord(N - 500 * c1 - 3, 4000) + 1; c3 += 1)