2 * Copyright 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
14 #include <isl_ctx_private.h>
16 #include <isl_map_private.h>
17 #include <isl_union_map_private.h>
18 #include <isl_aff_private.h>
19 #include <isl_space_private.h>
20 #include <isl_local_space_private.h>
21 #include <isl_vec_private.h>
22 #include <isl_mat_private.h>
23 #include <isl/constraint.h>
26 #include <isl_val_private.h>
27 #include <isl/deprecated/aff_int.h>
28 #include <isl_config.h>
33 #include <isl_list_templ.c>
38 #include <isl_list_templ.c>
41 #define BASE union_pw_multi_aff
43 #include <isl_list_templ.c>
45 __isl_give isl_aff
*isl_aff_alloc_vec(__isl_take isl_local_space
*ls
,
46 __isl_take isl_vec
*v
)
53 aff
= isl_calloc_type(v
->ctx
, struct isl_aff
);
63 isl_local_space_free(ls
);
68 __isl_give isl_aff
*isl_aff_alloc(__isl_take isl_local_space
*ls
)
77 ctx
= isl_local_space_get_ctx(ls
);
78 if (!isl_local_space_divs_known(ls
))
79 isl_die(ctx
, isl_error_invalid
, "local space has unknown divs",
81 if (!isl_local_space_is_set(ls
))
82 isl_die(ctx
, isl_error_invalid
,
83 "domain of affine expression should be a set",
86 total
= isl_local_space_dim(ls
, isl_dim_all
);
87 v
= isl_vec_alloc(ctx
, 1 + 1 + total
);
88 return isl_aff_alloc_vec(ls
, v
);
90 isl_local_space_free(ls
);
94 __isl_give isl_aff
*isl_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
98 aff
= isl_aff_alloc(ls
);
102 isl_int_set_si(aff
->v
->el
[0], 1);
103 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
108 /* Return a piecewise affine expression defined on the specified domain
109 * that is equal to zero.
111 __isl_give isl_pw_aff
*isl_pw_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
113 return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
116 /* Return an affine expression defined on the specified domain
117 * that represents NaN.
119 __isl_give isl_aff
*isl_aff_nan_on_domain(__isl_take isl_local_space
*ls
)
123 aff
= isl_aff_alloc(ls
);
127 isl_seq_clr(aff
->v
->el
, aff
->v
->size
);
132 /* Return a piecewise affine expression defined on the specified domain
133 * that represents NaN.
135 __isl_give isl_pw_aff
*isl_pw_aff_nan_on_domain(__isl_take isl_local_space
*ls
)
137 return isl_pw_aff_from_aff(isl_aff_nan_on_domain(ls
));
140 /* Return an affine expression that is equal to "val" on
141 * domain local space "ls".
143 __isl_give isl_aff
*isl_aff_val_on_domain(__isl_take isl_local_space
*ls
,
144 __isl_take isl_val
*val
)
150 if (!isl_val_is_rat(val
))
151 isl_die(isl_val_get_ctx(val
), isl_error_invalid
,
152 "expecting rational value", goto error
);
154 aff
= isl_aff_alloc(isl_local_space_copy(ls
));
158 isl_seq_clr(aff
->v
->el
+ 2, aff
->v
->size
- 2);
159 isl_int_set(aff
->v
->el
[1], val
->n
);
160 isl_int_set(aff
->v
->el
[0], val
->d
);
162 isl_local_space_free(ls
);
166 isl_local_space_free(ls
);
171 /* Return an affine expression that is equal to the specified dimension
174 __isl_give isl_aff
*isl_aff_var_on_domain(__isl_take isl_local_space
*ls
,
175 enum isl_dim_type type
, unsigned pos
)
183 space
= isl_local_space_get_space(ls
);
186 if (isl_space_is_map(space
))
187 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
188 "expecting (parameter) set space", goto error
);
189 if (pos
>= isl_local_space_dim(ls
, type
))
190 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
191 "position out of bounds", goto error
);
193 isl_space_free(space
);
194 aff
= isl_aff_alloc(ls
);
198 pos
+= isl_local_space_offset(aff
->ls
, type
);
200 isl_int_set_si(aff
->v
->el
[0], 1);
201 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
202 isl_int_set_si(aff
->v
->el
[1 + pos
], 1);
206 isl_local_space_free(ls
);
207 isl_space_free(space
);
211 /* Return a piecewise affine expression that is equal to
212 * the specified dimension in "ls".
214 __isl_give isl_pw_aff
*isl_pw_aff_var_on_domain(__isl_take isl_local_space
*ls
,
215 enum isl_dim_type type
, unsigned pos
)
217 return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, type
, pos
));
220 __isl_give isl_aff
*isl_aff_copy(__isl_keep isl_aff
*aff
)
229 __isl_give isl_aff
*isl_aff_dup(__isl_keep isl_aff
*aff
)
234 return isl_aff_alloc_vec(isl_local_space_copy(aff
->ls
),
235 isl_vec_copy(aff
->v
));
238 __isl_give isl_aff
*isl_aff_cow(__isl_take isl_aff
*aff
)
246 return isl_aff_dup(aff
);
249 __isl_null isl_aff
*isl_aff_free(__isl_take isl_aff
*aff
)
257 isl_local_space_free(aff
->ls
);
258 isl_vec_free(aff
->v
);
265 isl_ctx
*isl_aff_get_ctx(__isl_keep isl_aff
*aff
)
267 return aff
? isl_local_space_get_ctx(aff
->ls
) : NULL
;
270 /* Externally, an isl_aff has a map space, but internally, the
271 * ls field corresponds to the domain of that space.
273 int isl_aff_dim(__isl_keep isl_aff
*aff
, enum isl_dim_type type
)
277 if (type
== isl_dim_out
)
279 if (type
== isl_dim_in
)
281 return isl_local_space_dim(aff
->ls
, type
);
284 /* Return the position of the dimension of the given type and name
286 * Return -1 if no such dimension can be found.
288 int isl_aff_find_dim_by_name(__isl_keep isl_aff
*aff
, enum isl_dim_type type
,
293 if (type
== isl_dim_out
)
295 if (type
== isl_dim_in
)
297 return isl_local_space_find_dim_by_name(aff
->ls
, type
, name
);
300 __isl_give isl_space
*isl_aff_get_domain_space(__isl_keep isl_aff
*aff
)
302 return aff
? isl_local_space_get_space(aff
->ls
) : NULL
;
305 __isl_give isl_space
*isl_aff_get_space(__isl_keep isl_aff
*aff
)
310 space
= isl_local_space_get_space(aff
->ls
);
311 space
= isl_space_from_domain(space
);
312 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
316 __isl_give isl_local_space
*isl_aff_get_domain_local_space(
317 __isl_keep isl_aff
*aff
)
319 return aff
? isl_local_space_copy(aff
->ls
) : NULL
;
322 __isl_give isl_local_space
*isl_aff_get_local_space(__isl_keep isl_aff
*aff
)
327 ls
= isl_local_space_copy(aff
->ls
);
328 ls
= isl_local_space_from_domain(ls
);
329 ls
= isl_local_space_add_dims(ls
, isl_dim_out
, 1);
333 /* Externally, an isl_aff has a map space, but internally, the
334 * ls field corresponds to the domain of that space.
336 const char *isl_aff_get_dim_name(__isl_keep isl_aff
*aff
,
337 enum isl_dim_type type
, unsigned pos
)
341 if (type
== isl_dim_out
)
343 if (type
== isl_dim_in
)
345 return isl_local_space_get_dim_name(aff
->ls
, type
, pos
);
348 __isl_give isl_aff
*isl_aff_reset_domain_space(__isl_take isl_aff
*aff
,
349 __isl_take isl_space
*dim
)
351 aff
= isl_aff_cow(aff
);
355 aff
->ls
= isl_local_space_reset_space(aff
->ls
, dim
);
357 return isl_aff_free(aff
);
366 /* Reset the space of "aff". This function is called from isl_pw_templ.c
367 * and doesn't know if the space of an element object is represented
368 * directly or through its domain. It therefore passes along both.
370 __isl_give isl_aff
*isl_aff_reset_space_and_domain(__isl_take isl_aff
*aff
,
371 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
373 isl_space_free(space
);
374 return isl_aff_reset_domain_space(aff
, domain
);
377 /* Reorder the coefficients of the affine expression based
378 * on the given reodering.
379 * The reordering r is assumed to have been extended with the local
382 static __isl_give isl_vec
*vec_reorder(__isl_take isl_vec
*vec
,
383 __isl_take isl_reordering
*r
, int n_div
)
391 res
= isl_vec_alloc(vec
->ctx
,
392 2 + isl_space_dim(r
->dim
, isl_dim_all
) + n_div
);
393 isl_seq_cpy(res
->el
, vec
->el
, 2);
394 isl_seq_clr(res
->el
+ 2, res
->size
- 2);
395 for (i
= 0; i
< r
->len
; ++i
)
396 isl_int_set(res
->el
[2 + r
->pos
[i
]], vec
->el
[2 + i
]);
398 isl_reordering_free(r
);
403 isl_reordering_free(r
);
407 /* Reorder the dimensions of the domain of "aff" according
408 * to the given reordering.
410 __isl_give isl_aff
*isl_aff_realign_domain(__isl_take isl_aff
*aff
,
411 __isl_take isl_reordering
*r
)
413 aff
= isl_aff_cow(aff
);
417 r
= isl_reordering_extend(r
, aff
->ls
->div
->n_row
);
418 aff
->v
= vec_reorder(aff
->v
, isl_reordering_copy(r
),
419 aff
->ls
->div
->n_row
);
420 aff
->ls
= isl_local_space_realign(aff
->ls
, r
);
422 if (!aff
->v
|| !aff
->ls
)
423 return isl_aff_free(aff
);
428 isl_reordering_free(r
);
432 __isl_give isl_aff
*isl_aff_align_params(__isl_take isl_aff
*aff
,
433 __isl_take isl_space
*model
)
438 if (!isl_space_match(aff
->ls
->dim
, isl_dim_param
,
439 model
, isl_dim_param
)) {
442 model
= isl_space_drop_dims(model
, isl_dim_in
,
443 0, isl_space_dim(model
, isl_dim_in
));
444 model
= isl_space_drop_dims(model
, isl_dim_out
,
445 0, isl_space_dim(model
, isl_dim_out
));
446 exp
= isl_parameter_alignment_reordering(aff
->ls
->dim
, model
);
447 exp
= isl_reordering_extend_space(exp
,
448 isl_aff_get_domain_space(aff
));
449 aff
= isl_aff_realign_domain(aff
, exp
);
452 isl_space_free(model
);
455 isl_space_free(model
);
460 /* Is "aff" obviously equal to zero?
462 * If the denominator is zero, then "aff" is not equal to zero.
464 int isl_aff_plain_is_zero(__isl_keep isl_aff
*aff
)
469 if (isl_int_is_zero(aff
->v
->el
[0]))
471 return isl_seq_first_non_zero(aff
->v
->el
+ 1, aff
->v
->size
- 1) < 0;
474 /* Does "aff" represent NaN?
476 int isl_aff_is_nan(__isl_keep isl_aff
*aff
)
481 return isl_seq_first_non_zero(aff
->v
->el
, 2) < 0;
484 /* Does "pa" involve any NaNs?
486 int isl_pw_aff_involves_nan(__isl_keep isl_pw_aff
*pa
)
495 for (i
= 0; i
< pa
->n
; ++i
) {
496 int is_nan
= isl_aff_is_nan(pa
->p
[i
].aff
);
497 if (is_nan
< 0 || is_nan
)
504 /* Are "aff1" and "aff2" obviously equal?
506 * NaN is not equal to anything, not even to another NaN.
508 int isl_aff_plain_is_equal(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
515 if (isl_aff_is_nan(aff1
) || isl_aff_is_nan(aff2
))
518 equal
= isl_local_space_is_equal(aff1
->ls
, aff2
->ls
);
519 if (equal
< 0 || !equal
)
522 return isl_vec_is_equal(aff1
->v
, aff2
->v
);
525 /* Return the common denominator of "aff" in "v".
527 * We cannot return anything meaningful in case of a NaN.
529 int isl_aff_get_denominator(__isl_keep isl_aff
*aff
, isl_int
*v
)
533 if (isl_aff_is_nan(aff
))
534 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
535 "cannot get denominator of NaN", return -1);
536 isl_int_set(*v
, aff
->v
->el
[0]);
540 /* Return the common denominator of "aff".
542 __isl_give isl_val
*isl_aff_get_denominator_val(__isl_keep isl_aff
*aff
)
549 ctx
= isl_aff_get_ctx(aff
);
550 if (isl_aff_is_nan(aff
))
551 return isl_val_nan(ctx
);
552 return isl_val_int_from_isl_int(ctx
, aff
->v
->el
[0]);
555 /* Return the constant term of "aff" in "v".
557 * We cannot return anything meaningful in case of a NaN.
559 int isl_aff_get_constant(__isl_keep isl_aff
*aff
, isl_int
*v
)
563 if (isl_aff_is_nan(aff
))
564 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
565 "cannot get constant term of NaN", return -1);
566 isl_int_set(*v
, aff
->v
->el
[1]);
570 /* Return the constant term of "aff".
572 __isl_give isl_val
*isl_aff_get_constant_val(__isl_keep isl_aff
*aff
)
580 ctx
= isl_aff_get_ctx(aff
);
581 if (isl_aff_is_nan(aff
))
582 return isl_val_nan(ctx
);
583 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1], aff
->v
->el
[0]);
584 return isl_val_normalize(v
);
587 /* Return the coefficient of the variable of type "type" at position "pos"
590 * We cannot return anything meaningful in case of a NaN.
592 int isl_aff_get_coefficient(__isl_keep isl_aff
*aff
,
593 enum isl_dim_type type
, int pos
, isl_int
*v
)
598 if (type
== isl_dim_out
)
599 isl_die(aff
->v
->ctx
, isl_error_invalid
,
600 "output/set dimension does not have a coefficient",
602 if (type
== isl_dim_in
)
605 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
606 isl_die(aff
->v
->ctx
, isl_error_invalid
,
607 "position out of bounds", return -1);
609 if (isl_aff_is_nan(aff
))
610 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
611 "cannot get coefficient of NaN", return -1);
612 pos
+= isl_local_space_offset(aff
->ls
, type
);
613 isl_int_set(*v
, aff
->v
->el
[1 + pos
]);
618 /* Return the coefficient of the variable of type "type" at position "pos"
621 __isl_give isl_val
*isl_aff_get_coefficient_val(__isl_keep isl_aff
*aff
,
622 enum isl_dim_type type
, int pos
)
630 ctx
= isl_aff_get_ctx(aff
);
631 if (type
== isl_dim_out
)
632 isl_die(ctx
, isl_error_invalid
,
633 "output/set dimension does not have a coefficient",
635 if (type
== isl_dim_in
)
638 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
639 isl_die(ctx
, isl_error_invalid
,
640 "position out of bounds", return NULL
);
642 if (isl_aff_is_nan(aff
))
643 return isl_val_nan(ctx
);
644 pos
+= isl_local_space_offset(aff
->ls
, type
);
645 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1 + pos
], aff
->v
->el
[0]);
646 return isl_val_normalize(v
);
649 /* Return the sign of the coefficient of the variable of type "type"
650 * at position "pos" of "aff".
652 int isl_aff_coefficient_sgn(__isl_keep isl_aff
*aff
, enum isl_dim_type type
,
660 ctx
= isl_aff_get_ctx(aff
);
661 if (type
== isl_dim_out
)
662 isl_die(ctx
, isl_error_invalid
,
663 "output/set dimension does not have a coefficient",
665 if (type
== isl_dim_in
)
668 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
669 isl_die(ctx
, isl_error_invalid
,
670 "position out of bounds", return 0);
672 pos
+= isl_local_space_offset(aff
->ls
, type
);
673 return isl_int_sgn(aff
->v
->el
[1 + pos
]);
676 /* Replace the denominator of "aff" by "v".
678 * A NaN is unaffected by this operation.
680 __isl_give isl_aff
*isl_aff_set_denominator(__isl_take isl_aff
*aff
, isl_int v
)
684 if (isl_aff_is_nan(aff
))
686 aff
= isl_aff_cow(aff
);
690 aff
->v
= isl_vec_cow(aff
->v
);
692 return isl_aff_free(aff
);
694 isl_int_set(aff
->v
->el
[0], v
);
699 /* Replace the numerator of the constant term of "aff" by "v".
701 * A NaN is unaffected by this operation.
703 __isl_give isl_aff
*isl_aff_set_constant(__isl_take isl_aff
*aff
, isl_int v
)
707 if (isl_aff_is_nan(aff
))
709 aff
= isl_aff_cow(aff
);
713 aff
->v
= isl_vec_cow(aff
->v
);
715 return isl_aff_free(aff
);
717 isl_int_set(aff
->v
->el
[1], v
);
722 /* Replace the constant term of "aff" by "v".
724 * A NaN is unaffected by this operation.
726 __isl_give isl_aff
*isl_aff_set_constant_val(__isl_take isl_aff
*aff
,
727 __isl_take isl_val
*v
)
732 if (isl_aff_is_nan(aff
)) {
737 if (!isl_val_is_rat(v
))
738 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
739 "expecting rational value", goto error
);
741 if (isl_int_eq(aff
->v
->el
[1], v
->n
) &&
742 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
747 aff
= isl_aff_cow(aff
);
750 aff
->v
= isl_vec_cow(aff
->v
);
754 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
755 isl_int_set(aff
->v
->el
[1], v
->n
);
756 } else if (isl_int_is_one(v
->d
)) {
757 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
759 isl_seq_scale(aff
->v
->el
+ 1,
760 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
761 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
762 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
763 aff
->v
= isl_vec_normalize(aff
->v
);
776 /* Add "v" to the constant term of "aff".
778 * A NaN is unaffected by this operation.
780 __isl_give isl_aff
*isl_aff_add_constant(__isl_take isl_aff
*aff
, isl_int v
)
782 if (isl_int_is_zero(v
))
787 if (isl_aff_is_nan(aff
))
789 aff
= isl_aff_cow(aff
);
793 aff
->v
= isl_vec_cow(aff
->v
);
795 return isl_aff_free(aff
);
797 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
);
802 /* Add "v" to the constant term of "aff".
804 * A NaN is unaffected by this operation.
806 __isl_give isl_aff
*isl_aff_add_constant_val(__isl_take isl_aff
*aff
,
807 __isl_take isl_val
*v
)
812 if (isl_aff_is_nan(aff
) || isl_val_is_zero(v
)) {
817 if (!isl_val_is_rat(v
))
818 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
819 "expecting rational value", goto error
);
821 aff
= isl_aff_cow(aff
);
825 aff
->v
= isl_vec_cow(aff
->v
);
829 if (isl_int_is_one(v
->d
)) {
830 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
831 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
832 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
->n
);
833 aff
->v
= isl_vec_normalize(aff
->v
);
837 isl_seq_scale(aff
->v
->el
+ 1,
838 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
839 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
840 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
841 aff
->v
= isl_vec_normalize(aff
->v
);
854 __isl_give isl_aff
*isl_aff_add_constant_si(__isl_take isl_aff
*aff
, int v
)
859 isl_int_set_si(t
, v
);
860 aff
= isl_aff_add_constant(aff
, t
);
866 /* Add "v" to the numerator of the constant term of "aff".
868 * A NaN is unaffected by this operation.
870 __isl_give isl_aff
*isl_aff_add_constant_num(__isl_take isl_aff
*aff
, isl_int v
)
872 if (isl_int_is_zero(v
))
877 if (isl_aff_is_nan(aff
))
879 aff
= isl_aff_cow(aff
);
883 aff
->v
= isl_vec_cow(aff
->v
);
885 return isl_aff_free(aff
);
887 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
);
892 /* Add "v" to the numerator of the constant term of "aff".
894 * A NaN is unaffected by this operation.
896 __isl_give isl_aff
*isl_aff_add_constant_num_si(__isl_take isl_aff
*aff
, int v
)
904 isl_int_set_si(t
, v
);
905 aff
= isl_aff_add_constant_num(aff
, t
);
911 /* Replace the numerator of the constant term of "aff" by "v".
913 * A NaN is unaffected by this operation.
915 __isl_give isl_aff
*isl_aff_set_constant_si(__isl_take isl_aff
*aff
, int v
)
919 if (isl_aff_is_nan(aff
))
921 aff
= isl_aff_cow(aff
);
925 aff
->v
= isl_vec_cow(aff
->v
);
927 return isl_aff_free(aff
);
929 isl_int_set_si(aff
->v
->el
[1], v
);
934 /* Replace the numerator of the coefficient of the variable of type "type"
935 * at position "pos" of "aff" by "v".
937 * A NaN is unaffected by this operation.
939 __isl_give isl_aff
*isl_aff_set_coefficient(__isl_take isl_aff
*aff
,
940 enum isl_dim_type type
, int pos
, isl_int v
)
945 if (type
== isl_dim_out
)
946 isl_die(aff
->v
->ctx
, isl_error_invalid
,
947 "output/set dimension does not have a coefficient",
948 return isl_aff_free(aff
));
949 if (type
== isl_dim_in
)
952 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
953 isl_die(aff
->v
->ctx
, isl_error_invalid
,
954 "position out of bounds", return isl_aff_free(aff
));
956 if (isl_aff_is_nan(aff
))
958 aff
= isl_aff_cow(aff
);
962 aff
->v
= isl_vec_cow(aff
->v
);
964 return isl_aff_free(aff
);
966 pos
+= isl_local_space_offset(aff
->ls
, type
);
967 isl_int_set(aff
->v
->el
[1 + pos
], v
);
972 /* Replace the numerator of the coefficient of the variable of type "type"
973 * at position "pos" of "aff" by "v".
975 * A NaN is unaffected by this operation.
977 __isl_give isl_aff
*isl_aff_set_coefficient_si(__isl_take isl_aff
*aff
,
978 enum isl_dim_type type
, int pos
, int v
)
983 if (type
== isl_dim_out
)
984 isl_die(aff
->v
->ctx
, isl_error_invalid
,
985 "output/set dimension does not have a coefficient",
986 return isl_aff_free(aff
));
987 if (type
== isl_dim_in
)
990 if (pos
< 0 || pos
>= isl_local_space_dim(aff
->ls
, type
))
991 isl_die(aff
->v
->ctx
, isl_error_invalid
,
992 "position out of bounds", return isl_aff_free(aff
));
994 if (isl_aff_is_nan(aff
))
996 pos
+= isl_local_space_offset(aff
->ls
, type
);
997 if (isl_int_cmp_si(aff
->v
->el
[1 + pos
], v
) == 0)
1000 aff
= isl_aff_cow(aff
);
1004 aff
->v
= isl_vec_cow(aff
->v
);
1006 return isl_aff_free(aff
);
1008 isl_int_set_si(aff
->v
->el
[1 + pos
], v
);
1013 /* Replace the coefficient of the variable of type "type" at position "pos"
1016 * A NaN is unaffected by this operation.
1018 __isl_give isl_aff
*isl_aff_set_coefficient_val(__isl_take isl_aff
*aff
,
1019 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
1024 if (type
== isl_dim_out
)
1025 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1026 "output/set dimension does not have a coefficient",
1028 if (type
== isl_dim_in
)
1031 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
1032 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1033 "position out of bounds", goto error
);
1035 if (isl_aff_is_nan(aff
)) {
1039 if (!isl_val_is_rat(v
))
1040 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1041 "expecting rational value", goto error
);
1043 pos
+= isl_local_space_offset(aff
->ls
, type
);
1044 if (isl_int_eq(aff
->v
->el
[1 + pos
], v
->n
) &&
1045 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
1050 aff
= isl_aff_cow(aff
);
1053 aff
->v
= isl_vec_cow(aff
->v
);
1057 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
1058 isl_int_set(aff
->v
->el
[1 + pos
], v
->n
);
1059 } else if (isl_int_is_one(v
->d
)) {
1060 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1062 isl_seq_scale(aff
->v
->el
+ 1,
1063 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
1064 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1065 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
1066 aff
->v
= isl_vec_normalize(aff
->v
);
1079 /* Add "v" to the coefficient of the variable of type "type"
1080 * at position "pos" of "aff".
1082 * A NaN is unaffected by this operation.
1084 __isl_give isl_aff
*isl_aff_add_coefficient(__isl_take isl_aff
*aff
,
1085 enum isl_dim_type type
, int pos
, isl_int v
)
1090 if (type
== isl_dim_out
)
1091 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1092 "output/set dimension does not have a coefficient",
1093 return isl_aff_free(aff
));
1094 if (type
== isl_dim_in
)
1097 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
1098 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1099 "position out of bounds", return isl_aff_free(aff
));
1101 if (isl_aff_is_nan(aff
))
1103 aff
= isl_aff_cow(aff
);
1107 aff
->v
= isl_vec_cow(aff
->v
);
1109 return isl_aff_free(aff
);
1111 pos
+= isl_local_space_offset(aff
->ls
, type
);
1112 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
);
1117 /* Add "v" to the coefficient of the variable of type "type"
1118 * at position "pos" of "aff".
1120 * A NaN is unaffected by this operation.
1122 __isl_give isl_aff
*isl_aff_add_coefficient_val(__isl_take isl_aff
*aff
,
1123 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
1128 if (isl_val_is_zero(v
)) {
1133 if (type
== isl_dim_out
)
1134 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1135 "output/set dimension does not have a coefficient",
1137 if (type
== isl_dim_in
)
1140 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
1141 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1142 "position out of bounds", goto error
);
1144 if (isl_aff_is_nan(aff
)) {
1148 if (!isl_val_is_rat(v
))
1149 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1150 "expecting rational value", goto error
);
1152 aff
= isl_aff_cow(aff
);
1156 aff
->v
= isl_vec_cow(aff
->v
);
1160 pos
+= isl_local_space_offset(aff
->ls
, type
);
1161 if (isl_int_is_one(v
->d
)) {
1162 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1163 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
1164 isl_int_add(aff
->v
->el
[1 + pos
], aff
->v
->el
[1 + pos
], v
->n
);
1165 aff
->v
= isl_vec_normalize(aff
->v
);
1169 isl_seq_scale(aff
->v
->el
+ 1,
1170 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
1171 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1172 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
1173 aff
->v
= isl_vec_normalize(aff
->v
);
1186 __isl_give isl_aff
*isl_aff_add_coefficient_si(__isl_take isl_aff
*aff
,
1187 enum isl_dim_type type
, int pos
, int v
)
1192 isl_int_set_si(t
, v
);
1193 aff
= isl_aff_add_coefficient(aff
, type
, pos
, t
);
1199 __isl_give isl_aff
*isl_aff_get_div(__isl_keep isl_aff
*aff
, int pos
)
1204 return isl_local_space_get_div(aff
->ls
, pos
);
1207 /* Return the negation of "aff".
1209 * As a special case, -NaN = NaN.
1211 __isl_give isl_aff
*isl_aff_neg(__isl_take isl_aff
*aff
)
1215 if (isl_aff_is_nan(aff
))
1217 aff
= isl_aff_cow(aff
);
1220 aff
->v
= isl_vec_cow(aff
->v
);
1222 return isl_aff_free(aff
);
1224 isl_seq_neg(aff
->v
->el
+ 1, aff
->v
->el
+ 1, aff
->v
->size
- 1);
1229 /* Remove divs from the local space that do not appear in the affine
1231 * We currently only remove divs at the end.
1232 * Some intermediate divs may also not appear directly in the affine
1233 * expression, but we would also need to check that no other divs are
1234 * defined in terms of them.
1236 __isl_give isl_aff
*isl_aff_remove_unused_divs( __isl_take isl_aff
*aff
)
1245 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1246 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1248 pos
= isl_seq_last_non_zero(aff
->v
->el
+ 1 + off
, n
) + 1;
1252 aff
= isl_aff_cow(aff
);
1256 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, isl_dim_div
, pos
, n
- pos
);
1257 aff
->v
= isl_vec_drop_els(aff
->v
, 1 + off
+ pos
, n
- pos
);
1258 if (!aff
->ls
|| !aff
->v
)
1259 return isl_aff_free(aff
);
1264 /* Given two affine expressions "p" of length p_len (including the
1265 * denominator and the constant term) and "subs" of length subs_len,
1266 * plug in "subs" for the variable at position "pos".
1267 * The variables of "subs" and "p" are assumed to match up to subs_len,
1268 * but "p" may have additional variables.
1269 * "v" is an initialized isl_int that can be used internally.
1271 * In particular, if "p" represents the expression
1275 * with i the variable at position "pos" and "subs" represents the expression
1279 * then the result represents the expression
1284 void isl_seq_substitute(isl_int
*p
, int pos
, isl_int
*subs
,
1285 int p_len
, int subs_len
, isl_int v
)
1287 isl_int_set(v
, p
[1 + pos
]);
1288 isl_int_set_si(p
[1 + pos
], 0);
1289 isl_seq_combine(p
+ 1, subs
[0], p
+ 1, v
, subs
+ 1, subs_len
- 1);
1290 isl_seq_scale(p
+ subs_len
, p
+ subs_len
, subs
[0], p_len
- subs_len
);
1291 isl_int_mul(p
[0], p
[0], subs
[0]);
1294 /* Look for any divs in the aff->ls with a denominator equal to one
1295 * and plug them into the affine expression and any subsequent divs
1296 * that may reference the div.
1298 static __isl_give isl_aff
*plug_in_integral_divs(__isl_take isl_aff
*aff
)
1304 isl_local_space
*ls
;
1310 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1312 for (i
= 0; i
< n
; ++i
) {
1313 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][0]))
1315 ls
= isl_local_space_copy(aff
->ls
);
1316 ls
= isl_local_space_substitute_seq(ls
, isl_dim_div
, i
,
1317 aff
->ls
->div
->row
[i
], len
, i
+ 1, n
- (i
+ 1));
1318 vec
= isl_vec_copy(aff
->v
);
1319 vec
= isl_vec_cow(vec
);
1325 pos
= isl_local_space_offset(aff
->ls
, isl_dim_div
) + i
;
1326 isl_seq_substitute(vec
->el
, pos
, aff
->ls
->div
->row
[i
],
1331 isl_vec_free(aff
->v
);
1333 isl_local_space_free(aff
->ls
);
1340 isl_local_space_free(ls
);
1341 return isl_aff_free(aff
);
1344 /* Look for any divs j that appear with a unit coefficient inside
1345 * the definitions of other divs i and plug them into the definitions
1348 * In particular, an expression of the form
1350 * floor((f(..) + floor(g(..)/n))/m)
1354 * floor((n * f(..) + g(..))/(n * m))
1356 * This simplification is correct because we can move the expression
1357 * f(..) into the inner floor in the original expression to obtain
1359 * floor(floor((n * f(..) + g(..))/n)/m)
1361 * from which we can derive the simplified expression.
1363 static __isl_give isl_aff
*plug_in_unit_divs(__isl_take isl_aff
*aff
)
1371 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1372 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1373 for (i
= 1; i
< n
; ++i
) {
1374 for (j
= 0; j
< i
; ++j
) {
1375 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][1 + off
+ j
]))
1377 aff
->ls
= isl_local_space_substitute_seq(aff
->ls
,
1378 isl_dim_div
, j
, aff
->ls
->div
->row
[j
],
1379 aff
->v
->size
, i
, 1);
1381 return isl_aff_free(aff
);
1388 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
1390 * Even though this function is only called on isl_affs with a single
1391 * reference, we are careful to only change aff->v and aff->ls together.
1393 static __isl_give isl_aff
*swap_div(__isl_take isl_aff
*aff
, int a
, int b
)
1395 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1396 isl_local_space
*ls
;
1399 ls
= isl_local_space_copy(aff
->ls
);
1400 ls
= isl_local_space_swap_div(ls
, a
, b
);
1401 v
= isl_vec_copy(aff
->v
);
1406 isl_int_swap(v
->el
[1 + off
+ a
], v
->el
[1 + off
+ b
]);
1407 isl_vec_free(aff
->v
);
1409 isl_local_space_free(aff
->ls
);
1415 isl_local_space_free(ls
);
1416 return isl_aff_free(aff
);
1419 /* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
1421 * We currently do not actually remove div "b", but simply add its
1422 * coefficient to that of "a" and then zero it out.
1424 static __isl_give isl_aff
*merge_divs(__isl_take isl_aff
*aff
, int a
, int b
)
1426 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1428 if (isl_int_is_zero(aff
->v
->el
[1 + off
+ b
]))
1431 aff
->v
= isl_vec_cow(aff
->v
);
1433 return isl_aff_free(aff
);
1435 isl_int_add(aff
->v
->el
[1 + off
+ a
],
1436 aff
->v
->el
[1 + off
+ a
], aff
->v
->el
[1 + off
+ b
]);
1437 isl_int_set_si(aff
->v
->el
[1 + off
+ b
], 0);
1442 /* Sort the divs in the local space of "aff" according to
1443 * the comparison function "cmp_row" in isl_local_space.c,
1444 * combining the coefficients of identical divs.
1446 * Reordering divs does not change the semantics of "aff",
1447 * so there is no need to call isl_aff_cow.
1448 * Moreover, this function is currently only called on isl_affs
1449 * with a single reference.
1451 static __isl_give isl_aff
*sort_divs(__isl_take isl_aff
*aff
)
1459 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1460 n
= isl_aff_dim(aff
, isl_dim_div
);
1461 for (i
= 1; i
< n
; ++i
) {
1462 for (j
= i
- 1; j
>= 0; --j
) {
1463 int cmp
= isl_mat_cmp_div(aff
->ls
->div
, j
, j
+ 1);
1467 aff
= merge_divs(aff
, j
, j
+ 1);
1469 aff
= swap_div(aff
, j
, j
+ 1);
1478 /* Normalize the representation of "aff".
1480 * This function should only be called of "new" isl_affs, i.e.,
1481 * with only a single reference. We therefore do not need to
1482 * worry about affecting other instances.
1484 __isl_give isl_aff
*isl_aff_normalize(__isl_take isl_aff
*aff
)
1488 aff
->v
= isl_vec_normalize(aff
->v
);
1490 return isl_aff_free(aff
);
1491 aff
= plug_in_integral_divs(aff
);
1492 aff
= plug_in_unit_divs(aff
);
1493 aff
= sort_divs(aff
);
1494 aff
= isl_aff_remove_unused_divs(aff
);
1498 /* Given f, return floor(f).
1499 * If f is an integer expression, then just return f.
1500 * If f is a constant, then return the constant floor(f).
1501 * Otherwise, if f = g/m, write g = q m + r,
1502 * create a new div d = [r/m] and return the expression q + d.
1503 * The coefficients in r are taken to lie between -m/2 and m/2.
1505 * As a special case, floor(NaN) = NaN.
1507 __isl_give isl_aff
*isl_aff_floor(__isl_take isl_aff
*aff
)
1517 if (isl_aff_is_nan(aff
))
1519 if (isl_int_is_one(aff
->v
->el
[0]))
1522 aff
= isl_aff_cow(aff
);
1526 aff
->v
= isl_vec_cow(aff
->v
);
1528 return isl_aff_free(aff
);
1530 if (isl_aff_is_cst(aff
)) {
1531 isl_int_fdiv_q(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1532 isl_int_set_si(aff
->v
->el
[0], 1);
1536 div
= isl_vec_copy(aff
->v
);
1537 div
= isl_vec_cow(div
);
1539 return isl_aff_free(aff
);
1541 ctx
= isl_aff_get_ctx(aff
);
1542 isl_int_fdiv_q(aff
->v
->el
[0], aff
->v
->el
[0], ctx
->two
);
1543 for (i
= 1; i
< aff
->v
->size
; ++i
) {
1544 isl_int_fdiv_r(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1545 isl_int_fdiv_q(aff
->v
->el
[i
], aff
->v
->el
[i
], div
->el
[0]);
1546 if (isl_int_gt(div
->el
[i
], aff
->v
->el
[0])) {
1547 isl_int_sub(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1548 isl_int_add_ui(aff
->v
->el
[i
], aff
->v
->el
[i
], 1);
1552 aff
->ls
= isl_local_space_add_div(aff
->ls
, div
);
1554 return isl_aff_free(aff
);
1556 size
= aff
->v
->size
;
1557 aff
->v
= isl_vec_extend(aff
->v
, size
+ 1);
1559 return isl_aff_free(aff
);
1560 isl_int_set_si(aff
->v
->el
[0], 1);
1561 isl_int_set_si(aff
->v
->el
[size
], 1);
1563 aff
= isl_aff_normalize(aff
);
1570 * aff mod m = aff - m * floor(aff/m)
1572 __isl_give isl_aff
*isl_aff_mod(__isl_take isl_aff
*aff
, isl_int m
)
1576 res
= isl_aff_copy(aff
);
1577 aff
= isl_aff_scale_down(aff
, m
);
1578 aff
= isl_aff_floor(aff
);
1579 aff
= isl_aff_scale(aff
, m
);
1580 res
= isl_aff_sub(res
, aff
);
1587 * aff mod m = aff - m * floor(aff/m)
1589 * with m an integer value.
1591 __isl_give isl_aff
*isl_aff_mod_val(__isl_take isl_aff
*aff
,
1592 __isl_take isl_val
*m
)
1599 if (!isl_val_is_int(m
))
1600 isl_die(isl_val_get_ctx(m
), isl_error_invalid
,
1601 "expecting integer modulo", goto error
);
1603 res
= isl_aff_copy(aff
);
1604 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(m
));
1605 aff
= isl_aff_floor(aff
);
1606 aff
= isl_aff_scale_val(aff
, m
);
1607 res
= isl_aff_sub(res
, aff
);
1618 * pwaff mod m = pwaff - m * floor(pwaff/m)
1620 __isl_give isl_pw_aff
*isl_pw_aff_mod(__isl_take isl_pw_aff
*pwaff
, isl_int m
)
1624 res
= isl_pw_aff_copy(pwaff
);
1625 pwaff
= isl_pw_aff_scale_down(pwaff
, m
);
1626 pwaff
= isl_pw_aff_floor(pwaff
);
1627 pwaff
= isl_pw_aff_scale(pwaff
, m
);
1628 res
= isl_pw_aff_sub(res
, pwaff
);
1635 * pa mod m = pa - m * floor(pa/m)
1637 * with m an integer value.
1639 __isl_give isl_pw_aff
*isl_pw_aff_mod_val(__isl_take isl_pw_aff
*pa
,
1640 __isl_take isl_val
*m
)
1644 if (!isl_val_is_int(m
))
1645 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
1646 "expecting integer modulo", goto error
);
1647 pa
= isl_pw_aff_mod(pa
, m
->n
);
1651 isl_pw_aff_free(pa
);
1656 /* Given f, return ceil(f).
1657 * If f is an integer expression, then just return f.
1658 * Otherwise, let f be the expression
1664 * floor((e + m - 1)/m)
1666 * As a special case, ceil(NaN) = NaN.
1668 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
1673 if (isl_aff_is_nan(aff
))
1675 if (isl_int_is_one(aff
->v
->el
[0]))
1678 aff
= isl_aff_cow(aff
);
1681 aff
->v
= isl_vec_cow(aff
->v
);
1683 return isl_aff_free(aff
);
1685 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1686 isl_int_sub_ui(aff
->v
->el
[1], aff
->v
->el
[1], 1);
1687 aff
= isl_aff_floor(aff
);
1692 /* Apply the expansion computed by isl_merge_divs.
1693 * The expansion itself is given by "exp" while the resulting
1694 * list of divs is given by "div".
1696 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
1697 __isl_take isl_mat
*div
, int *exp
)
1704 aff
= isl_aff_cow(aff
);
1708 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1709 new_n_div
= isl_mat_rows(div
);
1710 if (new_n_div
< old_n_div
)
1711 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
1712 "not an expansion", goto error
);
1714 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
1718 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
1720 for (i
= new_n_div
- 1; i
>= 0; --i
) {
1721 if (j
>= 0 && exp
[j
] == i
) {
1723 isl_int_swap(aff
->v
->el
[offset
+ i
],
1724 aff
->v
->el
[offset
+ j
]);
1727 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
1730 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
1741 /* Add two affine expressions that live in the same local space.
1743 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
1744 __isl_take isl_aff
*aff2
)
1748 aff1
= isl_aff_cow(aff1
);
1752 aff1
->v
= isl_vec_cow(aff1
->v
);
1758 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
1759 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1760 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
1761 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
1762 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
1763 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1764 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
1776 /* Return the sum of "aff1" and "aff2".
1778 * If either of the two is NaN, then the result is NaN.
1780 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
1781 __isl_take isl_aff
*aff2
)
1792 ctx
= isl_aff_get_ctx(aff1
);
1793 if (!isl_space_is_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
1794 isl_die(ctx
, isl_error_invalid
,
1795 "spaces don't match", goto error
);
1797 if (isl_aff_is_nan(aff1
)) {
1801 if (isl_aff_is_nan(aff2
)) {
1806 n_div1
= isl_aff_dim(aff1
, isl_dim_div
);
1807 n_div2
= isl_aff_dim(aff2
, isl_dim_div
);
1808 if (n_div1
== 0 && n_div2
== 0)
1809 return add_expanded(aff1
, aff2
);
1811 exp1
= isl_alloc_array(ctx
, int, n_div1
);
1812 exp2
= isl_alloc_array(ctx
, int, n_div2
);
1813 if ((n_div1
&& !exp1
) || (n_div2
&& !exp2
))
1816 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
1817 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
1818 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
1822 return add_expanded(aff1
, aff2
);
1831 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
1832 __isl_take isl_aff
*aff2
)
1834 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
1837 /* Return the result of scaling "aff" by a factor of "f".
1839 * As a special case, f * NaN = NaN.
1841 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
1847 if (isl_aff_is_nan(aff
))
1850 if (isl_int_is_one(f
))
1853 aff
= isl_aff_cow(aff
);
1856 aff
->v
= isl_vec_cow(aff
->v
);
1858 return isl_aff_free(aff
);
1860 if (isl_int_is_pos(f
) && isl_int_is_divisible_by(aff
->v
->el
[0], f
)) {
1861 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], f
);
1866 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
1867 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1868 isl_int_divexact(gcd
, f
, gcd
);
1869 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1875 /* Multiple "aff" by "v".
1877 __isl_give isl_aff
*isl_aff_scale_val(__isl_take isl_aff
*aff
,
1878 __isl_take isl_val
*v
)
1883 if (isl_val_is_one(v
)) {
1888 if (!isl_val_is_rat(v
))
1889 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1890 "expecting rational factor", goto error
);
1892 aff
= isl_aff_scale(aff
, v
->n
);
1893 aff
= isl_aff_scale_down(aff
, v
->d
);
1903 /* Return the result of scaling "aff" down by a factor of "f".
1905 * As a special case, NaN/f = NaN.
1907 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
1913 if (isl_aff_is_nan(aff
))
1916 if (isl_int_is_one(f
))
1919 aff
= isl_aff_cow(aff
);
1923 if (isl_int_is_zero(f
))
1924 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1925 "cannot scale down by zero", return isl_aff_free(aff
));
1927 aff
->v
= isl_vec_cow(aff
->v
);
1929 return isl_aff_free(aff
);
1932 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
1933 isl_int_gcd(gcd
, gcd
, f
);
1934 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1935 isl_int_divexact(gcd
, f
, gcd
);
1936 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1942 /* Divide "aff" by "v".
1944 __isl_give isl_aff
*isl_aff_scale_down_val(__isl_take isl_aff
*aff
,
1945 __isl_take isl_val
*v
)
1950 if (isl_val_is_one(v
)) {
1955 if (!isl_val_is_rat(v
))
1956 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1957 "expecting rational factor", goto error
);
1958 if (!isl_val_is_pos(v
))
1959 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1960 "factor needs to be positive", goto error
);
1962 aff
= isl_aff_scale(aff
, v
->d
);
1963 aff
= isl_aff_scale_down(aff
, v
->n
);
1973 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
1981 isl_int_set_ui(v
, f
);
1982 aff
= isl_aff_scale_down(aff
, v
);
1988 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
1989 enum isl_dim_type type
, unsigned pos
, const char *s
)
1991 aff
= isl_aff_cow(aff
);
1994 if (type
== isl_dim_out
)
1995 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1996 "cannot set name of output/set dimension",
1997 return isl_aff_free(aff
));
1998 if (type
== isl_dim_in
)
2000 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
2002 return isl_aff_free(aff
);
2007 __isl_give isl_aff
*isl_aff_set_dim_id(__isl_take isl_aff
*aff
,
2008 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
2010 aff
= isl_aff_cow(aff
);
2013 if (type
== isl_dim_out
)
2014 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2015 "cannot set name of output/set dimension",
2017 if (type
== isl_dim_in
)
2019 aff
->ls
= isl_local_space_set_dim_id(aff
->ls
, type
, pos
, id
);
2021 return isl_aff_free(aff
);
2030 /* Replace the identifier of the input tuple of "aff" by "id".
2031 * type is currently required to be equal to isl_dim_in
2033 __isl_give isl_aff
*isl_aff_set_tuple_id(__isl_take isl_aff
*aff
,
2034 enum isl_dim_type type
, __isl_take isl_id
*id
)
2036 aff
= isl_aff_cow(aff
);
2039 if (type
!= isl_dim_out
)
2040 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2041 "cannot only set id of input tuple", goto error
);
2042 aff
->ls
= isl_local_space_set_tuple_id(aff
->ls
, isl_dim_set
, id
);
2044 return isl_aff_free(aff
);
2053 /* Exploit the equalities in "eq" to simplify the affine expression
2054 * and the expressions of the integer divisions in the local space.
2055 * The integer divisions in this local space are assumed to appear
2056 * as regular dimensions in "eq".
2058 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
2059 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
2067 if (eq
->n_eq
== 0) {
2068 isl_basic_set_free(eq
);
2072 aff
= isl_aff_cow(aff
);
2076 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
2077 isl_basic_set_copy(eq
));
2078 aff
->v
= isl_vec_cow(aff
->v
);
2079 if (!aff
->ls
|| !aff
->v
)
2082 total
= 1 + isl_space_dim(eq
->dim
, isl_dim_all
);
2084 for (i
= 0; i
< eq
->n_eq
; ++i
) {
2085 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
2086 if (j
< 0 || j
== 0 || j
>= total
)
2089 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
2093 isl_basic_set_free(eq
);
2094 aff
= isl_aff_normalize(aff
);
2097 isl_basic_set_free(eq
);
2102 /* Exploit the equalities in "eq" to simplify the affine expression
2103 * and the expressions of the integer divisions in the local space.
2105 __isl_give isl_aff
*isl_aff_substitute_equalities(__isl_take isl_aff
*aff
,
2106 __isl_take isl_basic_set
*eq
)
2112 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
2114 eq
= isl_basic_set_add_dims(eq
, isl_dim_set
, n_div
);
2115 return isl_aff_substitute_equalities_lifted(aff
, eq
);
2117 isl_basic_set_free(eq
);
2122 /* Look for equalities among the variables shared by context and aff
2123 * and the integer divisions of aff, if any.
2124 * The equalities are then used to eliminate coefficients and/or integer
2125 * divisions from aff.
2127 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
2128 __isl_take isl_set
*context
)
2130 isl_basic_set
*hull
;
2135 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
2137 isl_basic_set
*bset
;
2138 isl_local_space
*ls
;
2139 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
2140 ls
= isl_aff_get_domain_local_space(aff
);
2141 bset
= isl_basic_set_from_local_space(ls
);
2142 bset
= isl_basic_set_lift(bset
);
2143 bset
= isl_basic_set_flatten(bset
);
2144 context
= isl_set_intersect(context
,
2145 isl_set_from_basic_set(bset
));
2148 hull
= isl_set_affine_hull(context
);
2149 return isl_aff_substitute_equalities_lifted(aff
, hull
);
2152 isl_set_free(context
);
2156 __isl_give isl_aff
*isl_aff_gist_params(__isl_take isl_aff
*aff
,
2157 __isl_take isl_set
*context
)
2159 isl_set
*dom_context
= isl_set_universe(isl_aff_get_domain_space(aff
));
2160 dom_context
= isl_set_intersect_params(dom_context
, context
);
2161 return isl_aff_gist(aff
, dom_context
);
2164 /* Return a basic set containing those elements in the space
2165 * of aff where it is positive. "rational" should not be set.
2167 * If "aff" is NaN, then it is not positive.
2169 static __isl_give isl_basic_set
*aff_pos_basic_set(__isl_take isl_aff
*aff
,
2172 isl_constraint
*ineq
;
2173 isl_basic_set
*bset
;
2178 if (isl_aff_is_nan(aff
)) {
2179 isl_space
*space
= isl_aff_get_domain_space(aff
);
2181 return isl_basic_set_empty(space
);
2184 isl_die(isl_aff_get_ctx(aff
), isl_error_unsupported
,
2185 "rational sets not supported", goto error
);
2187 ineq
= isl_inequality_from_aff(aff
);
2188 c
= isl_constraint_get_constant_val(ineq
);
2189 c
= isl_val_sub_ui(c
, 1);
2190 ineq
= isl_constraint_set_constant_val(ineq
, c
);
2192 bset
= isl_basic_set_from_constraint(ineq
);
2193 bset
= isl_basic_set_simplify(bset
);
2200 /* Return a basic set containing those elements in the space
2201 * of aff where it is non-negative.
2202 * If "rational" is set, then return a rational basic set.
2204 * If "aff" is NaN, then it is not non-negative (it's not negative either).
2206 static __isl_give isl_basic_set
*aff_nonneg_basic_set(
2207 __isl_take isl_aff
*aff
, int rational
)
2209 isl_constraint
*ineq
;
2210 isl_basic_set
*bset
;
2214 if (isl_aff_is_nan(aff
)) {
2215 isl_space
*space
= isl_aff_get_domain_space(aff
);
2217 return isl_basic_set_empty(space
);
2220 ineq
= isl_inequality_from_aff(aff
);
2222 bset
= isl_basic_set_from_constraint(ineq
);
2224 bset
= isl_basic_set_set_rational(bset
);
2225 bset
= isl_basic_set_simplify(bset
);
2229 /* Return a basic set containing those elements in the space
2230 * of aff where it is non-negative.
2232 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
2234 return aff_nonneg_basic_set(aff
, 0);
2237 /* Return a basic set containing those elements in the domain space
2238 * of aff where it is negative.
2240 __isl_give isl_basic_set
*isl_aff_neg_basic_set(__isl_take isl_aff
*aff
)
2242 aff
= isl_aff_neg(aff
);
2243 aff
= isl_aff_add_constant_num_si(aff
, -1);
2244 return isl_aff_nonneg_basic_set(aff
);
2247 /* Return a basic set containing those elements in the space
2248 * of aff where it is zero.
2249 * If "rational" is set, then return a rational basic set.
2251 * If "aff" is NaN, then it is not zero.
2253 static __isl_give isl_basic_set
*aff_zero_basic_set(__isl_take isl_aff
*aff
,
2256 isl_constraint
*ineq
;
2257 isl_basic_set
*bset
;
2261 if (isl_aff_is_nan(aff
)) {
2262 isl_space
*space
= isl_aff_get_domain_space(aff
);
2264 return isl_basic_set_empty(space
);
2267 ineq
= isl_equality_from_aff(aff
);
2269 bset
= isl_basic_set_from_constraint(ineq
);
2271 bset
= isl_basic_set_set_rational(bset
);
2272 bset
= isl_basic_set_simplify(bset
);
2276 /* Return a basic set containing those elements in the space
2277 * of aff where it is zero.
2279 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
2281 return aff_zero_basic_set(aff
, 0);
2284 /* Return a basic set containing those elements in the shared space
2285 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
2287 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
2288 __isl_take isl_aff
*aff2
)
2290 aff1
= isl_aff_sub(aff1
, aff2
);
2292 return isl_aff_nonneg_basic_set(aff1
);
2295 /* Return a basic set containing those elements in the shared space
2296 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
2298 __isl_give isl_basic_set
*isl_aff_le_basic_set(__isl_take isl_aff
*aff1
,
2299 __isl_take isl_aff
*aff2
)
2301 return isl_aff_ge_basic_set(aff2
, aff1
);
2304 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
2305 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
2307 aff1
= isl_aff_add(aff1
, aff2
);
2308 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
2312 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
2320 /* Check whether the given affine expression has non-zero coefficient
2321 * for any dimension in the given range or if any of these dimensions
2322 * appear with non-zero coefficients in any of the integer divisions
2323 * involved in the affine expression.
2325 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
2326 enum isl_dim_type type
, unsigned first
, unsigned n
)
2338 ctx
= isl_aff_get_ctx(aff
);
2339 if (first
+ n
> isl_aff_dim(aff
, type
))
2340 isl_die(ctx
, isl_error_invalid
,
2341 "range out of bounds", return -1);
2343 active
= isl_local_space_get_active(aff
->ls
, aff
->v
->el
+ 2);
2347 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
2348 for (i
= 0; i
< n
; ++i
)
2349 if (active
[first
+ i
]) {
2362 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
2363 enum isl_dim_type type
, unsigned first
, unsigned n
)
2369 if (type
== isl_dim_out
)
2370 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2371 "cannot drop output/set dimension",
2372 return isl_aff_free(aff
));
2373 if (type
== isl_dim_in
)
2375 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
2378 ctx
= isl_aff_get_ctx(aff
);
2379 if (first
+ n
> isl_local_space_dim(aff
->ls
, type
))
2380 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
2381 return isl_aff_free(aff
));
2383 aff
= isl_aff_cow(aff
);
2387 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
2389 return isl_aff_free(aff
);
2391 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2392 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
2394 return isl_aff_free(aff
);
2399 /* Project the domain of the affine expression onto its parameter space.
2400 * The affine expression may not involve any of the domain dimensions.
2402 __isl_give isl_aff
*isl_aff_project_domain_on_params(__isl_take isl_aff
*aff
)
2408 n
= isl_aff_dim(aff
, isl_dim_in
);
2409 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, 0, n
);
2411 return isl_aff_free(aff
);
2413 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2414 "affine expression involves some of the domain dimensions",
2415 return isl_aff_free(aff
));
2416 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, 0, n
);
2417 space
= isl_aff_get_domain_space(aff
);
2418 space
= isl_space_params(space
);
2419 aff
= isl_aff_reset_domain_space(aff
, space
);
2423 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
2424 enum isl_dim_type type
, unsigned first
, unsigned n
)
2430 if (type
== isl_dim_out
)
2431 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2432 "cannot insert output/set dimensions",
2433 return isl_aff_free(aff
));
2434 if (type
== isl_dim_in
)
2436 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
2439 ctx
= isl_aff_get_ctx(aff
);
2440 if (first
> isl_local_space_dim(aff
->ls
, type
))
2441 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
2442 return isl_aff_free(aff
));
2444 aff
= isl_aff_cow(aff
);
2448 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
2450 return isl_aff_free(aff
);
2452 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2453 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
2455 return isl_aff_free(aff
);
2460 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
2461 enum isl_dim_type type
, unsigned n
)
2465 pos
= isl_aff_dim(aff
, type
);
2467 return isl_aff_insert_dims(aff
, type
, pos
, n
);
2470 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
2471 enum isl_dim_type type
, unsigned n
)
2475 pos
= isl_pw_aff_dim(pwaff
, type
);
2477 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
2480 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "aff"
2481 * to dimensions of "dst_type" at "dst_pos".
2483 * We only support moving input dimensions to parameters and vice versa.
2485 __isl_give isl_aff
*isl_aff_move_dims(__isl_take isl_aff
*aff
,
2486 enum isl_dim_type dst_type
, unsigned dst_pos
,
2487 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
2495 !isl_local_space_is_named_or_nested(aff
->ls
, src_type
) &&
2496 !isl_local_space_is_named_or_nested(aff
->ls
, dst_type
))
2499 if (dst_type
== isl_dim_out
|| src_type
== isl_dim_out
)
2500 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2501 "cannot move output/set dimension", isl_aff_free(aff
));
2502 if (dst_type
== isl_dim_div
|| src_type
== isl_dim_div
)
2503 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2504 "cannot move divs", isl_aff_free(aff
));
2505 if (dst_type
== isl_dim_in
)
2506 dst_type
= isl_dim_set
;
2507 if (src_type
== isl_dim_in
)
2508 src_type
= isl_dim_set
;
2510 if (src_pos
+ n
> isl_local_space_dim(aff
->ls
, src_type
))
2511 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2512 "range out of bounds", isl_aff_free(aff
));
2513 if (dst_type
== src_type
)
2514 isl_die(isl_aff_get_ctx(aff
), isl_error_unsupported
,
2515 "moving dims within the same type not supported",
2518 aff
= isl_aff_cow(aff
);
2522 g_src_pos
= 1 + isl_local_space_offset(aff
->ls
, src_type
) + src_pos
;
2523 g_dst_pos
= 1 + isl_local_space_offset(aff
->ls
, dst_type
) + dst_pos
;
2524 if (dst_type
> src_type
)
2527 aff
->v
= isl_vec_move_els(aff
->v
, g_dst_pos
, g_src_pos
, n
);
2528 aff
->ls
= isl_local_space_move_dims(aff
->ls
, dst_type
, dst_pos
,
2529 src_type
, src_pos
, n
);
2530 if (!aff
->v
|| !aff
->ls
)
2531 return isl_aff_free(aff
);
2533 aff
= sort_divs(aff
);
2538 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
2540 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
2541 return isl_pw_aff_alloc(dom
, aff
);
2545 #define PW isl_pw_aff
2549 #define EL_IS_ZERO is_empty
2553 #define IS_ZERO is_empty
2556 #undef DEFAULT_IS_ZERO
2557 #define DEFAULT_IS_ZERO 0
2564 #include <isl_pw_templ.c>
2566 static __isl_give isl_set
*align_params_pw_pw_set_and(
2567 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
2568 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2569 __isl_take isl_pw_aff
*pwaff2
))
2571 if (!pwaff1
|| !pwaff2
)
2573 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
2574 pwaff2
->dim
, isl_dim_param
))
2575 return fn(pwaff1
, pwaff2
);
2576 if (!isl_space_has_named_params(pwaff1
->dim
) ||
2577 !isl_space_has_named_params(pwaff2
->dim
))
2578 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
2579 "unaligned unnamed parameters", goto error
);
2580 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
2581 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
2582 return fn(pwaff1
, pwaff2
);
2584 isl_pw_aff_free(pwaff1
);
2585 isl_pw_aff_free(pwaff2
);
2589 /* Compute a piecewise quasi-affine expression with a domain that
2590 * is the union of those of pwaff1 and pwaff2 and such that on each
2591 * cell, the quasi-affine expression is the better (according to cmp)
2592 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
2593 * is defined on a given cell, then the associated expression
2594 * is the defined one.
2596 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2597 __isl_take isl_pw_aff
*pwaff2
,
2598 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
2599 __isl_take isl_aff
*aff2
))
2606 if (!pwaff1
|| !pwaff2
)
2609 ctx
= isl_space_get_ctx(pwaff1
->dim
);
2610 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
2611 isl_die(ctx
, isl_error_invalid
,
2612 "arguments should live in same space", goto error
);
2614 if (isl_pw_aff_is_empty(pwaff1
)) {
2615 isl_pw_aff_free(pwaff1
);
2619 if (isl_pw_aff_is_empty(pwaff2
)) {
2620 isl_pw_aff_free(pwaff2
);
2624 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
2625 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
2627 for (i
= 0; i
< pwaff1
->n
; ++i
) {
2628 set
= isl_set_copy(pwaff1
->p
[i
].set
);
2629 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2630 struct isl_set
*common
;
2633 common
= isl_set_intersect(
2634 isl_set_copy(pwaff1
->p
[i
].set
),
2635 isl_set_copy(pwaff2
->p
[j
].set
));
2636 better
= isl_set_from_basic_set(cmp(
2637 isl_aff_copy(pwaff2
->p
[j
].aff
),
2638 isl_aff_copy(pwaff1
->p
[i
].aff
)));
2639 better
= isl_set_intersect(common
, better
);
2640 if (isl_set_plain_is_empty(better
)) {
2641 isl_set_free(better
);
2644 set
= isl_set_subtract(set
, isl_set_copy(better
));
2646 res
= isl_pw_aff_add_piece(res
, better
,
2647 isl_aff_copy(pwaff2
->p
[j
].aff
));
2649 res
= isl_pw_aff_add_piece(res
, set
,
2650 isl_aff_copy(pwaff1
->p
[i
].aff
));
2653 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2654 set
= isl_set_copy(pwaff2
->p
[j
].set
);
2655 for (i
= 0; i
< pwaff1
->n
; ++i
)
2656 set
= isl_set_subtract(set
,
2657 isl_set_copy(pwaff1
->p
[i
].set
));
2658 res
= isl_pw_aff_add_piece(res
, set
,
2659 isl_aff_copy(pwaff2
->p
[j
].aff
));
2662 isl_pw_aff_free(pwaff1
);
2663 isl_pw_aff_free(pwaff2
);
2667 isl_pw_aff_free(pwaff1
);
2668 isl_pw_aff_free(pwaff2
);
2672 /* Compute a piecewise quasi-affine expression with a domain that
2673 * is the union of those of pwaff1 and pwaff2 and such that on each
2674 * cell, the quasi-affine expression is the maximum of those of pwaff1
2675 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2676 * cell, then the associated expression is the defined one.
2678 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2679 __isl_take isl_pw_aff
*pwaff2
)
2681 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
2684 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2685 __isl_take isl_pw_aff
*pwaff2
)
2687 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2691 /* Compute a piecewise quasi-affine expression with a domain that
2692 * is the union of those of pwaff1 and pwaff2 and such that on each
2693 * cell, the quasi-affine expression is the minimum of those of pwaff1
2694 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2695 * cell, then the associated expression is the defined one.
2697 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2698 __isl_take isl_pw_aff
*pwaff2
)
2700 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
2703 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2704 __isl_take isl_pw_aff
*pwaff2
)
2706 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2710 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2711 __isl_take isl_pw_aff
*pwaff2
, int max
)
2714 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
2716 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
2719 /* Construct a map with as domain the domain of pwaff and
2720 * one-dimensional range corresponding to the affine expressions.
2722 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2731 dim
= isl_pw_aff_get_space(pwaff
);
2732 map
= isl_map_empty(dim
);
2734 for (i
= 0; i
< pwaff
->n
; ++i
) {
2735 isl_basic_map
*bmap
;
2738 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
2739 map_i
= isl_map_from_basic_map(bmap
);
2740 map_i
= isl_map_intersect_domain(map_i
,
2741 isl_set_copy(pwaff
->p
[i
].set
));
2742 map
= isl_map_union_disjoint(map
, map_i
);
2745 isl_pw_aff_free(pwaff
);
2750 /* Construct a map with as domain the domain of pwaff and
2751 * one-dimensional range corresponding to the affine expressions.
2753 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2757 if (isl_space_is_set(pwaff
->dim
))
2758 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2759 "space of input is not a map", goto error
);
2760 return map_from_pw_aff(pwaff
);
2762 isl_pw_aff_free(pwaff
);
2766 /* Construct a one-dimensional set with as parameter domain
2767 * the domain of pwaff and the single set dimension
2768 * corresponding to the affine expressions.
2770 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2774 if (!isl_space_is_set(pwaff
->dim
))
2775 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2776 "space of input is not a set", goto error
);
2777 return map_from_pw_aff(pwaff
);
2779 isl_pw_aff_free(pwaff
);
2783 /* Return a set containing those elements in the domain
2784 * of "pwaff" where it satisfies "fn" (if complement is 0) or
2785 * does not satisfy "fn" (if complement is 1).
2787 * The pieces with a NaN never belong to the result since
2788 * NaN does not satisfy any property.
2790 static __isl_give isl_set
*pw_aff_locus(__isl_take isl_pw_aff
*pwaff
,
2791 __isl_give isl_basic_set
*(*fn
)(__isl_take isl_aff
*aff
, int rational
),
2800 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2802 for (i
= 0; i
< pwaff
->n
; ++i
) {
2803 isl_basic_set
*bset
;
2804 isl_set
*set_i
, *locus
;
2807 if (isl_aff_is_nan(pwaff
->p
[i
].aff
))
2810 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2811 bset
= fn(isl_aff_copy(pwaff
->p
[i
].aff
), rational
);
2812 locus
= isl_set_from_basic_set(bset
);
2813 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
2815 set_i
= isl_set_subtract(set_i
, locus
);
2817 set_i
= isl_set_intersect(set_i
, locus
);
2818 set
= isl_set_union_disjoint(set
, set_i
);
2821 isl_pw_aff_free(pwaff
);
2826 /* Return a set containing those elements in the domain
2827 * of "pa" where it is positive.
2829 __isl_give isl_set
*isl_pw_aff_pos_set(__isl_take isl_pw_aff
*pa
)
2831 return pw_aff_locus(pa
, &aff_pos_basic_set
, 0);
2834 /* Return a set containing those elements in the domain
2835 * of pwaff where it is non-negative.
2837 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
2839 return pw_aff_locus(pwaff
, &aff_nonneg_basic_set
, 0);
2842 /* Return a set containing those elements in the domain
2843 * of pwaff where it is zero.
2845 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
2847 return pw_aff_locus(pwaff
, &aff_zero_basic_set
, 0);
2850 /* Return a set containing those elements in the domain
2851 * of pwaff where it is not zero.
2853 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
2855 return pw_aff_locus(pwaff
, &aff_zero_basic_set
, 1);
2858 /* Return a set containing those elements in the shared domain
2859 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2861 * We compute the difference on the shared domain and then construct
2862 * the set of values where this difference is non-negative.
2863 * If strict is set, we first subtract 1 from the difference.
2864 * If equal is set, we only return the elements where pwaff1 and pwaff2
2867 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
2868 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
2870 isl_set
*set1
, *set2
;
2872 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
2873 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
2874 set1
= isl_set_intersect(set1
, set2
);
2875 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
2876 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
2877 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
2880 isl_space
*dim
= isl_set_get_space(set1
);
2882 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2883 aff
= isl_aff_add_constant_si(aff
, -1);
2884 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
2889 return isl_pw_aff_zero_set(pwaff1
);
2890 return isl_pw_aff_nonneg_set(pwaff1
);
2893 /* Return a set containing those elements in the shared domain
2894 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2896 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2897 __isl_take isl_pw_aff
*pwaff2
)
2899 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
2902 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2903 __isl_take isl_pw_aff
*pwaff2
)
2905 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2908 /* Return a set containing those elements in the shared domain
2909 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2911 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2912 __isl_take isl_pw_aff
*pwaff2
)
2914 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2917 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2918 __isl_take isl_pw_aff
*pwaff2
)
2920 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2923 /* Return a set containing those elements in the shared domain
2924 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2926 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2927 __isl_take isl_pw_aff
*pwaff2
)
2929 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2932 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2933 __isl_take isl_pw_aff
*pwaff2
)
2935 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2938 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2939 __isl_take isl_pw_aff
*pwaff2
)
2941 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2944 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2945 __isl_take isl_pw_aff
*pwaff2
)
2947 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2950 /* Return a set containing those elements in the shared domain
2951 * of the elements of list1 and list2 where each element in list1
2952 * has the relation specified by "fn" with each element in list2.
2954 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2955 __isl_take isl_pw_aff_list
*list2
,
2956 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2957 __isl_take isl_pw_aff
*pwaff2
))
2963 if (!list1
|| !list2
)
2966 ctx
= isl_pw_aff_list_get_ctx(list1
);
2967 if (list1
->n
< 1 || list2
->n
< 1)
2968 isl_die(ctx
, isl_error_invalid
,
2969 "list should contain at least one element", goto error
);
2971 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2972 for (i
= 0; i
< list1
->n
; ++i
)
2973 for (j
= 0; j
< list2
->n
; ++j
) {
2976 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2977 isl_pw_aff_copy(list2
->p
[j
]));
2978 set
= isl_set_intersect(set
, set_ij
);
2981 isl_pw_aff_list_free(list1
);
2982 isl_pw_aff_list_free(list2
);
2985 isl_pw_aff_list_free(list1
);
2986 isl_pw_aff_list_free(list2
);
2990 /* Return a set containing those elements in the shared domain
2991 * of the elements of list1 and list2 where each element in list1
2992 * is equal to each element in list2.
2994 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2995 __isl_take isl_pw_aff_list
*list2
)
2997 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
3000 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
3001 __isl_take isl_pw_aff_list
*list2
)
3003 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
3006 /* Return a set containing those elements in the shared domain
3007 * of the elements of list1 and list2 where each element in list1
3008 * is less than or equal to each element in list2.
3010 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
3011 __isl_take isl_pw_aff_list
*list2
)
3013 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
3016 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
3017 __isl_take isl_pw_aff_list
*list2
)
3019 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
3022 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
3023 __isl_take isl_pw_aff_list
*list2
)
3025 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
3028 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
3029 __isl_take isl_pw_aff_list
*list2
)
3031 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
3035 /* Return a set containing those elements in the shared domain
3036 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
3038 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
3039 __isl_take isl_pw_aff
*pwaff2
)
3041 isl_set
*set_lt
, *set_gt
;
3043 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
3044 isl_pw_aff_copy(pwaff2
));
3045 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
3046 return isl_set_union_disjoint(set_lt
, set_gt
);
3049 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
3050 __isl_take isl_pw_aff
*pwaff2
)
3052 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
3055 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
3060 if (isl_int_is_one(v
))
3062 if (!isl_int_is_pos(v
))
3063 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
3064 "factor needs to be positive",
3065 return isl_pw_aff_free(pwaff
));
3066 pwaff
= isl_pw_aff_cow(pwaff
);
3072 for (i
= 0; i
< pwaff
->n
; ++i
) {
3073 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
3074 if (!pwaff
->p
[i
].aff
)
3075 return isl_pw_aff_free(pwaff
);
3081 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
3085 pwaff
= isl_pw_aff_cow(pwaff
);
3091 for (i
= 0; i
< pwaff
->n
; ++i
) {
3092 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
3093 if (!pwaff
->p
[i
].aff
)
3094 return isl_pw_aff_free(pwaff
);
3100 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
3104 pwaff
= isl_pw_aff_cow(pwaff
);
3110 for (i
= 0; i
< pwaff
->n
; ++i
) {
3111 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
3112 if (!pwaff
->p
[i
].aff
)
3113 return isl_pw_aff_free(pwaff
);
3119 /* Assuming that "cond1" and "cond2" are disjoint,
3120 * return an affine expression that is equal to pwaff1 on cond1
3121 * and to pwaff2 on cond2.
3123 static __isl_give isl_pw_aff
*isl_pw_aff_select(
3124 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
3125 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
3127 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
3128 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
3130 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
3133 /* Return an affine expression that is equal to pwaff_true for elements
3134 * where "cond" is non-zero and to pwaff_false for elements where "cond"
3136 * That is, return cond ? pwaff_true : pwaff_false;
3138 * If "cond" involves and NaN, then we conservatively return a NaN
3139 * on its entire domain. In principle, we could consider the pieces
3140 * where it is NaN separately from those where it is not.
3142 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
3143 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
3145 isl_set
*cond_true
, *cond_false
;
3149 if (isl_pw_aff_involves_nan(cond
)) {
3150 isl_space
*space
= isl_pw_aff_get_domain_space(cond
);
3151 isl_local_space
*ls
= isl_local_space_from_space(space
);
3152 isl_pw_aff_free(cond
);
3153 isl_pw_aff_free(pwaff_true
);
3154 isl_pw_aff_free(pwaff_false
);
3155 return isl_pw_aff_nan_on_domain(ls
);
3158 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
3159 cond_false
= isl_pw_aff_zero_set(cond
);
3160 return isl_pw_aff_select(cond_true
, pwaff_true
,
3161 cond_false
, pwaff_false
);
3163 isl_pw_aff_free(cond
);
3164 isl_pw_aff_free(pwaff_true
);
3165 isl_pw_aff_free(pwaff_false
);
3169 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
3174 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
3177 /* Check whether pwaff is a piecewise constant.
3179 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
3186 for (i
= 0; i
< pwaff
->n
; ++i
) {
3187 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
3188 if (is_cst
< 0 || !is_cst
)
3195 /* Return the product of "aff1" and "aff2".
3197 * If either of the two is NaN, then the result is NaN.
3199 * Otherwise, at least one of "aff1" or "aff2" needs to be a constant.
3201 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
3202 __isl_take isl_aff
*aff2
)
3207 if (isl_aff_is_nan(aff1
)) {
3211 if (isl_aff_is_nan(aff2
)) {
3216 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
3217 return isl_aff_mul(aff2
, aff1
);
3219 if (!isl_aff_is_cst(aff2
))
3220 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
3221 "at least one affine expression should be constant",
3224 aff1
= isl_aff_cow(aff1
);
3228 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
3229 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
3239 /* Divide "aff1" by "aff2", assuming "aff2" is a constant.
3241 * If either of the two is NaN, then the result is NaN.
3243 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
3244 __isl_take isl_aff
*aff2
)
3252 if (isl_aff_is_nan(aff1
)) {
3256 if (isl_aff_is_nan(aff2
)) {
3261 is_cst
= isl_aff_is_cst(aff2
);
3265 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
3266 "second argument should be a constant", goto error
);
3271 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
3273 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
3274 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
3277 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
3278 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
3281 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
3282 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
3293 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
3294 __isl_take isl_pw_aff
*pwaff2
)
3296 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
3299 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
3300 __isl_take isl_pw_aff
*pwaff2
)
3302 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
3305 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
3306 __isl_take isl_pw_aff
*pwaff2
)
3308 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
3311 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
3312 __isl_take isl_pw_aff
*pwaff2
)
3314 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
3317 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
3318 __isl_take isl_pw_aff
*pwaff2
)
3320 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
3323 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
3324 __isl_take isl_pw_aff
*pa2
)
3326 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
3329 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
3331 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
3332 __isl_take isl_pw_aff
*pa2
)
3336 is_cst
= isl_pw_aff_is_cst(pa2
);
3340 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3341 "second argument should be a piecewise constant",
3343 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
3345 isl_pw_aff_free(pa1
);
3346 isl_pw_aff_free(pa2
);
3350 /* Compute the quotient of the integer division of "pa1" by "pa2"
3351 * with rounding towards zero.
3352 * "pa2" is assumed to be a piecewise constant.
3354 * In particular, return
3356 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
3359 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
3360 __isl_take isl_pw_aff
*pa2
)
3366 is_cst
= isl_pw_aff_is_cst(pa2
);
3370 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3371 "second argument should be a piecewise constant",
3374 pa1
= isl_pw_aff_div(pa1
, pa2
);
3376 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
3377 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
3378 c
= isl_pw_aff_ceil(pa1
);
3379 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
3381 isl_pw_aff_free(pa1
);
3382 isl_pw_aff_free(pa2
);
3386 /* Compute the remainder of the integer division of "pa1" by "pa2"
3387 * with rounding towards zero.
3388 * "pa2" is assumed to be a piecewise constant.
3390 * In particular, return
3392 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
3395 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
3396 __isl_take isl_pw_aff
*pa2
)
3401 is_cst
= isl_pw_aff_is_cst(pa2
);
3405 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3406 "second argument should be a piecewise constant",
3408 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
3409 res
= isl_pw_aff_mul(pa2
, res
);
3410 res
= isl_pw_aff_sub(pa1
, res
);
3413 isl_pw_aff_free(pa1
);
3414 isl_pw_aff_free(pa2
);
3418 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
3419 __isl_take isl_pw_aff
*pwaff2
)
3424 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
3425 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
3426 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
3427 isl_pw_aff_copy(pwaff2
));
3428 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
3429 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
3432 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
3433 __isl_take isl_pw_aff
*pwaff2
)
3435 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
3438 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3439 __isl_take isl_pw_aff
*pwaff2
)
3444 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
3445 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
3446 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
3447 isl_pw_aff_copy(pwaff2
));
3448 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
3449 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
3452 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3453 __isl_take isl_pw_aff
*pwaff2
)
3455 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
3458 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
3459 __isl_take isl_pw_aff_list
*list
,
3460 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
3461 __isl_take isl_pw_aff
*pwaff2
))
3470 ctx
= isl_pw_aff_list_get_ctx(list
);
3472 isl_die(ctx
, isl_error_invalid
,
3473 "list should contain at least one element", goto error
);
3475 res
= isl_pw_aff_copy(list
->p
[0]);
3476 for (i
= 1; i
< list
->n
; ++i
)
3477 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
3479 isl_pw_aff_list_free(list
);
3482 isl_pw_aff_list_free(list
);
3486 /* Return an isl_pw_aff that maps each element in the intersection of the
3487 * domains of the elements of list to the minimal corresponding affine
3490 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
3492 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
3495 /* Return an isl_pw_aff that maps each element in the intersection of the
3496 * domains of the elements of list to the maximal corresponding affine
3499 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
3501 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
3504 /* Mark the domains of "pwaff" as rational.
3506 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__isl_take isl_pw_aff
*pwaff
)
3510 pwaff
= isl_pw_aff_cow(pwaff
);
3516 for (i
= 0; i
< pwaff
->n
; ++i
) {
3517 pwaff
->p
[i
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
3518 if (!pwaff
->p
[i
].set
)
3519 return isl_pw_aff_free(pwaff
);
3525 /* Mark the domains of the elements of "list" as rational.
3527 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
3528 __isl_take isl_pw_aff_list
*list
)
3538 for (i
= 0; i
< n
; ++i
) {
3541 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
3542 pa
= isl_pw_aff_set_rational(pa
);
3543 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
3549 /* Do the parameters of "aff" match those of "space"?
3551 int isl_aff_matching_params(__isl_keep isl_aff
*aff
,
3552 __isl_keep isl_space
*space
)
3554 isl_space
*aff_space
;
3560 aff_space
= isl_aff_get_domain_space(aff
);
3562 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3564 isl_space_free(aff_space
);
3568 /* Check that the domain space of "aff" matches "space".
3570 * Return 0 on success and -1 on error.
3572 int isl_aff_check_match_domain_space(__isl_keep isl_aff
*aff
,
3573 __isl_keep isl_space
*space
)
3575 isl_space
*aff_space
;
3581 aff_space
= isl_aff_get_domain_space(aff
);
3583 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3587 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3588 "parameters don't match", goto error
);
3589 match
= isl_space_tuple_is_equal(space
, isl_dim_in
,
3590 aff_space
, isl_dim_set
);
3594 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3595 "domains don't match", goto error
);
3596 isl_space_free(aff_space
);
3599 isl_space_free(aff_space
);
3605 #define NO_INTERSECT_DOMAIN
3608 #include <isl_multi_templ.c>
3611 #undef NO_INTERSECT_DOMAIN
3613 /* Remove any internal structure of the domain of "ma".
3614 * If there is any such internal structure in the input,
3615 * then the name of the corresponding space is also removed.
3617 __isl_give isl_multi_aff
*isl_multi_aff_flatten_domain(
3618 __isl_take isl_multi_aff
*ma
)
3625 if (!ma
->space
->nested
[0])
3628 space
= isl_multi_aff_get_space(ma
);
3629 space
= isl_space_flatten_domain(space
);
3630 ma
= isl_multi_aff_reset_space(ma
, space
);
3635 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3636 * of the space to its domain.
3638 __isl_give isl_multi_aff
*isl_multi_aff_domain_map(__isl_take isl_space
*space
)
3641 isl_local_space
*ls
;
3646 if (!isl_space_is_map(space
))
3647 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3648 "not a map space", goto error
);
3650 n_in
= isl_space_dim(space
, isl_dim_in
);
3651 space
= isl_space_domain_map(space
);
3653 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3655 isl_space_free(space
);
3659 space
= isl_space_domain(space
);
3660 ls
= isl_local_space_from_space(space
);
3661 for (i
= 0; i
< n_in
; ++i
) {
3664 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3666 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3668 isl_local_space_free(ls
);
3671 isl_space_free(space
);
3675 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3676 * of the space to its range.
3678 __isl_give isl_multi_aff
*isl_multi_aff_range_map(__isl_take isl_space
*space
)
3681 isl_local_space
*ls
;
3686 if (!isl_space_is_map(space
))
3687 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3688 "not a map space", goto error
);
3690 n_in
= isl_space_dim(space
, isl_dim_in
);
3691 n_out
= isl_space_dim(space
, isl_dim_out
);
3692 space
= isl_space_range_map(space
);
3694 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3696 isl_space_free(space
);
3700 space
= isl_space_domain(space
);
3701 ls
= isl_local_space_from_space(space
);
3702 for (i
= 0; i
< n_out
; ++i
) {
3705 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3706 isl_dim_set
, n_in
+ i
);
3707 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3709 isl_local_space_free(ls
);
3712 isl_space_free(space
);
3716 /* Given a map space, return an isl_pw_multi_aff that maps a wrapped copy
3717 * of the space to its range.
3719 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_map(
3720 __isl_take isl_space
*space
)
3722 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_range_map(space
));
3725 /* Given the space of a set and a range of set dimensions,
3726 * construct an isl_multi_aff that projects out those dimensions.
3728 __isl_give isl_multi_aff
*isl_multi_aff_project_out_map(
3729 __isl_take isl_space
*space
, enum isl_dim_type type
,
3730 unsigned first
, unsigned n
)
3733 isl_local_space
*ls
;
3738 if (!isl_space_is_set(space
))
3739 isl_die(isl_space_get_ctx(space
), isl_error_unsupported
,
3740 "expecting set space", goto error
);
3741 if (type
!= isl_dim_set
)
3742 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3743 "only set dimensions can be projected out", goto error
);
3745 dim
= isl_space_dim(space
, isl_dim_set
);
3746 if (first
+ n
> dim
)
3747 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3748 "range out of bounds", goto error
);
3750 space
= isl_space_from_domain(space
);
3751 space
= isl_space_add_dims(space
, isl_dim_out
, dim
- n
);
3754 return isl_multi_aff_alloc(space
);
3756 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3757 space
= isl_space_domain(space
);
3758 ls
= isl_local_space_from_space(space
);
3760 for (i
= 0; i
< first
; ++i
) {
3763 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3765 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3768 for (i
= 0; i
< dim
- (first
+ n
); ++i
) {
3771 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3772 isl_dim_set
, first
+ n
+ i
);
3773 ma
= isl_multi_aff_set_aff(ma
, first
+ i
, aff
);
3776 isl_local_space_free(ls
);
3779 isl_space_free(space
);
3783 /* Given the space of a set and a range of set dimensions,
3784 * construct an isl_pw_multi_aff that projects out those dimensions.
3786 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_project_out_map(
3787 __isl_take isl_space
*space
, enum isl_dim_type type
,
3788 unsigned first
, unsigned n
)
3792 ma
= isl_multi_aff_project_out_map(space
, type
, first
, n
);
3793 return isl_pw_multi_aff_from_multi_aff(ma
);
3796 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
3799 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
3800 __isl_take isl_multi_aff
*ma
)
3802 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
3803 return isl_pw_multi_aff_alloc(dom
, ma
);
3806 /* Create a piecewise multi-affine expression in the given space that maps each
3807 * input dimension to the corresponding output dimension.
3809 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
3810 __isl_take isl_space
*space
)
3812 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
3815 /* Add "ma2" to "ma1" and return the result.
3817 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
3819 static __isl_give isl_multi_aff
*isl_multi_aff_add_aligned(
3820 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3822 return isl_multi_aff_bin_op(maff1
, maff2
, &isl_aff_add
);
3825 /* Add "ma2" to "ma1" and return the result.
3827 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*ma1
,
3828 __isl_take isl_multi_aff
*ma2
)
3830 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
3831 &isl_multi_aff_add_aligned
);
3834 /* Exploit the equalities in "eq" to simplify the affine expressions.
3836 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
3837 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
3841 maff
= isl_multi_aff_cow(maff
);
3845 for (i
= 0; i
< maff
->n
; ++i
) {
3846 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
3847 isl_basic_set_copy(eq
));
3852 isl_basic_set_free(eq
);
3855 isl_basic_set_free(eq
);
3856 isl_multi_aff_free(maff
);
3860 /* Given f, return floor(f).
3862 __isl_give isl_multi_aff
*isl_multi_aff_floor(__isl_take isl_multi_aff
*ma
)
3866 ma
= isl_multi_aff_cow(ma
);
3870 for (i
= 0; i
< ma
->n
; ++i
) {
3871 ma
->p
[i
] = isl_aff_floor(ma
->p
[i
]);
3873 return isl_multi_aff_free(ma
);
3879 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
3884 maff
= isl_multi_aff_cow(maff
);
3888 for (i
= 0; i
< maff
->n
; ++i
) {
3889 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
3891 return isl_multi_aff_free(maff
);
3897 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
3898 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3900 maff1
= isl_multi_aff_add(maff1
, maff2
);
3901 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
3905 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
3913 /* Return the set of domain elements where "ma1" is lexicographically
3914 * smaller than or equal to "ma2".
3916 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
3917 __isl_take isl_multi_aff
*ma2
)
3919 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
3922 /* Return the set of domain elements where "ma1" is lexicographically
3923 * greater than or equal to "ma2".
3925 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
3926 __isl_take isl_multi_aff
*ma2
)
3929 isl_map
*map1
, *map2
;
3932 map1
= isl_map_from_multi_aff(ma1
);
3933 map2
= isl_map_from_multi_aff(ma2
);
3934 map
= isl_map_range_product(map1
, map2
);
3935 space
= isl_space_range(isl_map_get_space(map
));
3936 space
= isl_space_domain(isl_space_unwrap(space
));
3937 ge
= isl_map_lex_ge(space
);
3938 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
3940 return isl_map_domain(map
);
3944 #define PW isl_pw_multi_aff
3946 #define EL isl_multi_aff
3948 #define EL_IS_ZERO is_empty
3952 #define IS_ZERO is_empty
3955 #undef DEFAULT_IS_ZERO
3956 #define DEFAULT_IS_ZERO 0
3961 #define NO_INVOLVES_DIMS
3962 #define NO_INSERT_DIMS
3966 #include <isl_pw_templ.c>
3971 #define UNION isl_union_pw_multi_aff
3973 #define PART isl_pw_multi_aff
3975 #define PARTS pw_multi_aff
3976 #define ALIGN_DOMAIN
3980 #include <isl_union_templ.c>
3982 /* Given a function "cmp" that returns the set of elements where
3983 * "ma1" is "better" than "ma2", return the intersection of this
3984 * set with "dom1" and "dom2".
3986 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
3987 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
3988 __isl_keep isl_multi_aff
*ma2
,
3989 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3990 __isl_take isl_multi_aff
*ma2
))
3996 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
3997 is_empty
= isl_set_plain_is_empty(common
);
3998 if (is_empty
>= 0 && is_empty
)
4001 return isl_set_free(common
);
4002 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
4003 better
= isl_set_intersect(common
, better
);
4008 /* Given a function "cmp" that returns the set of elements where
4009 * "ma1" is "better" than "ma2", return a piecewise multi affine
4010 * expression defined on the union of the definition domains
4011 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
4012 * "pma2" on each cell. If only one of the two input functions
4013 * is defined on a given cell, then it is considered the best.
4015 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
4016 __isl_take isl_pw_multi_aff
*pma1
,
4017 __isl_take isl_pw_multi_aff
*pma2
,
4018 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
4019 __isl_take isl_multi_aff
*ma2
))
4022 isl_pw_multi_aff
*res
= NULL
;
4024 isl_set
*set
= NULL
;
4029 ctx
= isl_space_get_ctx(pma1
->dim
);
4030 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
4031 isl_die(ctx
, isl_error_invalid
,
4032 "arguments should live in the same space", goto error
);
4034 if (isl_pw_multi_aff_is_empty(pma1
)) {
4035 isl_pw_multi_aff_free(pma1
);
4039 if (isl_pw_multi_aff_is_empty(pma2
)) {
4040 isl_pw_multi_aff_free(pma2
);
4044 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
4045 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
4047 for (i
= 0; i
< pma1
->n
; ++i
) {
4048 set
= isl_set_copy(pma1
->p
[i
].set
);
4049 for (j
= 0; j
< pma2
->n
; ++j
) {
4053 better
= shared_and_better(pma2
->p
[j
].set
,
4054 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
4055 pma1
->p
[i
].maff
, cmp
);
4056 is_empty
= isl_set_plain_is_empty(better
);
4057 if (is_empty
< 0 || is_empty
) {
4058 isl_set_free(better
);
4063 set
= isl_set_subtract(set
, isl_set_copy(better
));
4065 res
= isl_pw_multi_aff_add_piece(res
, better
,
4066 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4068 res
= isl_pw_multi_aff_add_piece(res
, set
,
4069 isl_multi_aff_copy(pma1
->p
[i
].maff
));
4072 for (j
= 0; j
< pma2
->n
; ++j
) {
4073 set
= isl_set_copy(pma2
->p
[j
].set
);
4074 for (i
= 0; i
< pma1
->n
; ++i
)
4075 set
= isl_set_subtract(set
,
4076 isl_set_copy(pma1
->p
[i
].set
));
4077 res
= isl_pw_multi_aff_add_piece(res
, set
,
4078 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4081 isl_pw_multi_aff_free(pma1
);
4082 isl_pw_multi_aff_free(pma2
);
4086 isl_pw_multi_aff_free(pma1
);
4087 isl_pw_multi_aff_free(pma2
);
4089 return isl_pw_multi_aff_free(res
);
4092 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
4093 __isl_take isl_pw_multi_aff
*pma1
,
4094 __isl_take isl_pw_multi_aff
*pma2
)
4096 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
4099 /* Given two piecewise multi affine expressions, return a piecewise
4100 * multi-affine expression defined on the union of the definition domains
4101 * of the inputs that is equal to the lexicographic maximum of the two
4102 * inputs on each cell. If only one of the two inputs is defined on
4103 * a given cell, then it is considered to be the maximum.
4105 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
4106 __isl_take isl_pw_multi_aff
*pma1
,
4107 __isl_take isl_pw_multi_aff
*pma2
)
4109 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4110 &pw_multi_aff_union_lexmax
);
4113 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
4114 __isl_take isl_pw_multi_aff
*pma1
,
4115 __isl_take isl_pw_multi_aff
*pma2
)
4117 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
4120 /* Given two piecewise multi affine expressions, return a piecewise
4121 * multi-affine expression defined on the union of the definition domains
4122 * of the inputs that is equal to the lexicographic minimum of the two
4123 * inputs on each cell. If only one of the two inputs is defined on
4124 * a given cell, then it is considered to be the minimum.
4126 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
4127 __isl_take isl_pw_multi_aff
*pma1
,
4128 __isl_take isl_pw_multi_aff
*pma2
)
4130 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4131 &pw_multi_aff_union_lexmin
);
4134 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
4135 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4137 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
4138 &isl_multi_aff_add
);
4141 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
4142 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4144 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4148 static __isl_give isl_pw_multi_aff
*pw_multi_aff_sub(
4149 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4151 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
4152 &isl_multi_aff_sub
);
4155 /* Subtract "pma2" from "pma1" and return the result.
4157 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_sub(
4158 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4160 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4164 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
4165 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4167 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
4170 /* Compute the sum of "upma1" and "upma2" on the union of their domains,
4171 * with the actual sum on the shared domain and
4172 * the defined expression on the symmetric difference of the domains.
4174 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_union_add(
4175 __isl_take isl_union_pw_multi_aff
*upma1
,
4176 __isl_take isl_union_pw_multi_aff
*upma2
)
4178 return isl_union_pw_multi_aff_union_add_(upma1
, upma2
);
4181 /* Given two piecewise multi-affine expressions A -> B and C -> D,
4182 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
4184 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
4185 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4189 isl_pw_multi_aff
*res
;
4194 n
= pma1
->n
* pma2
->n
;
4195 space
= isl_space_product(isl_space_copy(pma1
->dim
),
4196 isl_space_copy(pma2
->dim
));
4197 res
= isl_pw_multi_aff_alloc_size(space
, n
);
4199 for (i
= 0; i
< pma1
->n
; ++i
) {
4200 for (j
= 0; j
< pma2
->n
; ++j
) {
4204 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
4205 isl_set_copy(pma2
->p
[j
].set
));
4206 ma
= isl_multi_aff_product(
4207 isl_multi_aff_copy(pma1
->p
[i
].maff
),
4208 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4209 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
4213 isl_pw_multi_aff_free(pma1
);
4214 isl_pw_multi_aff_free(pma2
);
4217 isl_pw_multi_aff_free(pma1
);
4218 isl_pw_multi_aff_free(pma2
);
4222 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
4223 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4225 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4226 &pw_multi_aff_product
);
4229 /* Construct a map mapping the domain of the piecewise multi-affine expression
4230 * to its range, with each dimension in the range equated to the
4231 * corresponding affine expression on its cell.
4233 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
4241 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
4243 for (i
= 0; i
< pma
->n
; ++i
) {
4244 isl_multi_aff
*maff
;
4245 isl_basic_map
*bmap
;
4248 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
4249 bmap
= isl_basic_map_from_multi_aff(maff
);
4250 map_i
= isl_map_from_basic_map(bmap
);
4251 map_i
= isl_map_intersect_domain(map_i
,
4252 isl_set_copy(pma
->p
[i
].set
));
4253 map
= isl_map_union_disjoint(map
, map_i
);
4256 isl_pw_multi_aff_free(pma
);
4260 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
4265 if (!isl_space_is_set(pma
->dim
))
4266 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4267 "isl_pw_multi_aff cannot be converted into an isl_set",
4270 return isl_map_from_pw_multi_aff(pma
);
4272 isl_pw_multi_aff_free(pma
);
4276 /* Given a basic map with a single output dimension that is defined
4277 * in terms of the parameters and input dimensions using an equality,
4278 * extract an isl_aff that expresses the output dimension in terms
4279 * of the parameters and input dimensions.
4280 * Note that this expression may involve integer divisions defined
4281 * in terms of parameters and input dimensions.
4283 * This function shares some similarities with
4284 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
4286 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
4287 __isl_take isl_basic_map
*bmap
)
4292 isl_local_space
*ls
;
4297 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
4298 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
4299 "basic map should have a single output dimension",
4301 eq
= isl_basic_map_output_defining_equality(bmap
, 0);
4302 if (eq
>= bmap
->n_eq
)
4303 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
4304 "unable to find suitable equality", goto error
);
4305 ls
= isl_basic_map_get_local_space(bmap
);
4306 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
4309 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
4310 n_div
= isl_basic_map_dim(bmap
, isl_dim_div
);
4311 if (isl_int_is_neg(bmap
->eq
[eq
][offset
])) {
4312 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[eq
], offset
);
4313 isl_seq_cpy(aff
->v
->el
+ 1 + offset
, bmap
->eq
[eq
] + offset
+ 1,
4316 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[eq
], offset
);
4317 isl_seq_neg(aff
->v
->el
+ 1 + offset
, bmap
->eq
[eq
] + offset
+ 1,
4320 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[eq
][offset
]);
4321 isl_basic_map_free(bmap
);
4323 aff
= isl_aff_remove_unused_divs(aff
);
4326 isl_basic_map_free(bmap
);
4330 /* Given a basic map where each output dimension is defined
4331 * in terms of the parameters and input dimensions using an equality,
4332 * extract an isl_multi_aff that expresses the output dimensions in terms
4333 * of the parameters and input dimensions.
4335 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
4336 __isl_take isl_basic_map
*bmap
)
4345 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
4346 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
4348 for (i
= 0; i
< n_out
; ++i
) {
4349 isl_basic_map
*bmap_i
;
4352 bmap_i
= isl_basic_map_copy(bmap
);
4353 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
4354 i
+ 1, n_out
- (1 + i
));
4355 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
4356 aff
= extract_isl_aff_from_basic_map(bmap_i
);
4357 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4360 isl_basic_map_free(bmap
);
4365 /* Given a basic set where each set dimension is defined
4366 * in terms of the parameters using an equality,
4367 * extract an isl_multi_aff that expresses the set dimensions in terms
4368 * of the parameters.
4370 __isl_give isl_multi_aff
*isl_multi_aff_from_basic_set_equalities(
4371 __isl_take isl_basic_set
*bset
)
4373 return extract_isl_multi_aff_from_basic_map(bset
);
4376 /* Create an isl_pw_multi_aff that is equivalent to
4377 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
4378 * The given basic map is such that each output dimension is defined
4379 * in terms of the parameters and input dimensions using an equality.
4381 * Since some applications expect the result of isl_pw_multi_aff_from_map
4382 * to only contain integer affine expressions, we compute the floor
4383 * of the expression before returning.
4385 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
4386 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
4390 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
4391 ma
= isl_multi_aff_floor(ma
);
4392 return isl_pw_multi_aff_alloc(domain
, ma
);
4395 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4396 * This obviously only works if the input "map" is single-valued.
4397 * If so, we compute the lexicographic minimum of the image in the form
4398 * of an isl_pw_multi_aff. Since the image is unique, it is equal
4399 * to its lexicographic minimum.
4400 * If the input is not single-valued, we produce an error.
4402 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
4403 __isl_take isl_map
*map
)
4407 isl_pw_multi_aff
*pma
;
4409 sv
= isl_map_is_single_valued(map
);
4413 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
4414 "map is not single-valued", goto error
);
4415 map
= isl_map_make_disjoint(map
);
4419 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
4421 for (i
= 0; i
< map
->n
; ++i
) {
4422 isl_pw_multi_aff
*pma_i
;
4423 isl_basic_map
*bmap
;
4424 bmap
= isl_basic_map_copy(map
->p
[i
]);
4425 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
4426 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
4436 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4437 * taking into account that the output dimension at position "d"
4438 * can be represented as
4440 * x = floor((e(...) + c1) / m)
4442 * given that constraint "i" is of the form
4444 * e(...) + c1 - m x >= 0
4447 * Let "map" be of the form
4451 * We construct a mapping
4453 * A -> [A -> x = floor(...)]
4455 * apply that to the map, obtaining
4457 * [A -> x = floor(...)] -> B
4459 * and equate dimension "d" to x.
4460 * We then compute a isl_pw_multi_aff representation of the resulting map
4461 * and plug in the mapping above.
4463 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
4464 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
4468 isl_local_space
*ls
;
4476 isl_pw_multi_aff
*pma
;
4479 is_set
= isl_map_is_set(map
);
4481 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
4482 ctx
= isl_map_get_ctx(map
);
4483 space
= isl_space_domain(isl_map_get_space(map
));
4484 n_in
= isl_space_dim(space
, isl_dim_set
);
4485 n
= isl_space_dim(space
, isl_dim_all
);
4487 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
4489 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
4490 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
4492 isl_basic_map_free(hull
);
4494 ls
= isl_local_space_from_space(isl_space_copy(space
));
4495 aff
= isl_aff_alloc_vec(ls
, v
);
4496 aff
= isl_aff_floor(aff
);
4498 isl_space_free(space
);
4499 ma
= isl_multi_aff_from_aff(aff
);
4501 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
4502 ma
= isl_multi_aff_range_product(ma
,
4503 isl_multi_aff_from_aff(aff
));
4506 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
4507 map
= isl_map_apply_domain(map
, insert
);
4508 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
4509 pma
= isl_pw_multi_aff_from_map(map
);
4510 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
4515 /* Is constraint "c" of the form
4517 * e(...) + c1 - m x >= 0
4521 * -e(...) + c2 + m x >= 0
4523 * where m > 1 and e only depends on parameters and input dimemnsions?
4525 * "offset" is the offset of the output dimensions
4526 * "pos" is the position of output dimension x.
4528 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
4530 if (isl_int_is_zero(c
[offset
+ d
]))
4532 if (isl_int_is_one(c
[offset
+ d
]))
4534 if (isl_int_is_negone(c
[offset
+ d
]))
4536 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
4538 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
4539 total
- (offset
+ d
+ 1)) != -1)
4544 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4546 * As a special case, we first check if there is any pair of constraints,
4547 * shared by all the basic maps in "map" that force a given dimension
4548 * to be equal to the floor of some affine combination of the input dimensions.
4550 * In particular, if we can find two constraints
4552 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
4556 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
4558 * where m > 1 and e only depends on parameters and input dimemnsions,
4561 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
4563 * then we know that we can take
4565 * x = floor((e(...) + c1) / m)
4567 * without having to perform any computation.
4569 * Note that we know that
4573 * If c1 + c2 were 0, then we would have detected an equality during
4574 * simplification. If c1 + c2 were negative, then we would have detected
4577 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
4578 __isl_take isl_map
*map
)
4584 isl_basic_map
*hull
;
4586 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
4591 dim
= isl_map_dim(map
, isl_dim_out
);
4592 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
4593 total
= 1 + isl_basic_map_total_dim(hull
);
4595 for (d
= 0; d
< dim
; ++d
) {
4596 for (i
= 0; i
< n
; ++i
) {
4597 if (!is_potential_div_constraint(hull
->ineq
[i
],
4600 for (j
= i
+ 1; j
< n
; ++j
) {
4601 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
4602 hull
->ineq
[j
] + 1, total
- 1))
4604 isl_int_add(sum
, hull
->ineq
[i
][0],
4606 if (isl_int_abs_lt(sum
,
4607 hull
->ineq
[i
][offset
+ d
]))
4614 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
4616 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
4620 isl_basic_map_free(hull
);
4621 return pw_multi_aff_from_map_base(map
);
4624 isl_basic_map_free(hull
);
4628 /* Given an affine expression
4630 * [A -> B] -> f(A,B)
4632 * construct an isl_multi_aff
4636 * such that dimension "d" in B' is set to "aff" and the remaining
4637 * dimensions are set equal to the corresponding dimensions in B.
4638 * "n_in" is the dimension of the space A.
4639 * "n_out" is the dimension of the space B.
4641 * If "is_set" is set, then the affine expression is of the form
4645 * and we construct an isl_multi_aff
4649 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
4650 unsigned n_in
, unsigned n_out
, int is_set
)
4654 isl_space
*space
, *space2
;
4655 isl_local_space
*ls
;
4657 space
= isl_aff_get_domain_space(aff
);
4658 ls
= isl_local_space_from_space(isl_space_copy(space
));
4659 space2
= isl_space_copy(space
);
4661 space2
= isl_space_range(isl_space_unwrap(space2
));
4662 space
= isl_space_map_from_domain_and_range(space
, space2
);
4663 ma
= isl_multi_aff_alloc(space
);
4664 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
4666 for (i
= 0; i
< n_out
; ++i
) {
4669 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
4670 isl_dim_set
, n_in
+ i
);
4671 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4674 isl_local_space_free(ls
);
4679 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4680 * taking into account that the dimension at position "d" can be written as
4682 * x = m a + f(..) (1)
4684 * where m is equal to "gcd".
4685 * "i" is the index of the equality in "hull" that defines f(..).
4686 * In particular, the equality is of the form
4688 * f(..) - x + m g(existentials) = 0
4692 * -f(..) + x + m g(existentials) = 0
4694 * We basically plug (1) into "map", resulting in a map with "a"
4695 * in the range instead of "x". The corresponding isl_pw_multi_aff
4696 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
4698 * Specifically, given the input map
4702 * We first wrap it into a set
4706 * and define (1) on top of the corresponding space, resulting in "aff".
4707 * We use this to create an isl_multi_aff that maps the output position "d"
4708 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
4709 * We plug this into the wrapped map, unwrap the result and compute the
4710 * corresponding isl_pw_multi_aff.
4711 * The result is an expression
4719 * so that we can plug that into "aff", after extending the latter to
4725 * If "map" is actually a set, then there is no "A" space, meaning
4726 * that we do not need to perform any wrapping, and that the result
4727 * of the recursive call is of the form
4731 * which is plugged into a mapping of the form
4735 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
4736 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
4741 isl_local_space
*ls
;
4744 isl_pw_multi_aff
*pma
, *id
;
4750 is_set
= isl_map_is_set(map
);
4752 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
4753 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4754 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4759 set
= isl_map_wrap(map
);
4760 space
= isl_space_map_from_set(isl_set_get_space(set
));
4761 ma
= isl_multi_aff_identity(space
);
4762 ls
= isl_local_space_from_space(isl_set_get_space(set
));
4763 aff
= isl_aff_alloc(ls
);
4765 isl_int_set_si(aff
->v
->el
[0], 1);
4766 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
4767 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
4770 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
4772 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
4774 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
4775 set
= isl_set_preimage_multi_aff(set
, ma
);
4777 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
4782 map
= isl_set_unwrap(set
);
4783 pma
= isl_pw_multi_aff_from_map(set
);
4786 space
= isl_pw_multi_aff_get_domain_space(pma
);
4787 space
= isl_space_map_from_set(space
);
4788 id
= isl_pw_multi_aff_identity(space
);
4789 pma
= isl_pw_multi_aff_range_product(id
, pma
);
4791 id
= isl_pw_multi_aff_from_multi_aff(ma
);
4792 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
4794 isl_basic_map_free(hull
);
4798 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4800 * As a special case, we first check if all output dimensions are uniquely
4801 * defined in terms of the parameters and input dimensions over the entire
4802 * domain. If so, we extract the desired isl_pw_multi_aff directly
4803 * from the affine hull of "map" and its domain.
4805 * Otherwise, we check if any of the output dimensions is "strided".
4806 * That is, we check if can be written as
4810 * with m greater than 1, a some combination of existentiall quantified
4811 * variables and f and expression in the parameters and input dimensions.
4812 * If so, we remove the stride in pw_multi_aff_from_map_stride.
4814 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
4817 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
4821 isl_basic_map
*hull
;
4831 hull
= isl_map_affine_hull(isl_map_copy(map
));
4832 sv
= isl_basic_map_plain_is_single_valued(hull
);
4834 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
4836 hull
= isl_basic_map_free(hull
);
4840 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
4841 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
4844 isl_basic_map_free(hull
);
4845 return pw_multi_aff_from_map_check_div(map
);
4850 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4851 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4853 for (i
= 0; i
< n_out
; ++i
) {
4854 for (j
= 0; j
< hull
->n_eq
; ++j
) {
4855 isl_int
*eq
= hull
->eq
[j
];
4856 isl_pw_multi_aff
*res
;
4858 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
4859 !isl_int_is_negone(eq
[o_out
+ i
]))
4861 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
4863 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
4864 n_out
- (i
+ 1)) != -1)
4866 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
4867 if (isl_int_is_zero(gcd
))
4869 if (isl_int_is_one(gcd
))
4872 res
= pw_multi_aff_from_map_stride(map
, hull
,
4880 isl_basic_map_free(hull
);
4881 return pw_multi_aff_from_map_check_div(map
);
4887 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
4889 return isl_pw_multi_aff_from_map(set
);
4892 /* Convert "map" into an isl_pw_multi_aff (if possible) and
4895 static int pw_multi_aff_from_map(__isl_take isl_map
*map
, void *user
)
4897 isl_union_pw_multi_aff
**upma
= user
;
4898 isl_pw_multi_aff
*pma
;
4900 pma
= isl_pw_multi_aff_from_map(map
);
4901 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4903 return *upma
? 0 : -1;
4906 /* Create an isl_union_pw_multi_aff with the given isl_aff on a universe
4909 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_aff(
4910 __isl_take isl_aff
*aff
)
4913 isl_pw_multi_aff
*pma
;
4915 ma
= isl_multi_aff_from_aff(aff
);
4916 pma
= isl_pw_multi_aff_from_multi_aff(ma
);
4917 return isl_union_pw_multi_aff_from_pw_multi_aff(pma
);
4920 /* Try and create an isl_union_pw_multi_aff that is equivalent
4921 * to the given isl_union_map.
4922 * The isl_union_map is required to be single-valued in each space.
4923 * Otherwise, an error is produced.
4925 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_map(
4926 __isl_take isl_union_map
*umap
)
4929 isl_union_pw_multi_aff
*upma
;
4931 space
= isl_union_map_get_space(umap
);
4932 upma
= isl_union_pw_multi_aff_empty(space
);
4933 if (isl_union_map_foreach_map(umap
, &pw_multi_aff_from_map
, &upma
) < 0)
4934 upma
= isl_union_pw_multi_aff_free(upma
);
4935 isl_union_map_free(umap
);
4940 /* Try and create an isl_union_pw_multi_aff that is equivalent
4941 * to the given isl_union_set.
4942 * The isl_union_set is required to be a singleton in each space.
4943 * Otherwise, an error is produced.
4945 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_set(
4946 __isl_take isl_union_set
*uset
)
4948 return isl_union_pw_multi_aff_from_union_map(uset
);
4951 /* Return the piecewise affine expression "set ? 1 : 0".
4953 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
4956 isl_space
*space
= isl_set_get_space(set
);
4957 isl_local_space
*ls
= isl_local_space_from_space(space
);
4958 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
4959 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
4961 one
= isl_aff_add_constant_si(one
, 1);
4962 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
4963 set
= isl_set_complement(set
);
4964 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
4969 /* Plug in "subs" for dimension "type", "pos" of "aff".
4971 * Let i be the dimension to replace and let "subs" be of the form
4975 * and "aff" of the form
4981 * (a f + d g')/(m d)
4983 * where g' is the result of plugging in "subs" in each of the integer
4986 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
4987 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
4992 aff
= isl_aff_cow(aff
);
4994 return isl_aff_free(aff
);
4996 ctx
= isl_aff_get_ctx(aff
);
4997 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
4998 isl_die(ctx
, isl_error_invalid
,
4999 "spaces don't match", return isl_aff_free(aff
));
5000 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
5001 isl_die(ctx
, isl_error_unsupported
,
5002 "cannot handle divs yet", return isl_aff_free(aff
));
5004 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
5006 return isl_aff_free(aff
);
5008 aff
->v
= isl_vec_cow(aff
->v
);
5010 return isl_aff_free(aff
);
5012 pos
+= isl_local_space_offset(aff
->ls
, type
);
5015 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
5016 aff
->v
->size
, subs
->v
->size
, v
);
5022 /* Plug in "subs" for dimension "type", "pos" in each of the affine
5023 * expressions in "maff".
5025 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
5026 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
5027 __isl_keep isl_aff
*subs
)
5031 maff
= isl_multi_aff_cow(maff
);
5033 return isl_multi_aff_free(maff
);
5035 if (type
== isl_dim_in
)
5038 for (i
= 0; i
< maff
->n
; ++i
) {
5039 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
5041 return isl_multi_aff_free(maff
);
5047 /* Plug in "subs" for dimension "type", "pos" of "pma".
5049 * pma is of the form
5053 * while subs is of the form
5055 * v' = B_j(v) -> S_j
5057 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
5058 * has a contribution in the result, in particular
5060 * C_ij(S_j) -> M_i(S_j)
5062 * Note that plugging in S_j in C_ij may also result in an empty set
5063 * and this contribution should simply be discarded.
5065 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
5066 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
5067 __isl_keep isl_pw_aff
*subs
)
5070 isl_pw_multi_aff
*res
;
5073 return isl_pw_multi_aff_free(pma
);
5075 n
= pma
->n
* subs
->n
;
5076 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
5078 for (i
= 0; i
< pma
->n
; ++i
) {
5079 for (j
= 0; j
< subs
->n
; ++j
) {
5081 isl_multi_aff
*res_ij
;
5084 common
= isl_set_intersect(
5085 isl_set_copy(pma
->p
[i
].set
),
5086 isl_set_copy(subs
->p
[j
].set
));
5087 common
= isl_set_substitute(common
,
5088 type
, pos
, subs
->p
[j
].aff
);
5089 empty
= isl_set_plain_is_empty(common
);
5090 if (empty
< 0 || empty
) {
5091 isl_set_free(common
);
5097 res_ij
= isl_multi_aff_substitute(
5098 isl_multi_aff_copy(pma
->p
[i
].maff
),
5099 type
, pos
, subs
->p
[j
].aff
);
5101 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5105 isl_pw_multi_aff_free(pma
);
5108 isl_pw_multi_aff_free(pma
);
5109 isl_pw_multi_aff_free(res
);
5113 /* Compute the preimage of a range of dimensions in the affine expression "src"
5114 * under "ma" and put the result in "dst". The number of dimensions in "src"
5115 * that precede the range is given by "n_before". The number of dimensions
5116 * in the range is given by the number of output dimensions of "ma".
5117 * The number of dimensions that follow the range is given by "n_after".
5118 * If "has_denom" is set (to one),
5119 * then "src" and "dst" have an extra initial denominator.
5120 * "n_div_ma" is the number of existentials in "ma"
5121 * "n_div_bset" is the number of existentials in "src"
5122 * The resulting "dst" (which is assumed to have been allocated by
5123 * the caller) contains coefficients for both sets of existentials,
5124 * first those in "ma" and then those in "src".
5125 * f, c1, c2 and g are temporary objects that have been initialized
5128 * Let src represent the expression
5130 * (a(p) + f_u u + b v + f_w w + c(divs))/d
5132 * and let ma represent the expressions
5134 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
5136 * We start out with the following expression for dst:
5138 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d
5140 * with the multiplication factor f initially equal to 1
5141 * and f \sum_i b_i v_i kept separately.
5142 * For each x_i that we substitute, we multiply the numerator
5143 * (and denominator) of dst by c_1 = m_i and add the numerator
5144 * of the x_i expression multiplied by c_2 = f b_i,
5145 * after removing the common factors of c_1 and c_2.
5146 * The multiplication factor f also needs to be multiplied by c_1
5147 * for the next x_j, j > i.
5149 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
5150 __isl_keep isl_multi_aff
*ma
, int n_before
, int n_after
,
5151 int n_div_ma
, int n_div_bmap
,
5152 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
5155 int n_param
, n_in
, n_out
;
5158 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
5159 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
5160 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
5162 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
+ n_before
);
5163 o_dst
= o_src
= has_denom
+ 1 + n_param
+ n_before
;
5164 isl_seq_clr(dst
+ o_dst
, n_in
);
5167 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_after
);
5170 isl_seq_clr(dst
+ o_dst
, n_div_ma
);
5172 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_div_bmap
);
5174 isl_int_set_si(f
, 1);
5176 for (i
= 0; i
< n_out
; ++i
) {
5177 int offset
= has_denom
+ 1 + n_param
+ n_before
+ i
;
5179 if (isl_int_is_zero(src
[offset
]))
5181 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
5182 isl_int_mul(c2
, f
, src
[offset
]);
5183 isl_int_gcd(g
, c1
, c2
);
5184 isl_int_divexact(c1
, c1
, g
);
5185 isl_int_divexact(c2
, c2
, g
);
5187 isl_int_mul(f
, f
, c1
);
5190 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5191 c2
, ma
->p
[i
]->v
->el
+ o_src
, 1 + n_param
);
5192 o_dst
+= 1 + n_param
;
5193 o_src
+= 1 + n_param
;
5194 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_before
);
5196 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5197 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_in
);
5200 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_after
);
5202 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5203 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_div_ma
);
5206 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_div_bmap
);
5208 isl_int_mul(dst
[0], dst
[0], c1
);
5212 /* Compute the pullback of "aff" by the function represented by "ma".
5213 * In other words, plug in "ma" in "aff". The result is an affine expression
5214 * defined over the domain space of "ma".
5216 * If "aff" is represented by
5218 * (a(p) + b x + c(divs))/d
5220 * and ma is represented by
5222 * x = D(p) + F(y) + G(divs')
5224 * then the result is
5226 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
5228 * The divs in the local space of the input are similarly adjusted
5229 * through a call to isl_local_space_preimage_multi_aff.
5231 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
5232 __isl_take isl_multi_aff
*ma
)
5234 isl_aff
*res
= NULL
;
5235 isl_local_space
*ls
;
5236 int n_div_aff
, n_div_ma
;
5237 isl_int f
, c1
, c2
, g
;
5239 ma
= isl_multi_aff_align_divs(ma
);
5243 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
5244 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
5246 ls
= isl_aff_get_domain_local_space(aff
);
5247 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
5248 res
= isl_aff_alloc(ls
);
5257 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, 0, 0, n_div_ma
, n_div_aff
,
5266 isl_multi_aff_free(ma
);
5267 res
= isl_aff_normalize(res
);
5271 isl_multi_aff_free(ma
);
5276 /* Compute the pullback of "aff1" by the function represented by "aff2".
5277 * In other words, plug in "aff2" in "aff1". The result is an affine expression
5278 * defined over the domain space of "aff1".
5280 * The domain of "aff1" should match the range of "aff2", which means
5281 * that it should be single-dimensional.
5283 __isl_give isl_aff
*isl_aff_pullback_aff(__isl_take isl_aff
*aff1
,
5284 __isl_take isl_aff
*aff2
)
5288 ma
= isl_multi_aff_from_aff(aff2
);
5289 return isl_aff_pullback_multi_aff(aff1
, ma
);
5292 /* Compute the pullback of "ma1" by the function represented by "ma2".
5293 * In other words, plug in "ma2" in "ma1".
5295 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
5297 static __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff_aligned(
5298 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5301 isl_space
*space
= NULL
;
5303 ma2
= isl_multi_aff_align_divs(ma2
);
5304 ma1
= isl_multi_aff_cow(ma1
);
5308 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
5309 isl_multi_aff_get_space(ma1
));
5311 for (i
= 0; i
< ma1
->n
; ++i
) {
5312 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
5313 isl_multi_aff_copy(ma2
));
5318 ma1
= isl_multi_aff_reset_space(ma1
, space
);
5319 isl_multi_aff_free(ma2
);
5322 isl_space_free(space
);
5323 isl_multi_aff_free(ma2
);
5324 isl_multi_aff_free(ma1
);
5328 /* Compute the pullback of "ma1" by the function represented by "ma2".
5329 * In other words, plug in "ma2" in "ma1".
5331 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
5332 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5334 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
5335 &isl_multi_aff_pullback_multi_aff_aligned
);
5338 /* Extend the local space of "dst" to include the divs
5339 * in the local space of "src".
5341 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
5342 __isl_keep isl_aff
*src
)
5350 return isl_aff_free(dst
);
5352 ctx
= isl_aff_get_ctx(src
);
5353 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
5354 isl_die(ctx
, isl_error_invalid
,
5355 "spaces don't match", goto error
);
5357 if (src
->ls
->div
->n_row
== 0)
5360 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
5361 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
5362 if (!exp1
|| (dst
->ls
->div
->n_row
&& !exp2
))
5365 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
5366 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
5374 return isl_aff_free(dst
);
5377 /* Adjust the local spaces of the affine expressions in "maff"
5378 * such that they all have the save divs.
5380 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
5381 __isl_take isl_multi_aff
*maff
)
5389 maff
= isl_multi_aff_cow(maff
);
5393 for (i
= 1; i
< maff
->n
; ++i
)
5394 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
5395 for (i
= 1; i
< maff
->n
; ++i
) {
5396 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
5398 return isl_multi_aff_free(maff
);
5404 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
5406 aff
= isl_aff_cow(aff
);
5410 aff
->ls
= isl_local_space_lift(aff
->ls
);
5412 return isl_aff_free(aff
);
5417 /* Lift "maff" to a space with extra dimensions such that the result
5418 * has no more existentially quantified variables.
5419 * If "ls" is not NULL, then *ls is assigned the local space that lies
5420 * at the basis of the lifting applied to "maff".
5422 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
5423 __isl_give isl_local_space
**ls
)
5437 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
5438 *ls
= isl_local_space_from_space(space
);
5440 return isl_multi_aff_free(maff
);
5445 maff
= isl_multi_aff_cow(maff
);
5446 maff
= isl_multi_aff_align_divs(maff
);
5450 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
5451 space
= isl_multi_aff_get_space(maff
);
5452 space
= isl_space_lift(isl_space_domain(space
), n_div
);
5453 space
= isl_space_extend_domain_with_range(space
,
5454 isl_multi_aff_get_space(maff
));
5456 return isl_multi_aff_free(maff
);
5457 isl_space_free(maff
->space
);
5458 maff
->space
= space
;
5461 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
5463 return isl_multi_aff_free(maff
);
5466 for (i
= 0; i
< maff
->n
; ++i
) {
5467 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
5475 isl_local_space_free(*ls
);
5476 return isl_multi_aff_free(maff
);
5480 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
5482 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
5483 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
5493 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
5494 if (pos
< 0 || pos
>= n_out
)
5495 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5496 "index out of bounds", return NULL
);
5498 space
= isl_pw_multi_aff_get_space(pma
);
5499 space
= isl_space_drop_dims(space
, isl_dim_out
,
5500 pos
+ 1, n_out
- pos
- 1);
5501 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
5503 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
5504 for (i
= 0; i
< pma
->n
; ++i
) {
5506 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
5507 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
5513 /* Return an isl_pw_multi_aff with the given "set" as domain and
5514 * an unnamed zero-dimensional range.
5516 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
5517 __isl_take isl_set
*set
)
5522 space
= isl_set_get_space(set
);
5523 space
= isl_space_from_domain(space
);
5524 ma
= isl_multi_aff_zero(space
);
5525 return isl_pw_multi_aff_alloc(set
, ma
);
5528 /* Add an isl_pw_multi_aff with the given "set" as domain and
5529 * an unnamed zero-dimensional range to *user.
5531 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
5533 isl_union_pw_multi_aff
**upma
= user
;
5534 isl_pw_multi_aff
*pma
;
5536 pma
= isl_pw_multi_aff_from_domain(set
);
5537 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
5542 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
5543 * an unnamed zero-dimensional range.
5545 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
5546 __isl_take isl_union_set
*uset
)
5549 isl_union_pw_multi_aff
*upma
;
5554 space
= isl_union_set_get_space(uset
);
5555 upma
= isl_union_pw_multi_aff_empty(space
);
5557 if (isl_union_set_foreach_set(uset
,
5558 &add_pw_multi_aff_from_domain
, &upma
) < 0)
5561 isl_union_set_free(uset
);
5564 isl_union_set_free(uset
);
5565 isl_union_pw_multi_aff_free(upma
);
5569 /* Convert "pma" to an isl_map and add it to *umap.
5571 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
5573 isl_union_map
**umap
= user
;
5576 map
= isl_map_from_pw_multi_aff(pma
);
5577 *umap
= isl_union_map_add_map(*umap
, map
);
5582 /* Construct a union map mapping the domain of the union
5583 * piecewise multi-affine expression to its range, with each dimension
5584 * in the range equated to the corresponding affine expression on its cell.
5586 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
5587 __isl_take isl_union_pw_multi_aff
*upma
)
5590 isl_union_map
*umap
;
5595 space
= isl_union_pw_multi_aff_get_space(upma
);
5596 umap
= isl_union_map_empty(space
);
5598 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
5599 &map_from_pw_multi_aff
, &umap
) < 0)
5602 isl_union_pw_multi_aff_free(upma
);
5605 isl_union_pw_multi_aff_free(upma
);
5606 isl_union_map_free(umap
);
5610 /* Local data for bin_entry and the callback "fn".
5612 struct isl_union_pw_multi_aff_bin_data
{
5613 isl_union_pw_multi_aff
*upma2
;
5614 isl_union_pw_multi_aff
*res
;
5615 isl_pw_multi_aff
*pma
;
5616 int (*fn
)(void **entry
, void *user
);
5619 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
5620 * and call data->fn for each isl_pw_multi_aff in data->upma2.
5622 static int bin_entry(void **entry
, void *user
)
5624 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5625 isl_pw_multi_aff
*pma
= *entry
;
5628 if (isl_hash_table_foreach(data
->upma2
->space
->ctx
, &data
->upma2
->table
,
5629 data
->fn
, data
) < 0)
5635 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
5636 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
5637 * passed as user field) and the isl_pw_multi_aff from upma2 is available
5638 * as *entry. The callback should adjust data->res if desired.
5640 static __isl_give isl_union_pw_multi_aff
*bin_op(
5641 __isl_take isl_union_pw_multi_aff
*upma1
,
5642 __isl_take isl_union_pw_multi_aff
*upma2
,
5643 int (*fn
)(void **entry
, void *user
))
5646 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
5648 space
= isl_union_pw_multi_aff_get_space(upma2
);
5649 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
5650 space
= isl_union_pw_multi_aff_get_space(upma1
);
5651 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
5653 if (!upma1
|| !upma2
)
5657 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->space
),
5659 if (isl_hash_table_foreach(upma1
->space
->ctx
, &upma1
->table
,
5660 &bin_entry
, &data
) < 0)
5663 isl_union_pw_multi_aff_free(upma1
);
5664 isl_union_pw_multi_aff_free(upma2
);
5667 isl_union_pw_multi_aff_free(upma1
);
5668 isl_union_pw_multi_aff_free(upma2
);
5669 isl_union_pw_multi_aff_free(data
.res
);
5673 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5674 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5676 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
5677 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5681 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5682 isl_pw_multi_aff_get_space(pma2
));
5683 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5684 &isl_multi_aff_range_product
);
5687 /* Given two isl_pw_multi_affs A -> B and C -> D,
5688 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5690 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
5691 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5693 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5694 &pw_multi_aff_range_product
);
5697 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5698 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5700 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
5701 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5705 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5706 isl_pw_multi_aff_get_space(pma2
));
5707 space
= isl_space_flatten_range(space
);
5708 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5709 &isl_multi_aff_flat_range_product
);
5712 /* Given two isl_pw_multi_affs A -> B and C -> D,
5713 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5715 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
5716 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5718 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5719 &pw_multi_aff_flat_range_product
);
5722 /* If data->pma and *entry have the same domain space, then compute
5723 * their flat range product and the result to data->res.
5725 static int flat_range_product_entry(void **entry
, void *user
)
5727 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5728 isl_pw_multi_aff
*pma2
= *entry
;
5730 if (!isl_space_tuple_is_equal(data
->pma
->dim
, isl_dim_in
,
5731 pma2
->dim
, isl_dim_in
))
5734 pma2
= isl_pw_multi_aff_flat_range_product(
5735 isl_pw_multi_aff_copy(data
->pma
),
5736 isl_pw_multi_aff_copy(pma2
));
5738 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
5743 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
5744 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
5746 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
5747 __isl_take isl_union_pw_multi_aff
*upma1
,
5748 __isl_take isl_union_pw_multi_aff
*upma2
)
5750 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
5753 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5754 * The parameters are assumed to have been aligned.
5756 * The implementation essentially performs an isl_pw_*_on_shared_domain,
5757 * except that it works on two different isl_pw_* types.
5759 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
5760 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5761 __isl_take isl_pw_aff
*pa
)
5764 isl_pw_multi_aff
*res
= NULL
;
5769 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_in
,
5770 pa
->dim
, isl_dim_in
))
5771 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5772 "domains don't match", goto error
);
5773 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
5774 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5775 "index out of bounds", goto error
);
5778 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
5780 for (i
= 0; i
< pma
->n
; ++i
) {
5781 for (j
= 0; j
< pa
->n
; ++j
) {
5783 isl_multi_aff
*res_ij
;
5786 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
5787 isl_set_copy(pa
->p
[j
].set
));
5788 empty
= isl_set_plain_is_empty(common
);
5789 if (empty
< 0 || empty
) {
5790 isl_set_free(common
);
5796 res_ij
= isl_multi_aff_set_aff(
5797 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
5798 isl_aff_copy(pa
->p
[j
].aff
));
5799 res_ij
= isl_multi_aff_gist(res_ij
,
5800 isl_set_copy(common
));
5802 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5806 isl_pw_multi_aff_free(pma
);
5807 isl_pw_aff_free(pa
);
5810 isl_pw_multi_aff_free(pma
);
5811 isl_pw_aff_free(pa
);
5812 return isl_pw_multi_aff_free(res
);
5815 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5817 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
5818 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5819 __isl_take isl_pw_aff
*pa
)
5823 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
5824 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5825 if (!isl_space_has_named_params(pma
->dim
) ||
5826 !isl_space_has_named_params(pa
->dim
))
5827 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5828 "unaligned unnamed parameters", goto error
);
5829 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
5830 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
5831 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5833 isl_pw_multi_aff_free(pma
);
5834 isl_pw_aff_free(pa
);
5838 /* Do the parameters of "pa" match those of "space"?
5840 int isl_pw_aff_matching_params(__isl_keep isl_pw_aff
*pa
,
5841 __isl_keep isl_space
*space
)
5843 isl_space
*pa_space
;
5849 pa_space
= isl_pw_aff_get_space(pa
);
5851 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5853 isl_space_free(pa_space
);
5857 /* Check that the domain space of "pa" matches "space".
5859 * Return 0 on success and -1 on error.
5861 int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff
*pa
,
5862 __isl_keep isl_space
*space
)
5864 isl_space
*pa_space
;
5870 pa_space
= isl_pw_aff_get_space(pa
);
5872 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5876 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5877 "parameters don't match", goto error
);
5878 match
= isl_space_tuple_is_equal(space
, isl_dim_in
,
5879 pa_space
, isl_dim_in
);
5883 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5884 "domains don't match", goto error
);
5885 isl_space_free(pa_space
);
5888 isl_space_free(pa_space
);
5895 #include <isl_multi_templ.c>
5897 /* Scale the elements of "pma" by the corresponding elements of "mv".
5899 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_scale_multi_val(
5900 __isl_take isl_pw_multi_aff
*pma
, __isl_take isl_multi_val
*mv
)
5904 pma
= isl_pw_multi_aff_cow(pma
);
5907 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_out
,
5908 mv
->space
, isl_dim_set
))
5909 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5910 "spaces don't match", goto error
);
5911 if (!isl_space_match(pma
->dim
, isl_dim_param
,
5912 mv
->space
, isl_dim_param
)) {
5913 pma
= isl_pw_multi_aff_align_params(pma
,
5914 isl_multi_val_get_space(mv
));
5915 mv
= isl_multi_val_align_params(mv
,
5916 isl_pw_multi_aff_get_space(pma
));
5921 for (i
= 0; i
< pma
->n
; ++i
) {
5922 pma
->p
[i
].maff
= isl_multi_aff_scale_multi_val(pma
->p
[i
].maff
,
5923 isl_multi_val_copy(mv
));
5924 if (!pma
->p
[i
].maff
)
5928 isl_multi_val_free(mv
);
5931 isl_multi_val_free(mv
);
5932 isl_pw_multi_aff_free(pma
);
5936 /* Internal data structure for isl_union_pw_multi_aff_scale_multi_val.
5937 * mv contains the mv argument.
5938 * res collects the results.
5940 struct isl_union_pw_multi_aff_scale_multi_val_data
{
5942 isl_union_pw_multi_aff
*res
;
5945 /* This function is called for each entry of an isl_union_pw_multi_aff.
5946 * If the space of the entry matches that of data->mv,
5947 * then apply isl_pw_multi_aff_scale_multi_val and add the result
5950 static int union_pw_multi_aff_scale_multi_val_entry(void **entry
, void *user
)
5952 struct isl_union_pw_multi_aff_scale_multi_val_data
*data
= user
;
5953 isl_pw_multi_aff
*pma
= *entry
;
5957 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_out
,
5958 data
->mv
->space
, isl_dim_set
))
5961 pma
= isl_pw_multi_aff_copy(pma
);
5962 pma
= isl_pw_multi_aff_scale_multi_val(pma
,
5963 isl_multi_val_copy(data
->mv
));
5964 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
5971 /* Scale the elements of "upma" by the corresponding elements of "mv",
5972 * for those entries that match the space of "mv".
5974 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_scale_multi_val(
5975 __isl_take isl_union_pw_multi_aff
*upma
, __isl_take isl_multi_val
*mv
)
5977 struct isl_union_pw_multi_aff_scale_multi_val_data data
;
5979 upma
= isl_union_pw_multi_aff_align_params(upma
,
5980 isl_multi_val_get_space(mv
));
5981 mv
= isl_multi_val_align_params(mv
,
5982 isl_union_pw_multi_aff_get_space(upma
));
5987 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma
->space
),
5989 if (isl_hash_table_foreach(upma
->space
->ctx
, &upma
->table
,
5990 &union_pw_multi_aff_scale_multi_val_entry
, &data
) < 0)
5993 isl_multi_val_free(mv
);
5994 isl_union_pw_multi_aff_free(upma
);
5997 isl_multi_val_free(mv
);
5998 isl_union_pw_multi_aff_free(upma
);
6002 /* Construct and return a piecewise multi affine expression
6003 * in the given space with value zero in each of the output dimensions and
6004 * a universe domain.
6006 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_zero(__isl_take isl_space
*space
)
6008 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_zero(space
));
6011 /* Construct and return a piecewise multi affine expression
6012 * that is equal to the given piecewise affine expression.
6014 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_pw_aff(
6015 __isl_take isl_pw_aff
*pa
)
6019 isl_pw_multi_aff
*pma
;
6024 space
= isl_pw_aff_get_space(pa
);
6025 pma
= isl_pw_multi_aff_alloc_size(space
, pa
->n
);
6027 for (i
= 0; i
< pa
->n
; ++i
) {
6031 set
= isl_set_copy(pa
->p
[i
].set
);
6032 ma
= isl_multi_aff_from_aff(isl_aff_copy(pa
->p
[i
].aff
));
6033 pma
= isl_pw_multi_aff_add_piece(pma
, set
, ma
);
6036 isl_pw_aff_free(pa
);
6040 /* Construct a set or map mapping the shared (parameter) domain
6041 * of the piecewise affine expressions to the range of "mpa"
6042 * with each dimension in the range equated to the
6043 * corresponding piecewise affine expression.
6045 static __isl_give isl_map
*map_from_multi_pw_aff(
6046 __isl_take isl_multi_pw_aff
*mpa
)
6055 if (isl_space_dim(mpa
->space
, isl_dim_out
) != mpa
->n
)
6056 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6057 "invalid space", goto error
);
6059 space
= isl_multi_pw_aff_get_domain_space(mpa
);
6060 map
= isl_map_universe(isl_space_from_domain(space
));
6062 for (i
= 0; i
< mpa
->n
; ++i
) {
6066 pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6067 map_i
= map_from_pw_aff(pa
);
6069 map
= isl_map_flat_range_product(map
, map_i
);
6072 map
= isl_map_reset_space(map
, isl_multi_pw_aff_get_space(mpa
));
6074 isl_multi_pw_aff_free(mpa
);
6077 isl_multi_pw_aff_free(mpa
);
6081 /* Construct a map mapping the shared domain
6082 * of the piecewise affine expressions to the range of "mpa"
6083 * with each dimension in the range equated to the
6084 * corresponding piecewise affine expression.
6086 __isl_give isl_map
*isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6090 if (isl_space_is_set(mpa
->space
))
6091 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6092 "space of input is not a map", goto error
);
6094 return map_from_multi_pw_aff(mpa
);
6096 isl_multi_pw_aff_free(mpa
);
6100 /* Construct a set mapping the shared parameter domain
6101 * of the piecewise affine expressions to the space of "mpa"
6102 * with each dimension in the range equated to the
6103 * corresponding piecewise affine expression.
6105 __isl_give isl_set
*isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6109 if (!isl_space_is_set(mpa
->space
))
6110 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6111 "space of input is not a set", goto error
);
6113 return map_from_multi_pw_aff(mpa
);
6115 isl_multi_pw_aff_free(mpa
);
6119 /* Construct and return a piecewise multi affine expression
6120 * that is equal to the given multi piecewise affine expression
6121 * on the shared domain of the piecewise affine expressions.
6123 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_pw_aff(
6124 __isl_take isl_multi_pw_aff
*mpa
)
6129 isl_pw_multi_aff
*pma
;
6134 space
= isl_multi_pw_aff_get_space(mpa
);
6137 isl_multi_pw_aff_free(mpa
);
6138 return isl_pw_multi_aff_zero(space
);
6141 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
6142 pma
= isl_pw_multi_aff_from_pw_aff(pa
);
6144 for (i
= 1; i
< mpa
->n
; ++i
) {
6145 isl_pw_multi_aff
*pma_i
;
6147 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6148 pma_i
= isl_pw_multi_aff_from_pw_aff(pa
);
6149 pma
= isl_pw_multi_aff_range_product(pma
, pma_i
);
6152 pma
= isl_pw_multi_aff_reset_space(pma
, space
);
6154 isl_multi_pw_aff_free(mpa
);
6158 /* Construct and return a multi piecewise affine expression
6159 * that is equal to the given multi affine expression.
6161 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_multi_aff(
6162 __isl_take isl_multi_aff
*ma
)
6165 isl_multi_pw_aff
*mpa
;
6170 n
= isl_multi_aff_dim(ma
, isl_dim_out
);
6171 mpa
= isl_multi_pw_aff_alloc(isl_multi_aff_get_space(ma
));
6173 for (i
= 0; i
< n
; ++i
) {
6176 pa
= isl_pw_aff_from_aff(isl_multi_aff_get_aff(ma
, i
));
6177 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6180 isl_multi_aff_free(ma
);
6184 /* Construct and return a multi piecewise affine expression
6185 * that is equal to the given piecewise multi affine expression.
6187 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_pw_multi_aff(
6188 __isl_take isl_pw_multi_aff
*pma
)
6192 isl_multi_pw_aff
*mpa
;
6197 n
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
6198 space
= isl_pw_multi_aff_get_space(pma
);
6199 mpa
= isl_multi_pw_aff_alloc(space
);
6201 for (i
= 0; i
< n
; ++i
) {
6204 pa
= isl_pw_multi_aff_get_pw_aff(pma
, i
);
6205 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6208 isl_pw_multi_aff_free(pma
);
6212 /* Do "pa1" and "pa2" represent the same function?
6214 * We first check if they are obviously equal.
6215 * If not, we convert them to maps and check if those are equal.
6217 int isl_pw_aff_is_equal(__isl_keep isl_pw_aff
*pa1
, __isl_keep isl_pw_aff
*pa2
)
6220 isl_map
*map1
, *map2
;
6225 equal
= isl_pw_aff_plain_is_equal(pa1
, pa2
);
6226 if (equal
< 0 || equal
)
6229 map1
= map_from_pw_aff(isl_pw_aff_copy(pa1
));
6230 map2
= map_from_pw_aff(isl_pw_aff_copy(pa2
));
6231 equal
= isl_map_is_equal(map1
, map2
);
6238 /* Do "mpa1" and "mpa2" represent the same function?
6240 * Note that we cannot convert the entire isl_multi_pw_aff
6241 * to a map because the domains of the piecewise affine expressions
6242 * may not be the same.
6244 int isl_multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
6245 __isl_keep isl_multi_pw_aff
*mpa2
)
6253 if (!isl_space_match(mpa1
->space
, isl_dim_param
,
6254 mpa2
->space
, isl_dim_param
)) {
6255 if (!isl_space_has_named_params(mpa1
->space
))
6257 if (!isl_space_has_named_params(mpa2
->space
))
6259 mpa1
= isl_multi_pw_aff_copy(mpa1
);
6260 mpa2
= isl_multi_pw_aff_copy(mpa2
);
6261 mpa1
= isl_multi_pw_aff_align_params(mpa1
,
6262 isl_multi_pw_aff_get_space(mpa2
));
6263 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
6264 isl_multi_pw_aff_get_space(mpa1
));
6265 equal
= isl_multi_pw_aff_is_equal(mpa1
, mpa2
);
6266 isl_multi_pw_aff_free(mpa1
);
6267 isl_multi_pw_aff_free(mpa2
);
6271 equal
= isl_space_is_equal(mpa1
->space
, mpa2
->space
);
6272 if (equal
< 0 || !equal
)
6275 for (i
= 0; i
< mpa1
->n
; ++i
) {
6276 equal
= isl_pw_aff_is_equal(mpa1
->p
[i
], mpa2
->p
[i
]);
6277 if (equal
< 0 || !equal
)
6284 /* Coalesce the elements of "mpa".
6286 * Note that such coalescing does not change the meaning of "mpa"
6287 * so there is no need to cow. We do need to be careful not to
6288 * destroy any other copies of "mpa" in case of failure.
6290 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_coalesce(
6291 __isl_take isl_multi_pw_aff
*mpa
)
6298 for (i
= 0; i
< mpa
->n
; ++i
) {
6299 isl_pw_aff
*pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6300 pa
= isl_pw_aff_coalesce(pa
);
6302 return isl_multi_pw_aff_free(mpa
);
6303 isl_pw_aff_free(mpa
->p
[i
]);
6310 /* Compute the pullback of "mpa" by the function represented by "ma".
6311 * In other words, plug in "ma" in "mpa".
6313 * The parameters of "mpa" and "ma" are assumed to have been aligned.
6315 static __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff_aligned(
6316 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6319 isl_space
*space
= NULL
;
6321 mpa
= isl_multi_pw_aff_cow(mpa
);
6325 space
= isl_space_join(isl_multi_aff_get_space(ma
),
6326 isl_multi_pw_aff_get_space(mpa
));
6330 for (i
= 0; i
< mpa
->n
; ++i
) {
6331 mpa
->p
[i
] = isl_pw_aff_pullback_multi_aff(mpa
->p
[i
],
6332 isl_multi_aff_copy(ma
));
6337 isl_multi_aff_free(ma
);
6338 isl_space_free(mpa
->space
);
6342 isl_space_free(space
);
6343 isl_multi_pw_aff_free(mpa
);
6344 isl_multi_aff_free(ma
);
6348 /* Compute the pullback of "mpa" by the function represented by "ma".
6349 * In other words, plug in "ma" in "mpa".
6351 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff(
6352 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6356 if (isl_space_match(mpa
->space
, isl_dim_param
,
6357 ma
->space
, isl_dim_param
))
6358 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6359 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_multi_aff_get_space(ma
));
6360 ma
= isl_multi_aff_align_params(ma
, isl_multi_pw_aff_get_space(mpa
));
6361 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6363 isl_multi_pw_aff_free(mpa
);
6364 isl_multi_aff_free(ma
);
6368 /* Compute the pullback of "mpa" by the function represented by "pma".
6369 * In other words, plug in "pma" in "mpa".
6371 * The parameters of "mpa" and "mpa" are assumed to have been aligned.
6373 static __isl_give isl_multi_pw_aff
*
6374 isl_multi_pw_aff_pullback_pw_multi_aff_aligned(
6375 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6378 isl_space
*space
= NULL
;
6380 mpa
= isl_multi_pw_aff_cow(mpa
);
6384 space
= isl_space_join(isl_pw_multi_aff_get_space(pma
),
6385 isl_multi_pw_aff_get_space(mpa
));
6387 for (i
= 0; i
< mpa
->n
; ++i
) {
6388 mpa
->p
[i
] = isl_pw_aff_pullback_pw_multi_aff_aligned(mpa
->p
[i
],
6389 isl_pw_multi_aff_copy(pma
));
6394 isl_pw_multi_aff_free(pma
);
6395 isl_space_free(mpa
->space
);
6399 isl_space_free(space
);
6400 isl_multi_pw_aff_free(mpa
);
6401 isl_pw_multi_aff_free(pma
);
6405 /* Compute the pullback of "mpa" by the function represented by "pma".
6406 * In other words, plug in "pma" in "mpa".
6408 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_pw_multi_aff(
6409 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6413 if (isl_space_match(mpa
->space
, isl_dim_param
, pma
->dim
, isl_dim_param
))
6414 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6415 mpa
= isl_multi_pw_aff_align_params(mpa
,
6416 isl_pw_multi_aff_get_space(pma
));
6417 pma
= isl_pw_multi_aff_align_params(pma
,
6418 isl_multi_pw_aff_get_space(mpa
));
6419 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6421 isl_multi_pw_aff_free(mpa
);
6422 isl_pw_multi_aff_free(pma
);
6426 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6427 * with the domain of "aff". The domain of the result is the same
6429 * "mpa" and "aff" are assumed to have been aligned.
6431 * We first extract the parametric constant from "aff", defined
6432 * over the correct domain.
6433 * Then we add the appropriate combinations of the members of "mpa".
6434 * Finally, we add the integer divisions through recursive calls.
6436 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff_aligned(
6437 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6439 int i
, n_param
, n_in
, n_div
;
6445 n_param
= isl_aff_dim(aff
, isl_dim_param
);
6446 n_in
= isl_aff_dim(aff
, isl_dim_in
);
6447 n_div
= isl_aff_dim(aff
, isl_dim_div
);
6449 space
= isl_space_domain(isl_multi_pw_aff_get_space(mpa
));
6450 tmp
= isl_aff_copy(aff
);
6451 tmp
= isl_aff_drop_dims(tmp
, isl_dim_div
, 0, n_div
);
6452 tmp
= isl_aff_drop_dims(tmp
, isl_dim_in
, 0, n_in
);
6453 tmp
= isl_aff_add_dims(tmp
, isl_dim_in
,
6454 isl_space_dim(space
, isl_dim_set
));
6455 tmp
= isl_aff_reset_domain_space(tmp
, space
);
6456 pa
= isl_pw_aff_from_aff(tmp
);
6458 for (i
= 0; i
< n_in
; ++i
) {
6461 if (!isl_aff_involves_dims(aff
, isl_dim_in
, i
, 1))
6463 v
= isl_aff_get_coefficient_val(aff
, isl_dim_in
, i
);
6464 pa_i
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6465 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6466 pa
= isl_pw_aff_add(pa
, pa_i
);
6469 for (i
= 0; i
< n_div
; ++i
) {
6473 if (!isl_aff_involves_dims(aff
, isl_dim_div
, i
, 1))
6475 div
= isl_aff_get_div(aff
, i
);
6476 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6477 isl_multi_pw_aff_copy(mpa
), div
);
6478 pa_i
= isl_pw_aff_floor(pa_i
);
6479 v
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, i
);
6480 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6481 pa
= isl_pw_aff_add(pa
, pa_i
);
6484 isl_multi_pw_aff_free(mpa
);
6490 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6491 * with the domain of "aff". The domain of the result is the same
6494 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff(
6495 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6499 if (isl_space_match(aff
->ls
->dim
, isl_dim_param
,
6500 mpa
->space
, isl_dim_param
))
6501 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6503 aff
= isl_aff_align_params(aff
, isl_multi_pw_aff_get_space(mpa
));
6504 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_aff_get_space(aff
));
6506 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6509 isl_multi_pw_aff_free(mpa
);
6513 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6514 * with the domain of "pa". The domain of the result is the same
6516 * "mpa" and "pa" are assumed to have been aligned.
6518 * We consider each piece in turn. Note that the domains of the
6519 * pieces are assumed to be disjoint and they remain disjoint
6520 * after taking the preimage (over the same function).
6522 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff_aligned(
6523 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6532 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa
),
6533 isl_pw_aff_get_space(pa
));
6534 res
= isl_pw_aff_empty(space
);
6536 for (i
= 0; i
< pa
->n
; ++i
) {
6540 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6541 isl_multi_pw_aff_copy(mpa
),
6542 isl_aff_copy(pa
->p
[i
].aff
));
6543 domain
= isl_set_copy(pa
->p
[i
].set
);
6544 domain
= isl_set_preimage_multi_pw_aff(domain
,
6545 isl_multi_pw_aff_copy(mpa
));
6546 pa_i
= isl_pw_aff_intersect_domain(pa_i
, domain
);
6547 res
= isl_pw_aff_add_disjoint(res
, pa_i
);
6550 isl_pw_aff_free(pa
);
6551 isl_multi_pw_aff_free(mpa
);
6554 isl_pw_aff_free(pa
);
6555 isl_multi_pw_aff_free(mpa
);
6559 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6560 * with the domain of "pa". The domain of the result is the same
6563 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff(
6564 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6568 if (isl_space_match(pa
->dim
, isl_dim_param
, mpa
->space
, isl_dim_param
))
6569 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6571 pa
= isl_pw_aff_align_params(pa
, isl_multi_pw_aff_get_space(mpa
));
6572 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_pw_aff_get_space(pa
));
6574 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6576 isl_pw_aff_free(pa
);
6577 isl_multi_pw_aff_free(mpa
);
6581 /* Compute the pullback of "pa" by the function represented by "mpa".
6582 * In other words, plug in "mpa" in "pa".
6583 * "pa" and "mpa" are assumed to have been aligned.
6585 * The pullback is computed by applying "pa" to "mpa".
6587 static __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff_aligned(
6588 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6590 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6593 /* Compute the pullback of "pa" by the function represented by "mpa".
6594 * In other words, plug in "mpa" in "pa".
6596 * The pullback is computed by applying "pa" to "mpa".
6598 __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff(
6599 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6601 return isl_multi_pw_aff_apply_pw_aff(mpa
, pa
);
6604 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6605 * In other words, plug in "mpa2" in "mpa1".
6607 * The parameters of "mpa1" and "mpa2" are assumed to have been aligned.
6609 * We pullback each member of "mpa1" in turn.
6611 static __isl_give isl_multi_pw_aff
*
6612 isl_multi_pw_aff_pullback_multi_pw_aff_aligned(
6613 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6616 isl_space
*space
= NULL
;
6618 mpa1
= isl_multi_pw_aff_cow(mpa1
);
6622 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa2
),
6623 isl_multi_pw_aff_get_space(mpa1
));
6625 for (i
= 0; i
< mpa1
->n
; ++i
) {
6626 mpa1
->p
[i
] = isl_pw_aff_pullback_multi_pw_aff_aligned(
6627 mpa1
->p
[i
], isl_multi_pw_aff_copy(mpa2
));
6632 mpa1
= isl_multi_pw_aff_reset_space(mpa1
, space
);
6634 isl_multi_pw_aff_free(mpa2
);
6637 isl_space_free(space
);
6638 isl_multi_pw_aff_free(mpa1
);
6639 isl_multi_pw_aff_free(mpa2
);
6643 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6644 * In other words, plug in "mpa2" in "mpa1".
6646 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_pw_aff(
6647 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6649 return isl_multi_pw_aff_align_params_multi_multi_and(mpa1
, mpa2
,
6650 &isl_multi_pw_aff_pullback_multi_pw_aff_aligned
);
6653 /* Compare two isl_affs.
6655 * Return -1 if "aff1" is "smaller" than "aff2", 1 if "aff1" is "greater"
6656 * than "aff2" and 0 if they are equal.
6658 * The order is fairly arbitrary. We do consider expressions that only involve
6659 * earlier dimensions as "smaller".
6661 int isl_aff_plain_cmp(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
6674 cmp
= isl_local_space_cmp(aff1
->ls
, aff2
->ls
);
6678 last1
= isl_seq_last_non_zero(aff1
->v
->el
+ 1, aff1
->v
->size
- 1);
6679 last2
= isl_seq_last_non_zero(aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
6681 return last1
- last2
;
6683 return isl_seq_cmp(aff1
->v
->el
, aff2
->v
->el
, aff1
->v
->size
);
6686 /* Compare two isl_pw_affs.
6688 * Return -1 if "pa1" is "smaller" than "pa2", 1 if "pa1" is "greater"
6689 * than "pa2" and 0 if they are equal.
6691 * The order is fairly arbitrary. We do consider expressions that only involve
6692 * earlier dimensions as "smaller".
6694 int isl_pw_aff_plain_cmp(__isl_keep isl_pw_aff
*pa1
,
6695 __isl_keep isl_pw_aff
*pa2
)
6708 cmp
= isl_space_cmp(pa1
->dim
, pa2
->dim
);
6712 if (pa1
->n
!= pa2
->n
)
6713 return pa1
->n
- pa2
->n
;
6715 for (i
= 0; i
< pa1
->n
; ++i
) {
6716 cmp
= isl_set_plain_cmp(pa1
->p
[i
].set
, pa2
->p
[i
].set
);
6719 cmp
= isl_aff_plain_cmp(pa1
->p
[i
].aff
, pa2
->p
[i
].aff
);
6727 /* Return a piecewise affine expression that is equal to "v" on "domain".
6729 __isl_give isl_pw_aff
*isl_pw_aff_val_on_domain(__isl_take isl_set
*domain
,
6730 __isl_take isl_val
*v
)
6733 isl_local_space
*ls
;
6736 space
= isl_set_get_space(domain
);
6737 ls
= isl_local_space_from_space(space
);
6738 aff
= isl_aff_val_on_domain(ls
, v
);
6740 return isl_pw_aff_alloc(domain
, aff
);
6743 /* Return a multi affine expression that is equal to "mv" on domain
6746 __isl_give isl_multi_aff
*isl_multi_aff_multi_val_on_space(
6747 __isl_take isl_space
*space
, __isl_take isl_multi_val
*mv
)
6751 isl_local_space
*ls
;
6757 n
= isl_multi_val_dim(mv
, isl_dim_set
);
6758 space2
= isl_multi_val_get_space(mv
);
6759 space2
= isl_space_align_params(space2
, isl_space_copy(space
));
6760 space
= isl_space_align_params(space
, isl_space_copy(space2
));
6761 space
= isl_space_map_from_domain_and_range(space
, space2
);
6762 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
6763 ls
= isl_local_space_from_space(isl_space_domain(space
));
6764 for (i
= 0; i
< n
; ++i
) {
6768 v
= isl_multi_val_get_val(mv
, i
);
6769 aff
= isl_aff_val_on_domain(isl_local_space_copy(ls
), v
);
6770 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
6772 isl_local_space_free(ls
);
6774 isl_multi_val_free(mv
);
6777 isl_space_free(space
);
6778 isl_multi_val_free(mv
);
6782 /* Return a piecewise multi-affine expression
6783 * that is equal to "mv" on "domain".
6785 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_multi_val_on_domain(
6786 __isl_take isl_set
*domain
, __isl_take isl_multi_val
*mv
)
6791 space
= isl_set_get_space(domain
);
6792 ma
= isl_multi_aff_multi_val_on_space(space
, mv
);
6794 return isl_pw_multi_aff_alloc(domain
, ma
);
6797 /* Internal data structure for isl_union_pw_multi_aff_multi_val_on_domain.
6798 * mv is the value that should be attained on each domain set
6799 * res collects the results
6801 struct isl_union_pw_multi_aff_multi_val_on_domain_data
{
6803 isl_union_pw_multi_aff
*res
;
6806 /* Create an isl_pw_multi_aff equal to data->mv on "domain"
6807 * and add it to data->res.
6809 static int pw_multi_aff_multi_val_on_domain(__isl_take isl_set
*domain
,
6812 struct isl_union_pw_multi_aff_multi_val_on_domain_data
*data
= user
;
6813 isl_pw_multi_aff
*pma
;
6816 mv
= isl_multi_val_copy(data
->mv
);
6817 pma
= isl_pw_multi_aff_multi_val_on_domain(domain
, mv
);
6818 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
6820 return data
->res
? 0 : -1;
6823 /* Return a union piecewise multi-affine expression
6824 * that is equal to "mv" on "domain".
6826 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_multi_val_on_domain(
6827 __isl_take isl_union_set
*domain
, __isl_take isl_multi_val
*mv
)
6829 struct isl_union_pw_multi_aff_multi_val_on_domain_data data
;
6832 space
= isl_union_set_get_space(domain
);
6833 data
.res
= isl_union_pw_multi_aff_empty(space
);
6835 if (isl_union_set_foreach_set(domain
,
6836 &pw_multi_aff_multi_val_on_domain
, &data
) < 0)
6837 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
6838 isl_union_set_free(domain
);
6839 isl_multi_val_free(mv
);
6843 /* Compute the pullback of data->pma by the function represented by "pma2",
6844 * provided the spaces match, and add the results to data->res.
6846 static int pullback_entry(void **entry
, void *user
)
6848 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
6849 isl_pw_multi_aff
*pma2
= *entry
;
6851 if (!isl_space_tuple_is_equal(data
->pma
->dim
, isl_dim_in
,
6852 pma2
->dim
, isl_dim_out
))
6855 pma2
= isl_pw_multi_aff_pullback_pw_multi_aff(
6856 isl_pw_multi_aff_copy(data
->pma
),
6857 isl_pw_multi_aff_copy(pma2
));
6859 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
6866 /* Compute the pullback of "upma1" by the function represented by "upma2".
6868 __isl_give isl_union_pw_multi_aff
*
6869 isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
6870 __isl_take isl_union_pw_multi_aff
*upma1
,
6871 __isl_take isl_union_pw_multi_aff
*upma2
)
6873 return bin_op(upma1
, upma2
, &pullback_entry
);