isl_range.c

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