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