2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2013-2014 Ecole Normale Superieure
5 * Copyright 2018-2019 Cerebras Systems
7 * Use of this software is governed by the MIT license
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
19 #include <isl_space_private.h>
20 #include <isl_id_private.h>
21 #include <isl_reordering.h>
23 isl_ctx
*isl_space_get_ctx(__isl_keep isl_space
*space
)
25 return space
? space
->ctx
: NULL
;
28 __isl_give isl_space
*isl_space_alloc(isl_ctx
*ctx
,
29 unsigned nparam
, unsigned n_in
, unsigned n_out
)
33 space
= isl_alloc_type(ctx
, struct isl_space
);
40 space
->nparam
= nparam
;
44 space
->tuple_id
[0] = NULL
;
45 space
->tuple_id
[1] = NULL
;
47 space
->nested
[0] = NULL
;
48 space
->nested
[1] = NULL
;
56 /* Mark the space as being that of a set, by setting the domain tuple
59 static __isl_give isl_space
*mark_as_set(__isl_take isl_space
*space
)
61 space
= isl_space_cow(space
);
64 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
68 /* Is the space that of a set?
70 isl_bool
isl_space_is_set(__isl_keep isl_space
*space
)
73 return isl_bool_error
;
74 if (space
->n_in
!= 0 || space
->nested
[0])
75 return isl_bool_false
;
76 if (space
->tuple_id
[0] != &isl_id_none
)
77 return isl_bool_false
;
81 /* Check that "space" is a set space.
83 isl_stat
isl_space_check_is_set(__isl_keep isl_space
*space
)
87 is_set
= isl_space_is_set(space
);
89 return isl_stat_error
;
91 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
92 "space is not a set", return isl_stat_error
);
96 /* Is the given space that of a map?
98 isl_bool
isl_space_is_map(__isl_keep isl_space
*space
)
103 return isl_bool_error
;
104 r
= space
->tuple_id
[0] != &isl_id_none
&&
105 space
->tuple_id
[1] != &isl_id_none
;
106 return isl_bool_ok(r
);
109 /* Check that "space" is the space of a map.
111 static isl_stat
isl_space_check_is_map(__isl_keep isl_space
*space
)
115 is_space
= isl_space_is_map(space
);
117 return isl_stat_error
;
119 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
120 "expecting map space", return isl_stat_error
);
124 /* Check that "space" is the space of a map
125 * where the domain is a wrapped map space.
127 isl_stat
isl_space_check_domain_is_wrapping(__isl_keep isl_space
*space
)
131 wrapping
= isl_space_domain_is_wrapping(space
);
133 return isl_stat_error
;
135 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
136 "domain not a product", return isl_stat_error
);
140 /* Check that "space" is the space of a map
141 * where the range is a wrapped map space.
143 isl_stat
isl_space_check_range_is_wrapping(__isl_keep isl_space
*space
)
147 wrapping
= isl_space_range_is_wrapping(space
);
149 return isl_stat_error
;
151 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
152 "range not a product", return isl_stat_error
);
156 __isl_give isl_space
*isl_space_set_alloc(isl_ctx
*ctx
,
157 unsigned nparam
, unsigned dim
)
160 space
= isl_space_alloc(ctx
, nparam
, 0, dim
);
161 space
= mark_as_set(space
);
165 /* Mark the space as being that of a parameter domain, by setting
166 * both tuples to isl_id_none.
168 static __isl_give isl_space
*mark_as_params(isl_space
*space
)
172 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
173 space
= isl_space_set_tuple_id(space
, isl_dim_out
, &isl_id_none
);
177 /* Is the space that of a parameter domain?
179 isl_bool
isl_space_is_params(__isl_keep isl_space
*space
)
182 return isl_bool_error
;
183 if (space
->n_in
!= 0 || space
->nested
[0] ||
184 space
->n_out
!= 0 || space
->nested
[1])
185 return isl_bool_false
;
186 if (space
->tuple_id
[0] != &isl_id_none
)
187 return isl_bool_false
;
188 if (space
->tuple_id
[1] != &isl_id_none
)
189 return isl_bool_false
;
190 return isl_bool_true
;
193 /* Create a space for a parameter domain.
195 __isl_give isl_space
*isl_space_params_alloc(isl_ctx
*ctx
, unsigned nparam
)
198 space
= isl_space_alloc(ctx
, nparam
, 0, 0);
199 space
= mark_as_params(space
);
203 /* Create a space for a parameter domain, without any parameters.
205 __isl_give isl_space
*isl_space_unit(isl_ctx
*ctx
)
207 return isl_space_params_alloc(ctx
, 0);
210 static isl_size
global_pos(__isl_keep isl_space
*space
,
211 enum isl_dim_type type
, unsigned pos
)
213 if (isl_space_check_range(space
, type
, pos
, 1) < 0)
214 return isl_size_error
;
220 return pos
+ space
->nparam
;
222 return pos
+ space
->nparam
+ space
->n_in
;
224 isl_assert(isl_space_get_ctx(space
), 0, return isl_size_error
);
226 return isl_size_error
;
229 /* Extend length of ids array to the total number of dimensions.
231 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*space
)
237 dim
= isl_space_dim(space
, isl_dim_all
);
239 return isl_space_free(space
);
240 if (dim
<= space
->n_id
)
244 space
->ids
= isl_calloc_array(space
->ctx
, isl_id
*, dim
);
248 ids
= isl_realloc_array(space
->ctx
, space
->ids
, isl_id
*, dim
);
252 for (i
= space
->n_id
; i
< dim
; ++i
)
253 space
->ids
[i
] = NULL
;
260 isl_space_free(space
);
264 static __isl_give isl_space
*set_id(__isl_take isl_space
*space
,
265 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
269 space
= isl_space_cow(space
);
271 gpos
= global_pos(space
, type
, pos
);
275 if (gpos
>= space
->n_id
) {
278 space
= extend_ids(space
);
283 space
->ids
[gpos
] = id
;
288 isl_space_free(space
);
292 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*space
,
293 enum isl_dim_type type
, unsigned pos
)
297 gpos
= global_pos(space
, type
, pos
);
300 if (gpos
>= space
->n_id
)
302 return space
->ids
[gpos
];
305 /* Return the nested space at the given position.
307 static __isl_keep isl_space
*isl_space_peek_nested(__isl_keep isl_space
*space
,
312 if (!space
->nested
[pos
])
313 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
314 "no nested space", return NULL
);
315 return space
->nested
[pos
];
318 static unsigned offset(__isl_keep isl_space
*space
, enum isl_dim_type type
)
321 case isl_dim_param
: return 0;
322 case isl_dim_in
: return space
->nparam
;
323 case isl_dim_out
: return space
->nparam
+ space
->n_in
;
328 static unsigned n(__isl_keep isl_space
*space
, enum isl_dim_type type
)
331 case isl_dim_param
: return space
->nparam
;
332 case isl_dim_in
: return space
->n_in
;
333 case isl_dim_out
: return space
->n_out
;
335 return space
->nparam
+ space
->n_in
+ space
->n_out
;
340 isl_size
isl_space_dim(__isl_keep isl_space
*space
, enum isl_dim_type type
)
343 return isl_size_error
;
344 return n(space
, type
);
347 /* Return the dimensionality of tuple "inner" within the wrapped relation
348 * inside tuple "outer".
350 isl_size
isl_space_wrapped_dim(__isl_keep isl_space
*space
,
351 enum isl_dim_type outer
, enum isl_dim_type inner
)
356 return isl_size_error
;
357 if (outer
!= isl_dim_in
&& outer
!= isl_dim_out
)
358 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
359 "only input, output and set tuples "
360 "can have nested relations", return isl_size_error
);
361 pos
= outer
- isl_dim_in
;
362 return isl_space_dim(isl_space_peek_nested(space
, pos
), inner
);
365 unsigned isl_space_offset(__isl_keep isl_space
*space
, enum isl_dim_type type
)
369 return offset(space
, type
);
372 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
373 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
374 enum isl_dim_type src_type
)
382 for (i
= 0; i
< n(src
, src_type
); ++i
) {
383 id
= get_id(src
, src_type
, i
);
386 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
393 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*space
)
398 dup
= isl_space_alloc(space
->ctx
,
399 space
->nparam
, space
->n_in
, space
->n_out
);
402 if (space
->tuple_id
[0] &&
403 !(dup
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[0])))
405 if (space
->tuple_id
[1] &&
406 !(dup
->tuple_id
[1] = isl_id_copy(space
->tuple_id
[1])))
408 if (space
->nested
[0] &&
409 !(dup
->nested
[0] = isl_space_copy(space
->nested
[0])))
411 if (space
->nested
[1] &&
412 !(dup
->nested
[1] = isl_space_copy(space
->nested
[1])))
416 dup
= copy_ids(dup
, isl_dim_param
, 0, space
, isl_dim_param
);
417 dup
= copy_ids(dup
, isl_dim_in
, 0, space
, isl_dim_in
);
418 dup
= copy_ids(dup
, isl_dim_out
, 0, space
, isl_dim_out
);
425 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*space
)
433 return isl_space_dup(space
);
436 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*space
)
445 __isl_null isl_space
*isl_space_free(__isl_take isl_space
*space
)
452 if (--space
->ref
> 0)
455 isl_id_free(space
->tuple_id
[0]);
456 isl_id_free(space
->tuple_id
[1]);
458 isl_space_free(space
->nested
[0]);
459 isl_space_free(space
->nested
[1]);
461 for (i
= 0; i
< space
->n_id
; ++i
)
462 isl_id_free(space
->ids
[i
]);
464 isl_ctx_deref(space
->ctx
);
471 /* Check if "s" is a valid dimension or tuple name.
472 * We currently only forbid names that look like a number.
474 * s is assumed to be non-NULL.
476 static int name_ok(isl_ctx
*ctx
, const char *s
)
482 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
488 /* Return a copy of the nested space at the given position.
490 static __isl_keep isl_space
*isl_space_get_nested(__isl_keep isl_space
*space
,
493 return isl_space_copy(isl_space_peek_nested(space
, pos
));
496 /* Return the nested space at the given position.
497 * This may be either a copy or the nested space itself
498 * if there is only one reference to "space".
499 * This allows the nested space to be modified inplace
500 * if both "space" and the nested space have only a single reference.
501 * The caller is not allowed to modify "space" between this call and
502 * a subsequent call to isl_space_restore_nested.
503 * The only exception is that isl_space_free can be called instead.
505 static __isl_give isl_space
*isl_space_take_nested(__isl_keep isl_space
*space
,
513 return isl_space_get_nested(space
, pos
);
514 nested
= space
->nested
[pos
];
515 space
->nested
[pos
] = NULL
;
519 /* Replace the nested space at the given position by "nested",
520 * where this nested space of "space" may be missing
521 * due to a preceding call to isl_space_take_nested.
522 * However, in this case, "space" only has a single reference and
523 * then the call to isl_space_cow has no effect.
525 static __isl_give isl_space
*isl_space_restore_nested(
526 __isl_take isl_space
*space
, int pos
, __isl_take isl_space
*nested
)
528 if (!space
|| !nested
)
531 if (space
->nested
[pos
] == nested
) {
532 isl_space_free(nested
);
536 space
= isl_space_cow(space
);
539 isl_space_free(space
->nested
[pos
]);
540 space
->nested
[pos
] = nested
;
544 isl_space_free(space
);
545 isl_space_free(nested
);
549 /* Is it possible for the given dimension type to have a tuple id?
551 static int space_can_have_id(__isl_keep isl_space
*space
,
552 enum isl_dim_type type
)
556 if (isl_space_is_params(space
))
557 isl_die(space
->ctx
, isl_error_invalid
,
558 "parameter spaces don't have tuple ids", return 0);
559 if (isl_space_is_set(space
) && type
!= isl_dim_set
)
560 isl_die(space
->ctx
, isl_error_invalid
,
561 "set spaces can only have a set id", return 0);
562 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
563 isl_die(space
->ctx
, isl_error_invalid
,
564 "only input, output and set tuples can have ids",
570 /* Does the tuple have an id?
572 isl_bool
isl_space_has_tuple_id(__isl_keep isl_space
*space
,
573 enum isl_dim_type type
)
575 if (!space_can_have_id(space
, type
))
576 return isl_bool_error
;
577 return isl_bool_ok(space
->tuple_id
[type
- isl_dim_in
] != NULL
);
580 /* Does the domain tuple of the map space "space" have an identifier?
582 isl_bool
isl_space_has_domain_tuple_id(__isl_keep isl_space
*space
)
584 if (isl_space_check_is_map(space
) < 0)
585 return isl_bool_error
;
586 return isl_space_has_tuple_id(space
, isl_dim_in
);
589 /* Does the range tuple of the map space "space" have an identifier?
591 isl_bool
isl_space_has_range_tuple_id(__isl_keep isl_space
*space
)
593 if (isl_space_check_is_map(space
) < 0)
594 return isl_bool_error
;
595 return isl_space_has_tuple_id(space
, isl_dim_out
);
598 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*space
,
599 enum isl_dim_type type
)
605 has_id
= isl_space_has_tuple_id(space
, type
);
609 isl_die(space
->ctx
, isl_error_invalid
,
610 "tuple has no id", return NULL
);
611 return isl_id_copy(space
->tuple_id
[type
- isl_dim_in
]);
614 /* Return the identifier of the domain tuple of the map space "space",
615 * assuming it has one.
617 __isl_give isl_id
*isl_space_get_domain_tuple_id(
618 __isl_keep isl_space
*space
)
620 if (isl_space_check_is_map(space
) < 0)
622 return isl_space_get_tuple_id(space
, isl_dim_in
);
625 /* Return the identifier of the range tuple of the map space "space",
626 * assuming it has one.
628 __isl_give isl_id
*isl_space_get_range_tuple_id(
629 __isl_keep isl_space
*space
)
631 if (isl_space_check_is_map(space
) < 0)
633 return isl_space_get_tuple_id(space
, isl_dim_out
);
636 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*space
,
637 enum isl_dim_type type
, __isl_take isl_id
*id
)
639 space
= isl_space_cow(space
);
642 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
643 isl_die(space
->ctx
, isl_error_invalid
,
644 "only input, output and set tuples can have names",
647 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
648 space
->tuple_id
[type
- isl_dim_in
] = id
;
653 isl_space_free(space
);
657 /* Replace the identifier of the domain tuple of the map space "space"
660 __isl_give isl_space
*isl_space_set_domain_tuple_id(
661 __isl_take isl_space
*space
, __isl_take isl_id
*id
)
663 if (isl_space_check_is_map(space
) < 0)
664 space
= isl_space_free(space
);
665 return isl_space_set_tuple_id(space
, isl_dim_in
, id
);
668 /* Replace the identifier of the range tuple of the map space "space"
671 __isl_give isl_space
*isl_space_set_range_tuple_id(
672 __isl_take isl_space
*space
, __isl_take isl_id
*id
)
674 if (isl_space_check_is_map(space
) < 0)
675 space
= isl_space_free(space
);
676 return isl_space_set_tuple_id(space
, isl_dim_out
, id
);
679 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*space
,
680 enum isl_dim_type type
)
682 space
= isl_space_cow(space
);
685 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
686 isl_die(space
->ctx
, isl_error_invalid
,
687 "only input, output and set tuples can have names",
690 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
691 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
695 isl_space_free(space
);
699 /* Set the id of the given dimension of "space" to "id".
700 * If the dimension already has an id, then it is replaced.
701 * If the dimension is a parameter, then we need to change it
702 * in the nested spaces (if any) as well.
704 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*space
,
705 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
707 space
= isl_space_cow(space
);
711 if (type
== isl_dim_param
) {
714 for (i
= 0; i
< 2; ++i
) {
715 if (!space
->nested
[i
])
718 isl_space_set_dim_id(space
->nested
[i
],
719 type
, pos
, isl_id_copy(id
));
720 if (!space
->nested
[i
])
725 isl_id_free(get_id(space
, type
, pos
));
726 return set_id(space
, type
, pos
, id
);
729 isl_space_free(space
);
733 /* Reset the id of the given dimension of "space".
734 * If the dimension already has an id, then it is removed.
735 * If the dimension is a parameter, then we need to reset it
736 * in the nested spaces (if any) as well.
738 __isl_give isl_space
*isl_space_reset_dim_id(__isl_take isl_space
*space
,
739 enum isl_dim_type type
, unsigned pos
)
741 space
= isl_space_cow(space
);
745 if (type
== isl_dim_param
) {
748 for (i
= 0; i
< 2; ++i
) {
749 if (!space
->nested
[i
])
752 isl_space_reset_dim_id(space
->nested
[i
],
754 if (!space
->nested
[i
])
759 isl_id_free(get_id(space
, type
, pos
));
760 return set_id(space
, type
, pos
, NULL
);
762 isl_space_free(space
);
766 isl_bool
isl_space_has_dim_id(__isl_keep isl_space
*space
,
767 enum isl_dim_type type
, unsigned pos
)
770 return isl_bool_error
;
771 return isl_bool_ok(get_id(space
, type
, pos
) != NULL
);
774 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*space
,
775 enum isl_dim_type type
, unsigned pos
)
779 if (!get_id(space
, type
, pos
))
780 isl_die(space
->ctx
, isl_error_invalid
,
781 "dim has no id", return NULL
);
782 return isl_id_copy(get_id(space
, type
, pos
));
785 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*space
,
786 enum isl_dim_type type
, const char *s
)
794 return isl_space_reset_tuple_id(space
, type
);
796 if (!name_ok(space
->ctx
, s
))
799 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
800 return isl_space_set_tuple_id(space
, type
, id
);
802 isl_space_free(space
);
806 /* Does the tuple have a name?
808 isl_bool
isl_space_has_tuple_name(__isl_keep isl_space
*space
,
809 enum isl_dim_type type
)
813 if (!space_can_have_id(space
, type
))
814 return isl_bool_error
;
815 id
= space
->tuple_id
[type
- isl_dim_in
];
816 return isl_bool_ok(id
&& id
->name
);
819 __isl_keep
const char *isl_space_get_tuple_name(__isl_keep isl_space
*space
,
820 enum isl_dim_type type
)
825 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
827 id
= space
->tuple_id
[type
- isl_dim_in
];
828 return id
? id
->name
: NULL
;
831 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*space
,
832 enum isl_dim_type type
, unsigned pos
,
840 return isl_space_reset_dim_id(space
, type
, pos
);
841 if (!name_ok(space
->ctx
, s
))
843 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
844 return isl_space_set_dim_id(space
, type
, pos
, id
);
846 isl_space_free(space
);
850 /* Does the given dimension have a name?
852 isl_bool
isl_space_has_dim_name(__isl_keep isl_space
*space
,
853 enum isl_dim_type type
, unsigned pos
)
858 return isl_bool_error
;
859 id
= get_id(space
, type
, pos
);
860 return isl_bool_ok(id
&& id
->name
);
863 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*space
,
864 enum isl_dim_type type
, unsigned pos
)
866 isl_id
*id
= get_id(space
, type
, pos
);
867 return id
? id
->name
: NULL
;
870 int isl_space_find_dim_by_id(__isl_keep isl_space
*space
,
871 enum isl_dim_type type
, __isl_keep isl_id
*id
)
877 n
= isl_space_dim(space
, type
);
881 offset
= isl_space_offset(space
, type
);
882 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
)
883 if (space
->ids
[offset
+ i
] == id
)
889 int isl_space_find_dim_by_name(__isl_keep isl_space
*space
,
890 enum isl_dim_type type
, const char *name
)
896 n
= isl_space_dim(space
, type
);
900 offset
= isl_space_offset(space
, type
);
901 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
) {
902 isl_id
*id
= get_id(space
, type
, i
);
903 if (id
&& id
->name
&& !strcmp(id
->name
, name
))
910 /* Reset the user pointer on all identifiers of parameters and tuples
913 __isl_give isl_space
*isl_space_reset_user(__isl_take isl_space
*space
)
923 ctx
= isl_space_get_ctx(space
);
925 for (i
= 0; i
< space
->nparam
&& i
< space
->n_id
; ++i
) {
926 if (!isl_id_get_user(space
->ids
[i
]))
928 space
= isl_space_cow(space
);
931 name
= isl_id_get_name(space
->ids
[i
]);
932 id
= isl_id_alloc(ctx
, name
, NULL
);
933 isl_id_free(space
->ids
[i
]);
936 return isl_space_free(space
);
939 for (i
= 0; i
< 2; ++i
) {
940 if (!space
->tuple_id
[i
])
942 if (!isl_id_get_user(space
->tuple_id
[i
]))
944 space
= isl_space_cow(space
);
947 name
= isl_id_get_name(space
->tuple_id
[i
]);
948 id
= isl_id_alloc(ctx
, name
, NULL
);
949 isl_id_free(space
->tuple_id
[i
]);
950 space
->tuple_id
[i
] = id
;
952 return isl_space_free(space
);
955 for (i
= 0; i
< 2; ++i
) {
958 if (!space
->nested
[i
])
960 nested
= isl_space_take_nested(space
, i
);
961 nested
= isl_space_reset_user(nested
);
962 space
= isl_space_restore_nested(space
, i
, nested
);
970 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*space
,
971 enum isl_dim_type type
)
975 if (type
== isl_dim_in
)
976 return space
->tuple_id
[0];
977 if (type
== isl_dim_out
)
978 return space
->tuple_id
[1];
982 static __isl_keep isl_space
*nested(__isl_keep isl_space
*space
,
983 enum isl_dim_type type
)
987 if (type
== isl_dim_in
)
988 return space
->nested
[0];
989 if (type
== isl_dim_out
)
990 return space
->nested
[1];
994 /* Are the two spaces the same, apart from positions and names of parameters?
996 isl_bool
isl_space_has_equal_tuples(__isl_keep isl_space
*space1
,
997 __isl_keep isl_space
*space2
)
999 if (!space1
|| !space2
)
1000 return isl_bool_error
;
1001 if (space1
== space2
)
1002 return isl_bool_true
;
1003 return isl_space_tuple_is_equal(space1
, isl_dim_in
,
1004 space2
, isl_dim_in
) &&
1005 isl_space_tuple_is_equal(space1
, isl_dim_out
,
1006 space2
, isl_dim_out
);
1009 /* Check that a match involving "space" was successful.
1010 * That is, check that "match" is equal to isl_bool_true.
1012 static isl_stat
check_match(__isl_keep isl_space
*space
, isl_bool match
)
1015 return isl_stat_error
;
1017 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1018 "incompatible spaces", return isl_stat_error
);
1023 /* Check that the two spaces are the same,
1024 * apart from positions and names of parameters.
1026 isl_stat
isl_space_check_equal_tuples(__isl_keep isl_space
*space1
,
1027 __isl_keep isl_space
*space2
)
1031 is_equal
= isl_space_has_equal_tuples(space1
, space2
);
1032 return check_match(space1
, is_equal
);
1035 /* Check if the tuple of type "type1" of "space1" is the same as
1036 * the tuple of type "type2" of "space2".
1038 * That is, check if the tuples have the same identifier, the same dimension
1039 * and the same internal structure.
1040 * The identifiers of the dimensions inside the tuples do not affect the result.
1042 * Note that this function only checks the tuples themselves.
1043 * If nested tuples are involved, then we need to be careful not
1044 * to have result affected by possibly differing parameters
1045 * in those nested tuples.
1047 isl_bool
isl_space_tuple_is_equal(__isl_keep isl_space
*space1
,
1048 enum isl_dim_type type1
, __isl_keep isl_space
*space2
,
1049 enum isl_dim_type type2
)
1052 isl_space
*nested1
, *nested2
;
1054 if (!space1
|| !space2
)
1055 return isl_bool_error
;
1057 if (space1
== space2
&& type1
== type2
)
1058 return isl_bool_true
;
1060 if (n(space1
, type1
) != n(space2
, type2
))
1061 return isl_bool_false
;
1062 id1
= tuple_id(space1
, type1
);
1063 id2
= tuple_id(space2
, type2
);
1065 return isl_bool_false
;
1066 if (id1
&& id1
!= id2
)
1067 return isl_bool_false
;
1068 nested1
= nested(space1
, type1
);
1069 nested2
= nested(space2
, type2
);
1070 if (!nested1
^ !nested2
)
1071 return isl_bool_false
;
1072 if (nested1
&& !isl_space_has_equal_tuples(nested1
, nested2
))
1073 return isl_bool_false
;
1074 return isl_bool_true
;
1077 /* Is the tuple "inner" within the wrapped relation inside tuple "outer"
1078 * of "space1" equal to tuple "type2" of "space2"?
1080 isl_bool
isl_space_wrapped_tuple_is_equal(__isl_keep isl_space
*space1
,
1081 enum isl_dim_type outer
, enum isl_dim_type inner
,
1082 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1088 return isl_bool_error
;
1089 if (outer
!= isl_dim_in
&& outer
!= isl_dim_out
)
1090 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
1091 "only input, output and set tuples "
1092 "can have nested relations", return isl_bool_error
);
1093 pos
= outer
- isl_dim_in
;
1094 nested
= isl_space_peek_nested(space1
, pos
);
1095 return isl_space_tuple_is_equal(nested
, inner
, space2
, type2
);
1098 /* Check that the tuple "inner" within the wrapped relation inside tuple "outer"
1099 * of "space1" is equal to tuple "type2" of "space2".
1101 isl_stat
isl_space_check_wrapped_tuple_is_equal(__isl_keep isl_space
*space1
,
1102 enum isl_dim_type outer
, enum isl_dim_type inner
,
1103 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1107 is_equal
= isl_space_wrapped_tuple_is_equal(space1
, outer
, inner
,
1109 return check_match(space1
, is_equal
);
1112 static isl_bool
match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
1113 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1118 if (!space1
|| !space2
)
1119 return isl_bool_error
;
1121 if (space1
== space2
&& type1
== type2
)
1122 return isl_bool_true
;
1124 equal
= isl_space_tuple_is_equal(space1
, type1
, space2
, type2
);
1125 if (equal
< 0 || !equal
)
1128 if (!space1
->ids
&& !space2
->ids
)
1129 return isl_bool_true
;
1131 for (i
= 0; i
< n(space1
, type1
); ++i
) {
1132 if (get_id(space1
, type1
, i
) != get_id(space2
, type2
, i
))
1133 return isl_bool_false
;
1135 return isl_bool_true
;
1138 /* Do "space1" and "space2" have the same parameters?
1140 isl_bool
isl_space_has_equal_params(__isl_keep isl_space
*space1
,
1141 __isl_keep isl_space
*space2
)
1143 return match(space1
, isl_dim_param
, space2
, isl_dim_param
);
1146 /* Do "space1" and "space2" have the same identifiers for all
1147 * the tuple variables?
1149 isl_bool
isl_space_has_equal_ids(__isl_keep isl_space
*space1
,
1150 __isl_keep isl_space
*space2
)
1154 equal
= match(space1
, isl_dim_in
, space2
, isl_dim_in
);
1155 if (equal
< 0 || !equal
)
1157 return match(space1
, isl_dim_out
, space2
, isl_dim_out
);
1160 isl_bool
isl_space_match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
1161 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1163 return match(space1
, type1
, space2
, type2
);
1166 static void get_ids(__isl_keep isl_space
*space
, enum isl_dim_type type
,
1167 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
1171 for (i
= 0; i
< n
; ++i
)
1172 ids
[i
] = get_id(space
, type
, first
+ i
);
1175 static __isl_give isl_space
*space_extend(__isl_take isl_space
*space
,
1176 unsigned nparam
, unsigned n_in
, unsigned n_out
)
1178 isl_id
**ids
= NULL
;
1182 if (space
->nparam
== nparam
&&
1183 space
->n_in
== n_in
&& space
->n_out
== n_out
)
1186 isl_assert(space
->ctx
, space
->nparam
<= nparam
, goto error
);
1187 isl_assert(space
->ctx
, space
->n_in
<= n_in
, goto error
);
1188 isl_assert(space
->ctx
, space
->n_out
<= n_out
, goto error
);
1190 space
= isl_space_cow(space
);
1196 n
= nparam
+ n_in
+ n_out
;
1197 if (n
< nparam
|| n
< n_in
|| n
< n_out
)
1198 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1199 "overflow in total number of dimensions",
1201 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n
);
1204 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
1205 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
+ nparam
);
1206 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1207 ids
+ nparam
+ n_in
);
1210 space
->n_id
= nparam
+ n_in
+ n_out
;
1212 space
->nparam
= nparam
;
1214 space
->n_out
= n_out
;
1219 isl_space_free(space
);
1223 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*space
,
1224 unsigned nparam
, unsigned n_in
, unsigned n_out
)
1226 return space_extend(space
, nparam
, n_in
, n_out
);
1229 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*space
,
1230 enum isl_dim_type type
, unsigned n
)
1232 space
= isl_space_reset(space
, type
);
1237 space
= space_extend(space
,
1238 space
->nparam
+ n
, space
->n_in
, space
->n_out
);
1239 if (space
&& space
->nested
[0] &&
1240 !(space
->nested
[0] = isl_space_add_dims(space
->nested
[0],
1243 if (space
&& space
->nested
[1] &&
1244 !(space
->nested
[1] = isl_space_add_dims(space
->nested
[1],
1249 return space_extend(space
,
1250 space
->nparam
, space
->n_in
+ n
, space
->n_out
);
1252 return space_extend(space
,
1253 space
->nparam
, space
->n_in
, space
->n_out
+ n
);
1255 isl_die(space
->ctx
, isl_error_invalid
,
1256 "cannot add dimensions of specified type", goto error
);
1259 isl_space_free(space
);
1263 /* Add a parameter with identifier "id" to "space", provided
1264 * it does not already appear in "space".
1266 __isl_give isl_space
*isl_space_add_param_id(__isl_take isl_space
*space
,
1267 __isl_take isl_id
*id
)
1274 if (isl_space_find_dim_by_id(space
, isl_dim_param
, id
) >= 0) {
1279 pos
= isl_space_dim(space
, isl_dim_param
);
1282 space
= isl_space_add_dims(space
, isl_dim_param
, 1);
1283 space
= isl_space_set_dim_id(space
, isl_dim_param
, pos
, id
);
1287 isl_space_free(space
);
1292 static int valid_dim_type(enum isl_dim_type type
)
1305 #define TYPE isl_space
1306 #include "check_type_range_templ.c"
1308 /* Insert "n" dimensions of type "type" at position "pos".
1309 * If we are inserting parameters, then they are also inserted in
1310 * any nested spaces.
1312 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*space
,
1313 enum isl_dim_type type
, unsigned pos
, unsigned n
)
1316 isl_id
**ids
= NULL
;
1321 return isl_space_reset(space
, type
);
1323 ctx
= isl_space_get_ctx(space
);
1324 if (!valid_dim_type(type
))
1325 isl_die(ctx
, isl_error_invalid
,
1326 "cannot insert dimensions of specified type",
1329 if (isl_space_check_range(space
, type
, pos
, 0) < 0)
1330 return isl_space_free(space
);
1332 space
= isl_space_cow(space
);
1337 enum isl_dim_type t
, o
= isl_dim_param
;
1340 ids
= isl_calloc_array(ctx
, isl_id
*,
1341 space
->nparam
+ space
->n_in
+ space
->n_out
+ n
);
1345 s
[isl_dim_param
- o
] = space
->nparam
;
1346 s
[isl_dim_in
- o
] = space
->n_in
;
1347 s
[isl_dim_out
- o
] = space
->n_out
;
1348 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1350 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1353 get_ids(space
, t
, 0, pos
, ids
+ off
);
1355 get_ids(space
, t
, pos
, s
[t
- o
] - pos
,
1357 off
+= s
[t
- o
] - pos
;
1362 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
+ n
;
1365 case isl_dim_param
: space
->nparam
+= n
; break;
1366 case isl_dim_in
: space
->n_in
+= n
; break;
1367 case isl_dim_out
: space
->n_out
+= n
; break;
1370 space
= isl_space_reset(space
, type
);
1372 if (type
== isl_dim_param
) {
1373 if (space
&& space
->nested
[0] &&
1374 !(space
->nested
[0] = isl_space_insert_dims(space
->nested
[0],
1375 isl_dim_param
, pos
, n
)))
1377 if (space
&& space
->nested
[1] &&
1378 !(space
->nested
[1] = isl_space_insert_dims(space
->nested
[1],
1379 isl_dim_param
, pos
, n
)))
1385 isl_space_free(space
);
1389 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*space
,
1390 enum isl_dim_type dst_type
, unsigned dst_pos
,
1391 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1395 space
= isl_space_reset(space
, src_type
);
1396 space
= isl_space_reset(space
, dst_type
);
1402 if (isl_space_check_range(space
, src_type
, src_pos
, n
) < 0)
1403 return isl_space_free(space
);
1405 if (dst_type
== src_type
&& dst_pos
== src_pos
)
1408 isl_assert(space
->ctx
, dst_type
!= src_type
, goto error
);
1410 space
= isl_space_cow(space
);
1416 enum isl_dim_type t
, o
= isl_dim_param
;
1419 ids
= isl_calloc_array(space
->ctx
, isl_id
*,
1420 space
->nparam
+ space
->n_in
+ space
->n_out
);
1424 s
[isl_dim_param
- o
] = space
->nparam
;
1425 s
[isl_dim_in
- o
] = space
->n_in
;
1426 s
[isl_dim_out
- o
] = space
->n_out
;
1427 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1428 if (t
== dst_type
) {
1429 get_ids(space
, t
, 0, dst_pos
, ids
+ off
);
1431 get_ids(space
, src_type
, src_pos
, n
, ids
+ off
);
1433 get_ids(space
, t
, dst_pos
, s
[t
- o
] - dst_pos
,
1435 off
+= s
[t
- o
] - dst_pos
;
1436 } else if (t
== src_type
) {
1437 get_ids(space
, t
, 0, src_pos
, ids
+ off
);
1439 get_ids(space
, t
, src_pos
+ n
,
1440 s
[t
- o
] - src_pos
- n
, ids
+ off
);
1441 off
+= s
[t
- o
] - src_pos
- n
;
1443 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1449 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
;
1453 case isl_dim_param
: space
->nparam
+= n
; break;
1454 case isl_dim_in
: space
->n_in
+= n
; break;
1455 case isl_dim_out
: space
->n_out
+= n
; break;
1460 case isl_dim_param
: space
->nparam
-= n
; break;
1461 case isl_dim_in
: space
->n_in
-= n
; break;
1462 case isl_dim_out
: space
->n_out
-= n
; break;
1466 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
1469 for (i
= 0; i
< 2; ++i
) {
1472 if (!space
->nested
[i
])
1474 nested
= isl_space_take_nested(space
, i
);
1475 nested
= isl_space_replace_params(nested
, space
);
1476 space
= isl_space_restore_nested(space
, i
, nested
);
1483 isl_space_free(space
);
1487 /* Check that "space1" and "space2" have the same parameters,
1488 * reporting an error if they do not.
1490 isl_stat
isl_space_check_equal_params(__isl_keep isl_space
*space1
,
1491 __isl_keep isl_space
*space2
)
1495 equal
= isl_space_has_equal_params(space1
, space2
);
1497 return isl_stat_error
;
1499 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
1500 "parameters need to match", return isl_stat_error
);
1504 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
1505 __isl_take isl_space
*right
)
1509 if (isl_space_check_equal_params(left
, right
) < 0)
1512 isl_assert(left
->ctx
,
1513 isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_in
),
1516 space
= isl_space_alloc(left
->ctx
,
1517 left
->nparam
, left
->n_in
, right
->n_out
);
1521 space
= copy_ids(space
, isl_dim_param
, 0, left
, isl_dim_param
);
1522 space
= copy_ids(space
, isl_dim_in
, 0, left
, isl_dim_in
);
1523 space
= copy_ids(space
, isl_dim_out
, 0, right
, isl_dim_out
);
1525 if (space
&& left
->tuple_id
[0] &&
1526 !(space
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
1528 if (space
&& right
->tuple_id
[1] &&
1529 !(space
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
1531 if (space
&& left
->nested
[0] &&
1532 !(space
->nested
[0] = isl_space_copy(left
->nested
[0])))
1534 if (space
&& right
->nested
[1] &&
1535 !(space
->nested
[1] = isl_space_copy(right
->nested
[1])))
1538 isl_space_free(left
);
1539 isl_space_free(right
);
1543 isl_space_free(left
);
1544 isl_space_free(right
);
1548 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1549 * { [A -> B] -> [C -> D] }.
1550 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1552 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
1553 __isl_take isl_space
*right
)
1555 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
1558 if (!left
|| !right
)
1561 is_set
= isl_space_is_set(left
);
1562 if (is_set
!= isl_space_is_set(right
))
1563 isl_die(isl_space_get_ctx(left
), isl_error_invalid
,
1564 "expecting either two set spaces or two map spaces",
1567 return isl_space_range_product(left
, right
);
1569 if (isl_space_check_equal_params(left
, right
) < 0)
1572 dom1
= isl_space_domain(isl_space_copy(left
));
1573 dom2
= isl_space_domain(isl_space_copy(right
));
1574 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1576 dom1
= isl_space_range(left
);
1577 dom2
= isl_space_range(right
);
1578 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1580 return isl_space_join(isl_space_reverse(nest1
), nest2
);
1582 isl_space_free(left
);
1583 isl_space_free(right
);
1587 /* Given two spaces { A -> C } and { B -> C }, construct the space
1590 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
1591 __isl_take isl_space
*right
)
1593 isl_space
*ran
, *dom1
, *dom2
, *nest
;
1595 if (isl_space_check_equal_params(left
, right
) < 0)
1598 if (!isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_out
))
1599 isl_die(left
->ctx
, isl_error_invalid
,
1600 "ranges need to match", goto error
);
1602 ran
= isl_space_range(isl_space_copy(left
));
1604 dom1
= isl_space_domain(left
);
1605 dom2
= isl_space_domain(right
);
1606 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1608 return isl_space_join(isl_space_reverse(nest
), ran
);
1610 isl_space_free(left
);
1611 isl_space_free(right
);
1615 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
1616 __isl_take isl_space
*right
)
1618 isl_space
*dom
, *ran1
, *ran2
, *nest
;
1620 if (isl_space_check_equal_params(left
, right
) < 0)
1623 if (!isl_space_tuple_is_equal(left
, isl_dim_in
, right
, isl_dim_in
))
1624 isl_die(left
->ctx
, isl_error_invalid
,
1625 "domains need to match", goto error
);
1627 dom
= isl_space_domain(isl_space_copy(left
));
1629 ran1
= isl_space_range(left
);
1630 ran2
= isl_space_range(right
);
1631 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
1633 return isl_space_join(isl_space_reverse(dom
), nest
);
1635 isl_space_free(left
);
1636 isl_space_free(right
);
1640 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1642 __isl_give isl_space
*isl_space_domain_factor_domain(
1643 __isl_take isl_space
*space
)
1648 if (isl_space_check_domain_is_wrapping(space
) < 0)
1649 return isl_space_free(space
);
1651 nested
= space
->nested
[0];
1652 domain
= isl_space_copy(space
);
1653 domain
= isl_space_drop_dims(domain
, isl_dim_in
,
1654 nested
->n_in
, nested
->n_out
);
1656 return isl_space_free(space
);
1657 if (nested
->tuple_id
[0]) {
1658 domain
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[0]);
1659 if (!domain
->tuple_id
[0])
1662 if (nested
->nested
[0]) {
1663 domain
->nested
[0] = isl_space_copy(nested
->nested
[0]);
1664 if (!domain
->nested
[0])
1668 isl_space_free(space
);
1671 isl_space_free(space
);
1672 isl_space_free(domain
);
1676 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1678 __isl_give isl_space
*isl_space_domain_factor_range(
1679 __isl_take isl_space
*space
)
1684 if (isl_space_check_domain_is_wrapping(space
) < 0)
1685 return isl_space_free(space
);
1687 nested
= space
->nested
[0];
1688 range
= isl_space_copy(space
);
1689 range
= isl_space_drop_dims(range
, isl_dim_in
, 0, nested
->n_in
);
1691 return isl_space_free(space
);
1692 if (nested
->tuple_id
[1]) {
1693 range
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[1]);
1694 if (!range
->tuple_id
[0])
1697 if (nested
->nested
[1]) {
1698 range
->nested
[0] = isl_space_copy(nested
->nested
[1]);
1699 if (!range
->nested
[0])
1703 isl_space_free(space
);
1706 isl_space_free(space
);
1707 isl_space_free(range
);
1711 /* Internal function that selects the domain of the map that is
1712 * embedded in either a set space or the range of a map space.
1713 * In particular, given a space of the form [A -> B], return the space A.
1714 * Given a space of the form A -> [B -> C], return the space A -> B.
1716 static __isl_give isl_space
*range_factor_domain(__isl_take isl_space
*space
)
1724 nested
= space
->nested
[1];
1725 domain
= isl_space_copy(space
);
1726 domain
= isl_space_drop_dims(domain
, isl_dim_out
,
1727 nested
->n_in
, nested
->n_out
);
1729 return isl_space_free(space
);
1730 if (nested
->tuple_id
[0]) {
1731 domain
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[0]);
1732 if (!domain
->tuple_id
[1])
1735 if (nested
->nested
[0]) {
1736 domain
->nested
[1] = isl_space_copy(nested
->nested
[0]);
1737 if (!domain
->nested
[1])
1741 isl_space_free(space
);
1744 isl_space_free(space
);
1745 isl_space_free(domain
);
1749 /* Given a space of the form A -> [B -> C], return the space A -> B.
1751 __isl_give isl_space
*isl_space_range_factor_domain(
1752 __isl_take isl_space
*space
)
1754 if (isl_space_check_range_is_wrapping(space
) < 0)
1755 return isl_space_free(space
);
1757 return range_factor_domain(space
);
1760 /* Given a space of the form [A -> B], return the space A.
1762 static __isl_give isl_space
*set_factor_domain(__isl_take isl_space
*space
)
1766 if (!isl_space_is_wrapping(space
))
1767 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1768 "not a product", return isl_space_free(space
));
1770 return range_factor_domain(space
);
1773 /* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1774 * Given a space of the form [A -> B], return the space A.
1776 __isl_give isl_space
*isl_space_factor_domain(__isl_take isl_space
*space
)
1780 if (isl_space_is_set(space
))
1781 return set_factor_domain(space
);
1782 space
= isl_space_domain_factor_domain(space
);
1783 space
= isl_space_range_factor_domain(space
);
1787 /* Internal function that selects the range of the map that is
1788 * embedded in either a set space or the range of a map space.
1789 * In particular, given a space of the form [A -> B], return the space B.
1790 * Given a space of the form A -> [B -> C], return the space A -> C.
1792 static __isl_give isl_space
*range_factor_range(__isl_take isl_space
*space
)
1800 nested
= space
->nested
[1];
1801 range
= isl_space_copy(space
);
1802 range
= isl_space_drop_dims(range
, isl_dim_out
, 0, nested
->n_in
);
1804 return isl_space_free(space
);
1805 if (nested
->tuple_id
[1]) {
1806 range
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[1]);
1807 if (!range
->tuple_id
[1])
1810 if (nested
->nested
[1]) {
1811 range
->nested
[1] = isl_space_copy(nested
->nested
[1]);
1812 if (!range
->nested
[1])
1816 isl_space_free(space
);
1819 isl_space_free(space
);
1820 isl_space_free(range
);
1824 /* Given a space of the form A -> [B -> C], return the space A -> C.
1826 __isl_give isl_space
*isl_space_range_factor_range(
1827 __isl_take isl_space
*space
)
1829 if (isl_space_check_range_is_wrapping(space
) < 0)
1830 return isl_space_free(space
);
1832 return range_factor_range(space
);
1835 /* Given a space of the form [A -> B], return the space B.
1837 static __isl_give isl_space
*set_factor_range(__isl_take isl_space
*space
)
1841 if (!isl_space_is_wrapping(space
))
1842 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1843 "not a product", return isl_space_free(space
));
1845 return range_factor_range(space
);
1848 /* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1849 * Given a space of the form [A -> B], return the space B.
1851 __isl_give isl_space
*isl_space_factor_range(__isl_take isl_space
*space
)
1855 if (isl_space_is_set(space
))
1856 return set_factor_range(space
);
1857 space
= isl_space_domain_factor_range(space
);
1858 space
= isl_space_range_factor_range(space
);
1862 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*space
)
1865 isl_id
**ids
= NULL
;
1870 ctx
= isl_space_get_ctx(space
);
1871 if (!isl_space_is_set(space
))
1872 isl_die(ctx
, isl_error_invalid
, "not a set space", goto error
);
1873 space
= isl_space_cow(space
);
1876 n_id
= space
->nparam
+ space
->n_out
+ space
->n_out
;
1877 if (n_id
> 0 && space
->ids
) {
1878 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n_id
);
1881 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
1882 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1883 ids
+ space
->nparam
);
1885 space
->n_in
= space
->n_out
;
1890 space
= copy_ids(space
, isl_dim_out
, 0, space
, isl_dim_in
);
1892 isl_id_free(space
->tuple_id
[0]);
1893 space
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[1]);
1894 isl_space_free(space
->nested
[0]);
1895 space
->nested
[0] = isl_space_copy(space
->nested
[1]);
1898 isl_space_free(space
);
1902 __isl_give isl_space
*isl_space_map_from_domain_and_range(
1903 __isl_take isl_space
*domain
, __isl_take isl_space
*range
)
1905 if (!domain
|| !range
)
1907 if (!isl_space_is_set(domain
))
1908 isl_die(isl_space_get_ctx(domain
), isl_error_invalid
,
1909 "domain is not a set space", goto error
);
1910 if (!isl_space_is_set(range
))
1911 isl_die(isl_space_get_ctx(range
), isl_error_invalid
,
1912 "range is not a set space", goto error
);
1913 return isl_space_join(isl_space_reverse(domain
), range
);
1915 isl_space_free(domain
);
1916 isl_space_free(range
);
1920 static __isl_give isl_space
*set_ids(__isl_take isl_space
*space
,
1921 enum isl_dim_type type
,
1922 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
1926 for (i
= 0; i
< n
; ++i
)
1927 space
= set_id(space
, type
, first
+ i
, ids
[i
]);
1932 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*space
)
1937 isl_id
**ids
= NULL
;
1940 equal
= match(space
, isl_dim_in
, space
, isl_dim_out
);
1942 return isl_space_free(space
);
1946 space
= isl_space_cow(space
);
1950 id
= space
->tuple_id
[0];
1951 space
->tuple_id
[0] = space
->tuple_id
[1];
1952 space
->tuple_id
[1] = id
;
1954 nested
= space
->nested
[0];
1955 space
->nested
[0] = space
->nested
[1];
1956 space
->nested
[1] = nested
;
1959 int n_id
= space
->n_in
+ space
->n_out
;
1960 ids
= isl_alloc_array(space
->ctx
, isl_id
*, n_id
);
1963 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
);
1964 get_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
+ space
->n_in
);
1968 space
->n_in
= space
->n_out
;
1972 space
= set_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
);
1973 space
= set_ids(space
, isl_dim_in
, 0, space
->n_in
,
1974 ids
+ space
->n_out
);
1981 isl_space_free(space
);
1985 /* Given a space A -> (B -> C), return the corresponding space
1988 * If the range tuple is named, then the name is only preserved
1989 * if B and C are equal tuples, in which case the output
1990 * of this function is identical to the input.
1992 __isl_give isl_space
*isl_space_range_reverse(__isl_take isl_space
*space
)
1997 if (isl_space_check_range_is_wrapping(space
) < 0)
1998 return isl_space_free(space
);
2000 nested
= isl_space_peek_nested(space
, 1);
2001 equal
= isl_space_tuple_is_equal(nested
, isl_dim_in
,
2002 nested
, isl_dim_out
);
2004 return isl_space_free(space
);
2006 nested
= isl_space_take_nested(space
, 1);
2007 nested
= isl_space_reverse(nested
);
2008 space
= isl_space_restore_nested(space
, 1, nested
);
2010 space
= isl_space_reset_tuple_id(space
, isl_dim_out
);
2015 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*space
,
2016 enum isl_dim_type type
, unsigned first
, unsigned num
)
2024 return isl_space_reset(space
, type
);
2026 if (!valid_dim_type(type
))
2027 isl_die(space
->ctx
, isl_error_invalid
,
2028 "cannot drop dimensions of specified type", goto error
);
2030 if (isl_space_check_range(space
, type
, first
, num
) < 0)
2031 return isl_space_free(space
);
2032 space
= isl_space_cow(space
);
2036 space
= extend_ids(space
);
2039 for (i
= 0; i
< num
; ++i
)
2040 isl_id_free(get_id(space
, type
, first
+ i
));
2041 for (i
= first
+num
; i
< n(space
, type
); ++i
)
2042 set_id(space
, type
, i
- num
, get_id(space
, type
, i
));
2045 get_ids(space
, isl_dim_in
, 0, space
->n_in
,
2046 space
->ids
+ offset(space
, isl_dim_in
) - num
);
2048 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
2049 space
->ids
+ offset(space
, isl_dim_out
) - num
);
2056 case isl_dim_param
: space
->nparam
-= num
; break;
2057 case isl_dim_in
: space
->n_in
-= num
; break;
2058 case isl_dim_out
: space
->n_out
-= num
; break;
2061 space
= isl_space_reset(space
, type
);
2062 if (type
== isl_dim_param
) {
2063 if (space
&& space
->nested
[0] &&
2064 !(space
->nested
[0] = isl_space_drop_dims(space
->nested
[0],
2065 isl_dim_param
, first
, num
)))
2067 if (space
&& space
->nested
[1] &&
2068 !(space
->nested
[1] = isl_space_drop_dims(space
->nested
[1],
2069 isl_dim_param
, first
, num
)))
2074 isl_space_free(space
);
2078 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*space
,
2079 unsigned first
, unsigned n
)
2083 return isl_space_drop_dims(space
, isl_dim_in
, first
, n
);
2086 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*space
,
2087 unsigned first
, unsigned n
)
2091 return isl_space_drop_dims(space
, isl_dim_out
, first
, n
);
2094 /* Remove all parameters from "space".
2096 __isl_give isl_space
*isl_space_drop_all_params(__isl_take isl_space
*space
)
2100 nparam
= isl_space_dim(space
, isl_dim_param
);
2102 return isl_space_free(space
);
2103 return isl_space_drop_dims(space
, isl_dim_param
, 0, nparam
);
2106 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*space
)
2110 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, space
->n_out
);
2111 space
= isl_space_reverse(space
);
2112 space
= mark_as_set(space
);
2116 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*space
)
2120 if (!isl_space_is_set(space
))
2121 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2122 "not a set space", goto error
);
2123 space
= isl_space_reverse(space
);
2124 space
= isl_space_reset(space
, isl_dim_out
);
2127 isl_space_free(space
);
2131 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*space
)
2135 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, space
->n_in
);
2136 space
= mark_as_set(space
);
2140 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*space
)
2144 if (!isl_space_is_set(space
))
2145 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2146 "not a set space", goto error
);
2147 return isl_space_reset(space
, isl_dim_in
);
2149 isl_space_free(space
);
2153 /* Given a map space A -> B, return the map space [A -> B] -> A.
2155 __isl_give isl_space
*isl_space_domain_map(__isl_take isl_space
*space
)
2159 domain
= isl_space_from_range(isl_space_domain(isl_space_copy(space
)));
2160 space
= isl_space_from_domain(isl_space_wrap(space
));
2161 space
= isl_space_join(space
, domain
);
2166 /* Given a map space A -> B, return the map space [A -> B] -> B.
2168 __isl_give isl_space
*isl_space_range_map(__isl_take isl_space
*space
)
2172 range
= isl_space_from_range(isl_space_range(isl_space_copy(space
)));
2173 space
= isl_space_from_domain(isl_space_wrap(space
));
2174 space
= isl_space_join(space
, range
);
2179 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
2181 isl_size n_in
, n_out
;
2183 if (isl_space_is_params(space
))
2185 n_in
= isl_space_dim(space
, isl_dim_in
);
2186 n_out
= isl_space_dim(space
, isl_dim_out
);
2187 if (n_in
< 0 || n_out
< 0)
2188 return isl_space_free(space
);
2189 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, n_in
);
2190 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, n_out
);
2191 space
= mark_as_params(space
);
2195 __isl_give isl_space
*isl_space_set_from_params(__isl_take isl_space
*space
)
2199 if (!isl_space_is_params(space
))
2200 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2201 "not a parameter space", goto error
);
2202 return isl_space_reset(space
, isl_dim_set
);
2204 isl_space_free(space
);
2208 /* Add an unnamed tuple of dimension "dim" to "space".
2209 * This requires "space" to be a parameter or set space.
2211 * In particular, if "space" is a parameter space, then return
2212 * a set space with the given dimension.
2213 * If "space" is a set space, then return a map space
2214 * with "space" as domain and a range of the given dimension.
2216 __isl_give isl_space
*isl_space_add_unnamed_tuple_ui(
2217 __isl_take isl_space
*space
, unsigned dim
)
2219 isl_bool is_params
, is_set
;
2221 is_params
= isl_space_is_params(space
);
2222 is_set
= isl_space_is_set(space
);
2223 if (is_params
< 0 || is_set
< 0)
2224 return isl_space_free(space
);
2225 if (!is_params
&& !is_set
)
2226 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2227 "cannot add tuple to map space",
2228 return isl_space_free(space
));
2230 space
= isl_space_set_from_params(space
);
2232 space
= isl_space_from_domain(space
);
2233 space
= isl_space_add_dims(space
, isl_dim_out
, dim
);
2237 /* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"
2239 * This requires "space" to be a parameter or set space.
2241 __isl_give isl_space
*isl_space_add_named_tuple_id_ui(
2242 __isl_take isl_space
*space
, __isl_take isl_id
*tuple_id
, unsigned dim
)
2244 space
= isl_space_add_unnamed_tuple_ui(space
, dim
);
2245 space
= isl_space_set_tuple_id(space
, isl_dim_out
, tuple_id
);
2249 /* Check that the identifiers in "tuple" do not appear as parameters
2252 static isl_stat
check_fresh_params(__isl_keep isl_space
*space
,
2253 __isl_keep isl_multi_id
*tuple
)
2258 n
= isl_multi_id_size(tuple
);
2260 return isl_stat_error
;
2261 for (i
= 0; i
< n
; ++i
) {
2265 id
= isl_multi_id_get_at(tuple
, i
);
2267 return isl_stat_error
;
2268 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2271 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2272 "parameters not unique", return isl_stat_error
);
2278 /* Add the identifiers in "tuple" as parameters of "space"
2279 * that are known to be fresh.
2281 static __isl_give isl_space
*add_bind_params(__isl_take isl_space
*space
,
2282 __isl_keep isl_multi_id
*tuple
)
2287 first
= isl_space_dim(space
, isl_dim_param
);
2288 n
= isl_multi_id_size(tuple
);
2289 if (first
< 0 || n
< 0)
2290 return isl_space_free(space
);
2291 space
= isl_space_add_dims(space
, isl_dim_param
, n
);
2292 for (i
= 0; i
< n
; ++i
) {
2295 id
= isl_multi_id_get_at(tuple
, i
);
2296 space
= isl_space_set_dim_id(space
,
2297 isl_dim_param
, first
+ i
, id
);
2303 /* Internal function that removes the set tuple of "space",
2304 * which is assumed to correspond to the range space of "tuple", and
2305 * adds the identifiers in "tuple" as fresh parameters.
2306 * In other words, the set dimensions of "space" are reinterpreted
2307 * as parameters, but stay in the same global positions.
2309 __isl_give isl_space
*isl_space_bind_set(__isl_take isl_space
*space
,
2310 __isl_keep isl_multi_id
*tuple
)
2312 isl_space
*tuple_space
;
2314 if (isl_space_check_is_set(space
) < 0)
2315 return isl_space_free(space
);
2316 tuple_space
= isl_multi_id_peek_space(tuple
);
2317 if (isl_space_check_equal_tuples(tuple_space
, space
) < 0)
2318 return isl_space_free(space
);
2319 if (check_fresh_params(space
, tuple
) < 0)
2320 return isl_space_free(space
);
2321 space
= isl_space_params(space
);
2322 space
= add_bind_params(space
, tuple
);
2326 /* Internal function that removes the domain tuple of the map space "space",
2327 * which is assumed to correspond to the range space of "tuple", and
2328 * adds the identifiers in "tuple" as fresh parameters.
2329 * In other words, the domain dimensions of "space" are reinterpreted
2330 * as parameters, but stay in the same global positions.
2332 __isl_give isl_space
*isl_space_bind_map_domain(__isl_take isl_space
*space
,
2333 __isl_keep isl_multi_id
*tuple
)
2335 isl_space
*tuple_space
;
2337 if (isl_space_check_is_map(space
) < 0)
2338 return isl_space_free(space
);
2339 tuple_space
= isl_multi_id_peek_space(tuple
);
2340 if (isl_space_check_domain_tuples(tuple_space
, space
) < 0)
2341 return isl_space_free(space
);
2342 if (check_fresh_params(space
, tuple
) < 0)
2343 return isl_space_free(space
);
2344 space
= isl_space_range(space
);
2345 space
= add_bind_params(space
, tuple
);
2349 /* Internal function that, given a space of the form [A -> B] -> C and
2350 * a tuple of identifiers in A, returns a space B -> C with
2351 * the identifiers in "tuple" added as fresh parameters.
2352 * In other words, the domain dimensions of the wrapped relation
2353 * in the domain of "space" are reinterpreted
2354 * as parameters, but stay in the same global positions.
2356 __isl_give isl_space
*isl_space_bind_domain_wrapped_domain(
2357 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2359 isl_space
*tuple_space
;
2361 if (isl_space_check_is_map(space
) < 0)
2362 return isl_space_free(space
);
2363 tuple_space
= isl_multi_id_peek_space(tuple
);
2364 if (isl_space_check_domain_wrapped_domain_tuples(tuple_space
,
2366 return isl_space_free(space
);
2367 if (check_fresh_params(space
, tuple
) < 0)
2368 return isl_space_free(space
);
2369 space
= isl_space_domain_factor_range(space
);
2370 space
= add_bind_params(space
, tuple
);
2374 /* Insert a domain tuple in "space" corresponding to the set space "domain".
2375 * In particular, if "space" is a parameter space, then the result
2376 * is the set space "domain" combined with the parameters of "space".
2377 * If "space" is a set space, then the result
2378 * is a map space with "domain" as domain and the original space as range.
2380 static __isl_give isl_space
*isl_space_insert_domain(
2381 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
2385 domain
= isl_space_replace_params(domain
, space
);
2387 is_params
= isl_space_is_params(space
);
2388 if (is_params
< 0) {
2389 isl_space_free(domain
);
2390 space
= isl_space_free(space
);
2391 } else if (is_params
) {
2392 isl_space_free(space
);
2395 space
= isl_space_map_from_domain_and_range(domain
, space
);
2400 /* Internal function that introduces a domain in "space"
2401 * corresponding to the range space of "tuple".
2402 * In particular, if "space" is a parameter space, then the result
2403 * is a set space. If "space" is a set space, then the result
2404 * is a map space with the original space as range.
2405 * Parameters that correspond to the identifiers in "tuple" are removed.
2407 * The parameters are removed in reverse order (under the assumption
2408 * that they appear in the same order in "multi") because
2409 * it is slightly more efficient to remove parameters at the end.
2411 * For pretty-printing purposes, the identifiers of the set dimensions
2412 * of the introduced domain are set to the identifiers in "tuple".
2414 __isl_give isl_space
*isl_space_unbind_params_insert_domain(
2415 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2419 isl_space
*tuple_space
;
2421 n
= isl_multi_id_size(tuple
);
2422 if (!space
|| n
< 0)
2423 return isl_space_free(space
);
2424 for (i
= n
- 1; i
>= 0; --i
) {
2428 id
= isl_multi_id_get_id(tuple
, i
);
2430 return isl_space_free(space
);
2431 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2435 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
2437 tuple_space
= isl_multi_id_get_space(tuple
);
2438 for (i
= 0; i
< n
; ++i
) {
2441 id
= isl_multi_id_get_id(tuple
, i
);
2442 tuple_space
= isl_space_set_dim_id(tuple_space
,
2443 isl_dim_set
, i
, id
);
2445 return isl_space_insert_domain(space
, tuple_space
);
2448 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*space
,
2454 is_set
= isl_space_is_set(space
);
2456 return isl_space_free(space
);
2457 if (n_div
== 0 && is_set
&&
2458 space
->nparam
== 0 && space
->n_in
== 0 && space
->n_id
== 0)
2459 return isl_space_reset(space
, isl_dim_out
);
2460 space
= isl_space_cow(space
);
2463 space
->n_out
+= space
->nparam
+ space
->n_in
+ n_div
;
2467 for (i
= 0; i
< space
->n_id
; ++i
)
2468 isl_id_free(get_id(space
, isl_dim_out
, i
));
2470 space
= isl_space_reset(space
, isl_dim_in
);
2471 space
= isl_space_reset(space
, isl_dim_out
);
2472 space
= mark_as_set(space
);
2477 /* Are the two spaces the same, including positions and names of parameters?
2479 isl_bool
isl_space_is_equal(__isl_keep isl_space
*space1
,
2480 __isl_keep isl_space
*space2
)
2484 if (!space1
|| !space2
)
2485 return isl_bool_error
;
2486 if (space1
== space2
)
2487 return isl_bool_true
;
2488 equal
= isl_space_has_equal_params(space1
, space2
);
2489 if (equal
< 0 || !equal
)
2491 return isl_space_has_equal_tuples(space1
, space2
);
2494 /* Do the tuples of "space1" correspond to those of the domain of "space2"?
2495 * That is, is "space1" equal to the domain of "space2", ignoring parameters.
2497 * "space2" is allowed to be a set space, in which case "space1"
2498 * should be a parameter space.
2500 isl_bool
isl_space_has_domain_tuples(__isl_keep isl_space
*space1
,
2501 __isl_keep isl_space
*space2
)
2505 is_set
= isl_space_is_set(space1
);
2506 if (is_set
< 0 || !is_set
)
2508 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2509 space2
, isl_dim_in
);
2512 /* Do the tuples of "space1" correspond to those of the range of "space2"?
2513 * That is, is "space1" equal to the range of "space2", ignoring parameters.
2515 * "space2" is allowed to be the space of a set,
2516 * in which case it should be equal to "space1", ignoring parameters.
2518 isl_bool
isl_space_has_range_tuples(__isl_keep isl_space
*space1
,
2519 __isl_keep isl_space
*space2
)
2523 is_set
= isl_space_is_set(space1
);
2524 if (is_set
< 0 || !is_set
)
2526 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2527 space2
, isl_dim_out
);
2530 /* Check that the tuples of "space1" correspond to those
2531 * of the domain of "space2".
2532 * That is, check that "space1" is equal to the domain of "space2",
2533 * ignoring parameters.
2535 isl_stat
isl_space_check_domain_tuples(__isl_keep isl_space
*space1
,
2536 __isl_keep isl_space
*space2
)
2540 is_equal
= isl_space_has_domain_tuples(space1
, space2
);
2541 return check_match(space1
, is_equal
);
2544 /* Check that the tuples of "space1" correspond to those
2545 * of the domain of the wrapped relation in the domain of "space2".
2546 * That is, check that "space1" is equal to this domain,
2547 * ignoring parameters.
2549 isl_stat
isl_space_check_domain_wrapped_domain_tuples(
2550 __isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
2555 domain
= isl_space_unwrap(isl_space_domain(isl_space_copy(space2
)));
2556 r
= isl_space_check_domain_tuples(space1
, domain
);
2557 isl_space_free(domain
);
2562 /* Is space1 equal to the domain of space2?
2564 * In the internal version we also allow space2 to be the space of a set,
2565 * provided space1 is a parameter space.
2567 isl_bool
isl_space_is_domain_internal(__isl_keep isl_space
*space1
,
2568 __isl_keep isl_space
*space2
)
2570 isl_bool equal_params
;
2572 if (!space1
|| !space2
)
2573 return isl_bool_error
;
2574 equal_params
= isl_space_has_equal_params(space1
, space2
);
2575 if (equal_params
< 0 || !equal_params
)
2576 return equal_params
;
2577 return isl_space_has_domain_tuples(space1
, space2
);
2580 /* Is space1 equal to the domain of space2?
2582 isl_bool
isl_space_is_domain(__isl_keep isl_space
*space1
,
2583 __isl_keep isl_space
*space2
)
2586 return isl_bool_error
;
2587 if (!isl_space_is_map(space2
))
2588 return isl_bool_false
;
2589 return isl_space_is_domain_internal(space1
, space2
);
2592 /* Is space1 equal to the range of space2?
2594 * In the internal version, space2 is allowed to be the space of a set,
2595 * in which case it should be equal to space1.
2597 isl_bool
isl_space_is_range_internal(__isl_keep isl_space
*space1
,
2598 __isl_keep isl_space
*space2
)
2600 isl_bool equal_params
;
2602 if (!space1
|| !space2
)
2603 return isl_bool_error
;
2604 equal_params
= isl_space_has_equal_params(space1
, space2
);
2605 if (equal_params
< 0 || !equal_params
)
2606 return equal_params
;
2607 return isl_space_has_range_tuples(space1
, space2
);
2610 /* Is space1 equal to the range of space2?
2612 isl_bool
isl_space_is_range(__isl_keep isl_space
*space1
,
2613 __isl_keep isl_space
*space2
)
2616 return isl_bool_error
;
2617 if (!isl_space_is_map(space2
))
2618 return isl_bool_false
;
2619 return isl_space_is_range_internal(space1
, space2
);
2622 /* Update "hash" by hashing in the parameters of "space".
2624 static uint32_t isl_hash_params(uint32_t hash
, __isl_keep isl_space
*space
)
2632 isl_hash_byte(hash
, space
->nparam
% 256);
2634 for (i
= 0; i
< space
->nparam
; ++i
) {
2635 id
= get_id(space
, isl_dim_param
, i
);
2636 hash
= isl_hash_id(hash
, id
);
2642 /* Update "hash" by hashing in the tuples of "space".
2643 * Changes in this function should be reflected in isl_hash_tuples_domain.
2645 static uint32_t isl_hash_tuples(uint32_t hash
, __isl_keep isl_space
*space
)
2652 isl_hash_byte(hash
, space
->n_in
% 256);
2653 isl_hash_byte(hash
, space
->n_out
% 256);
2655 id
= tuple_id(space
, isl_dim_in
);
2656 hash
= isl_hash_id(hash
, id
);
2657 id
= tuple_id(space
, isl_dim_out
);
2658 hash
= isl_hash_id(hash
, id
);
2660 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2661 hash
= isl_hash_tuples(hash
, space
->nested
[1]);
2666 /* Update "hash" by hashing in the domain tuple of "space".
2667 * The result of this function is equal to the result of applying
2668 * isl_hash_tuples to the domain of "space".
2670 static uint32_t isl_hash_tuples_domain(uint32_t hash
,
2671 __isl_keep isl_space
*space
)
2678 isl_hash_byte(hash
, 0);
2679 isl_hash_byte(hash
, space
->n_in
% 256);
2681 hash
= isl_hash_id(hash
, &isl_id_none
);
2682 id
= tuple_id(space
, isl_dim_in
);
2683 hash
= isl_hash_id(hash
, id
);
2685 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2690 /* Return a hash value that digests the tuples of "space",
2691 * i.e., that ignores the parameters.
2692 * Changes in this function should be reflected
2693 * in isl_space_get_tuple_domain_hash.
2695 uint32_t isl_space_get_tuple_hash(__isl_keep isl_space
*space
)
2702 hash
= isl_hash_init();
2703 hash
= isl_hash_tuples(hash
, space
);
2708 /* Return the hash value of "space".
2710 uint32_t isl_space_get_full_hash(__isl_keep isl_space
*space
)
2717 hash
= isl_hash_init();
2718 hash
= isl_hash_params(hash
, space
);
2719 hash
= isl_hash_tuples(hash
, space
);
2724 /* Return the hash value of the domain tuple of "space".
2725 * That is, isl_space_get_tuple_domain_hash(space) is equal to
2726 * isl_space_get_tuple_hash(isl_space_domain(space)).
2728 uint32_t isl_space_get_tuple_domain_hash(__isl_keep isl_space
*space
)
2735 hash
= isl_hash_init();
2736 hash
= isl_hash_tuples_domain(hash
, space
);
2741 /* Is "space" the space of a set wrapping a map space?
2743 isl_bool
isl_space_is_wrapping(__isl_keep isl_space
*space
)
2746 return isl_bool_error
;
2748 if (!isl_space_is_set(space
))
2749 return isl_bool_false
;
2751 return isl_bool_ok(space
->nested
[1] != NULL
);
2754 /* Is "space" the space of a map where the domain is a wrapped map space?
2756 isl_bool
isl_space_domain_is_wrapping(__isl_keep isl_space
*space
)
2759 return isl_bool_error
;
2761 if (isl_space_is_set(space
))
2762 return isl_bool_false
;
2764 return isl_bool_ok(space
->nested
[0] != NULL
);
2767 /* Is "space" the space of a map where the range is a wrapped map space?
2769 isl_bool
isl_space_range_is_wrapping(__isl_keep isl_space
*space
)
2772 return isl_bool_error
;
2774 if (isl_space_is_set(space
))
2775 return isl_bool_false
;
2777 return isl_bool_ok(space
->nested
[1] != NULL
);
2780 /* Is "space" a product of two spaces?
2781 * That is, is it a wrapping set space or a map space
2782 * with wrapping domain and range?
2784 isl_bool
isl_space_is_product(__isl_keep isl_space
*space
)
2787 isl_bool is_product
;
2789 is_set
= isl_space_is_set(space
);
2791 return isl_bool_error
;
2793 return isl_space_is_wrapping(space
);
2794 is_product
= isl_space_domain_is_wrapping(space
);
2795 if (is_product
< 0 || !is_product
)
2797 return isl_space_range_is_wrapping(space
);
2800 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*space
)
2807 wrap
= isl_space_set_alloc(space
->ctx
,
2808 space
->nparam
, space
->n_in
+ space
->n_out
);
2810 wrap
= copy_ids(wrap
, isl_dim_param
, 0, space
, isl_dim_param
);
2811 wrap
= copy_ids(wrap
, isl_dim_set
, 0, space
, isl_dim_in
);
2812 wrap
= copy_ids(wrap
, isl_dim_set
, space
->n_in
, space
, isl_dim_out
);
2817 wrap
->nested
[1] = space
;
2821 isl_space_free(space
);
2825 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*space
)
2832 if (!isl_space_is_wrapping(space
))
2833 isl_die(space
->ctx
, isl_error_invalid
, "not a wrapping space",
2836 unwrap
= isl_space_copy(space
->nested
[1]);
2837 isl_space_free(space
);
2841 isl_space_free(space
);
2845 isl_bool
isl_space_is_named_or_nested(__isl_keep isl_space
*space
,
2846 enum isl_dim_type type
)
2848 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
2849 return isl_bool_false
;
2851 return isl_bool_error
;
2852 if (space
->tuple_id
[type
- isl_dim_in
])
2853 return isl_bool_true
;
2854 if (space
->nested
[type
- isl_dim_in
])
2855 return isl_bool_true
;
2856 return isl_bool_false
;
2859 isl_bool
isl_space_may_be_set(__isl_keep isl_space
*space
)
2865 return isl_bool_error
;
2866 if (isl_space_is_set(space
))
2867 return isl_bool_true
;
2868 n_in
= isl_space_dim(space
, isl_dim_in
);
2870 return isl_bool_error
;
2872 return isl_bool_false
;
2873 nested
= isl_space_is_named_or_nested(space
, isl_dim_in
);
2874 if (nested
< 0 || nested
)
2875 return isl_bool_not(nested
);
2876 return isl_bool_true
;
2879 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*space
,
2880 enum isl_dim_type type
)
2882 if (!isl_space_is_named_or_nested(space
, type
))
2885 space
= isl_space_cow(space
);
2889 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
2890 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
2891 isl_space_free(space
->nested
[type
- isl_dim_in
]);
2892 space
->nested
[type
- isl_dim_in
] = NULL
;
2897 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*space
)
2901 if (!space
->nested
[0] && !space
->nested
[1])
2904 if (space
->nested
[0])
2905 space
= isl_space_reset(space
, isl_dim_in
);
2906 if (space
&& space
->nested
[1])
2907 space
= isl_space_reset(space
, isl_dim_out
);
2912 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*space
)
2916 if (!space
->nested
[0])
2919 return isl_space_reset(space
, isl_dim_in
);
2922 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*space
)
2926 if (!space
->nested
[1])
2929 return isl_space_reset(space
, isl_dim_out
);
2932 /* Replace the parameters of dst by those of src.
2934 __isl_give isl_space
*isl_space_replace_params(__isl_take isl_space
*dst
,
2935 __isl_keep isl_space
*src
)
2937 isl_size dst_dim
, src_dim
;
2938 isl_bool equal_params
;
2939 enum isl_dim_type type
= isl_dim_param
;
2941 equal_params
= isl_space_has_equal_params(dst
, src
);
2942 if (equal_params
< 0)
2943 return isl_space_free(dst
);
2947 dst
= isl_space_cow(dst
);
2949 dst_dim
= isl_space_dim(dst
, type
);
2950 src_dim
= isl_space_dim(src
, type
);
2951 if (dst_dim
< 0 || src_dim
< 0)
2954 dst
= isl_space_drop_dims(dst
, type
, 0, dst_dim
);
2955 dst
= isl_space_add_dims(dst
, type
, src_dim
);
2956 dst
= copy_ids(dst
, type
, 0, src
, type
);
2960 for (i
= 0; i
<= 1; ++i
) {
2963 if (!dst
->nested
[i
])
2965 nested
= isl_space_take_nested(dst
, i
);
2966 nested
= isl_space_replace_params(nested
, src
);
2967 dst
= isl_space_restore_nested(dst
, i
, nested
);
2975 isl_space_free(dst
);
2979 /* Given two tuples ("dst_type" in "dst" and "src_type" in "src")
2980 * of the same size, check if any of the dimensions in the "dst" tuple
2981 * have no identifier, while the corresponding dimensions in "src"
2982 * does have an identifier,
2983 * If so, copy the identifier over to "dst".
2985 __isl_give isl_space
*isl_space_copy_ids_if_unset(__isl_take isl_space
*dst
,
2986 enum isl_dim_type dst_type
, __isl_keep isl_space
*src
,
2987 enum isl_dim_type src_type
)
2992 n
= isl_space_dim(dst
, dst_type
);
2994 return isl_space_free(dst
);
2995 for (i
= 0; i
< n
; ++i
) {
2999 set
= isl_space_has_dim_id(dst
, dst_type
, i
);
3001 return isl_space_free(dst
);
3005 set
= isl_space_has_dim_id(src
, src_type
, i
);
3007 return isl_space_free(dst
);
3011 id
= isl_space_get_dim_id(src
, src_type
, i
);
3012 dst
= isl_space_set_dim_id(dst
, dst_type
, i
, id
);
3018 /* Given a space "space" of a set, create a space
3019 * for the lift of the set. In particular, the result
3020 * is of the form lifted[space -> local[..]], with n_local variables in the
3021 * range of the wrapped map.
3023 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*space
,
3026 isl_space
*local_space
;
3031 local_space
= isl_space_dup(space
);
3032 local_space
= isl_space_drop_dims(local_space
, isl_dim_set
, 0,
3034 local_space
= isl_space_add_dims(local_space
, isl_dim_set
, n_local
);
3035 local_space
= isl_space_set_tuple_name(local_space
,
3036 isl_dim_set
, "local");
3037 space
= isl_space_join(isl_space_from_domain(space
),
3038 isl_space_from_range(local_space
));
3039 space
= isl_space_wrap(space
);
3040 space
= isl_space_set_tuple_name(space
, isl_dim_set
, "lifted");
3045 isl_bool
isl_space_can_zip(__isl_keep isl_space
*space
)
3049 is_set
= isl_space_is_set(space
);
3051 return isl_bool_error
;
3053 return isl_bool_false
;
3054 return isl_space_is_product(space
);
3057 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*space
)
3059 isl_space
*dom
, *ran
;
3060 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
3062 if (!isl_space_can_zip(space
))
3063 isl_die(space
->ctx
, isl_error_invalid
, "space cannot be zipped",
3068 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
3069 ran
= isl_space_unwrap(isl_space_range(space
));
3070 dom_dom
= isl_space_domain(isl_space_copy(dom
));
3071 dom_ran
= isl_space_range(dom
);
3072 ran_dom
= isl_space_domain(isl_space_copy(ran
));
3073 ran_ran
= isl_space_range(ran
);
3074 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
3075 isl_space_from_range(ran_dom
));
3076 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
3077 isl_space_from_range(ran_ran
));
3078 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
3079 isl_space_from_range(isl_space_wrap(ran
)));
3081 isl_space_free(space
);
3085 /* Can we apply isl_space_curry to "space"?
3086 * That is, does is it have a map space with a nested relation in its domain?
3088 isl_bool
isl_space_can_curry(__isl_keep isl_space
*space
)
3090 return isl_space_domain_is_wrapping(space
);
3093 /* Given a space (A -> B) -> C, return the corresponding space
3096 __isl_give isl_space
*isl_space_curry(__isl_take isl_space
*space
)
3098 isl_space
*dom
, *ran
;
3099 isl_space
*dom_dom
, *dom_ran
;
3104 if (!isl_space_can_curry(space
))
3105 isl_die(space
->ctx
, isl_error_invalid
,
3106 "space cannot be curried", goto error
);
3108 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
3109 ran
= isl_space_range(space
);
3110 dom_dom
= isl_space_domain(isl_space_copy(dom
));
3111 dom_ran
= isl_space_range(dom
);
3112 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
3113 isl_space_from_range(ran
));
3114 return isl_space_join(isl_space_from_domain(dom_dom
),
3115 isl_space_from_range(isl_space_wrap(ran
)));
3117 isl_space_free(space
);
3121 /* Can isl_space_range_curry be applied to "space"?
3122 * That is, does it have a nested relation in its range,
3123 * the domain of which is itself a nested relation?
3125 isl_bool
isl_space_can_range_curry(__isl_keep isl_space
*space
)
3130 return isl_bool_error
;
3131 can
= isl_space_range_is_wrapping(space
);
3132 if (can
< 0 || !can
)
3134 return isl_space_can_curry(space
->nested
[1]);
3137 /* Given a space A -> ((B -> C) -> D), return the corresponding space
3138 * A -> (B -> (C -> D)).
3140 __isl_give isl_space
*isl_space_range_curry(__isl_take isl_space
*space
)
3147 if (!isl_space_can_range_curry(space
))
3148 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3149 "space range cannot be curried",
3150 return isl_space_free(space
));
3152 nested
= isl_space_take_nested(space
, 1);
3153 nested
= isl_space_curry(nested
);
3154 space
= isl_space_restore_nested(space
, 1, nested
);
3159 /* Can we apply isl_space_uncurry to "space"?
3160 * That is, does it have a map space with a nested relation in its range?
3162 isl_bool
isl_space_can_uncurry(__isl_keep isl_space
*space
)
3164 return isl_space_range_is_wrapping(space
);
3167 /* Given a space A -> (B -> C), return the corresponding space
3170 __isl_give isl_space
*isl_space_uncurry(__isl_take isl_space
*space
)
3172 isl_space
*dom
, *ran
;
3173 isl_space
*ran_dom
, *ran_ran
;
3178 if (!isl_space_can_uncurry(space
))
3179 isl_die(space
->ctx
, isl_error_invalid
,
3180 "space cannot be uncurried",
3181 return isl_space_free(space
));
3183 dom
= isl_space_domain(isl_space_copy(space
));
3184 ran
= isl_space_unwrap(isl_space_range(space
));
3185 ran_dom
= isl_space_domain(isl_space_copy(ran
));
3186 ran_ran
= isl_space_range(ran
);
3187 dom
= isl_space_join(isl_space_from_domain(dom
),
3188 isl_space_from_range(ran_dom
));
3189 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
3190 isl_space_from_range(ran_ran
));
3193 isl_bool
isl_space_has_named_params(__isl_keep isl_space
*space
)
3199 return isl_bool_error
;
3200 if (space
->nparam
== 0)
3201 return isl_bool_true
;
3202 off
= isl_space_offset(space
, isl_dim_param
);
3203 if (off
+ space
->nparam
> space
->n_id
)
3204 return isl_bool_false
;
3205 for (i
= 0; i
< space
->nparam
; ++i
)
3206 if (!space
->ids
[off
+ i
])
3207 return isl_bool_false
;
3208 return isl_bool_true
;
3211 /* Check that "space" has only named parameters, reporting an error
3214 isl_stat
isl_space_check_named_params(__isl_keep isl_space
*space
)
3218 named
= isl_space_has_named_params(space
);
3220 return isl_stat_error
;
3222 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3223 "unexpected unnamed parameters", return isl_stat_error
);
3228 /* Align the initial parameters of space1 to match the order in space2.
3230 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*space1
,
3231 __isl_take isl_space
*space2
)
3233 isl_reordering
*exp
;
3235 if (isl_space_check_named_params(space1
) < 0 ||
3236 isl_space_check_named_params(space2
) < 0)
3239 exp
= isl_parameter_alignment_reordering(space1
, space2
);
3240 exp
= isl_reordering_extend_space(exp
, space1
);
3241 isl_space_free(space2
);
3242 space1
= isl_reordering_get_space(exp
);
3243 isl_reordering_free(exp
);
3246 isl_space_free(space1
);
3247 isl_space_free(space2
);
3251 /* Given the space of set (domain), construct a space for a map
3252 * with as domain the given space and as range the range of "model".
3254 __isl_give isl_space
*isl_space_extend_domain_with_range(
3255 __isl_take isl_space
*space
, __isl_take isl_space
*model
)
3262 space
= isl_space_from_domain(space
);
3263 n_out
= isl_space_dim(model
, isl_dim_out
);
3266 space
= isl_space_add_dims(space
, isl_dim_out
, n_out
);
3267 if (isl_space_has_tuple_id(model
, isl_dim_out
))
3268 space
= isl_space_set_tuple_id(space
, isl_dim_out
,
3269 isl_space_get_tuple_id(model
, isl_dim_out
));
3272 if (model
->nested
[1]) {
3273 isl_space
*nested
= isl_space_copy(model
->nested
[1]);
3274 isl_size n_nested
, n_space
;
3275 nested
= isl_space_align_params(nested
, isl_space_copy(space
));
3276 n_nested
= isl_space_dim(nested
, isl_dim_param
);
3277 n_space
= isl_space_dim(space
, isl_dim_param
);
3278 if (n_nested
< 0 || n_space
< 0)
3280 if (n_nested
> n_space
)
3281 nested
= isl_space_drop_dims(nested
, isl_dim_param
,
3282 n_space
, n_nested
- n_space
);
3285 space
->nested
[1] = nested
;
3287 isl_space_free(model
);
3290 isl_space_free(model
);
3291 isl_space_free(space
);
3295 /* Compare the "type" dimensions of two isl_spaces.
3297 * The order is fairly arbitrary.
3299 static int isl_space_cmp_type(__isl_keep isl_space
*space1
,
3300 __isl_keep isl_space
*space2
, enum isl_dim_type type
)
3303 isl_size dim1
, dim2
;
3304 isl_space
*nested1
, *nested2
;
3306 dim1
= isl_space_dim(space1
, type
);
3307 dim2
= isl_space_dim(space2
, type
);
3308 if (dim1
< 0 || dim2
< 0)
3313 cmp
= isl_id_cmp(tuple_id(space1
, type
), tuple_id(space2
, type
));
3317 nested1
= nested(space1
, type
);
3318 nested2
= nested(space2
, type
);
3319 if (!nested1
!= !nested2
)
3320 return !nested1
- !nested2
;
3323 return isl_space_cmp(nested1
, nested2
);
3328 /* Compare two isl_spaces.
3330 * The order is fairly arbitrary.
3332 int isl_space_cmp(__isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
3337 if (space1
== space2
)
3344 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_param
);
3347 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_in
);
3350 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_out
);
3354 if (!space1
->ids
&& !space2
->ids
)
3357 for (i
= 0; i
< n(space1
, isl_dim_param
); ++i
) {
3358 cmp
= isl_id_cmp(get_id(space1
, isl_dim_param
, i
),
3359 get_id(space2
, isl_dim_param
, i
));