1/* 2 * Copyright 2010 INRIA Saclay 3 * 4 * Use of this software is governed by the MIT license 5 * 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/* Compute a bound on the polynomial defined over the parametric polytope 20 * using either range propagation or bernstein expansion and 21 * store the result in bound->pwf and bound->pwf_tight. 22 * Since bernstein expansion requires bounded domains, we apply 23 * range propagation on unbounded domains. Otherwise, we respect the choice 24 * of the user. 25 */ 26static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset, 27 __isl_take isl_qpolynomial *poly, void *user) 28{ 29 struct isl_bound *bound = (struct isl_bound *)user; 30 int bounded; 31 32 if (!bset || !poly) 33 goto error; 34 35 if (bset->ctx->opt->bound == ISL_BOUND_RANGE) 36 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound); 37 38 bounded = isl_basic_set_is_bounded(bset); 39 if (bounded < 0) 40 goto error; 41 if (bounded) 42 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound); 43 else 44 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound); 45error: 46 isl_basic_set_free(bset); 47 isl_qpolynomial_free(poly); 48 return -1; 49} 50 51static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset, 52 __isl_take isl_qpolynomial *poly, void *user) 53{ 54 struct isl_bound *bound = (struct isl_bound *)user; 55 isl_pw_qpolynomial_fold *top_pwf; 56 isl_pw_qpolynomial_fold *top_pwf_tight; 57 isl_space *dim; 58 isl_morph *morph; 59 int r; 60 61 bset = isl_basic_set_detect_equalities(bset); 62 63 if (!bset) 64 goto error; 65 66 if (bset->n_eq == 0) 67 return compressed_guarded_poly_bound(bset, poly, user); 68 69 morph = isl_basic_set_full_compression(bset); 70 71 bset = isl_morph_basic_set(isl_morph_copy(morph), bset); 72 poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph)); 73 74 dim = isl_morph_get_ran_space(morph); 75 dim = isl_space_params(dim); 76 77 top_pwf = bound->pwf; 78 top_pwf_tight = bound->pwf_tight; 79 80 dim = isl_space_from_domain(dim); 81 dim = isl_space_add_dims(dim, isl_dim_out, 1); 82 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim), 83 bound->type); 84 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type); 85 86 r = compressed_guarded_poly_bound(bset, poly, user); 87 88 morph = isl_morph_dom_params(morph); 89 morph = isl_morph_ran_params(morph); 90 morph = isl_morph_inverse(morph); 91 92 bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf, 93 isl_morph_copy(morph)); 94 bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain( 95 bound->pwf_tight, morph); 96 97 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf); 98 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight, 99 bound->pwf_tight); 100 101 return r; 102error: 103 isl_basic_set_free(bset); 104 isl_qpolynomial_free(poly); 105 return -1; 106} 107 108static int guarded_poly_bound(__isl_take isl_basic_set *bset, 109 __isl_take isl_qpolynomial *poly, void *user) 110{ 111 struct isl_bound *bound = (struct isl_bound *)user; 112 isl_space *dim; 113 isl_pw_qpolynomial_fold *top_pwf; 114 isl_pw_qpolynomial_fold *top_pwf_tight; 115 int nparam; 116 int n_in; 117 int r; 118 119 if (!bound->wrapping) 120 return unwrapped_guarded_poly_bound(bset, poly, user); 121 122 nparam = isl_space_dim(bound->dim, isl_dim_param); 123 n_in = isl_space_dim(bound->dim, isl_dim_in); 124 125 bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam, 126 isl_dim_set, 0, n_in); 127 poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam, 128 isl_dim_in, 0, n_in); 129 130 dim = isl_basic_set_get_space(bset); 131 dim = isl_space_params(dim); 132 133 top_pwf = bound->pwf; 134 top_pwf_tight = bound->pwf_tight; 135 136 dim = isl_space_from_domain(dim); 137 dim = isl_space_add_dims(dim, isl_dim_out, 1); 138 bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(dim), 139 bound->type); 140 bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type); 141 142 r = unwrapped_guarded_poly_bound(bset, poly, user); 143 144 bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf, 145 isl_space_copy(bound->dim)); 146 bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight, 147 isl_space_copy(bound->dim)); 148 149 bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf); 150 bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight, 151 bound->pwf_tight); 152 153 return r; 154} 155 156static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user) 157{ 158 struct isl_bound *bound = (struct isl_bound *)user; 159 int r; 160 161 r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset, 162 &guarded_poly_bound, user); 163 isl_qpolynomial_free(qp); 164 return r; 165} 166 167static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user) 168{ 169 struct isl_bound *bound = (struct isl_bound *)user; 170 int r; 171 172 bound->bset = bset; 173 r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold, 174 &guarded_qp, user); 175 isl_basic_set_free(bset); 176 return r; 177} 178 179static int guarded_fold(__isl_take isl_set *set, 180 __isl_take isl_qpolynomial_fold *fold, void *user) 181{ 182 struct isl_bound *bound = (struct isl_bound *)user; 183 184 if (!set || !fold) 185 goto error; 186 187 set = isl_set_make_disjoint(set); 188 189 bound->fold = fold; 190 bound->type = isl_qpolynomial_fold_get_type(fold); 191 192 if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0) 193 goto error; 194 195 isl_set_free(set); 196 isl_qpolynomial_fold_free(fold); 197 198 return 0; 199error: 200 isl_set_free(set); 201 isl_qpolynomial_fold_free(fold); 202 return -1; 203} 204 205__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound( 206 __isl_take isl_pw_qpolynomial_fold *pwf, int *tight) 207{ 208 unsigned nvar; 209 struct isl_bound bound; 210 int covers; 211 212 if (!pwf) 213 return NULL; 214 215 bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf); 216 217 bound.wrapping = isl_space_is_wrapping(bound.dim); 218 if (bound.wrapping) 219 bound.dim = isl_space_unwrap(bound.dim); 220 nvar = isl_space_dim(bound.dim, isl_dim_out); 221 bound.dim = isl_space_domain(bound.dim); 222 bound.dim = isl_space_from_domain(bound.dim); 223 bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1); 224 225 if (nvar == 0) { 226 if (tight) 227 *tight = 1; 228 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim); 229 } 230 231 if (isl_pw_qpolynomial_fold_is_zero(pwf)) { 232 enum isl_fold type = pwf->type; 233 isl_pw_qpolynomial_fold_free(pwf); 234 if (tight) 235 *tight = 1; 236 return isl_pw_qpolynomial_fold_zero(bound.dim, type); 237 } 238 239 bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim), 240 pwf->type); 241 bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim), 242 pwf->type); 243 bound.check_tight = !!tight; 244 245 if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf, 246 guarded_fold, &bound) < 0) 247 goto error; 248 249 covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf); 250 if (covers < 0) 251 goto error; 252 253 if (tight) 254 *tight = covers; 255 256 isl_space_free(bound.dim); 257 isl_pw_qpolynomial_fold_free(pwf); 258 259 if (covers) { 260 isl_pw_qpolynomial_fold_free(bound.pwf); 261 return bound.pwf_tight; 262 } 263 264 bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight); 265 266 return bound.pwf; 267error: 268 isl_pw_qpolynomial_fold_free(bound.pwf_tight); 269 isl_pw_qpolynomial_fold_free(bound.pwf); 270 isl_pw_qpolynomial_fold_free(pwf); 271 isl_space_free(bound.dim); 272 return NULL; 273} 274 275__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound( 276 __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight) 277{ 278 isl_pw_qpolynomial_fold *pwf; 279 280 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp); 281 return isl_pw_qpolynomial_fold_bound(pwf, tight); 282} 283 284struct isl_union_bound_data { 285 enum isl_fold type; 286 int tight; 287 isl_union_pw_qpolynomial_fold *res; 288}; 289 290static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user) 291{ 292 struct isl_union_bound_data *data = user; 293 isl_pw_qpolynomial_fold *pwf; 294 295 pwf = isl_pw_qpolynomial_bound(pwqp, data->type, 296 data->tight ? &data->tight : NULL); 297 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( 298 data->res, pwf); 299 300 return 0; 301} 302 303__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound( 304 __isl_take isl_union_pw_qpolynomial *upwqp, 305 enum isl_fold type, int *tight) 306{ 307 isl_space *dim; 308 struct isl_union_bound_data data = { type, 1, NULL }; 309 310 if (!upwqp) 311 return NULL; 312 313 if (!tight) 314 data.tight = 0; 315 316 dim = isl_union_pw_qpolynomial_get_space(upwqp); 317 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type); 318 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, 319 &bound_pw, &data) < 0) 320 goto error; 321 322 isl_union_pw_qpolynomial_free(upwqp); 323 if (tight) 324 *tight = data.tight; 325 326 return data.res; 327error: 328 isl_union_pw_qpolynomial_free(upwqp); 329 isl_union_pw_qpolynomial_fold_free(data.res); 330 return NULL; 331} 332