isl_constraint.c

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