From c9fb3b769f5344738ce4abdb14bb93514b9fbf62 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 29 Apr 2015 16:35:19 +0200 Subject: [PATCH] isl_basic_map_simplify: remove integer coefficients from integer divisions If a variable has an integer coefficient inside the definition of an integer division, then it can safely be pulled out of the integer division. Do so to simplify the expression. It would be nice if we could perform this check only when there is some potential of finding integer coefficients, but unfortunately there are currently many places where an integer division is introduced or modified. Introducing integer divisions mainly happens inside set_div_from_lower_bound, but there are several places where affine expressions are plugged into div expressions, which may also result in integer coefficients in the result. Signed-off-by: Sven Verdoolaege --- isl_map_simplify.c | 75 +++++++++++++++++++++++++++++++++++++++ test_inputs/codegen/cloog/faber.c | 4 +-- 2 files changed, 77 insertions(+), 2 deletions(-) diff --git a/isl_map_simplify.c b/isl_map_simplify.c index 91456901..255c50f5 100644 --- a/isl_map_simplify.c +++ b/isl_map_simplify.c @@ -375,6 +375,80 @@ struct isl_basic_set *isl_basic_set_normalize_constraints( (struct isl_basic_map *)bset); } +/* Assuming the variable at position "pos" has an integer coefficient + * in integer division "div", extract it from this integer division. + * "pos" is as determined by isl_basic_map_offset, i.e., pos == 0 + * corresponds to the constant term. + * + * That is, the integer division is of the form + * + * floor((... + c * d * x_pos + ...)/d) + * + * Replace it by + * + * floor((... + 0 * x_pos + ...)/d) + c * x_pos + */ +static __isl_give isl_basic_map *remove_var_from_div( + __isl_take isl_basic_map *bmap, int div, int pos) +{ + isl_int shift; + + isl_int_init(shift); + isl_int_divexact(shift, bmap->div[div][1 + pos], bmap->div[div][0]); + isl_int_neg(shift, shift); + bmap = isl_basic_map_shift_div(bmap, div, pos, shift); + isl_int_clear(shift); + + return bmap; +} + +/* Check if integer division "div" has any integral coefficient + * (or constant term). If so, extract them from the integer division. + */ +static __isl_give isl_basic_map *remove_independent_vars_from_div( + __isl_take isl_basic_map *bmap, int div) +{ + int i; + unsigned total = 1 + isl_basic_map_total_dim(bmap); + + for (i = 0; i < total; ++i) { + if (isl_int_is_zero(bmap->div[div][1 + i])) + continue; + if (!isl_int_is_divisible_by(bmap->div[div][1 + i], + bmap->div[div][0])) + continue; + bmap = remove_var_from_div(bmap, div, i); + if (!bmap) + break; + } + + return bmap; +} + +/* Check if any known integer division has any integral coefficient + * (or constant term). If so, extract them from the integer division. + */ +static __isl_give isl_basic_map *remove_independent_vars_from_divs( + __isl_take isl_basic_map *bmap) +{ + int i; + + if (!bmap) + return NULL; + if (bmap->n_div == 0) + return bmap; + + for (i = 0; i < bmap->n_div; ++i) { + if (isl_int_is_zero(bmap->div[i][0])) + continue; + bmap = remove_independent_vars_from_div(bmap, i); + if (!bmap) + break; + } + + return bmap; +} + /* Remove any common factor in numerator and denominator of the div expression, * not taking into account the constant term. * That is, if the div is of the form @@ -1318,6 +1392,7 @@ struct isl_basic_map *isl_basic_map_simplify(struct isl_basic_map *bmap) if (isl_basic_map_plain_is_empty(bmap)) break; bmap = isl_basic_map_normalize_constraints(bmap); + bmap = remove_independent_vars_from_divs(bmap); bmap = normalize_div_expressions(bmap); bmap = remove_duplicate_divs(bmap, &progress); bmap = eliminate_unit_divs(bmap, &progress); diff --git a/test_inputs/codegen/cloog/faber.c b/test_inputs/codegen/cloog/faber.c index b100b7b3..934aa82e 100644 --- a/test_inputs/codegen/cloog/faber.c +++ b/test_inputs/codegen/cloog/faber.c @@ -86,13 +86,13 @@ S1(c0, c1, c2); } if (c0 >= 79 && c0 % 14 >= 9) { - for (int c2 = max((c0 - 70) / 14 + 24, (c0 - 70) / 14 - (3 * c0 + 14) / 14 + 49); c2 <= (c0 - 70) / 14 - (3 * c0 + 17) / 14 + 56; c2 += 1) + for (int c2 = max(c0 / 14 + 19, -((3 * c0 + 14) / 14) + c0 / 14 + 44); c2 <= -((3 * c0 + 17) / 14) + c0 / 14 + 51; c2 += 1) S1(c0, c0 / 14 - 5, c2); } else if (c0 <= 69 && c0 % 14 >= 9) { if (c0 <= 41) S7(c0, -3, 6); S6(c0, c0 / 14 - 5, 8); - for (int c2 = -((-c0 + 83) / 14) - (3 * c0 + 14) / 14 + 49; c2 <= -((-c0 + 83) / 14) - (3 * c0 + 17) / 14 + 56; c2 += 1) + for (int c2 = -((3 * c0 + 14) / 14) + c0 / 14 + 44; c2 <= -((3 * c0 + 17) / 14) + c0 / 14 + 51; c2 += 1) S1(c0, c0 / 14 - 5, c2); } for (int c1 = (c0 + 5) / 14 - 5; c1 < 0; c1 += 1) { -- 2.11.4.GIT