2 * Copyright 2010-2011 INRIA Saclay
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 #include <isl_map_private.h>
18 #include <isl_space_private.h>
19 #include <isl_union_map_private.h>
20 #include <isl/union_set.h>
22 /* Is this union set a parameter domain?
24 int isl_union_set_is_params(__isl_keep isl_union_set
*uset
)
31 if (uset
->table
.n
!= 1)
34 set
= isl_set_from_union_set(isl_union_set_copy(uset
));
35 params
= isl_set_is_params(set
);
40 static __isl_give isl_union_map
*isl_union_map_alloc(__isl_take isl_space
*dim
,
45 dim
= isl_space_params(dim
);
49 umap
= isl_calloc_type(dim
->ctx
, isl_union_map
);
55 if (isl_hash_table_init(dim
->ctx
, &umap
->table
, size
) < 0)
61 isl_union_map_free(umap
);
65 __isl_give isl_union_map
*isl_union_map_empty(__isl_take isl_space
*dim
)
67 return isl_union_map_alloc(dim
, 16);
70 __isl_give isl_union_set
*isl_union_set_empty(__isl_take isl_space
*dim
)
72 return isl_union_map_empty(dim
);
75 isl_ctx
*isl_union_map_get_ctx(__isl_keep isl_union_map
*umap
)
77 return umap
? umap
->dim
->ctx
: NULL
;
80 isl_ctx
*isl_union_set_get_ctx(__isl_keep isl_union_set
*uset
)
82 return uset
? uset
->dim
->ctx
: NULL
;
85 __isl_give isl_space
*isl_union_map_get_space(__isl_keep isl_union_map
*umap
)
89 return isl_space_copy(umap
->dim
);
92 __isl_give isl_space
*isl_union_set_get_space(__isl_keep isl_union_set
*uset
)
94 return isl_union_map_get_space(uset
);
97 static int free_umap_entry(void **entry
, void *user
)
99 isl_map
*map
= *entry
;
104 static int add_map(__isl_take isl_map
*map
, void *user
)
106 isl_union_map
**umap
= (isl_union_map
**)user
;
108 *umap
= isl_union_map_add_map(*umap
, map
);
113 __isl_give isl_union_map
*isl_union_map_dup(__isl_keep isl_union_map
*umap
)
120 dup
= isl_union_map_empty(isl_space_copy(umap
->dim
));
121 if (isl_union_map_foreach_map(umap
, &add_map
, &dup
) < 0)
125 isl_union_map_free(dup
);
129 __isl_give isl_union_map
*isl_union_map_cow(__isl_take isl_union_map
*umap
)
137 return isl_union_map_dup(umap
);
140 struct isl_union_align
{
145 static int align_entry(void **entry
, void *user
)
147 isl_map
*map
= *entry
;
149 struct isl_union_align
*data
= user
;
151 exp
= isl_reordering_extend_space(isl_reordering_copy(data
->exp
),
152 isl_map_get_space(map
));
154 data
->res
= isl_union_map_add_map(data
->res
,
155 isl_map_realign(isl_map_copy(map
), exp
));
160 /* Align the parameters of umap along those of model.
161 * The result has the parameters of model first, in the same order
162 * as they appear in model, followed by any remaining parameters of
163 * umap that do not appear in model.
165 __isl_give isl_union_map
*isl_union_map_align_params(
166 __isl_take isl_union_map
*umap
, __isl_take isl_space
*model
)
168 struct isl_union_align data
= { NULL
, NULL
};
173 if (isl_space_match(umap
->dim
, isl_dim_param
, model
, isl_dim_param
)) {
174 isl_space_free(model
);
178 model
= isl_space_params(model
);
179 data
.exp
= isl_parameter_alignment_reordering(umap
->dim
, model
);
183 data
.res
= isl_union_map_alloc(isl_space_copy(data
.exp
->dim
),
185 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
186 &align_entry
, &data
) < 0)
189 isl_reordering_free(data
.exp
);
190 isl_union_map_free(umap
);
191 isl_space_free(model
);
194 isl_reordering_free(data
.exp
);
195 isl_union_map_free(umap
);
196 isl_union_map_free(data
.res
);
197 isl_space_free(model
);
201 __isl_give isl_union_set
*isl_union_set_align_params(
202 __isl_take isl_union_set
*uset
, __isl_take isl_space
*model
)
204 return isl_union_map_align_params(uset
, model
);
207 __isl_give isl_union_map
*isl_union_map_union(__isl_take isl_union_map
*umap1
,
208 __isl_take isl_union_map
*umap2
)
210 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
211 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
213 umap1
= isl_union_map_cow(umap1
);
215 if (!umap1
|| !umap2
)
218 if (isl_union_map_foreach_map(umap2
, &add_map
, &umap1
) < 0)
221 isl_union_map_free(umap2
);
225 isl_union_map_free(umap1
);
226 isl_union_map_free(umap2
);
230 __isl_give isl_union_set
*isl_union_set_union(__isl_take isl_union_set
*uset1
,
231 __isl_take isl_union_set
*uset2
)
233 return isl_union_map_union(uset1
, uset2
);
236 __isl_give isl_union_map
*isl_union_map_copy(__isl_keep isl_union_map
*umap
)
245 __isl_give isl_union_set
*isl_union_set_copy(__isl_keep isl_union_set
*uset
)
247 return isl_union_map_copy(uset
);
250 void *isl_union_map_free(__isl_take isl_union_map
*umap
)
258 isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
259 &free_umap_entry
, NULL
);
260 isl_hash_table_clear(&umap
->table
);
261 isl_space_free(umap
->dim
);
266 void *isl_union_set_free(__isl_take isl_union_set
*uset
)
268 return isl_union_map_free(uset
);
271 static int has_dim(const void *entry
, const void *val
)
273 isl_map
*map
= (isl_map
*)entry
;
274 isl_space
*dim
= (isl_space
*)val
;
276 return isl_space_is_equal(map
->dim
, dim
);
279 __isl_give isl_union_map
*isl_union_map_add_map(__isl_take isl_union_map
*umap
,
280 __isl_take isl_map
*map
)
283 struct isl_hash_table_entry
*entry
;
288 if (isl_map_plain_is_empty(map
)) {
293 if (!isl_space_match(map
->dim
, isl_dim_param
, umap
->dim
, isl_dim_param
)) {
294 umap
= isl_union_map_align_params(umap
, isl_map_get_space(map
));
295 map
= isl_map_align_params(map
, isl_union_map_get_space(umap
));
298 umap
= isl_union_map_cow(umap
);
303 hash
= isl_space_get_hash(map
->dim
);
304 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
305 &has_dim
, map
->dim
, 1);
312 entry
->data
= isl_map_union(entry
->data
, isl_map_copy(map
));
321 isl_union_map_free(umap
);
325 __isl_give isl_union_set
*isl_union_set_add_set(__isl_take isl_union_set
*uset
,
326 __isl_take isl_set
*set
)
328 return isl_union_map_add_map(uset
, (isl_map
*)set
);
331 __isl_give isl_union_map
*isl_union_map_from_map(__isl_take isl_map
*map
)
339 dim
= isl_map_get_space(map
);
340 dim
= isl_space_params(dim
);
341 umap
= isl_union_map_empty(dim
);
342 umap
= isl_union_map_add_map(umap
, map
);
347 __isl_give isl_union_set
*isl_union_set_from_set(__isl_take isl_set
*set
)
349 return isl_union_map_from_map((isl_map
*)set
);
352 __isl_give isl_union_map
*isl_union_map_from_basic_map(
353 __isl_take isl_basic_map
*bmap
)
355 return isl_union_map_from_map(isl_map_from_basic_map(bmap
));
358 __isl_give isl_union_set
*isl_union_set_from_basic_set(
359 __isl_take isl_basic_set
*bset
)
361 return isl_union_map_from_basic_map(bset
);
364 struct isl_union_map_foreach_data
366 int (*fn
)(__isl_take isl_map
*map
, void *user
);
370 static int call_on_copy(void **entry
, void *user
)
372 isl_map
*map
= *entry
;
373 struct isl_union_map_foreach_data
*data
;
374 data
= (struct isl_union_map_foreach_data
*)user
;
376 return data
->fn(isl_map_copy(map
), data
->user
);
379 int isl_union_map_n_map(__isl_keep isl_union_map
*umap
)
381 return umap
? umap
->table
.n
: 0;
384 int isl_union_set_n_set(__isl_keep isl_union_set
*uset
)
386 return uset
? uset
->table
.n
: 0;
389 int isl_union_map_foreach_map(__isl_keep isl_union_map
*umap
,
390 int (*fn
)(__isl_take isl_map
*map
, void *user
), void *user
)
392 struct isl_union_map_foreach_data data
= { fn
, user
};
397 return isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
398 &call_on_copy
, &data
);
401 static int copy_map(void **entry
, void *user
)
403 isl_map
*map
= *entry
;
404 isl_map
**map_p
= user
;
406 *map_p
= isl_map_copy(map
);
411 __isl_give isl_map
*isl_map_from_union_map(__isl_take isl_union_map
*umap
)
418 ctx
= isl_union_map_get_ctx(umap
);
419 if (umap
->table
.n
!= 1)
420 isl_die(ctx
, isl_error_invalid
,
421 "union map needs to contain elements in exactly "
422 "one space", return isl_union_map_free(umap
));
424 isl_hash_table_foreach(ctx
, &umap
->table
, ©_map
, &map
);
426 isl_union_map_free(umap
);
431 __isl_give isl_set
*isl_set_from_union_set(__isl_take isl_union_set
*uset
)
433 return isl_map_from_union_map(uset
);
436 /* Extract the map in "umap" that lives in the given space (ignoring
439 __isl_give isl_map
*isl_union_map_extract_map(__isl_keep isl_union_map
*umap
,
440 __isl_take isl_space
*space
)
443 struct isl_hash_table_entry
*entry
;
445 space
= isl_space_drop_dims(space
, isl_dim_param
,
446 0, isl_space_dim(space
, isl_dim_param
));
447 space
= isl_space_align_params(space
, isl_union_map_get_space(umap
));
451 hash
= isl_space_get_hash(space
);
452 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
455 return isl_map_empty(space
);
456 isl_space_free(space
);
457 return isl_map_copy(entry
->data
);
459 isl_space_free(space
);
463 __isl_give isl_set
*isl_union_set_extract_set(__isl_keep isl_union_set
*uset
,
464 __isl_take isl_space
*dim
)
466 return (isl_set
*)isl_union_map_extract_map(uset
, dim
);
469 /* Check if umap contains a map in the given space.
471 __isl_give
int isl_union_map_contains(__isl_keep isl_union_map
*umap
,
472 __isl_keep isl_space
*dim
)
475 struct isl_hash_table_entry
*entry
;
480 hash
= isl_space_get_hash(dim
);
481 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
486 __isl_give
int isl_union_set_contains(__isl_keep isl_union_set
*uset
,
487 __isl_keep isl_space
*dim
)
489 return isl_union_map_contains(uset
, dim
);
492 int isl_union_set_foreach_set(__isl_keep isl_union_set
*uset
,
493 int (*fn
)(__isl_take isl_set
*set
, void *user
), void *user
)
495 return isl_union_map_foreach_map(uset
,
496 (int(*)(__isl_take isl_map
*, void*))fn
, user
);
499 struct isl_union_set_foreach_point_data
{
500 int (*fn
)(__isl_take isl_point
*pnt
, void *user
);
504 static int foreach_point(__isl_take isl_set
*set
, void *user
)
506 struct isl_union_set_foreach_point_data
*data
= user
;
509 r
= isl_set_foreach_point(set
, data
->fn
, data
->user
);
515 int isl_union_set_foreach_point(__isl_keep isl_union_set
*uset
,
516 int (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
518 struct isl_union_set_foreach_point_data data
= { fn
, user
};
519 return isl_union_set_foreach_set(uset
, &foreach_point
, &data
);
522 struct isl_union_map_gen_bin_data
{
523 isl_union_map
*umap2
;
527 static int subtract_entry(void **entry
, void *user
)
529 struct isl_union_map_gen_bin_data
*data
= user
;
531 struct isl_hash_table_entry
*entry2
;
532 isl_map
*map
= *entry
;
534 hash
= isl_space_get_hash(map
->dim
);
535 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
536 hash
, &has_dim
, map
->dim
, 0);
537 map
= isl_map_copy(map
);
540 map
= isl_map_subtract(map
, isl_map_copy(entry2
->data
));
542 empty
= isl_map_is_empty(map
);
552 data
->res
= isl_union_map_add_map(data
->res
, map
);
557 static __isl_give isl_union_map
*gen_bin_op(__isl_take isl_union_map
*umap1
,
558 __isl_take isl_union_map
*umap2
, int (*fn
)(void **, void *))
560 struct isl_union_map_gen_bin_data data
= { NULL
, NULL
};
562 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
563 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
565 if (!umap1
|| !umap2
)
569 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
571 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
575 isl_union_map_free(umap1
);
576 isl_union_map_free(umap2
);
579 isl_union_map_free(umap1
);
580 isl_union_map_free(umap2
);
581 isl_union_map_free(data
.res
);
585 __isl_give isl_union_map
*isl_union_map_subtract(
586 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
588 return gen_bin_op(umap1
, umap2
, &subtract_entry
);
591 __isl_give isl_union_set
*isl_union_set_subtract(
592 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
594 return isl_union_map_subtract(uset1
, uset2
);
597 struct isl_union_map_gen_bin_set_data
{
602 static int intersect_params_entry(void **entry
, void *user
)
604 struct isl_union_map_gen_bin_set_data
*data
= user
;
605 isl_map
*map
= *entry
;
608 map
= isl_map_copy(map
);
609 map
= isl_map_intersect_params(map
, isl_set_copy(data
->set
));
611 empty
= isl_map_is_empty(map
);
617 data
->res
= isl_union_map_add_map(data
->res
, map
);
622 static __isl_give isl_union_map
*gen_bin_set_op(__isl_take isl_union_map
*umap
,
623 __isl_take isl_set
*set
, int (*fn
)(void **, void *))
625 struct isl_union_map_gen_bin_set_data data
= { NULL
, NULL
};
627 umap
= isl_union_map_align_params(umap
, isl_set_get_space(set
));
628 set
= isl_set_align_params(set
, isl_union_map_get_space(umap
));
634 data
.res
= isl_union_map_alloc(isl_space_copy(umap
->dim
),
636 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
640 isl_union_map_free(umap
);
644 isl_union_map_free(umap
);
646 isl_union_map_free(data
.res
);
650 __isl_give isl_union_map
*isl_union_map_intersect_params(
651 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
653 return gen_bin_set_op(umap
, set
, &intersect_params_entry
);
656 __isl_give isl_union_set
*isl_union_set_intersect_params(
657 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
659 return isl_union_map_intersect_params(uset
, set
);
662 static __isl_give isl_union_map
*union_map_intersect_params(
663 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
665 return isl_union_map_intersect_params(umap
,
666 isl_set_from_union_set(uset
));
669 static __isl_give isl_union_map
*union_map_gist_params(
670 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
672 return isl_union_map_gist_params(umap
, isl_set_from_union_set(uset
));
675 struct isl_union_map_match_bin_data
{
676 isl_union_map
*umap2
;
678 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*);
681 static int match_bin_entry(void **entry
, void *user
)
683 struct isl_union_map_match_bin_data
*data
= user
;
685 struct isl_hash_table_entry
*entry2
;
686 isl_map
*map
= *entry
;
689 hash
= isl_space_get_hash(map
->dim
);
690 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
691 hash
, &has_dim
, map
->dim
, 0);
695 map
= isl_map_copy(map
);
696 map
= data
->fn(map
, isl_map_copy(entry2
->data
));
698 empty
= isl_map_is_empty(map
);
708 data
->res
= isl_union_map_add_map(data
->res
, map
);
713 static __isl_give isl_union_map
*match_bin_op(__isl_take isl_union_map
*umap1
,
714 __isl_take isl_union_map
*umap2
,
715 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*))
717 struct isl_union_map_match_bin_data data
= { NULL
, NULL
, fn
};
719 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
720 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
722 if (!umap1
|| !umap2
)
726 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
728 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
729 &match_bin_entry
, &data
) < 0)
732 isl_union_map_free(umap1
);
733 isl_union_map_free(umap2
);
736 isl_union_map_free(umap1
);
737 isl_union_map_free(umap2
);
738 isl_union_map_free(data
.res
);
742 __isl_give isl_union_map
*isl_union_map_intersect(
743 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
745 return match_bin_op(umap1
, umap2
, &isl_map_intersect
);
748 /* Compute the intersection of the two union_sets.
749 * As a special case, if exactly one of the two union_sets
750 * is a parameter domain, then intersect the parameter domain
751 * of the other one with this set.
753 __isl_give isl_union_set
*isl_union_set_intersect(
754 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
758 p1
= isl_union_set_is_params(uset1
);
759 p2
= isl_union_set_is_params(uset2
);
760 if (p1
< 0 || p2
< 0)
763 return union_map_intersect_params(uset1
, uset2
);
765 return union_map_intersect_params(uset2
, uset1
);
766 return isl_union_map_intersect(uset1
, uset2
);
768 isl_union_set_free(uset1
);
769 isl_union_set_free(uset2
);
773 static int gist_params_entry(void **entry
, void *user
)
775 struct isl_union_map_gen_bin_set_data
*data
= user
;
776 isl_map
*map
= *entry
;
779 map
= isl_map_copy(map
);
780 map
= isl_map_gist_params(map
, isl_set_copy(data
->set
));
782 empty
= isl_map_is_empty(map
);
788 data
->res
= isl_union_map_add_map(data
->res
, map
);
793 __isl_give isl_union_map
*isl_union_map_gist_params(
794 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
796 return gen_bin_set_op(umap
, set
, &gist_params_entry
);
799 __isl_give isl_union_set
*isl_union_set_gist_params(
800 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
802 return isl_union_map_gist_params(uset
, set
);
805 __isl_give isl_union_map
*isl_union_map_gist(__isl_take isl_union_map
*umap
,
806 __isl_take isl_union_map
*context
)
808 return match_bin_op(umap
, context
, &isl_map_gist
);
811 __isl_give isl_union_set
*isl_union_set_gist(__isl_take isl_union_set
*uset
,
812 __isl_take isl_union_set
*context
)
814 if (isl_union_set_is_params(context
))
815 return union_map_gist_params(uset
, context
);
816 return isl_union_map_gist(uset
, context
);
819 static __isl_give isl_map
*lex_le_set(__isl_take isl_map
*set1
,
820 __isl_take isl_map
*set2
)
822 return isl_set_lex_le_set((isl_set
*)set1
, (isl_set
*)set2
);
825 static __isl_give isl_map
*lex_lt_set(__isl_take isl_map
*set1
,
826 __isl_take isl_map
*set2
)
828 return isl_set_lex_lt_set((isl_set
*)set1
, (isl_set
*)set2
);
831 __isl_give isl_union_map
*isl_union_set_lex_lt_union_set(
832 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
834 return match_bin_op(uset1
, uset2
, &lex_lt_set
);
837 __isl_give isl_union_map
*isl_union_set_lex_le_union_set(
838 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
840 return match_bin_op(uset1
, uset2
, &lex_le_set
);
843 __isl_give isl_union_map
*isl_union_set_lex_gt_union_set(
844 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
846 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2
, uset1
));
849 __isl_give isl_union_map
*isl_union_set_lex_ge_union_set(
850 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
852 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2
, uset1
));
855 __isl_give isl_union_map
*isl_union_map_lex_gt_union_map(
856 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
858 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2
, umap1
));
861 __isl_give isl_union_map
*isl_union_map_lex_ge_union_map(
862 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
864 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2
, umap1
));
867 static int intersect_domain_entry(void **entry
, void *user
)
869 struct isl_union_map_gen_bin_data
*data
= user
;
871 struct isl_hash_table_entry
*entry2
;
873 isl_map
*map
= *entry
;
876 dim
= isl_map_get_space(map
);
877 dim
= isl_space_domain(dim
);
878 hash
= isl_space_get_hash(dim
);
879 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
880 hash
, &has_dim
, dim
, 0);
885 map
= isl_map_copy(map
);
886 map
= isl_map_intersect_domain(map
, isl_set_copy(entry2
->data
));
888 empty
= isl_map_is_empty(map
);
898 data
->res
= isl_union_map_add_map(data
->res
, map
);
903 /* Intersect the domain of "umap" with "uset".
904 * If "uset" is a parameters domain, then intersect the parameter
905 * domain of "umap" with this set.
907 __isl_give isl_union_map
*isl_union_map_intersect_domain(
908 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
910 if (isl_union_set_is_params(uset
))
911 return union_map_intersect_params(umap
, uset
);
912 return gen_bin_op(umap
, uset
, &intersect_domain_entry
);
915 /* Remove the elements of data->umap2 from the domain of *entry
916 * and add the result to data->res.
918 static int subtract_domain_entry(void **entry
, void *user
)
920 struct isl_union_map_gen_bin_data
*data
= user
;
922 struct isl_hash_table_entry
*entry2
;
924 isl_map
*map
= *entry
;
927 dim
= isl_map_get_space(map
);
928 dim
= isl_space_domain(dim
);
929 hash
= isl_space_get_hash(dim
);
930 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
931 hash
, &has_dim
, dim
, 0);
934 map
= isl_map_copy(map
);
937 data
->res
= isl_union_map_add_map(data
->res
, map
);
941 map
= isl_map_subtract_domain(map
, isl_set_copy(entry2
->data
));
943 empty
= isl_map_is_empty(map
);
953 data
->res
= isl_union_map_add_map(data
->res
, map
);
958 /* Remove the elements of "uset" from the domain of "umap".
960 __isl_give isl_union_map
*isl_union_map_subtract_domain(
961 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
963 return gen_bin_op(umap
, dom
, &subtract_domain_entry
);
966 /* Remove the elements of data->umap2 from the range of *entry
967 * and add the result to data->res.
969 static int subtract_range_entry(void **entry
, void *user
)
971 struct isl_union_map_gen_bin_data
*data
= user
;
973 struct isl_hash_table_entry
*entry2
;
975 isl_map
*map
= *entry
;
978 space
= isl_map_get_space(map
);
979 space
= isl_space_range(space
);
980 hash
= isl_space_get_hash(space
);
981 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
982 hash
, &has_dim
, space
, 0);
983 isl_space_free(space
);
985 map
= isl_map_copy(map
);
988 data
->res
= isl_union_map_add_map(data
->res
, map
);
992 map
= isl_map_subtract_range(map
, isl_set_copy(entry2
->data
));
994 empty
= isl_map_is_empty(map
);
1004 data
->res
= isl_union_map_add_map(data
->res
, map
);
1009 /* Remove the elements of "uset" from the range of "umap".
1011 __isl_give isl_union_map
*isl_union_map_subtract_range(
1012 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
1014 return gen_bin_op(umap
, dom
, &subtract_range_entry
);
1017 static int gist_domain_entry(void **entry
, void *user
)
1019 struct isl_union_map_gen_bin_data
*data
= user
;
1021 struct isl_hash_table_entry
*entry2
;
1023 isl_map
*map
= *entry
;
1026 dim
= isl_map_get_space(map
);
1027 dim
= isl_space_domain(dim
);
1028 hash
= isl_space_get_hash(dim
);
1029 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1030 hash
, &has_dim
, dim
, 0);
1031 isl_space_free(dim
);
1035 map
= isl_map_copy(map
);
1036 map
= isl_map_gist_domain(map
, isl_set_copy(entry2
->data
));
1038 empty
= isl_map_is_empty(map
);
1044 data
->res
= isl_union_map_add_map(data
->res
, map
);
1049 /* Compute the gist of "umap" with respect to the domain "uset".
1050 * If "uset" is a parameters domain, then compute the gist
1051 * with respect to this parameter domain.
1053 __isl_give isl_union_map
*isl_union_map_gist_domain(
1054 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1056 if (isl_union_set_is_params(uset
))
1057 return union_map_gist_params(umap
, uset
);
1058 return gen_bin_op(umap
, uset
, &gist_domain_entry
);
1061 static int gist_range_entry(void **entry
, void *user
)
1063 struct isl_union_map_gen_bin_data
*data
= user
;
1065 struct isl_hash_table_entry
*entry2
;
1067 isl_map
*map
= *entry
;
1070 space
= isl_map_get_space(map
);
1071 space
= isl_space_range(space
);
1072 hash
= isl_space_get_hash(space
);
1073 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1074 hash
, &has_dim
, space
, 0);
1075 isl_space_free(space
);
1079 map
= isl_map_copy(map
);
1080 map
= isl_map_gist_range(map
, isl_set_copy(entry2
->data
));
1082 empty
= isl_map_is_empty(map
);
1088 data
->res
= isl_union_map_add_map(data
->res
, map
);
1093 /* Compute the gist of "umap" with respect to the range "uset".
1095 __isl_give isl_union_map
*isl_union_map_gist_range(
1096 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1098 return gen_bin_op(umap
, uset
, &gist_range_entry
);
1101 static int intersect_range_entry(void **entry
, void *user
)
1103 struct isl_union_map_gen_bin_data
*data
= user
;
1105 struct isl_hash_table_entry
*entry2
;
1107 isl_map
*map
= *entry
;
1110 dim
= isl_map_get_space(map
);
1111 dim
= isl_space_range(dim
);
1112 hash
= isl_space_get_hash(dim
);
1113 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1114 hash
, &has_dim
, dim
, 0);
1115 isl_space_free(dim
);
1119 map
= isl_map_copy(map
);
1120 map
= isl_map_intersect_range(map
, isl_set_copy(entry2
->data
));
1122 empty
= isl_map_is_empty(map
);
1132 data
->res
= isl_union_map_add_map(data
->res
, map
);
1137 __isl_give isl_union_map
*isl_union_map_intersect_range(
1138 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1140 return gen_bin_op(umap
, uset
, &intersect_range_entry
);
1143 struct isl_union_map_bin_data
{
1144 isl_union_map
*umap2
;
1147 int (*fn
)(void **entry
, void *user
);
1150 static int apply_range_entry(void **entry
, void *user
)
1152 struct isl_union_map_bin_data
*data
= user
;
1153 isl_map
*map2
= *entry
;
1156 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1157 map2
->dim
, isl_dim_in
))
1160 map2
= isl_map_apply_range(isl_map_copy(data
->map
), isl_map_copy(map2
));
1162 empty
= isl_map_is_empty(map2
);
1172 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1177 static int bin_entry(void **entry
, void *user
)
1179 struct isl_union_map_bin_data
*data
= user
;
1180 isl_map
*map
= *entry
;
1183 if (isl_hash_table_foreach(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1184 data
->fn
, data
) < 0)
1190 static __isl_give isl_union_map
*bin_op(__isl_take isl_union_map
*umap1
,
1191 __isl_take isl_union_map
*umap2
, int (*fn
)(void **entry
, void *user
))
1193 struct isl_union_map_bin_data data
= { NULL
, NULL
, NULL
, fn
};
1195 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1196 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1198 if (!umap1
|| !umap2
)
1202 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
1204 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1205 &bin_entry
, &data
) < 0)
1208 isl_union_map_free(umap1
);
1209 isl_union_map_free(umap2
);
1212 isl_union_map_free(umap1
);
1213 isl_union_map_free(umap2
);
1214 isl_union_map_free(data
.res
);
1218 __isl_give isl_union_map
*isl_union_map_apply_range(
1219 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1221 return bin_op(umap1
, umap2
, &apply_range_entry
);
1224 __isl_give isl_union_map
*isl_union_map_apply_domain(
1225 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1227 umap1
= isl_union_map_reverse(umap1
);
1228 umap1
= isl_union_map_apply_range(umap1
, umap2
);
1229 return isl_union_map_reverse(umap1
);
1232 __isl_give isl_union_set
*isl_union_set_apply(
1233 __isl_take isl_union_set
*uset
, __isl_take isl_union_map
*umap
)
1235 return isl_union_map_apply_range(uset
, umap
);
1238 static int map_lex_lt_entry(void **entry
, void *user
)
1240 struct isl_union_map_bin_data
*data
= user
;
1241 isl_map
*map2
= *entry
;
1243 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1244 map2
->dim
, isl_dim_out
))
1247 map2
= isl_map_lex_lt_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1249 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1254 __isl_give isl_union_map
*isl_union_map_lex_lt_union_map(
1255 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1257 return bin_op(umap1
, umap2
, &map_lex_lt_entry
);
1260 static int map_lex_le_entry(void **entry
, void *user
)
1262 struct isl_union_map_bin_data
*data
= user
;
1263 isl_map
*map2
= *entry
;
1265 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1266 map2
->dim
, isl_dim_out
))
1269 map2
= isl_map_lex_le_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1271 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1276 __isl_give isl_union_map
*isl_union_map_lex_le_union_map(
1277 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1279 return bin_op(umap1
, umap2
, &map_lex_le_entry
);
1282 static int product_entry(void **entry
, void *user
)
1284 struct isl_union_map_bin_data
*data
= user
;
1285 isl_map
*map2
= *entry
;
1287 map2
= isl_map_product(isl_map_copy(data
->map
), isl_map_copy(map2
));
1289 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1294 __isl_give isl_union_map
*isl_union_map_product(__isl_take isl_union_map
*umap1
,
1295 __isl_take isl_union_map
*umap2
)
1297 return bin_op(umap1
, umap2
, &product_entry
);
1300 static int set_product_entry(void **entry
, void *user
)
1302 struct isl_union_map_bin_data
*data
= user
;
1303 isl_set
*set2
= *entry
;
1305 set2
= isl_set_product(isl_set_copy(data
->map
), isl_set_copy(set2
));
1307 data
->res
= isl_union_set_add_set(data
->res
, set2
);
1312 __isl_give isl_union_set
*isl_union_set_product(__isl_take isl_union_set
*uset1
,
1313 __isl_take isl_union_set
*uset2
)
1315 return bin_op(uset1
, uset2
, &set_product_entry
);
1318 static int domain_product_entry(void **entry
, void *user
)
1320 struct isl_union_map_bin_data
*data
= user
;
1321 isl_map
*map2
= *entry
;
1323 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1324 map2
->dim
, isl_dim_out
))
1327 map2
= isl_map_domain_product(isl_map_copy(data
->map
),
1328 isl_map_copy(map2
));
1330 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1335 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1337 __isl_give isl_union_map
*isl_union_map_domain_product(
1338 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1340 return bin_op(umap1
, umap2
, &domain_product_entry
);
1343 static int range_product_entry(void **entry
, void *user
)
1345 struct isl_union_map_bin_data
*data
= user
;
1346 isl_map
*map2
= *entry
;
1348 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1349 map2
->dim
, isl_dim_in
))
1352 map2
= isl_map_range_product(isl_map_copy(data
->map
),
1353 isl_map_copy(map2
));
1355 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1360 __isl_give isl_union_map
*isl_union_map_range_product(
1361 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1363 return bin_op(umap1
, umap2
, &range_product_entry
);
1366 static int flat_range_product_entry(void **entry
, void *user
)
1368 struct isl_union_map_bin_data
*data
= user
;
1369 isl_map
*map2
= *entry
;
1371 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1372 map2
->dim
, isl_dim_in
))
1375 map2
= isl_map_flat_range_product(isl_map_copy(data
->map
),
1376 isl_map_copy(map2
));
1378 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1383 __isl_give isl_union_map
*isl_union_map_flat_range_product(
1384 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1386 return bin_op(umap1
, umap2
, &flat_range_product_entry
);
1389 static __isl_give isl_union_set
*cond_un_op(__isl_take isl_union_map
*umap
,
1390 int (*fn
)(void **, void *))
1397 res
= isl_union_map_alloc(isl_space_copy(umap
->dim
), umap
->table
.n
);
1398 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, &res
) < 0)
1401 isl_union_map_free(umap
);
1404 isl_union_map_free(umap
);
1405 isl_union_set_free(res
);
1409 static int from_range_entry(void **entry
, void *user
)
1411 isl_map
*set
= *entry
;
1412 isl_union_set
**res
= user
;
1414 *res
= isl_union_map_add_map(*res
,
1415 isl_map_from_range(isl_set_copy(set
)));
1420 __isl_give isl_union_map
*isl_union_map_from_range(
1421 __isl_take isl_union_set
*uset
)
1423 return cond_un_op(uset
, &from_range_entry
);
1426 __isl_give isl_union_map
*isl_union_map_from_domain(
1427 __isl_take isl_union_set
*uset
)
1429 return isl_union_map_reverse(isl_union_map_from_range(uset
));
1432 __isl_give isl_union_map
*isl_union_map_from_domain_and_range(
1433 __isl_take isl_union_set
*domain
, __isl_take isl_union_set
*range
)
1435 return isl_union_map_apply_range(isl_union_map_from_domain(domain
),
1436 isl_union_map_from_range(range
));
1439 static __isl_give isl_union_map
*un_op(__isl_take isl_union_map
*umap
,
1440 int (*fn
)(void **, void *))
1442 umap
= isl_union_map_cow(umap
);
1446 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, NULL
) < 0)
1451 isl_union_map_free(umap
);
1455 static int affine_entry(void **entry
, void *user
)
1457 isl_map
**map
= (isl_map
**)entry
;
1459 *map
= isl_map_from_basic_map(isl_map_affine_hull(*map
));
1461 return *map
? 0 : -1;
1464 __isl_give isl_union_map
*isl_union_map_affine_hull(
1465 __isl_take isl_union_map
*umap
)
1467 return un_op(umap
, &affine_entry
);
1470 __isl_give isl_union_set
*isl_union_set_affine_hull(
1471 __isl_take isl_union_set
*uset
)
1473 return isl_union_map_affine_hull(uset
);
1476 static int polyhedral_entry(void **entry
, void *user
)
1478 isl_map
**map
= (isl_map
**)entry
;
1480 *map
= isl_map_from_basic_map(isl_map_polyhedral_hull(*map
));
1482 return *map
? 0 : -1;
1485 __isl_give isl_union_map
*isl_union_map_polyhedral_hull(
1486 __isl_take isl_union_map
*umap
)
1488 return un_op(umap
, &polyhedral_entry
);
1491 __isl_give isl_union_set
*isl_union_set_polyhedral_hull(
1492 __isl_take isl_union_set
*uset
)
1494 return isl_union_map_polyhedral_hull(uset
);
1497 static int simple_entry(void **entry
, void *user
)
1499 isl_map
**map
= (isl_map
**)entry
;
1501 *map
= isl_map_from_basic_map(isl_map_simple_hull(*map
));
1503 return *map
? 0 : -1;
1506 __isl_give isl_union_map
*isl_union_map_simple_hull(
1507 __isl_take isl_union_map
*umap
)
1509 return un_op(umap
, &simple_entry
);
1512 __isl_give isl_union_set
*isl_union_set_simple_hull(
1513 __isl_take isl_union_set
*uset
)
1515 return isl_union_map_simple_hull(uset
);
1518 static int inplace_entry(void **entry
, void *user
)
1520 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*);
1521 isl_map
**map
= (isl_map
**)entry
;
1524 fn
= *(__isl_give isl_map
*(**)(__isl_take isl_map
*)) user
;
1525 copy
= fn(isl_map_copy(*map
));
1535 static __isl_give isl_union_map
*inplace(__isl_take isl_union_map
*umap
,
1536 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*))
1541 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1542 &inplace_entry
, &fn
) < 0)
1547 isl_union_map_free(umap
);
1551 __isl_give isl_union_map
*isl_union_map_coalesce(
1552 __isl_take isl_union_map
*umap
)
1554 return inplace(umap
, &isl_map_coalesce
);
1557 __isl_give isl_union_set
*isl_union_set_coalesce(
1558 __isl_take isl_union_set
*uset
)
1560 return isl_union_map_coalesce(uset
);
1563 __isl_give isl_union_map
*isl_union_map_detect_equalities(
1564 __isl_take isl_union_map
*umap
)
1566 return inplace(umap
, &isl_map_detect_equalities
);
1569 __isl_give isl_union_set
*isl_union_set_detect_equalities(
1570 __isl_take isl_union_set
*uset
)
1572 return isl_union_map_detect_equalities(uset
);
1575 __isl_give isl_union_map
*isl_union_map_compute_divs(
1576 __isl_take isl_union_map
*umap
)
1578 return inplace(umap
, &isl_map_compute_divs
);
1581 __isl_give isl_union_set
*isl_union_set_compute_divs(
1582 __isl_take isl_union_set
*uset
)
1584 return isl_union_map_compute_divs(uset
);
1587 static int lexmin_entry(void **entry
, void *user
)
1589 isl_map
**map
= (isl_map
**)entry
;
1591 *map
= isl_map_lexmin(*map
);
1593 return *map
? 0 : -1;
1596 __isl_give isl_union_map
*isl_union_map_lexmin(
1597 __isl_take isl_union_map
*umap
)
1599 return un_op(umap
, &lexmin_entry
);
1602 __isl_give isl_union_set
*isl_union_set_lexmin(
1603 __isl_take isl_union_set
*uset
)
1605 return isl_union_map_lexmin(uset
);
1608 static int lexmax_entry(void **entry
, void *user
)
1610 isl_map
**map
= (isl_map
**)entry
;
1612 *map
= isl_map_lexmax(*map
);
1614 return *map
? 0 : -1;
1617 __isl_give isl_union_map
*isl_union_map_lexmax(
1618 __isl_take isl_union_map
*umap
)
1620 return un_op(umap
, &lexmax_entry
);
1623 __isl_give isl_union_set
*isl_union_set_lexmax(
1624 __isl_take isl_union_set
*uset
)
1626 return isl_union_map_lexmax(uset
);
1629 static int universe_entry(void **entry
, void *user
)
1631 isl_map
*map
= *entry
;
1632 isl_union_map
**res
= user
;
1634 map
= isl_map_universe(isl_map_get_space(map
));
1635 *res
= isl_union_map_add_map(*res
, map
);
1640 __isl_give isl_union_map
*isl_union_map_universe(__isl_take isl_union_map
*umap
)
1642 return cond_un_op(umap
, &universe_entry
);
1645 __isl_give isl_union_set
*isl_union_set_universe(__isl_take isl_union_set
*uset
)
1647 return isl_union_map_universe(uset
);
1650 static int reverse_entry(void **entry
, void *user
)
1652 isl_map
*map
= *entry
;
1653 isl_union_map
**res
= user
;
1655 *res
= isl_union_map_add_map(*res
, isl_map_reverse(isl_map_copy(map
)));
1660 __isl_give isl_union_map
*isl_union_map_reverse(__isl_take isl_union_map
*umap
)
1662 return cond_un_op(umap
, &reverse_entry
);
1665 static int params_entry(void **entry
, void *user
)
1667 isl_map
*map
= *entry
;
1668 isl_union_set
**res
= user
;
1670 *res
= isl_union_set_add_set(*res
, isl_map_params(isl_map_copy(map
)));
1675 /* Compute the parameter domain of the given union map.
1677 __isl_give isl_set
*isl_union_map_params(__isl_take isl_union_map
*umap
)
1681 empty
= isl_union_map_is_empty(umap
);
1683 return isl_union_map_free(umap
);
1685 return isl_set_empty(isl_union_map_get_space(umap
));
1686 return isl_set_from_union_set(cond_un_op(umap
, ¶ms_entry
));
1689 /* Compute the parameter domain of the given union set.
1691 __isl_give isl_set
*isl_union_set_params(__isl_take isl_union_set
*uset
)
1693 return isl_union_map_params(uset
);
1696 static int domain_entry(void **entry
, void *user
)
1698 isl_map
*map
= *entry
;
1699 isl_union_set
**res
= user
;
1701 *res
= isl_union_set_add_set(*res
, isl_map_domain(isl_map_copy(map
)));
1706 __isl_give isl_union_set
*isl_union_map_domain(__isl_take isl_union_map
*umap
)
1708 return cond_un_op(umap
, &domain_entry
);
1711 static int range_entry(void **entry
, void *user
)
1713 isl_map
*map
= *entry
;
1714 isl_union_set
**res
= user
;
1716 *res
= isl_union_set_add_set(*res
, isl_map_range(isl_map_copy(map
)));
1721 __isl_give isl_union_set
*isl_union_map_range(__isl_take isl_union_map
*umap
)
1723 return cond_un_op(umap
, &range_entry
);
1726 static int domain_map_entry(void **entry
, void *user
)
1728 isl_map
*map
= *entry
;
1729 isl_union_set
**res
= user
;
1731 *res
= isl_union_map_add_map(*res
,
1732 isl_map_domain_map(isl_map_copy(map
)));
1737 __isl_give isl_union_map
*isl_union_map_domain_map(
1738 __isl_take isl_union_map
*umap
)
1740 return cond_un_op(umap
, &domain_map_entry
);
1743 static int range_map_entry(void **entry
, void *user
)
1745 isl_map
*map
= *entry
;
1746 isl_union_set
**res
= user
;
1748 *res
= isl_union_map_add_map(*res
,
1749 isl_map_range_map(isl_map_copy(map
)));
1754 __isl_give isl_union_map
*isl_union_map_range_map(
1755 __isl_take isl_union_map
*umap
)
1757 return cond_un_op(umap
, &range_map_entry
);
1760 static int deltas_entry(void **entry
, void *user
)
1762 isl_map
*map
= *entry
;
1763 isl_union_set
**res
= user
;
1765 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1768 *res
= isl_union_set_add_set(*res
, isl_map_deltas(isl_map_copy(map
)));
1773 __isl_give isl_union_set
*isl_union_map_deltas(__isl_take isl_union_map
*umap
)
1775 return cond_un_op(umap
, &deltas_entry
);
1778 static int deltas_map_entry(void **entry
, void *user
)
1780 isl_map
*map
= *entry
;
1781 isl_union_map
**res
= user
;
1783 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1786 *res
= isl_union_map_add_map(*res
,
1787 isl_map_deltas_map(isl_map_copy(map
)));
1792 __isl_give isl_union_map
*isl_union_map_deltas_map(
1793 __isl_take isl_union_map
*umap
)
1795 return cond_un_op(umap
, &deltas_map_entry
);
1798 static int identity_entry(void **entry
, void *user
)
1800 isl_set
*set
= *entry
;
1801 isl_union_map
**res
= user
;
1803 *res
= isl_union_map_add_map(*res
, isl_set_identity(isl_set_copy(set
)));
1808 __isl_give isl_union_map
*isl_union_set_identity(__isl_take isl_union_set
*uset
)
1810 return cond_un_op(uset
, &identity_entry
);
1813 static int unwrap_entry(void **entry
, void *user
)
1815 isl_set
*set
= *entry
;
1816 isl_union_set
**res
= user
;
1818 if (!isl_set_is_wrapping(set
))
1821 *res
= isl_union_map_add_map(*res
, isl_set_unwrap(isl_set_copy(set
)));
1826 __isl_give isl_union_map
*isl_union_set_unwrap(__isl_take isl_union_set
*uset
)
1828 return cond_un_op(uset
, &unwrap_entry
);
1831 static int wrap_entry(void **entry
, void *user
)
1833 isl_map
*map
= *entry
;
1834 isl_union_set
**res
= user
;
1836 *res
= isl_union_set_add_set(*res
, isl_map_wrap(isl_map_copy(map
)));
1841 __isl_give isl_union_set
*isl_union_map_wrap(__isl_take isl_union_map
*umap
)
1843 return cond_un_op(umap
, &wrap_entry
);
1846 struct isl_union_map_is_subset_data
{
1847 isl_union_map
*umap2
;
1851 static int is_subset_entry(void **entry
, void *user
)
1853 struct isl_union_map_is_subset_data
*data
= user
;
1855 struct isl_hash_table_entry
*entry2
;
1856 isl_map
*map
= *entry
;
1858 hash
= isl_space_get_hash(map
->dim
);
1859 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1860 hash
, &has_dim
, map
->dim
, 0);
1862 int empty
= isl_map_is_empty(map
);
1867 data
->is_subset
= 0;
1871 data
->is_subset
= isl_map_is_subset(map
, entry2
->data
);
1872 if (data
->is_subset
< 0 || !data
->is_subset
)
1878 int isl_union_map_is_subset(__isl_keep isl_union_map
*umap1
,
1879 __isl_keep isl_union_map
*umap2
)
1881 struct isl_union_map_is_subset_data data
= { NULL
, 1 };
1883 umap1
= isl_union_map_copy(umap1
);
1884 umap2
= isl_union_map_copy(umap2
);
1885 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1886 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1888 if (!umap1
|| !umap2
)
1892 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1893 &is_subset_entry
, &data
) < 0 &&
1897 isl_union_map_free(umap1
);
1898 isl_union_map_free(umap2
);
1900 return data
.is_subset
;
1902 isl_union_map_free(umap1
);
1903 isl_union_map_free(umap2
);
1907 int isl_union_set_is_subset(__isl_keep isl_union_set
*uset1
,
1908 __isl_keep isl_union_set
*uset2
)
1910 return isl_union_map_is_subset(uset1
, uset2
);
1913 int isl_union_map_is_equal(__isl_keep isl_union_map
*umap1
,
1914 __isl_keep isl_union_map
*umap2
)
1918 if (!umap1
|| !umap2
)
1920 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1923 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1927 int isl_union_set_is_equal(__isl_keep isl_union_set
*uset1
,
1928 __isl_keep isl_union_set
*uset2
)
1930 return isl_union_map_is_equal(uset1
, uset2
);
1933 int isl_union_map_is_strict_subset(__isl_keep isl_union_map
*umap1
,
1934 __isl_keep isl_union_map
*umap2
)
1938 if (!umap1
|| !umap2
)
1940 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1943 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1944 if (is_subset
== -1)
1949 int isl_union_set_is_strict_subset(__isl_keep isl_union_set
*uset1
,
1950 __isl_keep isl_union_set
*uset2
)
1952 return isl_union_map_is_strict_subset(uset1
, uset2
);
1955 static int sample_entry(void **entry
, void *user
)
1957 isl_basic_map
**sample
= (isl_basic_map
**)user
;
1958 isl_map
*map
= *entry
;
1960 *sample
= isl_map_sample(isl_map_copy(map
));
1963 if (!isl_basic_map_plain_is_empty(*sample
))
1968 __isl_give isl_basic_map
*isl_union_map_sample(__isl_take isl_union_map
*umap
)
1970 isl_basic_map
*sample
= NULL
;
1975 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1976 &sample_entry
, &sample
) < 0 &&
1981 sample
= isl_basic_map_empty(isl_union_map_get_space(umap
));
1983 isl_union_map_free(umap
);
1987 isl_union_map_free(umap
);
1991 __isl_give isl_basic_set
*isl_union_set_sample(__isl_take isl_union_set
*uset
)
1993 return (isl_basic_set
*)isl_union_map_sample(uset
);
1996 struct isl_forall_data
{
1998 int (*fn
)(__isl_keep isl_map
*map
);
2001 static int forall_entry(void **entry
, void *user
)
2003 struct isl_forall_data
*data
= user
;
2004 isl_map
*map
= *entry
;
2006 data
->res
= data
->fn(map
);
2016 static int union_map_forall(__isl_keep isl_union_map
*umap
,
2017 int (*fn
)(__isl_keep isl_map
*map
))
2019 struct isl_forall_data data
= { 1, fn
};
2024 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2025 &forall_entry
, &data
) < 0 && data
.res
)
2031 struct isl_forall_user_data
{
2033 int (*fn
)(__isl_keep isl_map
*map
, void *user
);
2037 static int forall_user_entry(void **entry
, void *user
)
2039 struct isl_forall_user_data
*data
= user
;
2040 isl_map
*map
= *entry
;
2042 data
->res
= data
->fn(map
, data
->user
);
2052 /* Check if fn(map, user) returns true for all maps "map" in umap.
2054 static int union_map_forall_user(__isl_keep isl_union_map
*umap
,
2055 int (*fn
)(__isl_keep isl_map
*map
, void *user
), void *user
)
2057 struct isl_forall_user_data data
= { 1, fn
, user
};
2062 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2063 &forall_user_entry
, &data
) < 0 && data
.res
)
2069 int isl_union_map_is_empty(__isl_keep isl_union_map
*umap
)
2071 return union_map_forall(umap
, &isl_map_is_empty
);
2074 int isl_union_set_is_empty(__isl_keep isl_union_set
*uset
)
2076 return isl_union_map_is_empty(uset
);
2079 static int is_subset_of_identity(__isl_keep isl_map
*map
)
2088 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
2091 dim
= isl_map_get_space(map
);
2092 id
= isl_map_identity(dim
);
2094 is_subset
= isl_map_is_subset(map
, id
);
2101 /* Check if the given map is single-valued.
2106 * and check if the result is a subset of the identity mapping.
2108 int isl_union_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2110 isl_union_map
*test
;
2113 if (isl_union_map_n_map(umap
) == 1) {
2115 umap
= isl_union_map_copy(umap
);
2116 map
= isl_map_from_union_map(umap
);
2117 sv
= isl_map_is_single_valued(map
);
2122 test
= isl_union_map_reverse(isl_union_map_copy(umap
));
2123 test
= isl_union_map_apply_range(test
, isl_union_map_copy(umap
));
2125 sv
= union_map_forall(test
, &is_subset_of_identity
);
2127 isl_union_map_free(test
);
2132 int isl_union_map_is_injective(__isl_keep isl_union_map
*umap
)
2136 umap
= isl_union_map_copy(umap
);
2137 umap
= isl_union_map_reverse(umap
);
2138 in
= isl_union_map_is_single_valued(umap
);
2139 isl_union_map_free(umap
);
2144 /* Represents a map that has a fixed value (v) for one of its
2146 * The map in this structure is not reference counted, so it
2147 * is only valid while the isl_union_map from which it was
2148 * obtained is still alive.
2150 struct isl_fixed_map
{
2155 static struct isl_fixed_map
*alloc_isl_fixed_map_array(isl_ctx
*ctx
,
2159 struct isl_fixed_map
*v
;
2161 v
= isl_calloc_array(ctx
, struct isl_fixed_map
, n
);
2164 for (i
= 0; i
< n
; ++i
)
2165 isl_int_init(v
[i
].v
);
2169 static void free_isl_fixed_map_array(struct isl_fixed_map
*v
, int n
)
2175 for (i
= 0; i
< n
; ++i
)
2176 isl_int_clear(v
[i
].v
);
2180 /* Compare the "v" field of two isl_fixed_map structs.
2182 static int qsort_fixed_map_cmp(const void *p1
, const void *p2
)
2184 const struct isl_fixed_map
*e1
= (const struct isl_fixed_map
*) p1
;
2185 const struct isl_fixed_map
*e2
= (const struct isl_fixed_map
*) p2
;
2187 return isl_int_cmp(e1
->v
, e2
->v
);
2190 /* Internal data structure used while checking whether all maps
2191 * in a union_map have a fixed value for a given output dimension.
2192 * v is the list of maps, with the fixed value for the dimension
2193 * n is the number of maps considered so far
2194 * pos is the output dimension under investigation
2196 struct isl_fixed_dim_data
{
2197 struct isl_fixed_map
*v
;
2202 static int fixed_at_pos(__isl_keep isl_map
*map
, void *user
)
2204 struct isl_fixed_dim_data
*data
= user
;
2206 data
->v
[data
->n
].map
= map
;
2207 return isl_map_plain_is_fixed(map
, isl_dim_out
, data
->pos
,
2208 &data
->v
[data
->n
++].v
);
2211 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2212 int first
, int n_range
);
2214 /* Given a list of the maps, with their fixed values at output dimension "pos",
2215 * check whether the ranges of the maps form an obvious partition.
2217 * We first sort the maps according to their fixed values.
2218 * If all maps have a different value, then we know the ranges form
2220 * Otherwise, we collect the maps with the same fixed value and
2221 * check whether each such collection is obviously injective
2222 * based on later dimensions.
2224 static int separates(struct isl_fixed_map
*v
, int n
,
2225 __isl_take isl_space
*dim
, int pos
, int n_range
)
2232 qsort(v
, n
, sizeof(*v
), &qsort_fixed_map_cmp
);
2234 for (i
= 0; i
+ 1 < n
; ++i
) {
2236 isl_union_map
*part
;
2239 for (j
= i
+ 1; j
< n
; ++j
)
2240 if (isl_int_ne(v
[i
].v
, v
[j
].v
))
2246 part
= isl_union_map_alloc(isl_space_copy(dim
), j
- i
);
2247 for (k
= i
; k
< j
; ++k
)
2248 part
= isl_union_map_add_map(part
,
2249 isl_map_copy(v
[k
].map
));
2251 injective
= plain_injective_on_range(part
, pos
+ 1, n_range
);
2260 isl_space_free(dim
);
2261 free_isl_fixed_map_array(v
, n
);
2264 isl_space_free(dim
);
2265 free_isl_fixed_map_array(v
, n
);
2269 /* Check whether the maps in umap have obviously distinct ranges.
2270 * In particular, check for an output dimension in the range
2271 * [first,n_range) for which all maps have a fixed value
2272 * and then check if these values, possibly along with fixed values
2273 * at later dimensions, entail distinct ranges.
2275 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2276 int first
, int n_range
)
2280 struct isl_fixed_dim_data data
= { NULL
};
2282 ctx
= isl_union_map_get_ctx(umap
);
2284 n
= isl_union_map_n_map(umap
);
2289 isl_union_map_free(umap
);
2293 if (first
>= n_range
) {
2294 isl_union_map_free(umap
);
2298 data
.v
= alloc_isl_fixed_map_array(ctx
, n
);
2302 for (data
.pos
= first
; data
.pos
< n_range
; ++data
.pos
) {
2308 fixed
= union_map_forall_user(umap
, &fixed_at_pos
, &data
);
2313 dim
= isl_union_map_get_space(umap
);
2314 injective
= separates(data
.v
, n
, dim
, data
.pos
, n_range
);
2315 isl_union_map_free(umap
);
2319 free_isl_fixed_map_array(data
.v
, n
);
2320 isl_union_map_free(umap
);
2324 free_isl_fixed_map_array(data
.v
, n
);
2325 isl_union_map_free(umap
);
2329 /* Check whether the maps in umap that map to subsets of "ran"
2330 * have obviously distinct ranges.
2332 static int plain_injective_on_range_wrap(__isl_keep isl_set
*ran
, void *user
)
2334 isl_union_map
*umap
= user
;
2336 umap
= isl_union_map_copy(umap
);
2337 umap
= isl_union_map_intersect_range(umap
,
2338 isl_union_set_from_set(isl_set_copy(ran
)));
2339 return plain_injective_on_range(umap
, 0, isl_set_dim(ran
, isl_dim_set
));
2342 /* Check if the given union_map is obviously injective.
2344 * In particular, we first check if all individual maps are obviously
2345 * injective and then check if all the ranges of these maps are
2346 * obviously disjoint.
2348 int isl_union_map_plain_is_injective(__isl_keep isl_union_map
*umap
)
2351 isl_union_map
*univ
;
2354 in
= union_map_forall(umap
, &isl_map_plain_is_injective
);
2360 univ
= isl_union_map_universe(isl_union_map_copy(umap
));
2361 ran
= isl_union_map_range(univ
);
2363 in
= union_map_forall_user(ran
, &plain_injective_on_range_wrap
, umap
);
2365 isl_union_set_free(ran
);
2370 int isl_union_map_is_bijective(__isl_keep isl_union_map
*umap
)
2374 sv
= isl_union_map_is_single_valued(umap
);
2378 return isl_union_map_is_injective(umap
);
2381 static int zip_entry(void **entry
, void *user
)
2383 isl_map
*map
= *entry
;
2384 isl_union_map
**res
= user
;
2386 if (!isl_map_can_zip(map
))
2389 *res
= isl_union_map_add_map(*res
, isl_map_zip(isl_map_copy(map
)));
2394 __isl_give isl_union_map
*isl_union_map_zip(__isl_take isl_union_map
*umap
)
2396 return cond_un_op(umap
, &zip_entry
);
2399 static int uncurry_entry(void **entry
, void *user
)
2401 isl_map
*map
= *entry
;
2402 isl_union_map
**res
= user
;
2404 if (!isl_map_can_uncurry(map
))
2407 *res
= isl_union_map_add_map(*res
, isl_map_uncurry(isl_map_copy(map
)));
2412 /* Given a union map, take the maps of the form A -> (B -> C) and
2413 * return the union of the corresponding maps (A -> B) -> C.
2415 __isl_give isl_union_map
*isl_union_map_uncurry(__isl_take isl_union_map
*umap
)
2417 return cond_un_op(umap
, &uncurry_entry
);
2420 static int curry_entry(void **entry
, void *user
)
2422 isl_map
*map
= *entry
;
2423 isl_union_map
**res
= user
;
2425 if (!isl_map_can_curry(map
))
2428 *res
= isl_union_map_add_map(*res
, isl_map_curry(isl_map_copy(map
)));
2433 /* Given a union map, take the maps of the form (A -> B) -> C and
2434 * return the union of the corresponding maps A -> (B -> C).
2436 __isl_give isl_union_map
*isl_union_map_curry(__isl_take isl_union_map
*umap
)
2438 return cond_un_op(umap
, &curry_entry
);
2441 static int lift_entry(void **entry
, void *user
)
2443 isl_set
*set
= *entry
;
2444 isl_union_set
**res
= user
;
2446 *res
= isl_union_set_add_set(*res
, isl_set_lift(isl_set_copy(set
)));
2451 __isl_give isl_union_set
*isl_union_set_lift(__isl_take isl_union_set
*uset
)
2453 return cond_un_op(uset
, &lift_entry
);
2456 static int coefficients_entry(void **entry
, void *user
)
2458 isl_set
*set
= *entry
;
2459 isl_union_set
**res
= user
;
2461 set
= isl_set_copy(set
);
2462 set
= isl_set_from_basic_set(isl_set_coefficients(set
));
2463 *res
= isl_union_set_add_set(*res
, set
);
2468 __isl_give isl_union_set
*isl_union_set_coefficients(
2469 __isl_take isl_union_set
*uset
)
2478 ctx
= isl_union_set_get_ctx(uset
);
2479 dim
= isl_space_set_alloc(ctx
, 0, 0);
2480 res
= isl_union_map_alloc(dim
, uset
->table
.n
);
2481 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2482 &coefficients_entry
, &res
) < 0)
2485 isl_union_set_free(uset
);
2488 isl_union_set_free(uset
);
2489 isl_union_set_free(res
);
2493 static int solutions_entry(void **entry
, void *user
)
2495 isl_set
*set
= *entry
;
2496 isl_union_set
**res
= user
;
2498 set
= isl_set_copy(set
);
2499 set
= isl_set_from_basic_set(isl_set_solutions(set
));
2501 *res
= isl_union_set_from_set(set
);
2503 *res
= isl_union_set_add_set(*res
, set
);
2511 __isl_give isl_union_set
*isl_union_set_solutions(
2512 __isl_take isl_union_set
*uset
)
2514 isl_union_set
*res
= NULL
;
2519 if (uset
->table
.n
== 0) {
2520 res
= isl_union_set_empty(isl_union_set_get_space(uset
));
2521 isl_union_set_free(uset
);
2525 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2526 &solutions_entry
, &res
) < 0)
2529 isl_union_set_free(uset
);
2532 isl_union_set_free(uset
);
2533 isl_union_set_free(res
);
2537 /* Internal data structure for isl_union_map_preimage_domain_multi_aff.
2539 * "ma" is the function under which the preimage should be taken.
2540 * "space" is the space of "ma".
2541 * "res" collects the results.
2543 struct isl_union_map_preimage_domain_data
{
2549 /* Compute the preimage of the domain of *entry under the function
2550 * represented by data->ma, provided the domain space of *entry
2551 * match the target space of data->ma, and add the result to data->res.
2553 static int preimage_domain_entry(void **entry
, void *user
)
2556 isl_map
*map
= *entry
;
2557 struct isl_union_map_preimage_domain_data
*data
= user
;
2560 m
= isl_space_tuple_match(map
->dim
, isl_dim_in
,
2561 data
->space
, isl_dim_out
);
2567 map
= isl_map_copy(map
);
2568 map
= isl_map_preimage_domain_multi_aff(map
,
2569 isl_multi_aff_copy(data
->ma
));
2571 empty
= isl_map_is_empty(map
);
2572 if (empty
< 0 || empty
) {
2574 return empty
< 0 ? -1 : 0;
2577 data
->res
= isl_union_map_add_map(data
->res
, map
);
2582 /* Compute the preimage of the domain of "umap" under the function
2583 * represented by "ma".
2584 * In other words, plug in "ma" in the domain of "umap".
2585 * The result contains maps that live in the same spaces as the maps of "umap"
2586 * with domain space equal to the target space of "ma",
2587 * except that the domain has been replaced by the domain space of "ma".
2589 __isl_give isl_union_map
*isl_union_map_preimage_domain_multi_aff(
2590 __isl_take isl_union_map
*umap
, __isl_take isl_multi_aff
*ma
)
2594 struct isl_union_map_preimage_domain_data data
;
2599 ctx
= isl_union_map_get_ctx(umap
);
2600 space
= isl_union_map_get_space(umap
);
2601 data
.space
= isl_multi_aff_get_space(ma
);
2603 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
2604 if (isl_hash_table_foreach(ctx
, &umap
->table
, &preimage_domain_entry
,
2606 data
.res
= isl_union_map_free(data
.res
);
2608 isl_space_free(data
.space
);
2609 isl_union_map_free(umap
);
2610 isl_multi_aff_free(ma
);
2613 isl_union_map_free(umap
);
2614 isl_multi_aff_free(ma
);