From 6c6186f6655c8d1cd1264c9762a93480244b1b88 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 19 Feb 2013 15:44:19 +0100 Subject: [PATCH] isl_map_simplify.c: check_for_div_constraints: also check for "better" ones 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 --- isl_map_simplify.c | 36 ++++++++++++++++++++++++++++--- test_inputs/codegen/omega/floor_bound-6.c | 2 +- test_inputs/codegen/omega/lefur04-0.c | 2 +- 3 files changed, 35 insertions(+), 5 deletions(-) diff --git a/isl_map_simplify.c b/isl_map_simplify.c index c83888a0..a10da544 100644 --- a/isl_map_simplify.c +++ b/isl_map_simplify.c @@ -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])) diff --git a/test_inputs/codegen/omega/floor_bound-6.c b/test_inputs/codegen/omega/floor_bound-6.c index 06b32e58..743b0c93 100644 --- a/test_inputs/codegen/omega/floor_bound-6.c +++ b/test_inputs/codegen/omega/floor_bound-6.c @@ -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); diff --git a/test_inputs/codegen/omega/lefur04-0.c b/test_inputs/codegen/omega/lefur04-0.c index 079505ef..38639352 100644 --- a/test_inputs/codegen/omega/lefur04-0.c +++ b/test_inputs/codegen/omega/lefur04-0.c @@ -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); -- 2.11.4.GIT