2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2013-2014 Ecole Normale Superieure
5 * Copyright 2018-2019 Cerebras Systems
7 * Use of this software is governed by the MIT license
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
19 #include <isl_space_private.h>
20 #include <isl_id_private.h>
21 #include <isl_reordering.h>
23 isl_ctx
*isl_space_get_ctx(__isl_keep isl_space
*space
)
25 return space
? space
->ctx
: NULL
;
28 __isl_give isl_space
*isl_space_alloc(isl_ctx
*ctx
,
29 unsigned nparam
, unsigned n_in
, unsigned n_out
)
33 space
= isl_alloc_type(ctx
, struct isl_space
);
40 space
->nparam
= nparam
;
44 space
->tuple_id
[0] = NULL
;
45 space
->tuple_id
[1] = NULL
;
47 space
->nested
[0] = NULL
;
48 space
->nested
[1] = NULL
;
56 /* Mark the space as being that of a set, by setting the domain tuple
59 static __isl_give isl_space
*mark_as_set(__isl_take isl_space
*space
)
61 space
= isl_space_cow(space
);
64 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
68 /* Is the space that of a set?
70 isl_bool
isl_space_is_set(__isl_keep isl_space
*space
)
73 return isl_bool_error
;
74 if (space
->n_in
!= 0 || space
->nested
[0])
75 return isl_bool_false
;
76 if (space
->tuple_id
[0] != &isl_id_none
)
77 return isl_bool_false
;
81 /* Check that "space" is a set space.
83 isl_stat
isl_space_check_is_set(__isl_keep isl_space
*space
)
87 is_set
= isl_space_is_set(space
);
89 return isl_stat_error
;
91 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
92 "space is not a set", return isl_stat_error
);
96 /* Is the given space that of a map?
98 isl_bool
isl_space_is_map(__isl_keep isl_space
*space
)
103 return isl_bool_error
;
104 r
= space
->tuple_id
[0] != &isl_id_none
&&
105 space
->tuple_id
[1] != &isl_id_none
;
106 return isl_bool_ok(r
);
109 /* Check that "space" is the space of a map.
111 static isl_stat
isl_space_check_is_map(__isl_keep isl_space
*space
)
115 is_space
= isl_space_is_map(space
);
117 return isl_stat_error
;
119 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
120 "expecting map space", return isl_stat_error
);
124 /* Check that "space" is the space of a map
125 * where the domain is a wrapped map space.
127 isl_stat
isl_space_check_domain_is_wrapping(__isl_keep isl_space
*space
)
131 wrapping
= isl_space_domain_is_wrapping(space
);
133 return isl_stat_error
;
135 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
136 "domain not a product", return isl_stat_error
);
140 /* Check that "space" is the space of a map
141 * where the range is a wrapped map space.
143 isl_stat
isl_space_check_range_is_wrapping(__isl_keep isl_space
*space
)
147 wrapping
= isl_space_range_is_wrapping(space
);
149 return isl_stat_error
;
151 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
152 "range not a product", return isl_stat_error
);
156 __isl_give isl_space
*isl_space_set_alloc(isl_ctx
*ctx
,
157 unsigned nparam
, unsigned dim
)
160 space
= isl_space_alloc(ctx
, nparam
, 0, dim
);
161 space
= mark_as_set(space
);
165 /* Mark the space as being that of a parameter domain, by setting
166 * both tuples to isl_id_none.
168 static __isl_give isl_space
*mark_as_params(isl_space
*space
)
172 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
173 space
= isl_space_set_tuple_id(space
, isl_dim_out
, &isl_id_none
);
177 /* Is the space that of a parameter domain?
179 isl_bool
isl_space_is_params(__isl_keep isl_space
*space
)
182 return isl_bool_error
;
183 if (space
->n_in
!= 0 || space
->nested
[0] ||
184 space
->n_out
!= 0 || space
->nested
[1])
185 return isl_bool_false
;
186 if (space
->tuple_id
[0] != &isl_id_none
)
187 return isl_bool_false
;
188 if (space
->tuple_id
[1] != &isl_id_none
)
189 return isl_bool_false
;
190 return isl_bool_true
;
193 /* Create a space for a parameter domain.
195 __isl_give isl_space
*isl_space_params_alloc(isl_ctx
*ctx
, unsigned nparam
)
198 space
= isl_space_alloc(ctx
, nparam
, 0, 0);
199 space
= mark_as_params(space
);
203 /* Create a space for a parameter domain, without any parameters.
205 __isl_give isl_space
*isl_space_unit(isl_ctx
*ctx
)
207 return isl_space_params_alloc(ctx
, 0);
210 static isl_size
global_pos(__isl_keep isl_space
*space
,
211 enum isl_dim_type type
, unsigned pos
)
213 if (isl_space_check_range(space
, type
, pos
, 1) < 0)
214 return isl_size_error
;
220 return pos
+ space
->nparam
;
222 return pos
+ space
->nparam
+ space
->n_in
;
224 isl_assert(isl_space_get_ctx(space
), 0, return isl_size_error
);
226 return isl_size_error
;
229 /* Extend length of ids array to the total number of dimensions.
231 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*space
)
237 dim
= isl_space_dim(space
, isl_dim_all
);
239 return isl_space_free(space
);
240 if (dim
<= space
->n_id
)
244 space
->ids
= isl_calloc_array(space
->ctx
, isl_id
*, dim
);
248 ids
= isl_realloc_array(space
->ctx
, space
->ids
, isl_id
*, dim
);
252 for (i
= space
->n_id
; i
< dim
; ++i
)
253 space
->ids
[i
] = NULL
;
260 isl_space_free(space
);
264 static __isl_give isl_space
*set_id(__isl_take isl_space
*space
,
265 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
269 space
= isl_space_cow(space
);
271 gpos
= global_pos(space
, type
, pos
);
275 if (gpos
>= space
->n_id
) {
278 space
= extend_ids(space
);
283 space
->ids
[gpos
] = id
;
288 isl_space_free(space
);
292 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*space
,
293 enum isl_dim_type type
, unsigned pos
)
297 gpos
= global_pos(space
, type
, pos
);
300 if (gpos
>= space
->n_id
)
302 return space
->ids
[gpos
];
305 /* Return the nested space at the given position.
307 static __isl_keep isl_space
*isl_space_peek_nested(__isl_keep isl_space
*space
,
312 if (!space
->nested
[pos
])
313 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
314 "no nested space", return NULL
);
315 return space
->nested
[pos
];
318 static unsigned offset(__isl_keep isl_space
*space
, enum isl_dim_type type
)
321 case isl_dim_param
: return 0;
322 case isl_dim_in
: return space
->nparam
;
323 case isl_dim_out
: return space
->nparam
+ space
->n_in
;
328 static unsigned n(__isl_keep isl_space
*space
, enum isl_dim_type type
)
331 case isl_dim_param
: return space
->nparam
;
332 case isl_dim_in
: return space
->n_in
;
333 case isl_dim_out
: return space
->n_out
;
335 return space
->nparam
+ space
->n_in
+ space
->n_out
;
340 isl_size
isl_space_dim(__isl_keep isl_space
*space
, enum isl_dim_type type
)
343 return isl_size_error
;
344 return n(space
, type
);
347 /* Return the dimensionality of tuple "inner" within the wrapped relation
348 * inside tuple "outer".
350 isl_size
isl_space_wrapped_dim(__isl_keep isl_space
*space
,
351 enum isl_dim_type outer
, enum isl_dim_type inner
)
356 return isl_size_error
;
357 if (outer
!= isl_dim_in
&& outer
!= isl_dim_out
)
358 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
359 "only input, output and set tuples "
360 "can have nested relations", return isl_size_error
);
361 pos
= outer
- isl_dim_in
;
362 return isl_space_dim(isl_space_peek_nested(space
, pos
), inner
);
365 unsigned isl_space_offset(__isl_keep isl_space
*space
, enum isl_dim_type type
)
369 return offset(space
, type
);
372 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
373 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
374 enum isl_dim_type src_type
)
382 for (i
= 0; i
< n(src
, src_type
); ++i
) {
383 id
= get_id(src
, src_type
, i
);
386 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
393 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*space
)
398 dup
= isl_space_alloc(space
->ctx
,
399 space
->nparam
, space
->n_in
, space
->n_out
);
402 if (space
->tuple_id
[0] &&
403 !(dup
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[0])))
405 if (space
->tuple_id
[1] &&
406 !(dup
->tuple_id
[1] = isl_id_copy(space
->tuple_id
[1])))
408 if (space
->nested
[0] &&
409 !(dup
->nested
[0] = isl_space_copy(space
->nested
[0])))
411 if (space
->nested
[1] &&
412 !(dup
->nested
[1] = isl_space_copy(space
->nested
[1])))
416 dup
= copy_ids(dup
, isl_dim_param
, 0, space
, isl_dim_param
);
417 dup
= copy_ids(dup
, isl_dim_in
, 0, space
, isl_dim_in
);
418 dup
= copy_ids(dup
, isl_dim_out
, 0, space
, isl_dim_out
);
425 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*space
)
433 return isl_space_dup(space
);
436 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*space
)
445 __isl_null isl_space
*isl_space_free(__isl_take isl_space
*space
)
452 if (--space
->ref
> 0)
455 isl_id_free(space
->tuple_id
[0]);
456 isl_id_free(space
->tuple_id
[1]);
458 isl_space_free(space
->nested
[0]);
459 isl_space_free(space
->nested
[1]);
461 for (i
= 0; i
< space
->n_id
; ++i
)
462 isl_id_free(space
->ids
[i
]);
464 isl_ctx_deref(space
->ctx
);
471 /* Check if "s" is a valid dimension or tuple name.
472 * We currently only forbid names that look like a number.
474 * s is assumed to be non-NULL.
476 static int name_ok(isl_ctx
*ctx
, const char *s
)
481 dummy
= strtol(s
, &p
, 0);
483 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
489 /* Return a copy of the nested space at the given position.
491 static __isl_keep isl_space
*isl_space_get_nested(__isl_keep isl_space
*space
,
494 return isl_space_copy(isl_space_peek_nested(space
, pos
));
497 /* Return the nested space at the given position.
498 * This may be either a copy or the nested space itself
499 * if there is only one reference to "space".
500 * This allows the nested space to be modified inplace
501 * if both "space" and the nested space have only a single reference.
502 * The caller is not allowed to modify "space" between this call and
503 * a subsequent call to isl_space_restore_nested.
504 * The only exception is that isl_space_free can be called instead.
506 static __isl_give isl_space
*isl_space_take_nested(__isl_keep isl_space
*space
,
514 return isl_space_get_nested(space
, pos
);
515 nested
= space
->nested
[pos
];
516 space
->nested
[pos
] = NULL
;
520 /* Replace the nested space at the given position by "nested",
521 * where this nested space of "space" may be missing
522 * due to a preceding call to isl_space_take_nested.
523 * However, in this case, "space" only has a single reference and
524 * then the call to isl_space_cow has no effect.
526 static __isl_give isl_space
*isl_space_restore_nested(
527 __isl_take isl_space
*space
, int pos
, __isl_take isl_space
*nested
)
529 if (!space
|| !nested
)
532 if (space
->nested
[pos
] == nested
) {
533 isl_space_free(nested
);
537 space
= isl_space_cow(space
);
540 isl_space_free(space
->nested
[pos
]);
541 space
->nested
[pos
] = nested
;
545 isl_space_free(space
);
546 isl_space_free(nested
);
550 /* Is it possible for the given dimension type to have a tuple id?
552 static int space_can_have_id(__isl_keep isl_space
*space
,
553 enum isl_dim_type type
)
557 if (isl_space_is_params(space
))
558 isl_die(space
->ctx
, isl_error_invalid
,
559 "parameter spaces don't have tuple ids", return 0);
560 if (isl_space_is_set(space
) && type
!= isl_dim_set
)
561 isl_die(space
->ctx
, isl_error_invalid
,
562 "set spaces can only have a set id", return 0);
563 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
564 isl_die(space
->ctx
, isl_error_invalid
,
565 "only input, output and set tuples can have ids",
571 /* Does the tuple have an id?
573 isl_bool
isl_space_has_tuple_id(__isl_keep isl_space
*space
,
574 enum isl_dim_type type
)
576 if (!space_can_have_id(space
, type
))
577 return isl_bool_error
;
578 return isl_bool_ok(space
->tuple_id
[type
- isl_dim_in
] != NULL
);
581 /* Does the domain tuple of the map space "space" have an identifier?
583 isl_bool
isl_space_has_domain_tuple_id(__isl_keep isl_space
*space
)
585 if (isl_space_check_is_map(space
) < 0)
586 return isl_bool_error
;
587 return isl_space_has_tuple_id(space
, isl_dim_in
);
590 /* Does the range tuple of the map space "space" have an identifier?
592 isl_bool
isl_space_has_range_tuple_id(__isl_keep isl_space
*space
)
594 if (isl_space_check_is_map(space
) < 0)
595 return isl_bool_error
;
596 return isl_space_has_tuple_id(space
, isl_dim_out
);
599 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*space
,
600 enum isl_dim_type type
)
606 has_id
= isl_space_has_tuple_id(space
, type
);
610 isl_die(space
->ctx
, isl_error_invalid
,
611 "tuple has no id", return NULL
);
612 return isl_id_copy(space
->tuple_id
[type
- isl_dim_in
]);
615 /* Return the identifier of the domain tuple of the map space "space",
616 * assuming it has one.
618 __isl_give isl_id
*isl_space_get_domain_tuple_id(
619 __isl_keep isl_space
*space
)
621 if (isl_space_check_is_map(space
) < 0)
623 return isl_space_get_tuple_id(space
, isl_dim_in
);
626 /* Return the identifier of the range tuple of the map space "space",
627 * assuming it has one.
629 __isl_give isl_id
*isl_space_get_range_tuple_id(
630 __isl_keep isl_space
*space
)
632 if (isl_space_check_is_map(space
) < 0)
634 return isl_space_get_tuple_id(space
, isl_dim_out
);
637 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*space
,
638 enum isl_dim_type type
, __isl_take isl_id
*id
)
640 space
= isl_space_cow(space
);
643 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
644 isl_die(space
->ctx
, isl_error_invalid
,
645 "only input, output and set tuples can have names",
648 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
649 space
->tuple_id
[type
- isl_dim_in
] = id
;
654 isl_space_free(space
);
658 /* Replace the identifier of the domain tuple of the map space "space"
661 __isl_give isl_space
*isl_space_set_domain_tuple_id(
662 __isl_take isl_space
*space
, __isl_take isl_id
*id
)
664 if (isl_space_check_is_map(space
) < 0)
665 space
= isl_space_free(space
);
666 return isl_space_set_tuple_id(space
, isl_dim_in
, id
);
669 /* Replace the identifier of the range tuple of the map space "space"
672 __isl_give isl_space
*isl_space_set_range_tuple_id(
673 __isl_take isl_space
*space
, __isl_take isl_id
*id
)
675 if (isl_space_check_is_map(space
) < 0)
676 space
= isl_space_free(space
);
677 return isl_space_set_tuple_id(space
, isl_dim_out
, id
);
680 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*space
,
681 enum isl_dim_type type
)
683 space
= isl_space_cow(space
);
686 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
687 isl_die(space
->ctx
, isl_error_invalid
,
688 "only input, output and set tuples can have names",
691 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
692 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
696 isl_space_free(space
);
700 /* Set the id of the given dimension of "space" to "id".
701 * If the dimension already has an id, then it is replaced.
702 * If the dimension is a parameter, then we need to change it
703 * in the nested spaces (if any) as well.
705 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*space
,
706 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
708 space
= isl_space_cow(space
);
712 if (type
== isl_dim_param
) {
715 for (i
= 0; i
< 2; ++i
) {
716 if (!space
->nested
[i
])
719 isl_space_set_dim_id(space
->nested
[i
],
720 type
, pos
, isl_id_copy(id
));
721 if (!space
->nested
[i
])
726 isl_id_free(get_id(space
, type
, pos
));
727 return set_id(space
, type
, pos
, id
);
730 isl_space_free(space
);
734 /* Reset the id of the given dimension of "space".
735 * If the dimension already has an id, then it is removed.
736 * If the dimension is a parameter, then we need to reset it
737 * in the nested spaces (if any) as well.
739 __isl_give isl_space
*isl_space_reset_dim_id(__isl_take isl_space
*space
,
740 enum isl_dim_type type
, unsigned pos
)
742 space
= isl_space_cow(space
);
746 if (type
== isl_dim_param
) {
749 for (i
= 0; i
< 2; ++i
) {
750 if (!space
->nested
[i
])
753 isl_space_reset_dim_id(space
->nested
[i
],
755 if (!space
->nested
[i
])
760 isl_id_free(get_id(space
, type
, pos
));
761 return set_id(space
, type
, pos
, NULL
);
763 isl_space_free(space
);
767 isl_bool
isl_space_has_dim_id(__isl_keep isl_space
*space
,
768 enum isl_dim_type type
, unsigned pos
)
771 return isl_bool_error
;
772 return isl_bool_ok(get_id(space
, type
, pos
) != NULL
);
775 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*space
,
776 enum isl_dim_type type
, unsigned pos
)
780 if (!get_id(space
, type
, pos
))
781 isl_die(space
->ctx
, isl_error_invalid
,
782 "dim has no id", return NULL
);
783 return isl_id_copy(get_id(space
, type
, pos
));
786 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*space
,
787 enum isl_dim_type type
, const char *s
)
795 return isl_space_reset_tuple_id(space
, type
);
797 if (!name_ok(space
->ctx
, s
))
800 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
801 return isl_space_set_tuple_id(space
, type
, id
);
803 isl_space_free(space
);
807 /* Does the tuple have a name?
809 isl_bool
isl_space_has_tuple_name(__isl_keep isl_space
*space
,
810 enum isl_dim_type type
)
814 if (!space_can_have_id(space
, type
))
815 return isl_bool_error
;
816 id
= space
->tuple_id
[type
- isl_dim_in
];
817 return isl_bool_ok(id
&& id
->name
);
820 __isl_keep
const char *isl_space_get_tuple_name(__isl_keep isl_space
*space
,
821 enum isl_dim_type type
)
826 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
828 id
= space
->tuple_id
[type
- isl_dim_in
];
829 return id
? id
->name
: NULL
;
832 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*space
,
833 enum isl_dim_type type
, unsigned pos
,
841 return isl_space_reset_dim_id(space
, type
, pos
);
842 if (!name_ok(space
->ctx
, s
))
844 id
= isl_id_alloc(space
->ctx
, s
, NULL
);
845 return isl_space_set_dim_id(space
, type
, pos
, id
);
847 isl_space_free(space
);
851 /* Does the given dimension have a name?
853 isl_bool
isl_space_has_dim_name(__isl_keep isl_space
*space
,
854 enum isl_dim_type type
, unsigned pos
)
859 return isl_bool_error
;
860 id
= get_id(space
, type
, pos
);
861 return isl_bool_ok(id
&& id
->name
);
864 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*space
,
865 enum isl_dim_type type
, unsigned pos
)
867 isl_id
*id
= get_id(space
, type
, pos
);
868 return id
? id
->name
: NULL
;
871 int isl_space_find_dim_by_id(__isl_keep isl_space
*space
,
872 enum isl_dim_type type
, __isl_keep isl_id
*id
)
878 n
= isl_space_dim(space
, type
);
882 offset
= isl_space_offset(space
, type
);
883 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
)
884 if (space
->ids
[offset
+ i
] == id
)
890 int isl_space_find_dim_by_name(__isl_keep isl_space
*space
,
891 enum isl_dim_type type
, const char *name
)
897 n
= isl_space_dim(space
, type
);
901 offset
= isl_space_offset(space
, type
);
902 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
) {
903 isl_id
*id
= get_id(space
, type
, i
);
904 if (id
&& id
->name
&& !strcmp(id
->name
, name
))
911 /* Reset the user pointer on all identifiers of parameters and tuples
914 __isl_give isl_space
*isl_space_reset_user(__isl_take isl_space
*space
)
924 ctx
= isl_space_get_ctx(space
);
926 for (i
= 0; i
< space
->nparam
&& i
< space
->n_id
; ++i
) {
927 if (!isl_id_get_user(space
->ids
[i
]))
929 space
= isl_space_cow(space
);
932 name
= isl_id_get_name(space
->ids
[i
]);
933 id
= isl_id_alloc(ctx
, name
, NULL
);
934 isl_id_free(space
->ids
[i
]);
937 return isl_space_free(space
);
940 for (i
= 0; i
< 2; ++i
) {
941 if (!space
->tuple_id
[i
])
943 if (!isl_id_get_user(space
->tuple_id
[i
]))
945 space
= isl_space_cow(space
);
948 name
= isl_id_get_name(space
->tuple_id
[i
]);
949 id
= isl_id_alloc(ctx
, name
, NULL
);
950 isl_id_free(space
->tuple_id
[i
]);
951 space
->tuple_id
[i
] = id
;
953 return isl_space_free(space
);
956 for (i
= 0; i
< 2; ++i
) {
959 if (!space
->nested
[i
])
961 nested
= isl_space_take_nested(space
, i
);
962 nested
= isl_space_reset_user(nested
);
963 space
= isl_space_restore_nested(space
, i
, nested
);
971 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*space
,
972 enum isl_dim_type type
)
976 if (type
== isl_dim_in
)
977 return space
->tuple_id
[0];
978 if (type
== isl_dim_out
)
979 return space
->tuple_id
[1];
983 static __isl_keep isl_space
*nested(__isl_keep isl_space
*space
,
984 enum isl_dim_type type
)
988 if (type
== isl_dim_in
)
989 return space
->nested
[0];
990 if (type
== isl_dim_out
)
991 return space
->nested
[1];
995 /* Are the two spaces the same, apart from positions and names of parameters?
997 isl_bool
isl_space_has_equal_tuples(__isl_keep isl_space
*space1
,
998 __isl_keep isl_space
*space2
)
1000 if (!space1
|| !space2
)
1001 return isl_bool_error
;
1002 if (space1
== space2
)
1003 return isl_bool_true
;
1004 return isl_space_tuple_is_equal(space1
, isl_dim_in
,
1005 space2
, isl_dim_in
) &&
1006 isl_space_tuple_is_equal(space1
, isl_dim_out
,
1007 space2
, isl_dim_out
);
1010 /* Check that a match involving "space" was successful.
1011 * That is, check that "match" is equal to isl_bool_true.
1013 static isl_stat
check_match(__isl_keep isl_space
*space
, isl_bool match
)
1016 return isl_stat_error
;
1018 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1019 "incompatible spaces", return isl_stat_error
);
1024 /* Check that the two spaces are the same,
1025 * apart from positions and names of parameters.
1027 isl_stat
isl_space_check_equal_tuples(__isl_keep isl_space
*space1
,
1028 __isl_keep isl_space
*space2
)
1032 is_equal
= isl_space_has_equal_tuples(space1
, space2
);
1033 return check_match(space1
, is_equal
);
1036 /* Check if the tuple of type "type1" of "space1" is the same as
1037 * the tuple of type "type2" of "space2".
1039 * That is, check if the tuples have the same identifier, the same dimension
1040 * and the same internal structure.
1041 * The identifiers of the dimensions inside the tuples do not affect the result.
1043 * Note that this function only checks the tuples themselves.
1044 * If nested tuples are involved, then we need to be careful not
1045 * to have result affected by possibly differing parameters
1046 * in those nested tuples.
1048 isl_bool
isl_space_tuple_is_equal(__isl_keep isl_space
*space1
,
1049 enum isl_dim_type type1
, __isl_keep isl_space
*space2
,
1050 enum isl_dim_type type2
)
1053 isl_space
*nested1
, *nested2
;
1055 if (!space1
|| !space2
)
1056 return isl_bool_error
;
1058 if (space1
== space2
&& type1
== type2
)
1059 return isl_bool_true
;
1061 if (n(space1
, type1
) != n(space2
, type2
))
1062 return isl_bool_false
;
1063 id1
= tuple_id(space1
, type1
);
1064 id2
= tuple_id(space2
, type2
);
1066 return isl_bool_false
;
1067 if (id1
&& id1
!= id2
)
1068 return isl_bool_false
;
1069 nested1
= nested(space1
, type1
);
1070 nested2
= nested(space2
, type2
);
1071 if (!nested1
^ !nested2
)
1072 return isl_bool_false
;
1073 if (nested1
&& !isl_space_has_equal_tuples(nested1
, nested2
))
1074 return isl_bool_false
;
1075 return isl_bool_true
;
1078 /* Is the tuple "inner" within the wrapped relation inside tuple "outer"
1079 * of "space1" equal to tuple "type2" of "space2"?
1081 isl_bool
isl_space_wrapped_tuple_is_equal(__isl_keep isl_space
*space1
,
1082 enum isl_dim_type outer
, enum isl_dim_type inner
,
1083 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1089 return isl_bool_error
;
1090 if (outer
!= isl_dim_in
&& outer
!= isl_dim_out
)
1091 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
1092 "only input, output and set tuples "
1093 "can have nested relations", return isl_bool_error
);
1094 pos
= outer
- isl_dim_in
;
1095 nested
= isl_space_peek_nested(space1
, pos
);
1096 return isl_space_tuple_is_equal(nested
, inner
, space2
, type2
);
1099 /* Check that the tuple "inner" within the wrapped relation inside tuple "outer"
1100 * of "space1" is equal to tuple "type2" of "space2".
1102 isl_stat
isl_space_check_wrapped_tuple_is_equal(__isl_keep isl_space
*space1
,
1103 enum isl_dim_type outer
, enum isl_dim_type inner
,
1104 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1108 is_equal
= isl_space_wrapped_tuple_is_equal(space1
, outer
, inner
,
1110 return check_match(space1
, is_equal
);
1113 static isl_bool
match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
1114 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1119 if (!space1
|| !space2
)
1120 return isl_bool_error
;
1122 if (space1
== space2
&& type1
== type2
)
1123 return isl_bool_true
;
1125 equal
= isl_space_tuple_is_equal(space1
, type1
, space2
, type2
);
1126 if (equal
< 0 || !equal
)
1129 if (!space1
->ids
&& !space2
->ids
)
1130 return isl_bool_true
;
1132 for (i
= 0; i
< n(space1
, type1
); ++i
) {
1133 if (get_id(space1
, type1
, i
) != get_id(space2
, type2
, i
))
1134 return isl_bool_false
;
1136 return isl_bool_true
;
1139 /* Do "space1" and "space2" have the same parameters?
1141 isl_bool
isl_space_has_equal_params(__isl_keep isl_space
*space1
,
1142 __isl_keep isl_space
*space2
)
1144 return match(space1
, isl_dim_param
, space2
, isl_dim_param
);
1147 /* Do "space1" and "space2" have the same identifiers for all
1148 * the tuple variables?
1150 isl_bool
isl_space_has_equal_ids(__isl_keep isl_space
*space1
,
1151 __isl_keep isl_space
*space2
)
1155 equal
= match(space1
, isl_dim_in
, space2
, isl_dim_in
);
1156 if (equal
< 0 || !equal
)
1158 return match(space1
, isl_dim_out
, space2
, isl_dim_out
);
1161 isl_bool
isl_space_match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
1162 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
1164 return match(space1
, type1
, space2
, type2
);
1167 static void get_ids(__isl_keep isl_space
*space
, enum isl_dim_type type
,
1168 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
1172 for (i
= 0; i
< n
; ++i
)
1173 ids
[i
] = get_id(space
, type
, first
+ i
);
1176 static __isl_give isl_space
*space_extend(__isl_take isl_space
*space
,
1177 unsigned nparam
, unsigned n_in
, unsigned n_out
)
1179 isl_id
**ids
= NULL
;
1183 if (space
->nparam
== nparam
&&
1184 space
->n_in
== n_in
&& space
->n_out
== n_out
)
1187 isl_assert(space
->ctx
, space
->nparam
<= nparam
, goto error
);
1188 isl_assert(space
->ctx
, space
->n_in
<= n_in
, goto error
);
1189 isl_assert(space
->ctx
, space
->n_out
<= n_out
, goto error
);
1191 space
= isl_space_cow(space
);
1197 n
= nparam
+ n_in
+ n_out
;
1198 if (n
< nparam
|| n
< n_in
|| n
< n_out
)
1199 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1200 "overflow in total number of dimensions",
1202 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n
);
1205 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
1206 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
+ nparam
);
1207 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1208 ids
+ nparam
+ n_in
);
1211 space
->n_id
= nparam
+ n_in
+ n_out
;
1213 space
->nparam
= nparam
;
1215 space
->n_out
= n_out
;
1220 isl_space_free(space
);
1224 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*space
,
1225 unsigned nparam
, unsigned n_in
, unsigned n_out
)
1227 return space_extend(space
, nparam
, n_in
, n_out
);
1230 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*space
,
1231 enum isl_dim_type type
, unsigned n
)
1233 space
= isl_space_reset(space
, type
);
1238 space
= space_extend(space
,
1239 space
->nparam
+ n
, space
->n_in
, space
->n_out
);
1240 if (space
&& space
->nested
[0] &&
1241 !(space
->nested
[0] = isl_space_add_dims(space
->nested
[0],
1244 if (space
&& space
->nested
[1] &&
1245 !(space
->nested
[1] = isl_space_add_dims(space
->nested
[1],
1250 return space_extend(space
,
1251 space
->nparam
, space
->n_in
+ n
, space
->n_out
);
1253 return space_extend(space
,
1254 space
->nparam
, space
->n_in
, space
->n_out
+ n
);
1256 isl_die(space
->ctx
, isl_error_invalid
,
1257 "cannot add dimensions of specified type", goto error
);
1260 isl_space_free(space
);
1264 /* Add a parameter with identifier "id" to "space", provided
1265 * it does not already appear in "space".
1267 __isl_give isl_space
*isl_space_add_param_id(__isl_take isl_space
*space
,
1268 __isl_take isl_id
*id
)
1275 if (isl_space_find_dim_by_id(space
, isl_dim_param
, id
) >= 0) {
1280 pos
= isl_space_dim(space
, isl_dim_param
);
1283 space
= isl_space_add_dims(space
, isl_dim_param
, 1);
1284 space
= isl_space_set_dim_id(space
, isl_dim_param
, pos
, id
);
1288 isl_space_free(space
);
1293 static int valid_dim_type(enum isl_dim_type type
)
1306 #define TYPE isl_space
1307 #include "check_type_range_templ.c"
1309 /* Insert "n" dimensions of type "type" at position "pos".
1310 * If we are inserting parameters, then they are also inserted in
1311 * any nested spaces.
1313 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*space
,
1314 enum isl_dim_type type
, unsigned pos
, unsigned n
)
1317 isl_id
**ids
= NULL
;
1322 return isl_space_reset(space
, type
);
1324 ctx
= isl_space_get_ctx(space
);
1325 if (!valid_dim_type(type
))
1326 isl_die(ctx
, isl_error_invalid
,
1327 "cannot insert dimensions of specified type",
1330 if (isl_space_check_range(space
, type
, pos
, 0) < 0)
1331 return isl_space_free(space
);
1333 space
= isl_space_cow(space
);
1338 enum isl_dim_type t
, o
= isl_dim_param
;
1341 ids
= isl_calloc_array(ctx
, isl_id
*,
1342 space
->nparam
+ space
->n_in
+ space
->n_out
+ n
);
1346 s
[isl_dim_param
- o
] = space
->nparam
;
1347 s
[isl_dim_in
- o
] = space
->n_in
;
1348 s
[isl_dim_out
- o
] = space
->n_out
;
1349 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1351 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1354 get_ids(space
, t
, 0, pos
, ids
+ off
);
1356 get_ids(space
, t
, pos
, s
[t
- o
] - pos
,
1358 off
+= s
[t
- o
] - pos
;
1363 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
+ n
;
1366 case isl_dim_param
: space
->nparam
+= n
; break;
1367 case isl_dim_in
: space
->n_in
+= n
; break;
1368 case isl_dim_out
: space
->n_out
+= n
; break;
1371 space
= isl_space_reset(space
, type
);
1373 if (type
== isl_dim_param
) {
1374 if (space
&& space
->nested
[0] &&
1375 !(space
->nested
[0] = isl_space_insert_dims(space
->nested
[0],
1376 isl_dim_param
, pos
, n
)))
1378 if (space
&& space
->nested
[1] &&
1379 !(space
->nested
[1] = isl_space_insert_dims(space
->nested
[1],
1380 isl_dim_param
, pos
, n
)))
1386 isl_space_free(space
);
1390 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*space
,
1391 enum isl_dim_type dst_type
, unsigned dst_pos
,
1392 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1396 space
= isl_space_reset(space
, src_type
);
1397 space
= isl_space_reset(space
, dst_type
);
1403 if (isl_space_check_range(space
, src_type
, src_pos
, n
) < 0)
1404 return isl_space_free(space
);
1406 if (dst_type
== src_type
&& dst_pos
== src_pos
)
1409 isl_assert(space
->ctx
, dst_type
!= src_type
, goto error
);
1411 space
= isl_space_cow(space
);
1417 enum isl_dim_type t
, o
= isl_dim_param
;
1420 ids
= isl_calloc_array(space
->ctx
, isl_id
*,
1421 space
->nparam
+ space
->n_in
+ space
->n_out
);
1425 s
[isl_dim_param
- o
] = space
->nparam
;
1426 s
[isl_dim_in
- o
] = space
->n_in
;
1427 s
[isl_dim_out
- o
] = space
->n_out
;
1428 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1429 if (t
== dst_type
) {
1430 get_ids(space
, t
, 0, dst_pos
, ids
+ off
);
1432 get_ids(space
, src_type
, src_pos
, n
, ids
+ off
);
1434 get_ids(space
, t
, dst_pos
, s
[t
- o
] - dst_pos
,
1436 off
+= s
[t
- o
] - dst_pos
;
1437 } else if (t
== src_type
) {
1438 get_ids(space
, t
, 0, src_pos
, ids
+ off
);
1440 get_ids(space
, t
, src_pos
+ n
,
1441 s
[t
- o
] - src_pos
- n
, ids
+ off
);
1442 off
+= s
[t
- o
] - src_pos
- n
;
1444 get_ids(space
, t
, 0, s
[t
- o
], ids
+ off
);
1450 space
->n_id
= space
->nparam
+ space
->n_in
+ space
->n_out
;
1454 case isl_dim_param
: space
->nparam
+= n
; break;
1455 case isl_dim_in
: space
->n_in
+= n
; break;
1456 case isl_dim_out
: space
->n_out
+= n
; break;
1461 case isl_dim_param
: space
->nparam
-= n
; break;
1462 case isl_dim_in
: space
->n_in
-= n
; break;
1463 case isl_dim_out
: space
->n_out
-= n
; break;
1467 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
1470 for (i
= 0; i
< 2; ++i
) {
1473 if (!space
->nested
[i
])
1475 nested
= isl_space_take_nested(space
, i
);
1476 nested
= isl_space_replace_params(nested
, space
);
1477 space
= isl_space_restore_nested(space
, i
, nested
);
1484 isl_space_free(space
);
1488 /* Check that "space1" and "space2" have the same parameters,
1489 * reporting an error if they do not.
1491 isl_stat
isl_space_check_equal_params(__isl_keep isl_space
*space1
,
1492 __isl_keep isl_space
*space2
)
1496 equal
= isl_space_has_equal_params(space1
, space2
);
1498 return isl_stat_error
;
1500 isl_die(isl_space_get_ctx(space1
), isl_error_invalid
,
1501 "parameters need to match", return isl_stat_error
);
1505 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
1506 __isl_take isl_space
*right
)
1510 if (isl_space_check_equal_params(left
, right
) < 0)
1513 isl_assert(left
->ctx
,
1514 isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_in
),
1517 space
= isl_space_alloc(left
->ctx
,
1518 left
->nparam
, left
->n_in
, right
->n_out
);
1522 space
= copy_ids(space
, isl_dim_param
, 0, left
, isl_dim_param
);
1523 space
= copy_ids(space
, isl_dim_in
, 0, left
, isl_dim_in
);
1524 space
= copy_ids(space
, isl_dim_out
, 0, right
, isl_dim_out
);
1526 if (space
&& left
->tuple_id
[0] &&
1527 !(space
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
1529 if (space
&& right
->tuple_id
[1] &&
1530 !(space
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
1532 if (space
&& left
->nested
[0] &&
1533 !(space
->nested
[0] = isl_space_copy(left
->nested
[0])))
1535 if (space
&& right
->nested
[1] &&
1536 !(space
->nested
[1] = isl_space_copy(right
->nested
[1])))
1539 isl_space_free(left
);
1540 isl_space_free(right
);
1544 isl_space_free(left
);
1545 isl_space_free(right
);
1549 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1550 * { [A -> B] -> [C -> D] }.
1551 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1553 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
1554 __isl_take isl_space
*right
)
1556 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
1559 if (!left
|| !right
)
1562 is_set
= isl_space_is_set(left
);
1563 if (is_set
!= isl_space_is_set(right
))
1564 isl_die(isl_space_get_ctx(left
), isl_error_invalid
,
1565 "expecting either two set spaces or two map spaces",
1568 return isl_space_range_product(left
, right
);
1570 if (isl_space_check_equal_params(left
, right
) < 0)
1573 dom1
= isl_space_domain(isl_space_copy(left
));
1574 dom2
= isl_space_domain(isl_space_copy(right
));
1575 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1577 dom1
= isl_space_range(left
);
1578 dom2
= isl_space_range(right
);
1579 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1581 return isl_space_join(isl_space_reverse(nest1
), nest2
);
1583 isl_space_free(left
);
1584 isl_space_free(right
);
1588 /* Given two spaces { A -> C } and { B -> C }, construct the space
1591 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
1592 __isl_take isl_space
*right
)
1594 isl_space
*ran
, *dom1
, *dom2
, *nest
;
1596 if (isl_space_check_equal_params(left
, right
) < 0)
1599 if (!isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_out
))
1600 isl_die(left
->ctx
, isl_error_invalid
,
1601 "ranges need to match", goto error
);
1603 ran
= isl_space_range(isl_space_copy(left
));
1605 dom1
= isl_space_domain(left
);
1606 dom2
= isl_space_domain(right
);
1607 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1609 return isl_space_join(isl_space_reverse(nest
), ran
);
1611 isl_space_free(left
);
1612 isl_space_free(right
);
1616 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
1617 __isl_take isl_space
*right
)
1619 isl_space
*dom
, *ran1
, *ran2
, *nest
;
1621 if (isl_space_check_equal_params(left
, right
) < 0)
1624 if (!isl_space_tuple_is_equal(left
, isl_dim_in
, right
, isl_dim_in
))
1625 isl_die(left
->ctx
, isl_error_invalid
,
1626 "domains need to match", goto error
);
1628 dom
= isl_space_domain(isl_space_copy(left
));
1630 ran1
= isl_space_range(left
);
1631 ran2
= isl_space_range(right
);
1632 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
1634 return isl_space_join(isl_space_reverse(dom
), nest
);
1636 isl_space_free(left
);
1637 isl_space_free(right
);
1641 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1643 __isl_give isl_space
*isl_space_domain_factor_domain(
1644 __isl_take isl_space
*space
)
1649 if (isl_space_check_domain_is_wrapping(space
) < 0)
1650 return isl_space_free(space
);
1652 nested
= space
->nested
[0];
1653 domain
= isl_space_copy(space
);
1654 domain
= isl_space_drop_dims(domain
, isl_dim_in
,
1655 nested
->n_in
, nested
->n_out
);
1657 return isl_space_free(space
);
1658 if (nested
->tuple_id
[0]) {
1659 domain
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[0]);
1660 if (!domain
->tuple_id
[0])
1663 if (nested
->nested
[0]) {
1664 domain
->nested
[0] = isl_space_copy(nested
->nested
[0]);
1665 if (!domain
->nested
[0])
1669 isl_space_free(space
);
1672 isl_space_free(space
);
1673 isl_space_free(domain
);
1677 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1679 __isl_give isl_space
*isl_space_domain_factor_range(
1680 __isl_take isl_space
*space
)
1685 if (isl_space_check_domain_is_wrapping(space
) < 0)
1686 return isl_space_free(space
);
1688 nested
= space
->nested
[0];
1689 range
= isl_space_copy(space
);
1690 range
= isl_space_drop_dims(range
, isl_dim_in
, 0, nested
->n_in
);
1692 return isl_space_free(space
);
1693 if (nested
->tuple_id
[1]) {
1694 range
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[1]);
1695 if (!range
->tuple_id
[0])
1698 if (nested
->nested
[1]) {
1699 range
->nested
[0] = isl_space_copy(nested
->nested
[1]);
1700 if (!range
->nested
[0])
1704 isl_space_free(space
);
1707 isl_space_free(space
);
1708 isl_space_free(range
);
1712 /* Internal function that selects the domain of the map that is
1713 * embedded in either a set space or the range of a map space.
1714 * In particular, given a space of the form [A -> B], return the space A.
1715 * Given a space of the form A -> [B -> C], return the space A -> B.
1717 static __isl_give isl_space
*range_factor_domain(__isl_take isl_space
*space
)
1725 nested
= space
->nested
[1];
1726 domain
= isl_space_copy(space
);
1727 domain
= isl_space_drop_dims(domain
, isl_dim_out
,
1728 nested
->n_in
, nested
->n_out
);
1730 return isl_space_free(space
);
1731 if (nested
->tuple_id
[0]) {
1732 domain
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[0]);
1733 if (!domain
->tuple_id
[1])
1736 if (nested
->nested
[0]) {
1737 domain
->nested
[1] = isl_space_copy(nested
->nested
[0]);
1738 if (!domain
->nested
[1])
1742 isl_space_free(space
);
1745 isl_space_free(space
);
1746 isl_space_free(domain
);
1750 /* Given a space of the form A -> [B -> C], return the space A -> B.
1752 __isl_give isl_space
*isl_space_range_factor_domain(
1753 __isl_take isl_space
*space
)
1755 if (isl_space_check_range_is_wrapping(space
) < 0)
1756 return isl_space_free(space
);
1758 return range_factor_domain(space
);
1761 /* Given a space of the form [A -> B], return the space A.
1763 static __isl_give isl_space
*set_factor_domain(__isl_take isl_space
*space
)
1767 if (!isl_space_is_wrapping(space
))
1768 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1769 "not a product", return isl_space_free(space
));
1771 return range_factor_domain(space
);
1774 /* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.
1775 * Given a space of the form [A -> B], return the space A.
1777 __isl_give isl_space
*isl_space_factor_domain(__isl_take isl_space
*space
)
1781 if (isl_space_is_set(space
))
1782 return set_factor_domain(space
);
1783 space
= isl_space_domain_factor_domain(space
);
1784 space
= isl_space_range_factor_domain(space
);
1788 /* Internal function that selects the range of the map that is
1789 * embedded in either a set space or the range of a map space.
1790 * In particular, given a space of the form [A -> B], return the space B.
1791 * Given a space of the form A -> [B -> C], return the space A -> C.
1793 static __isl_give isl_space
*range_factor_range(__isl_take isl_space
*space
)
1801 nested
= space
->nested
[1];
1802 range
= isl_space_copy(space
);
1803 range
= isl_space_drop_dims(range
, isl_dim_out
, 0, nested
->n_in
);
1805 return isl_space_free(space
);
1806 if (nested
->tuple_id
[1]) {
1807 range
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[1]);
1808 if (!range
->tuple_id
[1])
1811 if (nested
->nested
[1]) {
1812 range
->nested
[1] = isl_space_copy(nested
->nested
[1]);
1813 if (!range
->nested
[1])
1817 isl_space_free(space
);
1820 isl_space_free(space
);
1821 isl_space_free(range
);
1825 /* Given a space of the form A -> [B -> C], return the space A -> C.
1827 __isl_give isl_space
*isl_space_range_factor_range(
1828 __isl_take isl_space
*space
)
1830 if (isl_space_check_range_is_wrapping(space
) < 0)
1831 return isl_space_free(space
);
1833 return range_factor_range(space
);
1836 /* Given a space of the form [A -> B], return the space B.
1838 static __isl_give isl_space
*set_factor_range(__isl_take isl_space
*space
)
1842 if (!isl_space_is_wrapping(space
))
1843 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1844 "not a product", return isl_space_free(space
));
1846 return range_factor_range(space
);
1849 /* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.
1850 * Given a space of the form [A -> B], return the space B.
1852 __isl_give isl_space
*isl_space_factor_range(__isl_take isl_space
*space
)
1856 if (isl_space_is_set(space
))
1857 return set_factor_range(space
);
1858 space
= isl_space_domain_factor_range(space
);
1859 space
= isl_space_range_factor_range(space
);
1863 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*space
)
1866 isl_id
**ids
= NULL
;
1871 ctx
= isl_space_get_ctx(space
);
1872 if (!isl_space_is_set(space
))
1873 isl_die(ctx
, isl_error_invalid
, "not a set space", goto error
);
1874 space
= isl_space_cow(space
);
1877 n_id
= space
->nparam
+ space
->n_out
+ space
->n_out
;
1878 if (n_id
> 0 && space
->ids
) {
1879 ids
= isl_calloc_array(space
->ctx
, isl_id
*, n_id
);
1882 get_ids(space
, isl_dim_param
, 0, space
->nparam
, ids
);
1883 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
1884 ids
+ space
->nparam
);
1886 space
->n_in
= space
->n_out
;
1891 space
= copy_ids(space
, isl_dim_out
, 0, space
, isl_dim_in
);
1893 isl_id_free(space
->tuple_id
[0]);
1894 space
->tuple_id
[0] = isl_id_copy(space
->tuple_id
[1]);
1895 isl_space_free(space
->nested
[0]);
1896 space
->nested
[0] = isl_space_copy(space
->nested
[1]);
1899 isl_space_free(space
);
1903 __isl_give isl_space
*isl_space_map_from_domain_and_range(
1904 __isl_take isl_space
*domain
, __isl_take isl_space
*range
)
1906 if (!domain
|| !range
)
1908 if (!isl_space_is_set(domain
))
1909 isl_die(isl_space_get_ctx(domain
), isl_error_invalid
,
1910 "domain is not a set space", goto error
);
1911 if (!isl_space_is_set(range
))
1912 isl_die(isl_space_get_ctx(range
), isl_error_invalid
,
1913 "range is not a set space", goto error
);
1914 return isl_space_join(isl_space_reverse(domain
), range
);
1916 isl_space_free(domain
);
1917 isl_space_free(range
);
1921 static __isl_give isl_space
*set_ids(__isl_take isl_space
*space
,
1922 enum isl_dim_type type
,
1923 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
1927 for (i
= 0; i
< n
; ++i
)
1928 space
= set_id(space
, type
, first
+ i
, ids
[i
]);
1933 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*space
)
1938 isl_id
**ids
= NULL
;
1941 equal
= match(space
, isl_dim_in
, space
, isl_dim_out
);
1943 return isl_space_free(space
);
1947 space
= isl_space_cow(space
);
1951 id
= space
->tuple_id
[0];
1952 space
->tuple_id
[0] = space
->tuple_id
[1];
1953 space
->tuple_id
[1] = id
;
1955 nested
= space
->nested
[0];
1956 space
->nested
[0] = space
->nested
[1];
1957 space
->nested
[1] = nested
;
1960 int n_id
= space
->n_in
+ space
->n_out
;
1961 ids
= isl_alloc_array(space
->ctx
, isl_id
*, n_id
);
1964 get_ids(space
, isl_dim_in
, 0, space
->n_in
, ids
);
1965 get_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
+ space
->n_in
);
1969 space
->n_in
= space
->n_out
;
1973 space
= set_ids(space
, isl_dim_out
, 0, space
->n_out
, ids
);
1974 space
= set_ids(space
, isl_dim_in
, 0, space
->n_in
,
1975 ids
+ space
->n_out
);
1982 isl_space_free(space
);
1986 /* Given a space A -> (B -> C), return the corresponding space
1989 * If the range tuple is named, then the name is only preserved
1990 * if B and C are equal tuples, in which case the output
1991 * of this function is identical to the input.
1993 __isl_give isl_space
*isl_space_range_reverse(__isl_take isl_space
*space
)
1998 if (isl_space_check_range_is_wrapping(space
) < 0)
1999 return isl_space_free(space
);
2001 nested
= isl_space_peek_nested(space
, 1);
2002 equal
= isl_space_tuple_is_equal(nested
, isl_dim_in
,
2003 nested
, isl_dim_out
);
2005 return isl_space_free(space
);
2007 nested
= isl_space_take_nested(space
, 1);
2008 nested
= isl_space_reverse(nested
);
2009 space
= isl_space_restore_nested(space
, 1, nested
);
2011 space
= isl_space_reset_tuple_id(space
, isl_dim_out
);
2016 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*space
,
2017 enum isl_dim_type type
, unsigned first
, unsigned num
)
2025 return isl_space_reset(space
, type
);
2027 if (!valid_dim_type(type
))
2028 isl_die(space
->ctx
, isl_error_invalid
,
2029 "cannot drop dimensions of specified type", goto error
);
2031 if (isl_space_check_range(space
, type
, first
, num
) < 0)
2032 return isl_space_free(space
);
2033 space
= isl_space_cow(space
);
2037 space
= extend_ids(space
);
2040 for (i
= 0; i
< num
; ++i
)
2041 isl_id_free(get_id(space
, type
, first
+ i
));
2042 for (i
= first
+num
; i
< n(space
, type
); ++i
)
2043 set_id(space
, type
, i
- num
, get_id(space
, type
, i
));
2046 get_ids(space
, isl_dim_in
, 0, space
->n_in
,
2047 space
->ids
+ offset(space
, isl_dim_in
) - num
);
2049 get_ids(space
, isl_dim_out
, 0, space
->n_out
,
2050 space
->ids
+ offset(space
, isl_dim_out
) - num
);
2057 case isl_dim_param
: space
->nparam
-= num
; break;
2058 case isl_dim_in
: space
->n_in
-= num
; break;
2059 case isl_dim_out
: space
->n_out
-= num
; break;
2062 space
= isl_space_reset(space
, type
);
2063 if (type
== isl_dim_param
) {
2064 if (space
&& space
->nested
[0] &&
2065 !(space
->nested
[0] = isl_space_drop_dims(space
->nested
[0],
2066 isl_dim_param
, first
, num
)))
2068 if (space
&& space
->nested
[1] &&
2069 !(space
->nested
[1] = isl_space_drop_dims(space
->nested
[1],
2070 isl_dim_param
, first
, num
)))
2075 isl_space_free(space
);
2079 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*space
,
2080 unsigned first
, unsigned n
)
2084 return isl_space_drop_dims(space
, isl_dim_in
, first
, n
);
2087 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*space
,
2088 unsigned first
, unsigned n
)
2092 return isl_space_drop_dims(space
, isl_dim_out
, first
, n
);
2095 /* Remove all parameters from "space".
2097 __isl_give isl_space
*isl_space_drop_all_params(__isl_take isl_space
*space
)
2101 nparam
= isl_space_dim(space
, isl_dim_param
);
2103 return isl_space_free(space
);
2104 return isl_space_drop_dims(space
, isl_dim_param
, 0, nparam
);
2107 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*space
)
2111 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, space
->n_out
);
2112 space
= isl_space_reverse(space
);
2113 space
= mark_as_set(space
);
2117 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*space
)
2121 if (!isl_space_is_set(space
))
2122 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2123 "not a set space", goto error
);
2124 space
= isl_space_reverse(space
);
2125 space
= isl_space_reset(space
, isl_dim_out
);
2128 isl_space_free(space
);
2132 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*space
)
2136 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, space
->n_in
);
2137 space
= mark_as_set(space
);
2141 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*space
)
2145 if (!isl_space_is_set(space
))
2146 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2147 "not a set space", goto error
);
2148 return isl_space_reset(space
, isl_dim_in
);
2150 isl_space_free(space
);
2154 /* Given a map space A -> B, return the map space [A -> B] -> A.
2156 __isl_give isl_space
*isl_space_domain_map(__isl_take isl_space
*space
)
2160 domain
= isl_space_from_range(isl_space_domain(isl_space_copy(space
)));
2161 space
= isl_space_from_domain(isl_space_wrap(space
));
2162 space
= isl_space_join(space
, domain
);
2167 /* Given a map space A -> B, return the map space [A -> B] -> B.
2169 __isl_give isl_space
*isl_space_range_map(__isl_take isl_space
*space
)
2173 range
= isl_space_from_range(isl_space_range(isl_space_copy(space
)));
2174 space
= isl_space_from_domain(isl_space_wrap(space
));
2175 space
= isl_space_join(space
, range
);
2180 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
2182 isl_size n_in
, n_out
;
2184 if (isl_space_is_params(space
))
2186 n_in
= isl_space_dim(space
, isl_dim_in
);
2187 n_out
= isl_space_dim(space
, isl_dim_out
);
2188 if (n_in
< 0 || n_out
< 0)
2189 return isl_space_free(space
);
2190 space
= isl_space_drop_dims(space
, isl_dim_in
, 0, n_in
);
2191 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, n_out
);
2192 space
= mark_as_params(space
);
2196 __isl_give isl_space
*isl_space_set_from_params(__isl_take isl_space
*space
)
2200 if (!isl_space_is_params(space
))
2201 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2202 "not a parameter space", goto error
);
2203 return isl_space_reset(space
, isl_dim_set
);
2205 isl_space_free(space
);
2209 /* Add an unnamed tuple of dimension "dim" to "space".
2210 * This requires "space" to be a parameter or set space.
2212 * In particular, if "space" is a parameter space, then return
2213 * a set space with the given dimension.
2214 * If "space" is a set space, then return a map space
2215 * with "space" as domain and a range of the given dimension.
2217 __isl_give isl_space
*isl_space_add_unnamed_tuple_ui(
2218 __isl_take isl_space
*space
, unsigned dim
)
2220 isl_bool is_params
, is_set
;
2222 is_params
= isl_space_is_params(space
);
2223 is_set
= isl_space_is_set(space
);
2224 if (is_params
< 0 || is_set
< 0)
2225 return isl_space_free(space
);
2226 if (!is_params
&& !is_set
)
2227 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2228 "cannot add tuple to map space",
2229 return isl_space_free(space
));
2231 space
= isl_space_set_from_params(space
);
2233 space
= isl_space_from_domain(space
);
2234 space
= isl_space_add_dims(space
, isl_dim_out
, dim
);
2238 /* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"
2240 * This requires "space" to be a parameter or set space.
2242 __isl_give isl_space
*isl_space_add_named_tuple_id_ui(
2243 __isl_take isl_space
*space
, __isl_take isl_id
*tuple_id
, unsigned dim
)
2245 space
= isl_space_add_unnamed_tuple_ui(space
, dim
);
2246 space
= isl_space_set_tuple_id(space
, isl_dim_out
, tuple_id
);
2250 /* Check that the identifiers in "tuple" do not appear as parameters
2253 static isl_stat
check_fresh_params(__isl_keep isl_space
*space
,
2254 __isl_keep isl_multi_id
*tuple
)
2259 n
= isl_multi_id_size(tuple
);
2261 return isl_stat_error
;
2262 for (i
= 0; i
< n
; ++i
) {
2266 id
= isl_multi_id_get_at(tuple
, i
);
2268 return isl_stat_error
;
2269 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2272 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
2273 "parameters not unique", return isl_stat_error
);
2279 /* Add the identifiers in "tuple" as parameters of "space"
2280 * that are known to be fresh.
2282 static __isl_give isl_space
*add_bind_params(__isl_take isl_space
*space
,
2283 __isl_keep isl_multi_id
*tuple
)
2288 first
= isl_space_dim(space
, isl_dim_param
);
2289 n
= isl_multi_id_size(tuple
);
2290 if (first
< 0 || n
< 0)
2291 return isl_space_free(space
);
2292 space
= isl_space_add_dims(space
, isl_dim_param
, n
);
2293 for (i
= 0; i
< n
; ++i
) {
2296 id
= isl_multi_id_get_at(tuple
, i
);
2297 space
= isl_space_set_dim_id(space
,
2298 isl_dim_param
, first
+ i
, id
);
2304 /* Internal function that removes the set tuple of "space",
2305 * which is assumed to correspond to the range space of "tuple", and
2306 * adds the identifiers in "tuple" as fresh parameters.
2307 * In other words, the set dimensions of "space" are reinterpreted
2308 * as parameters, but stay in the same global positions.
2310 __isl_give isl_space
*isl_space_bind_set(__isl_take isl_space
*space
,
2311 __isl_keep isl_multi_id
*tuple
)
2313 isl_space
*tuple_space
;
2315 if (isl_space_check_is_set(space
) < 0)
2316 return isl_space_free(space
);
2317 tuple_space
= isl_multi_id_peek_space(tuple
);
2318 if (isl_space_check_equal_tuples(tuple_space
, space
) < 0)
2319 return isl_space_free(space
);
2320 if (check_fresh_params(space
, tuple
) < 0)
2321 return isl_space_free(space
);
2322 space
= isl_space_params(space
);
2323 space
= add_bind_params(space
, tuple
);
2327 /* Internal function that removes the domain tuple of the map space "space",
2328 * which is assumed to correspond to the range space of "tuple", and
2329 * adds the identifiers in "tuple" as fresh parameters.
2330 * In other words, the domain dimensions of "space" are reinterpreted
2331 * as parameters, but stay in the same global positions.
2333 __isl_give isl_space
*isl_space_bind_map_domain(__isl_take isl_space
*space
,
2334 __isl_keep isl_multi_id
*tuple
)
2336 isl_space
*tuple_space
;
2338 if (isl_space_check_is_map(space
) < 0)
2339 return isl_space_free(space
);
2340 tuple_space
= isl_multi_id_peek_space(tuple
);
2341 if (isl_space_check_domain_tuples(tuple_space
, space
) < 0)
2342 return isl_space_free(space
);
2343 if (check_fresh_params(space
, tuple
) < 0)
2344 return isl_space_free(space
);
2345 space
= isl_space_range(space
);
2346 space
= add_bind_params(space
, tuple
);
2350 /* Internal function that, given a space of the form [A -> B] -> C and
2351 * a tuple of identifiers in A, returns a space B -> C with
2352 * the identifiers in "tuple" added as fresh parameters.
2353 * In other words, the domain dimensions of the wrapped relation
2354 * in the domain of "space" are reinterpreted
2355 * as parameters, but stay in the same global positions.
2357 __isl_give isl_space
*isl_space_bind_domain_wrapped_domain(
2358 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2360 isl_space
*tuple_space
;
2362 if (isl_space_check_is_map(space
) < 0)
2363 return isl_space_free(space
);
2364 tuple_space
= isl_multi_id_peek_space(tuple
);
2365 if (isl_space_check_domain_wrapped_domain_tuples(tuple_space
,
2367 return isl_space_free(space
);
2368 if (check_fresh_params(space
, tuple
) < 0)
2369 return isl_space_free(space
);
2370 space
= isl_space_domain_factor_range(space
);
2371 space
= add_bind_params(space
, tuple
);
2375 /* Insert a domain tuple in "space" corresponding to the set space "domain".
2376 * In particular, if "space" is a parameter space, then the result
2377 * is the set space "domain" combined with the parameters of "space".
2378 * If "space" is a set space, then the result
2379 * is a map space with "domain" as domain and the original space as range.
2381 static __isl_give isl_space
*isl_space_insert_domain(
2382 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
2386 domain
= isl_space_replace_params(domain
, space
);
2388 is_params
= isl_space_is_params(space
);
2389 if (is_params
< 0) {
2390 isl_space_free(domain
);
2391 space
= isl_space_free(space
);
2392 } else if (is_params
) {
2393 isl_space_free(space
);
2396 space
= isl_space_map_from_domain_and_range(domain
, space
);
2401 /* Internal function that introduces a domain in "space"
2402 * corresponding to the range space of "tuple".
2403 * In particular, if "space" is a parameter space, then the result
2404 * is a set space. If "space" is a set space, then the result
2405 * is a map space with the original space as range.
2406 * Parameters that correspond to the identifiers in "tuple" are removed.
2408 * The parameters are removed in reverse order (under the assumption
2409 * that they appear in the same order in "multi") because
2410 * it is slightly more efficient to remove parameters at the end.
2412 * For pretty-printing purposes, the identifiers of the set dimensions
2413 * of the introduced domain are set to the identifiers in "tuple".
2415 __isl_give isl_space
*isl_space_unbind_params_insert_domain(
2416 __isl_take isl_space
*space
, __isl_keep isl_multi_id
*tuple
)
2420 isl_space
*tuple_space
;
2422 n
= isl_multi_id_size(tuple
);
2423 if (!space
|| n
< 0)
2424 return isl_space_free(space
);
2425 for (i
= n
- 1; i
>= 0; --i
) {
2429 id
= isl_multi_id_get_id(tuple
, i
);
2431 return isl_space_free(space
);
2432 pos
= isl_space_find_dim_by_id(space
, isl_dim_param
, id
);
2436 space
= isl_space_drop_dims(space
, isl_dim_param
, pos
, 1);
2438 tuple_space
= isl_multi_id_get_space(tuple
);
2439 for (i
= 0; i
< n
; ++i
) {
2442 id
= isl_multi_id_get_id(tuple
, i
);
2443 tuple_space
= isl_space_set_dim_id(tuple_space
,
2444 isl_dim_set
, i
, id
);
2446 return isl_space_insert_domain(space
, tuple_space
);
2449 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*space
,
2455 is_set
= isl_space_is_set(space
);
2457 return isl_space_free(space
);
2458 if (n_div
== 0 && is_set
&&
2459 space
->nparam
== 0 && space
->n_in
== 0 && space
->n_id
== 0)
2460 return isl_space_reset(space
, isl_dim_out
);
2461 space
= isl_space_cow(space
);
2464 space
->n_out
+= space
->nparam
+ space
->n_in
+ n_div
;
2468 for (i
= 0; i
< space
->n_id
; ++i
)
2469 isl_id_free(get_id(space
, isl_dim_out
, i
));
2471 space
= isl_space_reset(space
, isl_dim_in
);
2472 space
= isl_space_reset(space
, isl_dim_out
);
2473 space
= mark_as_set(space
);
2478 /* Are the two spaces the same, including positions and names of parameters?
2480 isl_bool
isl_space_is_equal(__isl_keep isl_space
*space1
,
2481 __isl_keep isl_space
*space2
)
2485 if (!space1
|| !space2
)
2486 return isl_bool_error
;
2487 if (space1
== space2
)
2488 return isl_bool_true
;
2489 equal
= isl_space_has_equal_params(space1
, space2
);
2490 if (equal
< 0 || !equal
)
2492 return isl_space_has_equal_tuples(space1
, space2
);
2495 /* Do the tuples of "space1" correspond to those of the domain of "space2"?
2496 * That is, is "space1" equal to the domain of "space2", ignoring parameters.
2498 * "space2" is allowed to be a set space, in which case "space1"
2499 * should be a parameter space.
2501 isl_bool
isl_space_has_domain_tuples(__isl_keep isl_space
*space1
,
2502 __isl_keep isl_space
*space2
)
2506 is_set
= isl_space_is_set(space1
);
2507 if (is_set
< 0 || !is_set
)
2509 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2510 space2
, isl_dim_in
);
2513 /* Do the tuples of "space1" correspond to those of the range of "space2"?
2514 * That is, is "space1" equal to the range of "space2", ignoring parameters.
2516 * "space2" is allowed to be the space of a set,
2517 * in which case it should be equal to "space1", ignoring parameters.
2519 isl_bool
isl_space_has_range_tuples(__isl_keep isl_space
*space1
,
2520 __isl_keep isl_space
*space2
)
2524 is_set
= isl_space_is_set(space1
);
2525 if (is_set
< 0 || !is_set
)
2527 return isl_space_tuple_is_equal(space1
, isl_dim_set
,
2528 space2
, isl_dim_out
);
2531 /* Check that the tuples of "space1" correspond to those
2532 * of the domain of "space2".
2533 * That is, check that "space1" is equal to the domain of "space2",
2534 * ignoring parameters.
2536 isl_stat
isl_space_check_domain_tuples(__isl_keep isl_space
*space1
,
2537 __isl_keep isl_space
*space2
)
2541 is_equal
= isl_space_has_domain_tuples(space1
, space2
);
2542 return check_match(space1
, is_equal
);
2545 /* Check that the tuples of "space1" correspond to those
2546 * of the domain of the wrapped relation in the domain of "space2".
2547 * That is, check that "space1" is equal to this domain,
2548 * ignoring parameters.
2550 isl_stat
isl_space_check_domain_wrapped_domain_tuples(
2551 __isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
2556 domain
= isl_space_unwrap(isl_space_domain(isl_space_copy(space2
)));
2557 r
= isl_space_check_domain_tuples(space1
, domain
);
2558 isl_space_free(domain
);
2563 /* Is space1 equal to the domain of space2?
2565 * In the internal version we also allow space2 to be the space of a set,
2566 * provided space1 is a parameter space.
2568 isl_bool
isl_space_is_domain_internal(__isl_keep isl_space
*space1
,
2569 __isl_keep isl_space
*space2
)
2571 isl_bool equal_params
;
2573 if (!space1
|| !space2
)
2574 return isl_bool_error
;
2575 equal_params
= isl_space_has_equal_params(space1
, space2
);
2576 if (equal_params
< 0 || !equal_params
)
2577 return equal_params
;
2578 return isl_space_has_domain_tuples(space1
, space2
);
2581 /* Is space1 equal to the domain of space2?
2583 isl_bool
isl_space_is_domain(__isl_keep isl_space
*space1
,
2584 __isl_keep isl_space
*space2
)
2587 return isl_bool_error
;
2588 if (!isl_space_is_map(space2
))
2589 return isl_bool_false
;
2590 return isl_space_is_domain_internal(space1
, space2
);
2593 /* Is space1 equal to the range of space2?
2595 * In the internal version, space2 is allowed to be the space of a set,
2596 * in which case it should be equal to space1.
2598 isl_bool
isl_space_is_range_internal(__isl_keep isl_space
*space1
,
2599 __isl_keep isl_space
*space2
)
2601 isl_bool equal_params
;
2603 if (!space1
|| !space2
)
2604 return isl_bool_error
;
2605 equal_params
= isl_space_has_equal_params(space1
, space2
);
2606 if (equal_params
< 0 || !equal_params
)
2607 return equal_params
;
2608 return isl_space_has_range_tuples(space1
, space2
);
2611 /* Is space1 equal to the range of space2?
2613 isl_bool
isl_space_is_range(__isl_keep isl_space
*space1
,
2614 __isl_keep isl_space
*space2
)
2617 return isl_bool_error
;
2618 if (!isl_space_is_map(space2
))
2619 return isl_bool_false
;
2620 return isl_space_is_range_internal(space1
, space2
);
2623 /* Update "hash" by hashing in the parameters of "space".
2625 static uint32_t isl_hash_params(uint32_t hash
, __isl_keep isl_space
*space
)
2633 isl_hash_byte(hash
, space
->nparam
% 256);
2635 for (i
= 0; i
< space
->nparam
; ++i
) {
2636 id
= get_id(space
, isl_dim_param
, i
);
2637 hash
= isl_hash_id(hash
, id
);
2643 /* Update "hash" by hashing in the tuples of "space".
2644 * Changes in this function should be reflected in isl_hash_tuples_domain.
2646 static uint32_t isl_hash_tuples(uint32_t hash
, __isl_keep isl_space
*space
)
2653 isl_hash_byte(hash
, space
->n_in
% 256);
2654 isl_hash_byte(hash
, space
->n_out
% 256);
2656 id
= tuple_id(space
, isl_dim_in
);
2657 hash
= isl_hash_id(hash
, id
);
2658 id
= tuple_id(space
, isl_dim_out
);
2659 hash
= isl_hash_id(hash
, id
);
2661 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2662 hash
= isl_hash_tuples(hash
, space
->nested
[1]);
2667 /* Update "hash" by hashing in the domain tuple of "space".
2668 * The result of this function is equal to the result of applying
2669 * isl_hash_tuples to the domain of "space".
2671 static uint32_t isl_hash_tuples_domain(uint32_t hash
,
2672 __isl_keep isl_space
*space
)
2679 isl_hash_byte(hash
, 0);
2680 isl_hash_byte(hash
, space
->n_in
% 256);
2682 hash
= isl_hash_id(hash
, &isl_id_none
);
2683 id
= tuple_id(space
, isl_dim_in
);
2684 hash
= isl_hash_id(hash
, id
);
2686 hash
= isl_hash_tuples(hash
, space
->nested
[0]);
2691 /* Return a hash value that digests the tuples of "space",
2692 * i.e., that ignores the parameters.
2693 * Changes in this function should be reflected
2694 * in isl_space_get_tuple_domain_hash.
2696 uint32_t isl_space_get_tuple_hash(__isl_keep isl_space
*space
)
2703 hash
= isl_hash_init();
2704 hash
= isl_hash_tuples(hash
, space
);
2709 /* Return the hash value of "space".
2711 uint32_t isl_space_get_full_hash(__isl_keep isl_space
*space
)
2718 hash
= isl_hash_init();
2719 hash
= isl_hash_params(hash
, space
);
2720 hash
= isl_hash_tuples(hash
, space
);
2725 /* Return the hash value of the domain tuple of "space".
2726 * That is, isl_space_get_tuple_domain_hash(space) is equal to
2727 * isl_space_get_tuple_hash(isl_space_domain(space)).
2729 uint32_t isl_space_get_tuple_domain_hash(__isl_keep isl_space
*space
)
2736 hash
= isl_hash_init();
2737 hash
= isl_hash_tuples_domain(hash
, space
);
2742 /* Is "space" the space of a set wrapping a map space?
2744 isl_bool
isl_space_is_wrapping(__isl_keep isl_space
*space
)
2747 return isl_bool_error
;
2749 if (!isl_space_is_set(space
))
2750 return isl_bool_false
;
2752 return isl_bool_ok(space
->nested
[1] != NULL
);
2755 /* Is "space" the space of a map where the domain is a wrapped map space?
2757 isl_bool
isl_space_domain_is_wrapping(__isl_keep isl_space
*space
)
2760 return isl_bool_error
;
2762 if (isl_space_is_set(space
))
2763 return isl_bool_false
;
2765 return isl_bool_ok(space
->nested
[0] != NULL
);
2768 /* Is "space" the space of a map where the range is a wrapped map space?
2770 isl_bool
isl_space_range_is_wrapping(__isl_keep isl_space
*space
)
2773 return isl_bool_error
;
2775 if (isl_space_is_set(space
))
2776 return isl_bool_false
;
2778 return isl_bool_ok(space
->nested
[1] != NULL
);
2781 /* Is "space" a product of two spaces?
2782 * That is, is it a wrapping set space or a map space
2783 * with wrapping domain and range?
2785 isl_bool
isl_space_is_product(__isl_keep isl_space
*space
)
2788 isl_bool is_product
;
2790 is_set
= isl_space_is_set(space
);
2792 return isl_bool_error
;
2794 return isl_space_is_wrapping(space
);
2795 is_product
= isl_space_domain_is_wrapping(space
);
2796 if (is_product
< 0 || !is_product
)
2798 return isl_space_range_is_wrapping(space
);
2801 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*space
)
2808 wrap
= isl_space_set_alloc(space
->ctx
,
2809 space
->nparam
, space
->n_in
+ space
->n_out
);
2811 wrap
= copy_ids(wrap
, isl_dim_param
, 0, space
, isl_dim_param
);
2812 wrap
= copy_ids(wrap
, isl_dim_set
, 0, space
, isl_dim_in
);
2813 wrap
= copy_ids(wrap
, isl_dim_set
, space
->n_in
, space
, isl_dim_out
);
2818 wrap
->nested
[1] = space
;
2822 isl_space_free(space
);
2826 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*space
)
2833 if (!isl_space_is_wrapping(space
))
2834 isl_die(space
->ctx
, isl_error_invalid
, "not a wrapping space",
2837 unwrap
= isl_space_copy(space
->nested
[1]);
2838 isl_space_free(space
);
2842 isl_space_free(space
);
2846 isl_bool
isl_space_is_named_or_nested(__isl_keep isl_space
*space
,
2847 enum isl_dim_type type
)
2849 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
2850 return isl_bool_false
;
2852 return isl_bool_error
;
2853 if (space
->tuple_id
[type
- isl_dim_in
])
2854 return isl_bool_true
;
2855 if (space
->nested
[type
- isl_dim_in
])
2856 return isl_bool_true
;
2857 return isl_bool_false
;
2860 isl_bool
isl_space_may_be_set(__isl_keep isl_space
*space
)
2866 return isl_bool_error
;
2867 if (isl_space_is_set(space
))
2868 return isl_bool_true
;
2869 n_in
= isl_space_dim(space
, isl_dim_in
);
2871 return isl_bool_error
;
2873 return isl_bool_false
;
2874 nested
= isl_space_is_named_or_nested(space
, isl_dim_in
);
2875 if (nested
< 0 || nested
)
2876 return isl_bool_not(nested
);
2877 return isl_bool_true
;
2880 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*space
,
2881 enum isl_dim_type type
)
2883 if (!isl_space_is_named_or_nested(space
, type
))
2886 space
= isl_space_cow(space
);
2890 isl_id_free(space
->tuple_id
[type
- isl_dim_in
]);
2891 space
->tuple_id
[type
- isl_dim_in
] = NULL
;
2892 isl_space_free(space
->nested
[type
- isl_dim_in
]);
2893 space
->nested
[type
- isl_dim_in
] = NULL
;
2898 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*space
)
2902 if (!space
->nested
[0] && !space
->nested
[1])
2905 if (space
->nested
[0])
2906 space
= isl_space_reset(space
, isl_dim_in
);
2907 if (space
&& space
->nested
[1])
2908 space
= isl_space_reset(space
, isl_dim_out
);
2913 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*space
)
2917 if (!space
->nested
[0])
2920 return isl_space_reset(space
, isl_dim_in
);
2923 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*space
)
2927 if (!space
->nested
[1])
2930 return isl_space_reset(space
, isl_dim_out
);
2933 /* Replace the parameters of dst by those of src.
2935 __isl_give isl_space
*isl_space_replace_params(__isl_take isl_space
*dst
,
2936 __isl_keep isl_space
*src
)
2938 isl_size dst_dim
, src_dim
;
2939 isl_bool equal_params
;
2940 enum isl_dim_type type
= isl_dim_param
;
2942 equal_params
= isl_space_has_equal_params(dst
, src
);
2943 if (equal_params
< 0)
2944 return isl_space_free(dst
);
2948 dst
= isl_space_cow(dst
);
2950 dst_dim
= isl_space_dim(dst
, type
);
2951 src_dim
= isl_space_dim(src
, type
);
2952 if (dst_dim
< 0 || src_dim
< 0)
2955 dst
= isl_space_drop_dims(dst
, type
, 0, dst_dim
);
2956 dst
= isl_space_add_dims(dst
, type
, src_dim
);
2957 dst
= copy_ids(dst
, type
, 0, src
, type
);
2961 for (i
= 0; i
<= 1; ++i
) {
2964 if (!dst
->nested
[i
])
2966 nested
= isl_space_take_nested(dst
, i
);
2967 nested
= isl_space_replace_params(nested
, src
);
2968 dst
= isl_space_restore_nested(dst
, i
, nested
);
2976 isl_space_free(dst
);
2980 /* Given two tuples ("dst_type" in "dst" and "src_type" in "src")
2981 * of the same size, check if any of the dimensions in the "dst" tuple
2982 * have no identifier, while the corresponding dimensions in "src"
2983 * does have an identifier,
2984 * If so, copy the identifier over to "dst".
2986 __isl_give isl_space
*isl_space_copy_ids_if_unset(__isl_take isl_space
*dst
,
2987 enum isl_dim_type dst_type
, __isl_keep isl_space
*src
,
2988 enum isl_dim_type src_type
)
2993 n
= isl_space_dim(dst
, dst_type
);
2995 return isl_space_free(dst
);
2996 for (i
= 0; i
< n
; ++i
) {
3000 set
= isl_space_has_dim_id(dst
, dst_type
, i
);
3002 return isl_space_free(dst
);
3006 set
= isl_space_has_dim_id(src
, src_type
, i
);
3008 return isl_space_free(dst
);
3012 id
= isl_space_get_dim_id(src
, src_type
, i
);
3013 dst
= isl_space_set_dim_id(dst
, dst_type
, i
, id
);
3019 /* Given a space "space" of a set, create a space
3020 * for the lift of the set. In particular, the result
3021 * is of the form lifted[space -> local[..]], with n_local variables in the
3022 * range of the wrapped map.
3024 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*space
,
3027 isl_space
*local_space
;
3032 local_space
= isl_space_dup(space
);
3033 local_space
= isl_space_drop_dims(local_space
, isl_dim_set
, 0,
3035 local_space
= isl_space_add_dims(local_space
, isl_dim_set
, n_local
);
3036 local_space
= isl_space_set_tuple_name(local_space
,
3037 isl_dim_set
, "local");
3038 space
= isl_space_join(isl_space_from_domain(space
),
3039 isl_space_from_range(local_space
));
3040 space
= isl_space_wrap(space
);
3041 space
= isl_space_set_tuple_name(space
, isl_dim_set
, "lifted");
3046 isl_bool
isl_space_can_zip(__isl_keep isl_space
*space
)
3050 is_set
= isl_space_is_set(space
);
3052 return isl_bool_error
;
3054 return isl_bool_false
;
3055 return isl_space_is_product(space
);
3058 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*space
)
3060 isl_space
*dom
, *ran
;
3061 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
3063 if (!isl_space_can_zip(space
))
3064 isl_die(space
->ctx
, isl_error_invalid
, "space cannot be zipped",
3069 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
3070 ran
= isl_space_unwrap(isl_space_range(space
));
3071 dom_dom
= isl_space_domain(isl_space_copy(dom
));
3072 dom_ran
= isl_space_range(dom
);
3073 ran_dom
= isl_space_domain(isl_space_copy(ran
));
3074 ran_ran
= isl_space_range(ran
);
3075 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
3076 isl_space_from_range(ran_dom
));
3077 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
3078 isl_space_from_range(ran_ran
));
3079 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
3080 isl_space_from_range(isl_space_wrap(ran
)));
3082 isl_space_free(space
);
3086 /* Can we apply isl_space_curry to "space"?
3087 * That is, does is it have a map space with a nested relation in its domain?
3089 isl_bool
isl_space_can_curry(__isl_keep isl_space
*space
)
3091 return isl_space_domain_is_wrapping(space
);
3094 /* Given a space (A -> B) -> C, return the corresponding space
3097 __isl_give isl_space
*isl_space_curry(__isl_take isl_space
*space
)
3099 isl_space
*dom
, *ran
;
3100 isl_space
*dom_dom
, *dom_ran
;
3105 if (!isl_space_can_curry(space
))
3106 isl_die(space
->ctx
, isl_error_invalid
,
3107 "space cannot be curried", goto error
);
3109 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
3110 ran
= isl_space_range(space
);
3111 dom_dom
= isl_space_domain(isl_space_copy(dom
));
3112 dom_ran
= isl_space_range(dom
);
3113 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
3114 isl_space_from_range(ran
));
3115 return isl_space_join(isl_space_from_domain(dom_dom
),
3116 isl_space_from_range(isl_space_wrap(ran
)));
3118 isl_space_free(space
);
3122 /* Can isl_space_range_curry be applied to "space"?
3123 * That is, does it have a nested relation in its range,
3124 * the domain of which is itself a nested relation?
3126 isl_bool
isl_space_can_range_curry(__isl_keep isl_space
*space
)
3131 return isl_bool_error
;
3132 can
= isl_space_range_is_wrapping(space
);
3133 if (can
< 0 || !can
)
3135 return isl_space_can_curry(space
->nested
[1]);
3138 /* Given a space A -> ((B -> C) -> D), return the corresponding space
3139 * A -> (B -> (C -> D)).
3141 __isl_give isl_space
*isl_space_range_curry(__isl_take isl_space
*space
)
3148 if (!isl_space_can_range_curry(space
))
3149 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3150 "space range cannot be curried",
3151 return isl_space_free(space
));
3153 nested
= isl_space_take_nested(space
, 1);
3154 nested
= isl_space_curry(nested
);
3155 space
= isl_space_restore_nested(space
, 1, nested
);
3160 /* Can we apply isl_space_uncurry to "space"?
3161 * That is, does it have a map space with a nested relation in its range?
3163 isl_bool
isl_space_can_uncurry(__isl_keep isl_space
*space
)
3165 return isl_space_range_is_wrapping(space
);
3168 /* Given a space A -> (B -> C), return the corresponding space
3171 __isl_give isl_space
*isl_space_uncurry(__isl_take isl_space
*space
)
3173 isl_space
*dom
, *ran
;
3174 isl_space
*ran_dom
, *ran_ran
;
3179 if (!isl_space_can_uncurry(space
))
3180 isl_die(space
->ctx
, isl_error_invalid
,
3181 "space cannot be uncurried",
3182 return isl_space_free(space
));
3184 dom
= isl_space_domain(isl_space_copy(space
));
3185 ran
= isl_space_unwrap(isl_space_range(space
));
3186 ran_dom
= isl_space_domain(isl_space_copy(ran
));
3187 ran_ran
= isl_space_range(ran
);
3188 dom
= isl_space_join(isl_space_from_domain(dom
),
3189 isl_space_from_range(ran_dom
));
3190 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
3191 isl_space_from_range(ran_ran
));
3194 isl_bool
isl_space_has_named_params(__isl_keep isl_space
*space
)
3200 return isl_bool_error
;
3201 if (space
->nparam
== 0)
3202 return isl_bool_true
;
3203 off
= isl_space_offset(space
, isl_dim_param
);
3204 if (off
+ space
->nparam
> space
->n_id
)
3205 return isl_bool_false
;
3206 for (i
= 0; i
< space
->nparam
; ++i
)
3207 if (!space
->ids
[off
+ i
])
3208 return isl_bool_false
;
3209 return isl_bool_true
;
3212 /* Check that "space" has only named parameters, reporting an error
3215 isl_stat
isl_space_check_named_params(__isl_keep isl_space
*space
)
3219 named
= isl_space_has_named_params(space
);
3221 return isl_stat_error
;
3223 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3224 "unexpected unnamed parameters", return isl_stat_error
);
3229 /* Align the initial parameters of space1 to match the order in space2.
3231 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*space1
,
3232 __isl_take isl_space
*space2
)
3234 isl_reordering
*exp
;
3236 if (isl_space_check_named_params(space1
) < 0 ||
3237 isl_space_check_named_params(space2
) < 0)
3240 exp
= isl_parameter_alignment_reordering(space1
, space2
);
3241 exp
= isl_reordering_extend_space(exp
, space1
);
3242 isl_space_free(space2
);
3243 space1
= isl_reordering_get_space(exp
);
3244 isl_reordering_free(exp
);
3247 isl_space_free(space1
);
3248 isl_space_free(space2
);
3252 /* Given the space of set (domain), construct a space for a map
3253 * with as domain the given space and as range the range of "model".
3255 __isl_give isl_space
*isl_space_extend_domain_with_range(
3256 __isl_take isl_space
*space
, __isl_take isl_space
*model
)
3263 space
= isl_space_from_domain(space
);
3264 n_out
= isl_space_dim(model
, isl_dim_out
);
3267 space
= isl_space_add_dims(space
, isl_dim_out
, n_out
);
3268 if (isl_space_has_tuple_id(model
, isl_dim_out
))
3269 space
= isl_space_set_tuple_id(space
, isl_dim_out
,
3270 isl_space_get_tuple_id(model
, isl_dim_out
));
3273 if (model
->nested
[1]) {
3274 isl_space
*nested
= isl_space_copy(model
->nested
[1]);
3275 isl_size n_nested
, n_space
;
3276 nested
= isl_space_align_params(nested
, isl_space_copy(space
));
3277 n_nested
= isl_space_dim(nested
, isl_dim_param
);
3278 n_space
= isl_space_dim(space
, isl_dim_param
);
3279 if (n_nested
< 0 || n_space
< 0)
3281 if (n_nested
> n_space
)
3282 nested
= isl_space_drop_dims(nested
, isl_dim_param
,
3283 n_space
, n_nested
- n_space
);
3286 space
->nested
[1] = nested
;
3288 isl_space_free(model
);
3291 isl_space_free(model
);
3292 isl_space_free(space
);
3296 /* Compare the "type" dimensions of two isl_spaces.
3298 * The order is fairly arbitrary.
3300 static int isl_space_cmp_type(__isl_keep isl_space
*space1
,
3301 __isl_keep isl_space
*space2
, enum isl_dim_type type
)
3304 isl_size dim1
, dim2
;
3305 isl_space
*nested1
, *nested2
;
3307 dim1
= isl_space_dim(space1
, type
);
3308 dim2
= isl_space_dim(space2
, type
);
3309 if (dim1
< 0 || dim2
< 0)
3314 cmp
= isl_id_cmp(tuple_id(space1
, type
), tuple_id(space2
, type
));
3318 nested1
= nested(space1
, type
);
3319 nested2
= nested(space2
, type
);
3320 if (!nested1
!= !nested2
)
3321 return !nested1
- !nested2
;
3324 return isl_space_cmp(nested1
, nested2
);
3329 /* Compare two isl_spaces.
3331 * The order is fairly arbitrary.
3333 int isl_space_cmp(__isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
3338 if (space1
== space2
)
3345 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_param
);
3348 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_in
);
3351 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_out
);
3355 if (!space1
->ids
&& !space2
->ids
)
3358 for (i
= 0; i
< n(space1
, isl_dim_param
); ++i
) {
3359 cmp
= isl_id_cmp(get_id(space1
, isl_dim_param
, i
),
3360 get_id(space2
, isl_dim_param
, i
));