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>
17 #include <isl_space_private.h>
18 #include <isl_union_map_private.h>
19 #include <isl/union_set.h>
21 /* Is this union set a parameter domain?
23 int isl_union_set_is_params(__isl_keep isl_union_set
*uset
)
30 if (uset
->table
.n
!= 1)
33 set
= isl_set_from_union_set(isl_union_set_copy(uset
));
34 params
= isl_set_is_params(set
);
39 static __isl_give isl_union_map
*isl_union_map_alloc(__isl_take isl_space
*dim
,
47 umap
= isl_calloc_type(dim
->ctx
, isl_union_map
);
53 if (isl_hash_table_init(dim
->ctx
, &umap
->table
, size
) < 0)
59 isl_union_map_free(umap
);
63 __isl_give isl_union_map
*isl_union_map_empty(__isl_take isl_space
*dim
)
65 return isl_union_map_alloc(dim
, 16);
68 __isl_give isl_union_set
*isl_union_set_empty(__isl_take isl_space
*dim
)
70 return isl_union_map_empty(dim
);
73 isl_ctx
*isl_union_map_get_ctx(__isl_keep isl_union_map
*umap
)
75 return umap
? umap
->dim
->ctx
: NULL
;
78 isl_ctx
*isl_union_set_get_ctx(__isl_keep isl_union_set
*uset
)
80 return uset
? uset
->dim
->ctx
: NULL
;
83 __isl_give isl_space
*isl_union_map_get_space(__isl_keep isl_union_map
*umap
)
87 return isl_space_copy(umap
->dim
);
90 __isl_give isl_space
*isl_union_set_get_space(__isl_keep isl_union_set
*uset
)
92 return isl_union_map_get_space(uset
);
95 static int free_umap_entry(void **entry
, void *user
)
97 isl_map
*map
= *entry
;
102 static int add_map(__isl_take isl_map
*map
, void *user
)
104 isl_union_map
**umap
= (isl_union_map
**)user
;
106 *umap
= isl_union_map_add_map(*umap
, map
);
111 __isl_give isl_union_map
*isl_union_map_dup(__isl_keep isl_union_map
*umap
)
118 dup
= isl_union_map_empty(isl_space_copy(umap
->dim
));
119 if (isl_union_map_foreach_map(umap
, &add_map
, &dup
) < 0)
123 isl_union_map_free(dup
);
127 __isl_give isl_union_map
*isl_union_map_cow(__isl_take isl_union_map
*umap
)
135 return isl_union_map_dup(umap
);
138 struct isl_union_align
{
143 static int align_entry(void **entry
, void *user
)
145 isl_map
*map
= *entry
;
147 struct isl_union_align
*data
= user
;
149 exp
= isl_reordering_extend_space(isl_reordering_copy(data
->exp
),
150 isl_map_get_space(map
));
152 data
->res
= isl_union_map_add_map(data
->res
,
153 isl_map_realign(isl_map_copy(map
), exp
));
158 /* Align the parameters of umap along those of model.
159 * The result has the parameters of model first, in the same order
160 * as they appear in model, followed by any remaining parameters of
161 * umap that do not appear in model.
163 __isl_give isl_union_map
*isl_union_map_align_params(
164 __isl_take isl_union_map
*umap
, __isl_take isl_space
*model
)
166 struct isl_union_align data
= { NULL
, NULL
};
171 if (isl_space_match(umap
->dim
, isl_dim_param
, model
, isl_dim_param
)) {
172 isl_space_free(model
);
176 model
= isl_space_params(model
);
177 data
.exp
= isl_parameter_alignment_reordering(umap
->dim
, model
);
181 data
.res
= isl_union_map_alloc(isl_space_copy(data
.exp
->dim
),
183 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
184 &align_entry
, &data
) < 0)
187 isl_reordering_free(data
.exp
);
188 isl_union_map_free(umap
);
189 isl_space_free(model
);
192 isl_reordering_free(data
.exp
);
193 isl_union_map_free(umap
);
194 isl_union_map_free(data
.res
);
195 isl_space_free(model
);
199 __isl_give isl_union_set
*isl_union_set_align_params(
200 __isl_take isl_union_set
*uset
, __isl_take isl_space
*model
)
202 return isl_union_map_align_params(uset
, model
);
205 __isl_give isl_union_map
*isl_union_map_union(__isl_take isl_union_map
*umap1
,
206 __isl_take isl_union_map
*umap2
)
208 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
209 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
211 umap1
= isl_union_map_cow(umap1
);
213 if (!umap1
|| !umap2
)
216 if (isl_union_map_foreach_map(umap2
, &add_map
, &umap1
) < 0)
219 isl_union_map_free(umap2
);
223 isl_union_map_free(umap1
);
224 isl_union_map_free(umap2
);
228 __isl_give isl_union_set
*isl_union_set_union(__isl_take isl_union_set
*uset1
,
229 __isl_take isl_union_set
*uset2
)
231 return isl_union_map_union(uset1
, uset2
);
234 __isl_give isl_union_map
*isl_union_map_copy(__isl_keep isl_union_map
*umap
)
243 __isl_give isl_union_set
*isl_union_set_copy(__isl_keep isl_union_set
*uset
)
245 return isl_union_map_copy(uset
);
248 void *isl_union_map_free(__isl_take isl_union_map
*umap
)
256 isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
257 &free_umap_entry
, NULL
);
258 isl_hash_table_clear(&umap
->table
);
259 isl_space_free(umap
->dim
);
264 void *isl_union_set_free(__isl_take isl_union_set
*uset
)
266 return isl_union_map_free(uset
);
269 static int has_dim(const void *entry
, const void *val
)
271 isl_map
*map
= (isl_map
*)entry
;
272 isl_space
*dim
= (isl_space
*)val
;
274 return isl_space_is_equal(map
->dim
, dim
);
277 __isl_give isl_union_map
*isl_union_map_add_map(__isl_take isl_union_map
*umap
,
278 __isl_take isl_map
*map
)
281 struct isl_hash_table_entry
*entry
;
286 if (isl_map_plain_is_empty(map
)) {
291 if (!isl_space_match(map
->dim
, isl_dim_param
, umap
->dim
, isl_dim_param
)) {
292 umap
= isl_union_map_align_params(umap
, isl_map_get_space(map
));
293 map
= isl_map_align_params(map
, isl_union_map_get_space(umap
));
296 umap
= isl_union_map_cow(umap
);
301 hash
= isl_space_get_hash(map
->dim
);
302 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
303 &has_dim
, map
->dim
, 1);
310 entry
->data
= isl_map_union(entry
->data
, isl_map_copy(map
));
319 isl_union_map_free(umap
);
323 __isl_give isl_union_set
*isl_union_set_add_set(__isl_take isl_union_set
*uset
,
324 __isl_take isl_set
*set
)
326 return isl_union_map_add_map(uset
, (isl_map
*)set
);
329 __isl_give isl_union_map
*isl_union_map_from_map(__isl_take isl_map
*map
)
337 dim
= isl_map_get_space(map
);
338 dim
= isl_space_params(dim
);
339 umap
= isl_union_map_empty(dim
);
340 umap
= isl_union_map_add_map(umap
, map
);
345 __isl_give isl_union_set
*isl_union_set_from_set(__isl_take isl_set
*set
)
347 return isl_union_map_from_map((isl_map
*)set
);
350 __isl_give isl_union_map
*isl_union_map_from_basic_map(
351 __isl_take isl_basic_map
*bmap
)
353 return isl_union_map_from_map(isl_map_from_basic_map(bmap
));
356 __isl_give isl_union_set
*isl_union_set_from_basic_set(
357 __isl_take isl_basic_set
*bset
)
359 return isl_union_map_from_basic_map(bset
);
362 struct isl_union_map_foreach_data
364 int (*fn
)(__isl_take isl_map
*map
, void *user
);
368 static int call_on_copy(void **entry
, void *user
)
370 isl_map
*map
= *entry
;
371 struct isl_union_map_foreach_data
*data
;
372 data
= (struct isl_union_map_foreach_data
*)user
;
374 return data
->fn(isl_map_copy(map
), data
->user
);
377 int isl_union_map_n_map(__isl_keep isl_union_map
*umap
)
379 return umap
? umap
->table
.n
: 0;
382 int isl_union_set_n_set(__isl_keep isl_union_set
*uset
)
384 return uset
? uset
->table
.n
: 0;
387 int isl_union_map_foreach_map(__isl_keep isl_union_map
*umap
,
388 int (*fn
)(__isl_take isl_map
*map
, void *user
), void *user
)
390 struct isl_union_map_foreach_data data
= { fn
, user
};
395 return isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
396 &call_on_copy
, &data
);
399 static int copy_map(void **entry
, void *user
)
401 isl_map
*map
= *entry
;
402 isl_map
**map_p
= user
;
404 *map_p
= isl_map_copy(map
);
409 __isl_give isl_map
*isl_map_from_union_map(__isl_take isl_union_map
*umap
)
416 ctx
= isl_union_map_get_ctx(umap
);
417 if (umap
->table
.n
!= 1)
418 isl_die(ctx
, isl_error_invalid
,
419 "union map needs to contain elements in exactly "
420 "one space", return isl_union_map_free(umap
));
422 isl_hash_table_foreach(ctx
, &umap
->table
, ©_map
, &map
);
424 isl_union_map_free(umap
);
429 __isl_give isl_set
*isl_set_from_union_set(__isl_take isl_union_set
*uset
)
431 return isl_map_from_union_map(uset
);
434 /* Extract the map in "umap" that lives in the given space (ignoring
437 __isl_give isl_map
*isl_union_map_extract_map(__isl_keep isl_union_map
*umap
,
438 __isl_take isl_space
*space
)
441 struct isl_hash_table_entry
*entry
;
443 space
= isl_space_drop_dims(space
, isl_dim_param
,
444 0, isl_space_dim(space
, isl_dim_param
));
445 space
= isl_space_align_params(space
, isl_union_map_get_space(umap
));
449 hash
= isl_space_get_hash(space
);
450 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
453 return isl_map_empty(space
);
454 isl_space_free(space
);
455 return isl_map_copy(entry
->data
);
457 isl_space_free(space
);
461 __isl_give isl_set
*isl_union_set_extract_set(__isl_keep isl_union_set
*uset
,
462 __isl_take isl_space
*dim
)
464 return (isl_set
*)isl_union_map_extract_map(uset
, dim
);
467 /* Check if umap contains a map in the given space.
469 __isl_give
int isl_union_map_contains(__isl_keep isl_union_map
*umap
,
470 __isl_keep isl_space
*dim
)
473 struct isl_hash_table_entry
*entry
;
478 hash
= isl_space_get_hash(dim
);
479 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
484 __isl_give
int isl_union_set_contains(__isl_keep isl_union_set
*uset
,
485 __isl_keep isl_space
*dim
)
487 return isl_union_map_contains(uset
, dim
);
490 int isl_union_set_foreach_set(__isl_keep isl_union_set
*uset
,
491 int (*fn
)(__isl_take isl_set
*set
, void *user
), void *user
)
493 return isl_union_map_foreach_map(uset
,
494 (int(*)(__isl_take isl_map
*, void*))fn
, user
);
497 struct isl_union_set_foreach_point_data
{
498 int (*fn
)(__isl_take isl_point
*pnt
, void *user
);
502 static int foreach_point(__isl_take isl_set
*set
, void *user
)
504 struct isl_union_set_foreach_point_data
*data
= user
;
507 r
= isl_set_foreach_point(set
, data
->fn
, data
->user
);
513 int isl_union_set_foreach_point(__isl_keep isl_union_set
*uset
,
514 int (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
516 struct isl_union_set_foreach_point_data data
= { fn
, user
};
517 return isl_union_set_foreach_set(uset
, &foreach_point
, &data
);
520 struct isl_union_map_gen_bin_data
{
521 isl_union_map
*umap2
;
525 static int subtract_entry(void **entry
, void *user
)
527 struct isl_union_map_gen_bin_data
*data
= user
;
529 struct isl_hash_table_entry
*entry2
;
530 isl_map
*map
= *entry
;
532 hash
= isl_space_get_hash(map
->dim
);
533 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
534 hash
, &has_dim
, map
->dim
, 0);
535 map
= isl_map_copy(map
);
538 map
= isl_map_subtract(map
, isl_map_copy(entry2
->data
));
540 empty
= isl_map_is_empty(map
);
550 data
->res
= isl_union_map_add_map(data
->res
, map
);
555 static __isl_give isl_union_map
*gen_bin_op(__isl_take isl_union_map
*umap1
,
556 __isl_take isl_union_map
*umap2
, int (*fn
)(void **, void *))
558 struct isl_union_map_gen_bin_data data
= { NULL
, NULL
};
560 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
561 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
563 if (!umap1
|| !umap2
)
567 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
569 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
573 isl_union_map_free(umap1
);
574 isl_union_map_free(umap2
);
577 isl_union_map_free(umap1
);
578 isl_union_map_free(umap2
);
579 isl_union_map_free(data
.res
);
583 __isl_give isl_union_map
*isl_union_map_subtract(
584 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
586 return gen_bin_op(umap1
, umap2
, &subtract_entry
);
589 __isl_give isl_union_set
*isl_union_set_subtract(
590 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
592 return isl_union_map_subtract(uset1
, uset2
);
595 struct isl_union_map_gen_bin_set_data
{
600 static int intersect_params_entry(void **entry
, void *user
)
602 struct isl_union_map_gen_bin_set_data
*data
= user
;
603 isl_map
*map
= *entry
;
606 map
= isl_map_copy(map
);
607 map
= isl_map_intersect_params(map
, isl_set_copy(data
->set
));
609 empty
= isl_map_is_empty(map
);
615 data
->res
= isl_union_map_add_map(data
->res
, map
);
620 static __isl_give isl_union_map
*gen_bin_set_op(__isl_take isl_union_map
*umap
,
621 __isl_take isl_set
*set
, int (*fn
)(void **, void *))
623 struct isl_union_map_gen_bin_set_data data
= { NULL
, NULL
};
625 umap
= isl_union_map_align_params(umap
, isl_set_get_space(set
));
626 set
= isl_set_align_params(set
, isl_union_map_get_space(umap
));
632 data
.res
= isl_union_map_alloc(isl_space_copy(umap
->dim
),
634 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
638 isl_union_map_free(umap
);
642 isl_union_map_free(umap
);
644 isl_union_map_free(data
.res
);
648 __isl_give isl_union_map
*isl_union_map_intersect_params(
649 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
651 return gen_bin_set_op(umap
, set
, &intersect_params_entry
);
654 __isl_give isl_union_set
*isl_union_set_intersect_params(
655 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
657 return isl_union_map_intersect_params(uset
, set
);
660 static __isl_give isl_union_map
*union_map_intersect_params(
661 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
663 return isl_union_map_intersect_params(umap
,
664 isl_set_from_union_set(uset
));
667 static __isl_give isl_union_map
*union_map_gist_params(
668 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
670 return isl_union_map_gist_params(umap
, isl_set_from_union_set(uset
));
673 struct isl_union_map_match_bin_data
{
674 isl_union_map
*umap2
;
676 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*);
679 static int match_bin_entry(void **entry
, void *user
)
681 struct isl_union_map_match_bin_data
*data
= user
;
683 struct isl_hash_table_entry
*entry2
;
684 isl_map
*map
= *entry
;
687 hash
= isl_space_get_hash(map
->dim
);
688 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
689 hash
, &has_dim
, map
->dim
, 0);
693 map
= isl_map_copy(map
);
694 map
= data
->fn(map
, isl_map_copy(entry2
->data
));
696 empty
= isl_map_is_empty(map
);
706 data
->res
= isl_union_map_add_map(data
->res
, map
);
711 static __isl_give isl_union_map
*match_bin_op(__isl_take isl_union_map
*umap1
,
712 __isl_take isl_union_map
*umap2
,
713 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*))
715 struct isl_union_map_match_bin_data data
= { NULL
, NULL
, fn
};
717 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
718 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
720 if (!umap1
|| !umap2
)
724 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
726 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
727 &match_bin_entry
, &data
) < 0)
730 isl_union_map_free(umap1
);
731 isl_union_map_free(umap2
);
734 isl_union_map_free(umap1
);
735 isl_union_map_free(umap2
);
736 isl_union_map_free(data
.res
);
740 __isl_give isl_union_map
*isl_union_map_intersect(
741 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
743 return match_bin_op(umap1
, umap2
, &isl_map_intersect
);
746 /* Compute the intersection of the two union_sets.
747 * As a special case, if exactly one of the two union_sets
748 * is a parameter domain, then intersect the parameter domain
749 * of the other one with this set.
751 __isl_give isl_union_set
*isl_union_set_intersect(
752 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
756 p1
= isl_union_set_is_params(uset1
);
757 p2
= isl_union_set_is_params(uset2
);
758 if (p1
< 0 || p2
< 0)
761 return union_map_intersect_params(uset1
, uset2
);
763 return union_map_intersect_params(uset2
, uset1
);
764 return isl_union_map_intersect(uset1
, uset2
);
766 isl_union_set_free(uset1
);
767 isl_union_set_free(uset2
);
771 static int gist_params_entry(void **entry
, void *user
)
773 struct isl_union_map_gen_bin_set_data
*data
= user
;
774 isl_map
*map
= *entry
;
777 map
= isl_map_copy(map
);
778 map
= isl_map_gist_params(map
, isl_set_copy(data
->set
));
780 empty
= isl_map_is_empty(map
);
786 data
->res
= isl_union_map_add_map(data
->res
, map
);
791 __isl_give isl_union_map
*isl_union_map_gist_params(
792 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
794 return gen_bin_set_op(umap
, set
, &gist_params_entry
);
797 __isl_give isl_union_set
*isl_union_set_gist_params(
798 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
800 return isl_union_map_gist_params(uset
, set
);
803 __isl_give isl_union_map
*isl_union_map_gist(__isl_take isl_union_map
*umap
,
804 __isl_take isl_union_map
*context
)
806 return match_bin_op(umap
, context
, &isl_map_gist
);
809 __isl_give isl_union_set
*isl_union_set_gist(__isl_take isl_union_set
*uset
,
810 __isl_take isl_union_set
*context
)
812 if (isl_union_set_is_params(context
))
813 return union_map_gist_params(uset
, context
);
814 return isl_union_map_gist(uset
, context
);
817 static __isl_give isl_map
*lex_le_set(__isl_take isl_map
*set1
,
818 __isl_take isl_map
*set2
)
820 return isl_set_lex_le_set((isl_set
*)set1
, (isl_set
*)set2
);
823 static __isl_give isl_map
*lex_lt_set(__isl_take isl_map
*set1
,
824 __isl_take isl_map
*set2
)
826 return isl_set_lex_lt_set((isl_set
*)set1
, (isl_set
*)set2
);
829 __isl_give isl_union_map
*isl_union_set_lex_lt_union_set(
830 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
832 return match_bin_op(uset1
, uset2
, &lex_lt_set
);
835 __isl_give isl_union_map
*isl_union_set_lex_le_union_set(
836 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
838 return match_bin_op(uset1
, uset2
, &lex_le_set
);
841 __isl_give isl_union_map
*isl_union_set_lex_gt_union_set(
842 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
844 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2
, uset1
));
847 __isl_give isl_union_map
*isl_union_set_lex_ge_union_set(
848 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
850 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2
, uset1
));
853 __isl_give isl_union_map
*isl_union_map_lex_gt_union_map(
854 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
856 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2
, umap1
));
859 __isl_give isl_union_map
*isl_union_map_lex_ge_union_map(
860 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
862 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2
, umap1
));
865 static int intersect_domain_entry(void **entry
, void *user
)
867 struct isl_union_map_gen_bin_data
*data
= user
;
869 struct isl_hash_table_entry
*entry2
;
871 isl_map
*map
= *entry
;
874 dim
= isl_map_get_space(map
);
875 dim
= isl_space_domain(dim
);
876 hash
= isl_space_get_hash(dim
);
877 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
878 hash
, &has_dim
, dim
, 0);
883 map
= isl_map_copy(map
);
884 map
= isl_map_intersect_domain(map
, isl_set_copy(entry2
->data
));
886 empty
= isl_map_is_empty(map
);
896 data
->res
= isl_union_map_add_map(data
->res
, map
);
901 /* Intersect the domain of "umap" with "uset".
902 * If "uset" is a parameters domain, then intersect the parameter
903 * domain of "umap" with this set.
905 __isl_give isl_union_map
*isl_union_map_intersect_domain(
906 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
908 if (isl_union_set_is_params(uset
))
909 return union_map_intersect_params(umap
, uset
);
910 return gen_bin_op(umap
, uset
, &intersect_domain_entry
);
913 /* Remove the elements of data->umap2 from the domain of *entry
914 * and add the result to data->res.
916 static int subtract_domain_entry(void **entry
, void *user
)
918 struct isl_union_map_gen_bin_data
*data
= user
;
920 struct isl_hash_table_entry
*entry2
;
922 isl_map
*map
= *entry
;
925 dim
= isl_map_get_space(map
);
926 dim
= isl_space_domain(dim
);
927 hash
= isl_space_get_hash(dim
);
928 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
929 hash
, &has_dim
, dim
, 0);
932 map
= isl_map_copy(map
);
935 data
->res
= isl_union_map_add_map(data
->res
, map
);
939 map
= isl_map_subtract_domain(map
, isl_set_copy(entry2
->data
));
941 empty
= isl_map_is_empty(map
);
951 data
->res
= isl_union_map_add_map(data
->res
, map
);
956 /* Remove the elements of "uset" from the domain of "umap".
958 __isl_give isl_union_map
*isl_union_map_subtract_domain(
959 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
961 return gen_bin_op(umap
, dom
, &subtract_domain_entry
);
964 static int gist_domain_entry(void **entry
, void *user
)
966 struct isl_union_map_gen_bin_data
*data
= user
;
968 struct isl_hash_table_entry
*entry2
;
970 isl_map
*map
= *entry
;
973 dim
= isl_map_get_space(map
);
974 dim
= isl_space_domain(dim
);
975 hash
= isl_space_get_hash(dim
);
976 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
977 hash
, &has_dim
, dim
, 0);
982 map
= isl_map_copy(map
);
983 map
= isl_map_gist_domain(map
, isl_set_copy(entry2
->data
));
985 empty
= isl_map_is_empty(map
);
991 data
->res
= isl_union_map_add_map(data
->res
, map
);
996 /* Compute the gist of "umap" with respect to the domain "uset".
997 * If "uset" is a parameters domain, then compute the gist
998 * with respect to this parameter domain.
1000 __isl_give isl_union_map
*isl_union_map_gist_domain(
1001 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1003 if (isl_union_set_is_params(uset
))
1004 return union_map_gist_params(umap
, uset
);
1005 return gen_bin_op(umap
, uset
, &gist_domain_entry
);
1008 static int gist_range_entry(void **entry
, void *user
)
1010 struct isl_union_map_gen_bin_data
*data
= user
;
1012 struct isl_hash_table_entry
*entry2
;
1014 isl_map
*map
= *entry
;
1017 space
= isl_map_get_space(map
);
1018 space
= isl_space_range(space
);
1019 hash
= isl_space_get_hash(space
);
1020 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1021 hash
, &has_dim
, space
, 0);
1022 isl_space_free(space
);
1026 map
= isl_map_copy(map
);
1027 map
= isl_map_gist_range(map
, isl_set_copy(entry2
->data
));
1029 empty
= isl_map_is_empty(map
);
1035 data
->res
= isl_union_map_add_map(data
->res
, map
);
1040 /* Compute the gist of "umap" with respect to the range "uset".
1042 __isl_give isl_union_map
*isl_union_map_gist_range(
1043 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1045 return gen_bin_op(umap
, uset
, &gist_range_entry
);
1048 static int intersect_range_entry(void **entry
, void *user
)
1050 struct isl_union_map_gen_bin_data
*data
= user
;
1052 struct isl_hash_table_entry
*entry2
;
1054 isl_map
*map
= *entry
;
1057 dim
= isl_map_get_space(map
);
1058 dim
= isl_space_range(dim
);
1059 hash
= isl_space_get_hash(dim
);
1060 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1061 hash
, &has_dim
, dim
, 0);
1062 isl_space_free(dim
);
1066 map
= isl_map_copy(map
);
1067 map
= isl_map_intersect_range(map
, isl_set_copy(entry2
->data
));
1069 empty
= isl_map_is_empty(map
);
1079 data
->res
= isl_union_map_add_map(data
->res
, map
);
1084 __isl_give isl_union_map
*isl_union_map_intersect_range(
1085 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1087 return gen_bin_op(umap
, uset
, &intersect_range_entry
);
1090 struct isl_union_map_bin_data
{
1091 isl_union_map
*umap2
;
1094 int (*fn
)(void **entry
, void *user
);
1097 static int apply_range_entry(void **entry
, void *user
)
1099 struct isl_union_map_bin_data
*data
= user
;
1100 isl_map
*map2
= *entry
;
1103 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1104 map2
->dim
, isl_dim_in
))
1107 map2
= isl_map_apply_range(isl_map_copy(data
->map
), isl_map_copy(map2
));
1109 empty
= isl_map_is_empty(map2
);
1119 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1124 static int bin_entry(void **entry
, void *user
)
1126 struct isl_union_map_bin_data
*data
= user
;
1127 isl_map
*map
= *entry
;
1130 if (isl_hash_table_foreach(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1131 data
->fn
, data
) < 0)
1137 static __isl_give isl_union_map
*bin_op(__isl_take isl_union_map
*umap1
,
1138 __isl_take isl_union_map
*umap2
, int (*fn
)(void **entry
, void *user
))
1140 struct isl_union_map_bin_data data
= { NULL
, NULL
, NULL
, fn
};
1142 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1143 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1145 if (!umap1
|| !umap2
)
1149 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
1151 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1152 &bin_entry
, &data
) < 0)
1155 isl_union_map_free(umap1
);
1156 isl_union_map_free(umap2
);
1159 isl_union_map_free(umap1
);
1160 isl_union_map_free(umap2
);
1161 isl_union_map_free(data
.res
);
1165 __isl_give isl_union_map
*isl_union_map_apply_range(
1166 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1168 return bin_op(umap1
, umap2
, &apply_range_entry
);
1171 __isl_give isl_union_map
*isl_union_map_apply_domain(
1172 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1174 umap1
= isl_union_map_reverse(umap1
);
1175 umap1
= isl_union_map_apply_range(umap1
, umap2
);
1176 return isl_union_map_reverse(umap1
);
1179 __isl_give isl_union_set
*isl_union_set_apply(
1180 __isl_take isl_union_set
*uset
, __isl_take isl_union_map
*umap
)
1182 return isl_union_map_apply_range(uset
, umap
);
1185 static int map_lex_lt_entry(void **entry
, void *user
)
1187 struct isl_union_map_bin_data
*data
= user
;
1188 isl_map
*map2
= *entry
;
1190 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1191 map2
->dim
, isl_dim_out
))
1194 map2
= isl_map_lex_lt_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1196 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1201 __isl_give isl_union_map
*isl_union_map_lex_lt_union_map(
1202 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1204 return bin_op(umap1
, umap2
, &map_lex_lt_entry
);
1207 static int map_lex_le_entry(void **entry
, void *user
)
1209 struct isl_union_map_bin_data
*data
= user
;
1210 isl_map
*map2
= *entry
;
1212 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1213 map2
->dim
, isl_dim_out
))
1216 map2
= isl_map_lex_le_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1218 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1223 __isl_give isl_union_map
*isl_union_map_lex_le_union_map(
1224 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1226 return bin_op(umap1
, umap2
, &map_lex_le_entry
);
1229 static int product_entry(void **entry
, void *user
)
1231 struct isl_union_map_bin_data
*data
= user
;
1232 isl_map
*map2
= *entry
;
1234 map2
= isl_map_product(isl_map_copy(data
->map
), isl_map_copy(map2
));
1236 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1241 __isl_give isl_union_map
*isl_union_map_product(__isl_take isl_union_map
*umap1
,
1242 __isl_take isl_union_map
*umap2
)
1244 return bin_op(umap1
, umap2
, &product_entry
);
1247 static int set_product_entry(void **entry
, void *user
)
1249 struct isl_union_map_bin_data
*data
= user
;
1250 isl_set
*set2
= *entry
;
1252 set2
= isl_set_product(isl_set_copy(data
->map
), isl_set_copy(set2
));
1254 data
->res
= isl_union_set_add_set(data
->res
, set2
);
1259 __isl_give isl_union_set
*isl_union_set_product(__isl_take isl_union_set
*uset1
,
1260 __isl_take isl_union_set
*uset2
)
1262 return bin_op(uset1
, uset2
, &set_product_entry
);
1265 static int domain_product_entry(void **entry
, void *user
)
1267 struct isl_union_map_bin_data
*data
= user
;
1268 isl_map
*map2
= *entry
;
1270 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1271 map2
->dim
, isl_dim_out
))
1274 map2
= isl_map_domain_product(isl_map_copy(data
->map
),
1275 isl_map_copy(map2
));
1277 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1282 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1284 __isl_give isl_union_map
*isl_union_map_domain_product(
1285 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1287 return bin_op(umap1
, umap2
, &domain_product_entry
);
1290 static int range_product_entry(void **entry
, void *user
)
1292 struct isl_union_map_bin_data
*data
= user
;
1293 isl_map
*map2
= *entry
;
1295 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1296 map2
->dim
, isl_dim_in
))
1299 map2
= isl_map_range_product(isl_map_copy(data
->map
),
1300 isl_map_copy(map2
));
1302 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1307 __isl_give isl_union_map
*isl_union_map_range_product(
1308 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1310 return bin_op(umap1
, umap2
, &range_product_entry
);
1313 static int flat_range_product_entry(void **entry
, void *user
)
1315 struct isl_union_map_bin_data
*data
= user
;
1316 isl_map
*map2
= *entry
;
1318 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1319 map2
->dim
, isl_dim_in
))
1322 map2
= isl_map_flat_range_product(isl_map_copy(data
->map
),
1323 isl_map_copy(map2
));
1325 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1330 __isl_give isl_union_map
*isl_union_map_flat_range_product(
1331 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1333 return bin_op(umap1
, umap2
, &flat_range_product_entry
);
1336 static __isl_give isl_union_set
*cond_un_op(__isl_take isl_union_map
*umap
,
1337 int (*fn
)(void **, void *))
1344 res
= isl_union_map_alloc(isl_space_copy(umap
->dim
), umap
->table
.n
);
1345 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, &res
) < 0)
1348 isl_union_map_free(umap
);
1351 isl_union_map_free(umap
);
1352 isl_union_set_free(res
);
1356 static int from_range_entry(void **entry
, void *user
)
1358 isl_map
*set
= *entry
;
1359 isl_union_set
**res
= user
;
1361 *res
= isl_union_map_add_map(*res
,
1362 isl_map_from_range(isl_set_copy(set
)));
1367 __isl_give isl_union_map
*isl_union_map_from_range(
1368 __isl_take isl_union_set
*uset
)
1370 return cond_un_op(uset
, &from_range_entry
);
1373 __isl_give isl_union_map
*isl_union_map_from_domain(
1374 __isl_take isl_union_set
*uset
)
1376 return isl_union_map_reverse(isl_union_map_from_range(uset
));
1379 __isl_give isl_union_map
*isl_union_map_from_domain_and_range(
1380 __isl_take isl_union_set
*domain
, __isl_take isl_union_set
*range
)
1382 return isl_union_map_apply_range(isl_union_map_from_domain(domain
),
1383 isl_union_map_from_range(range
));
1386 static __isl_give isl_union_map
*un_op(__isl_take isl_union_map
*umap
,
1387 int (*fn
)(void **, void *))
1389 umap
= isl_union_map_cow(umap
);
1393 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, NULL
) < 0)
1398 isl_union_map_free(umap
);
1402 static int affine_entry(void **entry
, void *user
)
1404 isl_map
**map
= (isl_map
**)entry
;
1406 *map
= isl_map_from_basic_map(isl_map_affine_hull(*map
));
1408 return *map
? 0 : -1;
1411 __isl_give isl_union_map
*isl_union_map_affine_hull(
1412 __isl_take isl_union_map
*umap
)
1414 return un_op(umap
, &affine_entry
);
1417 __isl_give isl_union_set
*isl_union_set_affine_hull(
1418 __isl_take isl_union_set
*uset
)
1420 return isl_union_map_affine_hull(uset
);
1423 static int polyhedral_entry(void **entry
, void *user
)
1425 isl_map
**map
= (isl_map
**)entry
;
1427 *map
= isl_map_from_basic_map(isl_map_polyhedral_hull(*map
));
1429 return *map
? 0 : -1;
1432 __isl_give isl_union_map
*isl_union_map_polyhedral_hull(
1433 __isl_take isl_union_map
*umap
)
1435 return un_op(umap
, &polyhedral_entry
);
1438 __isl_give isl_union_set
*isl_union_set_polyhedral_hull(
1439 __isl_take isl_union_set
*uset
)
1441 return isl_union_map_polyhedral_hull(uset
);
1444 static int simple_entry(void **entry
, void *user
)
1446 isl_map
**map
= (isl_map
**)entry
;
1448 *map
= isl_map_from_basic_map(isl_map_simple_hull(*map
));
1450 return *map
? 0 : -1;
1453 __isl_give isl_union_map
*isl_union_map_simple_hull(
1454 __isl_take isl_union_map
*umap
)
1456 return un_op(umap
, &simple_entry
);
1459 __isl_give isl_union_set
*isl_union_set_simple_hull(
1460 __isl_take isl_union_set
*uset
)
1462 return isl_union_map_simple_hull(uset
);
1465 static int inplace_entry(void **entry
, void *user
)
1467 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*);
1468 isl_map
**map
= (isl_map
**)entry
;
1471 fn
= *(__isl_give isl_map
*(**)(__isl_take isl_map
*)) user
;
1472 copy
= fn(isl_map_copy(*map
));
1482 static __isl_give isl_union_map
*inplace(__isl_take isl_union_map
*umap
,
1483 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*))
1488 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1489 &inplace_entry
, &fn
) < 0)
1494 isl_union_map_free(umap
);
1498 __isl_give isl_union_map
*isl_union_map_coalesce(
1499 __isl_take isl_union_map
*umap
)
1501 return inplace(umap
, &isl_map_coalesce
);
1504 __isl_give isl_union_set
*isl_union_set_coalesce(
1505 __isl_take isl_union_set
*uset
)
1507 return isl_union_map_coalesce(uset
);
1510 __isl_give isl_union_map
*isl_union_map_detect_equalities(
1511 __isl_take isl_union_map
*umap
)
1513 return inplace(umap
, &isl_map_detect_equalities
);
1516 __isl_give isl_union_set
*isl_union_set_detect_equalities(
1517 __isl_take isl_union_set
*uset
)
1519 return isl_union_map_detect_equalities(uset
);
1522 __isl_give isl_union_map
*isl_union_map_compute_divs(
1523 __isl_take isl_union_map
*umap
)
1525 return inplace(umap
, &isl_map_compute_divs
);
1528 __isl_give isl_union_set
*isl_union_set_compute_divs(
1529 __isl_take isl_union_set
*uset
)
1531 return isl_union_map_compute_divs(uset
);
1534 static int lexmin_entry(void **entry
, void *user
)
1536 isl_map
**map
= (isl_map
**)entry
;
1538 *map
= isl_map_lexmin(*map
);
1540 return *map
? 0 : -1;
1543 __isl_give isl_union_map
*isl_union_map_lexmin(
1544 __isl_take isl_union_map
*umap
)
1546 return un_op(umap
, &lexmin_entry
);
1549 __isl_give isl_union_set
*isl_union_set_lexmin(
1550 __isl_take isl_union_set
*uset
)
1552 return isl_union_map_lexmin(uset
);
1555 static int lexmax_entry(void **entry
, void *user
)
1557 isl_map
**map
= (isl_map
**)entry
;
1559 *map
= isl_map_lexmax(*map
);
1561 return *map
? 0 : -1;
1564 __isl_give isl_union_map
*isl_union_map_lexmax(
1565 __isl_take isl_union_map
*umap
)
1567 return un_op(umap
, &lexmax_entry
);
1570 __isl_give isl_union_set
*isl_union_set_lexmax(
1571 __isl_take isl_union_set
*uset
)
1573 return isl_union_map_lexmax(uset
);
1576 static int universe_entry(void **entry
, void *user
)
1578 isl_map
*map
= *entry
;
1579 isl_union_map
**res
= user
;
1581 map
= isl_map_universe(isl_map_get_space(map
));
1582 *res
= isl_union_map_add_map(*res
, map
);
1587 __isl_give isl_union_map
*isl_union_map_universe(__isl_take isl_union_map
*umap
)
1589 return cond_un_op(umap
, &universe_entry
);
1592 __isl_give isl_union_set
*isl_union_set_universe(__isl_take isl_union_set
*uset
)
1594 return isl_union_map_universe(uset
);
1597 static int reverse_entry(void **entry
, void *user
)
1599 isl_map
*map
= *entry
;
1600 isl_union_map
**res
= user
;
1602 *res
= isl_union_map_add_map(*res
, isl_map_reverse(isl_map_copy(map
)));
1607 __isl_give isl_union_map
*isl_union_map_reverse(__isl_take isl_union_map
*umap
)
1609 return cond_un_op(umap
, &reverse_entry
);
1612 static int params_entry(void **entry
, void *user
)
1614 isl_map
*map
= *entry
;
1615 isl_union_set
**res
= user
;
1617 *res
= isl_union_set_add_set(*res
, isl_map_params(isl_map_copy(map
)));
1622 /* Compute the parameter domain of the given union map.
1624 __isl_give isl_set
*isl_union_map_params(__isl_take isl_union_map
*umap
)
1628 empty
= isl_union_map_is_empty(umap
);
1630 return isl_union_map_free(umap
);
1632 return isl_set_empty(isl_union_map_get_space(umap
));
1633 return isl_set_from_union_set(cond_un_op(umap
, ¶ms_entry
));
1636 /* Compute the parameter domain of the given union set.
1638 __isl_give isl_set
*isl_union_set_params(__isl_take isl_union_set
*uset
)
1640 return isl_union_map_params(uset
);
1643 static int domain_entry(void **entry
, void *user
)
1645 isl_map
*map
= *entry
;
1646 isl_union_set
**res
= user
;
1648 *res
= isl_union_set_add_set(*res
, isl_map_domain(isl_map_copy(map
)));
1653 __isl_give isl_union_set
*isl_union_map_domain(__isl_take isl_union_map
*umap
)
1655 return cond_un_op(umap
, &domain_entry
);
1658 static int range_entry(void **entry
, void *user
)
1660 isl_map
*map
= *entry
;
1661 isl_union_set
**res
= user
;
1663 *res
= isl_union_set_add_set(*res
, isl_map_range(isl_map_copy(map
)));
1668 __isl_give isl_union_set
*isl_union_map_range(__isl_take isl_union_map
*umap
)
1670 return cond_un_op(umap
, &range_entry
);
1673 static int domain_map_entry(void **entry
, void *user
)
1675 isl_map
*map
= *entry
;
1676 isl_union_set
**res
= user
;
1678 *res
= isl_union_map_add_map(*res
,
1679 isl_map_domain_map(isl_map_copy(map
)));
1684 __isl_give isl_union_map
*isl_union_map_domain_map(
1685 __isl_take isl_union_map
*umap
)
1687 return cond_un_op(umap
, &domain_map_entry
);
1690 static int range_map_entry(void **entry
, void *user
)
1692 isl_map
*map
= *entry
;
1693 isl_union_set
**res
= user
;
1695 *res
= isl_union_map_add_map(*res
,
1696 isl_map_range_map(isl_map_copy(map
)));
1701 __isl_give isl_union_map
*isl_union_map_range_map(
1702 __isl_take isl_union_map
*umap
)
1704 return cond_un_op(umap
, &range_map_entry
);
1707 static int deltas_entry(void **entry
, void *user
)
1709 isl_map
*map
= *entry
;
1710 isl_union_set
**res
= user
;
1712 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1715 *res
= isl_union_set_add_set(*res
, isl_map_deltas(isl_map_copy(map
)));
1720 __isl_give isl_union_set
*isl_union_map_deltas(__isl_take isl_union_map
*umap
)
1722 return cond_un_op(umap
, &deltas_entry
);
1725 static int deltas_map_entry(void **entry
, void *user
)
1727 isl_map
*map
= *entry
;
1728 isl_union_map
**res
= user
;
1730 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1733 *res
= isl_union_map_add_map(*res
,
1734 isl_map_deltas_map(isl_map_copy(map
)));
1739 __isl_give isl_union_map
*isl_union_map_deltas_map(
1740 __isl_take isl_union_map
*umap
)
1742 return cond_un_op(umap
, &deltas_map_entry
);
1745 static int identity_entry(void **entry
, void *user
)
1747 isl_set
*set
= *entry
;
1748 isl_union_map
**res
= user
;
1750 *res
= isl_union_map_add_map(*res
, isl_set_identity(isl_set_copy(set
)));
1755 __isl_give isl_union_map
*isl_union_set_identity(__isl_take isl_union_set
*uset
)
1757 return cond_un_op(uset
, &identity_entry
);
1760 static int unwrap_entry(void **entry
, void *user
)
1762 isl_set
*set
= *entry
;
1763 isl_union_set
**res
= user
;
1765 if (!isl_set_is_wrapping(set
))
1768 *res
= isl_union_map_add_map(*res
, isl_set_unwrap(isl_set_copy(set
)));
1773 __isl_give isl_union_map
*isl_union_set_unwrap(__isl_take isl_union_set
*uset
)
1775 return cond_un_op(uset
, &unwrap_entry
);
1778 static int wrap_entry(void **entry
, void *user
)
1780 isl_map
*map
= *entry
;
1781 isl_union_set
**res
= user
;
1783 *res
= isl_union_set_add_set(*res
, isl_map_wrap(isl_map_copy(map
)));
1788 __isl_give isl_union_set
*isl_union_map_wrap(__isl_take isl_union_map
*umap
)
1790 return cond_un_op(umap
, &wrap_entry
);
1793 struct isl_union_map_is_subset_data
{
1794 isl_union_map
*umap2
;
1798 static int is_subset_entry(void **entry
, void *user
)
1800 struct isl_union_map_is_subset_data
*data
= user
;
1802 struct isl_hash_table_entry
*entry2
;
1803 isl_map
*map
= *entry
;
1805 hash
= isl_space_get_hash(map
->dim
);
1806 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1807 hash
, &has_dim
, map
->dim
, 0);
1809 int empty
= isl_map_is_empty(map
);
1814 data
->is_subset
= 0;
1818 data
->is_subset
= isl_map_is_subset(map
, entry2
->data
);
1819 if (data
->is_subset
< 0 || !data
->is_subset
)
1825 int isl_union_map_is_subset(__isl_keep isl_union_map
*umap1
,
1826 __isl_keep isl_union_map
*umap2
)
1828 struct isl_union_map_is_subset_data data
= { NULL
, 1 };
1830 umap1
= isl_union_map_copy(umap1
);
1831 umap2
= isl_union_map_copy(umap2
);
1832 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1833 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1835 if (!umap1
|| !umap2
)
1839 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1840 &is_subset_entry
, &data
) < 0 &&
1844 isl_union_map_free(umap1
);
1845 isl_union_map_free(umap2
);
1847 return data
.is_subset
;
1849 isl_union_map_free(umap1
);
1850 isl_union_map_free(umap2
);
1854 int isl_union_set_is_subset(__isl_keep isl_union_set
*uset1
,
1855 __isl_keep isl_union_set
*uset2
)
1857 return isl_union_map_is_subset(uset1
, uset2
);
1860 int isl_union_map_is_equal(__isl_keep isl_union_map
*umap1
,
1861 __isl_keep isl_union_map
*umap2
)
1865 if (!umap1
|| !umap2
)
1867 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1870 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1874 int isl_union_set_is_equal(__isl_keep isl_union_set
*uset1
,
1875 __isl_keep isl_union_set
*uset2
)
1877 return isl_union_map_is_equal(uset1
, uset2
);
1880 int isl_union_map_is_strict_subset(__isl_keep isl_union_map
*umap1
,
1881 __isl_keep isl_union_map
*umap2
)
1885 if (!umap1
|| !umap2
)
1887 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1890 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1891 if (is_subset
== -1)
1896 int isl_union_set_is_strict_subset(__isl_keep isl_union_set
*uset1
,
1897 __isl_keep isl_union_set
*uset2
)
1899 return isl_union_map_is_strict_subset(uset1
, uset2
);
1902 static int sample_entry(void **entry
, void *user
)
1904 isl_basic_map
**sample
= (isl_basic_map
**)user
;
1905 isl_map
*map
= *entry
;
1907 *sample
= isl_map_sample(isl_map_copy(map
));
1910 if (!isl_basic_map_plain_is_empty(*sample
))
1915 __isl_give isl_basic_map
*isl_union_map_sample(__isl_take isl_union_map
*umap
)
1917 isl_basic_map
*sample
= NULL
;
1922 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1923 &sample_entry
, &sample
) < 0 &&
1928 sample
= isl_basic_map_empty(isl_union_map_get_space(umap
));
1930 isl_union_map_free(umap
);
1934 isl_union_map_free(umap
);
1938 __isl_give isl_basic_set
*isl_union_set_sample(__isl_take isl_union_set
*uset
)
1940 return (isl_basic_set
*)isl_union_map_sample(uset
);
1943 struct isl_forall_data
{
1945 int (*fn
)(__isl_keep isl_map
*map
);
1948 static int forall_entry(void **entry
, void *user
)
1950 struct isl_forall_data
*data
= user
;
1951 isl_map
*map
= *entry
;
1953 data
->res
= data
->fn(map
);
1963 static int union_map_forall(__isl_keep isl_union_map
*umap
,
1964 int (*fn
)(__isl_keep isl_map
*map
))
1966 struct isl_forall_data data
= { 1, fn
};
1971 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1972 &forall_entry
, &data
) < 0 && data
.res
)
1978 struct isl_forall_user_data
{
1980 int (*fn
)(__isl_keep isl_map
*map
, void *user
);
1984 static int forall_user_entry(void **entry
, void *user
)
1986 struct isl_forall_user_data
*data
= user
;
1987 isl_map
*map
= *entry
;
1989 data
->res
= data
->fn(map
, data
->user
);
1999 /* Check if fn(map, user) returns true for all maps "map" in umap.
2001 static int union_map_forall_user(__isl_keep isl_union_map
*umap
,
2002 int (*fn
)(__isl_keep isl_map
*map
, void *user
), void *user
)
2004 struct isl_forall_user_data data
= { 1, fn
, user
};
2009 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2010 &forall_user_entry
, &data
) < 0 && data
.res
)
2016 int isl_union_map_is_empty(__isl_keep isl_union_map
*umap
)
2018 return union_map_forall(umap
, &isl_map_is_empty
);
2021 int isl_union_set_is_empty(__isl_keep isl_union_set
*uset
)
2023 return isl_union_map_is_empty(uset
);
2026 static int is_subset_of_identity(__isl_keep isl_map
*map
)
2035 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
2038 dim
= isl_map_get_space(map
);
2039 id
= isl_map_identity(dim
);
2041 is_subset
= isl_map_is_subset(map
, id
);
2048 /* Check if the given map is single-valued.
2053 * and check if the result is a subset of the identity mapping.
2055 int isl_union_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2057 isl_union_map
*test
;
2060 if (isl_union_map_n_map(umap
) == 1) {
2062 umap
= isl_union_map_copy(umap
);
2063 map
= isl_map_from_union_map(umap
);
2064 sv
= isl_map_is_single_valued(map
);
2069 test
= isl_union_map_reverse(isl_union_map_copy(umap
));
2070 test
= isl_union_map_apply_range(test
, isl_union_map_copy(umap
));
2072 sv
= union_map_forall(test
, &is_subset_of_identity
);
2074 isl_union_map_free(test
);
2079 int isl_union_map_is_injective(__isl_keep isl_union_map
*umap
)
2083 umap
= isl_union_map_copy(umap
);
2084 umap
= isl_union_map_reverse(umap
);
2085 in
= isl_union_map_is_single_valued(umap
);
2086 isl_union_map_free(umap
);
2091 /* Represents a map that has a fixed value (v) for one of its
2093 * The map in this structure is not reference counted, so it
2094 * is only valid while the isl_union_map from which it was
2095 * obtained is still alive.
2097 struct isl_fixed_map
{
2102 static struct isl_fixed_map
*alloc_isl_fixed_map_array(isl_ctx
*ctx
,
2106 struct isl_fixed_map
*v
;
2108 v
= isl_calloc_array(ctx
, struct isl_fixed_map
, n
);
2111 for (i
= 0; i
< n
; ++i
)
2112 isl_int_init(v
[i
].v
);
2116 static void free_isl_fixed_map_array(struct isl_fixed_map
*v
, int n
)
2122 for (i
= 0; i
< n
; ++i
)
2123 isl_int_clear(v
[i
].v
);
2127 /* Compare the "v" field of two isl_fixed_map structs.
2129 static int qsort_fixed_map_cmp(const void *p1
, const void *p2
)
2131 const struct isl_fixed_map
*e1
= (const struct isl_fixed_map
*) p1
;
2132 const struct isl_fixed_map
*e2
= (const struct isl_fixed_map
*) p2
;
2134 return isl_int_cmp(e1
->v
, e2
->v
);
2137 /* Internal data structure used while checking whether all maps
2138 * in a union_map have a fixed value for a given output dimension.
2139 * v is the list of maps, with the fixed value for the dimension
2140 * n is the number of maps considered so far
2141 * pos is the output dimension under investigation
2143 struct isl_fixed_dim_data
{
2144 struct isl_fixed_map
*v
;
2149 static int fixed_at_pos(__isl_keep isl_map
*map
, void *user
)
2151 struct isl_fixed_dim_data
*data
= user
;
2153 data
->v
[data
->n
].map
= map
;
2154 return isl_map_plain_is_fixed(map
, isl_dim_out
, data
->pos
,
2155 &data
->v
[data
->n
++].v
);
2158 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2159 int first
, int n_range
);
2161 /* Given a list of the maps, with their fixed values at output dimension "pos",
2162 * check whether the ranges of the maps form an obvious partition.
2164 * We first sort the maps according to their fixed values.
2165 * If all maps have a different value, then we know the ranges form
2167 * Otherwise, we collect the maps with the same fixed value and
2168 * check whether each such collection is obviously injective
2169 * based on later dimensions.
2171 static int separates(struct isl_fixed_map
*v
, int n
,
2172 __isl_take isl_space
*dim
, int pos
, int n_range
)
2179 qsort(v
, n
, sizeof(*v
), &qsort_fixed_map_cmp
);
2181 for (i
= 0; i
+ 1 < n
; ++i
) {
2183 isl_union_map
*part
;
2186 for (j
= i
+ 1; j
< n
; ++j
)
2187 if (isl_int_ne(v
[i
].v
, v
[j
].v
))
2193 part
= isl_union_map_alloc(isl_space_copy(dim
), j
- i
);
2194 for (k
= i
; k
< j
; ++k
)
2195 part
= isl_union_map_add_map(part
,
2196 isl_map_copy(v
[k
].map
));
2198 injective
= plain_injective_on_range(part
, pos
+ 1, n_range
);
2207 isl_space_free(dim
);
2208 free_isl_fixed_map_array(v
, n
);
2211 isl_space_free(dim
);
2212 free_isl_fixed_map_array(v
, n
);
2216 /* Check whether the maps in umap have obviously distinct ranges.
2217 * In particular, check for an output dimension in the range
2218 * [first,n_range) for which all maps have a fixed value
2219 * and then check if these values, possibly along with fixed values
2220 * at later dimensions, entail distinct ranges.
2222 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2223 int first
, int n_range
)
2227 struct isl_fixed_dim_data data
= { NULL
};
2229 ctx
= isl_union_map_get_ctx(umap
);
2234 n
= isl_union_map_n_map(umap
);
2236 isl_union_map_free(umap
);
2240 if (first
>= n_range
) {
2241 isl_union_map_free(umap
);
2245 data
.v
= alloc_isl_fixed_map_array(ctx
, n
);
2249 for (data
.pos
= first
; data
.pos
< n_range
; ++data
.pos
) {
2255 fixed
= union_map_forall_user(umap
, &fixed_at_pos
, &data
);
2260 dim
= isl_union_map_get_space(umap
);
2261 injective
= separates(data
.v
, n
, dim
, data
.pos
, n_range
);
2262 isl_union_map_free(umap
);
2266 free_isl_fixed_map_array(data
.v
, n
);
2267 isl_union_map_free(umap
);
2271 free_isl_fixed_map_array(data
.v
, n
);
2272 isl_union_map_free(umap
);
2276 /* Check whether the maps in umap that map to subsets of "ran"
2277 * have obviously distinct ranges.
2279 static int plain_injective_on_range_wrap(__isl_keep isl_set
*ran
, void *user
)
2281 isl_union_map
*umap
= user
;
2283 umap
= isl_union_map_copy(umap
);
2284 umap
= isl_union_map_intersect_range(umap
,
2285 isl_union_set_from_set(isl_set_copy(ran
)));
2286 return plain_injective_on_range(umap
, 0, isl_set_dim(ran
, isl_dim_set
));
2289 /* Check if the given union_map is obviously injective.
2291 * In particular, we first check if all individual maps are obviously
2292 * injective and then check if all the ranges of these maps are
2293 * obviously disjoint.
2295 int isl_union_map_plain_is_injective(__isl_keep isl_union_map
*umap
)
2298 isl_union_map
*univ
;
2301 in
= union_map_forall(umap
, &isl_map_plain_is_injective
);
2307 univ
= isl_union_map_universe(isl_union_map_copy(umap
));
2308 ran
= isl_union_map_range(univ
);
2310 in
= union_map_forall_user(ran
, &plain_injective_on_range_wrap
, umap
);
2312 isl_union_set_free(ran
);
2317 int isl_union_map_is_bijective(__isl_keep isl_union_map
*umap
)
2321 sv
= isl_union_map_is_single_valued(umap
);
2325 return isl_union_map_is_injective(umap
);
2328 static int zip_entry(void **entry
, void *user
)
2330 isl_map
*map
= *entry
;
2331 isl_union_map
**res
= user
;
2333 if (!isl_map_can_zip(map
))
2336 *res
= isl_union_map_add_map(*res
, isl_map_zip(isl_map_copy(map
)));
2341 __isl_give isl_union_map
*isl_union_map_zip(__isl_take isl_union_map
*umap
)
2343 return cond_un_op(umap
, &zip_entry
);
2346 static int curry_entry(void **entry
, void *user
)
2348 isl_map
*map
= *entry
;
2349 isl_union_map
**res
= user
;
2351 if (!isl_map_can_curry(map
))
2354 *res
= isl_union_map_add_map(*res
, isl_map_curry(isl_map_copy(map
)));
2359 /* Given a union map, take the maps of the form (A -> B) -> C and
2360 * return the union of the corresponding maps A -> (B -> C).
2362 __isl_give isl_union_map
*isl_union_map_curry(__isl_take isl_union_map
*umap
)
2364 return cond_un_op(umap
, &curry_entry
);
2367 static int lift_entry(void **entry
, void *user
)
2369 isl_set
*set
= *entry
;
2370 isl_union_set
**res
= user
;
2372 *res
= isl_union_set_add_set(*res
, isl_set_lift(isl_set_copy(set
)));
2377 __isl_give isl_union_set
*isl_union_set_lift(__isl_take isl_union_set
*uset
)
2379 return cond_un_op(uset
, &lift_entry
);
2382 static int coefficients_entry(void **entry
, void *user
)
2384 isl_set
*set
= *entry
;
2385 isl_union_set
**res
= user
;
2387 set
= isl_set_copy(set
);
2388 set
= isl_set_from_basic_set(isl_set_coefficients(set
));
2389 *res
= isl_union_set_add_set(*res
, set
);
2394 __isl_give isl_union_set
*isl_union_set_coefficients(
2395 __isl_take isl_union_set
*uset
)
2404 ctx
= isl_union_set_get_ctx(uset
);
2405 dim
= isl_space_set_alloc(ctx
, 0, 0);
2406 res
= isl_union_map_alloc(dim
, uset
->table
.n
);
2407 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2408 &coefficients_entry
, &res
) < 0)
2411 isl_union_set_free(uset
);
2414 isl_union_set_free(uset
);
2415 isl_union_set_free(res
);
2419 static int solutions_entry(void **entry
, void *user
)
2421 isl_set
*set
= *entry
;
2422 isl_union_set
**res
= user
;
2424 set
= isl_set_copy(set
);
2425 set
= isl_set_from_basic_set(isl_set_solutions(set
));
2427 *res
= isl_union_set_from_set(set
);
2429 *res
= isl_union_set_add_set(*res
, set
);
2437 __isl_give isl_union_set
*isl_union_set_solutions(
2438 __isl_take isl_union_set
*uset
)
2440 isl_union_set
*res
= NULL
;
2445 if (uset
->table
.n
== 0) {
2446 res
= isl_union_set_empty(isl_union_set_get_space(uset
));
2447 isl_union_set_free(uset
);
2451 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2452 &solutions_entry
, &res
) < 0)
2455 isl_union_set_free(uset
);
2458 isl_union_set_free(uset
);
2459 isl_union_set_free(res
);