2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2013-2014 Ecole Normale Superieure
5 * Copyright 2018 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 __isl_give isl_space
*isl_space_set_alloc(isl_ctx
*ctx
,
125 unsigned nparam
, unsigned dim
)
128 space
= isl_space_alloc(ctx
, nparam
, 0, dim
);
129 space
= mark_as_set(space
);
133 /* Mark the space as being that of a parameter domain, by setting
134 * both tuples to isl_id_none.
136 static __isl_give isl_space
*mark_as_params(isl_space
*space
)
140 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
141 space
= isl_space_set_tuple_id(space
, isl_dim_out
, &isl_id_none
);
145 /* Is the space that of a parameter domain?
147 isl_bool
isl_space_is_params(__isl_keep isl_space
*space
)
150 return isl_bool_error
;
151 if (space
->n_in
!= 0 || space
->nested
[0] ||
152 space
->n_out
!= 0 || space
->nested
[1])
153 return isl_bool_false
;
154 if (space
->tuple_id
[0] != &isl_id_none
)
155 return isl_bool_false
;
156 if (space
->tuple_id
[1] != &isl_id_none
)
157 return isl_bool_false
;
158 return isl_bool_true
;
161 /* Create a space for a parameter domain.
163 __isl_give isl_space
*isl_space_params_alloc(isl_ctx
*ctx
, unsigned nparam
)
166 space
= isl_space_alloc(ctx
, nparam
, 0, 0);
167 space
= mark_as_params(space
);
171 /* Create a space for a parameter domain, without any parameters.
173 __isl_give isl_space
*isl_space_unit(isl_ctx
*ctx
)
175 return isl_space_params_alloc(ctx
, 0);
178 static isl_size
global_pos(__isl_keep isl_space
*space
,
179 enum isl_dim_type type
, unsigned pos
)
181 if (isl_space_check_range(space
, type
, pos
, 1) < 0)
182 return isl_size_error
;
188 return pos
+ space
->nparam
;
190 return pos
+ space
->nparam
+ space
->n_in
;
192 isl_assert(isl_space_get_ctx(space
), 0, return isl_size_error
);
194 return isl_size_error
;
197 /* Extend length of ids array to the total number of dimensions.
199 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*space
)
205 dim
= isl_space_dim(space
, isl_dim_all
);
207 return isl_space_free(space
);
208 if (dim
<= space
->n_id
)
212 space
->ids
= isl_calloc_array(space
->ctx
, isl_id
*, dim
);
216 ids
= isl_realloc_array(space
->ctx
, space
->ids
, isl_id
*, dim
);
220 for (i
= space
->n_id
; i
< dim
; ++i
)
221 space
->ids
[i
] = NULL
;
228 isl_space_free(space
);
232 static __isl_give isl_space
*set_id(__isl_take isl_space
*space
,
233 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
237 space
= isl_space_cow(space
);
239 gpos
= global_pos(space
, type
, pos
);
243 if (gpos
>= space
->n_id
) {
246 space
= extend_ids(space
);
251 space
->ids
[gpos
] = id
;
256 isl_space_free(space
);
260 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*space
,
261 enum isl_dim_type type
, unsigned pos
)
265 gpos
= global_pos(space
, type
, pos
);
268 if (gpos
>= space
->n_id
)
270 return space
->ids
[gpos
];
273 static unsigned offset(__isl_keep isl_space
*space
, enum isl_dim_type type
)
276 case isl_dim_param
: return 0;
277 case isl_dim_in
: return space
->nparam
;
278 case isl_dim_out
: return space
->nparam
+ space
->n_in
;
283 static unsigned n(__isl_keep isl_space
*space
, enum isl_dim_type type
)
286 case isl_dim_param
: return space
->nparam
;
287 case isl_dim_in
: return space
->n_in
;
288 case isl_dim_out
: return space
->n_out
;
290 return space
->nparam
+ space
->n_in
+ space
->n_out
;
295 isl_size
isl_space_dim(__isl_keep isl_space
*space
, enum isl_dim_type type
)
298 return isl_size_error
;
299 return n(space
, type
);
302 unsigned isl_space_offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
306 return offset(dim
, type
);
309 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
310 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
311 enum isl_dim_type src_type
)
319 for (i
= 0; i
< n(src
, src_type
); ++i
) {
320 id
= get_id(src
, src_type
, i
);
323 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
330 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*space
)
335 dup
= isl_space_alloc(space
->ctx
,
336 space
->nparam
, space
->n_in
, space
->n_out
);
339 if (space
->tuple_id
[0] &&
340 !(dup
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[0])))
342 if (space
->tuple_id
[1] &&
343 !(dup
->tuple_id
[1] = isl_id_copy(space
->tuple_id
[1])))
345 if (space
->nested
[0] &&
346 !(dup
->nested
[0] = isl_space_copy(space
->nested
[0])))
348 if (space
->nested
[1] &&
349 !(dup
->nested
[1] = isl_space_copy(space
->nested
[1])))
353 dup
= copy_ids(dup
, isl_dim_param
, 0, space
, isl_dim_param
);
354 dup
= copy_ids(dup
, isl_dim_in
, 0, space
, isl_dim_in
);
355 dup
= copy_ids(dup
, isl_dim_out
, 0, space
, isl_dim_out
);
362 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*space
)
370 return isl_space_dup(space
);
373 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*dim
)
382 __isl_null isl_space
*isl_space_free(__isl_take isl_space
*space
)
389 if (--space
->ref
> 0)
392 isl_id_free(space
->tuple_id
[0]);
393 isl_id_free(space
->tuple_id
[1]);
395 isl_space_free(space
->nested
[0]);
396 isl_space_free(space
->nested
[1]);
398 for (i
= 0; i
< space
->n_id
; ++i
)
399 isl_id_free(space
->ids
[i
]);
401 isl_ctx_deref(space
->ctx
);
408 /* Check if "s" is a valid dimension or tuple name.
409 * We currently only forbid names that look like a number.
411 * s is assumed to be non-NULL.
413 static int name_ok(isl_ctx
*ctx
, const char *s
)
418 dummy
= strtol(s
, &p
, 0);
420 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
426 /* Is it possible for the given dimension type to have a tuple id?
428 static int space_can_have_id(__isl_keep isl_space
*space
,
429 enum isl_dim_type type
)
433 if (isl_space_is_params(space
))
434 isl_die(space
->ctx
, isl_error_invalid
,
435 "parameter spaces don't have tuple ids", return 0);
436 if (isl_space_is_set(space
) && type
!= isl_dim_set
)
437 isl_die(space
->ctx
, isl_error_invalid
,
438 "set spaces can only have a set id", return 0);
439 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
440 isl_die(space
->ctx
, isl_error_invalid
,
441 "only input, output and set tuples can have ids",
447 /* Does the tuple have an id?
449 isl_bool
isl_space_has_tuple_id(__isl_keep isl_space
*space
,
450 enum isl_dim_type type
)
452 if (!space_can_have_id(space
, type
))
453 return isl_bool_error
;
454 return isl_bool_ok(space
->tuple_id
[type
- isl_dim_in
] != NULL
);
457 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*space
,
458 enum isl_dim_type type
)
464 has_id
= isl_space_has_tuple_id(space
, type
);
468 isl_die(space
->ctx
, isl_error_invalid
,
469 "tuple has no id", return NULL
);
470 return isl_id_copy(space
->tuple_id
[type
- isl_dim_in
]);
473 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*space
,
474 enum isl_dim_type type
, __isl_take isl_id
*id
)
476 space
= isl_space_cow(space
);
479 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
480 isl_die(space
->ctx
, isl_error_invalid
,
481 "only input, output and set tuples can have names",
484 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
485 space
->tuple_id
[type
- isl_dim_in
] = id
;
490 isl_space_free(space
);
494 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*space
,
495 enum isl_dim_type type
)
497 space
= isl_space_cow(space
);
500 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
501 isl_die(space
->ctx
, isl_error_invalid
,
502 "only input, output and set tuples can have names",
505 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
506 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
510 isl_space_free(space
);
514 /* Set the id of the given dimension of "space" to "id".
515 * If the dimension already has an id, then it is replaced.
516 * If the dimension is a parameter, then we need to change it
517 * in the nested spaces (if any) as well.
519 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*space
,
520 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
522 space
= isl_space_cow(space
);
526 if (type
== isl_dim_param
) {
529 for (i
= 0; i
< 2; ++i
) {
530 if (!space
->nested
[i
])
533 isl_space_set_dim_id(space
->nested
[i
],
534 type
, pos
, isl_id_copy(id
));
535 if (!space
->nested
[i
])
540 isl_id_free(get_id(space
, type
, pos
));
541 return set_id(space
, type
, pos
, id
);
544 isl_space_free(space
);
548 /* Reset the id of the given dimension of "space".
549 * If the dimension already has an id, then it is removed.
550 * If the dimension is a parameter, then we need to reset it
551 * in the nested spaces (if any) as well.
553 __isl_give isl_space
*isl_space_reset_dim_id(__isl_take isl_space
*space
,
554 enum isl_dim_type type
, unsigned pos
)
556 space
= isl_space_cow(space
);
560 if (type
== isl_dim_param
) {
563 for (i
= 0; i
< 2; ++i
) {
564 if (!space
->nested
[i
])
567 isl_space_reset_dim_id(space
->nested
[i
],
569 if (!space
->nested
[i
])
574 isl_id_free(get_id(space
, type
, pos
));
575 return set_id(space
, type
, pos
, NULL
);
577 isl_space_free(space
);
581 isl_bool
isl_space_has_dim_id(__isl_keep isl_space
*space
,
582 enum isl_dim_type type
, unsigned pos
)
585 return isl_bool_error
;
586 return isl_bool_ok(get_id(space
, type
, pos
) != NULL
);
589 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*space
,
590 enum isl_dim_type type
, unsigned pos
)
594 if (!get_id(space
, type
, pos
))
595 isl_die(space
->ctx
, isl_error_invalid
,
596 "dim has no id", return NULL
);
597 return isl_id_copy(get_id(space
, type
, pos
));
600 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*space
,
601 enum isl_dim_type type
, const char *s
)
609 return isl_space_reset_tuple_id(space
, type
);
611 if (!name_ok(space
->ctx
, s
))
614 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
615 return isl_space_set_tuple_id(space
, type
, id
);
617 isl_space_free(space
);
621 /* Does the tuple have a name?
623 isl_bool
isl_space_has_tuple_name(__isl_keep isl_space
*space
,
624 enum isl_dim_type type
)
628 if (!space_can_have_id(space
, type
))
629 return isl_bool_error
;
630 id
= space
->tuple_id
[type
- isl_dim_in
];
631 return isl_bool_ok(id
&& id
->name
);
634 __isl_keep
const char *isl_space_get_tuple_name(__isl_keep isl_space
*space
,
635 enum isl_dim_type type
)
640 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
642 id
= space
->tuple_id
[type
- isl_dim_in
];
643 return id
? id
->name
: NULL
;
646 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*space
,
647 enum isl_dim_type type
, unsigned pos
,
655 return isl_space_reset_dim_id(space
, type
, pos
);
656 if (!name_ok(space
->ctx
, s
))
658 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
659 return isl_space_set_dim_id(space
, type
, pos
, id
);
661 isl_space_free(space
);
665 /* Does the given dimension have a name?
667 isl_bool
isl_space_has_dim_name(__isl_keep isl_space
*space
,
668 enum isl_dim_type type
, unsigned pos
)
673 return isl_bool_error
;
674 id
= get_id(space
, type
, pos
);
675 return isl_bool_ok(id
&& id
->name
);
678 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*space
,
679 enum isl_dim_type type
, unsigned pos
)
681 isl_id
*id
= get_id(space
, type
, pos
);
682 return id
? id
->name
: NULL
;
685 int isl_space_find_dim_by_id(__isl_keep isl_space
*space
,
686 enum isl_dim_type type
, __isl_keep isl_id
*id
)
692 n
= isl_space_dim(space
, type
);
696 offset
= isl_space_offset(space
, type
);
697 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
)
698 if (space
->ids
[offset
+ i
] == id
)
704 int isl_space_find_dim_by_name(__isl_keep isl_space
*space
,
705 enum isl_dim_type type
, const char *name
)
711 n
= isl_space_dim(space
, type
);
715 offset
= isl_space_offset(space
, type
);
716 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
) {
717 isl_id
*id
= get_id(space
, type
, i
);
718 if (id
&& id
->name
&& !strcmp(id
->name
, name
))
725 /* Reset the user pointer on all identifiers of parameters and tuples
728 __isl_give isl_space
*isl_space_reset_user(__isl_take isl_space
*space
)
738 ctx
= isl_space_get_ctx(space
);
740 for (i
= 0; i
< space
->nparam
&& i
< space
->n_id
; ++i
) {
741 if (!isl_id_get_user(space
->ids
[i
]))
743 space
= isl_space_cow(space
);
746 name
= isl_id_get_name(space
->ids
[i
]);
747 id
= isl_id_alloc(ctx
, name
, NULL
);
748 isl_id_free(space
->ids
[i
]);
751 return isl_space_free(space
);
754 for (i
= 0; i
< 2; ++i
) {
755 if (!space
->tuple_id
[i
])
757 if (!isl_id_get_user(space
->tuple_id
[i
]))
759 space
= isl_space_cow(space
);
762 name
= isl_id_get_name(space
->tuple_id
[i
]);
763 id
= isl_id_alloc(ctx
, name
, NULL
);
764 isl_id_free(space
->tuple_id
[i
]);
765 space
->tuple_id
[i
] = id
;
767 return isl_space_free(space
);
770 for (i
= 0; i
< 2; ++i
) {
771 if (!space
->nested
[i
])
773 space
= isl_space_cow(space
);
776 space
->nested
[i
] = isl_space_reset_user(space
->nested
[i
]);
777 if (!space
->nested
[i
])
778 return isl_space_free(space
);
784 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*dim
,
785 enum isl_dim_type type
)
789 if (type
== isl_dim_in
)
790 return dim
->tuple_id
[0];
791 if (type
== isl_dim_out
)
792 return dim
->tuple_id
[1];
796 static __isl_keep isl_space
*nested(__isl_keep isl_space
*dim
,
797 enum isl_dim_type type
)
801 if (type
== isl_dim_in
)
802 return dim
->nested
[0];
803 if (type
== isl_dim_out
)
804 return dim
->nested
[1];
808 /* Are the two spaces the same, apart from positions and names of parameters?
810 isl_bool
isl_space_has_equal_tuples(__isl_keep isl_space
*space1
,
811 __isl_keep isl_space
*space2
)
813 if (!space1
|| !space2
)
814 return isl_bool_error
;
815 if (space1
== space2
)
816 return isl_bool_true
;
817 return isl_space_tuple_is_equal(space1
, isl_dim_in
,
818 space2
, isl_dim_in
) &&
819 isl_space_tuple_is_equal(space1
, isl_dim_out
,
820 space2
, isl_dim_out
);
823 /* Check that the two spaces are the same,
824 * apart from positions and names of parameters.
826 isl_stat
isl_space_check_equal_tuples(__isl_keep isl_space
*space1
,
827 __isl_keep isl_space
*space2
)
831 is_equal
= isl_space_has_equal_tuples(space1
, space2
);
833 return isl_stat_error
;
835 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
836 "incompatible spaces", return isl_stat_error
);
841 /* Check if the tuple of type "type1" of "space1" is the same as
842 * the tuple of type "type2" of "space2".
844 * That is, check if the tuples have the same identifier, the same dimension
845 * and the same internal structure.
846 * The identifiers of the dimensions inside the tuples do not affect the result.
848 * Note that this function only checks the tuples themselves.
849 * If nested tuples are involved, then we need to be careful not
850 * to have result affected by possibly differing parameters
851 * in those nested tuples.
853 isl_bool
isl_space_tuple_is_equal(__isl_keep isl_space
*space1
,
854 enum isl_dim_type type1
, __isl_keep isl_space
*space2
,
855 enum isl_dim_type type2
)
858 isl_space
*nested1
, *nested2
;
860 if (!space1
|| !space2
)
861 return isl_bool_error
;
863 if (space1
== space2
&& type1
== type2
)
864 return isl_bool_true
;
866 if (n(space1
, type1
) != n(space2
, type2
))
867 return isl_bool_false
;
868 id1
= tuple_id(space1
, type1
);
869 id2
= tuple_id(space2
, type2
);
871 return isl_bool_false
;
872 if (id1
&& id1
!= id2
)
873 return isl_bool_false
;
874 nested1
= nested(space1
, type1
);
875 nested2
= nested(space2
, type2
);
876 if (!nested1
^ !nested2
)
877 return isl_bool_false
;
878 if (nested1
&& !isl_space_has_equal_tuples(nested1
, nested2
))
879 return isl_bool_false
;
880 return isl_bool_true
;
883 static isl_bool
match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
884 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
888 if (space1
== space2
&& type1
== type2
)
889 return isl_bool_true
;
891 if (!isl_space_tuple_is_equal(space1
, type1
, space2
, type2
))
892 return isl_bool_false
;
894 if (!space1
->ids
&& !space2
->ids
)
895 return isl_bool_true
;
897 for (i
= 0; i
< n(space1
, type1
); ++i
) {
898 if (get_id(space1
, type1
, i
) != get_id(space2
, type2
, i
))
899 return isl_bool_false
;
901 return isl_bool_true
;
904 /* Do "space1" and "space2" have the same parameters?
906 isl_bool
isl_space_has_equal_params(__isl_keep isl_space
*space1
,
907 __isl_keep isl_space
*space2
)
909 if (!space1
|| !space2
)
910 return isl_bool_error
;
912 return match(space1
, isl_dim_param
, space2
, isl_dim_param
);
915 /* Do "space1" and "space2" have the same identifiers for all
916 * the tuple variables?
918 isl_bool
isl_space_has_equal_ids(__isl_keep isl_space
*space1
,
919 __isl_keep isl_space
*space2
)
923 if (!space1
|| !space2
)
924 return isl_bool_error
;
926 equal
= match(space1
, isl_dim_in
, space2
, isl_dim_in
);
927 if (equal
< 0 || !equal
)
929 return match(space1
, isl_dim_out
, space2
, isl_dim_out
);
932 isl_bool
isl_space_match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
933 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
935 if (!space1
|| !space2
)
936 return isl_bool_error
;
938 return match(space1
, type1
, space2
, type2
);
941 static void get_ids(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
942 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
946 for (i
= 0; i
< n
; ++i
)
947 ids
[i
] = get_id(dim
, type
, first
+ i
);
950 static __isl_give isl_space
*space_extend(__isl_take isl_space
*space
,
951 unsigned nparam
, unsigned n_in
, unsigned n_out
)
957 if (space
->nparam
== nparam
&&
958 space
->n_in
== n_in
&& space
->n_out
== n_out
)
961 isl_assert(space
->ctx
, space
->nparam
<= nparam
, goto error
);
962 isl_assert(space
->ctx
, space
->n_in
<= n_in
, goto error
);
963 isl_assert(space
->ctx
, space
->n_out
<= n_out
, goto error
);
965 space
= isl_space_cow(space
);
971 n
= nparam
+ n_in
+ n_out
;
972 if (n
< nparam
|| n
< n_in
|| n
< n_out
)
973 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
974 "overflow in total number of dimensions",
976 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n
);
979 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
980 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
+ nparam
);
981 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
982 ids
+ nparam
+ n_in
);
985 space
->n_id
= nparam
+ n_in
+ n_out
;
987 space
->nparam
= nparam
;
989 space
->n_out
= n_out
;
994 isl_space_free(space
);
998 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*space
,
999 unsigned nparam
, unsigned n_in
, unsigned n_out
)
1001 return space_extend(space
, nparam
, n_in
, n_out
);
1004 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*space
,
1005 enum isl_dim_type type
, unsigned n
)
1007 space
= isl_space_reset(space
, type
);
1012 space
= space_extend(space
,
1013 space
->nparam
+ n
, space
->n_in
, space
->n_out
);
1014 if (space
&& space
->nested
[0] &&
1015 !(space
->nested
[0] = isl_space_add_dims(space
->nested
[0],
1018 if (space
&& space
->nested
[1] &&
1019 !(space
->nested
[1] = isl_space_add_dims(space
->nested
[1],
1024 return space_extend(space
,
1025 space
->nparam
, space
->n_in
+ n
, space
->n_out
);
1027 return space_extend(space
,
1028 space
->nparam
, space
->n_in
, space
->n_out
+ n
);
1030 isl_die(space
->ctx
, isl_error_invalid
,
1031 "cannot add dimensions of specified type", goto error
);
1034 isl_space_free(space
);
1038 /* Add a parameter with identifier "id" to "space", provided
1039 * it does not already appear in "space".
1041 __isl_give isl_space
*isl_space_add_param_id(__isl_take isl_space
*space
,
1042 __isl_take isl_id
*id
)
1049 if (isl_space_find_dim_by_id(space
, isl_dim_param
, id
) >= 0) {
1054 pos
= isl_space_dim(space
, isl_dim_param
);
1057 space
= isl_space_add_dims(space
, isl_dim_param
, 1);
1058 space
= isl_space_set_dim_id(space
, isl_dim_param
, pos
, id
);
1062 isl_space_free(space
);
1067 static int valid_dim_type(enum isl_dim_type type
)
1080 #define TYPE isl_space
1081 #include "check_type_range_templ.c"
1083 /* Insert "n" dimensions of type "type" at position "pos".
1084 * If we are inserting parameters, then they are also inserted in
1085 * any nested spaces.
1087 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*space
,
1088 enum isl_dim_type type
, unsigned pos
, unsigned n
)
1091 isl_id
**ids
= NULL
;
1096 return isl_space_reset(space
, type
);
1098 ctx
= isl_space_get_ctx(space
);
1099 if (!valid_dim_type(type
))
1100 isl_die(ctx
, isl_error_invalid
,
1101 "cannot insert dimensions of specified type",
1104 if (isl_space_check_range(space
, type
, pos
, 0) < 0)
1105 return isl_space_free(space
);
1107 space
= isl_space_cow(space
);
1112 enum isl_dim_type t
, o
= isl_dim_param
;
1115 ids
= isl_calloc_array(ctx
, isl_id
*,
1116 space
->nparam
+ space
->n_in
+ space
->n_out
+ n
);
1120 s
[isl_dim_param
- o
] = space
->nparam
;
1121 s
[isl_dim_in
- o
] = space
->n_in
;
1122 s
[isl_dim_out
- o
] = space
->n_out
;
1123 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1125 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1128 get_ids(space
, t
, 0, pos
, ids
+ off
);
1130 get_ids(space
, t
, pos
, s
[t
- o
] - pos
,
1132 off
+= s
[t
- o
] - pos
;
1137 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
+ n
;
1140 case isl_dim_param
: space
->nparam
+= n
; break;
1141 case isl_dim_in
: space
->n_in
+= n
; break;
1142 case isl_dim_out
: space
->n_out
+= n
; break;
1145 space
= isl_space_reset(space
, type
);
1147 if (type
== isl_dim_param
) {
1148 if (space
&& space
->nested
[0] &&
1149 !(space
->nested
[0] = isl_space_insert_dims(space
->nested
[0],
1150 isl_dim_param
, pos
, n
)))
1152 if (space
&& space
->nested
[1] &&
1153 !(space
->nested
[1] = isl_space_insert_dims(space
->nested
[1],
1154 isl_dim_param
, pos
, n
)))
1160 isl_space_free(space
);
1164 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*space
,
1165 enum isl_dim_type dst_type
, unsigned dst_pos
,
1166 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1170 space
= isl_space_reset(space
, src_type
);
1171 space
= isl_space_reset(space
, dst_type
);
1177 if (isl_space_check_range(space
, src_type
, src_pos
, n
) < 0)
1178 return isl_space_free(space
);
1180 if (dst_type
== src_type
&& dst_pos
== src_pos
)
1183 isl_assert(space
->ctx
, dst_type
!= src_type
, goto error
);
1185 space
= isl_space_cow(space
);
1191 enum isl_dim_type t
, o
= isl_dim_param
;
1194 ids
= isl_calloc_array(space
->ctx
, isl_id
*,
1195 space
->nparam
+ space
->n_in
+ space
->n_out
);
1199 s
[isl_dim_param
- o
] = space
->nparam
;
1200 s
[isl_dim_in
- o
] = space
->n_in
;
1201 s
[isl_dim_out
- o
] = space
->n_out
;
1202 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1203 if (t
== dst_type
) {
1204 get_ids(space
, t
, 0, dst_pos
, ids
+ off
);
1206 get_ids(space
, src_type
, src_pos
, n
, ids
+ off
);
1208 get_ids(space
, t
, dst_pos
, s
[t
- o
] - dst_pos
,
1210 off
+= s
[t
- o
] - dst_pos
;
1211 } else if (t
== src_type
) {
1212 get_ids(space
, t
, 0, src_pos
, ids
+ off
);
1214 get_ids(space
, t
, src_pos
+ n
,
1215 s
[t
- o
] - src_pos
- n
, ids
+ off
);
1216 off
+= s
[t
- o
] - src_pos
- n
;
1218 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1224 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
;
1228 case isl_dim_param
: space
->nparam
+= n
; break;
1229 case isl_dim_in
: space
->n_in
+= n
; break;
1230 case isl_dim_out
: space
->n_out
+= n
; break;
1235 case isl_dim_param
: space
->nparam
-= n
; break;
1236 case isl_dim_in
: space
->n_in
-= n
; break;
1237 case isl_dim_out
: space
->n_out
-= n
; break;
1241 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
1244 for (i
= 0; i
< 2; ++i
) {
1245 if (!space
->nested
[i
])
1247 space
->nested
[i
] = isl_space_replace_params(space
->nested
[i
],
1249 if (!space
->nested
[i
])
1255 isl_space_free(space
);
1259 /* Check that "space1" and "space2" have the same parameters,
1260 * reporting an error if they do not.
1262 isl_stat
isl_space_check_equal_params(__isl_keep isl_space
*space1
,
1263 __isl_keep isl_space
*space2
)
1267 equal
= isl_space_has_equal_params(space1
, space2
);
1269 return isl_stat_error
;
1271 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
1272 "parameters need to match", return isl_stat_error
);
1276 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
1277 __isl_take isl_space
*right
)
1281 if (isl_space_check_equal_params(left
, right
) < 0)
1284 isl_assert(left
->ctx
,
1285 isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_in
),
1288 space
= isl_space_alloc(left
->ctx
,
1289 left
->nparam
, left
->n_in
, right
->n_out
);
1293 space
= copy_ids(space
, isl_dim_param
, 0, left
, isl_dim_param
);
1294 space
= copy_ids(space
, isl_dim_in
, 0, left
, isl_dim_in
);
1295 space
= copy_ids(space
, isl_dim_out
, 0, right
, isl_dim_out
);
1297 if (space
&& left
->tuple_id
[0] &&
1298 !(space
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
1300 if (space
&& right
->tuple_id
[1] &&
1301 !(space
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
1303 if (space
&& left
->nested
[0] &&
1304 !(space
->nested
[0] = isl_space_copy(left
->nested
[0])))
1306 if (space
&& right
->nested
[1] &&
1307 !(space
->nested
[1] = isl_space_copy(right
->nested
[1])))
1310 isl_space_free(left
);
1311 isl_space_free(right
);
1315 isl_space_free(left
);
1316 isl_space_free(right
);
1320 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1321 * { [A -> B] -> [C -> D] }.
1322 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1324 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
1325 __isl_take isl_space
*right
)
1327 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
1330 if (!left
|| !right
)
1333 is_set
= isl_space_is_set(left
);
1334 if (is_set
!= isl_space_is_set(right
))
1335 isl_die(isl_space_get_ctx(left
), isl_error_invalid
,
1336 "expecting either two set spaces or two map spaces",
1339 return isl_space_range_product(left
, right
);
1341 if (isl_space_check_equal_params(left
, right
) < 0)
1344 dom1
= isl_space_domain(isl_space_copy(left
));
1345 dom2
= isl_space_domain(isl_space_copy(right
));
1346 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1348 dom1
= isl_space_range(left
);
1349 dom2
= isl_space_range(right
);
1350 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1352 return isl_space_join(isl_space_reverse(nest1
), nest2
);
1354 isl_space_free(left
);
1355 isl_space_free(right
);
1359 /* Given two spaces { A -> C } and { B -> C }, construct the space
1362 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
1363 __isl_take isl_space
*right
)
1365 isl_space
*ran
, *dom1
, *dom2
, *nest
;
1367 if (isl_space_check_equal_params(left
, right
) < 0)
1370 if (!isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_out
))
1371 isl_die(left
->ctx
, isl_error_invalid
,
1372 "ranges need to match", goto error
);
1374 ran
= isl_space_range(isl_space_copy(left
));
1376 dom1
= isl_space_domain(left
);
1377 dom2
= isl_space_domain(right
);
1378 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1380 return isl_space_join(isl_space_reverse(nest
), ran
);
1382 isl_space_free(left
);
1383 isl_space_free(right
);
1387 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
1388 __isl_take isl_space
*right
)
1390 isl_space
*dom
, *ran1
, *ran2
, *nest
;
1392 if (isl_space_check_equal_params(left
, right
) < 0)
1395 if (!isl_space_tuple_is_equal(left
, isl_dim_in
, right
, isl_dim_in
))
1396 isl_die(left
->ctx
, isl_error_invalid
,
1397 "domains need to match", goto error
);
1399 dom
= isl_space_domain(isl_space_copy(left
));
1401 ran1
= isl_space_range(left
);
1402 ran2
= isl_space_range(right
);
1403 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
1405 return isl_space_join(isl_space_reverse(dom
), nest
);
1407 isl_space_free(left
);
1408 isl_space_free(right
);
1412 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1414 __isl_give isl_space
*isl_space_domain_factor_domain(
1415 __isl_take isl_space
*space
)
1422 if (!isl_space_domain_is_wrapping(space
))
1423 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1424 "domain not a product", return isl_space_free(space
));
1426 nested
= space
->nested
[0];
1427 domain
= isl_space_copy(space
);
1428 domain
= isl_space_drop_dims(domain
, isl_dim_in
,
1429 nested
->n_in
, nested
->n_out
);
1431 return isl_space_free(space
);
1432 if (nested
->tuple_id
[0]) {
1433 domain
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[0]);
1434 if (!domain
->tuple_id
[0])
1437 if (nested
->nested
[0]) {
1438 domain
->nested
[0] = isl_space_copy(nested
->nested
[0]);
1439 if (!domain
->nested
[0])
1443 isl_space_free(space
);
1446 isl_space_free(space
);
1447 isl_space_free(domain
);
1451 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1453 __isl_give isl_space
*isl_space_domain_factor_range(
1454 __isl_take isl_space
*space
)
1461 if (!isl_space_domain_is_wrapping(space
))
1462 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1463 "domain not a product", return isl_space_free(space
));
1465 nested
= space
->nested
[0];
1466 range
= isl_space_copy(space
);
1467 range
= isl_space_drop_dims(range
, isl_dim_in
, 0, nested
->n_in
);
1469 return isl_space_free(space
);
1470 if (nested
->tuple_id
[1]) {
1471 range
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[1]);
1472 if (!range
->tuple_id
[0])
1475 if (nested
->nested
[1]) {
1476 range
->nested
[0] = isl_space_copy(nested
->nested
[1]);
1477 if (!range
->nested
[0])
1481 isl_space_free(space
);
1484 isl_space_free(space
);
1485 isl_space_free(range
);
1489 /* Internal function that selects the domain of the map that is
1490 * embedded in either a set space or the range of a map space.
1491 * In particular, given a space of the form [A -> B], return the space A.
1492 * Given a space of the form A -> [B -> C], return the space A -> B.
1494 static __isl_give isl_space
*range_factor_domain(__isl_take isl_space
*space
)
1502 nested
= space
->nested
[1];
1503 domain
= isl_space_copy(space
);
1504 domain
= isl_space_drop_dims(domain
, isl_dim_out
,
1505 nested
->n_in
, nested
->n_out
);
1507 return isl_space_free(space
);
1508 if (nested
->tuple_id
[0]) {
1509 domain
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[0]);
1510 if (!domain
->tuple_id
[1])
1513 if (nested
->nested
[0]) {
1514 domain
->nested
[1] = isl_space_copy(nested
->nested
[0]);
1515 if (!domain
->nested
[1])
1519 isl_space_free(space
);
1522 isl_space_free(space
);
1523 isl_space_free(domain
);
1527 /* Given a space of the form A -> [B -> C], return the space A -> B.
1529 __isl_give isl_space
*isl_space_range_factor_domain(
1530 __isl_take isl_space
*space
)
1534 if (!isl_space_range_is_wrapping(space
))
1535 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1536 "range not a product", return isl_space_free(space
));
1538 return range_factor_domain(space
);
1541 /* Given a space of the form [A -> B], return the space A.
1543 static __isl_give isl_space
*set_factor_domain(__isl_take isl_space
*space
)
1547 if (!isl_space_is_wrapping(space
))
1548 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1549 "not a product", return isl_space_free(space
));
1551 return range_factor_domain(space
);
1554 /* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1555 * Given a space of the form [A -> B], return the space A.
1557 __isl_give isl_space
*isl_space_factor_domain(__isl_take isl_space
*space
)
1561 if (isl_space_is_set(space
))
1562 return set_factor_domain(space
);
1563 space
= isl_space_domain_factor_domain(space
);
1564 space
= isl_space_range_factor_domain(space
);
1568 /* Internal function that selects the range of the map that is
1569 * embedded in either a set space or the range of a map space.
1570 * In particular, given a space of the form [A -> B], return the space B.
1571 * Given a space of the form A -> [B -> C], return the space A -> C.
1573 static __isl_give isl_space
*range_factor_range(__isl_take isl_space
*space
)
1581 nested
= space
->nested
[1];
1582 range
= isl_space_copy(space
);
1583 range
= isl_space_drop_dims(range
, isl_dim_out
, 0, nested
->n_in
);
1585 return isl_space_free(space
);
1586 if (nested
->tuple_id
[1]) {
1587 range
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[1]);
1588 if (!range
->tuple_id
[1])
1591 if (nested
->nested
[1]) {
1592 range
->nested
[1] = isl_space_copy(nested
->nested
[1]);
1593 if (!range
->nested
[1])
1597 isl_space_free(space
);
1600 isl_space_free(space
);
1601 isl_space_free(range
);
1605 /* Given a space of the form A -> [B -> C], return the space A -> C.
1607 __isl_give isl_space
*isl_space_range_factor_range(
1608 __isl_take isl_space
*space
)
1612 if (!isl_space_range_is_wrapping(space
))
1613 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1614 "range not a product", return isl_space_free(space
));
1616 return range_factor_range(space
);
1619 /* Given a space of the form [A -> B], return the space B.
1621 static __isl_give isl_space
*set_factor_range(__isl_take isl_space
*space
)
1625 if (!isl_space_is_wrapping(space
))
1626 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1627 "not a product", return isl_space_free(space
));
1629 return range_factor_range(space
);
1632 /* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1633 * Given a space of the form [A -> B], return the space B.
1635 __isl_give isl_space
*isl_space_factor_range(__isl_take isl_space
*space
)
1639 if (isl_space_is_set(space
))
1640 return set_factor_range(space
);
1641 space
= isl_space_domain_factor_range(space
);
1642 space
= isl_space_range_factor_range(space
);
1646 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*space
)
1649 isl_id
**ids
= NULL
;
1654 ctx
= isl_space_get_ctx(space
);
1655 if (!isl_space_is_set(space
))
1656 isl_die(ctx
, isl_error_invalid
, "not a set space", goto error
);
1657 space
= isl_space_cow(space
);
1660 n_id
= space
->nparam
+ space
->n_out
+ space
->n_out
;
1661 if (n_id
> 0 && space
->ids
) {
1662 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n_id
);
1665 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
1666 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1667 ids
+ space
->nparam
);
1669 space
->n_in
= space
->n_out
;
1674 space
= copy_ids(space
, isl_dim_out
, 0, space
, isl_dim_in
);
1676 isl_id_free(space
->tuple_id
[0]);
1677 space
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[1]);
1678 isl_space_free(space
->nested
[0]);
1679 space
->nested
[0] = isl_space_copy(space
->nested
[1]);
1682 isl_space_free(space
);
1686 __isl_give isl_space
*isl_space_map_from_domain_and_range(
1687 __isl_take isl_space
*domain
, __isl_take isl_space
*range
)
1689 if (!domain
|| !range
)
1691 if (!isl_space_is_set(domain
))
1692 isl_die(isl_space_get_ctx(domain
), isl_error_invalid
,
1693 "domain is not a set space", goto error
);
1694 if (!isl_space_is_set(range
))
1695 isl_die(isl_space_get_ctx(range
), isl_error_invalid
,
1696 "range is not a set space", goto error
);
1697 return isl_space_join(isl_space_reverse(domain
), range
);
1699 isl_space_free(domain
);
1700 isl_space_free(range
);
1704 static __isl_give isl_space
*set_ids(__isl_take isl_space
*dim
,
1705 enum isl_dim_type type
,
1706 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
1710 for (i
= 0; i
< n
; ++i
)
1711 dim
= set_id(dim
, type
, first
+ i
, ids
[i
]);
1716 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*space
)
1720 isl_id
**ids
= NULL
;
1725 if (match(space
, isl_dim_in
, space
, isl_dim_out
))
1728 space
= isl_space_cow(space
);
1732 id
= space
->tuple_id
[0];
1733 space
->tuple_id
[0] = space
->tuple_id
[1];
1734 space
->tuple_id
[1] = id
;
1736 nested
= space
->nested
[0];
1737 space
->nested
[0] = space
->nested
[1];
1738 space
->nested
[1] = nested
;
1741 int n_id
= space
->n_in
+ space
->n_out
;
1742 ids
= isl_alloc_array(space
->ctx
, isl_id
*, n_id
);
1745 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
);
1746 get_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
+ space
->n_in
);
1750 space
->n_in
= space
->n_out
;
1754 space
= set_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
);
1755 space
= set_ids(space
, isl_dim_in
, 0, space
->n_in
,
1756 ids
+ space
->n_out
);
1763 isl_space_free(space
);
1767 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*space
,
1768 enum isl_dim_type type
, unsigned first
, unsigned num
)
1776 return isl_space_reset(space
, type
);
1778 if (!valid_dim_type(type
))
1779 isl_die(space
->ctx
, isl_error_invalid
,
1780 "cannot drop dimensions of specified type", goto error
);
1782 if (isl_space_check_range(space
, type
, first
, num
) < 0)
1783 return isl_space_free(space
);
1784 space
= isl_space_cow(space
);
1788 space
= extend_ids(space
);
1791 for (i
= 0; i
< num
; ++i
)
1792 isl_id_free(get_id(space
, type
, first
+ i
));
1793 for (i
= first
+num
; i
< n(space
, type
); ++i
)
1794 set_id(space
, type
, i
- num
, get_id(space
, type
, i
));
1797 get_ids(space
, isl_dim_in
, 0, space
->n_in
,
1798 space
->ids
+ offset(space
, isl_dim_in
) - num
);
1800 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1801 space
->ids
+ offset(space
, isl_dim_out
) - num
);
1808 case isl_dim_param
: space
->nparam
-= num
; break;
1809 case isl_dim_in
: space
->n_in
-= num
; break;
1810 case isl_dim_out
: space
->n_out
-= num
; break;
1813 space
= isl_space_reset(space
, type
);
1814 if (type
== isl_dim_param
) {
1815 if (space
&& space
->nested
[0] &&
1816 !(space
->nested
[0] = isl_space_drop_dims(space
->nested
[0],
1817 isl_dim_param
, first
, num
)))
1819 if (space
&& space
->nested
[1] &&
1820 !(space
->nested
[1] = isl_space_drop_dims(space
->nested
[1],
1821 isl_dim_param
, first
, num
)))
1826 isl_space_free(space
);
1830 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*dim
,
1831 unsigned first
, unsigned n
)
1835 return isl_space_drop_dims(dim
, isl_dim_in
, first
, n
);
1838 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*dim
,
1839 unsigned first
, unsigned n
)
1843 return isl_space_drop_dims(dim
, isl_dim_out
, first
, n
);
1846 /* Remove all parameters from "space".
1848 __isl_give isl_space
*isl_space_drop_all_params(__isl_take isl_space
*space
)
1852 nparam
= isl_space_dim(space
, isl_dim_param
);
1854 return isl_space_free(space
);
1855 return isl_space_drop_dims(space
, isl_dim_param
, 0, nparam
);
1858 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*space
)
1862 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, space
->n_out
);
1863 space
= isl_space_reverse(space
);
1864 space
= mark_as_set(space
);
1868 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*space
)
1872 if (!isl_space_is_set(space
))
1873 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1874 "not a set space", goto error
);
1875 space
= isl_space_reverse(space
);
1876 space
= isl_space_reset(space
, isl_dim_out
);
1879 isl_space_free(space
);
1883 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*space
)
1887 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, space
->n_in
);
1888 space
= mark_as_set(space
);
1892 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*space
)
1896 if (!isl_space_is_set(space
))
1897 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1898 "not a set space", goto error
);
1899 return isl_space_reset(space
, isl_dim_in
);
1901 isl_space_free(space
);
1905 /* Given a map space A -> B, return the map space [A -> B] -> A.
1907 __isl_give isl_space
*isl_space_domain_map(__isl_take isl_space
*space
)
1911 domain
= isl_space_from_range(isl_space_domain(isl_space_copy(space
)));
1912 space
= isl_space_from_domain(isl_space_wrap(space
));
1913 space
= isl_space_join(space
, domain
);
1918 /* Given a map space A -> B, return the map space [A -> B] -> B.
1920 __isl_give isl_space
*isl_space_range_map(__isl_take isl_space
*space
)
1924 range
= isl_space_from_range(isl_space_range(isl_space_copy(space
)));
1925 space
= isl_space_from_domain(isl_space_wrap(space
));
1926 space
= isl_space_join(space
, range
);
1931 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
1933 isl_size n_in
, n_out
;
1935 if (isl_space_is_params(space
))
1937 n_in
= isl_space_dim(space
, isl_dim_in
);
1938 n_out
= isl_space_dim(space
, isl_dim_out
);
1939 if (n_in
< 0 || n_out
< 0)
1940 return isl_space_free(space
);
1941 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, n_in
);
1942 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, n_out
);
1943 space
= mark_as_params(space
);
1947 __isl_give isl_space
*isl_space_set_from_params(__isl_take isl_space
*space
)
1951 if (!isl_space_is_params(space
))
1952 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1953 "not a parameter space", goto error
);
1954 return isl_space_reset(space
, isl_dim_set
);
1956 isl_space_free(space
);
1960 /* Add an unnamed tuple of dimension "dim" to "space".
1961 * This requires "space" to be a parameter or set space.
1963 * In particular, if "space" is a parameter space, then return
1964 * a set space with the given dimension.
1965 * If "space" is a set space, then return a map space
1966 * with "space" as domain and a range of the given dimension.
1968 __isl_give isl_space
*isl_space_add_unnamed_tuple_ui(
1969 __isl_take isl_space
*space
, unsigned dim
)
1971 isl_bool is_params
, is_set
;
1973 is_params
= isl_space_is_params(space
);
1974 is_set
= isl_space_is_set(space
);
1975 if (is_params
< 0 || is_set
< 0)
1976 return isl_space_free(space
);
1977 if (!is_params
&& !is_set
)
1978 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1979 "cannot add tuple to map space",
1980 return isl_space_free(space
));
1982 space
= isl_space_set_from_params(space
);
1984 space
= isl_space_from_domain(space
);
1985 space
= isl_space_add_dims(space
, isl_dim_out
, dim
);
1989 /* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"
1991 * This requires "space" to be a parameter or set space.
1993 __isl_give isl_space
*isl_space_add_named_tuple_id_ui(
1994 __isl_take isl_space
*space
, __isl_take isl_id
*tuple_id
, unsigned dim
)
1996 space
= isl_space_add_unnamed_tuple_ui(space
, dim
);
1997 space
= isl_space_set_tuple_id(space
, isl_dim_out
, tuple_id
);
2001 /* Check that the identifiers in "tuple" do not appear as parameters
2004 static isl_stat
check_fresh_params(__isl_keep isl_space
*space
,
2005 __isl_keep isl_multi_id
*tuple
)
2010 n
= isl_multi_id_size(tuple
);
2012 return isl_stat_error
;
2013 for (i
= 0; i
< n
; ++i
) {
2017 id
= isl_multi_id_get_at(tuple
, i
);
2019 return isl_stat_error
;
2020 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2023 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2024 "parameters not unique", return isl_stat_error
);
2030 /* Add the identifiers in "tuple" as parameters of "space"
2031 * that are known to be fresh.
2033 static __isl_give isl_space
*add_bind_params(__isl_take isl_space
*space
,
2034 __isl_keep isl_multi_id
*tuple
)
2039 first
= isl_space_dim(space
, isl_dim_param
);
2040 n
= isl_multi_id_size(tuple
);
2041 if (first
< 0 || n
< 0)
2042 return isl_space_free(space
);
2043 space
= isl_space_add_dims(space
, isl_dim_param
, n
);
2044 for (i
= 0; i
< n
; ++i
) {
2047 id
= isl_multi_id_get_at(tuple
, i
);
2048 space
= isl_space_set_dim_id(space
,
2049 isl_dim_param
, first
+ i
, id
);
2055 /* Internal function that removes the set tuple of "space",
2056 * which is assumed to correspond to the range space of "tuple", and
2057 * adds the identifiers in "tuple" as fresh parameters.
2058 * In other words, the set dimensions of "space" are reinterpreted
2059 * as parameters, but stay in the same global positions.
2061 __isl_give isl_space
*isl_space_bind_set(__isl_take isl_space
*space
,
2062 __isl_keep isl_multi_id
*tuple
)
2064 isl_space
*tuple_space
;
2066 if (isl_space_check_is_set(space
) < 0)
2067 return isl_space_free(space
);
2068 tuple_space
= isl_multi_id_peek_space(tuple
);
2069 if (isl_space_check_equal_tuples(tuple_space
, space
) < 0)
2070 return isl_space_free(space
);
2071 if (check_fresh_params(space
, tuple
) < 0)
2072 return isl_space_free(space
);
2073 space
= isl_space_params(space
);
2074 space
= add_bind_params(space
, tuple
);
2078 /* Internal function that removes the domain tuple of the map space "space",
2079 * which is assumed to correspond to the range space of "tuple", and
2080 * adds the identifiers in "tuple" as fresh parameters.
2081 * In other words, the domain dimensions of "space" are reinterpreted
2082 * as parameters, but stay in the same global positions.
2084 __isl_give isl_space
*isl_space_bind_map_domain(__isl_take isl_space
*space
,
2085 __isl_keep isl_multi_id
*tuple
)
2087 isl_space
*tuple_space
;
2089 if (isl_space_check_is_map(space
) < 0)
2090 return isl_space_free(space
);
2091 tuple_space
= isl_multi_id_peek_space(tuple
);
2092 if (isl_space_check_domain_tuples(tuple_space
, space
) < 0)
2093 return isl_space_free(space
);
2094 if (check_fresh_params(space
, tuple
) < 0)
2095 return isl_space_free(space
);
2096 space
= isl_space_range(space
);
2097 space
= add_bind_params(space
, tuple
);
2101 /* Internal function that, given a space of the form [A -> B] -> C and
2102 * a tuple of identifiers in A, returns a space B -> C with
2103 * the identifiers in "tuple" added as fresh parameters.
2104 * In other words, the domain dimensions of the wrapped relation
2105 * in the domain of "space" are reinterpreted
2106 * as parameters, but stay in the same global positions.
2108 __isl_give isl_space
*isl_space_bind_domain_wrapped_domain(
2109 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2111 isl_space
*tuple_space
;
2113 if (isl_space_check_is_map(space
) < 0)
2114 return isl_space_free(space
);
2115 tuple_space
= isl_multi_id_peek_space(tuple
);
2116 if (isl_space_check_domain_wrapped_domain_tuples(tuple_space
,
2118 return isl_space_free(space
);
2119 if (check_fresh_params(space
, tuple
) < 0)
2120 return isl_space_free(space
);
2121 space
= isl_space_domain_factor_range(space
);
2122 space
= add_bind_params(space
, tuple
);
2126 /* Insert a domain tuple in "space" corresponding to the set space "domain".
2127 * In particular, if "space" is a parameter space, then the result
2128 * is the set space "domain" combined with the parameters of "space".
2129 * If "space" is a set space, then the result
2130 * is a map space with "domain" as domain and the original space as range.
2132 static __isl_give isl_space
*isl_space_insert_domain(
2133 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
2137 domain
= isl_space_replace_params(domain
, space
);
2139 is_params
= isl_space_is_params(space
);
2140 if (is_params
< 0) {
2141 isl_space_free(domain
);
2142 space
= isl_space_free(space
);
2143 } else if (is_params
) {
2144 isl_space_free(space
);
2147 space
= isl_space_map_from_domain_and_range(domain
, space
);
2152 /* Internal function that introduces a domain in "space"
2153 * corresponding to the range space of "tuple".
2154 * In particular, if "space" is a parameter space, then the result
2155 * is a set space. If "space" is a set space, then the result
2156 * is a map space with the original space as range.
2157 * Parameters that correspond to the identifiers in "tuple" are removed.
2159 * The parameters are removed in reverse order (under the assumption
2160 * that they appear in the same order in "multi") because
2161 * it is slightly more efficient to remove parameters at the end.
2163 * For pretty-printing purposes, the identifiers of the set dimensions
2164 * of the introduced domain are set to the identifiers in "tuple".
2166 __isl_give isl_space
*isl_space_unbind_params_insert_domain(
2167 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2171 isl_space
*tuple_space
;
2173 n
= isl_multi_id_size(tuple
);
2174 if (!space
|| n
< 0)
2175 return isl_space_free(space
);
2176 for (i
= n
- 1; i
>= 0; --i
) {
2180 id
= isl_multi_id_get_id(tuple
, i
);
2182 return isl_space_free(space
);
2183 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2187 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
2189 tuple_space
= isl_multi_id_get_space(tuple
);
2190 for (i
= 0; i
< n
; ++i
) {
2193 id
= isl_multi_id_get_id(tuple
, i
);
2194 tuple_space
= isl_space_set_dim_id(tuple_space
,
2195 isl_dim_set
, i
, id
);
2197 return isl_space_insert_domain(space
, tuple_space
);
2200 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*space
,
2206 is_set
= isl_space_is_set(space
);
2208 return isl_space_free(space
);
2209 if (n_div
== 0 && is_set
&&
2210 space
->nparam
== 0 && space
->n_in
== 0 && space
->n_id
== 0)
2211 return isl_space_reset(space
, isl_dim_out
);
2212 space
= isl_space_cow(space
);
2215 space
->n_out
+= space
->nparam
+ space
->n_in
+ n_div
;
2219 for (i
= 0; i
< space
->n_id
; ++i
)
2220 isl_id_free(get_id(space
, isl_dim_out
, i
));
2222 space
= isl_space_reset(space
, isl_dim_in
);
2223 space
= isl_space_reset(space
, isl_dim_out
);
2224 space
= mark_as_set(space
);
2229 /* Are the two spaces the same, including positions and names of parameters?
2231 isl_bool
isl_space_is_equal(__isl_keep isl_space
*space1
,
2232 __isl_keep isl_space
*space2
)
2236 if (!space1
|| !space2
)
2237 return isl_bool_error
;
2238 if (space1
== space2
)
2239 return isl_bool_true
;
2240 equal
= isl_space_has_equal_params(space1
, space2
);
2241 if (equal
< 0 || !equal
)
2243 return isl_space_has_equal_tuples(space1
, space2
);
2246 /* Do the tuples of "space1" correspond to those of the domain of "space2"?
2247 * That is, is "space1" equal to the domain of "space2", ignoring parameters.
2249 * "space2" is allowed to be a set space, in which case "space1"
2250 * should be a parameter space.
2252 isl_bool
isl_space_has_domain_tuples(__isl_keep isl_space
*space1
,
2253 __isl_keep isl_space
*space2
)
2257 is_set
= isl_space_is_set(space1
);
2258 if (is_set
< 0 || !is_set
)
2260 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2261 space2
, isl_dim_in
);
2264 /* Do the tuples of "space1" correspond to those of the range of "space2"?
2265 * That is, is "space1" equal to the range of "space2", ignoring parameters.
2267 * "space2" is allowed to be the space of a set,
2268 * in which case it should be equal to "space1", ignoring parameters.
2270 isl_bool
isl_space_has_range_tuples(__isl_keep isl_space
*space1
,
2271 __isl_keep isl_space
*space2
)
2275 is_set
= isl_space_is_set(space1
);
2276 if (is_set
< 0 || !is_set
)
2278 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2279 space2
, isl_dim_out
);
2282 /* Check that the tuples of "space1" correspond to those
2283 * of the domain of "space2".
2284 * That is, check that "space1" is equal to the domain of "space2",
2285 * ignoring parameters.
2287 isl_stat
isl_space_check_domain_tuples(__isl_keep isl_space
*space1
,
2288 __isl_keep isl_space
*space2
)
2292 is_equal
= isl_space_has_domain_tuples(space1
, space2
);
2294 return isl_stat_error
;
2296 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
2297 "incompatible spaces", return isl_stat_error
);
2302 /* Check that the tuples of "space1" correspond to those
2303 * of the domain of the wrapped relation in the domain of "space2".
2304 * That is, check that "space1" is equal to this domain,
2305 * ignoring parameters.
2307 isl_stat
isl_space_check_domain_wrapped_domain_tuples(
2308 __isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
2313 domain
= isl_space_unwrap(isl_space_domain(isl_space_copy(space2
)));
2314 r
= isl_space_check_domain_tuples(space1
, domain
);
2315 isl_space_free(domain
);
2320 /* Is space1 equal to the domain of space2?
2322 * In the internal version we also allow space2 to be the space of a set,
2323 * provided space1 is a parameter space.
2325 isl_bool
isl_space_is_domain_internal(__isl_keep isl_space
*space1
,
2326 __isl_keep isl_space
*space2
)
2328 isl_bool equal_params
;
2330 if (!space1
|| !space2
)
2331 return isl_bool_error
;
2332 equal_params
= isl_space_has_equal_params(space1
, space2
);
2333 if (equal_params
< 0 || !equal_params
)
2334 return equal_params
;
2335 return isl_space_has_domain_tuples(space1
, space2
);
2338 /* Is space1 equal to the domain of space2?
2340 isl_bool
isl_space_is_domain(__isl_keep isl_space
*space1
,
2341 __isl_keep isl_space
*space2
)
2344 return isl_bool_error
;
2345 if (!isl_space_is_map(space2
))
2346 return isl_bool_false
;
2347 return isl_space_is_domain_internal(space1
, space2
);
2350 /* Is space1 equal to the range of space2?
2352 * In the internal version, space2 is allowed to be the space of a set,
2353 * in which case it should be equal to space1.
2355 isl_bool
isl_space_is_range_internal(__isl_keep isl_space
*space1
,
2356 __isl_keep isl_space
*space2
)
2358 isl_bool equal_params
;
2360 if (!space1
|| !space2
)
2361 return isl_bool_error
;
2362 equal_params
= isl_space_has_equal_params(space1
, space2
);
2363 if (equal_params
< 0 || !equal_params
)
2364 return equal_params
;
2365 return isl_space_has_range_tuples(space1
, space2
);
2368 /* Is space1 equal to the range of space2?
2370 isl_bool
isl_space_is_range(__isl_keep isl_space
*space1
,
2371 __isl_keep isl_space
*space2
)
2374 return isl_bool_error
;
2375 if (!isl_space_is_map(space2
))
2376 return isl_bool_false
;
2377 return isl_space_is_range_internal(space1
, space2
);
2380 /* Update "hash" by hashing in the parameters of "space".
2382 static uint32_t isl_hash_params(uint32_t hash
, __isl_keep isl_space
*space
)
2390 isl_hash_byte(hash
, space
->nparam
% 256);
2392 for (i
= 0; i
< space
->nparam
; ++i
) {
2393 id
= get_id(space
, isl_dim_param
, i
);
2394 hash
= isl_hash_id(hash
, id
);
2400 /* Update "hash" by hashing in the tuples of "space".
2401 * Changes in this function should be reflected in isl_hash_tuples_domain.
2403 static uint32_t isl_hash_tuples(uint32_t hash
, __isl_keep isl_space
*space
)
2410 isl_hash_byte(hash
, space
->n_in
% 256);
2411 isl_hash_byte(hash
, space
->n_out
% 256);
2413 id
= tuple_id(space
, isl_dim_in
);
2414 hash
= isl_hash_id(hash
, id
);
2415 id
= tuple_id(space
, isl_dim_out
);
2416 hash
= isl_hash_id(hash
, id
);
2418 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2419 hash
= isl_hash_tuples(hash
, space
->nested
[1]);
2424 /* Update "hash" by hashing in the domain tuple of "space".
2425 * The result of this function is equal to the result of applying
2426 * isl_hash_tuples to the domain of "space".
2428 static uint32_t isl_hash_tuples_domain(uint32_t hash
,
2429 __isl_keep isl_space
*space
)
2436 isl_hash_byte(hash
, 0);
2437 isl_hash_byte(hash
, space
->n_in
% 256);
2439 hash
= isl_hash_id(hash
, &isl_id_none
);
2440 id
= tuple_id(space
, isl_dim_in
);
2441 hash
= isl_hash_id(hash
, id
);
2443 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2448 /* Return a hash value that digests the tuples of "space",
2449 * i.e., that ignores the parameters.
2451 uint32_t isl_space_get_tuple_hash(__isl_keep isl_space
*space
)
2458 hash
= isl_hash_init();
2459 hash
= isl_hash_tuples(hash
, space
);
2464 uint32_t isl_space_get_hash(__isl_keep isl_space
*space
)
2471 hash
= isl_hash_init();
2472 hash
= isl_hash_params(hash
, space
);
2473 hash
= isl_hash_tuples(hash
, space
);
2478 /* Return the hash value of the domain of "space".
2479 * That is, isl_space_get_domain_hash(space) is equal to
2480 * isl_space_get_hash(isl_space_domain(space)).
2482 uint32_t isl_space_get_domain_hash(__isl_keep isl_space
*space
)
2489 hash
= isl_hash_init();
2490 hash
= isl_hash_params(hash
, space
);
2491 hash
= isl_hash_tuples_domain(hash
, space
);
2496 /* Is "space" the space of a set wrapping a map space?
2498 isl_bool
isl_space_is_wrapping(__isl_keep isl_space
*space
)
2501 return isl_bool_error
;
2503 if (!isl_space_is_set(space
))
2504 return isl_bool_false
;
2506 return isl_bool_ok(space
->nested
[1] != NULL
);
2509 /* Is "space" the space of a map where the domain is a wrapped map space?
2511 isl_bool
isl_space_domain_is_wrapping(__isl_keep isl_space
*space
)
2514 return isl_bool_error
;
2516 if (isl_space_is_set(space
))
2517 return isl_bool_false
;
2519 return isl_bool_ok(space
->nested
[0] != NULL
);
2522 /* Is "space" the space of a map where the range is a wrapped map space?
2524 isl_bool
isl_space_range_is_wrapping(__isl_keep isl_space
*space
)
2527 return isl_bool_error
;
2529 if (isl_space_is_set(space
))
2530 return isl_bool_false
;
2532 return isl_bool_ok(space
->nested
[1] != NULL
);
2535 /* Is "space" a product of two spaces?
2536 * That is, is it a wrapping set space or a map space
2537 * with wrapping domain and range?
2539 isl_bool
isl_space_is_product(__isl_keep isl_space
*space
)
2542 isl_bool is_product
;
2544 is_set
= isl_space_is_set(space
);
2546 return isl_bool_error
;
2548 return isl_space_is_wrapping(space
);
2549 is_product
= isl_space_domain_is_wrapping(space
);
2550 if (is_product
< 0 || !is_product
)
2552 return isl_space_range_is_wrapping(space
);
2555 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*space
)
2562 wrap
= isl_space_set_alloc(space
->ctx
,
2563 space
->nparam
, space
->n_in
+ space
->n_out
);
2565 wrap
= copy_ids(wrap
, isl_dim_param
, 0, space
, isl_dim_param
);
2566 wrap
= copy_ids(wrap
, isl_dim_set
, 0, space
, isl_dim_in
);
2567 wrap
= copy_ids(wrap
, isl_dim_set
, space
->n_in
, space
, isl_dim_out
);
2572 wrap
->nested
[1] = space
;
2576 isl_space_free(space
);
2580 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*space
)
2587 if (!isl_space_is_wrapping(space
))
2588 isl_die(space
->ctx
, isl_error_invalid
, "not a wrapping space",
2591 unwrap
= isl_space_copy(space
->nested
[1]);
2592 isl_space_free(space
);
2596 isl_space_free(space
);
2600 isl_bool
isl_space_is_named_or_nested(__isl_keep isl_space
*space
,
2601 enum isl_dim_type type
)
2603 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
2604 return isl_bool_false
;
2606 return isl_bool_error
;
2607 if (space
->tuple_id
[type
- isl_dim_in
])
2608 return isl_bool_true
;
2609 if (space
->nested
[type
- isl_dim_in
])
2610 return isl_bool_true
;
2611 return isl_bool_false
;
2614 isl_bool
isl_space_may_be_set(__isl_keep isl_space
*space
)
2620 return isl_bool_error
;
2621 if (isl_space_is_set(space
))
2622 return isl_bool_true
;
2623 n_in
= isl_space_dim(space
, isl_dim_in
);
2625 return isl_bool_error
;
2627 return isl_bool_false
;
2628 nested
= isl_space_is_named_or_nested(space
, isl_dim_in
);
2629 if (nested
< 0 || nested
)
2630 return isl_bool_not(nested
);
2631 return isl_bool_true
;
2634 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*space
,
2635 enum isl_dim_type type
)
2637 if (!isl_space_is_named_or_nested(space
, type
))
2640 space
= isl_space_cow(space
);
2644 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
2645 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
2646 isl_space_free(space
->nested
[type
- isl_dim_in
]);
2647 space
->nested
[type
- isl_dim_in
] = NULL
;
2652 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*space
)
2656 if (!space
->nested
[0] && !space
->nested
[1])
2659 if (space
->nested
[0])
2660 space
= isl_space_reset(space
, isl_dim_in
);
2661 if (space
&& space
->nested
[1])
2662 space
= isl_space_reset(space
, isl_dim_out
);
2667 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*space
)
2671 if (!space
->nested
[0])
2674 return isl_space_reset(space
, isl_dim_in
);
2677 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*space
)
2681 if (!space
->nested
[1])
2684 return isl_space_reset(space
, isl_dim_out
);
2687 /* Replace the parameters of dst by those of src.
2689 __isl_give isl_space
*isl_space_replace_params(__isl_take isl_space
*dst
,
2690 __isl_keep isl_space
*src
)
2692 isl_size dst_dim
, src_dim
;
2693 isl_bool equal_params
;
2694 enum isl_dim_type type
= isl_dim_param
;
2696 equal_params
= isl_space_has_equal_params(dst
, src
);
2697 if (equal_params
< 0)
2698 return isl_space_free(dst
);
2702 dst
= isl_space_cow(dst
);
2704 dst_dim
= isl_space_dim(dst
, type
);
2705 src_dim
= isl_space_dim(src
, type
);
2706 if (dst_dim
< 0 || src_dim
< 0)
2709 dst
= isl_space_drop_dims(dst
, type
, 0, dst_dim
);
2710 dst
= isl_space_add_dims(dst
, type
, src_dim
);
2711 dst
= copy_ids(dst
, type
, 0, src
, type
);
2715 for (i
= 0; i
<= 1; ++i
) {
2716 if (!dst
->nested
[i
])
2718 dst
->nested
[i
] = isl_space_replace_params(
2719 dst
->nested
[i
], src
);
2720 if (!dst
->nested
[i
])
2727 isl_space_free(dst
);
2731 /* Given a dimension specification "dim" of a set, create a dimension
2732 * specification for the lift of the set. In particular, the result
2733 * is of the form [dim -> local[..]], with n_local variables in the
2734 * range of the wrapped map.
2736 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*space
,
2739 isl_space
*local_space
;
2744 local_space
= isl_space_dup(space
);
2745 local_space
= isl_space_drop_dims(local_space
, isl_dim_set
, 0,
2747 local_space
= isl_space_add_dims(local_space
, isl_dim_set
, n_local
);
2748 local_space
= isl_space_set_tuple_name(local_space
,
2749 isl_dim_set
, "local");
2750 space
= isl_space_join(isl_space_from_domain(space
),
2751 isl_space_from_range(local_space
));
2752 space
= isl_space_wrap(space
);
2753 space
= isl_space_set_tuple_name(space
, isl_dim_set
, "lifted");
2758 isl_bool
isl_space_can_zip(__isl_keep isl_space
*space
)
2762 is_set
= isl_space_is_set(space
);
2764 return isl_bool_error
;
2766 return isl_bool_false
;
2767 return isl_space_is_product(space
);
2770 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*space
)
2772 isl_space
*dom
, *ran
;
2773 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
2775 if (!isl_space_can_zip(space
))
2776 isl_die(space
->ctx
, isl_error_invalid
, "dim cannot be zipped",
2781 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
2782 ran
= isl_space_unwrap(isl_space_range(space
));
2783 dom_dom
= isl_space_domain(isl_space_copy(dom
));
2784 dom_ran
= isl_space_range(dom
);
2785 ran_dom
= isl_space_domain(isl_space_copy(ran
));
2786 ran_ran
= isl_space_range(ran
);
2787 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
2788 isl_space_from_range(ran_dom
));
2789 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
2790 isl_space_from_range(ran_ran
));
2791 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
2792 isl_space_from_range(isl_space_wrap(ran
)));
2794 isl_space_free(space
);
2798 /* Can we apply isl_space_curry to "space"?
2799 * That is, does is it have a map space with a nested relation in its domain?
2801 isl_bool
isl_space_can_curry(__isl_keep isl_space
*space
)
2803 return isl_space_domain_is_wrapping(space
);
2806 /* Given a space (A -> B) -> C, return the corresponding space
2809 __isl_give isl_space
*isl_space_curry(__isl_take isl_space
*space
)
2811 isl_space
*dom
, *ran
;
2812 isl_space
*dom_dom
, *dom_ran
;
2817 if (!isl_space_can_curry(space
))
2818 isl_die(space
->ctx
, isl_error_invalid
,
2819 "space cannot be curried", goto error
);
2821 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
2822 ran
= isl_space_range(space
);
2823 dom_dom
= isl_space_domain(isl_space_copy(dom
));
2824 dom_ran
= isl_space_range(dom
);
2825 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
2826 isl_space_from_range(ran
));
2827 return isl_space_join(isl_space_from_domain(dom_dom
),
2828 isl_space_from_range(isl_space_wrap(ran
)));
2830 isl_space_free(space
);
2834 /* Can isl_space_range_curry be applied to "space"?
2835 * That is, does it have a nested relation in its range,
2836 * the domain of which is itself a nested relation?
2838 isl_bool
isl_space_can_range_curry(__isl_keep isl_space
*space
)
2843 return isl_bool_error
;
2844 can
= isl_space_range_is_wrapping(space
);
2845 if (can
< 0 || !can
)
2847 return isl_space_can_curry(space
->nested
[1]);
2850 /* Given a space A -> ((B -> C) -> D), return the corresponding space
2851 * A -> (B -> (C -> D)).
2853 __isl_give isl_space
*isl_space_range_curry(__isl_take isl_space
*space
)
2858 if (!isl_space_can_range_curry(space
))
2859 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2860 "space range cannot be curried",
2861 return isl_space_free(space
));
2863 space
= isl_space_cow(space
);
2866 space
->nested
[1] = isl_space_curry(space
->nested
[1]);
2867 if (!space
->nested
[1])
2868 return isl_space_free(space
);
2873 /* Can we apply isl_space_uncurry to "space"?
2874 * That is, does it have a map space with a nested relation in its range?
2876 isl_bool
isl_space_can_uncurry(__isl_keep isl_space
*space
)
2878 return isl_space_range_is_wrapping(space
);
2881 /* Given a space A -> (B -> C), return the corresponding space
2884 __isl_give isl_space
*isl_space_uncurry(__isl_take isl_space
*space
)
2886 isl_space
*dom
, *ran
;
2887 isl_space
*ran_dom
, *ran_ran
;
2892 if (!isl_space_can_uncurry(space
))
2893 isl_die(space
->ctx
, isl_error_invalid
,
2894 "space cannot be uncurried",
2895 return isl_space_free(space
));
2897 dom
= isl_space_domain(isl_space_copy(space
));
2898 ran
= isl_space_unwrap(isl_space_range(space
));
2899 ran_dom
= isl_space_domain(isl_space_copy(ran
));
2900 ran_ran
= isl_space_range(ran
);
2901 dom
= isl_space_join(isl_space_from_domain(dom
),
2902 isl_space_from_range(ran_dom
));
2903 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
2904 isl_space_from_range(ran_ran
));
2907 isl_bool
isl_space_has_named_params(__isl_keep isl_space
*space
)
2913 return isl_bool_error
;
2914 if (space
->nparam
== 0)
2915 return isl_bool_true
;
2916 off
= isl_space_offset(space
, isl_dim_param
);
2917 if (off
+ space
->nparam
> space
->n_id
)
2918 return isl_bool_false
;
2919 for (i
= 0; i
< space
->nparam
; ++i
)
2920 if (!space
->ids
[off
+ i
])
2921 return isl_bool_false
;
2922 return isl_bool_true
;
2925 /* Check that "space" has only named parameters, reporting an error
2928 isl_stat
isl_space_check_named_params(__isl_keep isl_space
*space
)
2932 named
= isl_space_has_named_params(space
);
2934 return isl_stat_error
;
2936 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2937 "unexpected unnamed parameters", return isl_stat_error
);
2942 /* Align the initial parameters of space1 to match the order in space2.
2944 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*space1
,
2945 __isl_take isl_space
*space2
)
2947 isl_reordering
*exp
;
2949 if (isl_space_check_named_params(space1
) < 0 ||
2950 isl_space_check_named_params(space2
) < 0)
2953 exp
= isl_parameter_alignment_reordering(space1
, space2
);
2954 exp
= isl_reordering_extend_space(exp
, space1
);
2955 isl_space_free(space2
);
2956 space1
= isl_reordering_get_space(exp
);
2957 isl_reordering_free(exp
);
2960 isl_space_free(space1
);
2961 isl_space_free(space2
);
2965 /* Given the space of set (domain), construct a space for a map
2966 * with as domain the given space and as range the range of "model".
2968 __isl_give isl_space
*isl_space_extend_domain_with_range(
2969 __isl_take isl_space
*space
, __isl_take isl_space
*model
)
2976 space
= isl_space_from_domain(space
);
2977 n_out
= isl_space_dim(model
, isl_dim_out
);
2980 space
= isl_space_add_dims(space
, isl_dim_out
, n_out
);
2981 if (isl_space_has_tuple_id(model
, isl_dim_out
))
2982 space
= isl_space_set_tuple_id(space
, isl_dim_out
,
2983 isl_space_get_tuple_id(model
, isl_dim_out
));
2986 if (model
->nested
[1]) {
2987 isl_space
*nested
= isl_space_copy(model
->nested
[1]);
2988 isl_size n_nested
, n_space
;
2989 nested
= isl_space_align_params(nested
, isl_space_copy(space
));
2990 n_nested
= isl_space_dim(nested
, isl_dim_param
);
2991 n_space
= isl_space_dim(space
, isl_dim_param
);
2992 if (n_nested
< 0 || n_space
< 0)
2994 if (n_nested
> n_space
)
2995 nested
= isl_space_drop_dims(nested
, isl_dim_param
,
2996 n_space
, n_nested
- n_space
);
2999 space
->nested
[1] = nested
;
3001 isl_space_free(model
);
3004 isl_space_free(model
);
3005 isl_space_free(space
);
3009 /* Compare the "type" dimensions of two isl_spaces.
3011 * The order is fairly arbitrary.
3013 static int isl_space_cmp_type(__isl_keep isl_space
*space1
,
3014 __isl_keep isl_space
*space2
, enum isl_dim_type type
)
3017 isl_size dim1
, dim2
;
3018 isl_space
*nested1
, *nested2
;
3020 dim1
= isl_space_dim(space1
, type
);
3021 dim2
= isl_space_dim(space2
, type
);
3022 if (dim1
< 0 || dim2
< 0)
3027 cmp
= isl_id_cmp(tuple_id(space1
, type
), tuple_id(space2
, type
));
3031 nested1
= nested(space1
, type
);
3032 nested2
= nested(space2
, type
);
3033 if (!nested1
!= !nested2
)
3034 return !nested1
- !nested2
;
3037 return isl_space_cmp(nested1
, nested2
);
3042 /* Compare two isl_spaces.
3044 * The order is fairly arbitrary.
3046 int isl_space_cmp(__isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
3051 if (space1
== space2
)
3058 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_param
);
3061 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_in
);
3064 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_out
);
3068 if (!space1
->ids
&& !space2
->ids
)
3071 for (i
= 0; i
< n(space1
, isl_dim_param
); ++i
) {
3072 cmp
= isl_id_cmp(get_id(space1
, isl_dim_param
, i
),
3073 get_id(space2
, isl_dim_param
, i
));