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
482 /* This function performs the same operation as isl_multi_*_from_*_list,
483 * but is considered as a function on an isl_space when exported.
484 */
MULTI(BASE)485 __isl_give MULTI(BASE) *FN(isl_space_multi,BASE)(__isl_take isl_space *space,
486 __isl_take LIST(EL) *list)
487 {
488 return FN(FN(MULTI(BASE),from),LIST(BASE))(space, list);
489 }
490
MULTI(BASE)491 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
492 __isl_take MULTI(BASE) *multi,
493 enum isl_dim_type type, unsigned first, unsigned n)
494 {
495 int i;
496
497 multi = FN(MULTI(BASE),cow)(multi);
498 if (FN(MULTI(BASE),check_range)(multi, type, first, n) < 0)
499 return FN(MULTI(BASE),free)(multi);
500
501 multi->space = isl_space_drop_dims(multi->space, type, first, n);
502 if (!multi->space)
503 return FN(MULTI(BASE),free)(multi);
504
505 if (type == isl_dim_out) {
506 for (i = 0; i < n; ++i)
507 FN(EL,free)(multi->u.p[first + i]);
508 for (i = first; i + n < multi->n; ++i)
509 multi->u.p[i] = multi->u.p[i + n];
510 multi->n -= n;
511 if (n > 0 && FN(MULTI(BASE),has_explicit_domain)(multi))
512 multi = FN(MULTI(BASE),init_explicit_domain)(multi);
513
514 return multi;
515 }
516
517 if (FN(MULTI(BASE),has_explicit_domain)(multi))
518 multi = FN(MULTI(BASE),drop_explicit_domain_dims)(multi,
519 type, first, n);
520 if (!multi)
521 return NULL;
522
523 for (i = 0; i < multi->n; ++i) {
524 multi->u.p[i] = FN(EL,drop_dims)(multi->u.p[i], type, first, n);
525 if (!multi->u.p[i])
526 return FN(MULTI(BASE),free)(multi);
527 }
528
529 return multi;
530 }
531
532 #undef TYPE
533 #define TYPE MULTI(BASE)
534
535 #include "isl_check_named_params_templ.c"
536 static
537 #include "isl_align_params_bin_templ.c"
538
539 /* Given two MULTI(BASE)s A -> B and C -> D,
540 * construct a MULTI(BASE) (A * C) -> [B -> D].
541 *
542 * If "multi1" and/or "multi2" has an explicit domain, then
543 * intersect the domain of the result with these explicit domains.
544 */
MULTI(BASE)545 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
546 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
547 {
548 int i;
549 isl_size n1, n2;
550 EL *el;
551 isl_space *space;
552 MULTI(BASE) *res;
553
554 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
555 n1 = FN(MULTI(BASE),size)(multi1);
556 n2 = FN(MULTI(BASE),size)(multi2);
557 if (n1 < 0 || n2 < 0)
558 goto error;
559
560 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
561 FN(MULTI(BASE),get_space)(multi2));
562 res = FN(MULTI(BASE),alloc)(space);
563
564 for (i = 0; i < n1; ++i) {
565 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
566 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
567 }
568
569 for (i = 0; i < n2; ++i) {
570 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
571 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
572 }
573
574 if (FN(MULTI(BASE),has_explicit_domain)(multi1))
575 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi1);
576 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
577 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi2);
578
579 FN(MULTI(BASE),free)(multi1);
580 FN(MULTI(BASE),free)(multi2);
581 return res;
582 error:
583 FN(MULTI(BASE),free)(multi1);
584 FN(MULTI(BASE),free)(multi2);
585 return NULL;
586 }
587
588 /* Is the range of "multi" a wrapped relation?
589 */
FN(MULTI (BASE),range_is_wrapping)590 isl_bool FN(MULTI(BASE),range_is_wrapping)(__isl_keep MULTI(BASE) *multi)
591 {
592 if (!multi)
593 return isl_bool_error;
594 return isl_space_range_is_wrapping(multi->space);
595 }
596
597 /* Given a function A -> [B -> C], extract the function A -> B.
598 */
MULTI(BASE)599 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_domain)(
600 __isl_take MULTI(BASE) *multi)
601 {
602 isl_space *space;
603 isl_size total, keep;
604
605 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
606 if (total < 0)
607 return FN(MULTI(BASE),free)(multi);
608 if (!isl_space_range_is_wrapping(multi->space))
609 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
610 "range is not a product",
611 return FN(MULTI(BASE),free)(multi));
612
613 space = FN(MULTI(BASE),get_space)(multi);
614 space = isl_space_range_factor_domain(space);
615 keep = isl_space_dim(space, isl_dim_out);
616 if (keep < 0)
617 multi = FN(MULTI(BASE),free)(multi);
618 multi = FN(MULTI(BASE),drop_dims)(multi,
619 isl_dim_out, keep, total - keep);
620 multi = FN(MULTI(BASE),reset_space)(multi, space);
621
622 return multi;
623 }
624
625 /* Given a function A -> [B -> C], extract the function A -> C.
626 */
MULTI(BASE)627 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)(
628 __isl_take MULTI(BASE) *multi)
629 {
630 isl_space *space;
631 isl_size total, keep;
632
633 total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
634 if (total < 0)
635 return FN(MULTI(BASE),free)(multi);
636 if (!isl_space_range_is_wrapping(multi->space))
637 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
638 "range is not a product",
639 return FN(MULTI(BASE),free)(multi));
640
641 space = FN(MULTI(BASE),get_space)(multi);
642 space = isl_space_range_factor_range(space);
643 keep = isl_space_dim(space, isl_dim_out);
644 if (keep < 0)
645 multi = FN(MULTI(BASE),free)(multi);
646 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);
647 multi = FN(MULTI(BASE),reset_space)(multi, space);
648
649 return multi;
650 }
651
652 /* Given a function [B -> C], extract the function C.
653 */
MULTI(BASE)654 __isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)(
655 __isl_take MULTI(BASE) *multi)
656 {
657 isl_space *space;
658 isl_size total, keep;
659
660 total = FN(MULTI(BASE),dim)(multi, isl_dim_set);
661 if (total < 0)
662 return FN(MULTI(BASE),free)(multi);
663 if (!isl_space_is_wrapping(multi->space))
664 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
665 "not a product", return FN(MULTI(BASE),free)(multi));
666
667 space = FN(MULTI(BASE),get_space)(multi);
668 space = isl_space_factor_range(space);
669 keep = isl_space_dim(space, isl_dim_set);
670 if (keep < 0)
671 multi = FN(MULTI(BASE),free)(multi);
672 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_set, 0, total - keep);
673 multi = FN(MULTI(BASE),reset_space)(multi, space);
674
675 return multi;
676 }
677
MULTI(BASE)678 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
679 __isl_take MULTI(BASE) *multi)
680 {
681 if (!multi)
682 return NULL;
683
684 if (!multi->space->nested[1])
685 return multi;
686
687 multi = FN(MULTI(BASE),cow)(multi);
688 if (!multi)
689 return NULL;
690
691 multi->space = isl_space_flatten_range(multi->space);
692 if (!multi->space)
693 return FN(MULTI(BASE),free)(multi);
694
695 return multi;
696 }
697
698 /* Given two MULTI(BASE)s A -> B and C -> D,
699 * construct a MULTI(BASE) (A * C) -> (B, D).
700 */
MULTI(BASE)701 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
702 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
703 {
704 MULTI(BASE) *multi;
705
706 multi = FN(MULTI(BASE),range_product)(multi1, multi2);
707 multi = FN(MULTI(BASE),flatten_range)(multi);
708 return multi;
709 }
710
711 /* Given two multi expressions, "multi1"
712 *
713 * [A] -> [B1 B2]
714 *
715 * where B2 starts at position "pos", and "multi2"
716 *
717 * [A] -> [D]
718 *
719 * return the multi expression
720 *
721 * [A] -> [B1 D B2]
722 */
MULTI(BASE)723 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
724 __isl_take MULTI(BASE) *multi1, unsigned pos,
725 __isl_take MULTI(BASE) *multi2)
726 {
727 MULTI(BASE) *res;
728 isl_size dim;
729
730 dim = FN(MULTI(BASE),size)(multi1);
731 if (dim < 0 || !multi2)
732 goto error;
733
734 if (FN(MULTI(BASE),check_range)(multi1, isl_dim_out, pos, 0) < 0)
735 goto error;
736
737 res = FN(MULTI(BASE),copy)(multi1);
738 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
739 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
740
741 res = FN(MULTI(BASE),flat_range_product)(res, multi2);
742 res = FN(MULTI(BASE),flat_range_product)(res, multi1);
743
744 return res;
745 error:
746 FN(MULTI(BASE),free)(multi1);
747 FN(MULTI(BASE),free)(multi2);
748 return NULL;
749 }
750
751 #undef TYPE
752 #define TYPE MULTI(BASE)
753
754 static
755 #include "isl_type_has_equal_space_bin_templ.c"
756 static
757 #include "isl_type_check_equal_space_templ.c"
758
759 /* This function is currently only used from isl_aff.c
760 */
761 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
762 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
763 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
764 __attribute__ ((unused));
765
766 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
767 * return the result.
768 *
769 * If "multi2" has an explicit domain, then
770 * intersect the domain of the result with this explicit domain.
771 */
MULTI(BASE)772 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
773 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
774 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
775 {
776 int i;
777
778 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
779 multi1 = FN(MULTI(BASE),cow)(multi1);
780 if (FN(MULTI(BASE),check_equal_space)(multi1, multi2) < 0)
781 goto error;
782
783 for (i = 0; i < multi1->n; ++i) {
784 multi1->u.p[i] = fn(multi1->u.p[i],
785 FN(EL,copy)(multi2->u.p[i]));
786 if (!multi1->u.p[i])
787 goto error;
788 }
789
790 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
791 multi1 = FN(MULTI(BASE),intersect_explicit_domain)(multi1,
792 multi2);
793
794 FN(MULTI(BASE),free)(multi2);
795 return multi1;
796 error:
797 FN(MULTI(BASE),free)(multi1);
798 FN(MULTI(BASE),free)(multi2);
799 return NULL;
800 }
801
802 /* Only used on some multi-expressions.
803 */
804 static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
805 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
806
807 /* Does "test" succeed on any base expression of "multi"?
808 */
FN(MULTI (BASE),any)809 static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
810 isl_bool (*test)(__isl_keep EL *))
811 {
812 isl_size n;
813 int i;
814
815 n = FN(MULTI(BASE),size)(multi);
816 if (n < 0)
817 return isl_bool_error;
818
819 for (i = 0; i < n; ++i) {
820 isl_bool any = test(multi->u.p[i]);
821 if (any < 0 || any)
822 return any;
823 }
824
825 return isl_bool_false;
826 }
827
828 /* Only used on some multi-expressions.
829 */
830 static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
831 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
832
833 /* Does "test" succeed on every base expression of "multi"?
834 */
FN(MULTI (BASE),every)835 static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
836 isl_bool (*test)(__isl_keep EL *))
837 {
838 isl_size n;
839 int i;
840
841 n = FN(MULTI(BASE),size)(multi);
842 if (n < 0)
843 return isl_bool_error;
844
845 for (i = 0; i < n; ++i) {
846 isl_bool every = test(multi->u.p[i]);
847 if (every < 0 || !every)
848 return every;
849 }
850
851 return isl_bool_true;
852 }
853
854 /* Convert a multiple expression defined over a parameter domain
855 * into one that is defined over a zero-dimensional set.
856 */
MULTI(BASE)857 __isl_give MULTI(BASE) *FN(MULTI(BASE),from_range)(
858 __isl_take MULTI(BASE) *multi)
859 {
860 isl_space *space;
861
862 if (!multi)
863 return NULL;
864 if (!isl_space_is_set(multi->space))
865 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
866 "not living in a set space",
867 return FN(MULTI(BASE),free)(multi));
868
869 space = FN(MULTI(BASE),get_space)(multi);
870 space = isl_space_from_range(space);
871 multi = FN(MULTI(BASE),reset_space)(multi, space);
872
873 return multi;
874 }
875
876 /* Are "multi1" and "multi2" obviously equal?
877 */
FN(MULTI (BASE),plain_is_equal)878 isl_bool FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1,
879 __isl_keep MULTI(BASE) *multi2)
880 {
881 int i;
882 isl_bool equal;
883
884 if (!multi1 || !multi2)
885 return isl_bool_error;
886 if (multi1->n != multi2->n)
887 return isl_bool_false;
888 equal = isl_space_is_equal(multi1->space, multi2->space);
889 if (equal < 0 || !equal)
890 return equal;
891
892 for (i = 0; i < multi1->n; ++i) {
893 equal = FN(EL,plain_is_equal)(multi1->u.p[i], multi2->u.p[i]);
894 if (equal < 0 || !equal)
895 return equal;
896 }
897
898 if (FN(MULTI(BASE),has_explicit_domain)(multi1) ||
899 FN(MULTI(BASE),has_explicit_domain)(multi2)) {
900 equal = FN(MULTI(BASE),equal_explicit_domain)(multi1, multi2);
901 if (equal < 0 || !equal)
902 return equal;
903 }
904
905 return isl_bool_true;
906 }
907