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_constraint.h>
  14 #include <isl_dim_private.h>
  15 #include "isl_seq.h"
  16 #include "isl_map_private.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 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
 318 {
 319         if (!constraint)
 320                 return;
 321         isl_int_set(*v, constraint->line[0][0]);
 322 }
 323
 324 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
 325         enum isl_dim_type type, int pos, isl_int *v)
 326 {
 327         if (!constraint)
 328                 return;
 329
 330         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 331         isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
 332 }
 333
 334 struct isl_div *isl_constraint_div(struct isl_constraint *constraint, int pos)
 335 {
 336         if (!constraint)
 337                 return NULL;
 338
 339         isl_assert(constraint->ctx, pos < n(constraint, isl_dim_div),
 340                         return NULL);
 341         isl_assert(constraint->ctx,
 342                 !isl_int_is_zero(constraint->bmap->div[pos][0]), return NULL);
 343         return isl_basic_map_div(isl_basic_map_copy(constraint->bmap), pos);
 344 }
 345
 346 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
 347 {
 348         if (!constraint)
 349                 return;
 350         isl_int_set(constraint->line[0][0], v);
 351 }
 352
 353 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
 354         enum isl_dim_type type, int pos, isl_int v)
 355 {
 356         if (!constraint)
 357                 return;
 358
 359         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 360         isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
 361 }
 362
 363 void isl_constraint_clear(struct isl_constraint *constraint)
 364 {
 365         unsigned total;
 366
 367         if (!constraint)
 368                 return;
 369         total = isl_basic_map_total_dim(constraint->bmap);
 370         isl_seq_clr(constraint->line[0], 1 + total);
 371 }
 372
 373 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
 374 {
 375         unsigned total;
 376
 377         if (!constraint)
 378                 return NULL;
 379
 380         isl_assert(constraint->ctx, !isl_constraint_is_equality(constraint),
 381                         goto error);
 382         isl_assert(constraint->ctx, constraint->bmap->ref == 1, goto error);
 383         total = isl_basic_map_total_dim(constraint->bmap);
 384         isl_seq_neg(constraint->line[0], constraint->line[0], 1 + total);
 385         isl_int_sub_ui(constraint->line[0][0], constraint->line[0][0], 1);
 386         ISL_F_CLR(constraint->bmap, ISL_BASIC_MAP_NORMALIZED);
 387         return constraint;
 388 error:
 389         isl_constraint_free(constraint);
 390         return NULL;
 391 }
 392
 393 int isl_constraint_is_equality(struct isl_constraint *constraint)
 394 {
 395         if (!constraint)
 396                 return -1;
 397         return constraint->line >= constraint->bmap->eq;
 398 }
 399
 400 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
 401 {
 402         int i;
 403
 404         if (!constraint)
 405                 return -1;
 406         if (isl_constraint_is_equality(constraint))
 407                 return 0;
 408         for (i = 0; i < constraint->bmap->n_div; ++i) {
 409                 if (isl_int_is_zero(constraint->bmap->div[i][0]))
 410                         continue;
 411                 if (isl_basic_map_is_div_constraint(constraint->bmap,
 412                                         constraint->line[0], i))
 413                         return 1;
 414         }
 415
 416         return 0;
 417 }
 418
 419 /* We manually set ISL_BASIC_SET_FINAL instead of calling
 420  * isl_basic_map_finalize because we want to keep the position
 421  * of the divs and we therefore do not want to throw away redundant divs.
 422  * This is arguably a bit fragile.
 423  */
 424 __isl_give isl_basic_map *isl_basic_map_from_constraint(
 425         __isl_take isl_constraint *constraint)
 426 {
 427         int k;
 428         struct isl_basic_map *bmap;
 429         isl_int *c;
 430         unsigned total;
 431
 432         if (!constraint)
 433                 return NULL;
 434
 435         if (constraint->bmap->n_eq == 1 && constraint->bmap->n_ineq == 0) {
 436                 bmap = isl_basic_map_copy(constraint->bmap);
 437                 isl_constraint_free(constraint);
 438                 return bmap;
 439         }
 440
 441         bmap = isl_basic_map_universe_like(constraint->bmap);
 442         bmap = isl_basic_map_align_divs(bmap, constraint->bmap);
 443         bmap = isl_basic_map_cow(bmap);
 444         bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
 445         if (isl_constraint_is_equality(constraint)) {
 446                 k = isl_basic_map_alloc_equality(bmap);
 447                 if (k < 0)
 448                         goto error;
 449                 c = bmap->eq[k];
 450         }
 451         else {
 452                 k = isl_basic_map_alloc_inequality(bmap);
 453                 if (k < 0)
 454                         goto error;
 455                 c = bmap->ineq[k];
 456         }
 457         total = isl_basic_map_total_dim(bmap);
 458         isl_seq_cpy(c, constraint->line[0], 1 + total);
 459         isl_constraint_free(constraint);
 460         if (bmap)
 461                 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
 462         return bmap;
 463 error:
 464         isl_constraint_free(constraint);
 465         isl_basic_map_free(bmap);
 466         return NULL;
 467 }
 468
 469 struct isl_basic_set *isl_basic_set_from_constraint(
 470         struct isl_constraint *constraint)
 471 {
 472         if (!constraint)
 473                 return NULL;
 474
 475         isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
 476         return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
 477 error:
 478         isl_constraint_free(constraint);
 479         return NULL;
 480 }
 481
 482 int isl_basic_map_has_defining_equality(
 483         __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
 484         __isl_give isl_constraint **c)
 485 {
 486         int i;
 487         unsigned offset;
 488         unsigned total;
 489
 490         if (!bmap)
 491                 return -1;
 492         offset = basic_map_offset(bmap, type);
 493         total = isl_basic_map_total_dim(bmap);
 494         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
 495         for (i = 0; i < bmap->n_eq; ++i)
 496                 if (!isl_int_is_zero(bmap->eq[i][offset + pos]) &&
 497                     isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
 498                                            1+total-offset-pos-1) == -1) {
 499                         *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 500                                                                 &bmap->eq[i]);
 501                         return 1;
 502                 }
 503         return 0;
 504 }
 505
 506 int isl_basic_set_has_defining_equality(
 507         __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
 508         __isl_give isl_constraint **c)
 509 {
 510         return isl_basic_map_has_defining_equality((isl_basic_map *)bset,
 511                                                     type, pos, c);
 512 }
 513
 514 int isl_basic_set_has_defining_inequalities(
 515         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 516         struct isl_constraint **lower,
 517         struct isl_constraint **upper)
 518 {
 519         int i, j;
 520         unsigned offset;
 521         unsigned total;
 522         isl_int m;
 523         isl_int **lower_line, **upper_line;
 524
 525         if (!bset)
 526                 return -1;
 527         offset = basic_set_offset(bset, type);
 528         total = isl_basic_set_total_dim(bset);
 529         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 530         isl_int_init(m);
 531         for (i = 0; i < bset->n_ineq; ++i) {
 532                 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
 533                         continue;
 534                 if (isl_int_is_one(bset->ineq[i][offset + pos]))
 535                         continue;
 536                 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
 537                         continue;
 538                 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
 539                                                 1+total-offset-pos-1) != -1)
 540                         continue;
 541                 for (j = i + 1; j < bset->n_ineq; ++j) {
 542                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 543                                             total))
 544                                 continue;
 545                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 546                         if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
 547                                 continue;
 548
 549                         if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
 550                                 lower_line = &bset->ineq[i];
 551                                 upper_line = &bset->ineq[j];
 552                         } else {
 553                                 lower_line = &bset->ineq[j];
 554                                 upper_line = &bset->ineq[i];
 555                         }
 556                         *lower = isl_basic_set_constraint(
 557                                         isl_basic_set_copy(bset), lower_line);
 558                         *upper = isl_basic_set_constraint(
 559                                         isl_basic_set_copy(bset), upper_line);
 560                         isl_int_clear(m);
 561                         return 1;
 562                 }
 563         }
 564         *lower = NULL;
 565         *upper = NULL;
 566         isl_int_clear(m);
 567         return 0;
 568 }
 569
 570 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
 571  * (in "a" and "b"), add a constraint to "bset" that ensures that the
 572  * bound implied by "a" is (strictly) larger than the bound implied by "b".
 573  *
 574  * If both constraints imply lower bounds, then this means that "a" is
 575  * active in the result.
 576  * If both constraints imply upper bounds, then this means that "b" is
 577  * active in the result.
 578  */
 579 static __isl_give isl_basic_set *add_larger_bound_constraint(
 580         __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
 581         unsigned abs_pos, int strict)
 582 {
 583         int k;
 584         isl_int t;
 585         unsigned total;
 586
 587         k = isl_basic_set_alloc_inequality(bset);
 588         if (k < 0)
 589                 goto error;
 590
 591         total = isl_basic_set_dim(bset, isl_dim_all);
 592
 593         isl_int_init(t);
 594         isl_int_neg(t, b[1 + abs_pos]);
 595
 596         isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
 597         isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
 598                 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
 599                 total - abs_pos);
 600
 601         if (strict)
 602                 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
 603
 604         isl_int_clear(t);
 605
 606         return bset;
 607 error:
 608         isl_basic_set_free(bset);
 609         return NULL;
 610 }
 611
 612 /* Add constraints to "context" that ensure that "u" is the smallest
 613  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 614  * the resulting basic set.
 615  */
 616 static __isl_give isl_basic_set *set_smallest_upper_bound(
 617         __isl_keep isl_basic_set *context,
 618         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
 619 {
 620         int j;
 621
 622         context = isl_basic_set_copy(context);
 623         context = isl_basic_set_cow(context);
 624
 625         context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
 626
 627         for (j = 0; j < bset->n_ineq; ++j) {
 628                 if (j == u)
 629                         continue;
 630                 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 631                         continue;
 632                 context = add_larger_bound_constraint(context,
 633                         bset->ineq[j], bset->ineq[u], abs_pos, j > u);
 634         }
 635
 636         context = isl_basic_set_simplify(context);
 637         context = isl_basic_set_finalize(context);
 638
 639         return context;
 640 }
 641
 642 /* Add constraints to "context" that ensure that "u" is the largest
 643  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 644  * the resulting basic set.
 645  */
 646 static __isl_give isl_basic_set *set_largest_lower_bound(
 647         __isl_keep isl_basic_set *context,
 648         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
 649 {
 650         int j;
 651
 652         context = isl_basic_set_copy(context);
 653         context = isl_basic_set_cow(context);
 654
 655         context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
 656
 657         for (j = 0; j < bset->n_ineq; ++j) {
 658                 if (j == l)
 659                         continue;
 660                 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
 661                         continue;
 662                 context = add_larger_bound_constraint(context,
 663                         bset->ineq[l], bset->ineq[j], abs_pos, j > l);
 664         }
 665
 666         context = isl_basic_set_simplify(context);
 667         context = isl_basic_set_finalize(context);
 668
 669         return context;
 670 }
 671
 672 static int foreach_upper_bound(__isl_keep isl_basic_set *bset,
 673         enum isl_dim_type type, unsigned abs_pos,
 674         __isl_take isl_basic_set *context, int n_upper,
 675         int (*fn)(__isl_take isl_constraint *lower,
 676                   __isl_take isl_constraint *upper,
 677                   __isl_take isl_basic_set *bset, void *user), void *user)
 678 {
 679         isl_basic_set *context_i;
 680         isl_constraint *upper = NULL;
 681         int i;
 682
 683         for (i = 0; i < bset->n_ineq; ++i) {
 684                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 685                         continue;
 686
 687                 context_i = set_smallest_upper_bound(context, bset,
 688                                                         abs_pos, n_upper, i);
 689                 if (isl_basic_set_is_empty(context_i)) {
 690                         isl_basic_set_free(context_i);
 691                         continue;
 692                 }
 693                 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 694                                                 &bset->ineq[i]);
 695                 if (!upper || !context_i)
 696                         goto error;
 697                 if (fn(NULL, upper, context_i, user) < 0)
 698                         break;
 699         }
 700
 701         isl_basic_set_free(context);
 702
 703         if (i < bset->n_ineq)
 704                 return -1;
 705
 706         return 0;
 707 error:
 708         isl_constraint_free(upper);
 709         isl_basic_set_free(context_i);
 710         isl_basic_set_free(context);
 711         return -1;
 712 }
 713
 714 static int foreach_lower_bound(__isl_keep isl_basic_set *bset,
 715         enum isl_dim_type type, unsigned abs_pos,
 716         __isl_take isl_basic_set *context, int n_lower,
 717         int (*fn)(__isl_take isl_constraint *lower,
 718                   __isl_take isl_constraint *upper,
 719                   __isl_take isl_basic_set *bset, void *user), void *user)
 720 {
 721         isl_basic_set *context_i;
 722         isl_constraint *lower = NULL;
 723         int i;
 724
 725         for (i = 0; i < bset->n_ineq; ++i) {
 726                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 727                         continue;
 728
 729                 context_i = set_largest_lower_bound(context, bset,
 730                                                         abs_pos, n_lower, i);
 731                 if (isl_basic_set_is_empty(context_i)) {
 732                         isl_basic_set_free(context_i);
 733                         continue;
 734                 }
 735                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 736                                                 &bset->ineq[i]);
 737                 if (!lower || !context_i)
 738                         goto error;
 739                 if (fn(lower, NULL, context_i, user) < 0)
 740                         break;
 741         }
 742
 743         isl_basic_set_free(context);
 744
 745         if (i < bset->n_ineq)
 746                 return -1;
 747
 748         return 0;
 749 error:
 750         isl_constraint_free(lower);
 751         isl_basic_set_free(context_i);
 752         isl_basic_set_free(context);
 753         return -1;
 754 }
 755
 756 static int foreach_bound_pair(__isl_keep isl_basic_set *bset,
 757         enum isl_dim_type type, unsigned abs_pos,
 758         __isl_take isl_basic_set *context, int n_lower, int n_upper,
 759         int (*fn)(__isl_take isl_constraint *lower,
 760                   __isl_take isl_constraint *upper,
 761                   __isl_take isl_basic_set *bset, void *user), void *user)
 762 {
 763         isl_basic_set *context_i, *context_j;
 764         isl_constraint *lower = NULL;
 765         isl_constraint *upper = NULL;
 766         int i, j;
 767
 768         for (i = 0; i < bset->n_ineq; ++i) {
 769                 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
 770                         continue;
 771
 772                 context_i = set_largest_lower_bound(context, bset,
 773                                                         abs_pos, n_lower, i);
 774                 if (isl_basic_set_is_empty(context_i)) {
 775                         isl_basic_set_free(context_i);
 776                         continue;
 777                 }
 778
 779                 for (j = 0; j < bset->n_ineq; ++j) {
 780                         if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 781                                 continue;
 782
 783                         context_j = set_smallest_upper_bound(context_i, bset,
 784                                                             abs_pos, n_upper, j);
 785                         context_j = isl_basic_set_extend_constraints(context_j,
 786                                                                         0, 1);
 787                         context_j = add_larger_bound_constraint(context_j,
 788                                 bset->ineq[i], bset->ineq[j], abs_pos, 0);
 789                         context_j = isl_basic_set_simplify(context_j);
 790                         context_j = isl_basic_set_finalize(context_j);
 791                         if (isl_basic_set_is_empty(context_j)) {
 792                                 isl_basic_set_free(context_j);
 793                                 continue;
 794                         }
 795                         lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 796                                                         &bset->ineq[i]);
 797                         upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 798                                                         &bset->ineq[j]);
 799                         if (!lower || !upper || !context_j)
 800                                 goto error;
 801                         if (fn(lower, upper, context_j, user) < 0)
 802                                 break;
 803                 }
 804
 805                 isl_basic_set_free(context_i);
 806
 807                 if (j < bset->n_ineq)
 808                         break;
 809         }
 810
 811         isl_basic_set_free(context);
 812
 813         if (i < bset->n_ineq)
 814                 return -1;
 815
 816         return 0;
 817 error:
 818         isl_constraint_free(lower);
 819         isl_constraint_free(upper);
 820         isl_basic_set_free(context_i);
 821         isl_basic_set_free(context_j);
 822         isl_basic_set_free(context);
 823         return -1;
 824 }
 825
 826 /* For each pair of lower and upper bounds on the variable "pos"
 827  * of type "type", call "fn" with these lower and upper bounds and the
 828  * set of constraints on the remaining variables where these bounds
 829  * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
 830  *
 831  * If the designated variable is equal to an affine combination of the
 832  * other variables then fn is called with both lower and upper
 833  * set to the corresponding equality.
 834  *
 835  * If there is no lower (or upper) bound, then NULL is passed
 836  * as the corresponding bound.
 837  *
 838  * We first check if the variable is involved in any equality.
 839  * If not, we count the number of lower and upper bounds and
 840  * act accordingly.
 841  */
 842 int isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
 843         enum isl_dim_type type, unsigned pos,
 844         int (*fn)(__isl_take isl_constraint *lower,
 845                   __isl_take isl_constraint *upper,
 846                   __isl_take isl_basic_set *bset, void *user), void *user)
 847 {
 848         int i;
 849         isl_constraint *lower = NULL;
 850         isl_constraint *upper = NULL;
 851         isl_basic_set *context = NULL;
 852         unsigned abs_pos;
 853         int n_lower, n_upper;
 854
 855         if (!bset)
 856                 return -1;
 857         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 858         isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
 859                 return -1);
 860
 861         abs_pos = pos;
 862         if (type == isl_dim_set)
 863                 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
 864
 865         for (i = 0; i < bset->n_eq; ++i) {
 866                 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
 867                         continue;
 868
 869                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 870                                                 &bset->eq[i]);
 871                 upper = isl_constraint_copy(lower);
 872                 context = isl_basic_set_remove(isl_basic_set_copy(bset),
 873                                         type, pos, 1);
 874                 if (!lower || !upper || !context)
 875                         goto error;
 876                 return fn(lower, upper, context, user);
 877         }
 878
 879         n_lower = 0;
 880         n_upper = 0;
 881         for (i = 0; i < bset->n_ineq; ++i) {
 882                 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
 883                         n_lower++;
 884                 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
 885                         n_upper++;
 886         }
 887
 888         context = isl_basic_set_copy(bset);
 889         context = isl_basic_set_cow(context);
 890         if (!context)
 891                 goto error;
 892         for (i = context->n_ineq - 1; i >= 0; --i)
 893                 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
 894                         isl_basic_set_drop_inequality(context, i);
 895
 896         context = isl_basic_set_drop(context, type, pos, 1);
 897         if (!n_lower && !n_upper)
 898                 return fn(NULL, NULL, context, user);
 899         if (!n_lower)
 900                 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
 901                                                 fn, user);
 902         if (!n_upper)
 903                 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
 904                                                 fn, user);
 905         return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
 906                                         fn, user);
 907 error:
 908         isl_constraint_free(lower);
 909         isl_constraint_free(upper);
 910         isl_basic_set_free(context);
 911         return -1;
 912 }