isl_aff_map.c

   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  */
  29 static 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  */
  45 static 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  */
  64 static __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;
 101 error:
 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;
 166 error:
 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  */
 176 static __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  */
 434 static __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;
 469 error:
 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  */
 516 static 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  */
 553 static 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;
 587 error:
 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 }