isl_bound.c

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