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
20isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
21{
22 return multi ? isl_space_get_ctx(space: multi->space) : NULL;
23}
24
25/* Return the space of "multi".
26 */
27__isl_keep isl_space *FN(MULTI(BASE),peek_space)(__isl_keep MULTI(BASE) *multi)
28{
29 return multi ? multi->space : NULL;
30}
31
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
37__isl_give isl_space *FN(MULTI(BASE),get_domain_space)(
38 __isl_keep MULTI(BASE) *multi)
39{
40 return multi ? isl_space_domain(space: isl_space_copy(space: 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 */
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, type: 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;
74error:
75 isl_space_free(space);
76 return NULL;
77}
78
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)(space: isl_space_copy(space: 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)(multi: dup, pos: i,
93 FN(EL,copy)(id: multi->u.p[i]));
94 if (FN(MULTI(BASE),has_explicit_domain)(multi))
95 dup = FN(MULTI(BASE),copy_explicit_domain)(dst: dup, src: multi);
96
97 return dup;
98}
99
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
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
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(space: multi->space);
132 for (i = 0; i < multi->n; ++i)
133 FN(EL,free)(id: multi->u.p[i]);
134 if (FN(MULTI(BASE),has_explicit_domain)(multi))
135 FN(MULTI(BASE),free_explicit_domain)(multi);
136 free(ptr: 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 */
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 */
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(space: multi->space);
182 multi->space = space;
183
184 return multi;
185error:
186 FN(MULTI(BASE),free)(multi);
187 isl_space_free(space);
188 return NULL;
189}
190
191isl_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 */
199isl_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)
206static
207#include "check_type_range_templ.c"
208
209/* Return the base expression at position "pos" in "multi".
210 */
211static __isl_give EL *FN(MULTI(BASE),peek_at)(__isl_keep MULTI(BASE) *multi,
212 int pos)
213{
214 if (FN(MULTI(BASE),check_range)(obj: multi, type: isl_dim_out, first: pos, n: 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 */
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 */
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 */
244static __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)(obj: multi, type: isl_dim_out, first: pos, n: 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 */
263static __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)(obj: multi, type: isl_dim_out, first: pos, n: 1) < 0 || !el)
267 goto error;
268
269 if (multi->u.p[pos] == el) {
270 FN(EL,free)(id: el);
271 return multi;
272 }
273
274 multi = FN(MULTI(BASE),cow)(multi);
275 if (!multi)
276 goto error;
277
278 FN(EL,free)(id: multi->u.p[pos]);
279 multi->u.p[pos] = el;
280
281 return multi;
282error:
283 FN(MULTI(BASE),free)(multi);
284 FN(EL,free)(id: 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 */
293static __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 */
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, space: 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(space: multi_space);
321 multi_space = FN(MULTI(BASE),get_space)(multi);
322 el = FN(EL,align_params)(el, space: isl_space_copy(space: multi_space));
323 }
324
325 multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el);
326
327 isl_space_free(space: multi_space);
328 isl_space_free(space: el_space);
329
330 return multi;
331error:
332 FN(MULTI(BASE),free)(multi);
333 FN(EL,free)(id: el);
334 isl_space_free(space: multi_space);
335 isl_space_free(space: el_space);
336 return NULL;
337}
338
339/* This is an alternative name for the function above.
340 */
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 */
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, pos: 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 */
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, pos: i);
393 el = FN(EL,reset_domain_space)(el, space: isl_space_copy(space: domain));
394 multi = FN(MULTI(BASE),restore_at)(multi, pos: i, el);
395 }
396 if (FN(MULTI(BASE),has_explicit_domain)(multi))
397 multi = FN(MULTI(BASE),reset_explicit_domain_space)(multi,
398 space: isl_space_copy(space: domain));
399 isl_space_free(space: domain);
400
401 multi = FN(MULTI(BASE),restore_space)(multi, space);
402
403 return multi;
404error:
405 isl_space_free(space: domain);
406 isl_space_free(space);
407 FN(MULTI(BASE),free)(multi);
408 return NULL;
409}
410
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(domain: isl_space_copy(space: domain),
418 model: multi_space);
419 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
420}
421
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(space: 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 */
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
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, pos: i);
460 el = FN(EL,realign_domain)(el, r: isl_reordering_copy(exp));
461 multi = FN(MULTI(BASE),restore_at)(multi, pos: i, el);
462 }
463
464 space = isl_reordering_get_space(r: exp);
465 multi = FN(MULTI(BASE),reset_domain_space)(multi, domain: space);
466
467 isl_reordering_free(exp);
468 return multi;
469error:
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 */
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(space1: multi->space, space2: model);
492 if (equal_params < 0)
493 goto error;
494 if (equal_params) {
495 isl_space_free(space: model);
496 return multi;
497 }
498
499 ctx = isl_space_get_ctx(space: model);
500 if (!isl_space_has_named_params(space: model))
501 isl_die(ctx, isl_error_invalid,
502 "model has unnamed parameters", goto error);
503 if (!isl_space_has_named_params(space: 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 space: isl_space_copy(space: model));
510 if (!multi)
511 goto error;
512 }
513 domain_space = FN(MULTI(BASE),get_domain_space)(multi);
514 exp = isl_parameter_alignment_reordering(alignee: domain_space, aligner: model);
515 isl_space_free(space: domain_space);
516 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
517
518 isl_space_free(space: model);
519 return multi;
520error:
521 isl_space_free(space: 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 */
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, type: 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, index: i);
553 space = isl_space_align_params(space1: space, FN(EL,get_space)(el));
554 }
555 multi = FN(MULTI(BASE),alloc)(space: isl_space_copy(space));
556 for (i = 0; i < n; ++i) {
557 EL *el = FN(FN(LIST(EL),get),BASE)(list, index: i);
558 el = FN(EL,align_params)(el, space: isl_space_copy(space));
559 multi = FN(MULTI(BASE),restore_check_space)(multi, pos: i, el);
560 }
561
562 isl_space_free(space);
563 FN(LIST(EL),free)(list);
564 return multi;
565error:
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 */
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 */
583static __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)(id: 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
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)(obj: 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, num: 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, pos: 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, pos: i);
632 el = FN(EL,drop_dims)(el, type, first, n);
633 multi = FN(MULTI(BASE),restore_at)(multi, pos: 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"
643static
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 */
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)(obj1: &multi1, obj2: &multi2);
662 n1 = FN(MULTI(BASE),size)(multi: multi1);
663 n2 = FN(MULTI(BASE),size)(multi: multi2);
664 if (n1 < 0 || n2 < 0)
665 goto error;
666
667 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi: multi1),
668 FN(MULTI(BASE),get_space)(multi: multi2));
669 res = FN(MULTI(BASE),alloc)(space);
670
671 for (i = 0; i < n1; ++i) {
672 el = FN(FN(MULTI(BASE),get),BASE)(multi: multi1, pos: i);
673 res = FN(FN(MULTI(BASE),set),BASE)(multi: res, pos: i, el);
674 }
675
676 for (i = 0; i < n2; ++i) {
677 el = FN(FN(MULTI(BASE),get),BASE)(multi: multi2, pos: i);
678 res = FN(FN(MULTI(BASE),set),BASE)(multi: res, pos: n1 + i, el);
679 }
680
681 if (FN(MULTI(BASE),has_explicit_domain)(multi: multi1))
682 res = FN(MULTI(BASE),intersect_explicit_domain)(dst: res, src: multi1);
683 if (FN(MULTI(BASE),has_explicit_domain)(multi: multi2))
684 res = FN(MULTI(BASE),intersect_explicit_domain)(dst: res, src: multi2);
685
686 FN(MULTI(BASE),free)(multi: multi1);
687 FN(MULTI(BASE),free)(multi: multi2);
688 return res;
689error:
690 FN(MULTI(BASE),free)(multi: multi1);
691 FN(MULTI(BASE),free)(multi: multi2);
692 return NULL;
693}
694
695/* Is the range of "multi" a wrapped relation?
696 */
697isl_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(space: multi->space);
702}
703
704/* Given a function A -> [B -> C], extract the function A -> B.
705 */
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, type: isl_dim_out);
713 if (total < 0)
714 return FN(MULTI(BASE),free)(multi);
715 if (!isl_space_range_is_wrapping(space: 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, type: isl_dim_out);
723 if (keep < 0)
724 multi = FN(MULTI(BASE),free)(multi);
725 multi = FN(MULTI(BASE),drop_dims)(multi,
726 type: isl_dim_out, first: keep, n: 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 */
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, type: isl_dim_out);
741 if (total < 0)
742 return FN(MULTI(BASE),free)(multi);
743 if (!isl_space_range_is_wrapping(space: 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, type: isl_dim_out);
751 if (keep < 0)
752 multi = FN(MULTI(BASE),free)(multi);
753 multi = FN(MULTI(BASE),drop_dims)(multi, type: isl_dim_out, first: 0, n: 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 */
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, type: isl_dim_set);
768 if (total < 0)
769 return FN(MULTI(BASE),free)(multi);
770 if (!isl_space_is_wrapping(space: 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, type: isl_dim_set);
777 if (keep < 0)
778 multi = FN(MULTI(BASE),free)(multi);
779 multi = FN(MULTI(BASE),drop_dims)(multi, type: isl_dim_set, first: 0, n: total - keep);
780 multi = FN(MULTI(BASE),reset_space)(multi, space);
781
782 return multi;
783}
784
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 */
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 */
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)(multi: multi1);
830 if (dim < 0 || !multi2)
831 goto error;
832
833 if (FN(MULTI(BASE),check_range)(obj: multi1, type: isl_dim_out, first: pos, n: 0) < 0)
834 goto error;
835
836 res = FN(MULTI(BASE),copy)(multi: multi1);
837 res = FN(MULTI(BASE),drop_dims)(multi: res, type: isl_dim_out, first: pos, n: dim - pos);
838 multi1 = FN(MULTI(BASE),drop_dims)(multi: multi1, type: isl_dim_out, first: 0, n: pos);
839
840 res = FN(MULTI(BASE),flat_range_product)(multi1: res, multi2);
841 res = FN(MULTI(BASE),flat_range_product)(multi1: res, multi2: multi1);
842
843 return res;
844error:
845 FN(MULTI(BASE),free)(multi: multi1);
846 FN(MULTI(BASE),free)(multi: multi2);
847 return NULL;
848}
849
850#undef TYPE
851#define TYPE MULTI(BASE)
852
853static
854#include "isl_type_has_equal_space_bin_templ.c"
855static
856#include "isl_type_check_equal_space_templ.c"
857
858/* This function is currently only used from isl_aff.c
859 */
860static __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 */
871static __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)(obj1: &multi1, obj2: &multi2);
879 n = FN(MULTI(BASE),size)(multi: multi1);
880 if (n < 0 || FN(MULTI(BASE),check_equal_space)(obj1: multi1, obj2: 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)(multi: multi2, pos: i);
887 el1 = FN(MULTI(BASE),take_at)(multi: multi1, pos: i);
888 el1 = fn(el1, el2);
889 multi1 = FN(MULTI(BASE),restore_at)(multi: multi1, pos: i, el: el1);
890 }
891
892 if (FN(MULTI(BASE),has_explicit_domain)(multi: multi2))
893 multi1 = FN(MULTI(BASE),intersect_explicit_domain)(dst: multi1,
894 src: multi2);
895
896 FN(MULTI(BASE),free)(multi: multi2);
897 return multi1;
898error:
899 FN(MULTI(BASE),free)(multi: multi1);
900 FN(MULTI(BASE),free)(multi: multi2);
901 return NULL;
902}
903
904/* Only used on some multi-expressions.
905 */
906static 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 */
911static 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 */
932static 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 */
937static 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 */
962isl_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(space1: multi1->space, space2: 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)(id1: multi1->u.p[i], id2: multi2->u.p[i]);
978 if (equal < 0 || !equal)
979 return equal;
980 }
981
982 if (FN(MULTI(BASE),has_explicit_domain)(multi: multi1) ||
983 FN(MULTI(BASE),has_explicit_domain)(multi: 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

source code of polly/lib/External/isl/isl_multi_templ.c