From 22c210cb91b56e8bca8924dd0d88296155fe3311 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 1 Sep 2009 22:59:21 +0200 Subject: [PATCH] isl_basic_map_gauss: try not to remove any div definitions After computing divs, the result may get simplified and during this simplification, isl_basic_map_gauss may actually remove some divs because it is trying to play safe wrt circular div definitions. By keeping the divs ordered, divs can safely be eliminated without introducing any circular definitions. --- isl_map.c | 7 ++++--- isl_map_private.h | 1 + isl_map_simplify.c | 26 ++++++++++++++++---------- 3 files changed, 21 insertions(+), 13 deletions(-) diff --git a/isl_map.c b/isl_map.c index 7a3344d9..3d6ed19e 100644 --- a/isl_map.c +++ b/isl_map.c @@ -4080,7 +4080,7 @@ struct isl_set *isl_basic_set_union( } /* Order divs such that any div only depends on previous divs */ -static struct isl_basic_map *order_divs(struct isl_basic_map *bmap) +struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap) { int i; unsigned off = isl_dim_total(bmap->dim); @@ -4101,7 +4101,8 @@ static struct isl_basic_map *order_divs(struct isl_basic_map *bmap) struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset) { - return (struct isl_basic_set *)order_divs((struct isl_basic_map *)bset); + return (struct isl_basic_set *) + isl_basic_map_order_divs((struct isl_basic_map *)bset); } /* Look for a div in dst that corresponds to the div "div" in src. @@ -4141,7 +4142,7 @@ struct isl_basic_map *isl_basic_map_align_divs( for (i = 0; i < src->n_div; ++i) isl_assert(src->ctx, !isl_int_is_zero(src->div[i][0]), goto error); - src = order_divs(src); + src = isl_basic_map_order_divs(src); dst = isl_basic_map_cow(dst); dst = isl_basic_map_extend_dim(dst, isl_dim_copy(dst->dim), src->n_div, 0, 2 * src->n_div); diff --git a/isl_map_private.h b/isl_map_private.h index 23e0bc79..bad2f58a 100644 --- a/isl_map_private.h +++ b/isl_map_private.h @@ -66,6 +66,7 @@ struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap); struct isl_map *isl_map_compute_divs(struct isl_map *map); struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset); void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b); +struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap); struct isl_basic_map *isl_basic_map_align_divs( struct isl_basic_map *dst, struct isl_basic_map *src); struct isl_basic_set *isl_basic_set_align_divs( diff --git a/isl_map_simplify.c b/isl_map_simplify.c index 38981aaf..38edcb66 100644 --- a/isl_map_simplify.c +++ b/isl_map_simplify.c @@ -441,17 +441,18 @@ static struct isl_basic_map *eliminate_divs_ineq( return bmap; } +/* Assumes divs have been ordered if keep_divs is set. + */ static void eliminate_var_using_equality(struct isl_basic_map *bmap, - unsigned pos, isl_int *eq, int *progress) + unsigned pos, isl_int *eq, int keep_divs, int *progress) { unsigned total; int k; - int contains_divs; + int last_div; total = isl_basic_map_total_dim(bmap); - contains_divs = - isl_seq_first_non_zero(eq + 1 + isl_dim_total(bmap->dim), - bmap->n_div) != -1; + last_div = isl_seq_last_non_zero(eq + 1 + isl_dim_total(bmap->dim), + bmap->n_div); for (k = 0; k < bmap->n_eq; ++k) { if (bmap->eq[k] == eq) continue; @@ -481,12 +482,15 @@ static void eliminate_var_using_equality(struct isl_basic_map *bmap, /* We need to be careful about circular definitions, * so for now we just remove the definition of div k * if the equality contains any divs. + * If keep_divs is set, then the divs have been ordered + * and we can keep the definition as long as the result + * is still ordered. */ - if (contains_divs) - isl_seq_clr(bmap->div[k], 1 + total); - else + if (last_div == -1 || (keep_divs && last_div < k)) isl_seq_elim(bmap->div[k]+1, eq, 1+pos, 1+total, &bmap->div[k][0]); + else + isl_seq_clr(bmap->div[k], 1 + total); ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED); } } @@ -500,6 +504,8 @@ struct isl_basic_map *isl_basic_map_gauss( unsigned total_var; unsigned total; + bmap = isl_basic_map_order_divs(bmap); + if (!bmap) return NULL; @@ -522,7 +528,7 @@ struct isl_basic_map *isl_basic_map_gauss( if (isl_int_is_neg(bmap->eq[done][1+last_var])) isl_seq_neg(bmap->eq[done], bmap->eq[done], 1+total); - eliminate_var_using_equality(bmap, last_var, bmap->eq[done], + eliminate_var_using_equality(bmap, last_var, bmap->eq[done], 1, progress); if (last_var >= total_var && @@ -1223,7 +1229,7 @@ struct isl_basic_map *isl_basic_map_eliminate_vars( for (i = 0; i < bmap->n_eq; ++i) { if (isl_int_is_zero(bmap->eq[i][1+d])) continue; - eliminate_var_using_equality(bmap, d, bmap->eq[i], NULL); + eliminate_var_using_equality(bmap, d, bmap->eq[i], 0, NULL); isl_basic_map_drop_equality(bmap, i); break; } -- 2.11.4.GIT