2 * Copyright 2011 Sven Verdoolaege
3 * Copyright 2012 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 __isl_give MULTI(BASE) *FN(MULTI(BASE),insert_dims)(
127 __isl_take MULTI(BASE) *multi,
128 enum isl_dim_type type, unsigned first, unsigned n)
134 if (type == isl_dim_out)
135 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
136 "cannot insert output/set dimensions",
137 return FN(MULTI(BASE),free)(multi));
138 if (n == 0 && !isl_space_is_named_or_nested(multi->space, type))
141 multi = FN(MULTI(BASE),cow)(multi);
145 multi->space = isl_space_insert_dims(multi->space, type, first, n);
147 return FN(MULTI(BASE),free)(multi);
149 for (i = 0; i < multi->n; ++i) {
150 multi->p[i] = FN(EL,insert_dims)(multi->p[i], type, first, n);
152 return FN(MULTI(BASE),free)(multi);
158 __isl_give MULTI(BASE) *FN(MULTI(BASE),add_dims)(__isl_take MULTI(BASE) *multi,
159 enum isl_dim_type type, unsigned n)
163 pos = FN(MULTI(BASE),dim)(multi, type);
165 return FN(MULTI(BASE),insert_dims)(multi, type, pos, n);
168 unsigned FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
169 enum isl_dim_type type)
171 return multi ? isl_space_dim(multi->space, type) : 0;
174 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_name)(
175 __isl_take MULTI(BASE) *multi,
176 enum isl_dim_type type, unsigned pos, const char *s)
180 multi = FN(MULTI(BASE),cow)(multi);
184 multi->space = isl_space_set_dim_name(multi->space, type, pos, s);
186 return FN(MULTI(BASE),free)(multi);
188 if (type == isl_dim_out)
190 for (i = 0; i < multi->n; ++i) {
191 multi->p[i] = FN(EL,set_dim_name)(multi->p[i], type, pos, s);
193 return FN(MULTI(BASE),free)(multi);
199 const char *FN(MULTI(BASE),get_tuple_name)(__isl_keep MULTI(BASE) *multi,
200 enum isl_dim_type type)
202 return multi ? isl_space_get_tuple_name(multi->space, type) : NULL;
205 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
212 ctx = FN(MULTI(BASE),get_ctx)(multi);
213 if (pos < 0 || pos >= multi->n)
214 isl_die(ctx, isl_error_invalid,
215 "index out of bounds", return NULL);
216 return FN(EL,copy)(multi->p[pos]);
219 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
220 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
222 isl_space *multi_space = NULL;
223 isl_space *el_space = NULL;
225 multi = FN(MULTI(BASE),cow)(multi);
229 multi_space = FN(MULTI(BASE),get_space)(multi);
230 el_space = FN(EL,get_space)(el);
232 if (!isl_space_match(multi_space, isl_dim_param,
233 el_space, isl_dim_param))
234 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
235 "parameters don't match", goto error);
236 if (!isl_space_tuple_match(multi_space, isl_dim_in,
237 el_space, isl_dim_in))
238 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
239 "domains don't match", goto error);
241 if (pos < 0 || pos >= multi->n)
242 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
243 "index out of bounds", goto error);
245 FN(EL,free)(multi->p[pos]);
248 isl_space_free(multi_space);
249 isl_space_free(el_space);
253 FN(MULTI(BASE),free)(multi);
255 isl_space_free(multi_space);
256 isl_space_free(el_space);
260 /* Reset the space of "multi". This function is called from isl_pw_templ.c
261 * and doesn't know if the space of an element object is represented
262 * directly or through its domain. It therefore passes along both,
263 * which we pass along to the element function since we don't how
264 * that is represented either.
266 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
267 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
268 __isl_take isl_space *domain)
272 multi = FN(MULTI(BASE),cow)(multi);
273 if (!multi || !space || !domain)
276 for (i = 0; i < multi->n; ++i) {
277 multi->p[i] = FN(EL,reset_domain_space)(multi->p[i],
278 isl_space_copy(domain));
282 isl_space_free(domain);
283 isl_space_free(multi->space);
284 multi->space = space;
288 isl_space_free(domain);
289 isl_space_free(space);
290 FN(MULTI(BASE),free)(multi);
294 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
295 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
299 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
300 isl_space_copy(multi->space));
301 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
304 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
305 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
309 domain = isl_space_domain(isl_space_copy(space));
310 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
313 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_name)(
314 __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
319 multi = FN(MULTI(BASE),cow)(multi);
323 space = FN(MULTI(BASE),get_space)(multi);
324 space = isl_space_set_tuple_name(space, type, s);
326 return FN(MULTI(BASE),reset_space)(multi, space);
329 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
330 __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
331 __isl_take isl_id *id)
335 multi = FN(MULTI(BASE),cow)(multi);
337 return isl_id_free(id);
339 space = FN(MULTI(BASE),get_space)(multi);
340 space = isl_space_set_tuple_id(space, type, id);
342 return FN(MULTI(BASE),reset_space)(multi, space);
345 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
346 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
350 multi = FN(MULTI(BASE),cow)(multi);
354 for (i = 0; i < multi->n; ++i) {
355 multi->p[i] = FN(EL,realign_domain)(multi->p[i],
356 isl_reordering_copy(exp));
361 multi = FN(MULTI(BASE),reset_domain_space)(multi,
362 isl_space_copy(exp->dim));
364 isl_reordering_free(exp);
367 isl_reordering_free(exp);
368 FN(MULTI(BASE),free)(multi);
372 /* Align the parameters of "multi" to those of "model".
374 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
375 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
379 if (!multi || !model)
382 ctx = isl_space_get_ctx(model);
383 if (!isl_space_has_named_params(model))
384 isl_die(ctx, isl_error_invalid,
385 "model has unnamed parameters", goto error);
386 if (!isl_space_has_named_params(multi->space))
387 isl_die(ctx, isl_error_invalid,
388 "input has unnamed parameters", goto error);
389 if (!isl_space_match(multi->space, isl_dim_param,
390 model, isl_dim_param)) {
393 model = isl_space_params(model);
394 exp = isl_parameter_alignment_reordering(multi->space, model);
395 exp = isl_reordering_extend_space(exp,
396 FN(MULTI(BASE),get_domain_space)(multi));
397 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
400 isl_space_free(model);
403 isl_space_free(model);
404 FN(MULTI(BASE),free)(multi);
408 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
409 __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
410 __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
411 __isl_take isl_set *set))
417 if (isl_space_match(multi->space, isl_dim_param,
418 set->dim, isl_dim_param))
419 return fn(multi, set);
420 ctx = FN(MULTI(BASE),get_ctx)(multi);
421 if (!isl_space_has_named_params(multi->space) ||
422 !isl_space_has_named_params(set->dim))
423 isl_die(ctx, isl_error_invalid,
424 "unaligned unnamed parameters", goto error);
425 multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
426 set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
427 return fn(multi, set);
429 FN(MULTI(BASE),free)(multi);
434 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
435 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
439 if (!multi || !context)
442 for (i = 0; i < multi->n; ++i) {
443 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
448 isl_set_free(context);
451 isl_set_free(context);
452 FN(MULTI(BASE),free)(multi);
456 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
457 __isl_take isl_set *context)
459 return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
460 &FN(MULTI(BASE),gist_aligned));
463 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
464 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
466 isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
467 isl_set *dom_context = isl_set_universe(space);
468 dom_context = isl_set_intersect_params(dom_context, context);
469 return FN(MULTI(BASE),gist)(multi, dom_context);
472 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
473 __isl_take isl_space *space, __isl_take LIST(EL) *list)
483 ctx = isl_space_get_ctx(space);
484 n = FN(FN(LIST(EL),n),BASE)(list);
485 if (n != isl_space_dim(space, isl_dim_out))
486 isl_die(ctx, isl_error_invalid,
487 "invalid number of elements in list", goto error);
489 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
490 for (i = 0; i < n; ++i) {
491 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
492 FN(FN(LIST(EL),get),BASE)(list, i));
495 isl_space_free(space);
496 FN(LIST(EL),free)(list);
499 isl_space_free(space);
500 FN(LIST(EL),free)(list);
504 /* Create a multi expression in the given space that maps each
505 * input dimension to the corresponding output dimension.
507 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
516 if (isl_space_is_set(space))
517 isl_die(isl_space_get_ctx(space), isl_error_invalid,
518 "expecting map space", goto error);
520 n = isl_space_dim(space, isl_dim_out);
521 if (n != isl_space_dim(space, isl_dim_in))
522 isl_die(isl_space_get_ctx(space), isl_error_invalid,
523 "number of input and output dimensions needs to be "
524 "the same", goto error);
526 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
529 isl_space_free(space);
533 space = isl_space_domain(space);
534 ls = isl_local_space_from_space(space);
536 for (i = 0; i < n; ++i) {
538 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
540 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
543 isl_local_space_free(ls);
547 isl_space_free(space);
551 /* Construct a multi expression in the given space with value zero in
552 * each of the output dimensions.
554 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
562 n = isl_space_dim(space , isl_dim_out);
563 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
566 isl_space_free(space);
572 space = isl_space_domain(space);
573 ls = isl_local_space_from_space(space);
574 el = FN(EL,zero_on_domain)(ls);
576 for (i = 0; i < n; ++i)
577 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
586 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
590 multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
591 multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
596 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
597 __isl_take MULTI(BASE) *multi,
598 enum isl_dim_type type, unsigned first, unsigned n)
603 multi = FN(MULTI(BASE),cow)(multi);
607 dim = FN(MULTI(BASE),dim)(multi, type);
608 if (first + n > dim || first + n < first)
609 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
610 "index out of bounds",
611 return FN(MULTI(BASE),cow)(multi));
613 multi->space = isl_space_drop_dims(multi->space, type, first, n);
615 return FN(MULTI(BASE),cow)(multi);
617 if (type == isl_dim_out) {
618 for (i = 0; i < n; ++i)
619 FN(EL,free)(multi->p[first + i]);
620 for (i = first; i + n < multi->n; ++i)
621 multi->p[i] = multi->p[i + n];
627 for (i = 0; i < multi->n; ++i) {
628 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
630 return FN(MULTI(BASE),cow)(multi);
636 /* Given two MULTI(BASE)s A -> B and C -> D,
637 * construct a MULTI(BASE) (A * C) -> (B, D).
639 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
640 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
647 if (!multi1 || !multi2)
650 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
651 FN(MULTI(BASE),get_space)(multi2));
652 res = FN(MULTI(BASE),alloc)(space);
654 n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
655 n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
657 for (i = 0; i < n1; ++i) {
658 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
659 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
662 for (i = 0; i < n2; ++i) {
663 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
664 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
667 FN(MULTI(BASE),free)(multi1);
668 FN(MULTI(BASE),free)(multi2);
671 FN(MULTI(BASE),free)(multi1);
672 FN(MULTI(BASE),free)(multi2);
676 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
677 __isl_take MULTI(BASE) *multi)
682 if (!multi->space->nested[1])
685 multi = FN(MULTI(BASE),cow)(multi);
689 multi->space = isl_space_flatten_range(multi->space);
691 return FN(MULTI(BASE),free)(multi);
696 /* Given two MULTI(BASE)s A -> B and C -> D,
697 * construct a MULTI(BASE) (A * C) -> [B -> D].
699 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
700 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
704 multi = FN(MULTI(BASE),range_product)(multi1, multi2);
705 multi = FN(MULTI(BASE),flatten_range)(multi);
709 /* Given two multi expressions, "multi1"
713 * where B2 starts at position "pos", and "multi2"
717 * return the multi expression
721 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
722 __isl_take MULTI(BASE) *multi1, unsigned pos,
723 __isl_take MULTI(BASE) *multi2)
728 if (!multi1 || !multi2)
731 dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
733 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
734 "index out of bounds", goto error);
736 res = FN(MULTI(BASE),copy)(multi1);
737 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
738 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
740 res = FN(MULTI(BASE),flat_range_product)(res, multi2);
741 res = FN(MULTI(BASE),flat_range_product)(res, multi1);
745 FN(MULTI(BASE),free)(multi1);
746 FN(MULTI(BASE),free)(multi2);
750 /* Given two multi expressions, "multi1"
754 * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
759 * return the multi expression
761 * [A1 C A2] -> [B1 D B2]
763 * We first insert input dimensions to obtain
765 * [A1 C A2] -> [B1 B2]
771 * and then apply range_splice.
773 __isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
774 __isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
775 __isl_take MULTI(BASE) *multi2)
780 if (!multi1 || !multi2)
783 n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
785 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
786 "index out of bounds", goto error);
788 n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
790 multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
791 multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
793 multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
795 return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
797 FN(MULTI(BASE),free)(multi1);
798 FN(MULTI(BASE),free)(multi2);
802 /* This function is currently only used from isl_aff.c
804 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
805 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
806 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
807 __attribute__ ((unused));
809 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
812 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
813 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
814 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
819 multi1 = FN(MULTI(BASE),cow)(multi1);
820 if (!multi1 || !multi2)
823 ctx = FN(MULTI(BASE),get_ctx)(multi1);
824 if (!isl_space_is_equal(multi1->space, multi2->space))
825 isl_die(ctx, isl_error_invalid,
826 "spaces don't match", goto error);
828 for (i = 0; i < multi1->n; ++i) {
829 multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
834 FN(MULTI(BASE),free)(multi2);
837 FN(MULTI(BASE),free)(multi1);
838 FN(MULTI(BASE),free)(multi2);