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 int isl_space_find_dim_by_name(__isl_keep isl_space
*space
,
547 enum isl_dim_type type
, const char *name
)
556 offset
= isl_space_offset(space
, type
);
557 n
= isl_space_dim(space
, type
);
558 for (i
= 0; i
< n
&& offset
+ i
< space
->n_id
; ++i
)
559 if (space
->ids
[offset
+ i
]->name
&&
560 !strcmp(space
->ids
[offset
+ i
]->name
, name
))
566 static __isl_keep isl_id
*tuple_id(__isl_keep isl_space
*dim
,
567 enum isl_dim_type type
)
571 if (type
== isl_dim_in
)
572 return dim
->tuple_id
[0];
573 if (type
== isl_dim_out
)
574 return dim
->tuple_id
[1];
578 static __isl_keep isl_space
*nested(__isl_keep isl_space
*dim
,
579 enum isl_dim_type type
)
583 if (type
== isl_dim_in
)
584 return dim
->nested
[0];
585 if (type
== isl_dim_out
)
586 return dim
->nested
[1];
590 int isl_space_tuple_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
591 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
594 isl_space
*nested1
, *nested2
;
599 if (dim1
== dim2
&& dim1_type
== dim2_type
)
602 if (n(dim1
, dim1_type
) != n(dim2
, dim2_type
))
604 id1
= tuple_id(dim1
, dim1_type
);
605 id2
= tuple_id(dim2
, dim2_type
);
608 if (id1
&& id1
!= id2
)
610 nested1
= nested(dim1
, dim1_type
);
611 nested2
= nested(dim2
, dim2_type
);
612 if (!nested1
^ !nested2
)
614 if (nested1
&& !isl_space_is_equal(nested1
, nested2
))
619 static int match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
620 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
624 if (dim1
== dim2
&& dim1_type
== dim2_type
)
627 if (!isl_space_tuple_match(dim1
, dim1_type
, dim2
, dim2_type
))
630 if (!dim1
->ids
&& !dim2
->ids
)
633 for (i
= 0; i
< n(dim1
, dim1_type
); ++i
) {
634 if (get_id(dim1
, dim1_type
, i
) != get_id(dim2
, dim2_type
, i
))
640 int isl_space_match(__isl_keep isl_space
*dim1
, enum isl_dim_type dim1_type
,
641 __isl_keep isl_space
*dim2
, enum isl_dim_type dim2_type
)
646 return match(dim1
, dim1_type
, dim2
, dim2_type
);
649 static void get_ids(__isl_keep isl_space
*dim
, enum isl_dim_type type
,
650 unsigned first
, unsigned n
, __isl_keep isl_id
**ids
)
654 for (i
= 0; i
< n
; ++i
)
655 ids
[i
] = get_id(dim
, type
, first
+ i
);
658 __isl_give isl_space
*isl_space_extend(__isl_take isl_space
*dim
,
659 unsigned nparam
, unsigned n_in
, unsigned n_out
)
665 if (dim
->nparam
== nparam
&& dim
->n_in
== n_in
&& dim
->n_out
== n_out
)
668 isl_assert(dim
->ctx
, dim
->nparam
<= nparam
, goto error
);
669 isl_assert(dim
->ctx
, dim
->n_in
<= n_in
, goto error
);
670 isl_assert(dim
->ctx
, dim
->n_out
<= n_out
, goto error
);
672 dim
= isl_space_cow(dim
);
675 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
676 nparam
+ n_in
+ n_out
);
679 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
680 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ nparam
);
681 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ nparam
+ n_in
);
684 dim
->n_id
= nparam
+ n_in
+ n_out
;
686 dim
->nparam
= nparam
;
697 __isl_give isl_space
*isl_space_add_dims(__isl_take isl_space
*dim
,
698 enum isl_dim_type type
, unsigned n
)
702 dim
= isl_space_reset(dim
, type
);
705 dim
= isl_space_extend(dim
,
706 dim
->nparam
+ n
, dim
->n_in
, dim
->n_out
);
707 if (dim
&& dim
->nested
[0] &&
708 !(dim
->nested
[0] = isl_space_add_dims(dim
->nested
[0],
711 if (dim
&& dim
->nested
[1] &&
712 !(dim
->nested
[1] = isl_space_add_dims(dim
->nested
[1],
717 return isl_space_extend(dim
,
718 dim
->nparam
, dim
->n_in
+ n
, dim
->n_out
);
720 return isl_space_extend(dim
,
721 dim
->nparam
, dim
->n_in
, dim
->n_out
+ n
);
723 isl_die(dim
->ctx
, isl_error_invalid
,
724 "cannot add dimensions of specified type", goto error
);
731 static int valid_dim_type(enum isl_dim_type type
)
743 __isl_give isl_space
*isl_space_insert_dims(__isl_take isl_space
*dim
,
744 enum isl_dim_type type
, unsigned pos
, unsigned n
)
751 return isl_space_reset(dim
, type
);
753 if (!valid_dim_type(type
))
754 isl_die(dim
->ctx
, isl_error_invalid
,
755 "cannot insert dimensions of specified type",
758 isl_assert(dim
->ctx
, pos
<= isl_space_dim(dim
, type
), goto error
);
760 dim
= isl_space_cow(dim
);
768 int *size
= s
- isl_dim_param
;
769 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
770 dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
);
774 size
[isl_dim_param
] = dim
->nparam
;
775 size
[isl_dim_in
] = dim
->n_in
;
776 size
[isl_dim_out
] = dim
->n_out
;
777 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
779 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
782 get_ids(dim
, t
, 0, pos
, ids
+ off
);
784 get_ids(dim
, t
, pos
, size
[t
] - pos
, ids
+ off
);
785 off
+= size
[t
] - pos
;
790 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
+ n
;
793 case isl_dim_param
: dim
->nparam
+= n
; break;
794 case isl_dim_in
: dim
->n_in
+= n
; break;
795 case isl_dim_out
: dim
->n_out
+= n
; break;
798 dim
= isl_space_reset(dim
, type
);
806 __isl_give isl_space
*isl_space_move_dims(__isl_take isl_space
*dim
,
807 enum isl_dim_type dst_type
, unsigned dst_pos
,
808 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
817 isl_assert(dim
->ctx
, src_pos
+ n
<= isl_space_dim(dim
, src_type
),
820 if (dst_type
== src_type
&& dst_pos
== src_pos
)
823 isl_assert(dim
->ctx
, dst_type
!= src_type
, goto error
);
825 dim
= isl_space_reset(dim
, src_type
);
826 dim
= isl_space_reset(dim
, dst_type
);
828 dim
= isl_space_cow(dim
);
837 int *size
= s
- isl_dim_param
;
838 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
839 dim
->nparam
+ dim
->n_in
+ dim
->n_out
);
843 size
[isl_dim_param
] = dim
->nparam
;
844 size
[isl_dim_in
] = dim
->n_in
;
845 size
[isl_dim_out
] = dim
->n_out
;
846 for (t
= isl_dim_param
; t
<= isl_dim_out
; ++t
) {
848 get_ids(dim
, t
, 0, dst_pos
, ids
+ off
);
850 get_ids(dim
, src_type
, src_pos
, n
, ids
+ off
);
852 get_ids(dim
, t
, dst_pos
, size
[t
] - dst_pos
,
854 off
+= size
[t
] - dst_pos
;
855 } else if (t
== src_type
) {
856 get_ids(dim
, t
, 0, src_pos
, ids
+ off
);
858 get_ids(dim
, t
, src_pos
+ n
,
859 size
[t
] - src_pos
- n
, ids
+ off
);
860 off
+= size
[t
] - src_pos
- n
;
862 get_ids(dim
, t
, 0, size
[t
], ids
+ off
);
868 dim
->n_id
= dim
->nparam
+ dim
->n_in
+ dim
->n_out
;
872 case isl_dim_param
: dim
->nparam
+= n
; break;
873 case isl_dim_in
: dim
->n_in
+= n
; break;
874 case isl_dim_out
: dim
->n_out
+= n
; break;
879 case isl_dim_param
: dim
->nparam
-= n
; break;
880 case isl_dim_in
: dim
->n_in
-= n
; break;
881 case isl_dim_out
: dim
->n_out
-= n
; break;
885 if (dst_type
!= isl_dim_param
&& src_type
!= isl_dim_param
)
888 for (i
= 0; i
< 2; ++i
) {
891 dim
->nested
[i
] = isl_space_replace(dim
->nested
[i
],
903 __isl_give isl_space
*isl_space_join(__isl_take isl_space
*left
,
904 __isl_take isl_space
*right
)
911 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
913 isl_assert(left
->ctx
,
914 isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_in
),
917 dim
= isl_space_alloc(left
->ctx
, left
->nparam
, left
->n_in
, right
->n_out
);
921 dim
= copy_ids(dim
, isl_dim_param
, 0, left
, isl_dim_param
);
922 dim
= copy_ids(dim
, isl_dim_in
, 0, left
, isl_dim_in
);
923 dim
= copy_ids(dim
, isl_dim_out
, 0, right
, isl_dim_out
);
925 if (dim
&& left
->tuple_id
[0] &&
926 !(dim
->tuple_id
[0] = isl_id_copy(left
->tuple_id
[0])))
928 if (dim
&& right
->tuple_id
[1] &&
929 !(dim
->tuple_id
[1] = isl_id_copy(right
->tuple_id
[1])))
931 if (dim
&& left
->nested
[0] &&
932 !(dim
->nested
[0] = isl_space_copy(left
->nested
[0])))
934 if (dim
&& right
->nested
[1] &&
935 !(dim
->nested
[1] = isl_space_copy(right
->nested
[1])))
938 isl_space_free(left
);
939 isl_space_free(right
);
943 isl_space_free(left
);
944 isl_space_free(right
);
948 __isl_give isl_space
*isl_space_product(__isl_take isl_space
*left
,
949 __isl_take isl_space
*right
)
951 isl_space
*dom1
, *dom2
, *nest1
, *nest2
;
956 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
959 dom1
= isl_space_domain(isl_space_copy(left
));
960 dom2
= isl_space_domain(isl_space_copy(right
));
961 nest1
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
963 dom1
= isl_space_range(left
);
964 dom2
= isl_space_range(right
);
965 nest2
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
967 return isl_space_join(isl_space_reverse(nest1
), nest2
);
969 isl_space_free(left
);
970 isl_space_free(right
);
974 /* Given two spaces { A -> C } and { B -> C }, construct the space
977 __isl_give isl_space
*isl_space_domain_product(__isl_take isl_space
*left
,
978 __isl_take isl_space
*right
)
980 isl_space
*ran
, *dom1
, *dom2
, *nest
;
985 if (!match(left
, isl_dim_param
, right
, isl_dim_param
))
986 isl_die(left
->ctx
, isl_error_invalid
,
987 "parameters need to match", goto error
);
988 if (!isl_space_tuple_match(left
, isl_dim_out
, right
, isl_dim_out
))
989 isl_die(left
->ctx
, isl_error_invalid
,
990 "ranges need to match", goto error
);
992 ran
= isl_space_range(isl_space_copy(left
));
994 dom1
= isl_space_domain(left
);
995 dom2
= isl_space_domain(right
);
996 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(dom1
), dom2
));
998 return isl_space_join(isl_space_reverse(nest
), ran
);
1000 isl_space_free(left
);
1001 isl_space_free(right
);
1005 __isl_give isl_space
*isl_space_range_product(__isl_take isl_space
*left
,
1006 __isl_take isl_space
*right
)
1008 isl_space
*dom
, *ran1
, *ran2
, *nest
;
1010 if (!left
|| !right
)
1013 isl_assert(left
->ctx
, match(left
, isl_dim_param
, right
, isl_dim_param
),
1015 if (!isl_space_tuple_match(left
, isl_dim_in
, right
, isl_dim_in
))
1016 isl_die(left
->ctx
, isl_error_invalid
,
1017 "domains need to match", goto error
);
1019 dom
= isl_space_domain(isl_space_copy(left
));
1021 ran1
= isl_space_range(left
);
1022 ran2
= isl_space_range(right
);
1023 nest
= isl_space_wrap(isl_space_join(isl_space_reverse(ran1
), ran2
));
1025 return isl_space_join(isl_space_reverse(dom
), nest
);
1027 isl_space_free(left
);
1028 isl_space_free(right
);
1032 __isl_give isl_space
*isl_space_map_from_set(__isl_take isl_space
*dim
)
1035 isl_id
**ids
= NULL
;
1039 ctx
= isl_space_get_ctx(dim
);
1040 if (!isl_space_is_set(dim
))
1041 isl_die(ctx
, isl_error_invalid
, "not a set space", goto error
);
1042 dim
= isl_space_cow(dim
);
1046 ids
= isl_calloc_array(dim
->ctx
, isl_id
*,
1047 dim
->nparam
+ dim
->n_out
+ dim
->n_out
);
1050 get_ids(dim
, isl_dim_param
, 0, dim
->nparam
, ids
);
1051 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->nparam
);
1053 dim
->n_in
= dim
->n_out
;
1057 dim
->n_id
= dim
->nparam
+ dim
->n_out
+ dim
->n_out
;
1058 dim
= copy_ids(dim
, isl_dim_out
, 0, dim
, isl_dim_in
);
1060 isl_id_free(dim
->tuple_id
[0]);
1061 dim
->tuple_id
[0] = isl_id_copy(dim
->tuple_id
[1]);
1062 isl_space_free(dim
->nested
[0]);
1063 dim
->nested
[0] = isl_space_copy(dim
->nested
[1]);
1066 isl_space_free(dim
);
1070 static __isl_give isl_space
*set_ids(__isl_take isl_space
*dim
,
1071 enum isl_dim_type type
,
1072 unsigned first
, unsigned n
, __isl_take isl_id
**ids
)
1076 for (i
= 0; i
< n
; ++i
)
1077 dim
= set_id(dim
, type
, first
+ i
, ids
[i
]);
1082 __isl_give isl_space
*isl_space_reverse(__isl_take isl_space
*dim
)
1086 isl_id
**ids
= NULL
;
1091 if (match(dim
, isl_dim_in
, dim
, isl_dim_out
))
1094 dim
= isl_space_cow(dim
);
1098 id
= dim
->tuple_id
[0];
1099 dim
->tuple_id
[0] = dim
->tuple_id
[1];
1100 dim
->tuple_id
[1] = id
;
1102 nested
= dim
->nested
[0];
1103 dim
->nested
[0] = dim
->nested
[1];
1104 dim
->nested
[1] = nested
;
1107 ids
= isl_alloc_array(dim
->ctx
, isl_id
*,
1108 dim
->n_in
+ dim
->n_out
);
1111 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
);
1112 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
+ dim
->n_in
);
1116 dim
->n_in
= dim
->n_out
;
1120 dim
= set_ids(dim
, isl_dim_out
, 0, dim
->n_out
, ids
);
1121 dim
= set_ids(dim
, isl_dim_in
, 0, dim
->n_in
, ids
+ dim
->n_out
);
1128 isl_space_free(dim
);
1132 __isl_give isl_space
*isl_space_drop_dims(__isl_take isl_space
*dim
,
1133 enum isl_dim_type type
, unsigned first
, unsigned num
)
1141 return isl_space_reset(dim
, type
);
1143 if (!valid_dim_type(type
))
1144 isl_die(dim
->ctx
, isl_error_invalid
,
1145 "cannot drop dimensions of specified type", goto error
);
1147 isl_assert(dim
->ctx
, first
+ num
<= n(dim
, type
), goto error
);
1148 dim
= isl_space_cow(dim
);
1152 dim
= extend_ids(dim
);
1155 for (i
= 0; i
< num
; ++i
)
1156 isl_id_free(get_id(dim
, type
, first
+ i
));
1157 for (i
= first
+num
; i
< n(dim
, type
); ++i
)
1158 set_id(dim
, type
, i
- num
, get_id(dim
, type
, i
));
1161 get_ids(dim
, isl_dim_in
, 0, dim
->n_in
,
1162 dim
->ids
+ offset(dim
, isl_dim_in
) - num
);
1164 get_ids(dim
, isl_dim_out
, 0, dim
->n_out
,
1165 dim
->ids
+ offset(dim
, isl_dim_out
) - num
);
1172 case isl_dim_param
: dim
->nparam
-= num
; break;
1173 case isl_dim_in
: dim
->n_in
-= num
; break;
1174 case isl_dim_out
: dim
->n_out
-= num
; break;
1177 dim
= isl_space_reset(dim
, type
);
1178 if (type
== isl_dim_param
) {
1179 if (dim
&& dim
->nested
[0] &&
1180 !(dim
->nested
[0] = isl_space_drop_dims(dim
->nested
[0],
1181 isl_dim_param
, first
, num
)))
1183 if (dim
&& dim
->nested
[1] &&
1184 !(dim
->nested
[1] = isl_space_drop_dims(dim
->nested
[1],
1185 isl_dim_param
, first
, num
)))
1190 isl_space_free(dim
);
1194 __isl_give isl_space
*isl_space_drop_inputs(__isl_take isl_space
*dim
,
1195 unsigned first
, unsigned n
)
1199 return isl_space_drop_dims(dim
, isl_dim_in
, first
, n
);
1202 __isl_give isl_space
*isl_space_drop_outputs(__isl_take isl_space
*dim
,
1203 unsigned first
, unsigned n
)
1207 return isl_space_drop_dims(dim
, isl_dim_out
, first
, n
);
1210 __isl_give isl_space
*isl_space_domain(__isl_take isl_space
*dim
)
1214 dim
= isl_space_drop_outputs(dim
, 0, dim
->n_out
);
1215 dim
= isl_space_reverse(dim
);
1216 dim
= mark_as_set(dim
);
1220 __isl_give isl_space
*isl_space_from_domain(__isl_take isl_space
*dim
)
1224 if (!isl_space_is_set(dim
))
1225 isl_die(isl_space_get_ctx(dim
), isl_error_invalid
,
1226 "not a set space", goto error
);
1227 dim
= isl_space_reverse(dim
);
1228 dim
= isl_space_reset(dim
, isl_dim_out
);
1231 isl_space_free(dim
);
1235 __isl_give isl_space
*isl_space_range(__isl_take isl_space
*dim
)
1239 dim
= isl_space_drop_inputs(dim
, 0, dim
->n_in
);
1240 dim
= mark_as_set(dim
);
1244 __isl_give isl_space
*isl_space_from_range(__isl_take isl_space
*dim
)
1248 if (!isl_space_is_set(dim
))
1249 isl_die(isl_space_get_ctx(dim
), isl_error_invalid
,
1250 "not a set space", goto error
);
1251 return isl_space_reset(dim
, isl_dim_in
);
1253 isl_space_free(dim
);
1257 __isl_give isl_space
*isl_space_params(__isl_take isl_space
*space
)
1259 if (isl_space_is_params(space
))
1261 space
= isl_space_drop_dims(space
,
1262 isl_dim_in
, 0, isl_space_dim(space
, isl_dim_in
));
1263 space
= isl_space_drop_dims(space
,
1264 isl_dim_out
, 0, isl_space_dim(space
, isl_dim_out
));
1265 space
= mark_as_params(space
);
1269 __isl_give isl_space
*isl_space_set_from_params(__isl_take isl_space
*space
)
1273 if (!isl_space_is_params(space
))
1274 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
1275 "not a parameter space", goto error
);
1276 return isl_space_reset(space
, isl_dim_set
);
1278 isl_space_free(space
);
1282 __isl_give isl_space
*isl_space_as_set_space(__isl_take isl_space
*dim
)
1284 dim
= isl_space_cow(dim
);
1288 dim
->n_out
+= dim
->n_in
;
1290 dim
= isl_space_reset(dim
, isl_dim_in
);
1291 dim
= isl_space_reset(dim
, isl_dim_out
);
1296 __isl_give isl_space
*isl_space_underlying(__isl_take isl_space
*dim
,
1304 dim
->nparam
== 0 && dim
->n_in
== 0 && dim
->n_id
== 0)
1305 return isl_space_reset(isl_space_reset(dim
, isl_dim_in
), isl_dim_out
);
1306 dim
= isl_space_cow(dim
);
1309 dim
->n_out
+= dim
->nparam
+ dim
->n_in
+ n_div
;
1313 for (i
= 0; i
< dim
->n_id
; ++i
)
1314 isl_id_free(get_id(dim
, isl_dim_out
, i
));
1316 dim
= isl_space_reset(dim
, isl_dim_in
);
1317 dim
= isl_space_reset(dim
, isl_dim_out
);
1322 int isl_space_is_equal(__isl_keep isl_space
*dim1
, __isl_keep isl_space
*dim2
)
1328 return match(dim1
, isl_dim_param
, dim2
, isl_dim_param
) &&
1329 isl_space_tuple_match(dim1
, isl_dim_in
, dim2
, isl_dim_in
) &&
1330 isl_space_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_out
);
1333 /* Is space1 equal to the domain of space2?
1335 int isl_space_is_domain(__isl_keep isl_space
*space1
,
1336 __isl_keep isl_space
*space2
)
1338 if (!space1
|| !space2
)
1340 if (!isl_space_is_set(space1
))
1342 return match(space1
, isl_dim_param
, space2
, isl_dim_param
) &&
1343 isl_space_tuple_match(space1
, isl_dim_set
, space2
, isl_dim_in
);
1346 int isl_space_compatible(__isl_keep isl_space
*dim1
,
1347 __isl_keep isl_space
*dim2
)
1349 return dim1
->nparam
== dim2
->nparam
&&
1350 dim1
->n_in
+ dim1
->n_out
== dim2
->n_in
+ dim2
->n_out
;
1353 static uint32_t isl_hash_dim(uint32_t hash
, __isl_keep isl_space
*dim
)
1361 hash
= isl_hash_builtin(hash
, dim
->nparam
);
1362 hash
= isl_hash_builtin(hash
, dim
->n_in
);
1363 hash
= isl_hash_builtin(hash
, dim
->n_out
);
1365 for (i
= 0; i
< dim
->nparam
; ++i
) {
1366 id
= get_id(dim
, isl_dim_param
, i
);
1367 hash
= isl_hash_id(hash
, id
);
1370 id
= tuple_id(dim
, isl_dim_in
);
1371 hash
= isl_hash_id(hash
, id
);
1372 id
= tuple_id(dim
, isl_dim_out
);
1373 hash
= isl_hash_id(hash
, id
);
1375 hash
= isl_hash_dim(hash
, dim
->nested
[0]);
1376 hash
= isl_hash_dim(hash
, dim
->nested
[1]);
1381 uint32_t isl_space_get_hash(__isl_keep isl_space
*dim
)
1388 hash
= isl_hash_init();
1389 hash
= isl_hash_dim(hash
, dim
);
1394 int isl_space_is_wrapping(__isl_keep isl_space
*dim
)
1399 if (!isl_space_is_set(dim
))
1402 return dim
->nested
[1] != NULL
;
1405 __isl_give isl_space
*isl_space_wrap(__isl_take isl_space
*dim
)
1412 wrap
= isl_space_set_alloc(dim
->ctx
,
1413 dim
->nparam
, dim
->n_in
+ dim
->n_out
);
1415 wrap
= copy_ids(wrap
, isl_dim_param
, 0, dim
, isl_dim_param
);
1416 wrap
= copy_ids(wrap
, isl_dim_set
, 0, dim
, isl_dim_in
);
1417 wrap
= copy_ids(wrap
, isl_dim_set
, dim
->n_in
, dim
, isl_dim_out
);
1422 wrap
->nested
[1] = dim
;
1426 isl_space_free(dim
);
1430 __isl_give isl_space
*isl_space_unwrap(__isl_take isl_space
*dim
)
1437 if (!isl_space_is_wrapping(dim
))
1438 isl_die(dim
->ctx
, isl_error_invalid
, "not a wrapping dim",
1441 unwrap
= isl_space_copy(dim
->nested
[1]);
1442 isl_space_free(dim
);
1446 isl_space_free(dim
);
1450 int isl_space_is_named_or_nested(__isl_keep isl_space
*dim
, enum isl_dim_type type
)
1452 if (type
!= isl_dim_in
&& type
!= isl_dim_out
)
1456 if (dim
->tuple_id
[type
- isl_dim_in
])
1458 if (dim
->nested
[type
- isl_dim_in
])
1463 int isl_space_may_be_set(__isl_keep isl_space
*dim
)
1467 if (isl_space_is_set(dim
))
1469 if (isl_space_dim(dim
, isl_dim_in
) != 0)
1471 if (isl_space_is_named_or_nested(dim
, isl_dim_in
))
1476 __isl_give isl_space
*isl_space_reset(__isl_take isl_space
*dim
,
1477 enum isl_dim_type type
)
1479 if (!isl_space_is_named_or_nested(dim
, type
))
1482 dim
= isl_space_cow(dim
);
1486 isl_id_free(dim
->tuple_id
[type
- isl_dim_in
]);
1487 dim
->tuple_id
[type
- isl_dim_in
] = NULL
;
1488 isl_space_free(dim
->nested
[type
- isl_dim_in
]);
1489 dim
->nested
[type
- isl_dim_in
] = NULL
;
1494 __isl_give isl_space
*isl_space_flatten(__isl_take isl_space
*dim
)
1498 if (!dim
->nested
[0] && !dim
->nested
[1])
1502 dim
= isl_space_reset(dim
, isl_dim_in
);
1503 if (dim
&& dim
->nested
[1])
1504 dim
= isl_space_reset(dim
, isl_dim_out
);
1509 __isl_give isl_space
*isl_space_flatten_domain(__isl_take isl_space
*dim
)
1513 if (!dim
->nested
[0])
1516 return isl_space_reset(dim
, isl_dim_in
);
1519 __isl_give isl_space
*isl_space_flatten_range(__isl_take isl_space
*dim
)
1523 if (!dim
->nested
[1])
1526 return isl_space_reset(dim
, isl_dim_out
);
1529 /* Replace the dimensions of the given type of dst by those of src.
1531 __isl_give isl_space
*isl_space_replace(__isl_take isl_space
*dst
,
1532 enum isl_dim_type type
, __isl_keep isl_space
*src
)
1534 dst
= isl_space_cow(dst
);
1539 dst
= isl_space_drop_dims(dst
, type
, 0, isl_space_dim(dst
, type
));
1540 dst
= isl_space_add_dims(dst
, type
, isl_space_dim(src
, type
));
1541 dst
= copy_ids(dst
, type
, 0, src
, type
);
1543 if (dst
&& type
== isl_dim_param
) {
1545 for (i
= 0; i
<= 1; ++i
) {
1546 if (!dst
->nested
[i
])
1548 dst
->nested
[i
] = isl_space_replace(dst
->nested
[i
],
1550 if (!dst
->nested
[i
])
1557 isl_space_free(dst
);
1561 /* Given a dimension specification "dim" of a set, create a dimension
1562 * specification for the lift of the set. In particular, the result
1563 * is of the form [dim -> local[..]], with n_local variables in the
1564 * range of the wrapped map.
1566 __isl_give isl_space
*isl_space_lift(__isl_take isl_space
*dim
, unsigned n_local
)
1568 isl_space
*local_dim
;
1573 local_dim
= isl_space_dup(dim
);
1574 local_dim
= isl_space_drop_dims(local_dim
, isl_dim_set
, 0, dim
->n_out
);
1575 local_dim
= isl_space_add_dims(local_dim
, isl_dim_set
, n_local
);
1576 local_dim
= isl_space_set_tuple_name(local_dim
, isl_dim_set
, "local");
1577 dim
= isl_space_join(isl_space_from_domain(dim
),
1578 isl_space_from_range(local_dim
));
1579 dim
= isl_space_wrap(dim
);
1580 dim
= isl_space_set_tuple_name(dim
, isl_dim_set
, "lifted");
1585 int isl_space_can_zip(__isl_keep isl_space
*dim
)
1590 return dim
->nested
[0] && dim
->nested
[1];
1593 __isl_give isl_space
*isl_space_zip(__isl_take isl_space
*dim
)
1595 isl_space
*dom
, *ran
;
1596 isl_space
*dom_dom
, *dom_ran
, *ran_dom
, *ran_ran
;
1598 if (!isl_space_can_zip(dim
))
1599 isl_die(dim
->ctx
, isl_error_invalid
, "dim cannot be zipped",
1604 dom
= isl_space_unwrap(isl_space_domain(isl_space_copy(dim
)));
1605 ran
= isl_space_unwrap(isl_space_range(dim
));
1606 dom_dom
= isl_space_domain(isl_space_copy(dom
));
1607 dom_ran
= isl_space_range(dom
);
1608 ran_dom
= isl_space_domain(isl_space_copy(ran
));
1609 ran_ran
= isl_space_range(ran
);
1610 dom
= isl_space_join(isl_space_from_domain(dom_dom
),
1611 isl_space_from_range(ran_dom
));
1612 ran
= isl_space_join(isl_space_from_domain(dom_ran
),
1613 isl_space_from_range(ran_ran
));
1614 return isl_space_join(isl_space_from_domain(isl_space_wrap(dom
)),
1615 isl_space_from_range(isl_space_wrap(ran
)));
1617 isl_space_free(dim
);
1621 int isl_space_has_named_params(__isl_keep isl_space
*dim
)
1628 if (dim
->nparam
== 0)
1630 off
= isl_space_offset(dim
, isl_dim_param
);
1631 if (off
+ dim
->nparam
> dim
->n_id
)
1633 for (i
= 0; i
< dim
->nparam
; ++i
)
1634 if (!dim
->ids
[off
+ i
])
1639 /* Align the initial parameters of dim1 to match the order in dim2.
1641 __isl_give isl_space
*isl_space_align_params(__isl_take isl_space
*dim1
,
1642 __isl_take isl_space
*dim2
)
1644 isl_reordering
*exp
;
1646 if (!isl_space_has_named_params(dim1
) || !isl_space_has_named_params(dim2
))
1647 isl_die(isl_space_get_ctx(dim1
), isl_error_invalid
,
1648 "parameter alignment requires named parameters",
1651 dim2
= isl_space_params(dim2
);
1652 exp
= isl_parameter_alignment_reordering(dim1
, dim2
);
1653 exp
= isl_reordering_extend_space(exp
, dim1
);
1654 isl_space_free(dim2
);
1657 dim1
= isl_space_copy(exp
->dim
);
1658 isl_reordering_free(exp
);
1661 isl_space_free(dim1
);
1662 isl_space_free(dim2
);
1666 /* Given the space of set (domain), construct a space for a map
1667 * with as domain the given space and as range the range of "model".
1669 __isl_give isl_space
*isl_space_extend_domain_with_range(
1670 __isl_take isl_space
*domain
, __isl_take isl_space
*model
)
1674 space
= isl_space_from_domain(domain
);
1675 space
= isl_space_add_dims(space
, isl_dim_out
,
1676 isl_space_dim(model
, isl_dim_out
));
1677 if (isl_space_has_tuple_id(model
, isl_dim_out
))
1678 space
= isl_space_set_tuple_id(space
, isl_dim_out
,
1679 isl_space_get_tuple_id(model
, isl_dim_out
));
1680 isl_space_free(model
);