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
->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
->p
[i
]);
133 /* Check whether "multi" has non-zero coefficients for any dimension
134 * in the given range or if any of these dimensions appear
135 * with non-zero coefficients in any of the integer divisions involved.
137 isl_bool
FN(MULTI(BASE
),involves_dims
)(__isl_keep
MULTI(BASE
) *multi
,
138 enum isl_dim_type type
, unsigned first
, unsigned n
)
143 return isl_bool_error
;
144 if (multi
->n
== 0 || n
== 0)
145 return isl_bool_false
;
147 for (i
= 0; i
< multi
->n
; ++i
) {
150 involves
= FN(EL
,involves_dims
)(multi
->p
[i
], type
, first
, n
);
151 if (involves
< 0 || involves
)
155 return isl_bool_false
;
158 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),insert_dims
)(
159 __isl_take
MULTI(BASE
) *multi
,
160 enum isl_dim_type type
, unsigned first
, unsigned n
)
166 if (type
== isl_dim_out
)
167 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
168 "cannot insert output/set dimensions",
169 return FN(MULTI(BASE
),free
)(multi
));
170 if (n
== 0 && !isl_space_is_named_or_nested(multi
->space
, type
))
173 multi
= FN(MULTI(BASE
),cow
)(multi
);
177 multi
->space
= isl_space_insert_dims(multi
->space
, type
, first
, n
);
179 return FN(MULTI(BASE
),free
)(multi
);
181 for (i
= 0; i
< multi
->n
; ++i
) {
182 multi
->p
[i
] = FN(EL
,insert_dims
)(multi
->p
[i
], type
, first
, n
);
184 return FN(MULTI(BASE
),free
)(multi
);
190 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),add_dims
)(__isl_take
MULTI(BASE
) *multi
,
191 enum isl_dim_type type
, unsigned n
)
195 pos
= FN(MULTI(BASE
),dim
)(multi
, type
);
197 return FN(MULTI(BASE
),insert_dims
)(multi
, type
, pos
, n
);
201 unsigned FN(MULTI(BASE
),dim
)(__isl_keep
MULTI(BASE
) *multi
,
202 enum isl_dim_type type
)
204 return multi
? isl_space_dim(multi
->space
, type
) : 0;
207 /* Return the position of the first dimension of "type" with id "id".
208 * Return -1 if there is no such dimension.
210 int FN(MULTI(BASE
),find_dim_by_id
)(__isl_keep
MULTI(BASE
) *multi
,
211 enum isl_dim_type type
, __isl_keep isl_id
*id
)
215 return isl_space_find_dim_by_id(multi
->space
, type
, id
);
218 /* Return the id of the given dimension.
220 __isl_give isl_id
*FN(MULTI(BASE
),get_dim_id
)(__isl_keep
MULTI(BASE
) *multi
,
221 enum isl_dim_type type
, unsigned pos
)
223 return multi
? isl_space_get_dim_id(multi
->space
, type
, pos
) : NULL
;
226 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_dim_name
)(
227 __isl_take
MULTI(BASE
) *multi
,
228 enum isl_dim_type type
, unsigned pos
, const char *s
)
232 multi
= FN(MULTI(BASE
),cow
)(multi
);
236 multi
->space
= isl_space_set_dim_name(multi
->space
, type
, pos
, s
);
238 return FN(MULTI(BASE
),free
)(multi
);
240 if (type
== isl_dim_out
)
242 for (i
= 0; i
< multi
->n
; ++i
) {
243 multi
->p
[i
] = FN(EL
,set_dim_name
)(multi
->p
[i
], type
, pos
, s
);
245 return FN(MULTI(BASE
),free
)(multi
);
251 const char *FN(MULTI(BASE
),get_tuple_name
)(__isl_keep
MULTI(BASE
) *multi
,
252 enum isl_dim_type type
)
254 return multi
? isl_space_get_tuple_name(multi
->space
, type
) : NULL
;
257 /* Does the specified tuple have an id?
259 isl_bool
FN(MULTI(BASE
),has_tuple_id
)(__isl_keep
MULTI(BASE
) *multi
,
260 enum isl_dim_type type
)
263 return isl_bool_error
;
264 return isl_space_has_tuple_id(multi
->space
, type
);
267 /* Return the id of the specified tuple.
269 __isl_give isl_id
*FN(MULTI(BASE
),get_tuple_id
)(__isl_keep
MULTI(BASE
) *multi
,
270 enum isl_dim_type type
)
272 return multi
? isl_space_get_tuple_id(multi
->space
, type
) : NULL
;
275 __isl_give EL
*FN(FN(MULTI(BASE
),get
),BASE
)(__isl_keep
MULTI(BASE
) *multi
,
282 ctx
= FN(MULTI(BASE
),get_ctx
)(multi
);
283 if (pos
< 0 || pos
>= multi
->n
)
284 isl_die(ctx
, isl_error_invalid
,
285 "index out of bounds", return NULL
);
286 return FN(EL
,copy
)(multi
->p
[pos
]);
289 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),set
),BASE
)(
290 __isl_take
MULTI(BASE
) *multi
, int pos
, __isl_take EL
*el
)
292 isl_space
*multi_space
= NULL
;
293 isl_space
*el_space
= NULL
;
296 multi
= FN(MULTI(BASE
),cow
)(multi
);
300 multi_space
= FN(MULTI(BASE
),get_space
)(multi
);
301 match
= FN(EL
,matching_params
)(el
, multi_space
);
305 multi
= FN(MULTI(BASE
),align_params
)(multi
,
306 FN(EL
,get_space
)(el
));
307 isl_space_free(multi_space
);
308 multi_space
= FN(MULTI(BASE
),get_space
)(multi
);
309 el
= FN(EL
,align_params
)(el
, isl_space_copy(multi_space
));
311 if (FN(EL
,check_match_domain_space
)(el
, multi_space
) < 0)
314 if (pos
< 0 || pos
>= multi
->n
)
315 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
316 "index out of bounds", goto error
);
318 FN(EL
,free
)(multi
->p
[pos
]);
321 isl_space_free(multi_space
);
322 isl_space_free(el_space
);
326 FN(MULTI(BASE
),free
)(multi
);
328 isl_space_free(multi_space
);
329 isl_space_free(el_space
);
333 /* Reset the space of "multi". This function is called from isl_pw_templ.c
334 * and doesn't know if the space of an element object is represented
335 * directly or through its domain. It therefore passes along both,
336 * which we pass along to the element function since we don't how
337 * that is represented either.
339 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_space_and_domain
)(
340 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*space
,
341 __isl_take isl_space
*domain
)
345 multi
= FN(MULTI(BASE
),cow
)(multi
);
346 if (!multi
|| !space
|| !domain
)
349 for (i
= 0; i
< multi
->n
; ++i
) {
350 multi
->p
[i
] = FN(EL
,reset_domain_space
)(multi
->p
[i
],
351 isl_space_copy(domain
));
355 isl_space_free(domain
);
356 isl_space_free(multi
->space
);
357 multi
->space
= space
;
361 isl_space_free(domain
);
362 isl_space_free(space
);
363 FN(MULTI(BASE
),free
)(multi
);
367 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_domain_space
)(
368 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*domain
)
372 space
= isl_space_extend_domain_with_range(isl_space_copy(domain
),
373 isl_space_copy(multi
->space
));
374 return FN(MULTI(BASE
),reset_space_and_domain
)(multi
, space
, domain
);
377 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_space
)(
378 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*space
)
382 domain
= isl_space_domain(isl_space_copy(space
));
383 return FN(MULTI(BASE
),reset_space_and_domain
)(multi
, space
, domain
);
386 /* Set the id of the given dimension of "multi" to "id".
388 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_dim_id
)(
389 __isl_take
MULTI(BASE
) *multi
,
390 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
394 multi
= FN(MULTI(BASE
),cow
)(multi
);
398 space
= FN(MULTI(BASE
),get_space
)(multi
);
399 space
= isl_space_set_dim_id(space
, type
, pos
, id
);
401 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
404 FN(MULTI(BASE
),free
)(multi
);
408 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_tuple_name
)(
409 __isl_keep
MULTI(BASE
) *multi
, enum isl_dim_type type
,
414 multi
= FN(MULTI(BASE
),cow
)(multi
);
418 space
= FN(MULTI(BASE
),get_space
)(multi
);
419 space
= isl_space_set_tuple_name(space
, type
, s
);
421 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
424 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),set_tuple_id
)(
425 __isl_take
MULTI(BASE
) *multi
, enum isl_dim_type type
,
426 __isl_take isl_id
*id
)
430 multi
= FN(MULTI(BASE
),cow
)(multi
);
434 space
= FN(MULTI(BASE
),get_space
)(multi
);
435 space
= isl_space_set_tuple_id(space
, type
, id
);
437 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
443 /* Drop the id on the specified tuple.
445 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_tuple_id
)(
446 __isl_take
MULTI(BASE
) *multi
, enum isl_dim_type type
)
452 if (!FN(MULTI(BASE
),has_tuple_id
)(multi
, type
))
455 multi
= FN(MULTI(BASE
),cow
)(multi
);
459 space
= FN(MULTI(BASE
),get_space
)(multi
);
460 space
= isl_space_reset_tuple_id(space
, type
);
462 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
465 /* Reset the user pointer on all identifiers of parameters and tuples
466 * of the space of "multi".
468 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),reset_user
)(
469 __isl_take
MULTI(BASE
) *multi
)
473 space
= FN(MULTI(BASE
),get_space
)(multi
);
474 space
= isl_space_reset_user(space
);
476 return FN(MULTI(BASE
),reset_space
)(multi
, space
);
479 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),realign_domain
)(
480 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_reordering
*exp
)
484 multi
= FN(MULTI(BASE
),cow
)(multi
);
488 for (i
= 0; i
< multi
->n
; ++i
) {
489 multi
->p
[i
] = FN(EL
,realign_domain
)(multi
->p
[i
],
490 isl_reordering_copy(exp
));
495 multi
= FN(MULTI(BASE
),reset_domain_space
)(multi
,
496 isl_space_copy(exp
->dim
));
498 isl_reordering_free(exp
);
501 isl_reordering_free(exp
);
502 FN(MULTI(BASE
),free
)(multi
);
506 /* Align the parameters of "multi" to those of "model".
508 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),align_params
)(
509 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_space
*model
)
514 if (!multi
|| !model
)
517 if (isl_space_match(multi
->space
, isl_dim_param
,
518 model
, isl_dim_param
)) {
519 isl_space_free(model
);
523 ctx
= isl_space_get_ctx(model
);
524 if (!isl_space_has_named_params(model
))
525 isl_die(ctx
, isl_error_invalid
,
526 "model has unnamed parameters", goto error
);
527 if (!isl_space_has_named_params(multi
->space
))
528 isl_die(ctx
, isl_error_invalid
,
529 "input has unnamed parameters", goto error
);
531 model
= isl_space_params(model
);
532 exp
= isl_parameter_alignment_reordering(multi
->space
, model
);
533 exp
= isl_reordering_extend_space(exp
,
534 FN(MULTI(BASE
),get_domain_space
)(multi
));
535 multi
= FN(MULTI(BASE
),realign_domain
)(multi
, exp
);
537 isl_space_free(model
);
540 isl_space_free(model
);
541 FN(MULTI(BASE
),free
)(multi
);
545 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),from
),LIST(BASE
))(
546 __isl_take isl_space
*space
, __isl_take
LIST(EL
) *list
)
556 ctx
= isl_space_get_ctx(space
);
557 n
= FN(FN(LIST(EL
),n
),BASE
)(list
);
558 if (n
!= isl_space_dim(space
, isl_dim_out
))
559 isl_die(ctx
, isl_error_invalid
,
560 "invalid number of elements in list", goto error
);
562 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
563 for (i
= 0; i
< n
; ++i
) {
564 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
,
565 FN(FN(LIST(EL
),get
),BASE
)(list
, i
));
568 isl_space_free(space
);
569 FN(LIST(EL
),free
)(list
);
572 isl_space_free(space
);
573 FN(LIST(EL
),free
)(list
);
578 /* Create a multi expression in the given space that maps each
579 * input dimension to the corresponding output dimension.
581 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),identity
)(__isl_take isl_space
*space
)
590 if (isl_space_is_set(space
))
591 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
592 "expecting map space", goto error
);
594 n
= isl_space_dim(space
, isl_dim_out
);
595 if (n
!= isl_space_dim(space
, isl_dim_in
))
596 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
597 "number of input and output dimensions needs to be "
598 "the same", goto error
);
600 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
603 isl_space_free(space
);
607 space
= isl_space_domain(space
);
608 ls
= isl_local_space_from_space(space
);
610 for (i
= 0; i
< n
; ++i
) {
612 el
= FN(EL
,var_on_domain
)(isl_local_space_copy(ls
),
614 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
, el
);
617 isl_local_space_free(ls
);
621 isl_space_free(space
);
627 /* Construct a multi expression in the given space with value zero in
628 * each of the output dimensions.
630 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),zero
)(__isl_take isl_space
*space
)
638 n
= isl_space_dim(space
, isl_dim_out
);
639 multi
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
642 isl_space_free(space
);
648 space
= isl_space_domain(space
);
649 ls
= isl_local_space_from_space(space
);
650 el
= FN(EL
,zero_on_domain
)(ls
);
652 for (i
= 0; i
< n
; ++i
)
653 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, i
,
664 /* Create a multiple expression with a single output/set dimension
666 * For most multiple expression types, the base type has a single
667 * output/set dimension and the space of the result is therefore
668 * the same as the space of the input.
669 * In the case of isl_multi_union_pw_aff, however, the base type
670 * lives in a parameter space and we therefore need to add
671 * a single set dimension.
673 __isl_give
MULTI(BASE
) *FN(FN(MULTI(BASE
),from
),BASE
)(__isl_take EL
*el
)
678 space
= FN(EL
,get_space(el
));
679 if (isl_space_is_params(space
)) {
680 space
= isl_space_set_from_params(space
);
681 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
683 multi
= FN(MULTI(BASE
),alloc
)(space
);
684 multi
= FN(FN(MULTI(BASE
),set
),BASE
)(multi
, 0, el
);
690 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),drop_dims
)(
691 __isl_take
MULTI(BASE
) *multi
,
692 enum isl_dim_type type
, unsigned first
, unsigned n
)
697 multi
= FN(MULTI(BASE
),cow
)(multi
);
701 dim
= FN(MULTI(BASE
),dim
)(multi
, type
);
702 if (first
+ n
> dim
|| first
+ n
< first
)
703 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
704 "index out of bounds",
705 return FN(MULTI(BASE
),cow
)(multi
));
707 multi
->space
= isl_space_drop_dims(multi
->space
, type
, first
, n
);
709 return FN(MULTI(BASE
),cow
)(multi
);
711 if (type
== isl_dim_out
) {
712 for (i
= 0; i
< n
; ++i
)
713 FN(EL
,free
)(multi
->p
[first
+ i
]);
714 for (i
= first
; i
+ n
< multi
->n
; ++i
)
715 multi
->p
[i
] = multi
->p
[i
+ n
];
721 for (i
= 0; i
< multi
->n
; ++i
) {
722 multi
->p
[i
] = FN(EL
,drop_dims
)(multi
->p
[i
], type
, first
, n
);
724 return FN(MULTI(BASE
),cow
)(multi
);
730 /* Align the parameters of "multi1" and "multi2" (if needed) and call "fn".
732 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),align_params_multi_multi_and
)(
733 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
734 __isl_give
MULTI(BASE
) *(*fn
)(__isl_take
MULTI(BASE
) *multi1
,
735 __isl_take
MULTI(BASE
) *multi2
))
739 if (!multi1
|| !multi2
)
741 if (isl_space_match(multi1
->space
, isl_dim_param
,
742 multi2
->space
, isl_dim_param
))
743 return fn(multi1
, multi2
);
744 ctx
= FN(MULTI(BASE
),get_ctx
)(multi1
);
745 if (!isl_space_has_named_params(multi1
->space
) ||
746 !isl_space_has_named_params(multi2
->space
))
747 isl_die(ctx
, isl_error_invalid
,
748 "unaligned unnamed parameters", goto error
);
749 multi1
= FN(MULTI(BASE
),align_params
)(multi1
,
750 FN(MULTI(BASE
),get_space
)(multi2
));
751 multi2
= FN(MULTI(BASE
),align_params
)(multi2
,
752 FN(MULTI(BASE
),get_space
)(multi1
));
753 return fn(multi1
, multi2
);
755 FN(MULTI(BASE
),free
)(multi1
);
756 FN(MULTI(BASE
),free
)(multi2
);
760 /* Given two MULTI(BASE)s A -> B and C -> D,
761 * construct a MULTI(BASE) (A * C) -> [B -> D].
763 * The parameters are assumed to have been aligned.
765 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_product_aligned
)(
766 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
773 if (!multi1
|| !multi2
)
776 space
= isl_space_range_product(FN(MULTI(BASE
),get_space
)(multi1
),
777 FN(MULTI(BASE
),get_space
)(multi2
));
778 res
= FN(MULTI(BASE
),alloc
)(space
);
780 n1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
781 n2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_out
);
783 for (i
= 0; i
< n1
; ++i
) {
784 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi1
, i
);
785 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, i
, el
);
788 for (i
= 0; i
< n2
; ++i
) {
789 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi2
, i
);
790 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, n1
+ i
, el
);
793 FN(MULTI(BASE
),free
)(multi1
);
794 FN(MULTI(BASE
),free
)(multi2
);
797 FN(MULTI(BASE
),free
)(multi1
);
798 FN(MULTI(BASE
),free
)(multi2
);
802 /* Given two MULTI(BASE)s A -> B and C -> D,
803 * construct a MULTI(BASE) (A * C) -> [B -> D].
805 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_product
)(
806 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
808 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
809 &FN(MULTI(BASE
),range_product_aligned
));
812 /* Is the range of "multi" a wrapped relation?
814 isl_bool
FN(MULTI(BASE
),range_is_wrapping
)(__isl_keep
MULTI(BASE
) *multi
)
817 return isl_bool_error
;
818 return isl_space_range_is_wrapping(multi
->space
);
821 /* Given a function A -> [B -> C], extract the function A -> B.
823 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_factor_domain
)(
824 __isl_take
MULTI(BASE
) *multi
)
831 if (!isl_space_range_is_wrapping(multi
->space
))
832 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
833 "range is not a product",
834 return FN(MULTI(BASE
),free
)(multi
));
836 space
= FN(MULTI(BASE
),get_space
)(multi
);
837 total
= isl_space_dim(space
, isl_dim_out
);
838 space
= isl_space_range_factor_domain(space
);
839 keep
= isl_space_dim(space
, isl_dim_out
);
840 multi
= FN(MULTI(BASE
),drop_dims
)(multi
,
841 isl_dim_out
, keep
, total
- keep
);
842 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
847 /* Given a function A -> [B -> C], extract the function A -> C.
849 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_factor_range
)(
850 __isl_take
MULTI(BASE
) *multi
)
857 if (!isl_space_range_is_wrapping(multi
->space
))
858 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
859 "range is not a product",
860 return FN(MULTI(BASE
),free
)(multi
));
862 space
= FN(MULTI(BASE
),get_space
)(multi
);
863 total
= isl_space_dim(space
, isl_dim_out
);
864 space
= isl_space_range_factor_range(space
);
865 keep
= isl_space_dim(space
, isl_dim_out
);
866 multi
= FN(MULTI(BASE
),drop_dims
)(multi
, isl_dim_out
, 0, total
- keep
);
867 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
872 /* Given a function [B -> C], extract the function C.
874 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),factor_range
)(
875 __isl_take
MULTI(BASE
) *multi
)
882 if (!isl_space_is_wrapping(multi
->space
))
883 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
884 "not a product", return FN(MULTI(BASE
),free
)(multi
));
886 space
= FN(MULTI(BASE
),get_space
)(multi
);
887 total
= isl_space_dim(space
, isl_dim_out
);
888 space
= isl_space_factor_range(space
);
889 keep
= isl_space_dim(space
, isl_dim_out
);
890 multi
= FN(MULTI(BASE
),drop_dims
)(multi
, isl_dim_out
, 0, total
- keep
);
891 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
897 /* Given two MULTI(BASE)s A -> B and C -> D,
898 * construct a MULTI(BASE) [A -> C] -> [B -> D].
900 * The parameters are assumed to have been aligned.
902 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),product_aligned
)(
903 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
909 int in1
, in2
, out1
, out2
;
911 in1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_in
);
912 in2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_in
);
913 out1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
914 out2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_out
);
915 space
= isl_space_product(FN(MULTI(BASE
),get_space
)(multi1
),
916 FN(MULTI(BASE
),get_space
)(multi2
));
917 res
= FN(MULTI(BASE
),alloc
)(isl_space_copy(space
));
918 space
= isl_space_domain(space
);
920 for (i
= 0; i
< out1
; ++i
) {
921 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi1
, i
);
922 el
= FN(EL
,insert_dims
)(el
, isl_dim_in
, in1
, in2
);
923 el
= FN(EL
,reset_domain_space
)(el
, isl_space_copy(space
));
924 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, i
, el
);
927 for (i
= 0; i
< out2
; ++i
) {
928 el
= FN(FN(MULTI(BASE
),get
),BASE
)(multi2
, i
);
929 el
= FN(EL
,insert_dims
)(el
, isl_dim_in
, 0, in1
);
930 el
= FN(EL
,reset_domain_space
)(el
, isl_space_copy(space
));
931 res
= FN(FN(MULTI(BASE
),set
),BASE
)(res
, out1
+ i
, el
);
934 isl_space_free(space
);
935 FN(MULTI(BASE
),free
)(multi1
);
936 FN(MULTI(BASE
),free
)(multi2
);
940 /* Given two MULTI(BASE)s A -> B and C -> D,
941 * construct a MULTI(BASE) [A -> C] -> [B -> D].
943 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),product
)(
944 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
946 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
947 &FN(MULTI(BASE
),product_aligned
));
951 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),flatten_range
)(
952 __isl_take
MULTI(BASE
) *multi
)
957 if (!multi
->space
->nested
[1])
960 multi
= FN(MULTI(BASE
),cow
)(multi
);
964 multi
->space
= isl_space_flatten_range(multi
->space
);
966 return FN(MULTI(BASE
),free
)(multi
);
971 /* Given two MULTI(BASE)s A -> B and C -> D,
972 * construct a MULTI(BASE) (A * C) -> (B, D).
974 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),flat_range_product
)(
975 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
979 multi
= FN(MULTI(BASE
),range_product
)(multi1
, multi2
);
980 multi
= FN(MULTI(BASE
),flatten_range
)(multi
);
984 /* Given two multi expressions, "multi1"
988 * where B2 starts at position "pos", and "multi2"
992 * return the multi expression
996 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),range_splice
)(
997 __isl_take
MULTI(BASE
) *multi1
, unsigned pos
,
998 __isl_take
MULTI(BASE
) *multi2
)
1003 if (!multi1
|| !multi2
)
1006 dim
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_out
);
1008 isl_die(FN(MULTI(BASE
),get_ctx
)(multi1
), isl_error_invalid
,
1009 "index out of bounds", goto error
);
1011 res
= FN(MULTI(BASE
),copy
)(multi1
);
1012 res
= FN(MULTI(BASE
),drop_dims
)(res
, isl_dim_out
, pos
, dim
- pos
);
1013 multi1
= FN(MULTI(BASE
),drop_dims
)(multi1
, isl_dim_out
, 0, pos
);
1015 res
= FN(MULTI(BASE
),flat_range_product
)(res
, multi2
);
1016 res
= FN(MULTI(BASE
),flat_range_product
)(res
, multi1
);
1020 FN(MULTI(BASE
),free
)(multi1
);
1021 FN(MULTI(BASE
),free
)(multi2
);
1026 /* Given two multi expressions, "multi1"
1028 * [A1 A2] -> [B1 B2]
1030 * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
1035 * return the multi expression
1037 * [A1 C A2] -> [B1 D B2]
1039 * We first insert input dimensions to obtain
1041 * [A1 C A2] -> [B1 B2]
1047 * and then apply range_splice.
1049 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),splice
)(
1050 __isl_take
MULTI(BASE
) *multi1
, unsigned in_pos
, unsigned out_pos
,
1051 __isl_take
MULTI(BASE
) *multi2
)
1056 if (!multi1
|| !multi2
)
1059 n_in1
= FN(MULTI(BASE
),dim
)(multi1
, isl_dim_in
);
1061 isl_die(FN(MULTI(BASE
),get_ctx
)(multi1
), isl_error_invalid
,
1062 "index out of bounds", goto error
);
1064 n_in2
= FN(MULTI(BASE
),dim
)(multi2
, isl_dim_in
);
1066 multi1
= FN(MULTI(BASE
),insert_dims
)(multi1
, isl_dim_in
, in_pos
, n_in2
);
1067 multi2
= FN(MULTI(BASE
),insert_dims
)(multi2
, isl_dim_in
, n_in2
,
1069 multi2
= FN(MULTI(BASE
),insert_dims
)(multi2
, isl_dim_in
, 0, in_pos
);
1071 return FN(MULTI(BASE
),range_splice
)(multi1
, out_pos
, multi2
);
1073 FN(MULTI(BASE
),free
)(multi1
);
1074 FN(MULTI(BASE
),free
)(multi2
);
1079 /* This function is currently only used from isl_aff.c
1081 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),bin_op
)(
1082 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
1083 __isl_give EL
*(*fn
)(__isl_take EL
*, __isl_take EL
*))
1084 __attribute__ ((unused
));
1086 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
1087 * return the result.
1089 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),bin_op
)(
1090 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
,
1091 __isl_give EL
*(*fn
)(__isl_take EL
*, __isl_take EL
*))
1096 multi1
= FN(MULTI(BASE
),cow
)(multi1
);
1097 if (!multi1
|| !multi2
)
1100 ctx
= FN(MULTI(BASE
),get_ctx
)(multi1
);
1101 if (!isl_space_is_equal(multi1
->space
, multi2
->space
))
1102 isl_die(ctx
, isl_error_invalid
,
1103 "spaces don't match", goto error
);
1105 for (i
= 0; i
< multi1
->n
; ++i
) {
1106 multi1
->p
[i
] = fn(multi1
->p
[i
], FN(EL
,copy
)(multi2
->p
[i
]));
1111 FN(MULTI(BASE
),free
)(multi2
);
1114 FN(MULTI(BASE
),free
)(multi1
);
1115 FN(MULTI(BASE
),free
)(multi2
);
1119 /* Subtract "multi2" from "multi1" and return the result.
1121 * The parameters of "multi1" and "multi2" are assumed to have been aligned.
1123 static __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),sub_aligned
)(
1124 __isl_take
MULTI(BASE
) *multi1
, __isl_take
MULTI(BASE
) *multi2
)
1126 return FN(MULTI(BASE
),bin_op
)(multi1
, multi2
, &FN(EL
,sub
));
1129 /* Subtract "multi2" from "multi1" and return the result.
1131 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),sub
)(__isl_take
MULTI(BASE
) *multi1
,
1132 __isl_take
MULTI(BASE
) *multi2
)
1134 return FN(MULTI(BASE
),align_params_multi_multi_and
)(multi1
, multi2
,
1135 &FN(MULTI(BASE
),sub_aligned
));
1138 /* Multiply the elements of "multi" by "v" and return the result.
1140 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_val
)(__isl_take
MULTI(BASE
) *multi
,
1141 __isl_take isl_val
*v
)
1148 if (isl_val_is_one(v
)) {
1153 if (!isl_val_is_rat(v
))
1154 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1155 "expecting rational factor", goto error
);
1157 multi
= FN(MULTI(BASE
),cow
)(multi
);
1161 for (i
= 0; i
< multi
->n
; ++i
) {
1162 multi
->p
[i
] = FN(EL
,scale_val
)(multi
->p
[i
], isl_val_copy(v
));
1171 return FN(MULTI(BASE
),free
)(multi
);
1174 /* Divide the elements of "multi" by "v" and return the result.
1176 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_down_val
)(
1177 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_val
*v
)
1184 if (isl_val_is_one(v
)) {
1189 if (!isl_val_is_rat(v
))
1190 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1191 "expecting rational factor", goto error
);
1192 if (isl_val_is_zero(v
))
1193 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1194 "cannot scale down by zero", goto error
);
1196 multi
= FN(MULTI(BASE
),cow
)(multi
);
1200 for (i
= 0; i
< multi
->n
; ++i
) {
1201 multi
->p
[i
] = FN(EL
,scale_down_val
)(multi
->p
[i
],
1211 return FN(MULTI(BASE
),free
)(multi
);
1214 /* Multiply the elements of "multi" by the corresponding element of "mv"
1215 * and return the result.
1217 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_multi_val
)(
1218 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1225 if (!isl_space_tuple_is_equal(multi
->space
, isl_dim_out
,
1226 mv
->space
, isl_dim_set
))
1227 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1228 "spaces don't match", goto error
);
1230 multi
= FN(MULTI(BASE
),cow
)(multi
);
1234 for (i
= 0; i
< multi
->n
; ++i
) {
1237 v
= isl_multi_val_get_val(mv
, i
);
1238 multi
->p
[i
] = FN(EL
,scale_val
)(multi
->p
[i
], v
);
1243 isl_multi_val_free(mv
);
1246 isl_multi_val_free(mv
);
1247 return FN(MULTI(BASE
),free
)(multi
);
1250 /* Divide the elements of "multi" by the corresponding element of "mv"
1251 * and return the result.
1253 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),scale_down_multi_val
)(
1254 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1261 if (!isl_space_tuple_is_equal(multi
->space
, isl_dim_out
,
1262 mv
->space
, isl_dim_set
))
1263 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1264 "spaces don't match", goto error
);
1266 multi
= FN(MULTI(BASE
),cow
)(multi
);
1270 for (i
= 0; i
< multi
->n
; ++i
) {
1273 v
= isl_multi_val_get_val(mv
, i
);
1274 multi
->p
[i
] = FN(EL
,scale_down_val
)(multi
->p
[i
], v
);
1279 isl_multi_val_free(mv
);
1282 isl_multi_val_free(mv
);
1283 return FN(MULTI(BASE
),free
)(multi
);
1286 /* Compute the residues of the elements of "multi" modulo
1287 * the corresponding element of "mv" and return the result.
1289 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),mod_multi_val
)(
1290 __isl_take
MULTI(BASE
) *multi
, __isl_take isl_multi_val
*mv
)
1297 if (!isl_space_tuple_is_equal(multi
->space
, isl_dim_out
,
1298 mv
->space
, isl_dim_set
))
1299 isl_die(isl_multi_val_get_ctx(mv
), isl_error_invalid
,
1300 "spaces don't match", goto error
);
1302 multi
= FN(MULTI(BASE
),cow
)(multi
);
1306 for (i
= 0; i
< multi
->n
; ++i
) {
1309 v
= isl_multi_val_get_val(mv
, i
);
1310 multi
->p
[i
] = FN(EL
,mod_val
)(multi
->p
[i
], v
);
1315 isl_multi_val_free(mv
);
1318 isl_multi_val_free(mv
);
1319 return FN(MULTI(BASE
),free
)(multi
);
1322 #ifndef NO_MOVE_DIMS
1323 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "multi"
1324 * to dimensions of "dst_type" at "dst_pos".
1326 * We only support moving input dimensions to parameters and vice versa.
1328 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),move_dims
)(__isl_take
MULTI(BASE
) *multi
,
1329 enum isl_dim_type dst_type
, unsigned dst_pos
,
1330 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1338 !isl_space_is_named_or_nested(multi
->space
, src_type
) &&
1339 !isl_space_is_named_or_nested(multi
->space
, dst_type
))
1342 if (dst_type
== isl_dim_out
|| src_type
== isl_dim_out
)
1343 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1344 "cannot move output/set dimension",
1345 return FN(MULTI(BASE
),free
)(multi
));
1346 if (dst_type
== isl_dim_div
|| src_type
== isl_dim_div
)
1347 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1349 return FN(MULTI(BASE
),free
)(multi
));
1350 if (src_pos
+ n
> isl_space_dim(multi
->space
, src_type
))
1351 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1352 "range out of bounds",
1353 return FN(MULTI(BASE
),free
)(multi
));
1354 if (dst_type
== src_type
)
1355 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_unsupported
,
1356 "moving dims within the same type not supported",
1357 return FN(MULTI(BASE
),free
)(multi
));
1359 multi
= FN(MULTI(BASE
),cow
)(multi
);
1363 multi
->space
= isl_space_move_dims(multi
->space
, dst_type
, dst_pos
,
1364 src_type
, src_pos
, n
);
1366 return FN(MULTI(BASE
),free
)(multi
);
1368 for (i
= 0; i
< multi
->n
; ++i
) {
1369 multi
->p
[i
] = FN(EL
,move_dims
)(multi
->p
[i
], dst_type
, dst_pos
,
1370 src_type
, src_pos
, n
);
1372 return FN(MULTI(BASE
),free
)(multi
);
1379 /* Convert a multiple expression defined over a parameter domain
1380 * into one that is defined over a zero-dimensional set.
1382 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),from_range
)(
1383 __isl_take
MULTI(BASE
) *multi
)
1389 if (!isl_space_is_set(multi
->space
))
1390 isl_die(FN(MULTI(BASE
),get_ctx
)(multi
), isl_error_invalid
,
1391 "not living in a set space",
1392 return FN(MULTI(BASE
),free
)(multi
));
1394 space
= FN(MULTI(BASE
),get_space
)(multi
);
1395 space
= isl_space_from_range(space
);
1396 multi
= FN(MULTI(BASE
),reset_space
)(multi
, space
);
1401 /* Are "multi1" and "multi2" obviously equal?
1403 isl_bool
FN(MULTI(BASE
),plain_is_equal
)(__isl_keep
MULTI(BASE
) *multi1
,
1404 __isl_keep
MULTI(BASE
) *multi2
)
1409 if (!multi1
|| !multi2
)
1410 return isl_bool_error
;
1411 if (multi1
->n
!= multi2
->n
)
1412 return isl_bool_false
;
1413 equal
= isl_space_is_equal(multi1
->space
, multi2
->space
);
1414 if (equal
< 0 || !equal
)
1417 for (i
= 0; i
< multi1
->n
; ++i
) {
1418 equal
= FN(EL
,plain_is_equal
)(multi1
->p
[i
], multi2
->p
[i
]);
1419 if (equal
< 0 || !equal
)
1423 return isl_bool_true
;
1427 /* Return the shared domain of the elements of "multi".
1429 __isl_give isl_set
*FN(MULTI(BASE
),domain
)(__isl_take
MULTI(BASE
) *multi
)
1437 dom
= isl_set_universe(FN(MULTI(BASE
),get_domain_space
)(multi
));
1438 for (i
= 0; i
< multi
->n
; ++i
) {
1441 dom_i
= FN(EL
,domain
)(FN(FN(MULTI(BASE
),get
),BASE
)(multi
, i
));
1442 dom
= isl_set_intersect(dom
, dom_i
);
1445 FN(MULTI(BASE
),free
)(multi
);
1451 /* Return the opposite of "multi".
1453 __isl_give
MULTI(BASE
) *FN(MULTI(BASE
),neg
)(__isl_take
MULTI(BASE
) *multi
)
1457 multi
= FN(MULTI(BASE
),cow
)(multi
);
1461 for (i
= 0; i
< multi
->n
; ++i
) {
1462 multi
->p
[i
] = FN(EL
,neg
)(multi
->p
[i
]);
1464 return FN(MULTI(BASE
),free
)(multi
);