428 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 *4 * Use of this software is governed by the MIT license5 *6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,8 * 91893 Orsay, France 9 */10 11#include <isl_ctx_private.h>12#include <isl_map_private.h>13#include <isl_bound.h>14#include <isl_bernstein.h>15#include <isl_range.h>16#include <isl_polynomial_private.h>17#include <isl_options_private.h>18 19/* Given a polynomial "poly" that is constant in terms20 * of the domain variables, construct a polynomial reduction21 * of type "type" that is equal to "poly" on "bset",22 * with the domain projected onto the parameters.23 */24__isl_give isl_pw_qpolynomial_fold *isl_qpolynomial_cst_bound(25 __isl_take isl_basic_set *bset, __isl_take isl_qpolynomial *poly,26 enum isl_fold type, isl_bool *tight)27{28 isl_set *dom;29 isl_qpolynomial_fold *fold;30 isl_pw_qpolynomial_fold *pwf;31 32 fold = isl_qpolynomial_fold_alloc(type, poly);33 dom = isl_set_from_basic_set(bset);34 if (tight)35 *tight = isl_bool_true;36 pwf = isl_pw_qpolynomial_fold_alloc(type, dom, fold);37 return isl_pw_qpolynomial_fold_project_domain_on_params(pwf);38}39 40/* Add the bound "pwf", which is not known to be tight,41 * to the output of "bound".42 */43isl_stat isl_bound_add(struct isl_bound *bound,44 __isl_take isl_pw_qpolynomial_fold *pwf)45{46 bound->pwf = isl_pw_qpolynomial_fold_fold(bound->pwf, pwf);47 return isl_stat_non_null(bound->pwf);48}49 50/* Add the bound "pwf", which is known to be tight,51 * to the output of "bound".52 */53isl_stat isl_bound_add_tight(struct isl_bound *bound,54 __isl_take isl_pw_qpolynomial_fold *pwf)55{56 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(bound->pwf_tight, pwf);57 return isl_stat_non_null(bound->pwf);58}59 60/* Given a polynomial "poly" that is constant in terms61 * of the domain variables and the domain "bset",62 * construct the corresponding polynomial reduction and63 * add it to the tight bounds of "bound".64 */65static isl_stat add_constant_poly(__isl_take isl_basic_set *bset,66 __isl_take isl_qpolynomial *poly, struct isl_bound *bound)67{68 isl_pw_qpolynomial_fold *pwf;69 70 pwf = isl_qpolynomial_cst_bound(bset, poly, bound->type, NULL);71 return isl_bound_add_tight(bound, pwf);72}73 74/* Compute a bound on the polynomial defined over the parametric polytope75 * using either range propagation or bernstein expansion and76 * store the result in bound->pwf and bound->pwf_tight.77 * Since bernstein expansion requires bounded domains, we apply78 * range propagation on unbounded domains. Otherwise, we respect the choice79 * of the user.80 *81 * If the polynomial does not depend on the set variables82 * then the bound is equal to the polynomial and83 * it can be added to "bound" directly.84 */85static isl_stat compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,86 __isl_take isl_qpolynomial *poly, void *user)87{88 struct isl_bound *bound = (struct isl_bound *)user;89 isl_ctx *ctx;90 int bounded;91 int degree;92 93 if (!bset || !poly)94 goto error;95 96 degree = isl_qpolynomial_degree(poly);97 if (degree < -1)98 goto error;99 if (degree <= 0)100 return add_constant_poly(bset, poly, bound);101 102 ctx = isl_basic_set_get_ctx(bset);103 if (ctx->opt->bound == ISL_BOUND_RANGE)104 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);105 106 bounded = isl_basic_set_is_bounded(bset);107 if (bounded < 0)108 goto error;109 if (bounded)110 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);111 else112 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);113error:114 isl_basic_set_free(bset);115 isl_qpolynomial_free(poly);116 return isl_stat_error;117}118 119static isl_stat unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,120 __isl_take isl_qpolynomial *poly, void *user)121{122 struct isl_bound *bound = (struct isl_bound *)user;123 isl_pw_qpolynomial_fold *top_pwf;124 isl_pw_qpolynomial_fold *top_pwf_tight;125 isl_space *space;126 isl_morph *morph;127 isl_stat r;128 129 bset = isl_basic_set_detect_equalities(bset);130 131 if (!bset)132 goto error;133 134 if (bset->n_eq == 0)135 return compressed_guarded_poly_bound(bset, poly, user);136 137 morph = isl_basic_set_full_compression(bset);138 139 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);140 poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));141 142 space = isl_morph_get_ran_space(morph);143 space = isl_space_params(space);144 145 top_pwf = bound->pwf;146 top_pwf_tight = bound->pwf_tight;147 148 space = isl_space_from_domain(space);149 space = isl_space_add_dims(space, isl_dim_out, 1);150 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),151 bound->type);152 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);153 154 r = compressed_guarded_poly_bound(bset, poly, user);155 156 morph = isl_morph_dom_params(morph);157 morph = isl_morph_ran_params(morph);158 morph = isl_morph_inverse(morph);159 160 bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,161 isl_morph_copy(morph));162 bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(163 bound->pwf_tight, morph);164 165 isl_bound_add(bound, top_pwf);166 isl_bound_add_tight(bound, top_pwf_tight);167 168 return r;169error:170 isl_basic_set_free(bset);171 isl_qpolynomial_free(poly);172 return isl_stat_error;173}174 175/* Update bound->pwf and bound->pwf_tight with a bound176 * of type bound->type on the polynomial "poly" over the domain "bset".177 *178 * If the original problem had a wrapped relation in the domain,179 * meaning that the bound should be computed over the range180 * of this relation, then temporarily treat the domain dimensions181 * of this wrapped relation as parameters, compute a bound182 * in terms of these and the original parameters,183 * turn the parameters back into set dimensions and184 * add the results to bound->pwf and bound->pwf_tight.185 *186 * Note that even though "bset" is known to live in the same space187 * as the domain of "poly", the names of the set dimensions188 * may be different (or missing). Make sure the naming is exactly189 * the same before turning these dimensions into parameters190 * to ensure that the spaces are still the same after191 * this operation.192 */193static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,194 __isl_take isl_qpolynomial *poly, void *user)195{196 struct isl_bound *bound = (struct isl_bound *)user;197 isl_space *space;198 isl_pw_qpolynomial_fold *top_pwf;199 isl_pw_qpolynomial_fold *top_pwf_tight;200 isl_size nparam;201 isl_size n_in;202 isl_stat r;203 204 if (!bound->wrapping)205 return unwrapped_guarded_poly_bound(bset, poly, user);206 207 nparam = isl_space_dim(bound->dim, isl_dim_param);208 n_in = isl_space_dim(bound->dim, isl_dim_in);209 if (nparam < 0 || n_in < 0)210 goto error;211 212 space = isl_qpolynomial_get_domain_space(poly);213 bset = isl_basic_set_reset_space(bset, space);214 215 bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,216 isl_dim_set, 0, n_in);217 poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,218 isl_dim_in, 0, n_in);219 220 space = isl_basic_set_get_space(bset);221 space = isl_space_params(space);222 223 top_pwf = bound->pwf;224 top_pwf_tight = bound->pwf_tight;225 226 space = isl_space_from_domain(space);227 space = isl_space_add_dims(space, isl_dim_out, 1);228 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),229 bound->type);230 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);231 232 r = unwrapped_guarded_poly_bound(bset, poly, user);233 234 bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,235 isl_space_copy(bound->dim));236 bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,237 isl_space_copy(bound->dim));238 239 isl_bound_add(bound, top_pwf);240 isl_bound_add_tight(bound, top_pwf_tight);241 242 return r;243error:244 isl_basic_set_free(bset);245 isl_qpolynomial_free(poly);246 return isl_stat_error;247}248 249static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)250{251 struct isl_bound *bound = (struct isl_bound *)user;252 isl_stat r;253 254 r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,255 &guarded_poly_bound, user);256 isl_qpolynomial_free(qp);257 return r;258}259 260static isl_stat basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)261{262 struct isl_bound *bound = (struct isl_bound *)user;263 isl_stat r;264 265 bound->bset = bset;266 r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,267 &guarded_qp, user);268 isl_basic_set_free(bset);269 return r;270}271 272static isl_stat guarded_fold(__isl_take isl_set *set,273 __isl_take isl_qpolynomial_fold *fold, void *user)274{275 struct isl_bound *bound = (struct isl_bound *)user;276 277 if (!set || !fold)278 goto error;279 280 set = isl_set_make_disjoint(set);281 282 bound->fold = fold;283 bound->type = isl_qpolynomial_fold_get_type(fold);284 285 if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)286 goto error;287 288 isl_set_free(set);289 isl_qpolynomial_fold_free(fold);290 291 return isl_stat_ok;292error:293 isl_set_free(set);294 isl_qpolynomial_fold_free(fold);295 return isl_stat_error;296}297 298__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(299 __isl_take isl_pw_qpolynomial_fold *pwf, isl_bool *tight)300{301 isl_size nvar;302 struct isl_bound bound;303 isl_bool covers;304 305 if (!pwf)306 return NULL;307 308 bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);309 310 bound.wrapping = isl_space_is_wrapping(bound.dim);311 if (bound.wrapping)312 bound.dim = isl_space_unwrap(bound.dim);313 nvar = isl_space_dim(bound.dim, isl_dim_out);314 if (nvar < 0)315 bound.dim = isl_space_free(bound.dim);316 bound.dim = isl_space_domain(bound.dim);317 bound.dim = isl_space_from_domain(bound.dim);318 bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);319 320 if (nvar == 0) {321 if (tight)322 *tight = isl_bool_true;323 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);324 }325 326 if (isl_pw_qpolynomial_fold_is_zero(pwf)) {327 enum isl_fold type = pwf->type;328 isl_pw_qpolynomial_fold_free(pwf);329 if (tight)330 *tight = isl_bool_true;331 return isl_pw_qpolynomial_fold_zero(bound.dim, type);332 }333 334 bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),335 pwf->type);336 bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),337 pwf->type);338 bound.check_tight = !!tight;339 340 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,341 guarded_fold, &bound) < 0)342 goto error;343 344 covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);345 if (covers < 0)346 goto error;347 348 if (tight)349 *tight = covers;350 351 isl_space_free(bound.dim);352 isl_pw_qpolynomial_fold_free(pwf);353 354 if (covers) {355 isl_pw_qpolynomial_fold_free(bound.pwf);356 return bound.pwf_tight;357 }358 359 bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);360 361 return bound.pwf;362error:363 isl_pw_qpolynomial_fold_free(bound.pwf_tight);364 isl_pw_qpolynomial_fold_free(bound.pwf);365 isl_pw_qpolynomial_fold_free(pwf);366 isl_space_free(bound.dim);367 return NULL;368}369 370__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(371 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,372 isl_bool *tight)373{374 isl_pw_qpolynomial_fold *pwf;375 376 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);377 return isl_pw_qpolynomial_fold_bound(pwf, tight);378}379 380struct isl_union_bound_data {381 enum isl_fold type;382 isl_bool tight;383 isl_union_pw_qpolynomial_fold *res;384};385 386static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)387{388 struct isl_union_bound_data *data = user;389 isl_pw_qpolynomial_fold *pwf;390 391 pwf = isl_pw_qpolynomial_bound(pwqp, data->type,392 data->tight ? &data->tight : NULL);393 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(394 data->res, pwf);395 396 return isl_stat_ok;397}398 399__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(400 __isl_take isl_union_pw_qpolynomial *upwqp,401 enum isl_fold type, isl_bool *tight)402{403 isl_space *space;404 struct isl_union_bound_data data = { type, 1, NULL };405 406 if (!upwqp)407 return NULL;408 409 if (!tight)410 data.tight = isl_bool_false;411 412 space = isl_union_pw_qpolynomial_get_space(upwqp);413 data.res = isl_union_pw_qpolynomial_fold_zero(space, type);414 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,415 &bound_pw, &data) < 0)416 goto error;417 418 isl_union_pw_qpolynomial_free(upwqp);419 if (tight)420 *tight = data.tight;421 422 return data.res;423error:424 isl_union_pw_qpolynomial_free(upwqp);425 isl_union_pw_qpolynomial_fold_free(data.res);426 return NULL;427}428