2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2013 Ecole Normale Superieure
4 * Copyright 2016 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
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>
23 #include <bset_from_bmap.c>
24 #include <set_from_map.c>
26 /* Check that the input living in "space" lives in a map space.
27 * That is, check that "space" is a map space.
29 static isl_stat
check_input_is_map(__isl_keep isl_space
*space
)
33 is_set
= isl_space_is_set(space
);
35 return isl_stat_error
;
37 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
38 "space of input is not a map", return isl_stat_error
);
42 /* Check that the input living in "space" lives in a set space.
43 * That is, check that "space" is a set space.
45 static isl_stat
check_input_is_set(__isl_keep isl_space
*space
)
49 is_set
= isl_space_is_set(space
);
51 return isl_stat_error
;
53 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
54 "space of input is not a set", return isl_stat_error
);
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.
62 * A NaN affine expression cannot be converted to a basic map.
64 static __isl_give isl_basic_map
*isl_basic_map_from_aff2(
65 __isl_take isl_aff
*aff
, int rational
)
71 isl_basic_map
*bmap
= NULL
;
75 is_nan
= isl_aff_is_nan(aff
);
79 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
80 "cannot convert NaN", goto error
);
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
);
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));
97 bmap
= isl_basic_map_set_rational(bmap
);
98 bmap
= isl_basic_map_gauss(bmap
, NULL
);
99 bmap
= isl_basic_map_finalize(bmap
);
103 isl_basic_map_free(bmap
);
107 /* Construct a basic map mapping the domain of the affine expression
108 * to a one-dimensional range prescribed by the affine expression.
110 __isl_give isl_basic_map
*isl_basic_map_from_aff(__isl_take isl_aff
*aff
)
112 return isl_basic_map_from_aff2(aff
, 0);
115 /* Construct a map mapping the domain of the affine expression
116 * to a one-dimensional range prescribed by the affine expression.
118 __isl_give isl_map
*isl_map_from_aff(__isl_take isl_aff
*aff
)
122 bmap
= isl_basic_map_from_aff(aff
);
123 return isl_map_from_basic_map(bmap
);
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.
131 __isl_give isl_basic_map
*isl_basic_map_from_multi_aff2(
132 __isl_take isl_multi_aff
*maff
, int rational
)
139 dim
= isl_multi_aff_dim(maff
, isl_dim_out
);
144 isl_die(isl_multi_aff_get_ctx(maff
), isl_error_internal
,
145 "invalid space", goto error
);
147 space
= isl_space_domain(isl_multi_aff_get_space(maff
));
148 bmap
= isl_basic_map_universe(isl_space_from_domain(space
));
150 bmap
= isl_basic_map_set_rational(bmap
);
152 for (i
= 0; i
< maff
->n
; ++i
) {
154 isl_basic_map
*bmap_i
;
156 aff
= isl_aff_copy(maff
->u
.p
[i
]);
157 bmap_i
= isl_basic_map_from_aff2(aff
, rational
);
159 bmap
= isl_basic_map_flat_range_product(bmap
, bmap_i
);
162 bmap
= isl_basic_map_reset_space(bmap
, isl_multi_aff_get_space(maff
));
164 isl_multi_aff_free(maff
);
167 isl_multi_aff_free(maff
);
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.
176 static __isl_give isl_basic_map
*basic_map_from_multi_aff(
177 __isl_take isl_multi_aff
*ma
)
179 return isl_basic_map_from_multi_aff2(ma
, 0);
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.
186 __isl_give isl_basic_map
*isl_basic_map_from_multi_aff(
187 __isl_take isl_multi_aff
*ma
)
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
);
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.
198 __isl_give isl_basic_set
*isl_basic_set_from_multi_aff(
199 __isl_take isl_multi_aff
*ma
)
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
));
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.
211 __isl_give isl_map
*isl_map_from_multi_aff_internal(
212 __isl_take isl_multi_aff
*maff
)
216 bmap
= basic_map_from_multi_aff(maff
);
217 return isl_map_from_basic_map(bmap
);
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.
224 __isl_give isl_map
*isl_map_from_multi_aff(__isl_take isl_multi_aff
*ma
)
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
);
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.
235 __isl_give isl_set
*isl_set_from_multi_aff(__isl_take isl_multi_aff
*ma
)
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
);
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
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
)
259 space
= isl_space_from_domain(domain_space
);
260 bmap
= isl_basic_map_universe(space
);
262 for (i
= 0; i
< list
->n
; ++i
) {
264 isl_basic_map
*bmap_i
;
266 aff
= isl_aff_copy(list
->p
[i
]);
267 bmap_i
= isl_basic_map_from_aff(aff
);
269 bmap
= isl_basic_map_flat_range_product(bmap
, bmap_i
);
272 isl_aff_list_free(list
);
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.
280 __isl_give isl_map
*isl_map_from_pw_aff_internal(__isl_take isl_pw_aff
*pwaff
)
289 space
= isl_pw_aff_get_space(pwaff
);
290 map
= isl_map_empty(space
);
292 for (i
= 0; i
< pwaff
->n
; ++i
) {
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
);
303 isl_pw_aff_free(pwaff
);
308 /* Construct a map with as domain the domain of pwaff and
309 * one-dimensional range corresponding to the affine expressions.
311 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
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
);
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.
322 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
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
));
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.
333 * If the domain of "pma" is rational, then so is the constructed "map".
335 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
343 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
345 for (i
= 0; i
< pma
->n
; ++i
) {
351 rational
= isl_set_is_rational(pma
->p
[i
].set
);
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
);
362 isl_pw_multi_aff_free(pma
);
366 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
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
));
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.
378 static __isl_give isl_map
*map_from_multi_pw_aff(
379 __isl_take isl_multi_pw_aff
*mpa
)
386 dim
= isl_multi_pw_aff_dim(mpa
, isl_dim_out
);
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
);
394 space
= isl_multi_pw_aff_get_domain_space(mpa
);
395 map
= isl_map_universe(isl_space_from_domain(space
));
397 for (i
= 0; i
< mpa
->n
; ++i
) {
401 pa
= isl_pw_aff_copy(mpa
->u
.p
[i
]);
402 map_i
= isl_map_from_pw_aff_internal(pa
);
404 map
= isl_map_flat_range_product(map
, map_i
);
407 map
= isl_map_reset_space(map
, isl_multi_pw_aff_get_space(mpa
));
409 isl_multi_pw_aff_free(mpa
);
412 isl_multi_pw_aff_free(mpa
);
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.
421 __isl_give isl_map
*isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
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
);
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.
433 __isl_give isl_set
*isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
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
));
440 /* Convert "pa" to an isl_map and add it to *umap.
442 static isl_stat
map_from_pw_aff_entry(__isl_take isl_pw_aff
*pa
, void *user
)
444 isl_union_map
**umap
= user
;
447 map
= isl_map_from_pw_aff(pa
);
448 *umap
= isl_union_map_add_map(*umap
, map
);
450 return *umap
? isl_stat_ok
: isl_stat_error
;
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.
457 __isl_give isl_union_map
*isl_union_map_from_union_pw_aff(
458 __isl_take isl_union_pw_aff
*upa
)
466 space
= isl_union_pw_aff_get_space(upa
);
467 umap
= isl_union_map_empty(space
);
469 if (isl_union_pw_aff_foreach_pw_aff(upa
, &map_from_pw_aff_entry
,
471 umap
= isl_union_map_free(umap
);
473 isl_union_pw_aff_free(upa
);
477 /* Convert "pma" to an isl_map and add it to *umap.
479 static isl_stat
map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
,
482 isl_union_map
**umap
= user
;
485 map
= isl_map_from_pw_multi_aff(pma
);
486 *umap
= isl_union_map_add_map(*umap
, map
);
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.
495 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
496 __isl_take isl_union_pw_multi_aff
*upma
)
504 space
= isl_union_pw_multi_aff_get_space(upma
);
505 umap
= isl_union_map_empty(space
);
507 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
508 &map_from_pw_multi_aff
, &umap
) < 0)
511 isl_union_pw_multi_aff_free(upma
);
514 isl_union_pw_multi_aff_free(upma
);
515 isl_union_map_free(umap
);