?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_map_simplify.c: isl_basic_map_eliminate_vars: drop redundant mark removal
[isl.git] / isl_multi_templ.c
bloba5c9939d6719497a48a59b3621801d843622a17e
1 /*
2 * Copyright 2011 Sven Verdoolaege
3 * Copyright 2012-2013 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_val_private.h>
14 #include <isl/set.h>
15 #include <isl_reordering.h>
16
17 #include <isl_multi_macro.h>
18
19 #define MULTI_NAME(BASE) "isl_multi_" #BASE
20 #define xLIST(EL) EL ## _list
21 #define LIST(EL) xLIST(EL)
22
23 isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
24 {
25 return multi ? isl_space_get_ctx(multi->space) : NULL;
26 }
27
28 /* Return the space of "multi".
29 */
30 __isl_keep isl_space *FN(MULTI(BASE),peek_space)(__isl_keep MULTI(BASE) *multi)
31 {
32 return multi ? multi->space : NULL;
33 }
34
35 __isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
36 {
37 return isl_space_copy(FN(MULTI(BASE),peek_space)(multi));
38 }
39
40 /* Return the position of the dimension of the given type and name
41 * in "multi".
42 * Return -1 if no such dimension can be found.
43 */
44 int FN(MULTI(BASE),find_dim_by_name)(__isl_keep MULTI(BASE) *multi,
45 enum isl_dim_type type, const char *name)
46 {
47 if (!multi)
48 return -1;
49 return isl_space_find_dim_by_name(multi->space, type, name);
50 }
51
52 __isl_give isl_space *FN(MULTI(BASE),get_domain_space)(
53 __isl_keep MULTI(BASE) *multi)
54 {
55 return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL;
56 }
57
58 /* Allocate a multi expression living in "space".
59 *
60 * If the number of base expressions is zero, then make sure
61 * there is enough room in the structure for the explicit domain,
62 * in case the type supports such an explicit domain.
63 */
64 __isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)
65 {
66 isl_ctx *ctx;
67 int n;
68 MULTI(BASE) *multi;
69
70 if (!space)
71 return NULL;
72
73 ctx = isl_space_get_ctx(space);
74 n = isl_space_dim(space, isl_dim_out);
75 if (n > 0)
76 multi = isl_calloc(ctx, MULTI(BASE),
77 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));
78 else
79 multi = isl_calloc(ctx, MULTI(BASE), sizeof(MULTI(BASE)));
80 if (!multi)
81 goto error;
82
83 multi->space = space;
84 multi->n = n;
85 multi->ref = 1;
86 if (FN(MULTI(BASE),has_explicit_domain)(multi))
87 multi = FN(MULTI(BASE),init_explicit_domain)(multi);
88 return multi;
89 error:
90 isl_space_free(space);
91 return NULL;
92 }
93
94 __isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)
95 {
96 int i;
97 MULTI(BASE) *dup;
98
99 if (!multi)
100 return NULL;
101
102 dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));
103 if (!dup)
104 return NULL;
105
106 for (i = 0; i < multi->n; ++i)
107 dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,
108 FN(EL,copy)(multi->u.p[i]));
109 if (FN(MULTI(BASE),has_explicit_domain)(multi))
110 dup = FN(MULTI(BASE),copy_explicit_domain)(dup, multi);
111
112 return dup;
113 }
114
115 __isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)
116 {
117 if (!multi)
118 return NULL;
119
120 if (multi->ref == 1)
121 return multi;
122
123 multi->ref--;
124 return FN(MULTI(BASE),dup)(multi);
125 }
126
127 __isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)
128 {
129 if (!multi)
130 return NULL;
131
132 multi->ref++;
133 return multi;
134 }
135
136 __isl_null MULTI(BASE) *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)
137 {
138 int i;
139
140 if (!multi)
141 return NULL;
142
143 if (--multi->ref > 0)
144 return NULL;
145
146 isl_space_free(multi->space);
147 for (i = 0; i < multi->n; ++i)
148 FN(EL,free)(multi->u.p[i]);
149 if (FN(MULTI(BASE),has_explicit_domain)(multi))
150 FN(MULTI(BASE),free_explicit_domain)(multi);
151 free(multi);
152
153 return NULL;
154 }
155
156 unsigned FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
157 enum isl_dim_type type)
158 {
159 return multi ? isl_space_dim(multi->space, type) : 0;
160 }
161
162 /* Return the position of the first dimension of "type" with id "id".
163 * Return -1 if there is no such dimension.
164 */
165 int FN(MULTI(BASE),find_dim_by_id)(__isl_keep MULTI(BASE) *multi,
166 enum isl_dim_type type, __isl_keep isl_id *id)
167 {
168 if (!multi)
169 return -1;
170 return isl_space_find_dim_by_id(multi->space, type, id);
171 }
172
173 /* Return the id of the given dimension.
174 */
175 __isl_give isl_id *FN(MULTI(BASE),get_dim_id)(__isl_keep MULTI(BASE) *multi,
176 enum isl_dim_type type, unsigned pos)
177 {
178 return multi ? isl_space_get_dim_id(multi->space, type, pos) : NULL;
179 }
180
181 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_name)(
182 __isl_take MULTI(BASE) *multi,
183 enum isl_dim_type type, unsigned pos, const char *s)
184 {
185 int i;
186
187 multi = FN(MULTI(BASE),cow)(multi);
188 if (!multi)
189 return NULL;
190
191 multi->space = isl_space_set_dim_name(multi->space, type, pos, s);
192 if (!multi->space)
193 return FN(MULTI(BASE),free)(multi);
194
195 if (type == isl_dim_out)
196 return multi;
197 for (i = 0; i < multi->n; ++i) {
198 multi->u.p[i] = FN(EL,set_dim_name)(multi->u.p[i],
199 type, pos, s);
200 if (!multi->u.p[i])
201 return FN(MULTI(BASE),free)(multi);
202 }
203
204 return multi;
205 }
206
207 const char *FN(MULTI(BASE),get_tuple_name)(__isl_keep MULTI(BASE) *multi,
208 enum isl_dim_type type)
209 {
210 return multi ? isl_space_get_tuple_name(multi->space, type) : NULL;
211 }
212
213 /* Does the specified tuple have an id?
214 */
215 isl_bool FN(MULTI(BASE),has_tuple_id)(__isl_keep MULTI(BASE) *multi,
216 enum isl_dim_type type)
217 {
218 if (!multi)
219 return isl_bool_error;
220 return isl_space_has_tuple_id(multi->space, type);
221 }
222
223 /* Return the id of the specified tuple.
224 */
225 __isl_give isl_id *FN(MULTI(BASE),get_tuple_id)(__isl_keep MULTI(BASE) *multi,
226 enum isl_dim_type type)
227 {
228 return multi ? isl_space_get_tuple_id(multi->space, type) : NULL;
229 }
230
231 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
232 int pos)
233 {
234 isl_ctx *ctx;
235
236 if (!multi)
237 return NULL;
238 ctx = FN(MULTI(BASE),get_ctx)(multi);
239 if (pos < 0 || pos >= multi->n)
240 isl_die(ctx, isl_error_invalid,
241 "index out of bounds", return NULL);
242 return FN(EL,copy)(multi->u.p[pos]);
243 }
244
245 /* Set the element at position "pos" of "multi" to "el",
246 * where the position may be empty if "multi" has only a single reference.
247 */
248 static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore)(
249 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
250 {
251 multi = FN(MULTI(BASE),cow)(multi);
252 if (!multi || !el)
253 goto error;
254
255 if (pos < 0 || pos >= multi->n)
256 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
257 "index out of bounds", goto error);
258
259 FN(EL,free)(multi->u.p[pos]);
260 multi->u.p[pos] = el;
261
262 return multi;
263 error:
264 FN(MULTI(BASE),free)(multi);
265 FN(EL,free)(el);
266 return NULL;
267 }
268
269 /* Set the element at position "pos" of "multi" to "el",
270 * where the position may be empty if "multi" has only a single reference.
271 * However, the space of "multi" is available and is checked
272 * for compatibility with "el".
273 */
274 static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_check_space)(
275 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
276 {
277 isl_space *space;
278
279 space = FN(MULTI(BASE),peek_space)(multi);
280 if (FN(EL,check_match_domain_space)(el, space) < 0)
281 multi = FN(MULTI(BASE),free)(multi);
282 return FN(MULTI(BASE),restore)(multi, pos, el);
283 }
284
285 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
286 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
287 {
288 isl_space *multi_space = NULL;
289 isl_space *el_space = NULL;
290 isl_bool match;
291
292 multi_space = FN(MULTI(BASE),get_space)(multi);
293 match = FN(EL,matching_params)(el, multi_space);
294 if (match < 0)
295 goto error;
296 if (!match) {
297 multi = FN(MULTI(BASE),align_params)(multi,
298 FN(EL,get_space)(el));
299 isl_space_free(multi_space);
300 multi_space = FN(MULTI(BASE),get_space)(multi);
301 el = FN(EL,align_params)(el, isl_space_copy(multi_space));
302 }
303
304 multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el);
305
306 isl_space_free(multi_space);
307 isl_space_free(el_space);
308
309 return multi;
310 error:
311 FN(MULTI(BASE),free)(multi);
312 FN(EL,free)(el);
313 isl_space_free(multi_space);
314 isl_space_free(el_space);
315 return NULL;
316 }
317
318 /* Reset the space of "multi". This function is called from isl_pw_templ.c
319 * and doesn't know if the space of an element object is represented
320 * directly or through its domain. It therefore passes along both,
321 * which we pass along to the element function since we don't know how
322 * that is represented either.
323 *
324 * If "multi" has an explicit domain, then the caller is expected
325 * to make sure that any modification that would change the dimensions
326 * of the explicit domain has bee applied before this function is called.
327 */
328 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
329 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
330 __isl_take isl_space *domain)
331 {
332 int i;
333
334 multi = FN(MULTI(BASE),cow)(multi);
335 if (!multi || !space || !domain)
336 goto error;
337
338 for (i = 0; i < multi->n; ++i) {
339 multi->u.p[i] = FN(EL,reset_domain_space)(multi->u.p[i],
340 isl_space_copy(domain));
341 if (!multi->u.p[i])
342 goto error;
343 }
344 if (FN(MULTI(BASE),has_explicit_domain)(multi)) {
345 multi = FN(MULTI(BASE),reset_explicit_domain_space)(multi,
346 isl_space_copy(domain));
347 if (!multi)
348 goto error;
349 }
350 isl_space_free(domain);
351 isl_space_free(multi->space);
352 multi->space = space;
353
354 return multi;
355 error:
356 isl_space_free(domain);
357 isl_space_free(space);
358 FN(MULTI(BASE),free)(multi);
359 return NULL;
360 }
361
362 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
363 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
364 {
365 isl_space *space;
366
367 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
368 isl_space_copy(multi->space));
369 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
370 }
371
372 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
373 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
374 {
375 isl_space *domain;
376
377 domain = isl_space_domain(isl_space_copy(space));
378 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
379 }
380
381 /* Set the id of the given dimension of "multi" to "id".
382 */
383 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_id)(
384 __isl_take MULTI(BASE) *multi,
385 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
386 {
387 isl_space *space;
388
389 multi = FN(MULTI(BASE),cow)(multi);
390 if (!multi || !id)
391 goto error;
392
393 space = FN(MULTI(BASE),get_space)(multi);
394 space = isl_space_set_dim_id(space, type, pos, id);
395
396 return FN(MULTI(BASE),reset_space)(multi, space);
397 error:
398 isl_id_free(id);
399 FN(MULTI(BASE),free)(multi);
400 return NULL;
401 }
402
403 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_name)(
404 __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
405 const char *s)
406 {
407 isl_space *space;
408
409 multi = FN(MULTI(BASE),cow)(multi);
410 if (!multi)
411 return NULL;
412
413 space = FN(MULTI(BASE),get_space)(multi);
414 space = isl_space_set_tuple_name(space, type, s);
415
416 return FN(MULTI(BASE),reset_space)(multi, space);
417 }
418
419 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
420 __isl_take MULTI(BASE) *multi, enum isl_dim_type type,
421 __isl_take isl_id *id)
422 {
423 isl_space *space;
424
425 multi = FN(MULTI(BASE),cow)(multi);
426 if (!multi)
427 goto error;
428
429 space = FN(MULTI(BASE),get_space)(multi);
430 space = isl_space_set_tuple_id(space, type, id);
431
432 return FN(MULTI(BASE),reset_space)(multi, space);
433 error:
434 isl_id_free(id);
435 return NULL;
436 }
437
438 /* Drop the id on the specified tuple.
439 */
440 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_tuple_id)(
441 __isl_take MULTI(BASE) *multi, enum isl_dim_type type)
442 {
443 isl_space *space;
444
445 if (!multi)
446 return NULL;
447 if (!FN(MULTI(BASE),has_tuple_id)(multi, type))
448 return multi;
449
450 multi = FN(MULTI(BASE),cow)(multi);
451 if (!multi)
452 return NULL;
453
454 space = FN(MULTI(BASE),get_space)(multi);
455 space = isl_space_reset_tuple_id(space, type);
456
457 return FN(MULTI(BASE),reset_space)(multi, space);
458 }
459
460 /* Reset the user pointer on all identifiers of parameters and tuples
461 * of the space of "multi".
462 */
463 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_user)(
464 __isl_take MULTI(BASE) *multi)
465 {
466 isl_space *space;
467
468 space = FN(MULTI(BASE),get_space)(multi);
469 space = isl_space_reset_user(space);
470
471 return FN(MULTI(BASE),reset_space)(multi, space);
472 }
473
474 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
475 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
476 {
477 int i;
478 isl_space *space;
479
480 multi = FN(MULTI(BASE),cow)(multi);
481 if (!multi || !exp)
482 goto error;
483
484 for (i = 0; i < multi->n; ++i) {
485 multi->u.p[i] = FN(EL,realign_domain)(multi->u.p[i],
486 isl_reordering_copy(exp));
487 if (!multi->u.p[i])
488 goto error;
489 }
490
491 space = isl_reordering_get_space(exp);
492 multi = FN(MULTI(BASE),reset_domain_space)(multi, space);
493
494 isl_reordering_free(exp);
495 return multi;
496 error:
497 isl_reordering_free(exp);
498 FN(MULTI(BASE),free)(multi);
499 return NULL;
500 }
501
502 /* Align the parameters of "multi" to those of "model".
503 *
504 * If "multi" has an explicit domain, then align the parameters
505 * of the domain first.
506 */
507 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
508 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
509 {
510 isl_ctx *ctx;
511 isl_bool equal_params;
512 isl_reordering *exp;
513
514 if (!multi || !model)
515 goto error;
516
517 equal_params = isl_space_has_equal_params(multi->space, model);
518 if (equal_params < 0)
519 goto error;
520 if (equal_params) {
521 isl_space_free(model);
522 return multi;
523 }
524
525 ctx = isl_space_get_ctx(model);
526 if (!isl_space_has_named_params(model))
527 isl_die(ctx, isl_error_invalid,
528 "model has unnamed parameters", goto error);
529 if (!isl_space_has_named_params(multi->space))
530 isl_die(ctx, isl_error_invalid,
531 "input has unnamed parameters", goto error);
532
533 if (FN(MULTI(BASE),has_explicit_domain)(multi)) {
534 multi = FN(MULTI(BASE),align_explicit_domain_params)(multi,
535 isl_space_copy(model));
536 if (!multi)
537 goto error;
538 }
539 exp = isl_parameter_alignment_reordering(multi->space, model);
540 exp = isl_reordering_extend_space(exp,
541 FN(MULTI(BASE),get_domain_space)(multi));
542 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
543
544 isl_space_free(model);
545 return multi;
546 error:
547 isl_space_free(model);
548 FN(MULTI(BASE),free)(multi);
549 return NULL;
550 }
551
552 /* Create a multi expression in the given space with the elements of "list"
553 * as base expressions.
554 *
555 * Since isl_multi_*_restore_* assumes that the element and
556 * the multi expression have matching spaces, the alignment
557 * (if any) needs to be performed beforehand.
558 */
559 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
560 __isl_take isl_space *space, __isl_take LIST(EL) *list)
561 {
562 int i;
563 int n;
564 isl_ctx *ctx;
565 MULTI(BASE) *multi;
566
567 if (!space || !list)
568 goto error;
569
570 ctx = isl_space_get_ctx(space);
571 n = FN(FN(LIST(EL),n),BASE)(list);
572 if (n != isl_space_dim(space, isl_dim_out))
573 isl_die(ctx, isl_error_invalid,
574 "invalid number of elements in list", goto error);
575
576 for (i = 0; i < n; ++i) {
577 EL *el = FN(LIST(EL),peek)(list, i);
578 space = isl_space_align_params(space, FN(EL,get_space)(el));
579 }
580 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
581 for (i = 0; i < n; ++i) {
582 EL *el = FN(FN(LIST(EL),get),BASE)(list, i);
583 el = FN(EL,align_params)(el, isl_space_copy(space));
584 multi = FN(MULTI(BASE),restore_check_space)(multi, i, el);
585 }
586
587 isl_space_free(space);
588 FN(LIST(EL),free)(list);
589 return multi;
590 error:
591 isl_space_free(space);
592 FN(LIST(EL),free)(list);
593 return NULL;
594 }
595
596 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
597 __isl_take MULTI(BASE) *multi,
598 enum isl_dim_type type, unsigned first, unsigned n)
599 {
600 int i;
601 unsigned dim;
602
603 multi = FN(MULTI(BASE),cow)(multi);
604 if (!multi)
605 return NULL;
606
607 dim = FN(MULTI(BASE),dim)(multi, type);
608 if (first + n > dim || first + n < first)
609 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
610 "index out of bounds",
611 return FN(MULTI(BASE),free)(multi));
612
613 multi->space = isl_space_drop_dims(multi->space, type, first, n);
614 if (!multi->space)
615 return FN(MULTI(BASE),free)(multi);
616
617 if (type == isl_dim_out) {
618 for (i = 0; i < n; ++i)
619 FN(EL,free)(multi->u.p[first + i]);
620 for (i = first; i + n < multi->n; ++i)
621 multi->u.p[i] = multi->u.p[i + n];
622 multi->n -= n;
623 if (n > 0 && FN(MULTI(BASE),has_explicit_domain)(multi))
624 multi = FN(MULTI(BASE),init_explicit_domain)(multi);
625
626 return multi;
627 }
628
629 if (FN(MULTI(BASE),has_explicit_domain)(multi))
630 multi = FN(MULTI(BASE),drop_explicit_domain_dims)(multi,
631 type, first, n);
632 if (!multi)
633 return NULL;
634
635 for (i = 0; i < multi->n; ++i) {
636 multi->u.p[i] = FN(EL,drop_dims)(multi->u.p[i], type, first, n);
637 if (!multi->u.p[i])
638 return FN(MULTI(BASE),free)(multi);
639 }
640
641 return multi;
642 }
643
644 /* Align the parameters of "multi1" and "multi2" (if needed) and call "fn".
645 */
646 static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_multi_and)(
647 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
648 __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi1,
649 __isl_take MULTI(BASE) *multi2))
650 {
651 isl_ctx *ctx;
652 isl_bool equal_params;
653
654 if (!multi1 || !multi2)
655 goto error;
656 equal_params = isl_space_has_equal_params(multi1->space, multi2->space);
657 if (equal_params < 0)
658 goto error;
659 if (equal_params)
660 return fn(multi1, multi2);
661 ctx = FN(MULTI(BASE),get_ctx)(multi1);
662 if (!isl_space_has_named_params(multi1->space) ||
663 !isl_space_has_named_params(multi2->space))
664 isl_die(ctx, isl_error_invalid,
665 "unaligned unnamed parameters", goto error);
666 multi1 = FN(MULTI(BASE),align_params)(multi1,
667 FN(MULTI(BASE),get_space)(multi2));
668 multi2 = FN(MULTI(BASE),align_params)(multi2,
669 FN(MULTI(BASE),get_space)(multi1));
670 return fn(multi1, multi2);
671 error:
672 FN(MULTI(BASE),free)(multi1);
673 FN(MULTI(BASE),free)(multi2);
674 return NULL;
675 }
676
677 /* Given two MULTI(BASE)s A -> B and C -> D,
678 * construct a MULTI(BASE) (A * C) -> [B -> D].
679 *
680 * The parameters are assumed to have been aligned.
681 *
682 * If "multi1" and/or "multi2" has an explicit domain, then
683 * intersect the domain of the result with these explicit domains.
684 */
685 static __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product_aligned)(
686 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
687 {
688 int i, n1, n2;
689 EL *el;
690 isl_space *space;
691 MULTI(BASE) *res;
692
693 if (!multi1 || !multi2)
694 goto error;
695
696 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
697 FN(MULTI(BASE),get_space)(multi2));
698 res = FN(MULTI(BASE),alloc)(space);
699
700 n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
701 n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
702
703 for (i = 0; i < n1; ++i) {
704 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
705 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
706 }
707
708 for (i = 0; i < n2; ++i) {
709 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
710 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
711 }
712
713 if (FN(MULTI(BASE),has_explicit_domain)(multi1))
714 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi1);
715 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
716 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi2);
717
718 FN(MULTI(BASE),free)(multi1);
719 FN(MULTI(BASE),free)(multi2);
720 return res;
721 error:
722 FN(MULTI(BASE),free)(multi1);
723 FN(MULTI(BASE),free)(multi2);
724 return NULL;
725 }
726
727 /* Given two MULTI(BASE)s A -> B and C -> D,
728 * construct a MULTI(BASE) (A * C) -> [B -> D].
729 */
730 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
731 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
732 {
733 return FN(MULTI(BASE),align_params_multi_multi_and)(multi1, multi2,
734 &FN(MULTI(BASE),range_product_aligned));
735 }
736
737 /* Is the range of "multi" a wrapped relation?
738 */
739 isl_bool FN(MULTI(BASE),range_is_wrapping)(__isl_keep MULTI(BASE) *multi)
740 {
741 if (!multi)
742 return isl_bool_error;
743 return isl_space_range_is_wrapping(multi->space);
744 }
745
746 /* Given a function A -> [B -> C], extract the function A -> B.
747 */
748 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_domain)(
749 __isl_take MULTI(BASE) *multi)
750 {
751 isl_space *space;
752 int total, keep;
753
754 if (!multi)
755 return NULL;
756 if (!isl_space_range_is_wrapping(multi->space))
757 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
758 "range is not a product",
759 return FN(MULTI(BASE),free)(multi));
760
761 space = FN(MULTI(BASE),get_space)(multi);
762 total = isl_space_dim(space, isl_dim_out);
763 space = isl_space_range_factor_domain(space);
764 keep = isl_space_dim(space, isl_dim_out);
765 multi = FN(MULTI(BASE),drop_dims)(multi,
766 isl_dim_out, keep, total - keep);
767 multi = FN(MULTI(BASE),reset_space)(multi, space);
768
769 return multi;
770 }
771
772 /* Given a function A -> [B -> C], extract the function A -> C.
773 */
774 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)(
775 __isl_take MULTI(BASE) *multi)
776 {
777 isl_space *space;
778 int total, keep;
779
780 if (!multi)
781 return NULL;
782 if (!isl_space_range_is_wrapping(multi->space))
783 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
784 "range is not a product",
785 return FN(MULTI(BASE),free)(multi));
786
787 space = FN(MULTI(BASE),get_space)(multi);
788 total = isl_space_dim(space, isl_dim_out);
789 space = isl_space_range_factor_range(space);
790 keep = isl_space_dim(space, isl_dim_out);
791 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);
792 multi = FN(MULTI(BASE),reset_space)(multi, space);
793
794 return multi;
795 }
796
797 /* Given a function [B -> C], extract the function C.
798 */
799 __isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)(
800 __isl_take MULTI(BASE) *multi)
801 {
802 isl_space *space;
803 int total, keep;
804
805 if (!multi)
806 return NULL;
807 if (!isl_space_is_wrapping(multi->space))
808 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
809 "not a product", return FN(MULTI(BASE),free)(multi));
810
811 space = FN(MULTI(BASE),get_space)(multi);
812 total = isl_space_dim(space, isl_dim_out);
813 space = isl_space_factor_range(space);
814 keep = isl_space_dim(space, isl_dim_out);
815 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);
816 multi = FN(MULTI(BASE),reset_space)(multi, space);
817
818 return multi;
819 }
820
821 __isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
822 __isl_take MULTI(BASE) *multi)
823 {
824 if (!multi)
825 return NULL;
826
827 if (!multi->space->nested[1])
828 return multi;
829
830 multi = FN(MULTI(BASE),cow)(multi);
831 if (!multi)
832 return NULL;
833
834 multi->space = isl_space_flatten_range(multi->space);
835 if (!multi->space)
836 return FN(MULTI(BASE),free)(multi);
837
838 return multi;
839 }
840
841 /* Given two MULTI(BASE)s A -> B and C -> D,
842 * construct a MULTI(BASE) (A * C) -> (B, D).
843 */
844 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
845 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
846 {
847 MULTI(BASE) *multi;
848
849 multi = FN(MULTI(BASE),range_product)(multi1, multi2);
850 multi = FN(MULTI(BASE),flatten_range)(multi);
851 return multi;
852 }
853
854 /* Given two multi expressions, "multi1"
855 *
856 * [A] -> [B1 B2]
857 *
858 * where B2 starts at position "pos", and "multi2"
859 *
860 * [A] -> [D]
861 *
862 * return the multi expression
863 *
864 * [A] -> [B1 D B2]
865 */
866 __isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
867 __isl_take MULTI(BASE) *multi1, unsigned pos,
868 __isl_take MULTI(BASE) *multi2)
869 {
870 MULTI(BASE) *res;
871 unsigned dim;
872
873 if (!multi1 || !multi2)
874 goto error;
875
876 dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
877 if (pos > dim)
878 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
879 "index out of bounds", goto error);
880
881 res = FN(MULTI(BASE),copy)(multi1);
882 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
883 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
884
885 res = FN(MULTI(BASE),flat_range_product)(res, multi2);
886 res = FN(MULTI(BASE),flat_range_product)(res, multi1);
887
888 return res;
889 error:
890 FN(MULTI(BASE),free)(multi1);
891 FN(MULTI(BASE),free)(multi2);
892 return NULL;
893 }
894
895 /* Check that "multi1" and "multi2" live in the same space,
896 * reporting an error if they do not.
897 */
898 static isl_stat FN(MULTI(BASE),check_equal_space)(
899 __isl_keep MULTI(BASE) *multi1, __isl_keep MULTI(BASE) *multi2)
900 {
901 isl_bool equal;
902
903 if (!multi1 || !multi2)
904 return isl_stat_error;
905
906 equal = isl_space_is_equal(multi1->space, multi2->space);
907 if (equal < 0)
908 return isl_stat_error;
909 if (!equal)
910 isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
911 "spaces don't match", return isl_stat_error);
912
913 return isl_stat_ok;
914 }
915
916 /* This function is currently only used from isl_aff.c
917 */
918 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
919 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
920 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
921 __attribute__ ((unused));
922
923 /* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
924 * return the result.
925 *
926 * If "multi2" has an explicit domain, then
927 * intersect the domain of the result with this explicit domain.
928 */
929 static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
930 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
931 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
932 {
933 int i;
934
935 multi1 = FN(MULTI(BASE),cow)(multi1);
936 if (FN(MULTI(BASE),check_equal_space)(multi1, multi2) < 0)
937 goto error;
938
939 for (i = 0; i < multi1->n; ++i) {
940 multi1->u.p[i] = fn(multi1->u.p[i],
941 FN(EL,copy)(multi2->u.p[i]));
942 if (!multi1->u.p[i])
943 goto error;
944 }
945
946 if (FN(MULTI(BASE),has_explicit_domain)(multi2))
947 multi1 = FN(MULTI(BASE),intersect_explicit_domain)(multi1,
948 multi2);
949
950 FN(MULTI(BASE),free)(multi2);
951 return multi1;
952 error:
953 FN(MULTI(BASE),free)(multi1);
954 FN(MULTI(BASE),free)(multi2);
955 return NULL;
956 }
957
958 /* Add "multi2" to "multi1" and return the result.
959 *
960 * The parameters of "multi1" and "multi2" are assumed to have been aligned.
961 */
962 static __isl_give MULTI(BASE) *FN(MULTI(BASE),add_aligned)(
963 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
964 {
965 return FN(MULTI(BASE),bin_op)(multi1, multi2, &FN(EL,add));
966 }
967
968 /* Add "multi2" to "multi1" and return the result.
969 */
970 __isl_give MULTI(BASE) *FN(MULTI(BASE),add)(__isl_take MULTI(BASE) *multi1,
971 __isl_take MULTI(BASE) *multi2)
972 {
973 return FN(MULTI(BASE),align_params_multi_multi_and)(multi1, multi2,
974 &FN(MULTI(BASE),add_aligned));
975 }
976
977 /* Subtract "multi2" from "multi1" and return the result.
978 *
979 * The parameters of "multi1" and "multi2" are assumed to have been aligned.
980 */
981 static __isl_give MULTI(BASE) *FN(MULTI(BASE),sub_aligned)(
982 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
983 {
984 return FN(MULTI(BASE),bin_op)(multi1, multi2, &FN(EL,sub));
985 }
986
987 /* Subtract "multi2" from "multi1" and return the result.
988 */
989 __isl_give MULTI(BASE) *FN(MULTI(BASE),sub)(__isl_take MULTI(BASE) *multi1,
990 __isl_take MULTI(BASE) *multi2)
991 {
992 return FN(MULTI(BASE),align_params_multi_multi_and)(multi1, multi2,
993 &FN(MULTI(BASE),sub_aligned));
994 }
995
996 /* Multiply the elements of "multi" by "v" and return the result.
997 */
998 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_val)(__isl_take MULTI(BASE) *multi,
999 __isl_take isl_val *v)
1000 {
1001 int i;
1002
1003 if (!multi || !v)
1004 goto error;
1005
1006 if (isl_val_is_one(v)) {
1007 isl_val_free(v);
1008 return multi;
1009 }
1010
1011 if (!isl_val_is_rat(v))
1012 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1013 "expecting rational factor", goto error);
1014
1015 multi = FN(MULTI(BASE),cow)(multi);
1016 if (!multi)
1017 return NULL;
1018
1019 for (i = 0; i < multi->n; ++i) {
1020 multi->u.p[i] = FN(EL,scale_val)(multi->u.p[i],
1021 isl_val_copy(v));
1022 if (!multi->u.p[i])
1023 goto error;
1024 }
1025
1026 isl_val_free(v);
1027 return multi;
1028 error:
1029 isl_val_free(v);
1030 return FN(MULTI(BASE),free)(multi);
1031 }
1032
1033 /* Divide the elements of "multi" by "v" and return the result.
1034 */
1035 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_down_val)(
1036 __isl_take MULTI(BASE) *multi, __isl_take isl_val *v)
1037 {
1038 int i;
1039
1040 if (!multi || !v)
1041 goto error;
1042
1043 if (isl_val_is_one(v)) {
1044 isl_val_free(v);
1045 return multi;
1046 }
1047
1048 if (!isl_val_is_rat(v))
1049 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1050 "expecting rational factor", goto error);
1051 if (isl_val_is_zero(v))
1052 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1053 "cannot scale down by zero", goto error);
1054
1055 multi = FN(MULTI(BASE),cow)(multi);
1056 if (!multi)
1057 return NULL;
1058
1059 for (i = 0; i < multi->n; ++i) {
1060 multi->u.p[i] = FN(EL,scale_down_val)(multi->u.p[i],
1061 isl_val_copy(v));
1062 if (!multi->u.p[i])
1063 goto error;
1064 }
1065
1066 isl_val_free(v);
1067 return multi;
1068 error:
1069 isl_val_free(v);
1070 return FN(MULTI(BASE),free)(multi);
1071 }
1072
1073 /* Multiply the elements of "multi" by the corresponding element of "mv"
1074 * and return the result.
1075 */
1076 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_multi_val)(
1077 __isl_take MULTI(BASE) *multi, __isl_take isl_multi_val *mv)
1078 {
1079 int i;
1080
1081 if (!multi || !mv)
1082 goto error;
1083
1084 if (!isl_space_tuple_is_equal(multi->space, isl_dim_out,
1085 mv->space, isl_dim_set))
1086 isl_die(isl_multi_val_get_ctx(mv), isl_error_invalid,
1087 "spaces don't match", goto error);
1088
1089 multi = FN(MULTI(BASE),cow)(multi);
1090 if (!multi)
1091 goto error;
1092
1093 for (i = 0; i < multi->n; ++i) {
1094 isl_val *v;
1095
1096 v = isl_multi_val_get_val(mv, i);
1097 multi->u.p[i] = FN(EL,scale_val)(multi->u.p[i], v);
1098 if (!multi->u.p[i])
1099 goto error;
1100 }
1101
1102 isl_multi_val_free(mv);
1103 return multi;
1104 error:
1105 isl_multi_val_free(mv);
1106 return FN(MULTI(BASE),free)(multi);
1107 }
1108
1109 /* Divide the elements of "multi" by the corresponding element of "mv"
1110 * and return the result.
1111 */
1112 __isl_give MULTI(BASE) *FN(MULTI(BASE),scale_down_multi_val)(
1113 __isl_take MULTI(BASE) *multi, __isl_take isl_multi_val *mv)
1114 {
1115 int i;
1116
1117 if (!multi || !mv)
1118 goto error;
1119
1120 if (!isl_space_tuple_is_equal(multi->space, isl_dim_out,
1121 mv->space, isl_dim_set))
1122 isl_die(isl_multi_val_get_ctx(mv), isl_error_invalid,
1123 "spaces don't match", goto error);
1124
1125 multi = FN(MULTI(BASE),cow)(multi);
1126 if (!multi)
1127 return NULL;
1128
1129 for (i = 0; i < multi->n; ++i) {
1130 isl_val *v;
1131
1132 v = isl_multi_val_get_val(mv, i);
1133 multi->u.p[i] = FN(EL,scale_down_val)(multi->u.p[i], v);
1134 if (!multi->u.p[i])
1135 goto error;
1136 }
1137
1138 isl_multi_val_free(mv);
1139 return multi;
1140 error:
1141 isl_multi_val_free(mv);
1142 return FN(MULTI(BASE),free)(multi);
1143 }
1144
1145 /* Compute the residues of the elements of "multi" modulo
1146 * the corresponding element of "mv" and return the result.
1147 */
1148 __isl_give MULTI(BASE) *FN(MULTI(BASE),mod_multi_val)(
1149 __isl_take MULTI(BASE) *multi, __isl_take isl_multi_val *mv)
1150 {
1151 int i;
1152
1153 if (!multi || !mv)
1154 goto error;
1155
1156 if (!isl_space_tuple_is_equal(multi->space, isl_dim_out,
1157 mv->space, isl_dim_set))
1158 isl_die(isl_multi_val_get_ctx(mv), isl_error_invalid,
1159 "spaces don't match", goto error);
1160
1161 multi = FN(MULTI(BASE),cow)(multi);
1162 if (!multi)
1163 goto error;
1164
1165 for (i = 0; i < multi->n; ++i) {
1166 isl_val *v;
1167
1168 v = isl_multi_val_get_val(mv, i);
1169 multi->u.p[i] = FN(EL,mod_val)(multi->u.p[i], v);
1170 if (!multi->u.p[i])
1171 goto error;
1172 }
1173
1174 isl_multi_val_free(mv);
1175 return multi;
1176 error:
1177 isl_multi_val_free(mv);
1178 return FN(MULTI(BASE),free)(multi);
1179 }
1180
1181 /* Convert a multiple expression defined over a parameter domain
1182 * into one that is defined over a zero-dimensional set.
1183 */
1184 __isl_give MULTI(BASE) *FN(MULTI(BASE),from_range)(
1185 __isl_take MULTI(BASE) *multi)
1186 {
1187 isl_space *space;
1188
1189 if (!multi)
1190 return NULL;
1191 if (!isl_space_is_set(multi->space))
1192 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
1193 "not living in a set space",
1194 return FN(MULTI(BASE),free)(multi));
1195
1196 space = FN(MULTI(BASE),get_space)(multi);
1197 space = isl_space_from_range(space);
1198 multi = FN(MULTI(BASE),reset_space)(multi, space);
1199
1200 return multi;
1201 }
1202
1203 /* Are "multi1" and "multi2" obviously equal?
1204 */
1205 isl_bool FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1,
1206 __isl_keep MULTI(BASE) *multi2)
1207 {
1208 int i;
1209 isl_bool equal;
1210
1211 if (!multi1 || !multi2)
1212 return isl_bool_error;
1213 if (multi1->n != multi2->n)
1214 return isl_bool_false;
1215 equal = isl_space_is_equal(multi1->space, multi2->space);
1216 if (equal < 0 || !equal)
1217 return equal;
1218
1219 for (i = 0; i < multi1->n; ++i) {
1220 equal = FN(EL,plain_is_equal)(multi1->u.p[i], multi2->u.p[i]);
1221 if (equal < 0 || !equal)
1222 return equal;
1223 }
1224
1225 if (FN(MULTI(BASE),has_explicit_domain)(multi1) ||
1226 FN(MULTI(BASE),has_explicit_domain)(multi2)) {
1227 equal = FN(MULTI(BASE),equal_explicit_domain)(multi1, multi2);
1228 if (equal < 0 || !equal)
1229 return equal;
1230 }
1231
1232 return isl_bool_true;
1233 }
1234
1235 /* Does "multi" involve any NaNs?
1236 */
1237 isl_bool FN(MULTI(BASE),involves_nan)(__isl_keep MULTI(BASE) *multi)
1238 {
1239 int i;
1240
1241 if (!multi)
1242 return isl_bool_error;
1243 if (multi->n == 0)
1244 return isl_bool_false;
1245
1246 for (i = 0; i < multi->n; ++i) {
1247 isl_bool has_nan = FN(EL,involves_nan)(multi->u.p[i]);
1248 if (has_nan < 0 || has_nan)
1249 return has_nan;
1250 }
1251
1252 return isl_bool_false;
1253 }
1254
1255 /* Return the opposite of "multi".
1256 */
1257 __isl_give MULTI(BASE) *FN(MULTI(BASE),neg)(__isl_take MULTI(BASE) *multi)
1258 {
1259 int i;
1260
1261 multi = FN(MULTI(BASE),cow)(multi);
1262 if (!multi)
1263 return NULL;
1264
1265 for (i = 0; i < multi->n; ++i) {
1266 multi->u.p[i] = FN(EL,neg)(multi->u.p[i]);
1267 if (!multi->u.p[i])
1268 return FN(MULTI(BASE),free)(multi);
1269 }
1270
1271 return multi;
1272 }
Integer set library