isl_constraint.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2010      INRIA Saclay
   4  *
   5  * Use of this software is governed by the GNU LGPLv2.1 license
   6  *
   7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  11  */
  12
  13 #include <isl_map_private.h>
  14 #include <isl/constraint.h>
  15 #include <isl_dim_private.h>
  16 #include <isl/seq.h>
  17
  18 static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
  19 {
  20         return isl_basic_map_dim(c->bmap, type);
  21 }
  22
  23 static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
  24 {
  25         struct isl_dim *dim = c->bmap->dim;
  26         switch (type) {
  27         case isl_dim_param:     return 1;
  28         case isl_dim_in:        return 1 + dim->nparam;
  29         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  30         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
  31         default:                return 0;
  32         }
  33 }
  34
  35 static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
  36                                                         enum isl_dim_type type)
  37 {
  38         return type == isl_dim_div ? 1 + isl_dim_total(bmap->dim)
  39                                    : 1 + isl_dim_offset(bmap->dim, type);
  40 }
  41
  42 static unsigned basic_set_offset(struct isl_basic_set *bset,
  43                                                         enum isl_dim_type type)
  44 {
  45         struct isl_dim *dim = bset->dim;
  46         switch (type) {
  47         case isl_dim_param:     return 1;
  48         case isl_dim_in:        return 1 + dim->nparam;
  49         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  50         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
  51         default:                return 0;
  52         }
  53 }
  54
  55 struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
  56         isl_int **line)
  57 {
  58         struct isl_constraint *constraint;
  59
  60         if (!bmap || !line)
  61                 goto error;
  62
  63         constraint = isl_alloc_type(bmap->ctx, struct isl_constraint);
  64         if (!constraint)
  65                 goto error;
  66
  67         constraint->ctx = bmap->ctx;
  68         isl_ctx_ref(constraint->ctx);
  69         constraint->ref = 1;
  70         constraint->bmap = bmap;
  71         constraint->line = line;
  72
  73         return constraint;
  74 error:
  75         isl_basic_map_free(bmap);
  76         return NULL;
  77 }
  78
  79 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
  80         isl_int **line)
  81 {
  82         return isl_basic_map_constraint((struct isl_basic_map *)bset, line);
  83 }
  84
  85 struct isl_constraint *isl_equality_alloc(struct isl_dim *dim)
  86 {
  87         struct isl_basic_map *bmap;
  88
  89         if (!dim)
  90                 return NULL;
  91
  92         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
  93         if (!bmap)
  94                 return NULL;
  95
  96         isl_basic_map_alloc_equality(bmap);
  97         isl_seq_clr(bmap->eq[0], 1 + isl_basic_map_total_dim(bmap));
  98         return isl_basic_map_constraint(bmap, &bmap->eq[0]);
  99 }
 100
 101 struct isl_constraint *isl_inequality_alloc(struct isl_dim *dim)
 102 {
 103         struct isl_basic_map *bmap;
 104
 105         if (!dim)
 106                 return NULL;
 107
 108         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 1);
 109         if (!bmap)
 110                 return NULL;
 111
 112         isl_basic_map_alloc_inequality(bmap);
 113         isl_seq_clr(bmap->ineq[0], 1 + isl_basic_map_total_dim(bmap));
 114         return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
 115 }
 116
 117 struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
 118 {
 119         struct isl_basic_map *bmap;
 120         int i;
 121         int eq;
 122
 123         if (!c)
 124                 return NULL;
 125
 126         eq = c->line < c->bmap->eq + c->bmap->n_eq;
 127         i = eq ? c->line - c->bmap->eq : c->line - c->bmap->ineq;
 128         bmap = isl_basic_map_copy(c->bmap);
 129         if (!bmap)
 130                 return NULL;
 131         return isl_basic_map_constraint(bmap, eq ? bmap->eq + i : bmap->ineq + i);
 132 }
 133
 134 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
 135 {
 136         if (!c)
 137                 return NULL;
 138
 139         if (c->ref == 1)
 140                 return c;
 141         c->ref--;
 142         return isl_constraint_dup(c);
 143 }
 144
 145 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
 146 {
 147         if (!constraint)
 148                 return NULL;
 149
 150         constraint->ref++;
 151         return constraint;
 152 }
 153
 154 void isl_constraint_free(struct isl_constraint *c)
 155 {
 156         if (!c)
 157                 return;
 158
 159         if (--c->ref > 0)
 160                 return;
 161
 162         isl_basic_map_free(c->bmap);
 163         isl_ctx_deref(c->ctx);
 164         free(c);
 165 }
 166
 167 __isl_give isl_constraint *isl_basic_map_first_constraint(
 168         __isl_take isl_basic_map *bmap)
 169 {
 170         if (!bmap)
 171                 return NULL;
 172
 173         if (bmap->n_eq > 0)
 174                 return isl_basic_map_constraint(bmap, &bmap->eq[0]);
 175
 176         if (bmap->n_ineq > 0)
 177                 return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
 178
 179         isl_basic_map_free(bmap);
 180         return NULL;
 181 }
 182
 183 __isl_give isl_constraint *isl_basic_set_first_constraint(
 184         __isl_take isl_basic_set *bset)
 185 {
 186         return isl_basic_map_first_constraint((struct isl_basic_map *)bset);
 187 }
 188
 189 struct isl_constraint *isl_constraint_next(struct isl_constraint *c)
 190 {
 191         c = isl_constraint_cow(c);
 192         if (c->line >= c->bmap->eq) {
 193                 c->line++;
 194                 if (c->line < c->bmap->eq + c->bmap->n_eq)
 195                         return c;
 196                 c->line = c->bmap->ineq;
 197         } else
 198                 c->line++;
 199         if (c->line < c->bmap->ineq + c->bmap->n_ineq)
 200                 return c;
 201         isl_constraint_free(c);
 202         return NULL;
 203 }
 204
 205 int isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap,
 206         int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
 207 {
 208         int i;
 209         struct isl_constraint *c;
 210
 211         if (!bmap)
 212                 return -1;
 213
 214         isl_assert(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),
 215                         return -1);
 216
 217         for (i = 0; i < bmap->n_eq; ++i) {
 218                 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 219                                                 &bmap->eq[i]);
 220                 if (!c)
 221                         return -1;
 222                 if (fn(c, user) < 0)
 223                         return -1;
 224         }
 225
 226         for (i = 0; i < bmap->n_ineq; ++i) {
 227                 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 228                                                 &bmap->ineq[i]);
 229                 if (!c)
 230                         return -1;
 231                 if (fn(c, user) < 0)
 232                         return -1;
 233         }
 234
 235         return 0;
 236 }
 237
 238 int isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset,
 239         int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
 240 {
 241         return isl_basic_map_foreach_constraint((isl_basic_map *)bset, fn, user);
 242 }
 243
 244 int isl_constraint_is_equal(struct isl_constraint *constraint1,
 245         struct isl_constraint *constraint2)
 246 {
 247         if (!constraint1 || !constraint2)
 248                 return 0;
 249         return constraint1->bmap == constraint2->bmap &&
 250                constraint1->line == constraint2->line;
 251 }
 252
 253 struct isl_basic_map *isl_basic_map_add_constraint(
 254         struct isl_basic_map *bmap, struct isl_constraint *constraint)
 255 {
 256         if (!bmap || !constraint)
 257                 goto error;
 258
 259         isl_assert(constraint->ctx,
 260                 isl_dim_equal(bmap->dim, constraint->bmap->dim), goto error);
 261
 262         bmap = isl_basic_map_intersect(bmap,
 263                                 isl_basic_map_from_constraint(constraint));
 264         return bmap;
 265 error:
 266         isl_basic_map_free(bmap);
 267         isl_constraint_free(constraint);
 268         return NULL;
 269 }
 270
 271 struct isl_basic_set *isl_basic_set_add_constraint(
 272         struct isl_basic_set *bset, struct isl_constraint *constraint)
 273 {
 274         return (struct isl_basic_set *)
 275                 isl_basic_map_add_constraint((struct isl_basic_map *)bset,
 276                                                 constraint);
 277 }
 278
 279 struct isl_constraint *isl_constraint_add_div(struct isl_constraint *constraint,
 280         struct isl_div *div, int *pos)
 281 {
 282         if (!constraint || !div)
 283                 goto error;
 284
 285         isl_assert(constraint->ctx,
 286             isl_dim_equal(div->bmap->dim, constraint->bmap->dim), goto error);
 287         isl_assert(constraint->ctx,
 288             constraint->bmap->n_eq + constraint->bmap->n_ineq == 1, goto error);
 289
 290         constraint->bmap = isl_basic_map_cow(constraint->bmap);
 291         constraint->bmap = isl_basic_map_extend_dim(constraint->bmap,
 292                                 isl_dim_copy(constraint->bmap->dim), 1, 0, 0);
 293         if (!constraint->bmap)
 294                 goto error;
 295         constraint->line = &constraint->bmap->ineq[0];
 296         *pos = isl_basic_map_alloc_div(constraint->bmap);
 297         if (*pos < 0)
 298                 goto error;
 299         isl_seq_cpy(constraint->bmap->div[*pos], div->line[0],
 300                         1 + 1 + isl_basic_map_total_dim(constraint->bmap));
 301         isl_div_free(div);
 302         return constraint;
 303 error:
 304         isl_constraint_free(constraint);
 305         isl_div_free(div);
 306         return NULL;
 307 }
 308
 309 int isl_constraint_dim(struct isl_constraint *constraint,
 310         enum isl_dim_type type)
 311 {
 312         if (!constraint)
 313                 return -1;
 314         return n(constraint, type);
 315 }
 316
 317 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
 318         enum isl_dim_type type, unsigned pos)
 319 {
 320         return constraint ?
 321             isl_basic_map_get_dim_name(constraint->bmap, type, pos) : NULL;
 322 }
 323
 324 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
 325 {
 326         if (!constraint)
 327                 return;
 328         isl_int_set(*v, constraint->line[0][0]);
 329 }
 330
 331 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
 332         enum isl_dim_type type, int pos, isl_int *v)
 333 {
 334         if (!constraint)
 335                 return;
 336
 337         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 338         isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
 339 }
 340
 341 struct isl_div *isl_constraint_div(struct isl_constraint *constraint, int pos)
 342 {
 343         if (!constraint)
 344                 return NULL;
 345
 346         isl_assert(constraint->ctx, pos < n(constraint, isl_dim_div),
 347                         return NULL);
 348         isl_assert(constraint->ctx,
 349                 !isl_int_is_zero(constraint->bmap->div[pos][0]), return NULL);
 350         return isl_basic_map_div(isl_basic_map_copy(constraint->bmap), pos);
 351 }
 352
 353 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
 354 {
 355         if (!constraint)
 356                 return;
 357         isl_int_set(constraint->line[0][0], v);
 358 }
 359
 360 void isl_constraint_set_constant_si(__isl_keep isl_constraint *constraint,
 361         int v)
 362 {
 363         if (!constraint)
 364                 return;
 365         isl_int_set_si(constraint->line[0][0], v);
 366 }
 367
 368 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
 369         enum isl_dim_type type, int pos, isl_int v)
 370 {
 371         if (!constraint)
 372                 return;
 373
 374         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 375         isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
 376 }
 377
 378 void isl_constraint_set_coefficient_si(__isl_keep isl_constraint *constraint,
 379         enum isl_dim_type type, int pos, int v)
 380 {
 381         if (!constraint)
 382                 return;
 383
 384         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 385         isl_int_set_si(constraint->line[0][offset(constraint, type) + pos], v);
 386 }
 387
 388 void isl_constraint_clear(struct isl_constraint *constraint)
 389 {
 390         unsigned total;
 391
 392         if (!constraint)
 393                 return;
 394         total = isl_basic_map_total_dim(constraint->bmap);
 395         isl_seq_clr(constraint->line[0], 1 + total);
 396 }
 397
 398 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
 399 {
 400         unsigned total;
 401
 402         if (!constraint)
 403                 return NULL;
 404
 405         isl_assert(constraint->ctx, !isl_constraint_is_equality(constraint),
 406                         goto error);
 407         isl_assert(constraint->ctx, constraint->bmap->ref == 1, goto error);
 408         total = isl_basic_map_total_dim(constraint->bmap);
 409         isl_seq_neg(constraint->line[0], constraint->line[0], 1 + total);
 410         isl_int_sub_ui(constraint->line[0][0], constraint->line[0][0], 1);
 411         ISL_F_CLR(constraint->bmap, ISL_BASIC_MAP_NORMALIZED);
 412         return constraint;
 413 error:
 414         isl_constraint_free(constraint);
 415         return NULL;
 416 }
 417
 418 int isl_constraint_is_equality(struct isl_constraint *constraint)
 419 {
 420         if (!constraint)
 421                 return -1;
 422         return constraint->line >= constraint->bmap->eq;
 423 }
 424
 425 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
 426 {
 427         int i;
 428
 429         if (!constraint)
 430                 return -1;
 431         if (isl_constraint_is_equality(constraint))
 432                 return 0;
 433         for (i = 0; i < constraint->bmap->n_div; ++i) {
 434                 if (isl_int_is_zero(constraint->bmap->div[i][0]))
 435                         continue;
 436                 if (isl_basic_map_is_div_constraint(constraint->bmap,
 437                                         constraint->line[0], i))
 438                         return 1;
 439         }
 440
 441         return 0;
 442 }
 443
 444 /* We manually set ISL_BASIC_SET_FINAL instead of calling
 445  * isl_basic_map_finalize because we want to keep the position
 446  * of the divs and we therefore do not want to throw away redundant divs.
 447  * This is arguably a bit fragile.
 448  */
 449 __isl_give isl_basic_map *isl_basic_map_from_constraint(
 450         __isl_take isl_constraint *constraint)
 451 {
 452         int k;
 453         struct isl_basic_map *bmap;
 454         isl_int *c;
 455         unsigned total;
 456
 457         if (!constraint)
 458                 return NULL;
 459
 460         if (constraint->bmap->n_eq == 1 && constraint->bmap->n_ineq == 0) {
 461                 bmap = isl_basic_map_copy(constraint->bmap);
 462                 isl_constraint_free(constraint);
 463                 return bmap;
 464         }
 465
 466         bmap = isl_basic_map_universe_like(constraint->bmap);
 467         bmap = isl_basic_map_align_divs(bmap, constraint->bmap);
 468         bmap = isl_basic_map_cow(bmap);
 469         bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
 470         if (isl_constraint_is_equality(constraint)) {
 471                 k = isl_basic_map_alloc_equality(bmap);
 472                 if (k < 0)
 473                         goto error;
 474                 c = bmap->eq[k];
 475         }
 476         else {
 477                 k = isl_basic_map_alloc_inequality(bmap);
 478                 if (k < 0)
 479                         goto error;
 480                 c = bmap->ineq[k];
 481         }
 482         total = isl_basic_map_total_dim(bmap);
 483         isl_seq_cpy(c, constraint->line[0], 1 + total);
 484         isl_constraint_free(constraint);
 485         if (bmap)
 486                 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
 487         return bmap;
 488 error:
 489         isl_constraint_free(constraint);
 490         isl_basic_map_free(bmap);
 491         return NULL;
 492 }
 493
 494 struct isl_basic_set *isl_basic_set_from_constraint(
 495         struct isl_constraint *constraint)
 496 {
 497         if (!constraint)
 498                 return NULL;
 499
 500         isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
 501         return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
 502 error:
 503         isl_constraint_free(constraint);
 504         return NULL;
 505 }
 506
 507 int isl_basic_map_has_defining_equality(
 508         __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
 509         __isl_give isl_constraint **c)
 510 {
 511         int i;
 512         unsigned offset;
 513         unsigned total;
 514
 515         if (!bmap)
 516                 return -1;
 517         offset = basic_map_offset(bmap, type);
 518         total = isl_basic_map_total_dim(bmap);
 519         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
 520         for (i = 0; i < bmap->n_eq; ++i)
 521                 if (!isl_int_is_zero(bmap->eq[i][offset + pos]) &&
 522                     isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
 523                                            1+total-offset-pos-1) == -1) {
 524                         *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 525                                                                 &bmap->eq[i]);
 526                         return 1;
 527                 }
 528         return 0;
 529 }
 530
 531 int isl_basic_set_has_defining_equality(
 532         __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
 533         __isl_give isl_constraint **c)
 534 {
 535         return isl_basic_map_has_defining_equality((isl_basic_map *)bset,
 536                                                     type, pos, c);
 537 }
 538
 539 int isl_basic_set_has_defining_inequalities(
 540         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 541         struct isl_constraint **lower,
 542         struct isl_constraint **upper)
 543 {
 544         int i, j;
 545         unsigned offset;
 546         unsigned total;
 547         isl_int m;
 548         isl_int **lower_line, **upper_line;
 549
 550         if (!bset)
 551                 return -1;
 552         offset = basic_set_offset(bset, type);
 553         total = isl_basic_set_total_dim(bset);
 554         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 555         isl_int_init(m);
 556         for (i = 0; i < bset->n_ineq; ++i) {
 557                 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
 558                         continue;
 559                 if (isl_int_is_one(bset->ineq[i][offset + pos]))
 560                         continue;
 561                 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
 562                         continue;
 563                 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
 564                                                 1+total-offset-pos-1) != -1)
 565                         continue;
 566                 for (j = i + 1; j < bset->n_ineq; ++j) {
 567                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 568                                             total))
 569                                 continue;
 570                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 571                         if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
 572                                 continue;
 573
 574                         if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
 575                                 lower_line = &bset->ineq[i];
 576                                 upper_line = &bset->ineq[j];
 577                         } else {
 578                                 lower_line = &bset->ineq[j];
 579                                 upper_line = &bset->ineq[i];
 580                         }
 581                         *lower = isl_basic_set_constraint(
 582                                         isl_basic_set_copy(bset), lower_line);
 583                         *upper = isl_basic_set_constraint(
 584                                         isl_basic_set_copy(bset), upper_line);
 585                         isl_int_clear(m);
 586                         return 1;
 587                 }
 588         }
 589         *lower = NULL;
 590         *upper = NULL;
 591         isl_int_clear(m);
 592         return 0;
 593 }
 594
 595 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
 596  * (in "a" and "b"), add a constraint to "bset" that ensures that the
 597  * bound implied by "a" is (strictly) larger than the bound implied by "b".
 598  *
 599  * If both constraints imply lower bounds, then this means that "a" is
 600  * active in the result.
 601  * If both constraints imply upper bounds, then this means that "b" is
 602  * active in the result.
 603  */
 604 static __isl_give isl_basic_set *add_larger_bound_constraint(
 605         __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
 606         unsigned abs_pos, int strict)
 607 {
 608         int k;
 609         isl_int t;
 610         unsigned total;
 611
 612         k = isl_basic_set_alloc_inequality(bset);
 613         if (k < 0)
 614                 goto error;
 615
 616         total = isl_basic_set_dim(bset, isl_dim_all);
 617
 618         isl_int_init(t);
 619         isl_int_neg(t, b[1 + abs_pos]);
 620
 621         isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
 622         isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
 623                 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
 624                 total - abs_pos);
 625
 626         if (strict)
 627                 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
 628
 629         isl_int_clear(t);
 630
 631         return bset;
 632 error:
 633         isl_basic_set_free(bset);
 634         return NULL;
 635 }
 636
 637 /* Add constraints to "context" that ensure that "u" is the smallest
 638  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 639  * the resulting basic set.
 640  */
 641 static __isl_give isl_basic_set *set_smallest_upper_bound(
 642         __isl_keep isl_basic_set *context,
 643         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
 644 {
 645         int j;
 646
 647         context = isl_basic_set_copy(context);
 648         context = isl_basic_set_cow(context);
 649
 650         context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
 651
 652         for (j = 0; j < bset->n_ineq; ++j) {
 653                 if (j == u)
 654                         continue;
 655                 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 656                         continue;
 657                 context = add_larger_bound_constraint(context,
 658                         bset->ineq[j], bset->ineq[u], abs_pos, j > u);
 659         }
 660
 661         context = isl_basic_set_simplify(context);
 662         context = isl_basic_set_finalize(context);
 663
 664         return context;
 665 }
 666
 667 /* Add constraints to "context" that ensure that "u" is the largest
 668  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 669  * the resulting basic set.
 670  */
 671 static __isl_give isl_basic_set *set_largest_lower_bound(
 672         __isl_keep isl_basic_set *context,
 673         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
 674 {
 675         int j;
 676
 677         context = isl_basic_set_copy(context);
 678         context = isl_basic_set_cow(context);
 679
 680         context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
 681
 682         for (j = 0; j < bset->n_ineq; ++j) {
 683                 if (j == l)
 684                         continue;
 685                 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
 686                         continue;
 687                 context = add_larger_bound_constraint(context,
 688                         bset->ineq[l], bset->ineq[j], abs_pos, j > l);
 689         }
 690
 691         context = isl_basic_set_simplify(context);
 692         context = isl_basic_set_finalize(context);
 693
 694         return context;
 695 }
 696
 697 static int foreach_upper_bound(__isl_keep isl_basic_set *bset,
 698         enum isl_dim_type type, unsigned abs_pos,
 699         __isl_take isl_basic_set *context, int n_upper,
 700         int (*fn)(__isl_take isl_constraint *lower,
 701                   __isl_take isl_constraint *upper,
 702                   __isl_take isl_basic_set *bset, void *user), void *user)
 703 {
 704         isl_basic_set *context_i;
 705         isl_constraint *upper = NULL;
 706         int i;
 707
 708         for (i = 0; i < bset->n_ineq; ++i) {
 709                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 710                         continue;
 711
 712                 context_i = set_smallest_upper_bound(context, bset,
 713                                                         abs_pos, n_upper, i);
 714                 if (isl_basic_set_is_empty(context_i)) {
 715                         isl_basic_set_free(context_i);
 716                         continue;
 717                 }
 718                 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 719                                                 &bset->ineq[i]);
 720                 if (!upper || !context_i)
 721                         goto error;
 722                 if (fn(NULL, upper, context_i, user) < 0)
 723                         break;
 724         }
 725
 726         isl_basic_set_free(context);
 727
 728         if (i < bset->n_ineq)
 729                 return -1;
 730
 731         return 0;
 732 error:
 733         isl_constraint_free(upper);
 734         isl_basic_set_free(context_i);
 735         isl_basic_set_free(context);
 736         return -1;
 737 }
 738
 739 static int foreach_lower_bound(__isl_keep isl_basic_set *bset,
 740         enum isl_dim_type type, unsigned abs_pos,
 741         __isl_take isl_basic_set *context, int n_lower,
 742         int (*fn)(__isl_take isl_constraint *lower,
 743                   __isl_take isl_constraint *upper,
 744                   __isl_take isl_basic_set *bset, void *user), void *user)
 745 {
 746         isl_basic_set *context_i;
 747         isl_constraint *lower = NULL;
 748         int i;
 749
 750         for (i = 0; i < bset->n_ineq; ++i) {
 751                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 752                         continue;
 753
 754                 context_i = set_largest_lower_bound(context, bset,
 755                                                         abs_pos, n_lower, i);
 756                 if (isl_basic_set_is_empty(context_i)) {
 757                         isl_basic_set_free(context_i);
 758                         continue;
 759                 }
 760                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 761                                                 &bset->ineq[i]);
 762                 if (!lower || !context_i)
 763                         goto error;
 764                 if (fn(lower, NULL, context_i, user) < 0)
 765                         break;
 766         }
 767
 768         isl_basic_set_free(context);
 769
 770         if (i < bset->n_ineq)
 771                 return -1;
 772
 773         return 0;
 774 error:
 775         isl_constraint_free(lower);
 776         isl_basic_set_free(context_i);
 777         isl_basic_set_free(context);
 778         return -1;
 779 }
 780
 781 static int foreach_bound_pair(__isl_keep isl_basic_set *bset,
 782         enum isl_dim_type type, unsigned abs_pos,
 783         __isl_take isl_basic_set *context, int n_lower, int n_upper,
 784         int (*fn)(__isl_take isl_constraint *lower,
 785                   __isl_take isl_constraint *upper,
 786                   __isl_take isl_basic_set *bset, void *user), void *user)
 787 {
 788         isl_basic_set *context_i, *context_j;
 789         isl_constraint *lower = NULL;
 790         isl_constraint *upper = NULL;
 791         int i, j;
 792
 793         for (i = 0; i < bset->n_ineq; ++i) {
 794                 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
 795                         continue;
 796
 797                 context_i = set_largest_lower_bound(context, bset,
 798                                                         abs_pos, n_lower, i);
 799                 if (isl_basic_set_is_empty(context_i)) {
 800                         isl_basic_set_free(context_i);
 801                         continue;
 802                 }
 803
 804                 for (j = 0; j < bset->n_ineq; ++j) {
 805                         if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 806                                 continue;
 807
 808                         context_j = set_smallest_upper_bound(context_i, bset,
 809                                                             abs_pos, n_upper, j);
 810                         context_j = isl_basic_set_extend_constraints(context_j,
 811                                                                         0, 1);
 812                         context_j = add_larger_bound_constraint(context_j,
 813                                 bset->ineq[i], bset->ineq[j], abs_pos, 0);
 814                         context_j = isl_basic_set_simplify(context_j);
 815                         context_j = isl_basic_set_finalize(context_j);
 816                         if (isl_basic_set_is_empty(context_j)) {
 817                                 isl_basic_set_free(context_j);
 818                                 continue;
 819                         }
 820                         lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 821                                                         &bset->ineq[i]);
 822                         upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 823                                                         &bset->ineq[j]);
 824                         if (!lower || !upper || !context_j)
 825                                 goto error;
 826                         if (fn(lower, upper, context_j, user) < 0)
 827                                 break;
 828                 }
 829
 830                 isl_basic_set_free(context_i);
 831
 832                 if (j < bset->n_ineq)
 833                         break;
 834         }
 835
 836         isl_basic_set_free(context);
 837
 838         if (i < bset->n_ineq)
 839                 return -1;
 840
 841         return 0;
 842 error:
 843         isl_constraint_free(lower);
 844         isl_constraint_free(upper);
 845         isl_basic_set_free(context_i);
 846         isl_basic_set_free(context_j);
 847         isl_basic_set_free(context);
 848         return -1;
 849 }
 850
 851 /* For each pair of lower and upper bounds on the variable "pos"
 852  * of type "type", call "fn" with these lower and upper bounds and the
 853  * set of constraints on the remaining variables where these bounds
 854  * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
 855  *
 856  * If the designated variable is equal to an affine combination of the
 857  * other variables then fn is called with both lower and upper
 858  * set to the corresponding equality.
 859  *
 860  * If there is no lower (or upper) bound, then NULL is passed
 861  * as the corresponding bound.
 862  *
 863  * We first check if the variable is involved in any equality.
 864  * If not, we count the number of lower and upper bounds and
 865  * act accordingly.
 866  */
 867 int isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
 868         enum isl_dim_type type, unsigned pos,
 869         int (*fn)(__isl_take isl_constraint *lower,
 870                   __isl_take isl_constraint *upper,
 871                   __isl_take isl_basic_set *bset, void *user), void *user)
 872 {
 873         int i;
 874         isl_constraint *lower = NULL;
 875         isl_constraint *upper = NULL;
 876         isl_basic_set *context = NULL;
 877         unsigned abs_pos;
 878         int n_lower, n_upper;
 879
 880         if (!bset)
 881                 return -1;
 882         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 883         isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
 884                 return -1);
 885
 886         abs_pos = pos;
 887         if (type == isl_dim_set)
 888                 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
 889
 890         for (i = 0; i < bset->n_eq; ++i) {
 891                 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
 892                         continue;
 893
 894                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 895                                                 &bset->eq[i]);
 896                 upper = isl_constraint_copy(lower);
 897                 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
 898                                         type, pos, 1);
 899                 if (!lower || !upper || !context)
 900                         goto error;
 901                 return fn(lower, upper, context, user);
 902         }
 903
 904         n_lower = 0;
 905         n_upper = 0;
 906         for (i = 0; i < bset->n_ineq; ++i) {
 907                 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
 908                         n_lower++;
 909                 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
 910                         n_upper++;
 911         }
 912
 913         context = isl_basic_set_copy(bset);
 914         context = isl_basic_set_cow(context);
 915         if (!context)
 916                 goto error;
 917         for (i = context->n_ineq - 1; i >= 0; --i)
 918                 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
 919                         isl_basic_set_drop_inequality(context, i);
 920
 921         context = isl_basic_set_drop(context, type, pos, 1);
 922         if (!n_lower && !n_upper)
 923                 return fn(NULL, NULL, context, user);
 924         if (!n_lower)
 925                 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
 926                                                 fn, user);
 927         if (!n_upper)
 928                 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
 929                                                 fn, user);
 930         return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
 931                                         fn, user);
 932 error:
 933         isl_constraint_free(lower);
 934         isl_constraint_free(upper);
 935         isl_basic_set_free(context);
 936         return -1;
 937 }