isl_bound.c

   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 /* Given a polynomial "poly" that is constant in terms
  20  * of the domain variables, construct a polynomial reduction
  21  * 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  */
  43 isl_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  */
  53 isl_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 /* Compute a bound on the polynomial defined over the parametric polytope
  61  * using either range propagation or bernstein expansion and
  62  * store the result in bound->pwf and bound->pwf_tight.
  63  * Since bernstein expansion requires bounded domains, we apply
  64  * range propagation on unbounded domains.  Otherwise, we respect the choice
  65  * of the user.
  66  */
  67 static isl_stat compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
  68         __isl_take isl_qpolynomial *poly, void *user)
  69 {
  70         struct isl_bound *bound = (struct isl_bound *)user;
  71         isl_ctx *ctx;
  72         int bounded;
  73
  74         if (!bset || !poly)
  75                 goto error;
  76
  77         ctx = isl_basic_set_get_ctx(bset);
  78         if (ctx->opt->bound == ISL_BOUND_RANGE)
  79                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
  80
  81         bounded = isl_basic_set_is_bounded(bset);
  82         if (bounded < 0)
  83                 goto error;
  84         if (bounded)
  85                 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
  86         else
  87                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
  88 error:
  89         isl_basic_set_free(bset);
  90         isl_qpolynomial_free(poly);
  91         return isl_stat_error;
  92 }
  93
  94 static isl_stat unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
  95         __isl_take isl_qpolynomial *poly, void *user)
  96 {
  97         struct isl_bound *bound = (struct isl_bound *)user;
  98         isl_pw_qpolynomial_fold *top_pwf;
  99         isl_pw_qpolynomial_fold *top_pwf_tight;
 100         isl_space *space;
 101         isl_morph *morph;
 102         isl_stat r;
 103
 104         bset = isl_basic_set_detect_equalities(bset);
 105
 106         if (!bset)
 107                 goto error;
 108
 109         if (bset->n_eq == 0)
 110                 return compressed_guarded_poly_bound(bset, poly, user);
 111
 112         morph = isl_basic_set_full_compression(bset);
 113
 114         bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
 115         poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
 116
 117         space = isl_morph_get_ran_space(morph);
 118         space = isl_space_params(space);
 119
 120         top_pwf = bound->pwf;
 121         top_pwf_tight = bound->pwf_tight;
 122
 123         space = isl_space_from_domain(space);
 124         space = isl_space_add_dims(space, isl_dim_out, 1);
 125         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
 126                                                   bound->type);
 127         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);
 128
 129         r = compressed_guarded_poly_bound(bset, poly, user);
 130
 131         morph = isl_morph_dom_params(morph);
 132         morph = isl_morph_ran_params(morph);
 133         morph = isl_morph_inverse(morph);
 134
 135         bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,
 136                                                         isl_morph_copy(morph));
 137         bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(
 138                                                 bound->pwf_tight, morph);
 139
 140         isl_bound_add(bound, top_pwf);
 141         isl_bound_add_tight(bound, top_pwf_tight);
 142
 143         return r;
 144 error:
 145         isl_basic_set_free(bset);
 146         isl_qpolynomial_free(poly);
 147         return isl_stat_error;
 148 }
 149
 150 /* Update bound->pwf and bound->pwf_tight with a bound
 151  * of type bound->type on the polynomial "poly" over the domain "bset".
 152  *
 153  * If the original problem had a wrapped relation in the domain,
 154  * meaning that the bound should be computed over the range
 155  * of this relation, then temporarily treat the domain dimensions
 156  * of this wrapped relation as parameters, compute a bound
 157  * in terms of these and the original parameters,
 158  * turn the parameters back into set dimensions and
 159  * add the results to bound->pwf and bound->pwf_tight.
 160  *
 161  * Note that even though "bset" is known to live in the same space
 162  * as the domain of "poly", the names of the set dimensions
 163  * may be different (or missing).  Make sure the naming is exactly
 164  * the same before turning these dimensions into parameters
 165  * to ensure that the spaces are still the same after
 166  * this operation.
 167  */
 168 static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,
 169         __isl_take isl_qpolynomial *poly, void *user)
 170 {
 171         struct isl_bound *bound = (struct isl_bound *)user;
 172         isl_space *space;
 173         isl_pw_qpolynomial_fold *top_pwf;
 174         isl_pw_qpolynomial_fold *top_pwf_tight;
 175         isl_size nparam;
 176         isl_size n_in;
 177         isl_stat r;
 178
 179         if (!bound->wrapping)
 180                 return unwrapped_guarded_poly_bound(bset, poly, user);
 181
 182         nparam = isl_space_dim(bound->dim, isl_dim_param);
 183         n_in = isl_space_dim(bound->dim, isl_dim_in);
 184         if (nparam < 0 || n_in < 0)
 185                 goto error;
 186
 187         space = isl_qpolynomial_get_domain_space(poly);
 188         bset = isl_basic_set_reset_space(bset, space);
 189
 190         bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
 191                                         isl_dim_set, 0, n_in);
 192         poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
 193                                         isl_dim_in, 0, n_in);
 194
 195         space = isl_basic_set_get_space(bset);
 196         space = isl_space_params(space);
 197
 198         top_pwf = bound->pwf;
 199         top_pwf_tight = bound->pwf_tight;
 200
 201         space = isl_space_from_domain(space);
 202         space = isl_space_add_dims(space, isl_dim_out, 1);
 203         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
 204                                                   bound->type);
 205         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);
 206
 207         r = unwrapped_guarded_poly_bound(bset, poly, user);
 208
 209         bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
 210                                                     isl_space_copy(bound->dim));
 211         bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
 212                                                     isl_space_copy(bound->dim));
 213
 214         isl_bound_add(bound, top_pwf);
 215         isl_bound_add_tight(bound, top_pwf_tight);
 216
 217         return r;
 218 error:
 219         isl_basic_set_free(bset);
 220         isl_qpolynomial_free(poly);
 221         return isl_stat_error;
 222 }
 223
 224 static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
 225 {
 226         struct isl_bound *bound = (struct isl_bound *)user;
 227         isl_stat r;
 228
 229         r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
 230                                                     &guarded_poly_bound, user);
 231         isl_qpolynomial_free(qp);
 232         return r;
 233 }
 234
 235 static isl_stat basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
 236 {
 237         struct isl_bound *bound = (struct isl_bound *)user;
 238         isl_stat r;
 239
 240         bound->bset = bset;
 241         r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
 242                                                         &guarded_qp, user);
 243         isl_basic_set_free(bset);
 244         return r;
 245 }
 246
 247 static isl_stat guarded_fold(__isl_take isl_set *set,
 248         __isl_take isl_qpolynomial_fold *fold, void *user)
 249 {
 250         struct isl_bound *bound = (struct isl_bound *)user;
 251
 252         if (!set || !fold)
 253                 goto error;
 254
 255         set = isl_set_make_disjoint(set);
 256
 257         bound->fold = fold;
 258         bound->type = isl_qpolynomial_fold_get_type(fold);
 259
 260         if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
 261                 goto error;
 262
 263         isl_set_free(set);
 264         isl_qpolynomial_fold_free(fold);
 265
 266         return isl_stat_ok;
 267 error:
 268         isl_set_free(set);
 269         isl_qpolynomial_fold_free(fold);
 270         return isl_stat_error;
 271 }
 272
 273 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 274         __isl_take isl_pw_qpolynomial_fold *pwf, isl_bool *tight)
 275 {
 276         isl_size nvar;
 277         struct isl_bound bound;
 278         isl_bool covers;
 279
 280         if (!pwf)
 281                 return NULL;
 282
 283         bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
 284
 285         bound.wrapping = isl_space_is_wrapping(bound.dim);
 286         if (bound.wrapping)
 287                 bound.dim = isl_space_unwrap(bound.dim);
 288         nvar = isl_space_dim(bound.dim, isl_dim_out);
 289         if (nvar < 0)
 290                 bound.dim = isl_space_free(bound.dim);
 291         bound.dim = isl_space_domain(bound.dim);
 292         bound.dim = isl_space_from_domain(bound.dim);
 293         bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
 294
 295         if (nvar == 0) {
 296                 if (tight)
 297                         *tight = isl_bool_true;
 298                 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
 299         }
 300
 301         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
 302                 enum isl_fold type = pwf->type;
 303                 isl_pw_qpolynomial_fold_free(pwf);
 304                 if (tight)
 305                         *tight = isl_bool_true;
 306                 return isl_pw_qpolynomial_fold_zero(bound.dim, type);
 307         }
 308
 309         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
 310                                                         pwf->type);
 311         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
 312                                                         pwf->type);
 313         bound.check_tight = !!tight;
 314
 315         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
 316                                                         guarded_fold, &bound) < 0)
 317                 goto error;
 318
 319         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 320         if (covers < 0)
 321                 goto error;
 322
 323         if (tight)
 324                 *tight = covers;
 325
 326         isl_space_free(bound.dim);
 327         isl_pw_qpolynomial_fold_free(pwf);
 328
 329         if (covers) {
 330                 isl_pw_qpolynomial_fold_free(bound.pwf);
 331                 return bound.pwf_tight;
 332         }
 333
 334         bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
 335
 336         return bound.pwf;
 337 error:
 338         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 339         isl_pw_qpolynomial_fold_free(bound.pwf);
 340         isl_pw_qpolynomial_fold_free(pwf);
 341         isl_space_free(bound.dim);
 342         return NULL;
 343 }
 344
 345 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 346         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,
 347         isl_bool *tight)
 348 {
 349         isl_pw_qpolynomial_fold *pwf;
 350
 351         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 352         return isl_pw_qpolynomial_fold_bound(pwf, tight);
 353 }
 354
 355 struct isl_union_bound_data {
 356         enum isl_fold type;
 357         isl_bool tight;
 358         isl_union_pw_qpolynomial_fold *res;
 359 };
 360
 361 static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
 362 {
 363         struct isl_union_bound_data *data = user;
 364         isl_pw_qpolynomial_fold *pwf;
 365
 366         pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
 367                                         data->tight ? &data->tight : NULL);
 368         data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
 369                                                                 data->res, pwf);
 370
 371         return isl_stat_ok;
 372 }
 373
 374 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
 375         __isl_take isl_union_pw_qpolynomial *upwqp,
 376         enum isl_fold type, isl_bool *tight)
 377 {
 378         isl_space *space;
 379         struct isl_union_bound_data data = { type, 1, NULL };
 380
 381         if (!upwqp)
 382                 return NULL;
 383
 384         if (!tight)
 385                 data.tight = isl_bool_false;
 386
 387         space = isl_union_pw_qpolynomial_get_space(upwqp);
 388         data.res = isl_union_pw_qpolynomial_fold_zero(space, type);
 389         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
 390                                                     &bound_pw, &data) < 0)
 391                 goto error;
 392
 393         isl_union_pw_qpolynomial_free(upwqp);
 394         if (tight)
 395                 *tight = data.tight;
 396
 397         return data.res;
 398 error:
 399         isl_union_pw_qpolynomial_free(upwqp);
 400         isl_union_pw_qpolynomial_fold_free(data.res);
 401         return NULL;
 402 }