2 * Copyright 2011 Sven Verdoolaege
3 * Copyright 2012-2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11 #include <isl_space_private.h>
13 #include <isl_reordering.h>
15 #define xCAT(A,B) A ## B
16 #define CAT(A,B) xCAT(A,B)
18 #define EL CAT(isl_,BASE)
19 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
20 #define FN(TYPE,NAME) xFN(TYPE,NAME)
21 #define xMULTI(BASE) isl_multi_ ## BASE
22 #define MULTI(BASE) xMULTI(BASE)
23 #define MULTI_NAME(BASE) "isl_multi_" #BASE
24 #define xLIST(EL) EL ## _list
25 #define LIST(EL) xLIST(EL)
27 isl_ctx
*FN(MULTI(BASE
),get_ctx
)(__isl_keep
MULTI(BASE
) *multi
)
29 return multi
? isl_space_get_ctx(multi
->space
) : NULL
;
32 __isl_give isl_space
*FN(MULTI(BASE
),get_space
)(__isl_keep
MULTI(BASE
) *multi
)
34 return multi
? isl_space_copy(multi
->space
) : NULL
;
37 __isl_give isl_space
*FN(MULTI(BASE
),get_domain_space
)(
38 __isl_keep
MULTI(BASE
) *multi
)
40 return multi
? isl_space_domain(isl_space_copy(multi
->space
)) : NULL
;
43 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),alloc
)(__isl_take isl_space
*space
)
52 ctx
= isl_space_get_ctx(space
);
53 n
= isl_space_dim(space
, isl_dim_out
);
54 multi
= isl_calloc(ctx
, MULTI(BASE
),
55 sizeof(MULTI(BASE
)) + (n
- 1) * sizeof(struct EL
*));
64 isl_space_free(space
);
68 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),dup
)(__isl_keep
MULTI(BASE
) *multi
)
76 dup
= FN(MULTI(BASE
),alloc
)(isl_space_copy(multi
->space
));
80 for (i
= 0; i
< multi
->n
; ++i
)
81 dup
= FN(FN(MULTI(BASE
),set
),BASE
)(dup
, i
,
82 FN(EL
,copy
)(multi
->p
[i
]));
87 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),cow
)(__isl_take
MULTI(BASE
) *multi
)
96 return FN(MULTI(BASE
),dup
)(multi
);
99 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),copy
)(__isl_keep
MULTI(BASE
) *multi
)
108 void *FN(MULTI(BASE
),free
)(__isl_take
MULTI(BASE
) *multi
)
115 if (--multi
->ref
> 0)
118 isl_space_free(multi
->space
);
119 for (i
= 0; i
< multi
->n
; ++i
)
120 FN(EL
,free
)(multi
->p
[i
]);
126 /* Check whether "multi" has non-zero coefficients for any dimension
127 * in the given range or if any of these dimensions appear
128 * with non-zero coefficients in any of the integer divisions involved.
130 int FN(MULTI(BASE
),involves_dims
)(__isl_keep
MULTI(BASE
) *multi
,
131 enum isl_dim_type type
, unsigned first
, unsigned n
)
137 if (multi
->n
== 0 || n
== 0)
140 for (i
= 0; i
< multi
->n
; ++i
) {
143 involves
= FN(EL
,involves_dims
)(multi
->p
[i
], type
, first
, n
);
144 if (involves
< 0 || involves
)
151 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),insert_dims
)(
152 __isl_take
MULTI(BASE
) *multi
,
153 enum isl_dim_type type
, unsigned first
, unsigned n
)
159 if (type
== isl_dim_out
)
160 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
161 "cannot insert output/set dimensions",
162 return FN(MULTI(BASE
),free
)(multi
));
163 if (n
== 0 && !isl_space_is_named_or_nested(multi
->space
, type
))
166 multi
= FN(MULTI(BASE
),cow
)(multi
);
170 multi
->space
= isl_space_insert_dims(multi
->space
, type
, first
, n
);
172 return FN(MULTI(BASE
),free
)(multi
);
174 for (i
= 0; i
< multi
->n
; ++i
) {
175 multi
->p
[i
] = FN(EL
,insert_dims
)(multi
->p
[i
], type
, first
, n
);
177 return FN(MULTI(BASE
),free
)(multi
);
183 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),add_dims
)(__isl_take
MULTI(BASE
) *multi
,
184 enum isl_dim_type type
, unsigned n
)
188 pos
= FN(MULTI(BASE
),dim
)(multi
, type
);
190 return FN(MULTI(BASE
),insert_dims
)(multi
, type
, pos
, n
);
193 unsigned FN(MULTI(BASE
),dim
)(__isl_keep
MULTI(BASE
) *multi
,
194 enum isl_dim_type type
)
196 return multi
? isl_space_dim(multi
->space
, type
) : 0;
199 /* Return the position of the first dimension of "type" with id "id".
200 * Return -1 if there is no such dimension.
202 int FN(MULTI(BASE
),find_dim_by_id
)(__isl_keep
MULTI(BASE
) *multi
,
203 enum isl_dim_type type
, __isl_keep isl_id
*id
)
207 return isl_space_find_dim_by_id(multi
->space
, type
, id
);
210 /* Return the id of the given dimension.
212 __isl_give isl_id
*FN(MULTI(BASE
),get_dim_id
)(__isl_keep
MULTI(BASE
) *multi
,
213 enum isl_dim_type type
, unsigned pos
)
215 return multi
? isl_space_get_dim_id(multi
->space
, type
, pos
) : NULL
;
218 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_dim_name
)(
219 __isl_take
MULTI(BASE
) *multi
,
220 enum isl_dim_type type
, unsigned pos
, const char *s
)
224 multi
= FN(MULTI(BASE
),cow
)(multi
);
228 multi
->space
= isl_space_set_dim_name(multi
->space
, type
, pos
, s
);
230 return FN(MULTI(BASE
),free
)(multi
);
232 if (type
== isl_dim_out
)
234 for (i
= 0; i
< multi
->n
; ++i
) {
235 multi
->p
[i
] = FN(EL
,set_dim_name
)(multi
->p
[i
], type
, pos
, s
);
237 return FN(MULTI(BASE
),free
)(multi
);
243 const char *FN(MULTI(BASE
),get_tuple_name
)(__isl_keep
MULTI(BASE
) *multi
,
244 enum isl_dim_type type
)
246 return multi
? isl_space_get_tuple_name(multi
->space
, type
) : NULL
;
249 /* Does the specified tuple have an id?
251 int FN(MULTI(BASE
),has_tuple_id
)(__isl_keep
MULTI(BASE
) *multi
,
252 enum isl_dim_type type
)
254 return multi
? isl_space_has_tuple_id(multi
->space
, type
) : -1;
257 /* Return the id of the specified tuple.
259 __isl_give isl_id
*FN(MULTI(BASE
),get_tuple_id
)(__isl_keep
MULTI(BASE
) *multi
,
260 enum isl_dim_type type
)
262 return multi
? isl_space_get_tuple_id(multi
->space
, type
) : NULL
;
265 __isl_give EL
*FN(FN(MULTI(BASE
),get
),BASE
)(__isl_keep
MULTI(BASE
) *multi
,
272 ctx
= FN(MULTI(BASE
),get_ctx
)(multi
);
273 if (pos
< 0 || pos
>= multi
->n
)
274 isl_die(ctx
, isl_error_invalid
,
275 "index out of bounds", return NULL
);
276 return FN(EL
,copy
)(multi
->p
[pos
]);
279 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),set
),BASE
)(
280 __isl_take
MULTI(BASE
) *multi
, int pos
, __isl_take EL
*el
)
282 isl_space
*multi_space
= NULL
;
283 isl_space
*el_space
= NULL
;
286 multi
= FN(MULTI(BASE
),cow
)(multi
);
290 multi_space
= FN(MULTI(BASE
),get_space
)(multi
);
291 match
= FN(EL
,matching_params
)(el
, multi_space
);
295 multi
= FN(MULTI(BASE
),align_params
)(multi
,
296 FN(EL
,get_space
)(el
));
297 isl_space_free(multi_space
);
298 multi_space
= FN(MULTI(BASE
),get_space
)(multi
);
299 el
= FN(EL
,align_params
)(el
, isl_space_copy(multi_space
));
301 if (FN(EL
,check_match_domain_space
)(el
, multi_space
) < 0)
304 if (pos
< 0 || pos
>= multi
->n
)
305 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
306 "index out of bounds", goto error
);
308 FN(EL
,free
)(multi
->p
[pos
]);
311 isl_space_free(multi_space
);
312 isl_space_free(el_space
);
316 FN(MULTI(BASE
),free
)(multi
);
318 isl_space_free(multi_space
);
319 isl_space_free(el_space
);
323 /* Reset the space of "multi". This function is called from isl_pw_templ.c
324 * and doesn't know if the space of an element object is represented
325 * directly or through its domain. It therefore passes along both,
326 * which we pass along to the element function since we don't how
327 * that is represented either.
329 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_space_and_domain
)(
330 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*space
,
331 __isl_take isl_space
*domain
)
335 multi
= FN(MULTI(BASE
),cow
)(multi
);
336 if (!multi
|| !space
|| !domain
)
339 for (i
= 0; i
< multi
->n
; ++i
) {
340 multi
->p
[i
] = FN(EL
,reset_domain_space
)(multi
->p
[i
],
341 isl_space_copy(domain
));
345 isl_space_free(domain
);
346 isl_space_free(multi
->space
);
347 multi
->space
= space
;
351 isl_space_free(domain
);
352 isl_space_free(space
);
353 FN(MULTI(BASE
),free
)(multi
);
357 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_domain_space
)(
358 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*domain
)
362 space
= isl_space_extend_domain_with_range(isl_space_copy(domain
),
363 isl_space_copy(multi
->space
));
364 return FN(MULTI(BASE
),reset_space_and_domain
)(multi
, space
, domain
);
367 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_space
)(
368 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*space
)
372 domain
= isl_space_domain(isl_space_copy(space
));
373 return FN(MULTI(BASE
),reset_space_and_domain
)(multi
, space
, domain
);
376 /* Set the id of the given dimension of "multi" to "id".
378 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_dim_id
)(
379 __isl_take
MULTI(BASE
) *multi
,
380 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
384 multi
= FN(MULTI(BASE
),cow
)(multi
);
388 space
= FN(MULTI(BASE
),get_space
)(multi
);
389 space
= isl_space_set_dim_id(space
, type
, pos
, id
);
391 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
394 FN(MULTI(BASE
),free
)(multi
);
398 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_tuple_name
)(
399 __isl_keep
MULTI(BASE
) *multi
, enum isl_dim_type type
,
404 multi
= FN(MULTI(BASE
),cow
)(multi
);
408 space
= FN(MULTI(BASE
),get_space
)(multi
);
409 space
= isl_space_set_tuple_name(space
, type
, s
);
411 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
414 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_tuple_id
)(
415 __isl_take
MULTI(BASE
) *multi
, enum isl_dim_type type
,
416 __isl_take isl_id
*id
)
420 multi
= FN(MULTI(BASE
),cow
)(multi
);
422 return isl_id_free(id
);
424 space
= FN(MULTI(BASE
),get_space
)(multi
);
425 space
= isl_space_set_tuple_id(space
, type
, id
);
427 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
430 /* Drop the id on the specified tuple.
432 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_tuple_id
)(
433 __isl_take
MULTI(BASE
) *multi
, enum isl_dim_type type
)
439 if (!FN(MULTI(BASE
),has_tuple_id
)(multi
, type
))
442 multi
= FN(MULTI(BASE
),cow
)(multi
);
446 space
= FN(MULTI(BASE
),get_space
)(multi
);
447 space
= isl_space_reset_tuple_id(space
, type
);
449 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
452 /* Reset the user pointer on all identifiers of parameters and tuples
453 * of the space of "multi".
455 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_user
)(
456 __isl_take
MULTI(BASE
) *multi
)
460 space
= FN(MULTI(BASE
),get_space
)(multi
);
461 space
= isl_space_reset_user(space
);
463 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
466 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),realign_domain
)(
467 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_reordering
*exp
)
471 multi
= FN(MULTI(BASE
),cow
)(multi
);
475 for (i
= 0; i
< multi
->n
; ++i
) {
476 multi
->p
[i
] = FN(EL
,realign_domain
)(multi
->p
[i
],
477 isl_reordering_copy(exp
));
482 multi
= FN(MULTI(BASE
),reset_domain_space
)(multi
,
483 isl_space_copy(exp
->dim
));
485 isl_reordering_free(exp
);
488 isl_reordering_free(exp
);
489 FN(MULTI(BASE
),free
)(multi
);
493 /* Align the parameters of "multi" to those of "model".
495 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),align_params
)(
496 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*model
)
500 if (!multi
|| !model
)
503 ctx
= isl_space_get_ctx(model
);
504 if (!isl_space_has_named_params(model
))
505 isl_die(ctx
, isl_error_invalid
,
506 "model has unnamed parameters", goto error
);
507 if (!isl_space_has_named_params(multi
->space
))
508 isl_die(ctx
, isl_error_invalid
,
509 "input has unnamed parameters", goto error
);
510 if (!isl_space_match(multi
->space
, isl_dim_param
,
511 model
, isl_dim_param
)) {
514 model
= isl_space_params(model
);
515 exp
= isl_parameter_alignment_reordering(multi
->space
, model
);
516 exp
= isl_reordering_extend_space(exp
,
517 FN(MULTI(BASE
),get_domain_space
)(multi
));
518 multi
= FN(MULTI(BASE
),realign_domain
)(multi
, exp
);
521 isl_space_free(model
);
524 isl_space_free(model
);
525 FN(MULTI(BASE
),free
)(multi
);
529 #if !defined(NO_GIST) || !defined(NO_INTERSECT_DOMAIN)
530 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),align_params_multi_set_and
)(
531 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*set
,
532 __isl_give
MULTI(BASE
) *(*fn
)(__isl_take
MULTI(BASE
) *multi
,
533 __isl_take isl_set
*set
))
539 if (isl_space_match(multi
->space
, isl_dim_param
,
540 set
->dim
, isl_dim_param
))
541 return fn(multi
, set
);
542 ctx
= FN(MULTI(BASE
),get_ctx
)(multi
);
543 if (!isl_space_has_named_params(multi
->space
) ||
544 !isl_space_has_named_params(set
->dim
))
545 isl_die(ctx
, isl_error_invalid
,
546 "unaligned unnamed parameters", goto error
);
547 multi
= FN(MULTI(BASE
),align_params
)(multi
, isl_set_get_space(set
));
548 set
= isl_set_align_params(set
, FN(MULTI(BASE
),get_space
)(multi
));
549 return fn(multi
, set
);
551 FN(MULTI(BASE
),free
)(multi
);
558 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),gist_aligned
)(
559 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*context
)
563 multi
= FN(MULTI(BASE
),cow
)(multi
);
564 if (!multi
|| !context
)
567 for (i
= 0; i
< multi
->n
; ++i
) {
568 multi
->p
[i
] = FN(EL
,gist
)(multi
->p
[i
], isl_set_copy(context
));
573 isl_set_free(context
);
576 isl_set_free(context
);
577 FN(MULTI(BASE
),free
)(multi
);
581 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),gist
)(__isl_take
MULTI(BASE
) *multi
,
582 __isl_take isl_set
*context
)
584 return FN(MULTI(BASE
),align_params_multi_set_and
)(multi
, context
,
585 &FN(MULTI(BASE
),gist_aligned
));
588 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),gist_params
)(
589 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*context
)
591 isl_space
*space
= FN(MULTI(BASE
),get_domain_space
)(multi
);
592 isl_set
*dom_context
= isl_set_universe(space
);
593 dom_context
= isl_set_intersect_params(dom_context
, context
);
594 return FN(MULTI(BASE
),gist
)(multi
, dom_context
);
598 #ifndef NO_INTERSECT_DOMAIN
599 /* Transform the domain of "multi" by combining it with "domain"
602 * The parameters of "multi" and "domain" are assumed to have been aligned.
604 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),intersect_aligned
)(
605 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*domain
,
606 __isl_give EL
*(*fn
)(EL
*el
, __isl_take isl_set
*set2
))
610 if (!multi
|| !domain
)
614 isl_set_free(domain
);
618 multi
= FN(MULTI(BASE
),cow
)(multi
);
622 for (i
= 0; i
< multi
->n
; ++i
) {
623 multi
->p
[i
] = fn(multi
->p
[i
], isl_set_copy(domain
));
628 isl_set_free(domain
);
631 isl_set_free(domain
);
632 FN(MULTI(BASE
),free
)(multi
);
636 /* Intersect the domain of "multi" with "domain".
638 * The parameters of "multi" and "domain" are assumed to have been aligned.
640 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),intersect_domain_aligned
)(
641 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*domain
)
643 return FN(MULTI(BASE
),intersect_aligned
)(multi
, domain
,
644 &FN(EL
,intersect_domain
));
647 /* Intersect the domain of "multi" with "domain".
649 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),intersect_domain
)(
650 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*domain
)
652 return FN(MULTI(BASE
),align_params_multi_set_and
)(multi
, domain
,
653 &FN(MULTI(BASE
),intersect_domain_aligned
));
656 /* Intersect the parameter domain of "multi" with "domain".
658 * The parameters of "multi" and "domain" are assumed to have been aligned.
660 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),intersect_params_aligned
)(
661 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*domain
)
663 return FN(MULTI(BASE
),intersect_aligned
)(multi
, domain
,
664 &FN(EL
,intersect_params
));
667 /* Intersect the parameter domain of "multi" with "domain".
669 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),intersect_params
)(
670 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_set
*domain
)
672 return FN(MULTI(BASE
),align_params_multi_set_and
)(multi
, domain
,
673 &FN(MULTI(BASE
),intersect_params_aligned
));
677 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),from
),LIST(BASE
))(
678 __isl_take isl_space
*space
, __isl_take
LIST(EL
) *list
)
688 ctx
= isl_space_get_ctx(space
);
689 n
= FN(FN(LIST(EL
),n
),BASE
)(list
);
690 if (n
!= isl_space_dim(space
, isl_dim_out
))
691 isl_die(ctx
, isl_error_invalid
,
692 "invalid number of elements in list", goto error
);
694 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
695 for (i
= 0; i
< n
; ++i
) {
696 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
,
697 FN(FN(LIST(EL
),get
),BASE
)(list
, i
));
700 isl_space_free(space
);
701 FN(LIST(EL
),free
)(list
);
704 isl_space_free(space
);
705 FN(LIST(EL
),free
)(list
);
710 /* Create a multi expression in the given space that maps each
711 * input dimension to the corresponding output dimension.
713 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),identity
)(__isl_take isl_space
*space
)
722 if (isl_space_is_set(space
))
723 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
724 "expecting map space", goto error
);
726 n
= isl_space_dim(space
, isl_dim_out
);
727 if (n
!= isl_space_dim(space
, isl_dim_in
))
728 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
729 "number of input and output dimensions needs to be "
730 "the same", goto error
);
732 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
735 isl_space_free(space
);
739 space
= isl_space_domain(space
);
740 ls
= isl_local_space_from_space(space
);
742 for (i
= 0; i
< n
; ++i
) {
744 el
= FN(EL
,var_on_domain
)(isl_local_space_copy(ls
),
746 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
, el
);
749 isl_local_space_free(ls
);
753 isl_space_free(space
);
758 /* Construct a multi expression in the given space with value zero in
759 * each of the output dimensions.
761 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),zero
)(__isl_take isl_space
*space
)
769 n
= isl_space_dim(space
, isl_dim_out
);
770 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
773 isl_space_free(space
);
779 space
= isl_space_domain(space
);
780 ls
= isl_local_space_from_space(space
);
781 el
= FN(EL
,zero_on_domain
)(ls
);
783 for (i
= 0; i
< n
; ++i
)
784 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
,
794 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),from
),BASE
)(__isl_take EL
*el
)
798 multi
= FN(MULTI(BASE
),alloc
)(FN(EL
,get_space
)(el
));
799 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, 0, el
);
805 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),drop_dims
)(
806 __isl_take
MULTI(BASE
) *multi
,
807 enum isl_dim_type type
, unsigned first
, unsigned n
)
812 multi
= FN(MULTI(BASE
),cow
)(multi
);
816 dim
= FN(MULTI(BASE
),dim
)(multi
, type
);
817 if (first
+ n
> dim
|| first
+ n
< first
)
818 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
819 "index out of bounds",
820 return FN(MULTI(BASE
),cow
)(multi
));
822 multi
->space
= isl_space_drop_dims(multi
->space
, type
, first
, n
);
824 return FN(MULTI(BASE
),cow
)(multi
);
826 if (type
== isl_dim_out
) {
827 for (i
= 0; i
< n
; ++i
)
828 FN(EL
,free
)(multi
->p
[first
+ i
]);
829 for (i
= first
; i
+ n
< multi
->n
; ++i
)
830 multi
->p
[i
] = multi
->p
[i
+ n
];
836 for (i
= 0; i
< multi
->n
; ++i
) {
837 multi
->p
[i
] = FN(EL
,drop_dims
)(multi
->p
[i
], type
, first
, n
);
839 return FN(MULTI(BASE
),cow
)(multi
);
845 /* Align the parameters of "multi1" and "multi2" (if needed) and call "fn".
847 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),align_params_multi_multi_and
)(
848 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
849 __isl_give
MULTI(BASE
) *(*fn
)(__isl_take
MULTI(BASE
) *multi1
,
850 __isl_take
MULTI(BASE
) *multi2
))
854 if (!multi1
|| !multi2
)
856 if (isl_space_match(multi1
->space
, isl_dim_param
,
857 multi2
->space
, isl_dim_param
))
858 return fn(multi1
, multi2
);
859 ctx
= FN(MULTI(BASE
),get_ctx
)(multi1
);
860 if (!isl_space_has_named_params(multi1
->space
) ||
861 !isl_space_has_named_params(multi2
->space
))
862 isl_die(ctx
, isl_error_invalid
,
863 "unaligned unnamed parameters", goto error
);
864 multi1
= FN(MULTI(BASE
),align_params
)(multi1
,
865 FN(MULTI(BASE
),get_space
)(multi2
));
866 multi2
= FN(MULTI(BASE
),align_params
)(multi2
,
867 FN(MULTI(BASE
),get_space
)(multi1
));
868 return fn(multi1
, multi2
);
870 FN(MULTI(BASE
),free
)(multi1
);
871 FN(MULTI(BASE
),free
)(multi2
);
875 /* Given two MULTI(BASE)s A -> B and C -> D,
876 * construct a MULTI(BASE) (A * C) -> [B -> D].
878 * The parameters are assumed to have been aligned.
880 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_product_aligned
)(
881 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
888 if (!multi1
|| !multi2
)
891 space
= isl_space_range_product(FN(MULTI(BASE
),get_space
)(multi1
),
892 FN(MULTI(BASE
),get_space
)(multi2
));
893 res
= FN(MULTI(BASE
),alloc
)(space
);
895 n1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
896 n2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_out
);
898 for (i
= 0; i
< n1
; ++i
) {
899 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi1
, i
);
900 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, i
, el
);
903 for (i
= 0; i
< n2
; ++i
) {
904 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi2
, i
);
905 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, n1
+ i
, el
);
908 FN(MULTI(BASE
),free
)(multi1
);
909 FN(MULTI(BASE
),free
)(multi2
);
912 FN(MULTI(BASE
),free
)(multi1
);
913 FN(MULTI(BASE
),free
)(multi2
);
917 /* Given two MULTI(BASE)s A -> B and C -> D,
918 * construct a MULTI(BASE) (A * C) -> [B -> D].
920 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_product
)(
921 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
923 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
924 &FN(MULTI(BASE
),range_product_aligned
));
927 /* Is the range of "multi" a wrapped relation?
929 int FN(MULTI(BASE
),range_is_wrapping
)(__isl_keep
MULTI(BASE
) *multi
)
933 return isl_space_range_is_wrapping(multi
->space
);
936 /* Given a function A -> [B -> C], extract the function A -> B.
938 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_factor_domain
)(
939 __isl_take
MULTI(BASE
) *multi
)
946 if (!isl_space_range_is_wrapping(multi
->space
))
947 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
948 "range is not a product",
949 return FN(MULTI(BASE
),free
)(multi
));
951 space
= FN(MULTI(BASE
),get_space
)(multi
);
952 total
= isl_space_dim(space
, isl_dim_out
);
953 space
= isl_space_range_factor_domain(space
);
954 keep
= isl_space_dim(space
, isl_dim_out
);
955 multi
= FN(MULTI(BASE
),drop_dims
)(multi
,
956 isl_dim_out
, keep
, total
- keep
);
957 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
962 /* Given a function A -> [B -> C], extract the function A -> C.
964 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_factor_range
)(
965 __isl_take
MULTI(BASE
) *multi
)
972 if (!isl_space_range_is_wrapping(multi
->space
))
973 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
974 "range is not a product",
975 return FN(MULTI(BASE
),free
)(multi
));
977 space
= FN(MULTI(BASE
),get_space
)(multi
);
978 total
= isl_space_dim(space
, isl_dim_out
);
979 space
= isl_space_range_factor_range(space
);
980 keep
= isl_space_dim(space
, isl_dim_out
);
981 multi
= FN(MULTI(BASE
),drop_dims
)(multi
, isl_dim_out
, 0, total
- keep
);
982 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
987 /* Given two MULTI(BASE)s A -> B and C -> D,
988 * construct a MULTI(BASE) [A -> C] -> [B -> D].
990 * The parameters are assumed to have been aligned.
992 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),product_aligned
)(
993 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
999 int in1
, in2
, out1
, out2
;
1001 in1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_in
);
1002 in2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_in
);
1003 out1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
1004 out2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_out
);
1005 space
= isl_space_product(FN(MULTI(BASE
),get_space
)(multi1
),
1006 FN(MULTI(BASE
),get_space
)(multi2
));
1007 res
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
1008 space
= isl_space_domain(space
);
1010 for (i
= 0; i
< out1
; ++i
) {
1011 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi1
, i
);
1012 el
= FN(EL
,insert_dims
)(el
, isl_dim_in
, in1
, in2
);
1013 el
= FN(EL
,reset_domain_space
)(el
, isl_space_copy(space
));
1014 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, i
, el
);
1017 for (i
= 0; i
< out2
; ++i
) {
1018 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi2
, i
);
1019 el
= FN(EL
,insert_dims
)(el
, isl_dim_in
, 0, in1
);
1020 el
= FN(EL
,reset_domain_space
)(el
, isl_space_copy(space
));
1021 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, out1
+ i
, el
);
1024 isl_space_free(space
);
1025 FN(MULTI(BASE
),free
)(multi1
);
1026 FN(MULTI(BASE
),free
)(multi2
);
1030 /* Given two MULTI(BASE)s A -> B and C -> D,
1031 * construct a MULTI(BASE) [A -> C] -> [B -> D].
1033 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),product
)(
1034 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
1036 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
1037 &FN(MULTI(BASE
),product_aligned
));
1040 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),flatten_range
)(
1041 __isl_take
MULTI(BASE
) *multi
)
1046 if (!multi
->space
->nested
[1])
1049 multi
= FN(MULTI(BASE
),cow
)(multi
);
1053 multi
->space
= isl_space_flatten_range(multi
->space
);
1055 return FN(MULTI(BASE
),free
)(multi
);
1060 /* Given two MULTI(BASE)s A -> B and C -> D,
1061 * construct a MULTI(BASE) (A * C) -> (B, D).
1063 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),flat_range_product
)(
1064 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
1068 multi
= FN(MULTI(BASE
),range_product
)(multi1
, multi2
);
1069 multi
= FN(MULTI(BASE
),flatten_range
)(multi
);
1073 /* Given two multi expressions, "multi1"
1077 * where B2 starts at position "pos", and "multi2"
1081 * return the multi expression
1085 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_splice
)(
1086 __isl_take
MULTI(BASE
) *multi1
, unsigned pos
,
1087 __isl_take
MULTI(BASE
) *multi2
)
1092 if (!multi1
|| !multi2
)
1095 dim
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
1097 isl_die(FN(MULTI(BASE
),get_ctx
)(multi1
), isl_error_invalid
,
1098 "index out of bounds", goto error
);
1100 res
= FN(MULTI(BASE
),copy
)(multi1
);
1101 res
= FN(MULTI(BASE
),drop_dims
)(res
, isl_dim_out
, pos
, dim
- pos
);
1102 multi1
= FN(MULTI(BASE
),drop_dims
)(multi1
, isl_dim_out
, 0, pos
);
1104 res
= FN(MULTI(BASE
),flat_range_product
)(res
, multi2
);
1105 res
= FN(MULTI(BASE
),flat_range_product
)(res
, multi1
);
1109 FN(MULTI(BASE
),free
)(multi1
);
1110 FN(MULTI(BASE
),free
)(multi2
);
1114 /* Given two multi expressions, "multi1"
1116 * [A1 A2] -> [B1 B2]
1118 * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
1123 * return the multi expression
1125 * [A1 C A2] -> [B1 D B2]
1127 * We first insert input dimensions to obtain
1129 * [A1 C A2] -> [B1 B2]
1135 * and then apply range_splice.
1137 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),splice
)(
1138 __isl_take
MULTI(BASE
) *multi1
, unsigned in_pos
, unsigned out_pos
,
1139 __isl_take
MULTI(BASE
) *multi2
)
1144 if (!multi1
|| !multi2
)
1147 n_in1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_in
);
1149 isl_die(FN(MULTI(BASE
),get_ctx
)(multi1
), isl_error_invalid
,
1150 "index out of bounds", goto error
);
1152 n_in2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_in
);
1154 multi1
= FN(MULTI(BASE
),insert_dims
)(multi1
, isl_dim_in
, in_pos
, n_in2
);
1155 multi2
= FN(MULTI(BASE
),insert_dims
)(multi2
, isl_dim_in
, n_in2
,
1157 multi2
= FN(MULTI(BASE
),insert_dims
)(multi2
, isl_dim_in
, 0, in_pos
);
1159 return FN(MULTI(BASE
),range_splice
)(multi1
, out_pos
, multi2
);
1161 FN(MULTI(BASE
),free
)(multi1
);
1162 FN(MULTI(BASE
),free
)(multi2
);
1166 /* This function is currently only used from isl_aff.c
1168 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),bin_op
)(
1169 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
1170 __isl_give EL
*(*fn
)(__isl_take EL
*, __isl_take EL
*))
1171 __attribute__ ((unused
));
1173 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
1174 * return the result.
1176 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),bin_op
)(
1177 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
1178 __isl_give EL
*(*fn
)(__isl_take EL
*, __isl_take EL
*))
1183 multi1
= FN(MULTI(BASE
),cow
)(multi1
);
1184 if (!multi1
|| !multi2
)
1187 ctx
= FN(MULTI(BASE
),get_ctx
)(multi1
);
1188 if (!isl_space_is_equal(multi1
->space
, multi2
->space
))
1189 isl_die(ctx
, isl_error_invalid
,
1190 "spaces don't match", goto error
);
1192 for (i
= 0; i
< multi1
->n
; ++i
) {
1193 multi1
->p
[i
] = fn(multi1
->p
[i
], FN(EL
,copy
)(multi2
->p
[i
]));
1198 FN(MULTI(BASE
),free
)(multi2
);
1201 FN(MULTI(BASE
),free
)(multi1
);
1202 FN(MULTI(BASE
),free
)(multi2
);
1206 /* Multiply the elements of "multi" by "v" and return the result.
1208 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_val
)(__isl_take
MULTI(BASE
) *multi
,
1209 __isl_take isl_val
*v
)
1216 if (isl_val_is_one(v
)) {
1221 if (!isl_val_is_rat(v
))
1222 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1223 "expecting rational factor", goto error
);
1225 multi
= FN(MULTI(BASE
),cow
)(multi
);
1229 for (i
= 0; i
< multi
->n
; ++i
) {
1230 multi
->p
[i
] = FN(EL
,scale_val
)(multi
->p
[i
], isl_val_copy(v
));
1239 return FN(MULTI(BASE
),free
)(multi
);
1242 /* Multiply the elements of "multi" by the corresponding element of "mv"
1243 * and return the result.
1245 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_multi_val
)(
1246 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1253 if (!isl_space_tuple_match(multi
->space
, isl_dim_out
,
1254 mv
->space
, isl_dim_set
))
1255 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1256 "spaces don't match", goto error
);
1258 multi
= FN(MULTI(BASE
),cow
)(multi
);
1262 for (i
= 0; i
< multi
->n
; ++i
) {
1265 v
= isl_multi_val_get_val(mv
, i
);
1266 multi
->p
[i
] = FN(EL
,scale_val
)(multi
->p
[i
], v
);
1271 isl_multi_val_free(mv
);
1274 isl_multi_val_free(mv
);
1275 return FN(MULTI(BASE
),free
)(multi
);
1278 /* Divide the elements of "multi" by the corresponding element of "mv"
1279 * and return the result.
1281 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_down_multi_val
)(
1282 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1289 if (!isl_space_tuple_match(multi
->space
, isl_dim_out
,
1290 mv
->space
, isl_dim_set
))
1291 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1292 "spaces don't match", goto error
);
1294 multi
= FN(MULTI(BASE
),cow
)(multi
);
1298 for (i
= 0; i
< multi
->n
; ++i
) {
1301 v
= isl_multi_val_get_val(mv
, i
);
1302 multi
->p
[i
] = FN(EL
,scale_down_val
)(multi
->p
[i
], v
);
1307 isl_multi_val_free(mv
);
1310 isl_multi_val_free(mv
);
1311 return FN(MULTI(BASE
),free
)(multi
);
1314 #ifndef NO_MOVE_DIMS
1315 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "multi"
1316 * to dimensions of "dst_type" at "dst_pos".
1318 * We only support moving input dimensions to parameters and vice versa.
1320 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),move_dims
)(__isl_take
MULTI(BASE
) *multi
,
1321 enum isl_dim_type dst_type
, unsigned dst_pos
,
1322 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1330 !isl_space_is_named_or_nested(multi
->space
, src_type
) &&
1331 !isl_space_is_named_or_nested(multi
->space
, dst_type
))
1334 if (dst_type
== isl_dim_out
|| src_type
== isl_dim_out
)
1335 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1336 "cannot move output/set dimension",
1337 return FN(MULTI(BASE
),free
)(multi
));
1338 if (dst_type
== isl_dim_div
|| src_type
== isl_dim_div
)
1339 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1341 return FN(MULTI(BASE
),free
)(multi
));
1342 if (src_pos
+ n
> isl_space_dim(multi
->space
, src_type
))
1343 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1344 "range out of bounds",
1345 return FN(MULTI(BASE
),free
)(multi
));
1346 if (dst_type
== src_type
)
1347 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_unsupported
,
1348 "moving dims within the same type not supported",
1349 return FN(MULTI(BASE
),free
)(multi
));
1351 multi
= FN(MULTI(BASE
),cow
)(multi
);
1355 multi
->space
= isl_space_move_dims(multi
->space
, dst_type
, dst_pos
,
1356 src_type
, src_pos
, n
);
1358 return FN(MULTI(BASE
),free
)(multi
);
1360 for (i
= 0; i
< multi
->n
; ++i
) {
1361 multi
->p
[i
] = FN(EL
,move_dims
)(multi
->p
[i
], dst_type
, dst_pos
,
1362 src_type
, src_pos
, n
);
1364 return FN(MULTI(BASE
),free
)(multi
);
1371 /* Convert a multiple expression defined over a parameter domain
1372 * into one that is defined over a zero-dimensional set.
1374 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),from_range
)(
1375 __isl_take
MULTI(BASE
) *multi
)
1381 if (!isl_space_is_set(multi
->space
))
1382 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1383 "not living in a set space",
1384 return FN(MULTI(BASE
),free
)(multi
));
1386 space
= FN(MULTI(BASE
),get_space
)(multi
);
1387 space
= isl_space_from_range(space
);
1388 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
1393 /* Are "multi1" and "multi2" obviously equal?
1395 int FN(MULTI(BASE
),plain_is_equal
)(__isl_keep
MULTI(BASE
) *multi1
,
1396 __isl_keep
MULTI(BASE
) *multi2
)
1401 if (!multi1
|| !multi2
)
1403 if (multi1
->n
!= multi2
->n
)
1405 equal
= isl_space_is_equal(multi1
->space
, multi2
->space
);
1406 if (equal
< 0 || !equal
)
1409 for (i
= 0; i
< multi1
->n
; ++i
) {
1410 equal
= FN(EL
,plain_is_equal
)(multi1
->p
[i
], multi2
->p
[i
]);
1411 if (equal
< 0 || !equal
)
1419 /* Return the shared domain of the elements of "multi".
1421 __isl_give isl_set
*FN(MULTI(BASE
),domain
)(__isl_take
MULTI(BASE
) *multi
)
1429 dom
= isl_set_universe(FN(MULTI(BASE
),get_domain_space
)(multi
));
1430 for (i
= 0; i
< multi
->n
; ++i
) {
1433 dom_i
= FN(EL
,domain
)(FN(FN(MULTI(BASE
),get
),BASE
)(multi
, i
));
1434 dom
= isl_set_intersect(dom
, dom_i
);
1437 FN(MULTI(BASE
),free
)(multi
);