isl_range.c

   1 #include <isl_constraint.h>
   2 #include <isl_set.h>
   3 #include <isl_polynomial_private.h>
   4 #include <isl_morph.h>
   5 #include <isl_range.h>
   6
   7 struct range_data {
   8         struct isl_bound        *bound;
   9         int                     *signs;
  10         int                     sign;
  11         int                     test_monotonicity;
  12         int                     monotonicity;
  13         int                     tight;
  14         isl_qpolynomial         *poly;
  15         isl_pw_qpolynomial_fold *pwf;
  16         isl_pw_qpolynomial_fold *pwf_tight;
  17 };
  18
  19 static int propagate_on_domain(__isl_take isl_basic_set *bset,
  20         __isl_take isl_qpolynomial *poly, struct range_data *data);
  21
  22 /* Check whether the polynomial "poly" has sign "sign" over "bset",
  23  * i.e., if sign == 1, check that the lower bound on the polynomial
  24  * is non-negative and if sign == -1, check that the upper bound on
  25  * the polynomial is non-positive.
  26  */
  27 static int has_sign(__isl_keep isl_basic_set *bset,
  28         __isl_keep isl_qpolynomial *poly, int sign, int *signs)
  29 {
  30         struct range_data data_m;
  31         unsigned nvar;
  32         unsigned nparam;
  33         isl_dim *dim;
  34         isl_qpolynomial *opt;
  35         int r;
  36         enum isl_fold type;
  37
  38         nparam = isl_basic_set_dim(bset, isl_dim_param);
  39         nvar = isl_basic_set_dim(bset, isl_dim_set);
  40
  41         bset = isl_basic_set_copy(bset);
  42         poly = isl_qpolynomial_copy(poly);
  43
  44         bset = isl_basic_set_move_dims(bset, isl_dim_set, 0,
  45                                         isl_dim_param, 0, nparam);
  46         poly = isl_qpolynomial_move_dims(poly, isl_dim_set, 0,
  47                                         isl_dim_param, 0, nparam);
  48
  49         dim = isl_qpolynomial_get_dim(poly);
  50         dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
  51
  52         data_m.test_monotonicity = 0;
  53         data_m.signs = signs;
  54         data_m.sign = -sign;
  55         type = data_m.sign < 0 ? isl_fold_min : isl_fold_max;
  56         data_m.pwf = isl_pw_qpolynomial_fold_zero(dim, type);
  57         data_m.tight = 0;
  58         data_m.pwf_tight = NULL;
  59
  60         if (propagate_on_domain(bset, poly, &data_m) < 0)
  61                 goto error;
  62
  63         if (sign > 0)
  64                 opt = isl_pw_qpolynomial_fold_min(data_m.pwf);
  65         else
  66                 opt = isl_pw_qpolynomial_fold_max(data_m.pwf);
  67
  68         if (!opt)
  69                 r = -1;
  70         else if (isl_qpolynomial_is_nan(opt) ||
  71                  isl_qpolynomial_is_infty(opt) ||
  72                  isl_qpolynomial_is_neginfty(opt))
  73                 r = 0;
  74         else
  75                 r = sign * isl_qpolynomial_sgn(opt) >= 0;
  76
  77         isl_qpolynomial_free(opt);
  78
  79         return r;
  80 error:
  81         isl_pw_qpolynomial_fold_free(data_m.pwf);
  82         return -1;
  83 }
  84
  85 /* Return  1 if poly is monotonically increasing in the last set variable,
  86  *        -1 if poly is monotonically decreasing in the last set variable,
  87  *         0 if no conclusion,
  88  *        -2 on error.
  89  *
  90  * We simply check the sign of p(x+1)-p(x)
  91  */
  92 static int monotonicity(__isl_keep isl_basic_set *bset,
  93         __isl_keep isl_qpolynomial *poly, struct range_data *data)
  94 {
  95         isl_ctx *ctx;
  96         isl_dim *dim;
  97         isl_qpolynomial *sub = NULL;
  98         isl_qpolynomial *diff = NULL;
  99         int result = 0;
 100         int s;
 101         unsigned nvar;
 102
 103         ctx = isl_qpolynomial_get_ctx(poly);
 104         dim = isl_qpolynomial_get_dim(poly);
 105
 106         nvar = isl_basic_set_dim(bset, isl_dim_set);
 107
 108         sub = isl_qpolynomial_var(isl_dim_copy(dim), isl_dim_set, nvar - 1);
 109         sub = isl_qpolynomial_add(sub,
 110                 isl_qpolynomial_rat_cst(dim, ctx->one, ctx->one));
 111
 112         diff = isl_qpolynomial_substitute(isl_qpolynomial_copy(poly),
 113                         isl_dim_set, nvar - 1, 1, &sub);
 114         diff = isl_qpolynomial_sub(diff, isl_qpolynomial_copy(poly));
 115
 116         s = has_sign(bset, diff, 1, data->signs);
 117         if (s < 0)
 118                 goto error;
 119         if (s)
 120                 result = 1;
 121         else {
 122                 s = has_sign(bset, diff, -1, data->signs);
 123                 if (s < 0)
 124                         goto error;
 125                 if (s)
 126                         result = -1;
 127         }
 128
 129         isl_qpolynomial_free(diff);
 130         isl_qpolynomial_free(sub);
 131
 132         return result;
 133 error:
 134         isl_qpolynomial_free(diff);
 135         isl_qpolynomial_free(sub);
 136         return -2;
 137 }
 138
 139 static __isl_give isl_qpolynomial *bound2poly(__isl_take isl_constraint *bound,
 140         __isl_take isl_dim *dim, unsigned pos, int sign)
 141 {
 142         if (!bound) {
 143                 if (sign > 0)
 144                         return isl_qpolynomial_infty(dim);
 145                 else
 146                         return isl_qpolynomial_neginfty(dim);
 147         }
 148         isl_dim_free(dim);
 149         return isl_qpolynomial_from_constraint(bound, isl_dim_set, pos);
 150 }
 151
 152 static int bound_is_integer(__isl_take isl_constraint *bound, unsigned pos)
 153 {
 154         isl_int c;
 155         int is_int;
 156
 157         if (!bound)
 158                 return 1;
 159
 160         isl_int_init(c);
 161         isl_constraint_get_coefficient(bound, isl_dim_set, pos, &c);
 162         is_int = isl_int_is_one(c) || isl_int_is_negone(c);
 163         isl_int_clear(c);
 164
 165         return is_int;
 166 }
 167
 168 struct isl_fixed_sign_data {
 169         int             *signs;
 170         int             sign;
 171         isl_qpolynomial *poly;
 172 };
 173
 174 /* Add term "term" to data->poly if it has sign data->sign.
 175  * The sign is determined based on the signs of the parameters
 176  * and variables in data->signs.  The integer divisions, if
 177  * any, are assumed to be non-negative.
 178  */
 179 static int collect_fixed_sign_terms(__isl_take isl_term *term, void *user)
 180 {
 181         struct isl_fixed_sign_data *data = (struct isl_fixed_sign_data *)user;
 182         isl_int n;
 183         int i;
 184         int sign;
 185         unsigned nparam;
 186         unsigned nvar;
 187
 188         if (!term)
 189                 return -1;
 190
 191         nparam = isl_term_dim(term, isl_dim_param);
 192         nvar = isl_term_dim(term, isl_dim_set);
 193
 194         isl_int_init(n);
 195
 196         isl_term_get_num(term, &n);
 197
 198         sign = isl_int_sgn(n);
 199         for (i = 0; i < nparam; ++i) {
 200                 if (data->signs[i] > 0)
 201                         continue;
 202                 if (isl_term_get_exp(term, isl_dim_param, i) % 2)
 203                         sign = -sign;
 204         }
 205         for (i = 0; i < nvar; ++i) {
 206                 if (data->signs[nparam + i] > 0)
 207                         continue;
 208                 if (isl_term_get_exp(term, isl_dim_set, i) % 2)
 209                         sign = -sign;
 210         }
 211
 212         if (sign == data->sign) {
 213                 isl_qpolynomial *t = isl_qpolynomial_from_term(term);
 214
 215                 data->poly = isl_qpolynomial_add(data->poly, t);
 216         } else
 217                 isl_term_free(term);
 218
 219         isl_int_clear(n);
 220
 221         return 0;
 222 }
 223
 224 /* Construct and return a polynomial that consists of the terms
 225  * in "poly" that have sign "sign".  The integer divisions, if
 226  * any, are assumed to be non-negative.
 227  */
 228 __isl_give isl_qpolynomial *isl_qpolynomial_terms_of_sign(
 229         __isl_keep isl_qpolynomial *poly, int *signs, int sign)
 230 {
 231         struct isl_fixed_sign_data data = { signs, sign };
 232         data.poly = isl_qpolynomial_zero(isl_qpolynomial_get_dim(poly));
 233
 234         if (isl_qpolynomial_foreach_term(poly, collect_fixed_sign_terms, &data) < 0)
 235                 goto error;
 236
 237         return data.poly;
 238 error:
 239         isl_qpolynomial_free(data.poly);
 240         return NULL;
 241 }
 242
 243 /* Helper function to add a guarded polynomial to either pwf_tight or pwf,
 244  * depending on whether the result has been determined to be tight.
 245  */
 246 static int add_guarded_poly(__isl_take isl_basic_set *bset,
 247         __isl_take isl_qpolynomial *poly, struct range_data *data)
 248 {
 249         enum isl_fold type = data->sign < 0 ? isl_fold_min : isl_fold_max;
 250         isl_set *set;
 251         isl_qpolynomial_fold *fold;
 252         isl_pw_qpolynomial_fold *pwf;
 253
 254         fold = isl_qpolynomial_fold_alloc(type, poly);
 255         set = isl_set_from_basic_set(bset);
 256         pwf = isl_pw_qpolynomial_fold_alloc(type, set, fold);
 257         if (data->tight)
 258                 data->pwf_tight = isl_pw_qpolynomial_fold_fold(
 259                                                 data->pwf_tight, pwf);
 260         else
 261                 data->pwf = isl_pw_qpolynomial_fold_fold(data->pwf, pwf);
 262
 263         return 0;
 264 }
 265
 266 /* Given a lower and upper bound on the final variable and constraints
 267  * on the remaining variables where these bounds are active,
 268  * eliminate the variable from data->poly based on these bounds.
 269  * If the polynomial has been determined to be monotonic
 270  * in the variable, then simply plug in the appropriate bound.
 271  * If the current polynomial is tight and if this bound is integer,
 272  * then the result is still tight.  In all other cases, the results
 273  * may not be tight.
 274  * Otherwise, plug in the largest bound (in absolute value) in
 275  * the positive terms (if an upper bound is wanted) or the negative terms
 276  * (if a lower bounded is wanted) and the other bound in the other terms.
 277  *
 278  * If all variables have been eliminated, then record the result.
 279  * Ohterwise, recurse on the next variable.
 280  */
 281 static int propagate_on_bound_pair(__isl_take isl_constraint *lower,
 282         __isl_take isl_constraint *upper, __isl_take isl_basic_set *bset,
 283         void *user)
 284 {
 285         struct range_data *data = (struct range_data *)user;
 286         int save_tight = data->tight;
 287         isl_qpolynomial *poly;
 288         int r;
 289         unsigned nvar;
 290
 291         nvar = isl_basic_set_dim(bset, isl_dim_set);
 292
 293         if (data->monotonicity) {
 294                 isl_qpolynomial *sub;
 295                 isl_dim *dim = isl_qpolynomial_get_dim(data->poly);
 296                 if (data->monotonicity * data->sign > 0) {
 297                         if (data->tight)
 298                                 data->tight = bound_is_integer(upper, nvar);
 299                         sub = bound2poly(upper, dim, nvar, 1);
 300                         isl_constraint_free(lower);
 301                 } else {
 302                         if (data->tight)
 303                                 data->tight = bound_is_integer(lower, nvar);
 304                         sub = bound2poly(lower, dim, nvar, -1);
 305                         isl_constraint_free(upper);
 306                 }
 307                 poly = isl_qpolynomial_copy(data->poly);
 308                 poly = isl_qpolynomial_substitute(poly, isl_dim_set, nvar, 1, &sub);
 309                 poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, nvar, 1);
 310
 311                 isl_qpolynomial_free(sub);
 312         } else {
 313                 isl_qpolynomial *l, *u;
 314                 isl_qpolynomial *pos, *neg;
 315                 isl_dim *dim = isl_qpolynomial_get_dim(data->poly);
 316                 unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
 317                 int sign = data->sign * data->signs[nparam + nvar];
 318
 319                 data->tight = 0;
 320
 321                 u = bound2poly(upper, isl_dim_copy(dim), nvar, 1);
 322                 l = bound2poly(lower, dim, nvar, -1);
 323
 324                 pos = isl_qpolynomial_terms_of_sign(data->poly, data->signs, sign);
 325                 neg = isl_qpolynomial_terms_of_sign(data->poly, data->signs, -sign);
 326
 327                 pos = isl_qpolynomial_substitute(pos, isl_dim_set, nvar, 1, &u);
 328                 neg = isl_qpolynomial_substitute(neg, isl_dim_set, nvar, 1, &l);
 329
 330                 poly = isl_qpolynomial_add(pos, neg);
 331                 poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, nvar, 1);
 332
 333                 isl_qpolynomial_free(u);
 334                 isl_qpolynomial_free(l);
 335         }
 336
 337         if (isl_basic_set_dim(bset, isl_dim_set) == 0)
 338                 r = add_guarded_poly(bset, poly, data);
 339         else
 340                 r = propagate_on_domain(bset, poly, data);
 341
 342         data->tight = save_tight;
 343
 344         return r;
 345 }
 346
 347 /* Recursively perform range propagation on the polynomial "poly"
 348  * defined over the basic set "bset" and collect the results in "data".
 349  */
 350 static int propagate_on_domain(__isl_take isl_basic_set *bset,
 351         __isl_take isl_qpolynomial *poly, struct range_data *data)
 352 {
 353         isl_qpolynomial *save_poly = data->poly;
 354         int save_monotonicity = data->monotonicity;
 355         unsigned d;
 356
 357         if (!bset || !poly)
 358                 goto error;
 359
 360         d = isl_basic_set_dim(bset, isl_dim_set);
 361         isl_assert(bset->ctx, d >= 1, goto error);
 362
 363         if (isl_qpolynomial_is_cst(poly, NULL, NULL)) {
 364                 bset = isl_basic_set_project_out(bset, isl_dim_set, 0, d);
 365                 poly = isl_qpolynomial_drop_dims(poly, isl_dim_set, 0, d);
 366                 return add_guarded_poly(bset, poly, data);
 367         }
 368
 369         if (data->test_monotonicity)
 370                 data->monotonicity = monotonicity(bset, poly, data);
 371         else
 372                 data->monotonicity = 0;
 373         if (data->monotonicity < -1)
 374                 goto error;
 375
 376         data->poly = poly;
 377         if (isl_basic_set_foreach_bound_pair(bset, isl_dim_set, d - 1,
 378                                             &propagate_on_bound_pair, data) < 0)
 379                 goto error;
 380
 381         isl_basic_set_free(bset);
 382         isl_qpolynomial_free(poly);
 383         data->monotonicity = save_monotonicity;
 384         data->poly = save_poly;
 385
 386         return 0;
 387 error:
 388         isl_basic_set_free(bset);
 389         isl_qpolynomial_free(poly);
 390         data->monotonicity = save_monotonicity;
 391         data->poly = save_poly;
 392         return -1;
 393 }
 394
 395 static int basic_guarded_poly_bound(__isl_take isl_basic_set *bset, void *user)
 396 {
 397         struct range_data *data = (struct range_data *)user;
 398         unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
 399         unsigned dim = isl_basic_set_dim(bset, isl_dim_set);
 400         int r;
 401
 402         data->signs = NULL;
 403
 404         data->signs = isl_alloc_array(bset->ctx, int,
 405                                         isl_basic_set_dim(bset, isl_dim_all));
 406
 407         if (isl_basic_set_dims_get_sign(bset, isl_dim_set, 0, dim,
 408                                         data->signs + nparam) < 0)
 409                 goto error;
 410         if (isl_basic_set_dims_get_sign(bset, isl_dim_param, 0, nparam,
 411                                         data->signs) < 0)
 412                 goto error;
 413
 414         r = propagate_on_domain(bset, isl_qpolynomial_copy(data->poly), data);
 415
 416         free(data->signs);
 417
 418         return r;
 419 error:
 420         free(data->signs);
 421         isl_basic_set_free(bset);
 422         return -1;
 423 }
 424
 425 static int qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
 426         __isl_take isl_qpolynomial *poly, struct range_data *data)
 427 {
 428         unsigned nparam = isl_basic_set_dim(bset, isl_dim_param);
 429         unsigned nvar = isl_basic_set_dim(bset, isl_dim_set);
 430         isl_set *set;
 431
 432         if (!bset)
 433                 goto error;
 434
 435         if (nvar == 0)
 436                 return add_guarded_poly(bset, poly, data);
 437
 438         set = isl_set_from_basic_set(bset);
 439         set = isl_set_split_dims(set, isl_dim_param, 0, nparam);
 440         set = isl_set_split_dims(set, isl_dim_set, 0, nvar);
 441
 442         data->poly = poly;
 443
 444         data->test_monotonicity = 1;
 445         if (isl_set_foreach_basic_set(set, &basic_guarded_poly_bound, data) < 0)
 446                 goto error;
 447
 448         isl_set_free(set);
 449         isl_qpolynomial_free(poly);
 450
 451         return 0;
 452 error:
 453         isl_set_free(set);
 454         isl_qpolynomial_free(poly);
 455         return -1;
 456 }
 457
 458 int isl_qpolynomial_bound_on_domain_range(__isl_take isl_basic_set *bset,
 459         __isl_take isl_qpolynomial *poly, struct isl_bound *bound)
 460 {
 461         struct range_data data;
 462         int r;
 463
 464         data.pwf = bound->pwf;
 465         data.pwf_tight = bound->pwf_tight;
 466         data.tight = bound->check_tight;
 467         if (bound->type == isl_fold_min)
 468                 data.sign = -1;
 469         else
 470                 data.sign = 1;
 471
 472         r = qpolynomial_bound_on_domain_range(bset, poly, &data);
 473
 474         bound->pwf = data.pwf;
 475         bound->pwf_tight = data.pwf_tight;
 476
 477         return r;
 478 }