isl_constraint.c

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