2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2013-2014 Ecole Normale Superieure
4 * Copyright 2014 INRIA Rocquencourt
5 * Copyright 2016-2017 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
};
234 isl_bool equal_params
;
239 equal_params
= isl_space_has_equal_params(umap
->dim
, model
);
240 if (equal_params
< 0)
243 isl_space_free(model
);
247 model
= isl_space_params(model
);
248 data
.exp
= isl_parameter_alignment_reordering(umap
->dim
, model
);
252 data
.res
= isl_union_map_alloc(isl_space_copy(data
.exp
->dim
),
254 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
255 &align_entry
, &data
) < 0)
258 isl_reordering_free(data
.exp
);
259 isl_union_map_free(umap
);
260 isl_space_free(model
);
263 isl_reordering_free(data
.exp
);
264 isl_union_map_free(umap
);
265 isl_union_map_free(data
.res
);
266 isl_space_free(model
);
270 __isl_give isl_union_set
*isl_union_set_align_params(
271 __isl_take isl_union_set
*uset
, __isl_take isl_space
*model
)
273 return isl_union_map_align_params(uset
, model
);
276 __isl_give isl_union_map
*isl_union_map_union(__isl_take isl_union_map
*umap1
,
277 __isl_take isl_union_map
*umap2
)
279 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
280 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
282 umap1
= isl_union_map_cow(umap1
);
284 if (!umap1
|| !umap2
)
287 if (isl_union_map_foreach_map(umap2
, &add_map
, &umap1
) < 0)
290 isl_union_map_free(umap2
);
294 isl_union_map_free(umap1
);
295 isl_union_map_free(umap2
);
299 __isl_give isl_union_set
*isl_union_set_union(__isl_take isl_union_set
*uset1
,
300 __isl_take isl_union_set
*uset2
)
302 return isl_union_map_union(uset1
, uset2
);
305 __isl_give isl_union_map
*isl_union_map_copy(__isl_keep isl_union_map
*umap
)
314 __isl_give isl_union_set
*isl_union_set_copy(__isl_keep isl_union_set
*uset
)
316 return isl_union_map_copy(uset
);
319 __isl_null isl_union_map
*isl_union_map_free(__isl_take isl_union_map
*umap
)
327 isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
328 &free_umap_entry
, NULL
);
329 isl_hash_table_clear(&umap
->table
);
330 isl_space_free(umap
->dim
);
335 __isl_null isl_union_set
*isl_union_set_free(__isl_take isl_union_set
*uset
)
337 return isl_union_map_free(uset
);
340 /* Do "umap" and "space" have the same parameters?
342 isl_bool
isl_union_map_space_has_equal_params(__isl_keep isl_union_map
*umap
,
343 __isl_keep isl_space
*space
)
345 isl_space
*umap_space
;
347 umap_space
= isl_union_map_peek_space(umap
);
348 return isl_space_has_equal_params(umap_space
, space
);
351 static int has_space(const void *entry
, const void *val
)
353 isl_map
*map
= (isl_map
*)entry
;
354 isl_space
*space
= (isl_space
*) val
;
356 return isl_space_is_equal(map
->dim
, space
);
359 __isl_give isl_union_map
*isl_union_map_add_map(__isl_take isl_union_map
*umap
,
360 __isl_take isl_map
*map
)
363 struct isl_hash_table_entry
*entry
;
369 if (isl_map_plain_is_empty(map
)) {
374 aligned
= isl_map_space_has_equal_params(map
, umap
->dim
);
378 umap
= isl_union_map_align_params(umap
, isl_map_get_space(map
));
379 map
= isl_map_align_params(map
, isl_union_map_get_space(umap
));
382 umap
= isl_union_map_cow(umap
);
387 hash
= isl_space_get_hash(map
->dim
);
388 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
389 &has_space
, map
->dim
, 1);
396 entry
->data
= isl_map_union(entry
->data
, isl_map_copy(map
));
405 isl_union_map_free(umap
);
409 __isl_give isl_union_set
*isl_union_set_add_set(__isl_take isl_union_set
*uset
,
410 __isl_take isl_set
*set
)
412 return isl_union_map_add_map(uset
, set_to_map(set
));
415 __isl_give isl_union_map
*isl_union_map_from_map(__isl_take isl_map
*map
)
423 dim
= isl_map_get_space(map
);
424 dim
= isl_space_params(dim
);
425 umap
= isl_union_map_empty(dim
);
426 umap
= isl_union_map_add_map(umap
, map
);
431 __isl_give isl_union_set
*isl_union_set_from_set(__isl_take isl_set
*set
)
433 return isl_union_map_from_map(set_to_map(set
));
436 __isl_give isl_union_map
*isl_union_map_from_basic_map(
437 __isl_take isl_basic_map
*bmap
)
439 return isl_union_map_from_map(isl_map_from_basic_map(bmap
));
442 __isl_give isl_union_set
*isl_union_set_from_basic_set(
443 __isl_take isl_basic_set
*bset
)
445 return isl_union_map_from_basic_map(bset
);
448 struct isl_union_map_foreach_data
450 isl_stat (*fn
)(__isl_take isl_map
*map
, void *user
);
454 static isl_stat
call_on_copy(void **entry
, void *user
)
456 isl_map
*map
= *entry
;
457 struct isl_union_map_foreach_data
*data
;
458 data
= (struct isl_union_map_foreach_data
*)user
;
460 return data
->fn(isl_map_copy(map
), data
->user
);
463 int isl_union_map_n_map(__isl_keep isl_union_map
*umap
)
465 return umap
? umap
->table
.n
: 0;
468 int isl_union_set_n_set(__isl_keep isl_union_set
*uset
)
470 return uset
? uset
->table
.n
: 0;
473 isl_stat
isl_union_map_foreach_map(__isl_keep isl_union_map
*umap
,
474 isl_stat (*fn
)(__isl_take isl_map
*map
, void *user
), void *user
)
476 struct isl_union_map_foreach_data data
= { fn
, user
};
479 return isl_stat_error
;
481 return isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
482 &call_on_copy
, &data
);
485 static isl_stat
copy_map(void **entry
, void *user
)
487 isl_map
*map
= *entry
;
488 isl_map
**map_p
= user
;
490 *map_p
= isl_map_copy(map
);
492 return isl_stat_error
;
495 __isl_give isl_map
*isl_map_from_union_map(__isl_take isl_union_map
*umap
)
502 ctx
= isl_union_map_get_ctx(umap
);
503 if (umap
->table
.n
!= 1)
504 isl_die(ctx
, isl_error_invalid
,
505 "union map needs to contain elements in exactly "
506 "one space", goto error
);
508 isl_hash_table_foreach(ctx
, &umap
->table
, ©_map
, &map
);
510 isl_union_map_free(umap
);
514 isl_union_map_free(umap
);
518 __isl_give isl_set
*isl_set_from_union_set(__isl_take isl_union_set
*uset
)
520 return isl_map_from_union_map(uset
);
523 /* Extract the map in "umap" that lives in the given space (ignoring
526 __isl_give isl_map
*isl_union_map_extract_map(__isl_keep isl_union_map
*umap
,
527 __isl_take isl_space
*space
)
530 struct isl_hash_table_entry
*entry
;
532 space
= isl_space_drop_dims(space
, isl_dim_param
,
533 0, isl_space_dim(space
, isl_dim_param
));
534 space
= isl_space_align_params(space
, isl_union_map_get_space(umap
));
538 hash
= isl_space_get_hash(space
);
539 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
540 &has_space
, space
, 0);
542 return isl_map_empty(space
);
543 isl_space_free(space
);
544 return isl_map_copy(entry
->data
);
546 isl_space_free(space
);
550 __isl_give isl_set
*isl_union_set_extract_set(__isl_keep isl_union_set
*uset
,
551 __isl_take isl_space
*dim
)
553 return set_from_map(isl_union_map_extract_map(uset
, dim
));
556 /* Check if umap contains a map in the given space.
558 isl_bool
isl_union_map_contains(__isl_keep isl_union_map
*umap
,
559 __isl_keep isl_space
*space
)
562 struct isl_hash_table_entry
*entry
;
565 return isl_bool_error
;
567 hash
= isl_space_get_hash(space
);
568 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
569 &has_space
, space
, 0);
573 isl_bool
isl_union_set_contains(__isl_keep isl_union_set
*uset
,
574 __isl_keep isl_space
*space
)
576 return isl_union_map_contains(uset
, space
);
579 isl_stat
isl_union_set_foreach_set(__isl_keep isl_union_set
*uset
,
580 isl_stat (*fn
)(__isl_take isl_set
*set
, void *user
), void *user
)
582 return isl_union_map_foreach_map(uset
,
583 (isl_stat(*)(__isl_take isl_map
*, void*))fn
, user
);
586 struct isl_union_set_foreach_point_data
{
587 isl_stat (*fn
)(__isl_take isl_point
*pnt
, void *user
);
591 static isl_stat
foreach_point(__isl_take isl_set
*set
, void *user
)
593 struct isl_union_set_foreach_point_data
*data
= user
;
596 r
= isl_set_foreach_point(set
, data
->fn
, data
->user
);
602 isl_stat
isl_union_set_foreach_point(__isl_keep isl_union_set
*uset
,
603 isl_stat (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
605 struct isl_union_set_foreach_point_data data
= { fn
, user
};
606 return isl_union_set_foreach_set(uset
, &foreach_point
, &data
);
609 struct isl_union_map_gen_bin_data
{
610 isl_union_map
*umap2
;
614 static isl_stat
subtract_entry(void **entry
, void *user
)
616 struct isl_union_map_gen_bin_data
*data
= user
;
618 struct isl_hash_table_entry
*entry2
;
620 isl_map
*map
= *entry
;
622 space
= isl_map_get_space(map
);
623 hash
= isl_space_get_hash(space
);
624 entry2
= isl_hash_table_find(isl_union_map_get_ctx(data
->umap2
),
625 &data
->umap2
->table
, hash
,
626 &has_space
, space
, 0);
627 isl_space_free(space
);
628 map
= isl_map_copy(map
);
631 map
= isl_map_subtract(map
, isl_map_copy(entry2
->data
));
633 empty
= isl_map_is_empty(map
);
636 return isl_stat_error
;
643 data
->res
= isl_union_map_add_map(data
->res
, map
);
648 static __isl_give isl_union_map
*gen_bin_op(__isl_take isl_union_map
*umap1
,
649 __isl_take isl_union_map
*umap2
, isl_stat (*fn
)(void **, void *))
651 struct isl_union_map_gen_bin_data data
= { NULL
, NULL
};
653 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
654 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
656 if (!umap1
|| !umap2
)
660 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
662 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
666 isl_union_map_free(umap1
);
667 isl_union_map_free(umap2
);
670 isl_union_map_free(umap1
);
671 isl_union_map_free(umap2
);
672 isl_union_map_free(data
.res
);
676 __isl_give isl_union_map
*isl_union_map_subtract(
677 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
679 return gen_bin_op(umap1
, umap2
, &subtract_entry
);
682 __isl_give isl_union_set
*isl_union_set_subtract(
683 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
685 return isl_union_map_subtract(uset1
, uset2
);
688 struct isl_union_map_gen_bin_set_data
{
693 static isl_stat
intersect_params_entry(void **entry
, void *user
)
695 struct isl_union_map_gen_bin_set_data
*data
= user
;
696 isl_map
*map
= *entry
;
699 map
= isl_map_copy(map
);
700 map
= isl_map_intersect_params(map
, isl_set_copy(data
->set
));
702 empty
= isl_map_is_empty(map
);
705 return isl_stat_error
;
708 data
->res
= isl_union_map_add_map(data
->res
, map
);
713 static __isl_give isl_union_map
*gen_bin_set_op(__isl_take isl_union_map
*umap
,
714 __isl_take isl_set
*set
, isl_stat (*fn
)(void **, void *))
716 struct isl_union_map_gen_bin_set_data data
= { NULL
, NULL
};
718 umap
= isl_union_map_align_params(umap
, isl_set_get_space(set
));
719 set
= isl_set_align_params(set
, isl_union_map_get_space(umap
));
725 data
.res
= isl_union_map_alloc(isl_space_copy(umap
->dim
),
727 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
731 isl_union_map_free(umap
);
735 isl_union_map_free(umap
);
737 isl_union_map_free(data
.res
);
741 /* Intersect "umap" with the parameter domain "set".
743 * If "set" does not have any constraints, then we can return immediately.
745 __isl_give isl_union_map
*isl_union_map_intersect_params(
746 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
750 is_universe
= isl_set_plain_is_universe(set
);
758 return gen_bin_set_op(umap
, set
, &intersect_params_entry
);
760 isl_union_map_free(umap
);
765 __isl_give isl_union_set
*isl_union_set_intersect_params(
766 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
768 return isl_union_map_intersect_params(uset
, set
);
771 static __isl_give isl_union_map
*union_map_intersect_params(
772 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
774 return isl_union_map_intersect_params(umap
,
775 isl_set_from_union_set(uset
));
778 static __isl_give isl_union_map
*union_map_gist_params(
779 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
781 return isl_union_map_gist_params(umap
, isl_set_from_union_set(uset
));
784 struct isl_union_map_match_bin_data
{
785 isl_union_map
*umap2
;
787 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*);
790 static isl_stat
match_bin_entry(void **entry
, void *user
)
792 struct isl_union_map_match_bin_data
*data
= user
;
794 struct isl_hash_table_entry
*entry2
;
795 isl_map
*map
= *entry
;
798 hash
= isl_space_get_hash(map
->dim
);
799 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
800 hash
, &has_space
, map
->dim
, 0);
804 map
= isl_map_copy(map
);
805 map
= data
->fn(map
, isl_map_copy(entry2
->data
));
807 empty
= isl_map_is_empty(map
);
810 return isl_stat_error
;
817 data
->res
= isl_union_map_add_map(data
->res
, map
);
822 static __isl_give isl_union_map
*match_bin_op(__isl_take isl_union_map
*umap1
,
823 __isl_take isl_union_map
*umap2
,
824 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*))
826 struct isl_union_map_match_bin_data data
= { NULL
, NULL
, fn
};
828 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
829 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
831 if (!umap1
|| !umap2
)
835 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
837 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
838 &match_bin_entry
, &data
) < 0)
841 isl_union_map_free(umap1
);
842 isl_union_map_free(umap2
);
845 isl_union_map_free(umap1
);
846 isl_union_map_free(umap2
);
847 isl_union_map_free(data
.res
);
851 __isl_give isl_union_map
*isl_union_map_intersect(
852 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
854 return match_bin_op(umap1
, umap2
, &isl_map_intersect
);
857 /* Compute the intersection of the two union_sets.
858 * As a special case, if exactly one of the two union_sets
859 * is a parameter domain, then intersect the parameter domain
860 * of the other one with this set.
862 __isl_give isl_union_set
*isl_union_set_intersect(
863 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
867 p1
= isl_union_set_is_params(uset1
);
868 p2
= isl_union_set_is_params(uset2
);
869 if (p1
< 0 || p2
< 0)
872 return union_map_intersect_params(uset1
, uset2
);
874 return union_map_intersect_params(uset2
, uset1
);
875 return isl_union_map_intersect(uset1
, uset2
);
877 isl_union_set_free(uset1
);
878 isl_union_set_free(uset2
);
882 static isl_stat
gist_params_entry(void **entry
, void *user
)
884 struct isl_union_map_gen_bin_set_data
*data
= user
;
885 isl_map
*map
= *entry
;
888 map
= isl_map_copy(map
);
889 map
= isl_map_gist_params(map
, isl_set_copy(data
->set
));
891 empty
= isl_map_is_empty(map
);
894 return isl_stat_error
;
897 data
->res
= isl_union_map_add_map(data
->res
, map
);
902 __isl_give isl_union_map
*isl_union_map_gist_params(
903 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
905 return gen_bin_set_op(umap
, set
, &gist_params_entry
);
908 __isl_give isl_union_set
*isl_union_set_gist_params(
909 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
911 return isl_union_map_gist_params(uset
, set
);
914 __isl_give isl_union_map
*isl_union_map_gist(__isl_take isl_union_map
*umap
,
915 __isl_take isl_union_map
*context
)
917 return match_bin_op(umap
, context
, &isl_map_gist
);
920 __isl_give isl_union_set
*isl_union_set_gist(__isl_take isl_union_set
*uset
,
921 __isl_take isl_union_set
*context
)
923 if (isl_union_set_is_params(context
))
924 return union_map_gist_params(uset
, context
);
925 return isl_union_map_gist(uset
, context
);
928 /* For each map in "umap", remove the constraints in the corresponding map
930 * Each map in "context" is assumed to consist of a single disjunct and
931 * to have explicit representations for all local variables.
933 __isl_give isl_union_map
*isl_union_map_plain_gist(
934 __isl_take isl_union_map
*umap
, __isl_take isl_union_map
*context
)
936 return match_bin_op(umap
, context
, &isl_map_plain_gist
);
939 /* For each set in "uset", remove the constraints in the corresponding set
941 * Each set in "context" is assumed to consist of a single disjunct and
942 * to have explicit representations for all local variables.
944 __isl_give isl_union_set
*isl_union_set_plain_gist(
945 __isl_take isl_union_set
*uset
, __isl_take isl_union_set
*context
)
947 return isl_union_map_plain_gist(uset
, context
);
950 static __isl_give isl_map
*lex_le_set(__isl_take isl_map
*set1
,
951 __isl_take isl_map
*set2
)
953 return isl_set_lex_le_set(set_from_map(set1
), set_from_map(set2
));
956 static __isl_give isl_map
*lex_lt_set(__isl_take isl_map
*set1
,
957 __isl_take isl_map
*set2
)
959 return isl_set_lex_lt_set(set_from_map(set1
), set_from_map(set2
));
962 __isl_give isl_union_map
*isl_union_set_lex_lt_union_set(
963 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
965 return match_bin_op(uset1
, uset2
, &lex_lt_set
);
968 __isl_give isl_union_map
*isl_union_set_lex_le_union_set(
969 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
971 return match_bin_op(uset1
, uset2
, &lex_le_set
);
974 __isl_give isl_union_map
*isl_union_set_lex_gt_union_set(
975 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
977 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2
, uset1
));
980 __isl_give isl_union_map
*isl_union_set_lex_ge_union_set(
981 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
983 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2
, uset1
));
986 __isl_give isl_union_map
*isl_union_map_lex_gt_union_map(
987 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
989 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2
, umap1
));
992 __isl_give isl_union_map
*isl_union_map_lex_ge_union_map(
993 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
995 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2
, umap1
));
998 static isl_stat
intersect_domain_entry(void **entry
, void *user
)
1000 struct isl_union_map_gen_bin_data
*data
= user
;
1002 struct isl_hash_table_entry
*entry2
;
1004 isl_map
*map
= *entry
;
1007 dim
= isl_map_get_space(map
);
1008 dim
= isl_space_domain(dim
);
1009 hash
= isl_space_get_hash(dim
);
1010 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1011 hash
, &has_space
, dim
, 0);
1012 isl_space_free(dim
);
1016 map
= isl_map_copy(map
);
1017 map
= isl_map_intersect_domain(map
, isl_set_copy(entry2
->data
));
1019 empty
= isl_map_is_empty(map
);
1022 return isl_stat_error
;
1029 data
->res
= isl_union_map_add_map(data
->res
, map
);
1034 /* Intersect the domain of "umap" with "uset".
1035 * If "uset" is a parameters domain, then intersect the parameter
1036 * domain of "umap" with this set.
1038 __isl_give isl_union_map
*isl_union_map_intersect_domain(
1039 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1041 if (isl_union_set_is_params(uset
))
1042 return union_map_intersect_params(umap
, uset
);
1043 return gen_bin_op(umap
, uset
, &intersect_domain_entry
);
1046 /* Remove the elements of data->umap2 from the domain of *entry
1047 * and add the result to data->res.
1049 static isl_stat
subtract_domain_entry(void **entry
, void *user
)
1051 struct isl_union_map_gen_bin_data
*data
= user
;
1053 struct isl_hash_table_entry
*entry2
;
1055 isl_map
*map
= *entry
;
1058 dim
= isl_map_get_space(map
);
1059 dim
= isl_space_domain(dim
);
1060 hash
= isl_space_get_hash(dim
);
1061 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1062 hash
, &has_space
, dim
, 0);
1063 isl_space_free(dim
);
1065 map
= isl_map_copy(map
);
1068 data
->res
= isl_union_map_add_map(data
->res
, map
);
1072 map
= isl_map_subtract_domain(map
, isl_set_copy(entry2
->data
));
1074 empty
= isl_map_is_empty(map
);
1077 return isl_stat_error
;
1084 data
->res
= isl_union_map_add_map(data
->res
, map
);
1089 /* Remove the elements of "uset" from the domain of "umap".
1091 __isl_give isl_union_map
*isl_union_map_subtract_domain(
1092 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
1094 return gen_bin_op(umap
, dom
, &subtract_domain_entry
);
1097 /* Remove the elements of data->umap2 from the range of *entry
1098 * and add the result to data->res.
1100 static isl_stat
subtract_range_entry(void **entry
, void *user
)
1102 struct isl_union_map_gen_bin_data
*data
= user
;
1104 struct isl_hash_table_entry
*entry2
;
1106 isl_map
*map
= *entry
;
1109 space
= isl_map_get_space(map
);
1110 space
= isl_space_range(space
);
1111 hash
= isl_space_get_hash(space
);
1112 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1113 hash
, &has_space
, space
, 0);
1114 isl_space_free(space
);
1116 map
= isl_map_copy(map
);
1119 data
->res
= isl_union_map_add_map(data
->res
, map
);
1123 map
= isl_map_subtract_range(map
, isl_set_copy(entry2
->data
));
1125 empty
= isl_map_is_empty(map
);
1128 return isl_stat_error
;
1135 data
->res
= isl_union_map_add_map(data
->res
, map
);
1140 /* Remove the elements of "uset" from the range of "umap".
1142 __isl_give isl_union_map
*isl_union_map_subtract_range(
1143 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
1145 return gen_bin_op(umap
, dom
, &subtract_range_entry
);
1148 static isl_stat
gist_domain_entry(void **entry
, void *user
)
1150 struct isl_union_map_gen_bin_data
*data
= user
;
1152 struct isl_hash_table_entry
*entry2
;
1154 isl_map
*map
= *entry
;
1157 dim
= isl_map_get_space(map
);
1158 dim
= isl_space_domain(dim
);
1159 hash
= isl_space_get_hash(dim
);
1160 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1161 hash
, &has_space
, dim
, 0);
1162 isl_space_free(dim
);
1166 map
= isl_map_copy(map
);
1167 map
= isl_map_gist_domain(map
, isl_set_copy(entry2
->data
));
1169 empty
= isl_map_is_empty(map
);
1172 return isl_stat_error
;
1175 data
->res
= isl_union_map_add_map(data
->res
, map
);
1180 /* Compute the gist of "umap" with respect to the domain "uset".
1181 * If "uset" is a parameters domain, then compute the gist
1182 * with respect to this parameter domain.
1184 __isl_give isl_union_map
*isl_union_map_gist_domain(
1185 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1187 if (isl_union_set_is_params(uset
))
1188 return union_map_gist_params(umap
, uset
);
1189 return gen_bin_op(umap
, uset
, &gist_domain_entry
);
1192 static isl_stat
gist_range_entry(void **entry
, void *user
)
1194 struct isl_union_map_gen_bin_data
*data
= user
;
1196 struct isl_hash_table_entry
*entry2
;
1198 isl_map
*map
= *entry
;
1201 space
= isl_map_get_space(map
);
1202 space
= isl_space_range(space
);
1203 hash
= isl_space_get_hash(space
);
1204 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1205 hash
, &has_space
, space
, 0);
1206 isl_space_free(space
);
1210 map
= isl_map_copy(map
);
1211 map
= isl_map_gist_range(map
, isl_set_copy(entry2
->data
));
1213 empty
= isl_map_is_empty(map
);
1216 return isl_stat_error
;
1219 data
->res
= isl_union_map_add_map(data
->res
, map
);
1224 /* Compute the gist of "umap" with respect to the range "uset".
1226 __isl_give isl_union_map
*isl_union_map_gist_range(
1227 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1229 return gen_bin_op(umap
, uset
, &gist_range_entry
);
1232 static isl_stat
intersect_range_entry(void **entry
, void *user
)
1234 struct isl_union_map_gen_bin_data
*data
= user
;
1236 struct isl_hash_table_entry
*entry2
;
1238 isl_map
*map
= *entry
;
1241 dim
= isl_map_get_space(map
);
1242 dim
= isl_space_range(dim
);
1243 hash
= isl_space_get_hash(dim
);
1244 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1245 hash
, &has_space
, dim
, 0);
1246 isl_space_free(dim
);
1250 map
= isl_map_copy(map
);
1251 map
= isl_map_intersect_range(map
, isl_set_copy(entry2
->data
));
1253 empty
= isl_map_is_empty(map
);
1256 return isl_stat_error
;
1263 data
->res
= isl_union_map_add_map(data
->res
, map
);
1268 __isl_give isl_union_map
*isl_union_map_intersect_range(
1269 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1271 return gen_bin_op(umap
, uset
, &intersect_range_entry
);
1274 struct isl_union_map_bin_data
{
1275 isl_union_map
*umap2
;
1278 isl_stat (*fn
)(void **entry
, void *user
);
1281 static isl_stat
apply_range_entry(void **entry
, void *user
)
1283 struct isl_union_map_bin_data
*data
= user
;
1284 isl_map
*map2
= *entry
;
1287 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1288 map2
->dim
, isl_dim_in
))
1291 map2
= isl_map_apply_range(isl_map_copy(data
->map
), isl_map_copy(map2
));
1293 empty
= isl_map_is_empty(map2
);
1296 return isl_stat_error
;
1303 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1308 static isl_stat
bin_entry(void **entry
, void *user
)
1310 struct isl_union_map_bin_data
*data
= user
;
1311 isl_map
*map
= *entry
;
1314 if (isl_hash_table_foreach(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1315 data
->fn
, data
) < 0)
1316 return isl_stat_error
;
1321 static __isl_give isl_union_map
*bin_op(__isl_take isl_union_map
*umap1
,
1322 __isl_take isl_union_map
*umap2
,
1323 isl_stat (*fn
)(void **entry
, void *user
))
1325 struct isl_union_map_bin_data data
= { NULL
, NULL
, NULL
, fn
};
1327 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1328 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1330 if (!umap1
|| !umap2
)
1334 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
1336 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1337 &bin_entry
, &data
) < 0)
1340 isl_union_map_free(umap1
);
1341 isl_union_map_free(umap2
);
1344 isl_union_map_free(umap1
);
1345 isl_union_map_free(umap2
);
1346 isl_union_map_free(data
.res
);
1350 __isl_give isl_union_map
*isl_union_map_apply_range(
1351 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1353 return bin_op(umap1
, umap2
, &apply_range_entry
);
1356 __isl_give isl_union_map
*isl_union_map_apply_domain(
1357 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1359 umap1
= isl_union_map_reverse(umap1
);
1360 umap1
= isl_union_map_apply_range(umap1
, umap2
);
1361 return isl_union_map_reverse(umap1
);
1364 __isl_give isl_union_set
*isl_union_set_apply(
1365 __isl_take isl_union_set
*uset
, __isl_take isl_union_map
*umap
)
1367 return isl_union_map_apply_range(uset
, umap
);
1370 static isl_stat
map_lex_lt_entry(void **entry
, void *user
)
1372 struct isl_union_map_bin_data
*data
= user
;
1373 isl_map
*map2
= *entry
;
1375 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1376 map2
->dim
, isl_dim_out
))
1379 map2
= isl_map_lex_lt_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1381 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1386 __isl_give isl_union_map
*isl_union_map_lex_lt_union_map(
1387 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1389 return bin_op(umap1
, umap2
, &map_lex_lt_entry
);
1392 static isl_stat
map_lex_le_entry(void **entry
, void *user
)
1394 struct isl_union_map_bin_data
*data
= user
;
1395 isl_map
*map2
= *entry
;
1397 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1398 map2
->dim
, isl_dim_out
))
1401 map2
= isl_map_lex_le_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1403 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1408 __isl_give isl_union_map
*isl_union_map_lex_le_union_map(
1409 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1411 return bin_op(umap1
, umap2
, &map_lex_le_entry
);
1414 static isl_stat
product_entry(void **entry
, void *user
)
1416 struct isl_union_map_bin_data
*data
= user
;
1417 isl_map
*map2
= *entry
;
1419 map2
= isl_map_product(isl_map_copy(data
->map
), isl_map_copy(map2
));
1421 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1426 __isl_give isl_union_map
*isl_union_map_product(__isl_take isl_union_map
*umap1
,
1427 __isl_take isl_union_map
*umap2
)
1429 return bin_op(umap1
, umap2
, &product_entry
);
1432 static isl_stat
set_product_entry(void **entry
, void *user
)
1434 struct isl_union_map_bin_data
*data
= user
;
1435 isl_set
*set2
= *entry
;
1437 set2
= isl_set_product(isl_set_copy(data
->map
), isl_set_copy(set2
));
1439 data
->res
= isl_union_set_add_set(data
->res
, set2
);
1444 __isl_give isl_union_set
*isl_union_set_product(__isl_take isl_union_set
*uset1
,
1445 __isl_take isl_union_set
*uset2
)
1447 return bin_op(uset1
, uset2
, &set_product_entry
);
1450 static isl_stat
domain_product_entry(void **entry
, void *user
)
1452 struct isl_union_map_bin_data
*data
= user
;
1453 isl_map
*map2
= *entry
;
1455 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1456 map2
->dim
, isl_dim_out
))
1459 map2
= isl_map_domain_product(isl_map_copy(data
->map
),
1460 isl_map_copy(map2
));
1462 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1467 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1469 __isl_give isl_union_map
*isl_union_map_domain_product(
1470 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1472 return bin_op(umap1
, umap2
, &domain_product_entry
);
1475 static isl_stat
range_product_entry(void **entry
, void *user
)
1477 struct isl_union_map_bin_data
*data
= user
;
1478 isl_map
*map2
= *entry
;
1480 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_in
,
1481 map2
->dim
, isl_dim_in
))
1484 map2
= isl_map_range_product(isl_map_copy(data
->map
),
1485 isl_map_copy(map2
));
1487 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1492 __isl_give isl_union_map
*isl_union_map_range_product(
1493 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1495 return bin_op(umap1
, umap2
, &range_product_entry
);
1498 /* If data->map A -> B and "map2" C -> D have the same range space,
1499 * then add (A, C) -> (B * D) to data->res.
1501 static isl_stat
flat_domain_product_entry(void **entry
, void *user
)
1503 struct isl_union_map_bin_data
*data
= user
;
1504 isl_map
*map2
= *entry
;
1506 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_out
,
1507 map2
->dim
, isl_dim_out
))
1510 map2
= isl_map_flat_domain_product(isl_map_copy(data
->map
),
1511 isl_map_copy(map2
));
1513 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1518 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B * D).
1520 __isl_give isl_union_map
*isl_union_map_flat_domain_product(
1521 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1523 return bin_op(umap1
, umap2
, &flat_domain_product_entry
);
1526 static isl_stat
flat_range_product_entry(void **entry
, void *user
)
1528 struct isl_union_map_bin_data
*data
= user
;
1529 isl_map
*map2
= *entry
;
1531 if (!isl_space_tuple_is_equal(data
->map
->dim
, isl_dim_in
,
1532 map2
->dim
, isl_dim_in
))
1535 map2
= isl_map_flat_range_product(isl_map_copy(data
->map
),
1536 isl_map_copy(map2
));
1538 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1543 __isl_give isl_union_map
*isl_union_map_flat_range_product(
1544 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1546 return bin_op(umap1
, umap2
, &flat_range_product_entry
);
1549 /* Data structure that specifies how un_op should modify
1550 * the maps in the union map.
1552 * If "inplace" is set, then the maps in the input union map
1553 * are modified in place. This means that "fn_map" should not
1554 * change the meaning of the map or that the union map only
1555 * has a single reference.
1556 * If "total" is set, then all maps need to be modified and
1557 * the results need to live in the same space.
1558 * Otherwise, a new union map is constructed to store the results.
1559 * If "filter" is not NULL, then only the input maps that satisfy "filter"
1560 * are taken into account. No filter can be set if "inplace" or
1562 * "fn_map" specifies how the maps (selected by "filter")
1563 * should be transformed.
1565 struct isl_un_op_control
{
1568 isl_bool (*filter
)(__isl_keep isl_map
*map
);
1569 __isl_give isl_map
*(*fn_map
)(__isl_take isl_map
*map
);
1572 /* Internal data structure for "un_op".
1573 * "control" specifies how the maps in the union map should be modified.
1574 * "res" collects the results.
1576 struct isl_union_map_un_data
{
1577 struct isl_un_op_control
*control
;
1581 /* isl_hash_table_foreach callback for un_op.
1582 * Handle the map that "entry" points to.
1584 * If control->filter is set, then check if this map satisfies the filter.
1585 * If so (or if control->filter is not set), modify the map
1586 * by calling control->fn_map and either add the result to data->res or
1587 * replace the original entry by the result (if control->inplace is set).
1589 static isl_stat
un_entry(void **entry
, void *user
)
1591 struct isl_union_map_un_data
*data
= user
;
1592 isl_map
*map
= *entry
;
1594 if (data
->control
->filter
) {
1597 ok
= data
->control
->filter(map
);
1599 return isl_stat_error
;
1604 map
= data
->control
->fn_map(isl_map_copy(map
));
1606 return isl_stat_error
;
1607 if (data
->control
->inplace
) {
1608 isl_map_free(*entry
);
1611 data
->res
= isl_union_map_add_map(data
->res
, map
);
1613 return isl_stat_error
;
1619 /* Modify the maps in "umap" based on "control".
1620 * If control->inplace is set, then modify the maps in "umap" in-place.
1621 * Otherwise, create a new union map to hold the results.
1622 * If control->total is set, then perform an inplace computation
1623 * if "umap" is only referenced once. Otherwise, create a new union map
1624 * to store the results.
1626 static __isl_give isl_union_map
*un_op(__isl_take isl_union_map
*umap
,
1627 struct isl_un_op_control
*control
)
1629 struct isl_union_map_un_data data
= { control
};
1633 if ((control
->inplace
|| control
->total
) && control
->filter
)
1634 isl_die(isl_union_map_get_ctx(umap
), isl_error_invalid
,
1635 "inplace/total modification cannot be filtered",
1636 return isl_union_map_free(umap
));
1638 if (control
->total
&& umap
->ref
== 1)
1639 control
->inplace
= 1;
1640 if (control
->inplace
) {
1645 space
= isl_union_map_get_space(umap
);
1646 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
1648 if (isl_hash_table_foreach(isl_union_map_get_ctx(umap
),
1649 &umap
->table
, &un_entry
, &data
) < 0)
1650 data
.res
= isl_union_map_free(data
.res
);
1652 if (control
->inplace
)
1654 isl_union_map_free(umap
);
1658 __isl_give isl_union_map
*isl_union_map_from_range(
1659 __isl_take isl_union_set
*uset
)
1661 struct isl_un_op_control control
= {
1662 .fn_map
= &isl_map_from_range
,
1664 return un_op(uset
, &control
);
1667 __isl_give isl_union_map
*isl_union_map_from_domain(
1668 __isl_take isl_union_set
*uset
)
1670 return isl_union_map_reverse(isl_union_map_from_range(uset
));
1673 __isl_give isl_union_map
*isl_union_map_from_domain_and_range(
1674 __isl_take isl_union_set
*domain
, __isl_take isl_union_set
*range
)
1676 return isl_union_map_apply_range(isl_union_map_from_domain(domain
),
1677 isl_union_map_from_range(range
));
1680 /* Modify the maps in "umap" by applying "fn" on them.
1681 * "fn" should apply to all maps in "umap" and should not modify the space.
1683 static __isl_give isl_union_map
*total(__isl_take isl_union_map
*umap
,
1684 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*))
1686 struct isl_un_op_control control
= {
1691 return un_op(umap
, &control
);
1694 /* Compute the affine hull of "map" and return the result as an isl_map.
1696 static __isl_give isl_map
*isl_map_affine_hull_map(__isl_take isl_map
*map
)
1698 return isl_map_from_basic_map(isl_map_affine_hull(map
));
1701 __isl_give isl_union_map
*isl_union_map_affine_hull(
1702 __isl_take isl_union_map
*umap
)
1704 return total(umap
, &isl_map_affine_hull_map
);
1707 __isl_give isl_union_set
*isl_union_set_affine_hull(
1708 __isl_take isl_union_set
*uset
)
1710 return isl_union_map_affine_hull(uset
);
1713 /* Wrapper around isl_set_combined_lineality_space
1714 * that returns the combined lineality space in the form of an isl_set
1715 * instead of an isl_basic_set.
1717 static __isl_give isl_set
*combined_lineality_space(__isl_take isl_set
*set
)
1719 return isl_set_from_basic_set(isl_set_combined_lineality_space(set
));
1722 /* For each set in "uset", compute the (linear) hull
1723 * of the lineality spaces of its basic sets and
1724 * collect and return the results.
1726 __isl_give isl_union_set
*isl_union_set_combined_lineality_space(
1727 __isl_take isl_union_set
*uset
)
1729 struct isl_un_op_control control
= {
1730 .fn_map
= &combined_lineality_space
,
1732 return un_op(uset
, &control
);
1735 /* Compute the polyhedral hull of "map" and return the result as an isl_map.
1737 static __isl_give isl_map
*isl_map_polyhedral_hull_map(__isl_take isl_map
*map
)
1739 return isl_map_from_basic_map(isl_map_polyhedral_hull(map
));
1742 __isl_give isl_union_map
*isl_union_map_polyhedral_hull(
1743 __isl_take isl_union_map
*umap
)
1745 return total(umap
, &isl_map_polyhedral_hull_map
);
1748 __isl_give isl_union_set
*isl_union_set_polyhedral_hull(
1749 __isl_take isl_union_set
*uset
)
1751 return isl_union_map_polyhedral_hull(uset
);
1754 /* Compute a superset of the convex hull of "map" that is described
1755 * by only translates of the constraints in the constituents of "map" and
1756 * return the result as an isl_map.
1758 static __isl_give isl_map
*isl_map_simple_hull_map(__isl_take isl_map
*map
)
1760 return isl_map_from_basic_map(isl_map_simple_hull(map
));
1763 __isl_give isl_union_map
*isl_union_map_simple_hull(
1764 __isl_take isl_union_map
*umap
)
1766 return total(umap
, &isl_map_simple_hull_map
);
1769 __isl_give isl_union_set
*isl_union_set_simple_hull(
1770 __isl_take isl_union_set
*uset
)
1772 return isl_union_map_simple_hull(uset
);
1775 static __isl_give isl_union_map
*inplace(__isl_take isl_union_map
*umap
,
1776 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*))
1778 struct isl_un_op_control control
= {
1783 return un_op(umap
, &control
);
1786 /* Remove redundant constraints in each of the basic maps of "umap".
1787 * Since removing redundant constraints does not change the meaning
1788 * or the space, the operation can be performed in-place.
1790 __isl_give isl_union_map
*isl_union_map_remove_redundancies(
1791 __isl_take isl_union_map
*umap
)
1793 return inplace(umap
, &isl_map_remove_redundancies
);
1796 /* Remove redundant constraints in each of the basic sets of "uset".
1798 __isl_give isl_union_set
*isl_union_set_remove_redundancies(
1799 __isl_take isl_union_set
*uset
)
1801 return isl_union_map_remove_redundancies(uset
);
1804 __isl_give isl_union_map
*isl_union_map_coalesce(
1805 __isl_take isl_union_map
*umap
)
1807 return inplace(umap
, &isl_map_coalesce
);
1810 __isl_give isl_union_set
*isl_union_set_coalesce(
1811 __isl_take isl_union_set
*uset
)
1813 return isl_union_map_coalesce(uset
);
1816 __isl_give isl_union_map
*isl_union_map_detect_equalities(
1817 __isl_take isl_union_map
*umap
)
1819 return inplace(umap
, &isl_map_detect_equalities
);
1822 __isl_give isl_union_set
*isl_union_set_detect_equalities(
1823 __isl_take isl_union_set
*uset
)
1825 return isl_union_map_detect_equalities(uset
);
1828 __isl_give isl_union_map
*isl_union_map_compute_divs(
1829 __isl_take isl_union_map
*umap
)
1831 return inplace(umap
, &isl_map_compute_divs
);
1834 __isl_give isl_union_set
*isl_union_set_compute_divs(
1835 __isl_take isl_union_set
*uset
)
1837 return isl_union_map_compute_divs(uset
);
1840 __isl_give isl_union_map
*isl_union_map_lexmin(
1841 __isl_take isl_union_map
*umap
)
1843 return total(umap
, &isl_map_lexmin
);
1846 __isl_give isl_union_set
*isl_union_set_lexmin(
1847 __isl_take isl_union_set
*uset
)
1849 return isl_union_map_lexmin(uset
);
1852 __isl_give isl_union_map
*isl_union_map_lexmax(
1853 __isl_take isl_union_map
*umap
)
1855 return total(umap
, &isl_map_lexmax
);
1858 __isl_give isl_union_set
*isl_union_set_lexmax(
1859 __isl_take isl_union_set
*uset
)
1861 return isl_union_map_lexmax(uset
);
1864 /* Return the universe in the space of "map".
1866 static __isl_give isl_map
*universe(__isl_take isl_map
*map
)
1870 space
= isl_map_get_space(map
);
1872 return isl_map_universe(space
);
1875 __isl_give isl_union_map
*isl_union_map_universe(__isl_take isl_union_map
*umap
)
1877 struct isl_un_op_control control
= {
1878 .fn_map
= &universe
,
1880 return un_op(umap
, &control
);
1883 __isl_give isl_union_set
*isl_union_set_universe(__isl_take isl_union_set
*uset
)
1885 return isl_union_map_universe(uset
);
1888 __isl_give isl_union_map
*isl_union_map_reverse(__isl_take isl_union_map
*umap
)
1890 struct isl_un_op_control control
= {
1891 .fn_map
= &isl_map_reverse
,
1893 return un_op(umap
, &control
);
1896 /* Compute the parameter domain of the given union map.
1898 __isl_give isl_set
*isl_union_map_params(__isl_take isl_union_map
*umap
)
1900 struct isl_un_op_control control
= {
1901 .fn_map
= &isl_map_params
,
1905 empty
= isl_union_map_is_empty(umap
);
1910 space
= isl_union_map_get_space(umap
);
1911 isl_union_map_free(umap
);
1912 return isl_set_empty(space
);
1914 return isl_set_from_union_set(un_op(umap
, &control
));
1916 isl_union_map_free(umap
);
1920 /* Compute the parameter domain of the given union set.
1922 __isl_give isl_set
*isl_union_set_params(__isl_take isl_union_set
*uset
)
1924 return isl_union_map_params(uset
);
1927 __isl_give isl_union_set
*isl_union_map_domain(__isl_take isl_union_map
*umap
)
1929 struct isl_un_op_control control
= {
1930 .fn_map
= &isl_map_domain
,
1932 return un_op(umap
, &control
);
1935 __isl_give isl_union_set
*isl_union_map_range(__isl_take isl_union_map
*umap
)
1937 struct isl_un_op_control control
= {
1938 .fn_map
= &isl_map_range
,
1940 return un_op(umap
, &control
);
1943 __isl_give isl_union_map
*isl_union_map_domain_map(
1944 __isl_take isl_union_map
*umap
)
1946 struct isl_un_op_control control
= {
1947 .fn_map
= &isl_map_domain_map
,
1949 return un_op(umap
, &control
);
1952 /* Construct an isl_pw_multi_aff that maps "map" to its domain and
1953 * add the result to "res".
1955 static isl_stat
domain_map_upma(__isl_take isl_map
*map
, void *user
)
1957 isl_union_pw_multi_aff
**res
= user
;
1959 isl_pw_multi_aff
*pma
;
1961 ma
= isl_multi_aff_domain_map(isl_map_get_space(map
));
1962 pma
= isl_pw_multi_aff_alloc(isl_map_wrap(map
), ma
);
1963 *res
= isl_union_pw_multi_aff_add_pw_multi_aff(*res
, pma
);
1965 return *res
? isl_stat_ok
: isl_stat_error
;
1969 /* Return an isl_union_pw_multi_aff that maps a wrapped copy of "umap"
1972 __isl_give isl_union_pw_multi_aff
*isl_union_map_domain_map_union_pw_multi_aff(
1973 __isl_take isl_union_map
*umap
)
1975 isl_union_pw_multi_aff
*res
;
1977 res
= isl_union_pw_multi_aff_empty(isl_union_map_get_space(umap
));
1978 if (isl_union_map_foreach_map(umap
, &domain_map_upma
, &res
) < 0)
1979 res
= isl_union_pw_multi_aff_free(res
);
1981 isl_union_map_free(umap
);
1985 __isl_give isl_union_map
*isl_union_map_range_map(
1986 __isl_take isl_union_map
*umap
)
1988 struct isl_un_op_control control
= {
1989 .fn_map
= &isl_map_range_map
,
1991 return un_op(umap
, &control
);
1994 /* Given a collection of wrapped maps of the form A[B -> C],
1995 * return the collection of maps A[B -> C] -> B.
1997 __isl_give isl_union_map
*isl_union_set_wrapped_domain_map(
1998 __isl_take isl_union_set
*uset
)
2000 struct isl_un_op_control control
= {
2001 .filter
= &isl_set_is_wrapping
,
2002 .fn_map
= &isl_set_wrapped_domain_map
,
2004 return un_op(uset
, &control
);
2007 /* Does "map" relate elements from the same space?
2009 static isl_bool
equal_tuples(__isl_keep isl_map
*map
)
2011 return isl_space_tuple_is_equal(map
->dim
, isl_dim_in
,
2012 map
->dim
, isl_dim_out
);
2015 __isl_give isl_union_set
*isl_union_map_deltas(__isl_take isl_union_map
*umap
)
2017 struct isl_un_op_control control
= {
2018 .filter
= &equal_tuples
,
2019 .fn_map
= &isl_map_deltas
,
2021 return un_op(umap
, &control
);
2024 __isl_give isl_union_map
*isl_union_map_deltas_map(
2025 __isl_take isl_union_map
*umap
)
2027 struct isl_un_op_control control
= {
2028 .filter
= &equal_tuples
,
2029 .fn_map
= &isl_map_deltas_map
,
2031 return un_op(umap
, &control
);
2034 __isl_give isl_union_map
*isl_union_set_identity(__isl_take isl_union_set
*uset
)
2036 struct isl_un_op_control control
= {
2037 .fn_map
= &isl_set_identity
,
2039 return un_op(uset
, &control
);
2042 /* Construct an identity isl_pw_multi_aff on "set" and add it to *res.
2044 static isl_stat
identity_upma(__isl_take isl_set
*set
, void *user
)
2046 isl_union_pw_multi_aff
**res
= user
;
2048 isl_pw_multi_aff
*pma
;
2050 space
= isl_space_map_from_set(isl_set_get_space(set
));
2051 pma
= isl_pw_multi_aff_identity(space
);
2052 pma
= isl_pw_multi_aff_intersect_domain(pma
, set
);
2053 *res
= isl_union_pw_multi_aff_add_pw_multi_aff(*res
, pma
);
2055 return *res
? isl_stat_ok
: isl_stat_error
;
2058 /* Return an identity function on "uset" in the form
2059 * of an isl_union_pw_multi_aff.
2061 __isl_give isl_union_pw_multi_aff
*isl_union_set_identity_union_pw_multi_aff(
2062 __isl_take isl_union_set
*uset
)
2064 isl_union_pw_multi_aff
*res
;
2066 res
= isl_union_pw_multi_aff_empty(isl_union_set_get_space(uset
));
2067 if (isl_union_set_foreach_set(uset
, &identity_upma
, &res
) < 0)
2068 res
= isl_union_pw_multi_aff_free(res
);
2070 isl_union_set_free(uset
);
2074 /* For each map in "umap" of the form [A -> B] -> C,
2075 * construct the map A -> C and collect the results.
2077 __isl_give isl_union_map
*isl_union_map_domain_factor_domain(
2078 __isl_take isl_union_map
*umap
)
2080 struct isl_un_op_control control
= {
2081 .filter
= &isl_map_domain_is_wrapping
,
2082 .fn_map
= &isl_map_domain_factor_domain
,
2084 return un_op(umap
, &control
);
2087 /* For each map in "umap" of the form [A -> B] -> C,
2088 * construct the map B -> C and collect the results.
2090 __isl_give isl_union_map
*isl_union_map_domain_factor_range(
2091 __isl_take isl_union_map
*umap
)
2093 struct isl_un_op_control control
= {
2094 .filter
= &isl_map_domain_is_wrapping
,
2095 .fn_map
= &isl_map_domain_factor_range
,
2097 return un_op(umap
, &control
);
2100 /* For each map in "umap" of the form A -> [B -> C],
2101 * construct the map A -> B and collect the results.
2103 __isl_give isl_union_map
*isl_union_map_range_factor_domain(
2104 __isl_take isl_union_map
*umap
)
2106 struct isl_un_op_control control
= {
2107 .filter
= &isl_map_range_is_wrapping
,
2108 .fn_map
= &isl_map_range_factor_domain
,
2110 return un_op(umap
, &control
);
2113 /* For each map in "umap" of the form A -> [B -> C],
2114 * construct the map A -> C and collect the results.
2116 __isl_give isl_union_map
*isl_union_map_range_factor_range(
2117 __isl_take isl_union_map
*umap
)
2119 struct isl_un_op_control control
= {
2120 .filter
= &isl_map_range_is_wrapping
,
2121 .fn_map
= &isl_map_range_factor_range
,
2123 return un_op(umap
, &control
);
2126 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2127 * construct the map A -> C and collect the results.
2129 __isl_give isl_union_map
*isl_union_map_factor_domain(
2130 __isl_take isl_union_map
*umap
)
2132 struct isl_un_op_control control
= {
2133 .filter
= &isl_map_is_product
,
2134 .fn_map
= &isl_map_factor_domain
,
2136 return un_op(umap
, &control
);
2139 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2140 * construct the map B -> D and collect the results.
2142 __isl_give isl_union_map
*isl_union_map_factor_range(
2143 __isl_take isl_union_map
*umap
)
2145 struct isl_un_op_control control
= {
2146 .filter
= &isl_map_is_product
,
2147 .fn_map
= &isl_map_factor_range
,
2149 return un_op(umap
, &control
);
2152 __isl_give isl_union_map
*isl_union_set_unwrap(__isl_take isl_union_set
*uset
)
2154 struct isl_un_op_control control
= {
2155 .filter
= &isl_set_is_wrapping
,
2156 .fn_map
= &isl_set_unwrap
,
2158 return un_op(uset
, &control
);
2161 __isl_give isl_union_set
*isl_union_map_wrap(__isl_take isl_union_map
*umap
)
2163 struct isl_un_op_control control
= {
2164 .fn_map
= &isl_map_wrap
,
2166 return un_op(umap
, &control
);
2169 struct isl_union_map_is_subset_data
{
2170 isl_union_map
*umap2
;
2174 static isl_stat
is_subset_entry(void **entry
, void *user
)
2176 struct isl_union_map_is_subset_data
*data
= user
;
2178 struct isl_hash_table_entry
*entry2
;
2179 isl_map
*map
= *entry
;
2181 hash
= isl_space_get_hash(map
->dim
);
2182 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
2183 hash
, &has_space
, map
->dim
, 0);
2185 int empty
= isl_map_is_empty(map
);
2187 return isl_stat_error
;
2190 data
->is_subset
= 0;
2191 return isl_stat_error
;
2194 data
->is_subset
= isl_map_is_subset(map
, entry2
->data
);
2195 if (data
->is_subset
< 0 || !data
->is_subset
)
2196 return isl_stat_error
;
2201 isl_bool
isl_union_map_is_subset(__isl_keep isl_union_map
*umap1
,
2202 __isl_keep isl_union_map
*umap2
)
2204 struct isl_union_map_is_subset_data data
= { NULL
, isl_bool_true
};
2206 umap1
= isl_union_map_copy(umap1
);
2207 umap2
= isl_union_map_copy(umap2
);
2208 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
2209 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
2211 if (!umap1
|| !umap2
)
2215 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
2216 &is_subset_entry
, &data
) < 0 &&
2220 isl_union_map_free(umap1
);
2221 isl_union_map_free(umap2
);
2223 return data
.is_subset
;
2225 isl_union_map_free(umap1
);
2226 isl_union_map_free(umap2
);
2227 return isl_bool_error
;
2230 isl_bool
isl_union_set_is_subset(__isl_keep isl_union_set
*uset1
,
2231 __isl_keep isl_union_set
*uset2
)
2233 return isl_union_map_is_subset(uset1
, uset2
);
2236 isl_bool
isl_union_map_is_equal(__isl_keep isl_union_map
*umap1
,
2237 __isl_keep isl_union_map
*umap2
)
2241 if (!umap1
|| !umap2
)
2242 return isl_bool_error
;
2243 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
2244 if (is_subset
!= isl_bool_true
)
2246 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
2250 isl_bool
isl_union_set_is_equal(__isl_keep isl_union_set
*uset1
,
2251 __isl_keep isl_union_set
*uset2
)
2253 return isl_union_map_is_equal(uset1
, uset2
);
2256 isl_bool
isl_union_map_is_strict_subset(__isl_keep isl_union_map
*umap1
,
2257 __isl_keep isl_union_map
*umap2
)
2261 if (!umap1
|| !umap2
)
2262 return isl_bool_error
;
2263 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
2264 if (is_subset
!= isl_bool_true
)
2266 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
2267 if (is_subset
== isl_bool_error
)
2272 isl_bool
isl_union_set_is_strict_subset(__isl_keep isl_union_set
*uset1
,
2273 __isl_keep isl_union_set
*uset2
)
2275 return isl_union_map_is_strict_subset(uset1
, uset2
);
2278 /* Internal data structure for isl_union_map_is_disjoint.
2279 * umap2 is the union map with which we are comparing.
2280 * is_disjoint is initialized to 1 and is set to 0 as soon
2281 * as the union maps turn out not to be disjoint.
2283 struct isl_union_map_is_disjoint_data
{
2284 isl_union_map
*umap2
;
2285 isl_bool is_disjoint
;
2288 /* Check if "map" is disjoint from data->umap2 and abort
2289 * the search if it is not.
2291 static isl_stat
is_disjoint_entry(void **entry
, void *user
)
2293 struct isl_union_map_is_disjoint_data
*data
= user
;
2295 struct isl_hash_table_entry
*entry2
;
2296 isl_map
*map
= *entry
;
2298 hash
= isl_space_get_hash(map
->dim
);
2299 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
2300 hash
, &has_space
, map
->dim
, 0);
2304 data
->is_disjoint
= isl_map_is_disjoint(map
, entry2
->data
);
2305 if (data
->is_disjoint
< 0 || !data
->is_disjoint
)
2306 return isl_stat_error
;
2311 /* Are "umap1" and "umap2" disjoint?
2313 isl_bool
isl_union_map_is_disjoint(__isl_keep isl_union_map
*umap1
,
2314 __isl_keep isl_union_map
*umap2
)
2316 struct isl_union_map_is_disjoint_data data
= { NULL
, isl_bool_true
};
2318 umap1
= isl_union_map_copy(umap1
);
2319 umap2
= isl_union_map_copy(umap2
);
2320 umap1
= isl_union_map_align_params(umap1
,
2321 isl_union_map_get_space(umap2
));
2322 umap2
= isl_union_map_align_params(umap2
,
2323 isl_union_map_get_space(umap1
));
2325 if (!umap1
|| !umap2
)
2329 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
2330 &is_disjoint_entry
, &data
) < 0 &&
2334 isl_union_map_free(umap1
);
2335 isl_union_map_free(umap2
);
2337 return data
.is_disjoint
;
2339 isl_union_map_free(umap1
);
2340 isl_union_map_free(umap2
);
2341 return isl_bool_error
;
2344 /* Are "uset1" and "uset2" disjoint?
2346 isl_bool
isl_union_set_is_disjoint(__isl_keep isl_union_set
*uset1
,
2347 __isl_keep isl_union_set
*uset2
)
2349 return isl_union_map_is_disjoint(uset1
, uset2
);
2352 static isl_stat
sample_entry(void **entry
, void *user
)
2354 isl_basic_map
**sample
= (isl_basic_map
**)user
;
2355 isl_map
*map
= *entry
;
2357 *sample
= isl_map_sample(isl_map_copy(map
));
2359 return isl_stat_error
;
2360 if (!isl_basic_map_plain_is_empty(*sample
))
2361 return isl_stat_error
;
2365 __isl_give isl_basic_map
*isl_union_map_sample(__isl_take isl_union_map
*umap
)
2367 isl_basic_map
*sample
= NULL
;
2372 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2373 &sample_entry
, &sample
) < 0 &&
2378 sample
= isl_basic_map_empty(isl_union_map_get_space(umap
));
2380 isl_union_map_free(umap
);
2384 isl_union_map_free(umap
);
2388 __isl_give isl_basic_set
*isl_union_set_sample(__isl_take isl_union_set
*uset
)
2390 return bset_from_bmap(isl_union_map_sample(uset
));
2393 /* Return an element in "uset" in the form of an isl_point.
2394 * Return a void isl_point if "uset" is empty.
2396 __isl_give isl_point
*isl_union_set_sample_point(__isl_take isl_union_set
*uset
)
2398 return isl_basic_set_sample_point(isl_union_set_sample(uset
));
2401 struct isl_forall_data
{
2403 isl_bool (*fn
)(__isl_keep isl_map
*map
);
2406 static isl_stat
forall_entry(void **entry
, void *user
)
2408 struct isl_forall_data
*data
= user
;
2409 isl_map
*map
= *entry
;
2411 data
->res
= data
->fn(map
);
2413 return isl_stat_error
;
2416 return isl_stat_error
;
2421 static isl_bool
union_map_forall(__isl_keep isl_union_map
*umap
,
2422 isl_bool (*fn
)(__isl_keep isl_map
*map
))
2424 struct isl_forall_data data
= { isl_bool_true
, fn
};
2427 return isl_bool_error
;
2429 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2430 &forall_entry
, &data
) < 0 && data
.res
)
2431 return isl_bool_error
;
2436 struct isl_forall_user_data
{
2438 isl_bool (*fn
)(__isl_keep isl_map
*map
, void *user
);
2442 static isl_stat
forall_user_entry(void **entry
, void *user
)
2444 struct isl_forall_user_data
*data
= user
;
2445 isl_map
*map
= *entry
;
2447 data
->res
= data
->fn(map
, data
->user
);
2449 return isl_stat_error
;
2452 return isl_stat_error
;
2457 /* Check if fn(map, user) returns true for all maps "map" in umap.
2459 static isl_bool
union_map_forall_user(__isl_keep isl_union_map
*umap
,
2460 isl_bool (*fn
)(__isl_keep isl_map
*map
, void *user
), void *user
)
2462 struct isl_forall_user_data data
= { isl_bool_true
, fn
, user
};
2465 return isl_bool_error
;
2467 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2468 &forall_user_entry
, &data
) < 0 && data
.res
)
2469 return isl_bool_error
;
2474 isl_bool
isl_union_map_is_empty(__isl_keep isl_union_map
*umap
)
2476 return union_map_forall(umap
, &isl_map_is_empty
);
2479 isl_bool
isl_union_set_is_empty(__isl_keep isl_union_set
*uset
)
2481 return isl_union_map_is_empty(uset
);
2484 static isl_bool
is_subset_of_identity(__isl_keep isl_map
*map
)
2491 return isl_bool_error
;
2493 if (!isl_space_tuple_is_equal(map
->dim
, isl_dim_in
,
2494 map
->dim
, isl_dim_out
))
2495 return isl_bool_false
;
2497 dim
= isl_map_get_space(map
);
2498 id
= isl_map_identity(dim
);
2500 is_subset
= isl_map_is_subset(map
, id
);
2507 /* Given an isl_union_map that consists of a single map, check
2508 * if it is single-valued.
2510 static isl_bool
single_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2515 umap
= isl_union_map_copy(umap
);
2516 map
= isl_map_from_union_map(umap
);
2517 sv
= isl_map_is_single_valued(map
);
2523 /* Internal data structure for single_valued_on_domain.
2525 * "umap" is the union map to be tested.
2526 * "sv" is set to 1 as long as "umap" may still be single-valued.
2528 struct isl_union_map_is_sv_data
{
2529 isl_union_map
*umap
;
2533 /* Check if the data->umap is single-valued on "set".
2535 * If data->umap consists of a single map on "set", then test it
2538 * Otherwise, compute
2542 * check if the result is a subset of the identity mapping and
2543 * store the result in data->sv.
2545 * Terminate as soon as data->umap has been determined not to
2548 static isl_stat
single_valued_on_domain(__isl_take isl_set
*set
, void *user
)
2550 struct isl_union_map_is_sv_data
*data
= user
;
2551 isl_union_map
*umap
, *test
;
2553 umap
= isl_union_map_copy(data
->umap
);
2554 umap
= isl_union_map_intersect_domain(umap
,
2555 isl_union_set_from_set(set
));
2557 if (isl_union_map_n_map(umap
) == 1) {
2558 data
->sv
= single_map_is_single_valued(umap
);
2559 isl_union_map_free(umap
);
2561 test
= isl_union_map_reverse(isl_union_map_copy(umap
));
2562 test
= isl_union_map_apply_range(test
, umap
);
2564 data
->sv
= union_map_forall(test
, &is_subset_of_identity
);
2566 isl_union_map_free(test
);
2569 if (data
->sv
< 0 || !data
->sv
)
2570 return isl_stat_error
;
2574 /* Check if the given map is single-valued.
2576 * If the union map consists of a single map, then test it as an isl_map.
2577 * Otherwise, check if the union map is single-valued on each of its
2580 isl_bool
isl_union_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2582 isl_union_map
*universe
;
2583 isl_union_set
*domain
;
2584 struct isl_union_map_is_sv_data data
;
2586 if (isl_union_map_n_map(umap
) == 1)
2587 return single_map_is_single_valued(umap
);
2589 universe
= isl_union_map_universe(isl_union_map_copy(umap
));
2590 domain
= isl_union_map_domain(universe
);
2592 data
.sv
= isl_bool_true
;
2594 if (isl_union_set_foreach_set(domain
,
2595 &single_valued_on_domain
, &data
) < 0 && data
.sv
)
2596 data
.sv
= isl_bool_error
;
2597 isl_union_set_free(domain
);
2602 isl_bool
isl_union_map_is_injective(__isl_keep isl_union_map
*umap
)
2606 umap
= isl_union_map_copy(umap
);
2607 umap
= isl_union_map_reverse(umap
);
2608 in
= isl_union_map_is_single_valued(umap
);
2609 isl_union_map_free(umap
);
2614 /* Is "map" obviously not an identity relation because
2615 * it maps elements from one space to another space?
2616 * Update *non_identity accordingly.
2618 * In particular, if the domain and range spaces are the same,
2619 * then the map is not considered to obviously not be an identity relation.
2620 * Otherwise, the map is considered to obviously not be an identity relation
2621 * if it is is non-empty.
2623 * If "map" is determined to obviously not be an identity relation,
2624 * then the search is aborted.
2626 static isl_stat
map_plain_is_not_identity(__isl_take isl_map
*map
, void *user
)
2628 isl_bool
*non_identity
= user
;
2632 space
= isl_map_get_space(map
);
2633 equal
= isl_space_tuple_is_equal(space
, isl_dim_in
, space
, isl_dim_out
);
2634 if (equal
>= 0 && !equal
)
2635 *non_identity
= isl_bool_not(isl_map_is_empty(map
));
2637 *non_identity
= isl_bool_not(equal
);
2638 isl_space_free(space
);
2641 if (*non_identity
< 0 || *non_identity
)
2642 return isl_stat_error
;
2647 /* Is "umap" obviously not an identity relation because
2648 * it maps elements from one space to another space?
2650 * As soon as a map has been found that maps elements to a different space,
2651 * non_identity is changed and the search is aborted.
2653 static isl_bool
isl_union_map_plain_is_not_identity(
2654 __isl_keep isl_union_map
*umap
)
2656 isl_bool non_identity
;
2658 non_identity
= isl_bool_false
;
2659 if (isl_union_map_foreach_map(umap
, &map_plain_is_not_identity
,
2660 &non_identity
) < 0 &&
2661 non_identity
== isl_bool_false
)
2662 return isl_bool_error
;
2664 return non_identity
;
2667 /* Does "map" only map elements to themselves?
2668 * Update *identity accordingly.
2670 * If "map" is determined not to be an identity relation,
2671 * then the search is aborted.
2673 static isl_stat
map_is_identity(__isl_take isl_map
*map
, void *user
)
2675 isl_bool
*identity
= user
;
2677 *identity
= isl_map_is_identity(map
);
2680 if (*identity
< 0 || !*identity
)
2681 return isl_stat_error
;
2686 /* Does "umap" only map elements to themselves?
2688 * First check if there are any maps that map elements to different spaces.
2689 * If not, then check that all the maps (between identical spaces)
2690 * are identity relations.
2692 isl_bool
isl_union_map_is_identity(__isl_keep isl_union_map
*umap
)
2694 isl_bool non_identity
;
2697 non_identity
= isl_union_map_plain_is_not_identity(umap
);
2698 if (non_identity
< 0 || non_identity
)
2699 return isl_bool_not(non_identity
);
2701 identity
= isl_bool_true
;
2702 if (isl_union_map_foreach_map(umap
, &map_is_identity
, &identity
) < 0 &&
2703 identity
== isl_bool_true
)
2704 return isl_bool_error
;
2709 /* Represents a map that has a fixed value (v) for one of its
2711 * The map in this structure is not reference counted, so it
2712 * is only valid while the isl_union_map from which it was
2713 * obtained is still alive.
2715 struct isl_fixed_map
{
2720 static struct isl_fixed_map
*alloc_isl_fixed_map_array(isl_ctx
*ctx
,
2724 struct isl_fixed_map
*v
;
2726 v
= isl_calloc_array(ctx
, struct isl_fixed_map
, n
);
2729 for (i
= 0; i
< n
; ++i
)
2730 isl_int_init(v
[i
].v
);
2734 static void free_isl_fixed_map_array(struct isl_fixed_map
*v
, int n
)
2740 for (i
= 0; i
< n
; ++i
)
2741 isl_int_clear(v
[i
].v
);
2745 /* Compare the "v" field of two isl_fixed_map structs.
2747 static int qsort_fixed_map_cmp(const void *p1
, const void *p2
)
2749 const struct isl_fixed_map
*e1
= (const struct isl_fixed_map
*) p1
;
2750 const struct isl_fixed_map
*e2
= (const struct isl_fixed_map
*) p2
;
2752 return isl_int_cmp(e1
->v
, e2
->v
);
2755 /* Internal data structure used while checking whether all maps
2756 * in a union_map have a fixed value for a given output dimension.
2757 * v is the list of maps, with the fixed value for the dimension
2758 * n is the number of maps considered so far
2759 * pos is the output dimension under investigation
2761 struct isl_fixed_dim_data
{
2762 struct isl_fixed_map
*v
;
2767 static isl_bool
fixed_at_pos(__isl_keep isl_map
*map
, void *user
)
2769 struct isl_fixed_dim_data
*data
= user
;
2771 data
->v
[data
->n
].map
= map
;
2772 return isl_map_plain_is_fixed(map
, isl_dim_out
, data
->pos
,
2773 &data
->v
[data
->n
++].v
);
2776 static isl_bool
plain_injective_on_range(__isl_take isl_union_map
*umap
,
2777 int first
, int n_range
);
2779 /* Given a list of the maps, with their fixed values at output dimension "pos",
2780 * check whether the ranges of the maps form an obvious partition.
2782 * We first sort the maps according to their fixed values.
2783 * If all maps have a different value, then we know the ranges form
2785 * Otherwise, we collect the maps with the same fixed value and
2786 * check whether each such collection is obviously injective
2787 * based on later dimensions.
2789 static int separates(struct isl_fixed_map
*v
, int n
,
2790 __isl_take isl_space
*dim
, int pos
, int n_range
)
2797 qsort(v
, n
, sizeof(*v
), &qsort_fixed_map_cmp
);
2799 for (i
= 0; i
+ 1 < n
; ++i
) {
2801 isl_union_map
*part
;
2804 for (j
= i
+ 1; j
< n
; ++j
)
2805 if (isl_int_ne(v
[i
].v
, v
[j
].v
))
2811 part
= isl_union_map_alloc(isl_space_copy(dim
), j
- i
);
2812 for (k
= i
; k
< j
; ++k
)
2813 part
= isl_union_map_add_map(part
,
2814 isl_map_copy(v
[k
].map
));
2816 injective
= plain_injective_on_range(part
, pos
+ 1, n_range
);
2825 isl_space_free(dim
);
2826 free_isl_fixed_map_array(v
, n
);
2829 isl_space_free(dim
);
2830 free_isl_fixed_map_array(v
, n
);
2834 /* Check whether the maps in umap have obviously distinct ranges.
2835 * In particular, check for an output dimension in the range
2836 * [first,n_range) for which all maps have a fixed value
2837 * and then check if these values, possibly along with fixed values
2838 * at later dimensions, entail distinct ranges.
2840 static isl_bool
plain_injective_on_range(__isl_take isl_union_map
*umap
,
2841 int first
, int n_range
)
2845 struct isl_fixed_dim_data data
= { NULL
};
2847 ctx
= isl_union_map_get_ctx(umap
);
2849 n
= isl_union_map_n_map(umap
);
2854 isl_union_map_free(umap
);
2855 return isl_bool_true
;
2858 if (first
>= n_range
) {
2859 isl_union_map_free(umap
);
2860 return isl_bool_false
;
2863 data
.v
= alloc_isl_fixed_map_array(ctx
, n
);
2867 for (data
.pos
= first
; data
.pos
< n_range
; ++data
.pos
) {
2873 fixed
= union_map_forall_user(umap
, &fixed_at_pos
, &data
);
2878 dim
= isl_union_map_get_space(umap
);
2879 injective
= separates(data
.v
, n
, dim
, data
.pos
, n_range
);
2880 isl_union_map_free(umap
);
2884 free_isl_fixed_map_array(data
.v
, n
);
2885 isl_union_map_free(umap
);
2887 return isl_bool_false
;
2889 free_isl_fixed_map_array(data
.v
, n
);
2890 isl_union_map_free(umap
);
2891 return isl_bool_error
;
2894 /* Check whether the maps in umap that map to subsets of "ran"
2895 * have obviously distinct ranges.
2897 static isl_bool
plain_injective_on_range_wrap(__isl_keep isl_set
*ran
,
2900 isl_union_map
*umap
= user
;
2902 umap
= isl_union_map_copy(umap
);
2903 umap
= isl_union_map_intersect_range(umap
,
2904 isl_union_set_from_set(isl_set_copy(ran
)));
2905 return plain_injective_on_range(umap
, 0, isl_set_dim(ran
, isl_dim_set
));
2908 /* Check if the given union_map is obviously injective.
2910 * In particular, we first check if all individual maps are obviously
2911 * injective and then check if all the ranges of these maps are
2912 * obviously disjoint.
2914 isl_bool
isl_union_map_plain_is_injective(__isl_keep isl_union_map
*umap
)
2917 isl_union_map
*univ
;
2920 in
= union_map_forall(umap
, &isl_map_plain_is_injective
);
2922 return isl_bool_error
;
2924 return isl_bool_false
;
2926 univ
= isl_union_map_universe(isl_union_map_copy(umap
));
2927 ran
= isl_union_map_range(univ
);
2929 in
= union_map_forall_user(ran
, &plain_injective_on_range_wrap
, umap
);
2931 isl_union_set_free(ran
);
2936 isl_bool
isl_union_map_is_bijective(__isl_keep isl_union_map
*umap
)
2940 sv
= isl_union_map_is_single_valued(umap
);
2944 return isl_union_map_is_injective(umap
);
2947 __isl_give isl_union_map
*isl_union_map_zip(__isl_take isl_union_map
*umap
)
2949 struct isl_un_op_control control
= {
2950 .filter
= &isl_map_can_zip
,
2951 .fn_map
= &isl_map_zip
,
2953 return un_op(umap
, &control
);
2956 /* Given a union map, take the maps of the form A -> (B -> C) and
2957 * return the union of the corresponding maps (A -> B) -> C.
2959 __isl_give isl_union_map
*isl_union_map_uncurry(__isl_take isl_union_map
*umap
)
2961 struct isl_un_op_control control
= {
2962 .filter
= &isl_map_can_uncurry
,
2963 .fn_map
= &isl_map_uncurry
,
2965 return un_op(umap
, &control
);
2968 /* Given a union map, take the maps of the form (A -> B) -> C and
2969 * return the union of the corresponding maps A -> (B -> C).
2971 __isl_give isl_union_map
*isl_union_map_curry(__isl_take isl_union_map
*umap
)
2973 struct isl_un_op_control control
= {
2974 .filter
= &isl_map_can_curry
,
2975 .fn_map
= &isl_map_curry
,
2977 return un_op(umap
, &control
);
2980 /* Given a union map, take the maps of the form A -> ((B -> C) -> D) and
2981 * return the union of the corresponding maps A -> (B -> (C -> D)).
2983 __isl_give isl_union_map
*isl_union_map_range_curry(
2984 __isl_take isl_union_map
*umap
)
2986 struct isl_un_op_control control
= {
2987 .filter
= &isl_map_can_range_curry
,
2988 .fn_map
= &isl_map_range_curry
,
2990 return un_op(umap
, &control
);
2993 __isl_give isl_union_set
*isl_union_set_lift(__isl_take isl_union_set
*uset
)
2995 struct isl_un_op_control control
= {
2996 .fn_map
= &isl_set_lift
,
2998 return un_op(uset
, &control
);
3001 static isl_stat
coefficients_entry(void **entry
, void *user
)
3003 isl_set
*set
= *entry
;
3004 isl_union_set
**res
= user
;
3006 set
= isl_set_copy(set
);
3007 set
= isl_set_from_basic_set(isl_set_coefficients(set
));
3008 *res
= isl_union_set_add_set(*res
, set
);
3013 __isl_give isl_union_set
*isl_union_set_coefficients(
3014 __isl_take isl_union_set
*uset
)
3023 ctx
= isl_union_set_get_ctx(uset
);
3024 dim
= isl_space_set_alloc(ctx
, 0, 0);
3025 res
= isl_union_map_alloc(dim
, uset
->table
.n
);
3026 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
3027 &coefficients_entry
, &res
) < 0)
3030 isl_union_set_free(uset
);
3033 isl_union_set_free(uset
);
3034 isl_union_set_free(res
);
3038 static isl_stat
solutions_entry(void **entry
, void *user
)
3040 isl_set
*set
= *entry
;
3041 isl_union_set
**res
= user
;
3043 set
= isl_set_copy(set
);
3044 set
= isl_set_from_basic_set(isl_set_solutions(set
));
3046 *res
= isl_union_set_from_set(set
);
3048 *res
= isl_union_set_add_set(*res
, set
);
3051 return isl_stat_error
;
3056 __isl_give isl_union_set
*isl_union_set_solutions(
3057 __isl_take isl_union_set
*uset
)
3059 isl_union_set
*res
= NULL
;
3064 if (uset
->table
.n
== 0) {
3065 res
= isl_union_set_empty(isl_union_set_get_space(uset
));
3066 isl_union_set_free(uset
);
3070 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
3071 &solutions_entry
, &res
) < 0)
3074 isl_union_set_free(uset
);
3077 isl_union_set_free(uset
);
3078 isl_union_set_free(res
);
3082 /* Is the domain space of "map" equal to "space"?
3084 static int domain_match(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
)
3086 return isl_space_tuple_is_equal(map
->dim
, isl_dim_in
,
3087 space
, isl_dim_out
);
3090 /* Is the range space of "map" equal to "space"?
3092 static int range_match(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
)
3094 return isl_space_tuple_is_equal(map
->dim
, isl_dim_out
,
3095 space
, isl_dim_out
);
3098 /* Is the set space of "map" equal to "space"?
3100 static int set_match(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
)
3102 return isl_space_tuple_is_equal(map
->dim
, isl_dim_set
,
3103 space
, isl_dim_out
);
3106 /* Internal data structure for preimage_pw_multi_aff.
3108 * "pma" is the function under which the preimage should be taken.
3109 * "space" is the space of "pma".
3110 * "res" collects the results.
3111 * "fn" computes the preimage for a given map.
3112 * "match" returns true if "fn" can be called.
3114 struct isl_union_map_preimage_data
{
3116 isl_pw_multi_aff
*pma
;
3118 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
);
3119 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3120 __isl_take isl_pw_multi_aff
*pma
);
3123 /* Call data->fn to compute the preimage of the domain or range of *entry
3124 * under the function represented by data->pma, provided the domain/range
3125 * space of *entry matches the target space of data->pma
3126 * (as given by data->match), and add the result to data->res.
3128 static isl_stat
preimage_entry(void **entry
, void *user
)
3131 isl_map
*map
= *entry
;
3132 struct isl_union_map_preimage_data
*data
= user
;
3135 m
= data
->match(map
, data
->space
);
3137 return isl_stat_error
;
3141 map
= isl_map_copy(map
);
3142 map
= data
->fn(map
, isl_pw_multi_aff_copy(data
->pma
));
3144 empty
= isl_map_is_empty(map
);
3145 if (empty
< 0 || empty
) {
3147 return empty
< 0 ? isl_stat_error
: isl_stat_ok
;
3150 data
->res
= isl_union_map_add_map(data
->res
, map
);
3155 /* Compute the preimage of the domain or range of "umap" under the function
3156 * represented by "pma".
3157 * In other words, plug in "pma" in the domain or range of "umap".
3158 * The function "fn" performs the actual preimage computation on a map,
3159 * while "match" determines to which maps the function should be applied.
3161 static __isl_give isl_union_map
*preimage_pw_multi_aff(
3162 __isl_take isl_union_map
*umap
, __isl_take isl_pw_multi_aff
*pma
,
3163 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
),
3164 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3165 __isl_take isl_pw_multi_aff
*pma
))
3169 struct isl_union_map_preimage_data data
;
3171 umap
= isl_union_map_align_params(umap
,
3172 isl_pw_multi_aff_get_space(pma
));
3173 pma
= isl_pw_multi_aff_align_params(pma
, isl_union_map_get_space(umap
));
3178 ctx
= isl_union_map_get_ctx(umap
);
3179 space
= isl_union_map_get_space(umap
);
3180 data
.space
= isl_pw_multi_aff_get_space(pma
);
3182 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
3185 if (isl_hash_table_foreach(ctx
, &umap
->table
, &preimage_entry
,
3187 data
.res
= isl_union_map_free(data
.res
);
3189 isl_space_free(data
.space
);
3190 isl_union_map_free(umap
);
3191 isl_pw_multi_aff_free(pma
);
3194 isl_union_map_free(umap
);
3195 isl_pw_multi_aff_free(pma
);
3199 /* Compute the preimage of the domain of "umap" under the function
3200 * represented by "pma".
3201 * In other words, plug in "pma" in the domain of "umap".
3202 * The result contains maps that live in the same spaces as the maps of "umap"
3203 * with domain space equal to the target space of "pma",
3204 * except that the domain has been replaced by the domain space of "pma".
3206 __isl_give isl_union_map
*isl_union_map_preimage_domain_pw_multi_aff(
3207 __isl_take isl_union_map
*umap
, __isl_take isl_pw_multi_aff
*pma
)
3209 return preimage_pw_multi_aff(umap
, pma
, &domain_match
,
3210 &isl_map_preimage_domain_pw_multi_aff
);
3213 /* Compute the preimage of the range of "umap" under the function
3214 * represented by "pma".
3215 * In other words, plug in "pma" in the range of "umap".
3216 * The result contains maps that live in the same spaces as the maps of "umap"
3217 * with range space equal to the target space of "pma",
3218 * except that the range has been replaced by the domain space of "pma".
3220 __isl_give isl_union_map
*isl_union_map_preimage_range_pw_multi_aff(
3221 __isl_take isl_union_map
*umap
, __isl_take isl_pw_multi_aff
*pma
)
3223 return preimage_pw_multi_aff(umap
, pma
, &range_match
,
3224 &isl_map_preimage_range_pw_multi_aff
);
3227 /* Compute the preimage of "uset" under the function represented by "pma".
3228 * In other words, plug in "pma" in "uset".
3229 * The result contains sets that live in the same spaces as the sets of "uset"
3230 * with space equal to the target space of "pma",
3231 * except that the space has been replaced by the domain space of "pma".
3233 __isl_give isl_union_set
*isl_union_set_preimage_pw_multi_aff(
3234 __isl_take isl_union_set
*uset
, __isl_take isl_pw_multi_aff
*pma
)
3236 return preimage_pw_multi_aff(uset
, pma
, &set_match
,
3237 &isl_set_preimage_pw_multi_aff
);
3240 /* Compute the preimage of the domain of "umap" under the function
3241 * represented by "ma".
3242 * In other words, plug in "ma" in the domain of "umap".
3243 * The result contains maps that live in the same spaces as the maps of "umap"
3244 * with domain space equal to the target space of "ma",
3245 * except that the domain has been replaced by the domain space of "ma".
3247 __isl_give isl_union_map
*isl_union_map_preimage_domain_multi_aff(
3248 __isl_take isl_union_map
*umap
, __isl_take isl_multi_aff
*ma
)
3250 return isl_union_map_preimage_domain_pw_multi_aff(umap
,
3251 isl_pw_multi_aff_from_multi_aff(ma
));
3254 /* Compute the preimage of the range of "umap" under the function
3255 * represented by "ma".
3256 * In other words, plug in "ma" in the range of "umap".
3257 * The result contains maps that live in the same spaces as the maps of "umap"
3258 * with range space equal to the target space of "ma",
3259 * except that the range has been replaced by the domain space of "ma".
3261 __isl_give isl_union_map
*isl_union_map_preimage_range_multi_aff(
3262 __isl_take isl_union_map
*umap
, __isl_take isl_multi_aff
*ma
)
3264 return isl_union_map_preimage_range_pw_multi_aff(umap
,
3265 isl_pw_multi_aff_from_multi_aff(ma
));
3268 /* Compute the preimage of "uset" under the function represented by "ma".
3269 * In other words, plug in "ma" in "uset".
3270 * The result contains sets that live in the same spaces as the sets of "uset"
3271 * with space equal to the target space of "ma",
3272 * except that the space has been replaced by the domain space of "ma".
3274 __isl_give isl_union_map
*isl_union_set_preimage_multi_aff(
3275 __isl_take isl_union_set
*uset
, __isl_take isl_multi_aff
*ma
)
3277 return isl_union_set_preimage_pw_multi_aff(uset
,
3278 isl_pw_multi_aff_from_multi_aff(ma
));
3281 /* Internal data structure for preimage_multi_pw_aff.
3283 * "mpa" is the function under which the preimage should be taken.
3284 * "space" is the space of "mpa".
3285 * "res" collects the results.
3286 * "fn" computes the preimage for a given map.
3287 * "match" returns true if "fn" can be called.
3289 struct isl_union_map_preimage_mpa_data
{
3291 isl_multi_pw_aff
*mpa
;
3293 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
);
3294 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3295 __isl_take isl_multi_pw_aff
*mpa
);
3298 /* Call data->fn to compute the preimage of the domain or range of *entry
3299 * under the function represented by data->mpa, provided the domain/range
3300 * space of *entry matches the target space of data->mpa
3301 * (as given by data->match), and add the result to data->res.
3303 static isl_stat
preimage_mpa_entry(void **entry
, void *user
)
3306 isl_map
*map
= *entry
;
3307 struct isl_union_map_preimage_mpa_data
*data
= user
;
3310 m
= data
->match(map
, data
->space
);
3312 return isl_stat_error
;
3316 map
= isl_map_copy(map
);
3317 map
= data
->fn(map
, isl_multi_pw_aff_copy(data
->mpa
));
3319 empty
= isl_map_is_empty(map
);
3320 if (empty
< 0 || empty
) {
3322 return empty
< 0 ? isl_stat_error
: isl_stat_ok
;
3325 data
->res
= isl_union_map_add_map(data
->res
, map
);
3330 /* Compute the preimage of the domain or range of "umap" under the function
3331 * represented by "mpa".
3332 * In other words, plug in "mpa" in the domain or range of "umap".
3333 * The function "fn" performs the actual preimage computation on a map,
3334 * while "match" determines to which maps the function should be applied.
3336 static __isl_give isl_union_map
*preimage_multi_pw_aff(
3337 __isl_take isl_union_map
*umap
, __isl_take isl_multi_pw_aff
*mpa
,
3338 int (*match
)(__isl_keep isl_map
*map
, __isl_keep isl_space
*space
),
3339 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*map
,
3340 __isl_take isl_multi_pw_aff
*mpa
))
3344 struct isl_union_map_preimage_mpa_data data
;
3346 umap
= isl_union_map_align_params(umap
,
3347 isl_multi_pw_aff_get_space(mpa
));
3348 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_union_map_get_space(umap
));
3353 ctx
= isl_union_map_get_ctx(umap
);
3354 space
= isl_union_map_get_space(umap
);
3355 data
.space
= isl_multi_pw_aff_get_space(mpa
);
3357 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
3360 if (isl_hash_table_foreach(ctx
, &umap
->table
, &preimage_mpa_entry
,
3362 data
.res
= isl_union_map_free(data
.res
);
3364 isl_space_free(data
.space
);
3365 isl_union_map_free(umap
);
3366 isl_multi_pw_aff_free(mpa
);
3369 isl_union_map_free(umap
);
3370 isl_multi_pw_aff_free(mpa
);
3374 /* Compute the preimage of the domain of "umap" under the function
3375 * represented by "mpa".
3376 * In other words, plug in "mpa" in the domain of "umap".
3377 * The result contains maps that live in the same spaces as the maps of "umap"
3378 * with domain space equal to the target space of "mpa",
3379 * except that the domain has been replaced by the domain space of "mpa".
3381 __isl_give isl_union_map
*isl_union_map_preimage_domain_multi_pw_aff(
3382 __isl_take isl_union_map
*umap
, __isl_take isl_multi_pw_aff
*mpa
)
3384 return preimage_multi_pw_aff(umap
, mpa
, &domain_match
,
3385 &isl_map_preimage_domain_multi_pw_aff
);
3388 /* Internal data structure for preimage_upma.
3390 * "umap" is the map of which the preimage should be computed.
3391 * "res" collects the results.
3392 * "fn" computes the preimage for a given piecewise multi-affine function.
3394 struct isl_union_map_preimage_upma_data
{
3395 isl_union_map
*umap
;
3397 __isl_give isl_union_map
*(*fn
)(__isl_take isl_union_map
*umap
,
3398 __isl_take isl_pw_multi_aff
*pma
);
3401 /* Call data->fn to compute the preimage of the domain or range of data->umap
3402 * under the function represented by pma and add the result to data->res.
3404 static isl_stat
preimage_upma(__isl_take isl_pw_multi_aff
*pma
, void *user
)
3406 struct isl_union_map_preimage_upma_data
*data
= user
;
3407 isl_union_map
*umap
;
3409 umap
= isl_union_map_copy(data
->umap
);
3410 umap
= data
->fn(umap
, pma
);
3411 data
->res
= isl_union_map_union(data
->res
, umap
);
3413 return data
->res
? isl_stat_ok
: isl_stat_error
;
3416 /* Compute the preimage of the domain or range of "umap" under the function
3417 * represented by "upma".
3418 * In other words, plug in "upma" in the domain or range of "umap".
3419 * The function "fn" performs the actual preimage computation
3420 * on a piecewise multi-affine function.
3422 static __isl_give isl_union_map
*preimage_union_pw_multi_aff(
3423 __isl_take isl_union_map
*umap
,
3424 __isl_take isl_union_pw_multi_aff
*upma
,
3425 __isl_give isl_union_map
*(*fn
)(__isl_take isl_union_map
*umap
,
3426 __isl_take isl_pw_multi_aff
*pma
))
3428 struct isl_union_map_preimage_upma_data data
;
3431 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3433 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
3434 &preimage_upma
, &data
) < 0)
3435 data
.res
= isl_union_map_free(data
.res
);
3437 isl_union_map_free(umap
);
3438 isl_union_pw_multi_aff_free(upma
);
3443 /* Compute the preimage of the domain of "umap" under the function
3444 * represented by "upma".
3445 * In other words, plug in "upma" in the domain of "umap".
3446 * The result contains maps that live in the same spaces as the maps of "umap"
3447 * with domain space equal to one of the target spaces of "upma",
3448 * except that the domain has been replaced by one of the the domain spaces that
3449 * corresponds to that target space of "upma".
3451 __isl_give isl_union_map
*isl_union_map_preimage_domain_union_pw_multi_aff(
3452 __isl_take isl_union_map
*umap
,
3453 __isl_take isl_union_pw_multi_aff
*upma
)
3455 return preimage_union_pw_multi_aff(umap
, upma
,
3456 &isl_union_map_preimage_domain_pw_multi_aff
);
3459 /* Compute the preimage of the range of "umap" under the function
3460 * represented by "upma".
3461 * In other words, plug in "upma" in the range of "umap".
3462 * The result contains maps that live in the same spaces as the maps of "umap"
3463 * with range space equal to one of the target spaces of "upma",
3464 * except that the range has been replaced by one of the the domain spaces that
3465 * corresponds to that target space of "upma".
3467 __isl_give isl_union_map
*isl_union_map_preimage_range_union_pw_multi_aff(
3468 __isl_take isl_union_map
*umap
,
3469 __isl_take isl_union_pw_multi_aff
*upma
)
3471 return preimage_union_pw_multi_aff(umap
, upma
,
3472 &isl_union_map_preimage_range_pw_multi_aff
);
3475 /* Compute the preimage of "uset" under the function represented by "upma".
3476 * In other words, plug in "upma" in the range of "uset".
3477 * The result contains sets that live in the same spaces as the sets of "uset"
3478 * with space equal to one of the target spaces of "upma",
3479 * except that the space has been replaced by one of the the domain spaces that
3480 * corresponds to that target space of "upma".
3482 __isl_give isl_union_set
*isl_union_set_preimage_union_pw_multi_aff(
3483 __isl_take isl_union_set
*uset
,
3484 __isl_take isl_union_pw_multi_aff
*upma
)
3486 return preimage_union_pw_multi_aff(uset
, upma
,
3487 &isl_union_set_preimage_pw_multi_aff
);
3490 /* Reset the user pointer on all identifiers of parameters and tuples
3491 * of the spaces of "umap".
3493 __isl_give isl_union_map
*isl_union_map_reset_user(
3494 __isl_take isl_union_map
*umap
)
3496 umap
= isl_union_map_cow(umap
);
3499 umap
->dim
= isl_space_reset_user(umap
->dim
);
3501 return isl_union_map_free(umap
);
3502 return total(umap
, &isl_map_reset_user
);
3505 /* Reset the user pointer on all identifiers of parameters and tuples
3506 * of the spaces of "uset".
3508 __isl_give isl_union_set
*isl_union_set_reset_user(
3509 __isl_take isl_union_set
*uset
)
3511 return isl_union_map_reset_user(uset
);
3514 /* Remove all existentially quantified variables and integer divisions
3515 * from "umap" using Fourier-Motzkin elimination.
3517 __isl_give isl_union_map
*isl_union_map_remove_divs(
3518 __isl_take isl_union_map
*umap
)
3520 return total(umap
, &isl_map_remove_divs
);
3523 /* Remove all existentially quantified variables and integer divisions
3524 * from "uset" using Fourier-Motzkin elimination.
3526 __isl_give isl_union_set
*isl_union_set_remove_divs(
3527 __isl_take isl_union_set
*uset
)
3529 return isl_union_map_remove_divs(uset
);
3532 /* Internal data structure for isl_union_map_project_out.
3533 * "type", "first" and "n" are the arguments for the isl_map_project_out
3535 * "res" collects the results.
3537 struct isl_union_map_project_out_data
{
3538 enum isl_dim_type type
;
3545 /* Turn the data->n dimensions of type data->type, starting at data->first
3546 * into existentially quantified variables and add the result to data->res.
3548 static isl_stat
project_out(__isl_take isl_map
*map
, void *user
)
3550 struct isl_union_map_project_out_data
*data
= user
;
3552 map
= isl_map_project_out(map
, data
->type
, data
->first
, data
->n
);
3553 data
->res
= isl_union_map_add_map(data
->res
, map
);
3558 /* Turn the "n" dimensions of type "type", starting at "first"
3559 * into existentially quantified variables.
3560 * Since the space of an isl_union_map only contains parameters,
3561 * type is required to be equal to isl_dim_param.
3563 __isl_give isl_union_map
*isl_union_map_project_out(
3564 __isl_take isl_union_map
*umap
,
3565 enum isl_dim_type type
, unsigned first
, unsigned n
)
3568 struct isl_union_map_project_out_data data
= { type
, first
, n
};
3573 if (type
!= isl_dim_param
)
3574 isl_die(isl_union_map_get_ctx(umap
), isl_error_invalid
,
3575 "can only project out parameters",
3576 return isl_union_map_free(umap
));
3578 space
= isl_union_map_get_space(umap
);
3579 space
= isl_space_drop_dims(space
, type
, first
, n
);
3580 data
.res
= isl_union_map_empty(space
);
3581 if (isl_union_map_foreach_map(umap
, &project_out
, &data
) < 0)
3582 data
.res
= isl_union_map_free(data
.res
);
3584 isl_union_map_free(umap
);
3589 /* Turn the "n" dimensions of type "type", starting at "first"
3590 * into existentially quantified variables.
3591 * Since the space of an isl_union_set only contains parameters,
3592 * "type" is required to be equal to isl_dim_param.
3594 __isl_give isl_union_set
*isl_union_set_project_out(
3595 __isl_take isl_union_set
*uset
,
3596 enum isl_dim_type type
, unsigned first
, unsigned n
)
3598 return isl_union_map_project_out(uset
, type
, first
, n
);
3601 /* Internal data structure for isl_union_map_involves_dims.
3602 * "first" and "n" are the arguments for the isl_map_involves_dims calls.
3604 struct isl_union_map_involves_dims_data
{
3609 /* Does "map" _not_ involve the data->n parameters starting at data->first?
3611 static isl_bool
map_excludes(__isl_keep isl_map
*map
, void *user
)
3613 struct isl_union_map_involves_dims_data
*data
= user
;
3616 involves
= isl_map_involves_dims(map
,
3617 isl_dim_param
, data
->first
, data
->n
);
3619 return isl_bool_error
;
3623 /* Does "umap" involve any of the n parameters starting at first?
3624 * "type" is required to be set to isl_dim_param.
3626 * "umap" involves any of those parameters if any of its maps
3627 * involve the parameters. In other words, "umap" does not
3628 * involve any of the parameters if all its maps to not
3629 * involve the parameters.
3631 isl_bool
isl_union_map_involves_dims(__isl_keep isl_union_map
*umap
,
3632 enum isl_dim_type type
, unsigned first
, unsigned n
)
3634 struct isl_union_map_involves_dims_data data
= { first
, n
};
3637 if (type
!= isl_dim_param
)
3638 isl_die(isl_union_map_get_ctx(umap
), isl_error_invalid
,
3639 "can only reference parameters", return isl_bool_error
);
3641 excludes
= union_map_forall_user(umap
, &map_excludes
, &data
);
3644 return isl_bool_error
;
3649 /* Internal data structure for isl_union_map_reset_range_space.
3650 * "range" is the space from which to set the range space.
3651 * "res" collects the results.
3653 struct isl_union_map_reset_range_space_data
{
3658 /* Replace the range space of "map" by the range space of data->range and
3659 * add the result to data->res.
3661 static isl_stat
reset_range_space(__isl_take isl_map
*map
, void *user
)
3663 struct isl_union_map_reset_range_space_data
*data
= user
;
3666 space
= isl_map_get_space(map
);
3667 space
= isl_space_domain(space
);
3668 space
= isl_space_extend_domain_with_range(space
,
3669 isl_space_copy(data
->range
));
3670 map
= isl_map_reset_space(map
, space
);
3671 data
->res
= isl_union_map_add_map(data
->res
, map
);
3673 return data
->res
? isl_stat_ok
: isl_stat_error
;
3676 /* Replace the range space of all the maps in "umap" by
3677 * the range space of "space".
3679 * This assumes that all maps have the same output dimension.
3680 * This function should therefore not be made publicly available.
3682 * Since the spaces of the maps change, so do their hash value.
3683 * We therefore need to create a new isl_union_map.
3685 __isl_give isl_union_map
*isl_union_map_reset_range_space(
3686 __isl_take isl_union_map
*umap
, __isl_take isl_space
*space
)
3688 struct isl_union_map_reset_range_space_data data
= { space
};
3690 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3691 if (isl_union_map_foreach_map(umap
, &reset_range_space
, &data
) < 0)
3692 data
.res
= isl_union_map_free(data
.res
);
3694 isl_space_free(space
);
3695 isl_union_map_free(umap
);
3699 /* Internal data structure for isl_union_map_order_at_multi_union_pw_aff.
3700 * "mupa" is the function from which the isl_multi_pw_affs are extracted.
3701 * "order" is applied to the extracted isl_multi_pw_affs that correspond
3702 * to the domain and the range of each map.
3703 * "res" collects the results.
3705 struct isl_union_order_at_data
{
3706 isl_multi_union_pw_aff
*mupa
;
3707 __isl_give isl_map
*(*order
)(__isl_take isl_multi_pw_aff
*mpa1
,
3708 __isl_take isl_multi_pw_aff
*mpa2
);
3712 /* Intersect "map" with the result of applying data->order to
3713 * the functions in data->mupa that apply to the domain and the range
3714 * of "map" and add the result to data->res.
3716 static isl_stat
order_at(__isl_take isl_map
*map
, void *user
)
3718 struct isl_union_order_at_data
*data
= user
;
3720 isl_multi_pw_aff
*mpa1
, *mpa2
;
3723 space
= isl_space_domain(isl_map_get_space(map
));
3724 mpa1
= isl_multi_union_pw_aff_extract_multi_pw_aff(data
->mupa
, space
);
3725 space
= isl_space_range(isl_map_get_space(map
));
3726 mpa2
= isl_multi_union_pw_aff_extract_multi_pw_aff(data
->mupa
, space
);
3727 order
= data
->order(mpa1
, mpa2
);
3728 map
= isl_map_intersect(map
, order
);
3729 data
->res
= isl_union_map_add_map(data
->res
, map
);
3731 return data
->res
? isl_stat_ok
: isl_stat_error
;
3734 /* Intersect each map in "umap" with the result of calling "order"
3735 * on the functions is "mupa" that apply to the domain and the range
3738 static __isl_give isl_union_map
*isl_union_map_order_at_multi_union_pw_aff(
3739 __isl_take isl_union_map
*umap
, __isl_take isl_multi_union_pw_aff
*mupa
,
3740 __isl_give isl_map
*(*order
)(__isl_take isl_multi_pw_aff
*mpa1
,
3741 __isl_take isl_multi_pw_aff
*mpa2
))
3743 struct isl_union_order_at_data data
;
3745 umap
= isl_union_map_align_params(umap
,
3746 isl_multi_union_pw_aff_get_space(mupa
));
3747 mupa
= isl_multi_union_pw_aff_align_params(mupa
,
3748 isl_union_map_get_space(umap
));
3751 data
.res
= isl_union_map_empty(isl_union_map_get_space(umap
));
3752 if (isl_union_map_foreach_map(umap
, &order_at
, &data
) < 0)
3753 data
.res
= isl_union_map_free(data
.res
);
3755 isl_multi_union_pw_aff_free(mupa
);
3756 isl_union_map_free(umap
);
3760 /* Return the subset of "umap" where the domain and the range
3761 * have equal "mupa" values.
3763 __isl_give isl_union_map
*isl_union_map_eq_at_multi_union_pw_aff(
3764 __isl_take isl_union_map
*umap
,
3765 __isl_take isl_multi_union_pw_aff
*mupa
)
3767 return isl_union_map_order_at_multi_union_pw_aff(umap
, mupa
,
3768 &isl_multi_pw_aff_eq_map
);
3771 /* Return the subset of "umap" where the domain has a lexicographically
3772 * smaller "mupa" value than the range.
3774 __isl_give isl_union_map
*isl_union_map_lex_lt_at_multi_union_pw_aff(
3775 __isl_take isl_union_map
*umap
,
3776 __isl_take isl_multi_union_pw_aff
*mupa
)
3778 return isl_union_map_order_at_multi_union_pw_aff(umap
, mupa
,
3779 &isl_multi_pw_aff_lex_lt_map
);
3782 /* Return the subset of "umap" where the domain has a lexicographically
3783 * greater "mupa" value than the range.
3785 __isl_give isl_union_map
*isl_union_map_lex_gt_at_multi_union_pw_aff(
3786 __isl_take isl_union_map
*umap
,
3787 __isl_take isl_multi_union_pw_aff
*mupa
)
3789 return isl_union_map_order_at_multi_union_pw_aff(umap
, mupa
,
3790 &isl_multi_pw_aff_lex_gt_map
);
3793 /* Return the union of the elements in the list "list".
3795 __isl_give isl_union_set
*isl_union_set_list_union(
3796 __isl_take isl_union_set_list
*list
)
3806 ctx
= isl_union_set_list_get_ctx(list
);
3807 space
= isl_space_params_alloc(ctx
, 0);
3808 res
= isl_union_set_empty(space
);
3810 n
= isl_union_set_list_n_union_set(list
);
3811 for (i
= 0; i
< n
; ++i
) {
3812 isl_union_set
*uset_i
;
3814 uset_i
= isl_union_set_list_get_union_set(list
, i
);
3815 res
= isl_union_set_union(res
, uset_i
);
3818 isl_union_set_list_free(list
);
3822 /* Update *hash with the hash value of "map".
3824 static isl_stat
add_hash(__isl_take isl_map
*map
, void *user
)
3826 uint32_t *hash
= user
;
3829 map_hash
= isl_map_get_hash(map
);
3830 isl_hash_hash(*hash
, map_hash
);
3836 /* Return a hash value that digests "umap".
3838 uint32_t isl_union_map_get_hash(__isl_keep isl_union_map
*umap
)
3845 hash
= isl_hash_init();
3846 if (isl_union_map_foreach_map(umap
, &add_hash
, &hash
) < 0)
3852 /* Return a hash value that digests "uset".
3854 uint32_t isl_union_set_get_hash(__isl_keep isl_union_set
*uset
)
3856 return isl_union_map_get_hash(uset
);
3859 /* Add the number of basic sets in "set" to "n".
3861 static isl_stat
add_n(__isl_take isl_set
*set
, void *user
)
3865 *n
+= isl_set_n_basic_set(set
);
3871 /* Return the total number of basic sets in "uset".
3873 int isl_union_set_n_basic_set(__isl_keep isl_union_set
*uset
)
3877 if (isl_union_set_foreach_set(uset
, &add_n
, &n
) < 0)
3883 /* Add the basic sets in "set" to "list".
3885 static isl_stat
add_list(__isl_take isl_set
*set
, void *user
)
3887 isl_basic_set_list
**list
= user
;
3888 isl_basic_set_list
*list_i
;
3890 list_i
= isl_set_get_basic_set_list(set
);
3891 *list
= isl_basic_set_list_concat(*list
, list_i
);
3895 return isl_stat_error
;
3899 /* Return a list containing all the basic sets in "uset".
3901 * First construct a list of the appropriate size and
3902 * then add all the elements.
3904 __isl_give isl_basic_set_list
*isl_union_set_get_basic_set_list(
3905 __isl_keep isl_union_set
*uset
)
3909 isl_basic_set_list
*list
;
3913 ctx
= isl_union_set_get_ctx(uset
);
3914 n
= isl_union_set_n_basic_set(uset
);
3917 list
= isl_basic_set_list_alloc(ctx
, n
);
3918 if (isl_union_set_foreach_set(uset
, &add_list
, &list
) < 0)
3919 list
= isl_basic_set_list_free(list
);