isl_constraint.c

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