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