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
16 #include <isl_val_private.h>
18 #include <isl_pw_macro.h>
21 __isl_give PW
*FN(PW
,alloc_size
)(__isl_take isl_space
*dim
,
22 enum isl_fold type
, int n
)
24 __isl_give PW
*FN(PW
,alloc_size
)(__isl_take isl_space
*dim
, int n
)
32 ctx
= isl_space_get_ctx(dim
);
33 isl_assert(ctx
, n
>= 0, goto error
);
34 pw
= isl_alloc(ctx
, struct PW
,
35 sizeof(struct PW
) + (n
- 1) * sizeof(S(PW
,piece
)));
53 __isl_give PW
*FN(PW
,ZERO
)(__isl_take isl_space
*dim
, enum isl_fold type
)
55 return FN(PW
,alloc_size
)(dim
, type
, 0);
58 __isl_give PW
*FN(PW
,ZERO
)(__isl_take isl_space
*dim
)
60 return FN(PW
,alloc_size
)(dim
, 0);
64 __isl_give PW
*FN(PW
,add_piece
)(__isl_take PW
*pw
,
65 __isl_take isl_set
*set
, __isl_take EL
*el
)
68 isl_space
*el_dim
= NULL
;
70 if (!pw
|| !set
|| !el
)
73 if (isl_set_plain_is_empty(set
) || FN(EL
,EL_IS_ZERO
)(el
)) {
79 ctx
= isl_set_get_ctx(set
);
81 if (pw
->type
!= el
->type
)
82 isl_die(ctx
, isl_error_invalid
, "fold types don't match",
85 el_dim
= FN(EL
,get_space(el
));
86 isl_assert(ctx
, isl_space_is_equal(pw
->dim
, el_dim
), goto error
);
87 isl_assert(ctx
, pw
->n
< pw
->size
, goto error
);
89 pw
->p
[pw
->n
].set
= set
;
90 pw
->p
[pw
->n
].FIELD
= el
;
93 isl_space_free(el_dim
);
96 isl_space_free(el_dim
);
103 /* Does the space of "set" correspond to that of the domain of "el".
105 static isl_bool
FN(PW
,compatible_domain
)(__isl_keep EL
*el
,
106 __isl_keep isl_set
*set
)
109 isl_space
*el_space
, *set_space
;
112 return isl_bool_error
;
113 set_space
= isl_set_get_space(set
);
114 el_space
= FN(EL
,get_space
)(el
);
115 ok
= isl_space_is_domain_internal(set_space
, el_space
);
116 isl_space_free(el_space
);
117 isl_space_free(set_space
);
121 /* Check that the space of "set" corresponds to that of the domain of "el".
123 static isl_stat
FN(PW
,check_compatible_domain
)(__isl_keep EL
*el
,
124 __isl_keep isl_set
*set
)
128 ok
= FN(PW
,compatible_domain
)(el
, set
);
130 return isl_stat_error
;
132 isl_die(isl_set_get_ctx(set
), isl_error_invalid
,
133 "incompatible spaces", return isl_stat_error
);
139 __isl_give PW
*FN(PW
,alloc
)(enum isl_fold type
,
140 __isl_take isl_set
*set
, __isl_take EL
*el
)
142 __isl_give PW
*FN(PW
,alloc
)(__isl_take isl_set
*set
, __isl_take EL
*el
)
147 if (FN(PW
,check_compatible_domain
)(el
, set
) < 0)
151 pw
= FN(PW
,alloc_size
)(FN(EL
,get_space
)(el
), type
, 1);
153 pw
= FN(PW
,alloc_size
)(FN(EL
,get_space
)(el
), 1);
156 return FN(PW
,add_piece
)(pw
, set
, el
);
163 __isl_give PW
*FN(PW
,dup
)(__isl_keep PW
*pw
)
172 dup
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), pw
->type
, pw
->n
);
174 dup
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), pw
->n
);
179 for (i
= 0; i
< pw
->n
; ++i
)
180 dup
= FN(PW
,add_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 const char *FN(PW
,get_dim_name
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
228 return pw
? isl_space_get_dim_name(pw
->dim
, type
, pos
) : NULL
;
231 isl_bool
FN(PW
,has_dim_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
234 return pw
? isl_space_has_dim_id(pw
->dim
, type
, pos
) : isl_bool_error
;
237 __isl_give isl_id
*FN(PW
,get_dim_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
240 return pw
? isl_space_get_dim_id(pw
->dim
, type
, pos
) : NULL
;
243 isl_bool
FN(PW
,has_tuple_name
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
245 return pw
? isl_space_has_tuple_name(pw
->dim
, type
) : isl_bool_error
;
248 const char *FN(PW
,get_tuple_name
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
250 return pw
? isl_space_get_tuple_name(pw
->dim
, type
) : NULL
;
253 isl_bool
FN(PW
,has_tuple_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
255 return pw
? isl_space_has_tuple_id(pw
->dim
, type
) : isl_bool_error
;
258 __isl_give isl_id
*FN(PW
,get_tuple_id
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
260 return pw
? isl_space_get_tuple_id(pw
->dim
, type
) : NULL
;
263 isl_bool
FN(PW
,IS_ZERO
)(__isl_keep PW
*pw
)
266 return isl_bool_error
;
272 __isl_give PW
*FN(PW
,realign_domain
)(__isl_take PW
*pw
,
273 __isl_take isl_reordering
*exp
)
281 for (i
= 0; i
< pw
->n
; ++i
) {
282 pw
->p
[i
].set
= isl_set_realign(pw
->p
[i
].set
,
283 isl_reordering_copy(exp
));
286 pw
->p
[i
].FIELD
= FN(EL
,realign_domain
)(pw
->p
[i
].FIELD
,
287 isl_reordering_copy(exp
));
292 pw
= FN(PW
,reset_domain_space
)(pw
, isl_space_copy(exp
->dim
));
294 isl_reordering_free(exp
);
297 isl_reordering_free(exp
);
302 /* Align the parameters of "pw" to those of "model".
304 __isl_give PW
*FN(PW
,align_params
)(__isl_take PW
*pw
, __isl_take isl_space
*model
)
307 isl_bool equal_params
;
312 ctx
= isl_space_get_ctx(model
);
313 if (!isl_space_has_named_params(model
))
314 isl_die(ctx
, isl_error_invalid
,
315 "model has unnamed parameters", goto error
);
316 if (!isl_space_has_named_params(pw
->dim
))
317 isl_die(ctx
, isl_error_invalid
,
318 "input has unnamed parameters", goto error
);
319 equal_params
= isl_space_has_equal_params(pw
->dim
, model
);
320 if (equal_params
< 0)
325 model
= isl_space_drop_dims(model
, isl_dim_in
,
326 0, isl_space_dim(model
, isl_dim_in
));
327 model
= isl_space_drop_dims(model
, isl_dim_out
,
328 0, isl_space_dim(model
, isl_dim_out
));
329 exp
= isl_parameter_alignment_reordering(pw
->dim
, model
);
330 exp
= isl_reordering_extend_space(exp
,
331 FN(PW
,get_domain_space
)(pw
));
332 pw
= FN(PW
,realign_domain
)(pw
, exp
);
335 isl_space_free(model
);
338 isl_space_free(model
);
343 static __isl_give PW
*FN(PW
,align_params_pw_pw_and
)(__isl_take PW
*pw1
,
345 __isl_give PW
*(*fn
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
))
348 isl_bool equal_params
;
352 equal_params
= isl_space_has_equal_params(pw1
->dim
, pw2
->dim
);
353 if (equal_params
< 0)
357 ctx
= FN(PW
,get_ctx
)(pw1
);
358 if (!isl_space_has_named_params(pw1
->dim
) ||
359 !isl_space_has_named_params(pw2
->dim
))
360 isl_die(ctx
, isl_error_invalid
,
361 "unaligned unnamed parameters", goto error
);
362 pw1
= FN(PW
,align_params
)(pw1
, FN(PW
,get_space
)(pw2
));
363 pw2
= FN(PW
,align_params
)(pw2
, FN(PW
,get_space
)(pw1
));
371 static __isl_give PW
*FN(PW
,align_params_pw_set_and
)(__isl_take PW
*pw
,
372 __isl_take isl_set
*set
,
373 __isl_give PW
*(*fn
)(__isl_take PW
*pw
, __isl_take isl_set
*set
))
380 aligned
= isl_set_space_has_equal_params(set
, pw
->dim
);
385 ctx
= FN(PW
,get_ctx
)(pw
);
386 if (!isl_space_has_named_params(pw
->dim
) ||
387 !isl_space_has_named_params(set
->dim
))
388 isl_die(ctx
, isl_error_invalid
,
389 "unaligned unnamed parameters", goto error
);
390 pw
= FN(PW
,align_params
)(pw
, isl_set_get_space(set
));
391 set
= isl_set_align_params(set
, FN(PW
,get_space
)(pw
));
400 static __isl_give PW
*FN(PW
,union_add_aligned
)(__isl_take PW
*pw1
,
411 ctx
= isl_space_get_ctx(pw1
->dim
);
413 if (pw1
->type
!= pw2
->type
)
414 isl_die(ctx
, isl_error_invalid
,
415 "fold types don't match", goto error
);
417 isl_assert(ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
419 if (FN(PW
,IS_ZERO
)(pw1
)) {
424 if (FN(PW
,IS_ZERO
)(pw2
)) {
429 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
431 res
= FN(PW
,alloc_size
)(isl_space_copy(pw1
->dim
), pw1
->type
, n
);
433 res
= FN(PW
,alloc_size
)(isl_space_copy(pw1
->dim
), n
);
436 for (i
= 0; i
< pw1
->n
; ++i
) {
437 set
= isl_set_copy(pw1
->p
[i
].set
);
438 for (j
= 0; j
< pw2
->n
; ++j
) {
439 struct isl_set
*common
;
441 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
442 isl_set_copy(pw2
->p
[j
].set
));
443 if (isl_set_plain_is_empty(common
)) {
444 isl_set_free(common
);
447 set
= isl_set_subtract(set
,
448 isl_set_copy(pw2
->p
[j
].set
));
450 sum
= FN(EL
,add_on_domain
)(common
,
451 FN(EL
,copy
)(pw1
->p
[i
].FIELD
),
452 FN(EL
,copy
)(pw2
->p
[j
].FIELD
));
454 res
= FN(PW
,add_piece
)(res
, common
, sum
);
456 res
= FN(PW
,add_piece
)(res
, set
, FN(EL
,copy
)(pw1
->p
[i
].FIELD
));
459 for (j
= 0; j
< pw2
->n
; ++j
) {
460 set
= isl_set_copy(pw2
->p
[j
].set
);
461 for (i
= 0; i
< pw1
->n
; ++i
)
462 set
= isl_set_subtract(set
,
463 isl_set_copy(pw1
->p
[i
].set
));
464 res
= FN(PW
,add_piece
)(res
, set
, FN(EL
,copy
)(pw2
->p
[j
].FIELD
));
477 /* Private version of "union_add". For isl_pw_qpolynomial and
478 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
480 static __isl_give PW
*FN(PW
,union_add_
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
)
482 return FN(PW
,align_params_pw_pw_and
)(pw1
, pw2
,
483 &FN(PW
,union_add_aligned
));
486 /* Make sure "pw" has room for at least "n" more pieces.
488 * If there is only one reference to pw, we extend it in place.
489 * Otherwise, we create a new PW and copy the pieces.
491 static __isl_give PW
*FN(PW
,grow
)(__isl_take PW
*pw
, int n
)
499 if (pw
->n
+ n
<= pw
->size
)
501 ctx
= FN(PW
,get_ctx
)(pw
);
504 res
= isl_realloc(ctx
, pw
, struct PW
,
505 sizeof(struct PW
) + (n
- 1) * sizeof(S(PW
,piece
)));
507 return FN(PW
,free
)(pw
);
512 res
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), pw
->type
, n
);
514 res
= FN(PW
,alloc_size
)(isl_space_copy(pw
->dim
), n
);
517 return FN(PW
,free
)(pw
);
518 for (i
= 0; i
< pw
->n
; ++i
)
519 res
= FN(PW
,add_piece
)(res
, isl_set_copy(pw
->p
[i
].set
),
520 FN(EL
,copy
)(pw
->p
[i
].FIELD
));
525 static __isl_give PW
*FN(PW
,add_disjoint_aligned
)(__isl_take PW
*pw1
,
534 if (pw1
->size
< pw1
->n
+ pw2
->n
&& pw1
->n
< pw2
->n
)
535 return FN(PW
,add_disjoint_aligned
)(pw2
, pw1
);
537 ctx
= isl_space_get_ctx(pw1
->dim
);
539 if (pw1
->type
!= pw2
->type
)
540 isl_die(ctx
, isl_error_invalid
,
541 "fold types don't match", goto error
);
543 isl_assert(ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
545 if (FN(PW
,IS_ZERO
)(pw1
)) {
550 if (FN(PW
,IS_ZERO
)(pw2
)) {
555 pw1
= FN(PW
,grow
)(pw1
, pw2
->n
);
559 for (i
= 0; i
< pw2
->n
; ++i
)
560 pw1
= FN(PW
,add_piece
)(pw1
,
561 isl_set_copy(pw2
->p
[i
].set
),
562 FN(EL
,copy
)(pw2
->p
[i
].FIELD
));
573 __isl_give PW
*FN(PW
,add_disjoint
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
)
575 return FN(PW
,align_params_pw_pw_and
)(pw1
, pw2
,
576 &FN(PW
,add_disjoint_aligned
));
579 /* This function is currently only used from isl_aff.c
581 static __isl_give PW
*FN(PW
,on_shared_domain_in
)(__isl_take PW
*pw1
,
582 __isl_take PW
*pw2
, __isl_take isl_space
*space
,
583 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
584 __attribute__ ((unused
));
586 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
587 * The result of "fn" (and therefore also of this function) lives in "space".
589 static __isl_give PW
*FN(PW
,on_shared_domain_in
)(__isl_take PW
*pw1
,
590 __isl_take PW
*pw2
, __isl_take isl_space
*space
,
591 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
601 res
= FN(PW
,alloc_size
)(isl_space_copy(space
), pw1
->type
, n
);
603 res
= FN(PW
,alloc_size
)(isl_space_copy(space
), n
);
606 for (i
= 0; i
< pw1
->n
; ++i
) {
607 for (j
= 0; j
< pw2
->n
; ++j
) {
612 common
= isl_set_intersect(
613 isl_set_copy(pw1
->p
[i
].set
),
614 isl_set_copy(pw2
->p
[j
].set
));
615 empty
= isl_set_plain_is_empty(common
);
616 if (empty
< 0 || empty
) {
617 isl_set_free(common
);
623 res_ij
= fn(FN(EL
,copy
)(pw1
->p
[i
].FIELD
),
624 FN(EL
,copy
)(pw2
->p
[j
].FIELD
));
625 res_ij
= FN(EL
,gist
)(res_ij
, isl_set_copy(common
));
627 res
= FN(PW
,add_piece
)(res
, common
, res_ij
);
631 isl_space_free(space
);
636 isl_space_free(space
);
643 /* This function is currently only used from isl_aff.c
645 static __isl_give PW
*FN(PW
,on_shared_domain
)(__isl_take PW
*pw1
,
647 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
648 __attribute__ ((unused
));
650 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
651 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
653 static __isl_give PW
*FN(PW
,on_shared_domain
)(__isl_take PW
*pw1
,
655 __isl_give EL
*(*fn
)(__isl_take EL
*el1
, __isl_take EL
*el2
))
662 space
= isl_space_copy(pw1
->dim
);
663 return FN(PW
,on_shared_domain_in
)(pw1
, pw2
, space
, fn
);
671 __isl_give PW
*FN(PW
,neg
)(__isl_take PW
*pw
)
678 if (FN(PW
,IS_ZERO
)(pw
))
685 for (i
= 0; i
< pw
->n
; ++i
) {
686 pw
->p
[i
].FIELD
= FN(EL
,neg
)(pw
->p
[i
].FIELD
);
688 return FN(PW
,free
)(pw
);
696 __isl_give PW
*FN(PW
,sub
)(__isl_take PW
*pw1
, __isl_take PW
*pw2
)
698 return FN(PW
,add
)(pw1
, FN(PW
,neg
)(pw2
));
703 /* Evaluate "pw" in the void point "pnt".
704 * In particular, return the value NaN.
706 static __isl_give isl_val
*FN(PW
,eval_void
)(__isl_take PW
*pw
,
707 __isl_take isl_point
*pnt
)
711 ctx
= isl_point_get_ctx(pnt
);
714 return isl_val_nan(ctx
);
717 __isl_give isl_val
*FN(PW
,eval
)(__isl_take PW
*pw
, __isl_take isl_point
*pnt
)
723 isl_space
*pnt_dim
= NULL
;
728 ctx
= isl_point_get_ctx(pnt
);
729 pnt_dim
= isl_point_get_space(pnt
);
730 isl_assert(ctx
, isl_space_is_domain_internal(pnt_dim
, pw
->dim
),
732 is_void
= isl_point_is_void(pnt
);
736 return FN(PW
,eval_void
)(pw
, pnt
);
738 found
= isl_bool_false
;
739 for (i
= 0; i
< pw
->n
; ++i
) {
740 found
= isl_set_contains_point(pw
->p
[i
].set
, pnt
);
747 v
= FN(EL
,eval
)(FN(EL
,copy
)(pw
->p
[i
].FIELD
),
748 isl_point_copy(pnt
));
750 v
= isl_val_zero(ctx
);
752 isl_space_free(pnt_dim
);
757 isl_space_free(pnt_dim
);
763 /* Return the parameter domain of "pw".
765 __isl_give isl_set
*FN(PW
,params
)(__isl_take PW
*pw
)
767 return isl_set_params(FN(PW
,domain
)(pw
));
770 __isl_give isl_set
*FN(PW
,domain
)(__isl_take PW
*pw
)
778 dom
= isl_set_empty(FN(PW
,get_domain_space
)(pw
));
779 for (i
= 0; i
< pw
->n
; ++i
)
780 dom
= isl_set_union_disjoint(dom
, isl_set_copy(pw
->p
[i
].set
));
787 /* Exploit the equalities in the domain of piece "i" of "pw"
788 * to simplify the associated function.
789 * If the domain of piece "i" is empty, then remove it entirely,
790 * replacing it with the final piece.
792 static int FN(PW
,exploit_equalities_and_remove_if_empty
)(__isl_keep PW
*pw
,
796 int empty
= isl_set_plain_is_empty(pw
->p
[i
].set
);
801 isl_set_free(pw
->p
[i
].set
);
802 FN(EL
,free
)(pw
->p
[i
].FIELD
);
804 pw
->p
[i
] = pw
->p
[pw
->n
- 1];
810 aff
= isl_set_affine_hull(isl_set_copy(pw
->p
[i
].set
));
811 pw
->p
[i
].FIELD
= FN(EL
,substitute_equalities
)(pw
->p
[i
].FIELD
, aff
);
818 /* Convert a piecewise expression defined over a parameter domain
819 * into one that is defined over a zero-dimensional set.
821 __isl_give PW
*FN(PW
,from_range
)(__isl_take PW
*pw
)
827 if (!isl_space_is_set(pw
->dim
))
828 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
829 "not living in a set space", return FN(PW
,free
)(pw
));
831 space
= FN(PW
,get_space
)(pw
);
832 space
= isl_space_from_range(space
);
833 pw
= FN(PW
,reset_space
)(pw
, space
);
838 /* Fix the value of the given parameter or domain dimension of "pw"
839 * to be equal to "value".
841 __isl_give PW
*FN(PW
,fix_si
)(__isl_take PW
*pw
, enum isl_dim_type type
,
842 unsigned pos
, int value
)
849 if (type
== isl_dim_out
)
850 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
851 "cannot fix output dimension", return FN(PW
,free
)(pw
));
856 if (type
== isl_dim_in
)
861 return FN(PW
,free
)(pw
);
863 for (i
= pw
->n
- 1; i
>= 0; --i
) {
864 pw
->p
[i
].set
= isl_set_fix_si(pw
->p
[i
].set
, type
, pos
, value
);
865 if (FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
) < 0)
866 return FN(PW
,free
)(pw
);
872 /* Restrict the domain of "pw" by combining each cell
873 * with "set" through a call to "fn", where "fn" may be
874 * isl_set_intersect, isl_set_intersect_params or isl_set_subtract.
876 static __isl_give PW
*FN(PW
,restrict_domain_aligned
)(__isl_take PW
*pw
,
877 __isl_take isl_set
*set
,
878 __isl_give isl_set
*(*fn
)(__isl_take isl_set
*set1
,
879 __isl_take isl_set
*set2
))
895 for (i
= pw
->n
- 1; i
>= 0; --i
) {
896 pw
->p
[i
].set
= fn(pw
->p
[i
].set
, isl_set_copy(set
));
897 if (FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
) < 0)
909 static __isl_give PW
*FN(PW
,intersect_domain_aligned
)(__isl_take PW
*pw
,
910 __isl_take isl_set
*set
)
912 return FN(PW
,restrict_domain_aligned
)(pw
, set
, &isl_set_intersect
);
915 __isl_give PW
*FN(PW
,intersect_domain
)(__isl_take PW
*pw
,
916 __isl_take isl_set
*context
)
918 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
919 &FN(PW
,intersect_domain_aligned
));
922 static __isl_give PW
*FN(PW
,intersect_params_aligned
)(__isl_take PW
*pw
,
923 __isl_take isl_set
*set
)
925 return FN(PW
,restrict_domain_aligned
)(pw
, set
,
926 &isl_set_intersect_params
);
929 /* Intersect the domain of "pw" with the parameter domain "context".
931 __isl_give PW
*FN(PW
,intersect_params
)(__isl_take PW
*pw
,
932 __isl_take isl_set
*context
)
934 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
935 &FN(PW
,intersect_params_aligned
));
938 /* Subtract "domain' from the domain of "pw", assuming their
939 * parameters have been aligned.
941 static __isl_give PW
*FN(PW
,subtract_domain_aligned
)(__isl_take PW
*pw
,
942 __isl_take isl_set
*domain
)
944 return FN(PW
,restrict_domain_aligned
)(pw
, domain
, &isl_set_subtract
);
947 /* Subtract "domain' from the domain of "pw".
949 __isl_give PW
*FN(PW
,subtract_domain
)(__isl_take PW
*pw
,
950 __isl_take isl_set
*domain
)
952 return FN(PW
,align_params_pw_set_and
)(pw
, domain
,
953 &FN(PW
,subtract_domain_aligned
));
956 /* Compute the gist of "pw" with respect to the domain constraints
957 * of "context" for the case where the domain of the last element
958 * of "pw" is equal to "context".
959 * Call "fn_el" to compute the gist of this element, replace
960 * its domain by the universe and drop all other elements
961 * as their domains are necessarily disjoint from "context".
963 static __isl_give PW
*FN(PW
,gist_last
)(__isl_take PW
*pw
,
964 __isl_take isl_set
*context
,
965 __isl_give EL
*(*fn_el
)(__isl_take EL
*el
, __isl_take isl_set
*set
))
970 for (i
= 0; i
< pw
->n
- 1; ++i
) {
971 isl_set_free(pw
->p
[i
].set
);
972 FN(EL
,free
)(pw
->p
[i
].FIELD
);
974 pw
->p
[0].FIELD
= pw
->p
[pw
->n
- 1].FIELD
;
975 pw
->p
[0].set
= pw
->p
[pw
->n
- 1].set
;
978 space
= isl_set_get_space(context
);
979 pw
->p
[0].FIELD
= fn_el(pw
->p
[0].FIELD
, context
);
980 context
= isl_set_universe(space
);
981 isl_set_free(pw
->p
[0].set
);
982 pw
->p
[0].set
= context
;
984 if (!pw
->p
[0].FIELD
|| !pw
->p
[0].set
)
985 return FN(PW
,free
)(pw
);
990 /* Compute the gist of "pw" with respect to the domain constraints
991 * of "context". Call "fn_el" to compute the gist of the elements
992 * and "fn_dom" to compute the gist of the domains.
994 * If the piecewise expression is empty or the context is the universe,
995 * then nothing can be simplified.
997 static __isl_give PW
*FN(PW
,gist_aligned
)(__isl_take PW
*pw
,
998 __isl_take isl_set
*context
,
999 __isl_give EL
*(*fn_el
)(__isl_take EL
*el
,
1000 __isl_take isl_set
*set
),
1001 __isl_give isl_set
*(*fn_dom
)(__isl_take isl_set
*set
,
1002 __isl_take isl_basic_set
*bset
))
1007 isl_basic_set
*hull
= NULL
;
1009 if (!pw
|| !context
)
1013 isl_set_free(context
);
1017 is_universe
= isl_set_plain_is_universe(context
);
1018 if (is_universe
< 0)
1021 isl_set_free(context
);
1025 aligned
= isl_set_space_has_equal_params(context
, pw
->dim
);
1029 pw
= FN(PW
,align_params
)(pw
, isl_set_get_space(context
));
1030 context
= isl_set_align_params(context
, FN(PW
,get_space
)(pw
));
1033 pw
= FN(PW
,cow
)(pw
);
1040 equal
= isl_set_plain_is_equal(pw
->p
[0].set
, context
);
1044 return FN(PW
,gist_last
)(pw
, context
, fn_el
);
1047 context
= isl_set_compute_divs(context
);
1048 hull
= isl_set_simple_hull(isl_set_copy(context
));
1050 for (i
= pw
->n
- 1; i
>= 0; --i
) {
1054 if (i
== pw
->n
- 1) {
1056 equal
= isl_set_plain_is_equal(pw
->p
[i
].set
, context
);
1060 isl_basic_set_free(hull
);
1061 return FN(PW
,gist_last
)(pw
, context
, fn_el
);
1064 set_i
= isl_set_intersect(isl_set_copy(pw
->p
[i
].set
),
1065 isl_set_copy(context
));
1066 empty
= isl_set_plain_is_empty(set_i
);
1067 pw
->p
[i
].FIELD
= fn_el(pw
->p
[i
].FIELD
, set_i
);
1068 pw
->p
[i
].set
= fn_dom(pw
->p
[i
].set
, isl_basic_set_copy(hull
));
1069 if (empty
< 0 || !pw
->p
[i
].FIELD
|| !pw
->p
[i
].set
)
1072 isl_set_free(pw
->p
[i
].set
);
1073 FN(EL
,free
)(pw
->p
[i
].FIELD
);
1075 pw
->p
[i
] = pw
->p
[pw
->n
- 1];
1080 isl_basic_set_free(hull
);
1081 isl_set_free(context
);
1086 isl_basic_set_free(hull
);
1087 isl_set_free(context
);
1091 static __isl_give PW
*FN(PW
,gist_domain_aligned
)(__isl_take PW
*pw
,
1092 __isl_take isl_set
*set
)
1094 return FN(PW
,gist_aligned
)(pw
, set
, &FN(EL
,gist
),
1095 &isl_set_gist_basic_set
);
1098 __isl_give PW
*FN(PW
,gist
)(__isl_take PW
*pw
, __isl_take isl_set
*context
)
1100 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
1101 &FN(PW
,gist_domain_aligned
));
1104 static __isl_give PW
*FN(PW
,gist_params_aligned
)(__isl_take PW
*pw
,
1105 __isl_take isl_set
*set
)
1107 return FN(PW
,gist_aligned
)(pw
, set
, &FN(EL
,gist_params
),
1108 &isl_set_gist_params_basic_set
);
1111 __isl_give PW
*FN(PW
,gist_params
)(__isl_take PW
*pw
,
1112 __isl_take isl_set
*context
)
1114 return FN(PW
,align_params_pw_set_and
)(pw
, context
,
1115 &FN(PW
,gist_params_aligned
));
1118 /* Return -1 if the piece "p1" should be sorted before "p2"
1119 * and 1 if it should be sorted after "p2".
1120 * Return 0 if they do not need to be sorted in a specific order.
1122 * The two pieces are compared on the basis of their function value expressions.
1124 static int FN(PW
,sort_field_cmp
)(const void *p1
, const void *p2
, void *arg
)
1126 struct FN(PW
,piece
) const *pc1
= p1
;
1127 struct FN(PW
,piece
) const *pc2
= p2
;
1129 return FN(EL
,plain_cmp
)(pc1
->FIELD
, pc2
->FIELD
);
1132 /* Sort the pieces of "pw" according to their function value
1133 * expressions and then combine pairs of adjacent pieces with
1134 * the same such expression.
1136 * The sorting is performed in place because it does not
1137 * change the meaning of "pw", but care needs to be
1138 * taken not to change any possible other copies of "pw"
1139 * in case anything goes wrong.
1141 __isl_give PW
*FN(PW
,sort
)(__isl_take PW
*pw
)
1150 if (isl_sort(pw
->p
, pw
->n
, sizeof(pw
->p
[0]),
1151 &FN(PW
,sort_field_cmp
), NULL
) < 0)
1152 return FN(PW
,free
)(pw
);
1153 for (i
= pw
->n
- 1; i
>= 1; --i
) {
1154 if (!FN(EL
,plain_is_equal
)(pw
->p
[i
- 1].FIELD
, pw
->p
[i
].FIELD
))
1156 set
= isl_set_union(isl_set_copy(pw
->p
[i
- 1].set
),
1157 isl_set_copy(pw
->p
[i
].set
));
1159 return FN(PW
,free
)(pw
);
1160 isl_set_free(pw
->p
[i
].set
);
1161 FN(EL
,free
)(pw
->p
[i
].FIELD
);
1162 isl_set_free(pw
->p
[i
- 1].set
);
1163 pw
->p
[i
- 1].set
= set
;
1164 for (j
= i
+ 1; j
< pw
->n
; ++j
)
1165 pw
->p
[j
- 1] = pw
->p
[j
];
1172 /* Coalesce the domains of "pw".
1174 * Prior to the actual coalescing, first sort the pieces such that
1175 * pieces with the same function value expression are combined
1176 * into a single piece, the combined domain of which can then
1179 __isl_give PW
*FN(PW
,coalesce
)(__isl_take PW
*pw
)
1183 pw
= FN(PW
,sort
)(pw
);
1187 for (i
= 0; i
< pw
->n
; ++i
) {
1188 pw
->p
[i
].set
= isl_set_coalesce(pw
->p
[i
].set
);
1199 isl_ctx
*FN(PW
,get_ctx
)(__isl_keep PW
*pw
)
1201 return pw
? isl_space_get_ctx(pw
->dim
) : NULL
;
1204 #ifndef NO_INVOLVES_DIMS
1205 isl_bool
FN(PW
,involves_dims
)(__isl_keep PW
*pw
, enum isl_dim_type type
,
1206 unsigned first
, unsigned n
)
1209 enum isl_dim_type set_type
;
1212 return isl_bool_error
;
1213 if (pw
->n
== 0 || n
== 0)
1214 return isl_bool_false
;
1216 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1218 for (i
= 0; i
< pw
->n
; ++i
) {
1219 isl_bool involves
= FN(EL
,involves_dims
)(pw
->p
[i
].FIELD
,
1221 if (involves
< 0 || involves
)
1223 involves
= isl_set_involves_dims(pw
->p
[i
].set
,
1224 set_type
, first
, n
);
1225 if (involves
< 0 || involves
)
1228 return isl_bool_false
;
1232 __isl_give PW
*FN(PW
,set_dim_name
)(__isl_take PW
*pw
,
1233 enum isl_dim_type type
, unsigned pos
, const char *s
)
1236 enum isl_dim_type set_type
;
1238 pw
= FN(PW
,cow
)(pw
);
1242 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1244 pw
->dim
= isl_space_set_dim_name(pw
->dim
, type
, pos
, s
);
1248 for (i
= 0; i
< pw
->n
; ++i
) {
1249 pw
->p
[i
].set
= isl_set_set_dim_name(pw
->p
[i
].set
,
1253 pw
->p
[i
].FIELD
= FN(EL
,set_dim_name
)(pw
->p
[i
].FIELD
, type
, pos
, s
);
1254 if (!pw
->p
[i
].FIELD
)
1264 #ifndef NO_DROP_DIMS
1265 __isl_give PW
*FN(PW
,drop_dims
)(__isl_take PW
*pw
,
1266 enum isl_dim_type type
, unsigned first
, unsigned n
)
1269 enum isl_dim_type set_type
;
1273 if (n
== 0 && !isl_space_get_tuple_name(pw
->dim
, type
))
1276 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1278 pw
= FN(PW
,cow
)(pw
);
1281 pw
->dim
= isl_space_drop_dims(pw
->dim
, type
, first
, n
);
1284 for (i
= 0; i
< pw
->n
; ++i
) {
1285 pw
->p
[i
].FIELD
= FN(EL
,drop_dims
)(pw
->p
[i
].FIELD
, type
, first
, n
);
1286 if (!pw
->p
[i
].FIELD
)
1288 if (type
== isl_dim_out
)
1290 pw
->p
[i
].set
= isl_set_drop(pw
->p
[i
].set
, set_type
, first
, n
);
1301 /* This function is very similar to drop_dims.
1302 * The only difference is that the cells may still involve
1303 * the specified dimensions. They are removed using
1304 * isl_set_project_out instead of isl_set_drop.
1306 __isl_give PW
*FN(PW
,project_out
)(__isl_take PW
*pw
,
1307 enum isl_dim_type type
, unsigned first
, unsigned n
)
1310 enum isl_dim_type set_type
;
1314 if (n
== 0 && !isl_space_get_tuple_name(pw
->dim
, type
))
1317 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1319 pw
= FN(PW
,cow
)(pw
);
1322 pw
->dim
= isl_space_drop_dims(pw
->dim
, type
, first
, n
);
1325 for (i
= 0; i
< pw
->n
; ++i
) {
1326 pw
->p
[i
].set
= isl_set_project_out(pw
->p
[i
].set
,
1327 set_type
, first
, n
);
1330 pw
->p
[i
].FIELD
= FN(EL
,drop_dims
)(pw
->p
[i
].FIELD
, type
, first
, n
);
1331 if (!pw
->p
[i
].FIELD
)
1341 /* Project the domain of pw onto its parameter space.
1343 __isl_give PW
*FN(PW
,project_domain_on_params
)(__isl_take PW
*pw
)
1348 n
= FN(PW
,dim
)(pw
, isl_dim_in
);
1349 pw
= FN(PW
,project_out
)(pw
, isl_dim_in
, 0, n
);
1350 space
= FN(PW
,get_domain_space
)(pw
);
1351 space
= isl_space_params(space
);
1352 pw
= FN(PW
,reset_domain_space
)(pw
, space
);
1357 #ifndef NO_INSERT_DIMS
1358 __isl_give PW
*FN(PW
,insert_dims
)(__isl_take PW
*pw
, enum isl_dim_type type
,
1359 unsigned first
, unsigned n
)
1362 enum isl_dim_type set_type
;
1366 if (n
== 0 && !isl_space_is_named_or_nested(pw
->dim
, type
))
1369 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
1371 pw
= FN(PW
,cow
)(pw
);
1375 pw
->dim
= isl_space_insert_dims(pw
->dim
, type
, first
, n
);
1379 for (i
= 0; i
< pw
->n
; ++i
) {
1380 pw
->p
[i
].set
= isl_set_insert_dims(pw
->p
[i
].set
,
1381 set_type
, first
, n
);
1384 pw
->p
[i
].FIELD
= FN(EL
,insert_dims
)(pw
->p
[i
].FIELD
,
1386 if (!pw
->p
[i
].FIELD
)
1397 __isl_give PW
*FN(PW
,fix_dim
)(__isl_take PW
*pw
,
1398 enum isl_dim_type type
, unsigned pos
, isl_int v
)
1405 if (type
== isl_dim_in
)
1408 pw
= FN(PW
,cow
)(pw
);
1411 for (i
= 0; i
< pw
->n
; ++i
) {
1412 pw
->p
[i
].set
= isl_set_fix(pw
->p
[i
].set
, type
, pos
, v
);
1413 if (FN(PW
,exploit_equalities_and_remove_if_empty
)(pw
, i
) < 0)
1414 return FN(PW
,free
)(pw
);
1420 /* Fix the value of the variable at position "pos" of type "type" of "pw"
1421 * to be equal to "v".
1423 __isl_give PW
*FN(PW
,fix_val
)(__isl_take PW
*pw
,
1424 enum isl_dim_type type
, unsigned pos
, __isl_take isl_val
*v
)
1427 return FN(PW
,free
)(pw
);
1428 if (!isl_val_is_int(v
))
1429 isl_die(FN(PW
,get_ctx
)(pw
), isl_error_invalid
,
1430 "expecting integer value", goto error
);
1432 pw
= FN(PW
,fix_dim
)(pw
, type
, pos
, v
->n
);
1438 return FN(PW
,free
)(pw
);
1441 unsigned FN(PW
,dim
)(__isl_keep PW
*pw
, enum isl_dim_type type
)
1443 return pw
? isl_space_dim(pw
->dim
, type
) : 0;
1446 __isl_give PW
*FN(PW
,split_dims
)(__isl_take PW
*pw
,
1447 enum isl_dim_type type
, unsigned first
, unsigned n
)
1456 if (type
== isl_dim_in
)
1459 pw
= FN(PW
,cow
)(pw
);
1464 for (i
= 0; i
< pw
->n
; ++i
) {
1465 pw
->p
[i
].set
= isl_set_split_dims(pw
->p
[i
].set
, type
, first
, n
);
1477 /* Compute the maximal value attained by the piecewise quasipolynomial
1478 * on its domain or zero if the domain is empty.
1479 * In the worst case, the domain is scanned completely,
1480 * so the domain is assumed to be bounded.
1482 __isl_give isl_val
*FN(PW
,opt
)(__isl_take PW
*pw
, int max
)
1491 opt
= isl_val_zero(FN(PW
,get_ctx
)(pw
));
1496 opt
= FN(EL
,opt_on_domain
)(FN(EL
,copy
)(pw
->p
[0].FIELD
),
1497 isl_set_copy(pw
->p
[0].set
), max
);
1498 for (i
= 1; i
< pw
->n
; ++i
) {
1500 opt_i
= FN(EL
,opt_on_domain
)(FN(EL
,copy
)(pw
->p
[i
].FIELD
),
1501 isl_set_copy(pw
->p
[i
].set
), max
);
1503 opt
= isl_val_max(opt
, opt_i
);
1505 opt
= isl_val_min(opt
, opt_i
);
1512 __isl_give isl_val
*FN(PW
,max
)(__isl_take PW
*pw
)
1514 return FN(PW
,opt
)(pw
, 1);
1517 __isl_give isl_val
*FN(PW
,min
)(__isl_take PW
*pw
)
1519 return FN(PW
,opt
)(pw
, 0);
1523 /* Return the space of "pw".
1525 __isl_keep isl_space
*FN(PW
,peek_space
)(__isl_keep PW
*pw
)
1527 return pw
? pw
->dim
: NULL
;
1530 __isl_give isl_space
*FN(PW
,get_space
)(__isl_keep PW
*pw
)
1532 return isl_space_copy(FN(PW
,peek_space
)(pw
));
1535 __isl_give isl_space
*FN(PW
,get_domain_space
)(__isl_keep PW
*pw
)
1537 return pw
? isl_space_domain(isl_space_copy(pw
->dim
)) : NULL
;
1540 /* Return the position of the dimension of the given type and name
1542 * Return -1 if no such dimension can be found.
1544 int FN(PW
,find_dim_by_name
)(__isl_keep PW
*pw
,
1545 enum isl_dim_type type
, const char *name
)
1549 return isl_space_find_dim_by_name(pw
->dim
, type
, name
);
1552 #ifndef NO_RESET_DIM
1553 /* Reset the space of "pw". Since we don't know if the elements
1554 * represent the spaces themselves or their domains, we pass along
1555 * both when we call their reset_space_and_domain.
1557 static __isl_give PW
*FN(PW
,reset_space_and_domain
)(__isl_take PW
*pw
,
1558 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
1562 pw
= FN(PW
,cow
)(pw
);
1563 if (!pw
|| !space
|| !domain
)
1566 for (i
= 0; i
< pw
->n
; ++i
) {
1567 pw
->p
[i
].set
= isl_set_reset_space(pw
->p
[i
].set
,
1568 isl_space_copy(domain
));
1571 pw
->p
[i
].FIELD
= FN(EL
,reset_space_and_domain
)(pw
->p
[i
].FIELD
,
1572 isl_space_copy(space
), isl_space_copy(domain
));
1573 if (!pw
->p
[i
].FIELD
)
1577 isl_space_free(domain
);
1579 isl_space_free(pw
->dim
);
1584 isl_space_free(domain
);
1585 isl_space_free(space
);
1590 __isl_give PW
*FN(PW
,reset_domain_space
)(__isl_take PW
*pw
,
1591 __isl_take isl_space
*domain
)
1595 space
= isl_space_extend_domain_with_range(isl_space_copy(domain
),
1596 FN(PW
,get_space
)(pw
));
1597 return FN(PW
,reset_space_and_domain
)(pw
, space
, domain
);
1600 __isl_give PW
*FN(PW
,reset_space
)(__isl_take PW
*pw
, __isl_take isl_space
*dim
)
1604 domain
= isl_space_domain(isl_space_copy(dim
));
1605 return FN(PW
,reset_space_and_domain
)(pw
, dim
, domain
);
1608 __isl_give PW
*FN(PW
,set_tuple_id
)(__isl_take PW
*pw
, enum isl_dim_type type
,
1609 __isl_take isl_id
*id
)
1613 pw
= FN(PW
,cow
)(pw
);
1617 space
= FN(PW
,get_space
)(pw
);
1618 space
= isl_space_set_tuple_id(space
, type
, id
);
1620 return FN(PW
,reset_space
)(pw
, space
);
1623 return FN(PW
,free
)(pw
);
1626 /* Drop the id on the specified tuple.
1628 __isl_give PW
*FN(PW
,reset_tuple_id
)(__isl_take PW
*pw
, enum isl_dim_type type
)
1634 if (!FN(PW
,has_tuple_id
)(pw
, type
))
1637 pw
= FN(PW
,cow
)(pw
);
1641 space
= FN(PW
,get_space
)(pw
);
1642 space
= isl_space_reset_tuple_id(space
, type
);
1644 return FN(PW
,reset_space
)(pw
, space
);
1647 __isl_give PW
*FN(PW
,set_dim_id
)(__isl_take PW
*pw
,
1648 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1650 pw
= FN(PW
,cow
)(pw
);
1653 pw
->dim
= isl_space_set_dim_id(pw
->dim
, type
, pos
, id
);
1654 return FN(PW
,reset_space
)(pw
, isl_space_copy(pw
->dim
));
1657 return FN(PW
,free
)(pw
);
1661 /* Reset the user pointer on all identifiers of parameters and tuples
1662 * of the space of "pw".
1664 __isl_give PW
*FN(PW
,reset_user
)(__isl_take PW
*pw
)
1668 space
= FN(PW
,get_space
)(pw
);
1669 space
= isl_space_reset_user(space
);
1671 return FN(PW
,reset_space
)(pw
, space
);
1674 isl_bool
FN(PW
,has_equal_space
)(__isl_keep PW
*pw1
, __isl_keep PW
*pw2
)
1677 return isl_bool_error
;
1679 return isl_space_is_equal(pw1
->dim
, pw2
->dim
);
1683 __isl_give PW
*FN(PW
,morph_domain
)(__isl_take PW
*pw
,
1684 __isl_take isl_morph
*morph
)
1692 ctx
= isl_space_get_ctx(pw
->dim
);
1693 isl_assert(ctx
, isl_space_is_domain_internal(morph
->dom
->dim
, pw
->dim
),
1696 pw
= FN(PW
,cow
)(pw
);
1699 pw
->dim
= isl_space_extend_domain_with_range(
1700 isl_space_copy(morph
->ran
->dim
), pw
->dim
);
1704 for (i
= 0; i
< pw
->n
; ++i
) {
1705 pw
->p
[i
].set
= isl_morph_set(isl_morph_copy(morph
), pw
->p
[i
].set
);
1708 pw
->p
[i
].FIELD
= FN(EL
,morph_domain
)(pw
->p
[i
].FIELD
,
1709 isl_morph_copy(morph
));
1710 if (!pw
->p
[i
].FIELD
)
1714 isl_morph_free(morph
);
1719 isl_morph_free(morph
);
1724 int FN(PW
,n_piece
)(__isl_keep PW
*pw
)
1726 return pw
? pw
->n
: 0;
1729 isl_stat
FN(PW
,foreach_piece
)(__isl_keep PW
*pw
,
1730 isl_stat (*fn
)(__isl_take isl_set
*set
, __isl_take EL
*el
, void *user
),
1736 return isl_stat_error
;
1738 for (i
= 0; i
< pw
->n
; ++i
)
1739 if (fn(isl_set_copy(pw
->p
[i
].set
),
1740 FN(EL
,copy
)(pw
->p
[i
].FIELD
), user
) < 0)
1741 return isl_stat_error
;
1747 static isl_bool
any_divs(__isl_keep isl_set
*set
)
1752 return isl_bool_error
;
1754 for (i
= 0; i
< set
->n
; ++i
)
1755 if (set
->p
[i
]->n_div
> 0)
1756 return isl_bool_true
;
1758 return isl_bool_false
;
1761 static isl_stat
foreach_lifted_subset(__isl_take isl_set
*set
,
1763 isl_stat (*fn
)(__isl_take isl_set
*set
, __isl_take EL
*el
,
1764 void *user
), void *user
)
1771 for (i
= 0; i
< set
->n
; ++i
) {
1775 lift
= isl_set_from_basic_set(isl_basic_set_copy(set
->p
[i
]));
1776 lift
= isl_set_lift(lift
);
1778 copy
= FN(EL
,copy
)(el
);
1779 copy
= FN(EL
,lift
)(copy
, isl_set_get_space(lift
));
1781 if (fn(lift
, copy
, user
) < 0)
1792 return isl_stat_error
;
1795 isl_stat
FN(PW
,foreach_lifted_piece
)(__isl_keep PW
*pw
,
1796 isl_stat (*fn
)(__isl_take isl_set
*set
, __isl_take EL
*el
,
1797 void *user
), void *user
)
1802 return isl_stat_error
;
1804 for (i
= 0; i
< pw
->n
; ++i
) {
1809 any
= any_divs(pw
->p
[i
].set
);
1811 return isl_stat_error
;
1812 set
= isl_set_copy(pw
->p
[i
].set
);
1813 el
= FN(EL
,copy
)(pw
->p
[i
].FIELD
);
1815 if (fn(set
, el
, user
) < 0)
1816 return isl_stat_error
;
1819 if (foreach_lifted_subset(set
, el
, fn
, user
) < 0)
1820 return isl_stat_error
;
1827 #ifndef NO_MOVE_DIMS
1828 __isl_give PW
*FN(PW
,move_dims
)(__isl_take PW
*pw
,
1829 enum isl_dim_type dst_type
, unsigned dst_pos
,
1830 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1834 pw
= FN(PW
,cow
)(pw
);
1838 pw
->dim
= isl_space_move_dims(pw
->dim
, dst_type
, dst_pos
, src_type
, src_pos
, n
);
1842 for (i
= 0; i
< pw
->n
; ++i
) {
1843 pw
->p
[i
].FIELD
= FN(EL
,move_dims
)(pw
->p
[i
].FIELD
,
1844 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1845 if (!pw
->p
[i
].FIELD
)
1849 if (dst_type
== isl_dim_in
)
1850 dst_type
= isl_dim_set
;
1851 if (src_type
== isl_dim_in
)
1852 src_type
= isl_dim_set
;
1854 for (i
= 0; i
< pw
->n
; ++i
) {
1855 pw
->p
[i
].set
= isl_set_move_dims(pw
->p
[i
].set
,
1857 src_type
, src_pos
, n
);
1869 __isl_give PW
*FN(PW
,mul_isl_int
)(__isl_take PW
*pw
, isl_int v
)
1873 if (isl_int_is_one(v
))
1875 if (pw
&& DEFAULT_IS_ZERO
&& isl_int_is_zero(v
)) {
1877 isl_space
*dim
= FN(PW
,get_space
)(pw
);
1879 zero
= FN(PW
,ZERO
)(dim
, pw
->type
);
1881 zero
= FN(PW
,ZERO
)(dim
);
1886 pw
= FN(PW
,cow
)(pw
);
1893 if (isl_int_is_neg(v
))
1894 pw
->type
= isl_fold_type_negate(pw
->type
);
1896 for (i
= 0; i
< pw
->n
; ++i
) {
1897 pw
->p
[i
].FIELD
= FN(EL
,scale
)(pw
->p
[i
].FIELD
, v
);
1898 if (!pw
->p
[i
].FIELD
)
1908 /* Multiply the pieces of "pw" by "v" and return the result.
1910 __isl_give PW
*FN(PW
,scale_val
)(__isl_take PW
*pw
, __isl_take isl_val
*v
)
1917 if (isl_val_is_one(v
)) {
1921 if (pw
&& DEFAULT_IS_ZERO
&& isl_val_is_zero(v
)) {
1923 isl_space
*space
= FN(PW
,get_space
)(pw
);
1925 zero
= FN(PW
,ZERO
)(space
, pw
->type
);
1927 zero
= FN(PW
,ZERO
)(space
);
1937 pw
= FN(PW
,cow
)(pw
);
1942 if (isl_val_is_neg(v
))
1943 pw
->type
= isl_fold_type_negate(pw
->type
);
1945 for (i
= 0; i
< pw
->n
; ++i
) {
1946 pw
->p
[i
].FIELD
= FN(EL
,scale_val
)(pw
->p
[i
].FIELD
,
1948 if (!pw
->p
[i
].FIELD
)
1960 /* Divide the pieces of "pw" by "v" and return the result.
1962 __isl_give PW
*FN(PW
,scale_down_val
)(__isl_take PW
*pw
, __isl_take isl_val
*v
)
1969 if (isl_val_is_one(v
)) {
1974 if (!isl_val_is_rat(v
))
1975 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1976 "expecting rational factor", goto error
);
1977 if (isl_val_is_zero(v
))
1978 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1979 "cannot scale down by zero", goto error
);
1985 pw
= FN(PW
,cow
)(pw
);
1990 if (isl_val_is_neg(v
))
1991 pw
->type
= isl_fold_type_negate(pw
->type
);
1993 for (i
= 0; i
< pw
->n
; ++i
) {
1994 pw
->p
[i
].FIELD
= FN(EL
,scale_down_val
)(pw
->p
[i
].FIELD
,
1996 if (!pw
->p
[i
].FIELD
)
2008 __isl_give PW
*FN(PW
,scale
)(__isl_take PW
*pw
, isl_int v
)
2010 return FN(PW
,mul_isl_int
)(pw
, v
);
2013 /* Apply some normalization to "pw".
2014 * In particular, sort the pieces according to their function value
2015 * expressions, combining pairs of adjacent pieces with
2016 * the same such expression, and then normalize the domains of the pieces.
2018 * We normalize in place, but if anything goes wrong we need
2019 * to return NULL, so we need to make sure we don't change the
2020 * meaning of any possible other copies of "pw".
2022 __isl_give PW
*FN(PW
,normalize
)(__isl_take PW
*pw
)
2027 pw
= FN(PW
,sort
)(pw
);
2030 for (i
= 0; i
< pw
->n
; ++i
) {
2031 set
= isl_set_normalize(isl_set_copy(pw
->p
[i
].set
));
2033 return FN(PW
,free
)(pw
);
2034 isl_set_free(pw
->p
[i
].set
);
2041 /* Is pw1 obviously equal to pw2?
2042 * That is, do they have obviously identical cells and obviously identical
2043 * elements on each cell?
2045 * If "pw1" or "pw2" contain any NaNs, then they are considered
2046 * not to be the same. A NaN is not equal to anything, not even
2049 isl_bool
FN(PW
,plain_is_equal
)(__isl_keep PW
*pw1
, __isl_keep PW
*pw2
)
2052 isl_bool equal
, has_nan
;
2055 return isl_bool_error
;
2057 has_nan
= FN(PW
,involves_nan
)(pw1
);
2058 if (has_nan
>= 0 && !has_nan
)
2059 has_nan
= FN(PW
,involves_nan
)(pw2
);
2060 if (has_nan
< 0 || has_nan
)
2061 return isl_bool_not(has_nan
);
2064 return isl_bool_true
;
2065 if (!isl_space_is_equal(pw1
->dim
, pw2
->dim
))
2066 return isl_bool_false
;
2068 pw1
= FN(PW
,copy
)(pw1
);
2069 pw2
= FN(PW
,copy
)(pw2
);
2070 pw1
= FN(PW
,normalize
)(pw1
);
2071 pw2
= FN(PW
,normalize
)(pw2
);
2075 equal
= pw1
->n
== pw2
->n
;
2076 for (i
= 0; equal
&& i
< pw1
->n
; ++i
) {
2077 equal
= isl_set_plain_is_equal(pw1
->p
[i
].set
, pw2
->p
[i
].set
);
2082 equal
= FN(EL
,plain_is_equal
)(pw1
->p
[i
].FIELD
, pw2
->p
[i
].FIELD
);
2093 return isl_bool_error
;
2096 /* Does "pw" involve any NaNs?
2098 isl_bool
FN(PW
,involves_nan
)(__isl_keep PW
*pw
)
2103 return isl_bool_error
;
2105 return isl_bool_false
;
2107 for (i
= 0; i
< pw
->n
; ++i
) {
2108 isl_bool has_nan
= FN(EL
,involves_nan
)(pw
->p
[i
].FIELD
);
2109 if (has_nan
< 0 || has_nan
)
2113 return isl_bool_false
;
2117 static __isl_give PW
*FN(PW
,align_params_pw_multi_aff_and
)(__isl_take PW
*pw
,
2118 __isl_take isl_multi_aff
*ma
,
2119 __isl_give PW
*(*fn
)(__isl_take PW
*pw
, __isl_take isl_multi_aff
*ma
))
2122 isl_bool equal_params
;
2123 isl_space
*ma_space
;
2125 ma_space
= isl_multi_aff_get_space(ma
);
2126 if (!pw
|| !ma
|| !ma_space
)
2128 equal_params
= isl_space_has_equal_params(pw
->dim
, ma_space
);
2129 if (equal_params
< 0)
2132 isl_space_free(ma_space
);
2135 ctx
= FN(PW
,get_ctx
)(pw
);
2136 if (!isl_space_has_named_params(pw
->dim
) ||
2137 !isl_space_has_named_params(ma_space
))
2138 isl_die(ctx
, isl_error_invalid
,
2139 "unaligned unnamed parameters", goto error
);
2140 pw
= FN(PW
,align_params
)(pw
, ma_space
);
2141 ma
= isl_multi_aff_align_params(ma
, FN(PW
,get_space
)(pw
));
2144 isl_space_free(ma_space
);
2146 isl_multi_aff_free(ma
);
2150 static __isl_give PW
*FN(PW
,align_params_pw_pw_multi_aff_and
)(__isl_take PW
*pw
,
2151 __isl_take isl_pw_multi_aff
*pma
,
2152 __isl_give PW
*(*fn
)(__isl_take PW
*pw
,
2153 __isl_take isl_pw_multi_aff
*ma
))
2156 isl_bool equal_params
;
2157 isl_space
*pma_space
;
2159 pma_space
= isl_pw_multi_aff_get_space(pma
);
2160 if (!pw
|| !pma
|| !pma_space
)
2162 equal_params
= isl_space_has_equal_params(pw
->dim
, pma_space
);
2163 if (equal_params
< 0)
2166 isl_space_free(pma_space
);
2169 ctx
= FN(PW
,get_ctx
)(pw
);
2170 if (!isl_space_has_named_params(pw
->dim
) ||
2171 !isl_space_has_named_params(pma_space
))
2172 isl_die(ctx
, isl_error_invalid
,
2173 "unaligned unnamed parameters", goto error
);
2174 pw
= FN(PW
,align_params
)(pw
, pma_space
);
2175 pma
= isl_pw_multi_aff_align_params(pma
, FN(PW
,get_space
)(pw
));
2178 isl_space_free(pma_space
);
2180 isl_pw_multi_aff_free(pma
);
2184 /* Compute the pullback of "pw" by the function represented by "ma".
2185 * In other words, plug in "ma" in "pw".
2187 static __isl_give PW
*FN(PW
,pullback_multi_aff_aligned
)(__isl_take PW
*pw
,
2188 __isl_take isl_multi_aff
*ma
)
2191 isl_space
*space
= NULL
;
2193 ma
= isl_multi_aff_align_divs(ma
);
2194 pw
= FN(PW
,cow
)(pw
);
2198 space
= isl_space_join(isl_multi_aff_get_space(ma
),
2199 FN(PW
,get_space
)(pw
));
2201 for (i
= 0; i
< pw
->n
; ++i
) {
2202 pw
->p
[i
].set
= isl_set_preimage_multi_aff(pw
->p
[i
].set
,
2203 isl_multi_aff_copy(ma
));
2206 pw
->p
[i
].FIELD
= FN(EL
,pullback_multi_aff
)(pw
->p
[i
].FIELD
,
2207 isl_multi_aff_copy(ma
));
2208 if (!pw
->p
[i
].FIELD
)
2212 pw
= FN(PW
,reset_space
)(pw
, space
);
2213 isl_multi_aff_free(ma
);
2216 isl_space_free(space
);
2217 isl_multi_aff_free(ma
);
2222 __isl_give PW
*FN(PW
,pullback_multi_aff
)(__isl_take PW
*pw
,
2223 __isl_take isl_multi_aff
*ma
)
2225 return FN(PW
,align_params_pw_multi_aff_and
)(pw
, ma
,
2226 &FN(PW
,pullback_multi_aff_aligned
));
2229 /* Compute the pullback of "pw" by the function represented by "pma".
2230 * In other words, plug in "pma" in "pw".
2232 static __isl_give PW
*FN(PW
,pullback_pw_multi_aff_aligned
)(__isl_take PW
*pw
,
2233 __isl_take isl_pw_multi_aff
*pma
)
2243 space
= isl_space_join(isl_pw_multi_aff_get_space(pma
),
2244 FN(PW
,get_space
)(pw
));
2245 isl_pw_multi_aff_free(pma
);
2246 res
= FN(PW
,empty
)(space
);
2251 res
= FN(PW
,pullback_multi_aff
)(FN(PW
,copy
)(pw
),
2252 isl_multi_aff_copy(pma
->p
[0].maff
));
2253 res
= FN(PW
,intersect_domain
)(res
, isl_set_copy(pma
->p
[0].set
));
2255 for (i
= 1; i
< pma
->n
; ++i
) {
2258 res_i
= FN(PW
,pullback_multi_aff
)(FN(PW
,copy
)(pw
),
2259 isl_multi_aff_copy(pma
->p
[i
].maff
));
2260 res_i
= FN(PW
,intersect_domain
)(res_i
,
2261 isl_set_copy(pma
->p
[i
].set
));
2262 res
= FN(PW
,add_disjoint
)(res
, res_i
);
2265 isl_pw_multi_aff_free(pma
);
2269 isl_pw_multi_aff_free(pma
);
2274 __isl_give PW
*FN(PW
,pullback_pw_multi_aff
)(__isl_take PW
*pw
,
2275 __isl_take isl_pw_multi_aff
*pma
)
2277 return FN(PW
,align_params_pw_pw_multi_aff_and
)(pw
, pma
,
2278 &FN(PW
,pullback_pw_multi_aff_aligned
));