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