From 172b680822c3b8e6c30e3b6dff519b2299938ef4 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 15 Jul 2015 11:01:01 +0200 Subject: [PATCH] isl_coalesce.c: coalesce_with_subs: do not add div constraints to basic map Ever since 81fed9f (isl_map_coalesce: handle divs that have been simplified away in one basic map, Fri Oct 10 11:49:16 2014 +0200), we try adding back divs to a basic map from another basic map that may have been simplified away using the equalities in the basic map. In this process, the div constraints also get added to the basic map and they therefore also get added to the tableau, if only since e72b919 (isl_coalesce.c: coalesce_with_subs: add div constraints to tableau, Thu Jan 29 10:59:15 2015 +0100). However, the tableau also contains the equalities on the variables corresponding to the integer divisions that are derived from the equalities in both basic maps. Combined with the div constraints, these equalities may imply constraints on the other variables that do not hold in the original input. Instead of adding the div constraints to both basic map and tableau, do not add them to either. This also preserves the consistency between basic map and tableau and avoids the problem above. Although this issue has led to the wrong coalescing conclusion in practice, it is difficult to extract a test case. Reported-by: Tobias Grosser Signed-off-by: Sven Verdoolaege --- isl_coalesce.c | 69 +++++++++++++++++++++++----------------------------------- 1 file changed, 27 insertions(+), 42 deletions(-) diff --git a/isl_coalesce.c b/isl_coalesce.c index 5e7f9a8d..3418bb2d 100644 --- a/isl_coalesce.c +++ b/isl_coalesce.c @@ -2142,18 +2142,26 @@ error: return NULL; } -/* Add variables to "tab" corresponding to the elements in "list" - * that are not set to NaN. +/* Add variables to info->bmap and info->tab corresponding to the elements + * in "list" that are not set to NaN. + * "extra_var" is the number of these elements. * "dim" is the offset in the variables of "tab" where we should * start considering the elements in "list". * When this function returns, the total number of variables in "tab" * is equal to "dim" plus the number of elements in "list". */ -static int add_sub_vars(struct isl_tab *tab, __isl_keep isl_aff_list *list, - int dim) +static int add_sub_vars(struct isl_coalesce_info *info, + __isl_keep isl_aff_list *list, int dim, int extra_var) { int i, n; + isl_space *space; + space = isl_basic_map_get_space(info->bmap); + info->bmap = isl_basic_map_cow(info->bmap); + info->bmap = isl_basic_map_extend_space(info->bmap, space, + extra_var, 0, 0); + if (!info->bmap) + return -1; n = isl_aff_list_n_aff(list); for (i = 0; i < n; ++i) { int is_nan; @@ -2164,9 +2172,15 @@ static int add_sub_vars(struct isl_tab *tab, __isl_keep isl_aff_list *list, isl_aff_free(aff); if (is_nan < 0) return -1; + if (is_nan) + continue; - if (!is_nan && isl_tab_insert_var(tab, dim + i) < 0) + if (isl_tab_insert_var(info->tab, dim + i) < 0) return -1; + if (isl_basic_map_alloc_div(info->bmap) < 0) + return -1; + if (i != n - 1) + isl_basic_map_swap_div(info->bmap, i, n - 1); } return 0; @@ -2217,53 +2231,33 @@ error: return -1; } -/* Add variables to info->tab corresponding to the elements in "list" - * that are not set to NaN. The value of the added variable - * is fixed to the purely affine expression defined by the element. +/* Add variables to info->tab and info->bmap corresponding to the elements + * in "list" that are not set to NaN. The value of the added variable + * in info->tab is fixed to the purely affine expression defined by the element. * "dim" is the offset in the variables of info->tab where we should * start considering the elements in "list". * When this function returns, the total number of variables in info->tab * is equal to "dim" plus the number of elements in "list". - * Additionally, add the div constraints that have been added info->bmap - * after the tableau was constructed to info->tab. These constraints - * start at position "n_ineq" in info->bmap. - * The constraints need to be added to the tableau before - * the equalities assigning the purely affine expression - * because the position needs to match that in info->bmap. - * They are frozen because the corresponding added equality is a consequence - * of the two div constraints and the other equalities, meaning that - * the div constraints would otherwise get marked as redundant, - * while they are only redundant with respect to the extra equalities - * added to the tableau, which do not appear explicitly in the basic map. */ static int add_subs(struct isl_coalesce_info *info, - __isl_keep isl_aff_list *list, int dim, int n_ineq) + __isl_keep isl_aff_list *list, int dim) { - int i, extra_var, extra_con; + int extra_var; int n; - unsigned n_eq = info->bmap->n_eq; if (!list) return -1; n = isl_aff_list_n_aff(list); extra_var = n - (info->tab->n_var - dim); - extra_con = info->bmap->n_ineq - n_ineq; if (isl_tab_extend_vars(info->tab, extra_var) < 0) return -1; - if (isl_tab_extend_cons(info->tab, extra_con + 2 * extra_var) < 0) + if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0) return -1; - if (add_sub_vars(info->tab, list, dim) < 0) + if (add_sub_vars(info, list, dim, extra_var) < 0) return -1; - for (i = n_ineq; i < info->bmap->n_ineq; ++i) { - if (isl_tab_add_ineq(info->tab, info->bmap->ineq[i]) < 0) - return -1; - if (isl_tab_freeze_constraint(info->tab, n_eq + i) < 0) - return -1; - } - return add_sub_equalities(info->tab, list, dim); } @@ -2273,9 +2267,6 @@ static int add_subs(struct isl_coalesce_info *info, * is equal to the number of integer divisions in "i", while the number * of NaN elements in the list is equal to the number of integer divisions * in "j". - * Adding extra integer divisions to "j" through isl_basic_map_align_divs - * also adds the corresponding div constraints. These need to be added - * to the corresponding tableau as well in add_subs to maintain consistency. * * If no coalescing can be performed, then we need to revert basic map "j" * to its original state. We do the same if basic map "i" gets dropped @@ -2290,19 +2281,13 @@ static enum isl_change coalesce_with_subs(int i, int j, struct isl_tab_undo *snap; unsigned dim; enum isl_change change; - int n_ineq; bmap_j = isl_basic_map_copy(info[j].bmap); - n_ineq = info[j].bmap->n_ineq; - info[j].bmap = isl_basic_map_align_divs(info[j].bmap, info[i].bmap); - if (!info[j].bmap) - goto error; - snap = isl_tab_snap(info[j].tab); dim = isl_basic_map_dim(bmap_j, isl_dim_all); dim -= isl_basic_map_dim(bmap_j, isl_dim_div); - if (add_subs(&info[j], list, dim, n_ineq) < 0) + if (add_subs(&info[j], list, dim) < 0) goto error; change = coalesce_local_pair(i, j, info); -- 2.11.4.GIT