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