From a47882c4b55df049b413b352f19920714fb316bf Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 12 Mar 2013 17:23:49 +0100 Subject: [PATCH] isl_basic_map_lexopt: preinitialize domain The original code would pass a universe domain to isl_basic_map_partial_lexopt, but this means that the parametric integer programming engine will consider all inequalities as splitting (with respect to the universe context), resulting in a fair amount of wasted effort. More importantly, the border constraints may be transferred to the context in the middle of constraints that actually split the context into parts with possibly different solutions. The current heuristic for merging solutions that turn out to be identical will not be able to transfer solution across the border constraints since they only allow for a solution on one side of the constraint. By prepopulating the domain with some of the constraints from the input map, we can avoid some redundant computations and we improve the opportunities for merging identical partial solutions. Signed-off-by: Sven Verdoolaege --- isl_map.c | 32 +++++++++++++++++++++++--------- test_inputs/codegen/hoist2.c | 6 ++---- 2 files changed, 25 insertions(+), 13 deletions(-) diff --git a/isl_map.c b/isl_map.c index 58b20f2..6fffa60 100644 --- a/isl_map.c +++ b/isl_map.c @@ -6062,19 +6062,33 @@ __isl_give isl_set *isl_set_partial_lexmax( dom, empty); } +/* Compute the lexicographic minimum (or maximum if "max" is set) + * of "bmap" over its domain. + * + * Since we are not interested in the part of the domain space where + * there is no solution, we initialize the domain to those constraints + * of "bmap" that only involve the parameters and the input dimensions. + * This relieves the parametric programming engine from detecting those + * inequalities and transferring them to the context. More importantly, + * it ensures that those inequalities are transferred first and not + * intermixed with inequalities that actually split the domain. + */ __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max) { - struct isl_basic_set *dom = NULL; - isl_space *dom_dim; + int n_div; + int n_out; + isl_basic_map *copy; + isl_basic_set *dom; - if (!bmap) - goto error; - dom_dim = isl_space_domain(isl_space_copy(bmap->dim)); - dom = isl_basic_set_universe(dom_dim); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + n_out = isl_basic_map_dim(bmap, isl_dim_out); + copy = isl_basic_map_copy(bmap); + copy = isl_basic_map_drop_constraints_involving_dims(copy, + isl_dim_div, 0, n_div); + copy = isl_basic_map_drop_constraints_involving_dims(copy, + isl_dim_out, 0, n_out); + dom = isl_basic_map_domain(copy); return isl_basic_map_partial_lexopt(bmap, dom, NULL, max); -error: - isl_basic_map_free(bmap); - return NULL; } __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap) diff --git a/test_inputs/codegen/hoist2.c b/test_inputs/codegen/hoist2.c index 4cc0db3..4d43f4c 100644 --- a/test_inputs/codegen/hoist2.c +++ b/test_inputs/codegen/hoist2.c @@ -1,5 +1,3 @@ for (int c0 = 1; c0 <= 5; c0 += 1) - if (c0 >= 3 || c0 <= 2 || (b == 1 && t1 <= 6 && t1 + c0 <= 9)) - for (int c1 = max(t1, t1 - 64 * b + 64); c1 <= min(70, -((c0 + 1) % 2) - c0 + 73); c1 += 64) - if ((c0 >= 3 && c0 + c1 >= 10) || (c0 <= 2 && c0 >= 1 && c1 >= 7) || (c1 == t1 && b == 1 && t1 <= 6 && t1 + c0 <= 9)) - A(c0, 64 * b + c1 - 8); + for (int c1 = max(t1, t1 - 64 * b + 64); c1 <= min(70, -((c0 + 1) % 2) - c0 + 73); c1 += 64) + A(c0, 64 * b + c1 - 8); -- 2.7.4