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_private.h>
  15 #include <isl_space_private.h>
  16 #include <isl/seq.h>
  17 #include <isl_aff_private.h>
  18 #include <isl_local_space_private.h>
  19
  20 isl_ctx *isl_constraint_get_ctx(__isl_keep isl_constraint *c)
  21 {
  22         return c ? isl_local_space_get_ctx(c->ls) : NULL;
  23 }
  24
  25 static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
  26 {
  27         return isl_local_space_dim(c->ls, type);
  28 }
  29
  30 static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
  31 {
  32         return isl_local_space_offset(c->ls, type);
  33 }
  34
  35 static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
  36                                                         enum isl_dim_type type)
  37 {
  38         return type == isl_dim_div ? 1 + isl_space_dim(bmap->dim, isl_dim_all)
  39                                    : 1 + isl_space_offset(bmap->dim, type);
  40 }
  41
  42 static unsigned basic_set_offset(struct isl_basic_set *bset,
  43                                                         enum isl_dim_type type)
  44 {
  45         isl_space *dim = bset->dim;
  46         switch (type) {
  47         case isl_dim_param:     return 1;
  48         case isl_dim_in:        return 1 + dim->nparam;
  49         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  50         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
  51         default:                return 0;
  52         }
  53 }
  54
  55 __isl_give isl_constraint *isl_constraint_alloc_vec(int eq,
  56         __isl_take isl_local_space *ls, __isl_take isl_vec *v)
  57 {
  58         isl_constraint *constraint;
  59
  60         if (!ls || !v)
  61                 goto error;
  62
  63         constraint = isl_alloc_type(isl_vec_get_ctx(v), isl_constraint);
  64         if (!constraint)
  65                 goto error;
  66
  67         constraint->ref = 1;
  68         constraint->eq = eq;
  69         constraint->ls = ls;
  70         constraint->v = v;
  71
  72         return constraint;
  73 error:
  74         isl_local_space_free(ls);
  75         isl_vec_free(v);
  76         return NULL;
  77 }
  78
  79 __isl_give isl_constraint *isl_constraint_alloc(int eq,
  80         __isl_take isl_local_space *ls)
  81 {
  82         isl_ctx *ctx;
  83         isl_vec *v;
  84
  85         if (!ls)
  86                 return NULL;
  87
  88         ctx = isl_local_space_get_ctx(ls);
  89         v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
  90         v = isl_vec_clr(v);
  91         return isl_constraint_alloc_vec(eq, ls, v);
  92 }
  93
  94 struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
  95         isl_int **line)
  96 {
  97         int eq;
  98         isl_ctx *ctx;
  99         isl_vec *v;
 100         isl_local_space *ls = NULL;
 101         isl_constraint *constraint;
 102
 103         if (!bmap || !line)
 104                 goto error;
 105
 106         eq = line >= bmap->eq;
 107
 108         ctx = isl_basic_map_get_ctx(bmap);
 109         ls = isl_basic_map_get_local_space(bmap);
 110         v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
 111         if (!v)
 112                 goto error;
 113         isl_seq_cpy(v->el, line[0], v->size);
 114         constraint = isl_constraint_alloc_vec(eq, ls, v);
 115
 116         isl_basic_map_free(bmap);
 117         return constraint;
 118 error:
 119         isl_local_space_free(ls);
 120         isl_basic_map_free(bmap);
 121         return NULL;
 122 }
 123
 124 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
 125         isl_int **line)
 126 {
 127         return isl_basic_map_constraint((struct isl_basic_map *)bset, line);
 128 }
 129
 130 __isl_give isl_constraint *isl_equality_alloc(__isl_take isl_local_space *ls)
 131 {
 132         return isl_constraint_alloc(1, ls);
 133 }
 134
 135 __isl_give isl_constraint *isl_inequality_alloc(__isl_take isl_local_space *ls)
 136 {
 137         return isl_constraint_alloc(0, ls);
 138 }
 139
 140 struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
 141 {
 142         if (!c)
 143                 return NULL;
 144
 145         return isl_constraint_alloc_vec(c->eq, isl_local_space_copy(c->ls),
 146                                                 isl_vec_copy(c->v));
 147 }
 148
 149 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
 150 {
 151         if (!c)
 152                 return NULL;
 153
 154         if (c->ref == 1)
 155                 return c;
 156         c->ref--;
 157         return isl_constraint_dup(c);
 158 }
 159
 160 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
 161 {
 162         if (!constraint)
 163                 return NULL;
 164
 165         constraint->ref++;
 166         return constraint;
 167 }
 168
 169 void *isl_constraint_free(struct isl_constraint *c)
 170 {
 171         if (!c)
 172                 return NULL;
 173
 174         if (--c->ref > 0)
 175                 return NULL;
 176
 177         isl_local_space_free(c->ls);
 178         isl_vec_free(c->v);
 179         free(c);
 180
 181         return NULL;
 182 }
 183
 184 /* Return the number of constraints in "bset", i.e., the
 185  * number of times isl_basic_set_foreach_constraint will
 186  * call the callback.
 187  */
 188 int isl_basic_set_n_constraint(__isl_keep isl_basic_set *bset)
 189 {
 190         if (!bset)
 191                 return -1;
 192
 193         return bset->n_eq + bset->n_ineq;
 194 }
 195
 196 int isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap,
 197         int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
 198 {
 199         int i;
 200         struct isl_constraint *c;
 201
 202         if (!bmap)
 203                 return -1;
 204
 205         isl_assert(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),
 206                         return -1);
 207
 208         for (i = 0; i < bmap->n_eq; ++i) {
 209                 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 210                                                 &bmap->eq[i]);
 211                 if (!c)
 212                         return -1;
 213                 if (fn(c, user) < 0)
 214                         return -1;
 215         }
 216
 217         for (i = 0; i < bmap->n_ineq; ++i) {
 218                 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 219                                                 &bmap->ineq[i]);
 220                 if (!c)
 221                         return -1;
 222                 if (fn(c, user) < 0)
 223                         return -1;
 224         }
 225
 226         return 0;
 227 }
 228
 229 int isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset,
 230         int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
 231 {
 232         return isl_basic_map_foreach_constraint((isl_basic_map *)bset, fn, user);
 233 }
 234
 235 int isl_constraint_is_equal(struct isl_constraint *constraint1,
 236         struct isl_constraint *constraint2)
 237 {
 238         int equal;
 239
 240         if (!constraint1 || !constraint2)
 241                 return 0;
 242         if (constraint1->eq != constraint2->eq)
 243                 return 0;
 244         equal = isl_local_space_is_equal(constraint1->ls, constraint2->ls);
 245         if (equal < 0 || !equal)
 246                 return equal;
 247         return isl_vec_is_equal(constraint1->v, constraint2->v);
 248 }
 249
 250 struct isl_basic_map *isl_basic_map_add_constraint(
 251         struct isl_basic_map *bmap, struct isl_constraint *constraint)
 252 {
 253         isl_ctx *ctx;
 254         isl_space *dim;
 255         int equal_space;
 256
 257         if (!bmap || !constraint)
 258                 goto error;
 259
 260         ctx = isl_constraint_get_ctx(constraint);
 261         dim = isl_constraint_get_space(constraint);
 262         equal_space = isl_space_is_equal(bmap->dim, dim);
 263         isl_space_free(dim);
 264         isl_assert(ctx, equal_space, goto error);
 265
 266         bmap = isl_basic_map_intersect(bmap,
 267                                 isl_basic_map_from_constraint(constraint));
 268         return bmap;
 269 error:
 270         isl_basic_map_free(bmap);
 271         isl_constraint_free(constraint);
 272         return NULL;
 273 }
 274
 275 struct isl_basic_set *isl_basic_set_add_constraint(
 276         struct isl_basic_set *bset, struct isl_constraint *constraint)
 277 {
 278         return (struct isl_basic_set *)
 279                 isl_basic_map_add_constraint((struct isl_basic_map *)bset,
 280                                                 constraint);
 281 }
 282
 283 __isl_give isl_map *isl_map_add_constraint(__isl_take isl_map *map,
 284         __isl_take isl_constraint *constraint)
 285 {
 286         isl_basic_map *bmap;
 287
 288         bmap = isl_basic_map_from_constraint(constraint);
 289         map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
 290
 291         return map;
 292 }
 293
 294 __isl_give isl_set *isl_set_add_constraint(__isl_take isl_set *set,
 295         __isl_take isl_constraint *constraint)
 296 {
 297         return isl_map_add_constraint(set, constraint);
 298 }
 299
 300 __isl_give isl_space *isl_constraint_get_space(
 301         __isl_keep isl_constraint *constraint)
 302 {
 303         return constraint ? isl_local_space_get_space(constraint->ls) : NULL;
 304 }
 305
 306 int isl_constraint_dim(struct isl_constraint *constraint,
 307         enum isl_dim_type type)
 308 {
 309         if (!constraint)
 310                 return -1;
 311         return n(constraint, type);
 312 }
 313
 314 int isl_constraint_involves_dims(__isl_keep isl_constraint *constraint,
 315         enum isl_dim_type type, unsigned first, unsigned n)
 316 {
 317         int i;
 318         isl_ctx *ctx;
 319         int *active = NULL;
 320         int involves = 0;
 321
 322         if (!constraint)
 323                 return -1;
 324         if (n == 0)
 325                 return 0;
 326
 327         ctx = isl_constraint_get_ctx(constraint);
 328         if (first + n > isl_constraint_dim(constraint, type))
 329                 isl_die(ctx, isl_error_invalid,
 330                         "range out of bounds", return -1);
 331
 332         active = isl_local_space_get_active(constraint->ls,
 333                                             constraint->v->el + 1);
 334         if (!active)
 335                 goto error;
 336
 337         first += isl_local_space_offset(constraint->ls, type) - 1;
 338         for (i = 0; i < n; ++i)
 339                 if (active[first + i]) {
 340                         involves = 1;
 341                         break;
 342                 }
 343
 344         free(active);
 345
 346         return involves;
 347 error:
 348         free(active);
 349         return -1;
 350 }
 351
 352 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
 353         enum isl_dim_type type, unsigned pos)
 354 {
 355         return constraint ?
 356             isl_local_space_get_dim_name(constraint->ls, type, pos) : NULL;
 357 }
 358
 359 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
 360 {
 361         if (!constraint)
 362                 return;
 363         isl_int_set(*v, constraint->v->el[0]);
 364 }
 365
 366 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
 367         enum isl_dim_type type, int pos, isl_int *v)
 368 {
 369         if (!constraint)
 370                 return;
 371
 372         if (pos >= isl_local_space_dim(constraint->ls, type))
 373                 isl_die(constraint->v->ctx, isl_error_invalid,
 374                         "position out of bounds", return);
 375
 376         pos += isl_local_space_offset(constraint->ls, type);
 377         isl_int_set(*v, constraint->v->el[pos]);
 378 }
 379
 380 __isl_give isl_aff *isl_constraint_get_div(__isl_keep isl_constraint *constraint,
 381         int pos)
 382 {
 383         if (!constraint)
 384                 return NULL;
 385
 386         return isl_local_space_get_div(constraint->ls, pos);
 387 }
 388
 389 __isl_give isl_constraint *isl_constraint_set_constant(
 390         __isl_take isl_constraint *constraint, isl_int v)
 391 {
 392         constraint = isl_constraint_cow(constraint);
 393         if (!constraint)
 394                 return NULL;
 395
 396         constraint->v = isl_vec_cow(constraint->v);
 397         if (!constraint->v)
 398                 return isl_constraint_free(constraint);
 399
 400         isl_int_set(constraint->v->el[0], v);
 401         return constraint;
 402 }
 403
 404 __isl_give isl_constraint *isl_constraint_set_constant_si(
 405         __isl_take isl_constraint *constraint, int v)
 406 {
 407         constraint = isl_constraint_cow(constraint);
 408         if (!constraint)
 409                 return NULL;
 410
 411         constraint->v = isl_vec_cow(constraint->v);
 412         if (!constraint->v)
 413                 return isl_constraint_free(constraint);
 414
 415         isl_int_set_si(constraint->v->el[0], v);
 416         return constraint;
 417 }
 418
 419 __isl_give isl_constraint *isl_constraint_set_coefficient(
 420         __isl_take isl_constraint *constraint,
 421         enum isl_dim_type type, int pos, isl_int v)
 422 {
 423         constraint = isl_constraint_cow(constraint);
 424         if (!constraint)
 425                 return NULL;
 426
 427         if (pos >= isl_local_space_dim(constraint->ls, type))
 428                 isl_die(constraint->v->ctx, isl_error_invalid,
 429                         "position out of bounds",
 430                         return isl_constraint_free(constraint));
 431
 432         constraint = isl_constraint_cow(constraint);
 433         if (!constraint)
 434                 return NULL;
 435
 436         constraint->v = isl_vec_cow(constraint->v);
 437         if (!constraint->v)
 438                 return isl_constraint_free(constraint);
 439
 440         pos += isl_local_space_offset(constraint->ls, type);
 441         isl_int_set(constraint->v->el[pos], v);
 442
 443         return constraint;
 444 }
 445
 446 __isl_give isl_constraint *isl_constraint_set_coefficient_si(
 447         __isl_take isl_constraint *constraint,
 448         enum isl_dim_type type, int pos, int v)
 449 {
 450         constraint = isl_constraint_cow(constraint);
 451         if (!constraint)
 452                 return NULL;
 453
 454         if (pos >= isl_local_space_dim(constraint->ls, type))
 455                 isl_die(constraint->v->ctx, isl_error_invalid,
 456                         "position out of bounds",
 457                         return isl_constraint_free(constraint));
 458
 459         constraint = isl_constraint_cow(constraint);
 460         if (!constraint)
 461                 return NULL;
 462
 463         constraint->v = isl_vec_cow(constraint->v);
 464         if (!constraint->v)
 465                 return isl_constraint_free(constraint);
 466
 467         pos += isl_local_space_offset(constraint->ls, type);
 468         isl_int_set_si(constraint->v->el[pos], v);
 469
 470         return constraint;
 471 }
 472
 473 /* Drop any constraint from "bset" that is identical to "constraint".
 474  * In particular, this means that the local spaces of "bset" and
 475  * "constraint" need to be the same.
 476  *
 477  * Since the given constraint may actually be a pointer into the bset,
 478  * we have to be careful not to reorder the constraints as the user
 479  * may be holding on to other constraints from the same bset.
 480  * This should be cleaned up when the internal representation of
 481  * isl_constraint is changed to use isl_aff.
 482  */
 483 __isl_give isl_basic_set *isl_basic_set_drop_constraint(
 484         __isl_take isl_basic_set *bset, __isl_take isl_constraint *constraint)
 485 {
 486         int i;
 487         unsigned n;
 488         isl_int **row;
 489         unsigned total;
 490         isl_local_space *ls1;
 491         int equal;
 492
 493         if (!bset || !constraint)
 494                 goto error;
 495
 496         ls1 = isl_basic_set_get_local_space(bset);
 497         equal = isl_local_space_is_equal(ls1, constraint->ls);
 498         isl_local_space_free(ls1);
 499         if (equal < 0)
 500                 goto error;
 501         if (!equal) {
 502                 isl_constraint_free(constraint);
 503                 return bset;
 504         }
 505
 506         if (isl_constraint_is_equality(constraint)) {
 507                 n = bset->n_eq;
 508                 row = bset->eq;
 509         } else {
 510                 n = bset->n_ineq;
 511                 row = bset->ineq;
 512         }
 513
 514         total = isl_constraint_dim(constraint, isl_dim_all);
 515         for (i = 0; i < n; ++i)
 516                 if (isl_seq_eq(row[i], constraint->v->el, 1 + total))
 517                         isl_seq_clr(row[i], 1 + total);
 518
 519         isl_constraint_free(constraint);
 520         return bset;
 521 error:
 522         isl_constraint_free(constraint);
 523         isl_basic_set_free(bset);
 524         return NULL;
 525 }
 526
 527 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
 528 {
 529         isl_ctx *ctx;
 530
 531         constraint = isl_constraint_cow(constraint);
 532         if (!constraint)
 533                 return NULL;
 534
 535         ctx = isl_constraint_get_ctx(constraint);
 536         if (isl_constraint_is_equality(constraint))
 537                 isl_die(ctx, isl_error_invalid, "cannot negate equality",
 538                         return isl_constraint_free(constraint));
 539         constraint->v = isl_vec_neg(constraint->v);
 540         constraint->v = isl_vec_cow(constraint->v);
 541         if (!constraint->v)
 542                 return isl_constraint_free(constraint);
 543         isl_int_sub_ui(constraint->v->el[0], constraint->v->el[0], 1);
 544         return constraint;
 545 }
 546
 547 int isl_constraint_is_equality(struct isl_constraint *constraint)
 548 {
 549         if (!constraint)
 550                 return -1;
 551         return constraint->eq;
 552 }
 553
 554 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
 555 {
 556         int i;
 557         int n_div;
 558
 559         if (!constraint)
 560                 return -1;
 561         if (isl_constraint_is_equality(constraint))
 562                 return 0;
 563         n_div = isl_constraint_dim(constraint, isl_dim_div);
 564         for (i = 0; i < n_div; ++i) {
 565                 if (isl_local_space_is_div_constraint(constraint->ls,
 566                                                         constraint->v->el, i))
 567                         return 1;
 568         }
 569
 570         return 0;
 571 }
 572
 573 /* We manually set ISL_BASIC_SET_FINAL instead of calling
 574  * isl_basic_map_finalize because we want to keep the position
 575  * of the divs and we therefore do not want to throw away redundant divs.
 576  * This is arguably a bit fragile.
 577  */
 578 __isl_give isl_basic_map *isl_basic_map_from_constraint(
 579         __isl_take isl_constraint *constraint)
 580 {
 581         int k;
 582         isl_local_space *ls;
 583         struct isl_basic_map *bmap;
 584         isl_int *c;
 585         unsigned total;
 586
 587         if (!constraint)
 588                 return NULL;
 589
 590         ls = isl_local_space_copy(constraint->ls);
 591         bmap = isl_basic_map_from_local_space(ls);
 592         bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
 593         if (isl_constraint_is_equality(constraint)) {
 594                 k = isl_basic_map_alloc_equality(bmap);
 595                 if (k < 0)
 596                         goto error;
 597                 c = bmap->eq[k];
 598         }
 599         else {
 600                 k = isl_basic_map_alloc_inequality(bmap);
 601                 if (k < 0)
 602                         goto error;
 603                 c = bmap->ineq[k];
 604         }
 605         total = isl_basic_map_total_dim(bmap);
 606         isl_seq_cpy(c, constraint->v->el, 1 + total);
 607         isl_constraint_free(constraint);
 608         if (bmap)
 609                 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
 610         return bmap;
 611 error:
 612         isl_constraint_free(constraint);
 613         isl_basic_map_free(bmap);
 614         return NULL;
 615 }
 616
 617 struct isl_basic_set *isl_basic_set_from_constraint(
 618         struct isl_constraint *constraint)
 619 {
 620         if (!constraint)
 621                 return NULL;
 622
 623         if (isl_constraint_dim(constraint, isl_dim_in) != 0)
 624                 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
 625                         "not a set constraint",
 626                         return isl_constraint_free(constraint));
 627         return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
 628 }
 629
 630 int isl_basic_map_has_defining_equality(
 631         __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
 632         __isl_give isl_constraint **c)
 633 {
 634         int i;
 635         unsigned offset;
 636         unsigned total;
 637
 638         if (!bmap)
 639                 return -1;
 640         offset = basic_map_offset(bmap, type);
 641         total = isl_basic_map_total_dim(bmap);
 642         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
 643         for (i = 0; i < bmap->n_eq; ++i)
 644                 if (!isl_int_is_zero(bmap->eq[i][offset + pos]) &&
 645                     isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
 646                                            1+total-offset-pos-1) == -1) {
 647                         *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 648                                                                 &bmap->eq[i]);
 649                         return 1;
 650                 }
 651         return 0;
 652 }
 653
 654 int isl_basic_set_has_defining_equality(
 655         __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
 656         __isl_give isl_constraint **c)
 657 {
 658         return isl_basic_map_has_defining_equality((isl_basic_map *)bset,
 659                                                     type, pos, c);
 660 }
 661
 662 int isl_basic_set_has_defining_inequalities(
 663         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 664         struct isl_constraint **lower,
 665         struct isl_constraint **upper)
 666 {
 667         int i, j;
 668         unsigned offset;
 669         unsigned total;
 670         isl_int m;
 671         isl_int **lower_line, **upper_line;
 672
 673         if (!bset)
 674                 return -1;
 675         offset = basic_set_offset(bset, type);
 676         total = isl_basic_set_total_dim(bset);
 677         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 678         isl_int_init(m);
 679         for (i = 0; i < bset->n_ineq; ++i) {
 680                 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
 681                         continue;
 682                 if (isl_int_is_one(bset->ineq[i][offset + pos]))
 683                         continue;
 684                 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
 685                         continue;
 686                 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
 687                                                 1+total-offset-pos-1) != -1)
 688                         continue;
 689                 for (j = i + 1; j < bset->n_ineq; ++j) {
 690                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 691                                             total))
 692                                 continue;
 693                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 694                         if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
 695                                 continue;
 696
 697                         if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
 698                                 lower_line = &bset->ineq[i];
 699                                 upper_line = &bset->ineq[j];
 700                         } else {
 701                                 lower_line = &bset->ineq[j];
 702                                 upper_line = &bset->ineq[i];
 703                         }
 704                         *lower = isl_basic_set_constraint(
 705                                         isl_basic_set_copy(bset), lower_line);
 706                         *upper = isl_basic_set_constraint(
 707                                         isl_basic_set_copy(bset), upper_line);
 708                         isl_int_clear(m);
 709                         return 1;
 710                 }
 711         }
 712         *lower = NULL;
 713         *upper = NULL;
 714         isl_int_clear(m);
 715         return 0;
 716 }
 717
 718 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
 719  * (in "a" and "b"), add a constraint to "bset" that ensures that the
 720  * bound implied by "a" is (strictly) larger than the bound implied by "b".
 721  *
 722  * If both constraints imply lower bounds, then this means that "a" is
 723  * active in the result.
 724  * If both constraints imply upper bounds, then this means that "b" is
 725  * active in the result.
 726  */
 727 static __isl_give isl_basic_set *add_larger_bound_constraint(
 728         __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
 729         unsigned abs_pos, int strict)
 730 {
 731         int k;
 732         isl_int t;
 733         unsigned total;
 734
 735         k = isl_basic_set_alloc_inequality(bset);
 736         if (k < 0)
 737                 goto error;
 738
 739         total = isl_basic_set_dim(bset, isl_dim_all);
 740
 741         isl_int_init(t);
 742         isl_int_neg(t, b[1 + abs_pos]);
 743
 744         isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
 745         isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
 746                 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
 747                 total - abs_pos);
 748
 749         if (strict)
 750                 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
 751
 752         isl_int_clear(t);
 753
 754         return bset;
 755 error:
 756         isl_basic_set_free(bset);
 757         return NULL;
 758 }
 759
 760 /* Add constraints to "context" that ensure that "u" is the smallest
 761  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 762  * the resulting basic set.
 763  */
 764 static __isl_give isl_basic_set *set_smallest_upper_bound(
 765         __isl_keep isl_basic_set *context,
 766         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
 767 {
 768         int j;
 769
 770         context = isl_basic_set_copy(context);
 771         context = isl_basic_set_cow(context);
 772
 773         context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
 774
 775         for (j = 0; j < bset->n_ineq; ++j) {
 776                 if (j == u)
 777                         continue;
 778                 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 779                         continue;
 780                 context = add_larger_bound_constraint(context,
 781                         bset->ineq[j], bset->ineq[u], abs_pos, j > u);
 782         }
 783
 784         context = isl_basic_set_simplify(context);
 785         context = isl_basic_set_finalize(context);
 786
 787         return context;
 788 }
 789
 790 /* Add constraints to "context" that ensure that "u" is the largest
 791  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 792  * the resulting basic set.
 793  */
 794 static __isl_give isl_basic_set *set_largest_lower_bound(
 795         __isl_keep isl_basic_set *context,
 796         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
 797 {
 798         int j;
 799
 800         context = isl_basic_set_copy(context);
 801         context = isl_basic_set_cow(context);
 802
 803         context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
 804
 805         for (j = 0; j < bset->n_ineq; ++j) {
 806                 if (j == l)
 807                         continue;
 808                 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
 809                         continue;
 810                 context = add_larger_bound_constraint(context,
 811                         bset->ineq[l], bset->ineq[j], abs_pos, j > l);
 812         }
 813
 814         context = isl_basic_set_simplify(context);
 815         context = isl_basic_set_finalize(context);
 816
 817         return context;
 818 }
 819
 820 static int foreach_upper_bound(__isl_keep isl_basic_set *bset,
 821         enum isl_dim_type type, unsigned abs_pos,
 822         __isl_take isl_basic_set *context, int n_upper,
 823         int (*fn)(__isl_take isl_constraint *lower,
 824                   __isl_take isl_constraint *upper,
 825                   __isl_take isl_basic_set *bset, void *user), void *user)
 826 {
 827         isl_basic_set *context_i;
 828         isl_constraint *upper = NULL;
 829         int i;
 830
 831         for (i = 0; i < bset->n_ineq; ++i) {
 832                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 833                         continue;
 834
 835                 context_i = set_smallest_upper_bound(context, bset,
 836                                                         abs_pos, n_upper, i);
 837                 if (isl_basic_set_is_empty(context_i)) {
 838                         isl_basic_set_free(context_i);
 839                         continue;
 840                 }
 841                 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 842                                                 &bset->ineq[i]);
 843                 if (!upper || !context_i)
 844                         goto error;
 845                 if (fn(NULL, upper, context_i, user) < 0)
 846                         break;
 847         }
 848
 849         isl_basic_set_free(context);
 850
 851         if (i < bset->n_ineq)
 852                 return -1;
 853
 854         return 0;
 855 error:
 856         isl_constraint_free(upper);
 857         isl_basic_set_free(context_i);
 858         isl_basic_set_free(context);
 859         return -1;
 860 }
 861
 862 static int foreach_lower_bound(__isl_keep isl_basic_set *bset,
 863         enum isl_dim_type type, unsigned abs_pos,
 864         __isl_take isl_basic_set *context, int n_lower,
 865         int (*fn)(__isl_take isl_constraint *lower,
 866                   __isl_take isl_constraint *upper,
 867                   __isl_take isl_basic_set *bset, void *user), void *user)
 868 {
 869         isl_basic_set *context_i;
 870         isl_constraint *lower = NULL;
 871         int i;
 872
 873         for (i = 0; i < bset->n_ineq; ++i) {
 874                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 875                         continue;
 876
 877                 context_i = set_largest_lower_bound(context, bset,
 878                                                         abs_pos, n_lower, i);
 879                 if (isl_basic_set_is_empty(context_i)) {
 880                         isl_basic_set_free(context_i);
 881                         continue;
 882                 }
 883                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 884                                                 &bset->ineq[i]);
 885                 if (!lower || !context_i)
 886                         goto error;
 887                 if (fn(lower, NULL, context_i, user) < 0)
 888                         break;
 889         }
 890
 891         isl_basic_set_free(context);
 892
 893         if (i < bset->n_ineq)
 894                 return -1;
 895
 896         return 0;
 897 error:
 898         isl_constraint_free(lower);
 899         isl_basic_set_free(context_i);
 900         isl_basic_set_free(context);
 901         return -1;
 902 }
 903
 904 static int foreach_bound_pair(__isl_keep isl_basic_set *bset,
 905         enum isl_dim_type type, unsigned abs_pos,
 906         __isl_take isl_basic_set *context, int n_lower, int n_upper,
 907         int (*fn)(__isl_take isl_constraint *lower,
 908                   __isl_take isl_constraint *upper,
 909                   __isl_take isl_basic_set *bset, void *user), void *user)
 910 {
 911         isl_basic_set *context_i, *context_j;
 912         isl_constraint *lower = NULL;
 913         isl_constraint *upper = NULL;
 914         int i, j;
 915
 916         for (i = 0; i < bset->n_ineq; ++i) {
 917                 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
 918                         continue;
 919
 920                 context_i = set_largest_lower_bound(context, bset,
 921                                                         abs_pos, n_lower, i);
 922                 if (isl_basic_set_is_empty(context_i)) {
 923                         isl_basic_set_free(context_i);
 924                         continue;
 925                 }
 926
 927                 for (j = 0; j < bset->n_ineq; ++j) {
 928                         if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 929                                 continue;
 930
 931                         context_j = set_smallest_upper_bound(context_i, bset,
 932                                                             abs_pos, n_upper, j);
 933                         context_j = isl_basic_set_extend_constraints(context_j,
 934                                                                         0, 1);
 935                         context_j = add_larger_bound_constraint(context_j,
 936                                 bset->ineq[i], bset->ineq[j], abs_pos, 0);
 937                         context_j = isl_basic_set_simplify(context_j);
 938                         context_j = isl_basic_set_finalize(context_j);
 939                         if (isl_basic_set_is_empty(context_j)) {
 940                                 isl_basic_set_free(context_j);
 941                                 continue;
 942                         }
 943                         lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 944                                                         &bset->ineq[i]);
 945                         upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 946                                                         &bset->ineq[j]);
 947                         if (!lower || !upper || !context_j)
 948                                 goto error;
 949                         if (fn(lower, upper, context_j, user) < 0)
 950                                 break;
 951                 }
 952
 953                 isl_basic_set_free(context_i);
 954
 955                 if (j < bset->n_ineq)
 956                         break;
 957         }
 958
 959         isl_basic_set_free(context);
 960
 961         if (i < bset->n_ineq)
 962                 return -1;
 963
 964         return 0;
 965 error:
 966         isl_constraint_free(lower);
 967         isl_constraint_free(upper);
 968         isl_basic_set_free(context_i);
 969         isl_basic_set_free(context_j);
 970         isl_basic_set_free(context);
 971         return -1;
 972 }
 973
 974 /* For each pair of lower and upper bounds on the variable "pos"
 975  * of type "type", call "fn" with these lower and upper bounds and the
 976  * set of constraints on the remaining variables where these bounds
 977  * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
 978  *
 979  * If the designated variable is equal to an affine combination of the
 980  * other variables then fn is called with both lower and upper
 981  * set to the corresponding equality.
 982  *
 983  * If there is no lower (or upper) bound, then NULL is passed
 984  * as the corresponding bound.
 985  *
 986  * We first check if the variable is involved in any equality.
 987  * If not, we count the number of lower and upper bounds and
 988  * act accordingly.
 989  */
 990 int isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
 991         enum isl_dim_type type, unsigned pos,
 992         int (*fn)(__isl_take isl_constraint *lower,
 993                   __isl_take isl_constraint *upper,
 994                   __isl_take isl_basic_set *bset, void *user), void *user)
 995 {
 996         int i;
 997         isl_constraint *lower = NULL;
 998         isl_constraint *upper = NULL;
 999         isl_basic_set *context = NULL;
1000         unsigned abs_pos;
1001         int n_lower, n_upper;
1002
1003         if (!bset)
1004                 return -1;
1005         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
1006         isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
1007                 return -1);
1008
1009         abs_pos = pos;
1010         if (type == isl_dim_set)
1011                 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
1012
1013         for (i = 0; i < bset->n_eq; ++i) {
1014                 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
1015                         continue;
1016
1017                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1018                                                 &bset->eq[i]);
1019                 upper = isl_constraint_copy(lower);
1020                 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
1021                                         type, pos, 1);
1022                 if (!lower || !upper || !context)
1023                         goto error;
1024                 return fn(lower, upper, context, user);
1025         }
1026
1027         n_lower = 0;
1028         n_upper = 0;
1029         for (i = 0; i < bset->n_ineq; ++i) {
1030                 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1031                         n_lower++;
1032                 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
1033                         n_upper++;
1034         }
1035
1036         context = isl_basic_set_copy(bset);
1037         context = isl_basic_set_cow(context);
1038         if (!context)
1039                 goto error;
1040         for (i = context->n_ineq - 1; i >= 0; --i)
1041                 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
1042                         isl_basic_set_drop_inequality(context, i);
1043
1044         context = isl_basic_set_drop(context, type, pos, 1);
1045         if (!n_lower && !n_upper)
1046                 return fn(NULL, NULL, context, user);
1047         if (!n_lower)
1048                 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
1049                                                 fn, user);
1050         if (!n_upper)
1051                 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
1052                                                 fn, user);
1053         return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
1054                                         fn, user);
1055 error:
1056         isl_constraint_free(lower);
1057         isl_constraint_free(upper);
1058         isl_basic_set_free(context);
1059         return -1;
1060 }
1061
1062 __isl_give isl_aff *isl_constraint_get_bound(
1063         __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
1064 {
1065         isl_aff *aff;
1066         isl_ctx *ctx;
1067
1068         if (!constraint)
1069                 return NULL;
1070         ctx = isl_constraint_get_ctx(constraint);
1071         if (pos >= isl_constraint_dim(constraint, type))
1072                 isl_die(ctx, isl_error_invalid,
1073                         "index out of bounds", return NULL);
1074         if (isl_constraint_dim(constraint, isl_dim_in) != 0)
1075                 isl_die(ctx, isl_error_invalid,
1076                         "not a set constraint", return NULL);
1077
1078         pos += offset(constraint, type);
1079         if (isl_int_is_zero(constraint->v->el[pos]))
1080                 isl_die(ctx, isl_error_invalid,
1081                         "constraint does not define a bound on given dimension",
1082                         return NULL);
1083
1084         aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1085         if (!aff)
1086                 return NULL;
1087
1088         if (isl_int_is_neg(constraint->v->el[pos]))
1089                 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1090         else
1091                 isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1092         isl_int_set_si(aff->v->el[1 + pos], 0);
1093         isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1094
1095         return aff;
1096 }
1097
1098 /* For an inequality constraint
1099  *
1100  *      f >= 0
1101  *
1102  * or an equality constraint
1103  *
1104  *      f = 0
1105  *
1106  * return the affine expression f.
1107  */
1108 __isl_give isl_aff *isl_constraint_get_aff(
1109         __isl_keep isl_constraint *constraint)
1110 {
1111         isl_aff *aff;
1112
1113         if (!constraint)
1114                 return NULL;
1115
1116         aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1117         if (!aff)
1118                 return NULL;
1119
1120         isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1121         isl_int_set_si(aff->v->el[0], 1);
1122
1123         return aff;
1124 }
1125
1126 /* Construct an equality constraint equating the given affine expression
1127  * to zero.
1128  */
1129 __isl_give isl_constraint *isl_equality_from_aff(__isl_take isl_aff *aff)
1130 {
1131         int k;
1132         isl_local_space *ls;
1133         isl_basic_set *bset;
1134
1135         if (!aff)
1136                 return NULL;
1137
1138         ls = isl_aff_get_domain_local_space(aff);
1139         bset = isl_basic_set_from_local_space(ls);
1140         bset = isl_basic_set_extend_constraints(bset, 1, 0);
1141         k = isl_basic_set_alloc_equality(bset);
1142         if (k < 0)
1143                 goto error;
1144
1145         isl_seq_cpy(bset->eq[k], aff->v->el + 1, aff->v->size - 1);
1146         isl_aff_free(aff);
1147
1148         return isl_basic_set_constraint(bset, &bset->eq[k]);
1149 error:
1150         isl_aff_free(aff);
1151         isl_basic_set_free(bset);
1152         return NULL;
1153 }
1154
1155 /* Construct an inequality constraint enforcing the given affine expression
1156  * to be non-negative.
1157  */
1158 __isl_give isl_constraint *isl_inequality_from_aff(__isl_take isl_aff *aff)
1159 {
1160         int k;
1161         isl_local_space *ls;
1162         isl_basic_set *bset;
1163
1164         if (!aff)
1165                 return NULL;
1166
1167         ls = isl_aff_get_domain_local_space(aff);
1168         bset = isl_basic_set_from_local_space(ls);
1169         bset = isl_basic_set_extend_constraints(bset, 0, 1);
1170         k = isl_basic_set_alloc_inequality(bset);
1171         if (k < 0)
1172                 goto error;
1173
1174         isl_seq_cpy(bset->ineq[k], aff->v->el + 1, aff->v->size - 1);
1175         isl_aff_free(aff);
1176
1177         return isl_basic_set_constraint(bset, &bset->ineq[k]);
1178 error:
1179         isl_aff_free(aff);
1180         isl_basic_set_free(bset);
1181         return NULL;
1182 }