summaryloggraphiclog1graphiclog2commitcommitdifftreerefseditfork
rawpatchinlineside by side (parent: ecb2ef9)
rawpatchinlineside by side (parent: ecb2ef9)
| author | Sven Verdoolaege <sven@cerebras.net> | |
| Fri, 15 May 2020 14:18:33 +0000 (15 16:18 +0200) | ||
| committer | Sven Verdoolaege <sven@cerebras.net> | |
| Thu, 28 May 2020 08:34:23 +0000 (28 10:34 +0200) |
That is, improve handling of expressions that attain rational values.
The original implementation converts the isl_multi_aff objects
to isl_map objects, thereby removing elements from the domain
where either isl_multi_aff attains a rational value.
This is especially confusing when the affine expressions
are rational constants.
In particular, one of the isl_set_lexmin tests only worked
purely by accident because nothing (including 10)
is considered smaller than 1/2.
By the same token, 5 was not being considered smaller than 21/2.
This commit fixes this case.
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>
The original implementation converts the isl_multi_aff objects
to isl_map objects, thereby removing elements from the domain
where either isl_multi_aff attains a rational value.
This is especially confusing when the affine expressions
are rational constants.
In particular, one of the isl_set_lexmin tests only worked
purely by accident because nothing (including 10)
is considered smaller than 1/2.
By the same token, 5 was not being considered smaller than 21/2.
This commit fixes this case.
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>
| isl_aff.c | patchblobblamehistory | |
| isl_test.c | patchblobblamehistory |
diff --git a/isl_aff.c b/isl_aff.c
--- a/isl_aff.c
+++ b/isl_aff.c
@@ -4222,26 +4222,106 @@ __isl_give isl_set *isl_multi_aff_lex_lt_set(__isl_take isl_multi_aff *ma1,
return isl_multi_aff_lex_gt_set(ma2, ma1);
}
-/* Return the set of domain elements where "ma1" and "ma2"
- * satisfy "order".
+/* Return the set of domain elements where "ma1" is lexicographically
+ * greater than to "ma2". If "equal" is set, then include the domain
+ * elements where they are equal.
+ * Do this for the case where there are no entries.
+ * In this case, "ma1" cannot be greater than "ma2",
+ * but it is (greater than or) equal to "ma2".
*/
-static __isl_give isl_set *isl_multi_aff_order_set(
- __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2,
- __isl_give isl_map *order(__isl_take isl_space *set_space))
+static __isl_give isl_set *isl_multi_aff_lex_gte_set_0d(
+ __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2, int equal)
{
isl_space *space;
- isl_map *map1, *map2;
- isl_map *map, *ge;
- map1 = isl_map_from_multi_aff_internal(ma1);
- map2 = isl_map_from_multi_aff_internal(ma2);
- map = isl_map_range_product(map1, map2);
- space = isl_space_range(isl_map_get_space(map));
- space = isl_space_domain(isl_space_unwrap(space));
- ge = order(space);
- map = isl_map_intersect_range(map, isl_map_wrap(ge));
+ space = isl_multi_aff_get_domain_space(ma1);
+
+ isl_multi_aff_free(ma1);
+ isl_multi_aff_free(ma2);
+
+ if (equal)
+ return isl_set_universe(space);
+ else
+ return isl_set_empty(space);
+}
+
+/* Return the set where entry "i" of "ma1" and "ma2"
+ * satisfy the relation prescribed by "cmp".
+ */
+static __isl_give isl_set *isl_multi_aff_order_at(__isl_keep isl_multi_aff *ma1,
+ __isl_keep isl_multi_aff *ma2, int i,
+ __isl_give isl_set *(*cmp)(__isl_take isl_aff *aff1,
+ __isl_take isl_aff *aff2))
+{
+ isl_aff *aff1, *aff2;
+
+ aff1 = isl_multi_aff_get_at(ma1, i);
+ aff2 = isl_multi_aff_get_at(ma2, i);
+ return cmp(aff1, aff2);
+}
- return isl_map_domain(map);
+/* Return the set of domain elements where "ma1" is lexicographically
+ * greater than to "ma2". If "equal" is set, then include the domain
+ * elements where they are equal.
+ *
+ * In particular, for all but the final entry,
+ * include the set of elements where this entry is strictly greater in "ma1"
+ * and all previous entries are equal.
+ * The final entry is also allowed to be equal in the two functions
+ * if "equal" is set.
+ *
+ * The case where there are no entries is handled separately.
+ */
+static __isl_give isl_set *isl_multi_aff_lex_gte_set(
+ __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2, int equal)
+{
+ int i;
+ isl_size n;
+ isl_space *space;
+ isl_set *res;
+ isl_set *equal_set;
+ isl_set *gte;
+
+ if (isl_multi_aff_check_equal_space(ma1, ma2) < 0)
+ goto error;
+ n = isl_multi_aff_size(ma1);
+ if (n < 0)
+ goto error;
+ if (n == 0)
+ return isl_multi_aff_lex_gte_set_0d(ma1, ma2, equal);
+
+ space = isl_multi_aff_get_domain_space(ma1);
+ res = isl_set_empty(isl_space_copy(space));
+ equal_set = isl_set_universe(space);
+
+ for (i = 0; i + 1 < n; ++i) {
+ isl_bool empty;
+ isl_set *gt, *eq;
+
+ gt = isl_multi_aff_order_at(ma1, ma2, i, &isl_aff_gt_set);
+ gt = isl_set_intersect(gt, isl_set_copy(equal_set));
+ res = isl_set_union(res, gt);
+ eq = isl_multi_aff_order_at(ma1, ma2, i, &isl_aff_eq_set);
+ equal_set = isl_set_intersect(equal_set, eq);
+
+ empty = isl_set_is_empty(equal_set);
+ if (empty >= 0 && empty)
+ break;
+ }
+
+ if (equal)
+ gte = isl_multi_aff_order_at(ma1, ma2, n - 1, &isl_aff_ge_set);
+ else
+ gte = isl_multi_aff_order_at(ma1, ma2, n - 1, &isl_aff_gt_set);
+ isl_multi_aff_free(ma1);
+ isl_multi_aff_free(ma2);
+
+ gte = isl_set_intersect(gte, equal_set);
+ return isl_set_union(res, gte);
+error:
+ isl_multi_aff_free(ma1);
+ isl_multi_aff_free(ma2);
+ return NULL;
}
/* Return the set of domain elements where "ma1" is lexicographically
__isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
__isl_take isl_multi_aff *ma2)
{
- return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_ge);
+ return isl_multi_aff_lex_gte_set(ma1, ma2, 1);
}
/* Return the set of domain elements where "ma1" is lexicographically
__isl_give isl_set *isl_multi_aff_lex_gt_set(__isl_take isl_multi_aff *ma1,
__isl_take isl_multi_aff *ma2)
{
- return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_gt);
+ return isl_multi_aff_lex_gte_set(ma1, ma2, 0);
}
#define isl_multi_aff_zero_in_space isl_multi_aff_zero
diff --git a/isl_test.c b/isl_test.c
--- a/isl_test.c
+++ b/isl_test.c
"[a] -> [b = 0] : 0 < a <= 509 }" },
{ "{ rat: [i] : 1 <= 2i <= 9 }", "{ rat: [i] : 2i = 1 }" },
{ "{ rat: [i] : 1 <= 2i <= 9 or i >= 10 }", "{ rat: [i] : 2i = 1 }" },
+ { "{ rat: [i] : 21 <= 2i <= 29 or i = 5 }", "{ rat: [5] }" },
};
static int test_lexmin(struct isl_ctx *ctx)