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