isl_die(ctx, isl_error_unknown, "not expecting any divs",
return -1);
+ /* Check that isl_map_affine_hull is not confused by
+ * the reordering of divs in isl_map_align_divs.
+ */
+ str = "{ [a, b, c, 0] : exists (e0 = [(b)/32], e1 = [(c)/32]: "
+ "32e0 = b and 32e1 = c); "
+ "[a, 0, c, 0] : exists (e0 = [(c)/32]: 32e0 = c) }";
+ set = isl_set_read_from_str(ctx, str);
+ bset = isl_set_affine_hull(set);
+ isl_basic_set_free(bset);
+ if (!bset)
+ return -1;
+
return 0;
}
return r;
}
-int test_coalesce(struct isl_ctx *ctx)
-{
+/* Inputs for coalescing tests.
+ * "str" is a string representation of the input set.
+ * "single_disjunct" is set if we expect the result to consist of
+ * a single disjunct.
+ */
+struct {
+ int single_disjunct;
const char *str;
- struct isl_set *set, *set2;
- struct isl_map *map, *map2;
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: x >= 0 & x <= 10 & y >= 0 & y <= 10 or "
- "y >= x & x >= 2 & 5 >= y }");
- set = isl_set_coalesce(set);
- assert(set && set->n == 1);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
- "x + y >= 10 & y <= x & x + y <= 20 & y >= 0}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 1);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
- "x + y >= 10 & y <= x & x + y <= 19 & y >= 0}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 2);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x >= 6 & x <= 10 & y <= x}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 1);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x >= 7 & x <= 10 & y <= x}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 2);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x >= 6 & x <= 10 & y + 1 <= x}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 2);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x = 6 & y <= 6}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 1);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x = 7 & y <= 6}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 2);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x = 6 & y <= 5}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 1);
- set2 = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x = 6 & y <= 5}");
- assert(isl_set_is_equal(set, set2));
- isl_set_free(set);
- isl_set_free(set2);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y]: y >= 0 & x <= 5 & y <= x or "
- "y >= 0 & x = 6 & y <= 7}");
- set = isl_set_coalesce(set);
- assert(set && set->n == 2);
- isl_set_free(set);
-
- set = isl_set_read_from_str(ctx,
- "[n] -> { [i] : i = 1 and n >= 2 or 2 <= i and i <= n }");
- set = isl_set_coalesce(set);
- assert(set && set->n == 1);
- set2 = isl_set_read_from_str(ctx,
- "[n] -> { [i] : i = 1 and n >= 2 or 2 <= i and i <= n }");
- assert(isl_set_is_equal(set, set2));
- isl_set_free(set);
- isl_set_free(set2);
-
- set = isl_set_read_from_str(ctx,
- "{[x,y] : x >= 0 and y >= 0 or 0 <= y and y <= 5 and x = -1}");
- set = isl_set_coalesce(set);
- set2 = isl_set_read_from_str(ctx,
- "{[x,y] : x >= 0 and y >= 0 or 0 <= y and y <= 5 and x = -1}");
- assert(isl_set_is_equal(set, set2));
- isl_set_free(set);
- isl_set_free(set2);
-
- set = isl_set_read_from_str(ctx,
- "[n] -> { [i] : 1 <= i and i <= n - 1 or "
- "2 <= i and i <= n }");
- set = isl_set_coalesce(set);
- assert(set && set->n == 1);
- set2 = isl_set_read_from_str(ctx,
- "[n] -> { [i] : 1 <= i and i <= n - 1 or "
- "2 <= i and i <= n }");
- assert(isl_set_is_equal(set, set2));
- isl_set_free(set);
- isl_set_free(set2);
-
- map = isl_map_read_from_str(ctx,
- "[n] -> { [i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
+} coalesce_tests[] = {
+ { 1, "{[x,y]: x >= 0 & x <= 10 & y >= 0 & y <= 10 or "
+ "y >= x & x >= 2 & 5 >= y }" },
+ { 1, "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
+ "x + y >= 10 & y <= x & x + y <= 20 & y >= 0}" },
+ { 0, "{[x,y]: y >= 0 & 2x + y <= 30 & y <= 10 & x >= 0 or "
+ "x + y >= 10 & y <= x & x + y <= 19 & y >= 0}" },
+ { 1, "{[x,y]: y >= 0 & x <= 5 & y <= x or "
+ "y >= 0 & x >= 6 & x <= 10 & y <= x}" },
+ { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or "
+ "y >= 0 & x >= 7 & x <= 10 & y <= x}" },
+ { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or "
+ "y >= 0 & x >= 6 & x <= 10 & y + 1 <= x}" },
+ { 1, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 6 & y <= 6}" },
+ { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 7 & y <= 6}" },
+ { 1, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 6 & y <= 5}" },
+ { 0, "{[x,y]: y >= 0 & x <= 5 & y <= x or y >= 0 & x = 6 & y <= 7}" },
+ { 1, "[n] -> { [i] : i = 1 and n >= 2 or 2 <= i and i <= n }" },
+ { 0, "{[x,y] : x >= 0 and y >= 0 or 0 <= y and y <= 5 and x = -1}" },
+ { 1, "[n] -> { [i] : 1 <= i and i <= n - 1 or 2 <= i and i <= n }" },
+ { 0, "[n] -> { [[i0] -> [o0]] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
"e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "
"e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "
"4e4 = -2 + o0 and i0 >= 8 + 2n and o0 >= 2 + i0 and "
"i0 <= -11 + 4n and o0 >= 6 + 2n and 4e0 <= i0 and "
"4e0 >= -3 + i0 and 4e1 <= o0 and 4e1 >= -3 + o0 and "
"4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0);"
- "[i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
+ "[[i0] -> [o0]] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
"e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "
"e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "
"4e4 = -2 + o0 and 2e0 >= 3 + n and e0 <= -4 + n and "
"i0 <= -11 + 4n and i0 <= 57 + 2n and 4e0 <= -2 + i0 and "
"4e0 >= -3 + i0 and o0 >= 6 + 2n and o0 <= -11 + 4n and "
"o0 <= 57 + 2n and 4e1 <= -2 + o0 and 4e1 >= -3 + o0 and "
- "4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0 ) }");
- map = isl_map_coalesce(map);
- map2 = isl_map_read_from_str(ctx,
- "[n] -> { [i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
- "e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "
- "e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "
- "4e4 = -2 + o0 and i0 >= 8 + 2n and o0 >= 2 + i0 and "
- "o0 <= 56 + 2n and o0 <= -12 + 4n and i0 <= 57 + 2n and "
- "i0 <= -11 + 4n and o0 >= 6 + 2n and 4e0 <= i0 and "
- "4e0 >= -3 + i0 and 4e1 <= o0 and 4e1 >= -3 + o0 and "
- "4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0);"
- "[i0] -> [o0] : exists (e0 = [(i0)/4], e1 = [(o0)/4], "
- "e2 = [(n)/2], e3 = [(-2 + i0)/4], e4 = [(-2 + o0)/4], "
- "e5 = [(-2n + i0)/4]: 2e2 = n and 4e3 = -2 + i0 and "
- "4e4 = -2 + o0 and 2e0 >= 3 + n and e0 <= -4 + n and "
- "2e0 <= 27 + n and e1 <= -4 + n and 2e1 <= 27 + n and "
- "2e1 >= 2 + n and e1 >= 1 + e0 and i0 >= 7 + 2n and "
- "i0 <= -11 + 4n and i0 <= 57 + 2n and 4e0 <= -2 + i0 and "
- "4e0 >= -3 + i0 and o0 >= 6 + 2n and o0 <= -11 + 4n and "
- "o0 <= 57 + 2n and 4e1 <= -2 + o0 and 4e1 >= -3 + o0 and "
- "4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0 ) }");
- assert(isl_map_is_equal(map, map2));
- isl_map_free(map);
- isl_map_free(map2);
-
- str = "[n, m] -> { [] -> [o0, o2, o3] : (o3 = 1 and o0 >= 1 + m and "
+ "4e5 <= -2n + i0 and 4e5 >= -3 - 2n + i0 ) }" },
+ { 0, "[n, m] -> { [o0, o2, o3] : (o3 = 1 and o0 >= 1 + m and "
"o0 <= n + m and o2 <= m and o0 >= 2 + n and o2 >= 3) or "
"(o0 >= 2 + n and o0 >= 1 + m and o0 <= n + m and n >= 1 and "
- "o3 <= -1 + o2 and o3 >= 1 - m + o2 and o3 >= 2 and o3 <= n) }";
- map = isl_map_read_from_str(ctx, str);
- map = isl_map_coalesce(map);
- map2 = isl_map_read_from_str(ctx, str);
- assert(isl_map_is_equal(map, map2));
- isl_map_free(map);
- isl_map_free(map2);
-
- str = "[M, N] -> { [i0, i1, i2, i3, i4, i5, i6] -> "
- "[o0, o1, o2, o3, o4, o5, o6] : "
+ "o3 <= -1 + o2 and o3 >= 1 - m + o2 and o3 >= 2 and o3 <= n) }" },
+ { 0, "[M, N] -> { [[i0, i1, i2, i3, i4, i5, i6] -> "
+ "[o0, o1, o2, o3, o4, o5, o6]] : "
"(o6 <= -4 + 2M - 2N + i0 + i1 - i2 + i6 - o0 - o1 + o2 and "
"o3 <= -2 + i3 and o6 >= 2 + i0 + i3 + i6 - o0 - o3 and "
"o6 >= 2 - M + N + i3 + i4 + i6 - o3 - o4 and o0 <= -1 + i0 and "
"(N >= 2 and o3 <= -1 + i3 and o0 <= -1 + i0 and "
"o6 >= i3 + i6 - o3 and M >= 0 and "
"2o6 >= 1 + i0 + i3 + 2i6 - o0 - o3 and "
- "o6 >= 1 - M + i0 + i6 - o0 and N >= 2M and o6 >= i0 + i6 - o0) }";
- map = isl_map_read_from_str(ctx, str);
- map = isl_map_coalesce(map);
- map2 = isl_map_read_from_str(ctx, str);
- assert(isl_map_is_equal(map, map2));
- isl_map_free(map);
- isl_map_free(map2);
-
- str = "[M, N] -> { [] -> [o0] : (o0 = 0 and M >= 1 and N >= 2) or "
+ "o6 >= 1 - M + i0 + i6 - o0 and N >= 2M and o6 >= i0 + i6 - o0) }" },
+ { 0, "[M, N] -> { [o0] : (o0 = 0 and M >= 1 and N >= 2) or "
"(o0 = 0 and M >= 1 and N >= 2M and N >= 2 + M) or "
"(o0 = 0 and M >= 2 and N >= 3) or "
- "(M = 0 and o0 = 0 and N >= 3) }";
- map = isl_map_read_from_str(ctx, str);
- map = isl_map_coalesce(map);
- map2 = isl_map_read_from_str(ctx, str);
- assert(isl_map_is_equal(map, map2));
- isl_map_free(map);
- isl_map_free(map2);
-
- str = "{ [i0, i1, i2, i3] : (i1 = 10i0 and i0 >= 1 and 10i0 <= 100 and "
- "i3 <= 9 + 10 i2 and i3 >= 1 + 10i2 and i3 >= 0) or "
- "(i1 <= 9 + 10i0 and i1 >= 1 + 10i0 and i2 >= 0 and "
- "i0 >= 0 and i1 <= 100 and i3 <= 9 + 10i2 and i3 >= 1 + 10i2) }";
- map = isl_map_read_from_str(ctx, str);
- map = isl_map_coalesce(map);
- map2 = isl_map_read_from_str(ctx, str);
- assert(isl_map_is_equal(map, map2));
- isl_map_free(map);
- isl_map_free(map2);
-
- test_coalesce_set(ctx,
- "[M] -> { [i1] : (i1 >= 2 and i1 <= M) or "
- "(i1 = M and M >= 1) }", 0);
- test_coalesce_set(ctx,
- "{[x,y] : x,y >= 0; [x,y] : 10 <= x <= 20 and y >= -1 }", 0);
- test_coalesce_set(ctx,
- "{ [x, y] : (x >= 1 and y >= 1 and x <= 2 and y <= 2) or "
- "(y = 3 and x = 1) }", 1);
- test_coalesce_set(ctx,
- "[M] -> { [i0, i1, i2, i3, i4] : (i1 >= 3 and i4 >= 2 + i2 and "
+ "(M = 0 and o0 = 0 and N >= 3) }" },
+ { 0, "{ [i0, i1, i2, i3] : (i1 = 10i0 and i0 >= 1 and 10i0 <= 100 and "
+ "i3 <= 9 + 10 i2 and i3 >= 1 + 10i2 and i3 >= 0) or "
+ "(i1 <= 9 + 10i0 and i1 >= 1 + 10i0 and i2 >= 0 and "
+ "i0 >= 0 and i1 <= 100 and i3 <= 9 + 10i2 and i3 >= 1 + 10i2) }" },
+ { 0, "[M] -> { [i1] : (i1 >= 2 and i1 <= M) or (i1 = M and M >= 1) }" },
+ { 0, "{[x,y] : x,y >= 0; [x,y] : 10 <= x <= 20 and y >= -1 }" },
+ { 1, "{ [x, y] : (x >= 1 and y >= 1 and x <= 2 and y <= 2) or "
+ "(y = 3 and x = 1) }" },
+ { 1, "[M] -> { [i0, i1, i2, i3, i4] : (i1 >= 3 and i4 >= 2 + i2 and "
"i2 >= 2 and i0 >= 2 and i3 >= 1 + i2 and i0 <= M and "
"i1 <= M and i3 <= M and i4 <= M) or "
"(i1 >= 2 and i4 >= 1 + i2 and i2 >= 2 and i0 >= 2 and "
"i3 >= 1 + i2 and i0 <= M and i1 <= -1 + M and i3 <= M and "
- "i4 <= -1 + M) }", 1);
- test_coalesce_set(ctx,
- "{ [x, y] : (x >= 0 and y >= 0 and x <= 10 and y <= 10) or "
- "(x >= 1 and y >= 1 and x <= 11 and y <= 11) }", 1);
- if (test_coalesce_unbounded_wrapping(ctx) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{[x,0] : x >= 0; [x,1] : x <= 20}", 0) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [x, 1 - x] : 0 <= x <= 1; [0,0] }", 1) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [0,0]; [i,i] : 1 <= i <= 10 }", 1) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [0,0]; [i,j] : 1 <= i,j <= 10 }", 0) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [0,0]; [i,2i] : 1 <= i <= 10 }", 1) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [0,0]; [i,2i] : 2 <= i <= 10 }", 0) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [1,0]; [i,2i] : 1 <= i <= 10 }", 0) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [0,1]; [i,2i] : 1 <= i <= 10 }", 0) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [a, b] : exists e : 2e = a and "
- "a >= 0 and (a <= 3 or (b <= 0 and b >= -4 + a)) }", 0) < 0)
- return -1;
- if (test_coalesce_set(ctx,
- "{ [i, j, i', j'] : i <= 2 and j <= 2 and "
+ "i4 <= -1 + M) }" },
+ { 1, "{ [x, y] : (x >= 0 and y >= 0 and x <= 10 and y <= 10) or "
+ "(x >= 1 and y >= 1 and x <= 11 and y <= 11) }" },
+ { 0, "{[x,0] : x >= 0; [x,1] : x <= 20}" },
+ { 1, "{ [x, 1 - x] : 0 <= x <= 1; [0,0] }" },
+ { 1, "{ [0,0]; [i,i] : 1 <= i <= 10 }" },
+ { 0, "{ [0,0]; [i,j] : 1 <= i,j <= 10 }" },
+ { 1, "{ [0,0]; [i,2i] : 1 <= i <= 10 }" },
+ { 0, "{ [0,0]; [i,2i] : 2 <= i <= 10 }" },
+ { 0, "{ [1,0]; [i,2i] : 1 <= i <= 10 }" },
+ { 0, "{ [0,1]; [i,2i] : 1 <= i <= 10 }" },
+ { 0, "{ [a, b] : exists e : 2e = a and "
+ "a >= 0 and (a <= 3 or (b <= 0 and b >= -4 + a)) }" },
+ { 0, "{ [i, j, i', j'] : i <= 2 and j <= 2 and "
"j' >= -1 + 2i + j - 2i' and i' <= -1 + i and "
"j >= 1 and j' <= i + j - i' and i >= 1; "
- "[1, 1, 1, 1] }", 0) < 0)
- return -1;
- if (test_coalesce_set(ctx, "{ [i,j] : exists a,b : i = 2a and j = 3b; "
- "[i,j] : exists a : j = 3a }", 1) < 0)
+ "[1, 1, 1, 1] }" },
+ { 1, "{ [i,j] : exists a,b : i = 2a and j = 3b; "
+ "[i,j] : exists a : j = 3a }" },
+ { 1, "{ [a, b, c] : (c <= 7 - b and b <= 1 and b >= 0 and "
+ "c >= 3 + b and b <= 3 + 8a and b >= -26 + 8a and "
+ "a >= 3) or "
+ "(b <= 1 and c <= 7 and b >= 0 and c >= 4 + b and "
+ "b <= 3 + 8a and b >= -26 + 8a and a >= 3) }" },
+ { 1, "{ [a, 0, c] : c >= 1 and c <= 29 and c >= -1 + 8a and "
+ "c <= 6 + 8a and a >= 3; "
+ "[a, -1, c] : c >= 1 and c <= 30 and c >= 8a and "
+ "c <= 7 + 8a and a >= 3 and a <= 4 }" },
+ { 1, "{ [x,y] : 0 <= x <= 2 and y >= 0 and x + 2y <= 4; "
+ "[x,0] : 3 <= x <= 4 }" },
+ { 1, "{ [x,y] : 0 <= x <= 3 and y >= 0 and x + 3y <= 6; "
+ "[x,0] : 4 <= x <= 5 }" },
+ { 0, "{ [x,y] : 0 <= x <= 2 and y >= 0 and x + 2y <= 4; "
+ "[x,0] : 3 <= x <= 5 }" },
+ { 0, "{ [x,y] : 0 <= x <= 2 and y >= 0 and x + y <= 4; "
+ "[x,0] : 3 <= x <= 4 }" },
+ { 1 , "{ [i0, i1] : i0 <= 122 and i0 >= 1 and 128i1 >= -249 + i0 and "
+ "i1 <= 0; "
+ "[i0, 0] : i0 >= 123 and i0 <= 124 }" },
+};
+
+/* Test the functionality of isl_set_coalesce.
+ * That is, check that the output is always equal to the input
+ * and in some cases that the result consists of a single disjunct.
+ */
+static int test_coalesce(struct isl_ctx *ctx)
+{
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(coalesce_tests); ++i) {
+ const char *str = coalesce_tests[i].str;
+ int check_one = coalesce_tests[i].single_disjunct;
+ if (test_coalesce_set(ctx, str, check_one) < 0)
+ return -1;
+ }
+
+ if (test_coalesce_unbounded_wrapping(ctx) < 0)
return -1;
+
return 0;
}
isl_map_free(map);
}
-void test_lexmin(struct isl_ctx *ctx)
+static int test_lexmin(struct isl_ctx *ctx)
{
+ int equal;
const char *str;
isl_basic_map *bmap;
isl_map *map, *map2;
assert(isl_map_is_equal(map, map2));
isl_map_free(map);
isl_map_free(map2);
+
+ str = "[i] -> { [i', j] : j = i - 8i' and i' >= 0 and i' <= 7 and "
+ " 8i' <= i and 8i' >= -7 + i }";
+ set = isl_set_read_from_str(ctx, str);
+ pma = isl_set_lexmin_pw_multi_aff(isl_set_copy(set));
+ set2 = isl_set_from_pw_multi_aff(pma);
+ equal = isl_set_is_equal(set, set2);
+ isl_set_free(set);
+ isl_set_free(set2);
+ if (equal < 0)
+ return -1;
+ if (!equal)
+ isl_die(ctx, isl_error_unknown,
+ "unexpected difference between set and "
+ "piecewise affine expression", return -1);
+
+ return 0;
}
struct must_may {
if (!equal)
isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
+ /* Check that solutions are properly merged. */
+ str = "[n] -> { [a, b, c] : c >= -4a - 2b and "
+ "c <= -1 + n - 4a - 2b and c >= -2b and "
+ "4a >= -4 + n and c >= 0 }";
+ set = isl_set_read_from_str(ctx, str);
+ pwaff = isl_set_dim_min(set, 2);
+ set1 = isl_set_from_pw_aff(pwaff);
+ str = "[n] -> { [(0)] : n >= 1 }";
+ set2 = isl_set_read_from_str(ctx, str);
+ equal = isl_set_is_equal(set1, set2);
+ isl_set_free(set1);
+ isl_set_free(set2);
+
+ if (equal < 0)
+ return -1;
+ if (!equal)
+ isl_die(ctx, isl_error_unknown, "unexpected result", return -1);
+
return 0;
}
return 0;
}
+/* This is a regression test for a bug where isl_basic_map_simplify
+ * would end up in an infinite loop. In particular, we construct
+ * an empty basic set that is not obviously empty.
+ * isl_basic_set_is_empty marks the basic set as empty.
+ * After projecting out i3, the variable can be dropped completely,
+ * but isl_basic_map_simplify refrains from doing so if the basic set
+ * is empty and would end up in an infinite loop if it didn't test
+ * explicitly for empty basic maps in the outer loop.
+ */
+static int test_simplify(isl_ctx *ctx)
+{
+ const char *str;
+ isl_basic_set *bset;
+ int empty;
+
+ str = "{ [i0, i1, i2, i3] : i0 >= -2 and 6i2 <= 4 + i0 + 5i1 and "
+ "i2 <= 22 and 75i2 <= 111 + 13i0 + 60i1 and "
+ "25i2 >= 38 + 6i0 + 20i1 and i0 <= -1 and i2 >= 20 and "
+ "i3 >= i2 }";
+ bset = isl_basic_set_read_from_str(ctx, str);
+ empty = isl_basic_set_is_empty(bset);
+ bset = isl_basic_set_project_out(bset, isl_dim_set, 3, 1);
+ isl_basic_set_free(bset);
+ if (!bset)
+ return -1;
+ if (!empty)
+ isl_die(ctx, isl_error_unknown,
+ "basic set should be empty", return -1);
+
+ return 0;
+}
+
+/* This is a regression test for a bug where isl_tab_basic_map_partial_lexopt
+ * with gbr context would fail to disable the use of the shifted tableau
+ * when transferring equalities for the input to the context, resulting
+ * in invalid sample values.
+ */
+static int test_partial_lexmin(isl_ctx *ctx)
+{
+ const char *str;
+ isl_basic_set *bset;
+ isl_basic_map *bmap;
+ isl_map *map;
+
+ str = "{ [1, b, c, 1 - c] -> [e] : 2e <= -c and 2e >= -3 + c }";
+ bmap = isl_basic_map_read_from_str(ctx, str);
+ str = "{ [a, b, c, d] : c <= 1 and 2d >= 6 - 4b - c }";
+ bset = isl_basic_set_read_from_str(ctx, str);
+ map = isl_basic_map_partial_lexmin(bmap, bset, NULL);
+ isl_map_free(map);
+
+ if (!map)
+ return -1;
+
+ return 0;
+}
+
+/* Check that the variable compression performed on the existentially
+ * quantified variables inside isl_basic_set_compute_divs is not confused
+ * by the implicit equalities among the parameters.
+ */
+static int test_compute_divs(isl_ctx *ctx)
+{
+ const char *str;
+ isl_basic_set *bset;
+ isl_set *set;
+
+ str = "[a, b, c, d, e] -> { [] : exists (e0: 2d = b and a <= 124 and "
+ "b <= 2046 and b >= 0 and b <= 60 + 64a and 2e >= b + 2c and "
+ "2e >= b and 2e <= 1 + b and 2e <= 1 + b + 2c and "
+ "32768e0 >= -124 + a and 2097152e0 <= 60 + 64a - b) }";
+ bset = isl_basic_set_read_from_str(ctx, str);
+ set = isl_basic_set_compute_divs(bset);
+ isl_set_free(set);
+ if (!set)
+ return -1;
+
+ return 0;
+}
+
struct {
const char *name;
int (*fn)(isl_ctx *ctx);
} tests [] = {
+ { "compute divs", &test_compute_divs },
+ { "partial lexmin", &test_partial_lexmin },
+ { "simplify", &test_simplify },
{ "curry", &test_curry },
{ "piecewise multi affine expressions", &test_pw_multi_aff },
{ "conversion", &test_conversion },
{ "factorize", &test_factorize },
{ "subset", &test_subset },
{ "subtract", &test_subtract },
+ { "lexmin", &test_lexmin },
};
int main()
test_convex_hull(ctx);
test_gist(ctx);
test_closure(ctx);
- test_lexmin(ctx);
isl_ctx_free(ctx);
return 0;
error: