2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2013-2014 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
17 #include <isl_space_private.h>
18 #include <isl_id_private.h>
19 #include <isl_reordering.h>
21 isl_ctx
*isl_space_get_ctx(__isl_keep isl_space
*dim
)
23 return dim
? dim
->ctx
: NULL
;
26 __isl_give isl_space
*isl_space_alloc(isl_ctx
*ctx
,
27 unsigned nparam
, unsigned n_in
, unsigned n_out
)
31 dim
= isl_alloc_type(ctx
, struct isl_space
);
42 dim
->tuple_id
[0] = NULL
;
43 dim
->tuple_id
[1] = NULL
;
45 dim
->nested
[0] = NULL
;
46 dim
->nested
[1] = NULL
;
54 /* Mark the space as being that of a set, by setting the domain tuple
57 static __isl_give isl_space
*mark_as_set(__isl_take isl_space
*space
)
59 space
= isl_space_cow(space
);
62 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
66 /* Is the space that of a set?
68 int isl_space_is_set(__isl_keep isl_space
*space
)
72 if (space
->n_in
!= 0 || space
->nested
[0])
74 if (space
->tuple_id
[0] != &isl_id_none
)
79 /* Is the given space that of a map?
81 int isl_space_is_map(__isl_keep isl_space
*space
)
85 return space
->tuple_id
[0] != &isl_id_none
&&
86 space
->tuple_id
[1] != &isl_id_none
;
89 __isl_give isl_space
*isl_space_set_alloc(isl_ctx
*ctx
,
90 unsigned nparam
, unsigned dim
)
93 space
= isl_space_alloc(ctx
, nparam
, 0, dim
);
94 space
= mark_as_set(space
);
98 /* Mark the space as being that of a parameter domain, by setting
99 * both tuples to isl_id_none.
101 static __isl_give isl_space
*mark_as_params(isl_space
*space
)
105 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
106 space
= isl_space_set_tuple_id(space
, isl_dim_out
, &isl_id_none
);
110 /* Is the space that of a parameter domain?
112 int isl_space_is_params(__isl_keep isl_space
*space
)
116 if (space
->n_in
!= 0 || space
->nested
[0] ||
117 space
->n_out
!= 0 || space
->nested
[1])
119 if (space
->tuple_id
[0] != &isl_id_none
)
121 if (space
->tuple_id
[1] != &isl_id_none
)
126 /* Create a space for a parameter domain.
128 __isl_give isl_space
*isl_space_params_alloc(isl_ctx
*ctx
, unsigned nparam
)
131 space
= isl_space_alloc(ctx
, nparam
, 0, 0);
132 space
= mark_as_params(space
);
136 static unsigned global_pos(__isl_keep isl_space
*dim
,
137 enum isl_dim_type type
, unsigned pos
)
139 struct isl_ctx
*ctx
= dim
->ctx
;
143 isl_assert(ctx
, pos
< dim
->nparam
,
144 return isl_space_dim(dim
, isl_dim_all
));
147 isl_assert(ctx
, pos
< dim
->n_in
,
148 return isl_space_dim(dim
, isl_dim_all
));
149 return pos
+ dim
->nparam
;
151 isl_assert(ctx
, pos
< dim
->n_out
,
152 return isl_space_dim(dim
, isl_dim_all
));
153 return pos
+ dim
->nparam
+ dim
->n_in
;
155 isl_assert(ctx
, 0, return isl_space_dim(dim
, isl_dim_all
));
157 return isl_space_dim(dim
, isl_dim_all
);
160 /* Extend length of ids array to the total number of dimensions.
162 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*dim
)
167 if (isl_space_dim(dim
, isl_dim_all
) <= dim
->n_id
)
171 dim
->ids
= isl_calloc_array(dim
->ctx
,
172 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
176 ids
= isl_realloc_array(dim
->ctx
, dim
->ids
,
177 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
181 for (i
= dim
->n_id
; i
< isl_space_dim(dim
, isl_dim_all
); ++i
)
185 dim
->n_id
= isl_space_dim(dim
, isl_dim_all
);
193 static __isl_give isl_space
*set_id(__isl_take isl_space
*dim
,
194 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
196 dim
= isl_space_cow(dim
);
201 pos
= global_pos(dim
, type
, pos
);
202 if (pos
== isl_space_dim(dim
, isl_dim_all
))
205 if (pos
>= dim
->n_id
) {
208 dim
= extend_ids(dim
);
222 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*dim
,
223 enum isl_dim_type type
, unsigned pos
)
228 pos
= global_pos(dim
, type
, pos
);
229 if (pos
== isl_space_dim(dim
, isl_dim_all
))
231 if (pos
>= dim
->n_id
)
233 return dim
->ids
[pos
];
236 static unsigned offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
239 case isl_dim_param
: return 0;
240 case isl_dim_in
: return dim
->nparam
;
241 case isl_dim_out
: return dim
->nparam
+ dim
->n_in
;
246 static unsigned n(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
249 case isl_dim_param
: return dim
->nparam
;
250 case isl_dim_in
: return dim
->n_in
;
251 case isl_dim_out
: return dim
->n_out
;
252 case isl_dim_all
: return dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
257 unsigned isl_space_dim(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
264 unsigned isl_space_offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
268 return offset(dim
, type
);
271 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
272 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
273 enum isl_dim_type src_type
)
281 for (i
= 0; i
< n(src
, src_type
); ++i
) {
282 id
= get_id(src
, src_type
, i
);
285 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
292 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*dim
)
297 dup
= isl_space_alloc(dim
->ctx
, dim
->nparam
, dim
->n_in
, dim
->n_out
);
300 if (dim
->tuple_id
[0] &&
301 !(dup
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[0])))
303 if (dim
->tuple_id
[1] &&
304 !(dup
->tuple_id
[1] = isl_id_copy(dim
->tuple_id
[1])))
306 if (dim
->nested
[0] && !(dup
->nested
[0] = isl_space_copy(dim
->nested
[0])))
308 if (dim
->nested
[1] && !(dup
->nested
[1] = isl_space_copy(dim
->nested
[1])))
312 dup
= copy_ids(dup
, isl_dim_param
, 0, dim
, isl_dim_param
);
313 dup
= copy_ids(dup
, isl_dim_in
, 0, dim
, isl_dim_in
);
314 dup
= copy_ids(dup
, isl_dim_out
, 0, dim
, isl_dim_out
);
321 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*dim
)
329 return isl_space_dup(dim
);
332 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*dim
)
341 __isl_null isl_space
*isl_space_free(__isl_take isl_space
*space
)
348 if (--space
->ref
> 0)
351 isl_id_free(space
->tuple_id
[0]);
352 isl_id_free(space
->tuple_id
[1]);
354 isl_space_free(space
->nested
[0]);
355 isl_space_free(space
->nested
[1]);
357 for (i
= 0; i
< space
->n_id
; ++i
)
358 isl_id_free(space
->ids
[i
]);
360 isl_ctx_deref(space
->ctx
);
367 /* Check if "s" is a valid dimension or tuple name.
368 * We currently only forbid names that look like a number.
370 * s is assumed to be non-NULL.
372 static int name_ok(isl_ctx
*ctx
, const char *s
)
377 dummy
= strtol(s
, &p
, 0);
379 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
385 /* Is it possible for the given dimension type to have a tuple id?
387 static int space_can_have_id(__isl_keep isl_space
*space
,
388 enum isl_dim_type type
)
392 if (isl_space_is_params(space
))
393 isl_die(space
->ctx
, isl_error_invalid
,
394 "parameter spaces don't have tuple ids", return 0);
395 if (isl_space_is_set(space
) && type
!= isl_dim_set
)
396 isl_die(space
->ctx
, isl_error_invalid
,
397 "set spaces can only have a set id", return 0);
398 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
399 isl_die(space
->ctx
, isl_error_invalid
,
400 "only input, output and set tuples can have ids",
406 /* Does the tuple have an id?
408 int isl_space_has_tuple_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
410 if (!space_can_have_id(dim
, type
))
412 return dim
->tuple_id
[type
- isl_dim_in
] != NULL
;
415 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*dim
,
416 enum isl_dim_type type
)
422 has_id
= isl_space_has_tuple_id(dim
, type
);
426 isl_die(dim
->ctx
, isl_error_invalid
,
427 "tuple has no id", return NULL
);
428 return isl_id_copy(dim
->tuple_id
[type
- isl_dim_in
]);
431 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*dim
,
432 enum isl_dim_type type
, __isl_take isl_id
*id
)
434 dim
= isl_space_cow(dim
);
437 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
438 isl_die(dim
->ctx
, isl_error_invalid
,
439 "only input, output and set tuples can have names",
442 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
443 dim
->tuple_id
[type
- isl_dim_in
] = id
;
452 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*dim
,
453 enum isl_dim_type type
)
455 dim
= isl_space_cow(dim
);
458 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
459 isl_die(dim
->ctx
, isl_error_invalid
,
460 "only input, output and set tuples can have names",
463 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
464 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
472 /* Set the id of the given dimension of "space" to "id".
473 * If the dimension already has an id, then it is replaced.
474 * If the dimension is a parameter, then we need to change it
475 * in the nested spaces (if any) as well.
477 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*space
,
478 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
480 space
= isl_space_cow(space
);
484 if (type
== isl_dim_param
) {
487 for (i
= 0; i
< 2; ++i
) {
488 if (!space
->nested
[i
])
491 isl_space_set_dim_id(space
->nested
[i
],
492 type
, pos
, isl_id_copy(id
));
493 if (!space
->nested
[i
])
498 isl_id_free(get_id(space
, type
, pos
));
499 return set_id(space
, type
, pos
, id
);
502 isl_space_free(space
);
506 /* Reset the id of the given dimension of "space".
507 * If the dimension already has an id, then it is removed.
508 * If the dimension is a parameter, then we need to reset it
509 * in the nested spaces (if any) as well.
511 __isl_give isl_space
*isl_space_reset_dim_id(__isl_take isl_space
*space
,
512 enum isl_dim_type type
, unsigned pos
)
514 space
= isl_space_cow(space
);
518 if (type
== isl_dim_param
) {
521 for (i
= 0; i
< 2; ++i
) {
522 if (!space
->nested
[i
])
525 isl_space_reset_dim_id(space
->nested
[i
],
527 if (!space
->nested
[i
])
532 isl_id_free(get_id(space
, type
, pos
));
533 return set_id(space
, type
, pos
, NULL
);
535 isl_space_free(space
);
539 int isl_space_has_dim_id(__isl_keep isl_space
*dim
,
540 enum isl_dim_type type
, unsigned pos
)
544 return get_id(dim
, type
, pos
) != NULL
;
547 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*dim
,
548 enum isl_dim_type type
, unsigned pos
)
552 if (!get_id(dim
, type
, pos
))
553 isl_die(dim
->ctx
, isl_error_invalid
,
554 "dim has no id", return NULL
);
555 return isl_id_copy(get_id(dim
, type
, pos
));
558 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*dim
,
559 enum isl_dim_type type
, const char *s
)
567 return isl_space_reset_tuple_id(dim
, type
);
569 if (!name_ok(dim
->ctx
, s
))
572 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
573 return isl_space_set_tuple_id(dim
, type
, id
);
579 /* Does the tuple have a name?
581 int isl_space_has_tuple_name(__isl_keep isl_space
*space
,
582 enum isl_dim_type type
)
586 if (!space_can_have_id(space
, type
))
588 id
= space
->tuple_id
[type
- isl_dim_in
];
589 return id
&& id
->name
;
592 const char *isl_space_get_tuple_name(__isl_keep isl_space
*dim
,
593 enum isl_dim_type type
)
598 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
600 id
= dim
->tuple_id
[type
- isl_dim_in
];
601 return id
? id
->name
: NULL
;
604 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*dim
,
605 enum isl_dim_type type
, unsigned pos
,
613 return isl_space_reset_dim_id(dim
, type
, pos
);
614 if (!name_ok(dim
->ctx
, s
))
616 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
617 return isl_space_set_dim_id(dim
, type
, pos
, id
);
623 /* Does the given dimension have a name?
625 int isl_space_has_dim_name(__isl_keep isl_space
*space
,
626 enum isl_dim_type type
, unsigned pos
)
632 id
= get_id(space
, type
, pos
);
633 return id
&& id
->name
;
636 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*dim
,
637 enum isl_dim_type type
, unsigned pos
)
639 isl_id
*id
= get_id(dim
, type
, pos
);
640 return id
? id
->name
: NULL
;
643 int isl_space_find_dim_by_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
644 __isl_keep isl_id
*id
)
653 offset
= isl_space_offset(dim
, type
);
654 n
= isl_space_dim(dim
, type
);
655 for (i
= 0; i
< n
&& offset
+ i
< dim
->n_id
; ++i
)
656 if (dim
->ids
[offset
+ i
] == id
)
662 int isl_space_find_dim_by_name(__isl_keep isl_space
*space
,
663 enum isl_dim_type type
, const char *name
)
672 offset
= isl_space_offset(space
, type
);
673 n
= isl_space_dim(space
, type
);
674 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
)
675 if (space
->ids
[offset
+ i
]->name
&&
676 !strcmp(space
->ids
[offset
+ i
]->name
, name
))
682 /* Reset the user pointer on all identifiers of parameters and tuples
685 __isl_give isl_space
*isl_space_reset_user(__isl_take isl_space
*space
)
695 ctx
= isl_space_get_ctx(space
);
697 for (i
= 0; i
< space
->nparam
&& i
< space
->n_id
; ++i
) {
698 if (!isl_id_get_user(space
->ids
[i
]))
700 space
= isl_space_cow(space
);
703 name
= isl_id_get_name(space
->ids
[i
]);
704 id
= isl_id_alloc(ctx
, name
, NULL
);
705 isl_id_free(space
->ids
[i
]);
708 return isl_space_free(space
);
711 for (i
= 0; i
< 2; ++i
) {
712 if (!space
->tuple_id
[i
])
714 if (!isl_id_get_user(space
->tuple_id
[i
]))
716 space
= isl_space_cow(space
);
719 name
= isl_id_get_name(space
->tuple_id
[i
]);
720 id
= isl_id_alloc(ctx
, name
, NULL
);
721 isl_id_free(space
->tuple_id
[i
]);
722 space
->tuple_id
[i
] = id
;
724 return isl_space_free(space
);
727 for (i
= 0; i
< 2; ++i
) {
728 if (!space
->nested
[i
])
730 space
= isl_space_cow(space
);
733 space
->nested
[i
] = isl_space_reset_user(space
->nested
[i
]);
734 if (!space
->nested
[i
])
735 return isl_space_free(space
);
741 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*dim
,
742 enum isl_dim_type type
)
746 if (type
== isl_dim_in
)
747 return dim
->tuple_id
[0];
748 if (type
== isl_dim_out
)
749 return dim
->tuple_id
[1];
753 static __isl_keep isl_space
*nested(__isl_keep isl_space
*dim
,
754 enum isl_dim_type type
)
758 if (type
== isl_dim_in
)
759 return dim
->nested
[0];
760 if (type
== isl_dim_out
)
761 return dim
->nested
[1];
765 /* Are the two spaces the same, apart from positions and names of parameters?
767 static int isl_space_has_equal_tuples(__isl_keep isl_space
*space1
,
768 __isl_keep isl_space
*space2
)
770 if (!space1
|| !space2
)
772 if (space1
== space2
)
774 return isl_space_tuple_is_equal(space1
, isl_dim_in
,
775 space2
, isl_dim_in
) &&
776 isl_space_tuple_is_equal(space1
, isl_dim_out
,
777 space2
, isl_dim_out
);
780 /* Check if the tuple of type "type1" of "space1" is the same as
781 * the tuple of type "type2" of "space2".
783 * That is, check if the tuples have the same identifier, the same dimension
784 * and the same internal structure.
785 * The identifiers of the dimensions inside the tuples do not affect the result.
787 * Note that this function only checks the tuples themselves.
788 * If nested tuples are involved, then we need to be careful not
789 * to have result affected by possibly differing parameters
790 * in those nested tuples.
792 int isl_space_tuple_is_equal(__isl_keep isl_space
*space1
,
793 enum isl_dim_type type1
, __isl_keep isl_space
*space2
,
794 enum isl_dim_type type2
)
797 isl_space
*nested1
, *nested2
;
799 if (!space1
|| !space2
)
802 if (space1
== space2
&& type1
== type2
)
805 if (n(space1
, type1
) != n(space2
, type2
))
807 id1
= tuple_id(space1
, type1
);
808 id2
= tuple_id(space2
, type2
);
811 if (id1
&& id1
!= id2
)
813 nested1
= nested(space1
, type1
);
814 nested2
= nested(space2
, type2
);
815 if (!nested1
^ !nested2
)
817 if (nested1
&& !isl_space_has_equal_tuples(nested1
, nested2
))
822 /* This is the old, undocumented, name for isl_space_tuple_is_equal.
823 * It will be removed at some point.
825 int isl_space_tuple_match(__isl_keep isl_space
*space1
, enum isl_dim_type type1
,
826 __isl_keep isl_space
*space2
, enum isl_dim_type type2
)
828 return isl_space_tuple_is_equal(space1
, type1
, space2
, type2
);
831 static int match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
832 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
836 if (dim1
== dim2
&& dim1_type
== dim2_type
)
839 if (!isl_space_tuple_is_equal(dim1
, dim1_type
, dim2
, dim2_type
))
842 if (!dim1
->ids
&& !dim2
->ids
)
845 for (i
= 0; i
< n(dim1
, dim1_type
); ++i
) {
846 if (get_id(dim1
, dim1_type
, i
) != get_id(dim2
, dim2_type
, i
))
852 int isl_space_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
853 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
858 return match(dim1
, dim1_type
, dim2
, dim2_type
);
861 static void get_ids(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
862 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
866 for (i
= 0; i
< n
; ++i
)
867 ids
[i
] = get_id(dim
, type
, first
+ i
);
870 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*dim
,
871 unsigned nparam
, unsigned n_in
, unsigned n_out
)
877 if (dim
->nparam
== nparam
&& dim
->n_in
== n_in
&& dim
->n_out
== n_out
)
880 isl_assert(dim
->ctx
, dim
->nparam
<= nparam
, goto error
);
881 isl_assert(dim
->ctx
, dim
->n_in
<= n_in
, goto error
);
882 isl_assert(dim
->ctx
, dim
->n_out
<= n_out
, goto error
);
884 dim
= isl_space_cow(dim
);
889 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
890 nparam
+ n_in
+ n_out
);
893 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
894 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ nparam
);
895 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ nparam
+ n_in
);
898 dim
->n_id
= nparam
+ n_in
+ n_out
;
900 dim
->nparam
= nparam
;
911 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*dim
,
912 enum isl_dim_type type
, unsigned n
)
916 dim
= isl_space_reset(dim
, type
);
919 dim
= isl_space_extend(dim
,
920 dim
->nparam
+ n
, dim
->n_in
, dim
->n_out
);
921 if (dim
&& dim
->nested
[0] &&
922 !(dim
->nested
[0] = isl_space_add_dims(dim
->nested
[0],
925 if (dim
&& dim
->nested
[1] &&
926 !(dim
->nested
[1] = isl_space_add_dims(dim
->nested
[1],
931 return isl_space_extend(dim
,
932 dim
->nparam
, dim
->n_in
+ n
, dim
->n_out
);
934 return isl_space_extend(dim
,
935 dim
->nparam
, dim
->n_in
, dim
->n_out
+ n
);
937 isl_die(dim
->ctx
, isl_error_invalid
,
938 "cannot add dimensions of specified type", goto error
);
945 static int valid_dim_type(enum isl_dim_type type
)
957 /* Insert "n" dimensions of type "type" at position "pos".
958 * If we are inserting parameters, then they are also inserted in
961 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*dim
,
962 enum isl_dim_type type
, unsigned pos
, unsigned n
)
969 return isl_space_reset(dim
, type
);
971 if (!valid_dim_type(type
))
972 isl_die(dim
->ctx
, isl_error_invalid
,
973 "cannot insert dimensions of specified type",
976 isl_assert(dim
->ctx
, pos
<= isl_space_dim(dim
, type
), goto error
);
978 dim
= isl_space_cow(dim
);
983 enum isl_dim_type t
, o
= isl_dim_param
;
986 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
987 dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
);
991 s
[isl_dim_param
- o
] = dim
->nparam
;
992 s
[isl_dim_in
- o
] = dim
->n_in
;
993 s
[isl_dim_out
- o
] = dim
->n_out
;
994 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
996 get_ids(dim
, t
, 0, s
[t
- o
], ids
+ off
);
999 get_ids(dim
, t
, 0, pos
, ids
+ off
);
1001 get_ids(dim
, t
, pos
, s
[t
- o
] - pos
, ids
+ off
);
1002 off
+= s
[t
- o
] - pos
;
1007 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
;
1010 case isl_dim_param
: dim
->nparam
+= n
; break;
1011 case isl_dim_in
: dim
->n_in
+= n
; break;
1012 case isl_dim_out
: dim
->n_out
+= n
; break;
1015 dim
= isl_space_reset(dim
, type
);
1017 if (type
== isl_dim_param
) {
1018 if (dim
&& dim
->nested
[0] &&
1019 !(dim
->nested
[0] = isl_space_insert_dims(dim
->nested
[0],
1020 isl_dim_param
, pos
, n
)))
1022 if (dim
&& dim
->nested
[1] &&
1023 !(dim
->nested
[1] = isl_space_insert_dims(dim
->nested
[1],
1024 isl_dim_param
, pos
, n
)))
1030 isl_space_free(dim
);
1034 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*dim
,
1035 enum isl_dim_type dst_type
, unsigned dst_pos
,
1036 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1043 dim
= isl_space_reset(dim
, src_type
);
1044 return isl_space_reset(dim
, dst_type
);
1047 isl_assert(dim
->ctx
, src_pos
+ n
<= isl_space_dim(dim
, src_type
),
1050 if (dst_type
== src_type
&& dst_pos
== src_pos
)
1053 isl_assert(dim
->ctx
, dst_type
!= src_type
, goto error
);
1055 dim
= isl_space_reset(dim
, src_type
);
1056 dim
= isl_space_reset(dim
, dst_type
);
1058 dim
= isl_space_cow(dim
);
1064 enum isl_dim_type t
, o
= isl_dim_param
;
1067 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
1068 dim
->nparam
+ dim
->n_in
+ dim
->n_out
);
1072 s
[isl_dim_param
- o
] = dim
->nparam
;
1073 s
[isl_dim_in
- o
] = dim
->n_in
;
1074 s
[isl_dim_out
- o
] = dim
->n_out
;
1075 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
1076 if (t
== dst_type
) {
1077 get_ids(dim
, t
, 0, dst_pos
, ids
+ off
);
1079 get_ids(dim
, src_type
, src_pos
, n
, ids
+ off
);
1081 get_ids(dim
, t
, dst_pos
, s
[t
- o
] - dst_pos
,
1083 off
+= s
[t
- o
] - dst_pos
;
1084 } else if (t
== src_type
) {
1085 get_ids(dim
, t
, 0, src_pos
, ids
+ off
);
1087 get_ids(dim
, t
, src_pos
+ n
,
1088 s
[t
- o
] - src_pos
- n
, ids
+ off
);
1089 off
+= s
[t
- o
] - src_pos
- n
;
1091 get_ids(dim
, t
, 0, s
[t
- o
], ids
+ off
);
1097 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
1101 case isl_dim_param
: dim
->nparam
+= n
; break;
1102 case isl_dim_in
: dim
->n_in
+= n
; break;
1103 case isl_dim_out
: dim
->n_out
+= n
; break;
1108 case isl_dim_param
: dim
->nparam
-= n
; break;
1109 case isl_dim_in
: dim
->n_in
-= n
; break;
1110 case isl_dim_out
: dim
->n_out
-= n
; break;
1114 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
1117 for (i
= 0; i
< 2; ++i
) {
1118 if (!dim
->nested
[i
])
1120 dim
->nested
[i
] = isl_space_replace(dim
->nested
[i
],
1121 isl_dim_param
, dim
);
1122 if (!dim
->nested
[i
])
1128 isl_space_free(dim
);
1132 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
1133 __isl_take isl_space
*right
)
1137 if (!left
|| !right
)
1140 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
1142 isl_assert(left
->ctx
,
1143 isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_in
),
1146 dim
= isl_space_alloc(left
->ctx
, left
->nparam
, left
->n_in
, right
->n_out
);
1150 dim
= copy_ids(dim
, isl_dim_param
, 0, left
, isl_dim_param
);
1151 dim
= copy_ids(dim
, isl_dim_in
, 0, left
, isl_dim_in
);
1152 dim
= copy_ids(dim
, isl_dim_out
, 0, right
, isl_dim_out
);
1154 if (dim
&& left
->tuple_id
[0] &&
1155 !(dim
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
1157 if (dim
&& right
->tuple_id
[1] &&
1158 !(dim
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
1160 if (dim
&& left
->nested
[0] &&
1161 !(dim
->nested
[0] = isl_space_copy(left
->nested
[0])))
1163 if (dim
&& right
->nested
[1] &&
1164 !(dim
->nested
[1] = isl_space_copy(right
->nested
[1])))
1167 isl_space_free(left
);
1168 isl_space_free(right
);
1172 isl_space_free(left
);
1173 isl_space_free(right
);
1177 /* Given two map spaces { A -> C } and { B -> D }, construct the space
1178 * { [A -> B] -> [C -> D] }.
1179 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.
1181 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
1182 __isl_take isl_space
*right
)
1184 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
1187 if (!left
|| !right
)
1190 is_set
= isl_space_is_set(left
);
1191 if (is_set
!= isl_space_is_set(right
))
1192 isl_die(isl_space_get_ctx(left
), isl_error_invalid
,
1193 "expecting either two set spaces or two map spaces",
1196 return isl_space_range_product(left
, right
);
1198 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
1201 dom1
= isl_space_domain(isl_space_copy(left
));
1202 dom2
= isl_space_domain(isl_space_copy(right
));
1203 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1205 dom1
= isl_space_range(left
);
1206 dom2
= isl_space_range(right
);
1207 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1209 return isl_space_join(isl_space_reverse(nest1
), nest2
);
1211 isl_space_free(left
);
1212 isl_space_free(right
);
1216 /* Given two spaces { A -> C } and { B -> C }, construct the space
1219 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
1220 __isl_take isl_space
*right
)
1222 isl_space
*ran
, *dom1
, *dom2
, *nest
;
1224 if (!left
|| !right
)
1227 if (!match(left
, isl_dim_param
, right
, isl_dim_param
))
1228 isl_die(left
->ctx
, isl_error_invalid
,
1229 "parameters need to match", goto error
);
1230 if (!isl_space_tuple_is_equal(left
, isl_dim_out
, right
, isl_dim_out
))
1231 isl_die(left
->ctx
, isl_error_invalid
,
1232 "ranges need to match", goto error
);
1234 ran
= isl_space_range(isl_space_copy(left
));
1236 dom1
= isl_space_domain(left
);
1237 dom2
= isl_space_domain(right
);
1238 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
1240 return isl_space_join(isl_space_reverse(nest
), ran
);
1242 isl_space_free(left
);
1243 isl_space_free(right
);
1247 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
1248 __isl_take isl_space
*right
)
1250 isl_space
*dom
, *ran1
, *ran2
, *nest
;
1252 if (!left
|| !right
)
1255 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
1257 if (!isl_space_tuple_is_equal(left
, isl_dim_in
, right
, isl_dim_in
))
1258 isl_die(left
->ctx
, isl_error_invalid
,
1259 "domains need to match", goto error
);
1261 dom
= isl_space_domain(isl_space_copy(left
));
1263 ran1
= isl_space_range(left
);
1264 ran2
= isl_space_range(right
);
1265 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
1267 return isl_space_join(isl_space_reverse(dom
), nest
);
1269 isl_space_free(left
);
1270 isl_space_free(right
);
1274 /* Given a space of the form [A -> B] -> C, return the space A -> C.
1276 __isl_give isl_space
*isl_space_domain_factor_domain(
1277 __isl_take isl_space
*space
)
1284 if (!isl_space_domain_is_wrapping(space
))
1285 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1286 "domain not a product", return isl_space_free(space
));
1288 nested
= space
->nested
[0];
1289 domain
= isl_space_copy(space
);
1290 domain
= isl_space_drop_dims(space
, isl_dim_in
,
1291 nested
->n_in
, nested
->n_out
);
1293 return isl_space_free(space
);
1294 if (nested
->tuple_id
[0]) {
1295 domain
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[0]);
1296 if (!domain
->tuple_id
[0])
1299 if (nested
->nested
[0]) {
1300 domain
->nested
[0] = isl_space_copy(nested
->nested
[0]);
1301 if (!domain
->nested
[0])
1305 isl_space_free(space
);
1308 isl_space_free(space
);
1309 isl_space_free(domain
);
1313 /* Given a space of the form [A -> B] -> C, return the space B -> C.
1315 __isl_give isl_space
*isl_space_domain_factor_range(
1316 __isl_take isl_space
*space
)
1323 if (!isl_space_domain_is_wrapping(space
))
1324 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1325 "domain not a product", return isl_space_free(space
));
1327 nested
= space
->nested
[0];
1328 range
= isl_space_copy(space
);
1329 range
= isl_space_drop_dims(space
, isl_dim_in
, 0, nested
->n_in
);
1331 return isl_space_free(space
);
1332 if (nested
->tuple_id
[1]) {
1333 range
->tuple_id
[0] = isl_id_copy(nested
->tuple_id
[1]);
1334 if (!range
->tuple_id
[0])
1337 if (nested
->nested
[1]) {
1338 range
->nested
[0] = isl_space_copy(nested
->nested
[1]);
1339 if (!range
->nested
[0])
1343 isl_space_free(space
);
1346 isl_space_free(space
);
1347 isl_space_free(range
);
1351 /* Given a space of the form A -> [B -> C], return the space A -> B.
1353 __isl_give isl_space
*isl_space_range_factor_domain(
1354 __isl_take isl_space
*space
)
1361 if (!isl_space_range_is_wrapping(space
))
1362 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1363 "range not a product", return isl_space_free(space
));
1365 nested
= space
->nested
[1];
1366 domain
= isl_space_copy(space
);
1367 domain
= isl_space_drop_dims(space
, isl_dim_out
,
1368 nested
->n_in
, nested
->n_out
);
1370 return isl_space_free(space
);
1371 if (nested
->tuple_id
[0]) {
1372 domain
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[0]);
1373 if (!domain
->tuple_id
[1])
1376 if (nested
->nested
[0]) {
1377 domain
->nested
[1] = isl_space_copy(nested
->nested
[0]);
1378 if (!domain
->nested
[1])
1382 isl_space_free(space
);
1385 isl_space_free(space
);
1386 isl_space_free(domain
);
1390 /* Given a space of the form A -> [B -> C], return the space A -> C.
1392 __isl_give isl_space
*isl_space_range_factor_range(
1393 __isl_take isl_space
*space
)
1400 if (!isl_space_range_is_wrapping(space
))
1401 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1402 "range not a product", return isl_space_free(space
));
1404 nested
= space
->nested
[1];
1405 range
= isl_space_copy(space
);
1406 range
= isl_space_drop_dims(space
, isl_dim_out
, 0, nested
->n_in
);
1408 return isl_space_free(space
);
1409 if (nested
->tuple_id
[1]) {
1410 range
->tuple_id
[1] = isl_id_copy(nested
->tuple_id
[1]);
1411 if (!range
->tuple_id
[1])
1414 if (nested
->nested
[1]) {
1415 range
->nested
[1] = isl_space_copy(nested
->nested
[1]);
1416 if (!range
->nested
[1])
1420 isl_space_free(space
);
1423 isl_space_free(space
);
1424 isl_space_free(range
);
1428 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*dim
)
1431 isl_id
**ids
= NULL
;
1435 ctx
= isl_space_get_ctx(dim
);
1436 if (!isl_space_is_set(dim
))
1437 isl_die(ctx
, isl_error_invalid
, "not a set space", goto error
);
1438 dim
= isl_space_cow(dim
);
1442 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
1443 dim
->nparam
+ dim
->n_out
+ dim
->n_out
);
1446 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
1447 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->nparam
);
1449 dim
->n_in
= dim
->n_out
;
1453 dim
->n_id
= dim
->nparam
+ dim
->n_out
+ dim
->n_out
;
1454 dim
= copy_ids(dim
, isl_dim_out
, 0, dim
, isl_dim_in
);
1456 isl_id_free(dim
->tuple_id
[0]);
1457 dim
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[1]);
1458 isl_space_free(dim
->nested
[0]);
1459 dim
->nested
[0] = isl_space_copy(dim
->nested
[1]);
1462 isl_space_free(dim
);
1466 __isl_give isl_space
*isl_space_map_from_domain_and_range(
1467 __isl_take isl_space
*domain
, __isl_take isl_space
*range
)
1469 if (!domain
|| !range
)
1471 if (!isl_space_is_set(domain
))
1472 isl_die(isl_space_get_ctx(domain
), isl_error_invalid
,
1473 "domain is not a set space", goto error
);
1474 if (!isl_space_is_set(range
))
1475 isl_die(isl_space_get_ctx(range
), isl_error_invalid
,
1476 "range is not a set space", goto error
);
1477 return isl_space_join(isl_space_reverse(domain
), range
);
1479 isl_space_free(domain
);
1480 isl_space_free(range
);
1484 static __isl_give isl_space
*set_ids(__isl_take isl_space
*dim
,
1485 enum isl_dim_type type
,
1486 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
1490 for (i
= 0; i
< n
; ++i
)
1491 dim
= set_id(dim
, type
, first
+ i
, ids
[i
]);
1496 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*dim
)
1500 isl_id
**ids
= NULL
;
1505 if (match(dim
, isl_dim_in
, dim
, isl_dim_out
))
1508 dim
= isl_space_cow(dim
);
1512 id
= dim
->tuple_id
[0];
1513 dim
->tuple_id
[0] = dim
->tuple_id
[1];
1514 dim
->tuple_id
[1] = id
;
1516 nested
= dim
->nested
[0];
1517 dim
->nested
[0] = dim
->nested
[1];
1518 dim
->nested
[1] = nested
;
1521 int n_id
= dim
->n_in
+ dim
->n_out
;
1522 ids
= isl_alloc_array(dim
->ctx
, isl_id
*, n_id
);
1525 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
);
1526 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->n_in
);
1530 dim
->n_in
= dim
->n_out
;
1534 dim
= set_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
);
1535 dim
= set_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ dim
->n_out
);
1542 isl_space_free(dim
);
1546 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*dim
,
1547 enum isl_dim_type type
, unsigned first
, unsigned num
)
1555 return isl_space_reset(dim
, type
);
1557 if (!valid_dim_type(type
))
1558 isl_die(dim
->ctx
, isl_error_invalid
,
1559 "cannot drop dimensions of specified type", goto error
);
1561 if (first
+ num
> n(dim
, type
) || first
+ num
< first
)
1562 isl_die(isl_space_get_ctx(dim
), isl_error_invalid
,
1563 "index out of bounds", return isl_space_free(dim
));
1564 dim
= isl_space_cow(dim
);
1568 dim
= extend_ids(dim
);
1571 for (i
= 0; i
< num
; ++i
)
1572 isl_id_free(get_id(dim
, type
, first
+ i
));
1573 for (i
= first
+num
; i
< n(dim
, type
); ++i
)
1574 set_id(dim
, type
, i
- num
, get_id(dim
, type
, i
));
1577 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
,
1578 dim
->ids
+ offset(dim
, isl_dim_in
) - num
);
1580 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
,
1581 dim
->ids
+ offset(dim
, isl_dim_out
) - num
);
1588 case isl_dim_param
: dim
->nparam
-= num
; break;
1589 case isl_dim_in
: dim
->n_in
-= num
; break;
1590 case isl_dim_out
: dim
->n_out
-= num
; break;
1593 dim
= isl_space_reset(dim
, type
);
1594 if (type
== isl_dim_param
) {
1595 if (dim
&& dim
->nested
[0] &&
1596 !(dim
->nested
[0] = isl_space_drop_dims(dim
->nested
[0],
1597 isl_dim_param
, first
, num
)))
1599 if (dim
&& dim
->nested
[1] &&
1600 !(dim
->nested
[1] = isl_space_drop_dims(dim
->nested
[1],
1601 isl_dim_param
, first
, num
)))
1606 isl_space_free(dim
);
1610 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*dim
,
1611 unsigned first
, unsigned n
)
1615 return isl_space_drop_dims(dim
, isl_dim_in
, first
, n
);
1618 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*dim
,
1619 unsigned first
, unsigned n
)
1623 return isl_space_drop_dims(dim
, isl_dim_out
, first
, n
);
1626 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*dim
)
1630 dim
= isl_space_drop_outputs(dim
, 0, dim
->n_out
);
1631 dim
= isl_space_reverse(dim
);
1632 dim
= mark_as_set(dim
);
1636 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*dim
)
1640 if (!isl_space_is_set(dim
))
1641 isl_die(isl_space_get_ctx(dim
), isl_error_invalid
,
1642 "not a set space", goto error
);
1643 dim
= isl_space_reverse(dim
);
1644 dim
= isl_space_reset(dim
, isl_dim_out
);
1647 isl_space_free(dim
);
1651 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*dim
)
1655 dim
= isl_space_drop_inputs(dim
, 0, dim
->n_in
);
1656 dim
= mark_as_set(dim
);
1660 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*dim
)
1664 if (!isl_space_is_set(dim
))
1665 isl_die(isl_space_get_ctx(dim
), isl_error_invalid
,
1666 "not a set space", goto error
);
1667 return isl_space_reset(dim
, isl_dim_in
);
1669 isl_space_free(dim
);
1673 /* Given a map space A -> B, return the map space [A -> B] -> A.
1675 __isl_give isl_space
*isl_space_domain_map(__isl_take isl_space
*space
)
1679 domain
= isl_space_from_range(isl_space_domain(isl_space_copy(space
)));
1680 space
= isl_space_from_domain(isl_space_wrap(space
));
1681 space
= isl_space_join(space
, domain
);
1686 /* Given a map space A -> B, return the map space [A -> B] -> B.
1688 __isl_give isl_space
*isl_space_range_map(__isl_take isl_space
*space
)
1692 range
= isl_space_from_range(isl_space_range(isl_space_copy(space
)));
1693 space
= isl_space_from_domain(isl_space_wrap(space
));
1694 space
= isl_space_join(space
, range
);
1699 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
1701 if (isl_space_is_params(space
))
1703 space
= isl_space_drop_dims(space
,
1704 isl_dim_in
, 0, isl_space_dim(space
, isl_dim_in
));
1705 space
= isl_space_drop_dims(space
,
1706 isl_dim_out
, 0, isl_space_dim(space
, isl_dim_out
));
1707 space
= mark_as_params(space
);
1711 __isl_give isl_space
*isl_space_set_from_params(__isl_take isl_space
*space
)
1715 if (!isl_space_is_params(space
))
1716 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1717 "not a parameter space", goto error
);
1718 return isl_space_reset(space
, isl_dim_set
);
1720 isl_space_free(space
);
1724 __isl_give isl_space
*isl_space_as_set_space(__isl_take isl_space
*dim
)
1726 dim
= isl_space_cow(dim
);
1730 dim
->n_out
+= dim
->n_in
;
1732 dim
= isl_space_reset(dim
, isl_dim_in
);
1733 dim
= isl_space_reset(dim
, isl_dim_out
);
1738 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*dim
,
1746 dim
->nparam
== 0 && dim
->n_in
== 0 && dim
->n_id
== 0)
1747 return isl_space_reset(isl_space_reset(dim
, isl_dim_in
), isl_dim_out
);
1748 dim
= isl_space_cow(dim
);
1751 dim
->n_out
+= dim
->nparam
+ dim
->n_in
+ n_div
;
1755 for (i
= 0; i
< dim
->n_id
; ++i
)
1756 isl_id_free(get_id(dim
, isl_dim_out
, i
));
1758 dim
= isl_space_reset(dim
, isl_dim_in
);
1759 dim
= isl_space_reset(dim
, isl_dim_out
);
1764 /* Are the two spaces the same, including positions and names of parameters?
1766 int isl_space_is_equal(__isl_keep isl_space
*dim1
, __isl_keep isl_space
*dim2
)
1772 return match(dim1
, isl_dim_param
, dim2
, isl_dim_param
) &&
1773 isl_space_tuple_is_equal(dim1
, isl_dim_in
, dim2
, isl_dim_in
) &&
1774 isl_space_tuple_is_equal(dim1
, isl_dim_out
, dim2
, isl_dim_out
);
1777 /* Is space1 equal to the domain of space2?
1779 * In the internal version we also allow space2 to be the space of a set,
1780 * provided space1 is a parameter space.
1782 int isl_space_is_domain_internal(__isl_keep isl_space
*space1
,
1783 __isl_keep isl_space
*space2
)
1785 if (!space1
|| !space2
)
1787 if (!isl_space_is_set(space1
))
1789 return match(space1
, isl_dim_param
, space2
, isl_dim_param
) &&
1790 isl_space_tuple_is_equal(space1
, isl_dim_set
,
1791 space2
, isl_dim_in
);
1794 /* Is space1 equal to the domain of space2?
1796 int isl_space_is_domain(__isl_keep isl_space
*space1
,
1797 __isl_keep isl_space
*space2
)
1801 if (!isl_space_is_map(space2
))
1803 return isl_space_is_domain_internal(space1
, space2
);
1806 /* Is space1 equal to the range of space2?
1808 * In the internal version, space2 is allowed to be the space of a set,
1809 * in which case it should be equal to space1.
1811 int isl_space_is_range_internal(__isl_keep isl_space
*space1
,
1812 __isl_keep isl_space
*space2
)
1814 if (!space1
|| !space2
)
1816 if (!isl_space_is_set(space1
))
1818 return match(space1
, isl_dim_param
, space2
, isl_dim_param
) &&
1819 isl_space_tuple_is_equal(space1
, isl_dim_set
,
1820 space2
, isl_dim_out
);
1823 /* Is space1 equal to the range of space2?
1825 int isl_space_is_range(__isl_keep isl_space
*space1
,
1826 __isl_keep isl_space
*space2
)
1830 if (!isl_space_is_map(space2
))
1832 return isl_space_is_range_internal(space1
, space2
);
1835 int isl_space_compatible(__isl_keep isl_space
*dim1
,
1836 __isl_keep isl_space
*dim2
)
1838 return dim1
->nparam
== dim2
->nparam
&&
1839 dim1
->n_in
+ dim1
->n_out
== dim2
->n_in
+ dim2
->n_out
;
1842 static uint32_t isl_hash_dim(uint32_t hash
, __isl_keep isl_space
*dim
)
1850 isl_hash_byte(hash
, dim
->nparam
% 256);
1851 isl_hash_byte(hash
, dim
->n_in
% 256);
1852 isl_hash_byte(hash
, dim
->n_out
% 256);
1854 for (i
= 0; i
< dim
->nparam
; ++i
) {
1855 id
= get_id(dim
, isl_dim_param
, i
);
1856 hash
= isl_hash_id(hash
, id
);
1859 id
= tuple_id(dim
, isl_dim_in
);
1860 hash
= isl_hash_id(hash
, id
);
1861 id
= tuple_id(dim
, isl_dim_out
);
1862 hash
= isl_hash_id(hash
, id
);
1864 hash
= isl_hash_dim(hash
, dim
->nested
[0]);
1865 hash
= isl_hash_dim(hash
, dim
->nested
[1]);
1870 uint32_t isl_space_get_hash(__isl_keep isl_space
*dim
)
1877 hash
= isl_hash_init();
1878 hash
= isl_hash_dim(hash
, dim
);
1883 int isl_space_is_wrapping(__isl_keep isl_space
*dim
)
1888 if (!isl_space_is_set(dim
))
1891 return dim
->nested
[1] != NULL
;
1894 /* Is "space" the space of a map where the domain is a wrapped map space?
1896 int isl_space_domain_is_wrapping(__isl_keep isl_space
*space
)
1901 if (isl_space_is_set(space
))
1904 return space
->nested
[0] != NULL
;
1907 /* Is "space" the space of a map where the range is a wrapped map space?
1909 int isl_space_range_is_wrapping(__isl_keep isl_space
*space
)
1914 if (isl_space_is_set(space
))
1917 return space
->nested
[1] != NULL
;
1920 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*dim
)
1927 wrap
= isl_space_set_alloc(dim
->ctx
,
1928 dim
->nparam
, dim
->n_in
+ dim
->n_out
);
1930 wrap
= copy_ids(wrap
, isl_dim_param
, 0, dim
, isl_dim_param
);
1931 wrap
= copy_ids(wrap
, isl_dim_set
, 0, dim
, isl_dim_in
);
1932 wrap
= copy_ids(wrap
, isl_dim_set
, dim
->n_in
, dim
, isl_dim_out
);
1937 wrap
->nested
[1] = dim
;
1941 isl_space_free(dim
);
1945 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*dim
)
1952 if (!isl_space_is_wrapping(dim
))
1953 isl_die(dim
->ctx
, isl_error_invalid
, "not a wrapping space",
1956 unwrap
= isl_space_copy(dim
->nested
[1]);
1957 isl_space_free(dim
);
1961 isl_space_free(dim
);
1965 int isl_space_is_named_or_nested(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
1967 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
1971 if (dim
->tuple_id
[type
- isl_dim_in
])
1973 if (dim
->nested
[type
- isl_dim_in
])
1978 int isl_space_may_be_set(__isl_keep isl_space
*dim
)
1982 if (isl_space_is_set(dim
))
1984 if (isl_space_dim(dim
, isl_dim_in
) != 0)
1986 if (isl_space_is_named_or_nested(dim
, isl_dim_in
))
1991 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*dim
,
1992 enum isl_dim_type type
)
1994 if (!isl_space_is_named_or_nested(dim
, type
))
1997 dim
= isl_space_cow(dim
);
2001 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
2002 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
2003 isl_space_free(dim
->nested
[type
- isl_dim_in
]);
2004 dim
->nested
[type
- isl_dim_in
] = NULL
;
2009 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*dim
)
2013 if (!dim
->nested
[0] && !dim
->nested
[1])
2017 dim
= isl_space_reset(dim
, isl_dim_in
);
2018 if (dim
&& dim
->nested
[1])
2019 dim
= isl_space_reset(dim
, isl_dim_out
);
2024 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*dim
)
2028 if (!dim
->nested
[0])
2031 return isl_space_reset(dim
, isl_dim_in
);
2034 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*dim
)
2038 if (!dim
->nested
[1])
2041 return isl_space_reset(dim
, isl_dim_out
);
2044 /* Replace the dimensions of the given type of dst by those of src.
2046 __isl_give isl_space
*isl_space_replace(__isl_take isl_space
*dst
,
2047 enum isl_dim_type type
, __isl_keep isl_space
*src
)
2049 dst
= isl_space_cow(dst
);
2054 dst
= isl_space_drop_dims(dst
, type
, 0, isl_space_dim(dst
, type
));
2055 dst
= isl_space_add_dims(dst
, type
, isl_space_dim(src
, type
));
2056 dst
= copy_ids(dst
, type
, 0, src
, type
);
2058 if (dst
&& type
== isl_dim_param
) {
2060 for (i
= 0; i
<= 1; ++i
) {
2061 if (!dst
->nested
[i
])
2063 dst
->nested
[i
] = isl_space_replace(dst
->nested
[i
],
2065 if (!dst
->nested
[i
])
2072 isl_space_free(dst
);
2076 /* Given a dimension specification "dim" of a set, create a dimension
2077 * specification for the lift of the set. In particular, the result
2078 * is of the form [dim -> local[..]], with n_local variables in the
2079 * range of the wrapped map.
2081 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*dim
, unsigned n_local
)
2083 isl_space
*local_dim
;
2088 local_dim
= isl_space_dup(dim
);
2089 local_dim
= isl_space_drop_dims(local_dim
, isl_dim_set
, 0, dim
->n_out
);
2090 local_dim
= isl_space_add_dims(local_dim
, isl_dim_set
, n_local
);
2091 local_dim
= isl_space_set_tuple_name(local_dim
, isl_dim_set
, "local");
2092 dim
= isl_space_join(isl_space_from_domain(dim
),
2093 isl_space_from_range(local_dim
));
2094 dim
= isl_space_wrap(dim
);
2095 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, "lifted");
2100 int isl_space_can_zip(__isl_keep isl_space
*dim
)
2105 return dim
->nested
[0] && dim
->nested
[1];
2108 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*dim
)
2110 isl_space
*dom
, *ran
;
2111 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
2113 if (!isl_space_can_zip(dim
))
2114 isl_die(dim
->ctx
, isl_error_invalid
, "dim cannot be zipped",
2119 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(dim
)));
2120 ran
= isl_space_unwrap(isl_space_range(dim
));
2121 dom_dom
= isl_space_domain(isl_space_copy(dom
));
2122 dom_ran
= isl_space_range(dom
);
2123 ran_dom
= isl_space_domain(isl_space_copy(ran
));
2124 ran_ran
= isl_space_range(ran
);
2125 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
2126 isl_space_from_range(ran_dom
));
2127 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
2128 isl_space_from_range(ran_ran
));
2129 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
2130 isl_space_from_range(isl_space_wrap(ran
)));
2132 isl_space_free(dim
);
2136 /* Can we apply isl_space_curry to "space"?
2137 * That is, does it have a nested relation in its domain?
2139 int isl_space_can_curry(__isl_keep isl_space
*space
)
2144 return !!space
->nested
[0];
2147 /* Given a space (A -> B) -> C, return the corresponding space
2150 __isl_give isl_space
*isl_space_curry(__isl_take isl_space
*space
)
2152 isl_space
*dom
, *ran
;
2153 isl_space
*dom_dom
, *dom_ran
;
2158 if (!isl_space_can_curry(space
))
2159 isl_die(space
->ctx
, isl_error_invalid
,
2160 "space cannot be curried", goto error
);
2162 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(space
)));
2163 ran
= isl_space_range(space
);
2164 dom_dom
= isl_space_domain(isl_space_copy(dom
));
2165 dom_ran
= isl_space_range(dom
);
2166 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
2167 isl_space_from_range(ran
));
2168 return isl_space_join(isl_space_from_domain(dom_dom
),
2169 isl_space_from_range(isl_space_wrap(ran
)));
2171 isl_space_free(space
);
2175 /* Can we apply isl_space_uncurry to "space"?
2176 * That is, does it have a nested relation in its range?
2178 int isl_space_can_uncurry(__isl_keep isl_space
*space
)
2183 return !!space
->nested
[1];
2186 /* Given a space A -> (B -> C), return the corresponding space
2189 __isl_give isl_space
*isl_space_uncurry(__isl_take isl_space
*space
)
2191 isl_space
*dom
, *ran
;
2192 isl_space
*ran_dom
, *ran_ran
;
2197 if (!isl_space_can_uncurry(space
))
2198 isl_die(space
->ctx
, isl_error_invalid
,
2199 "space cannot be uncurried",
2200 return isl_space_free(space
));
2202 dom
= isl_space_domain(isl_space_copy(space
));
2203 ran
= isl_space_unwrap(isl_space_range(space
));
2204 ran_dom
= isl_space_domain(isl_space_copy(ran
));
2205 ran_ran
= isl_space_range(ran
);
2206 dom
= isl_space_join(isl_space_from_domain(dom
),
2207 isl_space_from_range(ran_dom
));
2208 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
2209 isl_space_from_range(ran_ran
));
2212 int isl_space_has_named_params(__isl_keep isl_space
*dim
)
2219 if (dim
->nparam
== 0)
2221 off
= isl_space_offset(dim
, isl_dim_param
);
2222 if (off
+ dim
->nparam
> dim
->n_id
)
2224 for (i
= 0; i
< dim
->nparam
; ++i
)
2225 if (!dim
->ids
[off
+ i
])
2230 /* Align the initial parameters of dim1 to match the order in dim2.
2232 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*dim1
,
2233 __isl_take isl_space
*dim2
)
2235 isl_reordering
*exp
;
2237 if (!isl_space_has_named_params(dim1
) || !isl_space_has_named_params(dim2
))
2238 isl_die(isl_space_get_ctx(dim1
), isl_error_invalid
,
2239 "parameter alignment requires named parameters",
2242 dim2
= isl_space_params(dim2
);
2243 exp
= isl_parameter_alignment_reordering(dim1
, dim2
);
2244 exp
= isl_reordering_extend_space(exp
, dim1
);
2245 isl_space_free(dim2
);
2248 dim1
= isl_space_copy(exp
->dim
);
2249 isl_reordering_free(exp
);
2252 isl_space_free(dim1
);
2253 isl_space_free(dim2
);
2257 /* Given the space of set (domain), construct a space for a map
2258 * with as domain the given space and as range the range of "model".
2260 __isl_give isl_space
*isl_space_extend_domain_with_range(
2261 __isl_take isl_space
*space
, __isl_take isl_space
*model
)
2266 space
= isl_space_from_domain(space
);
2267 space
= isl_space_add_dims(space
, isl_dim_out
,
2268 isl_space_dim(model
, isl_dim_out
));
2269 if (isl_space_has_tuple_id(model
, isl_dim_out
))
2270 space
= isl_space_set_tuple_id(space
, isl_dim_out
,
2271 isl_space_get_tuple_id(model
, isl_dim_out
));
2274 if (model
->nested
[1]) {
2275 isl_space
*nested
= isl_space_copy(model
->nested
[1]);
2276 int n_nested
, n_space
;
2277 nested
= isl_space_align_params(nested
, isl_space_copy(space
));
2278 n_nested
= isl_space_dim(nested
, isl_dim_param
);
2279 n_space
= isl_space_dim(space
, isl_dim_param
);
2280 if (n_nested
> n_space
)
2281 nested
= isl_space_drop_dims(nested
, isl_dim_param
,
2282 n_space
, n_nested
- n_space
);
2285 space
->nested
[1] = nested
;
2287 isl_space_free(model
);
2290 isl_space_free(model
);
2291 isl_space_free(space
);
2295 /* Compare the "type" dimensions of two isl_spaces.
2297 * The order is fairly arbitrary.
2299 static int isl_space_cmp_type(__isl_keep isl_space
*space1
,
2300 __isl_keep isl_space
*space2
, enum isl_dim_type type
)
2303 isl_space
*nested1
, *nested2
;
2305 if (isl_space_dim(space1
, type
) != isl_space_dim(space2
, type
))
2306 return isl_space_dim(space1
, type
) -
2307 isl_space_dim(space2
, type
);
2309 cmp
= isl_id_cmp(tuple_id(space1
, type
), tuple_id(space2
, type
));
2313 nested1
= nested(space1
, type
);
2314 nested2
= nested(space2
, type
);
2315 if (!nested1
!= !nested2
)
2316 return !nested1
- !nested2
;
2319 return isl_space_cmp(nested1
, nested2
);
2324 /* Compare two isl_spaces.
2326 * The order is fairly arbitrary.
2328 int isl_space_cmp(__isl_keep isl_space
*space1
, __isl_keep isl_space
*space2
)
2333 if (space1
== space2
)
2340 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_param
);
2343 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_in
);
2346 cmp
= isl_space_cmp_type(space1
, space2
, isl_dim_out
);
2350 if (!space1
->ids
&& !space2
->ids
)
2353 for (i
= 0; i
< n(space1
, isl_dim_param
); ++i
) {
2354 cmp
= isl_id_cmp(get_id(space1
, isl_dim_param
, i
),
2355 get_id(space2
, isl_dim_param
, i
));