From 3961a579833bebbcd7192f4f4fa5464937b6562a Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 14 Mar 2013 17:47:14 +0100 Subject: [PATCH] isl_basic_map_simplify: avoid infinite loop on empty input eliminate_divs_ineq skips the step of actually removing the div if the basic map is marked empty. This is needed because in the process of marking the basic map empty, the constraints may have been replaced by the canonical representation of an empty basic map which does not have any divs. However, the basic map may have already been marked empty before, possibly without having the constraints replaced by the canonical representation. In such cases, we would also skip the step that remove the div, but it would actually still be present and we would keep making "progress" in every iteration of isl_basic_map_simplify, resulting in an infinite loop. Reported-by: Tobias Grosser Signed-off-by: Sven Verdoolaege --- isl_map_simplify.c | 4 ++++ isl_test.c | 33 +++++++++++++++++++++++++++++++++ 2 files changed, 37 insertions(+) diff --git a/isl_map_simplify.c b/isl_map_simplify.c index 9057502..34d6094 100644 --- a/isl_map_simplify.c +++ b/isl_map_simplify.c @@ -1241,6 +1241,10 @@ struct isl_basic_map *isl_basic_map_simplify(struct isl_basic_map *bmap) return NULL; while (progress) { progress = 0; + if (!bmap) + break; + if (isl_basic_map_plain_is_empty(bmap)) + break; bmap = isl_basic_map_normalize_constraints(bmap); bmap = normalize_div_expressions(bmap); bmap = remove_duplicate_divs(bmap, &progress); diff --git a/isl_test.c b/isl_test.c index 8f03ddb..7c28f65 100644 --- a/isl_test.c +++ b/isl_test.c @@ -3804,10 +3804,43 @@ static int test_pw_multi_aff(isl_ctx *ctx) return 0; } +/* This is a regression test for a bug where isl_basic_map_simplify + * would end up in an infinite loop. In particular, we construct + * an empty basic set that is not obviously empty. + * isl_basic_set_is_empty marks the basic set as empty. + * After projecting out i3, the variable can be dropped completely, + * but isl_basic_map_simplify refrains from doing so if the basic set + * is empty and would end up in an infinite loop if it didn't test + * explicitly for empty basic maps in the outer loop. + */ +static int test_simplify(isl_ctx *ctx) +{ + const char *str; + isl_basic_set *bset; + int empty; + + str = "{ [i0, i1, i2, i3] : i0 >= -2 and 6i2 <= 4 + i0 + 5i1 and " + "i2 <= 22 and 75i2 <= 111 + 13i0 + 60i1 and " + "25i2 >= 38 + 6i0 + 20i1 and i0 <= -1 and i2 >= 20 and " + "i3 >= i2 }"; + bset = isl_basic_set_read_from_str(ctx, str); + empty = isl_basic_set_is_empty(bset); + bset = isl_basic_set_project_out(bset, isl_dim_set, 3, 1); + isl_basic_set_free(bset); + if (!bset) + return -1; + if (!empty) + isl_die(ctx, isl_error_unknown, + "basic set should be empty", return -1); + + return 0; +} + struct { const char *name; int (*fn)(isl_ctx *ctx); } tests [] = { + { "simplify", &test_simplify }, { "curry", &test_curry }, { "piecewise multi affine expressions", &test_pw_multi_aff }, { "conversion", &test_conversion }, -- 2.7.4