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 #include <isl_multi_macro.h>
17 #define MULTI_NAME(BASE) "isl_multi_" #BASE
18 #define xLIST(EL) EL ## _list
19 #define LIST(EL) xLIST(EL)
21 isl_ctx
*FN(MULTI(BASE
),get_ctx
)(__isl_keep
MULTI(BASE
) *multi
)
23 return multi
? isl_space_get_ctx(multi
->space
) : NULL
;
26 __isl_give isl_space
*FN(MULTI(BASE
),get_space
)(__isl_keep
MULTI(BASE
) *multi
)
28 return multi
? isl_space_copy(multi
->space
) : NULL
;
31 /* Return the position of the dimension of the given type and name
33 * Return -1 if no such dimension can be found.
35 int FN(MULTI(BASE
),find_dim_by_name
)(__isl_keep
MULTI(BASE
) *multi
,
36 enum isl_dim_type type
, const char *name
)
40 return isl_space_find_dim_by_name(multi
->space
, type
, name
);
43 __isl_give isl_space
*FN(MULTI(BASE
),get_domain_space
)(
44 __isl_keep
MULTI(BASE
) *multi
)
46 return multi
? isl_space_domain(isl_space_copy(multi
->space
)) : NULL
;
49 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),alloc
)(__isl_take isl_space
*space
)
58 ctx
= isl_space_get_ctx(space
);
59 n
= isl_space_dim(space
, isl_dim_out
);
60 multi
= isl_calloc(ctx
, MULTI(BASE
),
61 sizeof(MULTI(BASE
)) + (n
- 1) * sizeof(struct EL
*));
70 isl_space_free(space
);
74 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),dup
)(__isl_keep
MULTI(BASE
) *multi
)
82 dup
= FN(MULTI(BASE
),alloc
)(isl_space_copy(multi
->space
));
86 for (i
= 0; i
< multi
->n
; ++i
)
87 dup
= FN(FN(MULTI(BASE
),set
),BASE
)(dup
, i
,
88 FN(EL
,copy
)(multi
->u
.p
[i
]));
93 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),cow
)(__isl_take
MULTI(BASE
) *multi
)
102 return FN(MULTI(BASE
),dup
)(multi
);
105 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),copy
)(__isl_keep
MULTI(BASE
) *multi
)
114 __isl_null
MULTI(BASE
) *FN(MULTI(BASE
),free
)(__isl_take
MULTI(BASE
) *multi
)
121 if (--multi
->ref
> 0)
124 isl_space_free(multi
->space
);
125 for (i
= 0; i
< multi
->n
; ++i
)
126 FN(EL
,free
)(multi
->u
.p
[i
]);
132 unsigned FN(MULTI(BASE
),dim
)(__isl_keep
MULTI(BASE
) *multi
,
133 enum isl_dim_type type
)
135 return multi
? isl_space_dim(multi
->space
, type
) : 0;
138 /* Return the position of the first dimension of "type" with id "id".
139 * Return -1 if there is no such dimension.
141 int FN(MULTI(BASE
),find_dim_by_id
)(__isl_keep
MULTI(BASE
) *multi
,
142 enum isl_dim_type type
, __isl_keep isl_id
*id
)
146 return isl_space_find_dim_by_id(multi
->space
, type
, id
);
149 /* Return the id of the given dimension.
151 __isl_give isl_id
*FN(MULTI(BASE
),get_dim_id
)(__isl_keep
MULTI(BASE
) *multi
,
152 enum isl_dim_type type
, unsigned pos
)
154 return multi
? isl_space_get_dim_id(multi
->space
, type
, pos
) : NULL
;
157 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_dim_name
)(
158 __isl_take
MULTI(BASE
) *multi
,
159 enum isl_dim_type type
, unsigned pos
, const char *s
)
163 multi
= FN(MULTI(BASE
),cow
)(multi
);
167 multi
->space
= isl_space_set_dim_name(multi
->space
, type
, pos
, s
);
169 return FN(MULTI(BASE
),free
)(multi
);
171 if (type
== isl_dim_out
)
173 for (i
= 0; i
< multi
->n
; ++i
) {
174 multi
->u
.p
[i
] = FN(EL
,set_dim_name
)(multi
->u
.p
[i
],
177 return FN(MULTI(BASE
),free
)(multi
);
183 const char *FN(MULTI(BASE
),get_tuple_name
)(__isl_keep
MULTI(BASE
) *multi
,
184 enum isl_dim_type type
)
186 return multi
? isl_space_get_tuple_name(multi
->space
, type
) : NULL
;
189 /* Does the specified tuple have an id?
191 isl_bool
FN(MULTI(BASE
),has_tuple_id
)(__isl_keep
MULTI(BASE
) *multi
,
192 enum isl_dim_type type
)
195 return isl_bool_error
;
196 return isl_space_has_tuple_id(multi
->space
, type
);
199 /* Return the id of the specified tuple.
201 __isl_give isl_id
*FN(MULTI(BASE
),get_tuple_id
)(__isl_keep
MULTI(BASE
) *multi
,
202 enum isl_dim_type type
)
204 return multi
? isl_space_get_tuple_id(multi
->space
, type
) : NULL
;
207 __isl_give EL
*FN(FN(MULTI(BASE
),get
),BASE
)(__isl_keep
MULTI(BASE
) *multi
,
214 ctx
= FN(MULTI(BASE
),get_ctx
)(multi
);
215 if (pos
< 0 || pos
>= multi
->n
)
216 isl_die(ctx
, isl_error_invalid
,
217 "index out of bounds", return NULL
);
218 return FN(EL
,copy
)(multi
->u
.p
[pos
]);
221 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),set
),BASE
)(
222 __isl_take
MULTI(BASE
) *multi
, int pos
, __isl_take EL
*el
)
224 isl_space
*multi_space
= NULL
;
225 isl_space
*el_space
= NULL
;
228 multi
= FN(MULTI(BASE
),cow
)(multi
);
232 multi_space
= FN(MULTI(BASE
),get_space
)(multi
);
233 match
= FN(EL
,matching_params
)(el
, multi_space
);
237 multi
= FN(MULTI(BASE
),align_params
)(multi
,
238 FN(EL
,get_space
)(el
));
239 isl_space_free(multi_space
);
240 multi_space
= FN(MULTI(BASE
),get_space
)(multi
);
241 el
= FN(EL
,align_params
)(el
, isl_space_copy(multi_space
));
243 if (FN(EL
,check_match_domain_space
)(el
, multi_space
) < 0)
246 if (pos
< 0 || pos
>= multi
->n
)
247 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
248 "index out of bounds", goto error
);
250 FN(EL
,free
)(multi
->u
.p
[pos
]);
251 multi
->u
.p
[pos
] = el
;
253 isl_space_free(multi_space
);
254 isl_space_free(el_space
);
258 FN(MULTI(BASE
),free
)(multi
);
260 isl_space_free(multi_space
);
261 isl_space_free(el_space
);
265 /* Reset the space of "multi". This function is called from isl_pw_templ.c
266 * and doesn't know if the space of an element object is represented
267 * directly or through its domain. It therefore passes along both,
268 * which we pass along to the element function since we don't know how
269 * that is represented either.
271 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_space_and_domain
)(
272 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*space
,
273 __isl_take isl_space
*domain
)
277 multi
= FN(MULTI(BASE
),cow
)(multi
);
278 if (!multi
|| !space
|| !domain
)
281 for (i
= 0; i
< multi
->n
; ++i
) {
282 multi
->u
.p
[i
] = FN(EL
,reset_domain_space
)(multi
->u
.p
[i
],
283 isl_space_copy(domain
));
287 isl_space_free(domain
);
288 isl_space_free(multi
->space
);
289 multi
->space
= space
;
293 isl_space_free(domain
);
294 isl_space_free(space
);
295 FN(MULTI(BASE
),free
)(multi
);
299 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_domain_space
)(
300 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*domain
)
304 space
= isl_space_extend_domain_with_range(isl_space_copy(domain
),
305 isl_space_copy(multi
->space
));
306 return FN(MULTI(BASE
),reset_space_and_domain
)(multi
, space
, domain
);
309 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_space
)(
310 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*space
)
314 domain
= isl_space_domain(isl_space_copy(space
));
315 return FN(MULTI(BASE
),reset_space_and_domain
)(multi
, space
, domain
);
318 /* Set the id of the given dimension of "multi" to "id".
320 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_dim_id
)(
321 __isl_take
MULTI(BASE
) *multi
,
322 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
326 multi
= FN(MULTI(BASE
),cow
)(multi
);
330 space
= FN(MULTI(BASE
),get_space
)(multi
);
331 space
= isl_space_set_dim_id(space
, type
, pos
, id
);
333 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
336 FN(MULTI(BASE
),free
)(multi
);
340 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_tuple_name
)(
341 __isl_keep
MULTI(BASE
) *multi
, enum isl_dim_type type
,
346 multi
= FN(MULTI(BASE
),cow
)(multi
);
350 space
= FN(MULTI(BASE
),get_space
)(multi
);
351 space
= isl_space_set_tuple_name(space
, type
, s
);
353 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
356 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_tuple_id
)(
357 __isl_take
MULTI(BASE
) *multi
, enum isl_dim_type type
,
358 __isl_take isl_id
*id
)
362 multi
= FN(MULTI(BASE
),cow
)(multi
);
366 space
= FN(MULTI(BASE
),get_space
)(multi
);
367 space
= isl_space_set_tuple_id(space
, type
, id
);
369 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
375 /* Drop the id on the specified tuple.
377 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_tuple_id
)(
378 __isl_take
MULTI(BASE
) *multi
, enum isl_dim_type type
)
384 if (!FN(MULTI(BASE
),has_tuple_id
)(multi
, type
))
387 multi
= FN(MULTI(BASE
),cow
)(multi
);
391 space
= FN(MULTI(BASE
),get_space
)(multi
);
392 space
= isl_space_reset_tuple_id(space
, type
);
394 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
397 /* Reset the user pointer on all identifiers of parameters and tuples
398 * of the space of "multi".
400 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_user
)(
401 __isl_take
MULTI(BASE
) *multi
)
405 space
= FN(MULTI(BASE
),get_space
)(multi
);
406 space
= isl_space_reset_user(space
);
408 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
411 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),realign_domain
)(
412 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_reordering
*exp
)
416 multi
= FN(MULTI(BASE
),cow
)(multi
);
420 for (i
= 0; i
< multi
->n
; ++i
) {
421 multi
->u
.p
[i
] = FN(EL
,realign_domain
)(multi
->u
.p
[i
],
422 isl_reordering_copy(exp
));
427 multi
= FN(MULTI(BASE
),reset_domain_space
)(multi
,
428 isl_space_copy(exp
->dim
));
430 isl_reordering_free(exp
);
433 isl_reordering_free(exp
);
434 FN(MULTI(BASE
),free
)(multi
);
438 /* Align the parameters of "multi" to those of "model".
440 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),align_params
)(
441 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*model
)
444 isl_bool equal_params
;
447 if (!multi
|| !model
)
450 equal_params
= isl_space_has_equal_params(multi
->space
, model
);
451 if (equal_params
< 0)
454 isl_space_free(model
);
458 ctx
= isl_space_get_ctx(model
);
459 if (!isl_space_has_named_params(model
))
460 isl_die(ctx
, isl_error_invalid
,
461 "model has unnamed parameters", goto error
);
462 if (!isl_space_has_named_params(multi
->space
))
463 isl_die(ctx
, isl_error_invalid
,
464 "input has unnamed parameters", goto error
);
466 model
= isl_space_params(model
);
467 exp
= isl_parameter_alignment_reordering(multi
->space
, model
);
468 exp
= isl_reordering_extend_space(exp
,
469 FN(MULTI(BASE
),get_domain_space
)(multi
));
470 multi
= FN(MULTI(BASE
),realign_domain
)(multi
, exp
);
472 isl_space_free(model
);
475 isl_space_free(model
);
476 FN(MULTI(BASE
),free
)(multi
);
480 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),from
),LIST(BASE
))(
481 __isl_take isl_space
*space
, __isl_take
LIST(EL
) *list
)
491 ctx
= isl_space_get_ctx(space
);
492 n
= FN(FN(LIST(EL
),n
),BASE
)(list
);
493 if (n
!= isl_space_dim(space
, isl_dim_out
))
494 isl_die(ctx
, isl_error_invalid
,
495 "invalid number of elements in list", goto error
);
497 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
498 for (i
= 0; i
< n
; ++i
) {
499 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
,
500 FN(FN(LIST(EL
),get
),BASE
)(list
, i
));
503 isl_space_free(space
);
504 FN(LIST(EL
),free
)(list
);
507 isl_space_free(space
);
508 FN(LIST(EL
),free
)(list
);
513 /* Create a multi expression in the given space that maps each
514 * input dimension to the corresponding output dimension.
516 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),identity
)(__isl_take isl_space
*space
)
525 if (isl_space_is_set(space
))
526 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
527 "expecting map space", goto error
);
529 n
= isl_space_dim(space
, isl_dim_out
);
530 if (n
!= isl_space_dim(space
, isl_dim_in
))
531 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
532 "number of input and output dimensions needs to be "
533 "the same", goto error
);
535 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
538 isl_space_free(space
);
542 space
= isl_space_domain(space
);
543 ls
= isl_local_space_from_space(space
);
545 for (i
= 0; i
< n
; ++i
) {
547 el
= FN(EL
,var_on_domain
)(isl_local_space_copy(ls
),
549 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
, el
);
552 isl_local_space_free(ls
);
556 isl_space_free(space
);
562 /* Construct a multi expression in the given space with value zero in
563 * each of the output dimensions.
565 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),zero
)(__isl_take isl_space
*space
)
573 n
= isl_space_dim(space
, isl_dim_out
);
574 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
577 isl_space_free(space
);
583 space
= isl_space_domain(space
);
584 ls
= isl_local_space_from_space(space
);
585 el
= FN(EL
,zero_on_domain
)(ls
);
587 for (i
= 0; i
< n
; ++i
)
588 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
,
599 /* Create a multiple expression with a single output/set dimension
601 * For most multiple expression types, the base type has a single
602 * output/set dimension and the space of the result is therefore
603 * the same as the space of the input.
604 * In the case of isl_multi_union_pw_aff, however, the base type
605 * lives in a parameter space and we therefore need to add
606 * a single set dimension.
608 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),from
),BASE
)(__isl_take EL
*el
)
613 space
= FN(EL
,get_space(el
));
614 if (isl_space_is_params(space
)) {
615 space
= isl_space_set_from_params(space
);
616 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
618 multi
= FN(MULTI(BASE
),alloc
)(space
);
619 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, 0, el
);
625 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),drop_dims
)(
626 __isl_take
MULTI(BASE
) *multi
,
627 enum isl_dim_type type
, unsigned first
, unsigned n
)
632 multi
= FN(MULTI(BASE
),cow
)(multi
);
636 dim
= FN(MULTI(BASE
),dim
)(multi
, type
);
637 if (first
+ n
> dim
|| first
+ n
< first
)
638 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
639 "index out of bounds",
640 return FN(MULTI(BASE
),free
)(multi
));
642 multi
->space
= isl_space_drop_dims(multi
->space
, type
, first
, n
);
644 return FN(MULTI(BASE
),free
)(multi
);
646 if (type
== isl_dim_out
) {
647 for (i
= 0; i
< n
; ++i
)
648 FN(EL
,free
)(multi
->u
.p
[first
+ i
]);
649 for (i
= first
; i
+ n
< multi
->n
; ++i
)
650 multi
->u
.p
[i
] = multi
->u
.p
[i
+ n
];
656 for (i
= 0; i
< multi
->n
; ++i
) {
657 multi
->u
.p
[i
] = FN(EL
,drop_dims
)(multi
->u
.p
[i
], type
, first
, n
);
659 return FN(MULTI(BASE
),free
)(multi
);
665 /* Align the parameters of "multi1" and "multi2" (if needed) and call "fn".
667 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),align_params_multi_multi_and
)(
668 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
669 __isl_give
MULTI(BASE
) *(*fn
)(__isl_take
MULTI(BASE
) *multi1
,
670 __isl_take
MULTI(BASE
) *multi2
))
673 isl_bool equal_params
;
675 if (!multi1
|| !multi2
)
677 equal_params
= isl_space_has_equal_params(multi1
->space
, multi2
->space
);
678 if (equal_params
< 0)
681 return fn(multi1
, multi2
);
682 ctx
= FN(MULTI(BASE
),get_ctx
)(multi1
);
683 if (!isl_space_has_named_params(multi1
->space
) ||
684 !isl_space_has_named_params(multi2
->space
))
685 isl_die(ctx
, isl_error_invalid
,
686 "unaligned unnamed parameters", goto error
);
687 multi1
= FN(MULTI(BASE
),align_params
)(multi1
,
688 FN(MULTI(BASE
),get_space
)(multi2
));
689 multi2
= FN(MULTI(BASE
),align_params
)(multi2
,
690 FN(MULTI(BASE
),get_space
)(multi1
));
691 return fn(multi1
, multi2
);
693 FN(MULTI(BASE
),free
)(multi1
);
694 FN(MULTI(BASE
),free
)(multi2
);
698 /* Given two MULTI(BASE)s A -> B and C -> D,
699 * construct a MULTI(BASE) (A * C) -> [B -> D].
701 * The parameters are assumed to have been aligned.
703 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_product_aligned
)(
704 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
711 if (!multi1
|| !multi2
)
714 space
= isl_space_range_product(FN(MULTI(BASE
),get_space
)(multi1
),
715 FN(MULTI(BASE
),get_space
)(multi2
));
716 res
= FN(MULTI(BASE
),alloc
)(space
);
718 n1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
719 n2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_out
);
721 for (i
= 0; i
< n1
; ++i
) {
722 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi1
, i
);
723 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, i
, el
);
726 for (i
= 0; i
< n2
; ++i
) {
727 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi2
, i
);
728 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, n1
+ i
, el
);
731 FN(MULTI(BASE
),free
)(multi1
);
732 FN(MULTI(BASE
),free
)(multi2
);
735 FN(MULTI(BASE
),free
)(multi1
);
736 FN(MULTI(BASE
),free
)(multi2
);
740 /* Given two MULTI(BASE)s A -> B and C -> D,
741 * construct a MULTI(BASE) (A * C) -> [B -> D].
743 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_product
)(
744 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
746 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
747 &FN(MULTI(BASE
),range_product_aligned
));
750 /* Is the range of "multi" a wrapped relation?
752 isl_bool
FN(MULTI(BASE
),range_is_wrapping
)(__isl_keep
MULTI(BASE
) *multi
)
755 return isl_bool_error
;
756 return isl_space_range_is_wrapping(multi
->space
);
759 /* Given a function A -> [B -> C], extract the function A -> B.
761 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_factor_domain
)(
762 __isl_take
MULTI(BASE
) *multi
)
769 if (!isl_space_range_is_wrapping(multi
->space
))
770 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
771 "range is not a product",
772 return FN(MULTI(BASE
),free
)(multi
));
774 space
= FN(MULTI(BASE
),get_space
)(multi
);
775 total
= isl_space_dim(space
, isl_dim_out
);
776 space
= isl_space_range_factor_domain(space
);
777 keep
= isl_space_dim(space
, isl_dim_out
);
778 multi
= FN(MULTI(BASE
),drop_dims
)(multi
,
779 isl_dim_out
, keep
, total
- keep
);
780 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
785 /* Given a function A -> [B -> C], extract the function A -> C.
787 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_factor_range
)(
788 __isl_take
MULTI(BASE
) *multi
)
795 if (!isl_space_range_is_wrapping(multi
->space
))
796 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
797 "range is not a product",
798 return FN(MULTI(BASE
),free
)(multi
));
800 space
= FN(MULTI(BASE
),get_space
)(multi
);
801 total
= isl_space_dim(space
, isl_dim_out
);
802 space
= isl_space_range_factor_range(space
);
803 keep
= isl_space_dim(space
, isl_dim_out
);
804 multi
= FN(MULTI(BASE
),drop_dims
)(multi
, isl_dim_out
, 0, total
- keep
);
805 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
810 /* Given a function [B -> C], extract the function C.
812 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),factor_range
)(
813 __isl_take
MULTI(BASE
) *multi
)
820 if (!isl_space_is_wrapping(multi
->space
))
821 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
822 "not a product", return FN(MULTI(BASE
),free
)(multi
));
824 space
= FN(MULTI(BASE
),get_space
)(multi
);
825 total
= isl_space_dim(space
, isl_dim_out
);
826 space
= isl_space_factor_range(space
);
827 keep
= isl_space_dim(space
, isl_dim_out
);
828 multi
= FN(MULTI(BASE
),drop_dims
)(multi
, isl_dim_out
, 0, total
- keep
);
829 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
835 /* Given two MULTI(BASE)s A -> B and C -> D,
836 * construct a MULTI(BASE) [A -> C] -> [B -> D].
838 * The parameters are assumed to have been aligned.
840 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),product_aligned
)(
841 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
847 int in1
, in2
, out1
, out2
;
849 in1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_in
);
850 in2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_in
);
851 out1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
852 out2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_out
);
853 space
= isl_space_product(FN(MULTI(BASE
),get_space
)(multi1
),
854 FN(MULTI(BASE
),get_space
)(multi2
));
855 res
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
856 space
= isl_space_domain(space
);
858 for (i
= 0; i
< out1
; ++i
) {
859 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi1
, i
);
860 el
= FN(EL
,insert_dims
)(el
, isl_dim_in
, in1
, in2
);
861 el
= FN(EL
,reset_domain_space
)(el
, isl_space_copy(space
));
862 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, i
, el
);
865 for (i
= 0; i
< out2
; ++i
) {
866 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi2
, i
);
867 el
= FN(EL
,insert_dims
)(el
, isl_dim_in
, 0, in1
);
868 el
= FN(EL
,reset_domain_space
)(el
, isl_space_copy(space
));
869 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, out1
+ i
, el
);
872 isl_space_free(space
);
873 FN(MULTI(BASE
),free
)(multi1
);
874 FN(MULTI(BASE
),free
)(multi2
);
878 /* Given two MULTI(BASE)s A -> B and C -> D,
879 * construct a MULTI(BASE) [A -> C] -> [B -> D].
881 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),product
)(
882 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
884 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
885 &FN(MULTI(BASE
),product_aligned
));
889 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),flatten_range
)(
890 __isl_take
MULTI(BASE
) *multi
)
895 if (!multi
->space
->nested
[1])
898 multi
= FN(MULTI(BASE
),cow
)(multi
);
902 multi
->space
= isl_space_flatten_range(multi
->space
);
904 return FN(MULTI(BASE
),free
)(multi
);
909 /* Given two MULTI(BASE)s A -> B and C -> D,
910 * construct a MULTI(BASE) (A * C) -> (B, D).
912 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),flat_range_product
)(
913 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
917 multi
= FN(MULTI(BASE
),range_product
)(multi1
, multi2
);
918 multi
= FN(MULTI(BASE
),flatten_range
)(multi
);
922 /* Given two multi expressions, "multi1"
926 * where B2 starts at position "pos", and "multi2"
930 * return the multi expression
934 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_splice
)(
935 __isl_take
MULTI(BASE
) *multi1
, unsigned pos
,
936 __isl_take
MULTI(BASE
) *multi2
)
941 if (!multi1
|| !multi2
)
944 dim
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
946 isl_die(FN(MULTI(BASE
),get_ctx
)(multi1
), isl_error_invalid
,
947 "index out of bounds", goto error
);
949 res
= FN(MULTI(BASE
),copy
)(multi1
);
950 res
= FN(MULTI(BASE
),drop_dims
)(res
, isl_dim_out
, pos
, dim
- pos
);
951 multi1
= FN(MULTI(BASE
),drop_dims
)(multi1
, isl_dim_out
, 0, pos
);
953 res
= FN(MULTI(BASE
),flat_range_product
)(res
, multi2
);
954 res
= FN(MULTI(BASE
),flat_range_product
)(res
, multi1
);
958 FN(MULTI(BASE
),free
)(multi1
);
959 FN(MULTI(BASE
),free
)(multi2
);
964 /* Given two multi expressions, "multi1"
968 * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
973 * return the multi expression
975 * [A1 C A2] -> [B1 D B2]
977 * We first insert input dimensions to obtain
979 * [A1 C A2] -> [B1 B2]
985 * and then apply range_splice.
987 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),splice
)(
988 __isl_take
MULTI(BASE
) *multi1
, unsigned in_pos
, unsigned out_pos
,
989 __isl_take
MULTI(BASE
) *multi2
)
994 if (!multi1
|| !multi2
)
997 n_in1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_in
);
999 isl_die(FN(MULTI(BASE
),get_ctx
)(multi1
), isl_error_invalid
,
1000 "index out of bounds", goto error
);
1002 n_in2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_in
);
1004 multi1
= FN(MULTI(BASE
),insert_dims
)(multi1
, isl_dim_in
, in_pos
, n_in2
);
1005 multi2
= FN(MULTI(BASE
),insert_dims
)(multi2
, isl_dim_in
, n_in2
,
1007 multi2
= FN(MULTI(BASE
),insert_dims
)(multi2
, isl_dim_in
, 0, in_pos
);
1009 return FN(MULTI(BASE
),range_splice
)(multi1
, out_pos
, multi2
);
1011 FN(MULTI(BASE
),free
)(multi1
);
1012 FN(MULTI(BASE
),free
)(multi2
);
1017 /* Check that "multi1" and "multi2" live in the same space,
1018 * reporting an error if they do not.
1020 static isl_stat
FN(MULTI(BASE
),check_equal_space
)(
1021 __isl_keep
MULTI(BASE
) *multi1
, __isl_keep
MULTI(BASE
) *multi2
)
1025 if (!multi1
|| !multi2
)
1026 return isl_stat_error
;
1028 equal
= isl_space_is_equal(multi1
->space
, multi2
->space
);
1030 return isl_stat_error
;
1032 isl_die(FN(MULTI(BASE
),get_ctx
)(multi1
), isl_error_invalid
,
1033 "spaces don't match", return isl_stat_error
);
1038 /* This function is currently only used from isl_aff.c
1040 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),bin_op
)(
1041 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
1042 __isl_give EL
*(*fn
)(__isl_take EL
*, __isl_take EL
*))
1043 __attribute__ ((unused
));
1045 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
1046 * return the result.
1048 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),bin_op
)(
1049 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
1050 __isl_give EL
*(*fn
)(__isl_take EL
*, __isl_take EL
*))
1054 multi1
= FN(MULTI(BASE
),cow
)(multi1
);
1055 if (FN(MULTI(BASE
),check_equal_space
)(multi1
, multi2
) < 0)
1058 for (i
= 0; i
< multi1
->n
; ++i
) {
1059 multi1
->u
.p
[i
] = fn(multi1
->u
.p
[i
],
1060 FN(EL
,copy
)(multi2
->u
.p
[i
]));
1061 if (!multi1
->u
.p
[i
])
1065 FN(MULTI(BASE
),free
)(multi2
);
1068 FN(MULTI(BASE
),free
)(multi1
);
1069 FN(MULTI(BASE
),free
)(multi2
);
1073 /* Add "multi2" from "multi1" and return the result.
1075 * The parameters of "multi1" and "multi2" are assumed to have been aligned.
1077 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),add_aligned
)(
1078 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
1080 return FN(MULTI(BASE
),bin_op
)(multi1
, multi2
, &FN(EL
,add
));
1083 /* Add "multi2" from "multi1" and return the result.
1085 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),add
)(__isl_take
MULTI(BASE
) *multi1
,
1086 __isl_take
MULTI(BASE
) *multi2
)
1088 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
1089 &FN(MULTI(BASE
),add_aligned
));
1092 /* Subtract "multi2" from "multi1" and return the result.
1094 * The parameters of "multi1" and "multi2" are assumed to have been aligned.
1096 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),sub_aligned
)(
1097 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
1099 return FN(MULTI(BASE
),bin_op
)(multi1
, multi2
, &FN(EL
,sub
));
1102 /* Subtract "multi2" from "multi1" and return the result.
1104 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),sub
)(__isl_take
MULTI(BASE
) *multi1
,
1105 __isl_take
MULTI(BASE
) *multi2
)
1107 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
1108 &FN(MULTI(BASE
),sub_aligned
));
1111 /* Multiply the elements of "multi" by "v" and return the result.
1113 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_val
)(__isl_take
MULTI(BASE
) *multi
,
1114 __isl_take isl_val
*v
)
1121 if (isl_val_is_one(v
)) {
1126 if (!isl_val_is_rat(v
))
1127 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1128 "expecting rational factor", goto error
);
1130 multi
= FN(MULTI(BASE
),cow
)(multi
);
1134 for (i
= 0; i
< multi
->n
; ++i
) {
1135 multi
->u
.p
[i
] = FN(EL
,scale_val
)(multi
->u
.p
[i
],
1145 return FN(MULTI(BASE
),free
)(multi
);
1148 /* Divide the elements of "multi" by "v" and return the result.
1150 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_down_val
)(
1151 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_val
*v
)
1158 if (isl_val_is_one(v
)) {
1163 if (!isl_val_is_rat(v
))
1164 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1165 "expecting rational factor", goto error
);
1166 if (isl_val_is_zero(v
))
1167 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1168 "cannot scale down by zero", goto error
);
1170 multi
= FN(MULTI(BASE
),cow
)(multi
);
1174 for (i
= 0; i
< multi
->n
; ++i
) {
1175 multi
->u
.p
[i
] = FN(EL
,scale_down_val
)(multi
->u
.p
[i
],
1185 return FN(MULTI(BASE
),free
)(multi
);
1188 /* Multiply the elements of "multi" by the corresponding element of "mv"
1189 * and return the result.
1191 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_multi_val
)(
1192 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1199 if (!isl_space_tuple_is_equal(multi
->space
, isl_dim_out
,
1200 mv
->space
, isl_dim_set
))
1201 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1202 "spaces don't match", goto error
);
1204 multi
= FN(MULTI(BASE
),cow
)(multi
);
1208 for (i
= 0; i
< multi
->n
; ++i
) {
1211 v
= isl_multi_val_get_val(mv
, i
);
1212 multi
->u
.p
[i
] = FN(EL
,scale_val
)(multi
->u
.p
[i
], v
);
1217 isl_multi_val_free(mv
);
1220 isl_multi_val_free(mv
);
1221 return FN(MULTI(BASE
),free
)(multi
);
1224 /* Divide the elements of "multi" by the corresponding element of "mv"
1225 * and return the result.
1227 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_down_multi_val
)(
1228 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1235 if (!isl_space_tuple_is_equal(multi
->space
, isl_dim_out
,
1236 mv
->space
, isl_dim_set
))
1237 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1238 "spaces don't match", goto error
);
1240 multi
= FN(MULTI(BASE
),cow
)(multi
);
1244 for (i
= 0; i
< multi
->n
; ++i
) {
1247 v
= isl_multi_val_get_val(mv
, i
);
1248 multi
->u
.p
[i
] = FN(EL
,scale_down_val
)(multi
->u
.p
[i
], v
);
1253 isl_multi_val_free(mv
);
1256 isl_multi_val_free(mv
);
1257 return FN(MULTI(BASE
),free
)(multi
);
1260 /* Compute the residues of the elements of "multi" modulo
1261 * the corresponding element of "mv" and return the result.
1263 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),mod_multi_val
)(
1264 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1271 if (!isl_space_tuple_is_equal(multi
->space
, isl_dim_out
,
1272 mv
->space
, isl_dim_set
))
1273 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1274 "spaces don't match", goto error
);
1276 multi
= FN(MULTI(BASE
),cow
)(multi
);
1280 for (i
= 0; i
< multi
->n
; ++i
) {
1283 v
= isl_multi_val_get_val(mv
, i
);
1284 multi
->u
.p
[i
] = FN(EL
,mod_val
)(multi
->u
.p
[i
], v
);
1289 isl_multi_val_free(mv
);
1292 isl_multi_val_free(mv
);
1293 return FN(MULTI(BASE
),free
)(multi
);
1296 #ifndef NO_MOVE_DIMS
1297 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "multi"
1298 * to dimensions of "dst_type" at "dst_pos".
1300 * We only support moving input dimensions to parameters and vice versa.
1302 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),move_dims
)(__isl_take
MULTI(BASE
) *multi
,
1303 enum isl_dim_type dst_type
, unsigned dst_pos
,
1304 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1312 !isl_space_is_named_or_nested(multi
->space
, src_type
) &&
1313 !isl_space_is_named_or_nested(multi
->space
, dst_type
))
1316 if (dst_type
== isl_dim_out
|| src_type
== isl_dim_out
)
1317 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1318 "cannot move output/set dimension",
1319 return FN(MULTI(BASE
),free
)(multi
));
1320 if (dst_type
== isl_dim_div
|| src_type
== isl_dim_div
)
1321 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1323 return FN(MULTI(BASE
),free
)(multi
));
1324 if (src_pos
+ n
> isl_space_dim(multi
->space
, src_type
))
1325 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1326 "range out of bounds",
1327 return FN(MULTI(BASE
),free
)(multi
));
1328 if (dst_type
== src_type
)
1329 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_unsupported
,
1330 "moving dims within the same type not supported",
1331 return FN(MULTI(BASE
),free
)(multi
));
1333 multi
= FN(MULTI(BASE
),cow
)(multi
);
1337 multi
->space
= isl_space_move_dims(multi
->space
, dst_type
, dst_pos
,
1338 src_type
, src_pos
, n
);
1340 return FN(MULTI(BASE
),free
)(multi
);
1342 for (i
= 0; i
< multi
->n
; ++i
) {
1343 multi
->u
.p
[i
] = FN(EL
,move_dims
)(multi
->u
.p
[i
],
1345 src_type
, src_pos
, n
);
1347 return FN(MULTI(BASE
),free
)(multi
);
1354 /* Convert a multiple expression defined over a parameter domain
1355 * into one that is defined over a zero-dimensional set.
1357 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),from_range
)(
1358 __isl_take
MULTI(BASE
) *multi
)
1364 if (!isl_space_is_set(multi
->space
))
1365 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1366 "not living in a set space",
1367 return FN(MULTI(BASE
),free
)(multi
));
1369 space
= FN(MULTI(BASE
),get_space
)(multi
);
1370 space
= isl_space_from_range(space
);
1371 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
1376 /* Are "multi1" and "multi2" obviously equal?
1378 isl_bool
FN(MULTI(BASE
),plain_is_equal
)(__isl_keep
MULTI(BASE
) *multi1
,
1379 __isl_keep
MULTI(BASE
) *multi2
)
1384 if (!multi1
|| !multi2
)
1385 return isl_bool_error
;
1386 if (multi1
->n
!= multi2
->n
)
1387 return isl_bool_false
;
1388 equal
= isl_space_is_equal(multi1
->space
, multi2
->space
);
1389 if (equal
< 0 || !equal
)
1392 for (i
= 0; i
< multi1
->n
; ++i
) {
1393 equal
= FN(EL
,plain_is_equal
)(multi1
->u
.p
[i
], multi2
->u
.p
[i
]);
1394 if (equal
< 0 || !equal
)
1398 return isl_bool_true
;
1401 /* Does "multi" involve any NaNs?
1403 isl_bool
FN(MULTI(BASE
),involves_nan
)(__isl_keep
MULTI(BASE
) *multi
)
1408 return isl_bool_error
;
1410 return isl_bool_false
;
1412 for (i
= 0; i
< multi
->n
; ++i
) {
1413 isl_bool has_nan
= FN(EL
,involves_nan
)(multi
->u
.p
[i
]);
1414 if (has_nan
< 0 || has_nan
)
1418 return isl_bool_false
;
1422 /* Return the shared domain of the elements of "multi".
1424 __isl_give isl_set
*FN(MULTI(BASE
),domain
)(__isl_take
MULTI(BASE
) *multi
)
1432 dom
= isl_set_universe(FN(MULTI(BASE
),get_domain_space
)(multi
));
1433 for (i
= 0; i
< multi
->n
; ++i
) {
1436 dom_i
= FN(EL
,domain
)(FN(FN(MULTI(BASE
),get
),BASE
)(multi
, i
));
1437 dom
= isl_set_intersect(dom
, dom_i
);
1440 FN(MULTI(BASE
),free
)(multi
);
1446 /* Return the opposite of "multi".
1448 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),neg
)(__isl_take
MULTI(BASE
) *multi
)
1452 multi
= FN(MULTI(BASE
),cow
)(multi
);
1456 for (i
= 0; i
< multi
->n
; ++i
) {
1457 multi
->u
.p
[i
] = FN(EL
,neg
)(multi
->u
.p
[i
]);
1459 return FN(MULTI(BASE
),free
)(multi
);