2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
5 * Use of this software is governed by the GNU LGPLv2.1 license
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
14 #include <isl_space_private.h>
15 #include <isl_id_private.h>
16 #include <isl_reordering.h>
18 isl_ctx
*isl_space_get_ctx(__isl_keep isl_space
*dim
)
20 return dim
? dim
->ctx
: NULL
;
23 __isl_give isl_space
*isl_space_alloc(isl_ctx
*ctx
,
24 unsigned nparam
, unsigned n_in
, unsigned n_out
)
28 dim
= isl_alloc_type(ctx
, struct isl_space
);
39 dim
->tuple_id
[0] = NULL
;
40 dim
->tuple_id
[1] = NULL
;
42 dim
->nested
[0] = NULL
;
43 dim
->nested
[1] = NULL
;
51 __isl_give isl_space
*isl_space_set_alloc(isl_ctx
*ctx
,
52 unsigned nparam
, unsigned dim
)
54 return isl_space_alloc(ctx
, nparam
, 0, dim
);
57 static unsigned global_pos(__isl_keep isl_space
*dim
,
58 enum isl_dim_type type
, unsigned pos
)
60 struct isl_ctx
*ctx
= dim
->ctx
;
64 isl_assert(ctx
, pos
< dim
->nparam
,
65 return isl_space_dim(dim
, isl_dim_all
));
68 isl_assert(ctx
, pos
< dim
->n_in
,
69 return isl_space_dim(dim
, isl_dim_all
));
70 return pos
+ dim
->nparam
;
72 isl_assert(ctx
, pos
< dim
->n_out
,
73 return isl_space_dim(dim
, isl_dim_all
));
74 return pos
+ dim
->nparam
+ dim
->n_in
;
76 isl_assert(ctx
, 0, return isl_space_dim(dim
, isl_dim_all
));
78 return isl_space_dim(dim
, isl_dim_all
);
81 /* Extend length of ids array to the total number of dimensions.
83 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*dim
)
88 if (isl_space_dim(dim
, isl_dim_all
) <= dim
->n_id
)
92 dim
->ids
= isl_calloc_array(dim
->ctx
,
93 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
97 ids
= isl_realloc_array(dim
->ctx
, dim
->ids
,
98 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
102 for (i
= dim
->n_id
; i
< isl_space_dim(dim
, isl_dim_all
); ++i
)
106 dim
->n_id
= isl_space_dim(dim
, isl_dim_all
);
114 static __isl_give isl_space
*set_id(__isl_take isl_space
*dim
,
115 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
117 dim
= isl_space_cow(dim
);
122 pos
= global_pos(dim
, type
, pos
);
123 if (pos
== isl_space_dim(dim
, isl_dim_all
))
126 if (pos
>= dim
->n_id
) {
129 dim
= extend_ids(dim
);
143 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*dim
,
144 enum isl_dim_type type
, unsigned pos
)
149 pos
= global_pos(dim
, type
, pos
);
150 if (pos
== isl_space_dim(dim
, isl_dim_all
))
152 if (pos
>= dim
->n_id
)
154 return dim
->ids
[pos
];
157 static unsigned offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
160 case isl_dim_param
: return 0;
161 case isl_dim_in
: return dim
->nparam
;
162 case isl_dim_out
: return dim
->nparam
+ dim
->n_in
;
167 static unsigned n(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
170 case isl_dim_param
: return dim
->nparam
;
171 case isl_dim_in
: return dim
->n_in
;
172 case isl_dim_out
: return dim
->n_out
;
173 case isl_dim_all
: return dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
178 unsigned isl_space_dim(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
185 unsigned isl_space_offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
189 return offset(dim
, type
);
192 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
193 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
194 enum isl_dim_type src_type
)
202 for (i
= 0; i
< n(src
, src_type
); ++i
) {
203 id
= get_id(src
, src_type
, i
);
206 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
213 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*dim
)
218 dup
= isl_space_alloc(dim
->ctx
, dim
->nparam
, dim
->n_in
, dim
->n_out
);
219 if (dim
->tuple_id
[0] &&
220 !(dup
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[0])))
222 if (dim
->tuple_id
[1] &&
223 !(dup
->tuple_id
[1] = isl_id_copy(dim
->tuple_id
[1])))
225 if (dim
->nested
[0] && !(dup
->nested
[0] = isl_space_copy(dim
->nested
[0])))
227 if (dim
->nested
[1] && !(dup
->nested
[1] = isl_space_copy(dim
->nested
[1])))
231 dup
= copy_ids(dup
, isl_dim_param
, 0, dim
, isl_dim_param
);
232 dup
= copy_ids(dup
, isl_dim_in
, 0, dim
, isl_dim_in
);
233 dup
= copy_ids(dup
, isl_dim_out
, 0, dim
, isl_dim_out
);
240 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*dim
)
248 return isl_space_dup(dim
);
251 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*dim
)
260 void isl_space_free(__isl_take isl_space
*dim
)
270 isl_id_free(dim
->tuple_id
[0]);
271 isl_id_free(dim
->tuple_id
[1]);
273 isl_space_free(dim
->nested
[0]);
274 isl_space_free(dim
->nested
[1]);
276 for (i
= 0; i
< dim
->n_id
; ++i
)
277 isl_id_free(dim
->ids
[i
]);
279 isl_ctx_deref(dim
->ctx
);
284 static int name_ok(isl_ctx
*ctx
, const char *s
)
289 dummy
= strtol(s
, &p
, 0);
291 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
297 int isl_space_has_tuple_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
301 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
302 isl_die(dim
->ctx
, isl_error_invalid
,
303 "only input, output and set tuples can have ids",
305 return dim
->tuple_id
[type
- isl_dim_in
] != NULL
;
308 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*dim
,
309 enum isl_dim_type type
)
313 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
314 isl_die(dim
->ctx
, isl_error_invalid
,
315 "only input, output and set tuples can have ids",
317 if (!dim
->tuple_id
[type
- isl_dim_in
])
318 isl_die(dim
->ctx
, isl_error_invalid
,
319 "tuple has no id", return NULL
);
320 return isl_id_copy(dim
->tuple_id
[type
- isl_dim_in
]);
323 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*dim
,
324 enum isl_dim_type type
, __isl_take isl_id
*id
)
326 dim
= isl_space_cow(dim
);
329 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
330 isl_die(dim
->ctx
, isl_error_invalid
,
331 "only input, output and set tuples can have names",
334 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
335 dim
->tuple_id
[type
- isl_dim_in
] = id
;
344 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*dim
,
345 enum isl_dim_type type
)
347 dim
= isl_space_cow(dim
);
350 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
351 isl_die(dim
->ctx
, isl_error_invalid
,
352 "only input, output and set tuples can have names",
355 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
356 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
364 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*dim
,
365 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
367 dim
= isl_space_cow(dim
);
370 isl_id_free(get_id(dim
, type
, pos
));
371 return set_id(dim
, type
, pos
, id
);
378 int isl_space_has_dim_id(__isl_keep isl_space
*dim
,
379 enum isl_dim_type type
, unsigned pos
)
383 return get_id(dim
, type
, pos
) != NULL
;
386 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*dim
,
387 enum isl_dim_type type
, unsigned pos
)
391 if (!get_id(dim
, type
, pos
))
392 isl_die(dim
->ctx
, isl_error_invalid
,
393 "dim has no id", return NULL
);
394 return isl_id_copy(get_id(dim
, type
, pos
));
397 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*dim
,
398 enum isl_dim_type type
, const char *s
)
406 return isl_space_reset_tuple_id(dim
, type
);
408 if (!name_ok(dim
->ctx
, s
))
411 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
412 return isl_space_set_tuple_id(dim
, type
, id
);
418 const char *isl_space_get_tuple_name(__isl_keep isl_space
*dim
,
419 enum isl_dim_type type
)
424 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
426 id
= dim
->tuple_id
[type
- isl_dim_in
];
427 return id
? id
->name
: NULL
;
430 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*dim
,
431 enum isl_dim_type type
, unsigned pos
,
438 if (!name_ok(dim
->ctx
, s
))
440 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
441 return isl_space_set_dim_id(dim
, type
, pos
, id
);
447 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*dim
,
448 enum isl_dim_type type
, unsigned pos
)
450 isl_id
*id
= get_id(dim
, type
, pos
);
451 return id
? id
->name
: NULL
;
454 int isl_space_find_dim_by_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
455 __isl_keep isl_id
*id
)
464 offset
= isl_space_offset(dim
, type
);
465 n
= isl_space_dim(dim
, type
);
466 for (i
= 0; i
< n
&& offset
+ i
< dim
->n_id
; ++i
)
467 if (dim
->ids
[offset
+ i
] == id
)
473 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*dim
,
474 enum isl_dim_type type
)
478 if (type
== isl_dim_in
)
479 return dim
->tuple_id
[0];
480 if (type
== isl_dim_out
)
481 return dim
->tuple_id
[1];
485 static __isl_keep isl_space
*nested(__isl_keep isl_space
*dim
,
486 enum isl_dim_type type
)
490 if (type
== isl_dim_in
)
491 return dim
->nested
[0];
492 if (type
== isl_dim_out
)
493 return dim
->nested
[1];
497 int isl_space_tuple_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
498 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
501 isl_space
*nested1
, *nested2
;
506 if (dim1
== dim2
&& dim1_type
== dim2_type
)
509 if (n(dim1
, dim1_type
) != n(dim2
, dim2_type
))
511 id1
= tuple_id(dim1
, dim1_type
);
512 id2
= tuple_id(dim2
, dim2_type
);
515 if (id1
&& id1
!= id2
)
517 nested1
= nested(dim1
, dim1_type
);
518 nested2
= nested(dim2
, dim2_type
);
519 if (!nested1
^ !nested2
)
521 if (nested1
&& !isl_space_is_equal(nested1
, nested2
))
526 static int match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
527 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
531 if (dim1
== dim2
&& dim1_type
== dim2_type
)
534 if (!isl_space_tuple_match(dim1
, dim1_type
, dim2
, dim2_type
))
537 if (!dim1
->ids
&& !dim2
->ids
)
540 for (i
= 0; i
< n(dim1
, dim1_type
); ++i
) {
541 if (get_id(dim1
, dim1_type
, i
) != get_id(dim2
, dim2_type
, i
))
547 int isl_space_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
548 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
553 return match(dim1
, dim1_type
, dim2
, dim2_type
);
556 static void get_ids(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
557 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
561 for (i
= 0; i
< n
; ++i
)
562 ids
[i
] = get_id(dim
, type
, first
+ i
);
565 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*dim
,
566 unsigned nparam
, unsigned n_in
, unsigned n_out
)
572 if (dim
->nparam
== nparam
&& dim
->n_in
== n_in
&& dim
->n_out
== n_out
)
575 isl_assert(dim
->ctx
, dim
->nparam
<= nparam
, goto error
);
576 isl_assert(dim
->ctx
, dim
->n_in
<= n_in
, goto error
);
577 isl_assert(dim
->ctx
, dim
->n_out
<= n_out
, goto error
);
579 dim
= isl_space_cow(dim
);
582 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
583 nparam
+ n_in
+ n_out
);
586 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
587 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ nparam
);
588 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ nparam
+ n_in
);
591 dim
->n_id
= nparam
+ n_in
+ n_out
;
593 dim
->nparam
= nparam
;
604 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*dim
,
605 enum isl_dim_type type
, unsigned n
)
609 dim
= isl_space_reset(dim
, type
);
612 dim
= isl_space_extend(dim
,
613 dim
->nparam
+ n
, dim
->n_in
, dim
->n_out
);
614 if (dim
&& dim
->nested
[0] &&
615 !(dim
->nested
[0] = isl_space_add_dims(dim
->nested
[0],
618 if (dim
&& dim
->nested
[1] &&
619 !(dim
->nested
[1] = isl_space_add_dims(dim
->nested
[1],
624 return isl_space_extend(dim
,
625 dim
->nparam
, dim
->n_in
+ n
, dim
->n_out
);
627 return isl_space_extend(dim
,
628 dim
->nparam
, dim
->n_in
, dim
->n_out
+ n
);
630 isl_die(dim
->ctx
, isl_error_invalid
,
631 "cannot add dimensions of specified type", goto error
);
638 static int valid_dim_type(enum isl_dim_type type
)
650 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*dim
,
651 enum isl_dim_type type
, unsigned pos
, unsigned n
)
658 return isl_space_reset(dim
, type
);
660 if (!valid_dim_type(type
))
661 isl_die(dim
->ctx
, isl_error_invalid
,
662 "cannot insert dimensions of specified type",
665 isl_assert(dim
->ctx
, pos
<= isl_space_dim(dim
, type
), goto error
);
667 dim
= isl_space_cow(dim
);
675 int *size
= s
- isl_dim_param
;
676 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
677 dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
);
681 size
[isl_dim_param
] = dim
->nparam
;
682 size
[isl_dim_in
] = dim
->n_in
;
683 size
[isl_dim_out
] = dim
->n_out
;
684 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
686 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
689 get_ids(dim
, t
, 0, pos
, ids
+ off
);
691 get_ids(dim
, t
, pos
, size
[t
] - pos
, ids
+ off
);
692 off
+= size
[t
] - pos
;
697 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
;
700 case isl_dim_param
: dim
->nparam
+= n
; break;
701 case isl_dim_in
: dim
->n_in
+= n
; break;
702 case isl_dim_out
: dim
->n_out
+= n
; break;
705 dim
= isl_space_reset(dim
, type
);
713 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*dim
,
714 enum isl_dim_type dst_type
, unsigned dst_pos
,
715 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
724 isl_assert(dim
->ctx
, src_pos
+ n
<= isl_space_dim(dim
, src_type
),
727 if (dst_type
== src_type
&& dst_pos
== src_pos
)
730 isl_assert(dim
->ctx
, dst_type
!= src_type
, goto error
);
732 dim
= isl_space_reset(dim
, src_type
);
733 dim
= isl_space_reset(dim
, dst_type
);
735 dim
= isl_space_cow(dim
);
744 int *size
= s
- isl_dim_param
;
745 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
746 dim
->nparam
+ dim
->n_in
+ dim
->n_out
);
750 size
[isl_dim_param
] = dim
->nparam
;
751 size
[isl_dim_in
] = dim
->n_in
;
752 size
[isl_dim_out
] = dim
->n_out
;
753 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
755 get_ids(dim
, t
, 0, dst_pos
, ids
+ off
);
757 get_ids(dim
, src_type
, src_pos
, n
, ids
+ off
);
759 get_ids(dim
, t
, dst_pos
, size
[t
] - dst_pos
,
761 off
+= size
[t
] - dst_pos
;
762 } else if (t
== src_type
) {
763 get_ids(dim
, t
, 0, src_pos
, ids
+ off
);
765 get_ids(dim
, t
, src_pos
+ n
,
766 size
[t
] - src_pos
- n
, ids
+ off
);
767 off
+= size
[t
] - src_pos
- n
;
769 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
775 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
779 case isl_dim_param
: dim
->nparam
+= n
; break;
780 case isl_dim_in
: dim
->n_in
+= n
; break;
781 case isl_dim_out
: dim
->n_out
+= n
; break;
786 case isl_dim_param
: dim
->nparam
-= n
; break;
787 case isl_dim_in
: dim
->n_in
-= n
; break;
788 case isl_dim_out
: dim
->n_out
-= n
; break;
792 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
795 for (i
= 0; i
< 2; ++i
) {
798 dim
->nested
[i
] = isl_space_replace(dim
->nested
[i
],
810 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
811 __isl_take isl_space
*right
)
818 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
820 isl_assert(left
->ctx
,
821 isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_in
),
824 dim
= isl_space_alloc(left
->ctx
, left
->nparam
, left
->n_in
, right
->n_out
);
828 dim
= copy_ids(dim
, isl_dim_param
, 0, left
, isl_dim_param
);
829 dim
= copy_ids(dim
, isl_dim_in
, 0, left
, isl_dim_in
);
830 dim
= copy_ids(dim
, isl_dim_out
, 0, right
, isl_dim_out
);
832 if (dim
&& left
->tuple_id
[0] &&
833 !(dim
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
835 if (dim
&& right
->tuple_id
[1] &&
836 !(dim
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
838 if (dim
&& left
->nested
[0] &&
839 !(dim
->nested
[0] = isl_space_copy(left
->nested
[0])))
841 if (dim
&& right
->nested
[1] &&
842 !(dim
->nested
[1] = isl_space_copy(right
->nested
[1])))
845 isl_space_free(left
);
846 isl_space_free(right
);
850 isl_space_free(left
);
851 isl_space_free(right
);
855 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
856 __isl_take isl_space
*right
)
858 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
863 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
866 dom1
= isl_space_domain(isl_space_copy(left
));
867 dom2
= isl_space_domain(isl_space_copy(right
));
868 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
870 dom1
= isl_space_range(left
);
871 dom2
= isl_space_range(right
);
872 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
874 return isl_space_join(isl_space_reverse(nest1
), nest2
);
876 isl_space_free(left
);
877 isl_space_free(right
);
881 /* Given two spaces { A -> C } and { B -> C }, construct the space
884 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
885 __isl_take isl_space
*right
)
887 isl_space
*ran
, *dom1
, *dom2
, *nest
;
892 if (!match(left
, isl_dim_param
, right
, isl_dim_param
))
893 isl_die(left
->ctx
, isl_error_invalid
,
894 "parameters need to match", goto error
);
895 if (!isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_out
))
896 isl_die(left
->ctx
, isl_error_invalid
,
897 "ranges need to match", goto error
);
899 ran
= isl_space_range(isl_space_copy(left
));
901 dom1
= isl_space_domain(left
);
902 dom2
= isl_space_domain(right
);
903 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
905 return isl_space_join(isl_space_reverse(nest
), ran
);
907 isl_space_free(left
);
908 isl_space_free(right
);
912 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
913 __isl_take isl_space
*right
)
915 isl_space
*dom
, *ran1
, *ran2
, *nest
;
920 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
922 if (!isl_space_tuple_match(left
, isl_dim_in
, right
, isl_dim_in
))
923 isl_die(left
->ctx
, isl_error_invalid
,
924 "domains need to match", goto error
);
926 dom
= isl_space_domain(isl_space_copy(left
));
928 ran1
= isl_space_range(left
);
929 ran2
= isl_space_range(right
);
930 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
932 return isl_space_join(isl_space_reverse(dom
), nest
);
934 isl_space_free(left
);
935 isl_space_free(right
);
939 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*dim
)
945 isl_assert(dim
->ctx
, dim
->n_in
== 0, goto error
);
946 if (dim
->n_out
== 0 && !isl_space_is_named_or_nested(dim
, isl_dim_out
))
948 dim
= isl_space_cow(dim
);
952 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
953 dim
->nparam
+ dim
->n_out
+ dim
->n_out
);
956 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
957 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->nparam
);
959 dim
->n_in
= dim
->n_out
;
963 dim
->n_id
= dim
->nparam
+ dim
->n_out
+ dim
->n_out
;
964 dim
= copy_ids(dim
, isl_dim_out
, 0, dim
, isl_dim_in
);
966 isl_id_free(dim
->tuple_id
[0]);
967 dim
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[1]);
968 isl_space_free(dim
->nested
[0]);
969 dim
->nested
[0] = isl_space_copy(dim
->nested
[1]);
976 static __isl_give isl_space
*set_ids(__isl_take isl_space
*dim
,
977 enum isl_dim_type type
,
978 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
982 for (i
= 0; i
< n
; ++i
)
983 dim
= set_id(dim
, type
, first
+ i
, ids
[i
]);
988 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*dim
)
997 if (match(dim
, isl_dim_in
, dim
, isl_dim_out
))
1000 dim
= isl_space_cow(dim
);
1004 id
= dim
->tuple_id
[0];
1005 dim
->tuple_id
[0] = dim
->tuple_id
[1];
1006 dim
->tuple_id
[1] = id
;
1008 nested
= dim
->nested
[0];
1009 dim
->nested
[0] = dim
->nested
[1];
1010 dim
->nested
[1] = nested
;
1013 ids
= isl_alloc_array(dim
->ctx
, isl_id
*,
1014 dim
->n_in
+ dim
->n_out
);
1017 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
);
1018 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->n_in
);
1022 dim
->n_in
= dim
->n_out
;
1026 dim
= set_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
);
1027 dim
= set_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ dim
->n_out
);
1034 isl_space_free(dim
);
1038 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*dim
,
1039 enum isl_dim_type type
, unsigned first
, unsigned num
)
1047 return isl_space_reset(dim
, type
);
1049 if (!valid_dim_type(type
))
1050 isl_die(dim
->ctx
, isl_error_invalid
,
1051 "cannot drop dimensions of specified type", goto error
);
1053 isl_assert(dim
->ctx
, first
+ num
<= n(dim
, type
), goto error
);
1054 dim
= isl_space_cow(dim
);
1058 dim
= extend_ids(dim
);
1061 for (i
= 0; i
< num
; ++i
)
1062 isl_id_free(get_id(dim
, type
, first
+ i
));
1063 for (i
= first
+num
; i
< n(dim
, type
); ++i
)
1064 set_id(dim
, type
, i
- num
, get_id(dim
, type
, i
));
1067 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
,
1068 dim
->ids
+ offset(dim
, isl_dim_in
) - num
);
1070 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
,
1071 dim
->ids
+ offset(dim
, isl_dim_out
) - num
);
1078 case isl_dim_param
: dim
->nparam
-= num
; break;
1079 case isl_dim_in
: dim
->n_in
-= num
; break;
1080 case isl_dim_out
: dim
->n_out
-= num
; break;
1083 dim
= isl_space_reset(dim
, type
);
1084 if (type
== isl_dim_param
) {
1085 if (dim
&& dim
->nested
[0] &&
1086 !(dim
->nested
[0] = isl_space_drop_dims(dim
->nested
[0],
1087 isl_dim_param
, first
, num
)))
1089 if (dim
&& dim
->nested
[1] &&
1090 !(dim
->nested
[1] = isl_space_drop_dims(dim
->nested
[1],
1091 isl_dim_param
, first
, num
)))
1096 isl_space_free(dim
);
1100 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*dim
,
1101 unsigned first
, unsigned n
)
1105 return isl_space_drop_dims(dim
, isl_dim_in
, first
, n
);
1108 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*dim
,
1109 unsigned first
, unsigned n
)
1113 return isl_space_drop_dims(dim
, isl_dim_out
, first
, n
);
1116 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*dim
)
1120 dim
= isl_space_drop_outputs(dim
, 0, dim
->n_out
);
1121 return isl_space_reverse(dim
);
1124 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*dim
)
1126 return isl_space_reverse(dim
);
1129 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*dim
)
1133 return isl_space_drop_inputs(dim
, 0, dim
->n_in
);
1136 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*dim
)
1141 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
1143 space
= isl_space_drop_dims(space
,
1144 isl_dim_in
, 0, isl_space_dim(space
, isl_dim_in
));
1145 space
= isl_space_drop_dims(space
,
1146 isl_dim_out
, 0, isl_space_dim(space
, isl_dim_out
));
1150 __isl_give isl_space
*isl_space_as_set_space(__isl_take isl_space
*dim
)
1152 dim
= isl_space_cow(dim
);
1156 dim
->n_out
+= dim
->n_in
;
1158 dim
= isl_space_reset(dim
, isl_dim_in
);
1159 dim
= isl_space_reset(dim
, isl_dim_out
);
1164 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*dim
,
1172 dim
->nparam
== 0 && dim
->n_in
== 0 && dim
->n_id
== 0)
1173 return isl_space_reset(isl_space_reset(dim
, isl_dim_in
), isl_dim_out
);
1174 dim
= isl_space_cow(dim
);
1177 dim
->n_out
+= dim
->nparam
+ dim
->n_in
+ n_div
;
1181 for (i
= 0; i
< dim
->n_id
; ++i
)
1182 isl_id_free(get_id(dim
, isl_dim_out
, i
));
1184 dim
= isl_space_reset(dim
, isl_dim_in
);
1185 dim
= isl_space_reset(dim
, isl_dim_out
);
1190 int isl_space_is_equal(__isl_keep isl_space
*dim1
, __isl_keep isl_space
*dim2
)
1196 return match(dim1
, isl_dim_param
, dim2
, isl_dim_param
) &&
1197 isl_space_tuple_match(dim1
, isl_dim_in
, dim2
, isl_dim_in
) &&
1198 isl_space_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_out
);
1201 int isl_space_compatible(__isl_keep isl_space
*dim1
,
1202 __isl_keep isl_space
*dim2
)
1204 return dim1
->nparam
== dim2
->nparam
&&
1205 dim1
->n_in
+ dim1
->n_out
== dim2
->n_in
+ dim2
->n_out
;
1208 static uint32_t isl_hash_dim(uint32_t hash
, __isl_keep isl_space
*dim
)
1216 hash
= isl_hash_builtin(hash
, dim
->nparam
);
1217 hash
= isl_hash_builtin(hash
, dim
->n_in
);
1218 hash
= isl_hash_builtin(hash
, dim
->n_out
);
1220 for (i
= 0; i
< dim
->nparam
; ++i
) {
1221 id
= get_id(dim
, isl_dim_param
, i
);
1222 hash
= isl_hash_id(hash
, id
);
1225 id
= tuple_id(dim
, isl_dim_in
);
1226 hash
= isl_hash_id(hash
, id
);
1227 id
= tuple_id(dim
, isl_dim_out
);
1228 hash
= isl_hash_id(hash
, id
);
1230 hash
= isl_hash_dim(hash
, dim
->nested
[0]);
1231 hash
= isl_hash_dim(hash
, dim
->nested
[1]);
1236 uint32_t isl_space_get_hash(__isl_keep isl_space
*dim
)
1243 hash
= isl_hash_init();
1244 hash
= isl_hash_dim(hash
, dim
);
1249 int isl_space_is_wrapping(__isl_keep isl_space
*dim
)
1254 if (dim
->n_in
!= 0 || dim
->tuple_id
[0] || dim
->nested
[0])
1257 return dim
->nested
[1] != NULL
;
1260 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*dim
)
1267 wrap
= isl_space_alloc(dim
->ctx
, dim
->nparam
, 0, dim
->n_in
+ dim
->n_out
);
1269 wrap
= copy_ids(wrap
, isl_dim_param
, 0, dim
, isl_dim_param
);
1270 wrap
= copy_ids(wrap
, isl_dim_set
, 0, dim
, isl_dim_in
);
1271 wrap
= copy_ids(wrap
, isl_dim_set
, dim
->n_in
, dim
, isl_dim_out
);
1276 wrap
->nested
[1] = dim
;
1280 isl_space_free(dim
);
1284 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*dim
)
1291 if (!isl_space_is_wrapping(dim
))
1292 isl_die(dim
->ctx
, isl_error_invalid
, "not a wrapping dim",
1295 unwrap
= isl_space_copy(dim
->nested
[1]);
1296 isl_space_free(dim
);
1300 isl_space_free(dim
);
1304 int isl_space_is_named_or_nested(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
1306 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
1310 if (dim
->tuple_id
[type
- isl_dim_in
])
1312 if (dim
->nested
[type
- isl_dim_in
])
1317 int isl_space_may_be_set(__isl_keep isl_space
*dim
)
1321 if (isl_space_dim(dim
, isl_dim_in
) != 0)
1323 if (isl_space_is_named_or_nested(dim
, isl_dim_in
))
1328 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*dim
,
1329 enum isl_dim_type type
)
1331 if (!isl_space_is_named_or_nested(dim
, type
))
1334 dim
= isl_space_cow(dim
);
1338 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
1339 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
1340 isl_space_free(dim
->nested
[type
- isl_dim_in
]);
1341 dim
->nested
[type
- isl_dim_in
] = NULL
;
1346 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*dim
)
1350 if (!dim
->nested
[0] && !dim
->nested
[1])
1354 dim
= isl_space_reset(dim
, isl_dim_in
);
1355 if (dim
&& dim
->nested
[1])
1356 dim
= isl_space_reset(dim
, isl_dim_out
);
1361 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*dim
)
1365 if (!dim
->nested
[0])
1368 return isl_space_reset(dim
, isl_dim_in
);
1371 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*dim
)
1375 if (!dim
->nested
[1])
1378 return isl_space_reset(dim
, isl_dim_out
);
1381 /* Replace the dimensions of the given type of dst by those of src.
1383 __isl_give isl_space
*isl_space_replace(__isl_take isl_space
*dst
,
1384 enum isl_dim_type type
, __isl_keep isl_space
*src
)
1386 dst
= isl_space_cow(dst
);
1391 dst
= isl_space_drop_dims(dst
, type
, 0, isl_space_dim(dst
, type
));
1392 dst
= isl_space_add_dims(dst
, type
, isl_space_dim(src
, type
));
1393 dst
= copy_ids(dst
, type
, 0, src
, type
);
1395 if (dst
&& type
== isl_dim_param
) {
1397 for (i
= 0; i
<= 1; ++i
) {
1398 if (!dst
->nested
[i
])
1400 dst
->nested
[i
] = isl_space_replace(dst
->nested
[i
],
1402 if (!dst
->nested
[i
])
1409 isl_space_free(dst
);
1413 /* Given a dimension specification "dim" of a set, create a dimension
1414 * specification for the lift of the set. In particular, the result
1415 * is of the form [dim -> local[..]], with n_local variables in the
1416 * range of the wrapped map.
1418 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*dim
, unsigned n_local
)
1420 isl_space
*local_dim
;
1425 local_dim
= isl_space_dup(dim
);
1426 local_dim
= isl_space_drop_dims(local_dim
, isl_dim_set
, 0, dim
->n_out
);
1427 local_dim
= isl_space_add_dims(local_dim
, isl_dim_set
, n_local
);
1428 local_dim
= isl_space_set_tuple_name(local_dim
, isl_dim_set
, "local");
1429 dim
= isl_space_join(isl_space_from_domain(dim
),
1430 isl_space_from_range(local_dim
));
1431 dim
= isl_space_wrap(dim
);
1432 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, "lifted");
1437 int isl_space_can_zip(__isl_keep isl_space
*dim
)
1442 return dim
->nested
[0] && dim
->nested
[1];
1445 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*dim
)
1447 isl_space
*dom
, *ran
;
1448 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
1450 if (!isl_space_can_zip(dim
))
1451 isl_die(dim
->ctx
, isl_error_invalid
, "dim cannot be zipped",
1456 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(dim
)));
1457 ran
= isl_space_unwrap(isl_space_range(dim
));
1458 dom_dom
= isl_space_domain(isl_space_copy(dom
));
1459 dom_ran
= isl_space_range(dom
);
1460 ran_dom
= isl_space_domain(isl_space_copy(ran
));
1461 ran_ran
= isl_space_range(ran
);
1462 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
1463 isl_space_from_range(ran_dom
));
1464 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
1465 isl_space_from_range(ran_ran
));
1466 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
1467 isl_space_from_range(isl_space_wrap(ran
)));
1469 isl_space_free(dim
);
1473 int isl_space_has_named_params(__isl_keep isl_space
*dim
)
1480 if (dim
->nparam
== 0)
1482 off
= isl_space_offset(dim
, isl_dim_param
);
1483 if (off
+ dim
->nparam
> dim
->n_id
)
1485 for (i
= 0; i
< dim
->nparam
; ++i
)
1486 if (!dim
->ids
[off
+ i
])
1491 /* Align the initial parameters of dim1 to match the order in dim2.
1493 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*dim1
,
1494 __isl_take isl_space
*dim2
)
1496 isl_reordering
*exp
;
1498 if (!isl_space_has_named_params(dim1
) || !isl_space_has_named_params(dim2
))
1499 isl_die(isl_space_get_ctx(dim1
), isl_error_invalid
,
1500 "parameter alignment requires named parameters",
1503 dim2
= isl_space_params(dim2
);
1504 exp
= isl_parameter_alignment_reordering(dim1
, dim2
);
1505 exp
= isl_reordering_extend_space(exp
, dim1
);
1506 isl_space_free(dim2
);
1509 dim1
= isl_space_copy(exp
->dim
);
1510 isl_reordering_free(exp
);
1513 isl_space_free(dim1
);
1514 isl_space_free(dim2
);