From b6d921dfb89a4fcec6a79ce6bdeeb33be5778d57 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 11 Oct 2014 13:55:08 +0200 Subject: [PATCH] isl_map_coalesce: try and coalesce basic maps with different integer divisions If two basic maps have unknown or different integer divisions, then it may still be possible to coalesce them if the existentially quantified variables of one basic map happen to satisfy or be adjacent to the constraints on the quantified variables of the other basic map. In principle we should consider all possible matchings between existentially quantified variables or use heuristics to determine which existentially quantified variable in one basic map should be matched to which existentially quantified variable in the other basic map. Currently, however, we only consider the given order of the existentially quantified variables, which is already an improvement compared to not allowing unknown or different integer divisions at all. We do require that the total number of existentially quantified variables is the same in both basic maps. Note that this results in more pairs of basic maps being considered for coalescing, but if the default matching between existentially quantified variables is not fruitful, then a separating constraint should be found fairly quickly. The previous two commits made sure that the different ways of combining two basic maps into one can handle the case where the integer divisions are different in the two input basic maps. Signed-off-by: Sven Verdoolaege --- isl_coalesce.c | 9 ++++++++- isl_test.c | 5 +++++ 2 files changed, 13 insertions(+), 1 deletion(-) diff --git a/isl_coalesce.c b/isl_coalesce.c index e2d83fd8..b0f31509 100644 --- a/isl_coalesce.c +++ b/isl_coalesce.c @@ -2221,7 +2221,8 @@ static enum isl_change check_coalesce_eq(int i, int j, * Otherwise, return isl_change_none. * * We first check if the two basic maps live in the same local space. - * If so, we do the complete check. Otherwise, we check if one is + * If so, we do the complete check. Otherwise, we check if they have + * the same number of integer divisions and can be coalesced, if one is * an obvious subset of the other or if the extra integer divisions * of one basic map can be simplified away using the extra equalities * of the other basic map. @@ -2238,6 +2239,12 @@ static enum isl_change coalesce_pair(int i, int j, if (same) return coalesce_local_pair(i, j, info); + if (info[i].bmap->n_div == info[j].bmap->n_div) { + change = coalesce_local_pair(i, j, info); + if (change != isl_change_none) + return change; + } + change = check_coalesce_subset(i, j, info); if (change != isl_change_none) return change; diff --git a/isl_test.c b/isl_test.c index c6e4cc82..ecbd0022 100644 --- a/isl_test.c +++ b/isl_test.c @@ -1484,6 +1484,11 @@ struct { { 1, "{ [x,y] : 2x = 3y and 0 <= y <= 4; [-3,-2] }" }, { 0, "{ [x,y] : 2x = 3y and 0 <= y <= 4; [-2,-2] }" }, { 0, "{ [x,y] : 2x = 3y and 0 <= y <= 4; [-3,-1] }" }, + { 1, "{ [i] : exists j : i = 4 j and 0 <= i <= 100;" + "[i] : exists j : 1 <= i <= 100 and i >= 4j + 1 and " + "i <= 4j + 2 }" }, + { 1, "{ [c0] : (exists (e0 : c0 - 1 <= 3e0 <= c0)) or " + "(exists (e0 : 3e0 = -2 + c0)) }" }, }; /* Test the functionality of isl_set_coalesce. -- 2.11.4.GIT