1 /*
2 * Copyright 2011 Sven Verdoolaege
3 * Copyright 2012-2014 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 */
10
11 #include <isl/id.h>
12 #include <isl_space_private.h>
13 #include <isl/set.h>
14 #include <isl_reordering.h>
15
16 #include <isl_multi_macro.h>
17
18 #define MULTI_NAME(BASE) "isl_multi_" #BASE
19
FN(MULTI (BASE),get_ctx)20 isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
21 {
22 return multi ? isl_space_get_ctx(multi->space) : NULL;
23 }
24
25 /* Return the space of "multi".
26 */
FN(MULTI (BASE),peek_space)27 __isl_keep isl_space *FN(MULTI(BASE),peek_space)(__isl_keep MULTI(BASE) *multi)
28 {
29 return multi ? multi->space : NULL;
30 }
31
FN(MULTI (BASE),get_space)32 __isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
33 {
34 return isl_space_copy(FN(MULTI(BASE),peek_space)(multi));
35 }
36
FN(MULTI (BASE),get_domain_space)37 __isl_give isl_space *FN(MULTI(BASE),get_domain_space)(
38 __isl_keep MULTI(BASE) *multi)
39 {
40 return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL;
41 }
42
43 /* Allocate a multi expression living in "space".
44 *
45 * If the number of base expressions is zero, then make sure
46 * there is enough room in the structure for the explicit domain,
47 * in case the type supports such an explicit domain.
48 */
MULTI(BASE)49 __isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)
50 {
51 isl_ctx *ctx;
52 isl_size n;
53 MULTI(BASE) *multi;
54
55 n = isl_space_dim(space, isl_dim_out);
56 if (n < 0)
57 goto error;
58
59 ctx = isl_space_get_ctx(space);
60 if (n > 0)
61 multi = isl_calloc(ctx, MULTI(BASE),
62 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));
63 else
64 multi = isl_calloc(ctx, MULTI(BASE), sizeof(MULTI(BASE)));
65 if (!multi)
66 goto error;
67
68 multi->space = space;
69 multi->n = n;
70 multi->ref = 1;
71 if (FN(MULTI(BASE),has_explicit_domain)(multi))
72 multi = FN(MULTI(BASE),init_explicit_domain)(multi);
73 return multi;
74 error:
75 isl_space_free(space);
76 return NULL;
77 }
78
MULTI(BASE)79 __isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)
80 {
81 int i;
82 MULTI(BASE) *dup;
83
84 if (!multi)
85 return NULL;
86
87 dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));
88 if (!dup)
89 return NULL;
90
91 for (i = 0; i < multi->n; ++i)
92 dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,
93 FN(EL,copy)(multi->u.p[i]));
94 if (FN(MULTI(BASE),has_explicit_domain)(multi))
95 dup = FN(MULTI(BASE),copy_explicit_domain)(dup, multi);
96
97 return dup;
98 }
99
MULTI(BASE)100 __isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)
101 {
102 if (!multi)
103 return NULL;
104
105 if (multi->ref == 1)
106 return multi;
107
108 multi->ref--;
109 return FN(MULTI(BASE),dup)(multi);
110 }
111
MULTI(BASE)112 __isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)
113 {
114 if (!multi)
115 return NULL;
116
117 multi->ref++;
118 return multi;
119 }
120
MULTI(BASE)121 __isl_null MULTI(BASE) *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)
122 {
123 int i;
124
125 if (!multi)
126 return NULL;
127
128 if (--multi->ref > 0)
129 return NULL;
130
131 isl_space_free(multi->space);
132 for (i = 0; i < multi->n; ++i)
133 FN(EL,free)(multi->u.p[i]);
134 if (FN(MULTI(BASE),has_explicit_domain)(multi))
135 FN(MULTI(BASE),free_explicit_domain)(multi);
136 free(multi);
137
138 return NULL;
139 }
140
141 /* Return the space of "multi".
142 * The caller is not allowed to modify "multi" between this call
143 * and the call to *_restore_space because the number
144 * of references needs to stay the same.
145 * The only exception is that isl_multi_*_free can be called instead.
146 * No copy is taken of multi->space if "multi" has only one reference
147 * such that it can be modified inplace if both have only a single reference.
148 */
FN(MULTI (BASE),take_space)149 __isl_give isl_space *FN(MULTI(BASE),take_space)(__isl_keep MULTI(BASE) *multi)
150 {
151 isl_space *space;
152
153 if (!multi)
154 return NULL;
155 if (multi->ref != 1)
156 return FN(MULTI(BASE),get_space)(multi);
157 space = multi->space;
158 multi->space = NULL;
159 return space;
160 }
161
162 /* Set the space of "multi" to "space", where the space of "multi"
163 * may be missing due to a preceding call to isl_multi_*_take_space.
164 * However, in this case, "multi" only has a single reference and
165 * then the call to isl_multi_*_cow has no effect.
166 */
MULTI(BASE)167 __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_space)(
168 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
169 {
170 if (!multi || !space)
171 goto error;
172
173 if (multi->space == space) {
174 isl_space_free(space);
175 return multi;
176 }
177
178 multi = FN(MULTI(BASE),cow)(multi);
179 if (!multi)
180 goto error;
181 isl_space_free(multi->space);
182 multi->space = space;
183
184 return multi;
185 error:
186 FN(MULTI(BASE),free)(multi);
187 isl_space_free(space);
188 return NULL;
189 }
190
FN(MULTI (BASE),dim)191 isl_size FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
192 enum isl_dim_type type)
193 {
194 return isl_space_dim(FN(MULTI(BASE),peek_space)(multi), type);
195 }
196
197 /* Return the number of base expressions in "multi".
198 */
FN(MULTI (BASE),size)199 isl_size FN(MULTI(BASE),size)(__isl_keep MULTI(BASE) *multi)
200 {
201 return multi ? multi->n : isl_size_error;
202 }
203
204 #undef TYPE
205 #define TYPE MULTI(BASE)
206 static
207 #include "check_type_range_templ.c"
208
209 /* Return the base expression at position "pos" in "multi".
210 */
FN(MULTI (BASE),peek_at)211 static __isl_give EL *FN(MULTI(BASE),peek_at)(__isl_keep MULTI(BASE) *multi,
212 int pos)
213 {
214 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)
215 return NULL;
216 return multi->u.p[pos];
217 }
218
219 /* Return a copy of the base expression at position "pos" in "multi".
220 */
FN(MULTI (BASE),get_at)221 __isl_give EL *FN(MULTI(BASE),get_at)(__isl_keep MULTI(BASE) *multi, int pos)
222 {
223 return FN(EL,copy)(FN(MULTI(BASE),peek_at)(multi, pos));
224 }
225
226 /* This is an alternative name for the function above.
227 */
FN(FN (MULTI (BASE),get),BASE)228 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
229 int pos)
230 {
231 return FN(MULTI(BASE),get_at)(multi, pos);
232 }
233
234 /* Return the base expression at position "pos" in "multi".
235 * This may be either a copy or the base expression itself
236 * if there is only one reference to "multi".
237 * This allows the base expression to be modified inplace
238 * if both the multi expression and this base expression
239 * have only a single reference.
240 * The caller is not allowed to modify "multi" between this call and
241 * the subsequent call to isl_multi_*_restore_at_*.
242 * The only exception is that isl_multi_*_free can be called instead.
243 */
FN(MULTI (BASE),take_at)244 static __isl_give EL *FN(MULTI(BASE),take_at)(__isl_keep MULTI(BASE) *multi,
245 int pos)
246 {
247 EL *el;
248
249 if (!multi)
250 return NULL;
251 if (multi->ref != 1)
252 return FN(MULTI(BASE),get_at)(multi, pos);
253 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)
254 return NULL;
255 el = multi->u.p[pos];
256 multi->u.p[pos] = NULL;
257 return el;
258 }
259
260 /* Set the element at position "pos" of "multi" to "el",
261 * where the position may be empty if "multi" has only a single reference.
262 */
MULTI(BASE)263 static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_at)(
264 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
265 {
266 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0 || !el)
267 goto error;
268
269 if (multi->u.p[pos] == el) {
270 FN(EL,free)(el);
271 return multi;
272 }
273
274 multi = FN(MULTI(BASE),cow)(multi);
275 if (!multi)
276 goto error;
277
278 FN(EL,free)(multi->u.p[pos]);
279 multi->u.p[pos] = el;
280
281 return multi;
282 error:
283 FN(MULTI(BASE),free)(multi);
284 FN(EL,free)(el);
285 return NULL;
286 }
287
288 /* Set the element at position "pos" of "multi" to "el",
289 * where the position may be empty if "multi" has only a single reference.
290 * However, the space of "multi" is available and is checked
291 * for compatibility with "el".
292 */
MULTI(BASE)293 static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_check_space)(
294 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
295 {
296 isl_space *space;
297
298 space = FN(MULTI(BASE),peek_space)(multi);
299 if (FN(EL,check_match_domain_space)(el, space) < 0)
300 multi = FN(MULTI(BASE),free)(multi);
301 return FN(MULTI(BASE),restore_at)(multi, pos, el);
302 }
303
304 /* Replace the base expression at position "pos" in "multi" with "el".
305 */
MULTI(BASE)306 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_at)(
307 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
308 {
309 isl_space *multi_space = NULL;
310 isl_space *el_space = NULL;
311 isl_bool match;
312
313 multi_space = FN(MULTI(BASE),get_space)(multi);
314 match = FN(EL,matching_params)(el, multi_space);
315 if (match < 0)
316 goto error;
317 if (!match) {
318 multi = FN(MULTI(BASE),align_params)(multi,
319 FN(EL,get_space)(el));
320 isl_space_free(multi_space);
321 multi_space = FN(MULTI(BASE),get_space)(multi);
322 el = FN(EL,align_params)(el, isl_space_copy(multi_space));
323 }
324
325 multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el);
326
327 isl_space_free(multi_space);
328 isl_space_free(el_space);
329
330 return multi;
331 error:
332 FN(MULTI(BASE),free)(multi);
333 FN(EL,free)(el);
334 isl_space_free(multi_space);
335 isl_space_free(el_space);
336 return NULL;
337 }
338
339 /* This is an alternative name for the function above.
340 */
MULTI(BASE)341 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
342 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
343 {
344 return FN(MULTI(BASE),set_at)(multi, pos, el);
345 }
346
347 /* Return the base expressions of "multi" as a list.
348 */
LIST(EL)349 __isl_give LIST(EL) *FN(MULTI(BASE),get_list)(
350 __isl_keep MULTI(BASE) *multi)
351 {
352 isl_size n;
353 int i;
354 LIST(EL) *list;
355
356 n = FN(MULTI(BASE),size)(multi);
357 if (n < 0)
358 return NULL;
359 list = FN(LIST(EL),alloc)(FN(MULTI(BASE),get_ctx(multi)), n);
360 for (i = 0; i < n; ++i) {
361 EL *el = FN(MULTI(BASE),get_at)(multi, i);
362 list = FN(LIST(EL),add)(list, el);
363 }
364
365 return list;
366 }
367
368 /* Reset the space of "multi". This function is called from isl_pw_templ.c
369 * and doesn't know if the space of an element object is represented
370 * directly or through its domain. It therefore passes along both,
371 * which we pass along to the element function since we don't know how
372 * that is represented either.
373 *
374 * If "multi" has an explicit domain, then the caller is expected
375 * to make sure that any modification that would change the dimensions
376 * of the explicit domain has bee applied before this function is called.
377 */
MULTI(BASE)378 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
379 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
380 __isl_take isl_space *domain)
381 {
382 isl_size n;
383 int i;
384
385 n = FN(MULTI(BASE),size)(multi);
386 if (n < 0 || !space || !domain)
387 goto error;
388
389 for (i = 0; i < n; ++i) {
390 EL *el;
391
392 el = FN(MULTI(BASE),take_at)(multi, i);
393 el = FN(EL,reset_domain_space)(el, isl_space_copy(domain));
394 multi = FN(MULTI(BASE),restore_at)(multi, i, el);
395 }
396 if (FN(MULTI(BASE),has_explicit_domain)(multi))
397 multi = FN(MULTI(BASE),reset_explicit_domain_space)(multi,
398 isl_space_copy(domain));
399 isl_space_free(domain);
400
401 multi = FN(MULTI(BASE),restore_space)(multi, space);
402
403 return multi;
404 error:
405 isl_space_free(domain);
406 isl_space_free(space);
407 FN(MULTI(BASE),free)(multi);
408 return NULL;
409 }
410
MULTI(BASE)411 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
412 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
413 {
414 isl_space *space, *multi_space;
415
416 multi_space = FN(MULTI(BASE),get_space)(multi);
417 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
418 multi_space);
419 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
420 }
421
MULTI(BASE)422 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
423 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
424 {
425 isl_space *domain;
426
427 domain = isl_space_domain(isl_space_copy(space));
428 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
429 }
430
431 /* Reset the user pointer on all identifiers of parameters and tuples
432 * of the space of "multi".
433 */
MULTI(BASE)434 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_user)(
435 __isl_take MULTI(BASE) *multi)
436 {
437 isl_space *space;
438
439 space = FN(MULTI(BASE),get_space)(multi);
440 space = isl_space_reset_user(space);
441
442 return FN(MULTI(BASE),reset_space)(multi, space);
443 }
444
MULTI(BASE)445 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
446 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
447 {
448 int i;
449 isl_size n;
450 isl_space *space;
451
452 n = FN(MULTI(BASE),size)(multi);
453 if (n < 0 || !exp)
454 goto error;
455
456 for (i = 0; i < n; ++i) {
457 EL *el;
458
459 el = FN(MULTI(BASE),take_at)(multi, i);
460 el = FN(EL,realign_domain)(el, isl_reordering_copy(exp));
461 multi = FN(MULTI(BASE),restore_at)(multi, i, el);
462 }
463
464 space = isl_reordering_get_space(exp);
465 multi = FN(MULTI(BASE),reset_domain_space)(multi, space);
466
467 isl_reordering_free(exp);
468 return multi;
469 error:
470 isl_reordering_free(exp);
471 FN(MULTI(BASE),free)(multi);
472 return NULL;
473 }
474
475 /* Align the parameters of "multi" to those of "model".
476 *
477 * If "multi" has an explicit domain, then align the parameters
478 * of the domain first.
479 */
MULTI(BASE)480 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
481 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
482 {
483 isl_ctx *ctx;
484 isl_bool equal_params;
485 isl_space *domain_space;
486 isl_reordering *exp;
487
488 if (!multi || !model)
489 goto error;
490
491 equal_params = isl_space_has_equal_params(multi->space, model);
492 if (equal_params < 0)
493 goto error;
494 if (equal_params) {
495 isl_space_free(model);
496 return multi;
497 }
498
499 ctx = isl_space_get_ctx(model);
500 if (!isl_space_has_named_params(model))
501 isl_die(ctx, isl_error_invalid,
502 "model has unnamed parameters", goto error);
503 if (!isl_space_has_named_params(multi->space))
504 isl_die(ctx, isl_error_invalid,
505 "input has unnamed parameters", goto error);
506
507 if (FN(MULTI(BASE),has_explicit_domain)(multi)) {
508 multi = FN(MULTI(BASE),align_explicit_domain_params)(multi,
509 isl_space_copy(model));
510 if (!multi)
511 goto error;
512 }
513 domain_space = FN(MULTI(BASE),get_domain_space)(multi);
514 exp = isl_parameter_alignment_reordering(domain_space, model);
515 isl_space_free(domain_space);
516 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
517
518 isl_space_free(model);
519 return multi;
520 error:
521 isl_space_free(model);
522 FN(MULTI(BASE),free)(multi);
523 return NULL;
524 }
525
526 /* Create a multi expression in the given space with the elements of "list"
527 * as base expressions.
528 *
529 * Since isl_multi_*_restore_* assumes that the element and
530 * the multi expression have matching spaces, the alignment
531 * (if any) needs to be performed beforehand.
532 */
MULTI(BASE)533 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
534 __isl_take isl_space *space, __isl_take LIST(EL) *list)
535 {
536 int i;
537 isl_size n, dim;
538 isl_ctx *ctx;
539 MULTI(BASE) *multi;
540
541 dim = isl_space_dim(space, isl_dim_out);
542 n = FN(FN(LIST(EL),n),BASE)(list);
543 if (dim < 0 || n < 0)
544 goto error;
545
546 ctx = isl_space_get_ctx(space);
547 if (n != dim)
548 isl_die(ctx, isl_error_invalid,
549 "invalid number of elements in list", goto error);
550
551 for (i = 0; i < n; ++i) {
552 EL *el = FN(LIST(EL),peek)(list, i);
553 space = isl_space_align_params(space, FN(EL,get_space)(el));
554 }
555 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
556 for (i = 0; i < n; ++i) {
557 EL *el = FN(FN(LIST(EL),get),BASE)(list, i);
558 el = FN(EL,align_params)(el, isl_space_copy(space));
559 multi = FN(MULTI(BASE),restore_check_space)(multi, i, el);
560 }
561
562 isl_space_free(space);
563 FN(LIST(EL),free)(list);
564 return multi;
565 error:
566 isl_space_free(space);
567 FN(LIST(EL),free)(list);
568 return NULL;
569 }
570
571 /* This function performs the same operation as isl_multi_*_from_*_list,
572 * but is considered as a function on an isl_space when exported.
573 */
MULTI(BASE)574 __isl_give MULTI(BASE) *FN(isl_space_multi,BASE)(__isl_take isl_space *space,
575 __isl_take LIST(EL) *list)
576 {
577 return FN(FN(MULTI(BASE),from),LIST(BASE))(space, list);
578 }
579
580 /* Drop the "n" output dimensions of "multi" starting at "first",
581 * where the space is assumed to have been adjusted already.
582 */
MULTI(BASE)583 static __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_output_dims)(
584 __isl_take MULTI(BASE) *multi, unsigned first, unsigned n)
585 {
586 int i;
587
588 multi = FN(MULTI(BASE),cow)(multi);
589 if (!multi)
590 return NULL;
591
592 for (i = 0; i < n; ++i)
593 FN(EL,free)(multi->u.p[first + i]);
594 for (i = first; i + n < multi->n; ++i)
595 multi->u.p[i] = multi->u.p[i + n];
596 multi->n -= n;
597 if (n > 0 && FN(MULTI(BASE),has_explicit_domain)(multi))
598 multi = FN(MULTI(BASE),init_explicit_domain)(multi);
599
600 return multi;
601 }
602
MULTI(BASE)603 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
604 __isl_take MULTI(BASE) *multi,
605 enum isl_dim_type type, unsigned first, unsigned n)
606 {
607 isl_space *space;
608 isl_size size;
609 int i;
610
611 if (FN(MULTI(BASE),check_range)(multi, type, first, n) < 0)
612 return FN(MULTI(BASE),free)(multi);
613
614 space = FN(MULTI(BASE),take_space)(multi);
615 space = isl_space_drop_dims(space, type, first, n);
616 multi = FN(MULTI(BASE),restore_space)(multi, space);
617
618 if (type == isl_dim_out)
619 return FN(MULTI(BASE),drop_output_dims)(multi, first, n);
620
621 if (FN(MULTI(BASE),has_explicit_domain)(multi))
622 multi = FN(MULTI(BASE),drop_explicit_domain_dims)(multi,
623 type, first, n);
624
625 size = FN(MULTI(BASE),size)(multi);
626 if (size < 0)
627 return FN(MULTI(BASE),free)(multi);
628 for (i = 0; i < size; ++i) {
629 EL *el;
630
631 el = FN(MULTI(BASE),take_at)(multi, i);
632 el = FN(EL,drop_dims)(el, type, first, n);
633 multi = FN(MULTI(BASE),restore_at)(multi, i, el);
634 }
635
636 return multi;
637 }
638
639 #undef TYPE
640 #define TYPE MULTI(BASE)
641
642 #include "isl_check_named_params_templ.c"
643 static
644 #include "isl_align_params_bin_templ.c"
645
646 /* Given two MULTI(BASE)s A -> B and C -> D,
647 * construct a MULTI(BASE) (A * C) -> [B -> D].
648 *
649 * If "multi1" and/or "multi2" has an explicit domain, then
650 * intersect the domain of the result with these explicit domains.
651 */
MULTI(BASE)652 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
653 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
654 {
655 int i;
656 isl_size n1, n2;
657 EL *el;
658 isl_space *space;
659 MULTI(BASE) *res;
660
661 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
662 n1 = FN(MULTI(BASE),size)(multi1);
663 n2 = FN(MULTI(BASE),size)(multi2);
664 if (n1 < 0 || n2 < 0)
665 goto error;
666
667 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
668 FN(MULTI(BASE),get_space)(multi2));
669 res = FN(MULTI(BASE),alloc)(space);
670
671 for (i = 0; i < n1; ++i) {
672 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
673 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
674 }
675
676 for (i = 0; i < n2; ++i) {
677 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
678 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
679 }
680
681 if (FN(MULTI(BASE),has_explicit_domain)(multi1))
682 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi1);
683 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
684 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi2);
685
686 FN(MULTI(BASE),free)(multi1);
687 FN(MULTI(BASE),free)(multi2);
688 return res;
689 error:
690 FN(MULTI(BASE),free)(multi1);
691 FN(MULTI(BASE),free)(multi2);
692 return NULL;
693 }
694
695 /* Is the range of "multi" a wrapped relation?
696 */
FN(MULTI (BASE),range_is_wrapping)697 isl_bool FN(MULTI(BASE),range_is_wrapping)(__isl_keep MULTI(BASE) *multi)
698 {
699 if (!multi)
700 return isl_bool_error;
701 return isl_space_range_is_wrapping(multi->space);
702 }
703
704 /* Given a function A -> [B -> C], extract the function A -> B.
705 */
MULTI(BASE)706 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_domain)(
707 __isl_take MULTI(BASE) *multi)
708 {
709 isl_space *space;
710 isl_size total, keep;
711
712 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
713 if (total < 0)
714 return FN(MULTI(BASE),free)(multi);
715 if (!isl_space_range_is_wrapping(multi->space))
716 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
717 "range is not a product",
718 return FN(MULTI(BASE),free)(multi));
719
720 space = FN(MULTI(BASE),get_space)(multi);
721 space = isl_space_range_factor_domain(space);
722 keep = isl_space_dim(space, isl_dim_out);
723 if (keep < 0)
724 multi = FN(MULTI(BASE),free)(multi);
725 multi = FN(MULTI(BASE),drop_dims)(multi,
726 isl_dim_out, keep, total - keep);
727 multi = FN(MULTI(BASE),reset_space)(multi, space);
728
729 return multi;
730 }
731
732 /* Given a function A -> [B -> C], extract the function A -> C.
733 */
MULTI(BASE)734 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)(
735 __isl_take MULTI(BASE) *multi)
736 {
737 isl_space *space;
738 isl_size total, keep;
739
740 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
741 if (total < 0)
742 return FN(MULTI(BASE),free)(multi);
743 if (!isl_space_range_is_wrapping(multi->space))
744 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
745 "range is not a product",
746 return FN(MULTI(BASE),free)(multi));
747
748 space = FN(MULTI(BASE),get_space)(multi);
749 space = isl_space_range_factor_range(space);
750 keep = isl_space_dim(space, isl_dim_out);
751 if (keep < 0)
752 multi = FN(MULTI(BASE),free)(multi);
753 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);
754 multi = FN(MULTI(BASE),reset_space)(multi, space);
755
756 return multi;
757 }
758
759 /* Given a function [B -> C], extract the function C.
760 */
MULTI(BASE)761 __isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)(
762 __isl_take MULTI(BASE) *multi)
763 {
764 isl_space *space;
765 isl_size total, keep;
766
767 total = FN(MULTI(BASE),dim)(multi, isl_dim_set);
768 if (total < 0)
769 return FN(MULTI(BASE),free)(multi);
770 if (!isl_space_is_wrapping(multi->space))
771 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
772 "not a product", return FN(MULTI(BASE),free)(multi));
773
774 space = FN(MULTI(BASE),get_space)(multi);
775 space = isl_space_factor_range(space);
776 keep = isl_space_dim(space, isl_dim_set);
777 if (keep < 0)
778 multi = FN(MULTI(BASE),free)(multi);
779 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_set, 0, total - keep);
780 multi = FN(MULTI(BASE),reset_space)(multi, space);
781
782 return multi;
783 }
784
MULTI(BASE)785 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
786 __isl_take MULTI(BASE) *multi)
787 {
788 isl_space *space;
789
790 space = FN(MULTI(BASE),take_space)(multi);
791 space = isl_space_flatten_range(space);
792 multi = FN(MULTI(BASE),restore_space)(multi, space);
793
794 return multi;
795 }
796
797 /* Given two MULTI(BASE)s A -> B and C -> D,
798 * construct a MULTI(BASE) (A * C) -> (B, D).
799 */
MULTI(BASE)800 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
801 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
802 {
803 MULTI(BASE) *multi;
804
805 multi = FN(MULTI(BASE),range_product)(multi1, multi2);
806 multi = FN(MULTI(BASE),flatten_range)(multi);
807 return multi;
808 }
809
810 /* Given two multi expressions, "multi1"
811 *
812 * [A] -> [B1 B2]
813 *
814 * where B2 starts at position "pos", and "multi2"
815 *
816 * [A] -> [D]
817 *
818 * return the multi expression
819 *
820 * [A] -> [B1 D B2]
821 */
MULTI(BASE)822 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
823 __isl_take MULTI(BASE) *multi1, unsigned pos,
824 __isl_take MULTI(BASE) *multi2)
825 {
826 MULTI(BASE) *res;
827 isl_size dim;
828
829 dim = FN(MULTI(BASE),size)(multi1);
830 if (dim < 0 || !multi2)
831 goto error;
832
833 if (FN(MULTI(BASE),check_range)(multi1, isl_dim_out, pos, 0) < 0)
834 goto error;
835
836 res = FN(MULTI(BASE),copy)(multi1);
837 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
838 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
839
840 res = FN(MULTI(BASE),flat_range_product)(res, multi2);
841 res = FN(MULTI(BASE),flat_range_product)(res, multi1);
842
843 return res;
844 error:
845 FN(MULTI(BASE),free)(multi1);
846 FN(MULTI(BASE),free)(multi2);
847 return NULL;
848 }
849
850 #undef TYPE
851 #define TYPE MULTI(BASE)
852
853 static
854 #include "isl_type_has_equal_space_bin_templ.c"
855 static
856 #include "isl_type_check_equal_space_templ.c"
857
858 /* This function is currently only used from isl_aff.c
859 */
860 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
861 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
862 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
863 __attribute__ ((unused));
864
865 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
866 * return the result.
867 *
868 * If "multi2" has an explicit domain, then
869 * intersect the domain of the result with this explicit domain.
870 */
MULTI(BASE)871 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
872 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
873 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
874 {
875 isl_size n;
876 int i;
877
878 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
879 n = FN(MULTI(BASE),size)(multi1);
880 if (n < 0 || FN(MULTI(BASE),check_equal_space)(multi1, multi2) < 0)
881 goto error;
882
883 for (i = 0; i < n; ++i) {
884 EL *el1, *el2;
885
886 el2 = FN(MULTI(BASE),get_at)(multi2, i);
887 el1 = FN(MULTI(BASE),take_at)(multi1, i);
888 el1 = fn(el1, el2);
889 multi1 = FN(MULTI(BASE),restore_at)(multi1, i, el1);
890 }
891
892 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
893 multi1 = FN(MULTI(BASE),intersect_explicit_domain)(multi1,
894 multi2);
895
896 FN(MULTI(BASE),free)(multi2);
897 return multi1;
898 error:
899 FN(MULTI(BASE),free)(multi1);
900 FN(MULTI(BASE),free)(multi2);
901 return NULL;
902 }
903
904 /* Only used on some multi-expressions.
905 */
906 static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
907 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
908
909 /* Does "test" succeed on any base expression of "multi"?
910 */
FN(MULTI (BASE),any)911 static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
912 isl_bool (*test)(__isl_keep EL *))
913 {
914 isl_size n;
915 int i;
916
917 n = FN(MULTI(BASE),size)(multi);
918 if (n < 0)
919 return isl_bool_error;
920
921 for (i = 0; i < n; ++i) {
922 isl_bool any = test(multi->u.p[i]);
923 if (any < 0 || any)
924 return any;
925 }
926
927 return isl_bool_false;
928 }
929
930 /* Only used on some multi-expressions.
931 */
932 static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
933 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
934
935 /* Does "test" succeed on every base expression of "multi"?
936 */
FN(MULTI (BASE),every)937 static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
938 isl_bool (*test)(__isl_keep EL *))
939 {
940 isl_size n;
941 int i;
942
943 n = FN(MULTI(BASE),size)(multi);
944 if (n < 0)
945 return isl_bool_error;
946
947 for (i = 0; i < n; ++i) {
948 isl_bool every = test(multi->u.p[i]);
949 if (every < 0 || !every)
950 return every;
951 }
952
953 return isl_bool_true;
954 }
955
956 #undef TYPE
957 #define TYPE MULTI(BASE)
958 #include "isl_from_range_templ.c"
959
960 /* Are "multi1" and "multi2" obviously equal?
961 */
FN(MULTI (BASE),plain_is_equal)962 isl_bool FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1,
963 __isl_keep MULTI(BASE) *multi2)
964 {
965 int i;
966 isl_bool equal;
967
968 if (!multi1 || !multi2)
969 return isl_bool_error;
970 if (multi1->n != multi2->n)
971 return isl_bool_false;
972 equal = isl_space_is_equal(multi1->space, multi2->space);
973 if (equal < 0 || !equal)
974 return equal;
975
976 for (i = 0; i < multi1->n; ++i) {
977 equal = FN(EL,plain_is_equal)(multi1->u.p[i], multi2->u.p[i]);
978 if (equal < 0 || !equal)
979 return equal;
980 }
981
982 if (FN(MULTI(BASE),has_explicit_domain)(multi1) ||
983 FN(MULTI(BASE),has_explicit_domain)(multi2)) {
984 equal = FN(MULTI(BASE),equal_explicit_domain)(multi1, multi2);
985 if (equal < 0 || !equal)
986 return equal;
987 }
988
989 return isl_bool_true;
990 }
991