From 2049680c6e045e8e743db07bb2f1b4013f31ad48 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 20 Jun 2016 17:52:35 +0200 Subject: [PATCH] isl_map_coalesce: allow extensions to stick out by one That is, allow the basic map that is about to be extended to include the other one to also have some cut constraints, as long as relaxing these cut constraints by one makes them valid. The function is_adj_eq_extension has already been extended to is_relaxed_extension to handle these cut constraints in the previous commit. This commit simply collects the cut constraints and checks that relaxing them by one is sufficient. Signed-off-by: Sven Verdoolaege --- isl_coalesce.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++---------- isl_test.c | 8 +++++++ 2 files changed, 65 insertions(+), 11 deletions(-) diff --git a/isl_coalesce.c b/isl_coalesce.c index 7fee3087..77f9d212 100644 --- a/isl_coalesce.c +++ b/isl_coalesce.c @@ -1735,6 +1735,33 @@ static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info) return change; } +/* Check if all inequality constraints of "i" that cut "j" cease + * to be cut constraints if they are relaxed by one. + * If so, collect the cut constraints in "list". + * The caller is responsible for allocating "list". + */ +static isl_bool all_cut_by_one(int i, int j, struct isl_coalesce_info *info, + int *list) +{ + int l, n; + + n = 0; + for (l = 0; l < info[i].bmap->n_ineq; ++l) { + enum isl_ineq_type type; + + if (info[i].ineq[l] != STATUS_CUT) + continue; + type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[l]); + if (type == isl_ineq_error) + return isl_bool_error; + if (type != isl_ineq_redundant) + return isl_bool_false; + list[n++] = l; + } + + return isl_bool_true; +} + /* Given two basic maps such that "j" has at least one equality constraint * that is adjacent to an inequality constraint of "i" and such that "i" has * exactly one inequality constraint that is adjacent to an equality @@ -1744,29 +1771,48 @@ static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info) * or cut constraints of the other basic map. * However, none of the equality constraints of "i" are cut constraints. * - * If "i" has any "cut" (in)equality, then relaxing the inequality - * by one would not result in a basic map that contains the other - * basic map. However, it may still be possible to wrap in the other - * basic map. + * If "i" has any "cut" inequality constraints, then check if relaxing + * each of them by one is sufficient for them to become valid. + * If so, check if the inequality constraint adjacent to an equality + * constraint of "j" along with all these cut constraints + * can be relaxed by one to contain exactly "j". + * Otherwise, or if this fails, check if "j" can be wrapped into "i". */ static enum isl_change check_single_adj_eq(int i, int j, struct isl_coalesce_info *info) { enum isl_change change = isl_change_none; int k; - int any_cut; + int n_cut; + int *relax; + isl_ctx *ctx; + isl_bool try_relax; - any_cut = any(info[i].ineq, info[i].bmap->n_ineq, STATUS_CUT); + n_cut = count(info[i].ineq, info[i].bmap->n_ineq, STATUS_CUT); k = find(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_EQ); - if (!any_cut) { - change = is_relaxed_extension(i, j, 1, &k, info); - if (change != isl_change_none) - return change; + if (n_cut > 0) { + ctx = isl_basic_map_get_ctx(info[i].bmap); + relax = isl_calloc_array(ctx, int, 1 + n_cut); + if (!relax) + return isl_change_error; + relax[0] = k; + try_relax = all_cut_by_one(i, j, info, relax + 1); + if (try_relax < 0) + change = isl_change_error; + } else { + try_relax = isl_bool_true; + relax = &k; } + if (try_relax && change == isl_change_none) + change = is_relaxed_extension(i, j, 1 + n_cut, relax, info); + if (n_cut > 0) + free(relax); + if (change != isl_change_none) + return change; - change = can_wrap_in_facet(i, j, k, info, any_cut); + change = can_wrap_in_facet(i, j, k, info, n_cut > 0); return change; } diff --git a/isl_test.c b/isl_test.c index 1ebfef35..c129f3e1 100644 --- a/isl_test.c +++ b/isl_test.c @@ -1870,6 +1870,14 @@ struct { "[x, y] : 0 <= x <= 10 and 1 <= y <= 10 }" }, { 1, "{ [a] : a <= 8 and " "(a mod 10 = 7 or a mod 10 = 8 or a mod 10 = 9) }" }, + { 1, "{ [x, y] : 2y = -x and x <= 0 or " + "x <= -1 and 2y <= -x - 1 and 2y >= x - 1 }" }, + { 0, "{ [x, y] : 2y = -x and x <= 0 or " + "x <= -2 and 2y <= -x - 1 and 2y >= x - 1 }" }, + { 1, "{ [a] : (a <= 0 and 3*floor((a)/3) = a) or " + "(a < 0 and 3*floor((a)/3) < a) }" }, + { 1, "{ [a] : (a <= 0 and 3*floor((a)/3) = a) or " + "(a < -1 and 3*floor((a)/3) < a) }" }, }; /* A specialized coalescing test case that would result -- 2.11.4.GIT