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 */
29static 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 */
45static 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 */
64static __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(base: bmap, n_eq: 1, n_ineq: 0);
85 k = isl_basic_map_alloc_equality(bmap);
86 if (k < 0)
87 goto error;
88
89 pos = isl_basic_map_offset(bmap, type: isl_dim_out);
90 isl_seq_cpy(dst: bmap->eq[k], src: aff->v->el + 1, len: pos);
91 isl_int_neg(bmap->eq[k][pos], aff->v->el[0]);
92 isl_seq_cpy(dst: bmap->eq[k] + pos + 1, src: aff->v->el + 1 + pos,
93 len: 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;
101error:
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, rational: 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(multi: maff, type: 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(space: isl_multi_aff_get_space(multi: maff));
148 bmap = isl_basic_map_universe(space: 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(aff: maff->u.p[i]);
157 bmap_i = isl_basic_map_from_aff2(aff, rational);
158
159 bmap = isl_basic_map_flat_range_product(bmap1: bmap, bmap2: bmap_i);
160 }
161
162 bmap = isl_basic_map_reset_space(bmap, space: isl_multi_aff_get_space(multi: maff));
163
164 isl_multi_aff_free(multi: maff);
165 return bmap;
166error:
167 isl_multi_aff_free(multi: 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 */
176static __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(maff: ma, rational: 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(space: isl_multi_aff_peek_space(multi: ma)) < 0)
190 ma = isl_multi_aff_free(multi: 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(space: isl_multi_aff_peek_space(multi: ma)) < 0)
202 ma = isl_multi_aff_free(multi: ma);
203 return bset_from_bmap(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(ma: 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(space: isl_multi_aff_peek_space(multi: ma)) < 0)
227 ma = isl_multi_aff_free(multi: ma);
228 return isl_map_from_multi_aff_internal(maff: 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(space: isl_multi_aff_peek_space(multi: ma)) < 0)
246 ma = isl_multi_aff_free(multi: ma);
247 return isl_map_from_multi_aff_internal(maff: 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(space: 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(aff: list->p[i]);
283 bmap_i = isl_basic_map_from_aff(aff);
284
285 bmap = isl_basic_map_flat_range_product(bmap1: bmap, bmap2: 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(aff: isl_aff_copy(aff: pwaff->p[i].aff));
313 map_i = isl_map_from_basic_map(bmap);
314 map_i = isl_map_intersect_domain(map: map_i,
315 set: isl_set_copy(set: pwaff->p[i].set));
316 map = isl_map_union_disjoint(map1: map, map2: 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(space: isl_pw_aff_peek_space(pw: 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(pwaff: 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(space: isl_pw_aff_peek_space(pw: 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(space: 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(set: pma->p[i].set);
378 if (rational < 0)
379 map = isl_map_free(map);
380 maff = isl_multi_aff_copy(multi: 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: map_i,
384 set: isl_set_copy(set: pma->p[i].set));
385 map = isl_map_union_disjoint(map1: map, map2: 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(space: isl_pw_multi_aff_peek_space(pw: 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(space: isl_pw_multi_aff_peek_space(pw: 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 */
434static __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(multi: mpa, type: isl_dim_out);
443 if (dim < 0)
444 goto error;
445
446 if (isl_space_dim(space: mpa->space, type: 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(multi: mpa);
451 map = isl_map_universe(space: 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(pwaff: mpa->u.p[i]);
458 map_i = isl_map_from_pw_aff_internal(pwaff: pa);
459
460 map = isl_map_flat_range_product(map1: map, map2: map_i);
461 }
462
463 map = isl_map_reset_space(map, space: isl_multi_pw_aff_get_space(multi: mpa));
464
465 map = isl_map_intersect_multi_pw_aff_explicit_domain(map, mpa);
466
467 isl_multi_pw_aff_free(multi: mpa);
468 return map;
469error:
470 isl_multi_pw_aff_free(multi: 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(space: isl_multi_pw_aff_peek_space(multi: mpa)) < 0)
482 mpa = isl_multi_pw_aff_free(multi: 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(space: isl_multi_pw_aff_peek_space(multi: mpa)) < 0)
502 mpa = isl_multi_pw_aff_free(multi: 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 */
516static 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(pwaff: pa);
522 *umap = isl_union_map_add_map(umap: *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, fn: &map_from_pw_aff_entry,
544 user: &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 */
553static 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: *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 fn: &map_from_pw_multi_aff, user: &umap) < 0)
583 goto error;
584
585 isl_union_pw_multi_aff_free(upma);
586 return umap;
587error:
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}
602

source code of polly/lib/External/isl/isl_aff_map.c