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 if (FN(EL,check_match_domain_space)(el, multi_space) < 0)
233 if (pos < 0 || pos >= multi->n)
234 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
235 "index out of bounds", goto error);
237 FN(EL,free)(multi->p[pos]);
240 isl_space_free(multi_space);
241 isl_space_free(el_space);
245 FN(MULTI(BASE),free)(multi);
247 isl_space_free(multi_space);
248 isl_space_free(el_space);
252 /* Reset the space of "multi". This function is called from isl_pw_templ.c
253 * and doesn't know if the space of an element object is represented
254 * directly or through its domain. It therefore passes along both,
255 * which we pass along to the element function since we don't how
256 * that is represented either.
258 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
259 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
260 __isl_take isl_space *domain)
264 multi = FN(MULTI(BASE),cow)(multi);
265 if (!multi || !space || !domain)
268 for (i = 0; i < multi->n; ++i) {
269 multi->p[i] = FN(EL,reset_domain_space)(multi->p[i],
270 isl_space_copy(domain));
274 isl_space_free(domain);
275 isl_space_free(multi->space);
276 multi->space = space;
280 isl_space_free(domain);
281 isl_space_free(space);
282 FN(MULTI(BASE),free)(multi);
286 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
287 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
291 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
292 isl_space_copy(multi->space));
293 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
296 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
297 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
301 domain = isl_space_domain(isl_space_copy(space));
302 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
305 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_name)(
306 __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
311 multi = FN(MULTI(BASE),cow)(multi);
315 space = FN(MULTI(BASE),get_space)(multi);
316 space = isl_space_set_tuple_name(space, type, s);
318 return FN(MULTI(BASE),reset_space)(multi, space);
321 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
322 __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
323 __isl_take isl_id *id)
327 multi = FN(MULTI(BASE),cow)(multi);
329 return isl_id_free(id);
331 space = FN(MULTI(BASE),get_space)(multi);
332 space = isl_space_set_tuple_id(space, type, id);
334 return FN(MULTI(BASE),reset_space)(multi, space);
337 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
338 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
342 multi = FN(MULTI(BASE),cow)(multi);
346 for (i = 0; i < multi->n; ++i) {
347 multi->p[i] = FN(EL,realign_domain)(multi->p[i],
348 isl_reordering_copy(exp));
353 multi = FN(MULTI(BASE),reset_domain_space)(multi,
354 isl_space_copy(exp->dim));
356 isl_reordering_free(exp);
359 isl_reordering_free(exp);
360 FN(MULTI(BASE),free)(multi);
364 /* Align the parameters of "multi" to those of "model".
366 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
367 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
371 if (!multi || !model)
374 ctx = isl_space_get_ctx(model);
375 if (!isl_space_has_named_params(model))
376 isl_die(ctx, isl_error_invalid,
377 "model has unnamed parameters", goto error);
378 if (!isl_space_has_named_params(multi->space))
379 isl_die(ctx, isl_error_invalid,
380 "input has unnamed parameters", goto error);
381 if (!isl_space_match(multi->space, isl_dim_param,
382 model, isl_dim_param)) {
385 model = isl_space_params(model);
386 exp = isl_parameter_alignment_reordering(multi->space, model);
387 exp = isl_reordering_extend_space(exp,
388 FN(MULTI(BASE),get_domain_space)(multi));
389 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
392 isl_space_free(model);
395 isl_space_free(model);
396 FN(MULTI(BASE),free)(multi);
400 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
401 __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
402 __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
403 __isl_take isl_set *set))
409 if (isl_space_match(multi->space, isl_dim_param,
410 set->dim, isl_dim_param))
411 return fn(multi, set);
412 ctx = FN(MULTI(BASE),get_ctx)(multi);
413 if (!isl_space_has_named_params(multi->space) ||
414 !isl_space_has_named_params(set->dim))
415 isl_die(ctx, isl_error_invalid,
416 "unaligned unnamed parameters", goto error);
417 multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
418 set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
419 return fn(multi, set);
421 FN(MULTI(BASE),free)(multi);
426 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
427 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
431 if (!multi || !context)
434 for (i = 0; i < multi->n; ++i) {
435 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
440 isl_set_free(context);
443 isl_set_free(context);
444 FN(MULTI(BASE),free)(multi);
448 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
449 __isl_take isl_set *context)
451 return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
452 &FN(MULTI(BASE),gist_aligned));
455 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
456 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
458 isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
459 isl_set *dom_context = isl_set_universe(space);
460 dom_context = isl_set_intersect_params(dom_context, context);
461 return FN(MULTI(BASE),gist)(multi, dom_context);
464 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
465 __isl_take isl_space *space, __isl_take LIST(EL) *list)
475 ctx = isl_space_get_ctx(space);
476 n = FN(FN(LIST(EL),n),BASE)(list);
477 if (n != isl_space_dim(space, isl_dim_out))
478 isl_die(ctx, isl_error_invalid,
479 "invalid number of elements in list", goto error);
481 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
482 for (i = 0; i < n; ++i) {
483 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
484 FN(FN(LIST(EL),get),BASE)(list, i));
487 isl_space_free(space);
488 FN(LIST(EL),free)(list);
491 isl_space_free(space);
492 FN(LIST(EL),free)(list);
496 /* Create a multi expression in the given space that maps each
497 * input dimension to the corresponding output dimension.
499 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
508 if (isl_space_is_set(space))
509 isl_die(isl_space_get_ctx(space), isl_error_invalid,
510 "expecting map space", goto error);
512 n = isl_space_dim(space, isl_dim_out);
513 if (n != isl_space_dim(space, isl_dim_in))
514 isl_die(isl_space_get_ctx(space), isl_error_invalid,
515 "number of input and output dimensions needs to be "
516 "the same", goto error);
518 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
521 isl_space_free(space);
525 space = isl_space_domain(space);
526 ls = isl_local_space_from_space(space);
528 for (i = 0; i < n; ++i) {
530 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
532 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
535 isl_local_space_free(ls);
539 isl_space_free(space);
543 /* Construct a multi expression in the given space with value zero in
544 * each of the output dimensions.
546 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
554 n = isl_space_dim(space , isl_dim_out);
555 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
558 isl_space_free(space);
564 space = isl_space_domain(space);
565 ls = isl_local_space_from_space(space);
566 el = FN(EL,zero_on_domain)(ls);
568 for (i = 0; i < n; ++i)
569 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
578 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
582 multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
583 multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
588 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
589 __isl_take MULTI(BASE) *multi,
590 enum isl_dim_type type, unsigned first, unsigned n)
595 multi = FN(MULTI(BASE),cow)(multi);
599 dim = FN(MULTI(BASE),dim)(multi, type);
600 if (first + n > dim || first + n < first)
601 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
602 "index out of bounds",
603 return FN(MULTI(BASE),cow)(multi));
605 multi->space = isl_space_drop_dims(multi->space, type, first, n);
607 return FN(MULTI(BASE),cow)(multi);
609 if (type == isl_dim_out) {
610 for (i = 0; i < n; ++i)
611 FN(EL,free)(multi->p[first + i]);
612 for (i = first; i + n < multi->n; ++i)
613 multi->p[i] = multi->p[i + n];
619 for (i = 0; i < multi->n; ++i) {
620 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
622 return FN(MULTI(BASE),cow)(multi);
628 /* Given two MULTI(BASE)s A -> B and C -> D,
629 * construct a MULTI(BASE) (A * C) -> (B, D).
631 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
632 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
639 if (!multi1 || !multi2)
642 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
643 FN(MULTI(BASE),get_space)(multi2));
644 res = FN(MULTI(BASE),alloc)(space);
646 n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
647 n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
649 for (i = 0; i < n1; ++i) {
650 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
651 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
654 for (i = 0; i < n2; ++i) {
655 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
656 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
659 FN(MULTI(BASE),free)(multi1);
660 FN(MULTI(BASE),free)(multi2);
663 FN(MULTI(BASE),free)(multi1);
664 FN(MULTI(BASE),free)(multi2);
668 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
669 __isl_take MULTI(BASE) *multi)
674 if (!multi->space->nested[1])
677 multi = FN(MULTI(BASE),cow)(multi);
681 multi->space = isl_space_flatten_range(multi->space);
683 return FN(MULTI(BASE),free)(multi);
688 /* Given two MULTI(BASE)s A -> B and C -> D,
689 * construct a MULTI(BASE) (A * C) -> [B -> D].
691 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
692 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
696 multi = FN(MULTI(BASE),range_product)(multi1, multi2);
697 multi = FN(MULTI(BASE),flatten_range)(multi);
701 /* Given two multi expressions, "multi1"
705 * where B2 starts at position "pos", and "multi2"
709 * return the multi expression
713 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
714 __isl_take MULTI(BASE) *multi1, unsigned pos,
715 __isl_take MULTI(BASE) *multi2)
720 if (!multi1 || !multi2)
723 dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
725 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
726 "index out of bounds", goto error);
728 res = FN(MULTI(BASE),copy)(multi1);
729 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
730 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
732 res = FN(MULTI(BASE),flat_range_product)(res, multi2);
733 res = FN(MULTI(BASE),flat_range_product)(res, multi1);
737 FN(MULTI(BASE),free)(multi1);
738 FN(MULTI(BASE),free)(multi2);
742 /* Given two multi expressions, "multi1"
746 * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
751 * return the multi expression
753 * [A1 C A2] -> [B1 D B2]
755 * We first insert input dimensions to obtain
757 * [A1 C A2] -> [B1 B2]
763 * and then apply range_splice.
765 __isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
766 __isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
767 __isl_take MULTI(BASE) *multi2)
772 if (!multi1 || !multi2)
775 n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
777 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
778 "index out of bounds", goto error);
780 n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
782 multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
783 multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
785 multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
787 return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
789 FN(MULTI(BASE),free)(multi1);
790 FN(MULTI(BASE),free)(multi2);
794 /* This function is currently only used from isl_aff.c
796 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
797 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
798 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
799 __attribute__ ((unused));
801 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
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 *))
811 multi1 = FN(MULTI(BASE),cow)(multi1);
812 if (!multi1 || !multi2)
815 ctx = FN(MULTI(BASE),get_ctx)(multi1);
816 if (!isl_space_is_equal(multi1->space, multi2->space))
817 isl_die(ctx, isl_error_invalid,
818 "spaces don't match", goto error);
820 for (i = 0; i < multi1->n; ++i) {
821 multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
826 FN(MULTI(BASE),free)(multi2);
829 FN(MULTI(BASE),free)(multi1);
830 FN(MULTI(BASE),free)(multi2);