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 <set_from_map.c>
  24
  25 /* Check that the input living in "space" lives in a map space.
  26  * That is, check that "space" is a map space.
  27  */
  28 static isl_stat check_input_is_map(__isl_keep isl_space *space)
  29 {
  30         isl_bool is_set;
  31
  32         is_set = isl_space_is_set(space);
  33         if (is_set < 0)
  34                 return isl_stat_error;
  35         if (is_set)
  36                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
  37                         "space of input is not a map", return isl_stat_error);
  38         return isl_stat_ok;
  39 }
  40
  41 /* Check that the input living in "space" lives in a set space.
  42  * That is, check that "space" is a set space.
  43  */
  44 static isl_stat check_input_is_set(__isl_keep isl_space *space)
  45 {
  46         isl_bool is_set;
  47
  48         is_set = isl_space_is_set(space);
  49         if (is_set < 0)
  50                 return isl_stat_error;
  51         if (!is_set)
  52                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
  53                         "space of input is not a set", return isl_stat_error);
  54         return isl_stat_ok;
  55 }
  56
  57 /* Construct a basic map mapping the domain of the affine expression
  58  * to a one-dimensional range prescribed by the affine expression.
  59  * If "rational" is set, then construct a rational basic map.
  60  *
  61  * A NaN affine expression cannot be converted to a basic map.
  62  */
  63 static __isl_give isl_basic_map *isl_basic_map_from_aff2(
  64         __isl_take isl_aff *aff, int rational)
  65 {
  66         int k;
  67         int pos;
  68         isl_bool is_nan;
  69         isl_local_space *ls;
  70         isl_basic_map *bmap = NULL;
  71
  72         if (!aff)
  73                 return NULL;
  74         is_nan = isl_aff_is_nan(aff);
  75         if (is_nan < 0)
  76                 goto error;
  77         if (is_nan)
  78                 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
  79                         "cannot convert NaN", goto error);
  80
  81         ls = isl_aff_get_local_space(aff);
  82         bmap = isl_basic_map_from_local_space(ls);
  83         bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
  84         k = isl_basic_map_alloc_equality(bmap);
  85         if (k < 0)
  86                 goto error;
  87
  88         pos = isl_basic_map_offset(bmap, isl_dim_out);
  89         isl_seq_cpy(bmap->eq[k], aff->v->el + 1, pos);
  90         isl_int_neg(bmap->eq[k][pos], aff->v->el[0]);
  91         isl_seq_cpy(bmap->eq[k] + pos + 1, aff->v->el + 1 + pos,
  92                     aff->v->size - (pos + 1));
  93
  94         isl_aff_free(aff);
  95         if (rational)
  96                 bmap = isl_basic_map_set_rational(bmap);
  97         bmap = isl_basic_map_gauss(bmap, NULL);
  98         bmap = isl_basic_map_finalize(bmap);
  99         return bmap;
 100 error:
 101         isl_aff_free(aff);
 102         isl_basic_map_free(bmap);
 103         return NULL;
 104 }
 105
 106 /* Construct a basic map mapping the domain of the affine expression
 107  * to a one-dimensional range prescribed by the affine expression.
 108  */
 109 __isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff)
 110 {
 111         return isl_basic_map_from_aff2(aff, 0);
 112 }
 113
 114 /* Construct a map mapping the domain of the affine expression
 115  * to a one-dimensional range prescribed by the affine expression.
 116  */
 117 __isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff)
 118 {
 119         isl_basic_map *bmap;
 120
 121         bmap = isl_basic_map_from_aff(aff);
 122         return isl_map_from_basic_map(bmap);
 123 }
 124
 125 /* Construct a basic map mapping the domain of the multi-affine expression
 126  * to its range, with each dimension in the range equated to the
 127  * corresponding affine expression.
 128  * If "rational" is set, then construct a rational basic map.
 129  */
 130 __isl_give isl_basic_map *isl_basic_map_from_multi_aff2(
 131         __isl_take isl_multi_aff *maff, int rational)
 132 {
 133         int i;
 134         isl_space *space;
 135         isl_basic_map *bmap;
 136
 137         if (!maff)
 138                 return NULL;
 139
 140         if (isl_space_dim(maff->space, isl_dim_out) != maff->n)
 141                 isl_die(isl_multi_aff_get_ctx(maff), isl_error_internal,
 142                         "invalid space", goto error);
 143
 144         space = isl_space_domain(isl_multi_aff_get_space(maff));
 145         bmap = isl_basic_map_universe(isl_space_from_domain(space));
 146         if (rational)
 147                 bmap = isl_basic_map_set_rational(bmap);
 148
 149         for (i = 0; i < maff->n; ++i) {
 150                 isl_aff *aff;
 151                 isl_basic_map *bmap_i;
 152
 153                 aff = isl_aff_copy(maff->u.p[i]);
 154                 bmap_i = isl_basic_map_from_aff2(aff, rational);
 155
 156                 bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
 157         }
 158
 159         bmap = isl_basic_map_reset_space(bmap, isl_multi_aff_get_space(maff));
 160
 161         isl_multi_aff_free(maff);
 162         return bmap;
 163 error:
 164         isl_multi_aff_free(maff);
 165         return NULL;
 166 }
 167
 168 /* Construct a basic map mapping the domain of the multi-affine expression
 169  * to its range, with each dimension in the range equated to the
 170  * corresponding affine expression.
 171  * If "ma" lives in a set space, then the result is actually a set.
 172  */
 173 static __isl_give isl_basic_map *basic_map_from_multi_aff(
 174         __isl_take isl_multi_aff *ma)
 175 {
 176         return isl_basic_map_from_multi_aff2(ma, 0);
 177 }
 178
 179 /* Construct a basic map mapping the domain of the multi-affine expression
 180  * to its range, with each dimension in the range equated to the
 181  * corresponding affine expression.
 182  */
 183 __isl_give isl_basic_map *isl_basic_map_from_multi_aff(
 184         __isl_take isl_multi_aff *ma)
 185 {
 186         if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0)
 187                 ma = isl_multi_aff_free(ma);
 188         return basic_map_from_multi_aff(ma);
 189 }
 190
 191 /* Construct a map mapping the domain of the multi-affine expression
 192  * to its range, with each dimension in the range equated to the
 193  * corresponding affine expression.
 194  * If "maff" lives in a set space, then the result is actually a set.
 195  */
 196 __isl_give isl_map *isl_map_from_multi_aff_internal(
 197         __isl_take isl_multi_aff *maff)
 198 {
 199         isl_basic_map *bmap;
 200
 201         bmap = basic_map_from_multi_aff(maff);
 202         return isl_map_from_basic_map(bmap);
 203 }
 204
 205 /* Construct a map mapping the domain the multi-affine expression
 206  * to its range, with each dimension in the range equated to the
 207  * corresponding affine expression.
 208  */
 209 __isl_give isl_map *isl_map_from_multi_aff(__isl_take isl_multi_aff *ma)
 210 {
 211         if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0)
 212                 ma = isl_multi_aff_free(ma);
 213         return isl_map_from_multi_aff_internal(ma);
 214 }
 215
 216 /* Construct a basic map mapping a domain in the given space to
 217  * to an n-dimensional range, with n the number of elements in the list,
 218  * where each coordinate in the range is prescribed by the
 219  * corresponding affine expression.
 220  * The domains of all affine expressions in the list are assumed to match
 221  * domain_space.
 222  */
 223 __isl_give isl_basic_map *isl_basic_map_from_aff_list(
 224         __isl_take isl_space *domain_space, __isl_take isl_aff_list *list)
 225 {
 226         int i;
 227         isl_space *space;
 228         isl_basic_map *bmap;
 229
 230         if (!list)
 231                 return NULL;
 232
 233         space = isl_space_from_domain(domain_space);
 234         bmap = isl_basic_map_universe(space);
 235
 236         for (i = 0; i < list->n; ++i) {
 237                 isl_aff *aff;
 238                 isl_basic_map *bmap_i;
 239
 240                 aff = isl_aff_copy(list->p[i]);
 241                 bmap_i = isl_basic_map_from_aff(aff);
 242
 243                 bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
 244         }
 245
 246         isl_aff_list_free(list);
 247         return bmap;
 248 }
 249
 250 /* Construct a map with as domain the domain of pwaff and
 251  * one-dimensional range corresponding to the affine expressions.
 252  * If "pwaff" lives in a set space, then the result is actually a set.
 253  */
 254 __isl_give isl_map *isl_map_from_pw_aff_internal(__isl_take isl_pw_aff *pwaff)
 255 {
 256         int i;
 257         isl_space *space;
 258         isl_map *map;
 259
 260         if (!pwaff)
 261                 return NULL;
 262
 263         space = isl_pw_aff_get_space(pwaff);
 264         map = isl_map_empty(space);
 265
 266         for (i = 0; i < pwaff->n; ++i) {
 267                 isl_basic_map *bmap;
 268                 isl_map *map_i;
 269
 270                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
 271                 map_i = isl_map_from_basic_map(bmap);
 272                 map_i = isl_map_intersect_domain(map_i,
 273                                                 isl_set_copy(pwaff->p[i].set));
 274                 map = isl_map_union_disjoint(map, map_i);
 275         }
 276
 277         isl_pw_aff_free(pwaff);
 278
 279         return map;
 280 }
 281
 282 /* Construct a map with as domain the domain of pwaff and
 283  * one-dimensional range corresponding to the affine expressions.
 284  */
 285 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
 286 {
 287         if (check_input_is_map(isl_pw_aff_peek_space(pwaff)) < 0)
 288                 pwaff = isl_pw_aff_free(pwaff);
 289         return isl_map_from_pw_aff_internal(pwaff);
 290 }
 291
 292 /* Construct a one-dimensional set with as parameter domain
 293  * the domain of pwaff and the single set dimension
 294  * corresponding to the affine expressions.
 295  */
 296 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
 297 {
 298         if (check_input_is_set(isl_pw_aff_peek_space(pwaff)) < 0)
 299                 pwaff = isl_pw_aff_free(pwaff);
 300         return set_from_map(isl_map_from_pw_aff_internal(pwaff));
 301 }
 302
 303 /* Construct a map mapping the domain of the piecewise multi-affine expression
 304  * to its range, with each dimension in the range equated to the
 305  * corresponding affine expression on its cell.
 306  *
 307  * If the domain of "pma" is rational, then so is the constructed "map".
 308  */
 309 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
 310 {
 311         int i;
 312         isl_map *map;
 313
 314         if (!pma)
 315                 return NULL;
 316
 317         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
 318
 319         for (i = 0; i < pma->n; ++i) {
 320                 isl_bool rational;
 321                 isl_multi_aff *maff;
 322                 isl_basic_map *bmap;
 323                 isl_map *map_i;
 324
 325                 rational = isl_set_is_rational(pma->p[i].set);
 326                 if (rational < 0)
 327                         map = isl_map_free(map);
 328                 maff = isl_multi_aff_copy(pma->p[i].maff);
 329                 bmap = isl_basic_map_from_multi_aff2(maff, rational);
 330                 map_i = isl_map_from_basic_map(bmap);
 331                 map_i = isl_map_intersect_domain(map_i,
 332                                                 isl_set_copy(pma->p[i].set));
 333                 map = isl_map_union_disjoint(map, map_i);
 334         }
 335
 336         isl_pw_multi_aff_free(pma);
 337         return map;
 338 }
 339
 340 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
 341 {
 342         if (check_input_is_set(isl_pw_multi_aff_peek_space(pma)) < 0)
 343                 pma = isl_pw_multi_aff_free(pma);
 344         return set_from_map(isl_map_from_pw_multi_aff(pma));
 345 }
 346
 347 /* Construct a set or map mapping the shared (parameter) domain
 348  * of the piecewise affine expressions to the range of "mpa"
 349  * with each dimension in the range equated to the
 350  * corresponding piecewise affine expression.
 351  */
 352 static __isl_give isl_map *map_from_multi_pw_aff(
 353         __isl_take isl_multi_pw_aff *mpa)
 354 {
 355         int i;
 356         isl_space *space;
 357         isl_map *map;
 358
 359         if (!mpa)
 360                 return NULL;
 361
 362         if (isl_space_dim(mpa->space, isl_dim_out) != mpa->n)
 363                 isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal,
 364                         "invalid space", goto error);
 365
 366         space = isl_multi_pw_aff_get_domain_space(mpa);
 367         map = isl_map_universe(isl_space_from_domain(space));
 368
 369         for (i = 0; i < mpa->n; ++i) {
 370                 isl_pw_aff *pa;
 371                 isl_map *map_i;
 372
 373                 pa = isl_pw_aff_copy(mpa->u.p[i]);
 374                 map_i = isl_map_from_pw_aff_internal(pa);
 375
 376                 map = isl_map_flat_range_product(map, map_i);
 377         }
 378
 379         map = isl_map_reset_space(map, isl_multi_pw_aff_get_space(mpa));
 380
 381         isl_multi_pw_aff_free(mpa);
 382         return map;
 383 error:
 384         isl_multi_pw_aff_free(mpa);
 385         return NULL;
 386 }
 387
 388 /* Construct a map mapping the shared domain
 389  * of the piecewise affine expressions to the range of "mpa"
 390  * with each dimension in the range equated to the
 391  * corresponding piecewise affine expression.
 392  */
 393 __isl_give isl_map *isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
 394 {
 395         if (check_input_is_map(isl_multi_pw_aff_peek_space(mpa)) < 0)
 396                 mpa = isl_multi_pw_aff_free(mpa);
 397         return map_from_multi_pw_aff(mpa);
 398 }
 399
 400 /* Construct a set mapping the shared parameter domain
 401  * of the piecewise affine expressions to the space of "mpa"
 402  * with each dimension in the range equated to the
 403  * corresponding piecewise affine expression.
 404  */
 405 __isl_give isl_set *isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
 406 {
 407         if (check_input_is_set(isl_multi_pw_aff_peek_space(mpa)) < 0)
 408                 mpa = isl_multi_pw_aff_free(mpa);
 409         return set_from_map(map_from_multi_pw_aff(mpa));
 410 }
 411
 412 /* Convert "pa" to an isl_map and add it to *umap.
 413  */
 414 static isl_stat map_from_pw_aff_entry(__isl_take isl_pw_aff *pa, void *user)
 415 {
 416         isl_union_map **umap = user;
 417         isl_map *map;
 418
 419         map = isl_map_from_pw_aff(pa);
 420         *umap = isl_union_map_add_map(*umap, map);
 421
 422         return *umap ? isl_stat_ok : isl_stat_error;
 423 }
 424
 425 /* Construct a union map mapping the domain of the union
 426  * piecewise affine expression to its range, with the single output dimension
 427  * equated to the corresponding affine expressions on their cells.
 428  */
 429 __isl_give isl_union_map *isl_union_map_from_union_pw_aff(
 430         __isl_take isl_union_pw_aff *upa)
 431 {
 432         isl_space *space;
 433         isl_union_map *umap;
 434
 435         if (!upa)
 436                 return NULL;
 437
 438         space = isl_union_pw_aff_get_space(upa);
 439         umap = isl_union_map_empty(space);
 440
 441         if (isl_union_pw_aff_foreach_pw_aff(upa, &map_from_pw_aff_entry,
 442                                                 &umap) < 0)
 443                 umap = isl_union_map_free(umap);
 444
 445         isl_union_pw_aff_free(upa);
 446         return umap;
 447 }
 448
 449 /* Convert "pma" to an isl_map and add it to *umap.
 450  */
 451 static isl_stat map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma,
 452         void *user)
 453 {
 454         isl_union_map **umap = user;
 455         isl_map *map;
 456
 457         map = isl_map_from_pw_multi_aff(pma);
 458         *umap = isl_union_map_add_map(*umap, map);
 459
 460         return isl_stat_ok;
 461 }
 462
 463 /* Construct a union map mapping the domain of the union
 464  * piecewise multi-affine expression to its range, with each dimension
 465  * in the range equated to the corresponding affine expression on its cell.
 466  */
 467 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
 468         __isl_take isl_union_pw_multi_aff *upma)
 469 {
 470         isl_space *space;
 471         isl_union_map *umap;
 472
 473         if (!upma)
 474                 return NULL;
 475
 476         space = isl_union_pw_multi_aff_get_space(upma);
 477         umap = isl_union_map_empty(space);
 478
 479         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
 480                                         &map_from_pw_multi_aff, &umap) < 0)
 481                 goto error;
 482
 483         isl_union_pw_multi_aff_free(upma);
 484         return umap;
 485 error:
 486         isl_union_pw_multi_aff_free(upma);
 487         isl_union_map_free(umap);
 488         return NULL;
 489 }