From 32aabe2c05cbaa2df5907aee48d1874936266a29 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 14 Jun 2013 10:52:31 +0200 Subject: [PATCH] isl_map_gist_basic_map: remove alignment of context divs with all basic maps Ever since isl_map_gist was introduced in 0b4619a (add isl_set_gist, Thu Sep 25 15:24:24 2008 +0200), isl_map_gist (now isl_map_gist_basic_map) aligns the divs of the context with those of every basic map before computing the gist of each basic map individually. Presumably the reason for this global alignment is that if the same divs appear is multiple basic maps, then the context divs only have to be aligned to them once instead of once per basic map. The downside, however, is that if the basic maps have different divs, then they may end up spreading from one basic map to another, possibly resulting in a more complicated output, which is contrary to what you would expect from a "gist" operation. We remove the global alignment of divs. If this turns out to be problematic in some way, we can consider different strategies. Note that the new test case currently does not trigger even without this change due to simplifications during parsing of the input. We keep the test case to illustrate the change and in case parsing changes. Signed-off-by: Sven Verdoolaege --- isl_map_simplify.c | 2 -- isl_test.c | 31 +++++++++++++++++++++++++++++-- 2 files changed, 29 insertions(+), 4 deletions(-) diff --git a/isl_map_simplify.c b/isl_map_simplify.c index 5dcd52d..b3ceb80 100644 --- a/isl_map_simplify.c +++ b/isl_map_simplify.c @@ -2225,8 +2225,6 @@ __isl_give isl_map *isl_map_gist_basic_map(__isl_take isl_map *map, map = isl_map_compute_divs(map); if (!map) goto error; - for (i = 0; i < map->n; ++i) - context = isl_basic_map_align_divs(context, map->p[i]); for (i = map->n - 1; i >= 0; --i) { map->p[i] = isl_basic_map_gist(map->p[i], isl_basic_map_copy(context)); diff --git a/isl_test.c b/isl_test.c index 662f481..a508534 100644 --- a/isl_test.c +++ b/isl_test.c @@ -1093,10 +1093,11 @@ void test_gist_case(struct isl_ctx *ctx, const char *name) fclose(input); } -void test_gist(struct isl_ctx *ctx) +static int test_gist(struct isl_ctx *ctx) { const char *str; isl_basic_set *bset1, *bset2; + isl_map *map1, *map2; test_gist_case(ctx, "gist1"); @@ -1122,6 +1123,32 @@ void test_gist(struct isl_ctx *ctx) bset1 = isl_basic_set_gist(bset1, bset2); assert(bset1 && bset1->n_div == 0); isl_basic_set_free(bset1); + + /* Check that the integer divisions of the second disjunct + * do not spread to the first disjunct. + */ + str = "[t1] -> { S_0[] -> A[o0] : (exists (e0 = [(-t1 + o0)/16]: " + "16e0 = -t1 + o0 and o0 >= 0 and o0 <= 15 and t1 >= 0)) or " + "(exists (e0 = [(-1 + t1)/16], " + "e1 = [(-16 + t1 - 16e0)/4294967296]: " + "4294967296e1 = -16 + t1 - o0 - 16e0 and " + "16e0 <= -1 + t1 and 16e0 >= -16 + t1 and o0 >= 0 and " + "o0 <= 4294967295 and t1 <= -1)) }"; + map1 = isl_map_read_from_str(ctx, str); + str = "[t1] -> { S_0[] -> A[o0] : t1 >= 0 and t1 <= 4294967295 }"; + map2 = isl_map_read_from_str(ctx, str); + map1 = isl_map_gist(map1, map2); + if (!map1) + return -1; + if (map1->n != 1) + isl_die(ctx, isl_error_unknown, "expecting single disjunct", + isl_map_free(map1); return -1); + if (isl_basic_map_dim(map1->p[0], isl_dim_div) != 1) + isl_die(ctx, isl_error_unknown, "expecting single div", + isl_map_free(map1); return -1); + isl_map_free(map1); + + return 0; } int test_coalesce_set(isl_ctx *ctx, const char *str, int check_one) @@ -4340,6 +4367,7 @@ struct { { "subset", &test_subset }, { "subtract", &test_subtract }, { "lexmin", &test_lexmin }, + { "gist", &test_gist }, { "piecewise quasi-polynomials", &test_pwqp }, }; @@ -4370,7 +4398,6 @@ int main() test_dim(ctx); test_application(ctx); test_convex_hull(ctx); - test_gist(ctx); test_closure(ctx); isl_ctx_free(ctx); return 0; -- 2.7.4