2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2014 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 #include <isl_ctx_private.h>
16 #include <isl_map_private.h>
17 #include <isl_union_map_private.h>
18 #include <isl_aff_private.h>
19 #include <isl_space_private.h>
20 #include <isl_local_space_private.h>
21 #include <isl_vec_private.h>
22 #include <isl_mat_private.h>
23 #include <isl/constraint.h>
26 #include <isl_val_private.h>
27 #include <isl/deprecated/aff_int.h>
28 #include <isl_config.h>
33 #include <isl_list_templ.c>
38 #include <isl_list_templ.c>
40 __isl_give isl_aff
*isl_aff_alloc_vec(__isl_take isl_local_space
*ls
,
41 __isl_take isl_vec
*v
)
48 aff
= isl_calloc_type(v
->ctx
, struct isl_aff
);
58 isl_local_space_free(ls
);
63 __isl_give isl_aff
*isl_aff_alloc(__isl_take isl_local_space
*ls
)
72 ctx
= isl_local_space_get_ctx(ls
);
73 if (!isl_local_space_divs_known(ls
))
74 isl_die(ctx
, isl_error_invalid
, "local space has unknown divs",
76 if (!isl_local_space_is_set(ls
))
77 isl_die(ctx
, isl_error_invalid
,
78 "domain of affine expression should be a set",
81 total
= isl_local_space_dim(ls
, isl_dim_all
);
82 v
= isl_vec_alloc(ctx
, 1 + 1 + total
);
83 return isl_aff_alloc_vec(ls
, v
);
85 isl_local_space_free(ls
);
89 __isl_give isl_aff
*isl_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
93 aff
= isl_aff_alloc(ls
);
97 isl_int_set_si(aff
->v
->el
[0], 1);
98 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
103 /* Return a piecewise affine expression defined on the specified domain
104 * that is equal to zero.
106 __isl_give isl_pw_aff
*isl_pw_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
108 return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
111 /* Return an affine expression defined on the specified domain
112 * that represents NaN.
114 __isl_give isl_aff
*isl_aff_nan_on_domain(__isl_take isl_local_space
*ls
)
118 aff
= isl_aff_alloc(ls
);
122 isl_seq_clr(aff
->v
->el
, aff
->v
->size
);
127 /* Return a piecewise affine expression defined on the specified domain
128 * that represents NaN.
130 __isl_give isl_pw_aff
*isl_pw_aff_nan_on_domain(__isl_take isl_local_space
*ls
)
132 return isl_pw_aff_from_aff(isl_aff_nan_on_domain(ls
));
135 /* Return an affine expression that is equal to "val" on
136 * domain local space "ls".
138 __isl_give isl_aff
*isl_aff_val_on_domain(__isl_take isl_local_space
*ls
,
139 __isl_take isl_val
*val
)
145 if (!isl_val_is_rat(val
))
146 isl_die(isl_val_get_ctx(val
), isl_error_invalid
,
147 "expecting rational value", goto error
);
149 aff
= isl_aff_alloc(isl_local_space_copy(ls
));
153 isl_seq_clr(aff
->v
->el
+ 2, aff
->v
->size
- 2);
154 isl_int_set(aff
->v
->el
[1], val
->n
);
155 isl_int_set(aff
->v
->el
[0], val
->d
);
157 isl_local_space_free(ls
);
161 isl_local_space_free(ls
);
166 /* Return an affine expression that is equal to the specified dimension
169 __isl_give isl_aff
*isl_aff_var_on_domain(__isl_take isl_local_space
*ls
,
170 enum isl_dim_type type
, unsigned pos
)
178 space
= isl_local_space_get_space(ls
);
181 if (isl_space_is_map(space
))
182 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
183 "expecting (parameter) set space", goto error
);
184 if (pos
>= isl_local_space_dim(ls
, type
))
185 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
186 "position out of bounds", goto error
);
188 isl_space_free(space
);
189 aff
= isl_aff_alloc(ls
);
193 pos
+= isl_local_space_offset(aff
->ls
, type
);
195 isl_int_set_si(aff
->v
->el
[0], 1);
196 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
197 isl_int_set_si(aff
->v
->el
[1 + pos
], 1);
201 isl_local_space_free(ls
);
202 isl_space_free(space
);
206 /* Return a piecewise affine expression that is equal to
207 * the specified dimension in "ls".
209 __isl_give isl_pw_aff
*isl_pw_aff_var_on_domain(__isl_take isl_local_space
*ls
,
210 enum isl_dim_type type
, unsigned pos
)
212 return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, type
, pos
));
215 __isl_give isl_aff
*isl_aff_copy(__isl_keep isl_aff
*aff
)
224 __isl_give isl_aff
*isl_aff_dup(__isl_keep isl_aff
*aff
)
229 return isl_aff_alloc_vec(isl_local_space_copy(aff
->ls
),
230 isl_vec_copy(aff
->v
));
233 __isl_give isl_aff
*isl_aff_cow(__isl_take isl_aff
*aff
)
241 return isl_aff_dup(aff
);
244 __isl_null isl_aff
*isl_aff_free(__isl_take isl_aff
*aff
)
252 isl_local_space_free(aff
->ls
);
253 isl_vec_free(aff
->v
);
260 isl_ctx
*isl_aff_get_ctx(__isl_keep isl_aff
*aff
)
262 return aff
? isl_local_space_get_ctx(aff
->ls
) : NULL
;
265 /* Externally, an isl_aff has a map space, but internally, the
266 * ls field corresponds to the domain of that space.
268 int isl_aff_dim(__isl_keep isl_aff
*aff
, enum isl_dim_type type
)
272 if (type
== isl_dim_out
)
274 if (type
== isl_dim_in
)
276 return isl_local_space_dim(aff
->ls
, type
);
279 __isl_give isl_space
*isl_aff_get_domain_space(__isl_keep isl_aff
*aff
)
281 return aff
? isl_local_space_get_space(aff
->ls
) : NULL
;
284 __isl_give isl_space
*isl_aff_get_space(__isl_keep isl_aff
*aff
)
289 space
= isl_local_space_get_space(aff
->ls
);
290 space
= isl_space_from_domain(space
);
291 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
295 __isl_give isl_local_space
*isl_aff_get_domain_local_space(
296 __isl_keep isl_aff
*aff
)
298 return aff
? isl_local_space_copy(aff
->ls
) : NULL
;
301 __isl_give isl_local_space
*isl_aff_get_local_space(__isl_keep isl_aff
*aff
)
306 ls
= isl_local_space_copy(aff
->ls
);
307 ls
= isl_local_space_from_domain(ls
);
308 ls
= isl_local_space_add_dims(ls
, isl_dim_out
, 1);
312 /* Externally, an isl_aff has a map space, but internally, the
313 * ls field corresponds to the domain of that space.
315 const char *isl_aff_get_dim_name(__isl_keep isl_aff
*aff
,
316 enum isl_dim_type type
, unsigned pos
)
320 if (type
== isl_dim_out
)
322 if (type
== isl_dim_in
)
324 return isl_local_space_get_dim_name(aff
->ls
, type
, pos
);
327 __isl_give isl_aff
*isl_aff_reset_domain_space(__isl_take isl_aff
*aff
,
328 __isl_take isl_space
*dim
)
330 aff
= isl_aff_cow(aff
);
334 aff
->ls
= isl_local_space_reset_space(aff
->ls
, dim
);
336 return isl_aff_free(aff
);
345 /* Reset the space of "aff". This function is called from isl_pw_templ.c
346 * and doesn't know if the space of an element object is represented
347 * directly or through its domain. It therefore passes along both.
349 __isl_give isl_aff
*isl_aff_reset_space_and_domain(__isl_take isl_aff
*aff
,
350 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
352 isl_space_free(space
);
353 return isl_aff_reset_domain_space(aff
, domain
);
356 /* Reorder the coefficients of the affine expression based
357 * on the given reodering.
358 * The reordering r is assumed to have been extended with the local
361 static __isl_give isl_vec
*vec_reorder(__isl_take isl_vec
*vec
,
362 __isl_take isl_reordering
*r
, int n_div
)
370 res
= isl_vec_alloc(vec
->ctx
,
371 2 + isl_space_dim(r
->dim
, isl_dim_all
) + n_div
);
372 isl_seq_cpy(res
->el
, vec
->el
, 2);
373 isl_seq_clr(res
->el
+ 2, res
->size
- 2);
374 for (i
= 0; i
< r
->len
; ++i
)
375 isl_int_set(res
->el
[2 + r
->pos
[i
]], vec
->el
[2 + i
]);
377 isl_reordering_free(r
);
382 isl_reordering_free(r
);
386 /* Reorder the dimensions of the domain of "aff" according
387 * to the given reordering.
389 __isl_give isl_aff
*isl_aff_realign_domain(__isl_take isl_aff
*aff
,
390 __isl_take isl_reordering
*r
)
392 aff
= isl_aff_cow(aff
);
396 r
= isl_reordering_extend(r
, aff
->ls
->div
->n_row
);
397 aff
->v
= vec_reorder(aff
->v
, isl_reordering_copy(r
),
398 aff
->ls
->div
->n_row
);
399 aff
->ls
= isl_local_space_realign(aff
->ls
, r
);
401 if (!aff
->v
|| !aff
->ls
)
402 return isl_aff_free(aff
);
407 isl_reordering_free(r
);
411 __isl_give isl_aff
*isl_aff_align_params(__isl_take isl_aff
*aff
,
412 __isl_take isl_space
*model
)
417 if (!isl_space_match(aff
->ls
->dim
, isl_dim_param
,
418 model
, isl_dim_param
)) {
421 model
= isl_space_drop_dims(model
, isl_dim_in
,
422 0, isl_space_dim(model
, isl_dim_in
));
423 model
= isl_space_drop_dims(model
, isl_dim_out
,
424 0, isl_space_dim(model
, isl_dim_out
));
425 exp
= isl_parameter_alignment_reordering(aff
->ls
->dim
, model
);
426 exp
= isl_reordering_extend_space(exp
,
427 isl_aff_get_domain_space(aff
));
428 aff
= isl_aff_realign_domain(aff
, exp
);
431 isl_space_free(model
);
434 isl_space_free(model
);
439 /* Is "aff" obviously equal to zero?
441 * If the denominator is zero, then "aff" is not equal to zero.
443 int isl_aff_plain_is_zero(__isl_keep isl_aff
*aff
)
448 if (isl_int_is_zero(aff
->v
->el
[0]))
450 return isl_seq_first_non_zero(aff
->v
->el
+ 1, aff
->v
->size
- 1) < 0;
453 /* Does "aff" represent NaN?
455 int isl_aff_is_nan(__isl_keep isl_aff
*aff
)
460 return isl_seq_first_non_zero(aff
->v
->el
, 2) < 0;
463 /* Does "pa" involve any NaNs?
465 int isl_pw_aff_involves_nan(__isl_keep isl_pw_aff
*pa
)
474 for (i
= 0; i
< pa
->n
; ++i
) {
475 int is_nan
= isl_aff_is_nan(pa
->p
[i
].aff
);
476 if (is_nan
< 0 || is_nan
)
483 /* Are "aff1" and "aff2" obviously equal?
485 * NaN is not equal to anything, not even to another NaN.
487 int isl_aff_plain_is_equal(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
494 if (isl_aff_is_nan(aff1
) || isl_aff_is_nan(aff2
))
497 equal
= isl_local_space_is_equal(aff1
->ls
, aff2
->ls
);
498 if (equal
< 0 || !equal
)
501 return isl_vec_is_equal(aff1
->v
, aff2
->v
);
504 /* Return the common denominator of "aff" in "v".
506 * We cannot return anything meaningful in case of a NaN.
508 int isl_aff_get_denominator(__isl_keep isl_aff
*aff
, isl_int
*v
)
512 if (isl_aff_is_nan(aff
))
513 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
514 "cannot get denominator of NaN", return -1);
515 isl_int_set(*v
, aff
->v
->el
[0]);
519 /* Return the common denominator of "aff".
521 __isl_give isl_val
*isl_aff_get_denominator_val(__isl_keep isl_aff
*aff
)
528 ctx
= isl_aff_get_ctx(aff
);
529 if (isl_aff_is_nan(aff
))
530 return isl_val_nan(ctx
);
531 return isl_val_int_from_isl_int(ctx
, aff
->v
->el
[0]);
534 /* Return the constant term of "aff" in "v".
536 * We cannot return anything meaningful in case of a NaN.
538 int isl_aff_get_constant(__isl_keep isl_aff
*aff
, isl_int
*v
)
542 if (isl_aff_is_nan(aff
))
543 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
544 "cannot get constant term of NaN", return -1);
545 isl_int_set(*v
, aff
->v
->el
[1]);
549 /* Return the constant term of "aff".
551 __isl_give isl_val
*isl_aff_get_constant_val(__isl_keep isl_aff
*aff
)
559 ctx
= isl_aff_get_ctx(aff
);
560 if (isl_aff_is_nan(aff
))
561 return isl_val_nan(ctx
);
562 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1], aff
->v
->el
[0]);
563 return isl_val_normalize(v
);
566 /* Return the coefficient of the variable of type "type" at position "pos"
569 * We cannot return anything meaningful in case of a NaN.
571 int isl_aff_get_coefficient(__isl_keep isl_aff
*aff
,
572 enum isl_dim_type type
, int pos
, isl_int
*v
)
577 if (type
== isl_dim_out
)
578 isl_die(aff
->v
->ctx
, isl_error_invalid
,
579 "output/set dimension does not have a coefficient",
581 if (type
== isl_dim_in
)
584 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
585 isl_die(aff
->v
->ctx
, isl_error_invalid
,
586 "position out of bounds", return -1);
588 if (isl_aff_is_nan(aff
))
589 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
590 "cannot get coefficient of NaN", return -1);
591 pos
+= isl_local_space_offset(aff
->ls
, type
);
592 isl_int_set(*v
, aff
->v
->el
[1 + pos
]);
597 /* Return the coefficient of the variable of type "type" at position "pos"
600 __isl_give isl_val
*isl_aff_get_coefficient_val(__isl_keep isl_aff
*aff
,
601 enum isl_dim_type type
, int pos
)
609 ctx
= isl_aff_get_ctx(aff
);
610 if (type
== isl_dim_out
)
611 isl_die(ctx
, isl_error_invalid
,
612 "output/set dimension does not have a coefficient",
614 if (type
== isl_dim_in
)
617 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
618 isl_die(ctx
, isl_error_invalid
,
619 "position out of bounds", return NULL
);
621 if (isl_aff_is_nan(aff
))
622 return isl_val_nan(ctx
);
623 pos
+= isl_local_space_offset(aff
->ls
, type
);
624 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1 + pos
], aff
->v
->el
[0]);
625 return isl_val_normalize(v
);
628 /* Replace the denominator of "aff" by "v".
630 * A NaN is unaffected by this operation.
632 __isl_give isl_aff
*isl_aff_set_denominator(__isl_take isl_aff
*aff
, isl_int v
)
636 if (isl_aff_is_nan(aff
))
638 aff
= isl_aff_cow(aff
);
642 aff
->v
= isl_vec_cow(aff
->v
);
644 return isl_aff_free(aff
);
646 isl_int_set(aff
->v
->el
[0], v
);
651 /* Replace the numerator of the constant term of "aff" by "v".
653 * A NaN is unaffected by this operation.
655 __isl_give isl_aff
*isl_aff_set_constant(__isl_take isl_aff
*aff
, isl_int v
)
659 if (isl_aff_is_nan(aff
))
661 aff
= isl_aff_cow(aff
);
665 aff
->v
= isl_vec_cow(aff
->v
);
667 return isl_aff_free(aff
);
669 isl_int_set(aff
->v
->el
[1], v
);
674 /* Replace the constant term of "aff" by "v".
676 * A NaN is unaffected by this operation.
678 __isl_give isl_aff
*isl_aff_set_constant_val(__isl_take isl_aff
*aff
,
679 __isl_take isl_val
*v
)
684 if (isl_aff_is_nan(aff
)) {
689 if (!isl_val_is_rat(v
))
690 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
691 "expecting rational value", goto error
);
693 if (isl_int_eq(aff
->v
->el
[1], v
->n
) &&
694 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
699 aff
= isl_aff_cow(aff
);
702 aff
->v
= isl_vec_cow(aff
->v
);
706 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
707 isl_int_set(aff
->v
->el
[1], v
->n
);
708 } else if (isl_int_is_one(v
->d
)) {
709 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
711 isl_seq_scale(aff
->v
->el
+ 1,
712 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
713 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
714 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
715 aff
->v
= isl_vec_normalize(aff
->v
);
728 /* Add "v" to the constant term of "aff".
730 * A NaN is unaffected by this operation.
732 __isl_give isl_aff
*isl_aff_add_constant(__isl_take isl_aff
*aff
, isl_int v
)
734 if (isl_int_is_zero(v
))
739 if (isl_aff_is_nan(aff
))
741 aff
= isl_aff_cow(aff
);
745 aff
->v
= isl_vec_cow(aff
->v
);
747 return isl_aff_free(aff
);
749 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
);
754 /* Add "v" to the constant term of "aff".
756 * A NaN is unaffected by this operation.
758 __isl_give isl_aff
*isl_aff_add_constant_val(__isl_take isl_aff
*aff
,
759 __isl_take isl_val
*v
)
764 if (isl_aff_is_nan(aff
) || isl_val_is_zero(v
)) {
769 if (!isl_val_is_rat(v
))
770 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
771 "expecting rational value", goto error
);
773 aff
= isl_aff_cow(aff
);
777 aff
->v
= isl_vec_cow(aff
->v
);
781 if (isl_int_is_one(v
->d
)) {
782 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
783 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
784 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
->n
);
785 aff
->v
= isl_vec_normalize(aff
->v
);
789 isl_seq_scale(aff
->v
->el
+ 1,
790 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
791 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
792 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
793 aff
->v
= isl_vec_normalize(aff
->v
);
806 __isl_give isl_aff
*isl_aff_add_constant_si(__isl_take isl_aff
*aff
, int v
)
811 isl_int_set_si(t
, v
);
812 aff
= isl_aff_add_constant(aff
, t
);
818 /* Add "v" to the numerator of the constant term of "aff".
820 * A NaN is unaffected by this operation.
822 __isl_give isl_aff
*isl_aff_add_constant_num(__isl_take isl_aff
*aff
, isl_int v
)
824 if (isl_int_is_zero(v
))
829 if (isl_aff_is_nan(aff
))
831 aff
= isl_aff_cow(aff
);
835 aff
->v
= isl_vec_cow(aff
->v
);
837 return isl_aff_free(aff
);
839 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
);
844 /* Add "v" to the numerator of the constant term of "aff".
846 * A NaN is unaffected by this operation.
848 __isl_give isl_aff
*isl_aff_add_constant_num_si(__isl_take isl_aff
*aff
, int v
)
856 isl_int_set_si(t
, v
);
857 aff
= isl_aff_add_constant_num(aff
, t
);
863 /* Replace the numerator of the constant term of "aff" by "v".
865 * A NaN is unaffected by this operation.
867 __isl_give isl_aff
*isl_aff_set_constant_si(__isl_take isl_aff
*aff
, int v
)
871 if (isl_aff_is_nan(aff
))
873 aff
= isl_aff_cow(aff
);
877 aff
->v
= isl_vec_cow(aff
->v
);
879 return isl_aff_free(aff
);
881 isl_int_set_si(aff
->v
->el
[1], v
);
886 /* Replace the numerator of the coefficient of the variable of type "type"
887 * at position "pos" of "aff" by "v".
889 * A NaN is unaffected by this operation.
891 __isl_give isl_aff
*isl_aff_set_coefficient(__isl_take isl_aff
*aff
,
892 enum isl_dim_type type
, int pos
, isl_int v
)
897 if (type
== isl_dim_out
)
898 isl_die(aff
->v
->ctx
, isl_error_invalid
,
899 "output/set dimension does not have a coefficient",
900 return isl_aff_free(aff
));
901 if (type
== isl_dim_in
)
904 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
905 isl_die(aff
->v
->ctx
, isl_error_invalid
,
906 "position out of bounds", return isl_aff_free(aff
));
908 if (isl_aff_is_nan(aff
))
910 aff
= isl_aff_cow(aff
);
914 aff
->v
= isl_vec_cow(aff
->v
);
916 return isl_aff_free(aff
);
918 pos
+= isl_local_space_offset(aff
->ls
, type
);
919 isl_int_set(aff
->v
->el
[1 + pos
], v
);
924 /* Replace the numerator of the coefficient of the variable of type "type"
925 * at position "pos" of "aff" by "v".
927 * A NaN is unaffected by this operation.
929 __isl_give isl_aff
*isl_aff_set_coefficient_si(__isl_take isl_aff
*aff
,
930 enum isl_dim_type type
, int pos
, int v
)
935 if (type
== isl_dim_out
)
936 isl_die(aff
->v
->ctx
, isl_error_invalid
,
937 "output/set dimension does not have a coefficient",
938 return isl_aff_free(aff
));
939 if (type
== isl_dim_in
)
942 if (pos
< 0 || pos
>= isl_local_space_dim(aff
->ls
, type
))
943 isl_die(aff
->v
->ctx
, isl_error_invalid
,
944 "position out of bounds", return isl_aff_free(aff
));
946 if (isl_aff_is_nan(aff
))
948 pos
+= isl_local_space_offset(aff
->ls
, type
);
949 if (isl_int_cmp_si(aff
->v
->el
[1 + pos
], v
) == 0)
952 aff
= isl_aff_cow(aff
);
956 aff
->v
= isl_vec_cow(aff
->v
);
958 return isl_aff_free(aff
);
960 isl_int_set_si(aff
->v
->el
[1 + pos
], v
);
965 /* Replace the coefficient of the variable of type "type" at position "pos"
968 * A NaN is unaffected by this operation.
970 __isl_give isl_aff
*isl_aff_set_coefficient_val(__isl_take isl_aff
*aff
,
971 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
976 if (type
== isl_dim_out
)
977 isl_die(aff
->v
->ctx
, isl_error_invalid
,
978 "output/set dimension does not have a coefficient",
980 if (type
== isl_dim_in
)
983 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
984 isl_die(aff
->v
->ctx
, isl_error_invalid
,
985 "position out of bounds", goto error
);
987 if (isl_aff_is_nan(aff
)) {
991 if (!isl_val_is_rat(v
))
992 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
993 "expecting rational value", goto error
);
995 pos
+= isl_local_space_offset(aff
->ls
, type
);
996 if (isl_int_eq(aff
->v
->el
[1 + pos
], v
->n
) &&
997 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
1002 aff
= isl_aff_cow(aff
);
1005 aff
->v
= isl_vec_cow(aff
->v
);
1009 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
1010 isl_int_set(aff
->v
->el
[1 + pos
], v
->n
);
1011 } else if (isl_int_is_one(v
->d
)) {
1012 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1014 isl_seq_scale(aff
->v
->el
+ 1,
1015 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
1016 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1017 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
1018 aff
->v
= isl_vec_normalize(aff
->v
);
1031 /* Add "v" to the coefficient of the variable of type "type"
1032 * at position "pos" of "aff".
1034 * A NaN is unaffected by this operation.
1036 __isl_give isl_aff
*isl_aff_add_coefficient(__isl_take isl_aff
*aff
,
1037 enum isl_dim_type type
, int pos
, isl_int v
)
1042 if (type
== isl_dim_out
)
1043 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1044 "output/set dimension does not have a coefficient",
1045 return isl_aff_free(aff
));
1046 if (type
== isl_dim_in
)
1049 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
1050 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1051 "position out of bounds", return isl_aff_free(aff
));
1053 if (isl_aff_is_nan(aff
))
1055 aff
= isl_aff_cow(aff
);
1059 aff
->v
= isl_vec_cow(aff
->v
);
1061 return isl_aff_free(aff
);
1063 pos
+= isl_local_space_offset(aff
->ls
, type
);
1064 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
);
1069 /* Add "v" to the coefficient of the variable of type "type"
1070 * at position "pos" of "aff".
1072 * A NaN is unaffected by this operation.
1074 __isl_give isl_aff
*isl_aff_add_coefficient_val(__isl_take isl_aff
*aff
,
1075 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
1080 if (isl_val_is_zero(v
)) {
1085 if (type
== isl_dim_out
)
1086 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1087 "output/set dimension does not have a coefficient",
1089 if (type
== isl_dim_in
)
1092 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
1093 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1094 "position out of bounds", goto error
);
1096 if (isl_aff_is_nan(aff
)) {
1100 if (!isl_val_is_rat(v
))
1101 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1102 "expecting rational value", goto error
);
1104 aff
= isl_aff_cow(aff
);
1108 aff
->v
= isl_vec_cow(aff
->v
);
1112 pos
+= isl_local_space_offset(aff
->ls
, type
);
1113 if (isl_int_is_one(v
->d
)) {
1114 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1115 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
1116 isl_int_add(aff
->v
->el
[1 + pos
], aff
->v
->el
[1 + pos
], v
->n
);
1117 aff
->v
= isl_vec_normalize(aff
->v
);
1121 isl_seq_scale(aff
->v
->el
+ 1,
1122 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
1123 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
1124 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
1125 aff
->v
= isl_vec_normalize(aff
->v
);
1138 __isl_give isl_aff
*isl_aff_add_coefficient_si(__isl_take isl_aff
*aff
,
1139 enum isl_dim_type type
, int pos
, int v
)
1144 isl_int_set_si(t
, v
);
1145 aff
= isl_aff_add_coefficient(aff
, type
, pos
, t
);
1151 __isl_give isl_aff
*isl_aff_get_div(__isl_keep isl_aff
*aff
, int pos
)
1156 return isl_local_space_get_div(aff
->ls
, pos
);
1159 /* Return the negation of "aff".
1161 * As a special case, -NaN = NaN.
1163 __isl_give isl_aff
*isl_aff_neg(__isl_take isl_aff
*aff
)
1167 if (isl_aff_is_nan(aff
))
1169 aff
= isl_aff_cow(aff
);
1172 aff
->v
= isl_vec_cow(aff
->v
);
1174 return isl_aff_free(aff
);
1176 isl_seq_neg(aff
->v
->el
+ 1, aff
->v
->el
+ 1, aff
->v
->size
- 1);
1181 /* Remove divs from the local space that do not appear in the affine
1183 * We currently only remove divs at the end.
1184 * Some intermediate divs may also not appear directly in the affine
1185 * expression, but we would also need to check that no other divs are
1186 * defined in terms of them.
1188 __isl_give isl_aff
*isl_aff_remove_unused_divs( __isl_take isl_aff
*aff
)
1197 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1198 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1200 pos
= isl_seq_last_non_zero(aff
->v
->el
+ 1 + off
, n
) + 1;
1204 aff
= isl_aff_cow(aff
);
1208 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, isl_dim_div
, pos
, n
- pos
);
1209 aff
->v
= isl_vec_drop_els(aff
->v
, 1 + off
+ pos
, n
- pos
);
1210 if (!aff
->ls
|| !aff
->v
)
1211 return isl_aff_free(aff
);
1216 /* Given two affine expressions "p" of length p_len (including the
1217 * denominator and the constant term) and "subs" of length subs_len,
1218 * plug in "subs" for the variable at position "pos".
1219 * The variables of "subs" and "p" are assumed to match up to subs_len,
1220 * but "p" may have additional variables.
1221 * "v" is an initialized isl_int that can be used internally.
1223 * In particular, if "p" represents the expression
1227 * with i the variable at position "pos" and "subs" represents the expression
1231 * then the result represents the expression
1236 void isl_seq_substitute(isl_int
*p
, int pos
, isl_int
*subs
,
1237 int p_len
, int subs_len
, isl_int v
)
1239 isl_int_set(v
, p
[1 + pos
]);
1240 isl_int_set_si(p
[1 + pos
], 0);
1241 isl_seq_combine(p
+ 1, subs
[0], p
+ 1, v
, subs
+ 1, subs_len
- 1);
1242 isl_seq_scale(p
+ subs_len
, p
+ subs_len
, subs
[0], p_len
- subs_len
);
1243 isl_int_mul(p
[0], p
[0], subs
[0]);
1246 /* Look for any divs in the aff->ls with a denominator equal to one
1247 * and plug them into the affine expression and any subsequent divs
1248 * that may reference the div.
1250 static __isl_give isl_aff
*plug_in_integral_divs(__isl_take isl_aff
*aff
)
1256 isl_local_space
*ls
;
1262 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1264 for (i
= 0; i
< n
; ++i
) {
1265 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][0]))
1267 ls
= isl_local_space_copy(aff
->ls
);
1268 ls
= isl_local_space_substitute_seq(ls
, isl_dim_div
, i
,
1269 aff
->ls
->div
->row
[i
], len
, i
+ 1, n
- (i
+ 1));
1270 vec
= isl_vec_copy(aff
->v
);
1271 vec
= isl_vec_cow(vec
);
1277 pos
= isl_local_space_offset(aff
->ls
, isl_dim_div
) + i
;
1278 isl_seq_substitute(vec
->el
, pos
, aff
->ls
->div
->row
[i
],
1283 isl_vec_free(aff
->v
);
1285 isl_local_space_free(aff
->ls
);
1292 isl_local_space_free(ls
);
1293 return isl_aff_free(aff
);
1296 /* Look for any divs j that appear with a unit coefficient inside
1297 * the definitions of other divs i and plug them into the definitions
1300 * In particular, an expression of the form
1302 * floor((f(..) + floor(g(..)/n))/m)
1306 * floor((n * f(..) + g(..))/(n * m))
1308 * This simplification is correct because we can move the expression
1309 * f(..) into the inner floor in the original expression to obtain
1311 * floor(floor((n * f(..) + g(..))/n)/m)
1313 * from which we can derive the simplified expression.
1315 static __isl_give isl_aff
*plug_in_unit_divs(__isl_take isl_aff
*aff
)
1323 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1324 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1325 for (i
= 1; i
< n
; ++i
) {
1326 for (j
= 0; j
< i
; ++j
) {
1327 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][1 + off
+ j
]))
1329 aff
->ls
= isl_local_space_substitute_seq(aff
->ls
,
1330 isl_dim_div
, j
, aff
->ls
->div
->row
[j
],
1331 aff
->v
->size
, i
, 1);
1333 return isl_aff_free(aff
);
1340 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
1342 * Even though this function is only called on isl_affs with a single
1343 * reference, we are careful to only change aff->v and aff->ls together.
1345 static __isl_give isl_aff
*swap_div(__isl_take isl_aff
*aff
, int a
, int b
)
1347 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1348 isl_local_space
*ls
;
1351 ls
= isl_local_space_copy(aff
->ls
);
1352 ls
= isl_local_space_swap_div(ls
, a
, b
);
1353 v
= isl_vec_copy(aff
->v
);
1358 isl_int_swap(v
->el
[1 + off
+ a
], v
->el
[1 + off
+ b
]);
1359 isl_vec_free(aff
->v
);
1361 isl_local_space_free(aff
->ls
);
1367 isl_local_space_free(ls
);
1368 return isl_aff_free(aff
);
1371 /* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
1373 * We currently do not actually remove div "b", but simply add its
1374 * coefficient to that of "a" and then zero it out.
1376 static __isl_give isl_aff
*merge_divs(__isl_take isl_aff
*aff
, int a
, int b
)
1378 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1380 if (isl_int_is_zero(aff
->v
->el
[1 + off
+ b
]))
1383 aff
->v
= isl_vec_cow(aff
->v
);
1385 return isl_aff_free(aff
);
1387 isl_int_add(aff
->v
->el
[1 + off
+ a
],
1388 aff
->v
->el
[1 + off
+ a
], aff
->v
->el
[1 + off
+ b
]);
1389 isl_int_set_si(aff
->v
->el
[1 + off
+ b
], 0);
1394 /* Sort the divs in the local space of "aff" according to
1395 * the comparison function "cmp_row" in isl_local_space.c,
1396 * combining the coefficients of identical divs.
1398 * Reordering divs does not change the semantics of "aff",
1399 * so there is no need to call isl_aff_cow.
1400 * Moreover, this function is currently only called on isl_affs
1401 * with a single reference.
1403 static __isl_give isl_aff
*sort_divs(__isl_take isl_aff
*aff
)
1411 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1412 n
= isl_aff_dim(aff
, isl_dim_div
);
1413 for (i
= 1; i
< n
; ++i
) {
1414 for (j
= i
- 1; j
>= 0; --j
) {
1415 int cmp
= isl_mat_cmp_div(aff
->ls
->div
, j
, j
+ 1);
1419 aff
= merge_divs(aff
, j
, j
+ 1);
1421 aff
= swap_div(aff
, j
, j
+ 1);
1430 /* Normalize the representation of "aff".
1432 * This function should only be called of "new" isl_affs, i.e.,
1433 * with only a single reference. We therefore do not need to
1434 * worry about affecting other instances.
1436 __isl_give isl_aff
*isl_aff_normalize(__isl_take isl_aff
*aff
)
1440 aff
->v
= isl_vec_normalize(aff
->v
);
1442 return isl_aff_free(aff
);
1443 aff
= plug_in_integral_divs(aff
);
1444 aff
= plug_in_unit_divs(aff
);
1445 aff
= sort_divs(aff
);
1446 aff
= isl_aff_remove_unused_divs(aff
);
1450 /* Given f, return floor(f).
1451 * If f is an integer expression, then just return f.
1452 * If f is a constant, then return the constant floor(f).
1453 * Otherwise, if f = g/m, write g = q m + r,
1454 * create a new div d = [r/m] and return the expression q + d.
1455 * The coefficients in r are taken to lie between -m/2 and m/2.
1457 * As a special case, floor(NaN) = NaN.
1459 __isl_give isl_aff
*isl_aff_floor(__isl_take isl_aff
*aff
)
1469 if (isl_aff_is_nan(aff
))
1471 if (isl_int_is_one(aff
->v
->el
[0]))
1474 aff
= isl_aff_cow(aff
);
1478 aff
->v
= isl_vec_cow(aff
->v
);
1480 return isl_aff_free(aff
);
1482 if (isl_aff_is_cst(aff
)) {
1483 isl_int_fdiv_q(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1484 isl_int_set_si(aff
->v
->el
[0], 1);
1488 div
= isl_vec_copy(aff
->v
);
1489 div
= isl_vec_cow(div
);
1491 return isl_aff_free(aff
);
1493 ctx
= isl_aff_get_ctx(aff
);
1494 isl_int_fdiv_q(aff
->v
->el
[0], aff
->v
->el
[0], ctx
->two
);
1495 for (i
= 1; i
< aff
->v
->size
; ++i
) {
1496 isl_int_fdiv_r(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1497 isl_int_fdiv_q(aff
->v
->el
[i
], aff
->v
->el
[i
], div
->el
[0]);
1498 if (isl_int_gt(div
->el
[i
], aff
->v
->el
[0])) {
1499 isl_int_sub(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1500 isl_int_add_ui(aff
->v
->el
[i
], aff
->v
->el
[i
], 1);
1504 aff
->ls
= isl_local_space_add_div(aff
->ls
, div
);
1506 return isl_aff_free(aff
);
1508 size
= aff
->v
->size
;
1509 aff
->v
= isl_vec_extend(aff
->v
, size
+ 1);
1511 return isl_aff_free(aff
);
1512 isl_int_set_si(aff
->v
->el
[0], 1);
1513 isl_int_set_si(aff
->v
->el
[size
], 1);
1515 aff
= isl_aff_normalize(aff
);
1522 * aff mod m = aff - m * floor(aff/m)
1524 __isl_give isl_aff
*isl_aff_mod(__isl_take isl_aff
*aff
, isl_int m
)
1528 res
= isl_aff_copy(aff
);
1529 aff
= isl_aff_scale_down(aff
, m
);
1530 aff
= isl_aff_floor(aff
);
1531 aff
= isl_aff_scale(aff
, m
);
1532 res
= isl_aff_sub(res
, aff
);
1539 * aff mod m = aff - m * floor(aff/m)
1541 * with m an integer value.
1543 __isl_give isl_aff
*isl_aff_mod_val(__isl_take isl_aff
*aff
,
1544 __isl_take isl_val
*m
)
1551 if (!isl_val_is_int(m
))
1552 isl_die(isl_val_get_ctx(m
), isl_error_invalid
,
1553 "expecting integer modulo", goto error
);
1555 res
= isl_aff_copy(aff
);
1556 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(m
));
1557 aff
= isl_aff_floor(aff
);
1558 aff
= isl_aff_scale_val(aff
, m
);
1559 res
= isl_aff_sub(res
, aff
);
1570 * pwaff mod m = pwaff - m * floor(pwaff/m)
1572 __isl_give isl_pw_aff
*isl_pw_aff_mod(__isl_take isl_pw_aff
*pwaff
, isl_int m
)
1576 res
= isl_pw_aff_copy(pwaff
);
1577 pwaff
= isl_pw_aff_scale_down(pwaff
, m
);
1578 pwaff
= isl_pw_aff_floor(pwaff
);
1579 pwaff
= isl_pw_aff_scale(pwaff
, m
);
1580 res
= isl_pw_aff_sub(res
, pwaff
);
1587 * pa mod m = pa - m * floor(pa/m)
1589 * with m an integer value.
1591 __isl_give isl_pw_aff
*isl_pw_aff_mod_val(__isl_take isl_pw_aff
*pa
,
1592 __isl_take isl_val
*m
)
1596 if (!isl_val_is_int(m
))
1597 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
1598 "expecting integer modulo", goto error
);
1599 pa
= isl_pw_aff_mod(pa
, m
->n
);
1603 isl_pw_aff_free(pa
);
1608 /* Given f, return ceil(f).
1609 * If f is an integer expression, then just return f.
1610 * Otherwise, let f be the expression
1616 * floor((e + m - 1)/m)
1618 * As a special case, ceil(NaN) = NaN.
1620 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
1625 if (isl_aff_is_nan(aff
))
1627 if (isl_int_is_one(aff
->v
->el
[0]))
1630 aff
= isl_aff_cow(aff
);
1633 aff
->v
= isl_vec_cow(aff
->v
);
1635 return isl_aff_free(aff
);
1637 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1638 isl_int_sub_ui(aff
->v
->el
[1], aff
->v
->el
[1], 1);
1639 aff
= isl_aff_floor(aff
);
1644 /* Apply the expansion computed by isl_merge_divs.
1645 * The expansion itself is given by "exp" while the resulting
1646 * list of divs is given by "div".
1648 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
1649 __isl_take isl_mat
*div
, int *exp
)
1656 aff
= isl_aff_cow(aff
);
1660 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1661 new_n_div
= isl_mat_rows(div
);
1662 if (new_n_div
< old_n_div
)
1663 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
1664 "not an expansion", goto error
);
1666 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
1670 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
1672 for (i
= new_n_div
- 1; i
>= 0; --i
) {
1673 if (j
>= 0 && exp
[j
] == i
) {
1675 isl_int_swap(aff
->v
->el
[offset
+ i
],
1676 aff
->v
->el
[offset
+ j
]);
1679 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
1682 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
1693 /* Add two affine expressions that live in the same local space.
1695 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
1696 __isl_take isl_aff
*aff2
)
1700 aff1
= isl_aff_cow(aff1
);
1704 aff1
->v
= isl_vec_cow(aff1
->v
);
1710 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
1711 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1712 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
1713 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
1714 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
1715 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1716 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
1728 /* Return the sum of "aff1" and "aff2".
1730 * If either of the two is NaN, then the result is NaN.
1732 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
1733 __isl_take isl_aff
*aff2
)
1744 ctx
= isl_aff_get_ctx(aff1
);
1745 if (!isl_space_is_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
1746 isl_die(ctx
, isl_error_invalid
,
1747 "spaces don't match", goto error
);
1749 if (isl_aff_is_nan(aff1
)) {
1753 if (isl_aff_is_nan(aff2
)) {
1758 n_div1
= isl_aff_dim(aff1
, isl_dim_div
);
1759 n_div2
= isl_aff_dim(aff2
, isl_dim_div
);
1760 if (n_div1
== 0 && n_div2
== 0)
1761 return add_expanded(aff1
, aff2
);
1763 exp1
= isl_alloc_array(ctx
, int, n_div1
);
1764 exp2
= isl_alloc_array(ctx
, int, n_div2
);
1765 if ((n_div1
&& !exp1
) || (n_div2
&& !exp2
))
1768 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
1769 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
1770 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
1774 return add_expanded(aff1
, aff2
);
1783 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
1784 __isl_take isl_aff
*aff2
)
1786 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
1789 /* Return the result of scaling "aff" by a factor of "f".
1791 * As a special case, f * NaN = NaN.
1793 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
1799 if (isl_aff_is_nan(aff
))
1802 if (isl_int_is_one(f
))
1805 aff
= isl_aff_cow(aff
);
1808 aff
->v
= isl_vec_cow(aff
->v
);
1810 return isl_aff_free(aff
);
1812 if (isl_int_is_pos(f
) && isl_int_is_divisible_by(aff
->v
->el
[0], f
)) {
1813 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], f
);
1818 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
1819 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1820 isl_int_divexact(gcd
, f
, gcd
);
1821 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1827 /* Multiple "aff" by "v".
1829 __isl_give isl_aff
*isl_aff_scale_val(__isl_take isl_aff
*aff
,
1830 __isl_take isl_val
*v
)
1835 if (isl_val_is_one(v
)) {
1840 if (!isl_val_is_rat(v
))
1841 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1842 "expecting rational factor", goto error
);
1844 aff
= isl_aff_scale(aff
, v
->n
);
1845 aff
= isl_aff_scale_down(aff
, v
->d
);
1855 /* Return the result of scaling "aff" down by a factor of "f".
1857 * As a special case, NaN/f = NaN.
1859 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
1865 if (isl_aff_is_nan(aff
))
1868 if (isl_int_is_one(f
))
1871 aff
= isl_aff_cow(aff
);
1875 if (isl_int_is_zero(f
))
1876 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1877 "cannot scale down by zero", return isl_aff_free(aff
));
1879 aff
->v
= isl_vec_cow(aff
->v
);
1881 return isl_aff_free(aff
);
1884 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
1885 isl_int_gcd(gcd
, gcd
, f
);
1886 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1887 isl_int_divexact(gcd
, f
, gcd
);
1888 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1894 /* Divide "aff" by "v".
1896 __isl_give isl_aff
*isl_aff_scale_down_val(__isl_take isl_aff
*aff
,
1897 __isl_take isl_val
*v
)
1902 if (isl_val_is_one(v
)) {
1907 if (!isl_val_is_rat(v
))
1908 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1909 "expecting rational factor", goto error
);
1910 if (!isl_val_is_pos(v
))
1911 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1912 "factor needs to be positive", goto error
);
1914 aff
= isl_aff_scale(aff
, v
->d
);
1915 aff
= isl_aff_scale_down(aff
, v
->n
);
1925 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
1933 isl_int_set_ui(v
, f
);
1934 aff
= isl_aff_scale_down(aff
, v
);
1940 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
1941 enum isl_dim_type type
, unsigned pos
, const char *s
)
1943 aff
= isl_aff_cow(aff
);
1946 if (type
== isl_dim_out
)
1947 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1948 "cannot set name of output/set dimension",
1949 return isl_aff_free(aff
));
1950 if (type
== isl_dim_in
)
1952 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
1954 return isl_aff_free(aff
);
1959 __isl_give isl_aff
*isl_aff_set_dim_id(__isl_take isl_aff
*aff
,
1960 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1962 aff
= isl_aff_cow(aff
);
1965 if (type
== isl_dim_out
)
1966 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1967 "cannot set name of output/set dimension",
1969 if (type
== isl_dim_in
)
1971 aff
->ls
= isl_local_space_set_dim_id(aff
->ls
, type
, pos
, id
);
1973 return isl_aff_free(aff
);
1982 /* Replace the identifier of the input tuple of "aff" by "id".
1983 * type is currently required to be equal to isl_dim_in
1985 __isl_give isl_aff
*isl_aff_set_tuple_id(__isl_take isl_aff
*aff
,
1986 enum isl_dim_type type
, __isl_take isl_id
*id
)
1988 aff
= isl_aff_cow(aff
);
1991 if (type
!= isl_dim_out
)
1992 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1993 "cannot only set id of input tuple", goto error
);
1994 aff
->ls
= isl_local_space_set_tuple_id(aff
->ls
, isl_dim_set
, id
);
1996 return isl_aff_free(aff
);
2005 /* Exploit the equalities in "eq" to simplify the affine expression
2006 * and the expressions of the integer divisions in the local space.
2007 * The integer divisions in this local space are assumed to appear
2008 * as regular dimensions in "eq".
2010 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
2011 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
2019 if (eq
->n_eq
== 0) {
2020 isl_basic_set_free(eq
);
2024 aff
= isl_aff_cow(aff
);
2028 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
2029 isl_basic_set_copy(eq
));
2030 aff
->v
= isl_vec_cow(aff
->v
);
2031 if (!aff
->ls
|| !aff
->v
)
2034 total
= 1 + isl_space_dim(eq
->dim
, isl_dim_all
);
2036 for (i
= 0; i
< eq
->n_eq
; ++i
) {
2037 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
2038 if (j
< 0 || j
== 0 || j
>= total
)
2041 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
2045 isl_basic_set_free(eq
);
2046 aff
= isl_aff_normalize(aff
);
2049 isl_basic_set_free(eq
);
2054 /* Exploit the equalities in "eq" to simplify the affine expression
2055 * and the expressions of the integer divisions in the local space.
2057 static __isl_give isl_aff
*isl_aff_substitute_equalities(
2058 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
2064 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
2066 eq
= isl_basic_set_add_dims(eq
, isl_dim_set
, n_div
);
2067 return isl_aff_substitute_equalities_lifted(aff
, eq
);
2069 isl_basic_set_free(eq
);
2074 /* Look for equalities among the variables shared by context and aff
2075 * and the integer divisions of aff, if any.
2076 * The equalities are then used to eliminate coefficients and/or integer
2077 * divisions from aff.
2079 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
2080 __isl_take isl_set
*context
)
2082 isl_basic_set
*hull
;
2087 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
2089 isl_basic_set
*bset
;
2090 isl_local_space
*ls
;
2091 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
2092 ls
= isl_aff_get_domain_local_space(aff
);
2093 bset
= isl_basic_set_from_local_space(ls
);
2094 bset
= isl_basic_set_lift(bset
);
2095 bset
= isl_basic_set_flatten(bset
);
2096 context
= isl_set_intersect(context
,
2097 isl_set_from_basic_set(bset
));
2100 hull
= isl_set_affine_hull(context
);
2101 return isl_aff_substitute_equalities_lifted(aff
, hull
);
2104 isl_set_free(context
);
2108 __isl_give isl_aff
*isl_aff_gist_params(__isl_take isl_aff
*aff
,
2109 __isl_take isl_set
*context
)
2111 isl_set
*dom_context
= isl_set_universe(isl_aff_get_domain_space(aff
));
2112 dom_context
= isl_set_intersect_params(dom_context
, context
);
2113 return isl_aff_gist(aff
, dom_context
);
2116 /* Return a basic set containing those elements in the space
2117 * of aff where it is non-negative.
2118 * If "rational" is set, then return a rational basic set.
2120 * If "aff" is NaN, then it is not non-negative (it's not negative either).
2122 static __isl_give isl_basic_set
*aff_nonneg_basic_set(
2123 __isl_take isl_aff
*aff
, int rational
)
2125 isl_constraint
*ineq
;
2126 isl_basic_set
*bset
;
2130 if (isl_aff_is_nan(aff
)) {
2131 isl_space
*space
= isl_aff_get_domain_space(aff
);
2133 return isl_basic_set_empty(space
);
2136 ineq
= isl_inequality_from_aff(aff
);
2138 bset
= isl_basic_set_from_constraint(ineq
);
2140 bset
= isl_basic_set_set_rational(bset
);
2141 bset
= isl_basic_set_simplify(bset
);
2145 /* Return a basic set containing those elements in the space
2146 * of aff where it is non-negative.
2148 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
2150 return aff_nonneg_basic_set(aff
, 0);
2153 /* Return a basic set containing those elements in the domain space
2154 * of aff where it is negative.
2156 __isl_give isl_basic_set
*isl_aff_neg_basic_set(__isl_take isl_aff
*aff
)
2158 aff
= isl_aff_neg(aff
);
2159 aff
= isl_aff_add_constant_num_si(aff
, -1);
2160 return isl_aff_nonneg_basic_set(aff
);
2163 /* Return a basic set containing those elements in the space
2164 * of aff where it is zero.
2165 * If "rational" is set, then return a rational basic set.
2167 * If "aff" is NaN, then it is not zero.
2169 static __isl_give isl_basic_set
*aff_zero_basic_set(__isl_take isl_aff
*aff
,
2172 isl_constraint
*ineq
;
2173 isl_basic_set
*bset
;
2177 if (isl_aff_is_nan(aff
)) {
2178 isl_space
*space
= isl_aff_get_domain_space(aff
);
2180 return isl_basic_set_empty(space
);
2183 ineq
= isl_equality_from_aff(aff
);
2185 bset
= isl_basic_set_from_constraint(ineq
);
2187 bset
= isl_basic_set_set_rational(bset
);
2188 bset
= isl_basic_set_simplify(bset
);
2192 /* Return a basic set containing those elements in the space
2193 * of aff where it is zero.
2195 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
2197 return aff_zero_basic_set(aff
, 0);
2200 /* Return a basic set containing those elements in the shared space
2201 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
2203 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
2204 __isl_take isl_aff
*aff2
)
2206 aff1
= isl_aff_sub(aff1
, aff2
);
2208 return isl_aff_nonneg_basic_set(aff1
);
2211 /* Return a basic set containing those elements in the shared space
2212 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
2214 __isl_give isl_basic_set
*isl_aff_le_basic_set(__isl_take isl_aff
*aff1
,
2215 __isl_take isl_aff
*aff2
)
2217 return isl_aff_ge_basic_set(aff2
, aff1
);
2220 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
2221 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
2223 aff1
= isl_aff_add(aff1
, aff2
);
2224 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
2228 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
2236 /* Check whether the given affine expression has non-zero coefficient
2237 * for any dimension in the given range or if any of these dimensions
2238 * appear with non-zero coefficients in any of the integer divisions
2239 * involved in the affine expression.
2241 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
2242 enum isl_dim_type type
, unsigned first
, unsigned n
)
2254 ctx
= isl_aff_get_ctx(aff
);
2255 if (first
+ n
> isl_aff_dim(aff
, type
))
2256 isl_die(ctx
, isl_error_invalid
,
2257 "range out of bounds", return -1);
2259 active
= isl_local_space_get_active(aff
->ls
, aff
->v
->el
+ 2);
2263 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
2264 for (i
= 0; i
< n
; ++i
)
2265 if (active
[first
+ i
]) {
2278 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
2279 enum isl_dim_type type
, unsigned first
, unsigned n
)
2285 if (type
== isl_dim_out
)
2286 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2287 "cannot drop output/set dimension",
2288 return isl_aff_free(aff
));
2289 if (type
== isl_dim_in
)
2291 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
2294 ctx
= isl_aff_get_ctx(aff
);
2295 if (first
+ n
> isl_local_space_dim(aff
->ls
, type
))
2296 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
2297 return isl_aff_free(aff
));
2299 aff
= isl_aff_cow(aff
);
2303 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
2305 return isl_aff_free(aff
);
2307 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2308 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
2310 return isl_aff_free(aff
);
2315 /* Project the domain of the affine expression onto its parameter space.
2316 * The affine expression may not involve any of the domain dimensions.
2318 __isl_give isl_aff
*isl_aff_project_domain_on_params(__isl_take isl_aff
*aff
)
2324 n
= isl_aff_dim(aff
, isl_dim_in
);
2325 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, 0, n
);
2327 return isl_aff_free(aff
);
2329 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2330 "affine expression involves some of the domain dimensions",
2331 return isl_aff_free(aff
));
2332 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, 0, n
);
2333 space
= isl_aff_get_domain_space(aff
);
2334 space
= isl_space_params(space
);
2335 aff
= isl_aff_reset_domain_space(aff
, space
);
2339 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
2340 enum isl_dim_type type
, unsigned first
, unsigned n
)
2346 if (type
== isl_dim_out
)
2347 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2348 "cannot insert output/set dimensions",
2349 return isl_aff_free(aff
));
2350 if (type
== isl_dim_in
)
2352 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
2355 ctx
= isl_aff_get_ctx(aff
);
2356 if (first
> isl_local_space_dim(aff
->ls
, type
))
2357 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
2358 return isl_aff_free(aff
));
2360 aff
= isl_aff_cow(aff
);
2364 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
2366 return isl_aff_free(aff
);
2368 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2369 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
2371 return isl_aff_free(aff
);
2376 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
2377 enum isl_dim_type type
, unsigned n
)
2381 pos
= isl_aff_dim(aff
, type
);
2383 return isl_aff_insert_dims(aff
, type
, pos
, n
);
2386 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
2387 enum isl_dim_type type
, unsigned n
)
2391 pos
= isl_pw_aff_dim(pwaff
, type
);
2393 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
2396 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "aff"
2397 * to dimensions of "dst_type" at "dst_pos".
2399 * We only support moving input dimensions to parameters and vice versa.
2401 __isl_give isl_aff
*isl_aff_move_dims(__isl_take isl_aff
*aff
,
2402 enum isl_dim_type dst_type
, unsigned dst_pos
,
2403 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
2411 !isl_local_space_is_named_or_nested(aff
->ls
, src_type
) &&
2412 !isl_local_space_is_named_or_nested(aff
->ls
, dst_type
))
2415 if (dst_type
== isl_dim_out
|| src_type
== isl_dim_out
)
2416 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2417 "cannot move output/set dimension",
2418 return isl_aff_free(aff
));
2419 if (dst_type
== isl_dim_div
|| src_type
== isl_dim_div
)
2420 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2421 "cannot move divs", return isl_aff_free(aff
));
2422 if (dst_type
== isl_dim_in
)
2423 dst_type
= isl_dim_set
;
2424 if (src_type
== isl_dim_in
)
2425 src_type
= isl_dim_set
;
2427 if (src_pos
+ n
> isl_local_space_dim(aff
->ls
, src_type
))
2428 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2429 "range out of bounds", return isl_aff_free(aff
));
2430 if (dst_type
== src_type
)
2431 isl_die(isl_aff_get_ctx(aff
), isl_error_unsupported
,
2432 "moving dims within the same type not supported",
2433 return isl_aff_free(aff
));
2435 aff
= isl_aff_cow(aff
);
2439 g_src_pos
= 1 + isl_local_space_offset(aff
->ls
, src_type
) + src_pos
;
2440 g_dst_pos
= 1 + isl_local_space_offset(aff
->ls
, dst_type
) + dst_pos
;
2441 if (dst_type
> src_type
)
2444 aff
->v
= isl_vec_move_els(aff
->v
, g_dst_pos
, g_src_pos
, n
);
2445 aff
->ls
= isl_local_space_move_dims(aff
->ls
, dst_type
, dst_pos
,
2446 src_type
, src_pos
, n
);
2447 if (!aff
->v
|| !aff
->ls
)
2448 return isl_aff_free(aff
);
2450 aff
= sort_divs(aff
);
2455 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
2457 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
2458 return isl_pw_aff_alloc(dom
, aff
);
2462 #define PW isl_pw_aff
2466 #define EL_IS_ZERO is_empty
2470 #define IS_ZERO is_empty
2473 #undef DEFAULT_IS_ZERO
2474 #define DEFAULT_IS_ZERO 0
2481 #include <isl_pw_templ.c>
2483 static __isl_give isl_set
*align_params_pw_pw_set_and(
2484 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
2485 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2486 __isl_take isl_pw_aff
*pwaff2
))
2488 if (!pwaff1
|| !pwaff2
)
2490 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
2491 pwaff2
->dim
, isl_dim_param
))
2492 return fn(pwaff1
, pwaff2
);
2493 if (!isl_space_has_named_params(pwaff1
->dim
) ||
2494 !isl_space_has_named_params(pwaff2
->dim
))
2495 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
2496 "unaligned unnamed parameters", goto error
);
2497 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
2498 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
2499 return fn(pwaff1
, pwaff2
);
2501 isl_pw_aff_free(pwaff1
);
2502 isl_pw_aff_free(pwaff2
);
2506 /* Compute a piecewise quasi-affine expression with a domain that
2507 * is the union of those of pwaff1 and pwaff2 and such that on each
2508 * cell, the quasi-affine expression is the better (according to cmp)
2509 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
2510 * is defined on a given cell, then the associated expression
2511 * is the defined one.
2513 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2514 __isl_take isl_pw_aff
*pwaff2
,
2515 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
2516 __isl_take isl_aff
*aff2
))
2523 if (!pwaff1
|| !pwaff2
)
2526 ctx
= isl_space_get_ctx(pwaff1
->dim
);
2527 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
2528 isl_die(ctx
, isl_error_invalid
,
2529 "arguments should live in same space", goto error
);
2531 if (isl_pw_aff_is_empty(pwaff1
)) {
2532 isl_pw_aff_free(pwaff1
);
2536 if (isl_pw_aff_is_empty(pwaff2
)) {
2537 isl_pw_aff_free(pwaff2
);
2541 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
2542 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
2544 for (i
= 0; i
< pwaff1
->n
; ++i
) {
2545 set
= isl_set_copy(pwaff1
->p
[i
].set
);
2546 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2547 struct isl_set
*common
;
2550 common
= isl_set_intersect(
2551 isl_set_copy(pwaff1
->p
[i
].set
),
2552 isl_set_copy(pwaff2
->p
[j
].set
));
2553 better
= isl_set_from_basic_set(cmp(
2554 isl_aff_copy(pwaff2
->p
[j
].aff
),
2555 isl_aff_copy(pwaff1
->p
[i
].aff
)));
2556 better
= isl_set_intersect(common
, better
);
2557 if (isl_set_plain_is_empty(better
)) {
2558 isl_set_free(better
);
2561 set
= isl_set_subtract(set
, isl_set_copy(better
));
2563 res
= isl_pw_aff_add_piece(res
, better
,
2564 isl_aff_copy(pwaff2
->p
[j
].aff
));
2566 res
= isl_pw_aff_add_piece(res
, set
,
2567 isl_aff_copy(pwaff1
->p
[i
].aff
));
2570 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2571 set
= isl_set_copy(pwaff2
->p
[j
].set
);
2572 for (i
= 0; i
< pwaff1
->n
; ++i
)
2573 set
= isl_set_subtract(set
,
2574 isl_set_copy(pwaff1
->p
[i
].set
));
2575 res
= isl_pw_aff_add_piece(res
, set
,
2576 isl_aff_copy(pwaff2
->p
[j
].aff
));
2579 isl_pw_aff_free(pwaff1
);
2580 isl_pw_aff_free(pwaff2
);
2584 isl_pw_aff_free(pwaff1
);
2585 isl_pw_aff_free(pwaff2
);
2589 /* Compute a piecewise quasi-affine expression with a domain that
2590 * is the union of those of pwaff1 and pwaff2 and such that on each
2591 * cell, the quasi-affine expression is the maximum of those of pwaff1
2592 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2593 * cell, then the associated expression is the defined one.
2595 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2596 __isl_take isl_pw_aff
*pwaff2
)
2598 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
2601 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2602 __isl_take isl_pw_aff
*pwaff2
)
2604 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2608 /* Compute a piecewise quasi-affine expression with a domain that
2609 * is the union of those of pwaff1 and pwaff2 and such that on each
2610 * cell, the quasi-affine expression is the minimum of those of pwaff1
2611 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2612 * cell, then the associated expression is the defined one.
2614 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2615 __isl_take isl_pw_aff
*pwaff2
)
2617 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
2620 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2621 __isl_take isl_pw_aff
*pwaff2
)
2623 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2627 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2628 __isl_take isl_pw_aff
*pwaff2
, int max
)
2631 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
2633 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
2636 /* Construct a map with as domain the domain of pwaff and
2637 * one-dimensional range corresponding to the affine expressions.
2639 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2648 dim
= isl_pw_aff_get_space(pwaff
);
2649 map
= isl_map_empty(dim
);
2651 for (i
= 0; i
< pwaff
->n
; ++i
) {
2652 isl_basic_map
*bmap
;
2655 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
2656 map_i
= isl_map_from_basic_map(bmap
);
2657 map_i
= isl_map_intersect_domain(map_i
,
2658 isl_set_copy(pwaff
->p
[i
].set
));
2659 map
= isl_map_union_disjoint(map
, map_i
);
2662 isl_pw_aff_free(pwaff
);
2667 /* Construct a map with as domain the domain of pwaff and
2668 * one-dimensional range corresponding to the affine expressions.
2670 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2674 if (isl_space_is_set(pwaff
->dim
))
2675 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2676 "space of input is not a map", goto error
);
2677 return map_from_pw_aff(pwaff
);
2679 isl_pw_aff_free(pwaff
);
2683 /* Construct a one-dimensional set with as parameter domain
2684 * the domain of pwaff and the single set dimension
2685 * corresponding to the affine expressions.
2687 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2691 if (!isl_space_is_set(pwaff
->dim
))
2692 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2693 "space of input is not a set", goto error
);
2694 return map_from_pw_aff(pwaff
);
2696 isl_pw_aff_free(pwaff
);
2700 /* Return a set containing those elements in the domain
2701 * of pwaff where it is non-negative.
2703 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
2711 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2713 for (i
= 0; i
< pwaff
->n
; ++i
) {
2714 isl_basic_set
*bset
;
2718 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2719 bset
= aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2721 set_i
= isl_set_from_basic_set(bset
);
2722 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
2723 set
= isl_set_union_disjoint(set
, set_i
);
2726 isl_pw_aff_free(pwaff
);
2731 /* Return a set containing those elements in the domain
2732 * of pwaff where it is zero (if complement is 0) or not zero
2733 * (if complement is 1).
2735 * The pieces with a NaN never belong to the result since
2736 * NaN is neither zero nor non-zero.
2738 static __isl_give isl_set
*pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
,
2747 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2749 for (i
= 0; i
< pwaff
->n
; ++i
) {
2750 isl_basic_set
*bset
;
2751 isl_set
*set_i
, *zero
;
2754 if (isl_aff_is_nan(pwaff
->p
[i
].aff
))
2757 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2758 bset
= aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2760 zero
= isl_set_from_basic_set(bset
);
2761 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
2763 set_i
= isl_set_subtract(set_i
, zero
);
2765 set_i
= isl_set_intersect(set_i
, zero
);
2766 set
= isl_set_union_disjoint(set
, set_i
);
2769 isl_pw_aff_free(pwaff
);
2774 /* Return a set containing those elements in the domain
2775 * of pwaff where it is zero.
2777 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
2779 return pw_aff_zero_set(pwaff
, 0);
2782 /* Return a set containing those elements in the domain
2783 * of pwaff where it is not zero.
2785 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
2787 return pw_aff_zero_set(pwaff
, 1);
2790 /* Return a set containing those elements in the shared domain
2791 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2793 * We compute the difference on the shared domain and then construct
2794 * the set of values where this difference is non-negative.
2795 * If strict is set, we first subtract 1 from the difference.
2796 * If equal is set, we only return the elements where pwaff1 and pwaff2
2799 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
2800 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
2802 isl_set
*set1
, *set2
;
2804 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
2805 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
2806 set1
= isl_set_intersect(set1
, set2
);
2807 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
2808 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
2809 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
2812 isl_space
*dim
= isl_set_get_space(set1
);
2814 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2815 aff
= isl_aff_add_constant_si(aff
, -1);
2816 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
2821 return isl_pw_aff_zero_set(pwaff1
);
2822 return isl_pw_aff_nonneg_set(pwaff1
);
2825 /* Return a set containing those elements in the shared domain
2826 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2828 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2829 __isl_take isl_pw_aff
*pwaff2
)
2831 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
2834 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2835 __isl_take isl_pw_aff
*pwaff2
)
2837 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2840 /* Return a set containing those elements in the shared domain
2841 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2843 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2844 __isl_take isl_pw_aff
*pwaff2
)
2846 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2849 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2850 __isl_take isl_pw_aff
*pwaff2
)
2852 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2855 /* Return a set containing those elements in the shared domain
2856 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2858 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2859 __isl_take isl_pw_aff
*pwaff2
)
2861 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2864 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2865 __isl_take isl_pw_aff
*pwaff2
)
2867 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2870 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2871 __isl_take isl_pw_aff
*pwaff2
)
2873 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2876 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2877 __isl_take isl_pw_aff
*pwaff2
)
2879 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2882 /* Return a set containing those elements in the shared domain
2883 * of the elements of list1 and list2 where each element in list1
2884 * has the relation specified by "fn" with each element in list2.
2886 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2887 __isl_take isl_pw_aff_list
*list2
,
2888 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2889 __isl_take isl_pw_aff
*pwaff2
))
2895 if (!list1
|| !list2
)
2898 ctx
= isl_pw_aff_list_get_ctx(list1
);
2899 if (list1
->n
< 1 || list2
->n
< 1)
2900 isl_die(ctx
, isl_error_invalid
,
2901 "list should contain at least one element", goto error
);
2903 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2904 for (i
= 0; i
< list1
->n
; ++i
)
2905 for (j
= 0; j
< list2
->n
; ++j
) {
2908 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2909 isl_pw_aff_copy(list2
->p
[j
]));
2910 set
= isl_set_intersect(set
, set_ij
);
2913 isl_pw_aff_list_free(list1
);
2914 isl_pw_aff_list_free(list2
);
2917 isl_pw_aff_list_free(list1
);
2918 isl_pw_aff_list_free(list2
);
2922 /* Return a set containing those elements in the shared domain
2923 * of the elements of list1 and list2 where each element in list1
2924 * is equal to each element in list2.
2926 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2927 __isl_take isl_pw_aff_list
*list2
)
2929 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
2932 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
2933 __isl_take isl_pw_aff_list
*list2
)
2935 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
2938 /* Return a set containing those elements in the shared domain
2939 * of the elements of list1 and list2 where each element in list1
2940 * is less than or equal to each element in list2.
2942 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
2943 __isl_take isl_pw_aff_list
*list2
)
2945 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
2948 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
2949 __isl_take isl_pw_aff_list
*list2
)
2951 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
2954 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
2955 __isl_take isl_pw_aff_list
*list2
)
2957 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
2960 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
2961 __isl_take isl_pw_aff_list
*list2
)
2963 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
2967 /* Return a set containing those elements in the shared domain
2968 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2970 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2971 __isl_take isl_pw_aff
*pwaff2
)
2973 isl_set
*set_lt
, *set_gt
;
2975 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
2976 isl_pw_aff_copy(pwaff2
));
2977 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
2978 return isl_set_union_disjoint(set_lt
, set_gt
);
2981 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2982 __isl_take isl_pw_aff
*pwaff2
)
2984 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
2987 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
2992 if (isl_int_is_one(v
))
2994 if (!isl_int_is_pos(v
))
2995 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2996 "factor needs to be positive",
2997 return isl_pw_aff_free(pwaff
));
2998 pwaff
= isl_pw_aff_cow(pwaff
);
3004 for (i
= 0; i
< pwaff
->n
; ++i
) {
3005 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
3006 if (!pwaff
->p
[i
].aff
)
3007 return isl_pw_aff_free(pwaff
);
3013 /* Divide "pa" by "f".
3015 __isl_give isl_pw_aff
*isl_pw_aff_scale_down_val(__isl_take isl_pw_aff
*pa
,
3016 __isl_take isl_val
*f
)
3023 if (isl_val_is_one(f
)) {
3028 if (!isl_val_is_rat(f
))
3029 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3030 "expecting rational factor", goto error
);
3031 if (!isl_val_is_pos(f
))
3032 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3033 "factor needs to be positive", goto error
);
3035 pa
= isl_pw_aff_cow(pa
);
3041 for (i
= 0; i
< pa
->n
; ++i
) {
3042 pa
->p
[i
].aff
= isl_aff_scale_down_val(pa
->p
[i
].aff
,
3051 isl_pw_aff_free(pa
);
3056 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
3060 pwaff
= isl_pw_aff_cow(pwaff
);
3066 for (i
= 0; i
< pwaff
->n
; ++i
) {
3067 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
3068 if (!pwaff
->p
[i
].aff
)
3069 return isl_pw_aff_free(pwaff
);
3075 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
3079 pwaff
= isl_pw_aff_cow(pwaff
);
3085 for (i
= 0; i
< pwaff
->n
; ++i
) {
3086 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
3087 if (!pwaff
->p
[i
].aff
)
3088 return isl_pw_aff_free(pwaff
);
3094 /* Assuming that "cond1" and "cond2" are disjoint,
3095 * return an affine expression that is equal to pwaff1 on cond1
3096 * and to pwaff2 on cond2.
3098 static __isl_give isl_pw_aff
*isl_pw_aff_select(
3099 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
3100 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
3102 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
3103 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
3105 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
3108 /* Return an affine expression that is equal to pwaff_true for elements
3109 * where "cond" is non-zero and to pwaff_false for elements where "cond"
3111 * That is, return cond ? pwaff_true : pwaff_false;
3113 * If "cond" involves and NaN, then we conservatively return a NaN
3114 * on its entire domain. In principle, we could consider the pieces
3115 * where it is NaN separately from those where it is not.
3117 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
3118 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
3120 isl_set
*cond_true
, *cond_false
;
3124 if (isl_pw_aff_involves_nan(cond
)) {
3125 isl_space
*space
= isl_pw_aff_get_domain_space(cond
);
3126 isl_local_space
*ls
= isl_local_space_from_space(space
);
3127 isl_pw_aff_free(cond
);
3128 isl_pw_aff_free(pwaff_true
);
3129 isl_pw_aff_free(pwaff_false
);
3130 return isl_pw_aff_nan_on_domain(ls
);
3133 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
3134 cond_false
= isl_pw_aff_zero_set(cond
);
3135 return isl_pw_aff_select(cond_true
, pwaff_true
,
3136 cond_false
, pwaff_false
);
3138 isl_pw_aff_free(cond
);
3139 isl_pw_aff_free(pwaff_true
);
3140 isl_pw_aff_free(pwaff_false
);
3144 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
3149 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
3152 /* Check whether pwaff is a piecewise constant.
3154 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
3161 for (i
= 0; i
< pwaff
->n
; ++i
) {
3162 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
3163 if (is_cst
< 0 || !is_cst
)
3170 /* Return the product of "aff1" and "aff2".
3172 * If either of the two is NaN, then the result is NaN.
3174 * Otherwise, at least one of "aff1" or "aff2" needs to be a constant.
3176 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
3177 __isl_take isl_aff
*aff2
)
3182 if (isl_aff_is_nan(aff1
)) {
3186 if (isl_aff_is_nan(aff2
)) {
3191 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
3192 return isl_aff_mul(aff2
, aff1
);
3194 if (!isl_aff_is_cst(aff2
))
3195 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
3196 "at least one affine expression should be constant",
3199 aff1
= isl_aff_cow(aff1
);
3203 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
3204 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
3214 /* Divide "aff1" by "aff2", assuming "aff2" is a constant.
3216 * If either of the two is NaN, then the result is NaN.
3218 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
3219 __isl_take isl_aff
*aff2
)
3227 if (isl_aff_is_nan(aff1
)) {
3231 if (isl_aff_is_nan(aff2
)) {
3236 is_cst
= isl_aff_is_cst(aff2
);
3240 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
3241 "second argument should be a constant", goto error
);
3246 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
3248 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
3249 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
3252 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
3253 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
3256 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
3257 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
3268 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
3269 __isl_take isl_pw_aff
*pwaff2
)
3271 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
3274 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
3275 __isl_take isl_pw_aff
*pwaff2
)
3277 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
3280 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
3281 __isl_take isl_pw_aff
*pwaff2
)
3283 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
3286 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
3287 __isl_take isl_pw_aff
*pwaff2
)
3289 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
3292 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
3293 __isl_take isl_pw_aff
*pwaff2
)
3295 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
3298 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
3299 __isl_take isl_pw_aff
*pa2
)
3301 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
3304 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
3306 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
3307 __isl_take isl_pw_aff
*pa2
)
3311 is_cst
= isl_pw_aff_is_cst(pa2
);
3315 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3316 "second argument should be a piecewise constant",
3318 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
3320 isl_pw_aff_free(pa1
);
3321 isl_pw_aff_free(pa2
);
3325 /* Compute the quotient of the integer division of "pa1" by "pa2"
3326 * with rounding towards zero.
3327 * "pa2" is assumed to be a piecewise constant.
3329 * In particular, return
3331 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
3334 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
3335 __isl_take isl_pw_aff
*pa2
)
3341 is_cst
= isl_pw_aff_is_cst(pa2
);
3345 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3346 "second argument should be a piecewise constant",
3349 pa1
= isl_pw_aff_div(pa1
, pa2
);
3351 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
3352 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
3353 c
= isl_pw_aff_ceil(pa1
);
3354 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
3356 isl_pw_aff_free(pa1
);
3357 isl_pw_aff_free(pa2
);
3361 /* Compute the remainder of the integer division of "pa1" by "pa2"
3362 * with rounding towards zero.
3363 * "pa2" is assumed to be a piecewise constant.
3365 * In particular, return
3367 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
3370 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
3371 __isl_take isl_pw_aff
*pa2
)
3376 is_cst
= isl_pw_aff_is_cst(pa2
);
3380 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3381 "second argument should be a piecewise constant",
3383 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
3384 res
= isl_pw_aff_mul(pa2
, res
);
3385 res
= isl_pw_aff_sub(pa1
, res
);
3388 isl_pw_aff_free(pa1
);
3389 isl_pw_aff_free(pa2
);
3393 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
3394 __isl_take isl_pw_aff
*pwaff2
)
3399 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
3400 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
3401 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
3402 isl_pw_aff_copy(pwaff2
));
3403 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
3404 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
3407 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
3408 __isl_take isl_pw_aff
*pwaff2
)
3410 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
3413 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3414 __isl_take isl_pw_aff
*pwaff2
)
3419 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
3420 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
3421 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
3422 isl_pw_aff_copy(pwaff2
));
3423 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
3424 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
3427 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3428 __isl_take isl_pw_aff
*pwaff2
)
3430 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
3433 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
3434 __isl_take isl_pw_aff_list
*list
,
3435 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
3436 __isl_take isl_pw_aff
*pwaff2
))
3445 ctx
= isl_pw_aff_list_get_ctx(list
);
3447 isl_die(ctx
, isl_error_invalid
,
3448 "list should contain at least one element", goto error
);
3450 res
= isl_pw_aff_copy(list
->p
[0]);
3451 for (i
= 1; i
< list
->n
; ++i
)
3452 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
3454 isl_pw_aff_list_free(list
);
3457 isl_pw_aff_list_free(list
);
3461 /* Return an isl_pw_aff that maps each element in the intersection of the
3462 * domains of the elements of list to the minimal corresponding affine
3465 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
3467 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
3470 /* Return an isl_pw_aff that maps each element in the intersection of the
3471 * domains of the elements of list to the maximal corresponding affine
3474 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
3476 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
3479 /* Mark the domains of "pwaff" as rational.
3481 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__isl_take isl_pw_aff
*pwaff
)
3485 pwaff
= isl_pw_aff_cow(pwaff
);
3491 for (i
= 0; i
< pwaff
->n
; ++i
) {
3492 pwaff
->p
[i
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
3493 if (!pwaff
->p
[i
].set
)
3494 return isl_pw_aff_free(pwaff
);
3500 /* Mark the domains of the elements of "list" as rational.
3502 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
3503 __isl_take isl_pw_aff_list
*list
)
3513 for (i
= 0; i
< n
; ++i
) {
3516 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
3517 pa
= isl_pw_aff_set_rational(pa
);
3518 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
3524 /* Do the parameters of "aff" match those of "space"?
3526 int isl_aff_matching_params(__isl_keep isl_aff
*aff
,
3527 __isl_keep isl_space
*space
)
3529 isl_space
*aff_space
;
3535 aff_space
= isl_aff_get_domain_space(aff
);
3537 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3539 isl_space_free(aff_space
);
3543 /* Check that the domain space of "aff" matches "space".
3545 * Return 0 on success and -1 on error.
3547 int isl_aff_check_match_domain_space(__isl_keep isl_aff
*aff
,
3548 __isl_keep isl_space
*space
)
3550 isl_space
*aff_space
;
3556 aff_space
= isl_aff_get_domain_space(aff
);
3558 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3562 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3563 "parameters don't match", goto error
);
3564 match
= isl_space_tuple_is_equal(space
, isl_dim_in
,
3565 aff_space
, isl_dim_set
);
3569 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3570 "domains don't match", goto error
);
3571 isl_space_free(aff_space
);
3574 isl_space_free(aff_space
);
3580 #define NO_INTERSECT_DOMAIN
3583 #include <isl_multi_templ.c>
3586 #undef NO_INTERSECT_DOMAIN
3588 /* Remove any internal structure of the domain of "ma".
3589 * If there is any such internal structure in the input,
3590 * then the name of the corresponding space is also removed.
3592 __isl_give isl_multi_aff
*isl_multi_aff_flatten_domain(
3593 __isl_take isl_multi_aff
*ma
)
3600 if (!ma
->space
->nested
[0])
3603 space
= isl_multi_aff_get_space(ma
);
3604 space
= isl_space_flatten_domain(space
);
3605 ma
= isl_multi_aff_reset_space(ma
, space
);
3610 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3611 * of the space to its domain.
3613 __isl_give isl_multi_aff
*isl_multi_aff_domain_map(__isl_take isl_space
*space
)
3616 isl_local_space
*ls
;
3621 if (!isl_space_is_map(space
))
3622 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3623 "not a map space", goto error
);
3625 n_in
= isl_space_dim(space
, isl_dim_in
);
3626 space
= isl_space_domain_map(space
);
3628 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3630 isl_space_free(space
);
3634 space
= isl_space_domain(space
);
3635 ls
= isl_local_space_from_space(space
);
3636 for (i
= 0; i
< n_in
; ++i
) {
3639 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3641 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3643 isl_local_space_free(ls
);
3646 isl_space_free(space
);
3650 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3651 * of the space to its range.
3653 __isl_give isl_multi_aff
*isl_multi_aff_range_map(__isl_take isl_space
*space
)
3656 isl_local_space
*ls
;
3661 if (!isl_space_is_map(space
))
3662 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3663 "not a map space", goto error
);
3665 n_in
= isl_space_dim(space
, isl_dim_in
);
3666 n_out
= isl_space_dim(space
, isl_dim_out
);
3667 space
= isl_space_range_map(space
);
3669 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3671 isl_space_free(space
);
3675 space
= isl_space_domain(space
);
3676 ls
= isl_local_space_from_space(space
);
3677 for (i
= 0; i
< n_out
; ++i
) {
3680 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3681 isl_dim_set
, n_in
+ i
);
3682 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3684 isl_local_space_free(ls
);
3687 isl_space_free(space
);
3691 /* Given the space of a set and a range of set dimensions,
3692 * construct an isl_multi_aff that projects out those dimensions.
3694 __isl_give isl_multi_aff
*isl_multi_aff_project_out_map(
3695 __isl_take isl_space
*space
, enum isl_dim_type type
,
3696 unsigned first
, unsigned n
)
3699 isl_local_space
*ls
;
3704 if (!isl_space_is_set(space
))
3705 isl_die(isl_space_get_ctx(space
), isl_error_unsupported
,
3706 "expecting set space", goto error
);
3707 if (type
!= isl_dim_set
)
3708 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3709 "only set dimensions can be projected out", goto error
);
3711 dim
= isl_space_dim(space
, isl_dim_set
);
3712 if (first
+ n
> dim
)
3713 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3714 "range out of bounds", goto error
);
3716 space
= isl_space_from_domain(space
);
3717 space
= isl_space_add_dims(space
, isl_dim_out
, dim
- n
);
3720 return isl_multi_aff_alloc(space
);
3722 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3723 space
= isl_space_domain(space
);
3724 ls
= isl_local_space_from_space(space
);
3726 for (i
= 0; i
< first
; ++i
) {
3729 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3731 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3734 for (i
= 0; i
< dim
- (first
+ n
); ++i
) {
3737 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3738 isl_dim_set
, first
+ n
+ i
);
3739 ma
= isl_multi_aff_set_aff(ma
, first
+ i
, aff
);
3742 isl_local_space_free(ls
);
3745 isl_space_free(space
);
3749 /* Given the space of a set and a range of set dimensions,
3750 * construct an isl_pw_multi_aff that projects out those dimensions.
3752 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_project_out_map(
3753 __isl_take isl_space
*space
, enum isl_dim_type type
,
3754 unsigned first
, unsigned n
)
3758 ma
= isl_multi_aff_project_out_map(space
, type
, first
, n
);
3759 return isl_pw_multi_aff_from_multi_aff(ma
);
3762 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
3765 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
3766 __isl_take isl_multi_aff
*ma
)
3768 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
3769 return isl_pw_multi_aff_alloc(dom
, ma
);
3772 /* Create a piecewise multi-affine expression in the given space that maps each
3773 * input dimension to the corresponding output dimension.
3775 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
3776 __isl_take isl_space
*space
)
3778 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
3781 /* Add "ma2" to "ma1" and return the result.
3783 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
3785 static __isl_give isl_multi_aff
*isl_multi_aff_add_aligned(
3786 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3788 return isl_multi_aff_bin_op(maff1
, maff2
, &isl_aff_add
);
3791 /* Add "ma2" to "ma1" and return the result.
3793 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*ma1
,
3794 __isl_take isl_multi_aff
*ma2
)
3796 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
3797 &isl_multi_aff_add_aligned
);
3800 /* Subtract "ma2" from "ma1" and return the result.
3802 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
3804 static __isl_give isl_multi_aff
*isl_multi_aff_sub_aligned(
3805 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
3807 return isl_multi_aff_bin_op(ma1
, ma2
, &isl_aff_sub
);
3810 /* Subtract "ma2" from "ma1" and return the result.
3812 __isl_give isl_multi_aff
*isl_multi_aff_sub(__isl_take isl_multi_aff
*ma1
,
3813 __isl_take isl_multi_aff
*ma2
)
3815 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
3816 &isl_multi_aff_sub_aligned
);
3819 /* Exploit the equalities in "eq" to simplify the affine expressions.
3821 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
3822 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
3826 maff
= isl_multi_aff_cow(maff
);
3830 for (i
= 0; i
< maff
->n
; ++i
) {
3831 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
3832 isl_basic_set_copy(eq
));
3837 isl_basic_set_free(eq
);
3840 isl_basic_set_free(eq
);
3841 isl_multi_aff_free(maff
);
3845 /* Given f, return floor(f).
3847 __isl_give isl_multi_aff
*isl_multi_aff_floor(__isl_take isl_multi_aff
*ma
)
3851 ma
= isl_multi_aff_cow(ma
);
3855 for (i
= 0; i
< ma
->n
; ++i
) {
3856 ma
->p
[i
] = isl_aff_floor(ma
->p
[i
]);
3858 return isl_multi_aff_free(ma
);
3864 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
3869 maff
= isl_multi_aff_cow(maff
);
3873 for (i
= 0; i
< maff
->n
; ++i
) {
3874 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
3876 return isl_multi_aff_free(maff
);
3882 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
3883 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3885 maff1
= isl_multi_aff_add(maff1
, maff2
);
3886 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
3890 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
3898 /* Return the set of domain elements where "ma1" is lexicographically
3899 * smaller than or equal to "ma2".
3901 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
3902 __isl_take isl_multi_aff
*ma2
)
3904 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
3907 /* Return the set of domain elements where "ma1" is lexicographically
3908 * greater than or equal to "ma2".
3910 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
3911 __isl_take isl_multi_aff
*ma2
)
3914 isl_map
*map1
, *map2
;
3917 map1
= isl_map_from_multi_aff(ma1
);
3918 map2
= isl_map_from_multi_aff(ma2
);
3919 map
= isl_map_range_product(map1
, map2
);
3920 space
= isl_space_range(isl_map_get_space(map
));
3921 space
= isl_space_domain(isl_space_unwrap(space
));
3922 ge
= isl_map_lex_ge(space
);
3923 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
3925 return isl_map_domain(map
);
3929 #define PW isl_pw_multi_aff
3931 #define EL isl_multi_aff
3933 #define EL_IS_ZERO is_empty
3937 #define IS_ZERO is_empty
3940 #undef DEFAULT_IS_ZERO
3941 #define DEFAULT_IS_ZERO 0
3946 #define NO_INVOLVES_DIMS
3947 #define NO_INSERT_DIMS
3951 #include <isl_pw_templ.c>
3954 #define UNION isl_union_pw_multi_aff
3956 #define PART isl_pw_multi_aff
3958 #define PARTS pw_multi_aff
3959 #define ALIGN_DOMAIN
3963 #include <isl_union_templ.c>
3965 /* Given a function "cmp" that returns the set of elements where
3966 * "ma1" is "better" than "ma2", return the intersection of this
3967 * set with "dom1" and "dom2".
3969 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
3970 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
3971 __isl_keep isl_multi_aff
*ma2
,
3972 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3973 __isl_take isl_multi_aff
*ma2
))
3979 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
3980 is_empty
= isl_set_plain_is_empty(common
);
3981 if (is_empty
>= 0 && is_empty
)
3984 return isl_set_free(common
);
3985 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
3986 better
= isl_set_intersect(common
, better
);
3991 /* Given a function "cmp" that returns the set of elements where
3992 * "ma1" is "better" than "ma2", return a piecewise multi affine
3993 * expression defined on the union of the definition domains
3994 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
3995 * "pma2" on each cell. If only one of the two input functions
3996 * is defined on a given cell, then it is considered the best.
3998 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
3999 __isl_take isl_pw_multi_aff
*pma1
,
4000 __isl_take isl_pw_multi_aff
*pma2
,
4001 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
4002 __isl_take isl_multi_aff
*ma2
))
4005 isl_pw_multi_aff
*res
= NULL
;
4007 isl_set
*set
= NULL
;
4012 ctx
= isl_space_get_ctx(pma1
->dim
);
4013 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
4014 isl_die(ctx
, isl_error_invalid
,
4015 "arguments should live in the same space", goto error
);
4017 if (isl_pw_multi_aff_is_empty(pma1
)) {
4018 isl_pw_multi_aff_free(pma1
);
4022 if (isl_pw_multi_aff_is_empty(pma2
)) {
4023 isl_pw_multi_aff_free(pma2
);
4027 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
4028 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
4030 for (i
= 0; i
< pma1
->n
; ++i
) {
4031 set
= isl_set_copy(pma1
->p
[i
].set
);
4032 for (j
= 0; j
< pma2
->n
; ++j
) {
4036 better
= shared_and_better(pma2
->p
[j
].set
,
4037 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
4038 pma1
->p
[i
].maff
, cmp
);
4039 is_empty
= isl_set_plain_is_empty(better
);
4040 if (is_empty
< 0 || is_empty
) {
4041 isl_set_free(better
);
4046 set
= isl_set_subtract(set
, isl_set_copy(better
));
4048 res
= isl_pw_multi_aff_add_piece(res
, better
,
4049 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4051 res
= isl_pw_multi_aff_add_piece(res
, set
,
4052 isl_multi_aff_copy(pma1
->p
[i
].maff
));
4055 for (j
= 0; j
< pma2
->n
; ++j
) {
4056 set
= isl_set_copy(pma2
->p
[j
].set
);
4057 for (i
= 0; i
< pma1
->n
; ++i
)
4058 set
= isl_set_subtract(set
,
4059 isl_set_copy(pma1
->p
[i
].set
));
4060 res
= isl_pw_multi_aff_add_piece(res
, set
,
4061 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4064 isl_pw_multi_aff_free(pma1
);
4065 isl_pw_multi_aff_free(pma2
);
4069 isl_pw_multi_aff_free(pma1
);
4070 isl_pw_multi_aff_free(pma2
);
4072 return isl_pw_multi_aff_free(res
);
4075 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
4076 __isl_take isl_pw_multi_aff
*pma1
,
4077 __isl_take isl_pw_multi_aff
*pma2
)
4079 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
4082 /* Given two piecewise multi affine expressions, return a piecewise
4083 * multi-affine expression defined on the union of the definition domains
4084 * of the inputs that is equal to the lexicographic maximum of the two
4085 * inputs on each cell. If only one of the two inputs is defined on
4086 * a given cell, then it is considered to be the maximum.
4088 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
4089 __isl_take isl_pw_multi_aff
*pma1
,
4090 __isl_take isl_pw_multi_aff
*pma2
)
4092 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4093 &pw_multi_aff_union_lexmax
);
4096 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
4097 __isl_take isl_pw_multi_aff
*pma1
,
4098 __isl_take isl_pw_multi_aff
*pma2
)
4100 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
4103 /* Given two piecewise multi affine expressions, return a piecewise
4104 * multi-affine expression defined on the union of the definition domains
4105 * of the inputs that is equal to the lexicographic minimum of the two
4106 * inputs on each cell. If only one of the two inputs is defined on
4107 * a given cell, then it is considered to be the minimum.
4109 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
4110 __isl_take isl_pw_multi_aff
*pma1
,
4111 __isl_take isl_pw_multi_aff
*pma2
)
4113 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4114 &pw_multi_aff_union_lexmin
);
4117 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
4118 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4120 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
4121 &isl_multi_aff_add
);
4124 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
4125 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4127 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4131 static __isl_give isl_pw_multi_aff
*pw_multi_aff_sub(
4132 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4134 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
4135 &isl_multi_aff_sub
);
4138 /* Subtract "pma2" from "pma1" and return the result.
4140 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_sub(
4141 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4143 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4147 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
4148 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4150 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
4153 /* Given two piecewise multi-affine expressions A -> B and C -> D,
4154 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
4156 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
4157 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4161 isl_pw_multi_aff
*res
;
4166 n
= pma1
->n
* pma2
->n
;
4167 space
= isl_space_product(isl_space_copy(pma1
->dim
),
4168 isl_space_copy(pma2
->dim
));
4169 res
= isl_pw_multi_aff_alloc_size(space
, n
);
4171 for (i
= 0; i
< pma1
->n
; ++i
) {
4172 for (j
= 0; j
< pma2
->n
; ++j
) {
4176 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
4177 isl_set_copy(pma2
->p
[j
].set
));
4178 ma
= isl_multi_aff_product(
4179 isl_multi_aff_copy(pma1
->p
[i
].maff
),
4180 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4181 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
4185 isl_pw_multi_aff_free(pma1
);
4186 isl_pw_multi_aff_free(pma2
);
4189 isl_pw_multi_aff_free(pma1
);
4190 isl_pw_multi_aff_free(pma2
);
4194 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
4195 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4197 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4198 &pw_multi_aff_product
);
4201 /* Construct a map mapping the domain of the piecewise multi-affine expression
4202 * to its range, with each dimension in the range equated to the
4203 * corresponding affine expression on its cell.
4205 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
4213 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
4215 for (i
= 0; i
< pma
->n
; ++i
) {
4216 isl_multi_aff
*maff
;
4217 isl_basic_map
*bmap
;
4220 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
4221 bmap
= isl_basic_map_from_multi_aff(maff
);
4222 map_i
= isl_map_from_basic_map(bmap
);
4223 map_i
= isl_map_intersect_domain(map_i
,
4224 isl_set_copy(pma
->p
[i
].set
));
4225 map
= isl_map_union_disjoint(map
, map_i
);
4228 isl_pw_multi_aff_free(pma
);
4232 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
4237 if (!isl_space_is_set(pma
->dim
))
4238 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4239 "isl_pw_multi_aff cannot be converted into an isl_set",
4242 return isl_map_from_pw_multi_aff(pma
);
4244 isl_pw_multi_aff_free(pma
);
4248 /* Given a basic map with a single output dimension that is defined
4249 * in terms of the parameters and input dimensions using an equality,
4250 * extract an isl_aff that expresses the output dimension in terms
4251 * of the parameters and input dimensions.
4252 * Note that this expression may involve integer divisions defined
4253 * in terms of parameters and input dimensions.
4255 * This function shares some similarities with
4256 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
4258 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
4259 __isl_take isl_basic_map
*bmap
)
4264 isl_local_space
*ls
;
4269 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
4270 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
4271 "basic map should have a single output dimension",
4273 eq
= isl_basic_map_output_defining_equality(bmap
, 0);
4274 if (eq
>= bmap
->n_eq
)
4275 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
4276 "unable to find suitable equality", goto error
);
4277 ls
= isl_basic_map_get_local_space(bmap
);
4278 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
4281 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
4282 n_div
= isl_basic_map_dim(bmap
, isl_dim_div
);
4283 if (isl_int_is_neg(bmap
->eq
[eq
][offset
])) {
4284 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[eq
], offset
);
4285 isl_seq_cpy(aff
->v
->el
+ 1 + offset
, bmap
->eq
[eq
] + offset
+ 1,
4288 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[eq
], offset
);
4289 isl_seq_neg(aff
->v
->el
+ 1 + offset
, bmap
->eq
[eq
] + offset
+ 1,
4292 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[eq
][offset
]);
4293 isl_basic_map_free(bmap
);
4295 aff
= isl_aff_remove_unused_divs(aff
);
4298 isl_basic_map_free(bmap
);
4302 /* Given a basic map where each output dimension is defined
4303 * in terms of the parameters and input dimensions using an equality,
4304 * extract an isl_multi_aff that expresses the output dimensions in terms
4305 * of the parameters and input dimensions.
4307 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
4308 __isl_take isl_basic_map
*bmap
)
4317 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
4318 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
4320 for (i
= 0; i
< n_out
; ++i
) {
4321 isl_basic_map
*bmap_i
;
4324 bmap_i
= isl_basic_map_copy(bmap
);
4325 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
4326 i
+ 1, n_out
- (1 + i
));
4327 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
4328 aff
= extract_isl_aff_from_basic_map(bmap_i
);
4329 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4332 isl_basic_map_free(bmap
);
4337 /* Given a basic set where each set dimension is defined
4338 * in terms of the parameters using an equality,
4339 * extract an isl_multi_aff that expresses the set dimensions in terms
4340 * of the parameters.
4342 __isl_give isl_multi_aff
*isl_multi_aff_from_basic_set_equalities(
4343 __isl_take isl_basic_set
*bset
)
4345 return extract_isl_multi_aff_from_basic_map(bset
);
4348 /* Create an isl_pw_multi_aff that is equivalent to
4349 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
4350 * The given basic map is such that each output dimension is defined
4351 * in terms of the parameters and input dimensions using an equality.
4353 * Since some applications expect the result of isl_pw_multi_aff_from_map
4354 * to only contain integer affine expressions, we compute the floor
4355 * of the expression before returning.
4357 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
4358 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
4362 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
4363 ma
= isl_multi_aff_floor(ma
);
4364 return isl_pw_multi_aff_alloc(domain
, ma
);
4367 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4368 * This obviously only works if the input "map" is single-valued.
4369 * If so, we compute the lexicographic minimum of the image in the form
4370 * of an isl_pw_multi_aff. Since the image is unique, it is equal
4371 * to its lexicographic minimum.
4372 * If the input is not single-valued, we produce an error.
4374 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
4375 __isl_take isl_map
*map
)
4379 isl_pw_multi_aff
*pma
;
4381 sv
= isl_map_is_single_valued(map
);
4385 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
4386 "map is not single-valued", goto error
);
4387 map
= isl_map_make_disjoint(map
);
4391 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
4393 for (i
= 0; i
< map
->n
; ++i
) {
4394 isl_pw_multi_aff
*pma_i
;
4395 isl_basic_map
*bmap
;
4396 bmap
= isl_basic_map_copy(map
->p
[i
]);
4397 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
4398 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
4408 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4409 * taking into account that the output dimension at position "d"
4410 * can be represented as
4412 * x = floor((e(...) + c1) / m)
4414 * given that constraint "i" is of the form
4416 * e(...) + c1 - m x >= 0
4419 * Let "map" be of the form
4423 * We construct a mapping
4425 * A -> [A -> x = floor(...)]
4427 * apply that to the map, obtaining
4429 * [A -> x = floor(...)] -> B
4431 * and equate dimension "d" to x.
4432 * We then compute a isl_pw_multi_aff representation of the resulting map
4433 * and plug in the mapping above.
4435 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
4436 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
4440 isl_local_space
*ls
;
4448 isl_pw_multi_aff
*pma
;
4451 is_set
= isl_map_is_set(map
);
4453 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
4454 ctx
= isl_map_get_ctx(map
);
4455 space
= isl_space_domain(isl_map_get_space(map
));
4456 n_in
= isl_space_dim(space
, isl_dim_set
);
4457 n
= isl_space_dim(space
, isl_dim_all
);
4459 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
4461 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
4462 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
4464 isl_basic_map_free(hull
);
4466 ls
= isl_local_space_from_space(isl_space_copy(space
));
4467 aff
= isl_aff_alloc_vec(ls
, v
);
4468 aff
= isl_aff_floor(aff
);
4470 isl_space_free(space
);
4471 ma
= isl_multi_aff_from_aff(aff
);
4473 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
4474 ma
= isl_multi_aff_range_product(ma
,
4475 isl_multi_aff_from_aff(aff
));
4478 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
4479 map
= isl_map_apply_domain(map
, insert
);
4480 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
4481 pma
= isl_pw_multi_aff_from_map(map
);
4482 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
4487 /* Is constraint "c" of the form
4489 * e(...) + c1 - m x >= 0
4493 * -e(...) + c2 + m x >= 0
4495 * where m > 1 and e only depends on parameters and input dimemnsions?
4497 * "offset" is the offset of the output dimensions
4498 * "pos" is the position of output dimension x.
4500 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
4502 if (isl_int_is_zero(c
[offset
+ d
]))
4504 if (isl_int_is_one(c
[offset
+ d
]))
4506 if (isl_int_is_negone(c
[offset
+ d
]))
4508 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
4510 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
4511 total
- (offset
+ d
+ 1)) != -1)
4516 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4518 * As a special case, we first check if there is any pair of constraints,
4519 * shared by all the basic maps in "map" that force a given dimension
4520 * to be equal to the floor of some affine combination of the input dimensions.
4522 * In particular, if we can find two constraints
4524 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
4528 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
4530 * where m > 1 and e only depends on parameters and input dimemnsions,
4533 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
4535 * then we know that we can take
4537 * x = floor((e(...) + c1) / m)
4539 * without having to perform any computation.
4541 * Note that we know that
4545 * If c1 + c2 were 0, then we would have detected an equality during
4546 * simplification. If c1 + c2 were negative, then we would have detected
4549 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
4550 __isl_take isl_map
*map
)
4556 isl_basic_map
*hull
;
4558 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
4563 dim
= isl_map_dim(map
, isl_dim_out
);
4564 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
4565 total
= 1 + isl_basic_map_total_dim(hull
);
4567 for (d
= 0; d
< dim
; ++d
) {
4568 for (i
= 0; i
< n
; ++i
) {
4569 if (!is_potential_div_constraint(hull
->ineq
[i
],
4572 for (j
= i
+ 1; j
< n
; ++j
) {
4573 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
4574 hull
->ineq
[j
] + 1, total
- 1))
4576 isl_int_add(sum
, hull
->ineq
[i
][0],
4578 if (isl_int_abs_lt(sum
,
4579 hull
->ineq
[i
][offset
+ d
]))
4586 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
4588 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
4592 isl_basic_map_free(hull
);
4593 return pw_multi_aff_from_map_base(map
);
4596 isl_basic_map_free(hull
);
4600 /* Given an affine expression
4602 * [A -> B] -> f(A,B)
4604 * construct an isl_multi_aff
4608 * such that dimension "d" in B' is set to "aff" and the remaining
4609 * dimensions are set equal to the corresponding dimensions in B.
4610 * "n_in" is the dimension of the space A.
4611 * "n_out" is the dimension of the space B.
4613 * If "is_set" is set, then the affine expression is of the form
4617 * and we construct an isl_multi_aff
4621 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
4622 unsigned n_in
, unsigned n_out
, int is_set
)
4626 isl_space
*space
, *space2
;
4627 isl_local_space
*ls
;
4629 space
= isl_aff_get_domain_space(aff
);
4630 ls
= isl_local_space_from_space(isl_space_copy(space
));
4631 space2
= isl_space_copy(space
);
4633 space2
= isl_space_range(isl_space_unwrap(space2
));
4634 space
= isl_space_map_from_domain_and_range(space
, space2
);
4635 ma
= isl_multi_aff_alloc(space
);
4636 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
4638 for (i
= 0; i
< n_out
; ++i
) {
4641 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
4642 isl_dim_set
, n_in
+ i
);
4643 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4646 isl_local_space_free(ls
);
4651 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4652 * taking into account that the dimension at position "d" can be written as
4654 * x = m a + f(..) (1)
4656 * where m is equal to "gcd".
4657 * "i" is the index of the equality in "hull" that defines f(..).
4658 * In particular, the equality is of the form
4660 * f(..) - x + m g(existentials) = 0
4664 * -f(..) + x + m g(existentials) = 0
4666 * We basically plug (1) into "map", resulting in a map with "a"
4667 * in the range instead of "x". The corresponding isl_pw_multi_aff
4668 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
4670 * Specifically, given the input map
4674 * We first wrap it into a set
4678 * and define (1) on top of the corresponding space, resulting in "aff".
4679 * We use this to create an isl_multi_aff that maps the output position "d"
4680 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
4681 * We plug this into the wrapped map, unwrap the result and compute the
4682 * corresponding isl_pw_multi_aff.
4683 * The result is an expression
4691 * so that we can plug that into "aff", after extending the latter to
4697 * If "map" is actually a set, then there is no "A" space, meaning
4698 * that we do not need to perform any wrapping, and that the result
4699 * of the recursive call is of the form
4703 * which is plugged into a mapping of the form
4707 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
4708 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
4713 isl_local_space
*ls
;
4716 isl_pw_multi_aff
*pma
, *id
;
4722 is_set
= isl_map_is_set(map
);
4724 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
4725 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4726 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4731 set
= isl_map_wrap(map
);
4732 space
= isl_space_map_from_set(isl_set_get_space(set
));
4733 ma
= isl_multi_aff_identity(space
);
4734 ls
= isl_local_space_from_space(isl_set_get_space(set
));
4735 aff
= isl_aff_alloc(ls
);
4737 isl_int_set_si(aff
->v
->el
[0], 1);
4738 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
4739 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
4742 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
4744 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
4746 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
4747 set
= isl_set_preimage_multi_aff(set
, ma
);
4749 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
4754 map
= isl_set_unwrap(set
);
4755 pma
= isl_pw_multi_aff_from_map(map
);
4758 space
= isl_pw_multi_aff_get_domain_space(pma
);
4759 space
= isl_space_map_from_set(space
);
4760 id
= isl_pw_multi_aff_identity(space
);
4761 pma
= isl_pw_multi_aff_range_product(id
, pma
);
4763 id
= isl_pw_multi_aff_from_multi_aff(ma
);
4764 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
4766 isl_basic_map_free(hull
);
4770 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4772 * As a special case, we first check if all output dimensions are uniquely
4773 * defined in terms of the parameters and input dimensions over the entire
4774 * domain. If so, we extract the desired isl_pw_multi_aff directly
4775 * from the affine hull of "map" and its domain.
4777 * Otherwise, we check if any of the output dimensions is "strided".
4778 * That is, we check if can be written as
4782 * with m greater than 1, a some combination of existentiall quantified
4783 * variables and f and expression in the parameters and input dimensions.
4784 * If so, we remove the stride in pw_multi_aff_from_map_stride.
4786 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
4789 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
4793 isl_basic_map
*hull
;
4803 hull
= isl_map_affine_hull(isl_map_copy(map
));
4804 sv
= isl_basic_map_plain_is_single_valued(hull
);
4806 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
4808 hull
= isl_basic_map_free(hull
);
4812 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
4813 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
4816 isl_basic_map_free(hull
);
4817 return pw_multi_aff_from_map_check_div(map
);
4822 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4823 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4825 for (i
= 0; i
< n_out
; ++i
) {
4826 for (j
= 0; j
< hull
->n_eq
; ++j
) {
4827 isl_int
*eq
= hull
->eq
[j
];
4828 isl_pw_multi_aff
*res
;
4830 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
4831 !isl_int_is_negone(eq
[o_out
+ i
]))
4833 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
4835 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
4836 n_out
- (i
+ 1)) != -1)
4838 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
4839 if (isl_int_is_zero(gcd
))
4841 if (isl_int_is_one(gcd
))
4844 res
= pw_multi_aff_from_map_stride(map
, hull
,
4852 isl_basic_map_free(hull
);
4853 return pw_multi_aff_from_map_check_div(map
);
4859 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
4861 return isl_pw_multi_aff_from_map(set
);
4864 /* Convert "map" into an isl_pw_multi_aff (if possible) and
4867 static int pw_multi_aff_from_map(__isl_take isl_map
*map
, void *user
)
4869 isl_union_pw_multi_aff
**upma
= user
;
4870 isl_pw_multi_aff
*pma
;
4872 pma
= isl_pw_multi_aff_from_map(map
);
4873 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4875 return *upma
? 0 : -1;
4878 /* Try and create an isl_union_pw_multi_aff that is equivalent
4879 * to the given isl_union_map.
4880 * The isl_union_map is required to be single-valued in each space.
4881 * Otherwise, an error is produced.
4883 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_map(
4884 __isl_take isl_union_map
*umap
)
4887 isl_union_pw_multi_aff
*upma
;
4889 space
= isl_union_map_get_space(umap
);
4890 upma
= isl_union_pw_multi_aff_empty(space
);
4891 if (isl_union_map_foreach_map(umap
, &pw_multi_aff_from_map
, &upma
) < 0)
4892 upma
= isl_union_pw_multi_aff_free(upma
);
4893 isl_union_map_free(umap
);
4898 /* Try and create an isl_union_pw_multi_aff that is equivalent
4899 * to the given isl_union_set.
4900 * The isl_union_set is required to be a singleton in each space.
4901 * Otherwise, an error is produced.
4903 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_set(
4904 __isl_take isl_union_set
*uset
)
4906 return isl_union_pw_multi_aff_from_union_map(uset
);
4909 /* Return the piecewise affine expression "set ? 1 : 0".
4911 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
4914 isl_space
*space
= isl_set_get_space(set
);
4915 isl_local_space
*ls
= isl_local_space_from_space(space
);
4916 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
4917 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
4919 one
= isl_aff_add_constant_si(one
, 1);
4920 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
4921 set
= isl_set_complement(set
);
4922 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
4927 /* Plug in "subs" for dimension "type", "pos" of "aff".
4929 * Let i be the dimension to replace and let "subs" be of the form
4933 * and "aff" of the form
4939 * (a f + d g')/(m d)
4941 * where g' is the result of plugging in "subs" in each of the integer
4944 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
4945 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
4950 aff
= isl_aff_cow(aff
);
4952 return isl_aff_free(aff
);
4954 ctx
= isl_aff_get_ctx(aff
);
4955 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
4956 isl_die(ctx
, isl_error_invalid
,
4957 "spaces don't match", return isl_aff_free(aff
));
4958 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
4959 isl_die(ctx
, isl_error_unsupported
,
4960 "cannot handle divs yet", return isl_aff_free(aff
));
4962 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
4964 return isl_aff_free(aff
);
4966 aff
->v
= isl_vec_cow(aff
->v
);
4968 return isl_aff_free(aff
);
4970 pos
+= isl_local_space_offset(aff
->ls
, type
);
4973 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
4974 aff
->v
->size
, subs
->v
->size
, v
);
4980 /* Plug in "subs" for dimension "type", "pos" in each of the affine
4981 * expressions in "maff".
4983 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
4984 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
4985 __isl_keep isl_aff
*subs
)
4989 maff
= isl_multi_aff_cow(maff
);
4991 return isl_multi_aff_free(maff
);
4993 if (type
== isl_dim_in
)
4996 for (i
= 0; i
< maff
->n
; ++i
) {
4997 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
4999 return isl_multi_aff_free(maff
);
5005 /* Plug in "subs" for dimension "type", "pos" of "pma".
5007 * pma is of the form
5011 * while subs is of the form
5013 * v' = B_j(v) -> S_j
5015 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
5016 * has a contribution in the result, in particular
5018 * C_ij(S_j) -> M_i(S_j)
5020 * Note that plugging in S_j in C_ij may also result in an empty set
5021 * and this contribution should simply be discarded.
5023 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
5024 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
5025 __isl_keep isl_pw_aff
*subs
)
5028 isl_pw_multi_aff
*res
;
5031 return isl_pw_multi_aff_free(pma
);
5033 n
= pma
->n
* subs
->n
;
5034 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
5036 for (i
= 0; i
< pma
->n
; ++i
) {
5037 for (j
= 0; j
< subs
->n
; ++j
) {
5039 isl_multi_aff
*res_ij
;
5042 common
= isl_set_intersect(
5043 isl_set_copy(pma
->p
[i
].set
),
5044 isl_set_copy(subs
->p
[j
].set
));
5045 common
= isl_set_substitute(common
,
5046 type
, pos
, subs
->p
[j
].aff
);
5047 empty
= isl_set_plain_is_empty(common
);
5048 if (empty
< 0 || empty
) {
5049 isl_set_free(common
);
5055 res_ij
= isl_multi_aff_substitute(
5056 isl_multi_aff_copy(pma
->p
[i
].maff
),
5057 type
, pos
, subs
->p
[j
].aff
);
5059 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5063 isl_pw_multi_aff_free(pma
);
5066 isl_pw_multi_aff_free(pma
);
5067 isl_pw_multi_aff_free(res
);
5071 /* Compute the preimage of a range of dimensions in the affine expression "src"
5072 * under "ma" and put the result in "dst". The number of dimensions in "src"
5073 * that precede the range is given by "n_before". The number of dimensions
5074 * in the range is given by the number of output dimensions of "ma".
5075 * The number of dimensions that follow the range is given by "n_after".
5076 * If "has_denom" is set (to one),
5077 * then "src" and "dst" have an extra initial denominator.
5078 * "n_div_ma" is the number of existentials in "ma"
5079 * "n_div_bset" is the number of existentials in "src"
5080 * The resulting "dst" (which is assumed to have been allocated by
5081 * the caller) contains coefficients for both sets of existentials,
5082 * first those in "ma" and then those in "src".
5083 * f, c1, c2 and g are temporary objects that have been initialized
5086 * Let src represent the expression
5088 * (a(p) + f_u u + b v + f_w w + c(divs))/d
5090 * and let ma represent the expressions
5092 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
5094 * We start out with the following expression for dst:
5096 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d
5098 * with the multiplication factor f initially equal to 1
5099 * and f \sum_i b_i v_i kept separately.
5100 * For each x_i that we substitute, we multiply the numerator
5101 * (and denominator) of dst by c_1 = m_i and add the numerator
5102 * of the x_i expression multiplied by c_2 = f b_i,
5103 * after removing the common factors of c_1 and c_2.
5104 * The multiplication factor f also needs to be multiplied by c_1
5105 * for the next x_j, j > i.
5107 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
5108 __isl_keep isl_multi_aff
*ma
, int n_before
, int n_after
,
5109 int n_div_ma
, int n_div_bmap
,
5110 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
5113 int n_param
, n_in
, n_out
;
5116 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
5117 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
5118 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
5120 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
+ n_before
);
5121 o_dst
= o_src
= has_denom
+ 1 + n_param
+ n_before
;
5122 isl_seq_clr(dst
+ o_dst
, n_in
);
5125 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_after
);
5128 isl_seq_clr(dst
+ o_dst
, n_div_ma
);
5130 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_div_bmap
);
5132 isl_int_set_si(f
, 1);
5134 for (i
= 0; i
< n_out
; ++i
) {
5135 int offset
= has_denom
+ 1 + n_param
+ n_before
+ i
;
5137 if (isl_int_is_zero(src
[offset
]))
5139 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
5140 isl_int_mul(c2
, f
, src
[offset
]);
5141 isl_int_gcd(g
, c1
, c2
);
5142 isl_int_divexact(c1
, c1
, g
);
5143 isl_int_divexact(c2
, c2
, g
);
5145 isl_int_mul(f
, f
, c1
);
5148 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5149 c2
, ma
->p
[i
]->v
->el
+ o_src
, 1 + n_param
);
5150 o_dst
+= 1 + n_param
;
5151 o_src
+= 1 + n_param
;
5152 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_before
);
5154 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5155 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_in
);
5158 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_after
);
5160 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5161 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_div_ma
);
5164 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_div_bmap
);
5166 isl_int_mul(dst
[0], dst
[0], c1
);
5170 /* Compute the pullback of "aff" by the function represented by "ma".
5171 * In other words, plug in "ma" in "aff". The result is an affine expression
5172 * defined over the domain space of "ma".
5174 * If "aff" is represented by
5176 * (a(p) + b x + c(divs))/d
5178 * and ma is represented by
5180 * x = D(p) + F(y) + G(divs')
5182 * then the result is
5184 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
5186 * The divs in the local space of the input are similarly adjusted
5187 * through a call to isl_local_space_preimage_multi_aff.
5189 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
5190 __isl_take isl_multi_aff
*ma
)
5192 isl_aff
*res
= NULL
;
5193 isl_local_space
*ls
;
5194 int n_div_aff
, n_div_ma
;
5195 isl_int f
, c1
, c2
, g
;
5197 ma
= isl_multi_aff_align_divs(ma
);
5201 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
5202 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
5204 ls
= isl_aff_get_domain_local_space(aff
);
5205 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
5206 res
= isl_aff_alloc(ls
);
5215 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, 0, 0, n_div_ma
, n_div_aff
,
5224 isl_multi_aff_free(ma
);
5225 res
= isl_aff_normalize(res
);
5229 isl_multi_aff_free(ma
);
5234 /* Compute the pullback of "aff1" by the function represented by "aff2".
5235 * In other words, plug in "aff2" in "aff1". The result is an affine expression
5236 * defined over the domain space of "aff1".
5238 * The domain of "aff1" should match the range of "aff2", which means
5239 * that it should be single-dimensional.
5241 __isl_give isl_aff
*isl_aff_pullback_aff(__isl_take isl_aff
*aff1
,
5242 __isl_take isl_aff
*aff2
)
5246 ma
= isl_multi_aff_from_aff(aff2
);
5247 return isl_aff_pullback_multi_aff(aff1
, ma
);
5250 /* Compute the pullback of "ma1" by the function represented by "ma2".
5251 * In other words, plug in "ma2" in "ma1".
5253 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
5255 static __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff_aligned(
5256 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5259 isl_space
*space
= NULL
;
5261 ma2
= isl_multi_aff_align_divs(ma2
);
5262 ma1
= isl_multi_aff_cow(ma1
);
5266 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
5267 isl_multi_aff_get_space(ma1
));
5269 for (i
= 0; i
< ma1
->n
; ++i
) {
5270 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
5271 isl_multi_aff_copy(ma2
));
5276 ma1
= isl_multi_aff_reset_space(ma1
, space
);
5277 isl_multi_aff_free(ma2
);
5280 isl_space_free(space
);
5281 isl_multi_aff_free(ma2
);
5282 isl_multi_aff_free(ma1
);
5286 /* Compute the pullback of "ma1" by the function represented by "ma2".
5287 * In other words, plug in "ma2" in "ma1".
5289 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
5290 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5292 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
5293 &isl_multi_aff_pullback_multi_aff_aligned
);
5296 /* Extend the local space of "dst" to include the divs
5297 * in the local space of "src".
5299 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
5300 __isl_keep isl_aff
*src
)
5308 return isl_aff_free(dst
);
5310 ctx
= isl_aff_get_ctx(src
);
5311 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
5312 isl_die(ctx
, isl_error_invalid
,
5313 "spaces don't match", goto error
);
5315 if (src
->ls
->div
->n_row
== 0)
5318 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
5319 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
5320 if (!exp1
|| (dst
->ls
->div
->n_row
&& !exp2
))
5323 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
5324 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
5332 return isl_aff_free(dst
);
5335 /* Adjust the local spaces of the affine expressions in "maff"
5336 * such that they all have the save divs.
5338 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
5339 __isl_take isl_multi_aff
*maff
)
5347 maff
= isl_multi_aff_cow(maff
);
5351 for (i
= 1; i
< maff
->n
; ++i
)
5352 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
5353 for (i
= 1; i
< maff
->n
; ++i
) {
5354 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
5356 return isl_multi_aff_free(maff
);
5362 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
5364 aff
= isl_aff_cow(aff
);
5368 aff
->ls
= isl_local_space_lift(aff
->ls
);
5370 return isl_aff_free(aff
);
5375 /* Lift "maff" to a space with extra dimensions such that the result
5376 * has no more existentially quantified variables.
5377 * If "ls" is not NULL, then *ls is assigned the local space that lies
5378 * at the basis of the lifting applied to "maff".
5380 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
5381 __isl_give isl_local_space
**ls
)
5395 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
5396 *ls
= isl_local_space_from_space(space
);
5398 return isl_multi_aff_free(maff
);
5403 maff
= isl_multi_aff_cow(maff
);
5404 maff
= isl_multi_aff_align_divs(maff
);
5408 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
5409 space
= isl_multi_aff_get_space(maff
);
5410 space
= isl_space_lift(isl_space_domain(space
), n_div
);
5411 space
= isl_space_extend_domain_with_range(space
,
5412 isl_multi_aff_get_space(maff
));
5414 return isl_multi_aff_free(maff
);
5415 isl_space_free(maff
->space
);
5416 maff
->space
= space
;
5419 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
5421 return isl_multi_aff_free(maff
);
5424 for (i
= 0; i
< maff
->n
; ++i
) {
5425 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
5433 isl_local_space_free(*ls
);
5434 return isl_multi_aff_free(maff
);
5438 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
5440 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
5441 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
5451 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
5452 if (pos
< 0 || pos
>= n_out
)
5453 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5454 "index out of bounds", return NULL
);
5456 space
= isl_pw_multi_aff_get_space(pma
);
5457 space
= isl_space_drop_dims(space
, isl_dim_out
,
5458 pos
+ 1, n_out
- pos
- 1);
5459 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
5461 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
5462 for (i
= 0; i
< pma
->n
; ++i
) {
5464 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
5465 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
5471 /* Return an isl_pw_multi_aff with the given "set" as domain and
5472 * an unnamed zero-dimensional range.
5474 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
5475 __isl_take isl_set
*set
)
5480 space
= isl_set_get_space(set
);
5481 space
= isl_space_from_domain(space
);
5482 ma
= isl_multi_aff_zero(space
);
5483 return isl_pw_multi_aff_alloc(set
, ma
);
5486 /* Add an isl_pw_multi_aff with the given "set" as domain and
5487 * an unnamed zero-dimensional range to *user.
5489 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
5491 isl_union_pw_multi_aff
**upma
= user
;
5492 isl_pw_multi_aff
*pma
;
5494 pma
= isl_pw_multi_aff_from_domain(set
);
5495 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
5500 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
5501 * an unnamed zero-dimensional range.
5503 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
5504 __isl_take isl_union_set
*uset
)
5507 isl_union_pw_multi_aff
*upma
;
5512 space
= isl_union_set_get_space(uset
);
5513 upma
= isl_union_pw_multi_aff_empty(space
);
5515 if (isl_union_set_foreach_set(uset
,
5516 &add_pw_multi_aff_from_domain
, &upma
) < 0)
5519 isl_union_set_free(uset
);
5522 isl_union_set_free(uset
);
5523 isl_union_pw_multi_aff_free(upma
);
5527 /* Convert "pma" to an isl_map and add it to *umap.
5529 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
5531 isl_union_map
**umap
= user
;
5534 map
= isl_map_from_pw_multi_aff(pma
);
5535 *umap
= isl_union_map_add_map(*umap
, map
);
5540 /* Construct a union map mapping the domain of the union
5541 * piecewise multi-affine expression to its range, with each dimension
5542 * in the range equated to the corresponding affine expression on its cell.
5544 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
5545 __isl_take isl_union_pw_multi_aff
*upma
)
5548 isl_union_map
*umap
;
5553 space
= isl_union_pw_multi_aff_get_space(upma
);
5554 umap
= isl_union_map_empty(space
);
5556 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
5557 &map_from_pw_multi_aff
, &umap
) < 0)
5560 isl_union_pw_multi_aff_free(upma
);
5563 isl_union_pw_multi_aff_free(upma
);
5564 isl_union_map_free(umap
);
5568 /* Local data for bin_entry and the callback "fn".
5570 struct isl_union_pw_multi_aff_bin_data
{
5571 isl_union_pw_multi_aff
*upma2
;
5572 isl_union_pw_multi_aff
*res
;
5573 isl_pw_multi_aff
*pma
;
5574 int (*fn
)(void **entry
, void *user
);
5577 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
5578 * and call data->fn for each isl_pw_multi_aff in data->upma2.
5580 static int bin_entry(void **entry
, void *user
)
5582 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5583 isl_pw_multi_aff
*pma
= *entry
;
5586 if (isl_hash_table_foreach(data
->upma2
->dim
->ctx
, &data
->upma2
->table
,
5587 data
->fn
, data
) < 0)
5593 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
5594 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
5595 * passed as user field) and the isl_pw_multi_aff from upma2 is available
5596 * as *entry. The callback should adjust data->res if desired.
5598 static __isl_give isl_union_pw_multi_aff
*bin_op(
5599 __isl_take isl_union_pw_multi_aff
*upma1
,
5600 __isl_take isl_union_pw_multi_aff
*upma2
,
5601 int (*fn
)(void **entry
, void *user
))
5604 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
5606 space
= isl_union_pw_multi_aff_get_space(upma2
);
5607 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
5608 space
= isl_union_pw_multi_aff_get_space(upma1
);
5609 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
5611 if (!upma1
|| !upma2
)
5615 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->dim
),
5617 if (isl_hash_table_foreach(upma1
->dim
->ctx
, &upma1
->table
,
5618 &bin_entry
, &data
) < 0)
5621 isl_union_pw_multi_aff_free(upma1
);
5622 isl_union_pw_multi_aff_free(upma2
);
5625 isl_union_pw_multi_aff_free(upma1
);
5626 isl_union_pw_multi_aff_free(upma2
);
5627 isl_union_pw_multi_aff_free(data
.res
);
5631 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5632 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5634 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
5635 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5639 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5640 isl_pw_multi_aff_get_space(pma2
));
5641 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5642 &isl_multi_aff_range_product
);
5645 /* Given two isl_pw_multi_affs A -> B and C -> D,
5646 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5648 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
5649 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5651 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5652 &pw_multi_aff_range_product
);
5655 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5656 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5658 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
5659 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5663 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5664 isl_pw_multi_aff_get_space(pma2
));
5665 space
= isl_space_flatten_range(space
);
5666 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5667 &isl_multi_aff_flat_range_product
);
5670 /* Given two isl_pw_multi_affs A -> B and C -> D,
5671 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5673 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
5674 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5676 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5677 &pw_multi_aff_flat_range_product
);
5680 /* If data->pma and *entry have the same domain space, then compute
5681 * their flat range product and the result to data->res.
5683 static int flat_range_product_entry(void **entry
, void *user
)
5685 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5686 isl_pw_multi_aff
*pma2
= *entry
;
5688 if (!isl_space_tuple_is_equal(data
->pma
->dim
, isl_dim_in
,
5689 pma2
->dim
, isl_dim_in
))
5692 pma2
= isl_pw_multi_aff_flat_range_product(
5693 isl_pw_multi_aff_copy(data
->pma
),
5694 isl_pw_multi_aff_copy(pma2
));
5696 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
5701 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
5702 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
5704 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
5705 __isl_take isl_union_pw_multi_aff
*upma1
,
5706 __isl_take isl_union_pw_multi_aff
*upma2
)
5708 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
5711 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5712 * The parameters are assumed to have been aligned.
5714 * The implementation essentially performs an isl_pw_*_on_shared_domain,
5715 * except that it works on two different isl_pw_* types.
5717 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
5718 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5719 __isl_take isl_pw_aff
*pa
)
5722 isl_pw_multi_aff
*res
= NULL
;
5727 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_in
,
5728 pa
->dim
, isl_dim_in
))
5729 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5730 "domains don't match", goto error
);
5731 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
5732 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5733 "index out of bounds", goto error
);
5736 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
5738 for (i
= 0; i
< pma
->n
; ++i
) {
5739 for (j
= 0; j
< pa
->n
; ++j
) {
5741 isl_multi_aff
*res_ij
;
5744 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
5745 isl_set_copy(pa
->p
[j
].set
));
5746 empty
= isl_set_plain_is_empty(common
);
5747 if (empty
< 0 || empty
) {
5748 isl_set_free(common
);
5754 res_ij
= isl_multi_aff_set_aff(
5755 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
5756 isl_aff_copy(pa
->p
[j
].aff
));
5757 res_ij
= isl_multi_aff_gist(res_ij
,
5758 isl_set_copy(common
));
5760 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5764 isl_pw_multi_aff_free(pma
);
5765 isl_pw_aff_free(pa
);
5768 isl_pw_multi_aff_free(pma
);
5769 isl_pw_aff_free(pa
);
5770 return isl_pw_multi_aff_free(res
);
5773 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5775 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
5776 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5777 __isl_take isl_pw_aff
*pa
)
5781 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
5782 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5783 if (!isl_space_has_named_params(pma
->dim
) ||
5784 !isl_space_has_named_params(pa
->dim
))
5785 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5786 "unaligned unnamed parameters", goto error
);
5787 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
5788 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
5789 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5791 isl_pw_multi_aff_free(pma
);
5792 isl_pw_aff_free(pa
);
5796 /* Do the parameters of "pa" match those of "space"?
5798 int isl_pw_aff_matching_params(__isl_keep isl_pw_aff
*pa
,
5799 __isl_keep isl_space
*space
)
5801 isl_space
*pa_space
;
5807 pa_space
= isl_pw_aff_get_space(pa
);
5809 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5811 isl_space_free(pa_space
);
5815 /* Check that the domain space of "pa" matches "space".
5817 * Return 0 on success and -1 on error.
5819 int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff
*pa
,
5820 __isl_keep isl_space
*space
)
5822 isl_space
*pa_space
;
5828 pa_space
= isl_pw_aff_get_space(pa
);
5830 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5834 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5835 "parameters don't match", goto error
);
5836 match
= isl_space_tuple_is_equal(space
, isl_dim_in
,
5837 pa_space
, isl_dim_in
);
5841 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5842 "domains don't match", goto error
);
5843 isl_space_free(pa_space
);
5846 isl_space_free(pa_space
);
5853 #include <isl_multi_templ.c>
5855 /* Scale the elements of "pma" by the corresponding elements of "mv".
5857 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_scale_multi_val(
5858 __isl_take isl_pw_multi_aff
*pma
, __isl_take isl_multi_val
*mv
)
5862 pma
= isl_pw_multi_aff_cow(pma
);
5865 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_out
,
5866 mv
->space
, isl_dim_set
))
5867 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5868 "spaces don't match", goto error
);
5869 if (!isl_space_match(pma
->dim
, isl_dim_param
,
5870 mv
->space
, isl_dim_param
)) {
5871 pma
= isl_pw_multi_aff_align_params(pma
,
5872 isl_multi_val_get_space(mv
));
5873 mv
= isl_multi_val_align_params(mv
,
5874 isl_pw_multi_aff_get_space(pma
));
5879 for (i
= 0; i
< pma
->n
; ++i
) {
5880 pma
->p
[i
].maff
= isl_multi_aff_scale_multi_val(pma
->p
[i
].maff
,
5881 isl_multi_val_copy(mv
));
5882 if (!pma
->p
[i
].maff
)
5886 isl_multi_val_free(mv
);
5889 isl_multi_val_free(mv
);
5890 isl_pw_multi_aff_free(pma
);
5894 /* Internal data structure for isl_union_pw_multi_aff_scale_multi_val.
5895 * mv contains the mv argument.
5896 * res collects the results.
5898 struct isl_union_pw_multi_aff_scale_multi_val_data
{
5900 isl_union_pw_multi_aff
*res
;
5903 /* This function is called for each entry of an isl_union_pw_multi_aff.
5904 * If the space of the entry matches that of data->mv,
5905 * then apply isl_pw_multi_aff_scale_multi_val and add the result
5908 static int union_pw_multi_aff_scale_multi_val_entry(void **entry
, void *user
)
5910 struct isl_union_pw_multi_aff_scale_multi_val_data
*data
= user
;
5911 isl_pw_multi_aff
*pma
= *entry
;
5915 if (!isl_space_tuple_is_equal(pma
->dim
, isl_dim_out
,
5916 data
->mv
->space
, isl_dim_set
))
5919 pma
= isl_pw_multi_aff_copy(pma
);
5920 pma
= isl_pw_multi_aff_scale_multi_val(pma
,
5921 isl_multi_val_copy(data
->mv
));
5922 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
5929 /* Scale the elements of "upma" by the corresponding elements of "mv",
5930 * for those entries that match the space of "mv".
5932 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_scale_multi_val(
5933 __isl_take isl_union_pw_multi_aff
*upma
, __isl_take isl_multi_val
*mv
)
5935 struct isl_union_pw_multi_aff_scale_multi_val_data data
;
5937 upma
= isl_union_pw_multi_aff_align_params(upma
,
5938 isl_multi_val_get_space(mv
));
5939 mv
= isl_multi_val_align_params(mv
,
5940 isl_union_pw_multi_aff_get_space(upma
));
5945 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma
->dim
),
5947 if (isl_hash_table_foreach(upma
->dim
->ctx
, &upma
->table
,
5948 &union_pw_multi_aff_scale_multi_val_entry
, &data
) < 0)
5951 isl_multi_val_free(mv
);
5952 isl_union_pw_multi_aff_free(upma
);
5955 isl_multi_val_free(mv
);
5956 isl_union_pw_multi_aff_free(upma
);
5960 /* Construct and return a piecewise multi affine expression
5961 * in the given space with value zero in each of the output dimensions and
5962 * a universe domain.
5964 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_zero(__isl_take isl_space
*space
)
5966 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_zero(space
));
5969 /* Construct and return a piecewise multi affine expression
5970 * that is equal to the given piecewise affine expression.
5972 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_pw_aff(
5973 __isl_take isl_pw_aff
*pa
)
5977 isl_pw_multi_aff
*pma
;
5982 space
= isl_pw_aff_get_space(pa
);
5983 pma
= isl_pw_multi_aff_alloc_size(space
, pa
->n
);
5985 for (i
= 0; i
< pa
->n
; ++i
) {
5989 set
= isl_set_copy(pa
->p
[i
].set
);
5990 ma
= isl_multi_aff_from_aff(isl_aff_copy(pa
->p
[i
].aff
));
5991 pma
= isl_pw_multi_aff_add_piece(pma
, set
, ma
);
5994 isl_pw_aff_free(pa
);
5998 /* Construct a set or map mapping the shared (parameter) domain
5999 * of the piecewise affine expressions to the range of "mpa"
6000 * with each dimension in the range equated to the
6001 * corresponding piecewise affine expression.
6003 static __isl_give isl_map
*map_from_multi_pw_aff(
6004 __isl_take isl_multi_pw_aff
*mpa
)
6013 if (isl_space_dim(mpa
->space
, isl_dim_out
) != mpa
->n
)
6014 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6015 "invalid space", goto error
);
6017 space
= isl_multi_pw_aff_get_domain_space(mpa
);
6018 map
= isl_map_universe(isl_space_from_domain(space
));
6020 for (i
= 0; i
< mpa
->n
; ++i
) {
6024 pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6025 map_i
= map_from_pw_aff(pa
);
6027 map
= isl_map_flat_range_product(map
, map_i
);
6030 map
= isl_map_reset_space(map
, isl_multi_pw_aff_get_space(mpa
));
6032 isl_multi_pw_aff_free(mpa
);
6035 isl_multi_pw_aff_free(mpa
);
6039 /* Construct a map mapping the shared domain
6040 * of the piecewise affine expressions to the range of "mpa"
6041 * with each dimension in the range equated to the
6042 * corresponding piecewise affine expression.
6044 __isl_give isl_map
*isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6048 if (isl_space_is_set(mpa
->space
))
6049 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6050 "space of input is not a map", goto error
);
6052 return map_from_multi_pw_aff(mpa
);
6054 isl_multi_pw_aff_free(mpa
);
6058 /* Construct a set mapping the shared parameter domain
6059 * of the piecewise affine expressions to the space of "mpa"
6060 * with each dimension in the range equated to the
6061 * corresponding piecewise affine expression.
6063 __isl_give isl_set
*isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6067 if (!isl_space_is_set(mpa
->space
))
6068 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6069 "space of input is not a set", goto error
);
6071 return map_from_multi_pw_aff(mpa
);
6073 isl_multi_pw_aff_free(mpa
);
6077 /* Construct and return a piecewise multi affine expression
6078 * that is equal to the given multi piecewise affine expression
6079 * on the shared domain of the piecewise affine expressions.
6081 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_pw_aff(
6082 __isl_take isl_multi_pw_aff
*mpa
)
6087 isl_pw_multi_aff
*pma
;
6092 space
= isl_multi_pw_aff_get_space(mpa
);
6095 isl_multi_pw_aff_free(mpa
);
6096 return isl_pw_multi_aff_zero(space
);
6099 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
6100 pma
= isl_pw_multi_aff_from_pw_aff(pa
);
6102 for (i
= 1; i
< mpa
->n
; ++i
) {
6103 isl_pw_multi_aff
*pma_i
;
6105 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6106 pma_i
= isl_pw_multi_aff_from_pw_aff(pa
);
6107 pma
= isl_pw_multi_aff_range_product(pma
, pma_i
);
6110 pma
= isl_pw_multi_aff_reset_space(pma
, space
);
6112 isl_multi_pw_aff_free(mpa
);
6116 /* Construct and return a multi piecewise affine expression
6117 * that is equal to the given multi affine expression.
6119 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_multi_aff(
6120 __isl_take isl_multi_aff
*ma
)
6123 isl_multi_pw_aff
*mpa
;
6128 n
= isl_multi_aff_dim(ma
, isl_dim_out
);
6129 mpa
= isl_multi_pw_aff_alloc(isl_multi_aff_get_space(ma
));
6131 for (i
= 0; i
< n
; ++i
) {
6134 pa
= isl_pw_aff_from_aff(isl_multi_aff_get_aff(ma
, i
));
6135 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6138 isl_multi_aff_free(ma
);
6142 /* Construct and return a multi piecewise affine expression
6143 * that is equal to the given piecewise multi affine expression.
6145 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_pw_multi_aff(
6146 __isl_take isl_pw_multi_aff
*pma
)
6150 isl_multi_pw_aff
*mpa
;
6155 n
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
6156 space
= isl_pw_multi_aff_get_space(pma
);
6157 mpa
= isl_multi_pw_aff_alloc(space
);
6159 for (i
= 0; i
< n
; ++i
) {
6162 pa
= isl_pw_multi_aff_get_pw_aff(pma
, i
);
6163 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6166 isl_pw_multi_aff_free(pma
);
6170 /* Do "pa1" and "pa2" represent the same function?
6172 * We first check if they are obviously equal.
6173 * If not, we convert them to maps and check if those are equal.
6175 int isl_pw_aff_is_equal(__isl_keep isl_pw_aff
*pa1
, __isl_keep isl_pw_aff
*pa2
)
6178 isl_map
*map1
, *map2
;
6183 equal
= isl_pw_aff_plain_is_equal(pa1
, pa2
);
6184 if (equal
< 0 || equal
)
6187 map1
= map_from_pw_aff(isl_pw_aff_copy(pa1
));
6188 map2
= map_from_pw_aff(isl_pw_aff_copy(pa2
));
6189 equal
= isl_map_is_equal(map1
, map2
);
6196 /* Do "mpa1" and "mpa2" represent the same function?
6198 * Note that we cannot convert the entire isl_multi_pw_aff
6199 * to a map because the domains of the piecewise affine expressions
6200 * may not be the same.
6202 int isl_multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
6203 __isl_keep isl_multi_pw_aff
*mpa2
)
6211 if (!isl_space_match(mpa1
->space
, isl_dim_param
,
6212 mpa2
->space
, isl_dim_param
)) {
6213 if (!isl_space_has_named_params(mpa1
->space
))
6215 if (!isl_space_has_named_params(mpa2
->space
))
6217 mpa1
= isl_multi_pw_aff_copy(mpa1
);
6218 mpa2
= isl_multi_pw_aff_copy(mpa2
);
6219 mpa1
= isl_multi_pw_aff_align_params(mpa1
,
6220 isl_multi_pw_aff_get_space(mpa2
));
6221 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
6222 isl_multi_pw_aff_get_space(mpa1
));
6223 equal
= isl_multi_pw_aff_is_equal(mpa1
, mpa2
);
6224 isl_multi_pw_aff_free(mpa1
);
6225 isl_multi_pw_aff_free(mpa2
);
6229 equal
= isl_space_is_equal(mpa1
->space
, mpa2
->space
);
6230 if (equal
< 0 || !equal
)
6233 for (i
= 0; i
< mpa1
->n
; ++i
) {
6234 equal
= isl_pw_aff_is_equal(mpa1
->p
[i
], mpa2
->p
[i
]);
6235 if (equal
< 0 || !equal
)
6242 /* Coalesce the elements of "mpa".
6244 * Note that such coalescing does not change the meaning of "mpa"
6245 * so there is no need to cow. We do need to be careful not to
6246 * destroy any other copies of "mpa" in case of failure.
6248 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_coalesce(
6249 __isl_take isl_multi_pw_aff
*mpa
)
6256 for (i
= 0; i
< mpa
->n
; ++i
) {
6257 isl_pw_aff
*pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6258 pa
= isl_pw_aff_coalesce(pa
);
6260 return isl_multi_pw_aff_free(mpa
);
6261 isl_pw_aff_free(mpa
->p
[i
]);
6268 /* Compute the pullback of "mpa" by the function represented by "ma".
6269 * In other words, plug in "ma" in "mpa".
6271 * The parameters of "mpa" and "ma" are assumed to have been aligned.
6273 static __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff_aligned(
6274 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6277 isl_space
*space
= NULL
;
6279 mpa
= isl_multi_pw_aff_cow(mpa
);
6283 space
= isl_space_join(isl_multi_aff_get_space(ma
),
6284 isl_multi_pw_aff_get_space(mpa
));
6288 for (i
= 0; i
< mpa
->n
; ++i
) {
6289 mpa
->p
[i
] = isl_pw_aff_pullback_multi_aff(mpa
->p
[i
],
6290 isl_multi_aff_copy(ma
));
6295 isl_multi_aff_free(ma
);
6296 isl_space_free(mpa
->space
);
6300 isl_space_free(space
);
6301 isl_multi_pw_aff_free(mpa
);
6302 isl_multi_aff_free(ma
);
6306 /* Compute the pullback of "mpa" by the function represented by "ma".
6307 * In other words, plug in "ma" in "mpa".
6309 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff(
6310 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6314 if (isl_space_match(mpa
->space
, isl_dim_param
,
6315 ma
->space
, isl_dim_param
))
6316 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6317 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_multi_aff_get_space(ma
));
6318 ma
= isl_multi_aff_align_params(ma
, isl_multi_pw_aff_get_space(mpa
));
6319 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6321 isl_multi_pw_aff_free(mpa
);
6322 isl_multi_aff_free(ma
);
6326 /* Compute the pullback of "mpa" by the function represented by "pma".
6327 * In other words, plug in "pma" in "mpa".
6329 * The parameters of "mpa" and "mpa" are assumed to have been aligned.
6331 static __isl_give isl_multi_pw_aff
*
6332 isl_multi_pw_aff_pullback_pw_multi_aff_aligned(
6333 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6336 isl_space
*space
= NULL
;
6338 mpa
= isl_multi_pw_aff_cow(mpa
);
6342 space
= isl_space_join(isl_pw_multi_aff_get_space(pma
),
6343 isl_multi_pw_aff_get_space(mpa
));
6345 for (i
= 0; i
< mpa
->n
; ++i
) {
6346 mpa
->p
[i
] = isl_pw_aff_pullback_pw_multi_aff_aligned(mpa
->p
[i
],
6347 isl_pw_multi_aff_copy(pma
));
6352 isl_pw_multi_aff_free(pma
);
6353 isl_space_free(mpa
->space
);
6357 isl_space_free(space
);
6358 isl_multi_pw_aff_free(mpa
);
6359 isl_pw_multi_aff_free(pma
);
6363 /* Compute the pullback of "mpa" by the function represented by "pma".
6364 * In other words, plug in "pma" in "mpa".
6366 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_pw_multi_aff(
6367 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6371 if (isl_space_match(mpa
->space
, isl_dim_param
, pma
->dim
, isl_dim_param
))
6372 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6373 mpa
= isl_multi_pw_aff_align_params(mpa
,
6374 isl_pw_multi_aff_get_space(pma
));
6375 pma
= isl_pw_multi_aff_align_params(pma
,
6376 isl_multi_pw_aff_get_space(mpa
));
6377 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6379 isl_multi_pw_aff_free(mpa
);
6380 isl_pw_multi_aff_free(pma
);
6384 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6385 * with the domain of "aff". The domain of the result is the same
6387 * "mpa" and "aff" are assumed to have been aligned.
6389 * We first extract the parametric constant from "aff", defined
6390 * over the correct domain.
6391 * Then we add the appropriate combinations of the members of "mpa".
6392 * Finally, we add the integer divisions through recursive calls.
6394 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff_aligned(
6395 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6397 int i
, n_param
, n_in
, n_div
;
6403 n_param
= isl_aff_dim(aff
, isl_dim_param
);
6404 n_in
= isl_aff_dim(aff
, isl_dim_in
);
6405 n_div
= isl_aff_dim(aff
, isl_dim_div
);
6407 space
= isl_space_domain(isl_multi_pw_aff_get_space(mpa
));
6408 tmp
= isl_aff_copy(aff
);
6409 tmp
= isl_aff_drop_dims(tmp
, isl_dim_div
, 0, n_div
);
6410 tmp
= isl_aff_drop_dims(tmp
, isl_dim_in
, 0, n_in
);
6411 tmp
= isl_aff_add_dims(tmp
, isl_dim_in
,
6412 isl_space_dim(space
, isl_dim_set
));
6413 tmp
= isl_aff_reset_domain_space(tmp
, space
);
6414 pa
= isl_pw_aff_from_aff(tmp
);
6416 for (i
= 0; i
< n_in
; ++i
) {
6419 if (!isl_aff_involves_dims(aff
, isl_dim_in
, i
, 1))
6421 v
= isl_aff_get_coefficient_val(aff
, isl_dim_in
, i
);
6422 pa_i
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6423 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6424 pa
= isl_pw_aff_add(pa
, pa_i
);
6427 for (i
= 0; i
< n_div
; ++i
) {
6431 if (!isl_aff_involves_dims(aff
, isl_dim_div
, i
, 1))
6433 div
= isl_aff_get_div(aff
, i
);
6434 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6435 isl_multi_pw_aff_copy(mpa
), div
);
6436 pa_i
= isl_pw_aff_floor(pa_i
);
6437 v
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, i
);
6438 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6439 pa
= isl_pw_aff_add(pa
, pa_i
);
6442 isl_multi_pw_aff_free(mpa
);
6448 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6449 * with the domain of "aff". The domain of the result is the same
6452 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff(
6453 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6457 if (isl_space_match(aff
->ls
->dim
, isl_dim_param
,
6458 mpa
->space
, isl_dim_param
))
6459 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6461 aff
= isl_aff_align_params(aff
, isl_multi_pw_aff_get_space(mpa
));
6462 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_aff_get_space(aff
));
6464 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6467 isl_multi_pw_aff_free(mpa
);
6471 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6472 * with the domain of "pa". The domain of the result is the same
6474 * "mpa" and "pa" are assumed to have been aligned.
6476 * We consider each piece in turn. Note that the domains of the
6477 * pieces are assumed to be disjoint and they remain disjoint
6478 * after taking the preimage (over the same function).
6480 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff_aligned(
6481 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6490 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa
),
6491 isl_pw_aff_get_space(pa
));
6492 res
= isl_pw_aff_empty(space
);
6494 for (i
= 0; i
< pa
->n
; ++i
) {
6498 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6499 isl_multi_pw_aff_copy(mpa
),
6500 isl_aff_copy(pa
->p
[i
].aff
));
6501 domain
= isl_set_copy(pa
->p
[i
].set
);
6502 domain
= isl_set_preimage_multi_pw_aff(domain
,
6503 isl_multi_pw_aff_copy(mpa
));
6504 pa_i
= isl_pw_aff_intersect_domain(pa_i
, domain
);
6505 res
= isl_pw_aff_add_disjoint(res
, pa_i
);
6508 isl_pw_aff_free(pa
);
6509 isl_multi_pw_aff_free(mpa
);
6512 isl_pw_aff_free(pa
);
6513 isl_multi_pw_aff_free(mpa
);
6517 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6518 * with the domain of "pa". The domain of the result is the same
6521 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff(
6522 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6526 if (isl_space_match(pa
->dim
, isl_dim_param
, mpa
->space
, isl_dim_param
))
6527 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6529 pa
= isl_pw_aff_align_params(pa
, isl_multi_pw_aff_get_space(mpa
));
6530 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_pw_aff_get_space(pa
));
6532 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6534 isl_pw_aff_free(pa
);
6535 isl_multi_pw_aff_free(mpa
);
6539 /* Compute the pullback of "pa" by the function represented by "mpa".
6540 * In other words, plug in "mpa" in "pa".
6541 * "pa" and "mpa" are assumed to have been aligned.
6543 * The pullback is computed by applying "pa" to "mpa".
6545 static __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff_aligned(
6546 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6548 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6551 /* Compute the pullback of "pa" by the function represented by "mpa".
6552 * In other words, plug in "mpa" in "pa".
6554 * The pullback is computed by applying "pa" to "mpa".
6556 __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff(
6557 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6559 return isl_multi_pw_aff_apply_pw_aff(mpa
, pa
);
6562 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6563 * In other words, plug in "mpa2" in "mpa1".
6565 * The parameters of "mpa1" and "mpa2" are assumed to have been aligned.
6567 * We pullback each member of "mpa1" in turn.
6569 static __isl_give isl_multi_pw_aff
*
6570 isl_multi_pw_aff_pullback_multi_pw_aff_aligned(
6571 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6574 isl_space
*space
= NULL
;
6576 mpa1
= isl_multi_pw_aff_cow(mpa1
);
6580 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa2
),
6581 isl_multi_pw_aff_get_space(mpa1
));
6583 for (i
= 0; i
< mpa1
->n
; ++i
) {
6584 mpa1
->p
[i
] = isl_pw_aff_pullback_multi_pw_aff_aligned(
6585 mpa1
->p
[i
], isl_multi_pw_aff_copy(mpa2
));
6590 mpa1
= isl_multi_pw_aff_reset_space(mpa1
, space
);
6592 isl_multi_pw_aff_free(mpa2
);
6595 isl_space_free(space
);
6596 isl_multi_pw_aff_free(mpa1
);
6597 isl_multi_pw_aff_free(mpa2
);
6601 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6602 * In other words, plug in "mpa2" in "mpa1".
6604 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_pw_aff(
6605 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6607 return isl_multi_pw_aff_align_params_multi_multi_and(mpa1
, mpa2
,
6608 &isl_multi_pw_aff_pullback_multi_pw_aff_aligned
);
6611 /* Compare two isl_affs.
6613 * Return -1 if "aff1" is "smaller" than "aff2", 1 if "aff1" is "greater"
6614 * than "aff2" and 0 if they are equal.
6616 * The order is fairly arbitrary. We do consider expressions that only involve
6617 * earlier dimensions as "smaller".
6619 int isl_aff_plain_cmp(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
6632 cmp
= isl_local_space_cmp(aff1
->ls
, aff2
->ls
);
6636 last1
= isl_seq_last_non_zero(aff1
->v
->el
+ 1, aff1
->v
->size
- 1);
6637 last2
= isl_seq_last_non_zero(aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
6639 return last1
- last2
;
6641 return isl_seq_cmp(aff1
->v
->el
, aff2
->v
->el
, aff1
->v
->size
);
6644 /* Compare two isl_pw_affs.
6646 * Return -1 if "pa1" is "smaller" than "pa2", 1 if "pa1" is "greater"
6647 * than "pa2" and 0 if they are equal.
6649 * The order is fairly arbitrary. We do consider expressions that only involve
6650 * earlier dimensions as "smaller".
6652 int isl_pw_aff_plain_cmp(__isl_keep isl_pw_aff
*pa1
,
6653 __isl_keep isl_pw_aff
*pa2
)
6666 cmp
= isl_space_cmp(pa1
->dim
, pa2
->dim
);
6670 if (pa1
->n
!= pa2
->n
)
6671 return pa1
->n
- pa2
->n
;
6673 for (i
= 0; i
< pa1
->n
; ++i
) {
6674 cmp
= isl_set_plain_cmp(pa1
->p
[i
].set
, pa2
->p
[i
].set
);
6677 cmp
= isl_aff_plain_cmp(pa1
->p
[i
].aff
, pa2
->p
[i
].aff
);