From a929cb74cb3eeaa3200f266fde48259b781baa85 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 10 Oct 2014 16:02:37 +0200 Subject: [PATCH] isl_map_coalesce: remove hidden factors from constraint coefficients Removing these hidden factors improves the chances of an inequality being recognized as adjacent to an equality. For example, the set { [x,y] : 2x = 3y and 0 <= y <= 4; [-3,-2] } would not get coalesced before because the inequality 0 <= y is not recognized as being adjacent to an equality of the second basic map. After removing common factors, the set looks like { [x,y] : 2x = 3y and 0 <= x - y <= 2; [-3,-2] } and now the constraint 0 <= x - y is recognized as being adjacent to an equality of the second basic map. Signed-off-by: Sven Verdoolaege --- isl_coalesce.c | 6 ++++++ isl_test.c | 7 +++++++ 2 files changed, 13 insertions(+) diff --git a/isl_coalesce.c b/isl_coalesce.c index ce396a95..18b1d45a 100644 --- a/isl_coalesce.c +++ b/isl_coalesce.c @@ -2304,6 +2304,9 @@ static __isl_give isl_map *update_basic_maps(__isl_take isl_map *map, * can be represented by a single basic map. * If so, replace the pair by the single basic map and start over. * + * We factor out any (hidden) common factor from the constraint + * coefficients to improve the detection of adjacent constraints. + * * Since we are constructing the tableaus of the basic maps anyway, * we exploit them to detect implicit equalities and redundant constraints. * This also helps the coalescing as it can ignore the redundant constraints. @@ -2342,6 +2345,9 @@ struct isl_map *isl_map_coalesce(struct isl_map *map) goto error; for (i = 0; i < map->n; ++i) { + map->p[i] = isl_basic_map_reduce_coefficients(map->p[i]); + if (!map->p[i]) + goto error; info[i].bmap = isl_basic_map_copy(map->p[i]); info[i].tab = isl_tab_from_basic_map(info[i].bmap, 0); if (!info[i].tab) diff --git a/isl_test.c b/isl_test.c index 73aff13e..c6e4cc82 100644 --- a/isl_test.c +++ b/isl_test.c @@ -1477,6 +1477,13 @@ struct { { 1, "{ [i, i] : exists (e0 = floor((1 + 2i)/3): 3e0 <= 2i and " "3e0 >= -1 + 2i and i <= 9 and i >= 1);" "[0, 0] }" }, + { 1, "{ [t1] : exists (e0 = floor((-11 + t1)/2): 2e0 = -11 + t1 and " + "t1 >= 13 and t1 <= 16);" + "[t1] : t1 <= 15 and t1 >= 12 }" }, + { 1, "{ [x,y] : x = 3y and 0 <= y <= 2; [-3,-1] }" }, + { 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] }" }, }; /* Test the functionality of isl_set_coalesce. -- 2.11.4.GIT