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->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_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
  89         morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
  90         morph = isl_morph_inverse(morph);
  91
  92         bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
  93                                                         isl_morph_copy(morph));
  94         bound->pwf_tight = isl_pw_qpolynomial_fold_morph(bound->pwf_tight, morph);
  95
  96         bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
  97         bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
  98                                                         bound->pwf_tight);
  99
 100         return r;
 101 error:
 102         isl_basic_set_free(bset);
 103         isl_qpolynomial_free(poly);
 104         return -1;
 105 }
 106
 107 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
 108         __isl_take isl_qpolynomial *poly, void *user)
 109 {
 110         struct isl_bound *bound = (struct isl_bound *)user;
 111         isl_dim *dim;
 112         isl_dim *target_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 (!isl_basic_set_is_wrapping(bset))
 120                 return unwrapped_guarded_poly_bound(bset, poly, user);
 121
 122         target_dim = isl_basic_set_get_dim(bset);
 123         target_dim = isl_dim_unwrap(target_dim);
 124         target_dim = isl_dim_domain(target_dim);
 125
 126         nparam = isl_dim_size(target_dim, isl_dim_param);
 127         n_in = isl_dim_size(target_dim, isl_dim_set);
 128
 129         bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
 130                                         isl_dim_set, 0, n_in);
 131         poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
 132                                         isl_dim_set, 0, n_in);
 133
 134         dim = isl_basic_set_get_dim(bset);
 135         dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
 136
 137         top_pwf = bound->pwf;
 138         top_pwf_tight = bound->pwf_tight;
 139
 140         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim),
 141                                                   bound->type);
 142         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim, bound->type);
 143
 144         r = unwrapped_guarded_poly_bound(bset, poly, user);
 145
 146         bound->pwf = isl_pw_qpolynomial_fold_reset_dim(bound->pwf,
 147                                                     isl_dim_copy(target_dim));
 148         bound->pwf_tight = isl_pw_qpolynomial_fold_reset_dim(bound->pwf_tight,
 149                                                     target_dim);
 150
 151         bound->pwf = isl_pw_qpolynomial_fold_fold(top_pwf, bound->pwf);
 152         bound->pwf_tight = isl_pw_qpolynomial_fold_fold(top_pwf_tight,
 153                                                         bound->pwf_tight);
 154
 155         return r;
 156 }
 157
 158 static int guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
 159 {
 160         struct isl_bound *bound = (struct isl_bound *)user;
 161         int r;
 162
 163         r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
 164                                                     &guarded_poly_bound, user);
 165         isl_qpolynomial_free(qp);
 166         return r;
 167 }
 168
 169 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
 170 {
 171         struct isl_bound *bound = (struct isl_bound *)user;
 172         int r;
 173
 174         bound->bset = bset;
 175         r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
 176                                                         &guarded_qp, user);
 177         isl_basic_set_free(bset);
 178         return r;
 179 }
 180
 181 static int guarded_fold(__isl_take isl_set *set,
 182         __isl_take isl_qpolynomial_fold *fold, void *user)
 183 {
 184         struct isl_bound *bound = (struct isl_bound *)user;
 185
 186         if (!set || !fold)
 187                 goto error;
 188
 189         set = isl_set_make_disjoint(set);
 190
 191         bound->fold = fold;
 192         bound->type = isl_qpolynomial_fold_get_type(fold);
 193
 194         if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
 195                 goto error;
 196
 197         isl_set_free(set);
 198         isl_qpolynomial_fold_free(fold);
 199
 200         return 0;
 201 error:
 202         isl_set_free(set);
 203         isl_qpolynomial_fold_free(fold);
 204         return -1;
 205 }
 206
 207 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 208         __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
 209 {
 210         isl_dim *dim;
 211         unsigned nvar;
 212         struct isl_bound bound;
 213         int covers;
 214
 215         if (!pwf)
 216                 return NULL;
 217
 218         dim = isl_pw_qpolynomial_fold_get_dim(pwf);
 219         nvar = isl_dim_size(dim, isl_dim_set);
 220
 221         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
 222                 isl_pw_qpolynomial_fold_free(pwf);
 223                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 224                 if (tight)
 225                         *tight = 1;
 226                 return isl_pw_qpolynomial_fold_zero(dim, pwf->type);
 227         }
 228
 229         if (nvar == 0) {
 230                 isl_dim_free(dim);
 231                 if (tight)
 232                         *tight = 1;
 233                 return pwf;
 234         }
 235
 236         if (isl_dim_is_wrapping(dim)) {
 237                 dim = isl_dim_unwrap(dim);
 238                 nvar = isl_dim_size(dim, isl_dim_out);
 239                 dim = isl_dim_domain(dim);
 240                 if (nvar == 0) {
 241                         if (tight)
 242                                 *tight = 1;
 243                         return isl_pw_qpolynomial_fold_reset_dim(pwf, dim);
 244                 }
 245         } else
 246                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 247
 248         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim), pwf->type);
 249         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim),
 250                                                         pwf->type);
 251         bound.check_tight = !!tight;
 252
 253         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
 254                                                         guarded_fold, &bound) < 0)
 255                 goto error;
 256
 257         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 258         if (covers < 0)
 259                 goto error;
 260
 261         if (tight)
 262                 *tight = covers;
 263
 264         isl_dim_free(dim);
 265         isl_pw_qpolynomial_fold_free(pwf);
 266
 267         if (covers) {
 268                 isl_pw_qpolynomial_fold_free(bound.pwf);
 269                 return bound.pwf_tight;
 270         }
 271
 272         bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
 273
 274         return bound.pwf;
 275 error:
 276         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 277         isl_pw_qpolynomial_fold_free(bound.pwf);
 278         isl_pw_qpolynomial_fold_free(pwf);
 279         isl_dim_free(dim);
 280         return NULL;
 281 }
 282
 283 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 284         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
 285 {
 286         isl_pw_qpolynomial_fold *pwf;
 287
 288         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 289         return isl_pw_qpolynomial_fold_bound(pwf, tight);
 290 }
 291
 292 struct isl_union_bound_data {
 293         enum isl_fold type;
 294         int tight;
 295         isl_union_pw_qpolynomial_fold *res;
 296 };
 297
 298 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
 299 {
 300         struct isl_union_bound_data *data = user;
 301         isl_pw_qpolynomial_fold *pwf;
 302
 303         pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
 304                                         data->tight ? &data->tight : NULL);
 305         data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
 306                                                                 data->res, pwf);
 307
 308         return 0;
 309 }
 310
 311 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
 312         __isl_take isl_union_pw_qpolynomial *upwqp,
 313         enum isl_fold type, int *tight)
 314 {
 315         isl_dim *dim;
 316         struct isl_union_bound_data data = { type, 1, NULL };
 317
 318         if (!upwqp)
 319                 return NULL;
 320
 321         if (!tight)
 322                 data.tight = 0;
 323
 324         dim = isl_union_pw_qpolynomial_get_dim(upwqp);
 325         data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
 326         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
 327                                                     &bound_pw, &data) < 0)
 328                 goto error;
 329
 330         isl_union_pw_qpolynomial_free(upwqp);
 331         if (tight)
 332                 *tight = data.tight;
 333
 334         return data.res;
 335 error:
 336         isl_union_pw_qpolynomial_free(upwqp);
 337         isl_union_pw_qpolynomial_fold_free(data.res);
 338         return NULL;
 339 }