Line data Source code
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 0 : static isl_stat check_input_is_map(__isl_keep isl_space *space)
30 : {
31 : isl_bool is_set;
32 :
33 0 : is_set = isl_space_is_set(space);
34 0 : if (is_set < 0)
35 0 : return isl_stat_error;
36 0 : if (is_set)
37 0 : isl_die(isl_space_get_ctx(space), isl_error_invalid,
38 : "space of input is not a map", return isl_stat_error);
39 0 : 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 0 : static isl_stat check_input_is_set(__isl_keep isl_space *space)
46 : {
47 : isl_bool is_set;
48 :
49 0 : is_set = isl_space_is_set(space);
50 0 : if (is_set < 0)
51 0 : return isl_stat_error;
52 0 : if (!is_set)
53 0 : isl_die(isl_space_get_ctx(space), isl_error_invalid,
54 : "space of input is not a set", return isl_stat_error);
55 0 : 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 0 : 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 0 : isl_basic_map *bmap = NULL;
72 :
73 0 : if (!aff)
74 0 : return NULL;
75 0 : is_nan = isl_aff_is_nan(aff);
76 0 : if (is_nan < 0)
77 0 : goto error;
78 0 : if (is_nan)
79 0 : isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
80 : "cannot convert NaN", goto error);
81 :
82 0 : ls = isl_aff_get_local_space(aff);
83 0 : bmap = isl_basic_map_from_local_space(ls);
84 0 : bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
85 0 : k = isl_basic_map_alloc_equality(bmap);
86 0 : if (k < 0)
87 0 : goto error;
88 :
89 0 : pos = isl_basic_map_offset(bmap, isl_dim_out);
90 0 : isl_seq_cpy(bmap->eq[k], aff->v->el + 1, pos);
91 0 : isl_int_neg(bmap->eq[k][pos], aff->v->el[0]);
92 0 : isl_seq_cpy(bmap->eq[k] + pos + 1, aff->v->el + 1 + pos,
93 0 : aff->v->size - (pos + 1));
94 :
95 0 : isl_aff_free(aff);
96 0 : if (rational)
97 0 : bmap = isl_basic_map_set_rational(bmap);
98 0 : bmap = isl_basic_map_gauss(bmap, NULL);
99 0 : bmap = isl_basic_map_finalize(bmap);
100 0 : return bmap;
101 : error:
102 0 : isl_aff_free(aff);
103 0 : isl_basic_map_free(bmap);
104 0 : 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 0 : __isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff)
111 : {
112 0 : 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 0 : __isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff)
119 : {
120 : isl_basic_map *bmap;
121 :
122 0 : bmap = isl_basic_map_from_aff(aff);
123 0 : 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 0 : __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 0 : if (!maff)
139 0 : return NULL;
140 :
141 0 : if (isl_space_dim(maff->space, isl_dim_out) != maff->n)
142 0 : isl_die(isl_multi_aff_get_ctx(maff), isl_error_internal,
143 : "invalid space", goto error);
144 :
145 0 : space = isl_space_domain(isl_multi_aff_get_space(maff));
146 0 : bmap = isl_basic_map_universe(isl_space_from_domain(space));
147 0 : if (rational)
148 0 : bmap = isl_basic_map_set_rational(bmap);
149 :
150 0 : for (i = 0; i < maff->n; ++i) {
151 : isl_aff *aff;
152 : isl_basic_map *bmap_i;
153 :
154 0 : aff = isl_aff_copy(maff->u.p[i]);
155 0 : bmap_i = isl_basic_map_from_aff2(aff, rational);
156 :
157 0 : bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
158 : }
159 :
160 0 : bmap = isl_basic_map_reset_space(bmap, isl_multi_aff_get_space(maff));
161 :
162 0 : isl_multi_aff_free(maff);
163 0 : return bmap;
164 : error:
165 0 : isl_multi_aff_free(maff);
166 0 : 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 0 : static __isl_give isl_basic_map *basic_map_from_multi_aff(
175 : __isl_take isl_multi_aff *ma)
176 : {
177 0 : 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 0 : __isl_give isl_basic_map *isl_basic_map_from_multi_aff(
185 : __isl_take isl_multi_aff *ma)
186 : {
187 0 : if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0)
188 0 : ma = isl_multi_aff_free(ma);
189 0 : 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 0 : __isl_give isl_basic_set *isl_basic_set_from_multi_aff(
197 : __isl_take isl_multi_aff *ma)
198 : {
199 0 : if (check_input_is_set(isl_multi_aff_peek_space(ma)) < 0)
200 0 : ma = isl_multi_aff_free(ma);
201 0 : 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 0 : __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 0 : bmap = basic_map_from_multi_aff(maff);
215 0 : 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 0 : __isl_give isl_map *isl_map_from_multi_aff(__isl_take isl_multi_aff *ma)
223 : {
224 0 : if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0)
225 0 : ma = isl_multi_aff_free(ma);
226 0 : 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 0 : __isl_give isl_set *isl_set_from_multi_aff(__isl_take isl_multi_aff *ma)
234 : {
235 0 : if (check_input_is_set(isl_multi_aff_peek_space(ma)) < 0)
236 0 : ma = isl_multi_aff_free(ma);
237 0 : 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 0 : __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 0 : if (!list)
255 0 : return NULL;
256 :
257 0 : space = isl_space_from_domain(domain_space);
258 0 : bmap = isl_basic_map_universe(space);
259 :
260 0 : for (i = 0; i < list->n; ++i) {
261 : isl_aff *aff;
262 : isl_basic_map *bmap_i;
263 :
264 0 : aff = isl_aff_copy(list->p[i]);
265 0 : bmap_i = isl_basic_map_from_aff(aff);
266 :
267 0 : bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
268 : }
269 :
270 0 : isl_aff_list_free(list);
271 0 : 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 0 : __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 0 : if (!pwaff)
285 0 : return NULL;
286 :
287 0 : space = isl_pw_aff_get_space(pwaff);
288 0 : map = isl_map_empty(space);
289 :
290 0 : for (i = 0; i < pwaff->n; ++i) {
291 : isl_basic_map *bmap;
292 : isl_map *map_i;
293 :
294 0 : bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
295 0 : map_i = isl_map_from_basic_map(bmap);
296 0 : map_i = isl_map_intersect_domain(map_i,
297 0 : isl_set_copy(pwaff->p[i].set));
298 0 : map = isl_map_union_disjoint(map, map_i);
299 : }
300 :
301 0 : isl_pw_aff_free(pwaff);
302 :
303 0 : 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 0 : __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
310 : {
311 0 : if (check_input_is_map(isl_pw_aff_peek_space(pwaff)) < 0)
312 0 : pwaff = isl_pw_aff_free(pwaff);
313 0 : 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 0 : __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
321 : {
322 0 : if (check_input_is_set(isl_pw_aff_peek_space(pwaff)) < 0)
323 0 : pwaff = isl_pw_aff_free(pwaff);
324 0 : 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 0 : __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 0 : if (!pma)
339 0 : return NULL;
340 :
341 0 : map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
342 :
343 0 : 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 0 : rational = isl_set_is_rational(pma->p[i].set);
350 0 : if (rational < 0)
351 0 : map = isl_map_free(map);
352 0 : maff = isl_multi_aff_copy(pma->p[i].maff);
353 0 : bmap = isl_basic_map_from_multi_aff2(maff, rational);
354 0 : map_i = isl_map_from_basic_map(bmap);
355 0 : map_i = isl_map_intersect_domain(map_i,
356 : isl_set_copy(pma->p[i].set));
357 0 : map = isl_map_union_disjoint(map, map_i);
358 : }
359 :
360 0 : isl_pw_multi_aff_free(pma);
361 0 : return map;
362 : }
363 :
364 0 : __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
365 : {
366 0 : if (check_input_is_set(isl_pw_multi_aff_peek_space(pma)) < 0)
367 0 : pma = isl_pw_multi_aff_free(pma);
368 0 : 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 0 : 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 0 : if (!mpa)
384 0 : return NULL;
385 :
386 0 : if (isl_space_dim(mpa->space, isl_dim_out) != mpa->n)
387 0 : isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal,
388 : "invalid space", goto error);
389 :
390 0 : space = isl_multi_pw_aff_get_domain_space(mpa);
391 0 : map = isl_map_universe(isl_space_from_domain(space));
392 :
393 0 : for (i = 0; i < mpa->n; ++i) {
394 : isl_pw_aff *pa;
395 : isl_map *map_i;
396 :
397 0 : pa = isl_pw_aff_copy(mpa->u.p[i]);
398 0 : map_i = isl_map_from_pw_aff_internal(pa);
399 :
400 0 : map = isl_map_flat_range_product(map, map_i);
401 : }
402 :
403 0 : map = isl_map_reset_space(map, isl_multi_pw_aff_get_space(mpa));
404 :
405 0 : isl_multi_pw_aff_free(mpa);
406 0 : return map;
407 : error:
408 0 : isl_multi_pw_aff_free(mpa);
409 0 : 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 0 : __isl_give isl_map *isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
418 : {
419 0 : if (check_input_is_map(isl_multi_pw_aff_peek_space(mpa)) < 0)
420 0 : mpa = isl_multi_pw_aff_free(mpa);
421 0 : 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 0 : __isl_give isl_set *isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
430 : {
431 0 : if (check_input_is_set(isl_multi_pw_aff_peek_space(mpa)) < 0)
432 0 : mpa = isl_multi_pw_aff_free(mpa);
433 0 : 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 0 : static isl_stat map_from_pw_aff_entry(__isl_take isl_pw_aff *pa, void *user)
439 : {
440 0 : isl_union_map **umap = user;
441 : isl_map *map;
442 :
443 0 : map = isl_map_from_pw_aff(pa);
444 0 : *umap = isl_union_map_add_map(*umap, map);
445 :
446 0 : 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 0 : __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 0 : if (!upa)
460 0 : return NULL;
461 :
462 0 : space = isl_union_pw_aff_get_space(upa);
463 0 : umap = isl_union_map_empty(space);
464 :
465 0 : if (isl_union_pw_aff_foreach_pw_aff(upa, &map_from_pw_aff_entry,
466 : &umap) < 0)
467 0 : umap = isl_union_map_free(umap);
468 :
469 0 : isl_union_pw_aff_free(upa);
470 0 : return umap;
471 : }
472 :
473 : /* Convert "pma" to an isl_map and add it to *umap.
474 : */
475 0 : static isl_stat map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma,
476 : void *user)
477 : {
478 0 : isl_union_map **umap = user;
479 : isl_map *map;
480 :
481 0 : map = isl_map_from_pw_multi_aff(pma);
482 0 : *umap = isl_union_map_add_map(*umap, map);
483 :
484 0 : 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 0 : __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 0 : if (!upma)
498 0 : return NULL;
499 :
500 0 : space = isl_union_pw_multi_aff_get_space(upma);
501 0 : umap = isl_union_map_empty(space);
502 :
503 0 : if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
504 : &map_from_pw_multi_aff, &umap) < 0)
505 0 : goto error;
506 :
507 0 : isl_union_pw_multi_aff_free(upma);
508 0 : return umap;
509 : error:
510 0 : isl_union_pw_multi_aff_free(upma);
511 0 : isl_union_map_free(umap);
512 0 : return NULL;
513 : }
|
