2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2013-2014 Ecole Normale Superieure
4 * Copyright 2014 INRIA Rocquencourt
5 * Copyright 2016 Sven Verdoolaege
7 * Use of this software is governed by the MIT license
9 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
10 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
13 * B.P. 105 - 78153 Le Chesnay, France
17 #include <isl_map_private.h>
18 #include <isl_union_map_private.h>
24 #include <isl_space_private.h>
25 #include <isl/union_set.h>
26 #include <isl/deprecated/union_map_int.h>
28 #include <bset_from_bmap.c>
29 #include <set_to_map.c>
30 #include <set_from_map.c>
32 /* Return the number of parameters of "umap", where "type"
33 * is required to be set to isl_dim_param.
35 unsigned isl_union_map_dim(__isl_keep isl_union_map
*umap
,
36 enum isl_dim_type type
)
41 if (type
!= isl_dim_param
)
42 isl_die(isl_union_map_get_ctx(umap
), isl_error_invalid
,
43 "can only reference parameters", return 0);
45 return isl_space_dim(umap
->dim
, type
);
48 /* Return the number of parameters of "uset", where "type"
49 * is required to be set to isl_dim_param.
51 unsigned isl_union_set_dim(__isl_keep isl_union_set
*uset
,
52 enum isl_dim_type type
)
54 return isl_union_map_dim(uset
, type
);
57 /* Return the id of the specified dimension.
59 __isl_give isl_id
*isl_union_map_get_dim_id(__isl_keep isl_union_map
*umap
,
60 enum isl_dim_type type
, unsigned pos
)
65 if (type
!= isl_dim_param
)
66 isl_die(isl_union_map_get_ctx(umap
), isl_error_invalid
,
67 "can only reference parameters", return NULL
);
69 return isl_space_get_dim_id(umap
->dim
, type
, pos
);
72 /* Is this union set a parameter domain?
74 isl_bool
isl_union_set_is_params(__isl_keep isl_union_set
*uset
)
80 return isl_bool_error
;
81 if (uset
->table
.n
!= 1)
82 return isl_bool_false
;
84 set
= isl_set_from_union_set(isl_union_set_copy(uset
));
85 params
= isl_set_is_params(set
);
90 static __isl_give isl_union_map
*isl_union_map_alloc(
91 __isl_take isl_space
*space
, int size
)
95 space
= isl_space_params(space
);
99 umap
= isl_calloc_type(space
->ctx
, isl_union_map
);
101 isl_space_free(space
);
107 if (isl_hash_table_init(space
->ctx
, &umap
->table
, size
) < 0)
108 return isl_union_map_free(umap
);
113 __isl_give isl_union_map
*isl_union_map_empty(__isl_take isl_space
*dim
)
115 return isl_union_map_alloc(dim
, 16);
118 __isl_give isl_union_set
*isl_union_set_empty(__isl_take isl_space
*dim
)
120 return isl_union_map_empty(dim
);
123 isl_ctx
*isl_union_map_get_ctx(__isl_keep isl_union_map
*umap
)
125 return umap
? umap
->dim
->ctx
: NULL
;
128 isl_ctx
*isl_union_set_get_ctx(__isl_keep isl_union_set
*uset
)
130 return uset
? uset
->dim
->ctx
: NULL
;
133 /* Return the space of "umap".
135 __isl_keep isl_space
*isl_union_map_peek_space(__isl_keep isl_union_map
*umap
)
137 return umap
? umap
->dim
: NULL
;
140 __isl_give isl_space
*isl_union_map_get_space(__isl_keep isl_union_map
*umap
)
142 return isl_space_copy(isl_union_map_peek_space(umap
));
145 /* Return the position of the parameter with the given name
147 * Return -1 if no such dimension can be found.
149 int isl_union_map_find_dim_by_name(__isl_keep isl_union_map
*umap
,
150 enum isl_dim_type type
, const char *name
)
154 return isl_space_find_dim_by_name(umap
->dim
, type
, name
);
157 __isl_give isl_space
*isl_union_set_get_space(__isl_keep isl_union_set
*uset
)
159 return isl_union_map_get_space(uset
);
162 static isl_stat
free_umap_entry(void **entry
, void *user
)
164 isl_map
*map
= *entry
;
169 static isl_stat
add_map(__isl_take isl_map
*map
, void *user
)
171 isl_union_map
**umap
= (isl_union_map
**)user
;
173 *umap
= isl_union_map_add_map(*umap
, map
);
178 __isl_give isl_union_map
*isl_union_map_dup(__isl_keep isl_union_map
*umap
)
185 dup
= isl_union_map_empty(isl_space_copy(umap
->dim
));
186 if (isl_union_map_foreach_map(umap
, &add_map
, &dup
) < 0)
190 isl_union_map_free(dup
);
194 __isl_give isl_union_map
*isl_union_map_cow(__isl_take isl_union_map
*umap
)
202 return isl_union_map_dup(umap
);
205 struct isl_union_align
{
210 static isl_stat
align_entry(void **entry
, void *user
)
212 isl_map
*map
= *entry
;
214 struct isl_union_align
*data
= user
;
216 exp
= isl_reordering_extend_space(isl_reordering_copy(data
->exp
),
217 isl_map_get_space(map
));
219 data
->res
= isl_union_map_add_map(data
->res
,
220 isl_map_realign(isl_map_copy(map
), exp
));
225 /* Align the parameters of umap along those of model.
226 * The result has the parameters of model first, in the same order
227 * as they appear in model, followed by any remaining parameters of
228 * umap that do not appear in model.
230 __isl_give isl_union_map
*isl_union_map_align_params(
231 __isl_take isl_union_map
*umap
, __isl_take isl_space
*model
)
233 struct isl_union_align data
= { NULL
, NULL
};
238 if (isl_space_match(umap
->dim
, isl_dim_param
, model
, isl_dim_param
)) {
239 isl_space_free(model
);
243 model
= isl_space_params(model
);
244 data
.exp
= isl_parameter_alignment_reordering(umap
->dim
, model
);
248 data
.res
= isl_union_map_alloc(isl_space_copy(data
.exp
->dim
),
250 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
251 &align_entry
, &data
) < 0)
254 isl_reordering_free(data
.exp
);
255 isl_union_map_free(umap
);
256 isl_space_free(model
);
259 isl_reordering_free(data
.exp
);
260 isl_union_map_free(umap
);
261 isl_union_map_free(data
.res
);
262 isl_space_free(model
);
266 __isl_give isl_union_set
*isl_union_set_align_params(
267 __isl_take isl_union_set
*uset
, __isl_take isl_space
*model
)
269 return isl_union_map_align_params(uset
, model
);
272 __isl_give isl_union_map
*isl_union_map_union(__isl_take isl_union_map
*umap1
,
273 __isl_take isl_union_map
*umap2
)
275 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
276 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
278 umap1
= isl_union_map_cow(umap1
);
280 if (!umap1
|| !umap2
)
283 if (isl_union_map_foreach_map(umap2
, &add_map
, &umap1
) < 0)
286 isl_union_map_free(umap2
);
290 isl_union_map_free(umap1
);
291 isl_union_map_free(umap2
);
295 __isl_give isl_union_set
*isl_union_set_union(__isl_take isl_union_set
*uset1
,
296 __isl_take isl_union_set
*uset2
)
298 return isl_union_map_union(uset1
, uset2
);
301 __isl_give isl_union_map
*isl_union_map_copy(__isl_keep isl_union_map
*umap
)
310 __isl_give isl_union_set
*isl_union_set_copy(__isl_keep isl_union_set
*uset
)
312 return isl_union_map_copy(uset
);
315 __isl_null isl_union_map
*isl_union_map_free(__isl_take isl_union_map
*umap
)
323 isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
324 &free_umap_entry
, NULL
);
325 isl_hash_table_clear(&umap
->table
);
326 isl_space_free(umap
->dim
);
331 __isl_null isl_union_set
*isl_union_set_free(__isl_take isl_union_set
*uset
)
333 return isl_union_map_free(uset
);
336 /* Do "umap" and "space" have the same parameters?
338 isl_bool
isl_union_map_space_has_equal_params(__isl_keep isl_union_map
*umap
,
339 __isl_keep isl_space
*space
)
341 isl_space
*umap_space
;
343 umap_space
= isl_union_map_peek_space(umap
);
344 return isl_space_match(umap_space
, isl_dim_param
, space
, isl_dim_param
);
347 static int has_dim(const void *entry
, const void *val
)
349 isl_map
*map
= (isl_map
*)entry
;
350 isl_space
*dim
= (isl_space
*)val
;
352 return isl_space_is_equal(map
->dim
, dim
);
355 __isl_give isl_union_map
*isl_union_map_add_map(__isl_take isl_union_map
*umap
,
356 __isl_take isl_map
*map
)
359 struct isl_hash_table_entry
*entry
;
365 if (isl_map_plain_is_empty(map
)) {
370 aligned
= isl_map_space_has_equal_params(map
, umap
->dim
);
374 umap
= isl_union_map_align_params(umap
, isl_map_get_space(map
));
375 map
= isl_map_align_params(map
, isl_union_map_get_space(umap
));
378 umap
= isl_union_map_cow(umap
);
383 hash
= isl_space_get_hash(map
->dim
);
384 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
385 &has_dim
, map
->dim
, 1);
392 entry
->data
= isl_map_union(entry
->data
, isl_map_copy(map
));
401 isl_union_map_free(umap
);
405 __isl_give isl_union_set
*isl_union_set_add_set(__isl_take isl_union_set
*uset
,
406 __isl_take isl_set
*set
)
408 return isl_union_map_add_map(uset
, set_to_map(set
));
411 __isl_give isl_union_map
*isl_union_map_from_map(__isl_take isl_map
*map
)
419 dim
= isl_map_get_space(map
);
420 dim
= isl_space_params(dim
);
421 umap
= isl_union_map_empty(dim
);
422 umap
= isl_union_map_add_map(umap
, map
);
427 __isl_give isl_union_set
*isl_union_set_from_set(__isl_take isl_set
*set
)
429 return isl_union_map_from_map(set_to_map(set
));
432 __isl_give isl_union_map
*isl_union_map_from_basic_map(
433 __isl_take isl_basic_map
*bmap
)
435 return isl_union_map_from_map(isl_map_from_basic_map(bmap
));
438 __isl_give isl_union_set
*isl_union_set_from_basic_set(
439 __isl_take isl_basic_set
*bset
)
441 return isl_union_map_from_basic_map(bset
);
444 struct isl_union_map_foreach_data
446 isl_stat (*fn
)(__isl_take isl_map
*map
, void *user
);
450 static isl_stat
call_on_copy(void **entry
, void *user
)
452 isl_map
*map
= *entry
;
453 struct isl_union_map_foreach_data
*data
;
454 data
= (struct isl_union_map_foreach_data
*)user
;
456 return data
->fn(isl_map_copy(map
), data
->user
);
459 int isl_union_map_n_map(__isl_keep isl_union_map
*umap
)
461 return umap
? umap
->table
.n
: 0;
464 int isl_union_set_n_set(__isl_keep isl_union_set
*uset
)
466 return uset
? uset
->table
.n
: 0;
469 isl_stat
isl_union_map_foreach_map(__isl_keep isl_union_map
*umap
,
470 isl_stat (*fn
)(__isl_take isl_map
*map
, void *user
), void *user
)
472 struct isl_union_map_foreach_data data
= { fn
, user
};
475 return isl_stat_error
;
477 return isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
478 &call_on_copy
, &data
);
481 static isl_stat
copy_map(void **entry
, void *user
)
483 isl_map
*map
= *entry
;
484 isl_map
**map_p
= user
;
486 *map_p
= isl_map_copy(map
);
488 return isl_stat_error
;
491 __isl_give isl_map
*isl_map_from_union_map(__isl_take isl_union_map
*umap
)
498 ctx
= isl_union_map_get_ctx(umap
);
499 if (umap
->table
.n
!= 1)
500 isl_die(ctx
, isl_error_invalid
,
501 "union map needs to contain elements in exactly "
502 "one space", goto error
);
504 isl_hash_table_foreach(ctx
, &umap
->table
, ©_map
, &map
);
506 isl_union_map_free(umap
);
510 isl_union_map_free(umap
);
514 __isl_give isl_set
*isl_set_from_union_set(__isl_take isl_union_set
*uset
)
516 return isl_map_from_union_map(uset
);
519 /* Extract the map in "umap" that lives in the given space (ignoring
522 __isl_give isl_map
*isl_union_map_extract_map(__isl_keep isl_union_map
*umap
,
523 __isl_take isl_space
*space
)
526 struct isl_hash_table_entry
*entry
;
528 space
= isl_space_drop_dims(space
, isl_dim_param
,
529 0, isl_space_dim(space
, isl_dim_param
));
530 space
= isl_space_align_params(space
, isl_union_map_get_space(umap
));
534 hash
= isl_space_get_hash(space
);
535 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
538 return isl_map_empty(space
);
539 isl_space_free(space
);
540 return isl_map_copy(entry
->data
);
542 isl_space_free(space
);
546 __isl_give isl_set
*isl_union_set_extract_set(__isl_keep isl_union_set
*uset
,
547 __isl_take isl_space
*dim
)
549 return set_from_map(isl_union_map_extract_map(uset
, dim
));
552 /* Check if umap contains a map in the given space.
554 isl_bool
isl_union_map_contains(__isl_keep isl_union_map
*umap
,
555 __isl_keep isl_space
*space
)
558 struct isl_hash_table_entry
*entry
;
561 return isl_bool_error
;
563 hash
= isl_space_get_hash(space
);
564 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
569 isl_bool
isl_union_set_contains(__isl_keep isl_union_set
*uset
,
570 __isl_keep isl_space
*space
)
572 return isl_union_map_contains(uset
, space
);
575 isl_stat
isl_union_set_foreach_set(__isl_keep isl_union_set
*uset
,
576 isl_stat (*fn
)(__isl_take isl_set
*set
, void *user
), void *user
)
578 return isl_union_map_foreach_map(uset
,
579 (isl_stat(*)(__isl_take isl_map
*, void*))fn
, user
);
582 struct isl_union_set_foreach_point_data
{
583 isl_stat (*fn
)(__isl_take isl_point
*pnt
, void *user
);
587 static isl_stat
foreach_point(__isl_take isl_set
*set
, void *user
)
589 struct isl_union_set_foreach_point_data
*data
= user
;
592 r
= isl_set_foreach_point(set
, data
->fn
, data
->user
);
598 isl_stat
isl_union_set_foreach_point(__isl_keep isl_union_set
*uset
,
599 isl_stat (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
601 struct isl_union_set_foreach_point_data data
= { fn
, user
};
602 return isl_union_set_foreach_set(uset
, &foreach_point
, &data
);
605 struct isl_union_map_gen_bin_data
{
606 isl_union_map
*umap2
;
610 static isl_stat
subtract_entry(void **entry
, void *user
)
612 struct isl_union_map_gen_bin_data
*data
= user
;
614 struct isl_hash_table_entry
*entry2
;
615 isl_map
*map
= *entry
;
617 hash
= isl_space_get_hash(map
->dim
);
618 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
619 hash
, &has_dim
, map
->dim
, 0);
620 map
= isl_map_copy(map
);
623 map
= isl_map_subtract(map
, isl_map_copy(entry2
->data
));
625 empty
= isl_map_is_empty(map
);
628 return isl_stat_error
;
635 data
->res
= isl_union_map_add_map(data
->res
, map
);
640 static __isl_give isl_union_map
*gen_bin_op(__isl_take isl_union_map
*umap1
,
641 __isl_take isl_union_map
*umap2
, isl_stat (*fn
)(void **, void *))
643 struct isl_union_map_gen_bin_data data
= { NULL
, NULL
};
645 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
646 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
648 if (!umap1
|| !umap2
)
652 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
654 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
658 isl_union_map_free(umap1
);
659 isl_union_map_free(umap2
);
662 isl_union_map_free(umap1
);
663 isl_union_map_free(umap2
);
664 isl_union_map_free(data
.res
);
668 __isl_give isl_union_map
*isl_union_map_subtract(
669 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
671 return gen_bin_op(umap1
, umap2
, &subtract_entry
);
674 __isl_give isl_union_set
*isl_union_set_subtract(
675 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
677 return isl_union_map_subtract(uset1
, uset2
);
680 struct isl_union_map_gen_bin_set_data
{
685 static isl_stat
intersect_params_entry(void **entry
, void *user
)
687 struct isl_union_map_gen_bin_set_data
*data
= user
;
688 isl_map
*map
= *entry
;
691 map
= isl_map_copy(map
);
692 map
= isl_map_intersect_params(map
, isl_set_copy(data
->set
));
694 empty
= isl_map_is_empty(map
);
697 return isl_stat_error
;
700 data
->res
= isl_union_map_add_map(data
->res
, map
);
705 static __isl_give isl_union_map
*gen_bin_set_op(__isl_take isl_union_map
*umap
,
706 __isl_take isl_set
*set
, isl_stat (*fn
)(void **, void *))
708 struct isl_union_map_gen_bin_set_data data
= { NULL
, NULL
};
710 umap
= isl_union_map_align_params(umap
, isl_set_get_space(set
));
711 set
= isl_set_align_params(set
, isl_union_map_get_space(umap
));
717 data
.res
= isl_union_map_alloc(isl_space_copy(umap
->dim
),
719 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
723 isl_union_map_free(umap
);
727 isl_union_map_free(umap
);
729 isl_union_map_free(data
.res
);
733 /* Intersect "umap" with the parameter domain "set".
735 * If "set" does not have any constraints, then we can return immediately.
737 __isl_give isl_union_map
*isl_union_map_intersect_params(
738 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
742 is_universe
= isl_set_plain_is_universe(set
);
750 return gen_bin_set_op(umap
, set
, &intersect_params_entry
);
752 isl_union_map_free(umap
);
757 __isl_give isl_union_set
*isl_union_set_intersect_params(
758 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
760 return isl_union_map_intersect_params(uset
, set
);
763 static __isl_give isl_union_map
*union_map_intersect_params(
764 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
766 return isl_union_map_intersect_params(umap
,
767 isl_set_from_union_set(uset
));
770 static __isl_give isl_union_map
*union_map_gist_params(
771 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
773 return isl_union_map_gist_params(umap
, isl_set_from_union_set(uset
));
776 struct isl_union_map_match_bin_data
{
777 isl_union_map
*umap2
;
779 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*);
782 static isl_stat
match_bin_entry(void **entry
, void *user
)
784 struct isl_union_map_match_bin_data
*data
= user
;
786 struct isl_hash_table_entry
*entry2
;
787 isl_map
*map
= *entry
;
790 hash
= isl_space_get_hash(map
->dim
);
791 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
792 hash
, &has_dim
, map
->dim
, 0);
796 map
= isl_map_copy(map
);
797 map
= data
->fn(map
, isl_map_copy(entry2
->data
));
799 empty
= isl_map_is_empty(map
);
802 return isl_stat_error
;
809 data
->res
= isl_union_map_add_map(data
->res
, map
);
814 static __isl_give isl_union_map
*match_bin_op(__isl_take isl_union_map
*umap1
,
815 __isl_take isl_union_map
*umap2
,
816 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*))
818 struct isl_union_map_match_bin_data data
= { NULL
, NULL
, fn
};
820 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
821 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
823 if (!umap1
|| !umap2
)
827 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
829 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
830 &match_bin_entry
, &data
) < 0)
833 isl_union_map_free(umap1
);
834 isl_union_map_free(umap2
);
837 isl_union_map_free(umap1
);
838 isl_union_map_free(umap2
);
839 isl_union_map_free(data
.res
);
843 __isl_give isl_union_map
*isl_union_map_intersect(
844 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
846 return match_bin_op(umap1
, umap2
, &isl_map_intersect
);
849 /* Compute the intersection of the two union_sets.
850 * As a special case, if exactly one of the two union_sets
851 * is a parameter domain, then intersect the parameter domain
852 * of the other one with this set.
854 __isl_give isl_union_set
*isl_union_set_intersect(
855 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
859 p1
= isl_union_set_is_params(uset1
);
860 p2
= isl_union_set_is_params(uset2
);
861 if (p1
< 0 || p2
< 0)
864 return union_map_intersect_params(uset1
, uset2
);
866 return union_map_intersect_params(uset2
, uset1
);
867 return isl_union_map_intersect(uset1
, uset2
);
869 isl_union_set_free(uset1
);
870 isl_union_set_free(uset2
);
874 static isl_stat
gist_params_entry(void **entry
, void *user
)
876 struct isl_union_map_gen_bin_set_data
*data
= user
;
877 isl_map
*map
= *entry
;
880 map
= isl_map_copy(map
);
881 map
= isl_map_gist_params(map
, isl_set_copy(data
->set
));
883 empty
= isl_map_is_empty(map
);
886 return isl_stat_error
;
889 data
->res
= isl_union_map_add_map(data
->res
, map
);
894 __isl_give isl_union_map
*isl_union_map_gist_params(
895 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
897 return gen_bin_set_op(umap
, set
, &gist_params_entry
);
900 __isl_give isl_union_set
*isl_union_set_gist_params(
901 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
903 return isl_union_map_gist_params(uset
, set
);
906 __isl_give isl_union_map
*isl_union_map_gist(__isl_take isl_union_map
*umap
,
907 __isl_take isl_union_map
*context
)
909 return match_bin_op(umap
, context
, &isl_map_gist
);
912 __isl_give isl_union_set
*isl_union_set_gist(__isl_take isl_union_set
*uset
,
913 __isl_take isl_union_set
*context
)
915 if (isl_union_set_is_params(context
))
916 return union_map_gist_params(uset
, context
);
917 return isl_union_map_gist(uset
, context
);
920 static __isl_give isl_map
*lex_le_set(__isl_take isl_map
*set1
,
921 __isl_take isl_map
*set2
)
923 return isl_set_lex_le_set(set_from_map(set1
), set_from_map(set2
));
926 static __isl_give isl_map
*lex_lt_set(__isl_take isl_map
*set1
,
927 __isl_take isl_map
*set2
)
929 return isl_set_lex_lt_set(set_from_map(set1
), set_from_map(set2
));
932 __isl_give isl_union_map
*isl_union_set_lex_lt_union_set(
933 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
935 return match_bin_op(uset1
, uset2
, &lex_lt_set
);
938 __isl_give isl_union_map
*isl_union_set_lex_le_union_set(
939 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
941 return match_bin_op(uset1
, uset2
, &lex_le_set
);
944 __isl_give isl_union_map
*isl_union_set_lex_gt_union_set(
945 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
947 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2
, uset1
));
950 __isl_give isl_union_map
*isl_union_set_lex_ge_union_set(
951 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
953 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2
, uset1
));
956 __isl_give isl_union_map
*isl_union_map_lex_gt_union_map(
957 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
959 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2
, umap1
));
962 __isl_give isl_union_map
*isl_union_map_lex_ge_union_map(
963 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
965 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2
, umap1
));
968 static isl_stat
intersect_domain_entry(void **entry
, void *user
)
970 struct isl_union_map_gen_bin_data
*data
= user
;
972 struct isl_hash_table_entry
*entry2
;
974 isl_map
*map
= *entry
;
977 dim
= isl_map_get_space(map
);
978 dim
= isl_space_domain(dim
);
979 hash
= isl_space_get_hash(dim
);
980 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
981 hash
, &has_dim
, dim
, 0);
986 map
= isl_map_copy(map
);
987 map
= isl_map_intersect_domain(map
, isl_set_copy(entry2
->data
));
989 empty
= isl_map_is_empty(map
);
992 return isl_stat_error
;
999 data
->res
= isl_union_map_add_map(data
->res
, map
);
1004 /* Intersect the domain of "umap" with "uset".
1005 * If "uset" is a parameters domain, then intersect the parameter
1006 * domain of "umap" with this set.
1008 __isl_give isl_union_map
*isl_union_map_intersect_domain(
1009 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1011 if (isl_union_set_is_params(uset
))
1012 return union_map_intersect_params(umap
, uset
);
1013 return gen_bin_op(umap
, uset
, &intersect_domain_entry
);
1016 /* Remove the elements of data->umap2 from the domain of *entry
1017 * and add the result to data->res.
1019 static isl_stat
subtract_domain_entry(void **entry
, void *user
)
1021 struct isl_union_map_gen_bin_data
*data
= user
;
1023 struct isl_hash_table_entry
*entry2
;
1025 isl_map
*map
= *entry
;
1028 dim
= isl_map_get_space(map
);
1029 dim
= isl_space_domain(dim
);
1030 hash
= isl_space_get_hash(dim
);
1031 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1032 hash
, &has_dim
, dim
, 0);
1033 isl_space_free(dim
);
1035 map
= isl_map_copy(map
);
1038 data
->res
= isl_union_map_add_map(data
->res
, map
);
1042 map
= isl_map_subtract_domain(map
, isl_set_copy(entry2
->data
));
1044 empty
= isl_map_is_empty(map
);
1047 return isl_stat_error
;
1054 data
->res
= isl_union_map_add_map(data
->res
, map
);
1059 /* Remove the elements of "uset" from the domain of "umap".
1061 __isl_give isl_union_map
*isl_union_map_subtract_domain(
1062 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
1064 return gen_bin_op(umap
, dom
, &subtract_domain_entry
);
1067 /* Remove the elements of data->umap2 from the range of *entry
1068 * and add the result to data->res.
1070 static isl_stat
subtract_range_entry(void **entry
, void *user
)
1072 struct isl_union_map_gen_bin_data
*data
= user
;
1074 struct isl_hash_table_entry
*entry2
;
1076 isl_map
*map
= *entry
;
1079 space
= isl_map_get_space(map
);
1080 space
= isl_space_range(space
);
1081 hash
= isl_space_get_hash(space
);
1082 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1083 hash
, &has_dim
, space
, 0);
1084 isl_space_free(space
);
1086 map
= isl_map_copy(map
);
1089 data
->res
= isl_union_map_add_map(data
->res
, map
);
1093 map
= isl_map_subtract_range(map
, isl_set_copy(entry2
->data
));
1095 empty
= isl_map_is_empty(map
);
1098 return isl_stat_error
;
1105 data
->res
= isl_union_map_add_map(data
->res
, map
);
1110 /* Remove the elements of "uset" from the range of "umap".
1112 __isl_give isl_union_map
*isl_union_map_subtract_range(
1113 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
1115 return gen_bin_op(umap
, dom
, &subtract_range_entry
);
1118 static isl_stat
gist_domain_entry(void **entry
, void *user
)
1120 struct isl_union_map_gen_bin_data
*data
= user
;
1122 struct isl_hash_table_entry
*entry2
;
1124 isl_map
*map
= *entry
;
1127 dim
= isl_map_get_space(map
);
1128 dim
= isl_space_domain(dim
);
1129 hash
= isl_space_get_hash(dim
);
1130 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1131 hash
, &has_dim
, dim
, 0);
1132 isl_space_free(dim
);
1136 map
= isl_map_copy(map
);
1137 map
= isl_map_gist_domain(map
, isl_set_copy(entry2
->data
));
1139 empty
= isl_map_is_empty(map
);
1142 return isl_stat_error
;
1145 data
->res
= isl_union_map_add_map(data
->res
, map
);
1150 /* Compute the gist of "umap" with respect to the domain "uset".
1151 * If "uset" is a parameters domain, then compute the gist
1152 * with respect to this parameter domain.
1154 __isl_give isl_union_map
*isl_union_map_gist_domain(
1155 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1157 if (isl_union_set_is_params(uset
))
1158 return union_map_gist_params(umap
, uset
);
1159 return gen_bin_op(umap
, uset
, &gist_domain_entry
);
1162 static isl_stat
gist_range_entry(void **entry
, void *user
)
1164 struct isl_union_map_gen_bin_data
*data
= user
;
1166 struct isl_hash_table_entry
*entry2
;
1168 isl_map
*map
= *entry
;
1171 space
= isl_map_get_space(map
);
1172 space
= isl_space_range(space
);
1173 hash
= isl_space_get_hash(space
);
1174 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1175 hash
, &has_dim
, space
, 0);
1176 isl_space_free(space
);
1180 map
= isl_map_copy(map
);
1181 map
= isl_map_gist_range(map
, isl_set_copy(entry2
->data
));
1183 empty
= isl_map_is_empty(map
);
1186 return isl_stat_error
;
1189 data
->res
= isl_union_map_add_map(data
->res
, map
);
1194 /* Compute the gist of "umap" with respect to the range "uset".
1196 __isl_give isl_union_map
*isl_union_map_gist_range(
1197 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1199 return gen_bin_op(umap
, uset
, &gist_range_entry
);
1202 static isl_stat
intersect_range_entry(void **entry
, void *user
)
1204 struct isl_union_map_gen_bin_data
*data
= user
;
1206 struct isl_hash_table_entry
*entry2
;
1208 isl_map
*map
= *entry
;
1211 dim
= isl_map_get_space(map
);
1212 dim
= isl_space_range(dim
);
1213 hash
= isl_space_get_hash(dim
);
1214 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1215 hash
, &has_dim
, dim
, 0);
1216 isl_space_free(dim
);
1220 map
= isl_map_copy(map
);
1221 map
= isl_map_intersect_range(map
, isl_set_copy(entry2
->data
));
1223 empty
= isl_map_is_empty(map
);
1226 return isl_stat_error
;
1233 data
->res
= isl_union_map_add_map(data
->res
, map
);
1238 __isl_give isl_union_map
*isl_union_map_intersect_range(
1239 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1241 return gen_bin_op(umap
, uset
, &intersect_range_entry
);
1244 struct isl_union_map_bin_data
{
1245 isl_union_map
*umap2
;
1248 isl_stat (*fn
)(void **entry
, void *user
);
1251 static isl_stat
apply_range_entry(void **entry
, void *user
)
1253 struct isl_union_map_bin_data
*data
= user
;
1254 isl_map
*map2
= *entry
;
1257 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1258 map2
->dim
, isl_dim_in
))
1261 map2
= isl_map_apply_range(isl_map_copy(data
->map
), isl_map_copy(map2
));
1263 empty
= isl_map_is_empty(map2
);
1266 return isl_stat_error
;
1273 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1278 static isl_stat
bin_entry(void **entry
, void *user
)
1280 struct isl_union_map_bin_data
*data
= user
;
1281 isl_map
*map
= *entry
;
1284 if (isl_hash_table_foreach(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1285 data
->fn
, data
) < 0)
1286 return isl_stat_error
;
1291 static __isl_give isl_union_map
*bin_op(__isl_take isl_union_map
*umap1
,
1292 __isl_take isl_union_map
*umap2
,
1293 isl_stat (*fn
)(void **entry
, void *user
))
1295 struct isl_union_map_bin_data data
= { NULL
, NULL
, NULL
, fn
};
1297 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1298 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1300 if (!umap1
|| !umap2
)
1304 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
1306 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1307 &bin_entry
, &data
) < 0)
1310 isl_union_map_free(umap1
);
1311 isl_union_map_free(umap2
);
1314 isl_union_map_free(umap1
);
1315 isl_union_map_free(umap2
);
1316 isl_union_map_free(data
.res
);
1320 __isl_give isl_union_map
*isl_union_map_apply_range(
1321 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1323 return bin_op(umap1
, umap2
, &apply_range_entry
);
1326 __isl_give isl_union_map
*isl_union_map_apply_domain(
1327 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1329 umap1
= isl_union_map_reverse(umap1
);
1330 umap1
= isl_union_map_apply_range(umap1
, umap2
);
1331 return isl_union_map_reverse(umap1
);
1334 __isl_give isl_union_set
*isl_union_set_apply(
1335 __isl_take isl_union_set
*uset
, __isl_take isl_union_map
*umap
)
1337 return isl_union_map_apply_range(uset
, umap
);
1340 static isl_stat
map_lex_lt_entry(void **entry
, void *user
)
1342 struct isl_union_map_bin_data
*data
= user
;
1343 isl_map
*map2
= *entry
;
1345 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1346 map2
->dim
, isl_dim_out
))
1349 map2
= isl_map_lex_lt_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1351 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1356 __isl_give isl_union_map
*isl_union_map_lex_lt_union_map(
1357 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1359 return bin_op(umap1
, umap2
, &map_lex_lt_entry
);
1362 static isl_stat
map_lex_le_entry(void **entry
, void *user
)
1364 struct isl_union_map_bin_data
*data
= user
;
1365 isl_map
*map2
= *entry
;
1367 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1368 map2
->dim
, isl_dim_out
))
1371 map2
= isl_map_lex_le_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1373 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1378 __isl_give isl_union_map
*isl_union_map_lex_le_union_map(
1379 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1381 return bin_op(umap1
, umap2
, &map_lex_le_entry
);
1384 static isl_stat
product_entry(void **entry
, void *user
)
1386 struct isl_union_map_bin_data
*data
= user
;
1387 isl_map
*map2
= *entry
;
1389 map2
= isl_map_product(isl_map_copy(data
->map
), isl_map_copy(map2
));
1391 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1396 __isl_give isl_union_map
*isl_union_map_product(__isl_take isl_union_map
*umap1
,
1397 __isl_take isl_union_map
*umap2
)
1399 return bin_op(umap1
, umap2
, &product_entry
);
1402 static isl_stat
set_product_entry(void **entry
, void *user
)
1404 struct isl_union_map_bin_data
*data
= user
;
1405 isl_set
*set2
= *entry
;
1407 set2
= isl_set_product(isl_set_copy(data
->map
), isl_set_copy(set2
));
1409 data
->res
= isl_union_set_add_set(data
->res
, set2
);
1414 __isl_give isl_union_set
*isl_union_set_product(__isl_take isl_union_set
*uset1
,
1415 __isl_take isl_union_set
*uset2
)
1417 return bin_op(uset1
, uset2
, &set_product_entry
);
1420 static isl_stat
domain_product_entry(void **entry
, void *user
)
1422 struct isl_union_map_bin_data
*data
= user
;
1423 isl_map
*map2
= *entry
;
1425 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1426 map2
->dim
, isl_dim_out
))
1429 map2
= isl_map_domain_product(isl_map_copy(data
->map
),
1430 isl_map_copy(map2
));
1432 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1437 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1439 __isl_give isl_union_map
*isl_union_map_domain_product(
1440 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1442 return bin_op(umap1
, umap2
, &domain_product_entry
);
1445 static isl_stat
range_product_entry(void **entry
, void *user
)
1447 struct isl_union_map_bin_data
*data
= user
;
1448 isl_map
*map2
= *entry
;
1450 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_in
,
1451 map2
->dim
, isl_dim_in
))
1454 map2
= isl_map_range_product(isl_map_copy(data
->map
),
1455 isl_map_copy(map2
));
1457 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1462 __isl_give isl_union_map
*isl_union_map_range_product(
1463 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1465 return bin_op(umap1
, umap2
, &range_product_entry
);
1468 /* If data->map A -> B and "map2" C -> D have the same range space,
1469 * then add (A, C) -> (B * D) to data->res.
1471 static isl_stat
flat_domain_product_entry(void **entry
, void *user
)
1473 struct isl_union_map_bin_data
*data
= user
;
1474 isl_map
*map2
= *entry
;
1476 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1477 map2
->dim
, isl_dim_out
))
1480 map2
= isl_map_flat_domain_product(isl_map_copy(data
->map
),
1481 isl_map_copy(map2
));
1483 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1488 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B * D).
1490 __isl_give isl_union_map
*isl_union_map_flat_domain_product(
1491 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1493 return bin_op(umap1
, umap2
, &flat_domain_product_entry
);
1496 static isl_stat
flat_range_product_entry(void **entry
, void *user
)
1498 struct isl_union_map_bin_data
*data
= user
;
1499 isl_map
*map2
= *entry
;
1501 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_in
,
1502 map2
->dim
, isl_dim_in
))
1505 map2
= isl_map_flat_range_product(isl_map_copy(data
->map
),
1506 isl_map_copy(map2
));
1508 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1513 __isl_give isl_union_map
*isl_union_map_flat_range_product(
1514 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1516 return bin_op(umap1
, umap2
, &flat_range_product_entry
);
1519 static __isl_give isl_union_set
*cond_un_op(__isl_take isl_union_map
*umap
,
1520 isl_stat (*fn
)(void **, void *))
1527 res
= isl_union_map_alloc(isl_space_copy(umap
->dim
), umap
->table
.n
);
1528 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, &res
) < 0)
1531 isl_union_map_free(umap
);
1534 isl_union_map_free(umap
);
1535 isl_union_set_free(res
);
1539 static isl_stat
from_range_entry(void **entry
, void *user
)
1541 isl_map
*set
= *entry
;
1542 isl_union_set
**res
= user
;
1544 *res
= isl_union_map_add_map(*res
,
1545 isl_map_from_range(isl_set_copy(set
)));
1550 __isl_give isl_union_map
*isl_union_map_from_range(
1551 __isl_take isl_union_set
*uset
)
1553 return cond_un_op(uset
, &from_range_entry
);
1556 __isl_give isl_union_map
*isl_union_map_from_domain(
1557 __isl_take isl_union_set
*uset
)
1559 return isl_union_map_reverse(isl_union_map_from_range(uset
));
1562 __isl_give isl_union_map
*isl_union_map_from_domain_and_range(
1563 __isl_take isl_union_set
*domain
, __isl_take isl_union_set
*range
)
1565 return isl_union_map_apply_range(isl_union_map_from_domain(domain
),
1566 isl_union_map_from_range(range
));
1569 static __isl_give isl_union_map
*un_op(__isl_take isl_union_map
*umap
,
1570 isl_stat (*fn
)(void **, void *))
1572 umap
= isl_union_map_cow(umap
);
1576 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, NULL
) < 0)
1581 isl_union_map_free(umap
);
1585 static isl_stat
affine_entry(void **entry
, void *user
)
1587 isl_map
**map
= (isl_map
**)entry
;
1589 *map
= isl_map_from_basic_map(isl_map_affine_hull(*map
));
1591 return *map
? isl_stat_ok
: isl_stat_error
;
1594 __isl_give isl_union_map
*isl_union_map_affine_hull(
1595 __isl_take isl_union_map
*umap
)
1597 return un_op(umap
, &affine_entry
);
1600 __isl_give isl_union_set
*isl_union_set_affine_hull(
1601 __isl_take isl_union_set
*uset
)
1603 return isl_union_map_affine_hull(uset
);
1606 static isl_stat
polyhedral_entry(void **entry
, void *user
)
1608 isl_map
**map
= (isl_map
**)entry
;
1610 *map
= isl_map_from_basic_map(isl_map_polyhedral_hull(*map
));
1612 return *map
? isl_stat_ok
: isl_stat_error
;
1615 __isl_give isl_union_map
*isl_union_map_polyhedral_hull(
1616 __isl_take isl_union_map
*umap
)
1618 return un_op(umap
, &polyhedral_entry
);
1621 __isl_give isl_union_set
*isl_union_set_polyhedral_hull(
1622 __isl_take isl_union_set
*uset
)
1624 return isl_union_map_polyhedral_hull(uset
);
1627 static isl_stat
simple_entry(void **entry
, void *user
)
1629 isl_map
**map
= (isl_map
**)entry
;
1631 *map
= isl_map_from_basic_map(isl_map_simple_hull(*map
));
1633 return *map
? isl_stat_ok
: isl_stat_error
;
1636 __isl_give isl_union_map
*isl_union_map_simple_hull(
1637 __isl_take isl_union_map
*umap
)
1639 return un_op(umap
, &simple_entry
);
1642 __isl_give isl_union_set
*isl_union_set_simple_hull(
1643 __isl_take isl_union_set
*uset
)
1645 return isl_union_map_simple_hull(uset
);
1648 static isl_stat
inplace_entry(void **entry
, void *user
)
1650 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*);
1651 isl_map
**map
= (isl_map
**)entry
;
1654 fn
= *(__isl_give isl_map
*(**)(__isl_take isl_map
*)) user
;
1655 copy
= fn(isl_map_copy(*map
));
1657 return isl_stat_error
;
1665 static __isl_give isl_union_map
*inplace(__isl_take isl_union_map
*umap
,
1666 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*))
1671 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1672 &inplace_entry
, &fn
) < 0)
1677 isl_union_map_free(umap
);
1681 /* Remove redundant constraints in each of the basic maps of "umap".
1682 * Since removing redundant constraints does not change the meaning
1683 * or the space, the operation can be performed in-place.
1685 __isl_give isl_union_map
*isl_union_map_remove_redundancies(
1686 __isl_take isl_union_map
*umap
)
1688 return inplace(umap
, &isl_map_remove_redundancies
);
1691 /* Remove redundant constraints in each of the basic sets of "uset".
1693 __isl_give isl_union_set
*isl_union_set_remove_redundancies(
1694 __isl_take isl_union_set
*uset
)
1696 return isl_union_map_remove_redundancies(uset
);
1699 __isl_give isl_union_map
*isl_union_map_coalesce(
1700 __isl_take isl_union_map
*umap
)
1702 return inplace(umap
, &isl_map_coalesce
);
1705 __isl_give isl_union_set
*isl_union_set_coalesce(
1706 __isl_take isl_union_set
*uset
)
1708 return isl_union_map_coalesce(uset
);
1711 __isl_give isl_union_map
*isl_union_map_detect_equalities(
1712 __isl_take isl_union_map
*umap
)
1714 return inplace(umap
, &isl_map_detect_equalities
);
1717 __isl_give isl_union_set
*isl_union_set_detect_equalities(
1718 __isl_take isl_union_set
*uset
)
1720 return isl_union_map_detect_equalities(uset
);
1723 __isl_give isl_union_map
*isl_union_map_compute_divs(
1724 __isl_take isl_union_map
*umap
)
1726 return inplace(umap
, &isl_map_compute_divs
);
1729 __isl_give isl_union_set
*isl_union_set_compute_divs(
1730 __isl_take isl_union_set
*uset
)
1732 return isl_union_map_compute_divs(uset
);
1735 static isl_stat
lexmin_entry(void **entry
, void *user
)
1737 isl_map
**map
= (isl_map
**)entry
;
1739 *map
= isl_map_lexmin(*map
);
1741 return *map
? isl_stat_ok
: isl_stat_error
;
1744 __isl_give isl_union_map
*isl_union_map_lexmin(
1745 __isl_take isl_union_map
*umap
)
1747 return un_op(umap
, &lexmin_entry
);
1750 __isl_give isl_union_set
*isl_union_set_lexmin(
1751 __isl_take isl_union_set
*uset
)
1753 return isl_union_map_lexmin(uset
);
1756 static isl_stat
lexmax_entry(void **entry
, void *user
)
1758 isl_map
**map
= (isl_map
**)entry
;
1760 *map
= isl_map_lexmax(*map
);
1762 return *map
? isl_stat_ok
: isl_stat_error
;
1765 __isl_give isl_union_map
*isl_union_map_lexmax(
1766 __isl_take isl_union_map
*umap
)
1768 return un_op(umap
, &lexmax_entry
);
1771 __isl_give isl_union_set
*isl_union_set_lexmax(
1772 __isl_take isl_union_set
*uset
)
1774 return isl_union_map_lexmax(uset
);
1777 static isl_stat
universe_entry(void **entry
, void *user
)
1779 isl_map
*map
= *entry
;
1780 isl_union_map
**res
= user
;
1782 map
= isl_map_universe(isl_map_get_space(map
));
1783 *res
= isl_union_map_add_map(*res
, map
);
1788 __isl_give isl_union_map
*isl_union_map_universe(__isl_take isl_union_map
*umap
)
1790 return cond_un_op(umap
, &universe_entry
);
1793 __isl_give isl_union_set
*isl_union_set_universe(__isl_take isl_union_set
*uset
)
1795 return isl_union_map_universe(uset
);
1798 static isl_stat
reverse_entry(void **entry
, void *user
)
1800 isl_map
*map
= *entry
;
1801 isl_union_map
**res
= user
;
1803 *res
= isl_union_map_add_map(*res
, isl_map_reverse(isl_map_copy(map
)));
1808 __isl_give isl_union_map
*isl_union_map_reverse(__isl_take isl_union_map
*umap
)
1810 return cond_un_op(umap
, &reverse_entry
);
1813 static isl_stat
params_entry(void **entry
, void *user
)
1815 isl_map
*map
= *entry
;
1816 isl_union_set
**res
= user
;
1818 *res
= isl_union_set_add_set(*res
, isl_map_params(isl_map_copy(map
)));
1823 /* Compute the parameter domain of the given union map.
1825 __isl_give isl_set
*isl_union_map_params(__isl_take isl_union_map
*umap
)
1829 empty
= isl_union_map_is_empty(umap
);
1834 space
= isl_union_map_get_space(umap
);
1835 isl_union_map_free(umap
);
1836 return isl_set_empty(space
);
1838 return isl_set_from_union_set(cond_un_op(umap
, ¶ms_entry
));
1840 isl_union_map_free(umap
);
1844 /* Compute the parameter domain of the given union set.
1846 __isl_give isl_set
*isl_union_set_params(__isl_take isl_union_set
*uset
)
1848 return isl_union_map_params(uset
);
1851 static isl_stat
domain_entry(void **entry
, void *user
)
1853 isl_map
*map
= *entry
;
1854 isl_union_set
**res
= user
;
1856 *res
= isl_union_set_add_set(*res
, isl_map_domain(isl_map_copy(map
)));
1861 __isl_give isl_union_set
*isl_union_map_domain(__isl_take isl_union_map
*umap
)
1863 return cond_un_op(umap
, &domain_entry
);
1866 static isl_stat
range_entry(void **entry
, void *user
)
1868 isl_map
*map
= *entry
;
1869 isl_union_set
**res
= user
;
1871 *res
= isl_union_set_add_set(*res
, isl_map_range(isl_map_copy(map
)));
1876 __isl_give isl_union_set
*isl_union_map_range(__isl_take isl_union_map
*umap
)
1878 return cond_un_op(umap
, &range_entry
);
1881 static isl_stat
domain_map_entry(void **entry
, void *user
)
1883 isl_map
*map
= *entry
;
1884 isl_union_set
**res
= user
;
1886 *res
= isl_union_map_add_map(*res
,
1887 isl_map_domain_map(isl_map_copy(map
)));
1892 __isl_give isl_union_map
*isl_union_map_domain_map(
1893 __isl_take isl_union_map
*umap
)
1895 return cond_un_op(umap
, &domain_map_entry
);
1898 /* Construct an isl_pw_multi_aff that maps "map" to its domain and
1899 * add the result to "res".
1901 static isl_stat
domain_map_upma(__isl_take isl_map
*map
, void *user
)
1903 isl_union_pw_multi_aff
**res
= user
;
1905 isl_pw_multi_aff
*pma
;
1907 ma
= isl_multi_aff_domain_map(isl_map_get_space(map
));
1908 pma
= isl_pw_multi_aff_alloc(isl_map_wrap(map
), ma
);
1909 *res
= isl_union_pw_multi_aff_add_pw_multi_aff(*res
, pma
);
1911 return *res
? isl_stat_ok
: isl_stat_error
;
1915 /* Return an isl_union_pw_multi_aff that maps a wrapped copy of "umap"
1918 __isl_give isl_union_pw_multi_aff
*isl_union_map_domain_map_union_pw_multi_aff(
1919 __isl_take isl_union_map
*umap
)
1921 isl_union_pw_multi_aff
*res
;
1923 res
= isl_union_pw_multi_aff_empty(isl_union_map_get_space(umap
));
1924 if (isl_union_map_foreach_map(umap
, &domain_map_upma
, &res
) < 0)
1925 res
= isl_union_pw_multi_aff_free(res
);
1927 isl_union_map_free(umap
);
1931 static isl_stat
range_map_entry(void **entry
, void *user
)
1933 isl_map
*map
= *entry
;
1934 isl_union_set
**res
= user
;
1936 *res
= isl_union_map_add_map(*res
,
1937 isl_map_range_map(isl_map_copy(map
)));
1942 __isl_give isl_union_map
*isl_union_map_range_map(
1943 __isl_take isl_union_map
*umap
)
1945 return cond_un_op(umap
, &range_map_entry
);
1948 /* Check if "set" is of the form A[B -> C].
1949 * If so, add A[B -> C] -> B to "res".
1951 static isl_stat
wrapped_domain_map_entry(void **entry
, void *user
)
1953 isl_set
*set
= *entry
;
1954 isl_union_set
**res
= user
;
1957 wrapping
= isl_set_is_wrapping(set
);
1959 return isl_stat_error
;
1963 *res
= isl_union_map_add_map(*res
,
1964 isl_set_wrapped_domain_map(isl_set_copy(set
)));
1969 /* Given a collection of wrapped maps of the form A[B -> C],
1970 * return the collection of maps A[B -> C] -> B.
1972 __isl_give isl_union_map
*isl_union_set_wrapped_domain_map(
1973 __isl_take isl_union_set
*uset
)
1975 return cond_un_op(uset
, &wrapped_domain_map_entry
);
1978 static isl_stat
deltas_entry(void **entry
, void *user
)
1980 isl_map
*map
= *entry
;
1981 isl_union_set
**res
= user
;
1983 if (!isl_space_tuple_is_equal(map
->dim
, isl_dim_in
,
1984 map
->dim
, isl_dim_out
))
1987 *res
= isl_union_set_add_set(*res
, isl_map_deltas(isl_map_copy(map
)));
1992 __isl_give isl_union_set
*isl_union_map_deltas(__isl_take isl_union_map
*umap
)
1994 return cond_un_op(umap
, &deltas_entry
);
1997 static isl_stat
deltas_map_entry(void **entry
, void *user
)
1999 isl_map
*map
= *entry
;
2000 isl_union_map
**res
= user
;
2002 if (!isl_space_tuple_is_equal(map
->dim
, isl_dim_in
,
2003 map
->dim
, isl_dim_out
))
2006 *res
= isl_union_map_add_map(*res
,
2007 isl_map_deltas_map(isl_map_copy(map
)));
2012 __isl_give isl_union_map
*isl_union_map_deltas_map(
2013 __isl_take isl_union_map
*umap
)
2015 return cond_un_op(umap
, &deltas_map_entry
);
2018 static isl_stat
identity_entry(void **entry
, void *user
)
2020 isl_set
*set
= *entry
;
2021 isl_union_map
**res
= user
;
2023 *res
= isl_union_map_add_map(*res
, isl_set_identity(isl_set_copy(set
)));
2028 __isl_give isl_union_map
*isl_union_set_identity(__isl_take isl_union_set
*uset
)
2030 return cond_un_op(uset
, &identity_entry
);
2033 /* Construct an identity isl_pw_multi_aff on "set" and add it to *res.
2035 static isl_stat
identity_upma(__isl_take isl_set
*set
, void *user
)
2037 isl_union_pw_multi_aff
**res
= user
;
2039 isl_pw_multi_aff
*pma
;
2041 space
= isl_space_map_from_set(isl_set_get_space(set
));
2042 pma
= isl_pw_multi_aff_identity(space
);
2043 pma
= isl_pw_multi_aff_intersect_domain(pma
, set
);
2044 *res
= isl_union_pw_multi_aff_add_pw_multi_aff(*res
, pma
);
2046 return *res
? isl_stat_ok
: isl_stat_error
;
2049 /* Return an identity function on "uset" in the form
2050 * of an isl_union_pw_multi_aff.
2052 __isl_give isl_union_pw_multi_aff
*isl_union_set_identity_union_pw_multi_aff(
2053 __isl_take isl_union_set
*uset
)
2055 isl_union_pw_multi_aff
*res
;
2057 res
= isl_union_pw_multi_aff_empty(isl_union_set_get_space(uset
));
2058 if (isl_union_set_foreach_set(uset
, &identity_upma
, &res
) < 0)
2059 res
= isl_union_pw_multi_aff_free(res
);
2061 isl_union_set_free(uset
);
2065 /* If "map" is of the form [A -> B] -> C, then add A -> C to "res".
2067 static isl_stat
domain_factor_domain_entry(void **entry
, void *user
)
2069 isl_map
*map
= *entry
;
2070 isl_union_map
**res
= user
;
2072 if (!isl_map_domain_is_wrapping(map
))
2075 *res
= isl_union_map_add_map(*res
,
2076 isl_map_domain_factor_domain(isl_map_copy(map
)));
2078 return *res
? isl_stat_ok
: isl_stat_error
;
2081 /* For each map in "umap" of the form [A -> B] -> C,
2082 * construct the map A -> C and collect the results.
2084 __isl_give isl_union_map
*isl_union_map_domain_factor_domain(
2085 __isl_take isl_union_map
*umap
)
2087 return cond_un_op(umap
, &domain_factor_domain_entry
);
2090 /* If "map" is of the form [A -> B] -> C, then add B -> C to "res".
2092 static isl_stat
domain_factor_range_entry(void **entry
, void *user
)
2094 isl_map
*map
= *entry
;
2095 isl_union_map
**res
= user
;
2097 if (!isl_map_domain_is_wrapping(map
))
2100 *res
= isl_union_map_add_map(*res
,
2101 isl_map_domain_factor_range(isl_map_copy(map
)));
2103 return *res
? isl_stat_ok
: isl_stat_error
;
2106 /* For each map in "umap" of the form [A -> B] -> C,
2107 * construct the map B -> C and collect the results.
2109 __isl_give isl_union_map
*isl_union_map_domain_factor_range(
2110 __isl_take isl_union_map
*umap
)
2112 return cond_un_op(umap
, &domain_factor_range_entry
);
2115 /* If "map" is of the form A -> [B -> C], then add A -> B to "res".
2117 static isl_stat
range_factor_domain_entry(void **entry
, void *user
)
2119 isl_map
*map
= *entry
;
2120 isl_union_map
**res
= user
;
2122 if (!isl_map_range_is_wrapping(map
))
2125 *res
= isl_union_map_add_map(*res
,
2126 isl_map_range_factor_domain(isl_map_copy(map
)));
2128 return *res
? isl_stat_ok
: isl_stat_error
;
2131 /* For each map in "umap" of the form A -> [B -> C],
2132 * construct the map A -> B and collect the results.
2134 __isl_give isl_union_map
*isl_union_map_range_factor_domain(
2135 __isl_take isl_union_map
*umap
)
2137 return cond_un_op(umap
, &range_factor_domain_entry
);
2140 /* If "map" is of the form A -> [B -> C], then add A -> C to "res".
2142 static isl_stat
range_factor_range_entry(void **entry
, void *user
)
2144 isl_map
*map
= *entry
;
2145 isl_union_map
**res
= user
;
2147 if (!isl_map_range_is_wrapping(map
))
2150 *res
= isl_union_map_add_map(*res
,
2151 isl_map_range_factor_range(isl_map_copy(map
)));
2153 return *res
? isl_stat_ok
: isl_stat_error
;
2156 /* For each map in "umap" of the form A -> [B -> C],
2157 * construct the map A -> C and collect the results.
2159 __isl_give isl_union_map
*isl_union_map_range_factor_range(
2160 __isl_take isl_union_map
*umap
)
2162 return cond_un_op(umap
, &range_factor_range_entry
);
2165 /* If "map" is of the form [A -> B] -> [C -> D], then add A -> C to "res".
2167 static isl_stat
factor_domain_entry(void **entry
, void *user
)
2169 isl_map
*map
= *entry
;
2170 isl_union_map
**res
= user
;
2172 if (!isl_map_domain_is_wrapping(map
) || !isl_map_range_is_wrapping(map
))
2175 *res
= isl_union_map_add_map(*res
,
2176 isl_map_factor_domain(isl_map_copy(map
)));
2178 return *res
? isl_stat_ok
: isl_stat_error
;
2181 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2182 * construct the map A -> C and collect the results.
2184 __isl_give isl_union_map
*isl_union_map_factor_domain(
2185 __isl_take isl_union_map
*umap
)
2187 return cond_un_op(umap
, &factor_domain_entry
);
2190 /* If "map" is of the form [A -> B] -> [C -> D], then add B -> D to "res".
2192 static isl_stat
factor_range_entry(void **entry
, void *user
)
2194 isl_map
*map
= *entry
;
2195 isl_union_map
**res
= user
;
2197 if (!isl_map_domain_is_wrapping(map
) || !isl_map_range_is_wrapping(map
))
2200 *res
= isl_union_map_add_map(*res
,
2201 isl_map_factor_range(isl_map_copy(map
)));
2203 return *res
? isl_stat_ok
: isl_stat_error
;
2206 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2207 * construct the map B -> D and collect the results.
2209 __isl_give isl_union_map
*isl_union_map_factor_range(
2210 __isl_take isl_union_map
*umap
)
2212 return cond_un_op(umap
, &factor_range_entry
);
2215 static isl_stat
unwrap_entry(void **entry
, void *user
)
2217 isl_set
*set
= *entry
;
2218 isl_union_set
**res
= user
;
2220 if (!isl_set_is_wrapping(set
))
2223 *res
= isl_union_map_add_map(*res
, isl_set_unwrap(isl_set_copy(set
)));
2228 __isl_give isl_union_map
*isl_union_set_unwrap(__isl_take isl_union_set
*uset
)
2230 return cond_un_op(uset
, &unwrap_entry
);
2233 static isl_stat
wrap_entry(void **entry
, void *user
)
2235 isl_map
*map
= *entry
;
2236 isl_union_set
**res
= user
;
2238 *res
= isl_union_set_add_set(*res
, isl_map_wrap(isl_map_copy(map
)));
2243 __isl_give isl_union_set
*isl_union_map_wrap(__isl_take isl_union_map
*umap
)
2245 return cond_un_op(umap
, &wrap_entry
);
2248 struct isl_union_map_is_subset_data
{
2249 isl_union_map
*umap2
;
2253 static isl_stat
is_subset_entry(void **entry
, void *user
)
2255 struct isl_union_map_is_subset_data
*data
= user
;
2257 struct isl_hash_table_entry
*entry2
;
2258 isl_map
*map
= *entry
;
2260 hash
= isl_space_get_hash(map
->dim
);
2261 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
2262 hash
, &has_dim
, map
->dim
, 0);
2264 int empty
= isl_map_is_empty(map
);
2266 return isl_stat_error
;
2269 data
->is_subset
= 0;
2270 return isl_stat_error
;
2273 data
->is_subset
= isl_map_is_subset(map
, entry2
->data
);
2274 if (data
->is_subset
< 0 || !data
->is_subset
)
2275 return isl_stat_error
;
2280 isl_bool
isl_union_map_is_subset(__isl_keep isl_union_map
*umap1
,
2281 __isl_keep isl_union_map
*umap2
)
2283 struct isl_union_map_is_subset_data data
= { NULL
, isl_bool_true
};
2285 umap1
= isl_union_map_copy(umap1
);
2286 umap2
= isl_union_map_copy(umap2
);
2287 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
2288 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
2290 if (!umap1
|| !umap2
)
2294 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
2295 &is_subset_entry
, &data
) < 0 &&
2299 isl_union_map_free(umap1
);
2300 isl_union_map_free(umap2
);
2302 return data
.is_subset
;
2304 isl_union_map_free(umap1
);
2305 isl_union_map_free(umap2
);
2306 return isl_bool_error
;
2309 isl_bool
isl_union_set_is_subset(__isl_keep isl_union_set
*uset1
,
2310 __isl_keep isl_union_set
*uset2
)
2312 return isl_union_map_is_subset(uset1
, uset2
);
2315 isl_bool
isl_union_map_is_equal(__isl_keep isl_union_map
*umap1
,
2316 __isl_keep isl_union_map
*umap2
)
2320 if (!umap1
|| !umap2
)
2321 return isl_bool_error
;
2322 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
2323 if (is_subset
!= isl_bool_true
)
2325 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
2329 isl_bool
isl_union_set_is_equal(__isl_keep isl_union_set
*uset1
,
2330 __isl_keep isl_union_set
*uset2
)
2332 return isl_union_map_is_equal(uset1
, uset2
);
2335 isl_bool
isl_union_map_is_strict_subset(__isl_keep isl_union_map
*umap1
,
2336 __isl_keep isl_union_map
*umap2
)
2340 if (!umap1
|| !umap2
)
2341 return isl_bool_error
;
2342 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
2343 if (is_subset
!= isl_bool_true
)
2345 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
2346 if (is_subset
== isl_bool_error
)
2351 isl_bool
isl_union_set_is_strict_subset(__isl_keep isl_union_set
*uset1
,
2352 __isl_keep isl_union_set
*uset2
)
2354 return isl_union_map_is_strict_subset(uset1
, uset2
);
2357 /* Internal data structure for isl_union_map_is_disjoint.
2358 * umap2 is the union map with which we are comparing.
2359 * is_disjoint is initialized to 1 and is set to 0 as soon
2360 * as the union maps turn out not to be disjoint.
2362 struct isl_union_map_is_disjoint_data
{
2363 isl_union_map
*umap2
;
2364 isl_bool is_disjoint
;
2367 /* Check if "map" is disjoint from data->umap2 and abort
2368 * the search if it is not.
2370 static isl_stat
is_disjoint_entry(void **entry
, void *user
)
2372 struct isl_union_map_is_disjoint_data
*data
= user
;
2374 struct isl_hash_table_entry
*entry2
;
2375 isl_map
*map
= *entry
;
2377 hash
= isl_space_get_hash(map
->dim
);
2378 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
2379 hash
, &has_dim
, map
->dim
, 0);
2383 data
->is_disjoint
= isl_map_is_disjoint(map
, entry2
->data
);
2384 if (data
->is_disjoint
< 0 || !data
->is_disjoint
)
2385 return isl_stat_error
;
2390 /* Are "umap1" and "umap2" disjoint?
2392 isl_bool
isl_union_map_is_disjoint(__isl_keep isl_union_map
*umap1
,
2393 __isl_keep isl_union_map
*umap2
)
2395 struct isl_union_map_is_disjoint_data data
= { NULL
, isl_bool_true
};
2397 umap1
= isl_union_map_copy(umap1
);
2398 umap2
= isl_union_map_copy(umap2
);
2399 umap1
= isl_union_map_align_params(umap1
,
2400 isl_union_map_get_space(umap2
));
2401 umap2
= isl_union_map_align_params(umap2
,
2402 isl_union_map_get_space(umap1
));
2404 if (!umap1
|| !umap2
)
2408 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
2409 &is_disjoint_entry
, &data
) < 0 &&
2413 isl_union_map_free(umap1
);
2414 isl_union_map_free(umap2
);
2416 return data
.is_disjoint
;
2418 isl_union_map_free(umap1
);
2419 isl_union_map_free(umap2
);
2420 return isl_bool_error
;
2423 /* Are "uset1" and "uset2" disjoint?
2425 isl_bool
isl_union_set_is_disjoint(__isl_keep isl_union_set
*uset1
,
2426 __isl_keep isl_union_set
*uset2
)
2428 return isl_union_map_is_disjoint(uset1
, uset2
);
2431 static isl_stat
sample_entry(void **entry
, void *user
)
2433 isl_basic_map
**sample
= (isl_basic_map
**)user
;
2434 isl_map
*map
= *entry
;
2436 *sample
= isl_map_sample(isl_map_copy(map
));
2438 return isl_stat_error
;
2439 if (!isl_basic_map_plain_is_empty(*sample
))
2440 return isl_stat_error
;
2444 __isl_give isl_basic_map
*isl_union_map_sample(__isl_take isl_union_map
*umap
)
2446 isl_basic_map
*sample
= NULL
;
2451 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2452 &sample_entry
, &sample
) < 0 &&
2457 sample
= isl_basic_map_empty(isl_union_map_get_space(umap
));
2459 isl_union_map_free(umap
);
2463 isl_union_map_free(umap
);
2467 __isl_give isl_basic_set
*isl_union_set_sample(__isl_take isl_union_set
*uset
)
2469 return bset_from_bmap(isl_union_map_sample(uset
));
2472 /* Return an element in "uset" in the form of an isl_point.
2473 * Return a void isl_point if "uset" is empty.
2475 __isl_give isl_point
*isl_union_set_sample_point(__isl_take isl_union_set
*uset
)
2477 return isl_basic_set_sample_point(isl_union_set_sample(uset
));
2480 struct isl_forall_data
{
2482 isl_bool (*fn
)(__isl_keep isl_map
*map
);
2485 static isl_stat
forall_entry(void **entry
, void *user
)
2487 struct isl_forall_data
*data
= user
;
2488 isl_map
*map
= *entry
;
2490 data
->res
= data
->fn(map
);
2492 return isl_stat_error
;
2495 return isl_stat_error
;
2500 static isl_bool
union_map_forall(__isl_keep isl_union_map
*umap
,
2501 isl_bool (*fn
)(__isl_keep isl_map
*map
))
2503 struct isl_forall_data data
= { isl_bool_true
, fn
};
2506 return isl_bool_error
;
2508 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2509 &forall_entry
, &data
) < 0 && data
.res
)
2510 return isl_bool_error
;
2515 struct isl_forall_user_data
{
2517 isl_bool (*fn
)(__isl_keep isl_map
*map
, void *user
);
2521 static isl_stat
forall_user_entry(void **entry
, void *user
)
2523 struct isl_forall_user_data
*data
= user
;
2524 isl_map
*map
= *entry
;
2526 data
->res
= data
->fn(map
, data
->user
);
2528 return isl_stat_error
;
2531 return isl_stat_error
;
2536 /* Check if fn(map, user) returns true for all maps "map" in umap.
2538 static isl_bool
union_map_forall_user(__isl_keep isl_union_map
*umap
,
2539 isl_bool (*fn
)(__isl_keep isl_map
*map
, void *user
), void *user
)
2541 struct isl_forall_user_data data
= { isl_bool_true
, fn
, user
};
2544 return isl_bool_error
;
2546 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2547 &forall_user_entry
, &data
) < 0 && data
.res
)
2548 return isl_bool_error
;
2553 isl_bool
isl_union_map_is_empty(__isl_keep isl_union_map
*umap
)
2555 return union_map_forall(umap
, &isl_map_is_empty
);
2558 isl_bool
isl_union_set_is_empty(__isl_keep isl_union_set
*uset
)
2560 return isl_union_map_is_empty(uset
);
2563 static isl_bool
is_subset_of_identity(__isl_keep isl_map
*map
)
2570 return isl_bool_error
;
2572 if (!isl_space_tuple_is_equal(map
->dim
, isl_dim_in
,
2573 map
->dim
, isl_dim_out
))
2574 return isl_bool_false
;
2576 dim
= isl_map_get_space(map
);
2577 id
= isl_map_identity(dim
);
2579 is_subset
= isl_map_is_subset(map
, id
);
2586 /* Given an isl_union_map that consists of a single map, check
2587 * if it is single-valued.
2589 static isl_bool
single_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2594 umap
= isl_union_map_copy(umap
);
2595 map
= isl_map_from_union_map(umap
);
2596 sv
= isl_map_is_single_valued(map
);
2602 /* Internal data structure for single_valued_on_domain.
2604 * "umap" is the union map to be tested.
2605 * "sv" is set to 1 as long as "umap" may still be single-valued.
2607 struct isl_union_map_is_sv_data
{
2608 isl_union_map
*umap
;
2612 /* Check if the data->umap is single-valued on "set".
2614 * If data->umap consists of a single map on "set", then test it
2617 * Otherwise, compute
2621 * check if the result is a subset of the identity mapping and
2622 * store the result in data->sv.
2624 * Terminate as soon as data->umap has been determined not to
2627 static isl_stat
single_valued_on_domain(__isl_take isl_set
*set
, void *user
)
2629 struct isl_union_map_is_sv_data
*data
= user
;
2630 isl_union_map
*umap
, *test
;
2632 umap
= isl_union_map_copy(data
->umap
);
2633 umap
= isl_union_map_intersect_domain(umap
,
2634 isl_union_set_from_set(set
));
2636 if (isl_union_map_n_map(umap
) == 1) {
2637 data
->sv
= single_map_is_single_valued(umap
);
2638 isl_union_map_free(umap
);
2640 test
= isl_union_map_reverse(isl_union_map_copy(umap
));
2641 test
= isl_union_map_apply_range(test
, umap
);
2643 data
->sv
= union_map_forall(test
, &is_subset_of_identity
);
2645 isl_union_map_free(test
);
2648 if (data
->sv
< 0 || !data
->sv
)
2649 return isl_stat_error
;
2653 /* Check if the given map is single-valued.
2655 * If the union map consists of a single map, then test it as an isl_map.
2656 * Otherwise, check if the union map is single-valued on each of its
2659 isl_bool
isl_union_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2661 isl_union_map
*universe
;
2662 isl_union_set
*domain
;
2663 struct isl_union_map_is_sv_data data
;
2665 if (isl_union_map_n_map(umap
) == 1)
2666 return single_map_is_single_valued(umap
);
2668 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
2669 domain
= isl_union_map_domain(universe
);
2671 data
.sv
= isl_bool_true
;
2673 if (isl_union_set_foreach_set(domain
,
2674 &single_valued_on_domain
, &data
) < 0 && data
.sv
)
2675 data
.sv
= isl_bool_error
;
2676 isl_union_set_free(domain
);
2681 isl_bool
isl_union_map_is_injective(__isl_keep isl_union_map
*umap
)
2685 umap
= isl_union_map_copy(umap
);
2686 umap
= isl_union_map_reverse(umap
);
2687 in
= isl_union_map_is_single_valued(umap
);
2688 isl_union_map_free(umap
);
2693 /* Is "map" obviously not an identity relation because
2694 * it maps elements from one space to another space?
2695 * Update *non_identity accordingly.
2697 * In particular, if the domain and range spaces are the same,
2698 * then the map is not considered to obviously not be an identity relation.
2699 * Otherwise, the map is considered to obviously not be an identity relation
2700 * if it is is non-empty.
2702 * If "map" is determined to obviously not be an identity relation,
2703 * then the search is aborted.
2705 static isl_stat
map_plain_is_not_identity(__isl_take isl_map
*map
, void *user
)
2707 isl_bool
*non_identity
= user
;
2711 space
= isl_map_get_space(map
);
2712 equal
= isl_space_tuple_is_equal(space
, isl_dim_in
, space
, isl_dim_out
);
2713 if (equal
>= 0 && !equal
)
2714 *non_identity
= isl_bool_not(isl_map_is_empty(map
));
2716 *non_identity
= isl_bool_not(equal
);
2717 isl_space_free(space
);
2720 if (*non_identity
< 0 || *non_identity
)
2721 return isl_stat_error
;
2726 /* Is "umap" obviously not an identity relation because
2727 * it maps elements from one space to another space?
2729 * As soon as a map has been found that maps elements to a different space,
2730 * non_identity is changed and the search is aborted.
2732 static isl_bool
isl_union_map_plain_is_not_identity(
2733 __isl_keep isl_union_map
*umap
)
2735 isl_bool non_identity
;
2737 non_identity
= isl_bool_false
;
2738 if (isl_union_map_foreach_map(umap
, &map_plain_is_not_identity
,
2739 &non_identity
) < 0 &&
2740 non_identity
== isl_bool_false
)
2741 return isl_bool_error
;
2743 return non_identity
;
2746 /* Does "map" only map elements to themselves?
2747 * Update *identity accordingly.
2749 * If "map" is determined not to be an identity relation,
2750 * then the search is aborted.
2752 static isl_stat
map_is_identity(__isl_take isl_map
*map
, void *user
)
2754 isl_bool
*identity
= user
;
2756 *identity
= isl_map_is_identity(map
);
2759 if (*identity
< 0 || !*identity
)
2760 return isl_stat_error
;
2765 /* Does "umap" only map elements to themselves?
2767 * First check if there are any maps that map elements to different spaces.
2768 * If not, then check that all the maps (between identical spaces)
2769 * are identity relations.
2771 isl_bool
isl_union_map_is_identity(__isl_keep isl_union_map
*umap
)
2773 isl_bool non_identity
;
2776 non_identity
= isl_union_map_plain_is_not_identity(umap
);
2777 if (non_identity
< 0 || non_identity
)
2778 return isl_bool_not(non_identity
);
2780 identity
= isl_bool_true
;
2781 if (isl_union_map_foreach_map(umap
, &map_is_identity
, &identity
) < 0 &&
2782 identity
== isl_bool_true
)
2783 return isl_bool_error
;
2788 /* Represents a map that has a fixed value (v) for one of its
2790 * The map in this structure is not reference counted, so it
2791 * is only valid while the isl_union_map from which it was
2792 * obtained is still alive.
2794 struct isl_fixed_map
{
2799 static struct isl_fixed_map
*alloc_isl_fixed_map_array(isl_ctx
*ctx
,
2803 struct isl_fixed_map
*v
;
2805 v
= isl_calloc_array(ctx
, struct isl_fixed_map
, n
);
2808 for (i
= 0; i
< n
; ++i
)
2809 isl_int_init(v
[i
].v
);
2813 static void free_isl_fixed_map_array(struct isl_fixed_map
*v
, int n
)
2819 for (i
= 0; i
< n
; ++i
)
2820 isl_int_clear(v
[i
].v
);
2824 /* Compare the "v" field of two isl_fixed_map structs.
2826 static int qsort_fixed_map_cmp(const void *p1
, const void *p2
)
2828 const struct isl_fixed_map
*e1
= (const struct isl_fixed_map
*) p1
;
2829 const struct isl_fixed_map
*e2
= (const struct isl_fixed_map
*) p2
;
2831 return isl_int_cmp(e1
->v
, e2
->v
);
2834 /* Internal data structure used while checking whether all maps
2835 * in a union_map have a fixed value for a given output dimension.
2836 * v is the list of maps, with the fixed value for the dimension
2837 * n is the number of maps considered so far
2838 * pos is the output dimension under investigation
2840 struct isl_fixed_dim_data
{
2841 struct isl_fixed_map
*v
;
2846 static isl_bool
fixed_at_pos(__isl_keep isl_map
*map
, void *user
)
2848 struct isl_fixed_dim_data
*data
= user
;
2850 data
->v
[data
->n
].map
= map
;
2851 return isl_map_plain_is_fixed(map
, isl_dim_out
, data
->pos
,
2852 &data
->v
[data
->n
++].v
);
2855 static isl_bool
plain_injective_on_range(__isl_take isl_union_map
*umap
,
2856 int first
, int n_range
);
2858 /* Given a list of the maps, with their fixed values at output dimension "pos",
2859 * check whether the ranges of the maps form an obvious partition.
2861 * We first sort the maps according to their fixed values.
2862 * If all maps have a different value, then we know the ranges form
2864 * Otherwise, we collect the maps with the same fixed value and
2865 * check whether each such collection is obviously injective
2866 * based on later dimensions.
2868 static int separates(struct isl_fixed_map
*v
, int n
,
2869 __isl_take isl_space
*dim
, int pos
, int n_range
)
2876 qsort(v
, n
, sizeof(*v
), &qsort_fixed_map_cmp
);
2878 for (i
= 0; i
+ 1 < n
; ++i
) {
2880 isl_union_map
*part
;
2883 for (j
= i
+ 1; j
< n
; ++j
)
2884 if (isl_int_ne(v
[i
].v
, v
[j
].v
))
2890 part
= isl_union_map_alloc(isl_space_copy(dim
), j
- i
);
2891 for (k
= i
; k
< j
; ++k
)
2892 part
= isl_union_map_add_map(part
,
2893 isl_map_copy(v
[k
].map
));
2895 injective
= plain_injective_on_range(part
, pos
+ 1, n_range
);
2904 isl_space_free(dim
);
2905 free_isl_fixed_map_array(v
, n
);
2908 isl_space_free(dim
);
2909 free_isl_fixed_map_array(v
, n
);
2913 /* Check whether the maps in umap have obviously distinct ranges.
2914 * In particular, check for an output dimension in the range
2915 * [first,n_range) for which all maps have a fixed value
2916 * and then check if these values, possibly along with fixed values
2917 * at later dimensions, entail distinct ranges.
2919 static isl_bool
plain_injective_on_range(__isl_take isl_union_map
*umap
,
2920 int first
, int n_range
)
2924 struct isl_fixed_dim_data data
= { NULL
};
2926 ctx
= isl_union_map_get_ctx(umap
);
2928 n
= isl_union_map_n_map(umap
);
2933 isl_union_map_free(umap
);
2934 return isl_bool_true
;
2937 if (first
>= n_range
) {
2938 isl_union_map_free(umap
);
2939 return isl_bool_false
;
2942 data
.v
= alloc_isl_fixed_map_array(ctx
, n
);
2946 for (data
.pos
= first
; data
.pos
< n_range
; ++data
.pos
) {
2952 fixed
= union_map_forall_user(umap
, &fixed_at_pos
, &data
);
2957 dim
= isl_union_map_get_space(umap
);
2958 injective
= separates(data
.v
, n
, dim
, data
.pos
, n_range
);
2959 isl_union_map_free(umap
);
2963 free_isl_fixed_map_array(data
.v
, n
);
2964 isl_union_map_free(umap
);
2966 return isl_bool_false
;
2968 free_isl_fixed_map_array(data
.v
, n
);
2969 isl_union_map_free(umap
);
2970 return isl_bool_error
;
2973 /* Check whether the maps in umap that map to subsets of "ran"
2974 * have obviously distinct ranges.
2976 static isl_bool
plain_injective_on_range_wrap(__isl_keep isl_set
*ran
,
2979 isl_union_map
*umap
= user
;
2981 umap
= isl_union_map_copy(umap
);
2982 umap
= isl_union_map_intersect_range(umap
,
2983 isl_union_set_from_set(isl_set_copy(ran
)));
2984 return plain_injective_on_range(umap
, 0, isl_set_dim(ran
, isl_dim_set
));
2987 /* Check if the given union_map is obviously injective.
2989 * In particular, we first check if all individual maps are obviously
2990 * injective and then check if all the ranges of these maps are
2991 * obviously disjoint.
2993 isl_bool
isl_union_map_plain_is_injective(__isl_keep isl_union_map
*umap
)
2996 isl_union_map
*univ
;
2999 in
= union_map_forall(umap
, &isl_map_plain_is_injective
);
3001 return isl_bool_error
;
3003 return isl_bool_false
;
3005 univ
= isl_union_map_universe(isl_union_map_copy(umap
));
3006 ran
= isl_union_map_range(univ
);
3008 in
= union_map_forall_user(ran
, &plain_injective_on_range_wrap
, umap
);
3010 isl_union_set_free(ran
);
3015 isl_bool
isl_union_map_is_bijective(__isl_keep isl_union_map
*umap
)
3019 sv
= isl_union_map_is_single_valued(umap
);
3023 return isl_union_map_is_injective(umap
);
3026 static isl_stat
zip_entry(void **entry
, void *user
)
3028 isl_map
*map
= *entry
;
3029 isl_union_map
**res
= user
;
3031 if (!isl_map_can_zip(map
))
3034 *res
= isl_union_map_add_map(*res
, isl_map_zip(isl_map_copy(map
)));
3039 __isl_give isl_union_map
*isl_union_map_zip(__isl_take isl_union_map
*umap
)
3041 return cond_un_op(umap
, &zip_entry
);
3044 static isl_stat
uncurry_entry(void **entry
, void *user
)
3046 isl_map
*map
= *entry
;
3047 isl_union_map
**res
= user
;
3049 if (!isl_map_can_uncurry(map
))
3052 *res
= isl_union_map_add_map(*res
, isl_map_uncurry(isl_map_copy(map
)));
3057 /* Given a union map, take the maps of the form A -> (B -> C) and
3058 * return the union of the corresponding maps (A -> B) -> C.
3060 __isl_give isl_union_map
*isl_union_map_uncurry(__isl_take isl_union_map
*umap
)
3062 return cond_un_op(umap
, &uncurry_entry
);
3065 static isl_stat
curry_entry(void **entry
, void *user
)
3067 isl_map
*map
= *entry
;
3068 isl_union_map
**res
= user
;
3070 if (!isl_map_can_curry(map
))
3073 *res
= isl_union_map_add_map(*res
, isl_map_curry(isl_map_copy(map
)));
3078 /* Given a union map, take the maps of the form (A -> B) -> C and
3079 * return the union of the corresponding maps A -> (B -> C).
3081 __isl_give isl_union_map
*isl_union_map_curry(__isl_take isl_union_map
*umap
)
3083 return cond_un_op(umap
, &curry_entry
);
3086 /* If *entry is of the form A -> ((B -> C) -> D), then apply
3087 * isl_map_range_curry to it and add the result to *res.
3089 static isl_stat
range_curry_entry(void **entry
, void *user
)
3091 isl_map
*map
= *entry
;
3092 isl_union_map
**res
= user
;
3094 if (!isl_map_can_range_curry(map
))
3097 map
= isl_map_range_curry(isl_map_copy(map
));
3098 *res
= isl_union_map_add_map(*res
, map
);
3103 /* Given a union map, take the maps of the form A -> ((B -> C) -> D) and
3104 * return the union of the corresponding maps A -> (B -> (C -> D)).
3106 __isl_give isl_union_map
*isl_union_map_range_curry(
3107 __isl_take isl_union_map
*umap
)
3109 return cond_un_op(umap
, &range_curry_entry
);
3112 static isl_stat
lift_entry(void **entry
, void *user
)
3114 isl_set
*set
= *entry
;
3115 isl_union_set
**res
= user
;
3117 *res
= isl_union_set_add_set(*res
, isl_set_lift(isl_set_copy(set
)));
3122 __isl_give isl_union_set
*isl_union_set_lift(__isl_take isl_union_set
*uset
)
3124 return cond_un_op(uset
, &lift_entry
);
3127 static isl_stat
coefficients_entry(void **entry
, void *user
)
3129 isl_set
*set
= *entry
;
3130 isl_union_set
**res
= user
;
3132 set
= isl_set_copy(set
);
3133 set
= isl_set_from_basic_set(isl_set_coefficients(set
));
3134 *res
= isl_union_set_add_set(*res
, set
);
3139 __isl_give isl_union_set
*isl_union_set_coefficients(
3140 __isl_take isl_union_set
*uset
)
3149 ctx
= isl_union_set_get_ctx(uset
);
3150 dim
= isl_space_set_alloc(ctx
, 0, 0);
3151 res
= isl_union_map_alloc(dim
, uset
->table
.n
);
3152 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
3153 &coefficients_entry
, &res
) < 0)
3156 isl_union_set_free(uset
);
3159 isl_union_set_free(uset
);
3160 isl_union_set_free(res
);
3164 static isl_stat
solutions_entry(void **entry
, void *user
)
3166 isl_set
*set
= *entry
;
3167 isl_union_set
**res
= user
;
3169 set
= isl_set_copy(set
);
3170 set
= isl_set_from_basic_set(isl_set_solutions(set
));
3172 *res
= isl_union_set_from_set(set
);
3174 *res
= isl_union_set_add_set(*res
, set
);
3177 return isl_stat_error
;
3182 __isl_give isl_union_set
*isl_union_set_solutions(
3183 __isl_take isl_union_set
*uset
)
3185 isl_union_set
*res
= NULL
;
3190 if (uset
->table
.n
== 0) {
3191 res
= isl_union_set_empty(isl_union_set_get_space(uset
));
3192 isl_union_set_free(uset
);
3196 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
3197 &solutions_entry
, &res
) < 0)
3200 isl_union_set_free(uset
);
3203 isl_union_set_free(uset
);
3204 isl_union_set_free(res
);
3208 /* Is the domain space of "map" equal to "space"?
3210 static int domain_match(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
)
3212 return isl_space_tuple_is_equal(map
->dim
, isl_dim_in
,
3213 space
, isl_dim_out
);
3216 /* Is the range space of "map" equal to "space"?
3218 static int range_match(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
)
3220 return isl_space_tuple_is_equal(map
->dim
, isl_dim_out
,
3221 space
, isl_dim_out
);
3224 /* Is the set space of "map" equal to "space"?
3226 static int set_match(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
)
3228 return isl_space_tuple_is_equal(map
->dim
, isl_dim_set
,
3229 space
, isl_dim_out
);
3232 /* Internal data structure for preimage_pw_multi_aff.
3234 * "pma" is the function under which the preimage should be taken.
3235 * "space" is the space of "pma".
3236 * "res" collects the results.
3237 * "fn" computes the preimage for a given map.
3238 * "match" returns true if "fn" can be called.
3240 struct isl_union_map_preimage_data
{
3242 isl_pw_multi_aff
*pma
;
3244 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
);
3245 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3246 __isl_take isl_pw_multi_aff
*pma
);
3249 /* Call data->fn to compute the preimage of the domain or range of *entry
3250 * under the function represented by data->pma, provided the domain/range
3251 * space of *entry matches the target space of data->pma
3252 * (as given by data->match), and add the result to data->res.
3254 static isl_stat
preimage_entry(void **entry
, void *user
)
3257 isl_map
*map
= *entry
;
3258 struct isl_union_map_preimage_data
*data
= user
;
3261 m
= data
->match(map
, data
->space
);
3263 return isl_stat_error
;
3267 map
= isl_map_copy(map
);
3268 map
= data
->fn(map
, isl_pw_multi_aff_copy(data
->pma
));
3270 empty
= isl_map_is_empty(map
);
3271 if (empty
< 0 || empty
) {
3273 return empty
< 0 ? isl_stat_error
: isl_stat_ok
;
3276 data
->res
= isl_union_map_add_map(data
->res
, map
);
3281 /* Compute the preimage of the domain or range of "umap" under the function
3282 * represented by "pma".
3283 * In other words, plug in "pma" in the domain or range of "umap".
3284 * The function "fn" performs the actual preimage computation on a map,
3285 * while "match" determines to which maps the function should be applied.
3287 static __isl_give isl_union_map
*preimage_pw_multi_aff(
3288 __isl_take isl_union_map
*umap
, __isl_take isl_pw_multi_aff
*pma
,
3289 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
),
3290 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3291 __isl_take isl_pw_multi_aff
*pma
))
3295 struct isl_union_map_preimage_data data
;
3297 umap
= isl_union_map_align_params(umap
,
3298 isl_pw_multi_aff_get_space(pma
));
3299 pma
= isl_pw_multi_aff_align_params(pma
, isl_union_map_get_space(umap
));
3304 ctx
= isl_union_map_get_ctx(umap
);
3305 space
= isl_union_map_get_space(umap
);
3306 data
.space
= isl_pw_multi_aff_get_space(pma
);
3308 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
3311 if (isl_hash_table_foreach(ctx
, &umap
->table
, &preimage_entry
,
3313 data
.res
= isl_union_map_free(data
.res
);
3315 isl_space_free(data
.space
);
3316 isl_union_map_free(umap
);
3317 isl_pw_multi_aff_free(pma
);
3320 isl_union_map_free(umap
);
3321 isl_pw_multi_aff_free(pma
);
3325 /* Compute the preimage of the domain of "umap" under the function
3326 * represented by "pma".
3327 * In other words, plug in "pma" in the domain of "umap".
3328 * The result contains maps that live in the same spaces as the maps of "umap"
3329 * with domain space equal to the target space of "pma",
3330 * except that the domain has been replaced by the domain space of "pma".
3332 __isl_give isl_union_map
*isl_union_map_preimage_domain_pw_multi_aff(
3333 __isl_take isl_union_map
*umap
, __isl_take isl_pw_multi_aff
*pma
)
3335 return preimage_pw_multi_aff(umap
, pma
, &domain_match
,
3336 &isl_map_preimage_domain_pw_multi_aff
);
3339 /* Compute the preimage of the range of "umap" under the function
3340 * represented by "pma".
3341 * In other words, plug in "pma" in the range of "umap".
3342 * The result contains maps that live in the same spaces as the maps of "umap"
3343 * with range space equal to the target space of "pma",
3344 * except that the range has been replaced by the domain space of "pma".
3346 __isl_give isl_union_map
*isl_union_map_preimage_range_pw_multi_aff(
3347 __isl_take isl_union_map
*umap
, __isl_take isl_pw_multi_aff
*pma
)
3349 return preimage_pw_multi_aff(umap
, pma
, &range_match
,
3350 &isl_map_preimage_range_pw_multi_aff
);
3353 /* Compute the preimage of "uset" under the function represented by "pma".
3354 * In other words, plug in "pma" in "uset".
3355 * The result contains sets that live in the same spaces as the sets of "uset"
3356 * with space equal to the target space of "pma",
3357 * except that the space has been replaced by the domain space of "pma".
3359 __isl_give isl_union_set
*isl_union_set_preimage_pw_multi_aff(
3360 __isl_take isl_union_set
*uset
, __isl_take isl_pw_multi_aff
*pma
)
3362 return preimage_pw_multi_aff(uset
, pma
, &set_match
,
3363 &isl_set_preimage_pw_multi_aff
);
3366 /* Compute the preimage of the domain of "umap" under the function
3367 * represented by "ma".
3368 * In other words, plug in "ma" in the domain of "umap".
3369 * The result contains maps that live in the same spaces as the maps of "umap"
3370 * with domain space equal to the target space of "ma",
3371 * except that the domain has been replaced by the domain space of "ma".
3373 __isl_give isl_union_map
*isl_union_map_preimage_domain_multi_aff(
3374 __isl_take isl_union_map
*umap
, __isl_take isl_multi_aff
*ma
)
3376 return isl_union_map_preimage_domain_pw_multi_aff(umap
,
3377 isl_pw_multi_aff_from_multi_aff(ma
));
3380 /* Compute the preimage of the range of "umap" under the function
3381 * represented by "ma".
3382 * In other words, plug in "ma" in the range of "umap".
3383 * The result contains maps that live in the same spaces as the maps of "umap"
3384 * with range space equal to the target space of "ma",
3385 * except that the range has been replaced by the domain space of "ma".
3387 __isl_give isl_union_map
*isl_union_map_preimage_range_multi_aff(
3388 __isl_take isl_union_map
*umap
, __isl_take isl_multi_aff
*ma
)
3390 return isl_union_map_preimage_range_pw_multi_aff(umap
,
3391 isl_pw_multi_aff_from_multi_aff(ma
));
3394 /* Compute the preimage of "uset" under the function represented by "ma".
3395 * In other words, plug in "ma" in "uset".
3396 * The result contains sets that live in the same spaces as the sets of "uset"
3397 * with space equal to the target space of "ma",
3398 * except that the space has been replaced by the domain space of "ma".
3400 __isl_give isl_union_map
*isl_union_set_preimage_multi_aff(
3401 __isl_take isl_union_set
*uset
, __isl_take isl_multi_aff
*ma
)
3403 return isl_union_set_preimage_pw_multi_aff(uset
,
3404 isl_pw_multi_aff_from_multi_aff(ma
));
3407 /* Internal data structure for preimage_multi_pw_aff.
3409 * "mpa" is the function under which the preimage should be taken.
3410 * "space" is the space of "mpa".
3411 * "res" collects the results.
3412 * "fn" computes the preimage for a given map.
3413 * "match" returns true if "fn" can be called.
3415 struct isl_union_map_preimage_mpa_data
{
3417 isl_multi_pw_aff
*mpa
;
3419 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
);
3420 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3421 __isl_take isl_multi_pw_aff
*mpa
);
3424 /* Call data->fn to compute the preimage of the domain or range of *entry
3425 * under the function represented by data->mpa, provided the domain/range
3426 * space of *entry matches the target space of data->mpa
3427 * (as given by data->match), and add the result to data->res.
3429 static isl_stat
preimage_mpa_entry(void **entry
, void *user
)
3432 isl_map
*map
= *entry
;
3433 struct isl_union_map_preimage_mpa_data
*data
= user
;
3436 m
= data
->match(map
, data
->space
);
3438 return isl_stat_error
;
3442 map
= isl_map_copy(map
);
3443 map
= data
->fn(map
, isl_multi_pw_aff_copy(data
->mpa
));
3445 empty
= isl_map_is_empty(map
);
3446 if (empty
< 0 || empty
) {
3448 return empty
< 0 ? isl_stat_error
: isl_stat_ok
;
3451 data
->res
= isl_union_map_add_map(data
->res
, map
);
3456 /* Compute the preimage of the domain or range of "umap" under the function
3457 * represented by "mpa".
3458 * In other words, plug in "mpa" in the domain or range of "umap".
3459 * The function "fn" performs the actual preimage computation on a map,
3460 * while "match" determines to which maps the function should be applied.
3462 static __isl_give isl_union_map
*preimage_multi_pw_aff(
3463 __isl_take isl_union_map
*umap
, __isl_take isl_multi_pw_aff
*mpa
,
3464 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
),
3465 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3466 __isl_take isl_multi_pw_aff
*mpa
))
3470 struct isl_union_map_preimage_mpa_data data
;
3472 umap
= isl_union_map_align_params(umap
,
3473 isl_multi_pw_aff_get_space(mpa
));
3474 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_union_map_get_space(umap
));
3479 ctx
= isl_union_map_get_ctx(umap
);
3480 space
= isl_union_map_get_space(umap
);
3481 data
.space
= isl_multi_pw_aff_get_space(mpa
);
3483 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
3486 if (isl_hash_table_foreach(ctx
, &umap
->table
, &preimage_mpa_entry
,
3488 data
.res
= isl_union_map_free(data
.res
);
3490 isl_space_free(data
.space
);
3491 isl_union_map_free(umap
);
3492 isl_multi_pw_aff_free(mpa
);
3495 isl_union_map_free(umap
);
3496 isl_multi_pw_aff_free(mpa
);
3500 /* Compute the preimage of the domain of "umap" under the function
3501 * represented by "mpa".
3502 * In other words, plug in "mpa" in the domain of "umap".
3503 * The result contains maps that live in the same spaces as the maps of "umap"
3504 * with domain space equal to the target space of "mpa",
3505 * except that the domain has been replaced by the domain space of "mpa".
3507 __isl_give isl_union_map
*isl_union_map_preimage_domain_multi_pw_aff(
3508 __isl_take isl_union_map
*umap
, __isl_take isl_multi_pw_aff
*mpa
)
3510 return preimage_multi_pw_aff(umap
, mpa
, &domain_match
,
3511 &isl_map_preimage_domain_multi_pw_aff
);
3514 /* Internal data structure for preimage_upma.
3516 * "umap" is the map of which the preimage should be computed.
3517 * "res" collects the results.
3518 * "fn" computes the preimage for a given piecewise multi-affine function.
3520 struct isl_union_map_preimage_upma_data
{
3521 isl_union_map
*umap
;
3523 __isl_give isl_union_map
*(*fn
)(__isl_take isl_union_map
*umap
,
3524 __isl_take isl_pw_multi_aff
*pma
);
3527 /* Call data->fn to compute the preimage of the domain or range of data->umap
3528 * under the function represented by pma and add the result to data->res.
3530 static isl_stat
preimage_upma(__isl_take isl_pw_multi_aff
*pma
, void *user
)
3532 struct isl_union_map_preimage_upma_data
*data
= user
;
3533 isl_union_map
*umap
;
3535 umap
= isl_union_map_copy(data
->umap
);
3536 umap
= data
->fn(umap
, pma
);
3537 data
->res
= isl_union_map_union(data
->res
, umap
);
3539 return data
->res
? isl_stat_ok
: isl_stat_error
;
3542 /* Compute the preimage of the domain or range of "umap" under the function
3543 * represented by "upma".
3544 * In other words, plug in "upma" in the domain or range of "umap".
3545 * The function "fn" performs the actual preimage computation
3546 * on a piecewise multi-affine function.
3548 static __isl_give isl_union_map
*preimage_union_pw_multi_aff(
3549 __isl_take isl_union_map
*umap
,
3550 __isl_take isl_union_pw_multi_aff
*upma
,
3551 __isl_give isl_union_map
*(*fn
)(__isl_take isl_union_map
*umap
,
3552 __isl_take isl_pw_multi_aff
*pma
))
3554 struct isl_union_map_preimage_upma_data data
;
3557 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3559 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
3560 &preimage_upma
, &data
) < 0)
3561 data
.res
= isl_union_map_free(data
.res
);
3563 isl_union_map_free(umap
);
3564 isl_union_pw_multi_aff_free(upma
);
3569 /* Compute the preimage of the domain of "umap" under the function
3570 * represented by "upma".
3571 * In other words, plug in "upma" in the domain of "umap".
3572 * The result contains maps that live in the same spaces as the maps of "umap"
3573 * with domain space equal to one of the target spaces of "upma",
3574 * except that the domain has been replaced by one of the the domain spaces that
3575 * corresponds to that target space of "upma".
3577 __isl_give isl_union_map
*isl_union_map_preimage_domain_union_pw_multi_aff(
3578 __isl_take isl_union_map
*umap
,
3579 __isl_take isl_union_pw_multi_aff
*upma
)
3581 return preimage_union_pw_multi_aff(umap
, upma
,
3582 &isl_union_map_preimage_domain_pw_multi_aff
);
3585 /* Compute the preimage of the range of "umap" under the function
3586 * represented by "upma".
3587 * In other words, plug in "upma" in the range of "umap".
3588 * The result contains maps that live in the same spaces as the maps of "umap"
3589 * with range space equal to one of the target spaces of "upma",
3590 * except that the range has been replaced by one of the the domain spaces that
3591 * corresponds to that target space of "upma".
3593 __isl_give isl_union_map
*isl_union_map_preimage_range_union_pw_multi_aff(
3594 __isl_take isl_union_map
*umap
,
3595 __isl_take isl_union_pw_multi_aff
*upma
)
3597 return preimage_union_pw_multi_aff(umap
, upma
,
3598 &isl_union_map_preimage_range_pw_multi_aff
);
3601 /* Compute the preimage of "uset" under the function represented by "upma".
3602 * In other words, plug in "upma" in the range of "uset".
3603 * The result contains sets that live in the same spaces as the sets of "uset"
3604 * with space equal to one of the target spaces of "upma",
3605 * except that the space has been replaced by one of the the domain spaces that
3606 * corresponds to that target space of "upma".
3608 __isl_give isl_union_set
*isl_union_set_preimage_union_pw_multi_aff(
3609 __isl_take isl_union_set
*uset
,
3610 __isl_take isl_union_pw_multi_aff
*upma
)
3612 return preimage_union_pw_multi_aff(uset
, upma
,
3613 &isl_union_set_preimage_pw_multi_aff
);
3616 /* Reset the user pointer on all identifiers of parameters and tuples
3617 * of the space of *entry.
3619 static isl_stat
reset_user(void **entry
, void *user
)
3621 isl_map
**map
= (isl_map
**)entry
;
3623 *map
= isl_map_reset_user(*map
);
3625 return *map
? isl_stat_ok
: isl_stat_error
;
3628 /* Reset the user pointer on all identifiers of parameters and tuples
3629 * of the spaces of "umap".
3631 __isl_give isl_union_map
*isl_union_map_reset_user(
3632 __isl_take isl_union_map
*umap
)
3634 umap
= isl_union_map_cow(umap
);
3637 umap
->dim
= isl_space_reset_user(umap
->dim
);
3639 return isl_union_map_free(umap
);
3640 umap
= un_op(umap
, &reset_user
);
3645 /* Reset the user pointer on all identifiers of parameters and tuples
3646 * of the spaces of "uset".
3648 __isl_give isl_union_set
*isl_union_set_reset_user(
3649 __isl_take isl_union_set
*uset
)
3651 return isl_union_map_reset_user(uset
);
3654 /* Internal data structure for isl_union_map_project_out.
3655 * "type", "first" and "n" are the arguments for the isl_map_project_out
3657 * "res" collects the results.
3659 struct isl_union_map_project_out_data
{
3660 enum isl_dim_type type
;
3667 /* Turn the data->n dimensions of type data->type, starting at data->first
3668 * into existentially quantified variables and add the result to data->res.
3670 static isl_stat
project_out(__isl_take isl_map
*map
, void *user
)
3672 struct isl_union_map_project_out_data
*data
= user
;
3674 map
= isl_map_project_out(map
, data
->type
, data
->first
, data
->n
);
3675 data
->res
= isl_union_map_add_map(data
->res
, map
);
3680 /* Turn the "n" dimensions of type "type", starting at "first"
3681 * into existentially quantified variables.
3682 * Since the space of an isl_union_map only contains parameters,
3683 * type is required to be equal to isl_dim_param.
3685 __isl_give isl_union_map
*isl_union_map_project_out(
3686 __isl_take isl_union_map
*umap
,
3687 enum isl_dim_type type
, unsigned first
, unsigned n
)
3690 struct isl_union_map_project_out_data data
= { type
, first
, n
};
3695 if (type
!= isl_dim_param
)
3696 isl_die(isl_union_map_get_ctx(umap
), isl_error_invalid
,
3697 "can only project out parameters",
3698 return isl_union_map_free(umap
));
3700 space
= isl_union_map_get_space(umap
);
3701 space
= isl_space_drop_dims(space
, type
, first
, n
);
3702 data
.res
= isl_union_map_empty(space
);
3703 if (isl_union_map_foreach_map(umap
, &project_out
, &data
) < 0)
3704 data
.res
= isl_union_map_free(data
.res
);
3706 isl_union_map_free(umap
);
3711 /* Turn the "n" dimensions of type "type", starting at "first"
3712 * into existentially quantified variables.
3713 * Since the space of an isl_union_set only contains parameters,
3714 * "type" is required to be equal to isl_dim_param.
3716 __isl_give isl_union_set
*isl_union_set_project_out(
3717 __isl_take isl_union_set
*uset
,
3718 enum isl_dim_type type
, unsigned first
, unsigned n
)
3720 return isl_union_map_project_out(uset
, type
, first
, n
);
3723 /* Internal data structure for isl_union_map_involves_dims.
3724 * "first" and "n" are the arguments for the isl_map_involves_dims calls.
3726 struct isl_union_map_involves_dims_data
{
3731 /* Does "map" _not_ involve the data->n parameters starting at data->first?
3733 static isl_bool
map_excludes(__isl_keep isl_map
*map
, void *user
)
3735 struct isl_union_map_involves_dims_data
*data
= user
;
3738 involves
= isl_map_involves_dims(map
,
3739 isl_dim_param
, data
->first
, data
->n
);
3741 return isl_bool_error
;
3745 /* Does "umap" involve any of the n parameters starting at first?
3746 * "type" is required to be set to isl_dim_param.
3748 * "umap" involves any of those parameters if any of its maps
3749 * involve the parameters. In other words, "umap" does not
3750 * involve any of the parameters if all its maps to not
3751 * involve the parameters.
3753 isl_bool
isl_union_map_involves_dims(__isl_keep isl_union_map
*umap
,
3754 enum isl_dim_type type
, unsigned first
, unsigned n
)
3756 struct isl_union_map_involves_dims_data data
= { first
, n
};
3759 if (type
!= isl_dim_param
)
3760 isl_die(isl_union_map_get_ctx(umap
), isl_error_invalid
,
3761 "can only reference parameters", return isl_bool_error
);
3763 excludes
= union_map_forall_user(umap
, &map_excludes
, &data
);
3766 return isl_bool_error
;
3771 /* Internal data structure for isl_union_map_reset_range_space.
3772 * "range" is the space from which to set the range space.
3773 * "res" collects the results.
3775 struct isl_union_map_reset_range_space_data
{
3780 /* Replace the range space of "map" by the range space of data->range and
3781 * add the result to data->res.
3783 static isl_stat
reset_range_space(__isl_take isl_map
*map
, void *user
)
3785 struct isl_union_map_reset_range_space_data
*data
= user
;
3788 space
= isl_map_get_space(map
);
3789 space
= isl_space_domain(space
);
3790 space
= isl_space_extend_domain_with_range(space
,
3791 isl_space_copy(data
->range
));
3792 map
= isl_map_reset_space(map
, space
);
3793 data
->res
= isl_union_map_add_map(data
->res
, map
);
3795 return data
->res
? isl_stat_ok
: isl_stat_error
;
3798 /* Replace the range space of all the maps in "umap" by
3799 * the range space of "space".
3801 * This assumes that all maps have the same output dimension.
3802 * This function should therefore not be made publicly available.
3804 * Since the spaces of the maps change, so do their hash value.
3805 * We therefore need to create a new isl_union_map.
3807 __isl_give isl_union_map
*isl_union_map_reset_range_space(
3808 __isl_take isl_union_map
*umap
, __isl_take isl_space
*space
)
3810 struct isl_union_map_reset_range_space_data data
= { space
};
3812 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3813 if (isl_union_map_foreach_map(umap
, &reset_range_space
, &data
) < 0)
3814 data
.res
= isl_union_map_free(data
.res
);
3816 isl_space_free(space
);
3817 isl_union_map_free(umap
);
3821 /* Internal data structure for isl_union_map_order_at_multi_union_pw_aff.
3822 * "mupa" is the function from which the isl_multi_pw_affs are extracted.
3823 * "order" is applied to the extracted isl_multi_pw_affs that correspond
3824 * to the domain and the range of each map.
3825 * "res" collects the results.
3827 struct isl_union_order_at_data
{
3828 isl_multi_union_pw_aff
*mupa
;
3829 __isl_give isl_map
*(*order
)(__isl_take isl_multi_pw_aff
*mpa1
,
3830 __isl_take isl_multi_pw_aff
*mpa2
);
3834 /* Intersect "map" with the result of applying data->order to
3835 * the functions in data->mupa that apply to the domain and the range
3836 * of "map" and add the result to data->res.
3838 static isl_stat
order_at(__isl_take isl_map
*map
, void *user
)
3840 struct isl_union_order_at_data
*data
= user
;
3842 isl_multi_pw_aff
*mpa1
, *mpa2
;
3845 space
= isl_space_domain(isl_map_get_space(map
));
3846 mpa1
= isl_multi_union_pw_aff_extract_multi_pw_aff(data
->mupa
, space
);
3847 space
= isl_space_range(isl_map_get_space(map
));
3848 mpa2
= isl_multi_union_pw_aff_extract_multi_pw_aff(data
->mupa
, space
);
3849 order
= data
->order(mpa1
, mpa2
);
3850 map
= isl_map_intersect(map
, order
);
3851 data
->res
= isl_union_map_add_map(data
->res
, map
);
3853 return data
->res
? isl_stat_ok
: isl_stat_error
;
3856 /* Intersect each map in "umap" with the result of calling "order"
3857 * on the functions is "mupa" that apply to the domain and the range
3860 static __isl_give isl_union_map
*isl_union_map_order_at_multi_union_pw_aff(
3861 __isl_take isl_union_map
*umap
, __isl_take isl_multi_union_pw_aff
*mupa
,
3862 __isl_give isl_map
*(*order
)(__isl_take isl_multi_pw_aff
*mpa1
,
3863 __isl_take isl_multi_pw_aff
*mpa2
))
3865 struct isl_union_order_at_data data
;
3867 umap
= isl_union_map_align_params(umap
,
3868 isl_multi_union_pw_aff_get_space(mupa
));
3869 mupa
= isl_multi_union_pw_aff_align_params(mupa
,
3870 isl_union_map_get_space(umap
));
3873 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3874 if (isl_union_map_foreach_map(umap
, &order_at
, &data
) < 0)
3875 data
.res
= isl_union_map_free(data
.res
);
3877 isl_multi_union_pw_aff_free(mupa
);
3878 isl_union_map_free(umap
);
3882 /* Return the subset of "umap" where the domain and the range
3883 * have equal "mupa" values.
3885 __isl_give isl_union_map
*isl_union_map_eq_at_multi_union_pw_aff(
3886 __isl_take isl_union_map
*umap
,
3887 __isl_take isl_multi_union_pw_aff
*mupa
)
3889 return isl_union_map_order_at_multi_union_pw_aff(umap
, mupa
,
3890 &isl_multi_pw_aff_eq_map
);
3893 /* Return the subset of "umap" where the domain has a lexicographically
3894 * smaller "mupa" value than the range.
3896 __isl_give isl_union_map
*isl_union_map_lex_lt_at_multi_union_pw_aff(
3897 __isl_take isl_union_map
*umap
,
3898 __isl_take isl_multi_union_pw_aff
*mupa
)
3900 return isl_union_map_order_at_multi_union_pw_aff(umap
, mupa
,
3901 &isl_multi_pw_aff_lex_lt_map
);
3904 /* Return the subset of "umap" where the domain has a lexicographically
3905 * greater "mupa" value than the range.
3907 __isl_give isl_union_map
*isl_union_map_lex_gt_at_multi_union_pw_aff(
3908 __isl_take isl_union_map
*umap
,
3909 __isl_take isl_multi_union_pw_aff
*mupa
)
3911 return isl_union_map_order_at_multi_union_pw_aff(umap
, mupa
,
3912 &isl_multi_pw_aff_lex_gt_map
);
3915 /* Return the union of the elements in the list "list".
3917 __isl_give isl_union_set
*isl_union_set_list_union(
3918 __isl_take isl_union_set_list
*list
)
3928 ctx
= isl_union_set_list_get_ctx(list
);
3929 space
= isl_space_params_alloc(ctx
, 0);
3930 res
= isl_union_set_empty(space
);
3932 n
= isl_union_set_list_n_union_set(list
);
3933 for (i
= 0; i
< n
; ++i
) {
3934 isl_union_set
*uset_i
;
3936 uset_i
= isl_union_set_list_get_union_set(list
, i
);
3937 res
= isl_union_set_union(res
, uset_i
);
3940 isl_union_set_list_free(list
);
3944 /* Update *hash with the hash value of "map".
3946 static isl_stat
add_hash(__isl_take isl_map
*map
, void *user
)
3948 uint32_t *hash
= user
;
3951 map_hash
= isl_map_get_hash(map
);
3952 isl_hash_hash(*hash
, map_hash
);
3958 /* Return a hash value that digests "umap".
3960 uint32_t isl_union_map_get_hash(__isl_keep isl_union_map
*umap
)
3967 hash
= isl_hash_init();
3968 if (isl_union_map_foreach_map(umap
, &add_hash
, &hash
) < 0)
3974 /* Return a hash value that digests "uset".
3976 uint32_t isl_union_set_get_hash(__isl_keep isl_union_set
*uset
)
3978 return isl_union_map_get_hash(uset
);