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 /* Try and create an isl_union_pw_multi_aff that is equivalent
4907 * to the given isl_union_map.
4908 * The isl_union_map is required to be single-valued in each space.
4909 * Otherwise, an error is produced.
4911 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_map(
4912 __isl_take isl_union_map
*umap
)
4915 isl_union_pw_multi_aff
*upma
;
4917 space
= isl_union_map_get_space(umap
);
4918 upma
= isl_union_pw_multi_aff_empty(space
);
4919 if (isl_union_map_foreach_map(umap
, &pw_multi_aff_from_map
, &upma
) < 0)
4920 upma
= isl_union_pw_multi_aff_free(upma
);
4921 isl_union_map_free(umap
);
4926 /* Try and create an isl_union_pw_multi_aff that is equivalent
4927 * to the given isl_union_set.
4928 * The isl_union_set is required to be a singleton in each space.
4929 * Otherwise, an error is produced.
4931 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_set(
4932 __isl_take isl_union_set
*uset
)
4934 return isl_union_pw_multi_aff_from_union_map(uset
);
4937 /* Return the piecewise affine expression "set ? 1 : 0".
4939 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
4942 isl_space
*space
= isl_set_get_space(set
);
4943 isl_local_space
*ls
= isl_local_space_from_space(space
);
4944 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
4945 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
4947 one
= isl_aff_add_constant_si(one
, 1);
4948 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
4949 set
= isl_set_complement(set
);
4950 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
4955 /* Plug in "subs" for dimension "type", "pos" of "aff".
4957 * Let i be the dimension to replace and let "subs" be of the form
4961 * and "aff" of the form
4967 * (a f + d g')/(m d)
4969 * where g' is the result of plugging in "subs" in each of the integer
4972 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
4973 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
4978 aff
= isl_aff_cow(aff
);
4980 return isl_aff_free(aff
);
4982 ctx
= isl_aff_get_ctx(aff
);
4983 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
4984 isl_die(ctx
, isl_error_invalid
,
4985 "spaces don't match", return isl_aff_free(aff
));
4986 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
4987 isl_die(ctx
, isl_error_unsupported
,
4988 "cannot handle divs yet", return isl_aff_free(aff
));
4990 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
4992 return isl_aff_free(aff
);
4994 aff
->v
= isl_vec_cow(aff
->v
);
4996 return isl_aff_free(aff
);
4998 pos
+= isl_local_space_offset(aff
->ls
, type
);
5001 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
5002 aff
->v
->size
, subs
->v
->size
, v
);
5008 /* Plug in "subs" for dimension "type", "pos" in each of the affine
5009 * expressions in "maff".
5011 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
5012 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
5013 __isl_keep isl_aff
*subs
)
5017 maff
= isl_multi_aff_cow(maff
);
5019 return isl_multi_aff_free(maff
);
5021 if (type
== isl_dim_in
)
5024 for (i
= 0; i
< maff
->n
; ++i
) {
5025 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
5027 return isl_multi_aff_free(maff
);
5033 /* Plug in "subs" for dimension "type", "pos" of "pma".
5035 * pma is of the form
5039 * while subs is of the form
5041 * v' = B_j(v) -> S_j
5043 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
5044 * has a contribution in the result, in particular
5046 * C_ij(S_j) -> M_i(S_j)
5048 * Note that plugging in S_j in C_ij may also result in an empty set
5049 * and this contribution should simply be discarded.
5051 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
5052 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
5053 __isl_keep isl_pw_aff
*subs
)
5056 isl_pw_multi_aff
*res
;
5059 return isl_pw_multi_aff_free(pma
);
5061 n
= pma
->n
* subs
->n
;
5062 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
5064 for (i
= 0; i
< pma
->n
; ++i
) {
5065 for (j
= 0; j
< subs
->n
; ++j
) {
5067 isl_multi_aff
*res_ij
;
5070 common
= isl_set_intersect(
5071 isl_set_copy(pma
->p
[i
].set
),
5072 isl_set_copy(subs
->p
[j
].set
));
5073 common
= isl_set_substitute(common
,
5074 type
, pos
, subs
->p
[j
].aff
);
5075 empty
= isl_set_plain_is_empty(common
);
5076 if (empty
< 0 || empty
) {
5077 isl_set_free(common
);
5083 res_ij
= isl_multi_aff_substitute(
5084 isl_multi_aff_copy(pma
->p
[i
].maff
),
5085 type
, pos
, subs
->p
[j
].aff
);
5087 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5091 isl_pw_multi_aff_free(pma
);
5094 isl_pw_multi_aff_free(pma
);
5095 isl_pw_multi_aff_free(res
);
5099 /* Compute the preimage of a range of dimensions in the affine expression "src"
5100 * under "ma" and put the result in "dst". The number of dimensions in "src"
5101 * that precede the range is given by "n_before". The number of dimensions
5102 * in the range is given by the number of output dimensions of "ma".
5103 * The number of dimensions that follow the range is given by "n_after".
5104 * If "has_denom" is set (to one),
5105 * then "src" and "dst" have an extra initial denominator.
5106 * "n_div_ma" is the number of existentials in "ma"
5107 * "n_div_bset" is the number of existentials in "src"
5108 * The resulting "dst" (which is assumed to have been allocated by
5109 * the caller) contains coefficients for both sets of existentials,
5110 * first those in "ma" and then those in "src".
5111 * f, c1, c2 and g are temporary objects that have been initialized
5114 * Let src represent the expression
5116 * (a(p) + f_u u + b v + f_w w + c(divs))/d
5118 * and let ma represent the expressions
5120 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
5122 * We start out with the following expression for dst:
5124 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d
5126 * with the multiplication factor f initially equal to 1
5127 * and f \sum_i b_i v_i kept separately.
5128 * For each x_i that we substitute, we multiply the numerator
5129 * (and denominator) of dst by c_1 = m_i and add the numerator
5130 * of the x_i expression multiplied by c_2 = f b_i,
5131 * after removing the common factors of c_1 and c_2.
5132 * The multiplication factor f also needs to be multiplied by c_1
5133 * for the next x_j, j > i.
5135 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
5136 __isl_keep isl_multi_aff
*ma
, int n_before
, int n_after
,
5137 int n_div_ma
, int n_div_bmap
,
5138 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
5141 int n_param
, n_in
, n_out
;
5144 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
5145 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
5146 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
5148 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
+ n_before
);
5149 o_dst
= o_src
= has_denom
+ 1 + n_param
+ n_before
;
5150 isl_seq_clr(dst
+ o_dst
, n_in
);
5153 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_after
);
5156 isl_seq_clr(dst
+ o_dst
, n_div_ma
);
5158 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_div_bmap
);
5160 isl_int_set_si(f
, 1);
5162 for (i
= 0; i
< n_out
; ++i
) {
5163 int offset
= has_denom
+ 1 + n_param
+ n_before
+ i
;
5165 if (isl_int_is_zero(src
[offset
]))
5167 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
5168 isl_int_mul(c2
, f
, src
[offset
]);
5169 isl_int_gcd(g
, c1
, c2
);
5170 isl_int_divexact(c1
, c1
, g
);
5171 isl_int_divexact(c2
, c2
, g
);
5173 isl_int_mul(f
, f
, c1
);
5176 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5177 c2
, ma
->p
[i
]->v
->el
+ o_src
, 1 + n_param
);
5178 o_dst
+= 1 + n_param
;
5179 o_src
+= 1 + n_param
;
5180 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_before
);
5182 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5183 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_in
);
5186 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_after
);
5188 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5189 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_div_ma
);
5192 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_div_bmap
);
5194 isl_int_mul(dst
[0], dst
[0], c1
);
5198 /* Compute the pullback of "aff" by the function represented by "ma".
5199 * In other words, plug in "ma" in "aff". The result is an affine expression
5200 * defined over the domain space of "ma".
5202 * If "aff" is represented by
5204 * (a(p) + b x + c(divs))/d
5206 * and ma is represented by
5208 * x = D(p) + F(y) + G(divs')
5210 * then the result is
5212 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
5214 * The divs in the local space of the input are similarly adjusted
5215 * through a call to isl_local_space_preimage_multi_aff.
5217 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
5218 __isl_take isl_multi_aff
*ma
)
5220 isl_aff
*res
= NULL
;
5221 isl_local_space
*ls
;
5222 int n_div_aff
, n_div_ma
;
5223 isl_int f
, c1
, c2
, g
;
5225 ma
= isl_multi_aff_align_divs(ma
);
5229 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
5230 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
5232 ls
= isl_aff_get_domain_local_space(aff
);
5233 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
5234 res
= isl_aff_alloc(ls
);
5243 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, 0, 0, n_div_ma
, n_div_aff
,
5252 isl_multi_aff_free(ma
);
5253 res
= isl_aff_normalize(res
);
5257 isl_multi_aff_free(ma
);
5262 /* Compute the pullback of "aff1" by the function represented by "aff2".
5263 * In other words, plug in "aff2" in "aff1". The result is an affine expression
5264 * defined over the domain space of "aff1".
5266 * The domain of "aff1" should match the range of "aff2", which means
5267 * that it should be single-dimensional.
5269 __isl_give isl_aff
*isl_aff_pullback_aff(__isl_take isl_aff
*aff1
,
5270 __isl_take isl_aff
*aff2
)
5274 ma
= isl_multi_aff_from_aff(aff2
);
5275 return isl_aff_pullback_multi_aff(aff1
, ma
);
5278 /* Compute the pullback of "ma1" by the function represented by "ma2".
5279 * In other words, plug in "ma2" in "ma1".
5281 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
5283 static __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff_aligned(
5284 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5287 isl_space
*space
= NULL
;
5289 ma2
= isl_multi_aff_align_divs(ma2
);
5290 ma1
= isl_multi_aff_cow(ma1
);
5294 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
5295 isl_multi_aff_get_space(ma1
));
5297 for (i
= 0; i
< ma1
->n
; ++i
) {
5298 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
5299 isl_multi_aff_copy(ma2
));
5304 ma1
= isl_multi_aff_reset_space(ma1
, space
);
5305 isl_multi_aff_free(ma2
);
5308 isl_space_free(space
);
5309 isl_multi_aff_free(ma2
);
5310 isl_multi_aff_free(ma1
);
5314 /* Compute the pullback of "ma1" by the function represented by "ma2".
5315 * In other words, plug in "ma2" in "ma1".
5317 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
5318 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5320 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
5321 &isl_multi_aff_pullback_multi_aff_aligned
);
5324 /* Extend the local space of "dst" to include the divs
5325 * in the local space of "src".
5327 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
5328 __isl_keep isl_aff
*src
)
5336 return isl_aff_free(dst
);
5338 ctx
= isl_aff_get_ctx(src
);
5339 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
5340 isl_die(ctx
, isl_error_invalid
,
5341 "spaces don't match", goto error
);
5343 if (src
->ls
->div
->n_row
== 0)
5346 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
5347 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
5348 if (!exp1
|| (dst
->ls
->div
->n_row
&& !exp2
))
5351 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
5352 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
5360 return isl_aff_free(dst
);
5363 /* Adjust the local spaces of the affine expressions in "maff"
5364 * such that they all have the save divs.
5366 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
5367 __isl_take isl_multi_aff
*maff
)
5375 maff
= isl_multi_aff_cow(maff
);
5379 for (i
= 1; i
< maff
->n
; ++i
)
5380 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
5381 for (i
= 1; i
< maff
->n
; ++i
) {
5382 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
5384 return isl_multi_aff_free(maff
);
5390 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
5392 aff
= isl_aff_cow(aff
);
5396 aff
->ls
= isl_local_space_lift(aff
->ls
);
5398 return isl_aff_free(aff
);
5403 /* Lift "maff" to a space with extra dimensions such that the result
5404 * has no more existentially quantified variables.
5405 * If "ls" is not NULL, then *ls is assigned the local space that lies
5406 * at the basis of the lifting applied to "maff".
5408 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
5409 __isl_give isl_local_space
**ls
)
5423 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
5424 *ls
= isl_local_space_from_space(space
);
5426 return isl_multi_aff_free(maff
);
5431 maff
= isl_multi_aff_cow(maff
);
5432 maff
= isl_multi_aff_align_divs(maff
);
5436 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
5437 space
= isl_multi_aff_get_space(maff
);
5438 space
= isl_space_lift(isl_space_domain(space
), n_div
);
5439 space
= isl_space_extend_domain_with_range(space
,
5440 isl_multi_aff_get_space(maff
));
5442 return isl_multi_aff_free(maff
);
5443 isl_space_free(maff
->space
);
5444 maff
->space
= space
;
5447 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
5449 return isl_multi_aff_free(maff
);
5452 for (i
= 0; i
< maff
->n
; ++i
) {
5453 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
5461 isl_local_space_free(*ls
);
5462 return isl_multi_aff_free(maff
);
5466 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
5468 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
5469 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
5479 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
5480 if (pos
< 0 || pos
>= n_out
)
5481 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5482 "index out of bounds", return NULL
);
5484 space
= isl_pw_multi_aff_get_space(pma
);
5485 space
= isl_space_drop_dims(space
, isl_dim_out
,
5486 pos
+ 1, n_out
- pos
- 1);
5487 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
5489 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
5490 for (i
= 0; i
< pma
->n
; ++i
) {
5492 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
5493 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
5499 /* Return an isl_pw_multi_aff with the given "set" as domain and
5500 * an unnamed zero-dimensional range.
5502 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
5503 __isl_take isl_set
*set
)
5508 space
= isl_set_get_space(set
);
5509 space
= isl_space_from_domain(space
);
5510 ma
= isl_multi_aff_zero(space
);
5511 return isl_pw_multi_aff_alloc(set
, ma
);
5514 /* Add an isl_pw_multi_aff with the given "set" as domain and
5515 * an unnamed zero-dimensional range to *user.
5517 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
5519 isl_union_pw_multi_aff
**upma
= user
;
5520 isl_pw_multi_aff
*pma
;
5522 pma
= isl_pw_multi_aff_from_domain(set
);
5523 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
5528 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
5529 * an unnamed zero-dimensional range.
5531 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
5532 __isl_take isl_union_set
*uset
)
5535 isl_union_pw_multi_aff
*upma
;
5540 space
= isl_union_set_get_space(uset
);
5541 upma
= isl_union_pw_multi_aff_empty(space
);
5543 if (isl_union_set_foreach_set(uset
,
5544 &add_pw_multi_aff_from_domain
, &upma
) < 0)
5547 isl_union_set_free(uset
);
5550 isl_union_set_free(uset
);
5551 isl_union_pw_multi_aff_free(upma
);
5555 /* Convert "pma" to an isl_map and add it to *umap.
5557 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
5559 isl_union_map
**umap
= user
;
5562 map
= isl_map_from_pw_multi_aff(pma
);
5563 *umap
= isl_union_map_add_map(*umap
, map
);
5568 /* Construct a union map mapping the domain of the union
5569 * piecewise multi-affine expression to its range, with each dimension
5570 * in the range equated to the corresponding affine expression on its cell.
5572 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
5573 __isl_take isl_union_pw_multi_aff
*upma
)
5576 isl_union_map
*umap
;
5581 space
= isl_union_pw_multi_aff_get_space(upma
);
5582 umap
= isl_union_map_empty(space
);
5584 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
5585 &map_from_pw_multi_aff
, &umap
) < 0)
5588 isl_union_pw_multi_aff_free(upma
);
5591 isl_union_pw_multi_aff_free(upma
);
5592 isl_union_map_free(umap
);
5596 /* Local data for bin_entry and the callback "fn".
5598 struct isl_union_pw_multi_aff_bin_data
{
5599 isl_union_pw_multi_aff
*upma2
;
5600 isl_union_pw_multi_aff
*res
;
5601 isl_pw_multi_aff
*pma
;
5602 int (*fn
)(void **entry
, void *user
);
5605 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
5606 * and call data->fn for each isl_pw_multi_aff in data->upma2.
5608 static int bin_entry(void **entry
, void *user
)
5610 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5611 isl_pw_multi_aff
*pma
= *entry
;
5614 if (isl_hash_table_foreach(data
->upma2
->space
->ctx
, &data
->upma2
->table
,
5615 data
->fn
, data
) < 0)
5621 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
5622 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
5623 * passed as user field) and the isl_pw_multi_aff from upma2 is available
5624 * as *entry. The callback should adjust data->res if desired.
5626 static __isl_give isl_union_pw_multi_aff
*bin_op(
5627 __isl_take isl_union_pw_multi_aff
*upma1
,
5628 __isl_take isl_union_pw_multi_aff
*upma2
,
5629 int (*fn
)(void **entry
, void *user
))
5632 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
5634 space
= isl_union_pw_multi_aff_get_space(upma2
);
5635 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
5636 space
= isl_union_pw_multi_aff_get_space(upma1
);
5637 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
5639 if (!upma1
|| !upma2
)
5643 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->space
),
5645 if (isl_hash_table_foreach(upma1
->space
->ctx
, &upma1
->table
,
5646 &bin_entry
, &data
) < 0)
5649 isl_union_pw_multi_aff_free(upma1
);
5650 isl_union_pw_multi_aff_free(upma2
);
5653 isl_union_pw_multi_aff_free(upma1
);
5654 isl_union_pw_multi_aff_free(upma2
);
5655 isl_union_pw_multi_aff_free(data
.res
);
5659 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5660 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5662 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
5663 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5667 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5668 isl_pw_multi_aff_get_space(pma2
));
5669 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5670 &isl_multi_aff_range_product
);
5673 /* Given two isl_pw_multi_affs A -> B and C -> D,
5674 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5676 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
5677 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5679 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5680 &pw_multi_aff_range_product
);
5683 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5684 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5686 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
5687 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5691 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5692 isl_pw_multi_aff_get_space(pma2
));
5693 space
= isl_space_flatten_range(space
);
5694 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5695 &isl_multi_aff_flat_range_product
);
5698 /* Given two isl_pw_multi_affs A -> B and C -> D,
5699 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5701 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
5702 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5704 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5705 &pw_multi_aff_flat_range_product
);
5708 /* If data->pma and *entry have the same domain space, then compute
5709 * their flat range product and the result to data->res.
5711 static int flat_range_product_entry(void **entry
, void *user
)
5713 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5714 isl_pw_multi_aff
*pma2
= *entry
;
5716 if (!isl_space_tuple_is_equal(data
->pma
->dim
, isl_dim_in
,
5717 pma2
->dim
, isl_dim_in
))
5720 pma2
= isl_pw_multi_aff_flat_range_product(
5721 isl_pw_multi_aff_copy(data
->pma
),
5722 isl_pw_multi_aff_copy(pma2
));
5724 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
5729 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
5730 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
5732 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
5733 __isl_take isl_union_pw_multi_aff
*upma1
,
5734 __isl_take isl_union_pw_multi_aff
*upma2
)
5736 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
5739 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5740 * The parameters are assumed to have been aligned.
5742 * The implementation essentially performs an isl_pw_*_on_shared_domain,
5743 * except that it works on two different isl_pw_* types.
5745 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
5746 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5747 __isl_take isl_pw_aff
*pa
)
5750 isl_pw_multi_aff
*res
= NULL
;
5755 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_in
,
5756 pa
->dim
, isl_dim_in
))
5757 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5758 "domains don't match", goto error
);
5759 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
5760 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5761 "index out of bounds", goto error
);
5764 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
5766 for (i
= 0; i
< pma
->n
; ++i
) {
5767 for (j
= 0; j
< pa
->n
; ++j
) {
5769 isl_multi_aff
*res_ij
;
5772 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
5773 isl_set_copy(pa
->p
[j
].set
));
5774 empty
= isl_set_plain_is_empty(common
);
5775 if (empty
< 0 || empty
) {
5776 isl_set_free(common
);
5782 res_ij
= isl_multi_aff_set_aff(
5783 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
5784 isl_aff_copy(pa
->p
[j
].aff
));
5785 res_ij
= isl_multi_aff_gist(res_ij
,
5786 isl_set_copy(common
));
5788 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5792 isl_pw_multi_aff_free(pma
);
5793 isl_pw_aff_free(pa
);
5796 isl_pw_multi_aff_free(pma
);
5797 isl_pw_aff_free(pa
);
5798 return isl_pw_multi_aff_free(res
);
5801 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5803 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
5804 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5805 __isl_take isl_pw_aff
*pa
)
5809 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
5810 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5811 if (!isl_space_has_named_params(pma
->dim
) ||
5812 !isl_space_has_named_params(pa
->dim
))
5813 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5814 "unaligned unnamed parameters", goto error
);
5815 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
5816 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
5817 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5819 isl_pw_multi_aff_free(pma
);
5820 isl_pw_aff_free(pa
);
5824 /* Do the parameters of "pa" match those of "space"?
5826 int isl_pw_aff_matching_params(__isl_keep isl_pw_aff
*pa
,
5827 __isl_keep isl_space
*space
)
5829 isl_space
*pa_space
;
5835 pa_space
= isl_pw_aff_get_space(pa
);
5837 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5839 isl_space_free(pa_space
);
5843 /* Check that the domain space of "pa" matches "space".
5845 * Return 0 on success and -1 on error.
5847 int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff
*pa
,
5848 __isl_keep isl_space
*space
)
5850 isl_space
*pa_space
;
5856 pa_space
= isl_pw_aff_get_space(pa
);
5858 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5862 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5863 "parameters don't match", goto error
);
5864 match
= isl_space_tuple_is_equal(space
, isl_dim_in
,
5865 pa_space
, isl_dim_in
);
5869 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5870 "domains don't match", goto error
);
5871 isl_space_free(pa_space
);
5874 isl_space_free(pa_space
);
5881 #include <isl_multi_templ.c>
5883 /* Scale the elements of "pma" by the corresponding elements of "mv".
5885 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_scale_multi_val(
5886 __isl_take isl_pw_multi_aff
*pma
, __isl_take isl_multi_val
*mv
)
5890 pma
= isl_pw_multi_aff_cow(pma
);
5893 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_out
,
5894 mv
->space
, isl_dim_set
))
5895 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5896 "spaces don't match", goto error
);
5897 if (!isl_space_match(pma
->dim
, isl_dim_param
,
5898 mv
->space
, isl_dim_param
)) {
5899 pma
= isl_pw_multi_aff_align_params(pma
,
5900 isl_multi_val_get_space(mv
));
5901 mv
= isl_multi_val_align_params(mv
,
5902 isl_pw_multi_aff_get_space(pma
));
5907 for (i
= 0; i
< pma
->n
; ++i
) {
5908 pma
->p
[i
].maff
= isl_multi_aff_scale_multi_val(pma
->p
[i
].maff
,
5909 isl_multi_val_copy(mv
));
5910 if (!pma
->p
[i
].maff
)
5914 isl_multi_val_free(mv
);
5917 isl_multi_val_free(mv
);
5918 isl_pw_multi_aff_free(pma
);
5922 /* Internal data structure for isl_union_pw_multi_aff_scale_multi_val.
5923 * mv contains the mv argument.
5924 * res collects the results.
5926 struct isl_union_pw_multi_aff_scale_multi_val_data
{
5928 isl_union_pw_multi_aff
*res
;
5931 /* This function is called for each entry of an isl_union_pw_multi_aff.
5932 * If the space of the entry matches that of data->mv,
5933 * then apply isl_pw_multi_aff_scale_multi_val and add the result
5936 static int union_pw_multi_aff_scale_multi_val_entry(void **entry
, void *user
)
5938 struct isl_union_pw_multi_aff_scale_multi_val_data
*data
= user
;
5939 isl_pw_multi_aff
*pma
= *entry
;
5943 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_out
,
5944 data
->mv
->space
, isl_dim_set
))
5947 pma
= isl_pw_multi_aff_copy(pma
);
5948 pma
= isl_pw_multi_aff_scale_multi_val(pma
,
5949 isl_multi_val_copy(data
->mv
));
5950 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
5957 /* Scale the elements of "upma" by the corresponding elements of "mv",
5958 * for those entries that match the space of "mv".
5960 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_scale_multi_val(
5961 __isl_take isl_union_pw_multi_aff
*upma
, __isl_take isl_multi_val
*mv
)
5963 struct isl_union_pw_multi_aff_scale_multi_val_data data
;
5965 upma
= isl_union_pw_multi_aff_align_params(upma
,
5966 isl_multi_val_get_space(mv
));
5967 mv
= isl_multi_val_align_params(mv
,
5968 isl_union_pw_multi_aff_get_space(upma
));
5973 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma
->space
),
5975 if (isl_hash_table_foreach(upma
->space
->ctx
, &upma
->table
,
5976 &union_pw_multi_aff_scale_multi_val_entry
, &data
) < 0)
5979 isl_multi_val_free(mv
);
5980 isl_union_pw_multi_aff_free(upma
);
5983 isl_multi_val_free(mv
);
5984 isl_union_pw_multi_aff_free(upma
);
5988 /* Construct and return a piecewise multi affine expression
5989 * in the given space with value zero in each of the output dimensions and
5990 * a universe domain.
5992 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_zero(__isl_take isl_space
*space
)
5994 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_zero(space
));
5997 /* Construct and return a piecewise multi affine expression
5998 * that is equal to the given piecewise affine expression.
6000 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_pw_aff(
6001 __isl_take isl_pw_aff
*pa
)
6005 isl_pw_multi_aff
*pma
;
6010 space
= isl_pw_aff_get_space(pa
);
6011 pma
= isl_pw_multi_aff_alloc_size(space
, pa
->n
);
6013 for (i
= 0; i
< pa
->n
; ++i
) {
6017 set
= isl_set_copy(pa
->p
[i
].set
);
6018 ma
= isl_multi_aff_from_aff(isl_aff_copy(pa
->p
[i
].aff
));
6019 pma
= isl_pw_multi_aff_add_piece(pma
, set
, ma
);
6022 isl_pw_aff_free(pa
);
6026 /* Construct a set or map mapping the shared (parameter) domain
6027 * of the piecewise affine expressions to the range of "mpa"
6028 * with each dimension in the range equated to the
6029 * corresponding piecewise affine expression.
6031 static __isl_give isl_map
*map_from_multi_pw_aff(
6032 __isl_take isl_multi_pw_aff
*mpa
)
6041 if (isl_space_dim(mpa
->space
, isl_dim_out
) != mpa
->n
)
6042 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6043 "invalid space", goto error
);
6045 space
= isl_multi_pw_aff_get_domain_space(mpa
);
6046 map
= isl_map_universe(isl_space_from_domain(space
));
6048 for (i
= 0; i
< mpa
->n
; ++i
) {
6052 pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6053 map_i
= map_from_pw_aff(pa
);
6055 map
= isl_map_flat_range_product(map
, map_i
);
6058 map
= isl_map_reset_space(map
, isl_multi_pw_aff_get_space(mpa
));
6060 isl_multi_pw_aff_free(mpa
);
6063 isl_multi_pw_aff_free(mpa
);
6067 /* Construct a map mapping the shared domain
6068 * of the piecewise affine expressions to the range of "mpa"
6069 * with each dimension in the range equated to the
6070 * corresponding piecewise affine expression.
6072 __isl_give isl_map
*isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6076 if (isl_space_is_set(mpa
->space
))
6077 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6078 "space of input is not a map", goto error
);
6080 return map_from_multi_pw_aff(mpa
);
6082 isl_multi_pw_aff_free(mpa
);
6086 /* Construct a set mapping the shared parameter domain
6087 * of the piecewise affine expressions to the space of "mpa"
6088 * with each dimension in the range equated to the
6089 * corresponding piecewise affine expression.
6091 __isl_give isl_set
*isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6095 if (!isl_space_is_set(mpa
->space
))
6096 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6097 "space of input is not a set", goto error
);
6099 return map_from_multi_pw_aff(mpa
);
6101 isl_multi_pw_aff_free(mpa
);
6105 /* Construct and return a piecewise multi affine expression
6106 * that is equal to the given multi piecewise affine expression
6107 * on the shared domain of the piecewise affine expressions.
6109 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_pw_aff(
6110 __isl_take isl_multi_pw_aff
*mpa
)
6115 isl_pw_multi_aff
*pma
;
6120 space
= isl_multi_pw_aff_get_space(mpa
);
6123 isl_multi_pw_aff_free(mpa
);
6124 return isl_pw_multi_aff_zero(space
);
6127 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
6128 pma
= isl_pw_multi_aff_from_pw_aff(pa
);
6130 for (i
= 1; i
< mpa
->n
; ++i
) {
6131 isl_pw_multi_aff
*pma_i
;
6133 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6134 pma_i
= isl_pw_multi_aff_from_pw_aff(pa
);
6135 pma
= isl_pw_multi_aff_range_product(pma
, pma_i
);
6138 pma
= isl_pw_multi_aff_reset_space(pma
, space
);
6140 isl_multi_pw_aff_free(mpa
);
6144 /* Construct and return a multi piecewise affine expression
6145 * that is equal to the given multi affine expression.
6147 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_multi_aff(
6148 __isl_take isl_multi_aff
*ma
)
6151 isl_multi_pw_aff
*mpa
;
6156 n
= isl_multi_aff_dim(ma
, isl_dim_out
);
6157 mpa
= isl_multi_pw_aff_alloc(isl_multi_aff_get_space(ma
));
6159 for (i
= 0; i
< n
; ++i
) {
6162 pa
= isl_pw_aff_from_aff(isl_multi_aff_get_aff(ma
, i
));
6163 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6166 isl_multi_aff_free(ma
);
6170 /* Construct and return a multi piecewise affine expression
6171 * that is equal to the given piecewise multi affine expression.
6173 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_pw_multi_aff(
6174 __isl_take isl_pw_multi_aff
*pma
)
6178 isl_multi_pw_aff
*mpa
;
6183 n
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
6184 space
= isl_pw_multi_aff_get_space(pma
);
6185 mpa
= isl_multi_pw_aff_alloc(space
);
6187 for (i
= 0; i
< n
; ++i
) {
6190 pa
= isl_pw_multi_aff_get_pw_aff(pma
, i
);
6191 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6194 isl_pw_multi_aff_free(pma
);
6198 /* Do "pa1" and "pa2" represent the same function?
6200 * We first check if they are obviously equal.
6201 * If not, we convert them to maps and check if those are equal.
6203 int isl_pw_aff_is_equal(__isl_keep isl_pw_aff
*pa1
, __isl_keep isl_pw_aff
*pa2
)
6206 isl_map
*map1
, *map2
;
6211 equal
= isl_pw_aff_plain_is_equal(pa1
, pa2
);
6212 if (equal
< 0 || equal
)
6215 map1
= map_from_pw_aff(isl_pw_aff_copy(pa1
));
6216 map2
= map_from_pw_aff(isl_pw_aff_copy(pa2
));
6217 equal
= isl_map_is_equal(map1
, map2
);
6224 /* Do "mpa1" and "mpa2" represent the same function?
6226 * Note that we cannot convert the entire isl_multi_pw_aff
6227 * to a map because the domains of the piecewise affine expressions
6228 * may not be the same.
6230 int isl_multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
6231 __isl_keep isl_multi_pw_aff
*mpa2
)
6239 if (!isl_space_match(mpa1
->space
, isl_dim_param
,
6240 mpa2
->space
, isl_dim_param
)) {
6241 if (!isl_space_has_named_params(mpa1
->space
))
6243 if (!isl_space_has_named_params(mpa2
->space
))
6245 mpa1
= isl_multi_pw_aff_copy(mpa1
);
6246 mpa2
= isl_multi_pw_aff_copy(mpa2
);
6247 mpa1
= isl_multi_pw_aff_align_params(mpa1
,
6248 isl_multi_pw_aff_get_space(mpa2
));
6249 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
6250 isl_multi_pw_aff_get_space(mpa1
));
6251 equal
= isl_multi_pw_aff_is_equal(mpa1
, mpa2
);
6252 isl_multi_pw_aff_free(mpa1
);
6253 isl_multi_pw_aff_free(mpa2
);
6257 equal
= isl_space_is_equal(mpa1
->space
, mpa2
->space
);
6258 if (equal
< 0 || !equal
)
6261 for (i
= 0; i
< mpa1
->n
; ++i
) {
6262 equal
= isl_pw_aff_is_equal(mpa1
->p
[i
], mpa2
->p
[i
]);
6263 if (equal
< 0 || !equal
)
6270 /* Coalesce the elements of "mpa".
6272 * Note that such coalescing does not change the meaning of "mpa"
6273 * so there is no need to cow. We do need to be careful not to
6274 * destroy any other copies of "mpa" in case of failure.
6276 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_coalesce(
6277 __isl_take isl_multi_pw_aff
*mpa
)
6284 for (i
= 0; i
< mpa
->n
; ++i
) {
6285 isl_pw_aff
*pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6286 pa
= isl_pw_aff_coalesce(pa
);
6288 return isl_multi_pw_aff_free(mpa
);
6289 isl_pw_aff_free(mpa
->p
[i
]);
6296 /* Compute the pullback of "mpa" by the function represented by "ma".
6297 * In other words, plug in "ma" in "mpa".
6299 * The parameters of "mpa" and "ma" are assumed to have been aligned.
6301 static __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff_aligned(
6302 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6305 isl_space
*space
= NULL
;
6307 mpa
= isl_multi_pw_aff_cow(mpa
);
6311 space
= isl_space_join(isl_multi_aff_get_space(ma
),
6312 isl_multi_pw_aff_get_space(mpa
));
6316 for (i
= 0; i
< mpa
->n
; ++i
) {
6317 mpa
->p
[i
] = isl_pw_aff_pullback_multi_aff(mpa
->p
[i
],
6318 isl_multi_aff_copy(ma
));
6323 isl_multi_aff_free(ma
);
6324 isl_space_free(mpa
->space
);
6328 isl_space_free(space
);
6329 isl_multi_pw_aff_free(mpa
);
6330 isl_multi_aff_free(ma
);
6334 /* Compute the pullback of "mpa" by the function represented by "ma".
6335 * In other words, plug in "ma" in "mpa".
6337 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff(
6338 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6342 if (isl_space_match(mpa
->space
, isl_dim_param
,
6343 ma
->space
, isl_dim_param
))
6344 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6345 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_multi_aff_get_space(ma
));
6346 ma
= isl_multi_aff_align_params(ma
, isl_multi_pw_aff_get_space(mpa
));
6347 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6349 isl_multi_pw_aff_free(mpa
);
6350 isl_multi_aff_free(ma
);
6354 /* Compute the pullback of "mpa" by the function represented by "pma".
6355 * In other words, plug in "pma" in "mpa".
6357 * The parameters of "mpa" and "mpa" are assumed to have been aligned.
6359 static __isl_give isl_multi_pw_aff
*
6360 isl_multi_pw_aff_pullback_pw_multi_aff_aligned(
6361 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6364 isl_space
*space
= NULL
;
6366 mpa
= isl_multi_pw_aff_cow(mpa
);
6370 space
= isl_space_join(isl_pw_multi_aff_get_space(pma
),
6371 isl_multi_pw_aff_get_space(mpa
));
6373 for (i
= 0; i
< mpa
->n
; ++i
) {
6374 mpa
->p
[i
] = isl_pw_aff_pullback_pw_multi_aff_aligned(mpa
->p
[i
],
6375 isl_pw_multi_aff_copy(pma
));
6380 isl_pw_multi_aff_free(pma
);
6381 isl_space_free(mpa
->space
);
6385 isl_space_free(space
);
6386 isl_multi_pw_aff_free(mpa
);
6387 isl_pw_multi_aff_free(pma
);
6391 /* Compute the pullback of "mpa" by the function represented by "pma".
6392 * In other words, plug in "pma" in "mpa".
6394 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_pw_multi_aff(
6395 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6399 if (isl_space_match(mpa
->space
, isl_dim_param
, pma
->dim
, isl_dim_param
))
6400 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6401 mpa
= isl_multi_pw_aff_align_params(mpa
,
6402 isl_pw_multi_aff_get_space(pma
));
6403 pma
= isl_pw_multi_aff_align_params(pma
,
6404 isl_multi_pw_aff_get_space(mpa
));
6405 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6407 isl_multi_pw_aff_free(mpa
);
6408 isl_pw_multi_aff_free(pma
);
6412 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6413 * with the domain of "aff". The domain of the result is the same
6415 * "mpa" and "aff" are assumed to have been aligned.
6417 * We first extract the parametric constant from "aff", defined
6418 * over the correct domain.
6419 * Then we add the appropriate combinations of the members of "mpa".
6420 * Finally, we add the integer divisions through recursive calls.
6422 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff_aligned(
6423 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6425 int i
, n_param
, n_in
, n_div
;
6431 n_param
= isl_aff_dim(aff
, isl_dim_param
);
6432 n_in
= isl_aff_dim(aff
, isl_dim_in
);
6433 n_div
= isl_aff_dim(aff
, isl_dim_div
);
6435 space
= isl_space_domain(isl_multi_pw_aff_get_space(mpa
));
6436 tmp
= isl_aff_copy(aff
);
6437 tmp
= isl_aff_drop_dims(tmp
, isl_dim_div
, 0, n_div
);
6438 tmp
= isl_aff_drop_dims(tmp
, isl_dim_in
, 0, n_in
);
6439 tmp
= isl_aff_add_dims(tmp
, isl_dim_in
,
6440 isl_space_dim(space
, isl_dim_set
));
6441 tmp
= isl_aff_reset_domain_space(tmp
, space
);
6442 pa
= isl_pw_aff_from_aff(tmp
);
6444 for (i
= 0; i
< n_in
; ++i
) {
6447 if (!isl_aff_involves_dims(aff
, isl_dim_in
, i
, 1))
6449 v
= isl_aff_get_coefficient_val(aff
, isl_dim_in
, i
);
6450 pa_i
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6451 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6452 pa
= isl_pw_aff_add(pa
, pa_i
);
6455 for (i
= 0; i
< n_div
; ++i
) {
6459 if (!isl_aff_involves_dims(aff
, isl_dim_div
, i
, 1))
6461 div
= isl_aff_get_div(aff
, i
);
6462 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6463 isl_multi_pw_aff_copy(mpa
), div
);
6464 pa_i
= isl_pw_aff_floor(pa_i
);
6465 v
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, i
);
6466 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6467 pa
= isl_pw_aff_add(pa
, pa_i
);
6470 isl_multi_pw_aff_free(mpa
);
6476 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6477 * with the domain of "aff". The domain of the result is the same
6480 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff(
6481 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6485 if (isl_space_match(aff
->ls
->dim
, isl_dim_param
,
6486 mpa
->space
, isl_dim_param
))
6487 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6489 aff
= isl_aff_align_params(aff
, isl_multi_pw_aff_get_space(mpa
));
6490 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_aff_get_space(aff
));
6492 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6495 isl_multi_pw_aff_free(mpa
);
6499 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6500 * with the domain of "pa". The domain of the result is the same
6502 * "mpa" and "pa" are assumed to have been aligned.
6504 * We consider each piece in turn. Note that the domains of the
6505 * pieces are assumed to be disjoint and they remain disjoint
6506 * after taking the preimage (over the same function).
6508 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff_aligned(
6509 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6518 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa
),
6519 isl_pw_aff_get_space(pa
));
6520 res
= isl_pw_aff_empty(space
);
6522 for (i
= 0; i
< pa
->n
; ++i
) {
6526 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6527 isl_multi_pw_aff_copy(mpa
),
6528 isl_aff_copy(pa
->p
[i
].aff
));
6529 domain
= isl_set_copy(pa
->p
[i
].set
);
6530 domain
= isl_set_preimage_multi_pw_aff(domain
,
6531 isl_multi_pw_aff_copy(mpa
));
6532 pa_i
= isl_pw_aff_intersect_domain(pa_i
, domain
);
6533 res
= isl_pw_aff_add_disjoint(res
, pa_i
);
6536 isl_pw_aff_free(pa
);
6537 isl_multi_pw_aff_free(mpa
);
6540 isl_pw_aff_free(pa
);
6541 isl_multi_pw_aff_free(mpa
);
6545 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6546 * with the domain of "pa". The domain of the result is the same
6549 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff(
6550 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6554 if (isl_space_match(pa
->dim
, isl_dim_param
, mpa
->space
, isl_dim_param
))
6555 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6557 pa
= isl_pw_aff_align_params(pa
, isl_multi_pw_aff_get_space(mpa
));
6558 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_pw_aff_get_space(pa
));
6560 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6562 isl_pw_aff_free(pa
);
6563 isl_multi_pw_aff_free(mpa
);
6567 /* Compute the pullback of "pa" by the function represented by "mpa".
6568 * In other words, plug in "mpa" in "pa".
6569 * "pa" and "mpa" are assumed to have been aligned.
6571 * The pullback is computed by applying "pa" to "mpa".
6573 static __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff_aligned(
6574 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6576 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6579 /* Compute the pullback of "pa" by the function represented by "mpa".
6580 * In other words, plug in "mpa" in "pa".
6582 * The pullback is computed by applying "pa" to "mpa".
6584 __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff(
6585 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6587 return isl_multi_pw_aff_apply_pw_aff(mpa
, pa
);
6590 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6591 * In other words, plug in "mpa2" in "mpa1".
6593 * The parameters of "mpa1" and "mpa2" are assumed to have been aligned.
6595 * We pullback each member of "mpa1" in turn.
6597 static __isl_give isl_multi_pw_aff
*
6598 isl_multi_pw_aff_pullback_multi_pw_aff_aligned(
6599 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6602 isl_space
*space
= NULL
;
6604 mpa1
= isl_multi_pw_aff_cow(mpa1
);
6608 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa2
),
6609 isl_multi_pw_aff_get_space(mpa1
));
6611 for (i
= 0; i
< mpa1
->n
; ++i
) {
6612 mpa1
->p
[i
] = isl_pw_aff_pullback_multi_pw_aff_aligned(
6613 mpa1
->p
[i
], isl_multi_pw_aff_copy(mpa2
));
6618 mpa1
= isl_multi_pw_aff_reset_space(mpa1
, space
);
6620 isl_multi_pw_aff_free(mpa2
);
6623 isl_space_free(space
);
6624 isl_multi_pw_aff_free(mpa1
);
6625 isl_multi_pw_aff_free(mpa2
);
6629 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6630 * In other words, plug in "mpa2" in "mpa1".
6632 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_pw_aff(
6633 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6635 return isl_multi_pw_aff_align_params_multi_multi_and(mpa1
, mpa2
,
6636 &isl_multi_pw_aff_pullback_multi_pw_aff_aligned
);
6639 /* Compare two isl_affs.
6641 * Return -1 if "aff1" is "smaller" than "aff2", 1 if "aff1" is "greater"
6642 * than "aff2" and 0 if they are equal.
6644 * The order is fairly arbitrary. We do consider expressions that only involve
6645 * earlier dimensions as "smaller".
6647 int isl_aff_plain_cmp(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
6660 cmp
= isl_local_space_cmp(aff1
->ls
, aff2
->ls
);
6664 last1
= isl_seq_last_non_zero(aff1
->v
->el
+ 1, aff1
->v
->size
- 1);
6665 last2
= isl_seq_last_non_zero(aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
6667 return last1
- last2
;
6669 return isl_seq_cmp(aff1
->v
->el
, aff2
->v
->el
, aff1
->v
->size
);
6672 /* Compare two isl_pw_affs.
6674 * Return -1 if "pa1" is "smaller" than "pa2", 1 if "pa1" is "greater"
6675 * than "pa2" and 0 if they are equal.
6677 * The order is fairly arbitrary. We do consider expressions that only involve
6678 * earlier dimensions as "smaller".
6680 int isl_pw_aff_plain_cmp(__isl_keep isl_pw_aff
*pa1
,
6681 __isl_keep isl_pw_aff
*pa2
)
6694 cmp
= isl_space_cmp(pa1
->dim
, pa2
->dim
);
6698 if (pa1
->n
!= pa2
->n
)
6699 return pa1
->n
- pa2
->n
;
6701 for (i
= 0; i
< pa1
->n
; ++i
) {
6702 cmp
= isl_set_plain_cmp(pa1
->p
[i
].set
, pa2
->p
[i
].set
);
6705 cmp
= isl_aff_plain_cmp(pa1
->p
[i
].aff
, pa2
->p
[i
].aff
);
6713 /* Return a piecewise affine expression that is equal to "v" on "domain".
6715 __isl_give isl_pw_aff
*isl_pw_aff_val_on_domain(__isl_take isl_set
*domain
,
6716 __isl_take isl_val
*v
)
6719 isl_local_space
*ls
;
6722 space
= isl_set_get_space(domain
);
6723 ls
= isl_local_space_from_space(space
);
6724 aff
= isl_aff_val_on_domain(ls
, v
);
6726 return isl_pw_aff_alloc(domain
, aff
);
6729 /* Return a multi affine expression that is equal to "mv" on domain
6732 __isl_give isl_multi_aff
*isl_multi_aff_multi_val_on_space(
6733 __isl_take isl_space
*space
, __isl_take isl_multi_val
*mv
)
6737 isl_local_space
*ls
;
6743 n
= isl_multi_val_dim(mv
, isl_dim_set
);
6744 space2
= isl_multi_val_get_space(mv
);
6745 space2
= isl_space_align_params(space2
, isl_space_copy(space
));
6746 space
= isl_space_align_params(space
, isl_space_copy(space2
));
6747 space
= isl_space_map_from_domain_and_range(space
, space2
);
6748 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
6749 ls
= isl_local_space_from_space(isl_space_domain(space
));
6750 for (i
= 0; i
< n
; ++i
) {
6754 v
= isl_multi_val_get_val(mv
, i
);
6755 aff
= isl_aff_val_on_domain(isl_local_space_copy(ls
), v
);
6756 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
6758 isl_local_space_free(ls
);
6760 isl_multi_val_free(mv
);
6763 isl_space_free(space
);
6764 isl_multi_val_free(mv
);
6768 /* Return a piecewise multi-affine expression
6769 * that is equal to "mv" on "domain".
6771 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_multi_val_on_domain(
6772 __isl_take isl_set
*domain
, __isl_take isl_multi_val
*mv
)
6777 space
= isl_set_get_space(domain
);
6778 ma
= isl_multi_aff_multi_val_on_space(space
, mv
);
6780 return isl_pw_multi_aff_alloc(domain
, ma
);
6783 /* Internal data structure for isl_union_pw_multi_aff_multi_val_on_domain.
6784 * mv is the value that should be attained on each domain set
6785 * res collects the results
6787 struct isl_union_pw_multi_aff_multi_val_on_domain_data
{
6789 isl_union_pw_multi_aff
*res
;
6792 /* Create an isl_pw_multi_aff equal to data->mv on "domain"
6793 * and add it to data->res.
6795 static int pw_multi_aff_multi_val_on_domain(__isl_take isl_set
*domain
,
6798 struct isl_union_pw_multi_aff_multi_val_on_domain_data
*data
= user
;
6799 isl_pw_multi_aff
*pma
;
6802 mv
= isl_multi_val_copy(data
->mv
);
6803 pma
= isl_pw_multi_aff_multi_val_on_domain(domain
, mv
);
6804 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
6806 return data
->res
? 0 : -1;
6809 /* Return a union piecewise multi-affine expression
6810 * that is equal to "mv" on "domain".
6812 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_multi_val_on_domain(
6813 __isl_take isl_union_set
*domain
, __isl_take isl_multi_val
*mv
)
6815 struct isl_union_pw_multi_aff_multi_val_on_domain_data data
;
6818 space
= isl_union_set_get_space(domain
);
6819 data
.res
= isl_union_pw_multi_aff_empty(space
);
6821 if (isl_union_set_foreach_set(domain
,
6822 &pw_multi_aff_multi_val_on_domain
, &data
) < 0)
6823 data
.res
= isl_union_pw_multi_aff_free(data
.res
);
6824 isl_union_set_free(domain
);
6825 isl_multi_val_free(mv
);