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 /* Mark the space as being that of a set, by setting the domain tuple
54 static __isl_give isl_space
*mark_as_set(__isl_take isl_space
*space
)
56 space
= isl_space_cow(space
);
59 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
63 /* Is the space that of a set?
65 int isl_space_is_set(__isl_keep isl_space
*space
)
69 if (space
->n_in
!= 0 || space
->nested
[0])
71 if (space
->tuple_id
[0] != &isl_id_none
)
76 __isl_give isl_space
*isl_space_set_alloc(isl_ctx
*ctx
,
77 unsigned nparam
, unsigned dim
)
80 space
= isl_space_alloc(ctx
, nparam
, 0, dim
);
81 space
= mark_as_set(space
);
85 /* Mark the space as being that of a parameter domain, by setting
86 * both tuples to isl_id_none.
88 static __isl_give isl_space
*mark_as_params(isl_space
*space
)
92 space
= isl_space_set_tuple_id(space
, isl_dim_in
, &isl_id_none
);
93 space
= isl_space_set_tuple_id(space
, isl_dim_out
, &isl_id_none
);
97 /* Is the space that of a parameter domain?
99 int isl_space_is_params(__isl_keep isl_space
*space
)
103 if (space
->n_in
!= 0 || space
->nested
[0] ||
104 space
->n_out
!= 0 || space
->nested
[1])
106 if (space
->tuple_id
[0] != &isl_id_none
)
108 if (space
->tuple_id
[1] != &isl_id_none
)
113 /* Create a space for a parameter domain.
115 __isl_give isl_space
*isl_space_params_alloc(isl_ctx
*ctx
, unsigned nparam
)
118 space
= isl_space_alloc(ctx
, nparam
, 0, 0);
119 space
= mark_as_params(space
);
123 static unsigned global_pos(__isl_keep isl_space
*dim
,
124 enum isl_dim_type type
, unsigned pos
)
126 struct isl_ctx
*ctx
= dim
->ctx
;
130 isl_assert(ctx
, pos
< dim
->nparam
,
131 return isl_space_dim(dim
, isl_dim_all
));
134 isl_assert(ctx
, pos
< dim
->n_in
,
135 return isl_space_dim(dim
, isl_dim_all
));
136 return pos
+ dim
->nparam
;
138 isl_assert(ctx
, pos
< dim
->n_out
,
139 return isl_space_dim(dim
, isl_dim_all
));
140 return pos
+ dim
->nparam
+ dim
->n_in
;
142 isl_assert(ctx
, 0, return isl_space_dim(dim
, isl_dim_all
));
144 return isl_space_dim(dim
, isl_dim_all
);
147 /* Extend length of ids array to the total number of dimensions.
149 static __isl_give isl_space
*extend_ids(__isl_take isl_space
*dim
)
154 if (isl_space_dim(dim
, isl_dim_all
) <= dim
->n_id
)
158 dim
->ids
= isl_calloc_array(dim
->ctx
,
159 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
163 ids
= isl_realloc_array(dim
->ctx
, dim
->ids
,
164 isl_id
*, isl_space_dim(dim
, isl_dim_all
));
168 for (i
= dim
->n_id
; i
< isl_space_dim(dim
, isl_dim_all
); ++i
)
172 dim
->n_id
= isl_space_dim(dim
, isl_dim_all
);
180 static __isl_give isl_space
*set_id(__isl_take isl_space
*dim
,
181 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
183 dim
= isl_space_cow(dim
);
188 pos
= global_pos(dim
, type
, pos
);
189 if (pos
== isl_space_dim(dim
, isl_dim_all
))
192 if (pos
>= dim
->n_id
) {
195 dim
= extend_ids(dim
);
209 static __isl_keep isl_id
*get_id(__isl_keep isl_space
*dim
,
210 enum isl_dim_type type
, unsigned pos
)
215 pos
= global_pos(dim
, type
, pos
);
216 if (pos
== isl_space_dim(dim
, isl_dim_all
))
218 if (pos
>= dim
->n_id
)
220 return dim
->ids
[pos
];
223 static unsigned offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
226 case isl_dim_param
: return 0;
227 case isl_dim_in
: return dim
->nparam
;
228 case isl_dim_out
: return dim
->nparam
+ dim
->n_in
;
233 static unsigned n(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
236 case isl_dim_param
: return dim
->nparam
;
237 case isl_dim_in
: return dim
->n_in
;
238 case isl_dim_out
: return dim
->n_out
;
239 case isl_dim_all
: return dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
244 unsigned isl_space_dim(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
251 unsigned isl_space_offset(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
255 return offset(dim
, type
);
258 static __isl_give isl_space
*copy_ids(__isl_take isl_space
*dst
,
259 enum isl_dim_type dst_type
, unsigned offset
, __isl_keep isl_space
*src
,
260 enum isl_dim_type src_type
)
268 for (i
= 0; i
< n(src
, src_type
); ++i
) {
269 id
= get_id(src
, src_type
, i
);
272 dst
= set_id(dst
, dst_type
, offset
+ i
, isl_id_copy(id
));
279 __isl_take isl_space
*isl_space_dup(__isl_keep isl_space
*dim
)
284 dup
= isl_space_alloc(dim
->ctx
, dim
->nparam
, dim
->n_in
, dim
->n_out
);
285 if (dim
->tuple_id
[0] &&
286 !(dup
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[0])))
288 if (dim
->tuple_id
[1] &&
289 !(dup
->tuple_id
[1] = isl_id_copy(dim
->tuple_id
[1])))
291 if (dim
->nested
[0] && !(dup
->nested
[0] = isl_space_copy(dim
->nested
[0])))
293 if (dim
->nested
[1] && !(dup
->nested
[1] = isl_space_copy(dim
->nested
[1])))
297 dup
= copy_ids(dup
, isl_dim_param
, 0, dim
, isl_dim_param
);
298 dup
= copy_ids(dup
, isl_dim_in
, 0, dim
, isl_dim_in
);
299 dup
= copy_ids(dup
, isl_dim_out
, 0, dim
, isl_dim_out
);
306 __isl_give isl_space
*isl_space_cow(__isl_take isl_space
*dim
)
314 return isl_space_dup(dim
);
317 __isl_give isl_space
*isl_space_copy(__isl_keep isl_space
*dim
)
326 void isl_space_free(__isl_take isl_space
*dim
)
336 isl_id_free(dim
->tuple_id
[0]);
337 isl_id_free(dim
->tuple_id
[1]);
339 isl_space_free(dim
->nested
[0]);
340 isl_space_free(dim
->nested
[1]);
342 for (i
= 0; i
< dim
->n_id
; ++i
)
343 isl_id_free(dim
->ids
[i
]);
345 isl_ctx_deref(dim
->ctx
);
350 static int name_ok(isl_ctx
*ctx
, const char *s
)
355 dummy
= strtol(s
, &p
, 0);
357 isl_die(ctx
, isl_error_invalid
, "name looks like a number",
363 int isl_space_has_tuple_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
367 if (isl_space_is_params(dim
))
368 isl_die(dim
->ctx
, isl_error_invalid
,
369 "parameter spaces don't have tuple ids", return -1);
370 if (isl_space_is_set(dim
) && type
!= isl_dim_set
)
371 isl_die(dim
->ctx
, isl_error_invalid
,
372 "set spaces can only have a set id", return -1);
373 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
374 isl_die(dim
->ctx
, isl_error_invalid
,
375 "only input, output and set tuples can have ids",
377 return dim
->tuple_id
[type
- isl_dim_in
] != NULL
;
380 __isl_give isl_id
*isl_space_get_tuple_id(__isl_keep isl_space
*dim
,
381 enum isl_dim_type type
)
387 has_id
= isl_space_has_tuple_id(dim
, type
);
391 isl_die(dim
->ctx
, isl_error_invalid
,
392 "tuple has no id", return NULL
);
393 return isl_id_copy(dim
->tuple_id
[type
- isl_dim_in
]);
396 __isl_give isl_space
*isl_space_set_tuple_id(__isl_take isl_space
*dim
,
397 enum isl_dim_type type
, __isl_take isl_id
*id
)
399 dim
= isl_space_cow(dim
);
402 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
403 isl_die(dim
->ctx
, isl_error_invalid
,
404 "only input, output and set tuples can have names",
407 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
408 dim
->tuple_id
[type
- isl_dim_in
] = id
;
417 __isl_give isl_space
*isl_space_reset_tuple_id(__isl_take isl_space
*dim
,
418 enum isl_dim_type type
)
420 dim
= isl_space_cow(dim
);
423 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
424 isl_die(dim
->ctx
, isl_error_invalid
,
425 "only input, output and set tuples can have names",
428 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
429 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
437 __isl_give isl_space
*isl_space_set_dim_id(__isl_take isl_space
*dim
,
438 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
440 dim
= isl_space_cow(dim
);
443 isl_id_free(get_id(dim
, type
, pos
));
444 return set_id(dim
, type
, pos
, id
);
451 int isl_space_has_dim_id(__isl_keep isl_space
*dim
,
452 enum isl_dim_type type
, unsigned pos
)
456 return get_id(dim
, type
, pos
) != NULL
;
459 __isl_give isl_id
*isl_space_get_dim_id(__isl_keep isl_space
*dim
,
460 enum isl_dim_type type
, unsigned pos
)
464 if (!get_id(dim
, type
, pos
))
465 isl_die(dim
->ctx
, isl_error_invalid
,
466 "dim has no id", return NULL
);
467 return isl_id_copy(get_id(dim
, type
, pos
));
470 __isl_give isl_space
*isl_space_set_tuple_name(__isl_take isl_space
*dim
,
471 enum isl_dim_type type
, const char *s
)
479 return isl_space_reset_tuple_id(dim
, type
);
481 if (!name_ok(dim
->ctx
, s
))
484 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
485 return isl_space_set_tuple_id(dim
, type
, id
);
491 const char *isl_space_get_tuple_name(__isl_keep isl_space
*dim
,
492 enum isl_dim_type type
)
497 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
499 id
= dim
->tuple_id
[type
- isl_dim_in
];
500 return id
? id
->name
: NULL
;
503 __isl_give isl_space
*isl_space_set_dim_name(__isl_take isl_space
*dim
,
504 enum isl_dim_type type
, unsigned pos
,
511 if (!name_ok(dim
->ctx
, s
))
513 id
= isl_id_alloc(dim
->ctx
, s
, NULL
);
514 return isl_space_set_dim_id(dim
, type
, pos
, id
);
520 __isl_keep
const char *isl_space_get_dim_name(__isl_keep isl_space
*dim
,
521 enum isl_dim_type type
, unsigned pos
)
523 isl_id
*id
= get_id(dim
, type
, pos
);
524 return id
? id
->name
: NULL
;
527 int isl_space_find_dim_by_id(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
528 __isl_keep isl_id
*id
)
537 offset
= isl_space_offset(dim
, type
);
538 n
= isl_space_dim(dim
, type
);
539 for (i
= 0; i
< n
&& offset
+ i
< dim
->n_id
; ++i
)
540 if (dim
->ids
[offset
+ i
] == id
)
546 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*dim
,
547 enum isl_dim_type type
)
551 if (type
== isl_dim_in
)
552 return dim
->tuple_id
[0];
553 if (type
== isl_dim_out
)
554 return dim
->tuple_id
[1];
558 static __isl_keep isl_space
*nested(__isl_keep isl_space
*dim
,
559 enum isl_dim_type type
)
563 if (type
== isl_dim_in
)
564 return dim
->nested
[0];
565 if (type
== isl_dim_out
)
566 return dim
->nested
[1];
570 int isl_space_tuple_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
571 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
574 isl_space
*nested1
, *nested2
;
579 if (dim1
== dim2
&& dim1_type
== dim2_type
)
582 if (n(dim1
, dim1_type
) != n(dim2
, dim2_type
))
584 id1
= tuple_id(dim1
, dim1_type
);
585 id2
= tuple_id(dim2
, dim2_type
);
588 if (id1
&& id1
!= id2
)
590 nested1
= nested(dim1
, dim1_type
);
591 nested2
= nested(dim2
, dim2_type
);
592 if (!nested1
^ !nested2
)
594 if (nested1
&& !isl_space_is_equal(nested1
, nested2
))
599 static int match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
600 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
604 if (dim1
== dim2
&& dim1_type
== dim2_type
)
607 if (!isl_space_tuple_match(dim1
, dim1_type
, dim2
, dim2_type
))
610 if (!dim1
->ids
&& !dim2
->ids
)
613 for (i
= 0; i
< n(dim1
, dim1_type
); ++i
) {
614 if (get_id(dim1
, dim1_type
, i
) != get_id(dim2
, dim2_type
, i
))
620 int isl_space_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
621 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
626 return match(dim1
, dim1_type
, dim2
, dim2_type
);
629 static void get_ids(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
630 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
634 for (i
= 0; i
< n
; ++i
)
635 ids
[i
] = get_id(dim
, type
, first
+ i
);
638 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*dim
,
639 unsigned nparam
, unsigned n_in
, unsigned n_out
)
645 if (dim
->nparam
== nparam
&& dim
->n_in
== n_in
&& dim
->n_out
== n_out
)
648 isl_assert(dim
->ctx
, dim
->nparam
<= nparam
, goto error
);
649 isl_assert(dim
->ctx
, dim
->n_in
<= n_in
, goto error
);
650 isl_assert(dim
->ctx
, dim
->n_out
<= n_out
, goto error
);
652 dim
= isl_space_cow(dim
);
655 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
656 nparam
+ n_in
+ n_out
);
659 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
660 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ nparam
);
661 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ nparam
+ n_in
);
664 dim
->n_id
= nparam
+ n_in
+ n_out
;
666 dim
->nparam
= nparam
;
677 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*dim
,
678 enum isl_dim_type type
, unsigned n
)
682 dim
= isl_space_reset(dim
, type
);
685 dim
= isl_space_extend(dim
,
686 dim
->nparam
+ n
, dim
->n_in
, dim
->n_out
);
687 if (dim
&& dim
->nested
[0] &&
688 !(dim
->nested
[0] = isl_space_add_dims(dim
->nested
[0],
691 if (dim
&& dim
->nested
[1] &&
692 !(dim
->nested
[1] = isl_space_add_dims(dim
->nested
[1],
697 return isl_space_extend(dim
,
698 dim
->nparam
, dim
->n_in
+ n
, dim
->n_out
);
700 return isl_space_extend(dim
,
701 dim
->nparam
, dim
->n_in
, dim
->n_out
+ n
);
703 isl_die(dim
->ctx
, isl_error_invalid
,
704 "cannot add dimensions of specified type", goto error
);
711 static int valid_dim_type(enum isl_dim_type type
)
723 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*dim
,
724 enum isl_dim_type type
, unsigned pos
, unsigned n
)
731 return isl_space_reset(dim
, type
);
733 if (!valid_dim_type(type
))
734 isl_die(dim
->ctx
, isl_error_invalid
,
735 "cannot insert dimensions of specified type",
738 isl_assert(dim
->ctx
, pos
<= isl_space_dim(dim
, type
), goto error
);
740 dim
= isl_space_cow(dim
);
748 int *size
= s
- isl_dim_param
;
749 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
750 dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
);
754 size
[isl_dim_param
] = dim
->nparam
;
755 size
[isl_dim_in
] = dim
->n_in
;
756 size
[isl_dim_out
] = dim
->n_out
;
757 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
759 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
762 get_ids(dim
, t
, 0, pos
, ids
+ off
);
764 get_ids(dim
, t
, pos
, size
[t
] - pos
, ids
+ off
);
765 off
+= size
[t
] - pos
;
770 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
;
773 case isl_dim_param
: dim
->nparam
+= n
; break;
774 case isl_dim_in
: dim
->n_in
+= n
; break;
775 case isl_dim_out
: dim
->n_out
+= n
; break;
778 dim
= isl_space_reset(dim
, type
);
786 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*dim
,
787 enum isl_dim_type dst_type
, unsigned dst_pos
,
788 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
797 isl_assert(dim
->ctx
, src_pos
+ n
<= isl_space_dim(dim
, src_type
),
800 if (dst_type
== src_type
&& dst_pos
== src_pos
)
803 isl_assert(dim
->ctx
, dst_type
!= src_type
, goto error
);
805 dim
= isl_space_reset(dim
, src_type
);
806 dim
= isl_space_reset(dim
, dst_type
);
808 dim
= isl_space_cow(dim
);
817 int *size
= s
- isl_dim_param
;
818 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
819 dim
->nparam
+ dim
->n_in
+ dim
->n_out
);
823 size
[isl_dim_param
] = dim
->nparam
;
824 size
[isl_dim_in
] = dim
->n_in
;
825 size
[isl_dim_out
] = dim
->n_out
;
826 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
828 get_ids(dim
, t
, 0, dst_pos
, ids
+ off
);
830 get_ids(dim
, src_type
, src_pos
, n
, ids
+ off
);
832 get_ids(dim
, t
, dst_pos
, size
[t
] - dst_pos
,
834 off
+= size
[t
] - dst_pos
;
835 } else if (t
== src_type
) {
836 get_ids(dim
, t
, 0, src_pos
, ids
+ off
);
838 get_ids(dim
, t
, src_pos
+ n
,
839 size
[t
] - src_pos
- n
, ids
+ off
);
840 off
+= size
[t
] - src_pos
- n
;
842 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
848 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
852 case isl_dim_param
: dim
->nparam
+= n
; break;
853 case isl_dim_in
: dim
->n_in
+= n
; break;
854 case isl_dim_out
: dim
->n_out
+= n
; break;
859 case isl_dim_param
: dim
->nparam
-= n
; break;
860 case isl_dim_in
: dim
->n_in
-= n
; break;
861 case isl_dim_out
: dim
->n_out
-= n
; break;
865 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
868 for (i
= 0; i
< 2; ++i
) {
871 dim
->nested
[i
] = isl_space_replace(dim
->nested
[i
],
883 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
884 __isl_take isl_space
*right
)
891 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
893 isl_assert(left
->ctx
,
894 isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_in
),
897 dim
= isl_space_alloc(left
->ctx
, left
->nparam
, left
->n_in
, right
->n_out
);
901 dim
= copy_ids(dim
, isl_dim_param
, 0, left
, isl_dim_param
);
902 dim
= copy_ids(dim
, isl_dim_in
, 0, left
, isl_dim_in
);
903 dim
= copy_ids(dim
, isl_dim_out
, 0, right
, isl_dim_out
);
905 if (dim
&& left
->tuple_id
[0] &&
906 !(dim
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
908 if (dim
&& right
->tuple_id
[1] &&
909 !(dim
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
911 if (dim
&& left
->nested
[0] &&
912 !(dim
->nested
[0] = isl_space_copy(left
->nested
[0])))
914 if (dim
&& right
->nested
[1] &&
915 !(dim
->nested
[1] = isl_space_copy(right
->nested
[1])))
918 isl_space_free(left
);
919 isl_space_free(right
);
923 isl_space_free(left
);
924 isl_space_free(right
);
928 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
929 __isl_take isl_space
*right
)
931 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
936 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
939 dom1
= isl_space_domain(isl_space_copy(left
));
940 dom2
= isl_space_domain(isl_space_copy(right
));
941 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
943 dom1
= isl_space_range(left
);
944 dom2
= isl_space_range(right
);
945 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
947 return isl_space_join(isl_space_reverse(nest1
), nest2
);
949 isl_space_free(left
);
950 isl_space_free(right
);
954 /* Given two spaces { A -> C } and { B -> C }, construct the space
957 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
958 __isl_take isl_space
*right
)
960 isl_space
*ran
, *dom1
, *dom2
, *nest
;
965 if (!match(left
, isl_dim_param
, right
, isl_dim_param
))
966 isl_die(left
->ctx
, isl_error_invalid
,
967 "parameters need to match", goto error
);
968 if (!isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_out
))
969 isl_die(left
->ctx
, isl_error_invalid
,
970 "ranges need to match", goto error
);
972 ran
= isl_space_range(isl_space_copy(left
));
974 dom1
= isl_space_domain(left
);
975 dom2
= isl_space_domain(right
);
976 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
978 return isl_space_join(isl_space_reverse(nest
), ran
);
980 isl_space_free(left
);
981 isl_space_free(right
);
985 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
986 __isl_take isl_space
*right
)
988 isl_space
*dom
, *ran1
, *ran2
, *nest
;
993 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
995 if (!isl_space_tuple_match(left
, isl_dim_in
, right
, isl_dim_in
))
996 isl_die(left
->ctx
, isl_error_invalid
,
997 "domains need to match", goto error
);
999 dom
= isl_space_domain(isl_space_copy(left
));
1001 ran1
= isl_space_range(left
);
1002 ran2
= isl_space_range(right
);
1003 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
1005 return isl_space_join(isl_space_reverse(dom
), nest
);
1007 isl_space_free(left
);
1008 isl_space_free(right
);
1012 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*dim
)
1015 isl_id
**ids
= NULL
;
1019 ctx
= isl_space_get_ctx(dim
);
1020 if (!isl_space_is_set(dim
))
1021 isl_die(ctx
, isl_error_invalid
, "not a set space", goto error
);
1022 dim
= isl_space_cow(dim
);
1026 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
1027 dim
->nparam
+ dim
->n_out
+ dim
->n_out
);
1030 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
1031 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->nparam
);
1033 dim
->n_in
= dim
->n_out
;
1037 dim
->n_id
= dim
->nparam
+ dim
->n_out
+ dim
->n_out
;
1038 dim
= copy_ids(dim
, isl_dim_out
, 0, dim
, isl_dim_in
);
1040 isl_id_free(dim
->tuple_id
[0]);
1041 dim
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[1]);
1042 isl_space_free(dim
->nested
[0]);
1043 dim
->nested
[0] = isl_space_copy(dim
->nested
[1]);
1046 isl_space_free(dim
);
1050 static __isl_give isl_space
*set_ids(__isl_take isl_space
*dim
,
1051 enum isl_dim_type type
,
1052 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
1056 for (i
= 0; i
< n
; ++i
)
1057 dim
= set_id(dim
, type
, first
+ i
, ids
[i
]);
1062 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*dim
)
1066 isl_id
**ids
= NULL
;
1071 if (match(dim
, isl_dim_in
, dim
, isl_dim_out
))
1074 dim
= isl_space_cow(dim
);
1078 id
= dim
->tuple_id
[0];
1079 dim
->tuple_id
[0] = dim
->tuple_id
[1];
1080 dim
->tuple_id
[1] = id
;
1082 nested
= dim
->nested
[0];
1083 dim
->nested
[0] = dim
->nested
[1];
1084 dim
->nested
[1] = nested
;
1087 ids
= isl_alloc_array(dim
->ctx
, isl_id
*,
1088 dim
->n_in
+ dim
->n_out
);
1091 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
);
1092 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->n_in
);
1096 dim
->n_in
= dim
->n_out
;
1100 dim
= set_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
);
1101 dim
= set_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ dim
->n_out
);
1108 isl_space_free(dim
);
1112 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*dim
,
1113 enum isl_dim_type type
, unsigned first
, unsigned num
)
1121 return isl_space_reset(dim
, type
);
1123 if (!valid_dim_type(type
))
1124 isl_die(dim
->ctx
, isl_error_invalid
,
1125 "cannot drop dimensions of specified type", goto error
);
1127 isl_assert(dim
->ctx
, first
+ num
<= n(dim
, type
), goto error
);
1128 dim
= isl_space_cow(dim
);
1132 dim
= extend_ids(dim
);
1135 for (i
= 0; i
< num
; ++i
)
1136 isl_id_free(get_id(dim
, type
, first
+ i
));
1137 for (i
= first
+num
; i
< n(dim
, type
); ++i
)
1138 set_id(dim
, type
, i
- num
, get_id(dim
, type
, i
));
1141 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
,
1142 dim
->ids
+ offset(dim
, isl_dim_in
) - num
);
1144 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
,
1145 dim
->ids
+ offset(dim
, isl_dim_out
) - num
);
1152 case isl_dim_param
: dim
->nparam
-= num
; break;
1153 case isl_dim_in
: dim
->n_in
-= num
; break;
1154 case isl_dim_out
: dim
->n_out
-= num
; break;
1157 dim
= isl_space_reset(dim
, type
);
1158 if (type
== isl_dim_param
) {
1159 if (dim
&& dim
->nested
[0] &&
1160 !(dim
->nested
[0] = isl_space_drop_dims(dim
->nested
[0],
1161 isl_dim_param
, first
, num
)))
1163 if (dim
&& dim
->nested
[1] &&
1164 !(dim
->nested
[1] = isl_space_drop_dims(dim
->nested
[1],
1165 isl_dim_param
, first
, num
)))
1170 isl_space_free(dim
);
1174 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*dim
,
1175 unsigned first
, unsigned n
)
1179 return isl_space_drop_dims(dim
, isl_dim_in
, first
, n
);
1182 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*dim
,
1183 unsigned first
, unsigned n
)
1187 return isl_space_drop_dims(dim
, isl_dim_out
, first
, n
);
1190 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*dim
)
1194 dim
= isl_space_drop_outputs(dim
, 0, dim
->n_out
);
1195 dim
= isl_space_reverse(dim
);
1196 dim
= mark_as_set(dim
);
1200 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*dim
)
1204 if (!isl_space_is_set(dim
))
1205 isl_die(isl_space_get_ctx(dim
), isl_error_invalid
,
1206 "not a set space", goto error
);
1207 dim
= isl_space_reverse(dim
);
1208 dim
= isl_space_reset(dim
, isl_dim_out
);
1211 isl_space_free(dim
);
1215 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*dim
)
1219 dim
= isl_space_drop_inputs(dim
, 0, dim
->n_in
);
1220 dim
= mark_as_set(dim
);
1224 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*dim
)
1228 if (!isl_space_is_set(dim
))
1229 isl_die(isl_space_get_ctx(dim
), isl_error_invalid
,
1230 "not a set space", goto error
);
1231 return isl_space_reset(dim
, isl_dim_in
);
1233 isl_space_free(dim
);
1237 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
1239 if (isl_space_is_params(space
))
1241 space
= isl_space_drop_dims(space
,
1242 isl_dim_in
, 0, isl_space_dim(space
, isl_dim_in
));
1243 space
= isl_space_drop_dims(space
,
1244 isl_dim_out
, 0, isl_space_dim(space
, isl_dim_out
));
1245 space
= mark_as_params(space
);
1249 __isl_give isl_space
*isl_space_as_set_space(__isl_take isl_space
*dim
)
1251 dim
= isl_space_cow(dim
);
1255 dim
->n_out
+= dim
->n_in
;
1257 dim
= isl_space_reset(dim
, isl_dim_in
);
1258 dim
= isl_space_reset(dim
, isl_dim_out
);
1263 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*dim
,
1271 dim
->nparam
== 0 && dim
->n_in
== 0 && dim
->n_id
== 0)
1272 return isl_space_reset(isl_space_reset(dim
, isl_dim_in
), isl_dim_out
);
1273 dim
= isl_space_cow(dim
);
1276 dim
->n_out
+= dim
->nparam
+ dim
->n_in
+ n_div
;
1280 for (i
= 0; i
< dim
->n_id
; ++i
)
1281 isl_id_free(get_id(dim
, isl_dim_out
, i
));
1283 dim
= isl_space_reset(dim
, isl_dim_in
);
1284 dim
= isl_space_reset(dim
, isl_dim_out
);
1289 int isl_space_is_equal(__isl_keep isl_space
*dim1
, __isl_keep isl_space
*dim2
)
1295 return match(dim1
, isl_dim_param
, dim2
, isl_dim_param
) &&
1296 isl_space_tuple_match(dim1
, isl_dim_in
, dim2
, isl_dim_in
) &&
1297 isl_space_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_out
);
1300 /* Is space1 equal to the domain of space2?
1302 int isl_space_is_domain(__isl_keep isl_space
*space1
,
1303 __isl_keep isl_space
*space2
)
1305 if (!space1
|| !space2
)
1307 if (!isl_space_is_set(space1
))
1309 return match(space1
, isl_dim_param
, space2
, isl_dim_param
) &&
1310 isl_space_tuple_match(space1
, isl_dim_set
, space2
, isl_dim_in
);
1313 int isl_space_compatible(__isl_keep isl_space
*dim1
,
1314 __isl_keep isl_space
*dim2
)
1316 return dim1
->nparam
== dim2
->nparam
&&
1317 dim1
->n_in
+ dim1
->n_out
== dim2
->n_in
+ dim2
->n_out
;
1320 static uint32_t isl_hash_dim(uint32_t hash
, __isl_keep isl_space
*dim
)
1328 hash
= isl_hash_builtin(hash
, dim
->nparam
);
1329 hash
= isl_hash_builtin(hash
, dim
->n_in
);
1330 hash
= isl_hash_builtin(hash
, dim
->n_out
);
1332 for (i
= 0; i
< dim
->nparam
; ++i
) {
1333 id
= get_id(dim
, isl_dim_param
, i
);
1334 hash
= isl_hash_id(hash
, id
);
1337 id
= tuple_id(dim
, isl_dim_in
);
1338 hash
= isl_hash_id(hash
, id
);
1339 id
= tuple_id(dim
, isl_dim_out
);
1340 hash
= isl_hash_id(hash
, id
);
1342 hash
= isl_hash_dim(hash
, dim
->nested
[0]);
1343 hash
= isl_hash_dim(hash
, dim
->nested
[1]);
1348 uint32_t isl_space_get_hash(__isl_keep isl_space
*dim
)
1355 hash
= isl_hash_init();
1356 hash
= isl_hash_dim(hash
, dim
);
1361 int isl_space_is_wrapping(__isl_keep isl_space
*dim
)
1366 if (!isl_space_is_set(dim
))
1369 return dim
->nested
[1] != NULL
;
1372 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*dim
)
1379 wrap
= isl_space_set_alloc(dim
->ctx
,
1380 dim
->nparam
, dim
->n_in
+ dim
->n_out
);
1382 wrap
= copy_ids(wrap
, isl_dim_param
, 0, dim
, isl_dim_param
);
1383 wrap
= copy_ids(wrap
, isl_dim_set
, 0, dim
, isl_dim_in
);
1384 wrap
= copy_ids(wrap
, isl_dim_set
, dim
->n_in
, dim
, isl_dim_out
);
1389 wrap
->nested
[1] = dim
;
1393 isl_space_free(dim
);
1397 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*dim
)
1404 if (!isl_space_is_wrapping(dim
))
1405 isl_die(dim
->ctx
, isl_error_invalid
, "not a wrapping dim",
1408 unwrap
= isl_space_copy(dim
->nested
[1]);
1409 isl_space_free(dim
);
1413 isl_space_free(dim
);
1417 int isl_space_is_named_or_nested(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
1419 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
1423 if (dim
->tuple_id
[type
- isl_dim_in
])
1425 if (dim
->nested
[type
- isl_dim_in
])
1430 int isl_space_may_be_set(__isl_keep isl_space
*dim
)
1434 if (isl_space_is_set(dim
))
1436 if (isl_space_dim(dim
, isl_dim_in
) != 0)
1438 if (isl_space_is_named_or_nested(dim
, isl_dim_in
))
1443 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*dim
,
1444 enum isl_dim_type type
)
1446 if (!isl_space_is_named_or_nested(dim
, type
))
1449 dim
= isl_space_cow(dim
);
1453 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
1454 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
1455 isl_space_free(dim
->nested
[type
- isl_dim_in
]);
1456 dim
->nested
[type
- isl_dim_in
] = NULL
;
1461 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*dim
)
1465 if (!dim
->nested
[0] && !dim
->nested
[1])
1469 dim
= isl_space_reset(dim
, isl_dim_in
);
1470 if (dim
&& dim
->nested
[1])
1471 dim
= isl_space_reset(dim
, isl_dim_out
);
1476 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*dim
)
1480 if (!dim
->nested
[0])
1483 return isl_space_reset(dim
, isl_dim_in
);
1486 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*dim
)
1490 if (!dim
->nested
[1])
1493 return isl_space_reset(dim
, isl_dim_out
);
1496 /* Replace the dimensions of the given type of dst by those of src.
1498 __isl_give isl_space
*isl_space_replace(__isl_take isl_space
*dst
,
1499 enum isl_dim_type type
, __isl_keep isl_space
*src
)
1501 dst
= isl_space_cow(dst
);
1506 dst
= isl_space_drop_dims(dst
, type
, 0, isl_space_dim(dst
, type
));
1507 dst
= isl_space_add_dims(dst
, type
, isl_space_dim(src
, type
));
1508 dst
= copy_ids(dst
, type
, 0, src
, type
);
1510 if (dst
&& type
== isl_dim_param
) {
1512 for (i
= 0; i
<= 1; ++i
) {
1513 if (!dst
->nested
[i
])
1515 dst
->nested
[i
] = isl_space_replace(dst
->nested
[i
],
1517 if (!dst
->nested
[i
])
1524 isl_space_free(dst
);
1528 /* Given a dimension specification "dim" of a set, create a dimension
1529 * specification for the lift of the set. In particular, the result
1530 * is of the form [dim -> local[..]], with n_local variables in the
1531 * range of the wrapped map.
1533 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*dim
, unsigned n_local
)
1535 isl_space
*local_dim
;
1540 local_dim
= isl_space_dup(dim
);
1541 local_dim
= isl_space_drop_dims(local_dim
, isl_dim_set
, 0, dim
->n_out
);
1542 local_dim
= isl_space_add_dims(local_dim
, isl_dim_set
, n_local
);
1543 local_dim
= isl_space_set_tuple_name(local_dim
, isl_dim_set
, "local");
1544 dim
= isl_space_join(isl_space_from_domain(dim
),
1545 isl_space_from_range(local_dim
));
1546 dim
= isl_space_wrap(dim
);
1547 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, "lifted");
1552 int isl_space_can_zip(__isl_keep isl_space
*dim
)
1557 return dim
->nested
[0] && dim
->nested
[1];
1560 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*dim
)
1562 isl_space
*dom
, *ran
;
1563 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
1565 if (!isl_space_can_zip(dim
))
1566 isl_die(dim
->ctx
, isl_error_invalid
, "dim cannot be zipped",
1571 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(dim
)));
1572 ran
= isl_space_unwrap(isl_space_range(dim
));
1573 dom_dom
= isl_space_domain(isl_space_copy(dom
));
1574 dom_ran
= isl_space_range(dom
);
1575 ran_dom
= isl_space_domain(isl_space_copy(ran
));
1576 ran_ran
= isl_space_range(ran
);
1577 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
1578 isl_space_from_range(ran_dom
));
1579 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
1580 isl_space_from_range(ran_ran
));
1581 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
1582 isl_space_from_range(isl_space_wrap(ran
)));
1584 isl_space_free(dim
);
1588 int isl_space_has_named_params(__isl_keep isl_space
*dim
)
1595 if (dim
->nparam
== 0)
1597 off
= isl_space_offset(dim
, isl_dim_param
);
1598 if (off
+ dim
->nparam
> dim
->n_id
)
1600 for (i
= 0; i
< dim
->nparam
; ++i
)
1601 if (!dim
->ids
[off
+ i
])
1606 /* Align the initial parameters of dim1 to match the order in dim2.
1608 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*dim1
,
1609 __isl_take isl_space
*dim2
)
1611 isl_reordering
*exp
;
1613 if (!isl_space_has_named_params(dim1
) || !isl_space_has_named_params(dim2
))
1614 isl_die(isl_space_get_ctx(dim1
), isl_error_invalid
,
1615 "parameter alignment requires named parameters",
1618 dim2
= isl_space_params(dim2
);
1619 exp
= isl_parameter_alignment_reordering(dim1
, dim2
);
1620 exp
= isl_reordering_extend_space(exp
, dim1
);
1621 isl_space_free(dim2
);
1624 dim1
= isl_space_copy(exp
->dim
);
1625 isl_reordering_free(exp
);
1628 isl_space_free(dim1
);
1629 isl_space_free(dim2
);
1633 /* Given the space of set (domain), construct a space for a map
1634 * with as domain the given space and as range the range of "model".
1636 __isl_give isl_space
*isl_space_extend_domain_with_range(
1637 __isl_take isl_space
*domain
, __isl_take isl_space
*model
)
1641 space
= isl_space_from_domain(domain
);
1642 space
= isl_space_add_dims(space
, isl_dim_out
,
1643 isl_space_dim(model
, isl_dim_out
));
1644 if (isl_space_has_tuple_id(model
, isl_dim_out
))
1645 space
= isl_space_set_tuple_id(space
, isl_dim_out
,
1646 isl_space_get_tuple_id(model
, isl_dim_out
));
1647 isl_space_free(model
);