1/* 2 * Copyright 2011 INRIA Saclay 3 * Copyright 2012-2013 Ecole Normale Superieure 4 * Copyright 2016 Sven Verdoolaege 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 */ 13 14#include <isl/ctx.h> 15#include <isl/space.h> 16#include <isl/local_space.h> 17#include <isl/union_map.h> 18#include <isl_map_private.h> 19#include <isl_aff_private.h> 20#include <isl_vec_private.h> 21#include <isl_seq.h> 22 23#include <bset_from_bmap.c> 24#include <set_from_map.c> 25 26/* Check that the input living in "space" lives in a map space. 27 * That is, check that "space" is a map space. 28 */ 29static isl_stat check_input_is_map(__isl_keep isl_space *space) 30{ 31 isl_bool is_set; 32 33 is_set = isl_space_is_set(space); 34 if (is_set < 0) 35 return isl_stat_error; 36 if (is_set) 37 isl_die(isl_space_get_ctx(space), isl_error_invalid, 38 "space of input is not a map", return isl_stat_error); 39 return isl_stat_ok; 40} 41 42/* Check that the input living in "space" lives in a set space. 43 * That is, check that "space" is a set space. 44 */ 45static isl_stat check_input_is_set(__isl_keep isl_space *space) 46{ 47 isl_bool is_set; 48 49 is_set = isl_space_is_set(space); 50 if (is_set < 0) 51 return isl_stat_error; 52 if (!is_set) 53 isl_die(isl_space_get_ctx(space), isl_error_invalid, 54 "space of input is not a set", return isl_stat_error); 55 return isl_stat_ok; 56} 57 58/* Construct a basic map mapping the domain of the affine expression 59 * to a one-dimensional range prescribed by the affine expression. 60 * If "rational" is set, then construct a rational basic map. 61 * 62 * A NaN affine expression cannot be converted to a basic map. 63 */ 64static __isl_give isl_basic_map *isl_basic_map_from_aff2( 65 __isl_take isl_aff *aff, int rational) 66{ 67 int k; 68 int pos; 69 isl_bool is_nan; 70 isl_local_space *ls; 71 isl_basic_map *bmap = NULL; 72 73 if (!aff) 74 return NULL; 75 is_nan = isl_aff_is_nan(aff); 76 if (is_nan < 0) 77 goto error; 78 if (is_nan) 79 isl_die(isl_aff_get_ctx(aff), isl_error_invalid, 80 "cannot convert NaN", goto error); 81 82 ls = isl_aff_get_local_space(aff); 83 bmap = isl_basic_map_from_local_space(ls); 84 bmap = isl_basic_map_extend_constraints(bmap, 1, 0); 85 k = isl_basic_map_alloc_equality(bmap); 86 if (k < 0) 87 goto error; 88 89 pos = isl_basic_map_offset(bmap, isl_dim_out); 90 isl_seq_cpy(bmap->eq[k], aff->v->el + 1, pos); 91 isl_int_neg(bmap->eq[k][pos], aff->v->el[0]); 92 isl_seq_cpy(bmap->eq[k] + pos + 1, aff->v->el + 1 + pos, 93 aff->v->size - (pos + 1)); 94 95 isl_aff_free(aff); 96 if (rational) 97 bmap = isl_basic_map_set_rational(bmap); 98 bmap = isl_basic_map_gauss(bmap, NULL); 99 bmap = isl_basic_map_finalize(bmap); 100 return bmap; 101error: 102 isl_aff_free(aff); 103 isl_basic_map_free(bmap); 104 return NULL; 105} 106 107/* Construct a basic map mapping the domain of the affine expression 108 * to a one-dimensional range prescribed by the affine expression. 109 */ 110__isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff) 111{ 112 return isl_basic_map_from_aff2(aff, 0); 113} 114 115/* Construct a map mapping the domain of the affine expression 116 * to a one-dimensional range prescribed by the affine expression. 117 */ 118__isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff) 119{ 120 isl_basic_map *bmap; 121 122 bmap = isl_basic_map_from_aff(aff); 123 return isl_map_from_basic_map(bmap); 124} 125 126/* Construct a basic map mapping the domain of the multi-affine expression 127 * to its range, with each dimension in the range equated to the 128 * corresponding affine expression. 129 * If "rational" is set, then construct a rational basic map. 130 */ 131__isl_give isl_basic_map *isl_basic_map_from_multi_aff2( 132 __isl_take isl_multi_aff *maff, int rational) 133{ 134 int i; 135 isl_size dim; 136 isl_space *space; 137 isl_basic_map *bmap; 138 139 dim = isl_multi_aff_dim(maff, isl_dim_out); 140 if (dim < 0) 141 goto error; 142 143 if (dim != maff->n) 144 isl_die(isl_multi_aff_get_ctx(maff), isl_error_internal, 145 "invalid space", goto error); 146 147 space = isl_space_domain(isl_multi_aff_get_space(maff)); 148 bmap = isl_basic_map_universe(isl_space_from_domain(space)); 149 if (rational) 150 bmap = isl_basic_map_set_rational(bmap); 151 152 for (i = 0; i < maff->n; ++i) { 153 isl_aff *aff; 154 isl_basic_map *bmap_i; 155 156 aff = isl_aff_copy(maff->u.p[i]); 157 bmap_i = isl_basic_map_from_aff2(aff, rational); 158 159 bmap = isl_basic_map_flat_range_product(bmap, bmap_i); 160 } 161 162 bmap = isl_basic_map_reset_space(bmap, isl_multi_aff_get_space(maff)); 163 164 isl_multi_aff_free(maff); 165 return bmap; 166error: 167 isl_multi_aff_free(maff); 168 return NULL; 169} 170 171/* Construct a basic map mapping the domain of the multi-affine expression 172 * to its range, with each dimension in the range equated to the 173 * corresponding affine expression. 174 * If "ma" lives in a set space, then the result is actually a set. 175 */ 176static __isl_give isl_basic_map *basic_map_from_multi_aff( 177 __isl_take isl_multi_aff *ma) 178{ 179 return isl_basic_map_from_multi_aff2(ma, 0); 180} 181 182/* Construct a basic map mapping the domain of the multi-affine expression 183 * to its range, with each dimension in the range equated to the 184 * corresponding affine expression. 185 */ 186__isl_give isl_basic_map *isl_basic_map_from_multi_aff( 187 __isl_take isl_multi_aff *ma) 188{ 189 if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0) 190 ma = isl_multi_aff_free(ma); 191 return basic_map_from_multi_aff(ma); 192} 193 194/* Construct a basic set mapping the parameter domain 195 * of the multi-affine expression to its space, with each dimension 196 * in the space equated to the corresponding affine expression. 197 */ 198__isl_give isl_basic_set *isl_basic_set_from_multi_aff( 199 __isl_take isl_multi_aff *ma) 200{ 201 if (check_input_is_set(isl_multi_aff_peek_space(ma)) < 0) 202 ma = isl_multi_aff_free(ma); 203 return bset_from_bmap(basic_map_from_multi_aff(ma)); 204} 205 206/* Construct a map mapping the domain of the multi-affine expression 207 * to its range, with each dimension in the range equated to the 208 * corresponding affine expression. 209 * If "maff" lives in a set space, then the result is actually a set. 210 */ 211__isl_give isl_map *isl_map_from_multi_aff_internal( 212 __isl_take isl_multi_aff *maff) 213{ 214 isl_basic_map *bmap; 215 216 bmap = basic_map_from_multi_aff(maff); 217 return isl_map_from_basic_map(bmap); 218} 219 220/* Construct a map mapping the domain the multi-affine expression 221 * to its range, with each dimension in the range equated to the 222 * corresponding affine expression. 223 */ 224__isl_give isl_map *isl_map_from_multi_aff(__isl_take isl_multi_aff *ma) 225{ 226 if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0) 227 ma = isl_multi_aff_free(ma); 228 return isl_map_from_multi_aff_internal(ma); 229} 230 231/* This function performs the same operation as isl_map_from_multi_aff, 232 * but is considered as a function on an isl_multi_aff when exported. 233 */ 234__isl_give isl_map *isl_multi_aff_as_map(__isl_take isl_multi_aff *ma) 235{ 236 return isl_map_from_multi_aff(ma); 237} 238 239/* Construct a set mapping the parameter domain the multi-affine expression 240 * to its space, with each dimension in the space equated to the 241 * corresponding affine expression. 242 */ 243__isl_give isl_set *isl_set_from_multi_aff(__isl_take isl_multi_aff *ma) 244{ 245 if (check_input_is_set(isl_multi_aff_peek_space(ma)) < 0) 246 ma = isl_multi_aff_free(ma); 247 return isl_map_from_multi_aff_internal(ma); 248} 249 250/* This function performs the same operation as isl_set_from_multi_aff, 251 * but is considered as a function on an isl_multi_aff when exported. 252 */ 253__isl_give isl_set *isl_multi_aff_as_set(__isl_take isl_multi_aff *ma) 254{ 255 return isl_set_from_multi_aff(ma); 256} 257 258/* Construct a basic map mapping a domain in the given space to 259 * to an n-dimensional range, with n the number of elements in the list, 260 * where each coordinate in the range is prescribed by the 261 * corresponding affine expression. 262 * The domains of all affine expressions in the list are assumed to match 263 * domain_space. 264 */ 265__isl_give isl_basic_map *isl_basic_map_from_aff_list( 266 __isl_take isl_space *domain_space, __isl_take isl_aff_list *list) 267{ 268 int i; 269 isl_space *space; 270 isl_basic_map *bmap; 271 272 if (!list) 273 return NULL; 274 275 space = isl_space_from_domain(domain_space); 276 bmap = isl_basic_map_universe(space); 277 278 for (i = 0; i < list->n; ++i) { 279 isl_aff *aff; 280 isl_basic_map *bmap_i; 281 282 aff = isl_aff_copy(list->p[i]); 283 bmap_i = isl_basic_map_from_aff(aff); 284 285 bmap = isl_basic_map_flat_range_product(bmap, bmap_i); 286 } 287 288 isl_aff_list_free(list); 289 return bmap; 290} 291 292/* Construct a map with as domain the domain of pwaff and 293 * one-dimensional range corresponding to the affine expressions. 294 * If "pwaff" lives in a set space, then the result is actually a set. 295 */ 296__isl_give isl_map *isl_map_from_pw_aff_internal(__isl_take isl_pw_aff *pwaff) 297{ 298 int i; 299 isl_space *space; 300 isl_map *map; 301 302 if (!pwaff) 303 return NULL; 304 305 space = isl_pw_aff_get_space(pwaff); 306 map = isl_map_empty(space); 307 308 for (i = 0; i < pwaff->n; ++i) { 309 isl_basic_map *bmap; 310 isl_map *map_i; 311 312 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff)); 313 map_i = isl_map_from_basic_map(bmap); 314 map_i = isl_map_intersect_domain(map_i, 315 isl_set_copy(pwaff->p[i].set)); 316 map = isl_map_union_disjoint(map, map_i); 317 } 318 319 isl_pw_aff_free(pwaff); 320 321 return map; 322} 323 324/* Construct a map with as domain the domain of pwaff and 325 * one-dimensional range corresponding to the affine expressions. 326 */ 327__isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff) 328{ 329 if (check_input_is_map(isl_pw_aff_peek_space(pwaff)) < 0) 330 pwaff = isl_pw_aff_free(pwaff); 331 return isl_map_from_pw_aff_internal(pwaff); 332} 333 334/* This function performs the same operation as isl_map_from_pw_aff, 335 * but is considered as a function on an isl_pw_aff when exported. 336 */ 337__isl_give isl_map *isl_pw_aff_as_map(__isl_take isl_pw_aff *pa) 338{ 339 return isl_map_from_pw_aff(pa); 340} 341 342/* Construct a one-dimensional set with as parameter domain 343 * the domain of pwaff and the single set dimension 344 * corresponding to the affine expressions. 345 */ 346__isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff) 347{ 348 if (check_input_is_set(isl_pw_aff_peek_space(pwaff)) < 0) 349 pwaff = isl_pw_aff_free(pwaff); 350 return set_from_map(isl_map_from_pw_aff_internal(pwaff)); 351} 352 353/* Construct a map mapping the domain of the piecewise multi-affine expression 354 * to its range, with each dimension in the range equated to the 355 * corresponding affine expression on its cell. 356 * If "pma" lives in a set space, then the result is actually a set. 357 * 358 * If the domain of "pma" is rational, then so is the constructed "map". 359 */ 360__isl_give isl_map *isl_map_from_pw_multi_aff_internal( 361 __isl_take isl_pw_multi_aff *pma) 362{ 363 int i; 364 isl_map *map; 365 366 if (!pma) 367 return NULL; 368 369 map = isl_map_empty(isl_pw_multi_aff_get_space(pma)); 370 371 for (i = 0; i < pma->n; ++i) { 372 isl_bool rational; 373 isl_multi_aff *maff; 374 isl_basic_map *bmap; 375 isl_map *map_i; 376 377 rational = isl_set_is_rational(pma->p[i].set); 378 if (rational < 0) 379 map = isl_map_free(map); 380 maff = isl_multi_aff_copy(pma->p[i].maff); 381 bmap = isl_basic_map_from_multi_aff2(maff, rational); 382 map_i = isl_map_from_basic_map(bmap); 383 map_i = isl_map_intersect_domain(map_i, 384 isl_set_copy(pma->p[i].set)); 385 map = isl_map_union_disjoint(map, map_i); 386 } 387 388 isl_pw_multi_aff_free(pma); 389 return map; 390} 391 392/* Construct a map mapping the domain of the piecewise multi-affine expression 393 * to its range, with each dimension in the range equated to the 394 * corresponding affine expression on its cell. 395 */ 396__isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma) 397{ 398 if (check_input_is_map(isl_pw_multi_aff_peek_space(pma)) < 0) 399 pma = isl_pw_multi_aff_free(pma); 400 return isl_map_from_pw_multi_aff_internal(pma); 401} 402 403/* This function performs the same operation as isl_map_from_pw_multi_aff, 404 * but is considered as a function on an isl_pw_multi_aff when exported. 405 */ 406__isl_give isl_map *isl_pw_multi_aff_as_map(__isl_take isl_pw_multi_aff *pma) 407{ 408 return isl_map_from_pw_multi_aff(pma); 409} 410 411__isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma) 412{ 413 if (check_input_is_set(isl_pw_multi_aff_peek_space(pma)) < 0) 414 pma = isl_pw_multi_aff_free(pma); 415 return set_from_map(isl_map_from_pw_multi_aff_internal(pma)); 416} 417 418/* This function performs the same operation as isl_set_from_pw_multi_aff, 419 * but is considered as a function on an isl_pw_multi_aff when exported. 420 */ 421__isl_give isl_set *isl_pw_multi_aff_as_set(__isl_take isl_pw_multi_aff *pma) 422{ 423 return isl_set_from_pw_multi_aff(pma); 424} 425 426/* Construct a set or map mapping the shared (parameter) domain 427 * of the piecewise affine expressions to the range of "mpa" 428 * with each dimension in the range equated to the 429 * corresponding piecewise affine expression. 430 * 431 * If "mpa" has an explicit domain (i.e., it is zero-dimensional), 432 * then return a set or map with the same (parameter) domain. 433 */ 434static __isl_give isl_map *map_from_multi_pw_aff( 435 __isl_take isl_multi_pw_aff *mpa) 436{ 437 int i; 438 isl_size dim; 439 isl_space *space; 440 isl_map *map; 441 442 dim = isl_multi_pw_aff_dim(mpa, isl_dim_out); 443 if (dim < 0) 444 goto error; 445 446 if (isl_space_dim(mpa->space, isl_dim_out) != mpa->n) 447 isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal, 448 "invalid space", goto error); 449 450 space = isl_multi_pw_aff_get_domain_space(mpa); 451 map = isl_map_universe(isl_space_from_domain(space)); 452 453 for (i = 0; i < mpa->n; ++i) { 454 isl_pw_aff *pa; 455 isl_map *map_i; 456 457 pa = isl_pw_aff_copy(mpa->u.p[i]); 458 map_i = isl_map_from_pw_aff_internal(pa); 459 460 map = isl_map_flat_range_product(map, map_i); 461 } 462 463 map = isl_map_reset_space(map, isl_multi_pw_aff_get_space(mpa)); 464 465 map = isl_map_intersect_multi_pw_aff_explicit_domain(map, mpa); 466 467 isl_multi_pw_aff_free(mpa); 468 return map; 469error: 470 isl_multi_pw_aff_free(mpa); 471 return NULL; 472} 473 474/* Construct a map mapping the shared domain 475 * of the piecewise affine expressions to the range of "mpa" 476 * with each dimension in the range equated to the 477 * corresponding piecewise affine expression. 478 */ 479__isl_give isl_map *isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa) 480{ 481 if (check_input_is_map(isl_multi_pw_aff_peek_space(mpa)) < 0) 482 mpa = isl_multi_pw_aff_free(mpa); 483 return map_from_multi_pw_aff(mpa); 484} 485 486/* This function performs the same operation as isl_map_from_multi_pw_aff, 487 * but is considered as a function on an isl_multi_pw_aff when exported. 488 */ 489__isl_give isl_map *isl_multi_pw_aff_as_map(__isl_take isl_multi_pw_aff *mpa) 490{ 491 return isl_map_from_multi_pw_aff(mpa); 492} 493 494/* Construct a set mapping the shared parameter domain 495 * of the piecewise affine expressions to the space of "mpa" 496 * with each dimension in the range equated to the 497 * corresponding piecewise affine expression. 498 */ 499__isl_give isl_set *isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa) 500{ 501 if (check_input_is_set(isl_multi_pw_aff_peek_space(mpa)) < 0) 502 mpa = isl_multi_pw_aff_free(mpa); 503 return set_from_map(map_from_multi_pw_aff(mpa)); 504} 505 506/* This function performs the same operation as isl_set_from_multi_pw_aff, 507 * but is considered as a function on an isl_multi_pw_aff when exported. 508 */ 509__isl_give isl_set *isl_multi_pw_aff_as_set(__isl_take isl_multi_pw_aff *mpa) 510{ 511 return isl_set_from_multi_pw_aff(mpa); 512} 513 514/* Convert "pa" to an isl_map and add it to *umap. 515 */ 516static isl_stat map_from_pw_aff_entry(__isl_take isl_pw_aff *pa, void *user) 517{ 518 isl_union_map **umap = user; 519 isl_map *map; 520 521 map = isl_map_from_pw_aff(pa); 522 *umap = isl_union_map_add_map(*umap, map); 523 524 return *umap ? isl_stat_ok : isl_stat_error; 525} 526 527/* Construct a union map mapping the domain of the union 528 * piecewise affine expression to its range, with the single output dimension 529 * equated to the corresponding affine expressions on their cells. 530 */ 531__isl_give isl_union_map *isl_union_map_from_union_pw_aff( 532 __isl_take isl_union_pw_aff *upa) 533{ 534 isl_space *space; 535 isl_union_map *umap; 536 537 if (!upa) 538 return NULL; 539 540 space = isl_union_pw_aff_get_space(upa); 541 umap = isl_union_map_empty(space); 542 543 if (isl_union_pw_aff_foreach_pw_aff(upa, &map_from_pw_aff_entry, 544 &umap) < 0) 545 umap = isl_union_map_free(umap); 546 547 isl_union_pw_aff_free(upa); 548 return umap; 549} 550 551/* Convert "pma" to an isl_map and add it to *umap. 552 */ 553static isl_stat map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, 554 void *user) 555{ 556 isl_union_map **umap = user; 557 isl_map *map; 558 559 map = isl_map_from_pw_multi_aff(pma); 560 *umap = isl_union_map_add_map(*umap, map); 561 562 return isl_stat_ok; 563} 564 565/* Construct a union map mapping the domain of the union 566 * piecewise multi-affine expression to its range, with each dimension 567 * in the range equated to the corresponding affine expression on its cell. 568 */ 569__isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff( 570 __isl_take isl_union_pw_multi_aff *upma) 571{ 572 isl_space *space; 573 isl_union_map *umap; 574 575 if (!upma) 576 return NULL; 577 578 space = isl_union_pw_multi_aff_get_space(upma); 579 umap = isl_union_map_empty(space); 580 581 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma, 582 &map_from_pw_multi_aff, &umap) < 0) 583 goto error; 584 585 isl_union_pw_multi_aff_free(upma); 586 return umap; 587error: 588 isl_union_pw_multi_aff_free(upma); 589 isl_union_map_free(umap); 590 return NULL; 591} 592 593/* This function performs the same operation as 594 * isl_union_map_from_union_pw_multi_aff, 595 * but is considered as a function on an isl_union_pw_multi_aff when exported. 596 */ 597__isl_give isl_union_map *isl_union_pw_multi_aff_as_union_map( 598 __isl_take isl_union_pw_multi_aff *upma) 599{ 600 return isl_union_map_from_union_pw_multi_aff(upma); 601} 602