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>
22 __isl_give PW
*FN(PW
,alloc_size
)(__isl_take isl_space
*dim
,
23 enum isl_fold type
, int n
)
25 __isl_give PW
*FN(PW
,alloc_size
)(__isl_take isl_space
*dim
, int n
)
33 ctx
= isl_space_get_ctx(dim
);
34 isl_assert(ctx
, n
>= 0, goto error
);
35 pw
= isl_alloc(ctx
, struct PW
,
36 sizeof(struct PW
) + (n
- 1) * sizeof(S(PW
,piece
)));
54 __isl_give PW
*FN(PW
,ZERO
)(__isl_take isl_space
*dim
, enum isl_fold type
)
56 return FN(PW
,alloc_size
)(dim
, type
, 0);
59 __isl_give PW
*FN(PW
,ZERO
)(__isl_take isl_space
*dim
)
61 return FN(PW
,alloc_size
)(dim
, 0);
65 __isl_give PW
*FN(PW
,add_piece
)(__isl_take PW
*pw
,
66 __isl_take isl_set
*set
, __isl_take EL
*el
)
69 isl_space
*el_dim
= NULL
;
71 if (!pw
|| !set
|| !el
)
74 if (isl_set_plain_is_empty(set
) || FN(EL
,EL_IS_ZERO
)(el
)) {
80 ctx
= isl_set_get_ctx(set
);
82 if (pw
->type
!= el
->type
)
83 isl_die(ctx
, isl_error_invalid
, "fold types don't match",
86 el_dim
= FN(EL
,get_space(el
));
87 isl_assert(ctx
, isl_space_is_equal(pw
->dim
, el_dim
), goto error
);
88 isl_assert(ctx
, pw
->n
< pw
->size
, goto error
);
90 pw
->p
[pw
->n
].set
= set
;
91 pw
->p
[pw
->n
].FIELD
= el
;
94 isl_space_free(el_dim
);
97 isl_space_free(el_dim
);
104 /* Does the space of "set" correspond to that of the domain of "el".
106 static isl_bool
FN(PW
,compatible_domain
)(__isl_keep EL
*el
,
107 __isl_keep isl_set
*set
)
110 isl_space
*el_space
, *set_space
;
113 return isl_bool_error
;
114 set_space
= isl_set_get_space(set
);
115 el_space
= FN(EL
,get_space
)(el
);
116 ok
= isl_space_is_domain_internal(set_space
, el_space
);
117 isl_space_free(el_space
);
118 isl_space_free(set_space
);
122 /* Check that the space of "set" corresponds to that of the domain of "el".
124 static isl_stat
FN(PW
,check_compatible_domain
)(__isl_keep EL
*el
,
125 __isl_keep isl_set
*set
)
129 ok
= FN(PW
,compatible_domain
)(el
, set
);
131 return isl_stat_error
;
133 isl_die(isl_set_get_ctx(set
), isl_error_invalid
,
134 "incompatible spaces", return isl_stat_error
);
140 __isl_give PW
*FN(PW
,alloc
)(enum isl_fold type
,
141 __isl_take isl_set
*set
, __isl_take EL
*el
)
143 __isl_give PW
*FN(PW
,alloc
)(__isl_take isl_set
*set
, __isl_take EL
*el
)
148 if (FN(PW
,check_compatible_domain
)(el
, set
) < 0)
152 pw
= FN(PW
,alloc_size
)(FN(EL
,get_space
)(el
), type
, 1);
154 pw
= FN(PW
,alloc_size
)(FN(EL
,get_space
)(el
), 1);
157 return FN(PW
,add_piece
)(pw
, set
, el
);
164 __isl_give PW
*FN(PW
,dup
)(__isl_keep PW
*pw
)
173 dup
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), pw
->type
, pw
->n
);
175 dup
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), pw
->n
);
180 for (i
= 0; i
< pw
->n
; ++i
)
181 dup
= FN(PW
,add_piece
)(dup
, isl_set_copy(pw
->p
[i
].set
),
182 FN(EL
,copy
)(pw
->p
[i
].FIELD
));
187 __isl_give PW
*FN(PW
,cow
)(__isl_take PW
*pw
)
195 return FN(PW
,dup
)(pw
);
198 __isl_give PW
*FN(PW
,copy
)(__isl_keep PW
*pw
)
207 __isl_null PW
*FN(PW
,free
)(__isl_take PW
*pw
)
216 for (i
= 0; i
< pw
->n
; ++i
) {
217 isl_set_free(pw
->p
[i
].set
);
218 FN(EL
,free
)(pw
->p
[i
].FIELD
);
220 isl_space_free(pw
->dim
);
226 const char *FN(PW
,get_dim_name
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
229 return pw
? isl_space_get_dim_name(pw
->dim
, type
, pos
) : NULL
;
232 isl_bool
FN(PW
,has_dim_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
235 return pw
? isl_space_has_dim_id(pw
->dim
, type
, pos
) : isl_bool_error
;
238 __isl_give isl_id
*FN(PW
,get_dim_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
241 return pw
? isl_space_get_dim_id(pw
->dim
, type
, pos
) : NULL
;
244 isl_bool
FN(PW
,has_tuple_name
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
246 return pw
? isl_space_has_tuple_name(pw
->dim
, type
) : isl_bool_error
;
249 const char *FN(PW
,get_tuple_name
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
251 return pw
? isl_space_get_tuple_name(pw
->dim
, type
) : NULL
;
254 isl_bool
FN(PW
,has_tuple_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
256 return pw
? isl_space_has_tuple_id(pw
->dim
, type
) : isl_bool_error
;
259 __isl_give isl_id
*FN(PW
,get_tuple_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
261 return pw
? isl_space_get_tuple_id(pw
->dim
, type
) : NULL
;
264 isl_bool
FN(PW
,IS_ZERO
)(__isl_keep PW
*pw
)
267 return isl_bool_error
;
273 __isl_give PW
*FN(PW
,realign_domain
)(__isl_take PW
*pw
,
274 __isl_take isl_reordering
*exp
)
282 for (i
= 0; i
< pw
->n
; ++i
) {
283 pw
->p
[i
].set
= isl_set_realign(pw
->p
[i
].set
,
284 isl_reordering_copy(exp
));
287 pw
->p
[i
].FIELD
= FN(EL
,realign_domain
)(pw
->p
[i
].FIELD
,
288 isl_reordering_copy(exp
));
293 pw
= FN(PW
,reset_domain_space
)(pw
, isl_reordering_get_space(exp
));
295 isl_reordering_free(exp
);
298 isl_reordering_free(exp
);
303 /* Check that "pw" has only named parameters, reporting an error
306 isl_stat
FN(PW
,check_named_params
)(__isl_keep PW
*pw
)
308 return isl_space_check_named_params(FN(PW
,peek_space
)(pw
));
311 /* Align the parameters of "pw" to those of "model".
313 __isl_give PW
*FN(PW
,align_params
)(__isl_take PW
*pw
, __isl_take isl_space
*model
)
316 isl_bool equal_params
;
321 ctx
= isl_space_get_ctx(model
);
322 if (!isl_space_has_named_params(model
))
323 isl_die(ctx
, isl_error_invalid
,
324 "model has unnamed parameters", goto error
);
325 if (FN(PW
,check_named_params
)(pw
) < 0)
327 equal_params
= isl_space_has_equal_params(pw
->dim
, model
);
328 if (equal_params
< 0)
333 model
= isl_space_drop_dims(model
, isl_dim_in
,
334 0, isl_space_dim(model
, isl_dim_in
));
335 model
= isl_space_drop_dims(model
, isl_dim_out
,
336 0, isl_space_dim(model
, isl_dim_out
));
337 exp
= isl_parameter_alignment_reordering(pw
->dim
, model
);
338 exp
= isl_reordering_extend_space(exp
,
339 FN(PW
,get_domain_space
)(pw
));
340 pw
= FN(PW
,realign_domain
)(pw
, exp
);
343 isl_space_free(model
);
346 isl_space_free(model
);
351 static __isl_give PW
*FN(PW
,align_params_pw_pw_and
)(__isl_take PW
*pw1
,
353 __isl_give PW
*(*fn
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
))
355 isl_bool equal_params
;
359 equal_params
= isl_space_has_equal_params(pw1
->dim
, pw2
->dim
);
360 if (equal_params
< 0)
364 if (FN(PW
,check_named_params
)(pw1
) < 0 ||
365 FN(PW
,check_named_params
)(pw2
) < 0)
367 pw1
= FN(PW
,align_params
)(pw1
, FN(PW
,get_space
)(pw2
));
368 pw2
= FN(PW
,align_params
)(pw2
, FN(PW
,get_space
)(pw1
));
376 static __isl_give PW
*FN(PW
,align_params_pw_set_and
)(__isl_take PW
*pw
,
377 __isl_take isl_set
*set
,
378 __isl_give PW
*(*fn
)(__isl_take PW
*pw
, __isl_take isl_set
*set
))
385 aligned
= isl_set_space_has_equal_params(set
, pw
->dim
);
390 ctx
= FN(PW
,get_ctx
)(pw
);
391 if (FN(PW
,check_named_params
)(pw
) < 0)
393 if (!isl_space_has_named_params(set
->dim
))
394 isl_die(ctx
, isl_error_invalid
,
395 "unaligned unnamed parameters", goto error
);
396 pw
= FN(PW
,align_params
)(pw
, isl_set_get_space(set
));
397 set
= isl_set_align_params(set
, FN(PW
,get_space
)(pw
));
406 static __isl_give PW
*FN(PW
,union_add_aligned
)(__isl_take PW
*pw1
,
417 ctx
= isl_space_get_ctx(pw1
->dim
);
419 if (pw1
->type
!= pw2
->type
)
420 isl_die(ctx
, isl_error_invalid
,
421 "fold types don't match", goto error
);
423 isl_assert(ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
425 if (FN(PW
,IS_ZERO
)(pw1
)) {
430 if (FN(PW
,IS_ZERO
)(pw2
)) {
435 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
437 res
= FN(PW
,alloc_size
)(isl_space_copy(pw1
->dim
), pw1
->type
, n
);
439 res
= FN(PW
,alloc_size
)(isl_space_copy(pw1
->dim
), n
);
442 for (i
= 0; i
< pw1
->n
; ++i
) {
443 set
= isl_set_copy(pw1
->p
[i
].set
);
444 for (j
= 0; j
< pw2
->n
; ++j
) {
445 struct isl_set
*common
;
447 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
448 isl_set_copy(pw2
->p
[j
].set
));
449 if (isl_set_plain_is_empty(common
)) {
450 isl_set_free(common
);
453 set
= isl_set_subtract(set
,
454 isl_set_copy(pw2
->p
[j
].set
));
456 sum
= FN(EL
,add_on_domain
)(common
,
457 FN(EL
,copy
)(pw1
->p
[i
].FIELD
),
458 FN(EL
,copy
)(pw2
->p
[j
].FIELD
));
460 res
= FN(PW
,add_piece
)(res
, common
, sum
);
462 res
= FN(PW
,add_piece
)(res
, set
, FN(EL
,copy
)(pw1
->p
[i
].FIELD
));
465 for (j
= 0; j
< pw2
->n
; ++j
) {
466 set
= isl_set_copy(pw2
->p
[j
].set
);
467 for (i
= 0; i
< pw1
->n
; ++i
)
468 set
= isl_set_subtract(set
,
469 isl_set_copy(pw1
->p
[i
].set
));
470 res
= FN(PW
,add_piece
)(res
, set
, FN(EL
,copy
)(pw2
->p
[j
].FIELD
));
483 /* Private version of "union_add". For isl_pw_qpolynomial and
484 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
486 static __isl_give PW
*FN(PW
,union_add_
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
)
488 return FN(PW
,align_params_pw_pw_and
)(pw1
, pw2
,
489 &FN(PW
,union_add_aligned
));
492 /* Make sure "pw" has room for at least "n" more pieces.
494 * If there is only one reference to pw, we extend it in place.
495 * Otherwise, we create a new PW and copy the pieces.
497 static __isl_give PW
*FN(PW
,grow
)(__isl_take PW
*pw
, int n
)
505 if (pw
->n
+ n
<= pw
->size
)
507 ctx
= FN(PW
,get_ctx
)(pw
);
510 res
= isl_realloc(ctx
, pw
, struct PW
,
511 sizeof(struct PW
) + (n
- 1) * sizeof(S(PW
,piece
)));
513 return FN(PW
,free
)(pw
);
518 res
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), pw
->type
, n
);
520 res
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), n
);
523 return FN(PW
,free
)(pw
);
524 for (i
= 0; i
< pw
->n
; ++i
)
525 res
= FN(PW
,add_piece
)(res
, isl_set_copy(pw
->p
[i
].set
),
526 FN(EL
,copy
)(pw
->p
[i
].FIELD
));
531 static __isl_give PW
*FN(PW
,add_disjoint_aligned
)(__isl_take PW
*pw1
,
540 if (pw1
->size
< pw1
->n
+ pw2
->n
&& pw1
->n
< pw2
->n
)
541 return FN(PW
,add_disjoint_aligned
)(pw2
, pw1
);
543 ctx
= isl_space_get_ctx(pw1
->dim
);
545 if (pw1
->type
!= pw2
->type
)
546 isl_die(ctx
, isl_error_invalid
,
547 "fold types don't match", goto error
);
549 isl_assert(ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
551 if (FN(PW
,IS_ZERO
)(pw1
)) {
556 if (FN(PW
,IS_ZERO
)(pw2
)) {
561 pw1
= FN(PW
,grow
)(pw1
, pw2
->n
);
565 for (i
= 0; i
< pw2
->n
; ++i
)
566 pw1
= FN(PW
,add_piece
)(pw1
,
567 isl_set_copy(pw2
->p
[i
].set
),
568 FN(EL
,copy
)(pw2
->p
[i
].FIELD
));
579 __isl_give PW
*FN(PW
,add_disjoint
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
)
581 return FN(PW
,align_params_pw_pw_and
)(pw1
, pw2
,
582 &FN(PW
,add_disjoint_aligned
));
585 /* This function is currently only used from isl_aff.c
587 static __isl_give PW
*FN(PW
,on_shared_domain_in
)(__isl_take PW
*pw1
,
588 __isl_take PW
*pw2
, __isl_take isl_space
*space
,
589 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
590 __attribute__ ((unused
));
592 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
593 * The result of "fn" (and therefore also of this function) lives in "space".
595 static __isl_give PW
*FN(PW
,on_shared_domain_in
)(__isl_take PW
*pw1
,
596 __isl_take PW
*pw2
, __isl_take isl_space
*space
,
597 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
607 res
= FN(PW
,alloc_size
)(isl_space_copy(space
), pw1
->type
, n
);
609 res
= FN(PW
,alloc_size
)(isl_space_copy(space
), n
);
612 for (i
= 0; i
< pw1
->n
; ++i
) {
613 for (j
= 0; j
< pw2
->n
; ++j
) {
618 common
= isl_set_intersect(
619 isl_set_copy(pw1
->p
[i
].set
),
620 isl_set_copy(pw2
->p
[j
].set
));
621 empty
= isl_set_plain_is_empty(common
);
622 if (empty
< 0 || empty
) {
623 isl_set_free(common
);
629 res_ij
= fn(FN(EL
,copy
)(pw1
->p
[i
].FIELD
),
630 FN(EL
,copy
)(pw2
->p
[j
].FIELD
));
631 res_ij
= FN(EL
,gist
)(res_ij
, isl_set_copy(common
));
633 res
= FN(PW
,add_piece
)(res
, common
, res_ij
);
637 isl_space_free(space
);
642 isl_space_free(space
);
649 /* This function is currently only used from isl_aff.c
651 static __isl_give PW
*FN(PW
,on_shared_domain
)(__isl_take PW
*pw1
,
653 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
654 __attribute__ ((unused
));
656 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
657 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
659 static __isl_give PW
*FN(PW
,on_shared_domain
)(__isl_take PW
*pw1
,
661 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
668 space
= isl_space_copy(pw1
->dim
);
669 return FN(PW
,on_shared_domain_in
)(pw1
, pw2
, space
, fn
);
677 __isl_give PW
*FN(PW
,neg
)(__isl_take PW
*pw
)
684 if (FN(PW
,IS_ZERO
)(pw
))
691 for (i
= 0; i
< pw
->n
; ++i
) {
692 pw
->p
[i
].FIELD
= FN(EL
,neg
)(pw
->p
[i
].FIELD
);
694 return FN(PW
,free
)(pw
);
702 __isl_give PW
*FN(PW
,sub
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
)
704 return FN(PW
,add
)(pw1
, FN(PW
,neg
)(pw2
));
708 /* Return the parameter domain of "pw".
710 __isl_give isl_set
*FN(PW
,params
)(__isl_take PW
*pw
)
712 return isl_set_params(FN(PW
,domain
)(pw
));
715 __isl_give isl_set
*FN(PW
,domain
)(__isl_take PW
*pw
)
723 dom
= isl_set_empty(FN(PW
,get_domain_space
)(pw
));
724 for (i
= 0; i
< pw
->n
; ++i
)
725 dom
= isl_set_union_disjoint(dom
, isl_set_copy(pw
->p
[i
].set
));
732 /* Exploit the equalities in the domain of piece "i" of "pw"
733 * to simplify the associated function.
734 * If the domain of piece "i" is empty, then remove it entirely,
735 * replacing it with the final piece.
737 static int FN(PW
,exploit_equalities_and_remove_if_empty
)(__isl_keep PW
*pw
,
741 int empty
= isl_set_plain_is_empty(pw
->p
[i
].set
);
746 isl_set_free(pw
->p
[i
].set
);
747 FN(EL
,free
)(pw
->p
[i
].FIELD
);
749 pw
->p
[i
] = pw
->p
[pw
->n
- 1];
755 aff
= isl_set_affine_hull(isl_set_copy(pw
->p
[i
].set
));
756 pw
->p
[i
].FIELD
= FN(EL
,substitute_equalities
)(pw
->p
[i
].FIELD
, aff
);
763 /* Convert a piecewise expression defined over a parameter domain
764 * into one that is defined over a zero-dimensional set.
766 __isl_give PW
*FN(PW
,from_range
)(__isl_take PW
*pw
)
772 if (!isl_space_is_set(pw
->dim
))
773 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
774 "not living in a set space", return FN(PW
,free
)(pw
));
776 space
= FN(PW
,get_space
)(pw
);
777 space
= isl_space_from_range(space
);
778 pw
= FN(PW
,reset_space
)(pw
, space
);
783 /* Fix the value of the given parameter or domain dimension of "pw"
784 * to be equal to "value".
786 __isl_give PW
*FN(PW
,fix_si
)(__isl_take PW
*pw
, enum isl_dim_type type
,
787 unsigned pos
, int value
)
794 if (type
== isl_dim_out
)
795 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
796 "cannot fix output dimension", return FN(PW
,free
)(pw
));
801 if (type
== isl_dim_in
)
806 return FN(PW
,free
)(pw
);
808 for (i
= pw
->n
- 1; i
>= 0; --i
) {
809 pw
->p
[i
].set
= isl_set_fix_si(pw
->p
[i
].set
, type
, pos
, value
);
810 if (FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
) < 0)
811 return FN(PW
,free
)(pw
);
817 /* Restrict the domain of "pw" by combining each cell
818 * with "set" through a call to "fn", where "fn" may be
819 * isl_set_intersect, isl_set_intersect_params or isl_set_subtract.
821 static __isl_give PW
*FN(PW
,restrict_domain_aligned
)(__isl_take PW
*pw
,
822 __isl_take isl_set
*set
,
823 __isl_give isl_set
*(*fn
)(__isl_take isl_set
*set1
,
824 __isl_take isl_set
*set2
))
840 for (i
= pw
->n
- 1; i
>= 0; --i
) {
841 pw
->p
[i
].set
= fn(pw
->p
[i
].set
, isl_set_copy(set
));
842 if (FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
) < 0)
854 static __isl_give PW
*FN(PW
,intersect_domain_aligned
)(__isl_take PW
*pw
,
855 __isl_take isl_set
*set
)
857 return FN(PW
,restrict_domain_aligned
)(pw
, set
, &isl_set_intersect
);
860 __isl_give PW
*FN(PW
,intersect_domain
)(__isl_take PW
*pw
,
861 __isl_take isl_set
*context
)
863 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
864 &FN(PW
,intersect_domain_aligned
));
867 static __isl_give PW
*FN(PW
,intersect_params_aligned
)(__isl_take PW
*pw
,
868 __isl_take isl_set
*set
)
870 return FN(PW
,restrict_domain_aligned
)(pw
, set
,
871 &isl_set_intersect_params
);
874 /* Intersect the domain of "pw" with the parameter domain "context".
876 __isl_give PW
*FN(PW
,intersect_params
)(__isl_take PW
*pw
,
877 __isl_take isl_set
*context
)
879 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
880 &FN(PW
,intersect_params_aligned
));
883 /* Subtract "domain' from the domain of "pw", assuming their
884 * parameters have been aligned.
886 static __isl_give PW
*FN(PW
,subtract_domain_aligned
)(__isl_take PW
*pw
,
887 __isl_take isl_set
*domain
)
889 return FN(PW
,restrict_domain_aligned
)(pw
, domain
, &isl_set_subtract
);
892 /* Subtract "domain' from the domain of "pw".
894 __isl_give PW
*FN(PW
,subtract_domain
)(__isl_take PW
*pw
,
895 __isl_take isl_set
*domain
)
897 return FN(PW
,align_params_pw_set_and
)(pw
, domain
,
898 &FN(PW
,subtract_domain_aligned
));
901 /* Compute the gist of "pw" with respect to the domain constraints
902 * of "context" for the case where the domain of the last element
903 * of "pw" is equal to "context".
904 * Call "fn_el" to compute the gist of this element, replace
905 * its domain by the universe and drop all other elements
906 * as their domains are necessarily disjoint from "context".
908 static __isl_give PW
*FN(PW
,gist_last
)(__isl_take PW
*pw
,
909 __isl_take isl_set
*context
,
910 __isl_give EL
*(*fn_el
)(__isl_take EL
*el
, __isl_take isl_set
*set
))
915 for (i
= 0; i
< pw
->n
- 1; ++i
) {
916 isl_set_free(pw
->p
[i
].set
);
917 FN(EL
,free
)(pw
->p
[i
].FIELD
);
919 pw
->p
[0].FIELD
= pw
->p
[pw
->n
- 1].FIELD
;
920 pw
->p
[0].set
= pw
->p
[pw
->n
- 1].set
;
923 space
= isl_set_get_space(context
);
924 pw
->p
[0].FIELD
= fn_el(pw
->p
[0].FIELD
, context
);
925 context
= isl_set_universe(space
);
926 isl_set_free(pw
->p
[0].set
);
927 pw
->p
[0].set
= context
;
929 if (!pw
->p
[0].FIELD
|| !pw
->p
[0].set
)
930 return FN(PW
,free
)(pw
);
935 /* Compute the gist of "pw" with respect to the domain constraints
936 * of "context". Call "fn_el" to compute the gist of the elements
937 * and "fn_dom" to compute the gist of the domains.
939 * If the piecewise expression is empty or the context is the universe,
940 * then nothing can be simplified.
942 static __isl_give PW
*FN(PW
,gist_aligned
)(__isl_take PW
*pw
,
943 __isl_take isl_set
*context
,
944 __isl_give EL
*(*fn_el
)(__isl_take EL
*el
,
945 __isl_take isl_set
*set
),
946 __isl_give isl_set
*(*fn_dom
)(__isl_take isl_set
*set
,
947 __isl_take isl_basic_set
*bset
))
952 isl_basic_set
*hull
= NULL
;
958 isl_set_free(context
);
962 is_universe
= isl_set_plain_is_universe(context
);
966 isl_set_free(context
);
970 aligned
= isl_set_space_has_equal_params(context
, pw
->dim
);
974 pw
= FN(PW
,align_params
)(pw
, isl_set_get_space(context
));
975 context
= isl_set_align_params(context
, FN(PW
,get_space
)(pw
));
985 equal
= isl_set_plain_is_equal(pw
->p
[0].set
, context
);
989 return FN(PW
,gist_last
)(pw
, context
, fn_el
);
992 context
= isl_set_compute_divs(context
);
993 hull
= isl_set_simple_hull(isl_set_copy(context
));
995 for (i
= pw
->n
- 1; i
>= 0; --i
) {
999 if (i
== pw
->n
- 1) {
1001 equal
= isl_set_plain_is_equal(pw
->p
[i
].set
, context
);
1005 isl_basic_set_free(hull
);
1006 return FN(PW
,gist_last
)(pw
, context
, fn_el
);
1009 set_i
= isl_set_intersect(isl_set_copy(pw
->p
[i
].set
),
1010 isl_set_copy(context
));
1011 empty
= isl_set_plain_is_empty(set_i
);
1012 pw
->p
[i
].FIELD
= fn_el(pw
->p
[i
].FIELD
, set_i
);
1013 pw
->p
[i
].set
= fn_dom(pw
->p
[i
].set
, isl_basic_set_copy(hull
));
1014 if (empty
< 0 || !pw
->p
[i
].FIELD
|| !pw
->p
[i
].set
)
1017 isl_set_free(pw
->p
[i
].set
);
1018 FN(EL
,free
)(pw
->p
[i
].FIELD
);
1020 pw
->p
[i
] = pw
->p
[pw
->n
- 1];
1025 isl_basic_set_free(hull
);
1026 isl_set_free(context
);
1031 isl_basic_set_free(hull
);
1032 isl_set_free(context
);
1036 static __isl_give PW
*FN(PW
,gist_domain_aligned
)(__isl_take PW
*pw
,
1037 __isl_take isl_set
*set
)
1039 return FN(PW
,gist_aligned
)(pw
, set
, &FN(EL
,gist
),
1040 &isl_set_gist_basic_set
);
1043 __isl_give PW
*FN(PW
,gist
)(__isl_take PW
*pw
, __isl_take isl_set
*context
)
1045 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
1046 &FN(PW
,gist_domain_aligned
));
1049 static __isl_give PW
*FN(PW
,gist_params_aligned
)(__isl_take PW
*pw
,
1050 __isl_take isl_set
*set
)
1052 return FN(PW
,gist_aligned
)(pw
, set
, &FN(EL
,gist_params
),
1053 &isl_set_gist_params_basic_set
);
1056 __isl_give PW
*FN(PW
,gist_params
)(__isl_take PW
*pw
,
1057 __isl_take isl_set
*context
)
1059 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
1060 &FN(PW
,gist_params_aligned
));
1063 /* Return -1 if the piece "p1" should be sorted before "p2"
1064 * and 1 if it should be sorted after "p2".
1065 * Return 0 if they do not need to be sorted in a specific order.
1067 * The two pieces are compared on the basis of their function value expressions.
1069 static int FN(PW
,sort_field_cmp
)(const void *p1
, const void *p2
, void *arg
)
1071 struct FN(PW
,piece
) const *pc1
= p1
;
1072 struct FN(PW
,piece
) const *pc2
= p2
;
1074 return FN(EL
,plain_cmp
)(pc1
->FIELD
, pc2
->FIELD
);
1077 /* Sort the pieces of "pw" according to their function value
1078 * expressions and then combine pairs of adjacent pieces with
1079 * the same such expression.
1081 * The sorting is performed in place because it does not
1082 * change the meaning of "pw", but care needs to be
1083 * taken not to change any possible other copies of "pw"
1084 * in case anything goes wrong.
1086 __isl_give PW
*FN(PW
,sort
)(__isl_take PW
*pw
)
1095 if (isl_sort(pw
->p
, pw
->n
, sizeof(pw
->p
[0]),
1096 &FN(PW
,sort_field_cmp
), NULL
) < 0)
1097 return FN(PW
,free
)(pw
);
1098 for (i
= pw
->n
- 1; i
>= 1; --i
) {
1099 if (!FN(EL
,plain_is_equal
)(pw
->p
[i
- 1].FIELD
, pw
->p
[i
].FIELD
))
1101 set
= isl_set_union(isl_set_copy(pw
->p
[i
- 1].set
),
1102 isl_set_copy(pw
->p
[i
].set
));
1104 return FN(PW
,free
)(pw
);
1105 isl_set_free(pw
->p
[i
].set
);
1106 FN(EL
,free
)(pw
->p
[i
].FIELD
);
1107 isl_set_free(pw
->p
[i
- 1].set
);
1108 pw
->p
[i
- 1].set
= set
;
1109 for (j
= i
+ 1; j
< pw
->n
; ++j
)
1110 pw
->p
[j
- 1] = pw
->p
[j
];
1117 /* Coalesce the domains of "pw".
1119 * Prior to the actual coalescing, first sort the pieces such that
1120 * pieces with the same function value expression are combined
1121 * into a single piece, the combined domain of which can then
1124 __isl_give PW
*FN(PW
,coalesce
)(__isl_take PW
*pw
)
1128 pw
= FN(PW
,sort
)(pw
);
1132 for (i
= 0; i
< pw
->n
; ++i
) {
1133 pw
->p
[i
].set
= isl_set_coalesce(pw
->p
[i
].set
);
1144 isl_ctx
*FN(PW
,get_ctx
)(__isl_keep PW
*pw
)
1146 return pw
? isl_space_get_ctx(pw
->dim
) : NULL
;
1149 isl_bool
FN(PW
,involves_dims
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
1150 unsigned first
, unsigned n
)
1153 enum isl_dim_type set_type
;
1156 return isl_bool_error
;
1157 if (pw
->n
== 0 || n
== 0)
1158 return isl_bool_false
;
1160 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1162 for (i
= 0; i
< pw
->n
; ++i
) {
1163 isl_bool involves
= FN(EL
,involves_dims
)(pw
->p
[i
].FIELD
,
1165 if (involves
< 0 || involves
)
1167 involves
= isl_set_involves_dims(pw
->p
[i
].set
,
1168 set_type
, first
, n
);
1169 if (involves
< 0 || involves
)
1172 return isl_bool_false
;
1175 __isl_give PW
*FN(PW
,set_dim_name
)(__isl_take PW
*pw
,
1176 enum isl_dim_type type
, unsigned pos
, const char *s
)
1179 enum isl_dim_type set_type
;
1181 pw
= FN(PW
,cow
)(pw
);
1185 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1187 pw
->dim
= isl_space_set_dim_name(pw
->dim
, type
, pos
, s
);
1191 for (i
= 0; i
< pw
->n
; ++i
) {
1192 pw
->p
[i
].set
= isl_set_set_dim_name(pw
->p
[i
].set
,
1196 pw
->p
[i
].FIELD
= FN(EL
,set_dim_name
)(pw
->p
[i
].FIELD
, type
, pos
, s
);
1197 if (!pw
->p
[i
].FIELD
)
1207 __isl_give PW
*FN(PW
,drop_dims
)(__isl_take PW
*pw
,
1208 enum isl_dim_type type
, unsigned first
, unsigned n
)
1211 enum isl_dim_type set_type
;
1215 if (n
== 0 && !isl_space_get_tuple_name(pw
->dim
, type
))
1218 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1220 pw
= FN(PW
,cow
)(pw
);
1223 pw
->dim
= isl_space_drop_dims(pw
->dim
, type
, first
, n
);
1226 for (i
= 0; i
< pw
->n
; ++i
) {
1227 pw
->p
[i
].FIELD
= FN(EL
,drop_dims
)(pw
->p
[i
].FIELD
, type
, first
, n
);
1228 if (!pw
->p
[i
].FIELD
)
1230 if (type
== isl_dim_out
)
1232 pw
->p
[i
].set
= isl_set_drop(pw
->p
[i
].set
, set_type
, first
, n
);
1243 /* This function is very similar to drop_dims.
1244 * The only difference is that the cells may still involve
1245 * the specified dimensions. They are removed using
1246 * isl_set_project_out instead of isl_set_drop.
1248 __isl_give PW
*FN(PW
,project_out
)(__isl_take PW
*pw
,
1249 enum isl_dim_type type
, unsigned first
, unsigned n
)
1252 enum isl_dim_type set_type
;
1256 if (n
== 0 && !isl_space_get_tuple_name(pw
->dim
, type
))
1259 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1261 pw
= FN(PW
,cow
)(pw
);
1264 pw
->dim
= isl_space_drop_dims(pw
->dim
, type
, first
, n
);
1267 for (i
= 0; i
< pw
->n
; ++i
) {
1268 pw
->p
[i
].set
= isl_set_project_out(pw
->p
[i
].set
,
1269 set_type
, first
, n
);
1272 pw
->p
[i
].FIELD
= FN(EL
,drop_dims
)(pw
->p
[i
].FIELD
, type
, first
, n
);
1273 if (!pw
->p
[i
].FIELD
)
1283 /* Project the domain of pw onto its parameter space.
1285 __isl_give PW
*FN(PW
,project_domain_on_params
)(__isl_take PW
*pw
)
1290 n
= FN(PW
,dim
)(pw
, isl_dim_in
);
1291 pw
= FN(PW
,project_out
)(pw
, isl_dim_in
, 0, n
);
1292 space
= FN(PW
,get_domain_space
)(pw
);
1293 space
= isl_space_params(space
);
1294 pw
= FN(PW
,reset_domain_space
)(pw
, space
);
1298 /* Drop all parameters not referenced by "pw".
1300 __isl_give PW
*FN(PW
,drop_unused_params
)(__isl_take PW
*pw
)
1304 if (FN(PW
,check_named_params
)(pw
) < 0)
1305 return FN(PW
,free
)(pw
);
1307 for (i
= FN(PW
,dim
)(pw
, isl_dim_param
) - 1; i
>= 0; i
--) {
1310 involves
= FN(PW
,involves_dims
)(pw
, isl_dim_param
, i
, 1);
1312 return FN(PW
,free
)(pw
);
1314 pw
= FN(PW
,drop_dims
)(pw
, isl_dim_param
, i
, 1);
1320 #ifndef NO_INSERT_DIMS
1321 __isl_give PW
*FN(PW
,insert_dims
)(__isl_take PW
*pw
, enum isl_dim_type type
,
1322 unsigned first
, unsigned n
)
1325 enum isl_dim_type set_type
;
1329 if (n
== 0 && !isl_space_is_named_or_nested(pw
->dim
, type
))
1332 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1334 pw
= FN(PW
,cow
)(pw
);
1338 pw
->dim
= isl_space_insert_dims(pw
->dim
, type
, first
, n
);
1342 for (i
= 0; i
< pw
->n
; ++i
) {
1343 pw
->p
[i
].set
= isl_set_insert_dims(pw
->p
[i
].set
,
1344 set_type
, first
, n
);
1347 pw
->p
[i
].FIELD
= FN(EL
,insert_dims
)(pw
->p
[i
].FIELD
,
1349 if (!pw
->p
[i
].FIELD
)
1360 __isl_give PW
*FN(PW
,fix_dim
)(__isl_take PW
*pw
,
1361 enum isl_dim_type type
, unsigned pos
, isl_int v
)
1368 if (type
== isl_dim_in
)
1371 pw
= FN(PW
,cow
)(pw
);
1374 for (i
= 0; i
< pw
->n
; ++i
) {
1375 pw
->p
[i
].set
= isl_set_fix(pw
->p
[i
].set
, type
, pos
, v
);
1376 if (FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
) < 0)
1377 return FN(PW
,free
)(pw
);
1383 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1384 * to be equal to "v".
1386 __isl_give PW
*FN(PW
,fix_val
)(__isl_take PW
*pw
,
1387 enum isl_dim_type type
, unsigned pos
, __isl_take isl_val
*v
)
1390 return FN(PW
,free
)(pw
);
1391 if (!isl_val_is_int(v
))
1392 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
1393 "expecting integer value", goto error
);
1395 pw
= FN(PW
,fix_dim
)(pw
, type
, pos
, v
->n
);
1401 return FN(PW
,free
)(pw
);
1404 unsigned FN(PW
,dim
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
1406 return pw
? isl_space_dim(pw
->dim
, type
) : 0;
1409 __isl_give PW
*FN(PW
,split_dims
)(__isl_take PW
*pw
,
1410 enum isl_dim_type type
, unsigned first
, unsigned n
)
1419 if (type
== isl_dim_in
)
1422 pw
= FN(PW
,cow
)(pw
);
1427 for (i
= 0; i
< pw
->n
; ++i
) {
1428 pw
->p
[i
].set
= isl_set_split_dims(pw
->p
[i
].set
, type
, first
, n
);
1440 /* Compute the maximal value attained by the piecewise quasipolynomial
1441 * on its domain or zero if the domain is empty.
1442 * In the worst case, the domain is scanned completely,
1443 * so the domain is assumed to be bounded.
1445 __isl_give isl_val
*FN(PW
,opt
)(__isl_take PW
*pw
, int max
)
1454 opt
= isl_val_zero(FN(PW
,get_ctx
)(pw
));
1459 opt
= FN(EL
,opt_on_domain
)(FN(EL
,copy
)(pw
->p
[0].FIELD
),
1460 isl_set_copy(pw
->p
[0].set
), max
);
1461 for (i
= 1; i
< pw
->n
; ++i
) {
1463 opt_i
= FN(EL
,opt_on_domain
)(FN(EL
,copy
)(pw
->p
[i
].FIELD
),
1464 isl_set_copy(pw
->p
[i
].set
), max
);
1466 opt
= isl_val_max(opt
, opt_i
);
1468 opt
= isl_val_min(opt
, opt_i
);
1475 __isl_give isl_val
*FN(PW
,max
)(__isl_take PW
*pw
)
1477 return FN(PW
,opt
)(pw
, 1);
1480 __isl_give isl_val
*FN(PW
,min
)(__isl_take PW
*pw
)
1482 return FN(PW
,opt
)(pw
, 0);
1486 /* Return the space of "pw".
1488 __isl_keep isl_space
*FN(PW
,peek_space
)(__isl_keep PW
*pw
)
1490 return pw
? pw
->dim
: NULL
;
1493 __isl_give isl_space
*FN(PW
,get_space
)(__isl_keep PW
*pw
)
1495 return isl_space_copy(FN(PW
,peek_space
)(pw
));
1498 __isl_give isl_space
*FN(PW
,get_domain_space
)(__isl_keep PW
*pw
)
1500 return pw
? isl_space_domain(isl_space_copy(pw
->dim
)) : NULL
;
1503 /* Return the position of the dimension of the given type and name
1505 * Return -1 if no such dimension can be found.
1507 int FN(PW
,find_dim_by_name
)(__isl_keep PW
*pw
,
1508 enum isl_dim_type type
, const char *name
)
1512 return isl_space_find_dim_by_name(pw
->dim
, type
, name
);
1515 #ifndef NO_RESET_DIM
1516 /* Reset the space of "pw". Since we don't know if the elements
1517 * represent the spaces themselves or their domains, we pass along
1518 * both when we call their reset_space_and_domain.
1520 static __isl_give PW
*FN(PW
,reset_space_and_domain
)(__isl_take PW
*pw
,
1521 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
1525 pw
= FN(PW
,cow
)(pw
);
1526 if (!pw
|| !space
|| !domain
)
1529 for (i
= 0; i
< pw
->n
; ++i
) {
1530 pw
->p
[i
].set
= isl_set_reset_space(pw
->p
[i
].set
,
1531 isl_space_copy(domain
));
1534 pw
->p
[i
].FIELD
= FN(EL
,reset_space_and_domain
)(pw
->p
[i
].FIELD
,
1535 isl_space_copy(space
), isl_space_copy(domain
));
1536 if (!pw
->p
[i
].FIELD
)
1540 isl_space_free(domain
);
1542 isl_space_free(pw
->dim
);
1547 isl_space_free(domain
);
1548 isl_space_free(space
);
1553 __isl_give PW
*FN(PW
,reset_domain_space
)(__isl_take PW
*pw
,
1554 __isl_take isl_space
*domain
)
1558 space
= isl_space_extend_domain_with_range(isl_space_copy(domain
),
1559 FN(PW
,get_space
)(pw
));
1560 return FN(PW
,reset_space_and_domain
)(pw
, space
, domain
);
1563 __isl_give PW
*FN(PW
,reset_space
)(__isl_take PW
*pw
, __isl_take isl_space
*dim
)
1567 domain
= isl_space_domain(isl_space_copy(dim
));
1568 return FN(PW
,reset_space_and_domain
)(pw
, dim
, domain
);
1571 __isl_give PW
*FN(PW
,set_tuple_id
)(__isl_take PW
*pw
, enum isl_dim_type type
,
1572 __isl_take isl_id
*id
)
1576 pw
= FN(PW
,cow
)(pw
);
1580 space
= FN(PW
,get_space
)(pw
);
1581 space
= isl_space_set_tuple_id(space
, type
, id
);
1583 return FN(PW
,reset_space
)(pw
, space
);
1586 return FN(PW
,free
)(pw
);
1589 /* Drop the id on the specified tuple.
1591 __isl_give PW
*FN(PW
,reset_tuple_id
)(__isl_take PW
*pw
, enum isl_dim_type type
)
1597 if (!FN(PW
,has_tuple_id
)(pw
, type
))
1600 pw
= FN(PW
,cow
)(pw
);
1604 space
= FN(PW
,get_space
)(pw
);
1605 space
= isl_space_reset_tuple_id(space
, type
);
1607 return FN(PW
,reset_space
)(pw
, space
);
1610 __isl_give PW
*FN(PW
,set_dim_id
)(__isl_take PW
*pw
,
1611 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1613 pw
= FN(PW
,cow
)(pw
);
1616 pw
->dim
= isl_space_set_dim_id(pw
->dim
, type
, pos
, id
);
1617 return FN(PW
,reset_space
)(pw
, isl_space_copy(pw
->dim
));
1620 return FN(PW
,free
)(pw
);
1624 /* Reset the user pointer on all identifiers of parameters and tuples
1625 * of the space of "pw".
1627 __isl_give PW
*FN(PW
,reset_user
)(__isl_take PW
*pw
)
1631 space
= FN(PW
,get_space
)(pw
);
1632 space
= isl_space_reset_user(space
);
1634 return FN(PW
,reset_space
)(pw
, space
);
1637 isl_bool
FN(PW
,has_equal_space
)(__isl_keep PW
*pw1
, __isl_keep PW
*pw2
)
1640 return isl_bool_error
;
1642 return isl_space_is_equal(pw1
->dim
, pw2
->dim
);
1646 __isl_give PW
*FN(PW
,morph_domain
)(__isl_take PW
*pw
,
1647 __isl_take isl_morph
*morph
)
1655 ctx
= isl_space_get_ctx(pw
->dim
);
1656 isl_assert(ctx
, isl_space_is_domain_internal(morph
->dom
->dim
, pw
->dim
),
1659 pw
= FN(PW
,cow
)(pw
);
1662 pw
->dim
= isl_space_extend_domain_with_range(
1663 isl_space_copy(morph
->ran
->dim
), pw
->dim
);
1667 for (i
= 0; i
< pw
->n
; ++i
) {
1668 pw
->p
[i
].set
= isl_morph_set(isl_morph_copy(morph
), pw
->p
[i
].set
);
1671 pw
->p
[i
].FIELD
= FN(EL
,morph_domain
)(pw
->p
[i
].FIELD
,
1672 isl_morph_copy(morph
));
1673 if (!pw
->p
[i
].FIELD
)
1677 isl_morph_free(morph
);
1682 isl_morph_free(morph
);
1687 int FN(PW
,n_piece
)(__isl_keep PW
*pw
)
1689 return pw
? pw
->n
: 0;
1692 isl_stat
FN(PW
,foreach_piece
)(__isl_keep PW
*pw
,
1693 isl_stat (*fn
)(__isl_take isl_set
*set
, __isl_take EL
*el
, void *user
),
1699 return isl_stat_error
;
1701 for (i
= 0; i
< pw
->n
; ++i
)
1702 if (fn(isl_set_copy(pw
->p
[i
].set
),
1703 FN(EL
,copy
)(pw
->p
[i
].FIELD
), user
) < 0)
1704 return isl_stat_error
;
1710 static isl_bool
any_divs(__isl_keep isl_set
*set
)
1715 return isl_bool_error
;
1717 for (i
= 0; i
< set
->n
; ++i
)
1718 if (set
->p
[i
]->n_div
> 0)
1719 return isl_bool_true
;
1721 return isl_bool_false
;
1724 static isl_stat
foreach_lifted_subset(__isl_take isl_set
*set
,
1726 isl_stat (*fn
)(__isl_take isl_set
*set
, __isl_take EL
*el
,
1727 void *user
), void *user
)
1734 for (i
= 0; i
< set
->n
; ++i
) {
1738 lift
= isl_set_from_basic_set(isl_basic_set_copy(set
->p
[i
]));
1739 lift
= isl_set_lift(lift
);
1741 copy
= FN(EL
,copy
)(el
);
1742 copy
= FN(EL
,lift
)(copy
, isl_set_get_space(lift
));
1744 if (fn(lift
, copy
, user
) < 0)
1755 return isl_stat_error
;
1758 isl_stat
FN(PW
,foreach_lifted_piece
)(__isl_keep PW
*pw
,
1759 isl_stat (*fn
)(__isl_take isl_set
*set
, __isl_take EL
*el
,
1760 void *user
), void *user
)
1765 return isl_stat_error
;
1767 for (i
= 0; i
< pw
->n
; ++i
) {
1772 any
= any_divs(pw
->p
[i
].set
);
1774 return isl_stat_error
;
1775 set
= isl_set_copy(pw
->p
[i
].set
);
1776 el
= FN(EL
,copy
)(pw
->p
[i
].FIELD
);
1778 if (fn(set
, el
, user
) < 0)
1779 return isl_stat_error
;
1782 if (foreach_lifted_subset(set
, el
, fn
, user
) < 0)
1783 return isl_stat_error
;
1790 #ifndef NO_MOVE_DIMS
1791 __isl_give PW
*FN(PW
,move_dims
)(__isl_take PW
*pw
,
1792 enum isl_dim_type dst_type
, unsigned dst_pos
,
1793 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1797 pw
= FN(PW
,cow
)(pw
);
1801 pw
->dim
= isl_space_move_dims(pw
->dim
, dst_type
, dst_pos
, src_type
, src_pos
, n
);
1805 for (i
= 0; i
< pw
->n
; ++i
) {
1806 pw
->p
[i
].FIELD
= FN(EL
,move_dims
)(pw
->p
[i
].FIELD
,
1807 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1808 if (!pw
->p
[i
].FIELD
)
1812 if (dst_type
== isl_dim_in
)
1813 dst_type
= isl_dim_set
;
1814 if (src_type
== isl_dim_in
)
1815 src_type
= isl_dim_set
;
1817 for (i
= 0; i
< pw
->n
; ++i
) {
1818 pw
->p
[i
].set
= isl_set_move_dims(pw
->p
[i
].set
,
1820 src_type
, src_pos
, n
);
1832 __isl_give PW
*FN(PW
,mul_isl_int
)(__isl_take PW
*pw
, isl_int v
)
1836 if (isl_int_is_one(v
))
1838 if (pw
&& DEFAULT_IS_ZERO
&& isl_int_is_zero(v
)) {
1840 isl_space
*dim
= FN(PW
,get_space
)(pw
);
1842 zero
= FN(PW
,ZERO
)(dim
, pw
->type
);
1844 zero
= FN(PW
,ZERO
)(dim
);
1849 pw
= FN(PW
,cow
)(pw
);
1856 if (isl_int_is_neg(v
))
1857 pw
->type
= isl_fold_type_negate(pw
->type
);
1859 for (i
= 0; i
< pw
->n
; ++i
) {
1860 pw
->p
[i
].FIELD
= FN(EL
,scale
)(pw
->p
[i
].FIELD
, v
);
1861 if (!pw
->p
[i
].FIELD
)
1871 /* Multiply the pieces of "pw" by "v" and return the result.
1873 __isl_give PW
*FN(PW
,scale_val
)(__isl_take PW
*pw
, __isl_take isl_val
*v
)
1880 if (isl_val_is_one(v
)) {
1884 if (pw
&& DEFAULT_IS_ZERO
&& isl_val_is_zero(v
)) {
1886 isl_space
*space
= FN(PW
,get_space
)(pw
);
1888 zero
= FN(PW
,ZERO
)(space
, pw
->type
);
1890 zero
= FN(PW
,ZERO
)(space
);
1900 pw
= FN(PW
,cow
)(pw
);
1905 if (isl_val_is_neg(v
))
1906 pw
->type
= isl_fold_type_negate(pw
->type
);
1908 for (i
= 0; i
< pw
->n
; ++i
) {
1909 pw
->p
[i
].FIELD
= FN(EL
,scale_val
)(pw
->p
[i
].FIELD
,
1911 if (!pw
->p
[i
].FIELD
)
1923 /* Divide the pieces of "pw" by "v" and return the result.
1925 __isl_give PW
*FN(PW
,scale_down_val
)(__isl_take PW
*pw
, __isl_take isl_val
*v
)
1932 if (isl_val_is_one(v
)) {
1937 if (!isl_val_is_rat(v
))
1938 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1939 "expecting rational factor", goto error
);
1940 if (isl_val_is_zero(v
))
1941 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1942 "cannot scale down by zero", goto error
);
1948 pw
= FN(PW
,cow
)(pw
);
1953 if (isl_val_is_neg(v
))
1954 pw
->type
= isl_fold_type_negate(pw
->type
);
1956 for (i
= 0; i
< pw
->n
; ++i
) {
1957 pw
->p
[i
].FIELD
= FN(EL
,scale_down_val
)(pw
->p
[i
].FIELD
,
1959 if (!pw
->p
[i
].FIELD
)
1971 __isl_give PW
*FN(PW
,scale
)(__isl_take PW
*pw
, isl_int v
)
1973 return FN(PW
,mul_isl_int
)(pw
, v
);
1976 /* Apply some normalization to "pw".
1977 * In particular, sort the pieces according to their function value
1978 * expressions, combining pairs of adjacent pieces with
1979 * the same such expression, and then normalize the domains of the pieces.
1981 * We normalize in place, but if anything goes wrong we need
1982 * to return NULL, so we need to make sure we don't change the
1983 * meaning of any possible other copies of "pw".
1985 __isl_give PW
*FN(PW
,normalize
)(__isl_take PW
*pw
)
1990 pw
= FN(PW
,sort
)(pw
);
1993 for (i
= 0; i
< pw
->n
; ++i
) {
1994 set
= isl_set_normalize(isl_set_copy(pw
->p
[i
].set
));
1996 return FN(PW
,free
)(pw
);
1997 isl_set_free(pw
->p
[i
].set
);
2004 /* Is pw1 obviously equal to pw2?
2005 * That is, do they have obviously identical cells and obviously identical
2006 * elements on each cell?
2008 * If "pw1" or "pw2" contain any NaNs, then they are considered
2009 * not to be the same. A NaN is not equal to anything, not even
2012 isl_bool
FN(PW
,plain_is_equal
)(__isl_keep PW
*pw1
, __isl_keep PW
*pw2
)
2015 isl_bool equal
, has_nan
;
2018 return isl_bool_error
;
2020 has_nan
= FN(PW
,involves_nan
)(pw1
);
2021 if (has_nan
>= 0 && !has_nan
)
2022 has_nan
= FN(PW
,involves_nan
)(pw2
);
2023 if (has_nan
< 0 || has_nan
)
2024 return isl_bool_not(has_nan
);
2027 return isl_bool_true
;
2028 if (!isl_space_is_equal(pw1
->dim
, pw2
->dim
))
2029 return isl_bool_false
;
2031 pw1
= FN(PW
,copy
)(pw1
);
2032 pw2
= FN(PW
,copy
)(pw2
);
2033 pw1
= FN(PW
,normalize
)(pw1
);
2034 pw2
= FN(PW
,normalize
)(pw2
);
2038 equal
= pw1
->n
== pw2
->n
;
2039 for (i
= 0; equal
&& i
< pw1
->n
; ++i
) {
2040 equal
= isl_set_plain_is_equal(pw1
->p
[i
].set
, pw2
->p
[i
].set
);
2045 equal
= FN(EL
,plain_is_equal
)(pw1
->p
[i
].FIELD
, pw2
->p
[i
].FIELD
);
2056 return isl_bool_error
;
2059 /* Does "pw" involve any NaNs?
2061 isl_bool
FN(PW
,involves_nan
)(__isl_keep PW
*pw
)
2066 return isl_bool_error
;
2068 return isl_bool_false
;
2070 for (i
= 0; i
< pw
->n
; ++i
) {
2071 isl_bool has_nan
= FN(EL
,involves_nan
)(pw
->p
[i
].FIELD
);
2072 if (has_nan
< 0 || has_nan
)
2076 return isl_bool_false
;
2080 static __isl_give PW
*FN(PW
,align_params_pw_multi_aff_and
)(__isl_take PW
*pw
,
2081 __isl_take isl_multi_aff
*ma
,
2082 __isl_give PW
*(*fn
)(__isl_take PW
*pw
, __isl_take isl_multi_aff
*ma
))
2085 isl_bool equal_params
;
2086 isl_space
*ma_space
;
2088 ma_space
= isl_multi_aff_get_space(ma
);
2089 if (!pw
|| !ma
|| !ma_space
)
2091 equal_params
= isl_space_has_equal_params(pw
->dim
, ma_space
);
2092 if (equal_params
< 0)
2095 isl_space_free(ma_space
);
2098 ctx
= FN(PW
,get_ctx
)(pw
);
2099 if (FN(PW
,check_named_params
)(pw
) < 0)
2101 if (!isl_space_has_named_params(ma_space
))
2102 isl_die(ctx
, isl_error_invalid
,
2103 "unaligned unnamed parameters", goto error
);
2104 pw
= FN(PW
,align_params
)(pw
, ma_space
);
2105 ma
= isl_multi_aff_align_params(ma
, FN(PW
,get_space
)(pw
));
2108 isl_space_free(ma_space
);
2110 isl_multi_aff_free(ma
);
2114 static __isl_give PW
*FN(PW
,align_params_pw_pw_multi_aff_and
)(__isl_take PW
*pw
,
2115 __isl_take isl_pw_multi_aff
*pma
,
2116 __isl_give PW
*(*fn
)(__isl_take PW
*pw
,
2117 __isl_take isl_pw_multi_aff
*ma
))
2119 isl_bool equal_params
;
2120 isl_space
*pma_space
;
2122 pma_space
= isl_pw_multi_aff_get_space(pma
);
2123 if (!pw
|| !pma
|| !pma_space
)
2125 equal_params
= isl_space_has_equal_params(pw
->dim
, pma_space
);
2126 if (equal_params
< 0)
2129 isl_space_free(pma_space
);
2132 if (FN(PW
,check_named_params
)(pw
) < 0 ||
2133 isl_pw_multi_aff_check_named_params(pma
) < 0)
2135 pw
= FN(PW
,align_params
)(pw
, pma_space
);
2136 pma
= isl_pw_multi_aff_align_params(pma
, FN(PW
,get_space
)(pw
));
2139 isl_space_free(pma_space
);
2141 isl_pw_multi_aff_free(pma
);
2145 /* Compute the pullback of "pw" by the function represented by "ma".
2146 * In other words, plug in "ma" in "pw".
2148 static __isl_give PW
*FN(PW
,pullback_multi_aff_aligned
)(__isl_take PW
*pw
,
2149 __isl_take isl_multi_aff
*ma
)
2152 isl_space
*space
= NULL
;
2154 ma
= isl_multi_aff_align_divs(ma
);
2155 pw
= FN(PW
,cow
)(pw
);
2159 space
= isl_space_join(isl_multi_aff_get_space(ma
),
2160 FN(PW
,get_space
)(pw
));
2162 for (i
= 0; i
< pw
->n
; ++i
) {
2163 pw
->p
[i
].set
= isl_set_preimage_multi_aff(pw
->p
[i
].set
,
2164 isl_multi_aff_copy(ma
));
2167 pw
->p
[i
].FIELD
= FN(EL
,pullback_multi_aff
)(pw
->p
[i
].FIELD
,
2168 isl_multi_aff_copy(ma
));
2169 if (!pw
->p
[i
].FIELD
)
2173 pw
= FN(PW
,reset_space
)(pw
, space
);
2174 isl_multi_aff_free(ma
);
2177 isl_space_free(space
);
2178 isl_multi_aff_free(ma
);
2183 __isl_give PW
*FN(PW
,pullback_multi_aff
)(__isl_take PW
*pw
,
2184 __isl_take isl_multi_aff
*ma
)
2186 return FN(PW
,align_params_pw_multi_aff_and
)(pw
, ma
,
2187 &FN(PW
,pullback_multi_aff_aligned
));
2190 /* Compute the pullback of "pw" by the function represented by "pma".
2191 * In other words, plug in "pma" in "pw".
2193 static __isl_give PW
*FN(PW
,pullback_pw_multi_aff_aligned
)(__isl_take PW
*pw
,
2194 __isl_take isl_pw_multi_aff
*pma
)
2204 space
= isl_space_join(isl_pw_multi_aff_get_space(pma
),
2205 FN(PW
,get_space
)(pw
));
2206 isl_pw_multi_aff_free(pma
);
2207 res
= FN(PW
,empty
)(space
);
2212 res
= FN(PW
,pullback_multi_aff
)(FN(PW
,copy
)(pw
),
2213 isl_multi_aff_copy(pma
->p
[0].maff
));
2214 res
= FN(PW
,intersect_domain
)(res
, isl_set_copy(pma
->p
[0].set
));
2216 for (i
= 1; i
< pma
->n
; ++i
) {
2219 res_i
= FN(PW
,pullback_multi_aff
)(FN(PW
,copy
)(pw
),
2220 isl_multi_aff_copy(pma
->p
[i
].maff
));
2221 res_i
= FN(PW
,intersect_domain
)(res_i
,
2222 isl_set_copy(pma
->p
[i
].set
));
2223 res
= FN(PW
,add_disjoint
)(res
, res_i
);
2226 isl_pw_multi_aff_free(pma
);
2230 isl_pw_multi_aff_free(pma
);
2235 __isl_give PW
*FN(PW
,pullback_pw_multi_aff
)(__isl_take PW
*pw
,
2236 __isl_take isl_pw_multi_aff
*pma
)
2238 return FN(PW
,align_params_pw_pw_multi_aff_and
)(pw
, pma
,
2239 &FN(PW
,pullback_pw_multi_aff_aligned
));