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 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_qp(__isl_take isl_qpolynomial *qp, void *user)
 107 {
 108         struct isl_bound *bound = (struct isl_bound *)user;
 109         int r;
 110
 111         r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
 112                                                     &guarded_poly_bound, user);
 113         isl_qpolynomial_free(qp);
 114         return r;
 115 }
 116
 117 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
 118 {
 119         struct isl_bound *bound = (struct isl_bound *)user;
 120         int r;
 121
 122         bound->bset = bset;
 123         r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
 124                                                         &guarded_qp, user);
 125         isl_basic_set_free(bset);
 126         return r;
 127 }
 128
 129 static int guarded_fold(__isl_take isl_set *set,
 130         __isl_take isl_qpolynomial_fold *fold, void *user)
 131 {
 132         struct isl_bound *bound = (struct isl_bound *)user;
 133
 134         if (!set || !fold)
 135                 goto error;
 136
 137         set = isl_set_make_disjoint(set);
 138
 139         bound->fold = fold;
 140         bound->type = isl_qpolynomial_fold_get_type(fold);
 141
 142         if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
 143                 goto error;
 144
 145         isl_set_free(set);
 146         isl_qpolynomial_fold_free(fold);
 147
 148         return 0;
 149 error:
 150         isl_set_free(set);
 151         isl_qpolynomial_fold_free(fold);
 152         return -1;
 153 }
 154
 155 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 156         __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
 157 {
 158         isl_dim *dim;
 159         unsigned nvar;
 160         struct isl_bound bound;
 161         int covers;
 162
 163         if (!pwf)
 164                 return NULL;
 165
 166         dim = isl_pw_qpolynomial_fold_get_dim(pwf);
 167         nvar = isl_dim_size(dim, isl_dim_set);
 168
 169         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
 170                 isl_pw_qpolynomial_fold_free(pwf);
 171                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 172                 if (tight)
 173                         *tight = 1;
 174                 return isl_pw_qpolynomial_fold_zero(dim);
 175         }
 176
 177         if (nvar == 0) {
 178                 isl_dim_free(dim);
 179                 if (tight)
 180                         *tight = 1;
 181                 return pwf;
 182         }
 183
 184         dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 185
 186         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 187         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 188         bound.check_tight = !!tight;
 189
 190         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
 191                                                         guarded_fold, &bound) < 0)
 192                 goto error;
 193
 194         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 195         if (covers < 0)
 196                 goto error;
 197
 198         if (tight)
 199                 *tight = covers;
 200
 201         isl_dim_free(dim);
 202         isl_pw_qpolynomial_fold_free(pwf);
 203
 204         if (covers) {
 205                 isl_pw_qpolynomial_fold_free(bound.pwf);
 206                 return bound.pwf_tight;
 207         }
 208
 209         bound.pwf = isl_pw_qpolynomial_fold_add(bound.pwf, bound.pwf_tight);
 210
 211         return bound.pwf;
 212 error:
 213         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 214         isl_pw_qpolynomial_fold_free(bound.pwf);
 215         isl_pw_qpolynomial_fold_free(pwf);
 216         isl_dim_free(dim);
 217         return NULL;
 218 }
 219
 220 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 221         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
 222 {
 223         isl_pw_qpolynomial_fold *pwf;
 224
 225         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 226         return isl_pw_qpolynomial_fold_bound(pwf, tight);
 227 }
 228
 229 struct isl_union_bound_data {
 230         enum isl_fold type;
 231         int tight;
 232         isl_union_pw_qpolynomial_fold *res;
 233 };
 234
 235 static int bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
 236 {
 237         struct isl_union_bound_data *data = user;
 238         isl_pw_qpolynomial_fold *pwf;
 239
 240         pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
 241                                         data->tight ? &data->tight : NULL);
 242         data->res = isl_union_pw_qpolynomial_fold_add_pw_qpolynomial_fold(
 243                                                                 data->res, pwf);
 244
 245         return 0;
 246 }
 247
 248 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
 249         __isl_take isl_union_pw_qpolynomial *upwqp,
 250         enum isl_fold type, int *tight)
 251 {
 252         isl_dim *dim;
 253         struct isl_union_bound_data data = { type, 1, NULL };
 254
 255         if (!upwqp)
 256                 return NULL;
 257
 258         if (!tight)
 259                 data.tight = 0;
 260
 261         dim = isl_union_pw_qpolynomial_get_dim(upwqp);
 262         data.res = isl_union_pw_qpolynomial_fold_zero(dim);
 263         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
 264                                                     &bound_pw, &data) < 0)
 265                 goto error;
 266
 267         isl_union_pw_qpolynomial_free(upwqp);
 268         if (tight)
 269                 *tight = data.tight;
 270
 271         return data.res;
 272 error:
 273         isl_union_pw_qpolynomial_free(upwqp);
 274         isl_union_pw_qpolynomial_fold_free(data.res);
 275         return NULL;
 276 }