summaryloggraphiclog1graphiclog2commitcommitdifftreerefseditfork
rawpatchinlineside by side (parent: 7415088)
rawpatchinlineside by side (parent: 7415088)
| author | Sven Verdoolaege <sven@cerebras.net> | |
| Fri, 24 Apr 2020 12:49:23 +0000 (24 14:49 +0200) | ||
| committer | Sven Verdoolaege <sven@cerebras.net> | |
| Sat, 16 May 2020 20:17:24 +0000 (16 22:17 +0200) |
The set from which a lower bound is constructed is not allowed
to have unknown local variables.
Originally, unknown local variables got removed by computing
explicit representations as integer divisions.
This can be quite costly, however, and isl-0.22.1-195-g240551690c
(isl_set_get_simple_fixed_box_hull: do not compute integer divisions,
Sun Mar 22 23:42:07 2020 +0100) replaced this by a removal
of all constraints involving unknown local variables.
This is also more in line with the intent of
isl_set_get_simple_fixed_box_hull, which is to only look
for bounds that are explicitly available in the input representation.
Unfortunately, this can also produce less accurate results
in some cases, including the test case that was added in that commit.
Remove the unknown local variables using (Fourier-Motzkin) elimination
instead. This is more expensive than simply dropping constraints,
but should still be a lot less expensive than computing
explicit representations, especially if the latter results
in a lot of different cases.
It does mean that constraints will be considered for lower bounds
that do not appear directly in the input representation, but
the additional constraints considered are simple combinations of
those that do. Furthermore, users of this function in the language
bindings cannot perform this elimination themselves since
it is considered low-level and not exported to the bindings.
Doing the elimination beforehand would also mean
that the set that is used for computing the size is also affected,
which is not the case when doing it internally.
It is not clear if this has any practical effect, however.
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>
to have unknown local variables.
Originally, unknown local variables got removed by computing
explicit representations as integer divisions.
This can be quite costly, however, and isl-0.22.1-195-g240551690c
(isl_set_get_simple_fixed_box_hull: do not compute integer divisions,
Sun Mar 22 23:42:07 2020 +0100) replaced this by a removal
of all constraints involving unknown local variables.
This is also more in line with the intent of
isl_set_get_simple_fixed_box_hull, which is to only look
for bounds that are explicitly available in the input representation.
Unfortunately, this can also produce less accurate results
in some cases, including the test case that was added in that commit.
Remove the unknown local variables using (Fourier-Motzkin) elimination
instead. This is more expensive than simply dropping constraints,
but should still be a lot less expensive than computing
explicit representations, especially if the latter results
in a lot of different cases.
It does mean that constraints will be considered for lower bounds
that do not appear directly in the input representation, but
the additional constraints considered are simple combinations of
those that do. Furthermore, users of this function in the language
bindings cannot perform this elimination themselves since
it is considered low-level and not exported to the bindings.
Doing the elimination beforehand would also mean
that the set that is used for computing the size is also affected,
which is not the case when doing it internally.
It is not clear if this has any practical effect, however.
Signed-off-by: Sven Verdoolaege <sven@cerebras.net>
| isl_box.c | patchblobblamehistory | |
| isl_test.c | patchblobblamehistory |
diff --git a/isl_box.c b/isl_box.c
--- a/isl_box.c
+++ b/isl_box.c
* Note that while evaluating the size corresponding to a lower bound,
* an affine expression is constructed from the lower bound.
* This lower bound may therefore not have any unknown local variables.
- * Remove all constraints with unknown local variables up front such that
- * the unknown local variables themselves also get removed
- * (since that makes them redundant).
+ * Eliminate any unknown local variables up front.
* No such restriction needs to be imposed on the set over which
* the size is computed.
*/
info.pos = isl_map_dim(map, isl_dim_in);
info.bset = isl_basic_map_wrap(isl_map_simple_hull(map));
bset = isl_basic_set_copy(info.bset);
- bset = isl_basic_set_drop_constraints_involving_unknown_divs(bset);
+ bset = isl_basic_set_remove_unknown_divs(bset);
if (info.pos < 0)
bset = isl_basic_set_free(bset);
if (isl_basic_set_foreach_constraint(bset,
diff --git a/isl_test.c b/isl_test.c
--- a/isl_test.c
+++ b/isl_test.c
"{ S[0, -4] }", "{ S[10, 9] }" },
{ "{ [i=0:10] : exists (e0, e1: 3e1 >= 1 + 2e0 and "
"8e1 <= -1 + 5i - 5e0 and 2e1 >= 1 + 2i - 5e0) }",
- "{ [0] }", "{ [11] }" },
+ "{ [3] }", "{ [8] }" },
+ { "[N] -> { [w = 0:17] : exists (e0: w < 2N and "
+ "-1 + w <= e0 <= w and 2e0 >= N + w and w <= 2e0 <= 15 + w) }",
+ "[N] -> { [N] }", "{ [9] }" },
};
/* Perform basic isl_set_get_simple_fixed_box_hull tests.