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 /* Create a space for a parameter domain.
59 __isl_give isl_space
*isl_space_params_alloc(isl_ctx
*ctx
, unsigned nparam
)
62 space
= isl_space_alloc(ctx
, nparam
, 0, 0);
66 static unsigned global_pos(__isl_keep isl_space
*dim
,
67 enum isl_dim_type type
, unsigned pos
)
69 struct isl_ctx
*ctx
= dim
->ctx
;
73 isl_assert(ctx
, pos
< dim
->nparam
,
74 return isl_space_dim(dim
, isl_dim_all
));
77 isl_assert(ctx
, pos
< dim
->n_in
,
78 return isl_space_dim(dim
, isl_dim_all
));
79 return pos
+ dim
->nparam
;
81 isl_assert(ctx
, pos
< dim
->n_out
,
82 return isl_space_dim(dim
, isl_dim_all
));
83 return pos
+ dim
->nparam
+ dim
->n_in
;
85 isl_assert(ctx
, 0, return isl_space_dim(dim
, isl_dim_all
));
87 return isl_space_dim(dim
, isl_dim_all
);
90 /* Extend length of ids array to the total number of dimensions.
92 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*dim
)
97 if (isl_space_dim(dim
, isl_dim_all
) <= dim
->n_id
)
101 dim
->ids
= isl_calloc_array(dim
->ctx
,
102 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
106 ids
= isl_realloc_array(dim
->ctx
, dim
->ids
,
107 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
111 for (i
= dim
->n_id
; i
< isl_space_dim(dim
, isl_dim_all
); ++i
)
115 dim
->n_id
= isl_space_dim(dim
, isl_dim_all
);
123 static __isl_give isl_space
*set_id(__isl_take isl_space
*dim
,
124 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
126 dim
= isl_space_cow(dim
);
131 pos
= global_pos(dim
, type
, pos
);
132 if (pos
== isl_space_dim(dim
, isl_dim_all
))
135 if (pos
>= dim
->n_id
) {
138 dim
= extend_ids(dim
);
152 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*dim
,
153 enum isl_dim_type type
, unsigned pos
)
158 pos
= global_pos(dim
, type
, pos
);
159 if (pos
== isl_space_dim(dim
, isl_dim_all
))
161 if (pos
>= dim
->n_id
)
163 return dim
->ids
[pos
];
166 static unsigned offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
169 case isl_dim_param
: return 0;
170 case isl_dim_in
: return dim
->nparam
;
171 case isl_dim_out
: return dim
->nparam
+ dim
->n_in
;
176 static unsigned n(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
179 case isl_dim_param
: return dim
->nparam
;
180 case isl_dim_in
: return dim
->n_in
;
181 case isl_dim_out
: return dim
->n_out
;
182 case isl_dim_all
: return dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
187 unsigned isl_space_dim(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
194 unsigned isl_space_offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
198 return offset(dim
, type
);
201 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
202 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
203 enum isl_dim_type src_type
)
211 for (i
= 0; i
< n(src
, src_type
); ++i
) {
212 id
= get_id(src
, src_type
, i
);
215 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
222 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*dim
)
227 dup
= isl_space_alloc(dim
->ctx
, dim
->nparam
, dim
->n_in
, dim
->n_out
);
228 if (dim
->tuple_id
[0] &&
229 !(dup
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[0])))
231 if (dim
->tuple_id
[1] &&
232 !(dup
->tuple_id
[1] = isl_id_copy(dim
->tuple_id
[1])))
234 if (dim
->nested
[0] && !(dup
->nested
[0] = isl_space_copy(dim
->nested
[0])))
236 if (dim
->nested
[1] && !(dup
->nested
[1] = isl_space_copy(dim
->nested
[1])))
240 dup
= copy_ids(dup
, isl_dim_param
, 0, dim
, isl_dim_param
);
241 dup
= copy_ids(dup
, isl_dim_in
, 0, dim
, isl_dim_in
);
242 dup
= copy_ids(dup
, isl_dim_out
, 0, dim
, isl_dim_out
);
249 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*dim
)
257 return isl_space_dup(dim
);
260 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*dim
)
269 void isl_space_free(__isl_take isl_space
*dim
)
279 isl_id_free(dim
->tuple_id
[0]);
280 isl_id_free(dim
->tuple_id
[1]);
282 isl_space_free(dim
->nested
[0]);
283 isl_space_free(dim
->nested
[1]);
285 for (i
= 0; i
< dim
->n_id
; ++i
)
286 isl_id_free(dim
->ids
[i
]);
288 isl_ctx_deref(dim
->ctx
);
293 static int name_ok(isl_ctx
*ctx
, const char *s
)
298 dummy
= strtol(s
, &p
, 0);
300 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
306 int isl_space_has_tuple_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
310 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
311 isl_die(dim
->ctx
, isl_error_invalid
,
312 "only input, output and set tuples can have ids",
314 return dim
->tuple_id
[type
- isl_dim_in
] != NULL
;
317 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*dim
,
318 enum isl_dim_type type
)
322 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
323 isl_die(dim
->ctx
, isl_error_invalid
,
324 "only input, output and set tuples can have ids",
326 if (!dim
->tuple_id
[type
- isl_dim_in
])
327 isl_die(dim
->ctx
, isl_error_invalid
,
328 "tuple has no id", return NULL
);
329 return isl_id_copy(dim
->tuple_id
[type
- isl_dim_in
]);
332 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*dim
,
333 enum isl_dim_type type
, __isl_take isl_id
*id
)
335 dim
= isl_space_cow(dim
);
338 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
339 isl_die(dim
->ctx
, isl_error_invalid
,
340 "only input, output and set tuples can have names",
343 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
344 dim
->tuple_id
[type
- isl_dim_in
] = id
;
353 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*dim
,
354 enum isl_dim_type type
)
356 dim
= isl_space_cow(dim
);
359 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
360 isl_die(dim
->ctx
, isl_error_invalid
,
361 "only input, output and set tuples can have names",
364 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
365 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
373 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*dim
,
374 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
376 dim
= isl_space_cow(dim
);
379 isl_id_free(get_id(dim
, type
, pos
));
380 return set_id(dim
, type
, pos
, id
);
387 int isl_space_has_dim_id(__isl_keep isl_space
*dim
,
388 enum isl_dim_type type
, unsigned pos
)
392 return get_id(dim
, type
, pos
) != NULL
;
395 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*dim
,
396 enum isl_dim_type type
, unsigned pos
)
400 if (!get_id(dim
, type
, pos
))
401 isl_die(dim
->ctx
, isl_error_invalid
,
402 "dim has no id", return NULL
);
403 return isl_id_copy(get_id(dim
, type
, pos
));
406 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*dim
,
407 enum isl_dim_type type
, const char *s
)
415 return isl_space_reset_tuple_id(dim
, type
);
417 if (!name_ok(dim
->ctx
, s
))
420 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
421 return isl_space_set_tuple_id(dim
, type
, id
);
427 const char *isl_space_get_tuple_name(__isl_keep isl_space
*dim
,
428 enum isl_dim_type type
)
433 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
435 id
= dim
->tuple_id
[type
- isl_dim_in
];
436 return id
? id
->name
: NULL
;
439 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*dim
,
440 enum isl_dim_type type
, unsigned pos
,
447 if (!name_ok(dim
->ctx
, s
))
449 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
450 return isl_space_set_dim_id(dim
, type
, pos
, id
);
456 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*dim
,
457 enum isl_dim_type type
, unsigned pos
)
459 isl_id
*id
= get_id(dim
, type
, pos
);
460 return id
? id
->name
: NULL
;
463 int isl_space_find_dim_by_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
464 __isl_keep isl_id
*id
)
473 offset
= isl_space_offset(dim
, type
);
474 n
= isl_space_dim(dim
, type
);
475 for (i
= 0; i
< n
&& offset
+ i
< dim
->n_id
; ++i
)
476 if (dim
->ids
[offset
+ i
] == id
)
482 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*dim
,
483 enum isl_dim_type type
)
487 if (type
== isl_dim_in
)
488 return dim
->tuple_id
[0];
489 if (type
== isl_dim_out
)
490 return dim
->tuple_id
[1];
494 static __isl_keep isl_space
*nested(__isl_keep isl_space
*dim
,
495 enum isl_dim_type type
)
499 if (type
== isl_dim_in
)
500 return dim
->nested
[0];
501 if (type
== isl_dim_out
)
502 return dim
->nested
[1];
506 int isl_space_tuple_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
507 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
510 isl_space
*nested1
, *nested2
;
515 if (dim1
== dim2
&& dim1_type
== dim2_type
)
518 if (n(dim1
, dim1_type
) != n(dim2
, dim2_type
))
520 id1
= tuple_id(dim1
, dim1_type
);
521 id2
= tuple_id(dim2
, dim2_type
);
524 if (id1
&& id1
!= id2
)
526 nested1
= nested(dim1
, dim1_type
);
527 nested2
= nested(dim2
, dim2_type
);
528 if (!nested1
^ !nested2
)
530 if (nested1
&& !isl_space_is_equal(nested1
, nested2
))
535 static int match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
536 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
540 if (dim1
== dim2
&& dim1_type
== dim2_type
)
543 if (!isl_space_tuple_match(dim1
, dim1_type
, dim2
, dim2_type
))
546 if (!dim1
->ids
&& !dim2
->ids
)
549 for (i
= 0; i
< n(dim1
, dim1_type
); ++i
) {
550 if (get_id(dim1
, dim1_type
, i
) != get_id(dim2
, dim2_type
, i
))
556 int isl_space_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
557 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
562 return match(dim1
, dim1_type
, dim2
, dim2_type
);
565 static void get_ids(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
566 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
570 for (i
= 0; i
< n
; ++i
)
571 ids
[i
] = get_id(dim
, type
, first
+ i
);
574 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*dim
,
575 unsigned nparam
, unsigned n_in
, unsigned n_out
)
581 if (dim
->nparam
== nparam
&& dim
->n_in
== n_in
&& dim
->n_out
== n_out
)
584 isl_assert(dim
->ctx
, dim
->nparam
<= nparam
, goto error
);
585 isl_assert(dim
->ctx
, dim
->n_in
<= n_in
, goto error
);
586 isl_assert(dim
->ctx
, dim
->n_out
<= n_out
, goto error
);
588 dim
= isl_space_cow(dim
);
591 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
592 nparam
+ n_in
+ n_out
);
595 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
596 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ nparam
);
597 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ nparam
+ n_in
);
600 dim
->n_id
= nparam
+ n_in
+ n_out
;
602 dim
->nparam
= nparam
;
613 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*dim
,
614 enum isl_dim_type type
, unsigned n
)
618 dim
= isl_space_reset(dim
, type
);
621 dim
= isl_space_extend(dim
,
622 dim
->nparam
+ n
, dim
->n_in
, dim
->n_out
);
623 if (dim
&& dim
->nested
[0] &&
624 !(dim
->nested
[0] = isl_space_add_dims(dim
->nested
[0],
627 if (dim
&& dim
->nested
[1] &&
628 !(dim
->nested
[1] = isl_space_add_dims(dim
->nested
[1],
633 return isl_space_extend(dim
,
634 dim
->nparam
, dim
->n_in
+ n
, dim
->n_out
);
636 return isl_space_extend(dim
,
637 dim
->nparam
, dim
->n_in
, dim
->n_out
+ n
);
639 isl_die(dim
->ctx
, isl_error_invalid
,
640 "cannot add dimensions of specified type", goto error
);
647 static int valid_dim_type(enum isl_dim_type type
)
659 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*dim
,
660 enum isl_dim_type type
, unsigned pos
, unsigned n
)
667 return isl_space_reset(dim
, type
);
669 if (!valid_dim_type(type
))
670 isl_die(dim
->ctx
, isl_error_invalid
,
671 "cannot insert dimensions of specified type",
674 isl_assert(dim
->ctx
, pos
<= isl_space_dim(dim
, type
), goto error
);
676 dim
= isl_space_cow(dim
);
684 int *size
= s
- isl_dim_param
;
685 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
686 dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
);
690 size
[isl_dim_param
] = dim
->nparam
;
691 size
[isl_dim_in
] = dim
->n_in
;
692 size
[isl_dim_out
] = dim
->n_out
;
693 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
695 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
698 get_ids(dim
, t
, 0, pos
, ids
+ off
);
700 get_ids(dim
, t
, pos
, size
[t
] - pos
, ids
+ off
);
701 off
+= size
[t
] - pos
;
706 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
;
709 case isl_dim_param
: dim
->nparam
+= n
; break;
710 case isl_dim_in
: dim
->n_in
+= n
; break;
711 case isl_dim_out
: dim
->n_out
+= n
; break;
714 dim
= isl_space_reset(dim
, type
);
722 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*dim
,
723 enum isl_dim_type dst_type
, unsigned dst_pos
,
724 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
733 isl_assert(dim
->ctx
, src_pos
+ n
<= isl_space_dim(dim
, src_type
),
736 if (dst_type
== src_type
&& dst_pos
== src_pos
)
739 isl_assert(dim
->ctx
, dst_type
!= src_type
, goto error
);
741 dim
= isl_space_reset(dim
, src_type
);
742 dim
= isl_space_reset(dim
, dst_type
);
744 dim
= isl_space_cow(dim
);
753 int *size
= s
- isl_dim_param
;
754 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
755 dim
->nparam
+ dim
->n_in
+ dim
->n_out
);
759 size
[isl_dim_param
] = dim
->nparam
;
760 size
[isl_dim_in
] = dim
->n_in
;
761 size
[isl_dim_out
] = dim
->n_out
;
762 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
764 get_ids(dim
, t
, 0, dst_pos
, ids
+ off
);
766 get_ids(dim
, src_type
, src_pos
, n
, ids
+ off
);
768 get_ids(dim
, t
, dst_pos
, size
[t
] - dst_pos
,
770 off
+= size
[t
] - dst_pos
;
771 } else if (t
== src_type
) {
772 get_ids(dim
, t
, 0, src_pos
, ids
+ off
);
774 get_ids(dim
, t
, src_pos
+ n
,
775 size
[t
] - src_pos
- n
, ids
+ off
);
776 off
+= size
[t
] - src_pos
- n
;
778 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
784 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
788 case isl_dim_param
: dim
->nparam
+= n
; break;
789 case isl_dim_in
: dim
->n_in
+= n
; break;
790 case isl_dim_out
: dim
->n_out
+= n
; break;
795 case isl_dim_param
: dim
->nparam
-= n
; break;
796 case isl_dim_in
: dim
->n_in
-= n
; break;
797 case isl_dim_out
: dim
->n_out
-= n
; break;
801 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
804 for (i
= 0; i
< 2; ++i
) {
807 dim
->nested
[i
] = isl_space_replace(dim
->nested
[i
],
819 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
820 __isl_take isl_space
*right
)
827 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
829 isl_assert(left
->ctx
,
830 isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_in
),
833 dim
= isl_space_alloc(left
->ctx
, left
->nparam
, left
->n_in
, right
->n_out
);
837 dim
= copy_ids(dim
, isl_dim_param
, 0, left
, isl_dim_param
);
838 dim
= copy_ids(dim
, isl_dim_in
, 0, left
, isl_dim_in
);
839 dim
= copy_ids(dim
, isl_dim_out
, 0, right
, isl_dim_out
);
841 if (dim
&& left
->tuple_id
[0] &&
842 !(dim
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
844 if (dim
&& right
->tuple_id
[1] &&
845 !(dim
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
847 if (dim
&& left
->nested
[0] &&
848 !(dim
->nested
[0] = isl_space_copy(left
->nested
[0])))
850 if (dim
&& right
->nested
[1] &&
851 !(dim
->nested
[1] = isl_space_copy(right
->nested
[1])))
854 isl_space_free(left
);
855 isl_space_free(right
);
859 isl_space_free(left
);
860 isl_space_free(right
);
864 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
865 __isl_take isl_space
*right
)
867 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
872 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
875 dom1
= isl_space_domain(isl_space_copy(left
));
876 dom2
= isl_space_domain(isl_space_copy(right
));
877 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
879 dom1
= isl_space_range(left
);
880 dom2
= isl_space_range(right
);
881 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
883 return isl_space_join(isl_space_reverse(nest1
), nest2
);
885 isl_space_free(left
);
886 isl_space_free(right
);
890 /* Given two spaces { A -> C } and { B -> C }, construct the space
893 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
894 __isl_take isl_space
*right
)
896 isl_space
*ran
, *dom1
, *dom2
, *nest
;
901 if (!match(left
, isl_dim_param
, right
, isl_dim_param
))
902 isl_die(left
->ctx
, isl_error_invalid
,
903 "parameters need to match", goto error
);
904 if (!isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_out
))
905 isl_die(left
->ctx
, isl_error_invalid
,
906 "ranges need to match", goto error
);
908 ran
= isl_space_range(isl_space_copy(left
));
910 dom1
= isl_space_domain(left
);
911 dom2
= isl_space_domain(right
);
912 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
914 return isl_space_join(isl_space_reverse(nest
), ran
);
916 isl_space_free(left
);
917 isl_space_free(right
);
921 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
922 __isl_take isl_space
*right
)
924 isl_space
*dom
, *ran1
, *ran2
, *nest
;
929 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
931 if (!isl_space_tuple_match(left
, isl_dim_in
, right
, isl_dim_in
))
932 isl_die(left
->ctx
, isl_error_invalid
,
933 "domains need to match", goto error
);
935 dom
= isl_space_domain(isl_space_copy(left
));
937 ran1
= isl_space_range(left
);
938 ran2
= isl_space_range(right
);
939 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
941 return isl_space_join(isl_space_reverse(dom
), nest
);
943 isl_space_free(left
);
944 isl_space_free(right
);
948 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*dim
)
954 isl_assert(dim
->ctx
, dim
->n_in
== 0, goto error
);
955 if (dim
->n_out
== 0 && !isl_space_is_named_or_nested(dim
, isl_dim_out
))
957 dim
= isl_space_cow(dim
);
961 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
962 dim
->nparam
+ dim
->n_out
+ dim
->n_out
);
965 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
966 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->nparam
);
968 dim
->n_in
= dim
->n_out
;
972 dim
->n_id
= dim
->nparam
+ dim
->n_out
+ dim
->n_out
;
973 dim
= copy_ids(dim
, isl_dim_out
, 0, dim
, isl_dim_in
);
975 isl_id_free(dim
->tuple_id
[0]);
976 dim
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[1]);
977 isl_space_free(dim
->nested
[0]);
978 dim
->nested
[0] = isl_space_copy(dim
->nested
[1]);
985 static __isl_give isl_space
*set_ids(__isl_take isl_space
*dim
,
986 enum isl_dim_type type
,
987 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
991 for (i
= 0; i
< n
; ++i
)
992 dim
= set_id(dim
, type
, first
+ i
, ids
[i
]);
997 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*dim
)
1001 isl_id
**ids
= NULL
;
1006 if (match(dim
, isl_dim_in
, dim
, isl_dim_out
))
1009 dim
= isl_space_cow(dim
);
1013 id
= dim
->tuple_id
[0];
1014 dim
->tuple_id
[0] = dim
->tuple_id
[1];
1015 dim
->tuple_id
[1] = id
;
1017 nested
= dim
->nested
[0];
1018 dim
->nested
[0] = dim
->nested
[1];
1019 dim
->nested
[1] = nested
;
1022 ids
= isl_alloc_array(dim
->ctx
, isl_id
*,
1023 dim
->n_in
+ dim
->n_out
);
1026 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
);
1027 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->n_in
);
1031 dim
->n_in
= dim
->n_out
;
1035 dim
= set_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
);
1036 dim
= set_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ dim
->n_out
);
1043 isl_space_free(dim
);
1047 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*dim
,
1048 enum isl_dim_type type
, unsigned first
, unsigned num
)
1056 return isl_space_reset(dim
, type
);
1058 if (!valid_dim_type(type
))
1059 isl_die(dim
->ctx
, isl_error_invalid
,
1060 "cannot drop dimensions of specified type", goto error
);
1062 isl_assert(dim
->ctx
, first
+ num
<= n(dim
, type
), goto error
);
1063 dim
= isl_space_cow(dim
);
1067 dim
= extend_ids(dim
);
1070 for (i
= 0; i
< num
; ++i
)
1071 isl_id_free(get_id(dim
, type
, first
+ i
));
1072 for (i
= first
+num
; i
< n(dim
, type
); ++i
)
1073 set_id(dim
, type
, i
- num
, get_id(dim
, type
, i
));
1076 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
,
1077 dim
->ids
+ offset(dim
, isl_dim_in
) - num
);
1079 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
,
1080 dim
->ids
+ offset(dim
, isl_dim_out
) - num
);
1087 case isl_dim_param
: dim
->nparam
-= num
; break;
1088 case isl_dim_in
: dim
->n_in
-= num
; break;
1089 case isl_dim_out
: dim
->n_out
-= num
; break;
1092 dim
= isl_space_reset(dim
, type
);
1093 if (type
== isl_dim_param
) {
1094 if (dim
&& dim
->nested
[0] &&
1095 !(dim
->nested
[0] = isl_space_drop_dims(dim
->nested
[0],
1096 isl_dim_param
, first
, num
)))
1098 if (dim
&& dim
->nested
[1] &&
1099 !(dim
->nested
[1] = isl_space_drop_dims(dim
->nested
[1],
1100 isl_dim_param
, first
, num
)))
1105 isl_space_free(dim
);
1109 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*dim
,
1110 unsigned first
, unsigned n
)
1114 return isl_space_drop_dims(dim
, isl_dim_in
, first
, n
);
1117 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*dim
,
1118 unsigned first
, unsigned n
)
1122 return isl_space_drop_dims(dim
, isl_dim_out
, first
, n
);
1125 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*dim
)
1129 dim
= isl_space_drop_outputs(dim
, 0, dim
->n_out
);
1130 return isl_space_reverse(dim
);
1133 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*dim
)
1135 return isl_space_reverse(dim
);
1138 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*dim
)
1142 return isl_space_drop_inputs(dim
, 0, dim
->n_in
);
1145 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*dim
)
1150 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
1152 space
= isl_space_drop_dims(space
,
1153 isl_dim_in
, 0, isl_space_dim(space
, isl_dim_in
));
1154 space
= isl_space_drop_dims(space
,
1155 isl_dim_out
, 0, isl_space_dim(space
, isl_dim_out
));
1159 __isl_give isl_space
*isl_space_as_set_space(__isl_take isl_space
*dim
)
1161 dim
= isl_space_cow(dim
);
1165 dim
->n_out
+= dim
->n_in
;
1167 dim
= isl_space_reset(dim
, isl_dim_in
);
1168 dim
= isl_space_reset(dim
, isl_dim_out
);
1173 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*dim
,
1181 dim
->nparam
== 0 && dim
->n_in
== 0 && dim
->n_id
== 0)
1182 return isl_space_reset(isl_space_reset(dim
, isl_dim_in
), isl_dim_out
);
1183 dim
= isl_space_cow(dim
);
1186 dim
->n_out
+= dim
->nparam
+ dim
->n_in
+ n_div
;
1190 for (i
= 0; i
< dim
->n_id
; ++i
)
1191 isl_id_free(get_id(dim
, isl_dim_out
, i
));
1193 dim
= isl_space_reset(dim
, isl_dim_in
);
1194 dim
= isl_space_reset(dim
, isl_dim_out
);
1199 int isl_space_is_equal(__isl_keep isl_space
*dim1
, __isl_keep isl_space
*dim2
)
1205 return match(dim1
, isl_dim_param
, dim2
, isl_dim_param
) &&
1206 isl_space_tuple_match(dim1
, isl_dim_in
, dim2
, isl_dim_in
) &&
1207 isl_space_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_out
);
1210 int isl_space_compatible(__isl_keep isl_space
*dim1
,
1211 __isl_keep isl_space
*dim2
)
1213 return dim1
->nparam
== dim2
->nparam
&&
1214 dim1
->n_in
+ dim1
->n_out
== dim2
->n_in
+ dim2
->n_out
;
1217 static uint32_t isl_hash_dim(uint32_t hash
, __isl_keep isl_space
*dim
)
1225 hash
= isl_hash_builtin(hash
, dim
->nparam
);
1226 hash
= isl_hash_builtin(hash
, dim
->n_in
);
1227 hash
= isl_hash_builtin(hash
, dim
->n_out
);
1229 for (i
= 0; i
< dim
->nparam
; ++i
) {
1230 id
= get_id(dim
, isl_dim_param
, i
);
1231 hash
= isl_hash_id(hash
, id
);
1234 id
= tuple_id(dim
, isl_dim_in
);
1235 hash
= isl_hash_id(hash
, id
);
1236 id
= tuple_id(dim
, isl_dim_out
);
1237 hash
= isl_hash_id(hash
, id
);
1239 hash
= isl_hash_dim(hash
, dim
->nested
[0]);
1240 hash
= isl_hash_dim(hash
, dim
->nested
[1]);
1245 uint32_t isl_space_get_hash(__isl_keep isl_space
*dim
)
1252 hash
= isl_hash_init();
1253 hash
= isl_hash_dim(hash
, dim
);
1258 int isl_space_is_wrapping(__isl_keep isl_space
*dim
)
1263 if (dim
->n_in
!= 0 || dim
->tuple_id
[0] || dim
->nested
[0])
1266 return dim
->nested
[1] != NULL
;
1269 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*dim
)
1276 wrap
= isl_space_set_alloc(dim
->ctx
,
1277 dim
->nparam
, dim
->n_in
+ dim
->n_out
);
1279 wrap
= copy_ids(wrap
, isl_dim_param
, 0, dim
, isl_dim_param
);
1280 wrap
= copy_ids(wrap
, isl_dim_set
, 0, dim
, isl_dim_in
);
1281 wrap
= copy_ids(wrap
, isl_dim_set
, dim
->n_in
, dim
, isl_dim_out
);
1286 wrap
->nested
[1] = dim
;
1290 isl_space_free(dim
);
1294 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*dim
)
1301 if (!isl_space_is_wrapping(dim
))
1302 isl_die(dim
->ctx
, isl_error_invalid
, "not a wrapping dim",
1305 unwrap
= isl_space_copy(dim
->nested
[1]);
1306 isl_space_free(dim
);
1310 isl_space_free(dim
);
1314 int isl_space_is_named_or_nested(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
1316 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
1320 if (dim
->tuple_id
[type
- isl_dim_in
])
1322 if (dim
->nested
[type
- isl_dim_in
])
1327 int isl_space_may_be_set(__isl_keep isl_space
*dim
)
1331 if (isl_space_dim(dim
, isl_dim_in
) != 0)
1333 if (isl_space_is_named_or_nested(dim
, isl_dim_in
))
1338 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*dim
,
1339 enum isl_dim_type type
)
1341 if (!isl_space_is_named_or_nested(dim
, type
))
1344 dim
= isl_space_cow(dim
);
1348 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
1349 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
1350 isl_space_free(dim
->nested
[type
- isl_dim_in
]);
1351 dim
->nested
[type
- isl_dim_in
] = NULL
;
1356 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*dim
)
1360 if (!dim
->nested
[0] && !dim
->nested
[1])
1364 dim
= isl_space_reset(dim
, isl_dim_in
);
1365 if (dim
&& dim
->nested
[1])
1366 dim
= isl_space_reset(dim
, isl_dim_out
);
1371 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*dim
)
1375 if (!dim
->nested
[0])
1378 return isl_space_reset(dim
, isl_dim_in
);
1381 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*dim
)
1385 if (!dim
->nested
[1])
1388 return isl_space_reset(dim
, isl_dim_out
);
1391 /* Replace the dimensions of the given type of dst by those of src.
1393 __isl_give isl_space
*isl_space_replace(__isl_take isl_space
*dst
,
1394 enum isl_dim_type type
, __isl_keep isl_space
*src
)
1396 dst
= isl_space_cow(dst
);
1401 dst
= isl_space_drop_dims(dst
, type
, 0, isl_space_dim(dst
, type
));
1402 dst
= isl_space_add_dims(dst
, type
, isl_space_dim(src
, type
));
1403 dst
= copy_ids(dst
, type
, 0, src
, type
);
1405 if (dst
&& type
== isl_dim_param
) {
1407 for (i
= 0; i
<= 1; ++i
) {
1408 if (!dst
->nested
[i
])
1410 dst
->nested
[i
] = isl_space_replace(dst
->nested
[i
],
1412 if (!dst
->nested
[i
])
1419 isl_space_free(dst
);
1423 /* Given a dimension specification "dim" of a set, create a dimension
1424 * specification for the lift of the set. In particular, the result
1425 * is of the form [dim -> local[..]], with n_local variables in the
1426 * range of the wrapped map.
1428 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*dim
, unsigned n_local
)
1430 isl_space
*local_dim
;
1435 local_dim
= isl_space_dup(dim
);
1436 local_dim
= isl_space_drop_dims(local_dim
, isl_dim_set
, 0, dim
->n_out
);
1437 local_dim
= isl_space_add_dims(local_dim
, isl_dim_set
, n_local
);
1438 local_dim
= isl_space_set_tuple_name(local_dim
, isl_dim_set
, "local");
1439 dim
= isl_space_join(isl_space_from_domain(dim
),
1440 isl_space_from_range(local_dim
));
1441 dim
= isl_space_wrap(dim
);
1442 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, "lifted");
1447 int isl_space_can_zip(__isl_keep isl_space
*dim
)
1452 return dim
->nested
[0] && dim
->nested
[1];
1455 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*dim
)
1457 isl_space
*dom
, *ran
;
1458 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
1460 if (!isl_space_can_zip(dim
))
1461 isl_die(dim
->ctx
, isl_error_invalid
, "dim cannot be zipped",
1466 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(dim
)));
1467 ran
= isl_space_unwrap(isl_space_range(dim
));
1468 dom_dom
= isl_space_domain(isl_space_copy(dom
));
1469 dom_ran
= isl_space_range(dom
);
1470 ran_dom
= isl_space_domain(isl_space_copy(ran
));
1471 ran_ran
= isl_space_range(ran
);
1472 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
1473 isl_space_from_range(ran_dom
));
1474 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
1475 isl_space_from_range(ran_ran
));
1476 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
1477 isl_space_from_range(isl_space_wrap(ran
)));
1479 isl_space_free(dim
);
1483 int isl_space_has_named_params(__isl_keep isl_space
*dim
)
1490 if (dim
->nparam
== 0)
1492 off
= isl_space_offset(dim
, isl_dim_param
);
1493 if (off
+ dim
->nparam
> dim
->n_id
)
1495 for (i
= 0; i
< dim
->nparam
; ++i
)
1496 if (!dim
->ids
[off
+ i
])
1501 /* Align the initial parameters of dim1 to match the order in dim2.
1503 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*dim1
,
1504 __isl_take isl_space
*dim2
)
1506 isl_reordering
*exp
;
1508 if (!isl_space_has_named_params(dim1
) || !isl_space_has_named_params(dim2
))
1509 isl_die(isl_space_get_ctx(dim1
), isl_error_invalid
,
1510 "parameter alignment requires named parameters",
1513 dim2
= isl_space_params(dim2
);
1514 exp
= isl_parameter_alignment_reordering(dim1
, dim2
);
1515 exp
= isl_reordering_extend_space(exp
, dim1
);
1516 isl_space_free(dim2
);
1519 dim1
= isl_space_copy(exp
->dim
);
1520 isl_reordering_free(exp
);
1523 isl_space_free(dim1
);
1524 isl_space_free(dim2
);