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_bound.h>
  12 #include <isl_bernstein.h>
  13 #include <isl_range.h>
  14 #include <isl_polynomial_private.h>
  15
  16 /* Compute a bound on the polynomial defined over the parametric polytope
  17  * using either range propagation or bernstein expansion and
  18  * store the result in bound->pwf and bound->pwf_tight.
  19  * Since bernstein expansion requires bounded domains, we apply
  20  * range propagation on unbounded domains.  Otherwise, we respect the choice
  21  * of the user.
  22  */
  23 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
  24         __isl_take isl_qpolynomial *poly, void *user)
  25 {
  26         struct isl_bound *bound = (struct isl_bound *)user;
  27         int bounded;
  28
  29         if (!bset || !poly)
  30                 goto error;
  31
  32         if (bset->ctx->opt->bound == ISL_BOUND_RANGE)
  33                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
  34
  35         bounded = isl_basic_set_is_bounded(bset);
  36         if (bounded < 0)
  37                 goto error;
  38         if (bounded)
  39                 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
  40         else
  41                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
  42 error:
  43         isl_basic_set_free(bset);
  44         isl_qpolynomial_free(poly);
  45         return -1;
  46 }
  47
  48 static int unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
  49         __isl_take isl_qpolynomial *poly, void *user)
  50 {
  51         struct isl_bound *bound = (struct isl_bound *)user;
  52         isl_pw_qpolynomial_fold *top_pwf;
  53         isl_pw_qpolynomial_fold *top_pwf_tight;
  54         isl_dim *dim;
  55         isl_morph *morph;
  56         unsigned orig_nvar, final_nvar;
  57         int r;
  58
  59         bset = isl_basic_set_detect_equalities(bset);
  60
  61         if (!bset)
  62                 goto error;
  63
  64         if (bset->n_eq == 0)
  65                 return compressed_guarded_poly_bound(bset, poly, user);
  66
  67         orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
  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(poly, isl_morph_copy(morph));
  73
  74         final_nvar = isl_basic_set_dim(bset, isl_dim_set);
  75
  76         dim = isl_morph_get_ran_dim(morph);
  77         dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
  78
  79         top_pwf = bound->pwf;
  80         top_pwf_tight = bound->pwf_tight;
  81
  82         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
  83         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim);
  84
  85         r = compressed_guarded_poly_bound(bset, poly, user);
  86
  87         morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
  88         morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
  89         morph = isl_morph_inverse(morph);
  90
  91         bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
  92                                                         isl_morph_copy(morph));
  93         bound->pwf_tight = isl_pw_qpolynomial_fold_morph(bound->pwf_tight, morph);
  94
  95         bound->pwf = isl_pw_qpolynomial_fold_add(top_pwf, bound->pwf);
  96         bound->pwf_tight = isl_pw_qpolynomial_fold_add(top_pwf_tight,
  97                                                         bound->pwf_tight);
  98
  99         return r;
 100 error:
 101         isl_basic_set_free(bset);
 102         isl_qpolynomial_free(poly);
 103         return -1;
 104 }
 105
 106 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
 107         __isl_take isl_qpolynomial *poly, void *user)
 108 {
 109         struct isl_bound *bound = (struct isl_bound *)user;
 110         isl_dim *dim;
 111         isl_dim *target_dim;
 112         isl_pw_qpolynomial_fold *top_pwf;
 113         isl_pw_qpolynomial_fold *top_pwf_tight;
 114         int nparam;
 115         int n_in;
 116         int r;
 117
 118         if (!isl_basic_set_is_wrapping(bset))
 119                 return unwrapped_guarded_poly_bound(bset, poly, user);
 120
 121         target_dim = isl_basic_set_get_dim(bset);
 122         target_dim = isl_dim_unwrap(target_dim);
 123         target_dim = isl_dim_domain(target_dim);
 124
 125         nparam = isl_dim_size(target_dim, isl_dim_param);
 126         n_in = isl_dim_size(target_dim, isl_dim_set);
 127
 128         bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
 129                                         isl_dim_set, 0, n_in);
 130         poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
 131                                         isl_dim_set, 0, n_in);
 132
 133         dim = isl_basic_set_get_dim(bset);
 134         dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
 135
 136         top_pwf = bound->pwf;
 137         top_pwf_tight = bound->pwf_tight;
 138
 139         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 140         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim);
 141
 142         r = unwrapped_guarded_poly_bound(bset, poly, user);
 143
 144         bound->pwf = isl_pw_qpolynomial_fold_reset_dim(bound->pwf,
 145                                                     isl_dim_copy(target_dim));
 146         bound->pwf_tight = isl_pw_qpolynomial_fold_reset_dim(bound->pwf_tight,
 147                                                     target_dim);
 148
 149         bound->pwf = isl_pw_qpolynomial_fold_add(top_pwf, bound->pwf);
 150         bound->pwf_tight = isl_pw_qpolynomial_fold_add(top_pwf_tight,
 151                                                         bound->pwf_tight);
 152
 153         return r;
 154 }
 155
 156 static 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
 167 static 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
 179 static 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;
 199 error:
 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         isl_dim *dim;
 209         unsigned nvar;
 210         struct isl_bound bound;
 211         int covers;
 212
 213         if (!pwf)
 214                 return NULL;
 215
 216         dim = isl_pw_qpolynomial_fold_get_dim(pwf);
 217         nvar = isl_dim_size(dim, isl_dim_set);
 218
 219         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
 220                 isl_pw_qpolynomial_fold_free(pwf);
 221                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 222                 if (tight)
 223                         *tight = 1;
 224                 return isl_pw_qpolynomial_fold_zero(dim);
 225         }
 226
 227         if (nvar == 0) {
 228                 isl_dim_free(dim);
 229                 if (tight)
 230                         *tight = 1;
 231                 return pwf;
 232         }
 233
 234         if (isl_dim_is_wrapping(dim)) {
 235                 dim = isl_dim_unwrap(dim);
 236                 nvar = isl_dim_size(dim, isl_dim_out);
 237                 dim = isl_dim_domain(dim);
 238                 if (nvar == 0) {
 239                         if (tight)
 240                                 *tight = 1;
 241                         return isl_pw_qpolynomial_fold_reset_dim(pwf, dim);
 242                 }
 243         } else
 244                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 245
 246         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 247         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 248         bound.check_tight = !!tight;
 249
 250         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
 251                                                         guarded_fold, &bound) < 0)
 252                 goto error;
 253
 254         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 255         if (covers < 0)
 256                 goto error;
 257
 258         if (tight)
 259                 *tight = covers;
 260
 261         isl_dim_free(dim);
 262         isl_pw_qpolynomial_fold_free(pwf);
 263
 264         if (covers) {
 265                 isl_pw_qpolynomial_fold_free(bound.pwf);
 266                 return bound.pwf_tight;
 267         }
 268
 269         bound.pwf = isl_pw_qpolynomial_fold_add(bound.pwf, bound.pwf_tight);
 270
 271         return bound.pwf;
 272 error:
 273         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 274         isl_pw_qpolynomial_fold_free(bound.pwf);
 275         isl_pw_qpolynomial_fold_free(pwf);
 276         isl_dim_free(dim);
 277         return NULL;
 278 }
 279
 280 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 281         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
 282 {
 283         isl_pw_qpolynomial_fold *pwf;
 284
 285         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 286         return isl_pw_qpolynomial_fold_bound(pwf, tight);
 287 }
 288
 289 struct isl_union_bound_data {
 290         enum isl_fold type;
 291         int tight;
 292         isl_union_pw_qpolynomial_fold *res;
 293 };
 294
 295 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
 296 {
 297         struct isl_union_bound_data *data = user;
 298         isl_pw_qpolynomial_fold *pwf;
 299
 300         pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
 301                                         data->tight ? &data->tight : NULL);
 302         data->res = isl_union_pw_qpolynomial_fold_add_pw_qpolynomial_fold(
 303                                                                 data->res, pwf);
 304
 305         return 0;
 306 }
 307
 308 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
 309         __isl_take isl_union_pw_qpolynomial *upwqp,
 310         enum isl_fold type, int *tight)
 311 {
 312         isl_dim *dim;
 313         struct isl_union_bound_data data = { type, 1, NULL };
 314
 315         if (!upwqp)
 316                 return NULL;
 317
 318         if (!tight)
 319                 data.tight = 0;
 320
 321         dim = isl_union_pw_qpolynomial_get_dim(upwqp);
 322         data.res = isl_union_pw_qpolynomial_fold_zero(dim);
 323         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
 324                                                     &bound_pw, &data) < 0)
 325                 goto error;
 326
 327         isl_union_pw_qpolynomial_free(upwqp);
 328         if (tight)
 329                 *tight = data.tight;
 330
 331         return data.res;
 332 error:
 333         isl_union_pw_qpolynomial_free(upwqp);
 334         isl_union_pw_qpolynomial_fold_free(data.res);
 335         return NULL;
 336 }