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 /* 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  */
  26 static isl_stat 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);
  45 error:
  46         isl_basic_set_free(bset);
  47         isl_qpolynomial_free(poly);
  48         return isl_stat_error;
  49 }
  50
  51 static isl_stat 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 *space;
  58         isl_morph *morph;
  59         isl_stat 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         space = isl_morph_get_ran_space(morph);
  75         space = isl_space_params(space);
  76
  77         top_pwf = bound->pwf;
  78         top_pwf_tight = bound->pwf_tight;
  79
  80         space = isl_space_from_domain(space);
  81         space = isl_space_add_dims(space, isl_dim_out, 1);
  82         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
  83                                                   bound->type);
  84         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, 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;
 102 error:
 103         isl_basic_set_free(bset);
 104         isl_qpolynomial_free(poly);
 105         return isl_stat_error;
 106 }
 107
 108 /* Update bound->pwf and bound->pwf_tight with a bound
 109  * of type bound->type on the polynomial "poly" over the domain "bset".
 110  *
 111  * If the original problem had a wrapped relation in the domain,
 112  * meaning that the bound should be computed over the range
 113  * of this relation, then temporarily treat the domain dimensions
 114  * of this wrapped relation as parameters, compute a bound
 115  * in terms of these and the original parameters,
 116  * turn the parameters back into set dimensions and
 117  * add the results to bound->pwf and bound->pwf_tight.
 118  *
 119  * Note that even though "bset" is known to live in the same space
 120  * as the domain of "poly", the names of the set dimensions
 121  * may be different (or missing).  Make sure the naming is exactly
 122  * the same before turning these dimensions into parameters
 123  * to ensure that the spaces are still the same after
 124  * this operation.
 125  */
 126 static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,
 127         __isl_take isl_qpolynomial *poly, void *user)
 128 {
 129         struct isl_bound *bound = (struct isl_bound *)user;
 130         isl_space *space;
 131         isl_pw_qpolynomial_fold *top_pwf;
 132         isl_pw_qpolynomial_fold *top_pwf_tight;
 133         isl_size nparam;
 134         isl_size n_in;
 135         isl_stat r;
 136
 137         if (!bound->wrapping)
 138                 return unwrapped_guarded_poly_bound(bset, poly, user);
 139
 140         nparam = isl_space_dim(bound->dim, isl_dim_param);
 141         n_in = isl_space_dim(bound->dim, isl_dim_in);
 142         if (nparam < 0 || n_in < 0)
 143                 goto error;
 144
 145         space = isl_qpolynomial_get_domain_space(poly);
 146         bset = isl_basic_set_reset_space(bset, space);
 147
 148         bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
 149                                         isl_dim_set, 0, n_in);
 150         poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
 151                                         isl_dim_in, 0, n_in);
 152
 153         space = isl_basic_set_get_space(bset);
 154         space = isl_space_params(space);
 155
 156         top_pwf = bound->pwf;
 157         top_pwf_tight = bound->pwf_tight;
 158
 159         space = isl_space_from_domain(space);
 160         space = isl_space_add_dims(space, isl_dim_out, 1);
 161         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
 162                                                   bound->type);
 163         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);
 164
 165         r = unwrapped_guarded_poly_bound(bset, poly, user);
 166
 167         bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
 168                                                     isl_space_copy(bound->dim));
 169         bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
 170                                                     isl_space_copy(bound->dim));
 171
 172         bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
 173         bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
 174                                                         bound->pwf_tight);
 175
 176         return r;
 177 error:
 178         isl_basic_set_free(bset);
 179         isl_qpolynomial_free(poly);
 180         return isl_stat_error;
 181 }
 182
 183 static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
 184 {
 185         struct isl_bound *bound = (struct isl_bound *)user;
 186         isl_stat r;
 187
 188         r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
 189                                                     &guarded_poly_bound, user);
 190         isl_qpolynomial_free(qp);
 191         return r;
 192 }
 193
 194 static isl_stat basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
 195 {
 196         struct isl_bound *bound = (struct isl_bound *)user;
 197         isl_stat r;
 198
 199         bound->bset = bset;
 200         r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
 201                                                         &guarded_qp, user);
 202         isl_basic_set_free(bset);
 203         return r;
 204 }
 205
 206 static isl_stat guarded_fold(__isl_take isl_set *set,
 207         __isl_take isl_qpolynomial_fold *fold, void *user)
 208 {
 209         struct isl_bound *bound = (struct isl_bound *)user;
 210
 211         if (!set || !fold)
 212                 goto error;
 213
 214         set = isl_set_make_disjoint(set);
 215
 216         bound->fold = fold;
 217         bound->type = isl_qpolynomial_fold_get_type(fold);
 218
 219         if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
 220                 goto error;
 221
 222         isl_set_free(set);
 223         isl_qpolynomial_fold_free(fold);
 224
 225         return isl_stat_ok;
 226 error:
 227         isl_set_free(set);
 228         isl_qpolynomial_fold_free(fold);
 229         return isl_stat_error;
 230 }
 231
 232 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 233         __isl_take isl_pw_qpolynomial_fold *pwf, isl_bool *tight)
 234 {
 235         isl_size nvar;
 236         struct isl_bound bound;
 237         isl_bool covers;
 238
 239         if (!pwf)
 240                 return NULL;
 241
 242         bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
 243
 244         bound.wrapping = isl_space_is_wrapping(bound.dim);
 245         if (bound.wrapping)
 246                 bound.dim = isl_space_unwrap(bound.dim);
 247         nvar = isl_space_dim(bound.dim, isl_dim_out);
 248         if (nvar < 0)
 249                 bound.dim = isl_space_free(bound.dim);
 250         bound.dim = isl_space_domain(bound.dim);
 251         bound.dim = isl_space_from_domain(bound.dim);
 252         bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
 253
 254         if (nvar == 0) {
 255                 if (tight)
 256                         *tight = isl_bool_true;
 257                 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
 258         }
 259
 260         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
 261                 enum isl_fold type = pwf->type;
 262                 isl_pw_qpolynomial_fold_free(pwf);
 263                 if (tight)
 264                         *tight = isl_bool_true;
 265                 return isl_pw_qpolynomial_fold_zero(bound.dim, type);
 266         }
 267
 268         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
 269                                                         pwf->type);
 270         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
 271                                                         pwf->type);
 272         bound.check_tight = !!tight;
 273
 274         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
 275                                                         guarded_fold, &bound) < 0)
 276                 goto error;
 277
 278         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 279         if (covers < 0)
 280                 goto error;
 281
 282         if (tight)
 283                 *tight = covers;
 284
 285         isl_space_free(bound.dim);
 286         isl_pw_qpolynomial_fold_free(pwf);
 287
 288         if (covers) {
 289                 isl_pw_qpolynomial_fold_free(bound.pwf);
 290                 return bound.pwf_tight;
 291         }
 292
 293         bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
 294
 295         return bound.pwf;
 296 error:
 297         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 298         isl_pw_qpolynomial_fold_free(bound.pwf);
 299         isl_pw_qpolynomial_fold_free(pwf);
 300         isl_space_free(bound.dim);
 301         return NULL;
 302 }
 303
 304 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 305         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,
 306         isl_bool *tight)
 307 {
 308         isl_pw_qpolynomial_fold *pwf;
 309
 310         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 311         return isl_pw_qpolynomial_fold_bound(pwf, tight);
 312 }
 313
 314 struct isl_union_bound_data {
 315         enum isl_fold type;
 316         isl_bool tight;
 317         isl_union_pw_qpolynomial_fold *res;
 318 };
 319
 320 static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
 321 {
 322         struct isl_union_bound_data *data = user;
 323         isl_pw_qpolynomial_fold *pwf;
 324
 325         pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
 326                                         data->tight ? &data->tight : NULL);
 327         data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
 328                                                                 data->res, pwf);
 329
 330         return isl_stat_ok;
 331 }
 332
 333 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
 334         __isl_take isl_union_pw_qpolynomial *upwqp,
 335         enum isl_fold type, isl_bool *tight)
 336 {
 337         isl_space *space;
 338         struct isl_union_bound_data data = { type, 1, NULL };
 339
 340         if (!upwqp)
 341                 return NULL;
 342
 343         if (!tight)
 344                 data.tight = isl_bool_false;
 345
 346         space = isl_union_pw_qpolynomial_get_space(upwqp);
 347         data.res = isl_union_pw_qpolynomial_fold_zero(space, type);
 348         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
 349                                                     &bound_pw, &data) < 0)
 350                 goto error;
 351
 352         isl_union_pw_qpolynomial_free(upwqp);
 353         if (tight)
 354                 *tight = data.tight;
 355
 356         return data.res;
 357 error:
 358         isl_union_pw_qpolynomial_free(upwqp);
 359         isl_union_pw_qpolynomial_fold_free(data.res);
 360         return NULL;
 361 }