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
FN(MULTI (BASE),dim)141 isl_size FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
142 enum isl_dim_type type)
143 {
144 return isl_space_dim(FN(MULTI(BASE),peek_space)(multi), type);
145 }
146
147 /* Return the number of base expressions in "multi".
148 */
FN(MULTI (BASE),size)149 isl_size FN(MULTI(BASE),size)(__isl_keep MULTI(BASE) *multi)
150 {
151 return multi ? multi->n : isl_size_error;
152 }
153
154 #undef TYPE
155 #define TYPE MULTI(BASE)
156 static
157 #include "check_type_range_templ.c"
158
159 /* Return a copy of the base expression at position "pos" in "multi".
160 */
FN(MULTI (BASE),get_at)161 __isl_give EL *FN(MULTI(BASE),get_at)(__isl_keep MULTI(BASE) *multi, int pos)
162 {
163 isl_ctx *ctx;
164
165 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)
166 return NULL;
167 ctx = FN(MULTI(BASE),get_ctx)(multi);
168 return FN(EL,copy)(multi->u.p[pos]);
169 }
170
171 /* This is an alternative name for the function above.
172 */
FN(FN (MULTI (BASE),get),BASE)173 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
174 int pos)
175 {
176 return FN(MULTI(BASE),get_at)(multi, pos);
177 }
178
179 /* Set the element at position "pos" of "multi" to "el",
180 * where the position may be empty if "multi" has only a single reference.
181 */
MULTI(BASE)182 static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore)(
183 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
184 {
185 multi = FN(MULTI(BASE),cow)(multi);
186 if (!multi || !el)
187 goto error;
188
189 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)
190 goto error;
191
192 FN(EL,free)(multi->u.p[pos]);
193 multi->u.p[pos] = el;
194
195 return multi;
196 error:
197 FN(MULTI(BASE),free)(multi);
198 FN(EL,free)(el);
199 return NULL;
200 }
201
202 /* Set the element at position "pos" of "multi" to "el",
203 * where the position may be empty if "multi" has only a single reference.
204 * However, the space of "multi" is available and is checked
205 * for compatibility with "el".
206 */
MULTI(BASE)207 static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_check_space)(
208 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
209 {
210 isl_space *space;
211
212 space = FN(MULTI(BASE),peek_space)(multi);
213 if (FN(EL,check_match_domain_space)(el, space) < 0)
214 multi = FN(MULTI(BASE),free)(multi);
215 return FN(MULTI(BASE),restore)(multi, pos, el);
216 }
217
218 /* Replace the base expression at position "pos" in "multi" with "el".
219 */
MULTI(BASE)220 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_at)(
221 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
222 {
223 isl_space *multi_space = NULL;
224 isl_space *el_space = NULL;
225 isl_bool match;
226
227 multi_space = FN(MULTI(BASE),get_space)(multi);
228 match = FN(EL,matching_params)(el, multi_space);
229 if (match < 0)
230 goto error;
231 if (!match) {
232 multi = FN(MULTI(BASE),align_params)(multi,
233 FN(EL,get_space)(el));
234 isl_space_free(multi_space);
235 multi_space = FN(MULTI(BASE),get_space)(multi);
236 el = FN(EL,align_params)(el, isl_space_copy(multi_space));
237 }
238
239 multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el);
240
241 isl_space_free(multi_space);
242 isl_space_free(el_space);
243
244 return multi;
245 error:
246 FN(MULTI(BASE),free)(multi);
247 FN(EL,free)(el);
248 isl_space_free(multi_space);
249 isl_space_free(el_space);
250 return NULL;
251 }
252
253 /* This is an alternative name for the function above.
254 */
MULTI(BASE)255 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
256 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
257 {
258 return FN(MULTI(BASE),set_at)(multi, pos, el);
259 }
260
261 /* Return the base expressions of "multi" as a list.
262 */
LIST(EL)263 __isl_give LIST(EL) *FN(MULTI(BASE),get_list)(
264 __isl_keep MULTI(BASE) *multi)
265 {
266 isl_size n;
267 int i;
268 LIST(EL) *list;
269
270 n = FN(MULTI(BASE),size)(multi);
271 if (n < 0)
272 return NULL;
273 list = FN(LIST(EL),alloc)(FN(MULTI(BASE),get_ctx(multi)), n);
274 for (i = 0; i < n; ++i) {
275 EL *el = FN(MULTI(BASE),get_at)(multi, i);
276 list = FN(LIST(EL),add)(list, el);
277 }
278
279 return list;
280 }
281
282 /* Reset the space of "multi". This function is called from isl_pw_templ.c
283 * and doesn't know if the space of an element object is represented
284 * directly or through its domain. It therefore passes along both,
285 * which we pass along to the element function since we don't know how
286 * that is represented either.
287 *
288 * If "multi" has an explicit domain, then the caller is expected
289 * to make sure that any modification that would change the dimensions
290 * of the explicit domain has bee applied before this function is called.
291 */
MULTI(BASE)292 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
293 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
294 __isl_take isl_space *domain)
295 {
296 int i;
297
298 multi = FN(MULTI(BASE),cow)(multi);
299 if (!multi || !space || !domain)
300 goto error;
301
302 for (i = 0; i < multi->n; ++i) {
303 multi->u.p[i] = FN(EL,reset_domain_space)(multi->u.p[i],
304 isl_space_copy(domain));
305 if (!multi->u.p[i])
306 goto error;
307 }
308 if (FN(MULTI(BASE),has_explicit_domain)(multi)) {
309 multi = FN(MULTI(BASE),reset_explicit_domain_space)(multi,
310 isl_space_copy(domain));
311 if (!multi)
312 goto error;
313 }
314 isl_space_free(domain);
315 isl_space_free(multi->space);
316 multi->space = space;
317
318 return multi;
319 error:
320 isl_space_free(domain);
321 isl_space_free(space);
322 FN(MULTI(BASE),free)(multi);
323 return NULL;
324 }
325
MULTI(BASE)326 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
327 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
328 {
329 isl_space *space;
330
331 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
332 isl_space_copy(multi->space));
333 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
334 }
335
MULTI(BASE)336 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
337 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
338 {
339 isl_space *domain;
340
341 domain = isl_space_domain(isl_space_copy(space));
342 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
343 }
344
345 /* Reset the user pointer on all identifiers of parameters and tuples
346 * of the space of "multi".
347 */
MULTI(BASE)348 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_user)(
349 __isl_take MULTI(BASE) *multi)
350 {
351 isl_space *space;
352
353 space = FN(MULTI(BASE),get_space)(multi);
354 space = isl_space_reset_user(space);
355
356 return FN(MULTI(BASE),reset_space)(multi, space);
357 }
358
MULTI(BASE)359 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
360 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
361 {
362 int i;
363 isl_space *space;
364
365 multi = FN(MULTI(BASE),cow)(multi);
366 if (!multi || !exp)
367 goto error;
368
369 for (i = 0; i < multi->n; ++i) {
370 multi->u.p[i] = FN(EL,realign_domain)(multi->u.p[i],
371 isl_reordering_copy(exp));
372 if (!multi->u.p[i])
373 goto error;
374 }
375
376 space = isl_reordering_get_space(exp);
377 multi = FN(MULTI(BASE),reset_domain_space)(multi, space);
378
379 isl_reordering_free(exp);
380 return multi;
381 error:
382 isl_reordering_free(exp);
383 FN(MULTI(BASE),free)(multi);
384 return NULL;
385 }
386
387 /* Align the parameters of "multi" to those of "model".
388 *
389 * If "multi" has an explicit domain, then align the parameters
390 * of the domain first.
391 */
MULTI(BASE)392 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
393 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
394 {
395 isl_ctx *ctx;
396 isl_bool equal_params;
397 isl_reordering *exp;
398
399 if (!multi || !model)
400 goto error;
401
402 equal_params = isl_space_has_equal_params(multi->space, model);
403 if (equal_params < 0)
404 goto error;
405 if (equal_params) {
406 isl_space_free(model);
407 return multi;
408 }
409
410 ctx = isl_space_get_ctx(model);
411 if (!isl_space_has_named_params(model))
412 isl_die(ctx, isl_error_invalid,
413 "model has unnamed parameters", goto error);
414 if (!isl_space_has_named_params(multi->space))
415 isl_die(ctx, isl_error_invalid,
416 "input has unnamed parameters", goto error);
417
418 if (FN(MULTI(BASE),has_explicit_domain)(multi)) {
419 multi = FN(MULTI(BASE),align_explicit_domain_params)(multi,
420 isl_space_copy(model));
421 if (!multi)
422 goto error;
423 }
424 exp = isl_parameter_alignment_reordering(multi->space, model);
425 exp = isl_reordering_extend_space(exp,
426 FN(MULTI(BASE),get_domain_space)(multi));
427 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
428
429 isl_space_free(model);
430 return multi;
431 error:
432 isl_space_free(model);
433 FN(MULTI(BASE),free)(multi);
434 return NULL;
435 }
436
437 /* Create a multi expression in the given space with the elements of "list"
438 * as base expressions.
439 *
440 * Since isl_multi_*_restore_* assumes that the element and
441 * the multi expression have matching spaces, the alignment
442 * (if any) needs to be performed beforehand.
443 */
MULTI(BASE)444 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
445 __isl_take isl_space *space, __isl_take LIST(EL) *list)
446 {
447 int i;
448 isl_size n, dim;
449 isl_ctx *ctx;
450 MULTI(BASE) *multi;
451
452 dim = isl_space_dim(space, isl_dim_out);
453 n = FN(FN(LIST(EL),n),BASE)(list);
454 if (dim < 0 || n < 0)
455 goto error;
456
457 ctx = isl_space_get_ctx(space);
458 if (n != dim)
459 isl_die(ctx, isl_error_invalid,
460 "invalid number of elements in list", goto error);
461
462 for (i = 0; i < n; ++i) {
463 EL *el = FN(LIST(EL),peek)(list, i);
464 space = isl_space_align_params(space, FN(EL,get_space)(el));
465 }
466 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
467 for (i = 0; i < n; ++i) {
468 EL *el = FN(FN(LIST(EL),get),BASE)(list, i);
469 el = FN(EL,align_params)(el, isl_space_copy(space));
470 multi = FN(MULTI(BASE),restore_check_space)(multi, i, el);
471 }
472
473 isl_space_free(space);
474 FN(LIST(EL),free)(list);
475 return multi;
476 error:
477 isl_space_free(space);
478 FN(LIST(EL),free)(list);
479 return NULL;
480 }
481
MULTI(BASE)482 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
483 __isl_take MULTI(BASE) *multi,
484 enum isl_dim_type type, unsigned first, unsigned n)
485 {
486 int i;
487
488 multi = FN(MULTI(BASE),cow)(multi);
489 if (FN(MULTI(BASE),check_range)(multi, type, first, n) < 0)
490 return FN(MULTI(BASE),free)(multi);
491
492 multi->space = isl_space_drop_dims(multi->space, type, first, n);
493 if (!multi->space)
494 return FN(MULTI(BASE),free)(multi);
495
496 if (type == isl_dim_out) {
497 for (i = 0; i < n; ++i)
498 FN(EL,free)(multi->u.p[first + i]);
499 for (i = first; i + n < multi->n; ++i)
500 multi->u.p[i] = multi->u.p[i + n];
501 multi->n -= n;
502 if (n > 0 && FN(MULTI(BASE),has_explicit_domain)(multi))
503 multi = FN(MULTI(BASE),init_explicit_domain)(multi);
504
505 return multi;
506 }
507
508 if (FN(MULTI(BASE),has_explicit_domain)(multi))
509 multi = FN(MULTI(BASE),drop_explicit_domain_dims)(multi,
510 type, first, n);
511 if (!multi)
512 return NULL;
513
514 for (i = 0; i < multi->n; ++i) {
515 multi->u.p[i] = FN(EL,drop_dims)(multi->u.p[i], type, first, n);
516 if (!multi->u.p[i])
517 return FN(MULTI(BASE),free)(multi);
518 }
519
520 return multi;
521 }
522
523 #undef TYPE
524 #define TYPE MULTI(BASE)
525
526 #include "isl_check_named_params_templ.c"
527 static
528 #include "isl_align_params_bin_templ.c"
529
530 /* Given two MULTI(BASE)s A -> B and C -> D,
531 * construct a MULTI(BASE) (A * C) -> [B -> D].
532 *
533 * If "multi1" and/or "multi2" has an explicit domain, then
534 * intersect the domain of the result with these explicit domains.
535 */
MULTI(BASE)536 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
537 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
538 {
539 int i;
540 isl_size n1, n2;
541 EL *el;
542 isl_space *space;
543 MULTI(BASE) *res;
544
545 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
546 n1 = FN(MULTI(BASE),size)(multi1);
547 n2 = FN(MULTI(BASE),size)(multi2);
548 if (n1 < 0 || n2 < 0)
549 goto error;
550
551 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
552 FN(MULTI(BASE),get_space)(multi2));
553 res = FN(MULTI(BASE),alloc)(space);
554
555 for (i = 0; i < n1; ++i) {
556 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
557 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
558 }
559
560 for (i = 0; i < n2; ++i) {
561 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
562 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
563 }
564
565 if (FN(MULTI(BASE),has_explicit_domain)(multi1))
566 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi1);
567 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
568 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi2);
569
570 FN(MULTI(BASE),free)(multi1);
571 FN(MULTI(BASE),free)(multi2);
572 return res;
573 error:
574 FN(MULTI(BASE),free)(multi1);
575 FN(MULTI(BASE),free)(multi2);
576 return NULL;
577 }
578
579 /* Is the range of "multi" a wrapped relation?
580 */
FN(MULTI (BASE),range_is_wrapping)581 isl_bool FN(MULTI(BASE),range_is_wrapping)(__isl_keep MULTI(BASE) *multi)
582 {
583 if (!multi)
584 return isl_bool_error;
585 return isl_space_range_is_wrapping(multi->space);
586 }
587
588 /* Given a function A -> [B -> C], extract the function A -> B.
589 */
MULTI(BASE)590 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_domain)(
591 __isl_take MULTI(BASE) *multi)
592 {
593 isl_space *space;
594 isl_size total, keep;
595
596 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
597 if (total < 0)
598 return FN(MULTI(BASE),free)(multi);
599 if (!isl_space_range_is_wrapping(multi->space))
600 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
601 "range is not a product",
602 return FN(MULTI(BASE),free)(multi));
603
604 space = FN(MULTI(BASE),get_space)(multi);
605 space = isl_space_range_factor_domain(space);
606 keep = isl_space_dim(space, isl_dim_out);
607 if (keep < 0)
608 multi = FN(MULTI(BASE),free)(multi);
609 multi = FN(MULTI(BASE),drop_dims)(multi,
610 isl_dim_out, keep, total - keep);
611 multi = FN(MULTI(BASE),reset_space)(multi, space);
612
613 return multi;
614 }
615
616 /* Given a function A -> [B -> C], extract the function A -> C.
617 */
MULTI(BASE)618 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)(
619 __isl_take MULTI(BASE) *multi)
620 {
621 isl_space *space;
622 isl_size total, keep;
623
624 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
625 if (total < 0)
626 return FN(MULTI(BASE),free)(multi);
627 if (!isl_space_range_is_wrapping(multi->space))
628 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
629 "range is not a product",
630 return FN(MULTI(BASE),free)(multi));
631
632 space = FN(MULTI(BASE),get_space)(multi);
633 space = isl_space_range_factor_range(space);
634 keep = isl_space_dim(space, isl_dim_out);
635 if (keep < 0)
636 multi = FN(MULTI(BASE),free)(multi);
637 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);
638 multi = FN(MULTI(BASE),reset_space)(multi, space);
639
640 return multi;
641 }
642
643 /* Given a function [B -> C], extract the function C.
644 */
MULTI(BASE)645 __isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)(
646 __isl_take MULTI(BASE) *multi)
647 {
648 isl_space *space;
649 isl_size total, keep;
650
651 total = FN(MULTI(BASE),dim)(multi, isl_dim_set);
652 if (total < 0)
653 return FN(MULTI(BASE),free)(multi);
654 if (!isl_space_is_wrapping(multi->space))
655 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
656 "not a product", return FN(MULTI(BASE),free)(multi));
657
658 space = FN(MULTI(BASE),get_space)(multi);
659 space = isl_space_factor_range(space);
660 keep = isl_space_dim(space, isl_dim_set);
661 if (keep < 0)
662 multi = FN(MULTI(BASE),free)(multi);
663 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_set, 0, total - keep);
664 multi = FN(MULTI(BASE),reset_space)(multi, space);
665
666 return multi;
667 }
668
MULTI(BASE)669 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
670 __isl_take MULTI(BASE) *multi)
671 {
672 if (!multi)
673 return NULL;
674
675 if (!multi->space->nested[1])
676 return multi;
677
678 multi = FN(MULTI(BASE),cow)(multi);
679 if (!multi)
680 return NULL;
681
682 multi->space = isl_space_flatten_range(multi->space);
683 if (!multi->space)
684 return FN(MULTI(BASE),free)(multi);
685
686 return multi;
687 }
688
689 /* Given two MULTI(BASE)s A -> B and C -> D,
690 * construct a MULTI(BASE) (A * C) -> (B, D).
691 */
MULTI(BASE)692 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
693 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
694 {
695 MULTI(BASE) *multi;
696
697 multi = FN(MULTI(BASE),range_product)(multi1, multi2);
698 multi = FN(MULTI(BASE),flatten_range)(multi);
699 return multi;
700 }
701
702 /* Given two multi expressions, "multi1"
703 *
704 * [A] -> [B1 B2]
705 *
706 * where B2 starts at position "pos", and "multi2"
707 *
708 * [A] -> [D]
709 *
710 * return the multi expression
711 *
712 * [A] -> [B1 D B2]
713 */
MULTI(BASE)714 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
715 __isl_take MULTI(BASE) *multi1, unsigned pos,
716 __isl_take MULTI(BASE) *multi2)
717 {
718 MULTI(BASE) *res;
719 isl_size dim;
720
721 dim = FN(MULTI(BASE),size)(multi1);
722 if (dim < 0 || !multi2)
723 goto error;
724
725 if (FN(MULTI(BASE),check_range)(multi1, isl_dim_out, pos, 0) < 0)
726 goto error;
727
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);
731
732 res = FN(MULTI(BASE),flat_range_product)(res, multi2);
733 res = FN(MULTI(BASE),flat_range_product)(res, multi1);
734
735 return res;
736 error:
737 FN(MULTI(BASE),free)(multi1);
738 FN(MULTI(BASE),free)(multi2);
739 return NULL;
740 }
741
742 #undef TYPE
743 #define TYPE MULTI(BASE)
744
745 static
746 #include "isl_type_has_equal_space_bin_templ.c"
747 static
748 #include "isl_type_check_equal_space_templ.c"
749
750 /* This function is currently only used from isl_aff.c
751 */
752 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
753 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
754 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
755 __attribute__ ((unused));
756
757 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
758 * return the result.
759 *
760 * If "multi2" has an explicit domain, then
761 * intersect the domain of the result with this explicit domain.
762 */
MULTI(BASE)763 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
764 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
765 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
766 {
767 int i;
768
769 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
770 multi1 = FN(MULTI(BASE),cow)(multi1);
771 if (FN(MULTI(BASE),check_equal_space)(multi1, multi2) < 0)
772 goto error;
773
774 for (i = 0; i < multi1->n; ++i) {
775 multi1->u.p[i] = fn(multi1->u.p[i],
776 FN(EL,copy)(multi2->u.p[i]));
777 if (!multi1->u.p[i])
778 goto error;
779 }
780
781 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
782 multi1 = FN(MULTI(BASE),intersect_explicit_domain)(multi1,
783 multi2);
784
785 FN(MULTI(BASE),free)(multi2);
786 return multi1;
787 error:
788 FN(MULTI(BASE),free)(multi1);
789 FN(MULTI(BASE),free)(multi2);
790 return NULL;
791 }
792
793 /* Only used on some multi-expressions.
794 */
795 static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
796 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
797
798 /* Does "test" succeed on any base expression of "multi"?
799 */
FN(MULTI (BASE),any)800 static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
801 isl_bool (*test)(__isl_keep EL *))
802 {
803 isl_size n;
804 int i;
805
806 n = FN(MULTI(BASE),size)(multi);
807 if (n < 0)
808 return isl_bool_error;
809
810 for (i = 0; i < n; ++i) {
811 isl_bool any = test(multi->u.p[i]);
812 if (any < 0 || any)
813 return any;
814 }
815
816 return isl_bool_false;
817 }
818
819 /* Only used on some multi-expressions.
820 */
821 static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
822 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
823
824 /* Does "test" succeed on every base expression of "multi"?
825 */
FN(MULTI (BASE),every)826 static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
827 isl_bool (*test)(__isl_keep EL *))
828 {
829 isl_size n;
830 int i;
831
832 n = FN(MULTI(BASE),size)(multi);
833 if (n < 0)
834 return isl_bool_error;
835
836 for (i = 0; i < n; ++i) {
837 isl_bool every = test(multi->u.p[i]);
838 if (every < 0 || !every)
839 return every;
840 }
841
842 return isl_bool_true;
843 }
844
845 /* Convert a multiple expression defined over a parameter domain
846 * into one that is defined over a zero-dimensional set.
847 */
MULTI(BASE)848 __isl_give MULTI(BASE) *FN(MULTI(BASE),from_range)(
849 __isl_take MULTI(BASE) *multi)
850 {
851 isl_space *space;
852
853 if (!multi)
854 return NULL;
855 if (!isl_space_is_set(multi->space))
856 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
857 "not living in a set space",
858 return FN(MULTI(BASE),free)(multi));
859
860 space = FN(MULTI(BASE),get_space)(multi);
861 space = isl_space_from_range(space);
862 multi = FN(MULTI(BASE),reset_space)(multi, space);
863
864 return multi;
865 }
866
867 /* Are "multi1" and "multi2" obviously equal?
868 */
FN(MULTI (BASE),plain_is_equal)869 isl_bool FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1,
870 __isl_keep MULTI(BASE) *multi2)
871 {
872 int i;
873 isl_bool equal;
874
875 if (!multi1 || !multi2)
876 return isl_bool_error;
877 if (multi1->n != multi2->n)
878 return isl_bool_false;
879 equal = isl_space_is_equal(multi1->space, multi2->space);
880 if (equal < 0 || !equal)
881 return equal;
882
883 for (i = 0; i < multi1->n; ++i) {
884 equal = FN(EL,plain_is_equal)(multi1->u.p[i], multi2->u.p[i]);
885 if (equal < 0 || !equal)
886 return equal;
887 }
888
889 if (FN(MULTI(BASE),has_explicit_domain)(multi1) ||
890 FN(MULTI(BASE),has_explicit_domain)(multi2)) {
891 equal = FN(MULTI(BASE),equal_explicit_domain)(multi1, multi2);
892 if (equal < 0 || !equal)
893 return equal;
894 }
895
896 return isl_bool_true;
897 }
898