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 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
 330         enum isl_dim_type type, unsigned pos)
 331 {
 332         return constraint ?
 333             isl_basic_map_get_dim_name(constraint->bmap, type, pos) : NULL;
 334 }
 335
 336 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
 337 {
 338         if (!constraint)
 339                 return;
 340         isl_int_set(*v, constraint->line[0][0]);
 341 }
 342
 343 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
 344         enum isl_dim_type type, int pos, isl_int *v)
 345 {
 346         if (!constraint)
 347                 return;
 348
 349         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 350         isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
 351 }
 352
 353 struct isl_div *isl_constraint_div(struct isl_constraint *constraint, int pos)
 354 {
 355         if (!constraint)
 356                 return NULL;
 357
 358         isl_assert(constraint->ctx, pos < n(constraint, isl_dim_div),
 359                         return NULL);
 360         isl_assert(constraint->ctx,
 361                 !isl_int_is_zero(constraint->bmap->div[pos][0]), return NULL);
 362         return isl_basic_map_div(isl_basic_map_copy(constraint->bmap), pos);
 363 }
 364
 365 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
 366 {
 367         if (!constraint)
 368                 return;
 369         isl_int_set(constraint->line[0][0], v);
 370 }
 371
 372 void isl_constraint_set_constant_si(__isl_keep isl_constraint *constraint,
 373         int v)
 374 {
 375         if (!constraint)
 376                 return;
 377         isl_int_set_si(constraint->line[0][0], v);
 378 }
 379
 380 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
 381         enum isl_dim_type type, int pos, isl_int v)
 382 {
 383         if (!constraint)
 384                 return;
 385
 386         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 387         isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
 388 }
 389
 390 void isl_constraint_set_coefficient_si(__isl_keep isl_constraint *constraint,
 391         enum isl_dim_type type, int pos, int v)
 392 {
 393         if (!constraint)
 394                 return;
 395
 396         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 397         isl_int_set_si(constraint->line[0][offset(constraint, type) + pos], v);
 398 }
 399
 400 void isl_constraint_clear(struct isl_constraint *constraint)
 401 {
 402         unsigned total;
 403
 404         if (!constraint)
 405                 return;
 406         total = isl_basic_map_total_dim(constraint->bmap);
 407         isl_seq_clr(constraint->line[0], 1 + total);
 408 }
 409
 410 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
 411 {
 412         unsigned total;
 413
 414         if (!constraint)
 415                 return NULL;
 416
 417         isl_assert(constraint->ctx, !isl_constraint_is_equality(constraint),
 418                         goto error);
 419         isl_assert(constraint->ctx, constraint->bmap->ref == 1, goto error);
 420         total = isl_basic_map_total_dim(constraint->bmap);
 421         isl_seq_neg(constraint->line[0], constraint->line[0], 1 + total);
 422         isl_int_sub_ui(constraint->line[0][0], constraint->line[0][0], 1);
 423         ISL_F_CLR(constraint->bmap, ISL_BASIC_MAP_NORMALIZED);
 424         return constraint;
 425 error:
 426         isl_constraint_free(constraint);
 427         return NULL;
 428 }
 429
 430 int isl_constraint_is_equality(struct isl_constraint *constraint)
 431 {
 432         if (!constraint)
 433                 return -1;
 434         return constraint->line >= constraint->bmap->eq;
 435 }
 436
 437 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
 438 {
 439         int i;
 440
 441         if (!constraint)
 442                 return -1;
 443         if (isl_constraint_is_equality(constraint))
 444                 return 0;
 445         for (i = 0; i < constraint->bmap->n_div; ++i) {
 446                 if (isl_int_is_zero(constraint->bmap->div[i][0]))
 447                         continue;
 448                 if (isl_basic_map_is_div_constraint(constraint->bmap,
 449                                         constraint->line[0], i))
 450                         return 1;
 451         }
 452
 453         return 0;
 454 }
 455
 456 /* We manually set ISL_BASIC_SET_FINAL instead of calling
 457  * isl_basic_map_finalize because we want to keep the position
 458  * of the divs and we therefore do not want to throw away redundant divs.
 459  * This is arguably a bit fragile.
 460  */
 461 __isl_give isl_basic_map *isl_basic_map_from_constraint(
 462         __isl_take isl_constraint *constraint)
 463 {
 464         int k;
 465         struct isl_basic_map *bmap;
 466         isl_int *c;
 467         unsigned total;
 468
 469         if (!constraint)
 470                 return NULL;
 471
 472         if (constraint->bmap->n_eq == 1 && constraint->bmap->n_ineq == 0) {
 473                 bmap = isl_basic_map_copy(constraint->bmap);
 474                 isl_constraint_free(constraint);
 475                 return bmap;
 476         }
 477
 478         bmap = isl_basic_map_universe_like(constraint->bmap);
 479         bmap = isl_basic_map_align_divs(bmap, constraint->bmap);
 480         bmap = isl_basic_map_cow(bmap);
 481         bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
 482         if (isl_constraint_is_equality(constraint)) {
 483                 k = isl_basic_map_alloc_equality(bmap);
 484                 if (k < 0)
 485                         goto error;
 486                 c = bmap->eq[k];
 487         }
 488         else {
 489                 k = isl_basic_map_alloc_inequality(bmap);
 490                 if (k < 0)
 491                         goto error;
 492                 c = bmap->ineq[k];
 493         }
 494         total = isl_basic_map_total_dim(bmap);
 495         isl_seq_cpy(c, constraint->line[0], 1 + total);
 496         isl_constraint_free(constraint);
 497         if (bmap)
 498                 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
 499         return bmap;
 500 error:
 501         isl_constraint_free(constraint);
 502         isl_basic_map_free(bmap);
 503         return NULL;
 504 }
 505
 506 struct isl_basic_set *isl_basic_set_from_constraint(
 507         struct isl_constraint *constraint)
 508 {
 509         if (!constraint)
 510                 return NULL;
 511
 512         isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
 513         return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
 514 error:
 515         isl_constraint_free(constraint);
 516         return NULL;
 517 }
 518
 519 int isl_basic_map_has_defining_equality(
 520         __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
 521         __isl_give isl_constraint **c)
 522 {
 523         int i;
 524         unsigned offset;
 525         unsigned total;
 526
 527         if (!bmap)
 528                 return -1;
 529         offset = basic_map_offset(bmap, type);
 530         total = isl_basic_map_total_dim(bmap);
 531         isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
 532         for (i = 0; i < bmap->n_eq; ++i)
 533                 if (!isl_int_is_zero(bmap->eq[i][offset + pos]) &&
 534                     isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
 535                                            1+total-offset-pos-1) == -1) {
 536                         *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 537                                                                 &bmap->eq[i]);
 538                         return 1;
 539                 }
 540         return 0;
 541 }
 542
 543 int isl_basic_set_has_defining_equality(
 544         __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
 545         __isl_give isl_constraint **c)
 546 {
 547         return isl_basic_map_has_defining_equality((isl_basic_map *)bset,
 548                                                     type, pos, c);
 549 }
 550
 551 int isl_basic_set_has_defining_inequalities(
 552         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 553         struct isl_constraint **lower,
 554         struct isl_constraint **upper)
 555 {
 556         int i, j;
 557         unsigned offset;
 558         unsigned total;
 559         isl_int m;
 560         isl_int **lower_line, **upper_line;
 561
 562         if (!bset)
 563                 return -1;
 564         offset = basic_set_offset(bset, type);
 565         total = isl_basic_set_total_dim(bset);
 566         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 567         isl_int_init(m);
 568         for (i = 0; i < bset->n_ineq; ++i) {
 569                 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
 570                         continue;
 571                 if (isl_int_is_one(bset->ineq[i][offset + pos]))
 572                         continue;
 573                 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
 574                         continue;
 575                 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
 576                                                 1+total-offset-pos-1) != -1)
 577                         continue;
 578                 for (j = i + 1; j < bset->n_ineq; ++j) {
 579                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 580                                             total))
 581                                 continue;
 582                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 583                         if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
 584                                 continue;
 585
 586                         if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
 587                                 lower_line = &bset->ineq[i];
 588                                 upper_line = &bset->ineq[j];
 589                         } else {
 590                                 lower_line = &bset->ineq[j];
 591                                 upper_line = &bset->ineq[i];
 592                         }
 593                         *lower = isl_basic_set_constraint(
 594                                         isl_basic_set_copy(bset), lower_line);
 595                         *upper = isl_basic_set_constraint(
 596                                         isl_basic_set_copy(bset), upper_line);
 597                         isl_int_clear(m);
 598                         return 1;
 599                 }
 600         }
 601         *lower = NULL;
 602         *upper = NULL;
 603         isl_int_clear(m);
 604         return 0;
 605 }
 606
 607 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
 608  * (in "a" and "b"), add a constraint to "bset" that ensures that the
 609  * bound implied by "a" is (strictly) larger than the bound implied by "b".
 610  *
 611  * If both constraints imply lower bounds, then this means that "a" is
 612  * active in the result.
 613  * If both constraints imply upper bounds, then this means that "b" is
 614  * active in the result.
 615  */
 616 static __isl_give isl_basic_set *add_larger_bound_constraint(
 617         __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
 618         unsigned abs_pos, int strict)
 619 {
 620         int k;
 621         isl_int t;
 622         unsigned total;
 623
 624         k = isl_basic_set_alloc_inequality(bset);
 625         if (k < 0)
 626                 goto error;
 627
 628         total = isl_basic_set_dim(bset, isl_dim_all);
 629
 630         isl_int_init(t);
 631         isl_int_neg(t, b[1 + abs_pos]);
 632
 633         isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
 634         isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
 635                 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
 636                 total - abs_pos);
 637
 638         if (strict)
 639                 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
 640
 641         isl_int_clear(t);
 642
 643         return bset;
 644 error:
 645         isl_basic_set_free(bset);
 646         return NULL;
 647 }
 648
 649 /* Add constraints to "context" that ensure that "u" is the smallest
 650  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 651  * the resulting basic set.
 652  */
 653 static __isl_give isl_basic_set *set_smallest_upper_bound(
 654         __isl_keep isl_basic_set *context,
 655         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
 656 {
 657         int j;
 658
 659         context = isl_basic_set_copy(context);
 660         context = isl_basic_set_cow(context);
 661
 662         context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
 663
 664         for (j = 0; j < bset->n_ineq; ++j) {
 665                 if (j == u)
 666                         continue;
 667                 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 668                         continue;
 669                 context = add_larger_bound_constraint(context,
 670                         bset->ineq[j], bset->ineq[u], abs_pos, j > u);
 671         }
 672
 673         context = isl_basic_set_simplify(context);
 674         context = isl_basic_set_finalize(context);
 675
 676         return context;
 677 }
 678
 679 /* Add constraints to "context" that ensure that "u" is the largest
 680  * (and therefore active) upper bound on "abs_pos" in "bset" and return
 681  * the resulting basic set.
 682  */
 683 static __isl_give isl_basic_set *set_largest_lower_bound(
 684         __isl_keep isl_basic_set *context,
 685         __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
 686 {
 687         int j;
 688
 689         context = isl_basic_set_copy(context);
 690         context = isl_basic_set_cow(context);
 691
 692         context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
 693
 694         for (j = 0; j < bset->n_ineq; ++j) {
 695                 if (j == l)
 696                         continue;
 697                 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
 698                         continue;
 699                 context = add_larger_bound_constraint(context,
 700                         bset->ineq[l], bset->ineq[j], abs_pos, j > l);
 701         }
 702
 703         context = isl_basic_set_simplify(context);
 704         context = isl_basic_set_finalize(context);
 705
 706         return context;
 707 }
 708
 709 static int foreach_upper_bound(__isl_keep isl_basic_set *bset,
 710         enum isl_dim_type type, unsigned abs_pos,
 711         __isl_take isl_basic_set *context, int n_upper,
 712         int (*fn)(__isl_take isl_constraint *lower,
 713                   __isl_take isl_constraint *upper,
 714                   __isl_take isl_basic_set *bset, void *user), void *user)
 715 {
 716         isl_basic_set *context_i;
 717         isl_constraint *upper = NULL;
 718         int i;
 719
 720         for (i = 0; i < bset->n_ineq; ++i) {
 721                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 722                         continue;
 723
 724                 context_i = set_smallest_upper_bound(context, bset,
 725                                                         abs_pos, n_upper, i);
 726                 if (isl_basic_set_is_empty(context_i)) {
 727                         isl_basic_set_free(context_i);
 728                         continue;
 729                 }
 730                 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 731                                                 &bset->ineq[i]);
 732                 if (!upper || !context_i)
 733                         goto error;
 734                 if (fn(NULL, upper, context_i, user) < 0)
 735                         break;
 736         }
 737
 738         isl_basic_set_free(context);
 739
 740         if (i < bset->n_ineq)
 741                 return -1;
 742
 743         return 0;
 744 error:
 745         isl_constraint_free(upper);
 746         isl_basic_set_free(context_i);
 747         isl_basic_set_free(context);
 748         return -1;
 749 }
 750
 751 static int foreach_lower_bound(__isl_keep isl_basic_set *bset,
 752         enum isl_dim_type type, unsigned abs_pos,
 753         __isl_take isl_basic_set *context, int n_lower,
 754         int (*fn)(__isl_take isl_constraint *lower,
 755                   __isl_take isl_constraint *upper,
 756                   __isl_take isl_basic_set *bset, void *user), void *user)
 757 {
 758         isl_basic_set *context_i;
 759         isl_constraint *lower = NULL;
 760         int i;
 761
 762         for (i = 0; i < bset->n_ineq; ++i) {
 763                 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
 764                         continue;
 765
 766                 context_i = set_largest_lower_bound(context, bset,
 767                                                         abs_pos, n_lower, i);
 768                 if (isl_basic_set_is_empty(context_i)) {
 769                         isl_basic_set_free(context_i);
 770                         continue;
 771                 }
 772                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 773                                                 &bset->ineq[i]);
 774                 if (!lower || !context_i)
 775                         goto error;
 776                 if (fn(lower, NULL, context_i, user) < 0)
 777                         break;
 778         }
 779
 780         isl_basic_set_free(context);
 781
 782         if (i < bset->n_ineq)
 783                 return -1;
 784
 785         return 0;
 786 error:
 787         isl_constraint_free(lower);
 788         isl_basic_set_free(context_i);
 789         isl_basic_set_free(context);
 790         return -1;
 791 }
 792
 793 static int foreach_bound_pair(__isl_keep isl_basic_set *bset,
 794         enum isl_dim_type type, unsigned abs_pos,
 795         __isl_take isl_basic_set *context, int n_lower, int n_upper,
 796         int (*fn)(__isl_take isl_constraint *lower,
 797                   __isl_take isl_constraint *upper,
 798                   __isl_take isl_basic_set *bset, void *user), void *user)
 799 {
 800         isl_basic_set *context_i, *context_j;
 801         isl_constraint *lower = NULL;
 802         isl_constraint *upper = NULL;
 803         int i, j;
 804
 805         for (i = 0; i < bset->n_ineq; ++i) {
 806                 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
 807                         continue;
 808
 809                 context_i = set_largest_lower_bound(context, bset,
 810                                                         abs_pos, n_lower, i);
 811                 if (isl_basic_set_is_empty(context_i)) {
 812                         isl_basic_set_free(context_i);
 813                         continue;
 814                 }
 815
 816                 for (j = 0; j < bset->n_ineq; ++j) {
 817                         if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
 818                                 continue;
 819
 820                         context_j = set_smallest_upper_bound(context_i, bset,
 821                                                             abs_pos, n_upper, j);
 822                         context_j = isl_basic_set_extend_constraints(context_j,
 823                                                                         0, 1);
 824                         context_j = add_larger_bound_constraint(context_j,
 825                                 bset->ineq[i], bset->ineq[j], abs_pos, 0);
 826                         context_j = isl_basic_set_simplify(context_j);
 827                         context_j = isl_basic_set_finalize(context_j);
 828                         if (isl_basic_set_is_empty(context_j)) {
 829                                 isl_basic_set_free(context_j);
 830                                 continue;
 831                         }
 832                         lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 833                                                         &bset->ineq[i]);
 834                         upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
 835                                                         &bset->ineq[j]);
 836                         if (!lower || !upper || !context_j)
 837                                 goto error;
 838                         if (fn(lower, upper, context_j, user) < 0)
 839                                 break;
 840                 }
 841
 842                 isl_basic_set_free(context_i);
 843
 844                 if (j < bset->n_ineq)
 845                         break;
 846         }
 847
 848         isl_basic_set_free(context);
 849
 850         if (i < bset->n_ineq)
 851                 return -1;
 852
 853         return 0;
 854 error:
 855         isl_constraint_free(lower);
 856         isl_constraint_free(upper);
 857         isl_basic_set_free(context_i);
 858         isl_basic_set_free(context_j);
 859         isl_basic_set_free(context);
 860         return -1;
 861 }
 862
 863 /* For each pair of lower and upper bounds on the variable "pos"
 864  * of type "type", call "fn" with these lower and upper bounds and the
 865  * set of constraints on the remaining variables where these bounds
 866  * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
 867  *
 868  * If the designated variable is equal to an affine combination of the
 869  * other variables then fn is called with both lower and upper
 870  * set to the corresponding equality.
 871  *
 872  * If there is no lower (or upper) bound, then NULL is passed
 873  * as the corresponding bound.
 874  *
 875  * We first check if the variable is involved in any equality.
 876  * If not, we count the number of lower and upper bounds and
 877  * act accordingly.
 878  */
 879 int isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
 880         enum isl_dim_type type, unsigned pos,
 881         int (*fn)(__isl_take isl_constraint *lower,
 882                   __isl_take isl_constraint *upper,
 883                   __isl_take isl_basic_set *bset, void *user), void *user)
 884 {
 885         int i;
 886         isl_constraint *lower = NULL;
 887         isl_constraint *upper = NULL;
 888         isl_basic_set *context = NULL;
 889         unsigned abs_pos;
 890         int n_lower, n_upper;
 891
 892         if (!bset)
 893                 return -1;
 894         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 895         isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
 896                 return -1);
 897
 898         abs_pos = pos;
 899         if (type == isl_dim_set)
 900                 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
 901
 902         for (i = 0; i < bset->n_eq; ++i) {
 903                 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
 904                         continue;
 905
 906                 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
 907                                                 &bset->eq[i]);
 908                 upper = isl_constraint_copy(lower);
 909                 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
 910                                         type, pos, 1);
 911                 if (!lower || !upper || !context)
 912                         goto error;
 913                 return fn(lower, upper, context, user);
 914         }
 915
 916         n_lower = 0;
 917         n_upper = 0;
 918         for (i = 0; i < bset->n_ineq; ++i) {
 919                 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
 920                         n_lower++;
 921                 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
 922                         n_upper++;
 923         }
 924
 925         context = isl_basic_set_copy(bset);
 926         context = isl_basic_set_cow(context);
 927         if (!context)
 928                 goto error;
 929         for (i = context->n_ineq - 1; i >= 0; --i)
 930                 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
 931                         isl_basic_set_drop_inequality(context, i);
 932
 933         context = isl_basic_set_drop(context, type, pos, 1);
 934         if (!n_lower && !n_upper)
 935                 return fn(NULL, NULL, context, user);
 936         if (!n_lower)
 937                 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
 938                                                 fn, user);
 939         if (!n_upper)
 940                 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
 941                                                 fn, user);
 942         return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
 943                                         fn, user);
 944 error:
 945         isl_constraint_free(lower);
 946         isl_constraint_free(upper);
 947         isl_basic_set_free(context);
 948         return -1;
 949 }