isl_map_simplify.c: div_find_coalesce: return isl_size
[isl.git] / isl_pw_templ.c
blobc431677df3198053b4b19b31c387fa3cf1294ec9
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2014 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 #include <isl/id.h>
15 #include <isl/aff.h>
16 #include <isl_sort.h>
17 #include <isl_val_private.h>
19 #include <isl_pw_macro.h>
21 #include "opt_type.h"
23 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *space
24 OPT_TYPE_PARAM, int n)
26 isl_ctx *ctx;
27 struct PW *pw;
29 if (!space)
30 return NULL;
31 ctx = isl_space_get_ctx(space);
32 isl_assert(ctx, n >= 0, goto error);
33 pw = isl_alloc(ctx, struct PW,
34 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
35 if (!pw)
36 goto error;
38 pw->ref = 1;
39 OPT_SET_TYPE(pw->, type);
40 pw->size = n;
41 pw->n = 0;
42 pw->dim = space;
43 return pw;
44 error:
45 isl_space_free(space);
46 return NULL;
49 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)
51 return FN(PW,alloc_size)(space OPT_TYPE_ARG(NO_LOC), 0);
54 /* Add a piece with domain "set" and base expression "el"
55 * to the piecewise expression "pw".
57 * Do this independently of the values of "set" and "el",
58 * such that this function can be used by isl_pw_*_dup.
60 static __isl_give PW *FN(PW,add_dup_piece)(__isl_take PW *pw,
61 __isl_take isl_set *set, __isl_take EL *el)
63 isl_ctx *ctx;
64 isl_space *el_dim = NULL;
66 if (!pw || !set || !el)
67 goto error;
69 ctx = isl_set_get_ctx(set);
70 if (!OPT_EQUAL_TYPES(pw->, el->))
71 isl_die(ctx, isl_error_invalid, "fold types don't match",
72 goto error);
73 el_dim = FN(EL,get_space(el));
74 isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error);
75 isl_assert(ctx, pw->n < pw->size, goto error);
77 pw->p[pw->n].set = set;
78 pw->p[pw->n].FIELD = el;
79 pw->n++;
81 isl_space_free(el_dim);
82 return pw;
83 error:
84 isl_space_free(el_dim);
85 FN(PW,free)(pw);
86 isl_set_free(set);
87 FN(EL,free)(el);
88 return NULL;
91 /* Add a piece with domain "set" and base expression "el"
92 * to the piecewise expression "pw", provided the domain
93 * is not obviously empty and the base expression
94 * is not equal to the default value.
96 __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,
97 __isl_take isl_set *set, __isl_take EL *el)
99 isl_bool skip;
101 skip = isl_set_plain_is_empty(set);
102 if (skip >= 0 && !skip)
103 skip = FN(EL,EL_IS_ZERO)(el);
104 if (skip >= 0 && !skip)
105 return FN(PW,add_dup_piece)(pw, set, el);
107 isl_set_free(set);
108 FN(EL,free)(el);
109 if (skip < 0)
110 return FN(PW,free)(pw);
111 return pw;
114 /* Does the space of "set" correspond to that of the domain of "el".
116 static isl_bool FN(PW,compatible_domain)(__isl_keep EL *el,
117 __isl_keep isl_set *set)
119 isl_bool ok;
120 isl_space *el_space, *set_space;
122 if (!set || !el)
123 return isl_bool_error;
124 set_space = isl_set_get_space(set);
125 el_space = FN(EL,get_space)(el);
126 ok = isl_space_is_domain_internal(set_space, el_space);
127 isl_space_free(el_space);
128 isl_space_free(set_space);
129 return ok;
132 /* Check that the space of "set" corresponds to that of the domain of "el".
134 static isl_stat FN(PW,check_compatible_domain)(__isl_keep EL *el,
135 __isl_keep isl_set *set)
137 isl_bool ok;
139 ok = FN(PW,compatible_domain)(el, set);
140 if (ok < 0)
141 return isl_stat_error;
142 if (!ok)
143 isl_die(isl_set_get_ctx(set), isl_error_invalid,
144 "incompatible spaces", return isl_stat_error);
146 return isl_stat_ok;
149 __isl_give PW *FN(PW,alloc)(OPT_TYPE_PARAM_FIRST
150 __isl_take isl_set *set, __isl_take EL *el)
152 PW *pw;
154 if (FN(PW,check_compatible_domain)(el, set) < 0)
155 goto error;
157 pw = FN(PW,alloc_size)(FN(EL,get_space)(el) OPT_TYPE_ARG(NO_LOC), 1);
159 return FN(PW,add_piece)(pw, set, el);
160 error:
161 isl_set_free(set);
162 FN(EL,free)(el);
163 return NULL;
166 __isl_give PW *FN(PW,dup)(__isl_keep PW *pw)
168 int i;
169 PW *dup;
171 if (!pw)
172 return NULL;
174 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim)
175 OPT_TYPE_ARG(pw->), pw->n);
176 if (!dup)
177 return NULL;
179 for (i = 0; i < pw->n; ++i)
180 dup = FN(PW,add_dup_piece)(dup, isl_set_copy(pw->p[i].set),
181 FN(EL,copy)(pw->p[i].FIELD));
183 return dup;
186 __isl_give PW *FN(PW,cow)(__isl_take PW *pw)
188 if (!pw)
189 return NULL;
191 if (pw->ref == 1)
192 return pw;
193 pw->ref--;
194 return FN(PW,dup)(pw);
197 __isl_give PW *FN(PW,copy)(__isl_keep PW *pw)
199 if (!pw)
200 return NULL;
202 pw->ref++;
203 return pw;
206 __isl_null PW *FN(PW,free)(__isl_take PW *pw)
208 int i;
210 if (!pw)
211 return NULL;
212 if (--pw->ref > 0)
213 return NULL;
215 for (i = 0; i < pw->n; ++i) {
216 isl_set_free(pw->p[i].set);
217 FN(EL,free)(pw->p[i].FIELD);
219 isl_space_free(pw->dim);
220 free(pw);
222 return NULL;
225 /* Return the space of "pw".
227 __isl_keep isl_space *FN(PW,peek_space)(__isl_keep PW *pw)
229 return pw ? pw->dim : NULL;
232 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
234 return isl_space_copy(FN(PW,peek_space)(pw));
237 /* Return the space of "pw".
238 * This may be either a copy or the space itself
239 * if there is only one reference to "pw".
240 * This allows the space to be modified inplace
241 * if both the piecewise expression and its space have only a single reference.
242 * The caller is not allowed to modify "pw" between this call and
243 * a subsequent call to isl_pw_*_restore_*.
244 * The only exception is that isl_pw_*_free can be called instead.
246 static __isl_give isl_space *FN(PW,take_space)(__isl_keep PW *pw)
248 isl_space *space;
250 if (!pw)
251 return NULL;
252 if (pw->ref != 1)
253 return FN(PW,get_space)(pw);
254 space = pw->dim;
255 pw->dim = NULL;
256 return space;
259 /* Set the space of "pw" to "space", where the space of "pw" may be missing
260 * due to a preceding call to isl_pw_*_take_space.
261 * However, in this case, "pw" only has a single reference and
262 * then the call to isl_pw_*_cow has no effect.
264 static __isl_give PW *FN(PW,restore_space)(__isl_take PW *pw,
265 __isl_take isl_space *space)
267 if (!pw || !space)
268 goto error;
270 if (pw->dim == space) {
271 isl_space_free(space);
272 return pw;
275 pw = FN(PW,cow)(pw);
276 if (!pw)
277 goto error;
278 isl_space_free(pw->dim);
279 pw->dim = space;
281 return pw;
282 error:
283 FN(PW,free)(pw);
284 isl_space_free(space);
285 return NULL;
288 /* Check that "pos" is a valid position for a cell in "pw".
290 static isl_stat FN(PW,check_pos)(__isl_keep PW *pw, int pos)
292 if (!pw)
293 return isl_stat_error;
294 if (pos < 0 || pos >= pw->n)
295 isl_die(FN(PW,get_ctx)(pw), isl_error_internal,
296 "position out of bounds", return isl_stat_error);
297 return isl_stat_ok;
300 /* Return the cell at position "pos" in "pw".
302 static __isl_keep isl_set *FN(PW,peek_domain_at)(__isl_keep PW *pw, int pos)
304 if (FN(PW,check_pos)(pw, pos) < 0)
305 return NULL;
306 return pw->p[pos].set;
309 /* Return a copy of the cell at position "pos" in "pw".
311 static __isl_give isl_set *FN(PW,get_domain_at)(__isl_keep PW *pw, int pos)
313 return isl_set_copy(FN(PW,peek_domain_at)(pw, pos));
316 /* Return the cell at position "pos" in "pw".
317 * This may be either a copy or the cell itself
318 * if there is only one reference to "pw".
319 * This allows the cell to be modified inplace
320 * if both the piecewise expression and this cell
321 * have only a single reference.
322 * The caller is not allowed to modify "pw" between this call and
323 * the subsequent call to isl_pw_*_restore_domain_at.
324 * The only exception is that isl_pw_*_free can be called instead.
326 static __isl_give isl_set *FN(PW,take_domain_at)(__isl_keep PW *pw, int pos)
328 isl_set *domain;
330 if (!pw)
331 return NULL;
332 if (pw->ref != 1)
333 return FN(PW,get_domain_at)(pw, pos);
334 if (FN(PW,check_pos)(pw, pos) < 0)
335 return NULL;
336 domain = pw->p[pos].set;
337 pw->p[pos].set = NULL;
338 return domain;
341 /* Set the cell at position "pos" in "pw" to "el",
342 * where this cell may be missing
343 * due to a preceding call to isl_pw_*_take_domain_at.
344 * However, in this case, "pw" only has a single reference and
345 * then the call to isl_pw_*_cow has no effect.
347 static __isl_give PW *FN(PW,restore_domain_at)(__isl_take PW *pw, int pos,
348 __isl_take isl_set *domain)
350 if (FN(PW,check_pos)(pw, pos) < 0 || !domain)
351 goto error;
353 if (pw->p[pos].set == domain) {
354 isl_set_free(domain);
355 return pw;
358 pw = FN(PW,cow)(pw);
359 if (!pw)
360 goto error;
361 isl_set_free(pw->p[pos].set);
362 pw->p[pos].set = domain;
364 return pw;
365 error:
366 FN(PW,free)(pw);
367 isl_set_free(domain);
368 return NULL;
371 /* Return the base expression associated to
372 * the cell at position "pos" in "pw".
374 __isl_keep EL *FN(PW,peek_base_at)(__isl_keep PW *pw, int pos)
376 if (FN(PW,check_pos)(pw, pos) < 0)
377 return NULL;
378 return pw->p[pos].FIELD;
381 /* Return a copy of the base expression associated to
382 * the cell at position "pos" in "pw".
384 static __isl_give EL *FN(PW,get_base_at)(__isl_keep PW *pw, int pos)
386 return FN(EL,copy)(FN(PW,peek_base_at)(pw, pos));
389 /* Return the base expression associated to
390 * the cell at position "pos" in "pw".
391 * This may be either a copy or the base expression itself
392 * if there is only one reference to "pw".
393 * This allows the base expression to be modified inplace
394 * if both the piecewise expression and this base expression
395 * have only a single reference.
396 * The caller is not allowed to modify "pw" between this call and
397 * a subsequent call to isl_pw_*_restore_*.
398 * The only exception is that isl_pw_*_free can be called instead.
400 static __isl_give EL *FN(PW,take_base_at)(__isl_keep PW *pw, int pos)
402 EL *el;
404 if (!pw)
405 return NULL;
406 if (pw->ref != 1)
407 return FN(PW,get_base_at)(pw, pos);
408 if (FN(PW,check_pos)(pw, pos) < 0)
409 return NULL;
410 el = pw->p[pos].FIELD;
411 pw->p[pos].FIELD = NULL;
412 return el;
415 /* Set the base expression associated to
416 * the cell at position "pos" in "pw" to "el",
417 * where this base expression may be missing
418 * due to a preceding call to isl_pw_*_take_base_at.
419 * However, in this case, "pw" only has a single reference and
420 * then the call to isl_pw_*_cow has no effect.
421 * If "inplace" is set, then replacing the base expression by "el"
422 * is known not to change the meaning of "pw". It can therefore be replaced
423 * in all references to "pw".
425 static __isl_give PW *FN(PW,restore_base_at_)(__isl_take PW *pw, int pos,
426 __isl_take EL *el, int inplace)
428 if (FN(PW,check_pos)(pw, pos) < 0 || !el)
429 goto error;
431 if (pw->p[pos].FIELD == el) {
432 FN(EL,free)(el);
433 return pw;
436 if (!inplace)
437 pw = FN(PW,cow)(pw);
438 if (!pw)
439 goto error;
440 FN(EL,free)(pw->p[pos].FIELD);
441 pw->p[pos].FIELD = el;
443 return pw;
444 error:
445 FN(PW,free)(pw);
446 FN(EL,free)(el);
447 return NULL;
450 /* Set the base expression associated to
451 * the cell at position "pos" in "pw" to "el",
452 * where this base expression may be missing
453 * due to a preceding call to isl_pw_*_take_base_at.
455 static __isl_give PW *FN(PW,restore_base_at)(__isl_take PW *pw, int pos,
456 __isl_take EL *el)
458 return FN(PW,restore_base_at_)(pw, pos, el, 0);
461 /* Set the base expression associated to
462 * the cell at position "pos" in "pw" to "el",
463 * where this base expression may be missing
464 * due to a preceding call to isl_pw_*_take_base_at.
465 * Furthermore, replacing the base expression by "el"
466 * is known not to change the meaning of "pw".
468 static __isl_give PW *FN(PW,restore_base_at_inplace)(__isl_take PW *pw, int pos,
469 __isl_take EL *el)
471 return FN(PW,restore_base_at_)(pw, pos, el, 1);
474 /* Create a piecewise expression with the given base expression on a universe
475 * domain.
477 static __isl_give PW *FN(FN(FN(PW,from),BASE),type_base)(__isl_take EL *el
478 OPT_TYPE_PARAM)
480 isl_set *dom = isl_set_universe(FN(EL,get_domain_space)(el));
481 return FN(PW,alloc)(OPT_TYPE_ARG_FIRST(NO_LOC) dom, el);
484 /* Create a piecewise expression with the given base expression on a universe
485 * domain.
487 * If the default value of this piecewise type is zero and
488 * if "el" is effectively zero, then create an empty piecewise expression
489 * instead.
491 static __isl_give PW *FN(FN(FN(PW,from),BASE),type)(__isl_take EL *el
492 OPT_TYPE_PARAM)
494 isl_bool is_zero;
495 isl_space *space;
497 if (!DEFAULT_IS_ZERO)
498 return FN(FN(FN(PW,from),BASE),type_base)(el
499 OPT_TYPE_ARG(NO_LOC));
500 is_zero = FN(EL,EL_IS_ZERO)(el);
501 if (is_zero < 0)
502 goto error;
503 if (!is_zero)
504 return FN(FN(FN(PW,from),BASE),type_base)(el
505 OPT_TYPE_ARG(NO_LOC));
506 space = FN(EL,get_space)(el);
507 FN(EL,free)(el);
508 return FN(PW,ZERO)(space OPT_TYPE_ARG(NO_LOC));
509 error:
510 FN(EL,free)(el);
511 return NULL;
514 #ifdef HAS_TYPE
515 /* Create a piecewise expression with the given base expression on a universe
516 * domain.
518 * Pass along the type as an extra argument for improved uniformity
519 * with piecewise types that do not have a fold type.
521 __isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el)
523 enum isl_fold type = FN(EL,get_type)(el);
524 return FN(FN(FN(PW,from),BASE),type)(el, type);
526 #else
527 __isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el)
529 return FN(FN(FN(PW,from),BASE),type)(el);
531 #endif
533 const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type,
534 unsigned pos)
536 return pw ? isl_space_get_dim_name(pw->dim, type, pos) : NULL;
539 isl_bool FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
540 unsigned pos)
542 return pw ? isl_space_has_dim_id(pw->dim, type, pos) : isl_bool_error;
545 __isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
546 unsigned pos)
548 return pw ? isl_space_get_dim_id(pw->dim, type, pos) : NULL;
551 isl_bool FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
553 return pw ? isl_space_has_tuple_name(pw->dim, type) : isl_bool_error;
556 const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
558 return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL;
561 isl_bool FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
563 return pw ? isl_space_has_tuple_id(pw->dim, type) : isl_bool_error;
566 __isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
568 return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL;
571 isl_bool FN(PW,IS_ZERO)(__isl_keep PW *pw)
573 if (!pw)
574 return isl_bool_error;
576 return isl_bool_ok(pw->n == 0);
579 static __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
580 __isl_take isl_reordering *exp)
582 int i;
583 isl_size n;
585 n = FN(PW,n_piece)(pw);
586 if (n < 0 || !exp)
587 goto error;
589 for (i = 0; i < n; ++i) {
590 isl_set *domain;
591 EL *el;
593 domain = FN(PW,take_domain_at)(pw, i);
594 domain = isl_set_realign(domain, isl_reordering_copy(exp));
595 pw = FN(PW,restore_domain_at)(pw, i, domain);
597 el = FN(PW,take_base_at)(pw, i);
598 el = FN(EL,realign_domain)(el, isl_reordering_copy(exp));
599 pw = FN(PW,restore_base_at)(pw, i, el);
602 pw = FN(PW,reset_domain_space)(pw, isl_reordering_get_space(exp));
604 isl_reordering_free(exp);
605 return pw;
606 error:
607 isl_reordering_free(exp);
608 FN(PW,free)(pw);
609 return NULL;
612 #undef TYPE
613 #define TYPE PW
615 #include "isl_check_named_params_templ.c"
617 /* Align the parameters of "pw" to those of "model".
619 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
621 isl_ctx *ctx;
622 isl_bool equal_params;
624 if (!pw || !model)
625 goto error;
627 ctx = isl_space_get_ctx(model);
628 if (!isl_space_has_named_params(model))
629 isl_die(ctx, isl_error_invalid,
630 "model has unnamed parameters", goto error);
631 if (FN(PW,check_named_params)(pw) < 0)
632 goto error;
633 equal_params = isl_space_has_equal_params(pw->dim, model);
634 if (equal_params < 0)
635 goto error;
636 if (!equal_params) {
637 isl_space *space;
638 isl_reordering *exp;
640 space = FN(PW,get_domain_space)(pw);
641 exp = isl_parameter_alignment_reordering(space, model);
642 isl_space_free(space);
643 pw = FN(PW,realign_domain)(pw, exp);
646 isl_space_free(model);
647 return pw;
648 error:
649 isl_space_free(model);
650 FN(PW,free)(pw);
651 return NULL;
654 #undef TYPE
655 #define TYPE PW
657 static
658 #include "isl_align_params_bin_templ.c"
660 #undef SUFFIX
661 #define SUFFIX set
662 #undef ARG1
663 #define ARG1 PW
664 #undef ARG2
665 #define ARG2 isl_set
667 static
668 #include "isl_align_params_templ.c"
670 #undef TYPE
671 #define TYPE PW
673 #include "isl_type_has_equal_space_bin_templ.c"
674 #include "isl_type_check_equal_space_templ.c"
676 /* Private version of "union_add". For isl_pw_qpolynomial and
677 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
679 static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2)
681 int i, j, n;
682 struct PW *res;
683 isl_ctx *ctx;
684 isl_set *set;
686 if (FN(PW,align_params_bin)(&pw1, &pw2) < 0)
687 goto error;
689 ctx = isl_space_get_ctx(pw1->dim);
690 if (!OPT_EQUAL_TYPES(pw1->, pw2->))
691 isl_die(ctx, isl_error_invalid,
692 "fold types don't match", goto error);
693 if (FN(PW,check_equal_space)(pw1, pw2) < 0)
694 goto error;
696 if (FN(PW,IS_ZERO)(pw1)) {
697 FN(PW,free)(pw1);
698 return pw2;
701 if (FN(PW,IS_ZERO)(pw2)) {
702 FN(PW,free)(pw2);
703 return pw1;
706 n = (pw1->n + 1) * (pw2->n + 1);
707 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim)
708 OPT_TYPE_ARG(pw1->), n);
710 for (i = 0; i < pw1->n; ++i) {
711 set = isl_set_copy(pw1->p[i].set);
712 for (j = 0; j < pw2->n; ++j) {
713 struct isl_set *common;
714 EL *sum;
715 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
716 isl_set_copy(pw2->p[j].set));
717 if (isl_set_plain_is_empty(common)) {
718 isl_set_free(common);
719 continue;
721 set = isl_set_subtract(set,
722 isl_set_copy(pw2->p[j].set));
724 sum = FN(EL,add_on_domain)(common,
725 FN(EL,copy)(pw1->p[i].FIELD),
726 FN(EL,copy)(pw2->p[j].FIELD));
728 res = FN(PW,add_piece)(res, common, sum);
730 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
733 for (j = 0; j < pw2->n; ++j) {
734 set = isl_set_copy(pw2->p[j].set);
735 for (i = 0; i < pw1->n; ++i)
736 set = isl_set_subtract(set,
737 isl_set_copy(pw1->p[i].set));
738 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
741 FN(PW,free)(pw1);
742 FN(PW,free)(pw2);
744 return res;
745 error:
746 FN(PW,free)(pw1);
747 FN(PW,free)(pw2);
748 return NULL;
751 #if !DEFAULT_IS_ZERO
753 /* Compute the sum of "pw1" and "pw2 on the union of their domains,
754 * with the actual sum on the shared domain and
755 * the defined expression on the symmetric difference of the domains.
757 * This function is only defined for object types that do not have
758 * a default zero value. For other object types, this function
759 * is simply called "add".
761 __isl_give PW *FN(PW,union_add)(__isl_take PW *pw1, __isl_take PW *pw2)
763 return FN(PW,union_add_)(pw1, pw2);
766 #endif
768 /* This function is currently only used from isl_aff.c
770 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
771 __isl_take PW *pw2, __isl_take isl_space *space,
772 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
773 __attribute__ ((unused));
775 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
776 * The result of "fn" (and therefore also of this function) lives in "space".
778 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
779 __isl_take PW *pw2, __isl_take isl_space *space,
780 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
782 int i, j, n;
783 PW *res = NULL;
785 if (!pw1 || !pw2)
786 goto error;
788 n = pw1->n * pw2->n;
789 res = FN(PW,alloc_size)(isl_space_copy(space) OPT_TYPE_ARG(pw1->), n);
791 for (i = 0; i < pw1->n; ++i) {
792 for (j = 0; j < pw2->n; ++j) {
793 isl_set *common;
794 EL *res_ij;
795 int empty;
797 common = isl_set_intersect(
798 isl_set_copy(pw1->p[i].set),
799 isl_set_copy(pw2->p[j].set));
800 empty = isl_set_plain_is_empty(common);
801 if (empty < 0 || empty) {
802 isl_set_free(common);
803 if (empty < 0)
804 goto error;
805 continue;
808 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD),
809 FN(EL,copy)(pw2->p[j].FIELD));
810 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common));
812 res = FN(PW,add_piece)(res, common, res_ij);
816 isl_space_free(space);
817 FN(PW,free)(pw1);
818 FN(PW,free)(pw2);
819 return res;
820 error:
821 isl_space_free(space);
822 FN(PW,free)(pw1);
823 FN(PW,free)(pw2);
824 FN(PW,free)(res);
825 return NULL;
828 /* This function is currently only used from isl_aff.c
830 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
831 __isl_take PW *pw2,
832 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
833 __attribute__ ((unused));
835 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
836 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
838 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
839 __isl_take PW *pw2,
840 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
842 isl_space *space;
844 if (FN(PW,check_equal_space)(pw1, pw2) < 0)
845 goto error;
847 space = isl_space_copy(pw1->dim);
848 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);
849 error:
850 FN(PW,free)(pw1);
851 FN(PW,free)(pw2);
852 return NULL;
855 /* Return the parameter domain of "pw".
857 __isl_give isl_set *FN(PW,params)(__isl_take PW *pw)
859 return isl_set_params(FN(PW,domain)(pw));
862 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
864 int i;
865 isl_set *dom;
867 if (!pw)
868 return NULL;
870 dom = isl_set_empty(FN(PW,get_domain_space)(pw));
871 for (i = 0; i < pw->n; ++i)
872 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
874 FN(PW,free)(pw);
876 return dom;
879 /* Exploit the equalities in the domain of piece "i" of "pw"
880 * to simplify the associated function.
881 * If the domain of piece "i" is empty, then remove it entirely,
882 * replacing it with the final piece.
884 static __isl_give PW *FN(PW,exploit_equalities_and_remove_if_empty)(
885 __isl_take PW *pw, int i)
887 EL *el;
888 isl_set *domain;
889 isl_basic_set *aff;
890 int empty;
892 domain = FN(PW,peek_domain_at)(pw, i);
893 empty = isl_set_plain_is_empty(domain);
894 if (empty < 0)
895 return FN(PW,free)(pw);
896 if (empty) {
897 isl_set_free(pw->p[i].set);
898 FN(EL,free)(pw->p[i].FIELD);
899 if (i != pw->n - 1)
900 pw->p[i] = pw->p[pw->n - 1];
901 pw->n--;
903 return pw;
906 aff = isl_set_affine_hull(FN(PW,get_domain_at)(pw, i));
907 el = FN(PW,take_base_at)(pw, i);
908 el = FN(EL,substitute_equalities)(el, aff);
909 pw = FN(PW,restore_base_at_inplace)(pw, i, el);
911 return pw;
914 /* Restrict the domain of "pw" by combining each cell
915 * with "set" through a call to "fn", where "fn" may be
916 * isl_set_intersect, isl_set_intersect_params, isl_set_intersect_factor_domain,
917 * isl_set_intersect_factor_range or isl_set_subtract.
919 static __isl_give PW *FN(PW,restrict_domain)(__isl_take PW *pw,
920 __isl_take isl_set *set,
921 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,
922 __isl_take isl_set *set2))
924 int i;
925 isl_size n;
927 FN(PW,align_params_set)(&pw, &set);
928 n = FN(PW,n_piece)(pw);
929 if (n < 0 || !set)
930 goto error;
932 for (i = n - 1; i >= 0; --i) {
933 isl_set *domain;
935 domain = FN(PW,take_domain_at)(pw, i);
936 domain = fn(domain, isl_set_copy(set));
937 pw = FN(PW,restore_domain_at)(pw, i, domain);
938 pw = FN(PW,exploit_equalities_and_remove_if_empty)(pw, i);
941 isl_set_free(set);
942 return pw;
943 error:
944 isl_set_free(set);
945 FN(PW,free)(pw);
946 return NULL;
949 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
950 __isl_take isl_set *context)
952 return FN(PW,restrict_domain)(pw, context, &isl_set_intersect);
955 /* Intersect the domain of "pw" with the parameter domain "context".
957 __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,
958 __isl_take isl_set *context)
960 return FN(PW,restrict_domain)(pw, context, &isl_set_intersect_params);
963 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
964 * a set in the space A, intersect the domain with the set.
966 __isl_give PW *FN(PW,intersect_domain_wrapped_domain)(__isl_take PW *pw,
967 __isl_take isl_set *set)
969 return FN(PW,restrict_domain)(pw, set,
970 &isl_set_intersect_factor_domain);
973 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
974 * a set in the space B, intersect the domain with the set.
976 __isl_give PW *FN(PW,intersect_domain_wrapped_range)(__isl_take PW *pw,
977 __isl_take isl_set *set)
979 return FN(PW,restrict_domain)(pw, set, &isl_set_intersect_factor_range);
982 /* Subtract "domain' from the domain of "pw".
984 __isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw,
985 __isl_take isl_set *domain)
987 return FN(PW,restrict_domain)(pw, domain, &isl_set_subtract);
990 /* Return -1 if the piece "p1" should be sorted before "p2"
991 * and 1 if it should be sorted after "p2".
992 * Return 0 if they do not need to be sorted in a specific order.
994 * The two pieces are compared on the basis of their function value expressions.
996 static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg)
998 struct FN(PW,piece) const *pc1 = p1;
999 struct FN(PW,piece) const *pc2 = p2;
1001 return FN(EL,plain_cmp)(pc1->FIELD, pc2->FIELD);
1004 /* Sort the pieces of "pw" according to their function value
1005 * expressions and then combine pairs of adjacent pieces with
1006 * the same such expression.
1008 * The sorting is performed in place because it does not
1009 * change the meaning of "pw", but care needs to be
1010 * taken not to change any possible other copies of "pw"
1011 * in case anything goes wrong.
1013 static __isl_give PW *FN(PW,sort_unique)(__isl_take PW *pw)
1015 int i, j;
1016 isl_set *set;
1018 if (!pw)
1019 return NULL;
1020 if (pw->n <= 1)
1021 return pw;
1022 if (isl_sort(pw->p, pw->n, sizeof(pw->p[0]),
1023 &FN(PW,sort_field_cmp), NULL) < 0)
1024 return FN(PW,free)(pw);
1025 for (i = pw->n - 1; i >= 1; --i) {
1026 isl_bool equal;
1027 EL *el, *el_prev;
1028 isl_set *set_prev;
1030 el = FN(PW,peek_base_at)(pw, i);
1031 el_prev = FN(PW,peek_base_at)(pw, i - 1);
1032 equal = FN(EL,plain_is_equal)(el, el_prev);
1033 if (equal < 0)
1034 return FN(PW,free)(pw);
1035 if (!equal)
1036 continue;
1037 set = FN(PW,get_domain_at)(pw, i);
1038 set_prev = FN(PW,get_domain_at)(pw, i - 1);
1039 set = isl_set_union(set_prev, set);
1040 if (!set)
1041 return FN(PW,free)(pw);
1042 isl_set_free(pw->p[i].set);
1043 FN(EL,free)(pw->p[i].FIELD);
1044 isl_set_free(pw->p[i - 1].set);
1045 pw->p[i - 1].set = set;
1046 for (j = i + 1; j < pw->n; ++j)
1047 pw->p[j - 1] = pw->p[j];
1048 pw->n--;
1051 return pw;
1054 /* Compute the gist of "pw" with respect to the domain constraints
1055 * of "context" for the case where the domain of the last element
1056 * of "pw" is equal to "context".
1057 * Compute the gist of this element, replace
1058 * its domain by the universe and drop all other elements
1059 * as their domains are necessarily disjoint from "context".
1061 static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw,
1062 __isl_take isl_set *context)
1064 int i;
1065 isl_space *space;
1066 EL *el;
1068 for (i = 0; i < pw->n - 1; ++i) {
1069 isl_set_free(pw->p[i].set);
1070 FN(EL,free)(pw->p[i].FIELD);
1072 pw->p[0].FIELD = pw->p[pw->n - 1].FIELD;
1073 pw->p[0].set = pw->p[pw->n - 1].set;
1074 pw->n = 1;
1076 space = isl_set_get_space(context);
1077 el = FN(PW,take_base_at)(pw, 0);
1078 el = FN(EL,gist)(el, context);
1079 pw = FN(PW,restore_base_at)(pw, 0, el);
1080 context = isl_set_universe(space);
1081 pw = FN(PW,restore_domain_at)(pw, 0, context);
1083 return pw;
1086 /* Compute the gist of "pw" with respect to the domain constraints
1087 * of "context".
1088 * Call "fn_dom" to compute the gist of the domains and
1089 * "intersect_context" to intersect the domain with the context.
1091 * If the piecewise expression is empty or the context is the universe,
1092 * then nothing can be simplified.
1093 * If "pw" has a single domain and it is equal to "context",
1094 * then simply replace the domain by the universe.
1095 * Combine duplicate function value expressions first
1096 * to increase the chance of "pw" having a single domain.
1098 static __isl_give PW *FN(PW,gist_fn)(__isl_take PW *pw,
1099 __isl_take isl_set *context,
1100 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
1101 __isl_take isl_set *context),
1102 __isl_give isl_set *intersect_context(__isl_take isl_set *set,
1103 __isl_take isl_set *context))
1105 int i;
1106 int is_universe;
1108 pw = FN(PW,sort_unique)(pw);
1109 if (!pw || !context)
1110 goto error;
1112 if (pw->n == 0) {
1113 isl_set_free(context);
1114 return pw;
1117 is_universe = isl_set_plain_is_universe(context);
1118 if (is_universe < 0)
1119 goto error;
1120 if (is_universe) {
1121 isl_set_free(context);
1122 return pw;
1125 FN(PW,align_params_set)(&pw, &context);
1127 pw = FN(PW,cow)(pw);
1128 if (!pw)
1129 goto error;
1131 if (pw->n == 1) {
1132 int equal;
1134 equal = isl_set_plain_is_equal(pw->p[0].set, context);
1135 if (equal < 0)
1136 goto error;
1137 if (equal)
1138 return FN(PW,gist_last)(pw, context);
1141 context = isl_set_compute_divs(context);
1143 for (i = pw->n - 1; i >= 0; --i) {
1144 isl_set *set_i;
1145 EL *el;
1146 int empty;
1148 if (i == pw->n - 1) {
1149 int equal;
1150 equal = isl_set_plain_is_equal(pw->p[i].set, context);
1151 if (equal < 0)
1152 goto error;
1153 if (equal)
1154 return FN(PW,gist_last)(pw, context);
1156 set_i = FN(PW,get_domain_at)(pw, i);
1157 set_i = intersect_context(set_i, isl_set_copy(context));
1158 empty = isl_set_plain_is_empty(set_i);
1159 el = FN(PW,take_base_at)(pw, i);
1160 el = FN(EL,gist)(el, set_i);
1161 pw = FN(PW,restore_base_at)(pw, i, el);
1162 set_i = FN(PW,take_domain_at)(pw, i);
1163 set_i = fn_dom(set_i, isl_set_copy(context));
1164 pw = FN(PW,restore_domain_at)(pw, i, set_i);
1165 if (empty < 0 || !pw)
1166 goto error;
1167 if (empty) {
1168 isl_set_free(pw->p[i].set);
1169 FN(EL,free)(pw->p[i].FIELD);
1170 if (i != pw->n - 1)
1171 pw->p[i] = pw->p[pw->n - 1];
1172 pw->n--;
1176 isl_set_free(context);
1178 return pw;
1179 error:
1180 FN(PW,free)(pw);
1181 isl_set_free(context);
1182 return NULL;
1185 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
1187 return FN(PW,gist_fn)(pw, context, &isl_set_gist,
1188 &isl_set_intersect);
1191 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
1192 __isl_take isl_set *context)
1194 return FN(PW,gist_fn)(pw, context, &isl_set_gist_params,
1195 &isl_set_intersect_params);
1198 /* Coalesce the domains of "pw".
1200 * Prior to the actual coalescing, first sort the pieces such that
1201 * pieces with the same function value expression are combined
1202 * into a single piece, the combined domain of which can then
1203 * be coalesced.
1205 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
1207 int i;
1208 isl_size n;
1210 pw = FN(PW,sort_unique)(pw);
1211 n = FN(PW,n_piece)(pw);
1212 if (n < 0)
1213 return FN(PW,free)(pw);
1215 for (i = 0; i < n; ++i) {
1216 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
1217 if (!pw->p[i].set)
1218 goto error;
1221 return pw;
1222 error:
1223 FN(PW,free)(pw);
1224 return NULL;
1227 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
1229 return pw ? isl_space_get_ctx(pw->dim) : NULL;
1232 isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
1233 unsigned first, unsigned n)
1235 int i;
1236 enum isl_dim_type set_type;
1238 if (!pw)
1239 return isl_bool_error;
1240 if (pw->n == 0 || n == 0)
1241 return isl_bool_false;
1243 set_type = type == isl_dim_in ? isl_dim_set : type;
1245 for (i = 0; i < pw->n; ++i) {
1246 isl_bool involves = FN(EL,involves_dims)(pw->p[i].FIELD,
1247 type, first, n);
1248 if (involves < 0 || involves)
1249 return involves;
1250 involves = isl_set_involves_dims(pw->p[i].set,
1251 set_type, first, n);
1252 if (involves < 0 || involves)
1253 return involves;
1255 return isl_bool_false;
1258 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
1259 enum isl_dim_type type, unsigned pos, const char *s)
1261 isl_space *space;
1263 space = FN(PW,get_space)(pw);
1264 space = isl_space_set_dim_name(space, type, pos, s);
1265 return FN(PW,reset_space)(pw, space);
1268 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
1269 enum isl_dim_type type, unsigned first, unsigned n)
1271 int i;
1272 isl_size n_piece;
1273 enum isl_dim_type set_type;
1274 isl_space *space;
1276 n_piece = FN(PW,n_piece)(pw);
1277 if (n_piece < 0)
1278 return FN(PW,free)(pw);
1279 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1280 return pw;
1282 set_type = type == isl_dim_in ? isl_dim_set : type;
1284 space = FN(PW,take_space)(pw);
1285 space = isl_space_drop_dims(space, type, first, n);
1286 pw = FN(PW,restore_space)(pw, space);
1287 for (i = 0; i < n_piece; ++i) {
1288 isl_set *domain;
1289 EL *el;
1291 el = FN(PW,take_base_at)(pw, i);
1292 el = FN(EL,drop_dims)(el, type, first, n);
1293 pw = FN(PW,restore_base_at)(pw, i, el);
1294 if (type == isl_dim_out)
1295 continue;
1296 domain = FN(PW,take_domain_at)(pw, i);
1297 domain = isl_set_drop(domain, set_type, first, n);
1298 pw = FN(PW,restore_domain_at)(pw, i, domain);
1301 return pw;
1304 /* This function is very similar to drop_dims.
1305 * The only difference is that the cells may still involve
1306 * the specified dimensions. They are removed using
1307 * isl_set_project_out instead of isl_set_drop.
1309 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1310 enum isl_dim_type type, unsigned first, unsigned n)
1312 int i;
1313 isl_size n_piece;
1314 enum isl_dim_type set_type;
1315 isl_space *space;
1317 n_piece = FN(PW,n_piece)(pw);
1318 if (n_piece < 0)
1319 return FN(PW,free)(pw);
1320 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1321 return pw;
1323 set_type = type == isl_dim_in ? isl_dim_set : type;
1325 space = FN(PW,take_space)(pw);
1326 space = isl_space_drop_dims(space, type, first, n);
1327 pw = FN(PW,restore_space)(pw, space);
1328 for (i = 0; i < n_piece; ++i) {
1329 isl_set *domain;
1330 EL *el;
1332 domain = FN(PW,take_domain_at)(pw, i);
1333 domain = isl_set_project_out(domain, set_type, first, n);
1334 pw = FN(PW,restore_domain_at)(pw, i, domain);
1335 el = FN(PW,take_base_at)(pw, i);
1336 el = FN(EL,drop_dims)(el, type, first, n);
1337 pw = FN(PW,restore_base_at)(pw, i, el);
1340 return pw;
1343 /* Project the domain of pw onto its parameter space.
1345 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1347 isl_space *space;
1348 isl_size n;
1350 n = FN(PW,dim)(pw, isl_dim_in);
1351 if (n < 0)
1352 return FN(PW,free)(pw);
1353 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1354 space = FN(PW,get_domain_space)(pw);
1355 space = isl_space_params(space);
1356 pw = FN(PW,reset_domain_space)(pw, space);
1357 return pw;
1360 #undef TYPE
1361 #define TYPE PW
1362 #include "isl_drop_unused_params_templ.c"
1364 isl_size FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1366 return isl_space_dim(FN(PW,peek_space)(pw), type);
1369 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1371 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1374 /* Return the position of the dimension of the given type and name
1375 * in "pw".
1376 * Return -1 if no such dimension can be found.
1378 int FN(PW,find_dim_by_name)(__isl_keep PW *pw,
1379 enum isl_dim_type type, const char *name)
1381 if (!pw)
1382 return -1;
1383 return isl_space_find_dim_by_name(pw->dim, type, name);
1386 /* Return the position of the dimension of the given type and identifier
1387 * in "pw".
1388 * Return -1 if no such dimension can be found.
1390 static int FN(PW,find_dim_by_id)(__isl_keep PW *pw,
1391 enum isl_dim_type type, __isl_keep isl_id *id)
1393 isl_space *space;
1395 space = FN(PW,peek_space)(pw);
1396 return isl_space_find_dim_by_id(space, type, id);
1399 /* Does the piecewise expression "pw" depend in any way
1400 * on the parameter with identifier "id"?
1402 isl_bool FN(PW,involves_param_id)(__isl_keep PW *pw, __isl_keep isl_id *id)
1404 int pos;
1406 if (!pw || !id)
1407 return isl_bool_error;
1408 if (pw->n == 0)
1409 return isl_bool_false;
1411 pos = FN(PW,find_dim_by_id)(pw, isl_dim_param, id);
1412 if (pos < 0)
1413 return isl_bool_false;
1414 return FN(PW,involves_dims)(pw, isl_dim_param, pos, 1);
1417 /* Reset the space of "pw". Since we don't know if the elements
1418 * represent the spaces themselves or their domains, we pass along
1419 * both when we call their reset_space_and_domain.
1421 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1422 __isl_take isl_space *space, __isl_take isl_space *domain)
1424 int i;
1425 isl_size n;
1427 n = FN(PW,n_piece)(pw);
1428 if (n < 0 || !space || !domain)
1429 goto error;
1431 for (i = 0; i < n; ++i) {
1432 isl_set *set;
1433 EL *el;
1435 set = FN(PW,take_domain_at)(pw, i);
1436 set = isl_set_reset_space(set, isl_space_copy(domain));
1437 pw = FN(PW,restore_domain_at)(pw, i, set);
1438 el = FN(PW,take_base_at)(pw, i);
1439 el = FN(EL,reset_space_and_domain)(el,
1440 isl_space_copy(space), isl_space_copy(domain));
1441 pw = FN(PW,restore_base_at)(pw, i, el);
1444 isl_space_free(domain);
1446 pw = FN(PW,restore_space)(pw, space);
1448 return pw;
1449 error:
1450 isl_space_free(domain);
1451 isl_space_free(space);
1452 FN(PW,free)(pw);
1453 return NULL;
1456 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1457 __isl_take isl_space *domain)
1459 isl_space *space;
1461 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1462 FN(PW,get_space)(pw));
1463 return FN(PW,reset_space_and_domain)(pw, space, domain);
1466 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw,
1467 __isl_take isl_space *space)
1469 isl_space *domain;
1471 domain = isl_space_domain(isl_space_copy(space));
1472 return FN(PW,reset_space_and_domain)(pw, space, domain);
1475 __isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,
1476 __isl_take isl_id *id)
1478 isl_space *space;
1480 pw = FN(PW,cow)(pw);
1481 if (!pw)
1482 goto error;
1484 space = FN(PW,get_space)(pw);
1485 space = isl_space_set_tuple_id(space, type, id);
1487 return FN(PW,reset_space)(pw, space);
1488 error:
1489 isl_id_free(id);
1490 return FN(PW,free)(pw);
1493 /* Drop the id on the specified tuple.
1495 __isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)
1497 isl_space *space;
1499 if (!pw)
1500 return NULL;
1501 if (!FN(PW,has_tuple_id)(pw, type))
1502 return pw;
1504 pw = FN(PW,cow)(pw);
1505 if (!pw)
1506 return NULL;
1508 space = FN(PW,get_space)(pw);
1509 space = isl_space_reset_tuple_id(space, type);
1511 return FN(PW,reset_space)(pw, space);
1514 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1515 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1517 isl_space *space;
1519 space = FN(PW,get_space)(pw);
1520 space = isl_space_set_dim_id(space, type, pos, id);
1521 return FN(PW,reset_space)(pw, space);
1524 /* Reset the user pointer on all identifiers of parameters and tuples
1525 * of the space of "pw".
1527 __isl_give PW *FN(PW,reset_user)(__isl_take PW *pw)
1529 isl_space *space;
1531 space = FN(PW,get_space)(pw);
1532 space = isl_space_reset_user(space);
1534 return FN(PW,reset_space)(pw, space);
1537 isl_size FN(PW,n_piece)(__isl_keep PW *pw)
1539 return pw ? pw->n : isl_size_error;
1542 isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw,
1543 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1544 void *user)
1546 int i;
1548 if (!pw)
1549 return isl_stat_error;
1551 for (i = 0; i < pw->n; ++i)
1552 if (fn(isl_set_copy(pw->p[i].set),
1553 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1554 return isl_stat_error;
1556 return isl_stat_ok;
1559 /* Does "test" succeed on every cell of "pw"?
1561 isl_bool FN(PW,every_piece)(__isl_keep PW *pw,
1562 isl_bool (*test)(__isl_keep isl_set *set,
1563 __isl_keep EL *el, void *user), void *user)
1565 int i;
1567 if (!pw)
1568 return isl_bool_error;
1570 for (i = 0; i < pw->n; ++i) {
1571 isl_bool r;
1573 r = test(pw->p[i].set, pw->p[i].FIELD, user);
1574 if (r < 0 || !r)
1575 return r;
1578 return isl_bool_true;
1581 /* Is "pw" defined over a single universe domain?
1583 * If the default value of this piecewise type is zero,
1584 * then a "pw" with a zero number of cells is also accepted
1585 * as it represents the default zero value.
1587 isl_bool FN(FN(PW,isa),BASE)(__isl_keep PW *pw)
1589 isl_size n;
1591 n = FN(PW,n_piece)(pw);
1592 if (n < 0)
1593 return isl_bool_error;
1594 if (DEFAULT_IS_ZERO && n == 0)
1595 return isl_bool_true;
1596 if (n != 1)
1597 return isl_bool_false;
1598 return isl_set_plain_is_universe(FN(PW,peek_domain_at)(pw, 0));
1601 /* Return a zero base expression in the same space (and of the same type)
1602 * as "pw".
1604 static __isl_give EL *FN(EL,zero_like_type)(__isl_take PW *pw OPT_TYPE_PARAM)
1606 isl_space *space;
1608 space = FN(PW,get_space)(pw);
1609 FN(PW,free)(pw);
1610 return FN(EL,zero_in_space)(space OPT_TYPE_ARG(NO_LOC));
1613 #ifndef HAS_TYPE
1614 /* Return a zero base expression in the same space as "pw".
1616 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1618 return FN(EL,zero_like_type)(pw);
1620 #else
1621 /* Return a zero base expression in the same space and of the same type
1622 * as "pw".
1624 * Pass along the type as an explicit argument for uniform handling
1625 * in isl_*_zero_like_type.
1627 static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)
1629 enum isl_fold type;
1631 type = FN(PW,get_type)(pw);
1632 if (type < 0)
1633 goto error;
1634 return FN(EL,zero_like_type)(pw, type);
1635 error:
1636 FN(PW,free)(pw);
1637 return NULL;
1639 #endif
1641 /* Given that "pw" is defined over a single universe domain,
1642 * return the base expression associated to this domain.
1644 * If the number of cells is zero, then "pw" is of a piecewise type
1645 * with a default zero value and effectively represents zero.
1646 * In this case, create a zero base expression in the same space
1647 * (and with the same type).
1648 * Otherwise, simply extract the associated base expression.
1650 __isl_give EL *FN(FN(PW,as),BASE)(__isl_take PW *pw)
1652 isl_bool is_total;
1653 isl_size n;
1654 EL *el;
1656 is_total = FN(FN(PW,isa),BASE)(pw);
1657 if (is_total < 0)
1658 goto error;
1659 if (!is_total)
1660 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,
1661 "expecting single total function", goto error);
1662 n = FN(PW,n_piece)(pw);
1663 if (n < 0)
1664 goto error;
1665 if (n == 0)
1666 return FN(EL,zero_like)(pw);
1667 el = FN(PW,take_base_at)(pw, 0);
1668 FN(PW,free)(pw);
1669 return el;
1670 error:
1671 FN(PW,free)(pw);
1672 return NULL;
1675 #ifdef HAS_TYPE
1676 /* Negate the type of "pw".
1678 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1680 pw = FN(PW,cow)(pw);
1681 if (!pw)
1682 return NULL;
1683 pw->type = isl_fold_type_negate(pw->type);
1684 return pw;
1686 #else
1687 /* Negate the type of "pw".
1688 * Since "pw" does not have a type, do nothing.
1690 static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)
1692 return pw;
1694 #endif
1696 /* Multiply the pieces of "pw" by "v" and return the result.
1698 __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)
1700 int i;
1701 isl_size n;
1703 if (!pw || !v)
1704 goto error;
1706 if (isl_val_is_one(v)) {
1707 isl_val_free(v);
1708 return pw;
1710 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {
1711 PW *zero;
1712 isl_space *space = FN(PW,get_space)(pw);
1713 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));
1714 FN(PW,free)(pw);
1715 isl_val_free(v);
1716 return zero;
1718 if (isl_val_is_neg(v))
1719 pw = FN(PW,negate_type)(pw);
1720 n = FN(PW,n_piece)(pw);
1721 if (n < 0)
1722 goto error;
1724 for (i = 0; i < n; ++i) {
1725 EL *el;
1727 el = FN(PW,take_base_at)(pw, i);
1728 el = FN(EL,scale_val)(el, isl_val_copy(v));
1729 pw = FN(PW,restore_base_at)(pw, i, el);
1732 isl_val_free(v);
1733 return pw;
1734 error:
1735 isl_val_free(v);
1736 FN(PW,free)(pw);
1737 return NULL;
1740 /* Divide the pieces of "pw" by "v" and return the result.
1742 __isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)
1744 int i;
1745 isl_size n;
1747 if (!pw || !v)
1748 goto error;
1750 if (isl_val_is_one(v)) {
1751 isl_val_free(v);
1752 return pw;
1755 if (!isl_val_is_rat(v))
1756 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1757 "expecting rational factor", goto error);
1758 if (isl_val_is_zero(v))
1759 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1760 "cannot scale down by zero", goto error);
1762 if (isl_val_is_neg(v))
1763 pw = FN(PW,negate_type)(pw);
1764 n = FN(PW,n_piece)(pw);
1765 if (n < 0)
1766 goto error;
1768 for (i = 0; i < n; ++i) {
1769 EL *el;
1771 el = FN(PW,take_base_at)(pw, i);
1772 el = FN(EL,scale_down_val)(el, isl_val_copy(v));
1773 pw = FN(PW,restore_base_at)(pw, i, el);
1776 isl_val_free(v);
1777 return pw;
1778 error:
1779 isl_val_free(v);
1780 FN(PW,free)(pw);
1781 return NULL;
1784 /* Apply some normalization to "pw".
1785 * In particular, sort the pieces according to their function value
1786 * expressions, combining pairs of adjacent pieces with
1787 * the same such expression, and then normalize the domains of the pieces.
1789 * We normalize in place, but if anything goes wrong we need
1790 * to return NULL, so we need to make sure we don't change the
1791 * meaning of any possible other copies of "pw".
1793 static __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1795 int i;
1796 isl_set *set;
1798 pw = FN(PW,sort_unique)(pw);
1799 if (!pw)
1800 return NULL;
1801 for (i = 0; i < pw->n; ++i) {
1802 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1803 if (!set)
1804 return FN(PW,free)(pw);
1805 isl_set_free(pw->p[i].set);
1806 pw->p[i].set = set;
1809 return pw;
1812 /* Is pw1 obviously equal to pw2?
1813 * That is, do they have obviously identical cells and obviously identical
1814 * elements on each cell?
1816 * If "pw1" or "pw2" contain any NaNs, then they are considered
1817 * not to be the same. A NaN is not equal to anything, not even
1818 * to another NaN.
1820 isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1822 int i;
1823 isl_bool equal, has_nan;
1825 if (!pw1 || !pw2)
1826 return isl_bool_error;
1828 has_nan = FN(PW,involves_nan)(pw1);
1829 if (has_nan >= 0 && !has_nan)
1830 has_nan = FN(PW,involves_nan)(pw2);
1831 if (has_nan < 0 || has_nan)
1832 return isl_bool_not(has_nan);
1834 if (pw1 == pw2)
1835 return isl_bool_true;
1836 equal = FN(PW,has_equal_space)(pw1, pw2);
1837 if (equal < 0 || !equal)
1838 return equal;
1840 pw1 = FN(PW,copy)(pw1);
1841 pw2 = FN(PW,copy)(pw2);
1842 pw1 = FN(PW,normalize)(pw1);
1843 pw2 = FN(PW,normalize)(pw2);
1844 if (!pw1 || !pw2)
1845 goto error;
1847 equal = isl_bool_ok(pw1->n == pw2->n);
1848 for (i = 0; equal && i < pw1->n; ++i) {
1849 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
1850 if (equal < 0)
1851 goto error;
1852 if (!equal)
1853 break;
1854 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
1855 if (equal < 0)
1856 goto error;
1859 FN(PW,free)(pw1);
1860 FN(PW,free)(pw2);
1861 return equal;
1862 error:
1863 FN(PW,free)(pw1);
1864 FN(PW,free)(pw2);
1865 return isl_bool_error;
1868 /* Does "pw" involve any NaNs?
1870 isl_bool FN(PW,involves_nan)(__isl_keep PW *pw)
1872 int i;
1874 if (!pw)
1875 return isl_bool_error;
1876 if (pw->n == 0)
1877 return isl_bool_false;
1879 for (i = 0; i < pw->n; ++i) {
1880 isl_bool has_nan = FN(EL,involves_nan)(pw->p[i].FIELD);
1881 if (has_nan < 0 || has_nan)
1882 return has_nan;
1885 return isl_bool_false;