isl_bound.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT 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 #include <isl_options_private.h>
  18
  19 /* Add the bound "pwf", which is not known to be tight,
  20  * to the output of "bound".
  21  */
  22 isl_stat isl_bound_add(struct isl_bound *bound,
  23         __isl_take isl_pw_qpolynomial_fold *pwf)
  24 {
  25         bound->pwf = isl_pw_qpolynomial_fold_fold(bound->pwf, pwf);
  26         return isl_stat_non_null(bound->pwf);
  27 }
  28
  29 /* Add the bound "pwf", which is known to be tight,
  30  * to the output of "bound".
  31  */
  32 isl_stat isl_bound_add_tight(struct isl_bound *bound,
  33         __isl_take isl_pw_qpolynomial_fold *pwf)
  34 {
  35         bound->pwf_tight = isl_pw_qpolynomial_fold_fold(bound->pwf_tight, pwf);
  36         return isl_stat_non_null(bound->pwf);
  37 }
  38
  39 /* Compute a bound on the polynomial defined over the parametric polytope
  40  * using either range propagation or bernstein expansion and
  41  * store the result in bound->pwf and bound->pwf_tight.
  42  * Since bernstein expansion requires bounded domains, we apply
  43  * range propagation on unbounded domains.  Otherwise, we respect the choice
  44  * of the user.
  45  */
  46 static isl_stat compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
  47         __isl_take isl_qpolynomial *poly, void *user)
  48 {
  49         struct isl_bound *bound = (struct isl_bound *)user;
  50         isl_ctx *ctx;
  51         int bounded;
  52
  53         if (!bset || !poly)
  54                 goto error;
  55
  56         ctx = isl_basic_set_get_ctx(bset);
  57         if (ctx->opt->bound == ISL_BOUND_RANGE)
  58                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
  59
  60         bounded = isl_basic_set_is_bounded(bset);
  61         if (bounded < 0)
  62                 goto error;
  63         if (bounded)
  64                 return isl_qpolynomial_bound_on_domain_bernstein(bset, poly, bound);
  65         else
  66                 return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
  67 error:
  68         isl_basic_set_free(bset);
  69         isl_qpolynomial_free(poly);
  70         return isl_stat_error;
  71 }
  72
  73 static isl_stat unwrapped_guarded_poly_bound(__isl_take isl_basic_set *bset,
  74         __isl_take isl_qpolynomial *poly, void *user)
  75 {
  76         struct isl_bound *bound = (struct isl_bound *)user;
  77         isl_pw_qpolynomial_fold *top_pwf;
  78         isl_pw_qpolynomial_fold *top_pwf_tight;
  79         isl_space *space;
  80         isl_morph *morph;
  81         isl_stat r;
  82
  83         bset = isl_basic_set_detect_equalities(bset);
  84
  85         if (!bset)
  86                 goto error;
  87
  88         if (bset->n_eq == 0)
  89                 return compressed_guarded_poly_bound(bset, poly, user);
  90
  91         morph = isl_basic_set_full_compression(bset);
  92
  93         bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
  94         poly = isl_qpolynomial_morph_domain(poly, isl_morph_copy(morph));
  95
  96         space = isl_morph_get_ran_space(morph);
  97         space = isl_space_params(space);
  98
  99         top_pwf = bound->pwf;
 100         top_pwf_tight = bound->pwf_tight;
 101
 102         space = isl_space_from_domain(space);
 103         space = isl_space_add_dims(space, isl_dim_out, 1);
 104         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
 105                                                   bound->type);
 106         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);
 107
 108         r = compressed_guarded_poly_bound(bset, poly, user);
 109
 110         morph = isl_morph_dom_params(morph);
 111         morph = isl_morph_ran_params(morph);
 112         morph = isl_morph_inverse(morph);
 113
 114         bound->pwf = isl_pw_qpolynomial_fold_morph_domain(bound->pwf,
 115                                                         isl_morph_copy(morph));
 116         bound->pwf_tight = isl_pw_qpolynomial_fold_morph_domain(
 117                                                 bound->pwf_tight, morph);
 118
 119         isl_bound_add(bound, top_pwf);
 120         isl_bound_add_tight(bound, top_pwf_tight);
 121
 122         return r;
 123 error:
 124         isl_basic_set_free(bset);
 125         isl_qpolynomial_free(poly);
 126         return isl_stat_error;
 127 }
 128
 129 /* Update bound->pwf and bound->pwf_tight with a bound
 130  * of type bound->type on the polynomial "poly" over the domain "bset".
 131  *
 132  * If the original problem had a wrapped relation in the domain,
 133  * meaning that the bound should be computed over the range
 134  * of this relation, then temporarily treat the domain dimensions
 135  * of this wrapped relation as parameters, compute a bound
 136  * in terms of these and the original parameters,
 137  * turn the parameters back into set dimensions and
 138  * add the results to bound->pwf and bound->pwf_tight.
 139  *
 140  * Note that even though "bset" is known to live in the same space
 141  * as the domain of "poly", the names of the set dimensions
 142  * may be different (or missing).  Make sure the naming is exactly
 143  * the same before turning these dimensions into parameters
 144  * to ensure that the spaces are still the same after
 145  * this operation.
 146  */
 147 static isl_stat guarded_poly_bound(__isl_take isl_basic_set *bset,
 148         __isl_take isl_qpolynomial *poly, void *user)
 149 {
 150         struct isl_bound *bound = (struct isl_bound *)user;
 151         isl_space *space;
 152         isl_pw_qpolynomial_fold *top_pwf;
 153         isl_pw_qpolynomial_fold *top_pwf_tight;
 154         isl_size nparam;
 155         isl_size n_in;
 156         isl_stat r;
 157
 158         if (!bound->wrapping)
 159                 return unwrapped_guarded_poly_bound(bset, poly, user);
 160
 161         nparam = isl_space_dim(bound->dim, isl_dim_param);
 162         n_in = isl_space_dim(bound->dim, isl_dim_in);
 163         if (nparam < 0 || n_in < 0)
 164                 goto error;
 165
 166         space = isl_qpolynomial_get_domain_space(poly);
 167         bset = isl_basic_set_reset_space(bset, space);
 168
 169         bset = isl_basic_set_move_dims(bset, isl_dim_param, nparam,
 170                                         isl_dim_set, 0, n_in);
 171         poly = isl_qpolynomial_move_dims(poly, isl_dim_param, nparam,
 172                                         isl_dim_in, 0, n_in);
 173
 174         space = isl_basic_set_get_space(bset);
 175         space = isl_space_params(space);
 176
 177         top_pwf = bound->pwf;
 178         top_pwf_tight = bound->pwf_tight;
 179
 180         space = isl_space_from_domain(space);
 181         space = isl_space_add_dims(space, isl_dim_out, 1);
 182         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(space),
 183                                                   bound->type);
 184         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(space, bound->type);
 185
 186         r = unwrapped_guarded_poly_bound(bset, poly, user);
 187
 188         bound->pwf = isl_pw_qpolynomial_fold_reset_space(bound->pwf,
 189                                                     isl_space_copy(bound->dim));
 190         bound->pwf_tight = isl_pw_qpolynomial_fold_reset_space(bound->pwf_tight,
 191                                                     isl_space_copy(bound->dim));
 192
 193         isl_bound_add(bound, top_pwf);
 194         isl_bound_add_tight(bound, top_pwf_tight);
 195
 196         return r;
 197 error:
 198         isl_basic_set_free(bset);
 199         isl_qpolynomial_free(poly);
 200         return isl_stat_error;
 201 }
 202
 203 static isl_stat guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
 204 {
 205         struct isl_bound *bound = (struct isl_bound *)user;
 206         isl_stat r;
 207
 208         r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
 209                                                     &guarded_poly_bound, user);
 210         isl_qpolynomial_free(qp);
 211         return r;
 212 }
 213
 214 static isl_stat basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
 215 {
 216         struct isl_bound *bound = (struct isl_bound *)user;
 217         isl_stat r;
 218
 219         bound->bset = bset;
 220         r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
 221                                                         &guarded_qp, user);
 222         isl_basic_set_free(bset);
 223         return r;
 224 }
 225
 226 static isl_stat guarded_fold(__isl_take isl_set *set,
 227         __isl_take isl_qpolynomial_fold *fold, void *user)
 228 {
 229         struct isl_bound *bound = (struct isl_bound *)user;
 230
 231         if (!set || !fold)
 232                 goto error;
 233
 234         set = isl_set_make_disjoint(set);
 235
 236         bound->fold = fold;
 237         bound->type = isl_qpolynomial_fold_get_type(fold);
 238
 239         if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
 240                 goto error;
 241
 242         isl_set_free(set);
 243         isl_qpolynomial_fold_free(fold);
 244
 245         return isl_stat_ok;
 246 error:
 247         isl_set_free(set);
 248         isl_qpolynomial_fold_free(fold);
 249         return isl_stat_error;
 250 }
 251
 252 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 253         __isl_take isl_pw_qpolynomial_fold *pwf, isl_bool *tight)
 254 {
 255         isl_size nvar;
 256         struct isl_bound bound;
 257         isl_bool covers;
 258
 259         if (!pwf)
 260                 return NULL;
 261
 262         bound.dim = isl_pw_qpolynomial_fold_get_domain_space(pwf);
 263
 264         bound.wrapping = isl_space_is_wrapping(bound.dim);
 265         if (bound.wrapping)
 266                 bound.dim = isl_space_unwrap(bound.dim);
 267         nvar = isl_space_dim(bound.dim, isl_dim_out);
 268         if (nvar < 0)
 269                 bound.dim = isl_space_free(bound.dim);
 270         bound.dim = isl_space_domain(bound.dim);
 271         bound.dim = isl_space_from_domain(bound.dim);
 272         bound.dim = isl_space_add_dims(bound.dim, isl_dim_out, 1);
 273
 274         if (nvar == 0) {
 275                 if (tight)
 276                         *tight = isl_bool_true;
 277                 return isl_pw_qpolynomial_fold_reset_space(pwf, bound.dim);
 278         }
 279
 280         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
 281                 enum isl_fold type = pwf->type;
 282                 isl_pw_qpolynomial_fold_free(pwf);
 283                 if (tight)
 284                         *tight = isl_bool_true;
 285                 return isl_pw_qpolynomial_fold_zero(bound.dim, type);
 286         }
 287
 288         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
 289                                                         pwf->type);
 290         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_space_copy(bound.dim),
 291                                                         pwf->type);
 292         bound.check_tight = !!tight;
 293
 294         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
 295                                                         guarded_fold, &bound) < 0)
 296                 goto error;
 297
 298         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 299         if (covers < 0)
 300                 goto error;
 301
 302         if (tight)
 303                 *tight = covers;
 304
 305         isl_space_free(bound.dim);
 306         isl_pw_qpolynomial_fold_free(pwf);
 307
 308         if (covers) {
 309                 isl_pw_qpolynomial_fold_free(bound.pwf);
 310                 return bound.pwf_tight;
 311         }
 312
 313         bound.pwf = isl_pw_qpolynomial_fold_fold(bound.pwf, bound.pwf_tight);
 314
 315         return bound.pwf;
 316 error:
 317         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 318         isl_pw_qpolynomial_fold_free(bound.pwf);
 319         isl_pw_qpolynomial_fold_free(pwf);
 320         isl_space_free(bound.dim);
 321         return NULL;
 322 }
 323
 324 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 325         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type,
 326         isl_bool *tight)
 327 {
 328         isl_pw_qpolynomial_fold *pwf;
 329
 330         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 331         return isl_pw_qpolynomial_fold_bound(pwf, tight);
 332 }
 333
 334 struct isl_union_bound_data {
 335         enum isl_fold type;
 336         isl_bool tight;
 337         isl_union_pw_qpolynomial_fold *res;
 338 };
 339
 340 static isl_stat bound_pw(__isl_take isl_pw_qpolynomial *pwqp, void *user)
 341 {
 342         struct isl_union_bound_data *data = user;
 343         isl_pw_qpolynomial_fold *pwf;
 344
 345         pwf = isl_pw_qpolynomial_bound(pwqp, data->type,
 346                                         data->tight ? &data->tight : NULL);
 347         data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
 348                                                                 data->res, pwf);
 349
 350         return isl_stat_ok;
 351 }
 352
 353 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
 354         __isl_take isl_union_pw_qpolynomial *upwqp,
 355         enum isl_fold type, isl_bool *tight)
 356 {
 357         isl_space *space;
 358         struct isl_union_bound_data data = { type, 1, NULL };
 359
 360         if (!upwqp)
 361                 return NULL;
 362
 363         if (!tight)
 364                 data.tight = isl_bool_false;
 365
 366         space = isl_union_pw_qpolynomial_get_space(upwqp);
 367         data.res = isl_union_pw_qpolynomial_fold_zero(space, type);
 368         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp,
 369                                                     &bound_pw, &data) < 0)
 370                 goto error;
 371
 372         isl_union_pw_qpolynomial_free(upwqp);
 373         if (tight)
 374                 *tight = data.tight;
 375
 376         return data.res;
 377 error:
 378         isl_union_pw_qpolynomial_free(upwqp);
 379         isl_union_pw_qpolynomial_fold_free(data.res);
 380         return NULL;
 381 }