2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2013 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_config.h>
32 #include <isl_list_templ.c>
37 #include <isl_list_templ.c>
39 __isl_give isl_aff
*isl_aff_alloc_vec(__isl_take isl_local_space
*ls
,
40 __isl_take isl_vec
*v
)
47 aff
= isl_calloc_type(v
->ctx
, struct isl_aff
);
57 isl_local_space_free(ls
);
62 __isl_give isl_aff
*isl_aff_alloc(__isl_take isl_local_space
*ls
)
71 ctx
= isl_local_space_get_ctx(ls
);
72 if (!isl_local_space_divs_known(ls
))
73 isl_die(ctx
, isl_error_invalid
, "local space has unknown divs",
75 if (!isl_local_space_is_set(ls
))
76 isl_die(ctx
, isl_error_invalid
,
77 "domain of affine expression should be a set",
80 total
= isl_local_space_dim(ls
, isl_dim_all
);
81 v
= isl_vec_alloc(ctx
, 1 + 1 + total
);
82 return isl_aff_alloc_vec(ls
, v
);
84 isl_local_space_free(ls
);
88 __isl_give isl_aff
*isl_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
92 aff
= isl_aff_alloc(ls
);
96 isl_int_set_si(aff
->v
->el
[0], 1);
97 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
102 /* Return a piecewise affine expression defined on the specified domain
103 * that is equal to zero.
105 __isl_give isl_pw_aff
*isl_pw_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
107 return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
110 /* Return an affine expression that is equal to the specified dimension
113 __isl_give isl_aff
*isl_aff_var_on_domain(__isl_take isl_local_space
*ls
,
114 enum isl_dim_type type
, unsigned pos
)
122 space
= isl_local_space_get_space(ls
);
125 if (isl_space_is_map(space
))
126 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
127 "expecting (parameter) set space", goto error
);
128 if (pos
>= isl_local_space_dim(ls
, type
))
129 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
130 "position out of bounds", goto error
);
132 isl_space_free(space
);
133 aff
= isl_aff_alloc(ls
);
137 pos
+= isl_local_space_offset(aff
->ls
, type
);
139 isl_int_set_si(aff
->v
->el
[0], 1);
140 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
141 isl_int_set_si(aff
->v
->el
[1 + pos
], 1);
145 isl_local_space_free(ls
);
146 isl_space_free(space
);
150 /* Return a piecewise affine expression that is equal to
151 * the specified dimension in "ls".
153 __isl_give isl_pw_aff
*isl_pw_aff_var_on_domain(__isl_take isl_local_space
*ls
,
154 enum isl_dim_type type
, unsigned pos
)
156 return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, type
, pos
));
159 __isl_give isl_aff
*isl_aff_copy(__isl_keep isl_aff
*aff
)
168 __isl_give isl_aff
*isl_aff_dup(__isl_keep isl_aff
*aff
)
173 return isl_aff_alloc_vec(isl_local_space_copy(aff
->ls
),
174 isl_vec_copy(aff
->v
));
177 __isl_give isl_aff
*isl_aff_cow(__isl_take isl_aff
*aff
)
185 return isl_aff_dup(aff
);
188 void *isl_aff_free(__isl_take isl_aff
*aff
)
196 isl_local_space_free(aff
->ls
);
197 isl_vec_free(aff
->v
);
204 isl_ctx
*isl_aff_get_ctx(__isl_keep isl_aff
*aff
)
206 return aff
? isl_local_space_get_ctx(aff
->ls
) : NULL
;
209 /* Externally, an isl_aff has a map space, but internally, the
210 * ls field corresponds to the domain of that space.
212 int isl_aff_dim(__isl_keep isl_aff
*aff
, enum isl_dim_type type
)
216 if (type
== isl_dim_out
)
218 if (type
== isl_dim_in
)
220 return isl_local_space_dim(aff
->ls
, type
);
223 __isl_give isl_space
*isl_aff_get_domain_space(__isl_keep isl_aff
*aff
)
225 return aff
? isl_local_space_get_space(aff
->ls
) : NULL
;
228 __isl_give isl_space
*isl_aff_get_space(__isl_keep isl_aff
*aff
)
233 space
= isl_local_space_get_space(aff
->ls
);
234 space
= isl_space_from_domain(space
);
235 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
239 __isl_give isl_local_space
*isl_aff_get_domain_local_space(
240 __isl_keep isl_aff
*aff
)
242 return aff
? isl_local_space_copy(aff
->ls
) : NULL
;
245 __isl_give isl_local_space
*isl_aff_get_local_space(__isl_keep isl_aff
*aff
)
250 ls
= isl_local_space_copy(aff
->ls
);
251 ls
= isl_local_space_from_domain(ls
);
252 ls
= isl_local_space_add_dims(ls
, isl_dim_out
, 1);
256 /* Externally, an isl_aff has a map space, but internally, the
257 * ls field corresponds to the domain of that space.
259 const char *isl_aff_get_dim_name(__isl_keep isl_aff
*aff
,
260 enum isl_dim_type type
, unsigned pos
)
264 if (type
== isl_dim_out
)
266 if (type
== isl_dim_in
)
268 return isl_local_space_get_dim_name(aff
->ls
, type
, pos
);
271 __isl_give isl_aff
*isl_aff_reset_domain_space(__isl_take isl_aff
*aff
,
272 __isl_take isl_space
*dim
)
274 aff
= isl_aff_cow(aff
);
278 aff
->ls
= isl_local_space_reset_space(aff
->ls
, dim
);
280 return isl_aff_free(aff
);
289 /* Reset the space of "aff". This function is called from isl_pw_templ.c
290 * and doesn't know if the space of an element object is represented
291 * directly or through its domain. It therefore passes along both.
293 __isl_give isl_aff
*isl_aff_reset_space_and_domain(__isl_take isl_aff
*aff
,
294 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
296 isl_space_free(space
);
297 return isl_aff_reset_domain_space(aff
, domain
);
300 /* Reorder the coefficients of the affine expression based
301 * on the given reodering.
302 * The reordering r is assumed to have been extended with the local
305 static __isl_give isl_vec
*vec_reorder(__isl_take isl_vec
*vec
,
306 __isl_take isl_reordering
*r
, int n_div
)
314 res
= isl_vec_alloc(vec
->ctx
,
315 2 + isl_space_dim(r
->dim
, isl_dim_all
) + n_div
);
316 isl_seq_cpy(res
->el
, vec
->el
, 2);
317 isl_seq_clr(res
->el
+ 2, res
->size
- 2);
318 for (i
= 0; i
< r
->len
; ++i
)
319 isl_int_set(res
->el
[2 + r
->pos
[i
]], vec
->el
[2 + i
]);
321 isl_reordering_free(r
);
326 isl_reordering_free(r
);
330 /* Reorder the dimensions of the domain of "aff" according
331 * to the given reordering.
333 __isl_give isl_aff
*isl_aff_realign_domain(__isl_take isl_aff
*aff
,
334 __isl_take isl_reordering
*r
)
336 aff
= isl_aff_cow(aff
);
340 r
= isl_reordering_extend(r
, aff
->ls
->div
->n_row
);
341 aff
->v
= vec_reorder(aff
->v
, isl_reordering_copy(r
),
342 aff
->ls
->div
->n_row
);
343 aff
->ls
= isl_local_space_realign(aff
->ls
, r
);
345 if (!aff
->v
|| !aff
->ls
)
346 return isl_aff_free(aff
);
351 isl_reordering_free(r
);
355 __isl_give isl_aff
*isl_aff_align_params(__isl_take isl_aff
*aff
,
356 __isl_take isl_space
*model
)
361 if (!isl_space_match(aff
->ls
->dim
, isl_dim_param
,
362 model
, isl_dim_param
)) {
365 model
= isl_space_drop_dims(model
, isl_dim_in
,
366 0, isl_space_dim(model
, isl_dim_in
));
367 model
= isl_space_drop_dims(model
, isl_dim_out
,
368 0, isl_space_dim(model
, isl_dim_out
));
369 exp
= isl_parameter_alignment_reordering(aff
->ls
->dim
, model
);
370 exp
= isl_reordering_extend_space(exp
,
371 isl_aff_get_domain_space(aff
));
372 aff
= isl_aff_realign_domain(aff
, exp
);
375 isl_space_free(model
);
378 isl_space_free(model
);
383 int isl_aff_plain_is_zero(__isl_keep isl_aff
*aff
)
388 return isl_seq_first_non_zero(aff
->v
->el
+ 1, aff
->v
->size
- 1) < 0;
391 int isl_aff_plain_is_equal(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
398 equal
= isl_local_space_is_equal(aff1
->ls
, aff2
->ls
);
399 if (equal
< 0 || !equal
)
402 return isl_vec_is_equal(aff1
->v
, aff2
->v
);
405 int isl_aff_get_denominator(__isl_keep isl_aff
*aff
, isl_int
*v
)
409 isl_int_set(*v
, aff
->v
->el
[0]);
413 /* Return the common denominator of "aff".
415 __isl_give isl_val
*isl_aff_get_denominator_val(__isl_keep isl_aff
*aff
)
422 ctx
= isl_aff_get_ctx(aff
);
423 return isl_val_int_from_isl_int(ctx
, aff
->v
->el
[0]);
426 int isl_aff_get_constant(__isl_keep isl_aff
*aff
, isl_int
*v
)
430 isl_int_set(*v
, aff
->v
->el
[1]);
434 /* Return the constant term of "aff".
436 __isl_give isl_val
*isl_aff_get_constant_val(__isl_keep isl_aff
*aff
)
444 ctx
= isl_aff_get_ctx(aff
);
445 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1], aff
->v
->el
[0]);
446 return isl_val_normalize(v
);
449 int isl_aff_get_coefficient(__isl_keep isl_aff
*aff
,
450 enum isl_dim_type type
, int pos
, isl_int
*v
)
455 if (type
== isl_dim_out
)
456 isl_die(aff
->v
->ctx
, isl_error_invalid
,
457 "output/set dimension does not have a coefficient",
459 if (type
== isl_dim_in
)
462 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
463 isl_die(aff
->v
->ctx
, isl_error_invalid
,
464 "position out of bounds", return -1);
466 pos
+= isl_local_space_offset(aff
->ls
, type
);
467 isl_int_set(*v
, aff
->v
->el
[1 + pos
]);
472 /* Return the coefficient of the variable of type "type" at position "pos"
475 __isl_give isl_val
*isl_aff_get_coefficient_val(__isl_keep isl_aff
*aff
,
476 enum isl_dim_type type
, int pos
)
484 ctx
= isl_aff_get_ctx(aff
);
485 if (type
== isl_dim_out
)
486 isl_die(ctx
, isl_error_invalid
,
487 "output/set dimension does not have a coefficient",
489 if (type
== isl_dim_in
)
492 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
493 isl_die(ctx
, isl_error_invalid
,
494 "position out of bounds", return NULL
);
496 pos
+= isl_local_space_offset(aff
->ls
, type
);
497 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1 + pos
], aff
->v
->el
[0]);
498 return isl_val_normalize(v
);
501 __isl_give isl_aff
*isl_aff_set_denominator(__isl_take isl_aff
*aff
, isl_int v
)
503 aff
= isl_aff_cow(aff
);
507 aff
->v
= isl_vec_cow(aff
->v
);
509 return isl_aff_free(aff
);
511 isl_int_set(aff
->v
->el
[0], v
);
516 __isl_give isl_aff
*isl_aff_set_constant(__isl_take isl_aff
*aff
, isl_int v
)
518 aff
= isl_aff_cow(aff
);
522 aff
->v
= isl_vec_cow(aff
->v
);
524 return isl_aff_free(aff
);
526 isl_int_set(aff
->v
->el
[1], v
);
531 /* Replace the constant term of "aff" by "v".
533 __isl_give isl_aff
*isl_aff_set_constant_val(__isl_take isl_aff
*aff
,
534 __isl_take isl_val
*v
)
539 if (!isl_val_is_rat(v
))
540 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
541 "expecting rational value", goto error
);
543 if (isl_int_eq(aff
->v
->el
[1], v
->n
) &&
544 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
549 aff
= isl_aff_cow(aff
);
552 aff
->v
= isl_vec_cow(aff
->v
);
556 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
557 isl_int_set(aff
->v
->el
[1], v
->n
);
558 } else if (isl_int_is_one(v
->d
)) {
559 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
561 isl_seq_scale(aff
->v
->el
+ 1,
562 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
563 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
564 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
565 aff
->v
= isl_vec_normalize(aff
->v
);
578 __isl_give isl_aff
*isl_aff_add_constant(__isl_take isl_aff
*aff
, isl_int v
)
580 if (isl_int_is_zero(v
))
583 aff
= isl_aff_cow(aff
);
587 aff
->v
= isl_vec_cow(aff
->v
);
589 return isl_aff_free(aff
);
591 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
);
596 /* Add "v" to the constant term of "aff".
598 __isl_give isl_aff
*isl_aff_add_constant_val(__isl_take isl_aff
*aff
,
599 __isl_take isl_val
*v
)
604 if (isl_val_is_zero(v
)) {
609 if (!isl_val_is_rat(v
))
610 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
611 "expecting rational value", goto error
);
613 aff
= isl_aff_cow(aff
);
617 aff
->v
= isl_vec_cow(aff
->v
);
621 if (isl_int_is_one(v
->d
)) {
622 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
623 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
624 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
->n
);
625 aff
->v
= isl_vec_normalize(aff
->v
);
629 isl_seq_scale(aff
->v
->el
+ 1,
630 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
631 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
632 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
633 aff
->v
= isl_vec_normalize(aff
->v
);
646 __isl_give isl_aff
*isl_aff_add_constant_si(__isl_take isl_aff
*aff
, int v
)
651 isl_int_set_si(t
, v
);
652 aff
= isl_aff_add_constant(aff
, t
);
658 /* Add "v" to the numerator of the constant term of "aff".
660 __isl_give isl_aff
*isl_aff_add_constant_num(__isl_take isl_aff
*aff
, isl_int v
)
662 if (isl_int_is_zero(v
))
665 aff
= isl_aff_cow(aff
);
669 aff
->v
= isl_vec_cow(aff
->v
);
671 return isl_aff_free(aff
);
673 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
);
678 /* Add "v" to the numerator of the constant term of "aff".
680 __isl_give isl_aff
*isl_aff_add_constant_num_si(__isl_take isl_aff
*aff
, int v
)
688 isl_int_set_si(t
, v
);
689 aff
= isl_aff_add_constant_num(aff
, t
);
695 __isl_give isl_aff
*isl_aff_set_constant_si(__isl_take isl_aff
*aff
, int v
)
697 aff
= isl_aff_cow(aff
);
701 aff
->v
= isl_vec_cow(aff
->v
);
703 return isl_aff_free(aff
);
705 isl_int_set_si(aff
->v
->el
[1], v
);
710 __isl_give isl_aff
*isl_aff_set_coefficient(__isl_take isl_aff
*aff
,
711 enum isl_dim_type type
, int pos
, isl_int v
)
716 if (type
== isl_dim_out
)
717 isl_die(aff
->v
->ctx
, isl_error_invalid
,
718 "output/set dimension does not have a coefficient",
719 return isl_aff_free(aff
));
720 if (type
== isl_dim_in
)
723 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
724 isl_die(aff
->v
->ctx
, isl_error_invalid
,
725 "position out of bounds", return isl_aff_free(aff
));
727 aff
= isl_aff_cow(aff
);
731 aff
->v
= isl_vec_cow(aff
->v
);
733 return isl_aff_free(aff
);
735 pos
+= isl_local_space_offset(aff
->ls
, type
);
736 isl_int_set(aff
->v
->el
[1 + pos
], v
);
741 __isl_give isl_aff
*isl_aff_set_coefficient_si(__isl_take isl_aff
*aff
,
742 enum isl_dim_type type
, int pos
, int v
)
747 if (type
== isl_dim_out
)
748 isl_die(aff
->v
->ctx
, isl_error_invalid
,
749 "output/set dimension does not have a coefficient",
750 return isl_aff_free(aff
));
751 if (type
== isl_dim_in
)
754 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
755 isl_die(aff
->v
->ctx
, isl_error_invalid
,
756 "position out of bounds", return isl_aff_free(aff
));
758 aff
= isl_aff_cow(aff
);
762 aff
->v
= isl_vec_cow(aff
->v
);
764 return isl_aff_free(aff
);
766 pos
+= isl_local_space_offset(aff
->ls
, type
);
767 isl_int_set_si(aff
->v
->el
[1 + pos
], v
);
772 /* Replace the coefficient of the variable of type "type" at position "pos"
775 __isl_give isl_aff
*isl_aff_set_coefficient_val(__isl_take isl_aff
*aff
,
776 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
781 if (type
== isl_dim_out
)
782 isl_die(aff
->v
->ctx
, isl_error_invalid
,
783 "output/set dimension does not have a coefficient",
785 if (type
== isl_dim_in
)
788 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
789 isl_die(aff
->v
->ctx
, isl_error_invalid
,
790 "position out of bounds", goto error
);
792 if (!isl_val_is_rat(v
))
793 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
794 "expecting rational value", goto error
);
796 pos
+= isl_local_space_offset(aff
->ls
, type
);
797 if (isl_int_eq(aff
->v
->el
[1 + pos
], v
->n
) &&
798 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
803 aff
= isl_aff_cow(aff
);
806 aff
->v
= isl_vec_cow(aff
->v
);
810 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
811 isl_int_set(aff
->v
->el
[1 + pos
], v
->n
);
812 } else if (isl_int_is_one(v
->d
)) {
813 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
815 isl_seq_scale(aff
->v
->el
+ 1,
816 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
817 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
818 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
819 aff
->v
= isl_vec_normalize(aff
->v
);
832 __isl_give isl_aff
*isl_aff_add_coefficient(__isl_take isl_aff
*aff
,
833 enum isl_dim_type type
, int pos
, isl_int v
)
838 if (type
== isl_dim_out
)
839 isl_die(aff
->v
->ctx
, isl_error_invalid
,
840 "output/set dimension does not have a coefficient",
841 return isl_aff_free(aff
));
842 if (type
== isl_dim_in
)
845 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
846 isl_die(aff
->v
->ctx
, isl_error_invalid
,
847 "position out of bounds", return isl_aff_free(aff
));
849 aff
= isl_aff_cow(aff
);
853 aff
->v
= isl_vec_cow(aff
->v
);
855 return isl_aff_free(aff
);
857 pos
+= isl_local_space_offset(aff
->ls
, type
);
858 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
);
863 /* Add "v" to the coefficient of the variable of type "type"
864 * at position "pos" of "aff".
866 __isl_give isl_aff
*isl_aff_add_coefficient_val(__isl_take isl_aff
*aff
,
867 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
872 if (isl_val_is_zero(v
)) {
877 if (type
== isl_dim_out
)
878 isl_die(aff
->v
->ctx
, isl_error_invalid
,
879 "output/set dimension does not have a coefficient",
881 if (type
== isl_dim_in
)
884 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
885 isl_die(aff
->v
->ctx
, isl_error_invalid
,
886 "position out of bounds", goto error
);
888 if (!isl_val_is_rat(v
))
889 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
890 "expecting rational value", goto error
);
892 aff
= isl_aff_cow(aff
);
896 aff
->v
= isl_vec_cow(aff
->v
);
900 pos
+= isl_local_space_offset(aff
->ls
, type
);
901 if (isl_int_is_one(v
->d
)) {
902 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
903 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
904 isl_int_add(aff
->v
->el
[1 + pos
], aff
->v
->el
[1 + pos
], v
->n
);
905 aff
->v
= isl_vec_normalize(aff
->v
);
909 isl_seq_scale(aff
->v
->el
+ 1,
910 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
911 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
912 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
913 aff
->v
= isl_vec_normalize(aff
->v
);
926 __isl_give isl_aff
*isl_aff_add_coefficient_si(__isl_take isl_aff
*aff
,
927 enum isl_dim_type type
, int pos
, int v
)
932 isl_int_set_si(t
, v
);
933 aff
= isl_aff_add_coefficient(aff
, type
, pos
, t
);
939 __isl_give isl_aff
*isl_aff_get_div(__isl_keep isl_aff
*aff
, int pos
)
944 return isl_local_space_get_div(aff
->ls
, pos
);
947 __isl_give isl_aff
*isl_aff_neg(__isl_take isl_aff
*aff
)
949 aff
= isl_aff_cow(aff
);
952 aff
->v
= isl_vec_cow(aff
->v
);
954 return isl_aff_free(aff
);
956 isl_seq_neg(aff
->v
->el
+ 1, aff
->v
->el
+ 1, aff
->v
->size
- 1);
961 /* Remove divs from the local space that do not appear in the affine
963 * We currently only remove divs at the end.
964 * Some intermediate divs may also not appear directly in the affine
965 * expression, but we would also need to check that no other divs are
966 * defined in terms of them.
968 __isl_give isl_aff
*isl_aff_remove_unused_divs( __isl_take isl_aff
*aff
)
977 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
978 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
980 pos
= isl_seq_last_non_zero(aff
->v
->el
+ 1 + off
, n
) + 1;
984 aff
= isl_aff_cow(aff
);
988 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, isl_dim_div
, pos
, n
- pos
);
989 aff
->v
= isl_vec_drop_els(aff
->v
, 1 + off
+ pos
, n
- pos
);
990 if (!aff
->ls
|| !aff
->v
)
991 return isl_aff_free(aff
);
996 /* Given two affine expressions "p" of length p_len (including the
997 * denominator and the constant term) and "subs" of length subs_len,
998 * plug in "subs" for the variable at position "pos".
999 * The variables of "subs" and "p" are assumed to match up to subs_len,
1000 * but "p" may have additional variables.
1001 * "v" is an initialized isl_int that can be used internally.
1003 * In particular, if "p" represents the expression
1007 * with i the variable at position "pos" and "subs" represents the expression
1011 * then the result represents the expression
1016 void isl_seq_substitute(isl_int
*p
, int pos
, isl_int
*subs
,
1017 int p_len
, int subs_len
, isl_int v
)
1019 isl_int_set(v
, p
[1 + pos
]);
1020 isl_int_set_si(p
[1 + pos
], 0);
1021 isl_seq_combine(p
+ 1, subs
[0], p
+ 1, v
, subs
+ 1, subs_len
- 1);
1022 isl_seq_scale(p
+ subs_len
, p
+ subs_len
, subs
[0], p_len
- subs_len
);
1023 isl_int_mul(p
[0], p
[0], subs
[0]);
1026 /* Look for any divs in the aff->ls with a denominator equal to one
1027 * and plug them into the affine expression and any subsequent divs
1028 * that may reference the div.
1030 static __isl_give isl_aff
*plug_in_integral_divs(__isl_take isl_aff
*aff
)
1036 isl_local_space
*ls
;
1042 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1044 for (i
= 0; i
< n
; ++i
) {
1045 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][0]))
1047 ls
= isl_local_space_copy(aff
->ls
);
1048 ls
= isl_local_space_substitute_seq(ls
, isl_dim_div
, i
,
1049 aff
->ls
->div
->row
[i
], len
, i
+ 1, n
- (i
+ 1));
1050 vec
= isl_vec_copy(aff
->v
);
1051 vec
= isl_vec_cow(vec
);
1057 pos
= isl_local_space_offset(aff
->ls
, isl_dim_div
) + i
;
1058 isl_seq_substitute(vec
->el
, pos
, aff
->ls
->div
->row
[i
],
1063 isl_vec_free(aff
->v
);
1065 isl_local_space_free(aff
->ls
);
1072 isl_local_space_free(ls
);
1073 return isl_aff_free(aff
);
1076 /* Look for any divs j that appear with a unit coefficient inside
1077 * the definitions of other divs i and plug them into the definitions
1080 * In particular, an expression of the form
1082 * floor((f(..) + floor(g(..)/n))/m)
1086 * floor((n * f(..) + g(..))/(n * m))
1088 * This simplification is correct because we can move the expression
1089 * f(..) into the inner floor in the original expression to obtain
1091 * floor(floor((n * f(..) + g(..))/n)/m)
1093 * from which we can derive the simplified expression.
1095 static __isl_give isl_aff
*plug_in_unit_divs(__isl_take isl_aff
*aff
)
1103 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1104 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1105 for (i
= 1; i
< n
; ++i
) {
1106 for (j
= 0; j
< i
; ++j
) {
1107 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][1 + off
+ j
]))
1109 aff
->ls
= isl_local_space_substitute_seq(aff
->ls
,
1110 isl_dim_div
, j
, aff
->ls
->div
->row
[j
],
1111 aff
->v
->size
, i
, 1);
1113 return isl_aff_free(aff
);
1120 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
1122 * Even though this function is only called on isl_affs with a single
1123 * reference, we are careful to only change aff->v and aff->ls together.
1125 static __isl_give isl_aff
*swap_div(__isl_take isl_aff
*aff
, int a
, int b
)
1127 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1128 isl_local_space
*ls
;
1131 ls
= isl_local_space_copy(aff
->ls
);
1132 ls
= isl_local_space_swap_div(ls
, a
, b
);
1133 v
= isl_vec_copy(aff
->v
);
1138 isl_int_swap(v
->el
[1 + off
+ a
], v
->el
[1 + off
+ b
]);
1139 isl_vec_free(aff
->v
);
1141 isl_local_space_free(aff
->ls
);
1147 isl_local_space_free(ls
);
1148 return isl_aff_free(aff
);
1151 /* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
1153 * We currently do not actually remove div "b", but simply add its
1154 * coefficient to that of "a" and then zero it out.
1156 static __isl_give isl_aff
*merge_divs(__isl_take isl_aff
*aff
, int a
, int b
)
1158 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1160 if (isl_int_is_zero(aff
->v
->el
[1 + off
+ b
]))
1163 aff
->v
= isl_vec_cow(aff
->v
);
1165 return isl_aff_free(aff
);
1167 isl_int_add(aff
->v
->el
[1 + off
+ a
],
1168 aff
->v
->el
[1 + off
+ a
], aff
->v
->el
[1 + off
+ b
]);
1169 isl_int_set_si(aff
->v
->el
[1 + off
+ b
], 0);
1174 /* Sort the divs in the local space of "aff" according to
1175 * the comparison function "cmp_row" in isl_local_space.c,
1176 * combining the coefficients of identical divs.
1178 * Reordering divs does not change the semantics of "aff",
1179 * so there is no need to call isl_aff_cow.
1180 * Moreover, this function is currently only called on isl_affs
1181 * with a single reference.
1183 static __isl_give isl_aff
*sort_divs(__isl_take isl_aff
*aff
)
1191 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1192 n
= isl_aff_dim(aff
, isl_dim_div
);
1193 for (i
= 1; i
< n
; ++i
) {
1194 for (j
= i
- 1; j
>= 0; --j
) {
1195 int cmp
= isl_mat_cmp_div(aff
->ls
->div
, j
, j
+ 1);
1199 aff
= merge_divs(aff
, j
, j
+ 1);
1201 aff
= swap_div(aff
, j
, j
+ 1);
1210 /* Normalize the representation of "aff".
1212 * This function should only be called of "new" isl_affs, i.e.,
1213 * with only a single reference. We therefore do not need to
1214 * worry about affecting other instances.
1216 __isl_give isl_aff
*isl_aff_normalize(__isl_take isl_aff
*aff
)
1220 aff
->v
= isl_vec_normalize(aff
->v
);
1222 return isl_aff_free(aff
);
1223 aff
= plug_in_integral_divs(aff
);
1224 aff
= plug_in_unit_divs(aff
);
1225 aff
= sort_divs(aff
);
1226 aff
= isl_aff_remove_unused_divs(aff
);
1230 /* Given f, return floor(f).
1231 * If f is an integer expression, then just return f.
1232 * If f is a constant, then return the constant floor(f).
1233 * Otherwise, if f = g/m, write g = q m + r,
1234 * create a new div d = [r/m] and return the expression q + d.
1235 * The coefficients in r are taken to lie between -m/2 and m/2.
1237 __isl_give isl_aff
*isl_aff_floor(__isl_take isl_aff
*aff
)
1247 if (isl_int_is_one(aff
->v
->el
[0]))
1250 aff
= isl_aff_cow(aff
);
1254 aff
->v
= isl_vec_cow(aff
->v
);
1256 return isl_aff_free(aff
);
1258 if (isl_aff_is_cst(aff
)) {
1259 isl_int_fdiv_q(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1260 isl_int_set_si(aff
->v
->el
[0], 1);
1264 div
= isl_vec_copy(aff
->v
);
1265 div
= isl_vec_cow(div
);
1267 return isl_aff_free(aff
);
1269 ctx
= isl_aff_get_ctx(aff
);
1270 isl_int_fdiv_q(aff
->v
->el
[0], aff
->v
->el
[0], ctx
->two
);
1271 for (i
= 1; i
< aff
->v
->size
; ++i
) {
1272 isl_int_fdiv_r(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1273 isl_int_fdiv_q(aff
->v
->el
[i
], aff
->v
->el
[i
], div
->el
[0]);
1274 if (isl_int_gt(div
->el
[i
], aff
->v
->el
[0])) {
1275 isl_int_sub(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1276 isl_int_add_ui(aff
->v
->el
[i
], aff
->v
->el
[i
], 1);
1280 aff
->ls
= isl_local_space_add_div(aff
->ls
, div
);
1282 return isl_aff_free(aff
);
1284 size
= aff
->v
->size
;
1285 aff
->v
= isl_vec_extend(aff
->v
, size
+ 1);
1287 return isl_aff_free(aff
);
1288 isl_int_set_si(aff
->v
->el
[0], 1);
1289 isl_int_set_si(aff
->v
->el
[size
], 1);
1291 aff
= isl_aff_normalize(aff
);
1298 * aff mod m = aff - m * floor(aff/m)
1300 __isl_give isl_aff
*isl_aff_mod(__isl_take isl_aff
*aff
, isl_int m
)
1304 res
= isl_aff_copy(aff
);
1305 aff
= isl_aff_scale_down(aff
, m
);
1306 aff
= isl_aff_floor(aff
);
1307 aff
= isl_aff_scale(aff
, m
);
1308 res
= isl_aff_sub(res
, aff
);
1315 * aff mod m = aff - m * floor(aff/m)
1317 * with m an integer value.
1319 __isl_give isl_aff
*isl_aff_mod_val(__isl_take isl_aff
*aff
,
1320 __isl_take isl_val
*m
)
1327 if (!isl_val_is_int(m
))
1328 isl_die(isl_val_get_ctx(m
), isl_error_invalid
,
1329 "expecting integer modulo", goto error
);
1331 res
= isl_aff_copy(aff
);
1332 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(m
));
1333 aff
= isl_aff_floor(aff
);
1334 aff
= isl_aff_scale_val(aff
, m
);
1335 res
= isl_aff_sub(res
, aff
);
1346 * pwaff mod m = pwaff - m * floor(pwaff/m)
1348 __isl_give isl_pw_aff
*isl_pw_aff_mod(__isl_take isl_pw_aff
*pwaff
, isl_int m
)
1352 res
= isl_pw_aff_copy(pwaff
);
1353 pwaff
= isl_pw_aff_scale_down(pwaff
, m
);
1354 pwaff
= isl_pw_aff_floor(pwaff
);
1355 pwaff
= isl_pw_aff_scale(pwaff
, m
);
1356 res
= isl_pw_aff_sub(res
, pwaff
);
1363 * pa mod m = pa - m * floor(pa/m)
1365 * with m an integer value.
1367 __isl_give isl_pw_aff
*isl_pw_aff_mod_val(__isl_take isl_pw_aff
*pa
,
1368 __isl_take isl_val
*m
)
1372 if (!isl_val_is_int(m
))
1373 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
1374 "expecting integer modulo", goto error
);
1375 pa
= isl_pw_aff_mod(pa
, m
->n
);
1379 isl_pw_aff_free(pa
);
1384 /* Given f, return ceil(f).
1385 * If f is an integer expression, then just return f.
1386 * Otherwise, let f be the expression
1392 * floor((e + m - 1)/m)
1394 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
1399 if (isl_int_is_one(aff
->v
->el
[0]))
1402 aff
= isl_aff_cow(aff
);
1405 aff
->v
= isl_vec_cow(aff
->v
);
1407 return isl_aff_free(aff
);
1409 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1410 isl_int_sub_ui(aff
->v
->el
[1], aff
->v
->el
[1], 1);
1411 aff
= isl_aff_floor(aff
);
1416 /* Apply the expansion computed by isl_merge_divs.
1417 * The expansion itself is given by "exp" while the resulting
1418 * list of divs is given by "div".
1420 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
1421 __isl_take isl_mat
*div
, int *exp
)
1428 aff
= isl_aff_cow(aff
);
1432 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1433 new_n_div
= isl_mat_rows(div
);
1434 if (new_n_div
< old_n_div
)
1435 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
1436 "not an expansion", goto error
);
1438 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
1442 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
1444 for (i
= new_n_div
- 1; i
>= 0; --i
) {
1445 if (j
>= 0 && exp
[j
] == i
) {
1447 isl_int_swap(aff
->v
->el
[offset
+ i
],
1448 aff
->v
->el
[offset
+ j
]);
1451 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
1454 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
1465 /* Add two affine expressions that live in the same local space.
1467 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
1468 __isl_take isl_aff
*aff2
)
1472 aff1
= isl_aff_cow(aff1
);
1476 aff1
->v
= isl_vec_cow(aff1
->v
);
1482 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
1483 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1484 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
1485 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
1486 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
1487 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1488 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
1500 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
1501 __isl_take isl_aff
*aff2
)
1511 ctx
= isl_aff_get_ctx(aff1
);
1512 if (!isl_space_is_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
1513 isl_die(ctx
, isl_error_invalid
,
1514 "spaces don't match", goto error
);
1516 if (aff1
->ls
->div
->n_row
== 0 && aff2
->ls
->div
->n_row
== 0)
1517 return add_expanded(aff1
, aff2
);
1519 exp1
= isl_alloc_array(ctx
, int, aff1
->ls
->div
->n_row
);
1520 exp2
= isl_alloc_array(ctx
, int, aff2
->ls
->div
->n_row
);
1524 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
1525 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
1526 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
1530 return add_expanded(aff1
, aff2
);
1539 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
1540 __isl_take isl_aff
*aff2
)
1542 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
1545 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
1549 if (isl_int_is_one(f
))
1552 aff
= isl_aff_cow(aff
);
1555 aff
->v
= isl_vec_cow(aff
->v
);
1557 return isl_aff_free(aff
);
1559 if (isl_int_is_pos(f
) && isl_int_is_divisible_by(aff
->v
->el
[0], f
)) {
1560 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], f
);
1565 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
1566 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1567 isl_int_divexact(gcd
, f
, gcd
);
1568 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1574 /* Multiple "aff" by "v".
1576 __isl_give isl_aff
*isl_aff_scale_val(__isl_take isl_aff
*aff
,
1577 __isl_take isl_val
*v
)
1582 if (isl_val_is_one(v
)) {
1587 if (!isl_val_is_rat(v
))
1588 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1589 "expecting rational factor", goto error
);
1591 aff
= isl_aff_scale(aff
, v
->n
);
1592 aff
= isl_aff_scale_down(aff
, v
->d
);
1602 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
1606 if (isl_int_is_one(f
))
1609 aff
= isl_aff_cow(aff
);
1613 if (isl_int_is_zero(f
))
1614 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1615 "cannot scale down by zero", return isl_aff_free(aff
));
1617 aff
->v
= isl_vec_cow(aff
->v
);
1619 return isl_aff_free(aff
);
1622 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
1623 isl_int_gcd(gcd
, gcd
, f
);
1624 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1625 isl_int_divexact(gcd
, f
, gcd
);
1626 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1632 /* Divide "aff" by "v".
1634 __isl_give isl_aff
*isl_aff_scale_down_val(__isl_take isl_aff
*aff
,
1635 __isl_take isl_val
*v
)
1640 if (isl_val_is_one(v
)) {
1645 if (!isl_val_is_rat(v
))
1646 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1647 "expecting rational factor", goto error
);
1648 if (!isl_val_is_pos(v
))
1649 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1650 "factor needs to be positive", goto error
);
1652 aff
= isl_aff_scale(aff
, v
->d
);
1653 aff
= isl_aff_scale_down(aff
, v
->n
);
1663 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
1671 isl_int_set_ui(v
, f
);
1672 aff
= isl_aff_scale_down(aff
, v
);
1678 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
1679 enum isl_dim_type type
, unsigned pos
, const char *s
)
1681 aff
= isl_aff_cow(aff
);
1684 if (type
== isl_dim_out
)
1685 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1686 "cannot set name of output/set dimension",
1687 return isl_aff_free(aff
));
1688 if (type
== isl_dim_in
)
1690 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
1692 return isl_aff_free(aff
);
1697 __isl_give isl_aff
*isl_aff_set_dim_id(__isl_take isl_aff
*aff
,
1698 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1700 aff
= isl_aff_cow(aff
);
1702 return isl_id_free(id
);
1703 if (type
== isl_dim_out
)
1704 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1705 "cannot set name of output/set dimension",
1707 if (type
== isl_dim_in
)
1709 aff
->ls
= isl_local_space_set_dim_id(aff
->ls
, type
, pos
, id
);
1711 return isl_aff_free(aff
);
1720 /* Exploit the equalities in "eq" to simplify the affine expression
1721 * and the expressions of the integer divisions in the local space.
1722 * The integer divisions in this local space are assumed to appear
1723 * as regular dimensions in "eq".
1725 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
1726 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1734 if (eq
->n_eq
== 0) {
1735 isl_basic_set_free(eq
);
1739 aff
= isl_aff_cow(aff
);
1743 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
1744 isl_basic_set_copy(eq
));
1745 aff
->v
= isl_vec_cow(aff
->v
);
1746 if (!aff
->ls
|| !aff
->v
)
1749 total
= 1 + isl_space_dim(eq
->dim
, isl_dim_all
);
1751 for (i
= 0; i
< eq
->n_eq
; ++i
) {
1752 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
1753 if (j
< 0 || j
== 0 || j
>= total
)
1756 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
1760 isl_basic_set_free(eq
);
1761 aff
= isl_aff_normalize(aff
);
1764 isl_basic_set_free(eq
);
1769 /* Exploit the equalities in "eq" to simplify the affine expression
1770 * and the expressions of the integer divisions in the local space.
1772 static __isl_give isl_aff
*isl_aff_substitute_equalities(
1773 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1779 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1781 eq
= isl_basic_set_add_dims(eq
, isl_dim_set
, n_div
);
1782 return isl_aff_substitute_equalities_lifted(aff
, eq
);
1784 isl_basic_set_free(eq
);
1789 /* Look for equalities among the variables shared by context and aff
1790 * and the integer divisions of aff, if any.
1791 * The equalities are then used to eliminate coefficients and/or integer
1792 * divisions from aff.
1794 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
1795 __isl_take isl_set
*context
)
1797 isl_basic_set
*hull
;
1802 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1804 isl_basic_set
*bset
;
1805 isl_local_space
*ls
;
1806 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
1807 ls
= isl_aff_get_domain_local_space(aff
);
1808 bset
= isl_basic_set_from_local_space(ls
);
1809 bset
= isl_basic_set_lift(bset
);
1810 bset
= isl_basic_set_flatten(bset
);
1811 context
= isl_set_intersect(context
,
1812 isl_set_from_basic_set(bset
));
1815 hull
= isl_set_affine_hull(context
);
1816 return isl_aff_substitute_equalities_lifted(aff
, hull
);
1819 isl_set_free(context
);
1823 __isl_give isl_aff
*isl_aff_gist_params(__isl_take isl_aff
*aff
,
1824 __isl_take isl_set
*context
)
1826 isl_set
*dom_context
= isl_set_universe(isl_aff_get_domain_space(aff
));
1827 dom_context
= isl_set_intersect_params(dom_context
, context
);
1828 return isl_aff_gist(aff
, dom_context
);
1831 /* Return a basic set containing those elements in the space
1832 * of aff where it is non-negative.
1833 * If "rational" is set, then return a rational basic set.
1835 static __isl_give isl_basic_set
*aff_nonneg_basic_set(
1836 __isl_take isl_aff
*aff
, int rational
)
1838 isl_constraint
*ineq
;
1839 isl_basic_set
*bset
;
1841 ineq
= isl_inequality_from_aff(aff
);
1843 bset
= isl_basic_set_from_constraint(ineq
);
1845 bset
= isl_basic_set_set_rational(bset
);
1846 bset
= isl_basic_set_simplify(bset
);
1850 /* Return a basic set containing those elements in the space
1851 * of aff where it is non-negative.
1853 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
1855 return aff_nonneg_basic_set(aff
, 0);
1858 /* Return a basic set containing those elements in the domain space
1859 * of aff where it is negative.
1861 __isl_give isl_basic_set
*isl_aff_neg_basic_set(__isl_take isl_aff
*aff
)
1863 aff
= isl_aff_neg(aff
);
1864 aff
= isl_aff_add_constant_num_si(aff
, -1);
1865 return isl_aff_nonneg_basic_set(aff
);
1868 /* Return a basic set containing those elements in the space
1869 * of aff where it is zero.
1870 * If "rational" is set, then return a rational basic set.
1872 static __isl_give isl_basic_set
*aff_zero_basic_set(__isl_take isl_aff
*aff
,
1875 isl_constraint
*ineq
;
1876 isl_basic_set
*bset
;
1878 ineq
= isl_equality_from_aff(aff
);
1880 bset
= isl_basic_set_from_constraint(ineq
);
1882 bset
= isl_basic_set_set_rational(bset
);
1883 bset
= isl_basic_set_simplify(bset
);
1887 /* Return a basic set containing those elements in the space
1888 * of aff where it is zero.
1890 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
1892 return aff_zero_basic_set(aff
, 0);
1895 /* Return a basic set containing those elements in the shared space
1896 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1898 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
1899 __isl_take isl_aff
*aff2
)
1901 aff1
= isl_aff_sub(aff1
, aff2
);
1903 return isl_aff_nonneg_basic_set(aff1
);
1906 /* Return a basic set containing those elements in the shared space
1907 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1909 __isl_give isl_basic_set
*isl_aff_le_basic_set(__isl_take isl_aff
*aff1
,
1910 __isl_take isl_aff
*aff2
)
1912 return isl_aff_ge_basic_set(aff2
, aff1
);
1915 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
1916 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
1918 aff1
= isl_aff_add(aff1
, aff2
);
1919 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
1923 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
1931 /* Check whether the given affine expression has non-zero coefficient
1932 * for any dimension in the given range or if any of these dimensions
1933 * appear with non-zero coefficients in any of the integer divisions
1934 * involved in the affine expression.
1936 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
1937 enum isl_dim_type type
, unsigned first
, unsigned n
)
1949 ctx
= isl_aff_get_ctx(aff
);
1950 if (first
+ n
> isl_aff_dim(aff
, type
))
1951 isl_die(ctx
, isl_error_invalid
,
1952 "range out of bounds", return -1);
1954 active
= isl_local_space_get_active(aff
->ls
, aff
->v
->el
+ 2);
1958 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
1959 for (i
= 0; i
< n
; ++i
)
1960 if (active
[first
+ i
]) {
1973 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
1974 enum isl_dim_type type
, unsigned first
, unsigned n
)
1980 if (type
== isl_dim_out
)
1981 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1982 "cannot drop output/set dimension",
1983 return isl_aff_free(aff
));
1984 if (type
== isl_dim_in
)
1986 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1989 ctx
= isl_aff_get_ctx(aff
);
1990 if (first
+ n
> isl_local_space_dim(aff
->ls
, type
))
1991 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
1992 return isl_aff_free(aff
));
1994 aff
= isl_aff_cow(aff
);
1998 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
2000 return isl_aff_free(aff
);
2002 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2003 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
2005 return isl_aff_free(aff
);
2010 /* Project the domain of the affine expression onto its parameter space.
2011 * The affine expression may not involve any of the domain dimensions.
2013 __isl_give isl_aff
*isl_aff_project_domain_on_params(__isl_take isl_aff
*aff
)
2019 n
= isl_aff_dim(aff
, isl_dim_in
);
2020 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, 0, n
);
2022 return isl_aff_free(aff
);
2024 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2025 "affine expression involves some of the domain dimensions",
2026 return isl_aff_free(aff
));
2027 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, 0, n
);
2028 space
= isl_aff_get_domain_space(aff
);
2029 space
= isl_space_params(space
);
2030 aff
= isl_aff_reset_domain_space(aff
, space
);
2034 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
2035 enum isl_dim_type type
, unsigned first
, unsigned n
)
2041 if (type
== isl_dim_out
)
2042 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2043 "cannot insert output/set dimensions",
2044 return isl_aff_free(aff
));
2045 if (type
== isl_dim_in
)
2047 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
2050 ctx
= isl_aff_get_ctx(aff
);
2051 if (first
> isl_local_space_dim(aff
->ls
, type
))
2052 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
2053 return isl_aff_free(aff
));
2055 aff
= isl_aff_cow(aff
);
2059 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
2061 return isl_aff_free(aff
);
2063 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2064 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
2066 return isl_aff_free(aff
);
2071 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
2072 enum isl_dim_type type
, unsigned n
)
2076 pos
= isl_aff_dim(aff
, type
);
2078 return isl_aff_insert_dims(aff
, type
, pos
, n
);
2081 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
2082 enum isl_dim_type type
, unsigned n
)
2086 pos
= isl_pw_aff_dim(pwaff
, type
);
2088 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
2091 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
2093 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
2094 return isl_pw_aff_alloc(dom
, aff
);
2098 #define PW isl_pw_aff
2102 #define EL_IS_ZERO is_empty
2106 #define IS_ZERO is_empty
2109 #undef DEFAULT_IS_ZERO
2110 #define DEFAULT_IS_ZERO 0
2114 #define NO_MOVE_DIMS
2118 #include <isl_pw_templ.c>
2120 static __isl_give isl_set
*align_params_pw_pw_set_and(
2121 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
2122 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2123 __isl_take isl_pw_aff
*pwaff2
))
2125 if (!pwaff1
|| !pwaff2
)
2127 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
2128 pwaff2
->dim
, isl_dim_param
))
2129 return fn(pwaff1
, pwaff2
);
2130 if (!isl_space_has_named_params(pwaff1
->dim
) ||
2131 !isl_space_has_named_params(pwaff2
->dim
))
2132 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
2133 "unaligned unnamed parameters", goto error
);
2134 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
2135 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
2136 return fn(pwaff1
, pwaff2
);
2138 isl_pw_aff_free(pwaff1
);
2139 isl_pw_aff_free(pwaff2
);
2143 /* Compute a piecewise quasi-affine expression with a domain that
2144 * is the union of those of pwaff1 and pwaff2 and such that on each
2145 * cell, the quasi-affine expression is the better (according to cmp)
2146 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
2147 * is defined on a given cell, then the associated expression
2148 * is the defined one.
2150 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2151 __isl_take isl_pw_aff
*pwaff2
,
2152 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
2153 __isl_take isl_aff
*aff2
))
2160 if (!pwaff1
|| !pwaff2
)
2163 ctx
= isl_space_get_ctx(pwaff1
->dim
);
2164 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
2165 isl_die(ctx
, isl_error_invalid
,
2166 "arguments should live in same space", goto error
);
2168 if (isl_pw_aff_is_empty(pwaff1
)) {
2169 isl_pw_aff_free(pwaff1
);
2173 if (isl_pw_aff_is_empty(pwaff2
)) {
2174 isl_pw_aff_free(pwaff2
);
2178 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
2179 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
2181 for (i
= 0; i
< pwaff1
->n
; ++i
) {
2182 set
= isl_set_copy(pwaff1
->p
[i
].set
);
2183 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2184 struct isl_set
*common
;
2187 common
= isl_set_intersect(
2188 isl_set_copy(pwaff1
->p
[i
].set
),
2189 isl_set_copy(pwaff2
->p
[j
].set
));
2190 better
= isl_set_from_basic_set(cmp(
2191 isl_aff_copy(pwaff2
->p
[j
].aff
),
2192 isl_aff_copy(pwaff1
->p
[i
].aff
)));
2193 better
= isl_set_intersect(common
, better
);
2194 if (isl_set_plain_is_empty(better
)) {
2195 isl_set_free(better
);
2198 set
= isl_set_subtract(set
, isl_set_copy(better
));
2200 res
= isl_pw_aff_add_piece(res
, better
,
2201 isl_aff_copy(pwaff2
->p
[j
].aff
));
2203 res
= isl_pw_aff_add_piece(res
, set
,
2204 isl_aff_copy(pwaff1
->p
[i
].aff
));
2207 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2208 set
= isl_set_copy(pwaff2
->p
[j
].set
);
2209 for (i
= 0; i
< pwaff1
->n
; ++i
)
2210 set
= isl_set_subtract(set
,
2211 isl_set_copy(pwaff1
->p
[i
].set
));
2212 res
= isl_pw_aff_add_piece(res
, set
,
2213 isl_aff_copy(pwaff2
->p
[j
].aff
));
2216 isl_pw_aff_free(pwaff1
);
2217 isl_pw_aff_free(pwaff2
);
2221 isl_pw_aff_free(pwaff1
);
2222 isl_pw_aff_free(pwaff2
);
2226 /* Compute a piecewise quasi-affine expression with a domain that
2227 * is the union of those of pwaff1 and pwaff2 and such that on each
2228 * cell, the quasi-affine expression is the maximum of those of pwaff1
2229 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2230 * cell, then the associated expression is the defined one.
2232 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2233 __isl_take isl_pw_aff
*pwaff2
)
2235 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
2238 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2239 __isl_take isl_pw_aff
*pwaff2
)
2241 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2245 /* Compute a piecewise quasi-affine expression with a domain that
2246 * is the union of those of pwaff1 and pwaff2 and such that on each
2247 * cell, the quasi-affine expression is the minimum of those of pwaff1
2248 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2249 * cell, then the associated expression is the defined one.
2251 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2252 __isl_take isl_pw_aff
*pwaff2
)
2254 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
2257 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2258 __isl_take isl_pw_aff
*pwaff2
)
2260 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2264 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2265 __isl_take isl_pw_aff
*pwaff2
, int max
)
2268 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
2270 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
2273 /* Construct a map with as domain the domain of pwaff and
2274 * one-dimensional range corresponding to the affine expressions.
2276 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2285 dim
= isl_pw_aff_get_space(pwaff
);
2286 map
= isl_map_empty(dim
);
2288 for (i
= 0; i
< pwaff
->n
; ++i
) {
2289 isl_basic_map
*bmap
;
2292 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
2293 map_i
= isl_map_from_basic_map(bmap
);
2294 map_i
= isl_map_intersect_domain(map_i
,
2295 isl_set_copy(pwaff
->p
[i
].set
));
2296 map
= isl_map_union_disjoint(map
, map_i
);
2299 isl_pw_aff_free(pwaff
);
2304 /* Construct a map with as domain the domain of pwaff and
2305 * one-dimensional range corresponding to the affine expressions.
2307 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2311 if (isl_space_is_set(pwaff
->dim
))
2312 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2313 "space of input is not a map",
2314 return isl_pw_aff_free(pwaff
));
2315 return map_from_pw_aff(pwaff
);
2318 /* Construct a one-dimensional set with as parameter domain
2319 * the domain of pwaff and the single set dimension
2320 * corresponding to the affine expressions.
2322 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2326 if (!isl_space_is_set(pwaff
->dim
))
2327 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2328 "space of input is not a set",
2329 return isl_pw_aff_free(pwaff
));
2330 return map_from_pw_aff(pwaff
);
2333 /* Return a set containing those elements in the domain
2334 * of pwaff where it is non-negative.
2336 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
2344 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2346 for (i
= 0; i
< pwaff
->n
; ++i
) {
2347 isl_basic_set
*bset
;
2351 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2352 bset
= aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2354 set_i
= isl_set_from_basic_set(bset
);
2355 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
2356 set
= isl_set_union_disjoint(set
, set_i
);
2359 isl_pw_aff_free(pwaff
);
2364 /* Return a set containing those elements in the domain
2365 * of pwaff where it is zero (if complement is 0) or not zero
2366 * (if complement is 1).
2368 static __isl_give isl_set
*pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
,
2377 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2379 for (i
= 0; i
< pwaff
->n
; ++i
) {
2380 isl_basic_set
*bset
;
2381 isl_set
*set_i
, *zero
;
2384 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2385 bset
= aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2387 zero
= isl_set_from_basic_set(bset
);
2388 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
2390 set_i
= isl_set_subtract(set_i
, zero
);
2392 set_i
= isl_set_intersect(set_i
, zero
);
2393 set
= isl_set_union_disjoint(set
, set_i
);
2396 isl_pw_aff_free(pwaff
);
2401 /* Return a set containing those elements in the domain
2402 * of pwaff where it is zero.
2404 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
2406 return pw_aff_zero_set(pwaff
, 0);
2409 /* Return a set containing those elements in the domain
2410 * of pwaff where it is not zero.
2412 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
2414 return pw_aff_zero_set(pwaff
, 1);
2417 /* Return a set containing those elements in the shared domain
2418 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2420 * We compute the difference on the shared domain and then construct
2421 * the set of values where this difference is non-negative.
2422 * If strict is set, we first subtract 1 from the difference.
2423 * If equal is set, we only return the elements where pwaff1 and pwaff2
2426 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
2427 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
2429 isl_set
*set1
, *set2
;
2431 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
2432 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
2433 set1
= isl_set_intersect(set1
, set2
);
2434 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
2435 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
2436 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
2439 isl_space
*dim
= isl_set_get_space(set1
);
2441 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2442 aff
= isl_aff_add_constant_si(aff
, -1);
2443 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
2448 return isl_pw_aff_zero_set(pwaff1
);
2449 return isl_pw_aff_nonneg_set(pwaff1
);
2452 /* Return a set containing those elements in the shared domain
2453 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2455 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2456 __isl_take isl_pw_aff
*pwaff2
)
2458 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
2461 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2462 __isl_take isl_pw_aff
*pwaff2
)
2464 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2467 /* Return a set containing those elements in the shared domain
2468 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2470 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2471 __isl_take isl_pw_aff
*pwaff2
)
2473 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2476 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2477 __isl_take isl_pw_aff
*pwaff2
)
2479 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2482 /* Return a set containing those elements in the shared domain
2483 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2485 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2486 __isl_take isl_pw_aff
*pwaff2
)
2488 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2491 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2492 __isl_take isl_pw_aff
*pwaff2
)
2494 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2497 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2498 __isl_take isl_pw_aff
*pwaff2
)
2500 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2503 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2504 __isl_take isl_pw_aff
*pwaff2
)
2506 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2509 /* Return a set containing those elements in the shared domain
2510 * of the elements of list1 and list2 where each element in list1
2511 * has the relation specified by "fn" with each element in list2.
2513 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2514 __isl_take isl_pw_aff_list
*list2
,
2515 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2516 __isl_take isl_pw_aff
*pwaff2
))
2522 if (!list1
|| !list2
)
2525 ctx
= isl_pw_aff_list_get_ctx(list1
);
2526 if (list1
->n
< 1 || list2
->n
< 1)
2527 isl_die(ctx
, isl_error_invalid
,
2528 "list should contain at least one element", goto error
);
2530 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2531 for (i
= 0; i
< list1
->n
; ++i
)
2532 for (j
= 0; j
< list2
->n
; ++j
) {
2535 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2536 isl_pw_aff_copy(list2
->p
[j
]));
2537 set
= isl_set_intersect(set
, set_ij
);
2540 isl_pw_aff_list_free(list1
);
2541 isl_pw_aff_list_free(list2
);
2544 isl_pw_aff_list_free(list1
);
2545 isl_pw_aff_list_free(list2
);
2549 /* Return a set containing those elements in the shared domain
2550 * of the elements of list1 and list2 where each element in list1
2551 * is equal to each element in list2.
2553 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2554 __isl_take isl_pw_aff_list
*list2
)
2556 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
2559 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
2560 __isl_take isl_pw_aff_list
*list2
)
2562 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
2565 /* Return a set containing those elements in the shared domain
2566 * of the elements of list1 and list2 where each element in list1
2567 * is less than or equal to each element in list2.
2569 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
2570 __isl_take isl_pw_aff_list
*list2
)
2572 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
2575 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
2576 __isl_take isl_pw_aff_list
*list2
)
2578 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
2581 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
2582 __isl_take isl_pw_aff_list
*list2
)
2584 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
2587 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
2588 __isl_take isl_pw_aff_list
*list2
)
2590 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
2594 /* Return a set containing those elements in the shared domain
2595 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2597 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2598 __isl_take isl_pw_aff
*pwaff2
)
2600 isl_set
*set_lt
, *set_gt
;
2602 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
2603 isl_pw_aff_copy(pwaff2
));
2604 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
2605 return isl_set_union_disjoint(set_lt
, set_gt
);
2608 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2609 __isl_take isl_pw_aff
*pwaff2
)
2611 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
2614 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
2619 if (isl_int_is_one(v
))
2621 if (!isl_int_is_pos(v
))
2622 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2623 "factor needs to be positive",
2624 return isl_pw_aff_free(pwaff
));
2625 pwaff
= isl_pw_aff_cow(pwaff
);
2631 for (i
= 0; i
< pwaff
->n
; ++i
) {
2632 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
2633 if (!pwaff
->p
[i
].aff
)
2634 return isl_pw_aff_free(pwaff
);
2640 /* Divide "pa" by "f".
2642 __isl_give isl_pw_aff
*isl_pw_aff_scale_down_val(__isl_take isl_pw_aff
*pa
,
2643 __isl_take isl_val
*f
)
2650 if (isl_val_is_one(f
)) {
2655 if (!isl_val_is_rat(f
))
2656 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
2657 "expecting rational factor", goto error
);
2658 if (!isl_val_is_pos(f
))
2659 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
2660 "factor needs to be positive", goto error
);
2662 pa
= isl_pw_aff_cow(pa
);
2668 for (i
= 0; i
< pa
->n
; ++i
) {
2669 pa
->p
[i
].aff
= isl_aff_scale_down_val(pa
->p
[i
].aff
,
2678 isl_pw_aff_free(pa
);
2683 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
2687 pwaff
= isl_pw_aff_cow(pwaff
);
2693 for (i
= 0; i
< pwaff
->n
; ++i
) {
2694 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
2695 if (!pwaff
->p
[i
].aff
)
2696 return isl_pw_aff_free(pwaff
);
2702 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
2706 pwaff
= isl_pw_aff_cow(pwaff
);
2712 for (i
= 0; i
< pwaff
->n
; ++i
) {
2713 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
2714 if (!pwaff
->p
[i
].aff
)
2715 return isl_pw_aff_free(pwaff
);
2721 /* Assuming that "cond1" and "cond2" are disjoint,
2722 * return an affine expression that is equal to pwaff1 on cond1
2723 * and to pwaff2 on cond2.
2725 static __isl_give isl_pw_aff
*isl_pw_aff_select(
2726 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
2727 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
2729 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
2730 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
2732 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
2735 /* Return an affine expression that is equal to pwaff_true for elements
2736 * where "cond" is non-zero and to pwaff_false for elements where "cond"
2738 * That is, return cond ? pwaff_true : pwaff_false;
2740 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
2741 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
2743 isl_set
*cond_true
, *cond_false
;
2745 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
2746 cond_false
= isl_pw_aff_zero_set(cond
);
2747 return isl_pw_aff_select(cond_true
, pwaff_true
,
2748 cond_false
, pwaff_false
);
2751 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
2756 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
2759 /* Check whether pwaff is a piecewise constant.
2761 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
2768 for (i
= 0; i
< pwaff
->n
; ++i
) {
2769 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
2770 if (is_cst
< 0 || !is_cst
)
2777 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
2778 __isl_take isl_aff
*aff2
)
2780 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
2781 return isl_aff_mul(aff2
, aff1
);
2783 if (!isl_aff_is_cst(aff2
))
2784 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
2785 "at least one affine expression should be constant",
2788 aff1
= isl_aff_cow(aff1
);
2792 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
2793 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
2803 /* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant.
2805 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
2806 __isl_take isl_aff
*aff2
)
2811 is_cst
= isl_aff_is_cst(aff2
);
2815 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
2816 "second argument should be a constant", goto error
);
2821 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
2823 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2824 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2827 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
2828 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
2831 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2832 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2843 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2844 __isl_take isl_pw_aff
*pwaff2
)
2846 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
2849 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2850 __isl_take isl_pw_aff
*pwaff2
)
2852 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
2855 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
2856 __isl_take isl_pw_aff
*pwaff2
)
2858 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
2861 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2862 __isl_take isl_pw_aff
*pwaff2
)
2864 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
2867 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2868 __isl_take isl_pw_aff
*pwaff2
)
2870 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
2873 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2874 __isl_take isl_pw_aff
*pa2
)
2876 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
2879 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
2881 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2882 __isl_take isl_pw_aff
*pa2
)
2886 is_cst
= isl_pw_aff_is_cst(pa2
);
2890 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2891 "second argument should be a piecewise constant",
2893 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
2895 isl_pw_aff_free(pa1
);
2896 isl_pw_aff_free(pa2
);
2900 /* Compute the quotient of the integer division of "pa1" by "pa2"
2901 * with rounding towards zero.
2902 * "pa2" is assumed to be a piecewise constant.
2904 * In particular, return
2906 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
2909 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
2910 __isl_take isl_pw_aff
*pa2
)
2916 is_cst
= isl_pw_aff_is_cst(pa2
);
2920 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2921 "second argument should be a piecewise constant",
2924 pa1
= isl_pw_aff_div(pa1
, pa2
);
2926 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
2927 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
2928 c
= isl_pw_aff_ceil(pa1
);
2929 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
2931 isl_pw_aff_free(pa1
);
2932 isl_pw_aff_free(pa2
);
2936 /* Compute the remainder of the integer division of "pa1" by "pa2"
2937 * with rounding towards zero.
2938 * "pa2" is assumed to be a piecewise constant.
2940 * In particular, return
2942 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
2945 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
2946 __isl_take isl_pw_aff
*pa2
)
2951 is_cst
= isl_pw_aff_is_cst(pa2
);
2955 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2956 "second argument should be a piecewise constant",
2958 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
2959 res
= isl_pw_aff_mul(pa2
, res
);
2960 res
= isl_pw_aff_sub(pa1
, res
);
2963 isl_pw_aff_free(pa1
);
2964 isl_pw_aff_free(pa2
);
2968 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2969 __isl_take isl_pw_aff
*pwaff2
)
2974 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2975 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2976 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
2977 isl_pw_aff_copy(pwaff2
));
2978 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
2979 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
2982 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2983 __isl_take isl_pw_aff
*pwaff2
)
2985 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
2988 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2989 __isl_take isl_pw_aff
*pwaff2
)
2994 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2995 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2996 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
2997 isl_pw_aff_copy(pwaff2
));
2998 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
2999 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
3002 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3003 __isl_take isl_pw_aff
*pwaff2
)
3005 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
3008 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
3009 __isl_take isl_pw_aff_list
*list
,
3010 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
3011 __isl_take isl_pw_aff
*pwaff2
))
3020 ctx
= isl_pw_aff_list_get_ctx(list
);
3022 isl_die(ctx
, isl_error_invalid
,
3023 "list should contain at least one element",
3024 return isl_pw_aff_list_free(list
));
3026 res
= isl_pw_aff_copy(list
->p
[0]);
3027 for (i
= 1; i
< list
->n
; ++i
)
3028 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
3030 isl_pw_aff_list_free(list
);
3034 /* Return an isl_pw_aff that maps each element in the intersection of the
3035 * domains of the elements of list to the minimal corresponding affine
3038 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
3040 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
3043 /* Return an isl_pw_aff that maps each element in the intersection of the
3044 * domains of the elements of list to the maximal corresponding affine
3047 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
3049 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
3052 /* Mark the domains of "pwaff" as rational.
3054 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__isl_take isl_pw_aff
*pwaff
)
3058 pwaff
= isl_pw_aff_cow(pwaff
);
3064 for (i
= 0; i
< pwaff
->n
; ++i
) {
3065 pwaff
->p
[i
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
3066 if (!pwaff
->p
[i
].set
)
3067 return isl_pw_aff_free(pwaff
);
3073 /* Mark the domains of the elements of "list" as rational.
3075 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
3076 __isl_take isl_pw_aff_list
*list
)
3086 for (i
= 0; i
< n
; ++i
) {
3089 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
3090 pa
= isl_pw_aff_set_rational(pa
);
3091 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
3097 /* Check that the domain space of "aff" matches "space".
3099 * Return 0 on success and -1 on error.
3101 int isl_aff_check_match_domain_space(__isl_keep isl_aff
*aff
,
3102 __isl_keep isl_space
*space
)
3104 isl_space
*aff_space
;
3110 aff_space
= isl_aff_get_domain_space(aff
);
3112 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3116 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3117 "parameters don't match", goto error
);
3118 match
= isl_space_tuple_match(space
, isl_dim_in
,
3119 aff_space
, isl_dim_set
);
3123 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3124 "domains don't match", goto error
);
3125 isl_space_free(aff_space
);
3128 isl_space_free(aff_space
);
3135 #include <isl_multi_templ.c>
3137 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
3140 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
3141 __isl_take isl_multi_aff
*ma
)
3143 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
3144 return isl_pw_multi_aff_alloc(dom
, ma
);
3147 /* Create a piecewise multi-affine expression in the given space that maps each
3148 * input dimension to the corresponding output dimension.
3150 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
3151 __isl_take isl_space
*space
)
3153 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
3156 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*maff1
,
3157 __isl_take isl_multi_aff
*maff2
)
3159 return isl_multi_aff_bin_op(maff1
, maff2
, &isl_aff_add
);
3162 /* Subtract "ma2" from "ma1" and return the result.
3164 __isl_give isl_multi_aff
*isl_multi_aff_sub(__isl_take isl_multi_aff
*ma1
,
3165 __isl_take isl_multi_aff
*ma2
)
3167 return isl_multi_aff_bin_op(ma1
, ma2
, &isl_aff_sub
);
3170 /* Given two multi-affine expressions A -> B and C -> D,
3171 * construct a multi-affine expression [A -> C] -> [B -> D].
3173 __isl_give isl_multi_aff
*isl_multi_aff_product(
3174 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
3180 int in1
, in2
, out1
, out2
;
3182 in1
= isl_multi_aff_dim(ma1
, isl_dim_in
);
3183 in2
= isl_multi_aff_dim(ma2
, isl_dim_in
);
3184 out1
= isl_multi_aff_dim(ma1
, isl_dim_out
);
3185 out2
= isl_multi_aff_dim(ma2
, isl_dim_out
);
3186 space
= isl_space_product(isl_multi_aff_get_space(ma1
),
3187 isl_multi_aff_get_space(ma2
));
3188 res
= isl_multi_aff_alloc(isl_space_copy(space
));
3189 space
= isl_space_domain(space
);
3191 for (i
= 0; i
< out1
; ++i
) {
3192 aff
= isl_multi_aff_get_aff(ma1
, i
);
3193 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, in1
, in2
);
3194 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
3195 res
= isl_multi_aff_set_aff(res
, i
, aff
);
3198 for (i
= 0; i
< out2
; ++i
) {
3199 aff
= isl_multi_aff_get_aff(ma2
, i
);
3200 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, 0, in1
);
3201 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
3202 res
= isl_multi_aff_set_aff(res
, out1
+ i
, aff
);
3205 isl_space_free(space
);
3206 isl_multi_aff_free(ma1
);
3207 isl_multi_aff_free(ma2
);
3211 /* Exploit the equalities in "eq" to simplify the affine expressions.
3213 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
3214 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
3218 maff
= isl_multi_aff_cow(maff
);
3222 for (i
= 0; i
< maff
->n
; ++i
) {
3223 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
3224 isl_basic_set_copy(eq
));
3229 isl_basic_set_free(eq
);
3232 isl_basic_set_free(eq
);
3233 isl_multi_aff_free(maff
);
3237 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
3242 maff
= isl_multi_aff_cow(maff
);
3246 for (i
= 0; i
< maff
->n
; ++i
) {
3247 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
3249 return isl_multi_aff_free(maff
);
3255 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
3256 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3258 maff1
= isl_multi_aff_add(maff1
, maff2
);
3259 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
3263 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
3271 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff
*maff1
,
3272 __isl_keep isl_multi_aff
*maff2
)
3277 if (!maff1
|| !maff2
)
3279 if (maff1
->n
!= maff2
->n
)
3281 equal
= isl_space_is_equal(maff1
->space
, maff2
->space
);
3282 if (equal
< 0 || !equal
)
3285 for (i
= 0; i
< maff1
->n
; ++i
) {
3286 equal
= isl_aff_plain_is_equal(maff1
->p
[i
], maff2
->p
[i
]);
3287 if (equal
< 0 || !equal
)
3294 /* Return the set of domain elements where "ma1" is lexicographically
3295 * smaller than or equal to "ma2".
3297 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
3298 __isl_take isl_multi_aff
*ma2
)
3300 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
3303 /* Return the set of domain elements where "ma1" is lexicographically
3304 * greater than or equal to "ma2".
3306 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
3307 __isl_take isl_multi_aff
*ma2
)
3310 isl_map
*map1
, *map2
;
3313 map1
= isl_map_from_multi_aff(ma1
);
3314 map2
= isl_map_from_multi_aff(ma2
);
3315 map
= isl_map_range_product(map1
, map2
);
3316 space
= isl_space_range(isl_map_get_space(map
));
3317 space
= isl_space_domain(isl_space_unwrap(space
));
3318 ge
= isl_map_lex_ge(space
);
3319 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
3321 return isl_map_domain(map
);
3325 #define PW isl_pw_multi_aff
3327 #define EL isl_multi_aff
3329 #define EL_IS_ZERO is_empty
3333 #define IS_ZERO is_empty
3336 #undef DEFAULT_IS_ZERO
3337 #define DEFAULT_IS_ZERO 0
3342 #define NO_INVOLVES_DIMS
3343 #define NO_MOVE_DIMS
3344 #define NO_INSERT_DIMS
3348 #include <isl_pw_templ.c>
3351 #define UNION isl_union_pw_multi_aff
3353 #define PART isl_pw_multi_aff
3355 #define PARTS pw_multi_aff
3356 #define ALIGN_DOMAIN
3360 #include <isl_union_templ.c>
3362 /* Given a function "cmp" that returns the set of elements where
3363 * "ma1" is "better" than "ma2", return the intersection of this
3364 * set with "dom1" and "dom2".
3366 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
3367 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
3368 __isl_keep isl_multi_aff
*ma2
,
3369 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3370 __isl_take isl_multi_aff
*ma2
))
3376 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
3377 is_empty
= isl_set_plain_is_empty(common
);
3378 if (is_empty
>= 0 && is_empty
)
3381 return isl_set_free(common
);
3382 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
3383 better
= isl_set_intersect(common
, better
);
3388 /* Given a function "cmp" that returns the set of elements where
3389 * "ma1" is "better" than "ma2", return a piecewise multi affine
3390 * expression defined on the union of the definition domains
3391 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
3392 * "pma2" on each cell. If only one of the two input functions
3393 * is defined on a given cell, then it is considered the best.
3395 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
3396 __isl_take isl_pw_multi_aff
*pma1
,
3397 __isl_take isl_pw_multi_aff
*pma2
,
3398 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3399 __isl_take isl_multi_aff
*ma2
))
3402 isl_pw_multi_aff
*res
= NULL
;
3404 isl_set
*set
= NULL
;
3409 ctx
= isl_space_get_ctx(pma1
->dim
);
3410 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
3411 isl_die(ctx
, isl_error_invalid
,
3412 "arguments should live in the same space", goto error
);
3414 if (isl_pw_multi_aff_is_empty(pma1
)) {
3415 isl_pw_multi_aff_free(pma1
);
3419 if (isl_pw_multi_aff_is_empty(pma2
)) {
3420 isl_pw_multi_aff_free(pma2
);
3424 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
3425 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
3427 for (i
= 0; i
< pma1
->n
; ++i
) {
3428 set
= isl_set_copy(pma1
->p
[i
].set
);
3429 for (j
= 0; j
< pma2
->n
; ++j
) {
3433 better
= shared_and_better(pma2
->p
[j
].set
,
3434 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
3435 pma1
->p
[i
].maff
, cmp
);
3436 is_empty
= isl_set_plain_is_empty(better
);
3437 if (is_empty
< 0 || is_empty
) {
3438 isl_set_free(better
);
3443 set
= isl_set_subtract(set
, isl_set_copy(better
));
3445 res
= isl_pw_multi_aff_add_piece(res
, better
,
3446 isl_multi_aff_copy(pma2
->p
[j
].maff
));
3448 res
= isl_pw_multi_aff_add_piece(res
, set
,
3449 isl_multi_aff_copy(pma1
->p
[i
].maff
));
3452 for (j
= 0; j
< pma2
->n
; ++j
) {
3453 set
= isl_set_copy(pma2
->p
[j
].set
);
3454 for (i
= 0; i
< pma1
->n
; ++i
)
3455 set
= isl_set_subtract(set
,
3456 isl_set_copy(pma1
->p
[i
].set
));
3457 res
= isl_pw_multi_aff_add_piece(res
, set
,
3458 isl_multi_aff_copy(pma2
->p
[j
].maff
));
3461 isl_pw_multi_aff_free(pma1
);
3462 isl_pw_multi_aff_free(pma2
);
3466 isl_pw_multi_aff_free(pma1
);
3467 isl_pw_multi_aff_free(pma2
);
3469 return isl_pw_multi_aff_free(res
);
3472 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
3473 __isl_take isl_pw_multi_aff
*pma1
,
3474 __isl_take isl_pw_multi_aff
*pma2
)
3476 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
3479 /* Given two piecewise multi affine expressions, return a piecewise
3480 * multi-affine expression defined on the union of the definition domains
3481 * of the inputs that is equal to the lexicographic maximum of the two
3482 * inputs on each cell. If only one of the two inputs is defined on
3483 * a given cell, then it is considered to be the maximum.
3485 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
3486 __isl_take isl_pw_multi_aff
*pma1
,
3487 __isl_take isl_pw_multi_aff
*pma2
)
3489 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3490 &pw_multi_aff_union_lexmax
);
3493 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
3494 __isl_take isl_pw_multi_aff
*pma1
,
3495 __isl_take isl_pw_multi_aff
*pma2
)
3497 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
3500 /* Given two piecewise multi affine expressions, return a piecewise
3501 * multi-affine expression defined on the union of the definition domains
3502 * of the inputs that is equal to the lexicographic minimum of the two
3503 * inputs on each cell. If only one of the two inputs is defined on
3504 * a given cell, then it is considered to be the minimum.
3506 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
3507 __isl_take isl_pw_multi_aff
*pma1
,
3508 __isl_take isl_pw_multi_aff
*pma2
)
3510 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3511 &pw_multi_aff_union_lexmin
);
3514 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
3515 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3517 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
3518 &isl_multi_aff_add
);
3521 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
3522 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3524 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3528 static __isl_give isl_pw_multi_aff
*pw_multi_aff_sub(
3529 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3531 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
3532 &isl_multi_aff_sub
);
3535 /* Subtract "pma2" from "pma1" and return the result.
3537 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_sub(
3538 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3540 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3544 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
3545 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3547 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
3550 /* Given two piecewise multi-affine expressions A -> B and C -> D,
3551 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
3553 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
3554 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3558 isl_pw_multi_aff
*res
;
3563 n
= pma1
->n
* pma2
->n
;
3564 space
= isl_space_product(isl_space_copy(pma1
->dim
),
3565 isl_space_copy(pma2
->dim
));
3566 res
= isl_pw_multi_aff_alloc_size(space
, n
);
3568 for (i
= 0; i
< pma1
->n
; ++i
) {
3569 for (j
= 0; j
< pma2
->n
; ++j
) {
3573 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
3574 isl_set_copy(pma2
->p
[j
].set
));
3575 ma
= isl_multi_aff_product(
3576 isl_multi_aff_copy(pma1
->p
[i
].maff
),
3577 isl_multi_aff_copy(pma2
->p
[i
].maff
));
3578 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
3582 isl_pw_multi_aff_free(pma1
);
3583 isl_pw_multi_aff_free(pma2
);
3586 isl_pw_multi_aff_free(pma1
);
3587 isl_pw_multi_aff_free(pma2
);
3591 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
3592 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3594 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3595 &pw_multi_aff_product
);
3598 /* Construct a map mapping the domain of the piecewise multi-affine expression
3599 * to its range, with each dimension in the range equated to the
3600 * corresponding affine expression on its cell.
3602 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3610 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
3612 for (i
= 0; i
< pma
->n
; ++i
) {
3613 isl_multi_aff
*maff
;
3614 isl_basic_map
*bmap
;
3617 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
3618 bmap
= isl_basic_map_from_multi_aff(maff
);
3619 map_i
= isl_map_from_basic_map(bmap
);
3620 map_i
= isl_map_intersect_domain(map_i
,
3621 isl_set_copy(pma
->p
[i
].set
));
3622 map
= isl_map_union_disjoint(map
, map_i
);
3625 isl_pw_multi_aff_free(pma
);
3629 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3634 if (!isl_space_is_set(pma
->dim
))
3635 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
3636 "isl_pw_multi_aff cannot be converted into an isl_set",
3637 return isl_pw_multi_aff_free(pma
));
3639 return isl_map_from_pw_multi_aff(pma
);
3642 /* Given a basic map with a single output dimension that is defined
3643 * in terms of the parameters and input dimensions using an equality,
3644 * extract an isl_aff that expresses the output dimension in terms
3645 * of the parameters and input dimensions.
3647 * Since some applications expect the result of isl_pw_multi_aff_from_map
3648 * to only contain integer affine expressions, we compute the floor
3649 * of the expression before returning.
3651 * This function shares some similarities with
3652 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
3654 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
3655 __isl_take isl_basic_map
*bmap
)
3660 isl_local_space
*ls
;
3665 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
3666 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3667 "basic map should have a single output dimension",
3669 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
3670 total
= isl_basic_map_total_dim(bmap
);
3671 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
3672 if (isl_int_is_zero(bmap
->eq
[i
][offset
]))
3674 if (isl_seq_first_non_zero(bmap
->eq
[i
] + offset
+ 1,
3675 1 + total
- (offset
+ 1)) != -1)
3679 if (i
>= bmap
->n_eq
)
3680 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3681 "unable to find suitable equality", goto error
);
3682 ls
= isl_basic_map_get_local_space(bmap
);
3683 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
3686 if (isl_int_is_neg(bmap
->eq
[i
][offset
]))
3687 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3689 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3690 isl_seq_clr(aff
->v
->el
+ 1 + offset
, aff
->v
->size
- (1 + offset
));
3691 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[i
][offset
]);
3692 isl_basic_map_free(bmap
);
3694 aff
= isl_aff_remove_unused_divs(aff
);
3695 aff
= isl_aff_floor(aff
);
3698 isl_basic_map_free(bmap
);
3702 /* Given a basic map where each output dimension is defined
3703 * in terms of the parameters and input dimensions using an equality,
3704 * extract an isl_multi_aff that expresses the output dimensions in terms
3705 * of the parameters and input dimensions.
3707 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
3708 __isl_take isl_basic_map
*bmap
)
3717 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
3718 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
3720 for (i
= 0; i
< n_out
; ++i
) {
3721 isl_basic_map
*bmap_i
;
3724 bmap_i
= isl_basic_map_copy(bmap
);
3725 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
3726 i
+ 1, n_out
- (1 + i
));
3727 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
3728 aff
= extract_isl_aff_from_basic_map(bmap_i
);
3729 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3732 isl_basic_map_free(bmap
);
3737 /* Create an isl_pw_multi_aff that is equivalent to
3738 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
3739 * The given basic map is such that each output dimension is defined
3740 * in terms of the parameters and input dimensions using an equality.
3742 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
3743 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
3747 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
3748 return isl_pw_multi_aff_alloc(domain
, ma
);
3751 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3752 * This obviously only works if the input "map" is single-valued.
3753 * If so, we compute the lexicographic minimum of the image in the form
3754 * of an isl_pw_multi_aff. Since the image is unique, it is equal
3755 * to its lexicographic minimum.
3756 * If the input is not single-valued, we produce an error.
3758 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
3759 __isl_take isl_map
*map
)
3763 isl_pw_multi_aff
*pma
;
3765 sv
= isl_map_is_single_valued(map
);
3769 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
3770 "map is not single-valued", goto error
);
3771 map
= isl_map_make_disjoint(map
);
3775 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
3777 for (i
= 0; i
< map
->n
; ++i
) {
3778 isl_pw_multi_aff
*pma_i
;
3779 isl_basic_map
*bmap
;
3780 bmap
= isl_basic_map_copy(map
->p
[i
]);
3781 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
3782 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
3792 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3793 * taking into account that the output dimension at position "d"
3794 * can be represented as
3796 * x = floor((e(...) + c1) / m)
3798 * given that constraint "i" is of the form
3800 * e(...) + c1 - m x >= 0
3803 * Let "map" be of the form
3807 * We construct a mapping
3809 * A -> [A -> x = floor(...)]
3811 * apply that to the map, obtaining
3813 * [A -> x = floor(...)] -> B
3815 * and equate dimension "d" to x.
3816 * We then compute a isl_pw_multi_aff representation of the resulting map
3817 * and plug in the mapping above.
3819 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
3820 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
3824 isl_local_space
*ls
;
3832 isl_pw_multi_aff
*pma
;
3835 is_set
= isl_map_is_set(map
);
3837 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3838 ctx
= isl_map_get_ctx(map
);
3839 space
= isl_space_domain(isl_map_get_space(map
));
3840 n_in
= isl_space_dim(space
, isl_dim_set
);
3841 n
= isl_space_dim(space
, isl_dim_all
);
3843 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
3845 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
3846 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
3848 isl_basic_map_free(hull
);
3850 ls
= isl_local_space_from_space(isl_space_copy(space
));
3851 aff
= isl_aff_alloc_vec(ls
, v
);
3852 aff
= isl_aff_floor(aff
);
3854 isl_space_free(space
);
3855 ma
= isl_multi_aff_from_aff(aff
);
3857 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
3858 ma
= isl_multi_aff_range_product(ma
,
3859 isl_multi_aff_from_aff(aff
));
3862 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
3863 map
= isl_map_apply_domain(map
, insert
);
3864 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
3865 pma
= isl_pw_multi_aff_from_map(map
);
3866 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
3871 /* Is constraint "c" of the form
3873 * e(...) + c1 - m x >= 0
3877 * -e(...) + c2 + m x >= 0
3879 * where m > 1 and e only depends on parameters and input dimemnsions?
3881 * "offset" is the offset of the output dimensions
3882 * "pos" is the position of output dimension x.
3884 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
3886 if (isl_int_is_zero(c
[offset
+ d
]))
3888 if (isl_int_is_one(c
[offset
+ d
]))
3890 if (isl_int_is_negone(c
[offset
+ d
]))
3892 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
3894 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
3895 total
- (offset
+ d
+ 1)) != -1)
3900 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3902 * As a special case, we first check if there is any pair of constraints,
3903 * shared by all the basic maps in "map" that force a given dimension
3904 * to be equal to the floor of some affine combination of the input dimensions.
3906 * In particular, if we can find two constraints
3908 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
3912 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
3914 * where m > 1 and e only depends on parameters and input dimemnsions,
3917 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
3919 * then we know that we can take
3921 * x = floor((e(...) + c1) / m)
3923 * without having to perform any computation.
3925 * Note that we know that
3929 * If c1 + c2 were 0, then we would have detected an equality during
3930 * simplification. If c1 + c2 were negative, then we would have detected
3933 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
3934 __isl_take isl_map
*map
)
3940 isl_basic_map
*hull
;
3942 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
3947 dim
= isl_map_dim(map
, isl_dim_out
);
3948 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3949 total
= 1 + isl_basic_map_total_dim(hull
);
3951 for (d
= 0; d
< dim
; ++d
) {
3952 for (i
= 0; i
< n
; ++i
) {
3953 if (!is_potential_div_constraint(hull
->ineq
[i
],
3956 for (j
= i
+ 1; j
< n
; ++j
) {
3957 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
3958 hull
->ineq
[j
] + 1, total
- 1))
3960 isl_int_add(sum
, hull
->ineq
[i
][0],
3962 if (isl_int_abs_lt(sum
,
3963 hull
->ineq
[i
][offset
+ d
]))
3970 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
3972 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
3976 isl_basic_map_free(hull
);
3977 return pw_multi_aff_from_map_base(map
);
3980 isl_basic_map_free(hull
);
3984 /* Given an affine expression
3986 * [A -> B] -> f(A,B)
3988 * construct an isl_multi_aff
3992 * such that dimension "d" in B' is set to "aff" and the remaining
3993 * dimensions are set equal to the corresponding dimensions in B.
3994 * "n_in" is the dimension of the space A.
3995 * "n_out" is the dimension of the space B.
3997 * If "is_set" is set, then the affine expression is of the form
4001 * and we construct an isl_multi_aff
4005 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
4006 unsigned n_in
, unsigned n_out
, int is_set
)
4010 isl_space
*space
, *space2
;
4011 isl_local_space
*ls
;
4013 space
= isl_aff_get_domain_space(aff
);
4014 ls
= isl_local_space_from_space(isl_space_copy(space
));
4015 space2
= isl_space_copy(space
);
4017 space2
= isl_space_range(isl_space_unwrap(space2
));
4018 space
= isl_space_map_from_domain_and_range(space
, space2
);
4019 ma
= isl_multi_aff_alloc(space
);
4020 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
4022 for (i
= 0; i
< n_out
; ++i
) {
4025 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
4026 isl_dim_set
, n_in
+ i
);
4027 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4030 isl_local_space_free(ls
);
4035 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4036 * taking into account that the dimension at position "d" can be written as
4038 * x = m a + f(..) (1)
4040 * where m is equal to "gcd".
4041 * "i" is the index of the equality in "hull" that defines f(..).
4042 * In particular, the equality is of the form
4044 * f(..) - x + m g(existentials) = 0
4048 * -f(..) + x + m g(existentials) = 0
4050 * We basically plug (1) into "map", resulting in a map with "a"
4051 * in the range instead of "x". The corresponding isl_pw_multi_aff
4052 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
4054 * Specifically, given the input map
4058 * We first wrap it into a set
4062 * and define (1) on top of the corresponding space, resulting in "aff".
4063 * We use this to create an isl_multi_aff that maps the output position "d"
4064 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
4065 * We plug this into the wrapped map, unwrap the result and compute the
4066 * corresponding isl_pw_multi_aff.
4067 * The result is an expression
4075 * so that we can plug that into "aff", after extending the latter to
4081 * If "map" is actually a set, then there is no "A" space, meaning
4082 * that we do not need to perform any wrapping, and that the result
4083 * of the recursive call is of the form
4087 * which is plugged into a mapping of the form
4091 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
4092 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
4097 isl_local_space
*ls
;
4100 isl_pw_multi_aff
*pma
, *id
;
4106 is_set
= isl_map_is_set(map
);
4108 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
4109 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4110 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4115 set
= isl_map_wrap(map
);
4116 space
= isl_space_map_from_set(isl_set_get_space(set
));
4117 ma
= isl_multi_aff_identity(space
);
4118 ls
= isl_local_space_from_space(isl_set_get_space(set
));
4119 aff
= isl_aff_alloc(ls
);
4121 isl_int_set_si(aff
->v
->el
[0], 1);
4122 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
4123 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
4126 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
4128 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
4130 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
4131 set
= isl_set_preimage_multi_aff(set
, ma
);
4133 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
4138 map
= isl_set_unwrap(set
);
4139 pma
= isl_pw_multi_aff_from_map(set
);
4142 space
= isl_pw_multi_aff_get_domain_space(pma
);
4143 space
= isl_space_map_from_set(space
);
4144 id
= isl_pw_multi_aff_identity(space
);
4145 pma
= isl_pw_multi_aff_range_product(id
, pma
);
4147 id
= isl_pw_multi_aff_from_multi_aff(ma
);
4148 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
4150 isl_basic_map_free(hull
);
4154 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4156 * As a special case, we first check if all output dimensions are uniquely
4157 * defined in terms of the parameters and input dimensions over the entire
4158 * domain. If so, we extract the desired isl_pw_multi_aff directly
4159 * from the affine hull of "map" and its domain.
4161 * Otherwise, we check if any of the output dimensions is "strided".
4162 * That is, we check if can be written as
4166 * with m greater than 1, a some combination of existentiall quantified
4167 * variables and f and expression in the parameters and input dimensions.
4168 * If so, we remove the stride in pw_multi_aff_from_map_stride.
4170 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
4173 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
4177 isl_basic_map
*hull
;
4187 hull
= isl_map_affine_hull(isl_map_copy(map
));
4188 sv
= isl_basic_map_plain_is_single_valued(hull
);
4190 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
4192 hull
= isl_basic_map_free(hull
);
4196 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
4197 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
4200 isl_basic_map_free(hull
);
4201 return pw_multi_aff_from_map_check_div(map
);
4206 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4207 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4209 for (i
= 0; i
< n_out
; ++i
) {
4210 for (j
= 0; j
< hull
->n_eq
; ++j
) {
4211 isl_int
*eq
= hull
->eq
[j
];
4212 isl_pw_multi_aff
*res
;
4214 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
4215 !isl_int_is_negone(eq
[o_out
+ i
]))
4217 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
4219 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
4220 n_out
- (i
+ 1)) != -1)
4222 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
4223 if (isl_int_is_zero(gcd
))
4225 if (isl_int_is_one(gcd
))
4228 res
= pw_multi_aff_from_map_stride(map
, hull
,
4236 isl_basic_map_free(hull
);
4237 return pw_multi_aff_from_map_check_div(map
);
4243 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
4245 return isl_pw_multi_aff_from_map(set
);
4248 /* Convert "map" into an isl_pw_multi_aff (if possible) and
4251 static int pw_multi_aff_from_map(__isl_take isl_map
*map
, void *user
)
4253 isl_union_pw_multi_aff
**upma
= user
;
4254 isl_pw_multi_aff
*pma
;
4256 pma
= isl_pw_multi_aff_from_map(map
);
4257 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4259 return *upma
? 0 : -1;
4262 /* Try and create an isl_union_pw_multi_aff that is equivalent
4263 * to the given isl_union_map.
4264 * The isl_union_map is required to be single-valued in each space.
4265 * Otherwise, an error is produced.
4267 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_map(
4268 __isl_take isl_union_map
*umap
)
4271 isl_union_pw_multi_aff
*upma
;
4273 space
= isl_union_map_get_space(umap
);
4274 upma
= isl_union_pw_multi_aff_empty(space
);
4275 if (isl_union_map_foreach_map(umap
, &pw_multi_aff_from_map
, &upma
) < 0)
4276 upma
= isl_union_pw_multi_aff_free(upma
);
4277 isl_union_map_free(umap
);
4282 /* Try and create an isl_union_pw_multi_aff that is equivalent
4283 * to the given isl_union_set.
4284 * The isl_union_set is required to be a singleton in each space.
4285 * Otherwise, an error is produced.
4287 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_set(
4288 __isl_take isl_union_set
*uset
)
4290 return isl_union_pw_multi_aff_from_union_map(uset
);
4293 /* Return the piecewise affine expression "set ? 1 : 0".
4295 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
4298 isl_space
*space
= isl_set_get_space(set
);
4299 isl_local_space
*ls
= isl_local_space_from_space(space
);
4300 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
4301 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
4303 one
= isl_aff_add_constant_si(one
, 1);
4304 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
4305 set
= isl_set_complement(set
);
4306 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
4311 /* Plug in "subs" for dimension "type", "pos" of "aff".
4313 * Let i be the dimension to replace and let "subs" be of the form
4317 * and "aff" of the form
4323 * (a f + d g')/(m d)
4325 * where g' is the result of plugging in "subs" in each of the integer
4328 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
4329 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
4334 aff
= isl_aff_cow(aff
);
4336 return isl_aff_free(aff
);
4338 ctx
= isl_aff_get_ctx(aff
);
4339 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
4340 isl_die(ctx
, isl_error_invalid
,
4341 "spaces don't match", return isl_aff_free(aff
));
4342 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
4343 isl_die(ctx
, isl_error_unsupported
,
4344 "cannot handle divs yet", return isl_aff_free(aff
));
4346 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
4348 return isl_aff_free(aff
);
4350 aff
->v
= isl_vec_cow(aff
->v
);
4352 return isl_aff_free(aff
);
4354 pos
+= isl_local_space_offset(aff
->ls
, type
);
4357 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
4358 aff
->v
->size
, subs
->v
->size
, v
);
4364 /* Plug in "subs" for dimension "type", "pos" in each of the affine
4365 * expressions in "maff".
4367 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
4368 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
4369 __isl_keep isl_aff
*subs
)
4373 maff
= isl_multi_aff_cow(maff
);
4375 return isl_multi_aff_free(maff
);
4377 if (type
== isl_dim_in
)
4380 for (i
= 0; i
< maff
->n
; ++i
) {
4381 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
4383 return isl_multi_aff_free(maff
);
4389 /* Plug in "subs" for dimension "type", "pos" of "pma".
4391 * pma is of the form
4395 * while subs is of the form
4397 * v' = B_j(v) -> S_j
4399 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
4400 * has a contribution in the result, in particular
4402 * C_ij(S_j) -> M_i(S_j)
4404 * Note that plugging in S_j in C_ij may also result in an empty set
4405 * and this contribution should simply be discarded.
4407 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
4408 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
4409 __isl_keep isl_pw_aff
*subs
)
4412 isl_pw_multi_aff
*res
;
4415 return isl_pw_multi_aff_free(pma
);
4417 n
= pma
->n
* subs
->n
;
4418 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
4420 for (i
= 0; i
< pma
->n
; ++i
) {
4421 for (j
= 0; j
< subs
->n
; ++j
) {
4423 isl_multi_aff
*res_ij
;
4426 common
= isl_set_intersect(
4427 isl_set_copy(pma
->p
[i
].set
),
4428 isl_set_copy(subs
->p
[j
].set
));
4429 common
= isl_set_substitute(common
,
4430 type
, pos
, subs
->p
[j
].aff
);
4431 empty
= isl_set_plain_is_empty(common
);
4432 if (empty
< 0 || empty
) {
4433 isl_set_free(common
);
4439 res_ij
= isl_multi_aff_substitute(
4440 isl_multi_aff_copy(pma
->p
[i
].maff
),
4441 type
, pos
, subs
->p
[j
].aff
);
4443 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
4447 isl_pw_multi_aff_free(pma
);
4450 isl_pw_multi_aff_free(pma
);
4451 isl_pw_multi_aff_free(res
);
4455 /* Compute the preimage of a range of dimensions in the affine expression "src"
4456 * under "ma" and put the result in "dst". The number of dimensions in "src"
4457 * that precede the range is given by "n_before". The number of dimensions
4458 * in the range is given by the number of output dimensions of "ma".
4459 * The number of dimensions that follow the range is given by "n_after".
4460 * If "has_denom" is set (to one),
4461 * then "src" and "dst" have an extra initial denominator.
4462 * "n_div_ma" is the number of existentials in "ma"
4463 * "n_div_bset" is the number of existentials in "src"
4464 * The resulting "dst" (which is assumed to have been allocated by
4465 * the caller) contains coefficients for both sets of existentials,
4466 * first those in "ma" and then those in "src".
4467 * f, c1, c2 and g are temporary objects that have been initialized
4470 * Let src represent the expression
4472 * (a(p) + f_u u + b v + f_w w + c(divs))/d
4474 * and let ma represent the expressions
4476 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
4478 * We start out with the following expression for dst:
4480 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d
4482 * with the multiplication factor f initially equal to 1
4483 * and f \sum_i b_i v_i kept separately.
4484 * For each x_i that we substitute, we multiply the numerator
4485 * (and denominator) of dst by c_1 = m_i and add the numerator
4486 * of the x_i expression multiplied by c_2 = f b_i,
4487 * after removing the common factors of c_1 and c_2.
4488 * The multiplication factor f also needs to be multiplied by c_1
4489 * for the next x_j, j > i.
4491 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
4492 __isl_keep isl_multi_aff
*ma
, int n_before
, int n_after
,
4493 int n_div_ma
, int n_div_bmap
,
4494 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
4497 int n_param
, n_in
, n_out
;
4500 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
4501 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
4502 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
4504 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
+ n_before
);
4505 o_dst
= o_src
= has_denom
+ 1 + n_param
+ n_before
;
4506 isl_seq_clr(dst
+ o_dst
, n_in
);
4509 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_after
);
4512 isl_seq_clr(dst
+ o_dst
, n_div_ma
);
4514 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_div_bmap
);
4516 isl_int_set_si(f
, 1);
4518 for (i
= 0; i
< n_out
; ++i
) {
4519 int offset
= has_denom
+ 1 + n_param
+ n_before
+ i
;
4521 if (isl_int_is_zero(src
[offset
]))
4523 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
4524 isl_int_mul(c2
, f
, src
[offset
]);
4525 isl_int_gcd(g
, c1
, c2
);
4526 isl_int_divexact(c1
, c1
, g
);
4527 isl_int_divexact(c2
, c2
, g
);
4529 isl_int_mul(f
, f
, c1
);
4532 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
4533 c2
, ma
->p
[i
]->v
->el
+ o_src
, 1 + n_param
);
4534 o_dst
+= 1 + n_param
;
4535 o_src
+= 1 + n_param
;
4536 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_before
);
4538 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
4539 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_in
);
4542 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_after
);
4544 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
4545 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_div_ma
);
4548 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_div_bmap
);
4550 isl_int_mul(dst
[0], dst
[0], c1
);
4554 /* Compute the pullback of "aff" by the function represented by "ma".
4555 * In other words, plug in "ma" in "aff". The result is an affine expression
4556 * defined over the domain space of "ma".
4558 * If "aff" is represented by
4560 * (a(p) + b x + c(divs))/d
4562 * and ma is represented by
4564 * x = D(p) + F(y) + G(divs')
4566 * then the result is
4568 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
4570 * The divs in the local space of the input are similarly adjusted
4571 * through a call to isl_local_space_preimage_multi_aff.
4573 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
4574 __isl_take isl_multi_aff
*ma
)
4576 isl_aff
*res
= NULL
;
4577 isl_local_space
*ls
;
4578 int n_div_aff
, n_div_ma
;
4579 isl_int f
, c1
, c2
, g
;
4581 ma
= isl_multi_aff_align_divs(ma
);
4585 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
4586 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
4588 ls
= isl_aff_get_domain_local_space(aff
);
4589 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
4590 res
= isl_aff_alloc(ls
);
4599 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, 0, 0, n_div_ma
, n_div_aff
,
4608 isl_multi_aff_free(ma
);
4609 res
= isl_aff_normalize(res
);
4613 isl_multi_aff_free(ma
);
4618 /* Compute the pullback of "ma1" by the function represented by "ma2".
4619 * In other words, plug in "ma2" in "ma1".
4621 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
4622 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
4625 isl_space
*space
= NULL
;
4627 ma2
= isl_multi_aff_align_divs(ma2
);
4628 ma1
= isl_multi_aff_cow(ma1
);
4632 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
4633 isl_multi_aff_get_space(ma1
));
4635 for (i
= 0; i
< ma1
->n
; ++i
) {
4636 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
4637 isl_multi_aff_copy(ma2
));
4642 ma1
= isl_multi_aff_reset_space(ma1
, space
);
4643 isl_multi_aff_free(ma2
);
4646 isl_space_free(space
);
4647 isl_multi_aff_free(ma2
);
4648 isl_multi_aff_free(ma1
);
4652 /* Extend the local space of "dst" to include the divs
4653 * in the local space of "src".
4655 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
4656 __isl_keep isl_aff
*src
)
4664 return isl_aff_free(dst
);
4666 ctx
= isl_aff_get_ctx(src
);
4667 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
4668 isl_die(ctx
, isl_error_invalid
,
4669 "spaces don't match", goto error
);
4671 if (src
->ls
->div
->n_row
== 0)
4674 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
4675 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
4679 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
4680 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
4688 return isl_aff_free(dst
);
4691 /* Adjust the local spaces of the affine expressions in "maff"
4692 * such that they all have the save divs.
4694 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
4695 __isl_take isl_multi_aff
*maff
)
4703 maff
= isl_multi_aff_cow(maff
);
4707 for (i
= 1; i
< maff
->n
; ++i
)
4708 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
4709 for (i
= 1; i
< maff
->n
; ++i
) {
4710 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
4712 return isl_multi_aff_free(maff
);
4718 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
4720 aff
= isl_aff_cow(aff
);
4724 aff
->ls
= isl_local_space_lift(aff
->ls
);
4726 return isl_aff_free(aff
);
4731 /* Lift "maff" to a space with extra dimensions such that the result
4732 * has no more existentially quantified variables.
4733 * If "ls" is not NULL, then *ls is assigned the local space that lies
4734 * at the basis of the lifting applied to "maff".
4736 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
4737 __isl_give isl_local_space
**ls
)
4751 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
4752 *ls
= isl_local_space_from_space(space
);
4754 return isl_multi_aff_free(maff
);
4759 maff
= isl_multi_aff_cow(maff
);
4760 maff
= isl_multi_aff_align_divs(maff
);
4764 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
4765 space
= isl_multi_aff_get_space(maff
);
4766 space
= isl_space_lift(isl_space_domain(space
), n_div
);
4767 space
= isl_space_extend_domain_with_range(space
,
4768 isl_multi_aff_get_space(maff
));
4770 return isl_multi_aff_free(maff
);
4771 isl_space_free(maff
->space
);
4772 maff
->space
= space
;
4775 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
4777 return isl_multi_aff_free(maff
);
4780 for (i
= 0; i
< maff
->n
; ++i
) {
4781 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
4789 isl_local_space_free(*ls
);
4790 return isl_multi_aff_free(maff
);
4794 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
4796 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
4797 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
4807 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
4808 if (pos
< 0 || pos
>= n_out
)
4809 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4810 "index out of bounds", return NULL
);
4812 space
= isl_pw_multi_aff_get_space(pma
);
4813 space
= isl_space_drop_dims(space
, isl_dim_out
,
4814 pos
+ 1, n_out
- pos
- 1);
4815 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
4817 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
4818 for (i
= 0; i
< pma
->n
; ++i
) {
4820 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
4821 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
4827 /* Return an isl_pw_multi_aff with the given "set" as domain and
4828 * an unnamed zero-dimensional range.
4830 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
4831 __isl_take isl_set
*set
)
4836 space
= isl_set_get_space(set
);
4837 space
= isl_space_from_domain(space
);
4838 ma
= isl_multi_aff_zero(space
);
4839 return isl_pw_multi_aff_alloc(set
, ma
);
4842 /* Add an isl_pw_multi_aff with the given "set" as domain and
4843 * an unnamed zero-dimensional range to *user.
4845 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
4847 isl_union_pw_multi_aff
**upma
= user
;
4848 isl_pw_multi_aff
*pma
;
4850 pma
= isl_pw_multi_aff_from_domain(set
);
4851 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4856 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
4857 * an unnamed zero-dimensional range.
4859 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
4860 __isl_take isl_union_set
*uset
)
4863 isl_union_pw_multi_aff
*upma
;
4868 space
= isl_union_set_get_space(uset
);
4869 upma
= isl_union_pw_multi_aff_empty(space
);
4871 if (isl_union_set_foreach_set(uset
,
4872 &add_pw_multi_aff_from_domain
, &upma
) < 0)
4875 isl_union_set_free(uset
);
4878 isl_union_set_free(uset
);
4879 isl_union_pw_multi_aff_free(upma
);
4883 /* Convert "pma" to an isl_map and add it to *umap.
4885 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
4887 isl_union_map
**umap
= user
;
4890 map
= isl_map_from_pw_multi_aff(pma
);
4891 *umap
= isl_union_map_add_map(*umap
, map
);
4896 /* Construct a union map mapping the domain of the union
4897 * piecewise multi-affine expression to its range, with each dimension
4898 * in the range equated to the corresponding affine expression on its cell.
4900 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
4901 __isl_take isl_union_pw_multi_aff
*upma
)
4904 isl_union_map
*umap
;
4909 space
= isl_union_pw_multi_aff_get_space(upma
);
4910 umap
= isl_union_map_empty(space
);
4912 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4913 &map_from_pw_multi_aff
, &umap
) < 0)
4916 isl_union_pw_multi_aff_free(upma
);
4919 isl_union_pw_multi_aff_free(upma
);
4920 isl_union_map_free(umap
);
4924 /* Local data for bin_entry and the callback "fn".
4926 struct isl_union_pw_multi_aff_bin_data
{
4927 isl_union_pw_multi_aff
*upma2
;
4928 isl_union_pw_multi_aff
*res
;
4929 isl_pw_multi_aff
*pma
;
4930 int (*fn
)(void **entry
, void *user
);
4933 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
4934 * and call data->fn for each isl_pw_multi_aff in data->upma2.
4936 static int bin_entry(void **entry
, void *user
)
4938 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4939 isl_pw_multi_aff
*pma
= *entry
;
4942 if (isl_hash_table_foreach(data
->upma2
->dim
->ctx
, &data
->upma2
->table
,
4943 data
->fn
, data
) < 0)
4949 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
4950 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
4951 * passed as user field) and the isl_pw_multi_aff from upma2 is available
4952 * as *entry. The callback should adjust data->res if desired.
4954 static __isl_give isl_union_pw_multi_aff
*bin_op(
4955 __isl_take isl_union_pw_multi_aff
*upma1
,
4956 __isl_take isl_union_pw_multi_aff
*upma2
,
4957 int (*fn
)(void **entry
, void *user
))
4960 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
4962 space
= isl_union_pw_multi_aff_get_space(upma2
);
4963 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
4964 space
= isl_union_pw_multi_aff_get_space(upma1
);
4965 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
4967 if (!upma1
|| !upma2
)
4971 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->dim
),
4973 if (isl_hash_table_foreach(upma1
->dim
->ctx
, &upma1
->table
,
4974 &bin_entry
, &data
) < 0)
4977 isl_union_pw_multi_aff_free(upma1
);
4978 isl_union_pw_multi_aff_free(upma2
);
4981 isl_union_pw_multi_aff_free(upma1
);
4982 isl_union_pw_multi_aff_free(upma2
);
4983 isl_union_pw_multi_aff_free(data
.res
);
4987 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4988 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4990 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
4991 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4995 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4996 isl_pw_multi_aff_get_space(pma2
));
4997 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4998 &isl_multi_aff_range_product
);
5001 /* Given two isl_pw_multi_affs A -> B and C -> D,
5002 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5004 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
5005 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5007 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5008 &pw_multi_aff_range_product
);
5011 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5012 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5014 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
5015 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5019 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5020 isl_pw_multi_aff_get_space(pma2
));
5021 space
= isl_space_flatten_range(space
);
5022 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5023 &isl_multi_aff_flat_range_product
);
5026 /* Given two isl_pw_multi_affs A -> B and C -> D,
5027 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5029 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
5030 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5032 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5033 &pw_multi_aff_flat_range_product
);
5036 /* If data->pma and *entry have the same domain space, then compute
5037 * their flat range product and the result to data->res.
5039 static int flat_range_product_entry(void **entry
, void *user
)
5041 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5042 isl_pw_multi_aff
*pma2
= *entry
;
5044 if (!isl_space_tuple_match(data
->pma
->dim
, isl_dim_in
,
5045 pma2
->dim
, isl_dim_in
))
5048 pma2
= isl_pw_multi_aff_flat_range_product(
5049 isl_pw_multi_aff_copy(data
->pma
),
5050 isl_pw_multi_aff_copy(pma2
));
5052 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
5057 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
5058 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
5060 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
5061 __isl_take isl_union_pw_multi_aff
*upma1
,
5062 __isl_take isl_union_pw_multi_aff
*upma2
)
5064 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
5067 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5068 * The parameters are assumed to have been aligned.
5070 * The implementation essentially performs an isl_pw_*_on_shared_domain,
5071 * except that it works on two different isl_pw_* types.
5073 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
5074 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5075 __isl_take isl_pw_aff
*pa
)
5078 isl_pw_multi_aff
*res
= NULL
;
5083 if (!isl_space_tuple_match(pma
->dim
, isl_dim_in
, pa
->dim
, isl_dim_in
))
5084 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5085 "domains don't match", goto error
);
5086 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
5087 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5088 "index out of bounds", goto error
);
5091 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
5093 for (i
= 0; i
< pma
->n
; ++i
) {
5094 for (j
= 0; j
< pa
->n
; ++j
) {
5096 isl_multi_aff
*res_ij
;
5099 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
5100 isl_set_copy(pa
->p
[j
].set
));
5101 empty
= isl_set_plain_is_empty(common
);
5102 if (empty
< 0 || empty
) {
5103 isl_set_free(common
);
5109 res_ij
= isl_multi_aff_set_aff(
5110 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
5111 isl_aff_copy(pa
->p
[j
].aff
));
5112 res_ij
= isl_multi_aff_gist(res_ij
,
5113 isl_set_copy(common
));
5115 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5119 isl_pw_multi_aff_free(pma
);
5120 isl_pw_aff_free(pa
);
5123 isl_pw_multi_aff_free(pma
);
5124 isl_pw_aff_free(pa
);
5125 return isl_pw_multi_aff_free(res
);
5128 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5130 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
5131 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5132 __isl_take isl_pw_aff
*pa
)
5136 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
5137 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5138 if (!isl_space_has_named_params(pma
->dim
) ||
5139 !isl_space_has_named_params(pa
->dim
))
5140 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5141 "unaligned unnamed parameters", goto error
);
5142 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
5143 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
5144 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5146 isl_pw_multi_aff_free(pma
);
5147 isl_pw_aff_free(pa
);
5151 /* Check that the domain space of "pa" matches "space".
5153 * Return 0 on success and -1 on error.
5155 int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff
*pa
,
5156 __isl_keep isl_space
*space
)
5158 isl_space
*pa_space
;
5164 pa_space
= isl_pw_aff_get_space(pa
);
5166 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5170 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5171 "parameters don't match", goto error
);
5172 match
= isl_space_tuple_match(space
, isl_dim_in
, pa_space
, isl_dim_in
);
5176 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5177 "domains don't match", goto error
);
5178 isl_space_free(pa_space
);
5181 isl_space_free(pa_space
);
5188 #include <isl_multi_templ.c>
5190 /* Scale the elements of "pma" by the corresponding elements of "mv".
5192 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_scale_multi_val(
5193 __isl_take isl_pw_multi_aff
*pma
, __isl_take isl_multi_val
*mv
)
5197 pma
= isl_pw_multi_aff_cow(pma
);
5200 if (!isl_space_tuple_match(pma
->dim
, isl_dim_out
,
5201 mv
->space
, isl_dim_set
))
5202 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5203 "spaces don't match", goto error
);
5204 if (!isl_space_match(pma
->dim
, isl_dim_param
,
5205 mv
->space
, isl_dim_param
)) {
5206 pma
= isl_pw_multi_aff_align_params(pma
,
5207 isl_multi_val_get_space(mv
));
5208 mv
= isl_multi_val_align_params(mv
,
5209 isl_pw_multi_aff_get_space(pma
));
5214 for (i
= 0; i
< pma
->n
; ++i
) {
5215 pma
->p
[i
].maff
= isl_multi_aff_scale_multi_val(pma
->p
[i
].maff
,
5216 isl_multi_val_copy(mv
));
5217 if (!pma
->p
[i
].maff
)
5221 isl_multi_val_free(mv
);
5224 isl_multi_val_free(mv
);
5225 isl_pw_multi_aff_free(pma
);
5229 /* Internal data structure for isl_union_pw_multi_aff_scale_multi_val.
5230 * mv contains the mv argument.
5231 * res collects the results.
5233 struct isl_union_pw_multi_aff_scale_multi_val_data
{
5235 isl_union_pw_multi_aff
*res
;
5238 /* This function is called for each entry of an isl_union_pw_multi_aff.
5239 * If the space of the entry matches that of data->mv,
5240 * then apply isl_pw_multi_aff_scale_multi_val and add the result
5243 static int union_pw_multi_aff_scale_multi_val_entry(void **entry
, void *user
)
5245 struct isl_union_pw_multi_aff_scale_multi_val_data
*data
= user
;
5246 isl_pw_multi_aff
*pma
= *entry
;
5250 if (!isl_space_tuple_match(pma
->dim
, isl_dim_out
,
5251 data
->mv
->space
, isl_dim_set
))
5254 pma
= isl_pw_multi_aff_copy(pma
);
5255 pma
= isl_pw_multi_aff_scale_multi_val(pma
,
5256 isl_multi_val_copy(data
->mv
));
5257 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
5264 /* Scale the elements of "upma" by the corresponding elements of "mv",
5265 * for those entries that match the space of "mv".
5267 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_scale_multi_val(
5268 __isl_take isl_union_pw_multi_aff
*upma
, __isl_take isl_multi_val
*mv
)
5270 struct isl_union_pw_multi_aff_scale_multi_val_data data
;
5272 upma
= isl_union_pw_multi_aff_align_params(upma
,
5273 isl_multi_val_get_space(mv
));
5274 mv
= isl_multi_val_align_params(mv
,
5275 isl_union_pw_multi_aff_get_space(upma
));
5280 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma
->dim
),
5282 if (isl_hash_table_foreach(upma
->dim
->ctx
, &upma
->table
,
5283 &union_pw_multi_aff_scale_multi_val_entry
, &data
) < 0)
5286 isl_multi_val_free(mv
);
5287 isl_union_pw_multi_aff_free(upma
);
5290 isl_multi_val_free(mv
);
5291 isl_union_pw_multi_aff_free(upma
);