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,
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
17 #include <isl_val_private.h>
19 #include <isl_pw_macro.h>
23 __isl_give PW
*FN(PW
,alloc_size
)(__isl_take isl_space
*space
24 OPT_TYPE_PARAM
, int n
)
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
)));
39 OPT_SET_TYPE(pw
->, type
);
45 isl_space_free(space
);
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
)
64 isl_space
*el_dim
= NULL
;
66 if (!pw
|| !set
|| !el
)
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",
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
;
81 isl_space_free(el_dim
);
84 isl_space_free(el_dim
);
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
)
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
);
110 return FN(PW
,free
)(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
)
120 isl_space
*el_space
, *set_space
;
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
);
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
)
139 ok
= FN(PW
,compatible_domain
)(el
, set
);
141 return isl_stat_error
;
143 isl_die(isl_set_get_ctx(set
), isl_error_invalid
,
144 "incompatible spaces", return isl_stat_error
);
149 __isl_give PW
*FN(PW
,alloc
)(OPT_TYPE_PARAM_FIRST
150 __isl_take isl_set
*set
, __isl_take EL
*el
)
154 if (FN(PW
,check_compatible_domain
)(el
, set
) < 0)
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
);
166 __isl_give PW
*FN(PW
,dup
)(__isl_keep PW
*pw
)
174 dup
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
)
175 OPT_TYPE_ARG(pw
->), pw
->n
);
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
));
186 __isl_give PW
*FN(PW
,cow
)(__isl_take PW
*pw
)
194 return FN(PW
,dup
)(pw
);
197 __isl_give PW
*FN(PW
,copy
)(__isl_keep PW
*pw
)
206 __isl_null PW
*FN(PW
,free
)(__isl_take PW
*pw
)
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
);
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
)
253 return FN(PW
,get_space
)(pw
);
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
)
270 if (pw
->dim
== space
) {
271 isl_space_free(space
);
278 isl_space_free(pw
->dim
);
284 isl_space_free(space
);
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
)
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
);
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)
306 return pw
->p
[pos
].set
;
309 /* Return a copy of the cell at position "pos" in "pw".
311 __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
)
333 return FN(PW
,get_domain_at
)(pw
, pos
);
334 if (FN(PW
,check_pos
)(pw
, pos
) < 0)
336 domain
= pw
->p
[pos
].set
;
337 pw
->p
[pos
].set
= NULL
;
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
)
353 if (pw
->p
[pos
].set
== domain
) {
354 isl_set_free(domain
);
361 isl_set_free(pw
->p
[pos
].set
);
362 pw
->p
[pos
].set
= domain
;
367 isl_set_free(domain
);
371 /* Return the base expression associated to
372 * the cell at position "pos" in "pw".
374 static __isl_keep EL
*FN(PW
,peek_base_at
)(__isl_keep PW
*pw
, int pos
)
376 if (FN(PW
,check_pos
)(pw
, pos
) < 0)
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 __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 __isl_give EL
*FN(PW
,take_base_at
)(__isl_keep PW
*pw
, int pos
)
407 return FN(PW
,get_base_at
)(pw
, pos
);
408 if (FN(PW
,check_pos
)(pw
, pos
) < 0)
410 el
= pw
->p
[pos
].FIELD
;
411 pw
->p
[pos
].FIELD
= NULL
;
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
)
431 if (pw
->p
[pos
].FIELD
== el
) {
440 FN(EL
,free
)(pw
->p
[pos
].FIELD
);
441 pw
->p
[pos
].FIELD
= el
;
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 __isl_give PW
*FN(PW
,restore_base_at
)(__isl_take PW
*pw
, int pos
,
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
,
471 return FN(PW
,restore_base_at_
)(pw
, pos
, el
, 1);
474 /* Create a piecewise expression with the given base expression on a universe
477 static __isl_give PW
*FN(FN(FN(PW
,from
),BASE
),type_base
)(__isl_take EL
*el
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
487 * If the default value of this piecewise type is zero and
488 * if "el" is effectively zero, then create an empty piecewise expression
491 static __isl_give PW
*FN(FN(FN(PW
,from
),BASE
),type
)(__isl_take EL
*el
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
);
504 return FN(FN(FN(PW
,from
),BASE
),type_base
)(el
505 OPT_TYPE_ARG(NO_LOC
));
506 space
= FN(EL
,get_space
)(el
);
508 return FN(PW
,ZERO
)(space
OPT_TYPE_ARG(NO_LOC
));
515 /* Create a piecewise expression with the given base expression on a universe
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
);
527 __isl_give PW
*FN(FN(PW
,from
),BASE
)(__isl_take EL
*el
)
529 return FN(FN(FN(PW
,from
),BASE
),type
)(el
);
533 const char *FN(PW
,get_dim_name
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
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
,
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
,
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
)
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
)
585 n
= FN(PW
,n_piece
)(pw
);
589 for (i
= 0; i
< n
; ++i
) {
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
);
607 isl_reordering_free(exp
);
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
)
622 isl_bool equal_params
;
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)
633 equal_params
= isl_space_has_equal_params(pw
->dim
, model
);
634 if (equal_params
< 0)
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
);
649 isl_space_free(model
);
658 #include "isl_align_params_bin_templ.c"
668 #include "isl_align_params_templ.c"
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
)
686 if (FN(PW
,align_params_bin
)(&pw1
, &pw2
) < 0)
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)
696 if (FN(PW
,IS_ZERO
)(pw1
)) {
701 if (FN(PW
,IS_ZERO
)(pw2
)) {
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
;
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
);
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
));
751 /* Make sure "pw" has room for at least "n" more pieces.
753 * If there is only one reference to pw, we extend it in place.
754 * Otherwise, we create a new PW and copy the pieces.
756 static __isl_give PW
*FN(PW
,grow
)(__isl_take PW
*pw
, int n
)
764 if (pw
->n
+ n
<= pw
->size
)
766 ctx
= FN(PW
,get_ctx
)(pw
);
769 res
= isl_realloc(ctx
, pw
, struct PW
,
770 sizeof(struct PW
) + (n
- 1) * sizeof(S(PW
,piece
)));
772 return FN(PW
,free
)(pw
);
776 res
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
) OPT_TYPE_ARG(pw
->), n
);
778 return FN(PW
,free
)(pw
);
779 for (i
= 0; i
< pw
->n
; ++i
)
780 res
= FN(PW
,add_piece
)(res
, isl_set_copy(pw
->p
[i
].set
),
781 FN(EL
,copy
)(pw
->p
[i
].FIELD
));
786 __isl_give PW
*FN(PW
,add_disjoint
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
)
791 if (FN(PW
,align_params_bin
)(&pw1
, &pw2
) < 0)
794 if (pw1
->size
< pw1
->n
+ pw2
->n
&& pw1
->n
< pw2
->n
)
795 return FN(PW
,add_disjoint
)(pw2
, pw1
);
797 ctx
= isl_space_get_ctx(pw1
->dim
);
798 if (!OPT_EQUAL_TYPES(pw1
->, pw2
->))
799 isl_die(ctx
, isl_error_invalid
,
800 "fold types don't match", goto error
);
801 if (FN(PW
,check_equal_space
)(pw1
, pw2
) < 0)
804 if (FN(PW
,IS_ZERO
)(pw1
)) {
809 if (FN(PW
,IS_ZERO
)(pw2
)) {
814 pw1
= FN(PW
,grow
)(pw1
, pw2
->n
);
818 for (i
= 0; i
< pw2
->n
; ++i
)
819 pw1
= FN(PW
,add_piece
)(pw1
,
820 isl_set_copy(pw2
->p
[i
].set
),
821 FN(EL
,copy
)(pw2
->p
[i
].FIELD
));
832 /* This function is currently only used from isl_aff.c
834 static __isl_give PW
*FN(PW
,on_shared_domain_in
)(__isl_take PW
*pw1
,
835 __isl_take PW
*pw2
, __isl_take isl_space
*space
,
836 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
837 __attribute__ ((unused
));
839 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
840 * The result of "fn" (and therefore also of this function) lives in "space".
842 static __isl_give PW
*FN(PW
,on_shared_domain_in
)(__isl_take PW
*pw1
,
843 __isl_take PW
*pw2
, __isl_take isl_space
*space
,
844 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
853 res
= FN(PW
,alloc_size
)(isl_space_copy(space
) OPT_TYPE_ARG(pw1
->), n
);
855 for (i
= 0; i
< pw1
->n
; ++i
) {
856 for (j
= 0; j
< pw2
->n
; ++j
) {
861 common
= isl_set_intersect(
862 isl_set_copy(pw1
->p
[i
].set
),
863 isl_set_copy(pw2
->p
[j
].set
));
864 empty
= isl_set_plain_is_empty(common
);
865 if (empty
< 0 || empty
) {
866 isl_set_free(common
);
872 res_ij
= fn(FN(EL
,copy
)(pw1
->p
[i
].FIELD
),
873 FN(EL
,copy
)(pw2
->p
[j
].FIELD
));
874 res_ij
= FN(EL
,gist
)(res_ij
, isl_set_copy(common
));
876 res
= FN(PW
,add_piece
)(res
, common
, res_ij
);
880 isl_space_free(space
);
885 isl_space_free(space
);
892 /* This function is currently only used from isl_aff.c
894 static __isl_give PW
*FN(PW
,on_shared_domain
)(__isl_take PW
*pw1
,
896 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
897 __attribute__ ((unused
));
899 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
900 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
902 static __isl_give PW
*FN(PW
,on_shared_domain
)(__isl_take PW
*pw1
,
904 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
908 if (FN(PW
,check_equal_space
)(pw1
, pw2
) < 0)
911 space
= isl_space_copy(pw1
->dim
);
912 return FN(PW
,on_shared_domain_in
)(pw1
, pw2
, space
, fn
);
919 /* Return the parameter domain of "pw".
921 __isl_give isl_set
*FN(PW
,params
)(__isl_take PW
*pw
)
923 return isl_set_params(FN(PW
,domain
)(pw
));
926 __isl_give isl_set
*FN(PW
,domain
)(__isl_take PW
*pw
)
934 dom
= isl_set_empty(FN(PW
,get_domain_space
)(pw
));
935 for (i
= 0; i
< pw
->n
; ++i
)
936 dom
= isl_set_union_disjoint(dom
, isl_set_copy(pw
->p
[i
].set
));
943 /* Exploit the equalities in the domain of piece "i" of "pw"
944 * to simplify the associated function.
945 * If the domain of piece "i" is empty, then remove it entirely,
946 * replacing it with the final piece.
948 static __isl_give PW
*FN(PW
,exploit_equalities_and_remove_if_empty
)(
949 __isl_take PW
*pw
, int i
)
956 domain
= FN(PW
,peek_domain_at
)(pw
, i
);
957 empty
= isl_set_plain_is_empty(domain
);
959 return FN(PW
,free
)(pw
);
961 isl_set_free(pw
->p
[i
].set
);
962 FN(EL
,free
)(pw
->p
[i
].FIELD
);
964 pw
->p
[i
] = pw
->p
[pw
->n
- 1];
970 aff
= isl_set_affine_hull(FN(PW
,get_domain_at
)(pw
, i
));
971 el
= FN(PW
,take_base_at
)(pw
, i
);
972 el
= FN(EL
,substitute_equalities
)(el
, aff
);
973 pw
= FN(PW
,restore_base_at_inplace
)(pw
, i
, el
);
978 /* Convert a piecewise expression defined over a parameter domain
979 * into one that is defined over a zero-dimensional set.
981 __isl_give PW
*FN(PW
,from_range
)(__isl_take PW
*pw
)
987 if (!isl_space_is_set(pw
->dim
))
988 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
989 "not living in a set space", return FN(PW
,free
)(pw
));
991 space
= FN(PW
,get_space
)(pw
);
992 space
= isl_space_from_range(space
);
993 pw
= FN(PW
,reset_space
)(pw
, space
);
998 /* Fix the value of the given parameter or domain dimension of "pw"
999 * to be equal to "value".
1001 __isl_give PW
*FN(PW
,fix_si
)(__isl_take PW
*pw
, enum isl_dim_type type
,
1002 unsigned pos
, int value
)
1007 n
= FN(PW
,n_piece
)(pw
);
1009 return FN(PW
,free
)(pw
);
1011 if (type
== isl_dim_out
)
1012 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
1013 "cannot fix output dimension", return FN(PW
,free
)(pw
));
1015 if (type
== isl_dim_in
)
1018 for (i
= n
- 1; i
>= 0; --i
) {
1021 domain
= FN(PW
,take_domain_at
)(pw
, i
);
1022 domain
= isl_set_fix_si(domain
, type
, pos
, value
);
1023 pw
= FN(PW
,restore_domain_at
)(pw
, i
, domain
);
1024 pw
= FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
);
1030 /* Restrict the domain of "pw" by combining each cell
1031 * with "set" through a call to "fn", where "fn" may be
1032 * isl_set_intersect, isl_set_intersect_params, isl_set_intersect_factor_domain,
1033 * isl_set_intersect_factor_range or isl_set_subtract.
1035 static __isl_give PW
*FN(PW
,restrict_domain
)(__isl_take PW
*pw
,
1036 __isl_take isl_set
*set
,
1037 __isl_give isl_set
*(*fn
)(__isl_take isl_set
*set1
,
1038 __isl_take isl_set
*set2
))
1043 FN(PW
,align_params_set
)(&pw
, &set
);
1044 n
= FN(PW
,n_piece
)(pw
);
1048 for (i
= n
- 1; i
>= 0; --i
) {
1051 domain
= FN(PW
,take_domain_at
)(pw
, i
);
1052 domain
= fn(domain
, isl_set_copy(set
));
1053 pw
= FN(PW
,restore_domain_at
)(pw
, i
, domain
);
1054 pw
= FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
);
1065 __isl_give PW
*FN(PW
,intersect_domain
)(__isl_take PW
*pw
,
1066 __isl_take isl_set
*context
)
1068 return FN(PW
,restrict_domain
)(pw
, context
, &isl_set_intersect
);
1071 /* Intersect the domain of "pw" with the parameter domain "context".
1073 __isl_give PW
*FN(PW
,intersect_params
)(__isl_take PW
*pw
,
1074 __isl_take isl_set
*context
)
1076 return FN(PW
,restrict_domain
)(pw
, context
, &isl_set_intersect_params
);
1079 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
1080 * a set in the space A, intersect the domain with the set.
1082 __isl_give PW
*FN(PW
,intersect_domain_wrapped_domain
)(__isl_take PW
*pw
,
1083 __isl_take isl_set
*set
)
1085 return FN(PW
,restrict_domain
)(pw
, set
,
1086 &isl_set_intersect_factor_domain
);
1089 /* Given a piecewise expression "pw" with domain in a space [A -> B] and
1090 * a set in the space B, intersect the domain with the set.
1092 __isl_give PW
*FN(PW
,intersect_domain_wrapped_range
)(__isl_take PW
*pw
,
1093 __isl_take isl_set
*set
)
1095 return FN(PW
,restrict_domain
)(pw
, set
, &isl_set_intersect_factor_range
);
1098 /* Subtract "domain' from the domain of "pw".
1100 __isl_give PW
*FN(PW
,subtract_domain
)(__isl_take PW
*pw
,
1101 __isl_take isl_set
*domain
)
1103 return FN(PW
,restrict_domain
)(pw
, domain
, &isl_set_subtract
);
1106 /* Return -1 if the piece "p1" should be sorted before "p2"
1107 * and 1 if it should be sorted after "p2".
1108 * Return 0 if they do not need to be sorted in a specific order.
1110 * The two pieces are compared on the basis of their function value expressions.
1112 static int FN(PW
,sort_field_cmp
)(const void *p1
, const void *p2
, void *arg
)
1114 struct FN(PW
,piece
) const *pc1
= p1
;
1115 struct FN(PW
,piece
) const *pc2
= p2
;
1117 return FN(EL
,plain_cmp
)(pc1
->FIELD
, pc2
->FIELD
);
1120 /* Sort the pieces of "pw" according to their function value
1121 * expressions and then combine pairs of adjacent pieces with
1122 * the same such expression.
1124 * The sorting is performed in place because it does not
1125 * change the meaning of "pw", but care needs to be
1126 * taken not to change any possible other copies of "pw"
1127 * in case anything goes wrong.
1129 static __isl_give PW
*FN(PW
,sort_unique
)(__isl_take PW
*pw
)
1138 if (isl_sort(pw
->p
, pw
->n
, sizeof(pw
->p
[0]),
1139 &FN(PW
,sort_field_cmp
), NULL
) < 0)
1140 return FN(PW
,free
)(pw
);
1141 for (i
= pw
->n
- 1; i
>= 1; --i
) {
1146 el
= FN(PW
,peek_base_at
)(pw
, i
);
1147 el_prev
= FN(PW
,peek_base_at
)(pw
, i
- 1);
1148 equal
= FN(EL
,plain_is_equal
)(el
, el_prev
);
1150 return FN(PW
,free
)(pw
);
1153 set
= FN(PW
,get_domain_at
)(pw
, i
);
1154 set_prev
= FN(PW
,get_domain_at
)(pw
, i
- 1);
1155 set
= isl_set_union(set_prev
, set
);
1157 return FN(PW
,free
)(pw
);
1158 isl_set_free(pw
->p
[i
].set
);
1159 FN(EL
,free
)(pw
->p
[i
].FIELD
);
1160 isl_set_free(pw
->p
[i
- 1].set
);
1161 pw
->p
[i
- 1].set
= set
;
1162 for (j
= i
+ 1; j
< pw
->n
; ++j
)
1163 pw
->p
[j
- 1] = pw
->p
[j
];
1170 /* Compute the gist of "pw" with respect to the domain constraints
1171 * of "context" for the case where the domain of the last element
1172 * of "pw" is equal to "context".
1173 * Compute the gist of this element, replace
1174 * its domain by the universe and drop all other elements
1175 * as their domains are necessarily disjoint from "context".
1177 static __isl_give PW
*FN(PW
,gist_last
)(__isl_take PW
*pw
,
1178 __isl_take isl_set
*context
)
1184 for (i
= 0; i
< pw
->n
- 1; ++i
) {
1185 isl_set_free(pw
->p
[i
].set
);
1186 FN(EL
,free
)(pw
->p
[i
].FIELD
);
1188 pw
->p
[0].FIELD
= pw
->p
[pw
->n
- 1].FIELD
;
1189 pw
->p
[0].set
= pw
->p
[pw
->n
- 1].set
;
1192 space
= isl_set_get_space(context
);
1193 el
= FN(PW
,take_base_at
)(pw
, 0);
1194 el
= FN(EL
,gist
)(el
, context
);
1195 pw
= FN(PW
,restore_base_at
)(pw
, 0, el
);
1196 context
= isl_set_universe(space
);
1197 pw
= FN(PW
,restore_domain_at
)(pw
, 0, context
);
1202 /* Compute the gist of "pw" with respect to the domain constraints
1204 * Call "fn_dom" to compute the gist of the domains and
1205 * "intersect_context" to intersect the domain with the context.
1207 * If the piecewise expression is empty or the context is the universe,
1208 * then nothing can be simplified.
1209 * If "pw" has a single domain and it is equal to "context",
1210 * then simply replace the domain by the universe.
1211 * Combine duplicate function value expressions first
1212 * to increase the chance of "pw" having a single domain.
1214 static __isl_give PW
*FN(PW
,gist_fn
)(__isl_take PW
*pw
,
1215 __isl_take isl_set
*context
,
1216 __isl_give isl_set
*(*fn_dom
)(__isl_take isl_set
*set
,
1217 __isl_take isl_basic_set
*bset
),
1218 __isl_give isl_set
*intersect_context(__isl_take isl_set
*set
,
1219 __isl_take isl_set
*context
))
1223 isl_basic_set
*hull
= NULL
;
1225 pw
= FN(PW
,sort_unique
)(pw
);
1226 if (!pw
|| !context
)
1230 isl_set_free(context
);
1234 is_universe
= isl_set_plain_is_universe(context
);
1235 if (is_universe
< 0)
1238 isl_set_free(context
);
1242 FN(PW
,align_params_set
)(&pw
, &context
);
1244 pw
= FN(PW
,cow
)(pw
);
1251 equal
= isl_set_plain_is_equal(pw
->p
[0].set
, context
);
1255 return FN(PW
,gist_last
)(pw
, context
);
1258 context
= isl_set_compute_divs(context
);
1259 hull
= isl_set_simple_hull(isl_set_copy(context
));
1261 for (i
= pw
->n
- 1; i
>= 0; --i
) {
1266 if (i
== pw
->n
- 1) {
1268 equal
= isl_set_plain_is_equal(pw
->p
[i
].set
, context
);
1272 isl_basic_set_free(hull
);
1273 return FN(PW
,gist_last
)(pw
, context
);
1276 set_i
= FN(PW
,get_domain_at
)(pw
, i
);
1277 set_i
= intersect_context(set_i
, isl_set_copy(context
));
1278 empty
= isl_set_plain_is_empty(set_i
);
1279 el
= FN(PW
,take_base_at
)(pw
, i
);
1280 el
= FN(EL
,gist
)(el
, set_i
);
1281 pw
= FN(PW
,restore_base_at
)(pw
, i
, el
);
1282 set_i
= FN(PW
,take_domain_at
)(pw
, i
);
1283 set_i
= fn_dom(set_i
, isl_basic_set_copy(hull
));
1284 pw
= FN(PW
,restore_domain_at
)(pw
, i
, set_i
);
1285 if (empty
< 0 || !pw
)
1288 isl_set_free(pw
->p
[i
].set
);
1289 FN(EL
,free
)(pw
->p
[i
].FIELD
);
1291 pw
->p
[i
] = pw
->p
[pw
->n
- 1];
1296 isl_basic_set_free(hull
);
1297 isl_set_free(context
);
1302 isl_basic_set_free(hull
);
1303 isl_set_free(context
);
1307 __isl_give PW
*FN(PW
,gist
)(__isl_take PW
*pw
, __isl_take isl_set
*context
)
1309 return FN(PW
,gist_fn
)(pw
, context
, &isl_set_gist_basic_set
,
1310 &isl_set_intersect
);
1313 __isl_give PW
*FN(PW
,gist_params
)(__isl_take PW
*pw
,
1314 __isl_take isl_set
*context
)
1316 return FN(PW
,gist_fn
)(pw
, context
, &isl_set_gist_params_basic_set
,
1317 &isl_set_intersect_params
);
1320 /* Coalesce the domains of "pw".
1322 * Prior to the actual coalescing, first sort the pieces such that
1323 * pieces with the same function value expression are combined
1324 * into a single piece, the combined domain of which can then
1327 __isl_give PW
*FN(PW
,coalesce
)(__isl_take PW
*pw
)
1332 pw
= FN(PW
,sort_unique
)(pw
);
1333 n
= FN(PW
,n_piece
)(pw
);
1335 return FN(PW
,free
)(pw
);
1337 for (i
= 0; i
< n
; ++i
) {
1338 pw
->p
[i
].set
= isl_set_coalesce(pw
->p
[i
].set
);
1349 isl_ctx
*FN(PW
,get_ctx
)(__isl_keep PW
*pw
)
1351 return pw
? isl_space_get_ctx(pw
->dim
) : NULL
;
1354 isl_bool
FN(PW
,involves_dims
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
1355 unsigned first
, unsigned n
)
1358 enum isl_dim_type set_type
;
1361 return isl_bool_error
;
1362 if (pw
->n
== 0 || n
== 0)
1363 return isl_bool_false
;
1365 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1367 for (i
= 0; i
< pw
->n
; ++i
) {
1368 isl_bool involves
= FN(EL
,involves_dims
)(pw
->p
[i
].FIELD
,
1370 if (involves
< 0 || involves
)
1372 involves
= isl_set_involves_dims(pw
->p
[i
].set
,
1373 set_type
, first
, n
);
1374 if (involves
< 0 || involves
)
1377 return isl_bool_false
;
1380 __isl_give PW
*FN(PW
,set_dim_name
)(__isl_take PW
*pw
,
1381 enum isl_dim_type type
, unsigned pos
, const char *s
)
1385 space
= FN(PW
,get_space
)(pw
);
1386 space
= isl_space_set_dim_name(space
, type
, pos
, s
);
1387 return FN(PW
,reset_space
)(pw
, space
);
1390 __isl_give PW
*FN(PW
,drop_dims
)(__isl_take PW
*pw
,
1391 enum isl_dim_type type
, unsigned first
, unsigned n
)
1395 enum isl_dim_type set_type
;
1398 n_piece
= FN(PW
,n_piece
)(pw
);
1400 return FN(PW
,free
)(pw
);
1401 if (n
== 0 && !isl_space_get_tuple_name(pw
->dim
, type
))
1404 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1406 space
= FN(PW
,take_space
)(pw
);
1407 space
= isl_space_drop_dims(space
, type
, first
, n
);
1408 pw
= FN(PW
,restore_space
)(pw
, space
);
1409 for (i
= 0; i
< n_piece
; ++i
) {
1413 el
= FN(PW
,take_base_at
)(pw
, i
);
1414 el
= FN(EL
,drop_dims
)(el
, type
, first
, n
);
1415 pw
= FN(PW
,restore_base_at
)(pw
, i
, el
);
1416 if (type
== isl_dim_out
)
1418 domain
= FN(PW
,take_domain_at
)(pw
, i
);
1419 domain
= isl_set_drop(domain
, set_type
, first
, n
);
1420 pw
= FN(PW
,restore_domain_at
)(pw
, i
, domain
);
1426 /* This function is very similar to drop_dims.
1427 * The only difference is that the cells may still involve
1428 * the specified dimensions. They are removed using
1429 * isl_set_project_out instead of isl_set_drop.
1431 __isl_give PW
*FN(PW
,project_out
)(__isl_take PW
*pw
,
1432 enum isl_dim_type type
, unsigned first
, unsigned n
)
1436 enum isl_dim_type set_type
;
1439 n_piece
= FN(PW
,n_piece
)(pw
);
1441 return FN(PW
,free
)(pw
);
1442 if (n
== 0 && !isl_space_get_tuple_name(pw
->dim
, type
))
1445 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1447 space
= FN(PW
,take_space
)(pw
);
1448 space
= isl_space_drop_dims(space
, type
, first
, n
);
1449 pw
= FN(PW
,restore_space
)(pw
, space
);
1450 for (i
= 0; i
< n_piece
; ++i
) {
1454 domain
= FN(PW
,take_domain_at
)(pw
, i
);
1455 domain
= isl_set_project_out(domain
, set_type
, first
, n
);
1456 pw
= FN(PW
,restore_domain_at
)(pw
, i
, domain
);
1457 el
= FN(PW
,take_base_at
)(pw
, i
);
1458 el
= FN(EL
,drop_dims
)(el
, type
, first
, n
);
1459 pw
= FN(PW
,restore_base_at
)(pw
, i
, el
);
1465 /* Project the domain of pw onto its parameter space.
1467 __isl_give PW
*FN(PW
,project_domain_on_params
)(__isl_take PW
*pw
)
1472 n
= FN(PW
,dim
)(pw
, isl_dim_in
);
1474 return FN(PW
,free
)(pw
);
1475 pw
= FN(PW
,project_out
)(pw
, isl_dim_in
, 0, n
);
1476 space
= FN(PW
,get_domain_space
)(pw
);
1477 space
= isl_space_params(space
);
1478 pw
= FN(PW
,reset_domain_space
)(pw
, space
);
1482 /* Drop all parameters not referenced by "pw".
1484 __isl_give PW
*FN(PW
,drop_unused_params
)(__isl_take PW
*pw
)
1489 if (FN(PW
,check_named_params
)(pw
) < 0)
1490 return FN(PW
,free
)(pw
);
1492 n
= FN(PW
,dim
)(pw
, isl_dim_param
);
1494 return FN(PW
,free
)(pw
);
1495 for (i
= n
- 1; i
>= 0; i
--) {
1498 involves
= FN(PW
,involves_dims
)(pw
, isl_dim_param
, i
, 1);
1500 return FN(PW
,free
)(pw
);
1502 pw
= FN(PW
,drop_dims
)(pw
, isl_dim_param
, i
, 1);
1508 __isl_give PW
*FN(PW
,fix_dim
)(__isl_take PW
*pw
,
1509 enum isl_dim_type type
, unsigned pos
, isl_int v
)
1514 n
= FN(PW
,n_piece
)(pw
);
1516 return FN(PW
,free
)(pw
);
1518 if (type
== isl_dim_in
)
1521 for (i
= 0; i
< n
; ++i
) {
1524 domain
= FN(PW
,take_domain_at
)(pw
, i
);
1525 domain
= isl_set_fix(domain
, type
, pos
, v
);
1526 pw
= FN(PW
,restore_domain_at
)(pw
, i
, domain
);
1527 pw
= FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
);
1533 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1534 * to be equal to "v".
1536 __isl_give PW
*FN(PW
,fix_val
)(__isl_take PW
*pw
,
1537 enum isl_dim_type type
, unsigned pos
, __isl_take isl_val
*v
)
1540 return FN(PW
,free
)(pw
);
1541 if (!isl_val_is_int(v
))
1542 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
1543 "expecting integer value", goto error
);
1545 pw
= FN(PW
,fix_dim
)(pw
, type
, pos
, v
->n
);
1551 return FN(PW
,free
)(pw
);
1554 isl_size
FN(PW
,dim
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
1556 return isl_space_dim(FN(PW
,peek_space
)(pw
), type
);
1559 __isl_give PW
*FN(PW
,split_dims
)(__isl_take PW
*pw
,
1560 enum isl_dim_type type
, unsigned first
, unsigned n
)
1565 n_piece
= FN(PW
,n_piece
)(pw
);
1567 return FN(PW
,free
)(pw
);
1571 if (type
== isl_dim_in
)
1574 for (i
= 0; i
< n
; ++i
) {
1577 domain
= FN(PW
,take_domain_at
)(pw
, i
);
1578 domain
= isl_set_split_dims(domain
, type
, first
, n
);
1579 pw
= FN(PW
,restore_domain_at
)(pw
, i
, domain
);
1585 __isl_give isl_space
*FN(PW
,get_domain_space
)(__isl_keep PW
*pw
)
1587 return pw
? isl_space_domain(isl_space_copy(pw
->dim
)) : NULL
;
1590 /* Return the position of the dimension of the given type and name
1592 * Return -1 if no such dimension can be found.
1594 int FN(PW
,find_dim_by_name
)(__isl_keep PW
*pw
,
1595 enum isl_dim_type type
, const char *name
)
1599 return isl_space_find_dim_by_name(pw
->dim
, type
, name
);
1602 /* Return the position of the dimension of the given type and identifier
1604 * Return -1 if no such dimension can be found.
1606 static int FN(PW
,find_dim_by_id
)(__isl_keep PW
*pw
,
1607 enum isl_dim_type type
, __isl_keep isl_id
*id
)
1611 space
= FN(PW
,peek_space
)(pw
);
1612 return isl_space_find_dim_by_id(space
, type
, id
);
1615 /* Does the piecewise expression "pw" depend in any way
1616 * on the parameter with identifier "id"?
1618 isl_bool
FN(PW
,involves_param_id
)(__isl_keep PW
*pw
, __isl_keep isl_id
*id
)
1623 return isl_bool_error
;
1625 return isl_bool_false
;
1627 pos
= FN(PW
,find_dim_by_id
)(pw
, isl_dim_param
, id
);
1629 return isl_bool_false
;
1630 return FN(PW
,involves_dims
)(pw
, isl_dim_param
, pos
, 1);
1633 /* Reset the space of "pw". Since we don't know if the elements
1634 * represent the spaces themselves or their domains, we pass along
1635 * both when we call their reset_space_and_domain.
1637 static __isl_give PW
*FN(PW
,reset_space_and_domain
)(__isl_take PW
*pw
,
1638 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
1643 n
= FN(PW
,n_piece
)(pw
);
1644 if (n
< 0 || !space
|| !domain
)
1647 for (i
= 0; i
< n
; ++i
) {
1651 set
= FN(PW
,take_domain_at
)(pw
, i
);
1652 set
= isl_set_reset_space(set
, isl_space_copy(domain
));
1653 pw
= FN(PW
,restore_domain_at
)(pw
, i
, set
);
1654 el
= FN(PW
,take_base_at
)(pw
, i
);
1655 el
= FN(EL
,reset_space_and_domain
)(el
,
1656 isl_space_copy(space
), isl_space_copy(domain
));
1657 pw
= FN(PW
,restore_base_at
)(pw
, i
, el
);
1660 isl_space_free(domain
);
1662 pw
= FN(PW
,restore_space
)(pw
, space
);
1666 isl_space_free(domain
);
1667 isl_space_free(space
);
1672 __isl_give PW
*FN(PW
,reset_domain_space
)(__isl_take PW
*pw
,
1673 __isl_take isl_space
*domain
)
1677 space
= isl_space_extend_domain_with_range(isl_space_copy(domain
),
1678 FN(PW
,get_space
)(pw
));
1679 return FN(PW
,reset_space_and_domain
)(pw
, space
, domain
);
1682 __isl_give PW
*FN(PW
,reset_space
)(__isl_take PW
*pw
,
1683 __isl_take isl_space
*space
)
1687 domain
= isl_space_domain(isl_space_copy(space
));
1688 return FN(PW
,reset_space_and_domain
)(pw
, space
, domain
);
1691 __isl_give PW
*FN(PW
,set_tuple_id
)(__isl_take PW
*pw
, enum isl_dim_type type
,
1692 __isl_take isl_id
*id
)
1696 pw
= FN(PW
,cow
)(pw
);
1700 space
= FN(PW
,get_space
)(pw
);
1701 space
= isl_space_set_tuple_id(space
, type
, id
);
1703 return FN(PW
,reset_space
)(pw
, space
);
1706 return FN(PW
,free
)(pw
);
1709 /* Drop the id on the specified tuple.
1711 __isl_give PW
*FN(PW
,reset_tuple_id
)(__isl_take PW
*pw
, enum isl_dim_type type
)
1717 if (!FN(PW
,has_tuple_id
)(pw
, type
))
1720 pw
= FN(PW
,cow
)(pw
);
1724 space
= FN(PW
,get_space
)(pw
);
1725 space
= isl_space_reset_tuple_id(space
, type
);
1727 return FN(PW
,reset_space
)(pw
, space
);
1730 __isl_give PW
*FN(PW
,set_dim_id
)(__isl_take PW
*pw
,
1731 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1735 space
= FN(PW
,get_space
)(pw
);
1736 space
= isl_space_set_dim_id(space
, type
, pos
, id
);
1737 return FN(PW
,reset_space
)(pw
, space
);
1740 /* Reset the user pointer on all identifiers of parameters and tuples
1741 * of the space of "pw".
1743 __isl_give PW
*FN(PW
,reset_user
)(__isl_take PW
*pw
)
1747 space
= FN(PW
,get_space
)(pw
);
1748 space
= isl_space_reset_user(space
);
1750 return FN(PW
,reset_space
)(pw
, space
);
1753 isl_size
FN(PW
,n_piece
)(__isl_keep PW
*pw
)
1755 return pw
? pw
->n
: isl_size_error
;
1758 isl_stat
FN(PW
,foreach_piece
)(__isl_keep PW
*pw
,
1759 isl_stat (*fn
)(__isl_take isl_set
*set
, __isl_take EL
*el
, void *user
),
1765 return isl_stat_error
;
1767 for (i
= 0; i
< pw
->n
; ++i
)
1768 if (fn(isl_set_copy(pw
->p
[i
].set
),
1769 FN(EL
,copy
)(pw
->p
[i
].FIELD
), user
) < 0)
1770 return isl_stat_error
;
1775 /* Does "test" succeed on every cell of "pw"?
1777 isl_bool
FN(PW
,every_piece
)(__isl_keep PW
*pw
,
1778 isl_bool (*test
)(__isl_keep isl_set
*set
,
1779 __isl_keep EL
*el
, void *user
), void *user
)
1784 return isl_bool_error
;
1786 for (i
= 0; i
< pw
->n
; ++i
) {
1789 r
= test(pw
->p
[i
].set
, pw
->p
[i
].FIELD
, user
);
1794 return isl_bool_true
;
1797 /* Is "pw" defined over a single universe domain?
1799 * If the default value of this piecewise type is zero,
1800 * then a "pw" with a zero number of cells is also accepted
1801 * as it represents the default zero value.
1803 isl_bool
FN(FN(PW
,isa
),BASE
)(__isl_keep PW
*pw
)
1807 n
= FN(PW
,n_piece
)(pw
);
1809 return isl_bool_error
;
1810 if (DEFAULT_IS_ZERO
&& n
== 0)
1811 return isl_bool_true
;
1813 return isl_bool_false
;
1814 return isl_set_plain_is_universe(FN(PW
,peek_domain_at
)(pw
, 0));
1817 /* Return a zero base expression in the same space (and of the same type)
1820 static __isl_give EL
*FN(EL
,zero_like_type
)(__isl_take PW
*pw OPT_TYPE_PARAM
)
1824 space
= FN(PW
,get_space
)(pw
);
1826 return FN(EL
,zero_in_space
)(space
OPT_TYPE_ARG(NO_LOC
));
1830 /* Return a zero base expression in the same space as "pw".
1832 static __isl_give EL
*FN(EL
,zero_like
)(__isl_take PW
*pw
)
1834 return FN(EL
,zero_like_type
)(pw
);
1837 /* Return a zero base expression in the same space and of the same type
1840 * Pass along the type as an explicit argument for uniform handling
1841 * in isl_*_zero_like_type.
1843 static __isl_give EL
*FN(EL
,zero_like
)(__isl_take PW
*pw
)
1847 type
= FN(PW
,get_type
)(pw
);
1850 return FN(EL
,zero_like_type
)(pw
, type
);
1857 /* Given that "pw" is defined over a single universe domain,
1858 * return the base expression associated to this domain.
1860 * If the number of cells is zero, then "pw" is of a piecewise type
1861 * with a default zero value and effectively represents zero.
1862 * In this case, create a zero base expression in the same space
1863 * (and with the same type).
1864 * Otherwise, simply extract the associated base expression.
1866 __isl_give EL
*FN(FN(PW
,as
),BASE
)(__isl_take PW
*pw
)
1872 is_total
= FN(FN(PW
,isa
),BASE
)(pw
);
1876 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
1877 "expecting single total function", goto error
);
1878 n
= FN(PW
,n_piece
)(pw
);
1882 return FN(EL
,zero_like
)(pw
);
1883 el
= FN(PW
,take_base_at
)(pw
, 0);
1892 /* Negate the type of "pw".
1894 static __isl_give PW
*FN(PW
,negate_type
)(__isl_take PW
*pw
)
1896 pw
= FN(PW
,cow
)(pw
);
1899 pw
->type
= isl_fold_type_negate(pw
->type
);
1903 /* Negate the type of "pw".
1904 * Since "pw" does not have a type, do nothing.
1906 static __isl_give PW
*FN(PW
,negate_type
)(__isl_take PW
*pw
)
1912 __isl_give PW
*FN(PW
,mul_isl_int
)(__isl_take PW
*pw
, isl_int v
)
1917 if (isl_int_is_one(v
))
1919 if (pw
&& DEFAULT_IS_ZERO
&& isl_int_is_zero(v
)) {
1921 isl_space
*space
= FN(PW
,get_space
)(pw
);
1922 zero
= FN(PW
,ZERO
)(space
OPT_TYPE_ARG(pw
->));
1926 if (isl_int_is_neg(v
))
1927 pw
= FN(PW
,negate_type
)(pw
);
1929 n
= FN(PW
,n_piece
)(pw
);
1931 return FN(PW
,free
)(pw
);
1932 for (i
= 0; i
< n
; ++i
) {
1935 el
= FN(PW
,take_base_at
)(pw
, i
);
1936 el
= FN(EL
,scale
)(el
, v
);
1937 pw
= FN(PW
,restore_base_at
)(pw
, i
, el
);
1943 /* Multiply the pieces of "pw" by "v" and return the result.
1945 __isl_give PW
*FN(PW
,scale_val
)(__isl_take PW
*pw
, __isl_take isl_val
*v
)
1953 if (isl_val_is_one(v
)) {
1957 if (pw
&& DEFAULT_IS_ZERO
&& isl_val_is_zero(v
)) {
1959 isl_space
*space
= FN(PW
,get_space
)(pw
);
1960 zero
= FN(PW
,ZERO
)(space
OPT_TYPE_ARG(pw
->));
1965 if (isl_val_is_neg(v
))
1966 pw
= FN(PW
,negate_type
)(pw
);
1967 n
= FN(PW
,n_piece
)(pw
);
1971 for (i
= 0; i
< n
; ++i
) {
1974 el
= FN(PW
,take_base_at
)(pw
, i
);
1975 el
= FN(EL
,scale_val
)(el
, isl_val_copy(v
));
1976 pw
= FN(PW
,restore_base_at
)(pw
, i
, el
);
1987 /* Divide the pieces of "pw" by "v" and return the result.
1989 __isl_give PW
*FN(PW
,scale_down_val
)(__isl_take PW
*pw
, __isl_take isl_val
*v
)
1997 if (isl_val_is_one(v
)) {
2002 if (!isl_val_is_rat(v
))
2003 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
2004 "expecting rational factor", goto error
);
2005 if (isl_val_is_zero(v
))
2006 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
2007 "cannot scale down by zero", goto error
);
2009 if (isl_val_is_neg(v
))
2010 pw
= FN(PW
,negate_type
)(pw
);
2011 n
= FN(PW
,n_piece
)(pw
);
2015 for (i
= 0; i
< n
; ++i
) {
2018 el
= FN(PW
,take_base_at
)(pw
, i
);
2019 el
= FN(EL
,scale_down_val
)(el
, isl_val_copy(v
));
2020 pw
= FN(PW
,restore_base_at
)(pw
, i
, el
);
2031 __isl_give PW
*FN(PW
,scale
)(__isl_take PW
*pw
, isl_int v
)
2033 return FN(PW
,mul_isl_int
)(pw
, v
);
2036 /* Apply some normalization to "pw".
2037 * In particular, sort the pieces according to their function value
2038 * expressions, combining pairs of adjacent pieces with
2039 * the same such expression, and then normalize the domains of the pieces.
2041 * We normalize in place, but if anything goes wrong we need
2042 * to return NULL, so we need to make sure we don't change the
2043 * meaning of any possible other copies of "pw".
2045 static __isl_give PW
*FN(PW
,normalize
)(__isl_take PW
*pw
)
2050 pw
= FN(PW
,sort_unique
)(pw
);
2053 for (i
= 0; i
< pw
->n
; ++i
) {
2054 set
= isl_set_normalize(isl_set_copy(pw
->p
[i
].set
));
2056 return FN(PW
,free
)(pw
);
2057 isl_set_free(pw
->p
[i
].set
);
2064 /* Is pw1 obviously equal to pw2?
2065 * That is, do they have obviously identical cells and obviously identical
2066 * elements on each cell?
2068 * If "pw1" or "pw2" contain any NaNs, then they are considered
2069 * not to be the same. A NaN is not equal to anything, not even
2072 isl_bool
FN(PW
,plain_is_equal
)(__isl_keep PW
*pw1
, __isl_keep PW
*pw2
)
2075 isl_bool equal
, has_nan
;
2078 return isl_bool_error
;
2080 has_nan
= FN(PW
,involves_nan
)(pw1
);
2081 if (has_nan
>= 0 && !has_nan
)
2082 has_nan
= FN(PW
,involves_nan
)(pw2
);
2083 if (has_nan
< 0 || has_nan
)
2084 return isl_bool_not(has_nan
);
2087 return isl_bool_true
;
2088 equal
= FN(PW
,has_equal_space
)(pw1
, pw2
);
2089 if (equal
< 0 || !equal
)
2092 pw1
= FN(PW
,copy
)(pw1
);
2093 pw2
= FN(PW
,copy
)(pw2
);
2094 pw1
= FN(PW
,normalize
)(pw1
);
2095 pw2
= FN(PW
,normalize
)(pw2
);
2099 equal
= isl_bool_ok(pw1
->n
== pw2
->n
);
2100 for (i
= 0; equal
&& i
< pw1
->n
; ++i
) {
2101 equal
= isl_set_plain_is_equal(pw1
->p
[i
].set
, pw2
->p
[i
].set
);
2106 equal
= FN(EL
,plain_is_equal
)(pw1
->p
[i
].FIELD
, pw2
->p
[i
].FIELD
);
2117 return isl_bool_error
;
2120 /* Does "pw" involve any NaNs?
2122 isl_bool
FN(PW
,involves_nan
)(__isl_keep PW
*pw
)
2127 return isl_bool_error
;
2129 return isl_bool_false
;
2131 for (i
= 0; i
< pw
->n
; ++i
) {
2132 isl_bool has_nan
= FN(EL
,involves_nan
)(pw
->p
[i
].FIELD
);
2133 if (has_nan
< 0 || has_nan
)
2137 return isl_bool_false
;