isl_map_simplify.c: check_for_div_constraints: also check for "better" ones
authorSven Verdoolaege <skimo@kotnet.org>
Tue, 19 Feb 2013 14:44:19 +0000 (19 15:44 +0100)
committerSven Verdoolaege <skimo@kotnet.org>
Tue, 19 Feb 2013 19:11:16 +0000 (19 20:11 +0100)
In check_for_div_constraints we check if two "opposite" constraints
can be used to define a div.  However, a given div may be definable
by multiple pairs of constraints and then we would just pick the pair
we come across.

We now also consider possible defining constraints for divs for which
we already have a definition, which makes the result less dependent
on the order of the constraints.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
isl_map_simplify.c
test_inputs/codegen/omega/floor_bound-6.c
test_inputs/codegen/omega/lefur04-0.c

index c83888a..a10da54 100644 (file)
@@ -1042,9 +1042,39 @@ static int ok_to_set_div_from_bound(struct isl_basic_map *bmap,
        return 1;
 }
 
+/* Would an expression for div "div" based on inequality "ineq" of "bmap"
+ * be a better expression than the current one?
+ *
+ * If we do not have any expression yet, then any expression would be better.
+ * Otherwise we check if the last variable involved in the inequality
+ * (disregarding the div that it would define) is in an earlier position
+ * than the last variable involved in the current div expression.
+ */
+static int better_div_constraint(__isl_keep isl_basic_map *bmap,
+       int div, int ineq)
+{
+       unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all);
+       int last_div;
+       int last_ineq;
+
+       if (isl_int_is_zero(bmap->div[div][0]))
+               return 1;
+
+       if (isl_seq_last_non_zero(bmap->ineq[ineq] + total + div + 1,
+                                 bmap->n_div - (div + 1)) >= 0)
+               return 0;
+
+       last_ineq = isl_seq_last_non_zero(bmap->ineq[ineq], total + div);
+       last_div = isl_seq_last_non_zero(bmap->div[div] + 1,
+                                        total + bmap->n_div);
+
+       return last_ineq < last_div;
+}
+
 /* Given two constraints "k" and "l" that are opposite to each other,
  * except for the constant term, check if we can use them
- * to obtain an expression for one of the hitherto unknown divs.
+ * to obtain an expression for one of the hitherto unknown divs or
+ * a "better" expression for a div for which we already have an expression.
  * "sum" is the sum of the constant terms of the constraints.
  * If this sum is strictly smaller than the coefficient of one
  * of the divs, then this pair can be used define the div.
@@ -1060,12 +1090,12 @@ static struct isl_basic_map *check_for_div_constraints(
        unsigned total = 1 + isl_space_dim(bmap->dim, isl_dim_all);
 
        for (i = 0; i < bmap->n_div; ++i) {
-               if (!isl_int_is_zero(bmap->div[i][0]))
-                       continue;
                if (isl_int_is_zero(bmap->ineq[k][total + i]))
                        continue;
                if (isl_int_abs_ge(sum, bmap->ineq[k][total + i]))
                        continue;
+               if (!better_div_constraint(bmap, i, k))
+                       continue;
                if (!ok_to_set_div_from_bound(bmap, i, k))
                        break;
                if (isl_int_is_pos(bmap->ineq[k][total + i]))
index 06b32e5..743b0c9 100644 (file)
@@ -1,3 +1,3 @@
 if (m >= 8 * floord(m + 1, 8))
-  for (int c0 = 4 * floord(floord(m + 1, 8), 4); c0 <= n; c0 += 1)
+  for (int c0 = 4 * floord(m + 1, 32); c0 <= n; c0 += 1)
     s0(c0);
index 079505e..3863935 100644 (file)
@@ -2,7 +2,7 @@ for (int c0 = 0; c0 <= 3; c0 += 1)
   for (int c1 = max(0, 2 * c0 - 3); c1 <= min(c0 + 1, 3); c1 += 1)
     for (int c2 = c0; c2 <= min(min(3, 3 * c1 + 2), 2 * c0 - c1 + 1); c2 += 1)
       for (int c3 = max(max(max(c2 - (c2 + 2) / 3, c2 + floord(3 * c1 - c2 - 1, 6)), c1 - (-c1 + 3) / 3), c0 - (-c2 + 3) / 3); c3 <= min(c0 + c0 / 2 + 1, 3); c3 += 1)
-        for (int c5 = max(max(max(max(c1 - (-c1 + 3) / 3, 0), 2 * c3 - 4), c3 - (c3 + 3) / 3), c2 - (c2 + 3) / 3); c5 <= min(min(-c2 + 2 * c3 - (c2 + 3) / 3 + 2, c1 + 1), c3); c5 += 1)
+        for (int c5 = max(max(max(max(0, c1 - (-c1 + 3) / 3), 2 * c3 - 4), c3 - (c3 + 3) / 3), c2 - (c2 + 3) / 3); c5 <= min(min(-c2 + 2 * c3 - (c2 + 3) / 3 + 2, c1 + 1), c3); c5 += 1)
           for (int c6 = max(max(max(max(max(250 * c3 + 1, 667 * c0 - 333 * c1 - (c0 + c1 + 3) / 3 - 332), -200 * c1 + 400 * c3 - 199), 333 * c1 + c1 / 3), 1000 * c0 - 500 * c5 - 501), 333 * c2 + (c2 + 1) / 3); c6 <= min(min(min(min(min(min(333 * c3 - (-c3 + 3) / 3 + 334, 1000), 333 * c2 - (-c2 + 3) / 3 + 333), 1000 * c0 - 500 * c5 + 997), 500 * c5 + 501), 500 * c0 + 499), -200 * c1 + 400 * c3 + 400); c6 += 1)
             for (int c7 = max(max(max(max(c6, 500 * c1 + (c6 + 1) / 2), 1000 * c0 - c6), 500 * c5 + 2), 1000 * c3 - 2 * c6 + 2); c7 <= min(min(min(min(500 * c5 + 501, 2 * c6 + 1), 1000 * c3 - 2 * c6 + 1001), 1000 * c0 - c6 + 999), 500 * c1 + (c6 + 1) / 2 + 499); c7 += 1)
               s0(c0, c1, c2, c3, c2 / 3, c5, c6, c7);