isl_constraint.c

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