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