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 range is a wrapped map space.
127 isl_stat
isl_space_check_range_is_wrapping(__isl_keep isl_space
*space
)
131 wrapping
= isl_space_range_is_wrapping(space
);
133 return isl_stat_error
;
135 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
136 "range not a product", return isl_stat_error
);
140 __isl_give isl_space
*isl_space_set_alloc(isl_ctx
*ctx
,
141 unsigned nparam
, unsigned dim
)
144 space
= isl_space_alloc(ctx
, nparam
, 0, dim
);
145 space
= mark_as_set(space
);
149 /* Mark the space as being that of a parameter domain, by setting
150 * both tuples to isl_id_none.
152 static __isl_give isl_space
*mark_as_params(isl_space
*space
)
156 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
157 space
= isl_space_set_tuple_id(space
, isl_dim_out
, &isl_id_none
);
161 /* Is the space that of a parameter domain?
163 isl_bool
isl_space_is_params(__isl_keep isl_space
*space
)
166 return isl_bool_error
;
167 if (space
->n_in
!= 0 || space
->nested
[0] ||
168 space
->n_out
!= 0 || space
->nested
[1])
169 return isl_bool_false
;
170 if (space
->tuple_id
[0] != &isl_id_none
)
171 return isl_bool_false
;
172 if (space
->tuple_id
[1] != &isl_id_none
)
173 return isl_bool_false
;
174 return isl_bool_true
;
177 /* Create a space for a parameter domain.
179 __isl_give isl_space
*isl_space_params_alloc(isl_ctx
*ctx
, unsigned nparam
)
182 space
= isl_space_alloc(ctx
, nparam
, 0, 0);
183 space
= mark_as_params(space
);
187 /* Create a space for a parameter domain, without any parameters.
189 __isl_give isl_space
*isl_space_unit(isl_ctx
*ctx
)
191 return isl_space_params_alloc(ctx
, 0);
194 static isl_size
global_pos(__isl_keep isl_space
*space
,
195 enum isl_dim_type type
, unsigned pos
)
197 if (isl_space_check_range(space
, type
, pos
, 1) < 0)
198 return isl_size_error
;
204 return pos
+ space
->nparam
;
206 return pos
+ space
->nparam
+ space
->n_in
;
208 isl_assert(isl_space_get_ctx(space
), 0, return isl_size_error
);
210 return isl_size_error
;
213 /* Extend length of ids array to the total number of dimensions.
215 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*space
)
221 dim
= isl_space_dim(space
, isl_dim_all
);
223 return isl_space_free(space
);
224 if (dim
<= space
->n_id
)
228 space
->ids
= isl_calloc_array(space
->ctx
, isl_id
*, dim
);
232 ids
= isl_realloc_array(space
->ctx
, space
->ids
, isl_id
*, dim
);
236 for (i
= space
->n_id
; i
< dim
; ++i
)
237 space
->ids
[i
] = NULL
;
244 isl_space_free(space
);
248 static __isl_give isl_space
*set_id(__isl_take isl_space
*space
,
249 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
253 space
= isl_space_cow(space
);
255 gpos
= global_pos(space
, type
, pos
);
259 if (gpos
>= space
->n_id
) {
262 space
= extend_ids(space
);
267 space
->ids
[gpos
] = id
;
272 isl_space_free(space
);
276 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*space
,
277 enum isl_dim_type type
, unsigned pos
)
281 gpos
= global_pos(space
, type
, pos
);
284 if (gpos
>= space
->n_id
)
286 return space
->ids
[gpos
];
289 /* Return the nested space at the given position.
291 static __isl_keep isl_space
*isl_space_peek_nested(__isl_keep isl_space
*space
,
296 if (!space
->nested
[pos
])
297 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
298 "no nested space", return NULL
);
299 return space
->nested
[pos
];
302 static unsigned offset(__isl_keep isl_space
*space
, enum isl_dim_type type
)
305 case isl_dim_param
: return 0;
306 case isl_dim_in
: return space
->nparam
;
307 case isl_dim_out
: return space
->nparam
+ space
->n_in
;
312 static unsigned n(__isl_keep isl_space
*space
, enum isl_dim_type type
)
315 case isl_dim_param
: return space
->nparam
;
316 case isl_dim_in
: return space
->n_in
;
317 case isl_dim_out
: return space
->n_out
;
319 return space
->nparam
+ space
->n_in
+ space
->n_out
;
324 isl_size
isl_space_dim(__isl_keep isl_space
*space
, enum isl_dim_type type
)
327 return isl_size_error
;
328 return n(space
, type
);
331 /* Return the dimensionality of tuple "inner" within the wrapped relation
332 * inside tuple "outer".
334 isl_size
isl_space_wrapped_dim(__isl_keep isl_space
*space
,
335 enum isl_dim_type outer
, enum isl_dim_type inner
)
340 return isl_size_error
;
341 if (outer
!= isl_dim_in
&& outer
!= isl_dim_out
)
342 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
343 "only input, output and set tuples "
344 "can have nested relations", return isl_size_error
);
345 pos
= outer
- isl_dim_in
;
346 return isl_space_dim(isl_space_peek_nested(space
, pos
), inner
);
349 unsigned isl_space_offset(__isl_keep isl_space
*space
, enum isl_dim_type type
)
353 return offset(space
, type
);
356 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
357 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
358 enum isl_dim_type src_type
)
366 for (i
= 0; i
< n(src
, src_type
); ++i
) {
367 id
= get_id(src
, src_type
, i
);
370 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
377 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*space
)
382 dup
= isl_space_alloc(space
->ctx
,
383 space
->nparam
, space
->n_in
, space
->n_out
);
386 if (space
->tuple_id
[0] &&
387 !(dup
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[0])))
389 if (space
->tuple_id
[1] &&
390 !(dup
->tuple_id
[1] = isl_id_copy(space
->tuple_id
[1])))
392 if (space
->nested
[0] &&
393 !(dup
->nested
[0] = isl_space_copy(space
->nested
[0])))
395 if (space
->nested
[1] &&
396 !(dup
->nested
[1] = isl_space_copy(space
->nested
[1])))
400 dup
= copy_ids(dup
, isl_dim_param
, 0, space
, isl_dim_param
);
401 dup
= copy_ids(dup
, isl_dim_in
, 0, space
, isl_dim_in
);
402 dup
= copy_ids(dup
, isl_dim_out
, 0, space
, isl_dim_out
);
409 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*space
)
417 return isl_space_dup(space
);
420 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*space
)
429 __isl_null isl_space
*isl_space_free(__isl_take isl_space
*space
)
436 if (--space
->ref
> 0)
439 isl_id_free(space
->tuple_id
[0]);
440 isl_id_free(space
->tuple_id
[1]);
442 isl_space_free(space
->nested
[0]);
443 isl_space_free(space
->nested
[1]);
445 for (i
= 0; i
< space
->n_id
; ++i
)
446 isl_id_free(space
->ids
[i
]);
448 isl_ctx_deref(space
->ctx
);
455 /* Check if "s" is a valid dimension or tuple name.
456 * We currently only forbid names that look like a number.
458 * s is assumed to be non-NULL.
460 static int name_ok(isl_ctx
*ctx
, const char *s
)
465 dummy
= strtol(s
, &p
, 0);
467 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
473 /* Return a copy of the nested space at the given position.
475 static __isl_keep isl_space
*isl_space_get_nested(__isl_keep isl_space
*space
,
478 return isl_space_copy(isl_space_peek_nested(space
, pos
));
481 /* Return the nested space at the given position.
482 * This may be either a copy or the nested space itself
483 * if there is only one reference to "space".
484 * This allows the nested space to be modified inplace
485 * if both "space" and the nested space have only a single reference.
486 * The caller is not allowed to modify "space" between this call and
487 * a subsequent call to isl_space_restore_nested.
488 * The only exception is that isl_space_free can be called instead.
490 static __isl_give isl_space
*isl_space_take_nested(__isl_keep isl_space
*space
,
498 return isl_space_get_nested(space
, pos
);
499 nested
= space
->nested
[pos
];
500 space
->nested
[pos
] = NULL
;
504 /* Replace the nested space at the given position by "nested",
505 * where this nested space of "space" may be missing
506 * due to a preceding call to isl_space_take_nested.
507 * However, in this case, "space" only has a single reference and
508 * then the call to isl_space_cow has no effect.
510 static __isl_give isl_space
*isl_space_restore_nested(
511 __isl_take isl_space
*space
, int pos
, __isl_take isl_space
*nested
)
513 if (!space
|| !nested
)
516 if (space
->nested
[pos
] == nested
) {
517 isl_space_free(nested
);
521 space
= isl_space_cow(space
);
524 isl_space_free(space
->nested
[pos
]);
525 space
->nested
[pos
] = nested
;
529 isl_space_free(space
);
530 isl_space_free(nested
);
534 /* Is it possible for the given dimension type to have a tuple id?
536 static int space_can_have_id(__isl_keep isl_space
*space
,
537 enum isl_dim_type type
)
541 if (isl_space_is_params(space
))
542 isl_die(space
->ctx
, isl_error_invalid
,
543 "parameter spaces don't have tuple ids", return 0);
544 if (isl_space_is_set(space
) && type
!= isl_dim_set
)
545 isl_die(space
->ctx
, isl_error_invalid
,
546 "set spaces can only have a set id", return 0);
547 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
548 isl_die(space
->ctx
, isl_error_invalid
,
549 "only input, output and set tuples can have ids",
555 /* Does the tuple have an id?
557 isl_bool
isl_space_has_tuple_id(__isl_keep isl_space
*space
,
558 enum isl_dim_type type
)
560 if (!space_can_have_id(space
, type
))
561 return isl_bool_error
;
562 return isl_bool_ok(space
->tuple_id
[type
- isl_dim_in
] != NULL
);
565 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*space
,
566 enum isl_dim_type type
)
572 has_id
= isl_space_has_tuple_id(space
, type
);
576 isl_die(space
->ctx
, isl_error_invalid
,
577 "tuple has no id", return NULL
);
578 return isl_id_copy(space
->tuple_id
[type
- isl_dim_in
]);
581 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*space
,
582 enum isl_dim_type type
, __isl_take isl_id
*id
)
584 space
= isl_space_cow(space
);
587 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
588 isl_die(space
->ctx
, isl_error_invalid
,
589 "only input, output and set tuples can have names",
592 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
593 space
->tuple_id
[type
- isl_dim_in
] = id
;
598 isl_space_free(space
);
602 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*space
,
603 enum isl_dim_type type
)
605 space
= isl_space_cow(space
);
608 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
609 isl_die(space
->ctx
, isl_error_invalid
,
610 "only input, output and set tuples can have names",
613 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
614 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
618 isl_space_free(space
);
622 /* Set the id of the given dimension of "space" to "id".
623 * If the dimension already has an id, then it is replaced.
624 * If the dimension is a parameter, then we need to change it
625 * in the nested spaces (if any) as well.
627 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*space
,
628 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
630 space
= isl_space_cow(space
);
634 if (type
== isl_dim_param
) {
637 for (i
= 0; i
< 2; ++i
) {
638 if (!space
->nested
[i
])
641 isl_space_set_dim_id(space
->nested
[i
],
642 type
, pos
, isl_id_copy(id
));
643 if (!space
->nested
[i
])
648 isl_id_free(get_id(space
, type
, pos
));
649 return set_id(space
, type
, pos
, id
);
652 isl_space_free(space
);
656 /* Reset the id of the given dimension of "space".
657 * If the dimension already has an id, then it is removed.
658 * If the dimension is a parameter, then we need to reset it
659 * in the nested spaces (if any) as well.
661 __isl_give isl_space
*isl_space_reset_dim_id(__isl_take isl_space
*space
,
662 enum isl_dim_type type
, unsigned pos
)
664 space
= isl_space_cow(space
);
668 if (type
== isl_dim_param
) {
671 for (i
= 0; i
< 2; ++i
) {
672 if (!space
->nested
[i
])
675 isl_space_reset_dim_id(space
->nested
[i
],
677 if (!space
->nested
[i
])
682 isl_id_free(get_id(space
, type
, pos
));
683 return set_id(space
, type
, pos
, NULL
);
685 isl_space_free(space
);
689 isl_bool
isl_space_has_dim_id(__isl_keep isl_space
*space
,
690 enum isl_dim_type type
, unsigned pos
)
693 return isl_bool_error
;
694 return isl_bool_ok(get_id(space
, type
, pos
) != NULL
);
697 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*space
,
698 enum isl_dim_type type
, unsigned pos
)
702 if (!get_id(space
, type
, pos
))
703 isl_die(space
->ctx
, isl_error_invalid
,
704 "dim has no id", return NULL
);
705 return isl_id_copy(get_id(space
, type
, pos
));
708 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*space
,
709 enum isl_dim_type type
, const char *s
)
717 return isl_space_reset_tuple_id(space
, type
);
719 if (!name_ok(space
->ctx
, s
))
722 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
723 return isl_space_set_tuple_id(space
, type
, id
);
725 isl_space_free(space
);
729 /* Does the tuple have a name?
731 isl_bool
isl_space_has_tuple_name(__isl_keep isl_space
*space
,
732 enum isl_dim_type type
)
736 if (!space_can_have_id(space
, type
))
737 return isl_bool_error
;
738 id
= space
->tuple_id
[type
- isl_dim_in
];
739 return isl_bool_ok(id
&& id
->name
);
742 __isl_keep
const char *isl_space_get_tuple_name(__isl_keep isl_space
*space
,
743 enum isl_dim_type type
)
748 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
750 id
= space
->tuple_id
[type
- isl_dim_in
];
751 return id
? id
->name
: NULL
;
754 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*space
,
755 enum isl_dim_type type
, unsigned pos
,
763 return isl_space_reset_dim_id(space
, type
, pos
);
764 if (!name_ok(space
->ctx
, s
))
766 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
767 return isl_space_set_dim_id(space
, type
, pos
, id
);
769 isl_space_free(space
);
773 /* Does the given dimension have a name?
775 isl_bool
isl_space_has_dim_name(__isl_keep isl_space
*space
,
776 enum isl_dim_type type
, unsigned pos
)
781 return isl_bool_error
;
782 id
= get_id(space
, type
, pos
);
783 return isl_bool_ok(id
&& id
->name
);
786 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*space
,
787 enum isl_dim_type type
, unsigned pos
)
789 isl_id
*id
= get_id(space
, type
, pos
);
790 return id
? id
->name
: NULL
;
793 int isl_space_find_dim_by_id(__isl_keep isl_space
*space
,
794 enum isl_dim_type type
, __isl_keep isl_id
*id
)
800 n
= isl_space_dim(space
, type
);
804 offset
= isl_space_offset(space
, type
);
805 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
)
806 if (space
->ids
[offset
+ i
] == id
)
812 int isl_space_find_dim_by_name(__isl_keep isl_space
*space
,
813 enum isl_dim_type type
, const char *name
)
819 n
= isl_space_dim(space
, type
);
823 offset
= isl_space_offset(space
, type
);
824 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
) {
825 isl_id
*id
= get_id(space
, type
, i
);
826 if (id
&& id
->name
&& !strcmp(id
->name
, name
))
833 /* Reset the user pointer on all identifiers of parameters and tuples
836 __isl_give isl_space
*isl_space_reset_user(__isl_take isl_space
*space
)
846 ctx
= isl_space_get_ctx(space
);
848 for (i
= 0; i
< space
->nparam
&& i
< space
->n_id
; ++i
) {
849 if (!isl_id_get_user(space
->ids
[i
]))
851 space
= isl_space_cow(space
);
854 name
= isl_id_get_name(space
->ids
[i
]);
855 id
= isl_id_alloc(ctx
, name
, NULL
);
856 isl_id_free(space
->ids
[i
]);
859 return isl_space_free(space
);
862 for (i
= 0; i
< 2; ++i
) {
863 if (!space
->tuple_id
[i
])
865 if (!isl_id_get_user(space
->tuple_id
[i
]))
867 space
= isl_space_cow(space
);
870 name
= isl_id_get_name(space
->tuple_id
[i
]);
871 id
= isl_id_alloc(ctx
, name
, NULL
);
872 isl_id_free(space
->tuple_id
[i
]);
873 space
->tuple_id
[i
] = id
;
875 return isl_space_free(space
);
878 for (i
= 0; i
< 2; ++i
) {
881 if (!space
->nested
[i
])
883 nested
= isl_space_take_nested(space
, i
);
884 nested
= isl_space_reset_user(nested
);
885 space
= isl_space_restore_nested(space
, i
, nested
);
893 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*space
,
894 enum isl_dim_type type
)
898 if (type
== isl_dim_in
)
899 return space
->tuple_id
[0];
900 if (type
== isl_dim_out
)
901 return space
->tuple_id
[1];
905 static __isl_keep isl_space
*nested(__isl_keep isl_space
*space
,
906 enum isl_dim_type type
)
910 if (type
== isl_dim_in
)
911 return space
->nested
[0];
912 if (type
== isl_dim_out
)
913 return space
->nested
[1];
917 /* Are the two spaces the same, apart from positions and names of parameters?
919 isl_bool
isl_space_has_equal_tuples(__isl_keep isl_space
*space1
,
920 __isl_keep isl_space
*space2
)
922 if (!space1
|| !space2
)
923 return isl_bool_error
;
924 if (space1
== space2
)
925 return isl_bool_true
;
926 return isl_space_tuple_is_equal(space1
, isl_dim_in
,
927 space2
, isl_dim_in
) &&
928 isl_space_tuple_is_equal(space1
, isl_dim_out
,
929 space2
, isl_dim_out
);
932 /* Check that the two spaces are the same,
933 * apart from positions and names of parameters.
935 isl_stat
isl_space_check_equal_tuples(__isl_keep isl_space
*space1
,
936 __isl_keep isl_space
*space2
)
940 is_equal
= isl_space_has_equal_tuples(space1
, space2
);
942 return isl_stat_error
;
944 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
945 "incompatible spaces", return isl_stat_error
);
950 /* Check if the tuple of type "type1" of "space1" is the same as
951 * the tuple of type "type2" of "space2".
953 * That is, check if the tuples have the same identifier, the same dimension
954 * and the same internal structure.
955 * The identifiers of the dimensions inside the tuples do not affect the result.
957 * Note that this function only checks the tuples themselves.
958 * If nested tuples are involved, then we need to be careful not
959 * to have result affected by possibly differing parameters
960 * in those nested tuples.
962 isl_bool
isl_space_tuple_is_equal(__isl_keep isl_space
*space1
,
963 enum isl_dim_type type1
, __isl_keep isl_space
*space2
,
964 enum isl_dim_type type2
)
967 isl_space
*nested1
, *nested2
;
969 if (!space1
|| !space2
)
970 return isl_bool_error
;
972 if (space1
== space2
&& type1
== type2
)
973 return isl_bool_true
;
975 if (n(space1
, type1
) != n(space2
, type2
))
976 return isl_bool_false
;
977 id1
= tuple_id(space1
, type1
);
978 id2
= tuple_id(space2
, type2
);
980 return isl_bool_false
;
981 if (id1
&& id1
!= id2
)
982 return isl_bool_false
;
983 nested1
= nested(space1
, type1
);
984 nested2
= nested(space2
, type2
);
985 if (!nested1
^ !nested2
)
986 return isl_bool_false
;
987 if (nested1
&& !isl_space_has_equal_tuples(nested1
, nested2
))
988 return isl_bool_false
;
989 return isl_bool_true
;
992 static isl_bool
match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
993 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
998 if (!space1
|| !space2
)
999 return isl_bool_error
;
1001 if (space1
== space2
&& type1
== type2
)
1002 return isl_bool_true
;
1004 equal
= isl_space_tuple_is_equal(space1
, type1
, space2
, type2
);
1005 if (equal
< 0 || !equal
)
1008 if (!space1
->ids
&& !space2
->ids
)
1009 return isl_bool_true
;
1011 for (i
= 0; i
< n(space1
, type1
); ++i
) {
1012 if (get_id(space1
, type1
, i
) != get_id(space2
, type2
, i
))
1013 return isl_bool_false
;
1015 return isl_bool_true
;
1018 /* Do "space1" and "space2" have the same parameters?
1020 isl_bool
isl_space_has_equal_params(__isl_keep isl_space
*space1
,
1021 __isl_keep isl_space
*space2
)
1023 return match(space1
, isl_dim_param
, space2
, isl_dim_param
);
1026 /* Do "space1" and "space2" have the same identifiers for all
1027 * the tuple variables?
1029 isl_bool
isl_space_has_equal_ids(__isl_keep isl_space
*space1
,
1030 __isl_keep isl_space
*space2
)
1034 equal
= match(space1
, isl_dim_in
, space2
, isl_dim_in
);
1035 if (equal
< 0 || !equal
)
1037 return match(space1
, isl_dim_out
, space2
, isl_dim_out
);
1040 isl_bool
isl_space_match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
1041 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1043 return match(space1
, type1
, space2
, type2
);
1046 static void get_ids(__isl_keep isl_space
*space
, enum isl_dim_type type
,
1047 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
1051 for (i
= 0; i
< n
; ++i
)
1052 ids
[i
] = get_id(space
, type
, first
+ i
);
1055 static __isl_give isl_space
*space_extend(__isl_take isl_space
*space
,
1056 unsigned nparam
, unsigned n_in
, unsigned n_out
)
1058 isl_id
**ids
= NULL
;
1062 if (space
->nparam
== nparam
&&
1063 space
->n_in
== n_in
&& space
->n_out
== n_out
)
1066 isl_assert(space
->ctx
, space
->nparam
<= nparam
, goto error
);
1067 isl_assert(space
->ctx
, space
->n_in
<= n_in
, goto error
);
1068 isl_assert(space
->ctx
, space
->n_out
<= n_out
, goto error
);
1070 space
= isl_space_cow(space
);
1076 n
= nparam
+ n_in
+ n_out
;
1077 if (n
< nparam
|| n
< n_in
|| n
< n_out
)
1078 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1079 "overflow in total number of dimensions",
1081 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n
);
1084 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
1085 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
+ nparam
);
1086 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1087 ids
+ nparam
+ n_in
);
1090 space
->n_id
= nparam
+ n_in
+ n_out
;
1092 space
->nparam
= nparam
;
1094 space
->n_out
= n_out
;
1099 isl_space_free(space
);
1103 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*space
,
1104 unsigned nparam
, unsigned n_in
, unsigned n_out
)
1106 return space_extend(space
, nparam
, n_in
, n_out
);
1109 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*space
,
1110 enum isl_dim_type type
, unsigned n
)
1112 space
= isl_space_reset(space
, type
);
1117 space
= space_extend(space
,
1118 space
->nparam
+ n
, space
->n_in
, space
->n_out
);
1119 if (space
&& space
->nested
[0] &&
1120 !(space
->nested
[0] = isl_space_add_dims(space
->nested
[0],
1123 if (space
&& space
->nested
[1] &&
1124 !(space
->nested
[1] = isl_space_add_dims(space
->nested
[1],
1129 return space_extend(space
,
1130 space
->nparam
, space
->n_in
+ n
, space
->n_out
);
1132 return space_extend(space
,
1133 space
->nparam
, space
->n_in
, space
->n_out
+ n
);
1135 isl_die(space
->ctx
, isl_error_invalid
,
1136 "cannot add dimensions of specified type", goto error
);
1139 isl_space_free(space
);
1143 /* Add a parameter with identifier "id" to "space", provided
1144 * it does not already appear in "space".
1146 __isl_give isl_space
*isl_space_add_param_id(__isl_take isl_space
*space
,
1147 __isl_take isl_id
*id
)
1154 if (isl_space_find_dim_by_id(space
, isl_dim_param
, id
) >= 0) {
1159 pos
= isl_space_dim(space
, isl_dim_param
);
1162 space
= isl_space_add_dims(space
, isl_dim_param
, 1);
1163 space
= isl_space_set_dim_id(space
, isl_dim_param
, pos
, id
);
1167 isl_space_free(space
);
1172 static int valid_dim_type(enum isl_dim_type type
)
1185 #define TYPE isl_space
1186 #include "check_type_range_templ.c"
1188 /* Insert "n" dimensions of type "type" at position "pos".
1189 * If we are inserting parameters, then they are also inserted in
1190 * any nested spaces.
1192 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*space
,
1193 enum isl_dim_type type
, unsigned pos
, unsigned n
)
1196 isl_id
**ids
= NULL
;
1201 return isl_space_reset(space
, type
);
1203 ctx
= isl_space_get_ctx(space
);
1204 if (!valid_dim_type(type
))
1205 isl_die(ctx
, isl_error_invalid
,
1206 "cannot insert dimensions of specified type",
1209 if (isl_space_check_range(space
, type
, pos
, 0) < 0)
1210 return isl_space_free(space
);
1212 space
= isl_space_cow(space
);
1217 enum isl_dim_type t
, o
= isl_dim_param
;
1220 ids
= isl_calloc_array(ctx
, isl_id
*,
1221 space
->nparam
+ space
->n_in
+ space
->n_out
+ n
);
1225 s
[isl_dim_param
- o
] = space
->nparam
;
1226 s
[isl_dim_in
- o
] = space
->n_in
;
1227 s
[isl_dim_out
- o
] = space
->n_out
;
1228 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1230 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1233 get_ids(space
, t
, 0, pos
, ids
+ off
);
1235 get_ids(space
, t
, pos
, s
[t
- o
] - pos
,
1237 off
+= s
[t
- o
] - pos
;
1242 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
+ n
;
1245 case isl_dim_param
: space
->nparam
+= n
; break;
1246 case isl_dim_in
: space
->n_in
+= n
; break;
1247 case isl_dim_out
: space
->n_out
+= n
; break;
1250 space
= isl_space_reset(space
, type
);
1252 if (type
== isl_dim_param
) {
1253 if (space
&& space
->nested
[0] &&
1254 !(space
->nested
[0] = isl_space_insert_dims(space
->nested
[0],
1255 isl_dim_param
, pos
, n
)))
1257 if (space
&& space
->nested
[1] &&
1258 !(space
->nested
[1] = isl_space_insert_dims(space
->nested
[1],
1259 isl_dim_param
, pos
, n
)))
1265 isl_space_free(space
);
1269 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*space
,
1270 enum isl_dim_type dst_type
, unsigned dst_pos
,
1271 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1275 space
= isl_space_reset(space
, src_type
);
1276 space
= isl_space_reset(space
, dst_type
);
1282 if (isl_space_check_range(space
, src_type
, src_pos
, n
) < 0)
1283 return isl_space_free(space
);
1285 if (dst_type
== src_type
&& dst_pos
== src_pos
)
1288 isl_assert(space
->ctx
, dst_type
!= src_type
, goto error
);
1290 space
= isl_space_cow(space
);
1296 enum isl_dim_type t
, o
= isl_dim_param
;
1299 ids
= isl_calloc_array(space
->ctx
, isl_id
*,
1300 space
->nparam
+ space
->n_in
+ space
->n_out
);
1304 s
[isl_dim_param
- o
] = space
->nparam
;
1305 s
[isl_dim_in
- o
] = space
->n_in
;
1306 s
[isl_dim_out
- o
] = space
->n_out
;
1307 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1308 if (t
== dst_type
) {
1309 get_ids(space
, t
, 0, dst_pos
, ids
+ off
);
1311 get_ids(space
, src_type
, src_pos
, n
, ids
+ off
);
1313 get_ids(space
, t
, dst_pos
, s
[t
- o
] - dst_pos
,
1315 off
+= s
[t
- o
] - dst_pos
;
1316 } else if (t
== src_type
) {
1317 get_ids(space
, t
, 0, src_pos
, ids
+ off
);
1319 get_ids(space
, t
, src_pos
+ n
,
1320 s
[t
- o
] - src_pos
- n
, ids
+ off
);
1321 off
+= s
[t
- o
] - src_pos
- n
;
1323 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1329 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
;
1333 case isl_dim_param
: space
->nparam
+= n
; break;
1334 case isl_dim_in
: space
->n_in
+= n
; break;
1335 case isl_dim_out
: space
->n_out
+= n
; break;
1340 case isl_dim_param
: space
->nparam
-= n
; break;
1341 case isl_dim_in
: space
->n_in
-= n
; break;
1342 case isl_dim_out
: space
->n_out
-= n
; break;
1346 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
1349 for (i
= 0; i
< 2; ++i
) {
1352 if (!space
->nested
[i
])
1354 nested
= isl_space_take_nested(space
, i
);
1355 nested
= isl_space_replace_params(nested
, space
);
1356 space
= isl_space_restore_nested(space
, i
, nested
);
1363 isl_space_free(space
);
1367 /* Check that "space1" and "space2" have the same parameters,
1368 * reporting an error if they do not.
1370 isl_stat
isl_space_check_equal_params(__isl_keep isl_space
*space1
,
1371 __isl_keep isl_space
*space2
)
1375 equal
= isl_space_has_equal_params(space1
, space2
);
1377 return isl_stat_error
;
1379 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
1380 "parameters need to match", return isl_stat_error
);
1384 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
1385 __isl_take isl_space
*right
)
1389 if (isl_space_check_equal_params(left
, right
) < 0)
1392 isl_assert(left
->ctx
,
1393 isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_in
),
1396 space
= isl_space_alloc(left
->ctx
,
1397 left
->nparam
, left
->n_in
, right
->n_out
);
1401 space
= copy_ids(space
, isl_dim_param
, 0, left
, isl_dim_param
);
1402 space
= copy_ids(space
, isl_dim_in
, 0, left
, isl_dim_in
);
1403 space
= copy_ids(space
, isl_dim_out
, 0, right
, isl_dim_out
);
1405 if (space
&& left
->tuple_id
[0] &&
1406 !(space
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
1408 if (space
&& right
->tuple_id
[1] &&
1409 !(space
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
1411 if (space
&& left
->nested
[0] &&
1412 !(space
->nested
[0] = isl_space_copy(left
->nested
[0])))
1414 if (space
&& right
->nested
[1] &&
1415 !(space
->nested
[1] = isl_space_copy(right
->nested
[1])))
1418 isl_space_free(left
);
1419 isl_space_free(right
);
1423 isl_space_free(left
);
1424 isl_space_free(right
);
1428 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1429 * { [A -> B] -> [C -> D] }.
1430 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1432 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
1433 __isl_take isl_space
*right
)
1435 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
1438 if (!left
|| !right
)
1441 is_set
= isl_space_is_set(left
);
1442 if (is_set
!= isl_space_is_set(right
))
1443 isl_die(isl_space_get_ctx(left
), isl_error_invalid
,
1444 "expecting either two set spaces or two map spaces",
1447 return isl_space_range_product(left
, right
);
1449 if (isl_space_check_equal_params(left
, right
) < 0)
1452 dom1
= isl_space_domain(isl_space_copy(left
));
1453 dom2
= isl_space_domain(isl_space_copy(right
));
1454 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1456 dom1
= isl_space_range(left
);
1457 dom2
= isl_space_range(right
);
1458 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1460 return isl_space_join(isl_space_reverse(nest1
), nest2
);
1462 isl_space_free(left
);
1463 isl_space_free(right
);
1467 /* Given two spaces { A -> C } and { B -> C }, construct the space
1470 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
1471 __isl_take isl_space
*right
)
1473 isl_space
*ran
, *dom1
, *dom2
, *nest
;
1475 if (isl_space_check_equal_params(left
, right
) < 0)
1478 if (!isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_out
))
1479 isl_die(left
->ctx
, isl_error_invalid
,
1480 "ranges need to match", goto error
);
1482 ran
= isl_space_range(isl_space_copy(left
));
1484 dom1
= isl_space_domain(left
);
1485 dom2
= isl_space_domain(right
);
1486 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1488 return isl_space_join(isl_space_reverse(nest
), ran
);
1490 isl_space_free(left
);
1491 isl_space_free(right
);
1495 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
1496 __isl_take isl_space
*right
)
1498 isl_space
*dom
, *ran1
, *ran2
, *nest
;
1500 if (isl_space_check_equal_params(left
, right
) < 0)
1503 if (!isl_space_tuple_is_equal(left
, isl_dim_in
, right
, isl_dim_in
))
1504 isl_die(left
->ctx
, isl_error_invalid
,
1505 "domains need to match", goto error
);
1507 dom
= isl_space_domain(isl_space_copy(left
));
1509 ran1
= isl_space_range(left
);
1510 ran2
= isl_space_range(right
);
1511 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
1513 return isl_space_join(isl_space_reverse(dom
), nest
);
1515 isl_space_free(left
);
1516 isl_space_free(right
);
1520 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1522 __isl_give isl_space
*isl_space_domain_factor_domain(
1523 __isl_take isl_space
*space
)
1530 if (!isl_space_domain_is_wrapping(space
))
1531 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1532 "domain not a product", return isl_space_free(space
));
1534 nested
= space
->nested
[0];
1535 domain
= isl_space_copy(space
);
1536 domain
= isl_space_drop_dims(domain
, isl_dim_in
,
1537 nested
->n_in
, nested
->n_out
);
1539 return isl_space_free(space
);
1540 if (nested
->tuple_id
[0]) {
1541 domain
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[0]);
1542 if (!domain
->tuple_id
[0])
1545 if (nested
->nested
[0]) {
1546 domain
->nested
[0] = isl_space_copy(nested
->nested
[0]);
1547 if (!domain
->nested
[0])
1551 isl_space_free(space
);
1554 isl_space_free(space
);
1555 isl_space_free(domain
);
1559 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1561 __isl_give isl_space
*isl_space_domain_factor_range(
1562 __isl_take isl_space
*space
)
1569 if (!isl_space_domain_is_wrapping(space
))
1570 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1571 "domain not a product", return isl_space_free(space
));
1573 nested
= space
->nested
[0];
1574 range
= isl_space_copy(space
);
1575 range
= isl_space_drop_dims(range
, isl_dim_in
, 0, nested
->n_in
);
1577 return isl_space_free(space
);
1578 if (nested
->tuple_id
[1]) {
1579 range
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[1]);
1580 if (!range
->tuple_id
[0])
1583 if (nested
->nested
[1]) {
1584 range
->nested
[0] = isl_space_copy(nested
->nested
[1]);
1585 if (!range
->nested
[0])
1589 isl_space_free(space
);
1592 isl_space_free(space
);
1593 isl_space_free(range
);
1597 /* Internal function that selects the domain of the map that is
1598 * embedded in either a set space or the range of a map space.
1599 * In particular, given a space of the form [A -> B], return the space A.
1600 * Given a space of the form A -> [B -> C], return the space A -> B.
1602 static __isl_give isl_space
*range_factor_domain(__isl_take isl_space
*space
)
1610 nested
= space
->nested
[1];
1611 domain
= isl_space_copy(space
);
1612 domain
= isl_space_drop_dims(domain
, isl_dim_out
,
1613 nested
->n_in
, nested
->n_out
);
1615 return isl_space_free(space
);
1616 if (nested
->tuple_id
[0]) {
1617 domain
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[0]);
1618 if (!domain
->tuple_id
[1])
1621 if (nested
->nested
[0]) {
1622 domain
->nested
[1] = isl_space_copy(nested
->nested
[0]);
1623 if (!domain
->nested
[1])
1627 isl_space_free(space
);
1630 isl_space_free(space
);
1631 isl_space_free(domain
);
1635 /* Given a space of the form A -> [B -> C], return the space A -> B.
1637 __isl_give isl_space
*isl_space_range_factor_domain(
1638 __isl_take isl_space
*space
)
1640 if (isl_space_check_range_is_wrapping(space
) < 0)
1641 return isl_space_free(space
);
1643 return range_factor_domain(space
);
1646 /* Given a space of the form [A -> B], return the space A.
1648 static __isl_give isl_space
*set_factor_domain(__isl_take isl_space
*space
)
1652 if (!isl_space_is_wrapping(space
))
1653 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1654 "not a product", return isl_space_free(space
));
1656 return range_factor_domain(space
);
1659 /* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1660 * Given a space of the form [A -> B], return the space A.
1662 __isl_give isl_space
*isl_space_factor_domain(__isl_take isl_space
*space
)
1666 if (isl_space_is_set(space
))
1667 return set_factor_domain(space
);
1668 space
= isl_space_domain_factor_domain(space
);
1669 space
= isl_space_range_factor_domain(space
);
1673 /* Internal function that selects the range of the map that is
1674 * embedded in either a set space or the range of a map space.
1675 * In particular, given a space of the form [A -> B], return the space B.
1676 * Given a space of the form A -> [B -> C], return the space A -> C.
1678 static __isl_give isl_space
*range_factor_range(__isl_take isl_space
*space
)
1686 nested
= space
->nested
[1];
1687 range
= isl_space_copy(space
);
1688 range
= isl_space_drop_dims(range
, isl_dim_out
, 0, nested
->n_in
);
1690 return isl_space_free(space
);
1691 if (nested
->tuple_id
[1]) {
1692 range
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[1]);
1693 if (!range
->tuple_id
[1])
1696 if (nested
->nested
[1]) {
1697 range
->nested
[1] = isl_space_copy(nested
->nested
[1]);
1698 if (!range
->nested
[1])
1702 isl_space_free(space
);
1705 isl_space_free(space
);
1706 isl_space_free(range
);
1710 /* Given a space of the form A -> [B -> C], return the space A -> C.
1712 __isl_give isl_space
*isl_space_range_factor_range(
1713 __isl_take isl_space
*space
)
1715 if (isl_space_check_range_is_wrapping(space
) < 0)
1716 return isl_space_free(space
);
1718 return range_factor_range(space
);
1721 /* Given a space of the form [A -> B], return the space B.
1723 static __isl_give isl_space
*set_factor_range(__isl_take isl_space
*space
)
1727 if (!isl_space_is_wrapping(space
))
1728 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1729 "not a product", return isl_space_free(space
));
1731 return range_factor_range(space
);
1734 /* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1735 * Given a space of the form [A -> B], return the space B.
1737 __isl_give isl_space
*isl_space_factor_range(__isl_take isl_space
*space
)
1741 if (isl_space_is_set(space
))
1742 return set_factor_range(space
);
1743 space
= isl_space_domain_factor_range(space
);
1744 space
= isl_space_range_factor_range(space
);
1748 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*space
)
1751 isl_id
**ids
= NULL
;
1756 ctx
= isl_space_get_ctx(space
);
1757 if (!isl_space_is_set(space
))
1758 isl_die(ctx
, isl_error_invalid
, "not a set space", goto error
);
1759 space
= isl_space_cow(space
);
1762 n_id
= space
->nparam
+ space
->n_out
+ space
->n_out
;
1763 if (n_id
> 0 && space
->ids
) {
1764 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n_id
);
1767 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
1768 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1769 ids
+ space
->nparam
);
1771 space
->n_in
= space
->n_out
;
1776 space
= copy_ids(space
, isl_dim_out
, 0, space
, isl_dim_in
);
1778 isl_id_free(space
->tuple_id
[0]);
1779 space
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[1]);
1780 isl_space_free(space
->nested
[0]);
1781 space
->nested
[0] = isl_space_copy(space
->nested
[1]);
1784 isl_space_free(space
);
1788 __isl_give isl_space
*isl_space_map_from_domain_and_range(
1789 __isl_take isl_space
*domain
, __isl_take isl_space
*range
)
1791 if (!domain
|| !range
)
1793 if (!isl_space_is_set(domain
))
1794 isl_die(isl_space_get_ctx(domain
), isl_error_invalid
,
1795 "domain is not a set space", goto error
);
1796 if (!isl_space_is_set(range
))
1797 isl_die(isl_space_get_ctx(range
), isl_error_invalid
,
1798 "range is not a set space", goto error
);
1799 return isl_space_join(isl_space_reverse(domain
), range
);
1801 isl_space_free(domain
);
1802 isl_space_free(range
);
1806 static __isl_give isl_space
*set_ids(__isl_take isl_space
*space
,
1807 enum isl_dim_type type
,
1808 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
1812 for (i
= 0; i
< n
; ++i
)
1813 space
= set_id(space
, type
, first
+ i
, ids
[i
]);
1818 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*space
)
1823 isl_id
**ids
= NULL
;
1826 equal
= match(space
, isl_dim_in
, space
, isl_dim_out
);
1828 return isl_space_free(space
);
1832 space
= isl_space_cow(space
);
1836 id
= space
->tuple_id
[0];
1837 space
->tuple_id
[0] = space
->tuple_id
[1];
1838 space
->tuple_id
[1] = id
;
1840 nested
= space
->nested
[0];
1841 space
->nested
[0] = space
->nested
[1];
1842 space
->nested
[1] = nested
;
1845 int n_id
= space
->n_in
+ space
->n_out
;
1846 ids
= isl_alloc_array(space
->ctx
, isl_id
*, n_id
);
1849 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
);
1850 get_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
+ space
->n_in
);
1854 space
->n_in
= space
->n_out
;
1858 space
= set_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
);
1859 space
= set_ids(space
, isl_dim_in
, 0, space
->n_in
,
1860 ids
+ space
->n_out
);
1867 isl_space_free(space
);
1871 /* Given a space A -> (B -> C), return the corresponding space
1874 * If the range tuple is named, then the name is only preserved
1875 * if B and C are equal tuples, in which case the output
1876 * of this function is identical to the input.
1878 __isl_give isl_space
*isl_space_range_reverse(__isl_take isl_space
*space
)
1883 if (isl_space_check_range_is_wrapping(space
) < 0)
1884 return isl_space_free(space
);
1886 nested
= isl_space_peek_nested(space
, 1);
1887 equal
= isl_space_tuple_is_equal(nested
, isl_dim_in
,
1888 nested
, isl_dim_out
);
1890 return isl_space_free(space
);
1892 nested
= isl_space_take_nested(space
, 1);
1893 nested
= isl_space_reverse(nested
);
1894 space
= isl_space_restore_nested(space
, 1, nested
);
1896 space
= isl_space_reset_tuple_id(space
, isl_dim_out
);
1901 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*space
,
1902 enum isl_dim_type type
, unsigned first
, unsigned num
)
1910 return isl_space_reset(space
, type
);
1912 if (!valid_dim_type(type
))
1913 isl_die(space
->ctx
, isl_error_invalid
,
1914 "cannot drop dimensions of specified type", goto error
);
1916 if (isl_space_check_range(space
, type
, first
, num
) < 0)
1917 return isl_space_free(space
);
1918 space
= isl_space_cow(space
);
1922 space
= extend_ids(space
);
1925 for (i
= 0; i
< num
; ++i
)
1926 isl_id_free(get_id(space
, type
, first
+ i
));
1927 for (i
= first
+num
; i
< n(space
, type
); ++i
)
1928 set_id(space
, type
, i
- num
, get_id(space
, type
, i
));
1931 get_ids(space
, isl_dim_in
, 0, space
->n_in
,
1932 space
->ids
+ offset(space
, isl_dim_in
) - num
);
1934 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1935 space
->ids
+ offset(space
, isl_dim_out
) - num
);
1942 case isl_dim_param
: space
->nparam
-= num
; break;
1943 case isl_dim_in
: space
->n_in
-= num
; break;
1944 case isl_dim_out
: space
->n_out
-= num
; break;
1947 space
= isl_space_reset(space
, type
);
1948 if (type
== isl_dim_param
) {
1949 if (space
&& space
->nested
[0] &&
1950 !(space
->nested
[0] = isl_space_drop_dims(space
->nested
[0],
1951 isl_dim_param
, first
, num
)))
1953 if (space
&& space
->nested
[1] &&
1954 !(space
->nested
[1] = isl_space_drop_dims(space
->nested
[1],
1955 isl_dim_param
, first
, num
)))
1960 isl_space_free(space
);
1964 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*space
,
1965 unsigned first
, unsigned n
)
1969 return isl_space_drop_dims(space
, isl_dim_in
, first
, n
);
1972 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*space
,
1973 unsigned first
, unsigned n
)
1977 return isl_space_drop_dims(space
, isl_dim_out
, first
, n
);
1980 /* Remove all parameters from "space".
1982 __isl_give isl_space
*isl_space_drop_all_params(__isl_take isl_space
*space
)
1986 nparam
= isl_space_dim(space
, isl_dim_param
);
1988 return isl_space_free(space
);
1989 return isl_space_drop_dims(space
, isl_dim_param
, 0, nparam
);
1992 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*space
)
1996 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, space
->n_out
);
1997 space
= isl_space_reverse(space
);
1998 space
= mark_as_set(space
);
2002 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*space
)
2006 if (!isl_space_is_set(space
))
2007 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2008 "not a set space", goto error
);
2009 space
= isl_space_reverse(space
);
2010 space
= isl_space_reset(space
, isl_dim_out
);
2013 isl_space_free(space
);
2017 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*space
)
2021 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, space
->n_in
);
2022 space
= mark_as_set(space
);
2026 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*space
)
2030 if (!isl_space_is_set(space
))
2031 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2032 "not a set space", goto error
);
2033 return isl_space_reset(space
, isl_dim_in
);
2035 isl_space_free(space
);
2039 /* Given a map space A -> B, return the map space [A -> B] -> A.
2041 __isl_give isl_space
*isl_space_domain_map(__isl_take isl_space
*space
)
2045 domain
= isl_space_from_range(isl_space_domain(isl_space_copy(space
)));
2046 space
= isl_space_from_domain(isl_space_wrap(space
));
2047 space
= isl_space_join(space
, domain
);
2052 /* Given a map space A -> B, return the map space [A -> B] -> B.
2054 __isl_give isl_space
*isl_space_range_map(__isl_take isl_space
*space
)
2058 range
= isl_space_from_range(isl_space_range(isl_space_copy(space
)));
2059 space
= isl_space_from_domain(isl_space_wrap(space
));
2060 space
= isl_space_join(space
, range
);
2065 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
2067 isl_size n_in
, n_out
;
2069 if (isl_space_is_params(space
))
2071 n_in
= isl_space_dim(space
, isl_dim_in
);
2072 n_out
= isl_space_dim(space
, isl_dim_out
);
2073 if (n_in
< 0 || n_out
< 0)
2074 return isl_space_free(space
);
2075 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, n_in
);
2076 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, n_out
);
2077 space
= mark_as_params(space
);
2081 __isl_give isl_space
*isl_space_set_from_params(__isl_take isl_space
*space
)
2085 if (!isl_space_is_params(space
))
2086 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2087 "not a parameter space", goto error
);
2088 return isl_space_reset(space
, isl_dim_set
);
2090 isl_space_free(space
);
2094 /* Add an unnamed tuple of dimension "dim" to "space".
2095 * This requires "space" to be a parameter or set space.
2097 * In particular, if "space" is a parameter space, then return
2098 * a set space with the given dimension.
2099 * If "space" is a set space, then return a map space
2100 * with "space" as domain and a range of the given dimension.
2102 __isl_give isl_space
*isl_space_add_unnamed_tuple_ui(
2103 __isl_take isl_space
*space
, unsigned dim
)
2105 isl_bool is_params
, is_set
;
2107 is_params
= isl_space_is_params(space
);
2108 is_set
= isl_space_is_set(space
);
2109 if (is_params
< 0 || is_set
< 0)
2110 return isl_space_free(space
);
2111 if (!is_params
&& !is_set
)
2112 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2113 "cannot add tuple to map space",
2114 return isl_space_free(space
));
2116 space
= isl_space_set_from_params(space
);
2118 space
= isl_space_from_domain(space
);
2119 space
= isl_space_add_dims(space
, isl_dim_out
, dim
);
2123 /* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"
2125 * This requires "space" to be a parameter or set space.
2127 __isl_give isl_space
*isl_space_add_named_tuple_id_ui(
2128 __isl_take isl_space
*space
, __isl_take isl_id
*tuple_id
, unsigned dim
)
2130 space
= isl_space_add_unnamed_tuple_ui(space
, dim
);
2131 space
= isl_space_set_tuple_id(space
, isl_dim_out
, tuple_id
);
2135 /* Check that the identifiers in "tuple" do not appear as parameters
2138 static isl_stat
check_fresh_params(__isl_keep isl_space
*space
,
2139 __isl_keep isl_multi_id
*tuple
)
2144 n
= isl_multi_id_size(tuple
);
2146 return isl_stat_error
;
2147 for (i
= 0; i
< n
; ++i
) {
2151 id
= isl_multi_id_get_at(tuple
, i
);
2153 return isl_stat_error
;
2154 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2157 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2158 "parameters not unique", return isl_stat_error
);
2164 /* Add the identifiers in "tuple" as parameters of "space"
2165 * that are known to be fresh.
2167 static __isl_give isl_space
*add_bind_params(__isl_take isl_space
*space
,
2168 __isl_keep isl_multi_id
*tuple
)
2173 first
= isl_space_dim(space
, isl_dim_param
);
2174 n
= isl_multi_id_size(tuple
);
2175 if (first
< 0 || n
< 0)
2176 return isl_space_free(space
);
2177 space
= isl_space_add_dims(space
, isl_dim_param
, n
);
2178 for (i
= 0; i
< n
; ++i
) {
2181 id
= isl_multi_id_get_at(tuple
, i
);
2182 space
= isl_space_set_dim_id(space
,
2183 isl_dim_param
, first
+ i
, id
);
2189 /* Internal function that removes the set tuple of "space",
2190 * which is assumed to correspond to the range space of "tuple", and
2191 * adds the identifiers in "tuple" as fresh parameters.
2192 * In other words, the set dimensions of "space" are reinterpreted
2193 * as parameters, but stay in the same global positions.
2195 __isl_give isl_space
*isl_space_bind_set(__isl_take isl_space
*space
,
2196 __isl_keep isl_multi_id
*tuple
)
2198 isl_space
*tuple_space
;
2200 if (isl_space_check_is_set(space
) < 0)
2201 return isl_space_free(space
);
2202 tuple_space
= isl_multi_id_peek_space(tuple
);
2203 if (isl_space_check_equal_tuples(tuple_space
, space
) < 0)
2204 return isl_space_free(space
);
2205 if (check_fresh_params(space
, tuple
) < 0)
2206 return isl_space_free(space
);
2207 space
= isl_space_params(space
);
2208 space
= add_bind_params(space
, tuple
);
2212 /* Internal function that removes the domain tuple of the map space "space",
2213 * which is assumed to correspond to the range space of "tuple", and
2214 * adds the identifiers in "tuple" as fresh parameters.
2215 * In other words, the domain dimensions of "space" are reinterpreted
2216 * as parameters, but stay in the same global positions.
2218 __isl_give isl_space
*isl_space_bind_map_domain(__isl_take isl_space
*space
,
2219 __isl_keep isl_multi_id
*tuple
)
2221 isl_space
*tuple_space
;
2223 if (isl_space_check_is_map(space
) < 0)
2224 return isl_space_free(space
);
2225 tuple_space
= isl_multi_id_peek_space(tuple
);
2226 if (isl_space_check_domain_tuples(tuple_space
, space
) < 0)
2227 return isl_space_free(space
);
2228 if (check_fresh_params(space
, tuple
) < 0)
2229 return isl_space_free(space
);
2230 space
= isl_space_range(space
);
2231 space
= add_bind_params(space
, tuple
);
2235 /* Internal function that, given a space of the form [A -> B] -> C and
2236 * a tuple of identifiers in A, returns a space B -> C with
2237 * the identifiers in "tuple" added as fresh parameters.
2238 * In other words, the domain dimensions of the wrapped relation
2239 * in the domain of "space" are reinterpreted
2240 * as parameters, but stay in the same global positions.
2242 __isl_give isl_space
*isl_space_bind_domain_wrapped_domain(
2243 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2245 isl_space
*tuple_space
;
2247 if (isl_space_check_is_map(space
) < 0)
2248 return isl_space_free(space
);
2249 tuple_space
= isl_multi_id_peek_space(tuple
);
2250 if (isl_space_check_domain_wrapped_domain_tuples(tuple_space
,
2252 return isl_space_free(space
);
2253 if (check_fresh_params(space
, tuple
) < 0)
2254 return isl_space_free(space
);
2255 space
= isl_space_domain_factor_range(space
);
2256 space
= add_bind_params(space
, tuple
);
2260 /* Insert a domain tuple in "space" corresponding to the set space "domain".
2261 * In particular, if "space" is a parameter space, then the result
2262 * is the set space "domain" combined with the parameters of "space".
2263 * If "space" is a set space, then the result
2264 * is a map space with "domain" as domain and the original space as range.
2266 static __isl_give isl_space
*isl_space_insert_domain(
2267 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
2271 domain
= isl_space_replace_params(domain
, space
);
2273 is_params
= isl_space_is_params(space
);
2274 if (is_params
< 0) {
2275 isl_space_free(domain
);
2276 space
= isl_space_free(space
);
2277 } else if (is_params
) {
2278 isl_space_free(space
);
2281 space
= isl_space_map_from_domain_and_range(domain
, space
);
2286 /* Internal function that introduces a domain in "space"
2287 * corresponding to the range space of "tuple".
2288 * In particular, if "space" is a parameter space, then the result
2289 * is a set space. If "space" is a set space, then the result
2290 * is a map space with the original space as range.
2291 * Parameters that correspond to the identifiers in "tuple" are removed.
2293 * The parameters are removed in reverse order (under the assumption
2294 * that they appear in the same order in "multi") because
2295 * it is slightly more efficient to remove parameters at the end.
2297 * For pretty-printing purposes, the identifiers of the set dimensions
2298 * of the introduced domain are set to the identifiers in "tuple".
2300 __isl_give isl_space
*isl_space_unbind_params_insert_domain(
2301 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2305 isl_space
*tuple_space
;
2307 n
= isl_multi_id_size(tuple
);
2308 if (!space
|| n
< 0)
2309 return isl_space_free(space
);
2310 for (i
= n
- 1; i
>= 0; --i
) {
2314 id
= isl_multi_id_get_id(tuple
, i
);
2316 return isl_space_free(space
);
2317 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2321 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
2323 tuple_space
= isl_multi_id_get_space(tuple
);
2324 for (i
= 0; i
< n
; ++i
) {
2327 id
= isl_multi_id_get_id(tuple
, i
);
2328 tuple_space
= isl_space_set_dim_id(tuple_space
,
2329 isl_dim_set
, i
, id
);
2331 return isl_space_insert_domain(space
, tuple_space
);
2334 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*space
,
2340 is_set
= isl_space_is_set(space
);
2342 return isl_space_free(space
);
2343 if (n_div
== 0 && is_set
&&
2344 space
->nparam
== 0 && space
->n_in
== 0 && space
->n_id
== 0)
2345 return isl_space_reset(space
, isl_dim_out
);
2346 space
= isl_space_cow(space
);
2349 space
->n_out
+= space
->nparam
+ space
->n_in
+ n_div
;
2353 for (i
= 0; i
< space
->n_id
; ++i
)
2354 isl_id_free(get_id(space
, isl_dim_out
, i
));
2356 space
= isl_space_reset(space
, isl_dim_in
);
2357 space
= isl_space_reset(space
, isl_dim_out
);
2358 space
= mark_as_set(space
);
2363 /* Are the two spaces the same, including positions and names of parameters?
2365 isl_bool
isl_space_is_equal(__isl_keep isl_space
*space1
,
2366 __isl_keep isl_space
*space2
)
2370 if (!space1
|| !space2
)
2371 return isl_bool_error
;
2372 if (space1
== space2
)
2373 return isl_bool_true
;
2374 equal
= isl_space_has_equal_params(space1
, space2
);
2375 if (equal
< 0 || !equal
)
2377 return isl_space_has_equal_tuples(space1
, space2
);
2380 /* Do the tuples of "space1" correspond to those of the domain of "space2"?
2381 * That is, is "space1" equal to the domain of "space2", ignoring parameters.
2383 * "space2" is allowed to be a set space, in which case "space1"
2384 * should be a parameter space.
2386 isl_bool
isl_space_has_domain_tuples(__isl_keep isl_space
*space1
,
2387 __isl_keep isl_space
*space2
)
2391 is_set
= isl_space_is_set(space1
);
2392 if (is_set
< 0 || !is_set
)
2394 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2395 space2
, isl_dim_in
);
2398 /* Do the tuples of "space1" correspond to those of the range of "space2"?
2399 * That is, is "space1" equal to the range of "space2", ignoring parameters.
2401 * "space2" is allowed to be the space of a set,
2402 * in which case it should be equal to "space1", ignoring parameters.
2404 isl_bool
isl_space_has_range_tuples(__isl_keep isl_space
*space1
,
2405 __isl_keep isl_space
*space2
)
2409 is_set
= isl_space_is_set(space1
);
2410 if (is_set
< 0 || !is_set
)
2412 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2413 space2
, isl_dim_out
);
2416 /* Check that the tuples of "space1" correspond to those
2417 * of the domain of "space2".
2418 * That is, check that "space1" is equal to the domain of "space2",
2419 * ignoring parameters.
2421 isl_stat
isl_space_check_domain_tuples(__isl_keep isl_space
*space1
,
2422 __isl_keep isl_space
*space2
)
2426 is_equal
= isl_space_has_domain_tuples(space1
, space2
);
2428 return isl_stat_error
;
2430 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
2431 "incompatible spaces", return isl_stat_error
);
2436 /* Check that the tuples of "space1" correspond to those
2437 * of the domain of the wrapped relation in the domain of "space2".
2438 * That is, check that "space1" is equal to this domain,
2439 * ignoring parameters.
2441 isl_stat
isl_space_check_domain_wrapped_domain_tuples(
2442 __isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
2447 domain
= isl_space_unwrap(isl_space_domain(isl_space_copy(space2
)));
2448 r
= isl_space_check_domain_tuples(space1
, domain
);
2449 isl_space_free(domain
);
2454 /* Is space1 equal to the domain of space2?
2456 * In the internal version we also allow space2 to be the space of a set,
2457 * provided space1 is a parameter space.
2459 isl_bool
isl_space_is_domain_internal(__isl_keep isl_space
*space1
,
2460 __isl_keep isl_space
*space2
)
2462 isl_bool equal_params
;
2464 if (!space1
|| !space2
)
2465 return isl_bool_error
;
2466 equal_params
= isl_space_has_equal_params(space1
, space2
);
2467 if (equal_params
< 0 || !equal_params
)
2468 return equal_params
;
2469 return isl_space_has_domain_tuples(space1
, space2
);
2472 /* Is space1 equal to the domain of space2?
2474 isl_bool
isl_space_is_domain(__isl_keep isl_space
*space1
,
2475 __isl_keep isl_space
*space2
)
2478 return isl_bool_error
;
2479 if (!isl_space_is_map(space2
))
2480 return isl_bool_false
;
2481 return isl_space_is_domain_internal(space1
, space2
);
2484 /* Is space1 equal to the range of space2?
2486 * In the internal version, space2 is allowed to be the space of a set,
2487 * in which case it should be equal to space1.
2489 isl_bool
isl_space_is_range_internal(__isl_keep isl_space
*space1
,
2490 __isl_keep isl_space
*space2
)
2492 isl_bool equal_params
;
2494 if (!space1
|| !space2
)
2495 return isl_bool_error
;
2496 equal_params
= isl_space_has_equal_params(space1
, space2
);
2497 if (equal_params
< 0 || !equal_params
)
2498 return equal_params
;
2499 return isl_space_has_range_tuples(space1
, space2
);
2502 /* Is space1 equal to the range of space2?
2504 isl_bool
isl_space_is_range(__isl_keep isl_space
*space1
,
2505 __isl_keep isl_space
*space2
)
2508 return isl_bool_error
;
2509 if (!isl_space_is_map(space2
))
2510 return isl_bool_false
;
2511 return isl_space_is_range_internal(space1
, space2
);
2514 /* Update "hash" by hashing in the parameters of "space".
2516 static uint32_t isl_hash_params(uint32_t hash
, __isl_keep isl_space
*space
)
2524 isl_hash_byte(hash
, space
->nparam
% 256);
2526 for (i
= 0; i
< space
->nparam
; ++i
) {
2527 id
= get_id(space
, isl_dim_param
, i
);
2528 hash
= isl_hash_id(hash
, id
);
2534 /* Update "hash" by hashing in the tuples of "space".
2535 * Changes in this function should be reflected in isl_hash_tuples_domain.
2537 static uint32_t isl_hash_tuples(uint32_t hash
, __isl_keep isl_space
*space
)
2544 isl_hash_byte(hash
, space
->n_in
% 256);
2545 isl_hash_byte(hash
, space
->n_out
% 256);
2547 id
= tuple_id(space
, isl_dim_in
);
2548 hash
= isl_hash_id(hash
, id
);
2549 id
= tuple_id(space
, isl_dim_out
);
2550 hash
= isl_hash_id(hash
, id
);
2552 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2553 hash
= isl_hash_tuples(hash
, space
->nested
[1]);
2558 /* Update "hash" by hashing in the domain tuple of "space".
2559 * The result of this function is equal to the result of applying
2560 * isl_hash_tuples to the domain of "space".
2562 static uint32_t isl_hash_tuples_domain(uint32_t hash
,
2563 __isl_keep isl_space
*space
)
2570 isl_hash_byte(hash
, 0);
2571 isl_hash_byte(hash
, space
->n_in
% 256);
2573 hash
= isl_hash_id(hash
, &isl_id_none
);
2574 id
= tuple_id(space
, isl_dim_in
);
2575 hash
= isl_hash_id(hash
, id
);
2577 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2582 /* Return a hash value that digests the tuples of "space",
2583 * i.e., that ignores the parameters.
2585 uint32_t isl_space_get_tuple_hash(__isl_keep isl_space
*space
)
2592 hash
= isl_hash_init();
2593 hash
= isl_hash_tuples(hash
, space
);
2598 /* Return the hash value of "space".
2599 * Changes in this function should be reflected
2600 * in isl_space_get_full_domain_hash.
2602 uint32_t isl_space_get_full_hash(__isl_keep isl_space
*space
)
2609 hash
= isl_hash_init();
2610 hash
= isl_hash_params(hash
, space
);
2611 hash
= isl_hash_tuples(hash
, space
);
2616 /* Return the hash value of the domain of "space".
2617 * That is, isl_space_get_full_domain_hash(space) is equal to
2618 * isl_space_get_full_hash(isl_space_domain(space)).
2620 uint32_t isl_space_get_full_domain_hash(__isl_keep isl_space
*space
)
2627 hash
= isl_hash_init();
2628 hash
= isl_hash_params(hash
, space
);
2629 hash
= isl_hash_tuples_domain(hash
, space
);
2634 /* Is "space" the space of a set wrapping a map space?
2636 isl_bool
isl_space_is_wrapping(__isl_keep isl_space
*space
)
2639 return isl_bool_error
;
2641 if (!isl_space_is_set(space
))
2642 return isl_bool_false
;
2644 return isl_bool_ok(space
->nested
[1] != NULL
);
2647 /* Is "space" the space of a map where the domain is a wrapped map space?
2649 isl_bool
isl_space_domain_is_wrapping(__isl_keep isl_space
*space
)
2652 return isl_bool_error
;
2654 if (isl_space_is_set(space
))
2655 return isl_bool_false
;
2657 return isl_bool_ok(space
->nested
[0] != NULL
);
2660 /* Is "space" the space of a map where the range is a wrapped map space?
2662 isl_bool
isl_space_range_is_wrapping(__isl_keep isl_space
*space
)
2665 return isl_bool_error
;
2667 if (isl_space_is_set(space
))
2668 return isl_bool_false
;
2670 return isl_bool_ok(space
->nested
[1] != NULL
);
2673 /* Is "space" a product of two spaces?
2674 * That is, is it a wrapping set space or a map space
2675 * with wrapping domain and range?
2677 isl_bool
isl_space_is_product(__isl_keep isl_space
*space
)
2680 isl_bool is_product
;
2682 is_set
= isl_space_is_set(space
);
2684 return isl_bool_error
;
2686 return isl_space_is_wrapping(space
);
2687 is_product
= isl_space_domain_is_wrapping(space
);
2688 if (is_product
< 0 || !is_product
)
2690 return isl_space_range_is_wrapping(space
);
2693 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*space
)
2700 wrap
= isl_space_set_alloc(space
->ctx
,
2701 space
->nparam
, space
->n_in
+ space
->n_out
);
2703 wrap
= copy_ids(wrap
, isl_dim_param
, 0, space
, isl_dim_param
);
2704 wrap
= copy_ids(wrap
, isl_dim_set
, 0, space
, isl_dim_in
);
2705 wrap
= copy_ids(wrap
, isl_dim_set
, space
->n_in
, space
, isl_dim_out
);
2710 wrap
->nested
[1] = space
;
2714 isl_space_free(space
);
2718 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*space
)
2725 if (!isl_space_is_wrapping(space
))
2726 isl_die(space
->ctx
, isl_error_invalid
, "not a wrapping space",
2729 unwrap
= isl_space_copy(space
->nested
[1]);
2730 isl_space_free(space
);
2734 isl_space_free(space
);
2738 isl_bool
isl_space_is_named_or_nested(__isl_keep isl_space
*space
,
2739 enum isl_dim_type type
)
2741 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
2742 return isl_bool_false
;
2744 return isl_bool_error
;
2745 if (space
->tuple_id
[type
- isl_dim_in
])
2746 return isl_bool_true
;
2747 if (space
->nested
[type
- isl_dim_in
])
2748 return isl_bool_true
;
2749 return isl_bool_false
;
2752 isl_bool
isl_space_may_be_set(__isl_keep isl_space
*space
)
2758 return isl_bool_error
;
2759 if (isl_space_is_set(space
))
2760 return isl_bool_true
;
2761 n_in
= isl_space_dim(space
, isl_dim_in
);
2763 return isl_bool_error
;
2765 return isl_bool_false
;
2766 nested
= isl_space_is_named_or_nested(space
, isl_dim_in
);
2767 if (nested
< 0 || nested
)
2768 return isl_bool_not(nested
);
2769 return isl_bool_true
;
2772 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*space
,
2773 enum isl_dim_type type
)
2775 if (!isl_space_is_named_or_nested(space
, type
))
2778 space
= isl_space_cow(space
);
2782 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
2783 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
2784 isl_space_free(space
->nested
[type
- isl_dim_in
]);
2785 space
->nested
[type
- isl_dim_in
] = NULL
;
2790 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*space
)
2794 if (!space
->nested
[0] && !space
->nested
[1])
2797 if (space
->nested
[0])
2798 space
= isl_space_reset(space
, isl_dim_in
);
2799 if (space
&& space
->nested
[1])
2800 space
= isl_space_reset(space
, isl_dim_out
);
2805 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*space
)
2809 if (!space
->nested
[0])
2812 return isl_space_reset(space
, isl_dim_in
);
2815 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*space
)
2819 if (!space
->nested
[1])
2822 return isl_space_reset(space
, isl_dim_out
);
2825 /* Replace the parameters of dst by those of src.
2827 __isl_give isl_space
*isl_space_replace_params(__isl_take isl_space
*dst
,
2828 __isl_keep isl_space
*src
)
2830 isl_size dst_dim
, src_dim
;
2831 isl_bool equal_params
;
2832 enum isl_dim_type type
= isl_dim_param
;
2834 equal_params
= isl_space_has_equal_params(dst
, src
);
2835 if (equal_params
< 0)
2836 return isl_space_free(dst
);
2840 dst
= isl_space_cow(dst
);
2842 dst_dim
= isl_space_dim(dst
, type
);
2843 src_dim
= isl_space_dim(src
, type
);
2844 if (dst_dim
< 0 || src_dim
< 0)
2847 dst
= isl_space_drop_dims(dst
, type
, 0, dst_dim
);
2848 dst
= isl_space_add_dims(dst
, type
, src_dim
);
2849 dst
= copy_ids(dst
, type
, 0, src
, type
);
2853 for (i
= 0; i
<= 1; ++i
) {
2856 if (!dst
->nested
[i
])
2858 nested
= isl_space_take_nested(dst
, i
);
2859 nested
= isl_space_replace_params(nested
, src
);
2860 dst
= isl_space_restore_nested(dst
, i
, nested
);
2868 isl_space_free(dst
);
2872 /* Given two tuples ("dst_type" in "dst" and "src_type" in "src")
2873 * of the same size, check if any of the dimensions in the "dst" tuple
2874 * have no identifier, while the corresponding dimensions in "src"
2875 * does have an identifier,
2876 * If so, copy the identifier over to "dst".
2878 __isl_give isl_space
*isl_space_copy_ids_if_unset(__isl_take isl_space
*dst
,
2879 enum isl_dim_type dst_type
, __isl_keep isl_space
*src
,
2880 enum isl_dim_type src_type
)
2885 n
= isl_space_dim(dst
, dst_type
);
2887 return isl_space_free(dst
);
2888 for (i
= 0; i
< n
; ++i
) {
2892 set
= isl_space_has_dim_id(dst
, dst_type
, i
);
2894 return isl_space_free(dst
);
2898 set
= isl_space_has_dim_id(src
, src_type
, i
);
2900 return isl_space_free(dst
);
2904 id
= isl_space_get_dim_id(src
, src_type
, i
);
2905 dst
= isl_space_set_dim_id(dst
, dst_type
, i
, id
);
2911 /* Given a space "space" of a set, create a space
2912 * for the lift of the set. In particular, the result
2913 * is of the form lifted[space -> local[..]], with n_local variables in the
2914 * range of the wrapped map.
2916 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*space
,
2919 isl_space
*local_space
;
2924 local_space
= isl_space_dup(space
);
2925 local_space
= isl_space_drop_dims(local_space
, isl_dim_set
, 0,
2927 local_space
= isl_space_add_dims(local_space
, isl_dim_set
, n_local
);
2928 local_space
= isl_space_set_tuple_name(local_space
,
2929 isl_dim_set
, "local");
2930 space
= isl_space_join(isl_space_from_domain(space
),
2931 isl_space_from_range(local_space
));
2932 space
= isl_space_wrap(space
);
2933 space
= isl_space_set_tuple_name(space
, isl_dim_set
, "lifted");
2938 isl_bool
isl_space_can_zip(__isl_keep isl_space
*space
)
2942 is_set
= isl_space_is_set(space
);
2944 return isl_bool_error
;
2946 return isl_bool_false
;
2947 return isl_space_is_product(space
);
2950 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*space
)
2952 isl_space
*dom
, *ran
;
2953 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
2955 if (!isl_space_can_zip(space
))
2956 isl_die(space
->ctx
, isl_error_invalid
, "space cannot be zipped",
2961 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
2962 ran
= isl_space_unwrap(isl_space_range(space
));
2963 dom_dom
= isl_space_domain(isl_space_copy(dom
));
2964 dom_ran
= isl_space_range(dom
);
2965 ran_dom
= isl_space_domain(isl_space_copy(ran
));
2966 ran_ran
= isl_space_range(ran
);
2967 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
2968 isl_space_from_range(ran_dom
));
2969 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
2970 isl_space_from_range(ran_ran
));
2971 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
2972 isl_space_from_range(isl_space_wrap(ran
)));
2974 isl_space_free(space
);
2978 /* Can we apply isl_space_curry to "space"?
2979 * That is, does is it have a map space with a nested relation in its domain?
2981 isl_bool
isl_space_can_curry(__isl_keep isl_space
*space
)
2983 return isl_space_domain_is_wrapping(space
);
2986 /* Given a space (A -> B) -> C, return the corresponding space
2989 __isl_give isl_space
*isl_space_curry(__isl_take isl_space
*space
)
2991 isl_space
*dom
, *ran
;
2992 isl_space
*dom_dom
, *dom_ran
;
2997 if (!isl_space_can_curry(space
))
2998 isl_die(space
->ctx
, isl_error_invalid
,
2999 "space cannot be curried", goto error
);
3001 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
3002 ran
= isl_space_range(space
);
3003 dom_dom
= isl_space_domain(isl_space_copy(dom
));
3004 dom_ran
= isl_space_range(dom
);
3005 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
3006 isl_space_from_range(ran
));
3007 return isl_space_join(isl_space_from_domain(dom_dom
),
3008 isl_space_from_range(isl_space_wrap(ran
)));
3010 isl_space_free(space
);
3014 /* Can isl_space_range_curry be applied to "space"?
3015 * That is, does it have a nested relation in its range,
3016 * the domain of which is itself a nested relation?
3018 isl_bool
isl_space_can_range_curry(__isl_keep isl_space
*space
)
3023 return isl_bool_error
;
3024 can
= isl_space_range_is_wrapping(space
);
3025 if (can
< 0 || !can
)
3027 return isl_space_can_curry(space
->nested
[1]);
3030 /* Given a space A -> ((B -> C) -> D), return the corresponding space
3031 * A -> (B -> (C -> D)).
3033 __isl_give isl_space
*isl_space_range_curry(__isl_take isl_space
*space
)
3040 if (!isl_space_can_range_curry(space
))
3041 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3042 "space range cannot be curried",
3043 return isl_space_free(space
));
3045 nested
= isl_space_take_nested(space
, 1);
3046 nested
= isl_space_curry(nested
);
3047 space
= isl_space_restore_nested(space
, 1, nested
);
3052 /* Can we apply isl_space_uncurry to "space"?
3053 * That is, does it have a map space with a nested relation in its range?
3055 isl_bool
isl_space_can_uncurry(__isl_keep isl_space
*space
)
3057 return isl_space_range_is_wrapping(space
);
3060 /* Given a space A -> (B -> C), return the corresponding space
3063 __isl_give isl_space
*isl_space_uncurry(__isl_take isl_space
*space
)
3065 isl_space
*dom
, *ran
;
3066 isl_space
*ran_dom
, *ran_ran
;
3071 if (!isl_space_can_uncurry(space
))
3072 isl_die(space
->ctx
, isl_error_invalid
,
3073 "space cannot be uncurried",
3074 return isl_space_free(space
));
3076 dom
= isl_space_domain(isl_space_copy(space
));
3077 ran
= isl_space_unwrap(isl_space_range(space
));
3078 ran_dom
= isl_space_domain(isl_space_copy(ran
));
3079 ran_ran
= isl_space_range(ran
);
3080 dom
= isl_space_join(isl_space_from_domain(dom
),
3081 isl_space_from_range(ran_dom
));
3082 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
3083 isl_space_from_range(ran_ran
));
3086 isl_bool
isl_space_has_named_params(__isl_keep isl_space
*space
)
3092 return isl_bool_error
;
3093 if (space
->nparam
== 0)
3094 return isl_bool_true
;
3095 off
= isl_space_offset(space
, isl_dim_param
);
3096 if (off
+ space
->nparam
> space
->n_id
)
3097 return isl_bool_false
;
3098 for (i
= 0; i
< space
->nparam
; ++i
)
3099 if (!space
->ids
[off
+ i
])
3100 return isl_bool_false
;
3101 return isl_bool_true
;
3104 /* Check that "space" has only named parameters, reporting an error
3107 isl_stat
isl_space_check_named_params(__isl_keep isl_space
*space
)
3111 named
= isl_space_has_named_params(space
);
3113 return isl_stat_error
;
3115 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3116 "unexpected unnamed parameters", return isl_stat_error
);
3121 /* Align the initial parameters of space1 to match the order in space2.
3123 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*space1
,
3124 __isl_take isl_space
*space2
)
3126 isl_reordering
*exp
;
3128 if (isl_space_check_named_params(space1
) < 0 ||
3129 isl_space_check_named_params(space2
) < 0)
3132 exp
= isl_parameter_alignment_reordering(space1
, space2
);
3133 exp
= isl_reordering_extend_space(exp
, space1
);
3134 isl_space_free(space2
);
3135 space1
= isl_reordering_get_space(exp
);
3136 isl_reordering_free(exp
);
3139 isl_space_free(space1
);
3140 isl_space_free(space2
);
3144 /* Given the space of set (domain), construct a space for a map
3145 * with as domain the given space and as range the range of "model".
3147 __isl_give isl_space
*isl_space_extend_domain_with_range(
3148 __isl_take isl_space
*space
, __isl_take isl_space
*model
)
3155 space
= isl_space_from_domain(space
);
3156 n_out
= isl_space_dim(model
, isl_dim_out
);
3159 space
= isl_space_add_dims(space
, isl_dim_out
, n_out
);
3160 if (isl_space_has_tuple_id(model
, isl_dim_out
))
3161 space
= isl_space_set_tuple_id(space
, isl_dim_out
,
3162 isl_space_get_tuple_id(model
, isl_dim_out
));
3165 if (model
->nested
[1]) {
3166 isl_space
*nested
= isl_space_copy(model
->nested
[1]);
3167 isl_size n_nested
, n_space
;
3168 nested
= isl_space_align_params(nested
, isl_space_copy(space
));
3169 n_nested
= isl_space_dim(nested
, isl_dim_param
);
3170 n_space
= isl_space_dim(space
, isl_dim_param
);
3171 if (n_nested
< 0 || n_space
< 0)
3173 if (n_nested
> n_space
)
3174 nested
= isl_space_drop_dims(nested
, isl_dim_param
,
3175 n_space
, n_nested
- n_space
);
3178 space
->nested
[1] = nested
;
3180 isl_space_free(model
);
3183 isl_space_free(model
);
3184 isl_space_free(space
);
3188 /* Compare the "type" dimensions of two isl_spaces.
3190 * The order is fairly arbitrary.
3192 static int isl_space_cmp_type(__isl_keep isl_space
*space1
,
3193 __isl_keep isl_space
*space2
, enum isl_dim_type type
)
3196 isl_size dim1
, dim2
;
3197 isl_space
*nested1
, *nested2
;
3199 dim1
= isl_space_dim(space1
, type
);
3200 dim2
= isl_space_dim(space2
, type
);
3201 if (dim1
< 0 || dim2
< 0)
3206 cmp
= isl_id_cmp(tuple_id(space1
, type
), tuple_id(space2
, type
));
3210 nested1
= nested(space1
, type
);
3211 nested2
= nested(space2
, type
);
3212 if (!nested1
!= !nested2
)
3213 return !nested1
- !nested2
;
3216 return isl_space_cmp(nested1
, nested2
);
3221 /* Compare two isl_spaces.
3223 * The order is fairly arbitrary.
3225 int isl_space_cmp(__isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
3230 if (space1
== space2
)
3237 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_param
);
3240 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_in
);
3243 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_out
);
3247 if (!space1
->ids
&& !space2
->ids
)
3250 for (i
= 0; i
< n(space1
, isl_dim_param
); ++i
) {
3251 cmp
= isl_id_cmp(get_id(space1
, isl_dim_param
, i
),
3252 get_id(space2
, isl_dim_param
, i
));