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 /* Construct a set mapping the parameter domain the multi-affine expression
 232  * to its space, with each dimension in the space equated to the
 233  * corresponding affine expression.
 234  */
 235 __isl_give isl_set *isl_set_from_multi_aff(__isl_take isl_multi_aff *ma)
 236 {
 237         if (check_input_is_set(isl_multi_aff_peek_space(ma)) < 0)
 238                 ma = isl_multi_aff_free(ma);
 239         return isl_map_from_multi_aff_internal(ma);
 240 }
 241
 242 /* Construct a basic map mapping a domain in the given space to
 243  * to an n-dimensional range, with n the number of elements in the list,
 244  * where each coordinate in the range is prescribed by the
 245  * corresponding affine expression.
 246  * The domains of all affine expressions in the list are assumed to match
 247  * domain_space.
 248  */
 249 __isl_give isl_basic_map *isl_basic_map_from_aff_list(
 250         __isl_take isl_space *domain_space, __isl_take isl_aff_list *list)
 251 {
 252         int i;
 253         isl_space *space;
 254         isl_basic_map *bmap;
 255
 256         if (!list)
 257                 return NULL;
 258
 259         space = isl_space_from_domain(domain_space);
 260         bmap = isl_basic_map_universe(space);
 261
 262         for (i = 0; i < list->n; ++i) {
 263                 isl_aff *aff;
 264                 isl_basic_map *bmap_i;
 265
 266                 aff = isl_aff_copy(list->p[i]);
 267                 bmap_i = isl_basic_map_from_aff(aff);
 268
 269                 bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
 270         }
 271
 272         isl_aff_list_free(list);
 273         return bmap;
 274 }
 275
 276 /* Construct a map with as domain the domain of pwaff and
 277  * one-dimensional range corresponding to the affine expressions.
 278  * If "pwaff" lives in a set space, then the result is actually a set.
 279  */
 280 __isl_give isl_map *isl_map_from_pw_aff_internal(__isl_take isl_pw_aff *pwaff)
 281 {
 282         int i;
 283         isl_space *space;
 284         isl_map *map;
 285
 286         if (!pwaff)
 287                 return NULL;
 288
 289         space = isl_pw_aff_get_space(pwaff);
 290         map = isl_map_empty(space);
 291
 292         for (i = 0; i < pwaff->n; ++i) {
 293                 isl_basic_map *bmap;
 294                 isl_map *map_i;
 295
 296                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
 297                 map_i = isl_map_from_basic_map(bmap);
 298                 map_i = isl_map_intersect_domain(map_i,
 299                                                 isl_set_copy(pwaff->p[i].set));
 300                 map = isl_map_union_disjoint(map, map_i);
 301         }
 302
 303         isl_pw_aff_free(pwaff);
 304
 305         return map;
 306 }
 307
 308 /* Construct a map with as domain the domain of pwaff and
 309  * one-dimensional range corresponding to the affine expressions.
 310  */
 311 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
 312 {
 313         if (check_input_is_map(isl_pw_aff_peek_space(pwaff)) < 0)
 314                 pwaff = isl_pw_aff_free(pwaff);
 315         return isl_map_from_pw_aff_internal(pwaff);
 316 }
 317
 318 /* Construct a one-dimensional set with as parameter domain
 319  * the domain of pwaff and the single set dimension
 320  * corresponding to the affine expressions.
 321  */
 322 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
 323 {
 324         if (check_input_is_set(isl_pw_aff_peek_space(pwaff)) < 0)
 325                 pwaff = isl_pw_aff_free(pwaff);
 326         return set_from_map(isl_map_from_pw_aff_internal(pwaff));
 327 }
 328
 329 /* Construct a map mapping the domain of the piecewise multi-affine expression
 330  * to its range, with each dimension in the range equated to the
 331  * corresponding affine expression on its cell.
 332  *
 333  * If the domain of "pma" is rational, then so is the constructed "map".
 334  */
 335 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
 336 {
 337         int i;
 338         isl_map *map;
 339
 340         if (!pma)
 341                 return NULL;
 342
 343         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
 344
 345         for (i = 0; i < pma->n; ++i) {
 346                 isl_bool rational;
 347                 isl_multi_aff *maff;
 348                 isl_basic_map *bmap;
 349                 isl_map *map_i;
 350
 351                 rational = isl_set_is_rational(pma->p[i].set);
 352                 if (rational < 0)
 353                         map = isl_map_free(map);
 354                 maff = isl_multi_aff_copy(pma->p[i].maff);
 355                 bmap = isl_basic_map_from_multi_aff2(maff, rational);
 356                 map_i = isl_map_from_basic_map(bmap);
 357                 map_i = isl_map_intersect_domain(map_i,
 358                                                 isl_set_copy(pma->p[i].set));
 359                 map = isl_map_union_disjoint(map, map_i);
 360         }
 361
 362         isl_pw_multi_aff_free(pma);
 363         return map;
 364 }
 365
 366 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
 367 {
 368         if (check_input_is_set(isl_pw_multi_aff_peek_space(pma)) < 0)
 369                 pma = isl_pw_multi_aff_free(pma);
 370         return set_from_map(isl_map_from_pw_multi_aff(pma));
 371 }
 372
 373 /* Construct a set or map mapping the shared (parameter) domain
 374  * of the piecewise affine expressions to the range of "mpa"
 375  * with each dimension in the range equated to the
 376  * corresponding piecewise affine expression.
 377  */
 378 static __isl_give isl_map *map_from_multi_pw_aff(
 379         __isl_take isl_multi_pw_aff *mpa)
 380 {
 381         int i;
 382         isl_size dim;
 383         isl_space *space;
 384         isl_map *map;
 385
 386         dim = isl_multi_pw_aff_dim(mpa, isl_dim_out);
 387         if (dim < 0)
 388                 goto error;
 389
 390         if (isl_space_dim(mpa->space, isl_dim_out) != mpa->n)
 391                 isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal,
 392                         "invalid space", goto error);
 393
 394         space = isl_multi_pw_aff_get_domain_space(mpa);
 395         map = isl_map_universe(isl_space_from_domain(space));
 396
 397         for (i = 0; i < mpa->n; ++i) {
 398                 isl_pw_aff *pa;
 399                 isl_map *map_i;
 400
 401                 pa = isl_pw_aff_copy(mpa->u.p[i]);
 402                 map_i = isl_map_from_pw_aff_internal(pa);
 403
 404                 map = isl_map_flat_range_product(map, map_i);
 405         }
 406
 407         map = isl_map_reset_space(map, isl_multi_pw_aff_get_space(mpa));
 408
 409         isl_multi_pw_aff_free(mpa);
 410         return map;
 411 error:
 412         isl_multi_pw_aff_free(mpa);
 413         return NULL;
 414 }
 415
 416 /* Construct a map mapping the shared domain
 417  * of the piecewise affine expressions to the range of "mpa"
 418  * with each dimension in the range equated to the
 419  * corresponding piecewise affine expression.
 420  */
 421 __isl_give isl_map *isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
 422 {
 423         if (check_input_is_map(isl_multi_pw_aff_peek_space(mpa)) < 0)
 424                 mpa = isl_multi_pw_aff_free(mpa);
 425         return map_from_multi_pw_aff(mpa);
 426 }
 427
 428 /* Construct a set mapping the shared parameter domain
 429  * of the piecewise affine expressions to the space of "mpa"
 430  * with each dimension in the range equated to the
 431  * corresponding piecewise affine expression.
 432  */
 433 __isl_give isl_set *isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
 434 {
 435         if (check_input_is_set(isl_multi_pw_aff_peek_space(mpa)) < 0)
 436                 mpa = isl_multi_pw_aff_free(mpa);
 437         return set_from_map(map_from_multi_pw_aff(mpa));
 438 }
 439
 440 /* Convert "pa" to an isl_map and add it to *umap.
 441  */
 442 static isl_stat map_from_pw_aff_entry(__isl_take isl_pw_aff *pa, void *user)
 443 {
 444         isl_union_map **umap = user;
 445         isl_map *map;
 446
 447         map = isl_map_from_pw_aff(pa);
 448         *umap = isl_union_map_add_map(*umap, map);
 449
 450         return *umap ? isl_stat_ok : isl_stat_error;
 451 }
 452
 453 /* Construct a union map mapping the domain of the union
 454  * piecewise affine expression to its range, with the single output dimension
 455  * equated to the corresponding affine expressions on their cells.
 456  */
 457 __isl_give isl_union_map *isl_union_map_from_union_pw_aff(
 458         __isl_take isl_union_pw_aff *upa)
 459 {
 460         isl_space *space;
 461         isl_union_map *umap;
 462
 463         if (!upa)
 464                 return NULL;
 465
 466         space = isl_union_pw_aff_get_space(upa);
 467         umap = isl_union_map_empty(space);
 468
 469         if (isl_union_pw_aff_foreach_pw_aff(upa, &map_from_pw_aff_entry,
 470                                                 &umap) < 0)
 471                 umap = isl_union_map_free(umap);
 472
 473         isl_union_pw_aff_free(upa);
 474         return umap;
 475 }
 476
 477 /* Convert "pma" to an isl_map and add it to *umap.
 478  */
 479 static isl_stat map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma,
 480         void *user)
 481 {
 482         isl_union_map **umap = user;
 483         isl_map *map;
 484
 485         map = isl_map_from_pw_multi_aff(pma);
 486         *umap = isl_union_map_add_map(*umap, map);
 487
 488         return isl_stat_ok;
 489 }
 490
 491 /* Construct a union map mapping the domain of the union
 492  * piecewise multi-affine expression to its range, with each dimension
 493  * in the range equated to the corresponding affine expression on its cell.
 494  */
 495 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
 496         __isl_take isl_union_pw_multi_aff *upma)
 497 {
 498         isl_space *space;
 499         isl_union_map *umap;
 500
 501         if (!upma)
 502                 return NULL;
 503
 504         space = isl_union_pw_multi_aff_get_space(upma);
 505         umap = isl_union_map_empty(space);
 506
 507         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
 508                                         &map_from_pw_multi_aff, &umap) < 0)
 509                 goto error;
 510
 511         isl_union_pw_multi_aff_free(upma);
 512         return umap;
 513 error:
 514         isl_union_pw_multi_aff_free(upma);
 515         isl_union_map_free(umap);
 516         return NULL;
 517 }