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