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