1/* 2 * Copyright 2011 INRIA Saclay 3 * Copyright 2012-2014 Ecole Normale Superieure 4 * Copyright 2019 Cerebras Systems 5 * 6 * Use of this software is governed by the MIT license 7 * 8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, 9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, 10 * 91893 Orsay, France 11 * and Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France 12 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA 13 */ 14 15#include <isl_ctx_private.h> 16#include <isl/id.h> 17#include <isl_map_private.h> 18#include <isl_local_space_private.h> 19#include <isl_space_private.h> 20#include <isl_mat_private.h> 21#include <isl_aff_private.h> 22#include <isl_vec_private.h> 23#include <isl_point_private.h> 24#include <isl_seq.h> 25#include <isl_local.h> 26 27isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls) 28{ 29 return ls ? ls->dim->ctx : NULL; 30} 31 32/* Return a hash value that digests "ls". 33 */ 34uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls) 35{ 36 uint32_t hash, space_hash, div_hash; 37 38 if (!ls) 39 return 0; 40 41 hash = isl_hash_init(); 42 space_hash = isl_space_get_full_hash(isl_local_space_peek_space(ls)); 43 isl_hash_hash(hash, space_hash); 44 div_hash = isl_mat_get_hash(ls->div); 45 isl_hash_hash(hash, div_hash); 46 47 return hash; 48} 49 50__isl_give isl_local_space *isl_local_space_alloc_div( 51 __isl_take isl_space *space, __isl_take isl_mat *div) 52{ 53 isl_ctx *ctx; 54 isl_local_space *ls = NULL; 55 56 if (!space || !div) 57 goto error; 58 59 ctx = isl_space_get_ctx(space); 60 ls = isl_calloc_type(ctx, struct isl_local_space); 61 if (!ls) 62 goto error; 63 64 ls->ref = 1; 65 ls->dim = space; 66 ls->div = div; 67 68 return ls; 69error: 70 isl_mat_free(div); 71 isl_space_free(space); 72 isl_local_space_free(ls); 73 return NULL; 74} 75 76__isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *space, 77 unsigned n_div) 78{ 79 isl_ctx *ctx; 80 isl_mat *div; 81 isl_size total; 82 83 if (!space) 84 return NULL; 85 86 total = isl_space_dim(space, isl_dim_all); 87 if (total < 0) 88 return isl_local_space_from_space(isl_space_free(space)); 89 90 ctx = isl_space_get_ctx(space); 91 div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div); 92 return isl_local_space_alloc_div(space, div); 93} 94 95__isl_give isl_local_space *isl_local_space_from_space( 96 __isl_take isl_space *space) 97{ 98 return isl_local_space_alloc(space, 0); 99} 100 101__isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls) 102{ 103 if (!ls) 104 return NULL; 105 106 ls->ref++; 107 return ls; 108} 109 110__isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls) 111{ 112 if (!ls) 113 return NULL; 114 115 return isl_local_space_alloc_div(isl_space_copy(ls->dim), 116 isl_mat_copy(ls->div)); 117 118} 119 120__isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls) 121{ 122 if (!ls) 123 return NULL; 124 125 if (ls->ref == 1) 126 return ls; 127 ls->ref--; 128 return isl_local_space_dup(ls); 129} 130 131__isl_null isl_local_space *isl_local_space_free( 132 __isl_take isl_local_space *ls) 133{ 134 if (!ls) 135 return NULL; 136 137 if (--ls->ref > 0) 138 return NULL; 139 140 isl_space_free(ls->dim); 141 isl_mat_free(ls->div); 142 143 free(ls); 144 145 return NULL; 146} 147 148/* Is the local space that of a parameter domain? 149 */ 150isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls) 151{ 152 if (!ls) 153 return isl_bool_error; 154 return isl_space_is_params(ls->dim); 155} 156 157/* Is the local space that of a set? 158 */ 159isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls) 160{ 161 return ls ? isl_space_is_set(ls->dim) : isl_bool_error; 162} 163 164#undef TYPE 165#define TYPE isl_local_space 166 167#include "isl_type_has_equal_space_bin_templ.c" 168#include "isl_type_has_space_templ.c" 169 170/* Check that the space of "ls" is equal to "space". 171 */ 172static isl_stat isl_local_space_check_has_space(__isl_keep isl_local_space *ls, 173 __isl_keep isl_space *space) 174{ 175 isl_bool ok; 176 177 ok = isl_local_space_has_space(ls, space); 178 if (ok < 0) 179 return isl_stat_error; 180 if (!ok) 181 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 182 "spaces don't match", return isl_stat_error); 183 return isl_stat_ok; 184} 185 186/* Return true if the two local spaces are identical, with identical 187 * expressions for the integer divisions. 188 */ 189isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1, 190 __isl_keep isl_local_space *ls2) 191{ 192 isl_bool equal; 193 194 equal = isl_local_space_has_equal_space(ls1, ls2); 195 if (equal < 0 || !equal) 196 return equal; 197 198 if (!isl_local_space_divs_known(ls1)) 199 return isl_bool_false; 200 if (!isl_local_space_divs_known(ls2)) 201 return isl_bool_false; 202 203 return isl_mat_is_equal(ls1->div, ls2->div); 204} 205 206/* Compare two isl_local_spaces. 207 * 208 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater" 209 * than "ls2" and 0 if they are equal. 210 */ 211int isl_local_space_cmp(__isl_keep isl_local_space *ls1, 212 __isl_keep isl_local_space *ls2) 213{ 214 int cmp; 215 216 if (ls1 == ls2) 217 return 0; 218 if (!ls1) 219 return -1; 220 if (!ls2) 221 return 1; 222 223 cmp = isl_space_cmp(ls1->dim, ls2->dim); 224 if (cmp != 0) 225 return cmp; 226 227 return isl_local_cmp(ls1->div, ls2->div); 228} 229 230isl_size isl_local_space_dim(__isl_keep isl_local_space *ls, 231 enum isl_dim_type type) 232{ 233 if (!ls) 234 return isl_size_error; 235 if (type == isl_dim_div) 236 return ls->div->n_row; 237 if (type == isl_dim_all) { 238 isl_size dim = isl_space_dim(ls->dim, isl_dim_all); 239 if (dim < 0) 240 return isl_size_error; 241 return dim + ls->div->n_row; 242 } 243 return isl_space_dim(ls->dim, type); 244} 245 246#undef TYPE 247#define TYPE isl_local_space 248#include "check_type_range_templ.c" 249 250/* Return the position of the variables of the given type 251 * within the sequence of variables of "ls". 252 */ 253isl_size isl_local_space_var_offset(__isl_keep isl_local_space *ls, 254 enum isl_dim_type type) 255{ 256 isl_space *space; 257 258 space = isl_local_space_peek_space(ls); 259 switch (type) { 260 case isl_dim_param: 261 case isl_dim_in: 262 case isl_dim_out: return isl_space_offset(space, type); 263 case isl_dim_div: return isl_space_dim(space, isl_dim_all); 264 case isl_dim_cst: 265 default: 266 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 267 "invalid dimension type", return isl_size_error); 268 } 269} 270 271/* Return the position of the coefficients of the variables of the given type 272 * within the sequence of coefficients of "ls". 273 */ 274unsigned isl_local_space_offset(__isl_keep isl_local_space *ls, 275 enum isl_dim_type type) 276{ 277 if (!ls) 278 return 0; 279 280 switch (type) { 281 case isl_dim_cst: return 0; 282 case isl_dim_param: 283 case isl_dim_in: 284 case isl_dim_out: 285 case isl_dim_div: return 1 + isl_local_space_var_offset(ls, type); 286 default: return 0; 287 } 288} 289 290/* Return the position of the dimension of the given type and name 291 * in "ls". 292 * Return -1 if no such dimension can be found. 293 */ 294int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls, 295 enum isl_dim_type type, const char *name) 296{ 297 if (!ls) 298 return -1; 299 if (type == isl_dim_div) 300 return -1; 301 return isl_space_find_dim_by_name(ls->dim, type, name); 302} 303 304/* Does the given dimension have a name? 305 */ 306isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls, 307 enum isl_dim_type type, unsigned pos) 308{ 309 return ls ? isl_space_has_dim_name(ls->dim, type, pos) : isl_bool_error; 310} 311 312const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls, 313 enum isl_dim_type type, unsigned pos) 314{ 315 return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL; 316} 317 318isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls, 319 enum isl_dim_type type, unsigned pos) 320{ 321 return ls ? isl_space_has_dim_id(ls->dim, type, pos) : isl_bool_error; 322} 323 324__isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls, 325 enum isl_dim_type type, unsigned pos) 326{ 327 return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL; 328} 329 330/* Return the argument of the integer division at position "pos" in "ls". 331 * All local variables in "ls" are known to have a (complete) explicit 332 * representation. 333 */ 334static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos) 335{ 336 isl_aff *aff; 337 338 aff = isl_aff_alloc(isl_local_space_copy(ls)); 339 if (!aff) 340 return NULL; 341 isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size); 342 return aff; 343} 344 345/* Return the argument of the integer division at position "pos" in "ls". 346 * The integer division at that position is known to have a complete 347 * explicit representation, but some of the others do not. 348 * Remove them first because the domain of an isl_aff 349 * is not allowed to have unknown local variables. 350 */ 351static __isl_give isl_aff *drop_unknown_divs_and_extract_div( 352 __isl_keep isl_local_space *ls, int pos) 353{ 354 int i; 355 isl_size n; 356 isl_bool unknown; 357 isl_aff *aff; 358 359 n = isl_local_space_dim(ls, isl_dim_div); 360 if (n < 0) 361 return NULL; 362 ls = isl_local_space_copy(ls); 363 for (i = n - 1; i >= 0; --i) { 364 unknown = isl_local_space_div_is_marked_unknown(ls, i); 365 if (unknown < 0) 366 ls = isl_local_space_free(ls); 367 else if (!unknown) 368 continue; 369 ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1); 370 if (pos > i) 371 --pos; 372 } 373 aff = extract_div(ls, pos); 374 isl_local_space_free(ls); 375 return aff; 376} 377 378/* Return the argument of the integer division at position "pos" in "ls". 379 * The integer division is assumed to have a complete explicit 380 * representation. If some of the other integer divisions 381 * do not have an explicit representation, then they need 382 * to be removed first because the domain of an isl_aff 383 * is not allowed to have unknown local variables. 384 */ 385__isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls, 386 int pos) 387{ 388 isl_bool known; 389 390 if (!ls) 391 return NULL; 392 393 if (pos < 0 || pos >= ls->div->n_row) 394 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 395 "index out of bounds", return NULL); 396 397 known = isl_local_space_div_is_known(ls, pos); 398 if (known < 0) 399 return NULL; 400 if (!known) 401 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 402 "expression of div unknown", return NULL); 403 if (!isl_local_space_is_set(ls)) 404 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 405 "cannot represent divs of map spaces", return NULL); 406 407 known = isl_local_space_divs_known(ls); 408 if (known < 0) 409 return NULL; 410 if (known) 411 return extract_div(ls, pos); 412 else 413 return drop_unknown_divs_and_extract_div(ls, pos); 414} 415 416/* Return the space of "ls". 417 */ 418__isl_keep isl_space *isl_local_space_peek_space(__isl_keep isl_local_space *ls) 419{ 420 if (!ls) 421 return NULL; 422 423 return ls->dim; 424} 425 426__isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls) 427{ 428 return isl_space_copy(isl_local_space_peek_space(ls)); 429} 430 431/* Return the space of "ls". 432 * This may be either a copy or the space itself 433 * if there is only one reference to "ls". 434 * This allows the space to be modified inplace 435 * if both the local space and its space have only a single reference. 436 * The caller is not allowed to modify "ls" between this call and 437 * a subsequent call to isl_local_space_restore_space. 438 * The only exception is that isl_local_space_free can be called instead. 439 */ 440__isl_give isl_space *isl_local_space_take_space(__isl_keep isl_local_space *ls) 441{ 442 isl_space *space; 443 444 if (!ls) 445 return NULL; 446 if (ls->ref != 1) 447 return isl_local_space_get_space(ls); 448 space = ls->dim; 449 ls->dim = NULL; 450 return space; 451} 452 453/* Set the space of "ls" to "space", where the space of "ls" may be missing 454 * due to a preceding call to isl_local_space_take_space. 455 * However, in this case, "ls" only has a single reference and 456 * then the call to isl_local_space_cow has no effect. 457 */ 458__isl_give isl_local_space *isl_local_space_restore_space( 459 __isl_take isl_local_space *ls, __isl_take isl_space *space) 460{ 461 if (!ls || !space) 462 goto error; 463 464 if (ls->dim == space) { 465 isl_space_free(space); 466 return ls; 467 } 468 469 ls = isl_local_space_cow(ls); 470 if (!ls) 471 goto error; 472 isl_space_free(ls->dim); 473 ls->dim = space; 474 475 return ls; 476error: 477 isl_local_space_free(ls); 478 isl_space_free(space); 479 return NULL; 480} 481 482/* Return the local variables of "ls". 483 */ 484__isl_keep isl_local *isl_local_space_peek_local(__isl_keep isl_local_space *ls) 485{ 486 return ls ? ls->div : NULL; 487} 488 489/* Return a copy of the local variables of "ls". 490 */ 491__isl_give isl_local *isl_local_space_get_local(__isl_keep isl_local_space *ls) 492{ 493 return isl_local_copy(isl_local_space_peek_local(ls)); 494} 495 496/* Return the local variables of "ls". 497 * This may be either a copy or the local variables itself 498 * if there is only one reference to "ls". 499 * This allows the local variables to be modified inplace 500 * if both the local space and its local variables have only a single reference. 501 * The caller is not allowed to modify "ls" between this call and 502 * the subsequent call to isl_local_space_restore_local. 503 * The only exception is that isl_local_space_free can be called instead. 504 */ 505static __isl_give isl_local *isl_local_space_take_local( 506 __isl_keep isl_local_space *ls) 507{ 508 isl_local *local; 509 510 if (!ls) 511 return NULL; 512 if (ls->ref != 1) 513 return isl_local_space_get_local(ls); 514 local = ls->div; 515 ls->div = NULL; 516 return local; 517} 518 519/* Set the local variables of "ls" to "local", 520 * where the local variables of "ls" may be missing 521 * due to a preceding call to isl_local_space_take_local. 522 * However, in this case, "ls" only has a single reference and 523 * then the call to isl_local_space_cow has no effect. 524 */ 525static __isl_give isl_local_space *isl_local_space_restore_local( 526 __isl_take isl_local_space *ls, __isl_take isl_local *local) 527{ 528 if (!ls || !local) 529 goto error; 530 531 if (ls->div == local) { 532 isl_local_free(local); 533 return ls; 534 } 535 536 ls = isl_local_space_cow(ls); 537 if (!ls) 538 goto error; 539 isl_local_free(ls->div); 540 ls->div = local; 541 542 return ls; 543error: 544 isl_local_space_free(ls); 545 isl_local_free(local); 546 return NULL; 547} 548 549/* Replace the identifier of the tuple of type "type" by "id". 550 */ 551__isl_give isl_local_space *isl_local_space_set_tuple_id( 552 __isl_take isl_local_space *ls, 553 enum isl_dim_type type, __isl_take isl_id *id) 554{ 555 ls = isl_local_space_cow(ls); 556 if (!ls) 557 goto error; 558 ls->dim = isl_space_set_tuple_id(ls->dim, type, id); 559 if (!ls->dim) 560 return isl_local_space_free(ls); 561 return ls; 562error: 563 isl_id_free(id); 564 return NULL; 565} 566 567__isl_give isl_local_space *isl_local_space_set_dim_name( 568 __isl_take isl_local_space *ls, 569 enum isl_dim_type type, unsigned pos, const char *s) 570{ 571 ls = isl_local_space_cow(ls); 572 if (!ls) 573 return NULL; 574 ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s); 575 if (!ls->dim) 576 return isl_local_space_free(ls); 577 578 return ls; 579} 580 581__isl_give isl_local_space *isl_local_space_set_dim_id( 582 __isl_take isl_local_space *ls, 583 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id) 584{ 585 ls = isl_local_space_cow(ls); 586 if (!ls) 587 goto error; 588 ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id); 589 if (!ls->dim) 590 return isl_local_space_free(ls); 591 592 return ls; 593error: 594 isl_id_free(id); 595 return NULL; 596} 597 598/* Construct a zero-dimensional local space with the given parameter domain. 599 */ 600__isl_give isl_local_space *isl_local_space_set_from_params( 601 __isl_take isl_local_space *ls) 602{ 603 isl_space *space; 604 605 space = isl_local_space_take_space(ls); 606 space = isl_space_set_from_params(space); 607 ls = isl_local_space_restore_space(ls, space); 608 609 return ls; 610} 611 612__isl_give isl_local_space *isl_local_space_reset_space( 613 __isl_take isl_local_space *ls, __isl_take isl_space *space) 614{ 615 ls = isl_local_space_cow(ls); 616 if (!ls || !space) 617 goto error; 618 619 isl_space_free(ls->dim); 620 ls->dim = space; 621 622 return ls; 623error: 624 isl_local_space_free(ls); 625 isl_space_free(space); 626 return NULL; 627} 628 629/* Reorder the dimensions of "ls" according to the given reordering. 630 * The reordering r is assumed to have been extended with the local 631 * variables, leaving them in the same order. 632 */ 633__isl_give isl_local_space *isl_local_space_realign( 634 __isl_take isl_local_space *ls, __isl_take isl_reordering *r) 635{ 636 isl_local *local; 637 638 local = isl_local_space_take_local(ls); 639 local = isl_local_reorder(local, isl_reordering_copy(r)); 640 ls = isl_local_space_restore_local(ls, local); 641 642 ls = isl_local_space_reset_space(ls, isl_reordering_get_space(r)); 643 644 isl_reordering_free(r); 645 return ls; 646} 647 648__isl_give isl_local_space *isl_local_space_add_div( 649 __isl_take isl_local_space *ls, __isl_take isl_vec *div) 650{ 651 ls = isl_local_space_cow(ls); 652 if (!ls || !div) 653 goto error; 654 655 if (ls->div->n_col != div->size) 656 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 657 "incompatible dimensions", goto error); 658 659 ls->div = isl_mat_add_zero_cols(ls->div, 1); 660 ls->div = isl_mat_add_rows(ls->div, 1); 661 if (!ls->div) 662 goto error; 663 664 isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size); 665 isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0); 666 667 isl_vec_free(div); 668 return ls; 669error: 670 isl_local_space_free(ls); 671 isl_vec_free(div); 672 return NULL; 673} 674 675__isl_give isl_local_space *isl_local_space_replace_divs( 676 __isl_take isl_local_space *ls, __isl_take isl_mat *div) 677{ 678 ls = isl_local_space_cow(ls); 679 680 if (!ls || !div) 681 goto error; 682 683 isl_mat_free(ls->div); 684 ls->div = div; 685 return ls; 686error: 687 isl_mat_free(div); 688 isl_local_space_free(ls); 689 return NULL; 690} 691 692/* Copy row "s" of "src" to row "d" of "dst", applying the expansion 693 * defined by "exp". 694 */ 695static void expand_row(__isl_keep isl_mat *dst, int d, 696 __isl_keep isl_mat *src, int s, int *exp) 697{ 698 int i; 699 unsigned c = src->n_col - src->n_row; 700 701 isl_seq_cpy(dst->row[d], src->row[s], c); 702 isl_seq_clr(dst->row[d] + c, dst->n_col - c); 703 704 for (i = 0; i < s; ++i) 705 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]); 706} 707 708/* Compare (known) divs. 709 * Return non-zero if at least one of the two divs is unknown. 710 * In particular, if both divs are unknown, we respect their 711 * current order. Otherwise, we sort the known div after the unknown 712 * div only if the known div depends on the unknown div. 713 */ 714static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j, 715 unsigned n_row, unsigned n_col) 716{ 717 int li, lj; 718 int unknown_i, unknown_j; 719 720 unknown_i = isl_int_is_zero(row_i[0]); 721 unknown_j = isl_int_is_zero(row_j[0]); 722 723 if (unknown_i && unknown_j) 724 return i - j; 725 726 if (unknown_i) 727 li = n_col - n_row + i; 728 else 729 li = isl_seq_last_non_zero(row_i, n_col); 730 if (unknown_j) 731 lj = n_col - n_row + j; 732 else 733 lj = isl_seq_last_non_zero(row_j, n_col); 734 735 if (li != lj) 736 return li - lj; 737 738 return isl_seq_cmp(row_i, row_j, n_col); 739} 740 741/* Call cmp_row for divs in a matrix. 742 */ 743int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j) 744{ 745 return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col); 746} 747 748/* Call cmp_row for divs in a basic map. 749 */ 750static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j, 751 unsigned total) 752{ 753 return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total); 754} 755 756/* Sort the divs in "bmap". 757 * 758 * We first make sure divs are placed after divs on which they depend. 759 * Then we perform a simple insertion sort based on the same ordering 760 * that is used in isl_merge_divs. 761 */ 762__isl_give isl_basic_map *isl_basic_map_sort_divs( 763 __isl_take isl_basic_map *bmap) 764{ 765 int i, j; 766 isl_size total; 767 768 bmap = isl_basic_map_order_divs(bmap); 769 if (!bmap) 770 return NULL; 771 if (bmap->n_div <= 1) 772 return bmap; 773 774 total = isl_basic_map_dim(bmap, isl_dim_all); 775 if (total < 0) 776 return isl_basic_map_free(bmap); 777 for (i = 1; i < bmap->n_div; ++i) { 778 for (j = i - 1; j >= 0; --j) { 779 if (bmap_cmp_row(bmap, j, j + 1, 2 + total) <= 0) 780 break; 781 bmap = isl_basic_map_swap_div(bmap, j, j + 1); 782 if (!bmap) 783 return NULL; 784 } 785 } 786 787 return bmap; 788} 789 790/* Sort the divs in the basic maps of "map". 791 */ 792__isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map) 793{ 794 return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs); 795} 796 797/* Combine the two lists of divs into a single list. 798 * For each row i in div1, exp1[i] is set to the position of the corresponding 799 * row in the result. Similarly for div2 and exp2. 800 * This function guarantees 801 * exp1[i] >= i 802 * exp1[i+1] > exp1[i] 803 * For optimal merging, the two input list should have been sorted. 804 */ 805__isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1, 806 __isl_keep isl_mat *div2, int *exp1, int *exp2) 807{ 808 int i, j, k; 809 isl_mat *div = NULL; 810 unsigned d; 811 812 if (!div1 || !div2) 813 return NULL; 814 815 d = div1->n_col - div1->n_row; 816 div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row, 817 d + div1->n_row + div2->n_row); 818 if (!div) 819 return NULL; 820 821 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) { 822 int cmp; 823 824 expand_row(div, k, div1, i, exp1); 825 expand_row(div, k + 1, div2, j, exp2); 826 827 cmp = isl_mat_cmp_div(div, k, k + 1); 828 if (cmp == 0) { 829 exp1[i++] = k; 830 exp2[j++] = k; 831 } else if (cmp < 0) { 832 exp1[i++] = k; 833 } else { 834 exp2[j++] = k; 835 isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col); 836 } 837 } 838 for (; i < div1->n_row; ++i, ++k) { 839 expand_row(div, k, div1, i, exp1); 840 exp1[i] = k; 841 } 842 for (; j < div2->n_row; ++j, ++k) { 843 expand_row(div, k, div2, j, exp2); 844 exp2[j] = k; 845 } 846 847 div->n_row = k; 848 div->n_col = d + k; 849 850 return div; 851} 852 853/* Swap divs "a" and "b" in "ls". 854 */ 855__isl_give isl_local_space *isl_local_space_swap_div( 856 __isl_take isl_local_space *ls, int a, int b) 857{ 858 int offset; 859 860 ls = isl_local_space_cow(ls); 861 if (!ls) 862 return NULL; 863 if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row) 864 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 865 "index out of bounds", return isl_local_space_free(ls)); 866 offset = ls->div->n_col - ls->div->n_row; 867 ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b); 868 ls->div = isl_mat_swap_rows(ls->div, a, b); 869 if (!ls->div) 870 return isl_local_space_free(ls); 871 return ls; 872} 873 874/* Construct a local space that contains all the divs in either 875 * "ls1" or "ls2". 876 */ 877__isl_give isl_local_space *isl_local_space_intersect( 878 __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2) 879{ 880 isl_ctx *ctx; 881 int *exp1 = NULL; 882 int *exp2 = NULL; 883 isl_mat *div = NULL; 884 isl_bool equal; 885 886 if (!ls1 || !ls2) 887 goto error; 888 889 ctx = isl_local_space_get_ctx(ls1); 890 if (!isl_space_is_equal(ls1->dim, ls2->dim)) 891 isl_die(ctx, isl_error_invalid, 892 "spaces should be identical", goto error); 893 894 if (ls2->div->n_row == 0) { 895 isl_local_space_free(ls2); 896 return ls1; 897 } 898 899 if (ls1->div->n_row == 0) { 900 isl_local_space_free(ls1); 901 return ls2; 902 } 903 904 exp1 = isl_alloc_array(ctx, int, ls1->div->n_row); 905 exp2 = isl_alloc_array(ctx, int, ls2->div->n_row); 906 if (!exp1 || !exp2) 907 goto error; 908 909 div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2); 910 if (!div) 911 goto error; 912 913 equal = isl_mat_is_equal(ls1->div, div); 914 if (equal < 0) 915 goto error; 916 if (!equal) 917 ls1 = isl_local_space_cow(ls1); 918 if (!ls1) 919 goto error; 920 921 free(exp1); 922 free(exp2); 923 isl_local_space_free(ls2); 924 isl_mat_free(ls1->div); 925 ls1->div = div; 926 927 return ls1; 928error: 929 free(exp1); 930 free(exp2); 931 isl_mat_free(div); 932 isl_local_space_free(ls1); 933 isl_local_space_free(ls2); 934 return NULL; 935} 936 937/* Is the local variable "div" of "ls" marked as not having 938 * an explicit representation? 939 * Note that even if this variable is not marked in this way and therefore 940 * does have an explicit representation, this representation may still 941 * depend (indirectly) on other local variables that do not 942 * have an explicit representation. 943 */ 944isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls, 945 int div) 946{ 947 if (!ls) 948 return isl_bool_error; 949 return isl_local_div_is_marked_unknown(ls->div, div); 950} 951 952/* Does "ls" have a complete explicit representation for div "div"? 953 */ 954isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div) 955{ 956 if (!ls) 957 return isl_bool_error; 958 return isl_local_div_is_known(ls->div, div); 959} 960 961/* Does "ls" have an explicit representation for all local variables? 962 */ 963isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls) 964{ 965 if (!ls) 966 return isl_bool_error; 967 return isl_local_divs_known(ls->div); 968} 969 970__isl_give isl_local_space *isl_local_space_domain( 971 __isl_take isl_local_space *ls) 972{ 973 isl_size n_out; 974 975 n_out = isl_local_space_dim(ls, isl_dim_out); 976 if (n_out < 0) 977 return isl_local_space_free(ls); 978 ls = isl_local_space_drop_dims(ls, isl_dim_out, 0, n_out); 979 ls = isl_local_space_cow(ls); 980 if (!ls) 981 return NULL; 982 ls->dim = isl_space_domain(ls->dim); 983 if (!ls->dim) 984 return isl_local_space_free(ls); 985 return ls; 986} 987 988__isl_give isl_local_space *isl_local_space_range( 989 __isl_take isl_local_space *ls) 990{ 991 isl_size n_in; 992 993 n_in = isl_local_space_dim(ls, isl_dim_in); 994 if (n_in < 0) 995 return isl_local_space_free(ls); 996 ls = isl_local_space_drop_dims(ls, isl_dim_in, 0, n_in); 997 ls = isl_local_space_cow(ls); 998 if (!ls) 999 return NULL; 1000 1001 ls->dim = isl_space_range(ls->dim); 1002 if (!ls->dim) 1003 return isl_local_space_free(ls); 1004 return ls; 1005} 1006 1007/* Construct a local space for a map that has the given local 1008 * space as domain and that has a zero-dimensional range. 1009 */ 1010__isl_give isl_local_space *isl_local_space_from_domain( 1011 __isl_take isl_local_space *ls) 1012{ 1013 ls = isl_local_space_cow(ls); 1014 if (!ls) 1015 return NULL; 1016 ls->dim = isl_space_from_domain(ls->dim); 1017 if (!ls->dim) 1018 return isl_local_space_free(ls); 1019 return ls; 1020} 1021 1022__isl_give isl_local_space *isl_local_space_add_dims( 1023 __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n) 1024{ 1025 isl_size pos; 1026 1027 pos = isl_local_space_dim(ls, type); 1028 if (pos < 0) 1029 return isl_local_space_free(ls); 1030 return isl_local_space_insert_dims(ls, type, pos, n); 1031} 1032 1033/* Lift the basic set "bset", living in the space of "ls" 1034 * to live in a space with extra coordinates corresponding 1035 * to the local variables of "ls". 1036 */ 1037__isl_give isl_basic_set *isl_local_space_lift_basic_set( 1038 __isl_take isl_local_space *ls, __isl_take isl_basic_set *bset) 1039{ 1040 isl_size n_local; 1041 isl_space *space; 1042 isl_basic_set *ls_bset; 1043 1044 n_local = isl_local_space_dim(ls, isl_dim_div); 1045 space = isl_basic_set_peek_space(bset); 1046 if (n_local < 0 || 1047 isl_local_space_check_has_space(ls, space) < 0) 1048 goto error; 1049 1050 if (n_local == 0) { 1051 isl_local_space_free(ls); 1052 return bset; 1053 } 1054 1055 bset = isl_basic_set_add_dims(bset, isl_dim_set, n_local); 1056 ls_bset = isl_basic_set_from_local_space(ls); 1057 ls_bset = isl_basic_set_lift(ls_bset); 1058 ls_bset = isl_basic_set_flatten(ls_bset); 1059 bset = isl_basic_set_intersect(bset, ls_bset); 1060 1061 return bset; 1062error: 1063 isl_local_space_free(ls); 1064 isl_basic_set_free(bset); 1065 return NULL; 1066} 1067 1068/* Lift the set "set", living in the space of "ls" 1069 * to live in a space with extra coordinates corresponding 1070 * to the local variables of "ls". 1071 */ 1072__isl_give isl_set *isl_local_space_lift_set(__isl_take isl_local_space *ls, 1073 __isl_take isl_set *set) 1074{ 1075 isl_size n_local; 1076 isl_basic_set *bset; 1077 1078 n_local = isl_local_space_dim(ls, isl_dim_div); 1079 if (n_local < 0 || 1080 isl_local_space_check_has_space(ls, isl_set_peek_space(set)) < 0) 1081 goto error; 1082 1083 if (n_local == 0) { 1084 isl_local_space_free(ls); 1085 return set; 1086 } 1087 1088 set = isl_set_add_dims(set, isl_dim_set, n_local); 1089 bset = isl_basic_set_from_local_space(ls); 1090 bset = isl_basic_set_lift(bset); 1091 bset = isl_basic_set_flatten(bset); 1092 set = isl_set_intersect(set, isl_set_from_basic_set(bset)); 1093 1094 return set; 1095error: 1096 isl_local_space_free(ls); 1097 isl_set_free(set); 1098 return NULL; 1099} 1100 1101/* Remove common factor of non-constant terms and denominator. 1102 */ 1103static __isl_give isl_local_space *normalize_div( 1104 __isl_take isl_local_space *ls, int div) 1105{ 1106 isl_ctx *ctx = ls->div->ctx; 1107 unsigned total = ls->div->n_col - 2; 1108 1109 isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd); 1110 isl_int_gcd(ctx->normalize_gcd, 1111 ctx->normalize_gcd, ls->div->row[div][0]); 1112 if (isl_int_is_one(ctx->normalize_gcd)) 1113 return ls; 1114 1115 isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2, 1116 ctx->normalize_gcd, total); 1117 isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0], 1118 ctx->normalize_gcd); 1119 isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1], 1120 ctx->normalize_gcd); 1121 1122 return ls; 1123} 1124 1125/* Exploit the equalities in "eq" to simplify the expressions of 1126 * the integer divisions in "ls". 1127 * The integer divisions in "ls" are assumed to appear as regular 1128 * dimensions in "eq". 1129 */ 1130__isl_give isl_local_space *isl_local_space_substitute_equalities( 1131 __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq) 1132{ 1133 int i, j, k; 1134 isl_size total, dim; 1135 unsigned n_div; 1136 1137 if (!ls || !eq) 1138 goto error; 1139 1140 total = isl_space_dim(eq->dim, isl_dim_all); 1141 dim = isl_local_space_dim(ls, isl_dim_all); 1142 if (dim < 0 || total < 0) 1143 goto error; 1144 if (dim != total) 1145 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 1146 "spaces don't match", goto error); 1147 total++; 1148 n_div = eq->n_div; 1149 for (i = 0; i < eq->n_eq; ++i) { 1150 j = isl_seq_last_non_zero(eq->eq[i], total + n_div); 1151 if (j < 0 || j == 0 || j >= total) 1152 continue; 1153 1154 for (k = 0; k < ls->div->n_row; ++k) { 1155 if (isl_int_is_zero(ls->div->row[k][1 + j])) 1156 continue; 1157 ls = isl_local_space_cow(ls); 1158 if (!ls) 1159 goto error; 1160 ls->div = isl_mat_cow(ls->div); 1161 if (!ls->div) 1162 goto error; 1163 isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total, 1164 &ls->div->row[k][0]); 1165 ls = normalize_div(ls, k); 1166 if (!ls) 1167 goto error; 1168 } 1169 } 1170 1171 isl_basic_set_free(eq); 1172 return ls; 1173error: 1174 isl_basic_set_free(eq); 1175 isl_local_space_free(ls); 1176 return NULL; 1177} 1178 1179/* Plug in the affine expressions "subs" of length "subs_len" (including 1180 * the denominator and the constant term) into the variable at position "pos" 1181 * of the "n" div expressions starting at "first". 1182 * 1183 * Let i be the dimension to replace and let "subs" be of the form 1184 * 1185 * f/d 1186 * 1187 * Any integer division starting at "first" with a non-zero coefficient for i, 1188 * 1189 * floor((a i + g)/m) 1190 * 1191 * is replaced by 1192 * 1193 * floor((a f + d g)/(m d)) 1194 */ 1195__isl_give isl_local_space *isl_local_space_substitute_seq( 1196 __isl_take isl_local_space *ls, 1197 enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len, 1198 int first, int n) 1199{ 1200 int i; 1201 isl_int v; 1202 1203 if (n == 0) 1204 return ls; 1205 ls = isl_local_space_cow(ls); 1206 if (!ls) 1207 return NULL; 1208 ls->div = isl_mat_cow(ls->div); 1209 if (!ls->div) 1210 return isl_local_space_free(ls); 1211 1212 if (first + n > ls->div->n_row) 1213 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 1214 "index out of bounds", return isl_local_space_free(ls)); 1215 1216 pos += isl_local_space_offset(ls, type); 1217 1218 isl_int_init(v); 1219 for (i = first; i < first + n; ++i) { 1220 if (isl_int_is_zero(ls->div->row[i][1 + pos])) 1221 continue; 1222 isl_seq_substitute(ls->div->row[i], pos, subs, 1223 ls->div->n_col, subs_len, v); 1224 ls = normalize_div(ls, i); 1225 if (!ls) 1226 break; 1227 } 1228 isl_int_clear(v); 1229 1230 return ls; 1231} 1232 1233/* Plug in "subs" for dimension "type", "pos" in the integer divisions 1234 * of "ls". 1235 * 1236 * Let i be the dimension to replace and let "subs" be of the form 1237 * 1238 * f/d 1239 * 1240 * Any integer division with a non-zero coefficient for i, 1241 * 1242 * floor((a i + g)/m) 1243 * 1244 * is replaced by 1245 * 1246 * floor((a f + d g)/(m d)) 1247 */ 1248__isl_give isl_local_space *isl_local_space_substitute( 1249 __isl_take isl_local_space *ls, 1250 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs) 1251{ 1252 isl_size n_div; 1253 1254 ls = isl_local_space_cow(ls); 1255 if (!ls || !subs) 1256 return isl_local_space_free(ls); 1257 1258 if (!isl_space_is_equal(ls->dim, subs->ls->dim)) 1259 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 1260 "spaces don't match", return isl_local_space_free(ls)); 1261 n_div = isl_local_space_dim(subs->ls, isl_dim_div); 1262 if (n_div < 0) 1263 return isl_local_space_free(ls); 1264 if (n_div != 0) 1265 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported, 1266 "cannot handle divs yet", 1267 return isl_local_space_free(ls)); 1268 1269 return isl_local_space_substitute_seq(ls, type, pos, subs->v->el, 1270 subs->v->size, 0, ls->div->n_row); 1271} 1272 1273isl_bool isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls, 1274 enum isl_dim_type type) 1275{ 1276 if (!ls) 1277 return isl_bool_error; 1278 return isl_space_is_named_or_nested(ls->dim, type); 1279} 1280 1281__isl_give isl_local_space *isl_local_space_drop_dims( 1282 __isl_take isl_local_space *ls, 1283 enum isl_dim_type type, unsigned first, unsigned n) 1284{ 1285 if (!ls) 1286 return NULL; 1287 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type)) 1288 return ls; 1289 1290 if (isl_local_space_check_range(ls, type, first, n) < 0) 1291 return isl_local_space_free(ls); 1292 1293 ls = isl_local_space_cow(ls); 1294 if (!ls) 1295 return NULL; 1296 1297 if (type == isl_dim_div) { 1298 ls->div = isl_mat_drop_rows(ls->div, first, n); 1299 } else { 1300 ls->dim = isl_space_drop_dims(ls->dim, type, first, n); 1301 if (!ls->dim) 1302 return isl_local_space_free(ls); 1303 } 1304 1305 first += 1 + isl_local_space_offset(ls, type); 1306 ls->div = isl_mat_drop_cols(ls->div, first, n); 1307 if (!ls->div) 1308 return isl_local_space_free(ls); 1309 1310 return ls; 1311} 1312 1313__isl_give isl_local_space *isl_local_space_insert_dims( 1314 __isl_take isl_local_space *ls, 1315 enum isl_dim_type type, unsigned first, unsigned n) 1316{ 1317 if (!ls) 1318 return NULL; 1319 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type)) 1320 return ls; 1321 1322 if (isl_local_space_check_range(ls, type, first, 0) < 0) 1323 return isl_local_space_free(ls); 1324 1325 ls = isl_local_space_cow(ls); 1326 if (!ls) 1327 return NULL; 1328 1329 if (type == isl_dim_div) { 1330 ls->div = isl_mat_insert_zero_rows(ls->div, first, n); 1331 } else { 1332 ls->dim = isl_space_insert_dims(ls->dim, type, first, n); 1333 if (!ls->dim) 1334 return isl_local_space_free(ls); 1335 } 1336 1337 first += 1 + isl_local_space_offset(ls, type); 1338 ls->div = isl_mat_insert_zero_cols(ls->div, first, n); 1339 if (!ls->div) 1340 return isl_local_space_free(ls); 1341 1342 return ls; 1343} 1344 1345/* Does the linear part of "constraint" correspond to 1346 * integer division "div" in "ls"? 1347 * 1348 * That is, given div = floor((c + f)/m), is the constraint of the form 1349 * 1350 * f - m d + c' >= 0 [sign = 1] 1351 * or 1352 * -f + m d + c'' >= 0 [sign = -1] 1353 * ? 1354 * If so, set *sign to the corresponding value. 1355 */ 1356static isl_bool is_linear_div_constraint(__isl_keep isl_local_space *ls, 1357 isl_int *constraint, unsigned div, int *sign) 1358{ 1359 isl_bool unknown; 1360 unsigned pos; 1361 1362 unknown = isl_local_space_div_is_marked_unknown(ls, div); 1363 if (unknown < 0) 1364 return isl_bool_error; 1365 if (unknown) 1366 return isl_bool_false; 1367 1368 pos = isl_local_space_offset(ls, isl_dim_div) + div; 1369 1370 if (isl_int_eq(constraint[pos], ls->div->row[div][0])) { 1371 *sign = -1; 1372 if (!isl_seq_is_neg(constraint + 1, 1373 ls->div->row[div] + 2, pos - 1)) 1374 return isl_bool_false; 1375 } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) { 1376 *sign = 1; 1377 if (!isl_seq_eq(constraint + 1, ls->div->row[div] + 2, pos - 1)) 1378 return isl_bool_false; 1379 } else { 1380 return isl_bool_false; 1381 } 1382 if (isl_seq_first_non_zero(constraint + pos + 1, 1383 ls->div->n_row - div - 1) != -1) 1384 return isl_bool_false; 1385 return isl_bool_true; 1386} 1387 1388/* Check if the constraints pointed to by "constraint" is a div 1389 * constraint corresponding to div "div" in "ls". 1390 * 1391 * That is, if div = floor(f/m), then check if the constraint is 1392 * 1393 * f - m d >= 0 1394 * or 1395 * -(f-(m-1)) + m d >= 0 1396 * 1397 * First check if the linear part is of the right form and 1398 * then check the constant term. 1399 */ 1400isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls, 1401 isl_int *constraint, unsigned div) 1402{ 1403 int sign; 1404 isl_bool linear; 1405 1406 linear = is_linear_div_constraint(ls, constraint, div, &sign); 1407 if (linear < 0 || !linear) 1408 return linear; 1409 1410 if (sign < 0) { 1411 int neg; 1412 isl_int_sub(ls->div->row[div][1], 1413 ls->div->row[div][1], ls->div->row[div][0]); 1414 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1); 1415 neg = isl_seq_is_neg(constraint, ls->div->row[div] + 1, 1); 1416 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1); 1417 isl_int_add(ls->div->row[div][1], 1418 ls->div->row[div][1], ls->div->row[div][0]); 1419 if (!neg) 1420 return isl_bool_false; 1421 } else { 1422 if (!isl_int_eq(constraint[0], ls->div->row[div][1])) 1423 return isl_bool_false; 1424 } 1425 1426 return isl_bool_true; 1427} 1428 1429/* Is the constraint pointed to by "constraint" one 1430 * of an equality that corresponds to integer division "div" in "ls"? 1431 * 1432 * That is, given an integer division of the form 1433 * 1434 * a = floor((f + c)/m) 1435 * 1436 * is the equality of the form 1437 * 1438 * -f + m d + c' = 0 1439 * ? 1440 * Note that the constant term is not checked explicitly, but given 1441 * that this is a valid equality constraint, the constant c' necessarily 1442 * has a value close to -c. 1443 */ 1444isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls, 1445 isl_int *constraint, unsigned div) 1446{ 1447 int sign; 1448 isl_bool linear; 1449 1450 linear = is_linear_div_constraint(ls, constraint, div, &sign); 1451 if (linear < 0 || !linear) 1452 return linear; 1453 1454 return isl_bool_ok(sign < 0); 1455} 1456 1457/* 1458 * Set active[i] to 1 if the dimension at position i is involved 1459 * in the linear expression l. 1460 */ 1461int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l) 1462{ 1463 int i, j; 1464 isl_ctx *ctx; 1465 int *active = NULL; 1466 isl_size total; 1467 unsigned offset; 1468 1469 ctx = isl_local_space_get_ctx(ls); 1470 total = isl_local_space_dim(ls, isl_dim_all); 1471 if (total < 0) 1472 return NULL; 1473 active = isl_calloc_array(ctx, int, total); 1474 if (total && !active) 1475 return NULL; 1476 1477 for (i = 0; i < total; ++i) 1478 active[i] = !isl_int_is_zero(l[i]); 1479 1480 offset = isl_local_space_offset(ls, isl_dim_div) - 1; 1481 for (i = ls->div->n_row - 1; i >= 0; --i) { 1482 if (!active[offset + i]) 1483 continue; 1484 for (j = 0; j < total; ++j) 1485 active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]); 1486 } 1487 1488 return active; 1489} 1490 1491/* Given a local space "ls" of a set, create a local space 1492 * for the lift of the set. In particular, the result 1493 * is of the form [dim -> local[..]], with ls->div->n_row variables in the 1494 * range of the wrapped map. 1495 */ 1496__isl_give isl_local_space *isl_local_space_lift( 1497 __isl_take isl_local_space *ls) 1498{ 1499 ls = isl_local_space_cow(ls); 1500 if (!ls) 1501 return NULL; 1502 1503 ls->dim = isl_space_lift(ls->dim, ls->div->n_row); 1504 ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row); 1505 if (!ls->dim || !ls->div) 1506 return isl_local_space_free(ls); 1507 1508 return ls; 1509} 1510 1511/* Construct a basic map that maps a set living in local space "ls" 1512 * to the corresponding lifted local space. 1513 */ 1514__isl_give isl_basic_map *isl_local_space_lifting( 1515 __isl_take isl_local_space *ls) 1516{ 1517 isl_basic_map *lifting; 1518 isl_basic_set *bset; 1519 1520 if (!ls) 1521 return NULL; 1522 if (!isl_local_space_is_set(ls)) 1523 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 1524 "lifting only defined on set spaces", goto error); 1525 1526 bset = isl_basic_set_from_local_space(ls); 1527 lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset)); 1528 lifting = isl_basic_map_domain_map(lifting); 1529 lifting = isl_basic_map_reverse(lifting); 1530 1531 return lifting; 1532error: 1533 isl_local_space_free(ls); 1534 return NULL; 1535} 1536 1537/* Compute the preimage of "ls" under the function represented by "ma". 1538 * In other words, plug in "ma" in "ls". The result is a local space 1539 * that is part of the domain space of "ma". 1540 * 1541 * If the divs in "ls" are represented as 1542 * 1543 * floor((a_i(p) + b_i x + c_i(divs))/n_i) 1544 * 1545 * and ma is represented by 1546 * 1547 * x = D(p) + F(y) + G(divs') 1548 * 1549 * then the resulting divs are 1550 * 1551 * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i) 1552 * 1553 * We first copy over the divs from "ma" and then 1554 * we add the modified divs from "ls". 1555 */ 1556__isl_give isl_local_space *isl_local_space_preimage_multi_aff( 1557 __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma) 1558{ 1559 int i; 1560 isl_space *space; 1561 isl_local_space *res = NULL; 1562 isl_size n_div_ls, n_div_ma; 1563 isl_int f, c1, c2, g; 1564 1565 ma = isl_multi_aff_align_divs(ma); 1566 if (!ls || !ma) 1567 goto error; 1568 if (!isl_space_is_range_internal(ls->dim, ma->space)) 1569 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 1570 "spaces don't match", goto error); 1571 1572 n_div_ls = isl_local_space_dim(ls, isl_dim_div); 1573 n_div_ma = ma->n ? isl_aff_dim(ma->u.p[0], isl_dim_div) : 0; 1574 if (n_div_ls < 0 || n_div_ma < 0) 1575 goto error; 1576 1577 space = isl_space_domain(isl_multi_aff_get_space(ma)); 1578 res = isl_local_space_alloc(space, n_div_ma + n_div_ls); 1579 if (!res) 1580 goto error; 1581 1582 if (n_div_ma) { 1583 isl_mat_free(res->div); 1584 res->div = isl_mat_copy(ma->u.p[0]->ls->div); 1585 res->div = isl_mat_add_zero_cols(res->div, n_div_ls); 1586 res->div = isl_mat_add_rows(res->div, n_div_ls); 1587 if (!res->div) 1588 goto error; 1589 } 1590 1591 isl_int_init(f); 1592 isl_int_init(c1); 1593 isl_int_init(c2); 1594 isl_int_init(g); 1595 1596 for (i = 0; i < ls->div->n_row; ++i) { 1597 if (isl_int_is_zero(ls->div->row[i][0])) { 1598 isl_int_set_si(res->div->row[n_div_ma + i][0], 0); 1599 continue; 1600 } 1601 if (isl_seq_preimage(res->div->row[n_div_ma + i], 1602 ls->div->row[i], 1603 ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1) < 0) 1604 res = isl_local_space_free(res); 1605 res = normalize_div(res, n_div_ma + i); 1606 if (!res) 1607 break; 1608 } 1609 1610 isl_int_clear(f); 1611 isl_int_clear(c1); 1612 isl_int_clear(c2); 1613 isl_int_clear(g); 1614 1615 isl_local_space_free(ls); 1616 isl_multi_aff_free(ma); 1617 return res; 1618error: 1619 isl_local_space_free(ls); 1620 isl_multi_aff_free(ma); 1621 isl_local_space_free(res); 1622 return NULL; 1623} 1624 1625/* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls" 1626 * to dimensions of "dst_type" at "dst_pos". 1627 * 1628 * Moving to/from local dimensions is not allowed. 1629 * We currently assume that the dimension type changes. 1630 */ 1631__isl_give isl_local_space *isl_local_space_move_dims( 1632 __isl_take isl_local_space *ls, 1633 enum isl_dim_type dst_type, unsigned dst_pos, 1634 enum isl_dim_type src_type, unsigned src_pos, unsigned n) 1635{ 1636 isl_space *space; 1637 isl_local *local; 1638 isl_size v_src, v_dst; 1639 unsigned g_dst_pos; 1640 unsigned g_src_pos; 1641 1642 if (!ls) 1643 return NULL; 1644 if (n == 0 && 1645 !isl_local_space_is_named_or_nested(ls, src_type) && 1646 !isl_local_space_is_named_or_nested(ls, dst_type)) 1647 return ls; 1648 1649 if (isl_local_space_check_range(ls, src_type, src_pos, n) < 0) 1650 return isl_local_space_free(ls); 1651 if (isl_local_space_check_range(ls, dst_type, dst_pos, 0) < 0) 1652 return isl_local_space_free(ls); 1653 if (src_type == isl_dim_div) 1654 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 1655 "cannot move divs", return isl_local_space_free(ls)); 1656 if (dst_type == isl_dim_div) 1657 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, 1658 "cannot move to divs", return isl_local_space_free(ls)); 1659 if (dst_type == src_type && dst_pos == src_pos) 1660 return ls; 1661 if (dst_type == src_type) 1662 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported, 1663 "moving dims within the same type not supported", 1664 return isl_local_space_free(ls)); 1665 1666 v_src = isl_local_space_var_offset(ls, src_type); 1667 v_dst = isl_local_space_var_offset(ls, dst_type); 1668 if (v_src < 0 || v_dst < 0) 1669 return isl_local_space_free(ls); 1670 g_src_pos = v_src + src_pos; 1671 g_dst_pos = v_dst + dst_pos; 1672 if (dst_type > src_type) 1673 g_dst_pos -= n; 1674 1675 local = isl_local_space_take_local(ls); 1676 local = isl_local_move_vars(local, g_dst_pos, g_src_pos, n); 1677 ls = isl_local_space_restore_local(ls, local); 1678 1679 space = isl_local_space_take_space(ls); 1680 space = isl_space_move_dims(space, dst_type, dst_pos, 1681 src_type, src_pos, n); 1682 ls = isl_local_space_restore_space(ls, space); 1683 1684 return ls; 1685} 1686 1687/* Given a local space (A -> B), return the corresponding local space 1688 * (B -> A). 1689 */ 1690__isl_give isl_local_space *isl_local_space_wrapped_reverse( 1691 __isl_take isl_local_space *ls) 1692{ 1693 isl_space *space; 1694 isl_local *local; 1695 isl_size n_in, n_out; 1696 unsigned offset; 1697 1698 space = isl_local_space_peek_space(ls); 1699 offset = isl_space_offset(space, isl_dim_set); 1700 n_in = isl_space_wrapped_dim(space, isl_dim_set, isl_dim_in); 1701 n_out = isl_space_wrapped_dim(space, isl_dim_set, isl_dim_out); 1702 if (offset < 0 || n_in < 0 || n_out < 0) 1703 return isl_local_space_free(ls); 1704 1705 space = isl_local_space_take_space(ls); 1706 space = isl_space_wrapped_reverse(space); 1707 ls = isl_local_space_restore_space(ls, space); 1708 1709 local = isl_local_space_take_local(ls); 1710 local = isl_local_move_vars(local, offset, offset + n_in, n_out); 1711 ls = isl_local_space_restore_local(ls, local); 1712 1713 return ls; 1714} 1715 1716/* Remove any internal structure of the domain of "ls". 1717 * If there is any such internal structure in the input, 1718 * then the name of the corresponding space is also removed. 1719 */ 1720__isl_give isl_local_space *isl_local_space_flatten_domain( 1721 __isl_take isl_local_space *ls) 1722{ 1723 if (!ls) 1724 return NULL; 1725 1726 if (!ls->dim->nested[0]) 1727 return ls; 1728 1729 ls = isl_local_space_cow(ls); 1730 if (!ls) 1731 return NULL; 1732 1733 ls->dim = isl_space_flatten_domain(ls->dim); 1734 if (!ls->dim) 1735 return isl_local_space_free(ls); 1736 1737 return ls; 1738} 1739 1740/* Remove any internal structure of the range of "ls". 1741 * If there is any such internal structure in the input, 1742 * then the name of the corresponding space is also removed. 1743 */ 1744__isl_give isl_local_space *isl_local_space_flatten_range( 1745 __isl_take isl_local_space *ls) 1746{ 1747 if (!ls) 1748 return NULL; 1749 1750 if (!ls->dim->nested[1]) 1751 return ls; 1752 1753 ls = isl_local_space_cow(ls); 1754 if (!ls) 1755 return NULL; 1756 1757 ls->dim = isl_space_flatten_range(ls->dim); 1758 if (!ls->dim) 1759 return isl_local_space_free(ls); 1760 1761 return ls; 1762} 1763 1764/* Given the local space "ls" of a map, return the local space of a set 1765 * that lives in a space that wraps the space of "ls" and that has 1766 * the same divs. 1767 */ 1768__isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls) 1769{ 1770 ls = isl_local_space_cow(ls); 1771 if (!ls) 1772 return NULL; 1773 1774 ls->dim = isl_space_wrap(ls->dim); 1775 if (!ls->dim) 1776 return isl_local_space_free(ls); 1777 1778 return ls; 1779} 1780 1781/* Lift the point "pnt", living in the (set) space of "ls" 1782 * to live in a space with extra coordinates corresponding 1783 * to the local variables of "ls". 1784 */ 1785__isl_give isl_point *isl_local_space_lift_point(__isl_take isl_local_space *ls, 1786 __isl_take isl_point *pnt) 1787{ 1788 isl_size n_local; 1789 isl_space *space; 1790 isl_local *local; 1791 isl_vec *vec; 1792 1793 if (isl_local_space_check_has_space(ls, isl_point_peek_space(pnt)) < 0) 1794 goto error; 1795 1796 local = isl_local_space_peek_local(ls); 1797 n_local = isl_local_space_dim(ls, isl_dim_div); 1798 if (n_local < 0) 1799 goto error; 1800 1801 space = isl_point_take_space(pnt); 1802 vec = isl_point_take_vec(pnt); 1803 1804 space = isl_space_lift(space, n_local); 1805 vec = isl_local_extend_point_vec(local, vec); 1806 1807 pnt = isl_point_restore_vec(pnt, vec); 1808 pnt = isl_point_restore_space(pnt, space); 1809 1810 isl_local_space_free(ls); 1811 1812 return pnt; 1813error: 1814 isl_local_space_free(ls); 1815 isl_point_free(pnt); 1816 return NULL; 1817} 1818 1819/* Do any of the local variables in "ls" depend on the specified dimensions? 1820 */ 1821isl_bool isl_local_space_involves_dims(__isl_keep isl_local_space *ls, 1822 enum isl_dim_type type, unsigned first, unsigned n) 1823{ 1824 isl_local *local; 1825 isl_size off; 1826 1827 off = isl_local_space_var_offset(ls, type); 1828 if (off < 0 || isl_local_space_check_range(ls, type, first, n) < 0) 1829 return isl_bool_error; 1830 1831 local = isl_local_space_peek_local(ls); 1832 return isl_local_involves_vars(local, off + first, n); 1833} 1834