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