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