602 lines · c
1/*2 * Copyright 2011 INRIA Saclay3 * Copyright 2012-2013 Ecole Normale Superieure4 * Copyright 2016 Sven Verdoolaege5 *6 * Use of this software is governed by the MIT license7 *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, France11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France12 */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 expression59 * 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 expression108 * 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 expression116 * 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 expression127 * to its range, with each dimension in the range equated to the128 * 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 expression172 * to its range, with each dimension in the range equated to the173 * 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 expression183 * to its range, with each dimension in the range equated to the184 * 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 domain195 * of the multi-affine expression to its space, with each dimension196 * 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 expression207 * to its range, with each dimension in the range equated to the208 * 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 expression221 * to its range, with each dimension in the range equated to the222 * 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 expression240 * to its space, with each dimension in the space equated to the241 * 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 to259 * to an n-dimensional range, with n the number of elements in the list,260 * where each coordinate in the range is prescribed by the261 * corresponding affine expression.262 * The domains of all affine expressions in the list are assumed to match263 * 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 and293 * 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 and325 * 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 domain343 * the domain of pwaff and the single set dimension344 * 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 expression354 * to its range, with each dimension in the range equated to the355 * 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 expression393 * to its range, with each dimension in the range equated to the394 * 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) domain427 * of the piecewise affine expressions to the range of "mpa"428 * with each dimension in the range equated to the429 * 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 domain475 * of the piecewise affine expressions to the range of "mpa"476 * with each dimension in the range equated to the477 * 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 domain495 * of the piecewise affine expressions to the space of "mpa"496 * with each dimension in the range equated to the497 * 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 union528 * piecewise affine expression to its range, with the single output dimension529 * 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 union566 * piecewise multi-affine expression to its range, with each dimension567 * 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 as594 * 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