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