1 /* 2 * Copyright 2010-2011 INRIA Saclay 3 * Copyright 2014 Ecole Normale Superieure 4 * 5 * Use of this software is governed by the MIT license 6 * 7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, 8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, 9 * 91893 Orsay, France 10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France 11 */ 12 13 #include <isl_map_private.h> 14 #include <isl_aff_private.h> 15 #include <isl_morph.h> 16 #include <isl_seq.h> 17 #include <isl_mat_private.h> 18 #include <isl_space_private.h> 19 #include <isl_equalities.h> 20 #include <isl_id_private.h> 21 #include <isl_aff_private.h> 22 #include <isl_vec_private.h> 23 24 isl_ctx *isl_morph_get_ctx(__isl_keep isl_morph *morph) 25 { 26 if (!morph) 27 return NULL; 28 return isl_basic_set_get_ctx(morph->dom); 29 } 30 31 __isl_give isl_morph *isl_morph_alloc( 32 __isl_take isl_basic_set *dom, __isl_take isl_basic_set *ran, 33 __isl_take isl_mat *map, __isl_take isl_mat *inv) 34 { 35 isl_morph *morph; 36 37 if (!dom || !ran || !map || !inv) 38 goto error; 39 40 morph = isl_alloc_type(dom->ctx, struct isl_morph); 41 if (!morph) 42 goto error; 43 44 morph->ref = 1; 45 morph->dom = dom; 46 morph->ran = ran; 47 morph->map = map; 48 morph->inv = inv; 49 50 return morph; 51 error: 52 isl_basic_set_free(dom); 53 isl_basic_set_free(ran); 54 isl_mat_free(map); 55 isl_mat_free(inv); 56 return NULL; 57 } 58 59 __isl_give isl_morph *isl_morph_copy(__isl_keep isl_morph *morph) 60 { 61 if (!morph) 62 return NULL; 63 64 morph->ref++; 65 return morph; 66 } 67 68 __isl_give isl_morph *isl_morph_dup(__isl_keep isl_morph *morph) 69 { 70 if (!morph) 71 return NULL; 72 73 return isl_morph_alloc(isl_basic_set_copy(morph->dom), 74 isl_basic_set_copy(morph->ran), 75 isl_mat_copy(morph->map), isl_mat_copy(morph->inv)); 76 } 77 78 __isl_give isl_morph *isl_morph_cow(__isl_take isl_morph *morph) 79 { 80 if (!morph) 81 return NULL; 82 83 if (morph->ref == 1) 84 return morph; 85 morph->ref--; 86 return isl_morph_dup(morph); 87 } 88 89 __isl_null isl_morph *isl_morph_free(__isl_take isl_morph *morph) 90 { 91 if (!morph) 92 return NULL; 93 94 if (--morph->ref > 0) 95 return NULL; 96 97 isl_basic_set_free(morph->dom); 98 isl_basic_set_free(morph->ran); 99 isl_mat_free(morph->map); 100 isl_mat_free(morph->inv); 101 free(morph); 102 103 return NULL; 104 } 105 106 /* Is "morph" an identity on the parameters? 107 */ 108 static isl_bool identity_on_parameters(__isl_keep isl_morph *morph) 109 { 110 isl_bool is_identity; 111 isl_size nparam, nparam_ran; 112 isl_mat *sub; 113 114 nparam = isl_morph_dom_dim(morph, isl_dim_param); 115 nparam_ran = isl_morph_ran_dim(morph, isl_dim_param); 116 if (nparam < 0 || nparam_ran < 0) 117 return isl_bool_error; 118 if (nparam != nparam_ran) 119 return isl_bool_false; 120 if (nparam == 0) 121 return isl_bool_true; 122 sub = isl_mat_sub_alloc(morph->map, 0, 1 + nparam, 0, 1 + nparam); 123 is_identity = isl_mat_is_scaled_identity(sub); 124 isl_mat_free(sub); 125 126 return is_identity; 127 } 128 129 /* Return an affine expression of the variables of the range of "morph" 130 * in terms of the parameters and the variables of the domain on "morph". 131 * 132 * In order for the space manipulations to make sense, we require 133 * that the parameters are not modified by "morph". 134 */ 135 __isl_give isl_multi_aff *isl_morph_get_var_multi_aff( 136 __isl_keep isl_morph *morph) 137 { 138 isl_space *dom, *ran, *space; 139 isl_local_space *ls; 140 isl_multi_aff *ma; 141 isl_size nparam, nvar; 142 int i; 143 isl_bool is_identity; 144 145 if (!morph) 146 return NULL; 147 148 is_identity = identity_on_parameters(morph); 149 if (is_identity < 0) 150 return NULL; 151 if (!is_identity) 152 isl_die(isl_morph_get_ctx(morph), isl_error_invalid, 153 "cannot handle parameter compression", return NULL); 154 155 dom = isl_morph_get_dom_space(morph); 156 ls = isl_local_space_from_space(isl_space_copy(dom)); 157 ran = isl_morph_get_ran_space(morph); 158 space = isl_space_map_from_domain_and_range(dom, ran); 159 ma = isl_multi_aff_zero(space); 160 161 nparam = isl_multi_aff_dim(ma, isl_dim_param); 162 nvar = isl_multi_aff_dim(ma, isl_dim_out); 163 if (nparam < 0 || nvar < 0) 164 ma = isl_multi_aff_free(ma); 165 for (i = 0; i < nvar; ++i) { 166 isl_val *val; 167 isl_vec *v; 168 isl_aff *aff; 169 170 v = isl_mat_get_row(morph->map, 1 + nparam + i); 171 v = isl_vec_insert_els(v, 0, 1); 172 val = isl_mat_get_element_val(morph->map, 0, 0); 173 v = isl_vec_set_element_val(v, 0, val); 174 aff = isl_aff_alloc_vec(isl_local_space_copy(ls), v); 175 ma = isl_multi_aff_set_aff(ma, i, aff); 176 } 177 178 isl_local_space_free(ls); 179 return ma; 180 } 181 182 /* Return the domain space of "morph". 183 */ 184 static __isl_keep isl_space *isl_morph_peek_dom_space( 185 __isl_keep isl_morph *morph) 186 { 187 if (!morph) 188 return NULL; 189 190 return isl_basic_set_peek_space(morph->dom); 191 } 192 193 /* Return a copy of the domain space of "morph". 194 */ 195 __isl_give isl_space *isl_morph_get_dom_space(__isl_keep isl_morph *morph) 196 { 197 return isl_space_copy(isl_morph_peek_dom_space(morph)); 198 } 199 200 /* Check that the match against "space" with result "match" was successful. 201 */ 202 static isl_stat check_space_match(__isl_keep isl_space *space, isl_bool match) 203 { 204 if (match < 0) 205 return isl_stat_error; 206 if (!match) 207 isl_die(isl_space_get_ctx(space), isl_error_invalid, 208 "spaces don't match", return isl_stat_error); 209 210 return isl_stat_ok; 211 } 212 213 /* Check that "morph" can be applied to the "space". 214 */ 215 isl_stat isl_morph_check_applies(__isl_keep isl_morph *morph, 216 __isl_keep isl_space *space) 217 { 218 isl_space *dom_space; 219 isl_bool applies; 220 221 dom_space = isl_morph_peek_dom_space(morph); 222 applies = isl_space_is_equal(dom_space, space); 223 return check_space_match(space, applies); 224 } 225 226 __isl_give isl_space *isl_morph_get_ran_space(__isl_keep isl_morph *morph) 227 { 228 if (!morph) 229 return NULL; 230 231 return isl_space_copy(morph->ran->dim); 232 } 233 234 isl_size isl_morph_dom_dim(__isl_keep isl_morph *morph, enum isl_dim_type type) 235 { 236 if (!morph) 237 return isl_size_error; 238 239 return isl_basic_set_dim(morph->dom, type); 240 } 241 242 isl_size isl_morph_ran_dim(__isl_keep isl_morph *morph, enum isl_dim_type type) 243 { 244 if (!morph) 245 return isl_size_error; 246 247 return isl_basic_set_dim(morph->ran, type); 248 } 249 250 __isl_give isl_morph *isl_morph_remove_dom_dims(__isl_take isl_morph *morph, 251 enum isl_dim_type type, unsigned first, unsigned n) 252 { 253 isl_size dom_offset; 254 255 if (n == 0) 256 return morph; 257 258 morph = isl_morph_cow(morph); 259 if (!morph) 260 return NULL; 261 262 dom_offset = isl_space_offset(morph->dom->dim, type); 263 if (dom_offset < 0) 264 return isl_morph_free(morph); 265 266 morph->dom = isl_basic_set_remove_dims(morph->dom, type, first, n); 267 268 morph->map = isl_mat_drop_cols(morph->map, 1 + dom_offset + first, n); 269 270 morph->inv = isl_mat_drop_rows(morph->inv, 1 + dom_offset + first, n); 271 272 if (morph->dom && morph->ran && morph->map && morph->inv) 273 return morph; 274 275 isl_morph_free(morph); 276 return NULL; 277 } 278 279 __isl_give isl_morph *isl_morph_remove_ran_dims(__isl_take isl_morph *morph, 280 enum isl_dim_type type, unsigned first, unsigned n) 281 { 282 isl_size ran_offset; 283 284 if (n == 0) 285 return morph; 286 287 morph = isl_morph_cow(morph); 288 if (!morph) 289 return NULL; 290 291 ran_offset = isl_space_offset(morph->ran->dim, type); 292 if (ran_offset < 0) 293 return isl_morph_free(morph); 294 295 morph->ran = isl_basic_set_remove_dims(morph->ran, type, first, n); 296 297 morph->map = isl_mat_drop_rows(morph->map, 1 + ran_offset + first, n); 298 299 morph->inv = isl_mat_drop_cols(morph->inv, 1 + ran_offset + first, n); 300 301 if (morph->dom && morph->ran && morph->map && morph->inv) 302 return morph; 303 304 isl_morph_free(morph); 305 return NULL; 306 } 307 308 /* Project domain of morph onto its parameter domain. 309 */ 310 __isl_give isl_morph *isl_morph_dom_params(__isl_take isl_morph *morph) 311 { 312 isl_size n; 313 314 morph = isl_morph_cow(morph); 315 if (!morph) 316 return NULL; 317 n = isl_basic_set_dim(morph->dom, isl_dim_set); 318 if (n < 0) 319 return isl_morph_free(morph); 320 morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, n); 321 if (!morph) 322 return NULL; 323 morph->dom = isl_basic_set_params(morph->dom); 324 if (morph->dom) 325 return morph; 326 327 isl_morph_free(morph); 328 return NULL; 329 } 330 331 /* Project range of morph onto its parameter domain. 332 */ 333 __isl_give isl_morph *isl_morph_ran_params(__isl_take isl_morph *morph) 334 { 335 isl_size n; 336 337 morph = isl_morph_cow(morph); 338 if (!morph) 339 return NULL; 340 n = isl_basic_set_dim(morph->ran, isl_dim_set); 341 if (n < 0) 342 return isl_morph_free(morph); 343 morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, n); 344 if (!morph) 345 return NULL; 346 morph->ran = isl_basic_set_params(morph->ran); 347 if (morph->ran) 348 return morph; 349 350 isl_morph_free(morph); 351 return NULL; 352 } 353 354 /* Replace the identifier of the tuple of the range of the morph by "id". 355 */ 356 static __isl_give isl_morph *isl_morph_set_ran_tuple_id( 357 __isl_take isl_morph *morph, __isl_keep isl_id *id) 358 { 359 morph = isl_morph_cow(morph); 360 if (!morph) 361 return NULL; 362 morph->ran = isl_basic_set_set_tuple_id(morph->ran, isl_id_copy(id)); 363 if (!morph->ran) 364 return isl_morph_free(morph); 365 return morph; 366 } 367 368 void isl_morph_print_internal(__isl_take isl_morph *morph, FILE *out) 369 { 370 if (!morph) 371 return; 372 373 isl_basic_set_dump(morph->dom); 374 isl_basic_set_dump(morph->ran); 375 isl_mat_print_internal(morph->map, out, 4); 376 isl_mat_print_internal(morph->inv, out, 4); 377 } 378 379 void isl_morph_dump(__isl_take isl_morph *morph) 380 { 381 isl_morph_print_internal(morph, stderr); 382 } 383 384 __isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_set *bset) 385 { 386 isl_mat *id; 387 isl_basic_set *universe; 388 isl_size total; 389 390 total = isl_basic_set_dim(bset, isl_dim_all); 391 if (total < 0) 392 return NULL; 393 394 id = isl_mat_identity(bset->ctx, 1 + total); 395 universe = isl_basic_set_universe(isl_space_copy(bset->dim)); 396 397 return isl_morph_alloc(universe, isl_basic_set_copy(universe), 398 id, isl_mat_copy(id)); 399 } 400 401 /* Create a(n identity) morphism between empty sets of the same dimension 402 * a "bset". 403 */ 404 __isl_give isl_morph *isl_morph_empty(__isl_keep isl_basic_set *bset) 405 { 406 isl_mat *id; 407 isl_basic_set *empty; 408 isl_size total; 409 410 total = isl_basic_set_dim(bset, isl_dim_all); 411 if (total < 0) 412 return NULL; 413 414 id = isl_mat_identity(bset->ctx, 1 + total); 415 empty = isl_basic_set_empty(isl_space_copy(bset->dim)); 416 417 return isl_morph_alloc(empty, isl_basic_set_copy(empty), 418 id, isl_mat_copy(id)); 419 } 420 421 /* Construct a basic set described by the "n" equalities of "bset" starting 422 * at "first". 423 */ 424 static __isl_give isl_basic_set *copy_equalities(__isl_keep isl_basic_set *bset, 425 unsigned first, unsigned n) 426 { 427 int i, k; 428 isl_basic_set *eq; 429 isl_size total; 430 431 total = isl_basic_set_dim(bset, isl_dim_all); 432 if (total < 0 || isl_basic_set_check_no_locals(bset) < 0) 433 return NULL; 434 435 eq = isl_basic_set_alloc_space(isl_basic_set_get_space(bset), 0, n, 0); 436 if (!eq) 437 return NULL; 438 for (i = 0; i < n; ++i) { 439 k = isl_basic_set_alloc_equality(eq); 440 if (k < 0) 441 goto error; 442 isl_seq_cpy(eq->eq[k], bset->eq[first + i], 1 + total); 443 } 444 445 return eq; 446 error: 447 isl_basic_set_free(eq); 448 return NULL; 449 } 450 451 /* Given a basic set, exploit the equalities in the basic set to construct 452 * a morphism that maps the basic set to a lower-dimensional space. 453 * Specifically, the morphism reduces the number of dimensions of type "type". 454 * 455 * We first select the equalities of interest, that is those that involve 456 * variables of type "type" and no later variables. 457 * Denote those equalities as 458 * 459 * -C(p) + M x = 0 460 * 461 * where C(p) depends on the parameters if type == isl_dim_set and 462 * is a constant if type == isl_dim_param. 463 * 464 * Use isl_mat_final_variable_compression to construct a compression 465 * 466 * x = T x' 467 * 468 * x' = Q x 469 * 470 * If T is a zero-column matrix, then the set of equality constraints 471 * do not admit a solution. In this case, an empty morphism is returned. 472 * 473 * Both matrices are extended to map the full original space to the full 474 * compressed space. 475 */ 476 __isl_give isl_morph *isl_basic_set_variable_compression( 477 __isl_keep isl_basic_set *bset, enum isl_dim_type type) 478 { 479 unsigned otype; 480 isl_size ntype; 481 unsigned orest; 482 unsigned nrest; 483 isl_size total; 484 int f_eq, n_eq; 485 isl_space *space; 486 isl_mat *E, *Q, *C; 487 isl_basic_set *dom, *ran; 488 489 if (!bset) 490 return NULL; 491 492 if (isl_basic_set_plain_is_empty(bset)) 493 return isl_morph_empty(bset); 494 495 if (isl_basic_set_check_no_locals(bset) < 0) 496 return NULL; 497 498 ntype = isl_basic_set_dim(bset, type); 499 total = isl_basic_set_dim(bset, isl_dim_all); 500 if (ntype < 0 || total < 0) 501 return NULL; 502 otype = isl_basic_set_offset(bset, type); 503 orest = otype + ntype; 504 nrest = total - (orest - 1); 505 506 for (f_eq = 0; f_eq < bset->n_eq; ++f_eq) 507 if (isl_seq_first_non_zero(bset->eq[f_eq] + orest, nrest) == -1) 508 break; 509 for (n_eq = 0; f_eq + n_eq < bset->n_eq; ++n_eq) 510 if (isl_seq_first_non_zero(bset->eq[f_eq + n_eq] + otype, ntype) == -1) 511 break; 512 if (n_eq == 0) 513 return isl_morph_identity(bset); 514 515 E = isl_mat_sub_alloc6(bset->ctx, bset->eq, f_eq, n_eq, 0, orest); 516 C = isl_mat_final_variable_compression(E, otype - 1, &Q); 517 if (!Q) 518 C = isl_mat_free(C); 519 if (C && C->n_col == 0) { 520 isl_mat_free(C); 521 isl_mat_free(Q); 522 return isl_morph_empty(bset); 523 } 524 525 Q = isl_mat_diagonal(Q, isl_mat_identity(bset->ctx, nrest)); 526 C = isl_mat_diagonal(C, isl_mat_identity(bset->ctx, nrest)); 527 528 space = isl_space_copy(bset->dim); 529 space = isl_space_drop_dims(space, type, 0, ntype); 530 space = isl_space_add_dims(space, type, ntype - n_eq); 531 ran = isl_basic_set_universe(space); 532 dom = copy_equalities(bset, f_eq, n_eq); 533 534 return isl_morph_alloc(dom, ran, Q, C); 535 } 536 537 /* Given a basic set, exploit the equalities in the basic set to construct 538 * a morphism that maps the basic set to a lower-dimensional space 539 * with identifier "id". 540 * Specifically, the morphism reduces the number of set dimensions. 541 */ 542 __isl_give isl_morph *isl_basic_set_variable_compression_with_id( 543 __isl_keep isl_basic_set *bset, __isl_keep isl_id *id) 544 { 545 isl_morph *morph; 546 547 morph = isl_basic_set_variable_compression(bset, isl_dim_set); 548 morph = isl_morph_set_ran_tuple_id(morph, id); 549 return morph; 550 } 551 552 /* Construct a parameter compression for "bset". 553 * We basically just call isl_mat_parameter_compression with the right input 554 * and then extend the resulting matrix to include the variables. 555 * 556 * The implementation assumes that "bset" does not have any equalities 557 * that only involve the parameters and that isl_basic_set_gauss has 558 * been applied to "bset". 559 * 560 * Let the equalities be given as 561 * 562 * B(p) + A x = 0. 563 * 564 * We use isl_mat_parameter_compression_ext to compute the compression 565 * 566 * p = T p'. 567 */ 568 __isl_give isl_morph *isl_basic_set_parameter_compression( 569 __isl_keep isl_basic_set *bset) 570 { 571 isl_size nparam; 572 isl_size nvar; 573 isl_size n_div; 574 int n_eq; 575 isl_mat *H, *B; 576 isl_mat *map, *inv; 577 isl_basic_set *dom, *ran; 578 579 if (!bset) 580 return NULL; 581 582 if (isl_basic_set_plain_is_empty(bset)) 583 return isl_morph_empty(bset); 584 if (bset->n_eq == 0) 585 return isl_morph_identity(bset); 586 587 n_eq = bset->n_eq; 588 nparam = isl_basic_set_dim(bset, isl_dim_param); 589 nvar = isl_basic_set_dim(bset, isl_dim_set); 590 n_div = isl_basic_set_dim(bset, isl_dim_div); 591 if (nparam < 0 || nvar < 0 || n_div < 0) 592 return NULL; 593 594 if (isl_seq_first_non_zero(bset->eq[bset->n_eq - 1] + 1 + nparam, 595 nvar + n_div) == -1) 596 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid, 597 "input not allowed to have parameter equalities", 598 return NULL); 599 if (n_eq > nvar + n_div) 600 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid, 601 "input not gaussed", return NULL); 602 603 B = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam); 604 H = isl_mat_sub_alloc6(bset->ctx, bset->eq, 605 0, n_eq, 1 + nparam, nvar + n_div); 606 inv = isl_mat_parameter_compression_ext(B, H); 607 inv = isl_mat_diagonal(inv, isl_mat_identity(bset->ctx, nvar)); 608 map = isl_mat_right_inverse(isl_mat_copy(inv)); 609 610 dom = isl_basic_set_universe(isl_space_copy(bset->dim)); 611 ran = isl_basic_set_universe(isl_space_copy(bset->dim)); 612 613 return isl_morph_alloc(dom, ran, map, inv); 614 } 615 616 /* Construct an isl_multi_aff that corresponds 617 * to the affine transformation matrix "mat" and 618 * that lives in an anonymous space. 619 */ 620 static __isl_give isl_multi_aff *isl_multi_aff_from_aff_mat_anonymous( 621 __isl_take isl_mat *mat) 622 { 623 isl_size n_row, n_col; 624 isl_ctx *ctx; 625 isl_space *space; 626 627 ctx = isl_mat_get_ctx(mat); 628 n_row = isl_mat_rows(mat); 629 n_col = isl_mat_cols(mat); 630 if (n_row < 0 || n_col < 0) 631 space = NULL; 632 else 633 space = isl_space_alloc(ctx, 0, n_col - 1, n_row - 1); 634 635 return isl_multi_aff_from_aff_mat(space, mat); 636 } 637 638 /* Apply the morphism to the basic set. 639 * In particular, compute the preimage of "bset" under the inverse mapping 640 * in morph and intersect with the range of the morphism. 641 * Note that the mapping in morph applies to both parameters and set dimensions, 642 * so the parameters need to be treated as set dimensions during the call 643 * to isl_basic_set_preimage_multi_aff. 644 */ 645 __isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph, 646 __isl_take isl_basic_set *bset) 647 { 648 isl_size n_param; 649 isl_space *space; 650 isl_multi_aff *ma; 651 652 if (!morph || isl_basic_set_check_equal_space(bset, morph->dom) < 0) 653 goto error; 654 n_param = isl_basic_set_dim(morph->dom, isl_dim_param); 655 if (n_param < 0) 656 goto error; 657 658 ma = isl_multi_aff_from_aff_mat_anonymous(isl_mat_copy(morph->inv)); 659 660 bset = isl_basic_set_move_dims(bset, isl_dim_set, 0, 661 isl_dim_param, 0, n_param); 662 bset = isl_basic_set_preimage_multi_aff(bset, ma); 663 space = isl_basic_set_get_space(morph->ran); 664 bset = isl_basic_set_reset_space(bset, space); 665 bset = isl_basic_set_intersect(bset, isl_basic_set_copy(morph->ran)); 666 667 isl_morph_free(morph); 668 return bset; 669 error: 670 isl_morph_free(morph); 671 isl_basic_set_free(bset); 672 return NULL; 673 } 674 675 /* Apply the morphism to the set. 676 * In particular, compute the preimage of "set" under the inverse mapping 677 * in morph and intersect with the range of the morphism. 678 * Note that the mapping in morph applies to both parameters and set dimensions, 679 * so the parameters need to be treated as set dimensions during the call 680 * to isl_set_preimage_multi_aff. 681 */ 682 __isl_give isl_set *isl_morph_set(__isl_take isl_morph *morph, 683 __isl_take isl_set *set) 684 { 685 isl_size n_param; 686 isl_space *space; 687 isl_multi_aff *ma; 688 isl_basic_set *ran; 689 690 if (!morph || isl_set_basic_set_check_equal_space(set, morph->dom) < 0) 691 goto error; 692 n_param = isl_basic_set_dim(morph->dom, isl_dim_param); 693 if (n_param < 0) 694 goto error; 695 696 ma = isl_multi_aff_from_aff_mat_anonymous(isl_mat_copy(morph->inv)); 697 698 set = isl_set_move_dims(set, isl_dim_set, 0, isl_dim_param, 0, n_param); 699 set = isl_set_preimage_multi_aff(set, ma); 700 space = isl_basic_set_get_space(morph->ran); 701 set = isl_set_reset_space(set, space); 702 ran = isl_basic_set_copy(morph->ran); 703 set = isl_set_intersect(set, isl_set_from_basic_set(ran)); 704 705 isl_morph_free(morph); 706 return set; 707 error: 708 isl_set_free(set); 709 isl_morph_free(morph); 710 return NULL; 711 } 712 713 /* Construct a morphism that first does morph2 and then morph1. 714 */ 715 __isl_give isl_morph *isl_morph_compose(__isl_take isl_morph *morph1, 716 __isl_take isl_morph *morph2) 717 { 718 isl_mat *map, *inv; 719 isl_basic_set *dom, *ran; 720 721 if (!morph1 || !morph2) 722 goto error; 723 724 map = isl_mat_product(isl_mat_copy(morph1->map), isl_mat_copy(morph2->map)); 725 inv = isl_mat_product(isl_mat_copy(morph2->inv), isl_mat_copy(morph1->inv)); 726 dom = isl_morph_basic_set(isl_morph_inverse(isl_morph_copy(morph2)), 727 isl_basic_set_copy(morph1->dom)); 728 dom = isl_basic_set_intersect(dom, isl_basic_set_copy(morph2->dom)); 729 ran = isl_morph_basic_set(isl_morph_copy(morph1), 730 isl_basic_set_copy(morph2->ran)); 731 ran = isl_basic_set_intersect(ran, isl_basic_set_copy(morph1->ran)); 732 733 isl_morph_free(morph1); 734 isl_morph_free(morph2); 735 736 return isl_morph_alloc(dom, ran, map, inv); 737 error: 738 isl_morph_free(morph1); 739 isl_morph_free(morph2); 740 return NULL; 741 } 742 743 __isl_give isl_morph *isl_morph_inverse(__isl_take isl_morph *morph) 744 { 745 isl_basic_set *bset; 746 isl_mat *mat; 747 748 morph = isl_morph_cow(morph); 749 if (!morph) 750 return NULL; 751 752 bset = morph->dom; 753 morph->dom = morph->ran; 754 morph->ran = bset; 755 756 mat = morph->map; 757 morph->map = morph->inv; 758 morph->inv = mat; 759 760 return morph; 761 } 762 763 /* We detect all the equalities first to avoid implicit equalities 764 * being discovered during the computations. In particular, 765 * the compression on the variables could expose additional stride 766 * constraints on the parameters. This would result in existentially 767 * quantified variables after applying the resulting morph, which 768 * in turn could break invariants of the calling functions. 769 */ 770 __isl_give isl_morph *isl_basic_set_full_compression( 771 __isl_keep isl_basic_set *bset) 772 { 773 isl_morph *morph, *morph2; 774 775 bset = isl_basic_set_copy(bset); 776 bset = isl_basic_set_detect_equalities(bset); 777 778 morph = isl_basic_set_variable_compression(bset, isl_dim_param); 779 bset = isl_morph_basic_set(isl_morph_copy(morph), bset); 780 781 morph2 = isl_basic_set_parameter_compression(bset); 782 bset = isl_morph_basic_set(isl_morph_copy(morph2), bset); 783 784 morph = isl_morph_compose(morph2, morph); 785 786 morph2 = isl_basic_set_variable_compression(bset, isl_dim_set); 787 isl_basic_set_free(bset); 788 789 morph = isl_morph_compose(morph2, morph); 790 791 return morph; 792 } 793 794 __isl_give isl_vec *isl_morph_vec(__isl_take isl_morph *morph, 795 __isl_take isl_vec *vec) 796 { 797 if (!morph) 798 goto error; 799 800 vec = isl_mat_vec_product(isl_mat_copy(morph->map), vec); 801 802 isl_morph_free(morph); 803 return vec; 804 error: 805 isl_morph_free(morph); 806 isl_vec_free(vec); 807 return NULL; 808 } 809
Indexes created Fri Jun 12 00:25:51 UTC 2026