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", isl_aff_free(aff
));
2418 if (dst_type
== isl_dim_div
|| src_type
== isl_dim_div
)
2419 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2420 "cannot move divs", isl_aff_free(aff
));
2421 if (dst_type
== isl_dim_in
)
2422 dst_type
= isl_dim_set
;
2423 if (src_type
== isl_dim_in
)
2424 src_type
= isl_dim_set
;
2426 if (src_pos
+ n
> isl_local_space_dim(aff
->ls
, src_type
))
2427 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2428 "range out of bounds", isl_aff_free(aff
));
2429 if (dst_type
== src_type
)
2430 isl_die(isl_aff_get_ctx(aff
), isl_error_unsupported
,
2431 "moving dims within the same type not supported",
2434 aff
= isl_aff_cow(aff
);
2438 g_src_pos
= 1 + isl_local_space_offset(aff
->ls
, src_type
) + src_pos
;
2439 g_dst_pos
= 1 + isl_local_space_offset(aff
->ls
, dst_type
) + dst_pos
;
2440 if (dst_type
> src_type
)
2443 aff
->v
= isl_vec_move_els(aff
->v
, g_dst_pos
, g_src_pos
, n
);
2444 aff
->ls
= isl_local_space_move_dims(aff
->ls
, dst_type
, dst_pos
,
2445 src_type
, src_pos
, n
);
2446 if (!aff
->v
|| !aff
->ls
)
2447 return isl_aff_free(aff
);
2449 aff
= sort_divs(aff
);
2454 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
2456 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
2457 return isl_pw_aff_alloc(dom
, aff
);
2461 #define PW isl_pw_aff
2465 #define EL_IS_ZERO is_empty
2469 #define IS_ZERO is_empty
2472 #undef DEFAULT_IS_ZERO
2473 #define DEFAULT_IS_ZERO 0
2480 #include <isl_pw_templ.c>
2482 static __isl_give isl_set
*align_params_pw_pw_set_and(
2483 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
2484 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2485 __isl_take isl_pw_aff
*pwaff2
))
2487 if (!pwaff1
|| !pwaff2
)
2489 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
2490 pwaff2
->dim
, isl_dim_param
))
2491 return fn(pwaff1
, pwaff2
);
2492 if (!isl_space_has_named_params(pwaff1
->dim
) ||
2493 !isl_space_has_named_params(pwaff2
->dim
))
2494 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
2495 "unaligned unnamed parameters", goto error
);
2496 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
2497 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
2498 return fn(pwaff1
, pwaff2
);
2500 isl_pw_aff_free(pwaff1
);
2501 isl_pw_aff_free(pwaff2
);
2505 /* Compute a piecewise quasi-affine expression with a domain that
2506 * is the union of those of pwaff1 and pwaff2 and such that on each
2507 * cell, the quasi-affine expression is the better (according to cmp)
2508 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
2509 * is defined on a given cell, then the associated expression
2510 * is the defined one.
2512 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2513 __isl_take isl_pw_aff
*pwaff2
,
2514 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
2515 __isl_take isl_aff
*aff2
))
2522 if (!pwaff1
|| !pwaff2
)
2525 ctx
= isl_space_get_ctx(pwaff1
->dim
);
2526 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
2527 isl_die(ctx
, isl_error_invalid
,
2528 "arguments should live in same space", goto error
);
2530 if (isl_pw_aff_is_empty(pwaff1
)) {
2531 isl_pw_aff_free(pwaff1
);
2535 if (isl_pw_aff_is_empty(pwaff2
)) {
2536 isl_pw_aff_free(pwaff2
);
2540 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
2541 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
2543 for (i
= 0; i
< pwaff1
->n
; ++i
) {
2544 set
= isl_set_copy(pwaff1
->p
[i
].set
);
2545 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2546 struct isl_set
*common
;
2549 common
= isl_set_intersect(
2550 isl_set_copy(pwaff1
->p
[i
].set
),
2551 isl_set_copy(pwaff2
->p
[j
].set
));
2552 better
= isl_set_from_basic_set(cmp(
2553 isl_aff_copy(pwaff2
->p
[j
].aff
),
2554 isl_aff_copy(pwaff1
->p
[i
].aff
)));
2555 better
= isl_set_intersect(common
, better
);
2556 if (isl_set_plain_is_empty(better
)) {
2557 isl_set_free(better
);
2560 set
= isl_set_subtract(set
, isl_set_copy(better
));
2562 res
= isl_pw_aff_add_piece(res
, better
,
2563 isl_aff_copy(pwaff2
->p
[j
].aff
));
2565 res
= isl_pw_aff_add_piece(res
, set
,
2566 isl_aff_copy(pwaff1
->p
[i
].aff
));
2569 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2570 set
= isl_set_copy(pwaff2
->p
[j
].set
);
2571 for (i
= 0; i
< pwaff1
->n
; ++i
)
2572 set
= isl_set_subtract(set
,
2573 isl_set_copy(pwaff1
->p
[i
].set
));
2574 res
= isl_pw_aff_add_piece(res
, set
,
2575 isl_aff_copy(pwaff2
->p
[j
].aff
));
2578 isl_pw_aff_free(pwaff1
);
2579 isl_pw_aff_free(pwaff2
);
2583 isl_pw_aff_free(pwaff1
);
2584 isl_pw_aff_free(pwaff2
);
2588 /* Compute a piecewise quasi-affine expression with a domain that
2589 * is the union of those of pwaff1 and pwaff2 and such that on each
2590 * cell, the quasi-affine expression is the maximum of those of pwaff1
2591 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2592 * cell, then the associated expression is the defined one.
2594 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2595 __isl_take isl_pw_aff
*pwaff2
)
2597 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
2600 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2601 __isl_take isl_pw_aff
*pwaff2
)
2603 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2607 /* Compute a piecewise quasi-affine expression with a domain that
2608 * is the union of those of pwaff1 and pwaff2 and such that on each
2609 * cell, the quasi-affine expression is the minimum of those of pwaff1
2610 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2611 * cell, then the associated expression is the defined one.
2613 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2614 __isl_take isl_pw_aff
*pwaff2
)
2616 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
2619 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2620 __isl_take isl_pw_aff
*pwaff2
)
2622 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2626 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2627 __isl_take isl_pw_aff
*pwaff2
, int max
)
2630 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
2632 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
2635 /* Construct a map with as domain the domain of pwaff and
2636 * one-dimensional range corresponding to the affine expressions.
2638 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2647 dim
= isl_pw_aff_get_space(pwaff
);
2648 map
= isl_map_empty(dim
);
2650 for (i
= 0; i
< pwaff
->n
; ++i
) {
2651 isl_basic_map
*bmap
;
2654 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
2655 map_i
= isl_map_from_basic_map(bmap
);
2656 map_i
= isl_map_intersect_domain(map_i
,
2657 isl_set_copy(pwaff
->p
[i
].set
));
2658 map
= isl_map_union_disjoint(map
, map_i
);
2661 isl_pw_aff_free(pwaff
);
2666 /* Construct a map with as domain the domain of pwaff and
2667 * one-dimensional range corresponding to the affine expressions.
2669 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2673 if (isl_space_is_set(pwaff
->dim
))
2674 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2675 "space of input is not a map", goto error
);
2676 return map_from_pw_aff(pwaff
);
2678 isl_pw_aff_free(pwaff
);
2682 /* Construct a one-dimensional set with as parameter domain
2683 * the domain of pwaff and the single set dimension
2684 * corresponding to the affine expressions.
2686 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2690 if (!isl_space_is_set(pwaff
->dim
))
2691 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2692 "space of input is not a set", goto error
);
2693 return map_from_pw_aff(pwaff
);
2695 isl_pw_aff_free(pwaff
);
2699 /* Return a set containing those elements in the domain
2700 * of pwaff where it is non-negative.
2702 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
2710 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2712 for (i
= 0; i
< pwaff
->n
; ++i
) {
2713 isl_basic_set
*bset
;
2717 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2718 bset
= aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2720 set_i
= isl_set_from_basic_set(bset
);
2721 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
2722 set
= isl_set_union_disjoint(set
, set_i
);
2725 isl_pw_aff_free(pwaff
);
2730 /* Return a set containing those elements in the domain
2731 * of pwaff where it is zero (if complement is 0) or not zero
2732 * (if complement is 1).
2734 * The pieces with a NaN never belong to the result since
2735 * NaN is neither zero nor non-zero.
2737 static __isl_give isl_set
*pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
,
2746 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2748 for (i
= 0; i
< pwaff
->n
; ++i
) {
2749 isl_basic_set
*bset
;
2750 isl_set
*set_i
, *zero
;
2753 if (isl_aff_is_nan(pwaff
->p
[i
].aff
))
2756 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2757 bset
= aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2759 zero
= isl_set_from_basic_set(bset
);
2760 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
2762 set_i
= isl_set_subtract(set_i
, zero
);
2764 set_i
= isl_set_intersect(set_i
, zero
);
2765 set
= isl_set_union_disjoint(set
, set_i
);
2768 isl_pw_aff_free(pwaff
);
2773 /* Return a set containing those elements in the domain
2774 * of pwaff where it is zero.
2776 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
2778 return pw_aff_zero_set(pwaff
, 0);
2781 /* Return a set containing those elements in the domain
2782 * of pwaff where it is not zero.
2784 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
2786 return pw_aff_zero_set(pwaff
, 1);
2789 /* Return a set containing those elements in the shared domain
2790 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2792 * We compute the difference on the shared domain and then construct
2793 * the set of values where this difference is non-negative.
2794 * If strict is set, we first subtract 1 from the difference.
2795 * If equal is set, we only return the elements where pwaff1 and pwaff2
2798 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
2799 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
2801 isl_set
*set1
, *set2
;
2803 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
2804 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
2805 set1
= isl_set_intersect(set1
, set2
);
2806 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
2807 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
2808 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
2811 isl_space
*dim
= isl_set_get_space(set1
);
2813 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2814 aff
= isl_aff_add_constant_si(aff
, -1);
2815 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
2820 return isl_pw_aff_zero_set(pwaff1
);
2821 return isl_pw_aff_nonneg_set(pwaff1
);
2824 /* Return a set containing those elements in the shared domain
2825 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2827 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2828 __isl_take isl_pw_aff
*pwaff2
)
2830 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
2833 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2834 __isl_take isl_pw_aff
*pwaff2
)
2836 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2839 /* Return a set containing those elements in the shared domain
2840 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2842 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2843 __isl_take isl_pw_aff
*pwaff2
)
2845 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2848 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2849 __isl_take isl_pw_aff
*pwaff2
)
2851 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2854 /* Return a set containing those elements in the shared domain
2855 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2857 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2858 __isl_take isl_pw_aff
*pwaff2
)
2860 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2863 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2864 __isl_take isl_pw_aff
*pwaff2
)
2866 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2869 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2870 __isl_take isl_pw_aff
*pwaff2
)
2872 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2875 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2876 __isl_take isl_pw_aff
*pwaff2
)
2878 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2881 /* Return a set containing those elements in the shared domain
2882 * of the elements of list1 and list2 where each element in list1
2883 * has the relation specified by "fn" with each element in list2.
2885 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2886 __isl_take isl_pw_aff_list
*list2
,
2887 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2888 __isl_take isl_pw_aff
*pwaff2
))
2894 if (!list1
|| !list2
)
2897 ctx
= isl_pw_aff_list_get_ctx(list1
);
2898 if (list1
->n
< 1 || list2
->n
< 1)
2899 isl_die(ctx
, isl_error_invalid
,
2900 "list should contain at least one element", goto error
);
2902 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2903 for (i
= 0; i
< list1
->n
; ++i
)
2904 for (j
= 0; j
< list2
->n
; ++j
) {
2907 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2908 isl_pw_aff_copy(list2
->p
[j
]));
2909 set
= isl_set_intersect(set
, set_ij
);
2912 isl_pw_aff_list_free(list1
);
2913 isl_pw_aff_list_free(list2
);
2916 isl_pw_aff_list_free(list1
);
2917 isl_pw_aff_list_free(list2
);
2921 /* Return a set containing those elements in the shared domain
2922 * of the elements of list1 and list2 where each element in list1
2923 * is equal to each element in list2.
2925 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2926 __isl_take isl_pw_aff_list
*list2
)
2928 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
2931 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
2932 __isl_take isl_pw_aff_list
*list2
)
2934 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
2937 /* Return a set containing those elements in the shared domain
2938 * of the elements of list1 and list2 where each element in list1
2939 * is less than or equal to each element in list2.
2941 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
2942 __isl_take isl_pw_aff_list
*list2
)
2944 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
2947 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
2948 __isl_take isl_pw_aff_list
*list2
)
2950 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
2953 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
2954 __isl_take isl_pw_aff_list
*list2
)
2956 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
2959 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
2960 __isl_take isl_pw_aff_list
*list2
)
2962 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
2966 /* Return a set containing those elements in the shared domain
2967 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2969 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2970 __isl_take isl_pw_aff
*pwaff2
)
2972 isl_set
*set_lt
, *set_gt
;
2974 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
2975 isl_pw_aff_copy(pwaff2
));
2976 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
2977 return isl_set_union_disjoint(set_lt
, set_gt
);
2980 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2981 __isl_take isl_pw_aff
*pwaff2
)
2983 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
2986 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
2991 if (isl_int_is_one(v
))
2993 if (!isl_int_is_pos(v
))
2994 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2995 "factor needs to be positive",
2996 return isl_pw_aff_free(pwaff
));
2997 pwaff
= isl_pw_aff_cow(pwaff
);
3003 for (i
= 0; i
< pwaff
->n
; ++i
) {
3004 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
3005 if (!pwaff
->p
[i
].aff
)
3006 return isl_pw_aff_free(pwaff
);
3012 /* Divide "pa" by "f".
3014 __isl_give isl_pw_aff
*isl_pw_aff_scale_down_val(__isl_take isl_pw_aff
*pa
,
3015 __isl_take isl_val
*f
)
3022 if (isl_val_is_one(f
)) {
3027 if (!isl_val_is_rat(f
))
3028 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3029 "expecting rational factor", goto error
);
3030 if (!isl_val_is_pos(f
))
3031 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
3032 "factor needs to be positive", goto error
);
3034 pa
= isl_pw_aff_cow(pa
);
3040 for (i
= 0; i
< pa
->n
; ++i
) {
3041 pa
->p
[i
].aff
= isl_aff_scale_down_val(pa
->p
[i
].aff
,
3050 isl_pw_aff_free(pa
);
3055 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
3059 pwaff
= isl_pw_aff_cow(pwaff
);
3065 for (i
= 0; i
< pwaff
->n
; ++i
) {
3066 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
3067 if (!pwaff
->p
[i
].aff
)
3068 return isl_pw_aff_free(pwaff
);
3074 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
3078 pwaff
= isl_pw_aff_cow(pwaff
);
3084 for (i
= 0; i
< pwaff
->n
; ++i
) {
3085 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
3086 if (!pwaff
->p
[i
].aff
)
3087 return isl_pw_aff_free(pwaff
);
3093 /* Assuming that "cond1" and "cond2" are disjoint,
3094 * return an affine expression that is equal to pwaff1 on cond1
3095 * and to pwaff2 on cond2.
3097 static __isl_give isl_pw_aff
*isl_pw_aff_select(
3098 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
3099 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
3101 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
3102 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
3104 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
3107 /* Return an affine expression that is equal to pwaff_true for elements
3108 * where "cond" is non-zero and to pwaff_false for elements where "cond"
3110 * That is, return cond ? pwaff_true : pwaff_false;
3112 * If "cond" involves and NaN, then we conservatively return a NaN
3113 * on its entire domain. In principle, we could consider the pieces
3114 * where it is NaN separately from those where it is not.
3116 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
3117 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
3119 isl_set
*cond_true
, *cond_false
;
3123 if (isl_pw_aff_involves_nan(cond
)) {
3124 isl_space
*space
= isl_pw_aff_get_domain_space(cond
);
3125 isl_local_space
*ls
= isl_local_space_from_space(space
);
3126 isl_pw_aff_free(cond
);
3127 isl_pw_aff_free(pwaff_true
);
3128 isl_pw_aff_free(pwaff_false
);
3129 return isl_pw_aff_nan_on_domain(ls
);
3132 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
3133 cond_false
= isl_pw_aff_zero_set(cond
);
3134 return isl_pw_aff_select(cond_true
, pwaff_true
,
3135 cond_false
, pwaff_false
);
3137 isl_pw_aff_free(cond
);
3138 isl_pw_aff_free(pwaff_true
);
3139 isl_pw_aff_free(pwaff_false
);
3143 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
3148 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
3151 /* Check whether pwaff is a piecewise constant.
3153 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
3160 for (i
= 0; i
< pwaff
->n
; ++i
) {
3161 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
3162 if (is_cst
< 0 || !is_cst
)
3169 /* Return the product of "aff1" and "aff2".
3171 * If either of the two is NaN, then the result is NaN.
3173 * Otherwise, at least one of "aff1" or "aff2" needs to be a constant.
3175 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
3176 __isl_take isl_aff
*aff2
)
3181 if (isl_aff_is_nan(aff1
)) {
3185 if (isl_aff_is_nan(aff2
)) {
3190 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
3191 return isl_aff_mul(aff2
, aff1
);
3193 if (!isl_aff_is_cst(aff2
))
3194 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
3195 "at least one affine expression should be constant",
3198 aff1
= isl_aff_cow(aff1
);
3202 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
3203 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
3213 /* Divide "aff1" by "aff2", assuming "aff2" is a constant.
3215 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
3216 __isl_take isl_aff
*aff2
)
3221 is_cst
= isl_aff_is_cst(aff2
);
3225 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
3226 "second argument should be a constant", goto error
);
3231 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
3233 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
3234 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
3237 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
3238 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
3241 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
3242 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
3253 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
3254 __isl_take isl_pw_aff
*pwaff2
)
3256 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
3259 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
3260 __isl_take isl_pw_aff
*pwaff2
)
3262 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
3265 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
3266 __isl_take isl_pw_aff
*pwaff2
)
3268 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
3271 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
3272 __isl_take isl_pw_aff
*pwaff2
)
3274 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
3277 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
3278 __isl_take isl_pw_aff
*pwaff2
)
3280 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
3283 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
3284 __isl_take isl_pw_aff
*pa2
)
3286 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
3289 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
3291 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
3292 __isl_take isl_pw_aff
*pa2
)
3296 is_cst
= isl_pw_aff_is_cst(pa2
);
3300 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3301 "second argument should be a piecewise constant",
3303 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
3305 isl_pw_aff_free(pa1
);
3306 isl_pw_aff_free(pa2
);
3310 /* Compute the quotient of the integer division of "pa1" by "pa2"
3311 * with rounding towards zero.
3312 * "pa2" is assumed to be a piecewise constant.
3314 * In particular, return
3316 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
3319 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
3320 __isl_take isl_pw_aff
*pa2
)
3326 is_cst
= isl_pw_aff_is_cst(pa2
);
3330 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3331 "second argument should be a piecewise constant",
3334 pa1
= isl_pw_aff_div(pa1
, pa2
);
3336 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
3337 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
3338 c
= isl_pw_aff_ceil(pa1
);
3339 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
3341 isl_pw_aff_free(pa1
);
3342 isl_pw_aff_free(pa2
);
3346 /* Compute the remainder of the integer division of "pa1" by "pa2"
3347 * with rounding towards zero.
3348 * "pa2" is assumed to be a piecewise constant.
3350 * In particular, return
3352 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
3355 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
3356 __isl_take isl_pw_aff
*pa2
)
3361 is_cst
= isl_pw_aff_is_cst(pa2
);
3365 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
3366 "second argument should be a piecewise constant",
3368 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
3369 res
= isl_pw_aff_mul(pa2
, res
);
3370 res
= isl_pw_aff_sub(pa1
, res
);
3373 isl_pw_aff_free(pa1
);
3374 isl_pw_aff_free(pa2
);
3378 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
3379 __isl_take isl_pw_aff
*pwaff2
)
3384 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
3385 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
3386 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
3387 isl_pw_aff_copy(pwaff2
));
3388 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
3389 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
3392 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
3393 __isl_take isl_pw_aff
*pwaff2
)
3395 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
3398 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3399 __isl_take isl_pw_aff
*pwaff2
)
3404 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
3405 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
3406 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
3407 isl_pw_aff_copy(pwaff2
));
3408 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
3409 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
3412 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3413 __isl_take isl_pw_aff
*pwaff2
)
3415 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
3418 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
3419 __isl_take isl_pw_aff_list
*list
,
3420 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
3421 __isl_take isl_pw_aff
*pwaff2
))
3430 ctx
= isl_pw_aff_list_get_ctx(list
);
3432 isl_die(ctx
, isl_error_invalid
,
3433 "list should contain at least one element", goto error
);
3435 res
= isl_pw_aff_copy(list
->p
[0]);
3436 for (i
= 1; i
< list
->n
; ++i
)
3437 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
3439 isl_pw_aff_list_free(list
);
3442 isl_pw_aff_list_free(list
);
3446 /* Return an isl_pw_aff that maps each element in the intersection of the
3447 * domains of the elements of list to the minimal corresponding affine
3450 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
3452 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
3455 /* Return an isl_pw_aff that maps each element in the intersection of the
3456 * domains of the elements of list to the maximal corresponding affine
3459 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
3461 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
3464 /* Mark the domains of "pwaff" as rational.
3466 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__isl_take isl_pw_aff
*pwaff
)
3470 pwaff
= isl_pw_aff_cow(pwaff
);
3476 for (i
= 0; i
< pwaff
->n
; ++i
) {
3477 pwaff
->p
[i
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
3478 if (!pwaff
->p
[i
].set
)
3479 return isl_pw_aff_free(pwaff
);
3485 /* Mark the domains of the elements of "list" as rational.
3487 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
3488 __isl_take isl_pw_aff_list
*list
)
3498 for (i
= 0; i
< n
; ++i
) {
3501 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
3502 pa
= isl_pw_aff_set_rational(pa
);
3503 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
3509 /* Do the parameters of "aff" match those of "space"?
3511 int isl_aff_matching_params(__isl_keep isl_aff
*aff
,
3512 __isl_keep isl_space
*space
)
3514 isl_space
*aff_space
;
3520 aff_space
= isl_aff_get_domain_space(aff
);
3522 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3524 isl_space_free(aff_space
);
3528 /* Check that the domain space of "aff" matches "space".
3530 * Return 0 on success and -1 on error.
3532 int isl_aff_check_match_domain_space(__isl_keep isl_aff
*aff
,
3533 __isl_keep isl_space
*space
)
3535 isl_space
*aff_space
;
3541 aff_space
= isl_aff_get_domain_space(aff
);
3543 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3547 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3548 "parameters don't match", goto error
);
3549 match
= isl_space_tuple_match(space
, isl_dim_in
,
3550 aff_space
, isl_dim_set
);
3554 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3555 "domains don't match", goto error
);
3556 isl_space_free(aff_space
);
3559 isl_space_free(aff_space
);
3565 #define NO_INTERSECT_DOMAIN
3568 #include <isl_multi_templ.c>
3571 #undef NO_INTERSECT_DOMAIN
3573 /* Remove any internal structure of the domain of "ma".
3574 * If there is any such internal structure in the input,
3575 * then the name of the corresponding space is also removed.
3577 __isl_give isl_multi_aff
*isl_multi_aff_flatten_domain(
3578 __isl_take isl_multi_aff
*ma
)
3585 if (!ma
->space
->nested
[0])
3588 space
= isl_multi_aff_get_space(ma
);
3589 space
= isl_space_flatten_domain(space
);
3590 ma
= isl_multi_aff_reset_space(ma
, space
);
3595 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3596 * of the space to its domain.
3598 __isl_give isl_multi_aff
*isl_multi_aff_domain_map(__isl_take isl_space
*space
)
3601 isl_local_space
*ls
;
3606 if (!isl_space_is_map(space
))
3607 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3608 "not a map space", goto error
);
3610 n_in
= isl_space_dim(space
, isl_dim_in
);
3611 space
= isl_space_domain_map(space
);
3613 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3615 isl_space_free(space
);
3619 space
= isl_space_domain(space
);
3620 ls
= isl_local_space_from_space(space
);
3621 for (i
= 0; i
< n_in
; ++i
) {
3624 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3626 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3628 isl_local_space_free(ls
);
3631 isl_space_free(space
);
3635 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3636 * of the space to its range.
3638 __isl_give isl_multi_aff
*isl_multi_aff_range_map(__isl_take isl_space
*space
)
3641 isl_local_space
*ls
;
3646 if (!isl_space_is_map(space
))
3647 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3648 "not a map space", goto error
);
3650 n_in
= isl_space_dim(space
, isl_dim_in
);
3651 n_out
= isl_space_dim(space
, isl_dim_out
);
3652 space
= isl_space_range_map(space
);
3654 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3656 isl_space_free(space
);
3660 space
= isl_space_domain(space
);
3661 ls
= isl_local_space_from_space(space
);
3662 for (i
= 0; i
< n_out
; ++i
) {
3665 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3666 isl_dim_set
, n_in
+ i
);
3667 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3669 isl_local_space_free(ls
);
3672 isl_space_free(space
);
3676 /* Given the space of a set and a range of set dimensions,
3677 * construct an isl_multi_aff that projects out those dimensions.
3679 __isl_give isl_multi_aff
*isl_multi_aff_project_out_map(
3680 __isl_take isl_space
*space
, enum isl_dim_type type
,
3681 unsigned first
, unsigned n
)
3684 isl_local_space
*ls
;
3689 if (!isl_space_is_set(space
))
3690 isl_die(isl_space_get_ctx(space
), isl_error_unsupported
,
3691 "expecting set space", goto error
);
3692 if (type
!= isl_dim_set
)
3693 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3694 "only set dimensions can be projected out", goto error
);
3696 dim
= isl_space_dim(space
, isl_dim_set
);
3697 if (first
+ n
> dim
)
3698 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
3699 "range out of bounds", goto error
);
3701 space
= isl_space_from_domain(space
);
3702 space
= isl_space_add_dims(space
, isl_dim_out
, dim
- n
);
3705 return isl_multi_aff_alloc(space
);
3707 ma
= isl_multi_aff_alloc(isl_space_copy(space
));
3708 space
= isl_space_domain(space
);
3709 ls
= isl_local_space_from_space(space
);
3711 for (i
= 0; i
< first
; ++i
) {
3714 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3716 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3719 for (i
= 0; i
< dim
- (first
+ n
); ++i
) {
3722 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3723 isl_dim_set
, first
+ n
+ i
);
3724 ma
= isl_multi_aff_set_aff(ma
, first
+ i
, aff
);
3727 isl_local_space_free(ls
);
3730 isl_space_free(space
);
3734 /* Given the space of a set and a range of set dimensions,
3735 * construct an isl_pw_multi_aff that projects out those dimensions.
3737 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_project_out_map(
3738 __isl_take isl_space
*space
, enum isl_dim_type type
,
3739 unsigned first
, unsigned n
)
3743 ma
= isl_multi_aff_project_out_map(space
, type
, first
, n
);
3744 return isl_pw_multi_aff_from_multi_aff(ma
);
3747 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
3750 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
3751 __isl_take isl_multi_aff
*ma
)
3753 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
3754 return isl_pw_multi_aff_alloc(dom
, ma
);
3757 /* Create a piecewise multi-affine expression in the given space that maps each
3758 * input dimension to the corresponding output dimension.
3760 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
3761 __isl_take isl_space
*space
)
3763 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
3766 /* Add "ma2" to "ma1" and return the result.
3768 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
3770 static __isl_give isl_multi_aff
*isl_multi_aff_add_aligned(
3771 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3773 return isl_multi_aff_bin_op(maff1
, maff2
, &isl_aff_add
);
3776 /* Add "ma2" to "ma1" and return the result.
3778 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*ma1
,
3779 __isl_take isl_multi_aff
*ma2
)
3781 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
3782 &isl_multi_aff_add_aligned
);
3785 /* Subtract "ma2" from "ma1" and return the result.
3787 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
3789 static __isl_give isl_multi_aff
*isl_multi_aff_sub_aligned(
3790 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
3792 return isl_multi_aff_bin_op(ma1
, ma2
, &isl_aff_sub
);
3795 /* Subtract "ma2" from "ma1" and return the result.
3797 __isl_give isl_multi_aff
*isl_multi_aff_sub(__isl_take isl_multi_aff
*ma1
,
3798 __isl_take isl_multi_aff
*ma2
)
3800 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
3801 &isl_multi_aff_sub_aligned
);
3804 /* Exploit the equalities in "eq" to simplify the affine expressions.
3806 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
3807 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
3811 maff
= isl_multi_aff_cow(maff
);
3815 for (i
= 0; i
< maff
->n
; ++i
) {
3816 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
3817 isl_basic_set_copy(eq
));
3822 isl_basic_set_free(eq
);
3825 isl_basic_set_free(eq
);
3826 isl_multi_aff_free(maff
);
3830 /* Given f, return floor(f).
3832 __isl_give isl_multi_aff
*isl_multi_aff_floor(__isl_take isl_multi_aff
*ma
)
3836 ma
= isl_multi_aff_cow(ma
);
3840 for (i
= 0; i
< ma
->n
; ++i
) {
3841 ma
->p
[i
] = isl_aff_floor(ma
->p
[i
]);
3843 return isl_multi_aff_free(ma
);
3849 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
3854 maff
= isl_multi_aff_cow(maff
);
3858 for (i
= 0; i
< maff
->n
; ++i
) {
3859 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
3861 return isl_multi_aff_free(maff
);
3867 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
3868 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3870 maff1
= isl_multi_aff_add(maff1
, maff2
);
3871 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
3875 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
3883 /* Return the set of domain elements where "ma1" is lexicographically
3884 * smaller than or equal to "ma2".
3886 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
3887 __isl_take isl_multi_aff
*ma2
)
3889 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
3892 /* Return the set of domain elements where "ma1" is lexicographically
3893 * greater than or equal to "ma2".
3895 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
3896 __isl_take isl_multi_aff
*ma2
)
3899 isl_map
*map1
, *map2
;
3902 map1
= isl_map_from_multi_aff(ma1
);
3903 map2
= isl_map_from_multi_aff(ma2
);
3904 map
= isl_map_range_product(map1
, map2
);
3905 space
= isl_space_range(isl_map_get_space(map
));
3906 space
= isl_space_domain(isl_space_unwrap(space
));
3907 ge
= isl_map_lex_ge(space
);
3908 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
3910 return isl_map_domain(map
);
3914 #define PW isl_pw_multi_aff
3916 #define EL isl_multi_aff
3918 #define EL_IS_ZERO is_empty
3922 #define IS_ZERO is_empty
3925 #undef DEFAULT_IS_ZERO
3926 #define DEFAULT_IS_ZERO 0
3931 #define NO_INVOLVES_DIMS
3932 #define NO_INSERT_DIMS
3936 #include <isl_pw_templ.c>
3939 #define UNION isl_union_pw_multi_aff
3941 #define PART isl_pw_multi_aff
3943 #define PARTS pw_multi_aff
3944 #define ALIGN_DOMAIN
3948 #include <isl_union_templ.c>
3950 /* Given a function "cmp" that returns the set of elements where
3951 * "ma1" is "better" than "ma2", return the intersection of this
3952 * set with "dom1" and "dom2".
3954 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
3955 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
3956 __isl_keep isl_multi_aff
*ma2
,
3957 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3958 __isl_take isl_multi_aff
*ma2
))
3964 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
3965 is_empty
= isl_set_plain_is_empty(common
);
3966 if (is_empty
>= 0 && is_empty
)
3969 return isl_set_free(common
);
3970 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
3971 better
= isl_set_intersect(common
, better
);
3976 /* Given a function "cmp" that returns the set of elements where
3977 * "ma1" is "better" than "ma2", return a piecewise multi affine
3978 * expression defined on the union of the definition domains
3979 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
3980 * "pma2" on each cell. If only one of the two input functions
3981 * is defined on a given cell, then it is considered the best.
3983 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
3984 __isl_take isl_pw_multi_aff
*pma1
,
3985 __isl_take isl_pw_multi_aff
*pma2
,
3986 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3987 __isl_take isl_multi_aff
*ma2
))
3990 isl_pw_multi_aff
*res
= NULL
;
3992 isl_set
*set
= NULL
;
3997 ctx
= isl_space_get_ctx(pma1
->dim
);
3998 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
3999 isl_die(ctx
, isl_error_invalid
,
4000 "arguments should live in the same space", goto error
);
4002 if (isl_pw_multi_aff_is_empty(pma1
)) {
4003 isl_pw_multi_aff_free(pma1
);
4007 if (isl_pw_multi_aff_is_empty(pma2
)) {
4008 isl_pw_multi_aff_free(pma2
);
4012 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
4013 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
4015 for (i
= 0; i
< pma1
->n
; ++i
) {
4016 set
= isl_set_copy(pma1
->p
[i
].set
);
4017 for (j
= 0; j
< pma2
->n
; ++j
) {
4021 better
= shared_and_better(pma2
->p
[j
].set
,
4022 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
4023 pma1
->p
[i
].maff
, cmp
);
4024 is_empty
= isl_set_plain_is_empty(better
);
4025 if (is_empty
< 0 || is_empty
) {
4026 isl_set_free(better
);
4031 set
= isl_set_subtract(set
, isl_set_copy(better
));
4033 res
= isl_pw_multi_aff_add_piece(res
, better
,
4034 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4036 res
= isl_pw_multi_aff_add_piece(res
, set
,
4037 isl_multi_aff_copy(pma1
->p
[i
].maff
));
4040 for (j
= 0; j
< pma2
->n
; ++j
) {
4041 set
= isl_set_copy(pma2
->p
[j
].set
);
4042 for (i
= 0; i
< pma1
->n
; ++i
)
4043 set
= isl_set_subtract(set
,
4044 isl_set_copy(pma1
->p
[i
].set
));
4045 res
= isl_pw_multi_aff_add_piece(res
, set
,
4046 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4049 isl_pw_multi_aff_free(pma1
);
4050 isl_pw_multi_aff_free(pma2
);
4054 isl_pw_multi_aff_free(pma1
);
4055 isl_pw_multi_aff_free(pma2
);
4057 return isl_pw_multi_aff_free(res
);
4060 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
4061 __isl_take isl_pw_multi_aff
*pma1
,
4062 __isl_take isl_pw_multi_aff
*pma2
)
4064 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
4067 /* Given two piecewise multi affine expressions, return a piecewise
4068 * multi-affine expression defined on the union of the definition domains
4069 * of the inputs that is equal to the lexicographic maximum of the two
4070 * inputs on each cell. If only one of the two inputs is defined on
4071 * a given cell, then it is considered to be the maximum.
4073 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
4074 __isl_take isl_pw_multi_aff
*pma1
,
4075 __isl_take isl_pw_multi_aff
*pma2
)
4077 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4078 &pw_multi_aff_union_lexmax
);
4081 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
4082 __isl_take isl_pw_multi_aff
*pma1
,
4083 __isl_take isl_pw_multi_aff
*pma2
)
4085 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
4088 /* Given two piecewise multi affine expressions, return a piecewise
4089 * multi-affine expression defined on the union of the definition domains
4090 * of the inputs that is equal to the lexicographic minimum of the two
4091 * inputs on each cell. If only one of the two inputs is defined on
4092 * a given cell, then it is considered to be the minimum.
4094 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
4095 __isl_take isl_pw_multi_aff
*pma1
,
4096 __isl_take isl_pw_multi_aff
*pma2
)
4098 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4099 &pw_multi_aff_union_lexmin
);
4102 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
4103 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4105 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
4106 &isl_multi_aff_add
);
4109 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
4110 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4112 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4116 static __isl_give isl_pw_multi_aff
*pw_multi_aff_sub(
4117 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4119 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
4120 &isl_multi_aff_sub
);
4123 /* Subtract "pma2" from "pma1" and return the result.
4125 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_sub(
4126 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4128 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4132 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
4133 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4135 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
4138 /* Given two piecewise multi-affine expressions A -> B and C -> D,
4139 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
4141 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
4142 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4146 isl_pw_multi_aff
*res
;
4151 n
= pma1
->n
* pma2
->n
;
4152 space
= isl_space_product(isl_space_copy(pma1
->dim
),
4153 isl_space_copy(pma2
->dim
));
4154 res
= isl_pw_multi_aff_alloc_size(space
, n
);
4156 for (i
= 0; i
< pma1
->n
; ++i
) {
4157 for (j
= 0; j
< pma2
->n
; ++j
) {
4161 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
4162 isl_set_copy(pma2
->p
[j
].set
));
4163 ma
= isl_multi_aff_product(
4164 isl_multi_aff_copy(pma1
->p
[i
].maff
),
4165 isl_multi_aff_copy(pma2
->p
[j
].maff
));
4166 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
4170 isl_pw_multi_aff_free(pma1
);
4171 isl_pw_multi_aff_free(pma2
);
4174 isl_pw_multi_aff_free(pma1
);
4175 isl_pw_multi_aff_free(pma2
);
4179 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
4180 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4182 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4183 &pw_multi_aff_product
);
4186 /* Construct a map mapping the domain of the piecewise multi-affine expression
4187 * to its range, with each dimension in the range equated to the
4188 * corresponding affine expression on its cell.
4190 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
4198 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
4200 for (i
= 0; i
< pma
->n
; ++i
) {
4201 isl_multi_aff
*maff
;
4202 isl_basic_map
*bmap
;
4205 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
4206 bmap
= isl_basic_map_from_multi_aff(maff
);
4207 map_i
= isl_map_from_basic_map(bmap
);
4208 map_i
= isl_map_intersect_domain(map_i
,
4209 isl_set_copy(pma
->p
[i
].set
));
4210 map
= isl_map_union_disjoint(map
, map_i
);
4213 isl_pw_multi_aff_free(pma
);
4217 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
4222 if (!isl_space_is_set(pma
->dim
))
4223 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4224 "isl_pw_multi_aff cannot be converted into an isl_set",
4227 return isl_map_from_pw_multi_aff(pma
);
4229 isl_pw_multi_aff_free(pma
);
4233 /* Given a basic map with a single output dimension that is defined
4234 * in terms of the parameters and input dimensions using an equality,
4235 * extract an isl_aff that expresses the output dimension in terms
4236 * of the parameters and input dimensions.
4238 * This function shares some similarities with
4239 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
4241 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
4242 __isl_take isl_basic_map
*bmap
)
4247 isl_local_space
*ls
;
4252 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
4253 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
4254 "basic map should have a single output dimension",
4256 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
4257 total
= isl_basic_map_total_dim(bmap
);
4258 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
4259 if (isl_int_is_zero(bmap
->eq
[i
][offset
]))
4261 if (isl_seq_first_non_zero(bmap
->eq
[i
] + offset
+ 1,
4262 1 + total
- (offset
+ 1)) != -1)
4266 if (i
>= bmap
->n_eq
)
4267 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
4268 "unable to find suitable equality", goto error
);
4269 ls
= isl_basic_map_get_local_space(bmap
);
4270 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
4273 if (isl_int_is_neg(bmap
->eq
[i
][offset
]))
4274 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
4276 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
4277 isl_seq_clr(aff
->v
->el
+ 1 + offset
, aff
->v
->size
- (1 + offset
));
4278 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[i
][offset
]);
4279 isl_basic_map_free(bmap
);
4281 aff
= isl_aff_remove_unused_divs(aff
);
4284 isl_basic_map_free(bmap
);
4288 /* Given a basic map where each output dimension is defined
4289 * in terms of the parameters and input dimensions using an equality,
4290 * extract an isl_multi_aff that expresses the output dimensions in terms
4291 * of the parameters and input dimensions.
4293 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
4294 __isl_take isl_basic_map
*bmap
)
4303 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
4304 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
4306 for (i
= 0; i
< n_out
; ++i
) {
4307 isl_basic_map
*bmap_i
;
4310 bmap_i
= isl_basic_map_copy(bmap
);
4311 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
4312 i
+ 1, n_out
- (1 + i
));
4313 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
4314 aff
= extract_isl_aff_from_basic_map(bmap_i
);
4315 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4318 isl_basic_map_free(bmap
);
4323 /* Given a basic set where each set dimension is defined
4324 * in terms of the parameters using an equality,
4325 * extract an isl_multi_aff that expresses the set dimensions in terms
4326 * of the parameters.
4328 __isl_give isl_multi_aff
*isl_multi_aff_from_basic_set_equalities(
4329 __isl_take isl_basic_set
*bset
)
4331 return extract_isl_multi_aff_from_basic_map(bset
);
4334 /* Create an isl_pw_multi_aff that is equivalent to
4335 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
4336 * The given basic map is such that each output dimension is defined
4337 * in terms of the parameters and input dimensions using an equality.
4339 * Since some applications expect the result of isl_pw_multi_aff_from_map
4340 * to only contain integer affine expressions, we compute the floor
4341 * of the expression before returning.
4343 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
4344 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
4348 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
4349 ma
= isl_multi_aff_floor(ma
);
4350 return isl_pw_multi_aff_alloc(domain
, ma
);
4353 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4354 * This obviously only works if the input "map" is single-valued.
4355 * If so, we compute the lexicographic minimum of the image in the form
4356 * of an isl_pw_multi_aff. Since the image is unique, it is equal
4357 * to its lexicographic minimum.
4358 * If the input is not single-valued, we produce an error.
4360 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
4361 __isl_take isl_map
*map
)
4365 isl_pw_multi_aff
*pma
;
4367 sv
= isl_map_is_single_valued(map
);
4371 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
4372 "map is not single-valued", goto error
);
4373 map
= isl_map_make_disjoint(map
);
4377 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
4379 for (i
= 0; i
< map
->n
; ++i
) {
4380 isl_pw_multi_aff
*pma_i
;
4381 isl_basic_map
*bmap
;
4382 bmap
= isl_basic_map_copy(map
->p
[i
]);
4383 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
4384 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
4394 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4395 * taking into account that the output dimension at position "d"
4396 * can be represented as
4398 * x = floor((e(...) + c1) / m)
4400 * given that constraint "i" is of the form
4402 * e(...) + c1 - m x >= 0
4405 * Let "map" be of the form
4409 * We construct a mapping
4411 * A -> [A -> x = floor(...)]
4413 * apply that to the map, obtaining
4415 * [A -> x = floor(...)] -> B
4417 * and equate dimension "d" to x.
4418 * We then compute a isl_pw_multi_aff representation of the resulting map
4419 * and plug in the mapping above.
4421 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
4422 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
4426 isl_local_space
*ls
;
4434 isl_pw_multi_aff
*pma
;
4437 is_set
= isl_map_is_set(map
);
4439 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
4440 ctx
= isl_map_get_ctx(map
);
4441 space
= isl_space_domain(isl_map_get_space(map
));
4442 n_in
= isl_space_dim(space
, isl_dim_set
);
4443 n
= isl_space_dim(space
, isl_dim_all
);
4445 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
4447 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
4448 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
4450 isl_basic_map_free(hull
);
4452 ls
= isl_local_space_from_space(isl_space_copy(space
));
4453 aff
= isl_aff_alloc_vec(ls
, v
);
4454 aff
= isl_aff_floor(aff
);
4456 isl_space_free(space
);
4457 ma
= isl_multi_aff_from_aff(aff
);
4459 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
4460 ma
= isl_multi_aff_range_product(ma
,
4461 isl_multi_aff_from_aff(aff
));
4464 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
4465 map
= isl_map_apply_domain(map
, insert
);
4466 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
4467 pma
= isl_pw_multi_aff_from_map(map
);
4468 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
4473 /* Is constraint "c" of the form
4475 * e(...) + c1 - m x >= 0
4479 * -e(...) + c2 + m x >= 0
4481 * where m > 1 and e only depends on parameters and input dimemnsions?
4483 * "offset" is the offset of the output dimensions
4484 * "pos" is the position of output dimension x.
4486 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
4488 if (isl_int_is_zero(c
[offset
+ d
]))
4490 if (isl_int_is_one(c
[offset
+ d
]))
4492 if (isl_int_is_negone(c
[offset
+ d
]))
4494 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
4496 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
4497 total
- (offset
+ d
+ 1)) != -1)
4502 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4504 * As a special case, we first check if there is any pair of constraints,
4505 * shared by all the basic maps in "map" that force a given dimension
4506 * to be equal to the floor of some affine combination of the input dimensions.
4508 * In particular, if we can find two constraints
4510 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
4514 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
4516 * where m > 1 and e only depends on parameters and input dimemnsions,
4519 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
4521 * then we know that we can take
4523 * x = floor((e(...) + c1) / m)
4525 * without having to perform any computation.
4527 * Note that we know that
4531 * If c1 + c2 were 0, then we would have detected an equality during
4532 * simplification. If c1 + c2 were negative, then we would have detected
4535 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
4536 __isl_take isl_map
*map
)
4542 isl_basic_map
*hull
;
4544 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
4549 dim
= isl_map_dim(map
, isl_dim_out
);
4550 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
4551 total
= 1 + isl_basic_map_total_dim(hull
);
4553 for (d
= 0; d
< dim
; ++d
) {
4554 for (i
= 0; i
< n
; ++i
) {
4555 if (!is_potential_div_constraint(hull
->ineq
[i
],
4558 for (j
= i
+ 1; j
< n
; ++j
) {
4559 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
4560 hull
->ineq
[j
] + 1, total
- 1))
4562 isl_int_add(sum
, hull
->ineq
[i
][0],
4564 if (isl_int_abs_lt(sum
,
4565 hull
->ineq
[i
][offset
+ d
]))
4572 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
4574 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
4578 isl_basic_map_free(hull
);
4579 return pw_multi_aff_from_map_base(map
);
4582 isl_basic_map_free(hull
);
4586 /* Given an affine expression
4588 * [A -> B] -> f(A,B)
4590 * construct an isl_multi_aff
4594 * such that dimension "d" in B' is set to "aff" and the remaining
4595 * dimensions are set equal to the corresponding dimensions in B.
4596 * "n_in" is the dimension of the space A.
4597 * "n_out" is the dimension of the space B.
4599 * If "is_set" is set, then the affine expression is of the form
4603 * and we construct an isl_multi_aff
4607 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
4608 unsigned n_in
, unsigned n_out
, int is_set
)
4612 isl_space
*space
, *space2
;
4613 isl_local_space
*ls
;
4615 space
= isl_aff_get_domain_space(aff
);
4616 ls
= isl_local_space_from_space(isl_space_copy(space
));
4617 space2
= isl_space_copy(space
);
4619 space2
= isl_space_range(isl_space_unwrap(space2
));
4620 space
= isl_space_map_from_domain_and_range(space
, space2
);
4621 ma
= isl_multi_aff_alloc(space
);
4622 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
4624 for (i
= 0; i
< n_out
; ++i
) {
4627 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
4628 isl_dim_set
, n_in
+ i
);
4629 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4632 isl_local_space_free(ls
);
4637 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4638 * taking into account that the dimension at position "d" can be written as
4640 * x = m a + f(..) (1)
4642 * where m is equal to "gcd".
4643 * "i" is the index of the equality in "hull" that defines f(..).
4644 * In particular, the equality is of the form
4646 * f(..) - x + m g(existentials) = 0
4650 * -f(..) + x + m g(existentials) = 0
4652 * We basically plug (1) into "map", resulting in a map with "a"
4653 * in the range instead of "x". The corresponding isl_pw_multi_aff
4654 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
4656 * Specifically, given the input map
4660 * We first wrap it into a set
4664 * and define (1) on top of the corresponding space, resulting in "aff".
4665 * We use this to create an isl_multi_aff that maps the output position "d"
4666 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
4667 * We plug this into the wrapped map, unwrap the result and compute the
4668 * corresponding isl_pw_multi_aff.
4669 * The result is an expression
4677 * so that we can plug that into "aff", after extending the latter to
4683 * If "map" is actually a set, then there is no "A" space, meaning
4684 * that we do not need to perform any wrapping, and that the result
4685 * of the recursive call is of the form
4689 * which is plugged into a mapping of the form
4693 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
4694 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
4699 isl_local_space
*ls
;
4702 isl_pw_multi_aff
*pma
, *id
;
4708 is_set
= isl_map_is_set(map
);
4710 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
4711 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4712 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4717 set
= isl_map_wrap(map
);
4718 space
= isl_space_map_from_set(isl_set_get_space(set
));
4719 ma
= isl_multi_aff_identity(space
);
4720 ls
= isl_local_space_from_space(isl_set_get_space(set
));
4721 aff
= isl_aff_alloc(ls
);
4723 isl_int_set_si(aff
->v
->el
[0], 1);
4724 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
4725 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
4728 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
4730 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
4732 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
4733 set
= isl_set_preimage_multi_aff(set
, ma
);
4735 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
4740 map
= isl_set_unwrap(set
);
4741 pma
= isl_pw_multi_aff_from_map(set
);
4744 space
= isl_pw_multi_aff_get_domain_space(pma
);
4745 space
= isl_space_map_from_set(space
);
4746 id
= isl_pw_multi_aff_identity(space
);
4747 pma
= isl_pw_multi_aff_range_product(id
, pma
);
4749 id
= isl_pw_multi_aff_from_multi_aff(ma
);
4750 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
4752 isl_basic_map_free(hull
);
4756 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4758 * As a special case, we first check if all output dimensions are uniquely
4759 * defined in terms of the parameters and input dimensions over the entire
4760 * domain. If so, we extract the desired isl_pw_multi_aff directly
4761 * from the affine hull of "map" and its domain.
4763 * Otherwise, we check if any of the output dimensions is "strided".
4764 * That is, we check if can be written as
4768 * with m greater than 1, a some combination of existentiall quantified
4769 * variables and f and expression in the parameters and input dimensions.
4770 * If so, we remove the stride in pw_multi_aff_from_map_stride.
4772 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
4775 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
4779 isl_basic_map
*hull
;
4789 hull
= isl_map_affine_hull(isl_map_copy(map
));
4790 sv
= isl_basic_map_plain_is_single_valued(hull
);
4792 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
4794 hull
= isl_basic_map_free(hull
);
4798 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
4799 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
4802 isl_basic_map_free(hull
);
4803 return pw_multi_aff_from_map_check_div(map
);
4808 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4809 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4811 for (i
= 0; i
< n_out
; ++i
) {
4812 for (j
= 0; j
< hull
->n_eq
; ++j
) {
4813 isl_int
*eq
= hull
->eq
[j
];
4814 isl_pw_multi_aff
*res
;
4816 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
4817 !isl_int_is_negone(eq
[o_out
+ i
]))
4819 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
4821 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
4822 n_out
- (i
+ 1)) != -1)
4824 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
4825 if (isl_int_is_zero(gcd
))
4827 if (isl_int_is_one(gcd
))
4830 res
= pw_multi_aff_from_map_stride(map
, hull
,
4838 isl_basic_map_free(hull
);
4839 return pw_multi_aff_from_map_check_div(map
);
4845 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
4847 return isl_pw_multi_aff_from_map(set
);
4850 /* Convert "map" into an isl_pw_multi_aff (if possible) and
4853 static int pw_multi_aff_from_map(__isl_take isl_map
*map
, void *user
)
4855 isl_union_pw_multi_aff
**upma
= user
;
4856 isl_pw_multi_aff
*pma
;
4858 pma
= isl_pw_multi_aff_from_map(map
);
4859 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4861 return *upma
? 0 : -1;
4864 /* Try and create an isl_union_pw_multi_aff that is equivalent
4865 * to the given isl_union_map.
4866 * The isl_union_map is required to be single-valued in each space.
4867 * Otherwise, an error is produced.
4869 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_map(
4870 __isl_take isl_union_map
*umap
)
4873 isl_union_pw_multi_aff
*upma
;
4875 space
= isl_union_map_get_space(umap
);
4876 upma
= isl_union_pw_multi_aff_empty(space
);
4877 if (isl_union_map_foreach_map(umap
, &pw_multi_aff_from_map
, &upma
) < 0)
4878 upma
= isl_union_pw_multi_aff_free(upma
);
4879 isl_union_map_free(umap
);
4884 /* Try and create an isl_union_pw_multi_aff that is equivalent
4885 * to the given isl_union_set.
4886 * The isl_union_set is required to be a singleton in each space.
4887 * Otherwise, an error is produced.
4889 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_set(
4890 __isl_take isl_union_set
*uset
)
4892 return isl_union_pw_multi_aff_from_union_map(uset
);
4895 /* Return the piecewise affine expression "set ? 1 : 0".
4897 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
4900 isl_space
*space
= isl_set_get_space(set
);
4901 isl_local_space
*ls
= isl_local_space_from_space(space
);
4902 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
4903 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
4905 one
= isl_aff_add_constant_si(one
, 1);
4906 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
4907 set
= isl_set_complement(set
);
4908 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
4913 /* Plug in "subs" for dimension "type", "pos" of "aff".
4915 * Let i be the dimension to replace and let "subs" be of the form
4919 * and "aff" of the form
4925 * (a f + d g')/(m d)
4927 * where g' is the result of plugging in "subs" in each of the integer
4930 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
4931 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
4936 aff
= isl_aff_cow(aff
);
4938 return isl_aff_free(aff
);
4940 ctx
= isl_aff_get_ctx(aff
);
4941 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
4942 isl_die(ctx
, isl_error_invalid
,
4943 "spaces don't match", return isl_aff_free(aff
));
4944 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
4945 isl_die(ctx
, isl_error_unsupported
,
4946 "cannot handle divs yet", return isl_aff_free(aff
));
4948 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
4950 return isl_aff_free(aff
);
4952 aff
->v
= isl_vec_cow(aff
->v
);
4954 return isl_aff_free(aff
);
4956 pos
+= isl_local_space_offset(aff
->ls
, type
);
4959 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
4960 aff
->v
->size
, subs
->v
->size
, v
);
4966 /* Plug in "subs" for dimension "type", "pos" in each of the affine
4967 * expressions in "maff".
4969 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
4970 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
4971 __isl_keep isl_aff
*subs
)
4975 maff
= isl_multi_aff_cow(maff
);
4977 return isl_multi_aff_free(maff
);
4979 if (type
== isl_dim_in
)
4982 for (i
= 0; i
< maff
->n
; ++i
) {
4983 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
4985 return isl_multi_aff_free(maff
);
4991 /* Plug in "subs" for dimension "type", "pos" of "pma".
4993 * pma is of the form
4997 * while subs is of the form
4999 * v' = B_j(v) -> S_j
5001 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
5002 * has a contribution in the result, in particular
5004 * C_ij(S_j) -> M_i(S_j)
5006 * Note that plugging in S_j in C_ij may also result in an empty set
5007 * and this contribution should simply be discarded.
5009 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
5010 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
5011 __isl_keep isl_pw_aff
*subs
)
5014 isl_pw_multi_aff
*res
;
5017 return isl_pw_multi_aff_free(pma
);
5019 n
= pma
->n
* subs
->n
;
5020 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
5022 for (i
= 0; i
< pma
->n
; ++i
) {
5023 for (j
= 0; j
< subs
->n
; ++j
) {
5025 isl_multi_aff
*res_ij
;
5028 common
= isl_set_intersect(
5029 isl_set_copy(pma
->p
[i
].set
),
5030 isl_set_copy(subs
->p
[j
].set
));
5031 common
= isl_set_substitute(common
,
5032 type
, pos
, subs
->p
[j
].aff
);
5033 empty
= isl_set_plain_is_empty(common
);
5034 if (empty
< 0 || empty
) {
5035 isl_set_free(common
);
5041 res_ij
= isl_multi_aff_substitute(
5042 isl_multi_aff_copy(pma
->p
[i
].maff
),
5043 type
, pos
, subs
->p
[j
].aff
);
5045 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5049 isl_pw_multi_aff_free(pma
);
5052 isl_pw_multi_aff_free(pma
);
5053 isl_pw_multi_aff_free(res
);
5057 /* Compute the preimage of a range of dimensions in the affine expression "src"
5058 * under "ma" and put the result in "dst". The number of dimensions in "src"
5059 * that precede the range is given by "n_before". The number of dimensions
5060 * in the range is given by the number of output dimensions of "ma".
5061 * The number of dimensions that follow the range is given by "n_after".
5062 * If "has_denom" is set (to one),
5063 * then "src" and "dst" have an extra initial denominator.
5064 * "n_div_ma" is the number of existentials in "ma"
5065 * "n_div_bset" is the number of existentials in "src"
5066 * The resulting "dst" (which is assumed to have been allocated by
5067 * the caller) contains coefficients for both sets of existentials,
5068 * first those in "ma" and then those in "src".
5069 * f, c1, c2 and g are temporary objects that have been initialized
5072 * Let src represent the expression
5074 * (a(p) + f_u u + b v + f_w w + c(divs))/d
5076 * and let ma represent the expressions
5078 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
5080 * We start out with the following expression for dst:
5082 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d
5084 * with the multiplication factor f initially equal to 1
5085 * and f \sum_i b_i v_i kept separately.
5086 * For each x_i that we substitute, we multiply the numerator
5087 * (and denominator) of dst by c_1 = m_i and add the numerator
5088 * of the x_i expression multiplied by c_2 = f b_i,
5089 * after removing the common factors of c_1 and c_2.
5090 * The multiplication factor f also needs to be multiplied by c_1
5091 * for the next x_j, j > i.
5093 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
5094 __isl_keep isl_multi_aff
*ma
, int n_before
, int n_after
,
5095 int n_div_ma
, int n_div_bmap
,
5096 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
5099 int n_param
, n_in
, n_out
;
5102 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
5103 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
5104 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
5106 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
+ n_before
);
5107 o_dst
= o_src
= has_denom
+ 1 + n_param
+ n_before
;
5108 isl_seq_clr(dst
+ o_dst
, n_in
);
5111 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_after
);
5114 isl_seq_clr(dst
+ o_dst
, n_div_ma
);
5116 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_div_bmap
);
5118 isl_int_set_si(f
, 1);
5120 for (i
= 0; i
< n_out
; ++i
) {
5121 int offset
= has_denom
+ 1 + n_param
+ n_before
+ i
;
5123 if (isl_int_is_zero(src
[offset
]))
5125 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
5126 isl_int_mul(c2
, f
, src
[offset
]);
5127 isl_int_gcd(g
, c1
, c2
);
5128 isl_int_divexact(c1
, c1
, g
);
5129 isl_int_divexact(c2
, c2
, g
);
5131 isl_int_mul(f
, f
, c1
);
5134 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5135 c2
, ma
->p
[i
]->v
->el
+ o_src
, 1 + n_param
);
5136 o_dst
+= 1 + n_param
;
5137 o_src
+= 1 + n_param
;
5138 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_before
);
5140 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5141 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_in
);
5144 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_after
);
5146 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
5147 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_div_ma
);
5150 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_div_bmap
);
5152 isl_int_mul(dst
[0], dst
[0], c1
);
5156 /* Compute the pullback of "aff" by the function represented by "ma".
5157 * In other words, plug in "ma" in "aff". The result is an affine expression
5158 * defined over the domain space of "ma".
5160 * If "aff" is represented by
5162 * (a(p) + b x + c(divs))/d
5164 * and ma is represented by
5166 * x = D(p) + F(y) + G(divs')
5168 * then the result is
5170 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
5172 * The divs in the local space of the input are similarly adjusted
5173 * through a call to isl_local_space_preimage_multi_aff.
5175 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
5176 __isl_take isl_multi_aff
*ma
)
5178 isl_aff
*res
= NULL
;
5179 isl_local_space
*ls
;
5180 int n_div_aff
, n_div_ma
;
5181 isl_int f
, c1
, c2
, g
;
5183 ma
= isl_multi_aff_align_divs(ma
);
5187 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
5188 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
5190 ls
= isl_aff_get_domain_local_space(aff
);
5191 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
5192 res
= isl_aff_alloc(ls
);
5201 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, 0, 0, n_div_ma
, n_div_aff
,
5210 isl_multi_aff_free(ma
);
5211 res
= isl_aff_normalize(res
);
5215 isl_multi_aff_free(ma
);
5220 /* Compute the pullback of "aff1" by the function represented by "aff2".
5221 * In other words, plug in "aff2" in "aff1". The result is an affine expression
5222 * defined over the domain space of "aff1".
5224 * The domain of "aff1" should match the range of "aff2", which means
5225 * that it should be single-dimensional.
5227 __isl_give isl_aff
*isl_aff_pullback_aff(__isl_take isl_aff
*aff1
,
5228 __isl_take isl_aff
*aff2
)
5232 ma
= isl_multi_aff_from_aff(aff2
);
5233 return isl_aff_pullback_multi_aff(aff1
, ma
);
5236 /* Compute the pullback of "ma1" by the function represented by "ma2".
5237 * In other words, plug in "ma2" in "ma1".
5239 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
5241 static __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff_aligned(
5242 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5245 isl_space
*space
= NULL
;
5247 ma2
= isl_multi_aff_align_divs(ma2
);
5248 ma1
= isl_multi_aff_cow(ma1
);
5252 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
5253 isl_multi_aff_get_space(ma1
));
5255 for (i
= 0; i
< ma1
->n
; ++i
) {
5256 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
5257 isl_multi_aff_copy(ma2
));
5262 ma1
= isl_multi_aff_reset_space(ma1
, space
);
5263 isl_multi_aff_free(ma2
);
5266 isl_space_free(space
);
5267 isl_multi_aff_free(ma2
);
5268 isl_multi_aff_free(ma1
);
5272 /* Compute the pullback of "ma1" by the function represented by "ma2".
5273 * In other words, plug in "ma2" in "ma1".
5275 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
5276 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
5278 return isl_multi_aff_align_params_multi_multi_and(ma1
, ma2
,
5279 &isl_multi_aff_pullback_multi_aff_aligned
);
5282 /* Extend the local space of "dst" to include the divs
5283 * in the local space of "src".
5285 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
5286 __isl_keep isl_aff
*src
)
5294 return isl_aff_free(dst
);
5296 ctx
= isl_aff_get_ctx(src
);
5297 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
5298 isl_die(ctx
, isl_error_invalid
,
5299 "spaces don't match", goto error
);
5301 if (src
->ls
->div
->n_row
== 0)
5304 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
5305 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
5306 if (!exp1
|| (dst
->ls
->div
->n_row
&& !exp2
))
5309 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
5310 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
5318 return isl_aff_free(dst
);
5321 /* Adjust the local spaces of the affine expressions in "maff"
5322 * such that they all have the save divs.
5324 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
5325 __isl_take isl_multi_aff
*maff
)
5333 maff
= isl_multi_aff_cow(maff
);
5337 for (i
= 1; i
< maff
->n
; ++i
)
5338 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
5339 for (i
= 1; i
< maff
->n
; ++i
) {
5340 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
5342 return isl_multi_aff_free(maff
);
5348 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
5350 aff
= isl_aff_cow(aff
);
5354 aff
->ls
= isl_local_space_lift(aff
->ls
);
5356 return isl_aff_free(aff
);
5361 /* Lift "maff" to a space with extra dimensions such that the result
5362 * has no more existentially quantified variables.
5363 * If "ls" is not NULL, then *ls is assigned the local space that lies
5364 * at the basis of the lifting applied to "maff".
5366 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
5367 __isl_give isl_local_space
**ls
)
5381 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
5382 *ls
= isl_local_space_from_space(space
);
5384 return isl_multi_aff_free(maff
);
5389 maff
= isl_multi_aff_cow(maff
);
5390 maff
= isl_multi_aff_align_divs(maff
);
5394 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
5395 space
= isl_multi_aff_get_space(maff
);
5396 space
= isl_space_lift(isl_space_domain(space
), n_div
);
5397 space
= isl_space_extend_domain_with_range(space
,
5398 isl_multi_aff_get_space(maff
));
5400 return isl_multi_aff_free(maff
);
5401 isl_space_free(maff
->space
);
5402 maff
->space
= space
;
5405 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
5407 return isl_multi_aff_free(maff
);
5410 for (i
= 0; i
< maff
->n
; ++i
) {
5411 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
5419 isl_local_space_free(*ls
);
5420 return isl_multi_aff_free(maff
);
5424 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
5426 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
5427 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
5437 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
5438 if (pos
< 0 || pos
>= n_out
)
5439 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5440 "index out of bounds", return NULL
);
5442 space
= isl_pw_multi_aff_get_space(pma
);
5443 space
= isl_space_drop_dims(space
, isl_dim_out
,
5444 pos
+ 1, n_out
- pos
- 1);
5445 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
5447 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
5448 for (i
= 0; i
< pma
->n
; ++i
) {
5450 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
5451 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
5457 /* Return an isl_pw_multi_aff with the given "set" as domain and
5458 * an unnamed zero-dimensional range.
5460 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
5461 __isl_take isl_set
*set
)
5466 space
= isl_set_get_space(set
);
5467 space
= isl_space_from_domain(space
);
5468 ma
= isl_multi_aff_zero(space
);
5469 return isl_pw_multi_aff_alloc(set
, ma
);
5472 /* Add an isl_pw_multi_aff with the given "set" as domain and
5473 * an unnamed zero-dimensional range to *user.
5475 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
5477 isl_union_pw_multi_aff
**upma
= user
;
5478 isl_pw_multi_aff
*pma
;
5480 pma
= isl_pw_multi_aff_from_domain(set
);
5481 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
5486 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
5487 * an unnamed zero-dimensional range.
5489 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
5490 __isl_take isl_union_set
*uset
)
5493 isl_union_pw_multi_aff
*upma
;
5498 space
= isl_union_set_get_space(uset
);
5499 upma
= isl_union_pw_multi_aff_empty(space
);
5501 if (isl_union_set_foreach_set(uset
,
5502 &add_pw_multi_aff_from_domain
, &upma
) < 0)
5505 isl_union_set_free(uset
);
5508 isl_union_set_free(uset
);
5509 isl_union_pw_multi_aff_free(upma
);
5513 /* Convert "pma" to an isl_map and add it to *umap.
5515 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
5517 isl_union_map
**umap
= user
;
5520 map
= isl_map_from_pw_multi_aff(pma
);
5521 *umap
= isl_union_map_add_map(*umap
, map
);
5526 /* Construct a union map mapping the domain of the union
5527 * piecewise multi-affine expression to its range, with each dimension
5528 * in the range equated to the corresponding affine expression on its cell.
5530 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
5531 __isl_take isl_union_pw_multi_aff
*upma
)
5534 isl_union_map
*umap
;
5539 space
= isl_union_pw_multi_aff_get_space(upma
);
5540 umap
= isl_union_map_empty(space
);
5542 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
5543 &map_from_pw_multi_aff
, &umap
) < 0)
5546 isl_union_pw_multi_aff_free(upma
);
5549 isl_union_pw_multi_aff_free(upma
);
5550 isl_union_map_free(umap
);
5554 /* Local data for bin_entry and the callback "fn".
5556 struct isl_union_pw_multi_aff_bin_data
{
5557 isl_union_pw_multi_aff
*upma2
;
5558 isl_union_pw_multi_aff
*res
;
5559 isl_pw_multi_aff
*pma
;
5560 int (*fn
)(void **entry
, void *user
);
5563 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
5564 * and call data->fn for each isl_pw_multi_aff in data->upma2.
5566 static int bin_entry(void **entry
, void *user
)
5568 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5569 isl_pw_multi_aff
*pma
= *entry
;
5572 if (isl_hash_table_foreach(data
->upma2
->dim
->ctx
, &data
->upma2
->table
,
5573 data
->fn
, data
) < 0)
5579 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
5580 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
5581 * passed as user field) and the isl_pw_multi_aff from upma2 is available
5582 * as *entry. The callback should adjust data->res if desired.
5584 static __isl_give isl_union_pw_multi_aff
*bin_op(
5585 __isl_take isl_union_pw_multi_aff
*upma1
,
5586 __isl_take isl_union_pw_multi_aff
*upma2
,
5587 int (*fn
)(void **entry
, void *user
))
5590 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
5592 space
= isl_union_pw_multi_aff_get_space(upma2
);
5593 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
5594 space
= isl_union_pw_multi_aff_get_space(upma1
);
5595 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
5597 if (!upma1
|| !upma2
)
5601 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->dim
),
5603 if (isl_hash_table_foreach(upma1
->dim
->ctx
, &upma1
->table
,
5604 &bin_entry
, &data
) < 0)
5607 isl_union_pw_multi_aff_free(upma1
);
5608 isl_union_pw_multi_aff_free(upma2
);
5611 isl_union_pw_multi_aff_free(upma1
);
5612 isl_union_pw_multi_aff_free(upma2
);
5613 isl_union_pw_multi_aff_free(data
.res
);
5617 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5618 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5620 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
5621 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5625 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5626 isl_pw_multi_aff_get_space(pma2
));
5627 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5628 &isl_multi_aff_range_product
);
5631 /* Given two isl_pw_multi_affs A -> B and C -> D,
5632 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5634 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
5635 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5637 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5638 &pw_multi_aff_range_product
);
5641 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5642 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5644 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
5645 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5649 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5650 isl_pw_multi_aff_get_space(pma2
));
5651 space
= isl_space_flatten_range(space
);
5652 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5653 &isl_multi_aff_flat_range_product
);
5656 /* Given two isl_pw_multi_affs A -> B and C -> D,
5657 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5659 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
5660 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5662 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5663 &pw_multi_aff_flat_range_product
);
5666 /* If data->pma and *entry have the same domain space, then compute
5667 * their flat range product and the result to data->res.
5669 static int flat_range_product_entry(void **entry
, void *user
)
5671 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5672 isl_pw_multi_aff
*pma2
= *entry
;
5674 if (!isl_space_tuple_match(data
->pma
->dim
, isl_dim_in
,
5675 pma2
->dim
, isl_dim_in
))
5678 pma2
= isl_pw_multi_aff_flat_range_product(
5679 isl_pw_multi_aff_copy(data
->pma
),
5680 isl_pw_multi_aff_copy(pma2
));
5682 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
5687 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
5688 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
5690 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
5691 __isl_take isl_union_pw_multi_aff
*upma1
,
5692 __isl_take isl_union_pw_multi_aff
*upma2
)
5694 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
5697 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5698 * The parameters are assumed to have been aligned.
5700 * The implementation essentially performs an isl_pw_*_on_shared_domain,
5701 * except that it works on two different isl_pw_* types.
5703 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
5704 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5705 __isl_take isl_pw_aff
*pa
)
5708 isl_pw_multi_aff
*res
= NULL
;
5713 if (!isl_space_tuple_match(pma
->dim
, isl_dim_in
, pa
->dim
, isl_dim_in
))
5714 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5715 "domains don't match", goto error
);
5716 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
5717 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5718 "index out of bounds", goto error
);
5721 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
5723 for (i
= 0; i
< pma
->n
; ++i
) {
5724 for (j
= 0; j
< pa
->n
; ++j
) {
5726 isl_multi_aff
*res_ij
;
5729 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
5730 isl_set_copy(pa
->p
[j
].set
));
5731 empty
= isl_set_plain_is_empty(common
);
5732 if (empty
< 0 || empty
) {
5733 isl_set_free(common
);
5739 res_ij
= isl_multi_aff_set_aff(
5740 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
5741 isl_aff_copy(pa
->p
[j
].aff
));
5742 res_ij
= isl_multi_aff_gist(res_ij
,
5743 isl_set_copy(common
));
5745 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5749 isl_pw_multi_aff_free(pma
);
5750 isl_pw_aff_free(pa
);
5753 isl_pw_multi_aff_free(pma
);
5754 isl_pw_aff_free(pa
);
5755 return isl_pw_multi_aff_free(res
);
5758 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5760 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
5761 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5762 __isl_take isl_pw_aff
*pa
)
5766 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
5767 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5768 if (!isl_space_has_named_params(pma
->dim
) ||
5769 !isl_space_has_named_params(pa
->dim
))
5770 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5771 "unaligned unnamed parameters", goto error
);
5772 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
5773 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
5774 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5776 isl_pw_multi_aff_free(pma
);
5777 isl_pw_aff_free(pa
);
5781 /* Do the parameters of "pa" match those of "space"?
5783 int isl_pw_aff_matching_params(__isl_keep isl_pw_aff
*pa
,
5784 __isl_keep isl_space
*space
)
5786 isl_space
*pa_space
;
5792 pa_space
= isl_pw_aff_get_space(pa
);
5794 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5796 isl_space_free(pa_space
);
5800 /* Check that the domain space of "pa" matches "space".
5802 * Return 0 on success and -1 on error.
5804 int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff
*pa
,
5805 __isl_keep isl_space
*space
)
5807 isl_space
*pa_space
;
5813 pa_space
= isl_pw_aff_get_space(pa
);
5815 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5819 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5820 "parameters don't match", goto error
);
5821 match
= isl_space_tuple_match(space
, isl_dim_in
, pa_space
, isl_dim_in
);
5825 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5826 "domains don't match", goto error
);
5827 isl_space_free(pa_space
);
5830 isl_space_free(pa_space
);
5837 #include <isl_multi_templ.c>
5839 /* Scale the elements of "pma" by the corresponding elements of "mv".
5841 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_scale_multi_val(
5842 __isl_take isl_pw_multi_aff
*pma
, __isl_take isl_multi_val
*mv
)
5846 pma
= isl_pw_multi_aff_cow(pma
);
5849 if (!isl_space_tuple_match(pma
->dim
, isl_dim_out
,
5850 mv
->space
, isl_dim_set
))
5851 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5852 "spaces don't match", goto error
);
5853 if (!isl_space_match(pma
->dim
, isl_dim_param
,
5854 mv
->space
, isl_dim_param
)) {
5855 pma
= isl_pw_multi_aff_align_params(pma
,
5856 isl_multi_val_get_space(mv
));
5857 mv
= isl_multi_val_align_params(mv
,
5858 isl_pw_multi_aff_get_space(pma
));
5863 for (i
= 0; i
< pma
->n
; ++i
) {
5864 pma
->p
[i
].maff
= isl_multi_aff_scale_multi_val(pma
->p
[i
].maff
,
5865 isl_multi_val_copy(mv
));
5866 if (!pma
->p
[i
].maff
)
5870 isl_multi_val_free(mv
);
5873 isl_multi_val_free(mv
);
5874 isl_pw_multi_aff_free(pma
);
5878 /* Internal data structure for isl_union_pw_multi_aff_scale_multi_val.
5879 * mv contains the mv argument.
5880 * res collects the results.
5882 struct isl_union_pw_multi_aff_scale_multi_val_data
{
5884 isl_union_pw_multi_aff
*res
;
5887 /* This function is called for each entry of an isl_union_pw_multi_aff.
5888 * If the space of the entry matches that of data->mv,
5889 * then apply isl_pw_multi_aff_scale_multi_val and add the result
5892 static int union_pw_multi_aff_scale_multi_val_entry(void **entry
, void *user
)
5894 struct isl_union_pw_multi_aff_scale_multi_val_data
*data
= user
;
5895 isl_pw_multi_aff
*pma
= *entry
;
5899 if (!isl_space_tuple_match(pma
->dim
, isl_dim_out
,
5900 data
->mv
->space
, isl_dim_set
))
5903 pma
= isl_pw_multi_aff_copy(pma
);
5904 pma
= isl_pw_multi_aff_scale_multi_val(pma
,
5905 isl_multi_val_copy(data
->mv
));
5906 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
5913 /* Scale the elements of "upma" by the corresponding elements of "mv",
5914 * for those entries that match the space of "mv".
5916 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_scale_multi_val(
5917 __isl_take isl_union_pw_multi_aff
*upma
, __isl_take isl_multi_val
*mv
)
5919 struct isl_union_pw_multi_aff_scale_multi_val_data data
;
5921 upma
= isl_union_pw_multi_aff_align_params(upma
,
5922 isl_multi_val_get_space(mv
));
5923 mv
= isl_multi_val_align_params(mv
,
5924 isl_union_pw_multi_aff_get_space(upma
));
5929 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma
->dim
),
5931 if (isl_hash_table_foreach(upma
->dim
->ctx
, &upma
->table
,
5932 &union_pw_multi_aff_scale_multi_val_entry
, &data
) < 0)
5935 isl_multi_val_free(mv
);
5936 isl_union_pw_multi_aff_free(upma
);
5939 isl_multi_val_free(mv
);
5940 isl_union_pw_multi_aff_free(upma
);
5944 /* Construct and return a piecewise multi affine expression
5945 * in the given space with value zero in each of the output dimensions and
5946 * a universe domain.
5948 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_zero(__isl_take isl_space
*space
)
5950 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_zero(space
));
5953 /* Construct and return a piecewise multi affine expression
5954 * that is equal to the given piecewise affine expression.
5956 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_pw_aff(
5957 __isl_take isl_pw_aff
*pa
)
5961 isl_pw_multi_aff
*pma
;
5966 space
= isl_pw_aff_get_space(pa
);
5967 pma
= isl_pw_multi_aff_alloc_size(space
, pa
->n
);
5969 for (i
= 0; i
< pa
->n
; ++i
) {
5973 set
= isl_set_copy(pa
->p
[i
].set
);
5974 ma
= isl_multi_aff_from_aff(isl_aff_copy(pa
->p
[i
].aff
));
5975 pma
= isl_pw_multi_aff_add_piece(pma
, set
, ma
);
5978 isl_pw_aff_free(pa
);
5982 /* Construct a set or map mapping the shared (parameter) domain
5983 * of the piecewise affine expressions to the range of "mpa"
5984 * with each dimension in the range equated to the
5985 * corresponding piecewise affine expression.
5987 static __isl_give isl_map
*map_from_multi_pw_aff(
5988 __isl_take isl_multi_pw_aff
*mpa
)
5997 if (isl_space_dim(mpa
->space
, isl_dim_out
) != mpa
->n
)
5998 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
5999 "invalid space", goto error
);
6001 space
= isl_multi_pw_aff_get_domain_space(mpa
);
6002 map
= isl_map_universe(isl_space_from_domain(space
));
6004 for (i
= 0; i
< mpa
->n
; ++i
) {
6008 pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6009 map_i
= map_from_pw_aff(pa
);
6011 map
= isl_map_flat_range_product(map
, map_i
);
6014 map
= isl_map_reset_space(map
, isl_multi_pw_aff_get_space(mpa
));
6016 isl_multi_pw_aff_free(mpa
);
6019 isl_multi_pw_aff_free(mpa
);
6023 /* Construct a map mapping the shared domain
6024 * of the piecewise affine expressions to the range of "mpa"
6025 * with each dimension in the range equated to the
6026 * corresponding piecewise affine expression.
6028 __isl_give isl_map
*isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6032 if (isl_space_is_set(mpa
->space
))
6033 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6034 "space of input is not a map", goto error
);
6036 return map_from_multi_pw_aff(mpa
);
6038 isl_multi_pw_aff_free(mpa
);
6042 /* Construct a set mapping the shared parameter domain
6043 * of the piecewise affine expressions to the space of "mpa"
6044 * with each dimension in the range equated to the
6045 * corresponding piecewise affine expression.
6047 __isl_give isl_set
*isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff
*mpa
)
6051 if (!isl_space_is_set(mpa
->space
))
6052 isl_die(isl_multi_pw_aff_get_ctx(mpa
), isl_error_internal
,
6053 "space of input is not a set", goto error
);
6055 return map_from_multi_pw_aff(mpa
);
6057 isl_multi_pw_aff_free(mpa
);
6061 /* Construct and return a piecewise multi affine expression
6062 * that is equal to the given multi piecewise affine expression
6063 * on the shared domain of the piecewise affine expressions.
6065 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_pw_aff(
6066 __isl_take isl_multi_pw_aff
*mpa
)
6071 isl_pw_multi_aff
*pma
;
6076 space
= isl_multi_pw_aff_get_space(mpa
);
6079 isl_multi_pw_aff_free(mpa
);
6080 return isl_pw_multi_aff_zero(space
);
6083 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
6084 pma
= isl_pw_multi_aff_from_pw_aff(pa
);
6086 for (i
= 1; i
< mpa
->n
; ++i
) {
6087 isl_pw_multi_aff
*pma_i
;
6089 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6090 pma_i
= isl_pw_multi_aff_from_pw_aff(pa
);
6091 pma
= isl_pw_multi_aff_range_product(pma
, pma_i
);
6094 pma
= isl_pw_multi_aff_reset_space(pma
, space
);
6096 isl_multi_pw_aff_free(mpa
);
6100 /* Construct and return a multi piecewise affine expression
6101 * that is equal to the given multi affine expression.
6103 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_multi_aff(
6104 __isl_take isl_multi_aff
*ma
)
6107 isl_multi_pw_aff
*mpa
;
6112 n
= isl_multi_aff_dim(ma
, isl_dim_out
);
6113 mpa
= isl_multi_pw_aff_alloc(isl_multi_aff_get_space(ma
));
6115 for (i
= 0; i
< n
; ++i
) {
6118 pa
= isl_pw_aff_from_aff(isl_multi_aff_get_aff(ma
, i
));
6119 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6122 isl_multi_aff_free(ma
);
6126 /* Construct and return a multi piecewise affine expression
6127 * that is equal to the given piecewise multi affine expression.
6129 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_from_pw_multi_aff(
6130 __isl_take isl_pw_multi_aff
*pma
)
6134 isl_multi_pw_aff
*mpa
;
6139 n
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
6140 space
= isl_pw_multi_aff_get_space(pma
);
6141 mpa
= isl_multi_pw_aff_alloc(space
);
6143 for (i
= 0; i
< n
; ++i
) {
6146 pa
= isl_pw_multi_aff_get_pw_aff(pma
, i
);
6147 mpa
= isl_multi_pw_aff_set_pw_aff(mpa
, i
, pa
);
6150 isl_pw_multi_aff_free(pma
);
6154 /* Do "pa1" and "pa2" represent the same function?
6156 * We first check if they are obviously equal.
6157 * If not, we convert them to maps and check if those are equal.
6159 int isl_pw_aff_is_equal(__isl_keep isl_pw_aff
*pa1
, __isl_keep isl_pw_aff
*pa2
)
6162 isl_map
*map1
, *map2
;
6167 equal
= isl_pw_aff_plain_is_equal(pa1
, pa2
);
6168 if (equal
< 0 || equal
)
6171 map1
= map_from_pw_aff(isl_pw_aff_copy(pa1
));
6172 map2
= map_from_pw_aff(isl_pw_aff_copy(pa2
));
6173 equal
= isl_map_is_equal(map1
, map2
);
6180 /* Do "mpa1" and "mpa2" represent the same function?
6182 * Note that we cannot convert the entire isl_multi_pw_aff
6183 * to a map because the domains of the piecewise affine expressions
6184 * may not be the same.
6186 int isl_multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff
*mpa1
,
6187 __isl_keep isl_multi_pw_aff
*mpa2
)
6195 if (!isl_space_match(mpa1
->space
, isl_dim_param
,
6196 mpa2
->space
, isl_dim_param
)) {
6197 if (!isl_space_has_named_params(mpa1
->space
))
6199 if (!isl_space_has_named_params(mpa2
->space
))
6201 mpa1
= isl_multi_pw_aff_copy(mpa1
);
6202 mpa2
= isl_multi_pw_aff_copy(mpa2
);
6203 mpa1
= isl_multi_pw_aff_align_params(mpa1
,
6204 isl_multi_pw_aff_get_space(mpa2
));
6205 mpa2
= isl_multi_pw_aff_align_params(mpa2
,
6206 isl_multi_pw_aff_get_space(mpa1
));
6207 equal
= isl_multi_pw_aff_is_equal(mpa1
, mpa2
);
6208 isl_multi_pw_aff_free(mpa1
);
6209 isl_multi_pw_aff_free(mpa2
);
6213 equal
= isl_space_is_equal(mpa1
->space
, mpa2
->space
);
6214 if (equal
< 0 || !equal
)
6217 for (i
= 0; i
< mpa1
->n
; ++i
) {
6218 equal
= isl_pw_aff_is_equal(mpa1
->p
[i
], mpa2
->p
[i
]);
6219 if (equal
< 0 || !equal
)
6226 /* Coalesce the elements of "mpa".
6228 * Note that such coalescing does not change the meaning of "mpa"
6229 * so there is no need to cow. We do need to be careful not to
6230 * destroy any other copies of "mpa" in case of failure.
6232 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_coalesce(
6233 __isl_take isl_multi_pw_aff
*mpa
)
6240 for (i
= 0; i
< mpa
->n
; ++i
) {
6241 isl_pw_aff
*pa
= isl_pw_aff_copy(mpa
->p
[i
]);
6242 pa
= isl_pw_aff_coalesce(pa
);
6244 return isl_multi_pw_aff_free(mpa
);
6245 isl_pw_aff_free(mpa
->p
[i
]);
6252 /* Compute the pullback of "mpa" by the function represented by "ma".
6253 * In other words, plug in "ma" in "mpa".
6255 * The parameters of "mpa" and "ma" are assumed to have been aligned.
6257 static __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff_aligned(
6258 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6261 isl_space
*space
= NULL
;
6263 mpa
= isl_multi_pw_aff_cow(mpa
);
6267 space
= isl_space_join(isl_multi_aff_get_space(ma
),
6268 isl_multi_pw_aff_get_space(mpa
));
6272 for (i
= 0; i
< mpa
->n
; ++i
) {
6273 mpa
->p
[i
] = isl_pw_aff_pullback_multi_aff(mpa
->p
[i
],
6274 isl_multi_aff_copy(ma
));
6279 isl_multi_aff_free(ma
);
6280 isl_space_free(mpa
->space
);
6284 isl_space_free(space
);
6285 isl_multi_pw_aff_free(mpa
);
6286 isl_multi_aff_free(ma
);
6290 /* Compute the pullback of "mpa" by the function represented by "ma".
6291 * In other words, plug in "ma" in "mpa".
6293 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_aff(
6294 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_multi_aff
*ma
)
6298 if (isl_space_match(mpa
->space
, isl_dim_param
,
6299 ma
->space
, isl_dim_param
))
6300 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6301 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_multi_aff_get_space(ma
));
6302 ma
= isl_multi_aff_align_params(ma
, isl_multi_pw_aff_get_space(mpa
));
6303 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa
, ma
);
6305 isl_multi_pw_aff_free(mpa
);
6306 isl_multi_aff_free(ma
);
6310 /* Compute the pullback of "mpa" by the function represented by "pma".
6311 * In other words, plug in "pma" in "mpa".
6313 * The parameters of "mpa" and "mpa" are assumed to have been aligned.
6315 static __isl_give isl_multi_pw_aff
*
6316 isl_multi_pw_aff_pullback_pw_multi_aff_aligned(
6317 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6320 isl_space
*space
= NULL
;
6322 mpa
= isl_multi_pw_aff_cow(mpa
);
6326 space
= isl_space_join(isl_pw_multi_aff_get_space(pma
),
6327 isl_multi_pw_aff_get_space(mpa
));
6329 for (i
= 0; i
< mpa
->n
; ++i
) {
6330 mpa
->p
[i
] = isl_pw_aff_pullback_pw_multi_aff_aligned(mpa
->p
[i
],
6331 isl_pw_multi_aff_copy(pma
));
6336 isl_pw_multi_aff_free(pma
);
6337 isl_space_free(mpa
->space
);
6341 isl_space_free(space
);
6342 isl_multi_pw_aff_free(mpa
);
6343 isl_pw_multi_aff_free(pma
);
6347 /* Compute the pullback of "mpa" by the function represented by "pma".
6348 * In other words, plug in "pma" in "mpa".
6350 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_pw_multi_aff(
6351 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_multi_aff
*pma
)
6355 if (isl_space_match(mpa
->space
, isl_dim_param
, pma
->dim
, isl_dim_param
))
6356 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6357 mpa
= isl_multi_pw_aff_align_params(mpa
,
6358 isl_pw_multi_aff_get_space(pma
));
6359 pma
= isl_pw_multi_aff_align_params(pma
,
6360 isl_multi_pw_aff_get_space(mpa
));
6361 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa
, pma
);
6363 isl_multi_pw_aff_free(mpa
);
6364 isl_pw_multi_aff_free(pma
);
6368 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6369 * with the domain of "aff". The domain of the result is the same
6371 * "mpa" and "aff" are assumed to have been aligned.
6373 * We first extract the parametric constant from "aff", defined
6374 * over the correct domain.
6375 * Then we add the appropriate combinations of the members of "mpa".
6376 * Finally, we add the integer divisions through recursive calls.
6378 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff_aligned(
6379 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6381 int i
, n_param
, n_in
, n_div
;
6387 n_param
= isl_aff_dim(aff
, isl_dim_param
);
6388 n_in
= isl_aff_dim(aff
, isl_dim_in
);
6389 n_div
= isl_aff_dim(aff
, isl_dim_div
);
6391 space
= isl_space_domain(isl_multi_pw_aff_get_space(mpa
));
6392 tmp
= isl_aff_copy(aff
);
6393 tmp
= isl_aff_drop_dims(tmp
, isl_dim_div
, 0, n_div
);
6394 tmp
= isl_aff_drop_dims(tmp
, isl_dim_in
, 0, n_in
);
6395 tmp
= isl_aff_add_dims(tmp
, isl_dim_in
,
6396 isl_space_dim(space
, isl_dim_set
));
6397 tmp
= isl_aff_reset_domain_space(tmp
, space
);
6398 pa
= isl_pw_aff_from_aff(tmp
);
6400 for (i
= 0; i
< n_in
; ++i
) {
6403 if (!isl_aff_involves_dims(aff
, isl_dim_in
, i
, 1))
6405 v
= isl_aff_get_coefficient_val(aff
, isl_dim_in
, i
);
6406 pa_i
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
6407 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6408 pa
= isl_pw_aff_add(pa
, pa_i
);
6411 for (i
= 0; i
< n_div
; ++i
) {
6415 if (!isl_aff_involves_dims(aff
, isl_dim_div
, i
, 1))
6417 div
= isl_aff_get_div(aff
, i
);
6418 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6419 isl_multi_pw_aff_copy(mpa
), div
);
6420 pa_i
= isl_pw_aff_floor(pa_i
);
6421 v
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, i
);
6422 pa_i
= isl_pw_aff_scale_val(pa_i
, v
);
6423 pa
= isl_pw_aff_add(pa
, pa_i
);
6426 isl_multi_pw_aff_free(mpa
);
6432 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6433 * with the domain of "aff". The domain of the result is the same
6436 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_aff(
6437 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_aff
*aff
)
6441 if (isl_space_match(aff
->ls
->dim
, isl_dim_param
,
6442 mpa
->space
, isl_dim_param
))
6443 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6445 aff
= isl_aff_align_params(aff
, isl_multi_pw_aff_get_space(mpa
));
6446 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_aff_get_space(aff
));
6448 return isl_multi_pw_aff_apply_aff_aligned(mpa
, aff
);
6451 isl_multi_pw_aff_free(mpa
);
6455 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6456 * with the domain of "pa". The domain of the result is the same
6458 * "mpa" and "pa" are assumed to have been aligned.
6460 * We consider each piece in turn. Note that the domains of the
6461 * pieces are assumed to be disjoint and they remain disjoint
6462 * after taking the preimage (over the same function).
6464 static __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff_aligned(
6465 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6474 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa
),
6475 isl_pw_aff_get_space(pa
));
6476 res
= isl_pw_aff_empty(space
);
6478 for (i
= 0; i
< pa
->n
; ++i
) {
6482 pa_i
= isl_multi_pw_aff_apply_aff_aligned(
6483 isl_multi_pw_aff_copy(mpa
),
6484 isl_aff_copy(pa
->p
[i
].aff
));
6485 domain
= isl_set_copy(pa
->p
[i
].set
);
6486 domain
= isl_set_preimage_multi_pw_aff(domain
,
6487 isl_multi_pw_aff_copy(mpa
));
6488 pa_i
= isl_pw_aff_intersect_domain(pa_i
, domain
);
6489 res
= isl_pw_aff_add_disjoint(res
, pa_i
);
6492 isl_pw_aff_free(pa
);
6493 isl_multi_pw_aff_free(mpa
);
6496 isl_pw_aff_free(pa
);
6497 isl_multi_pw_aff_free(mpa
);
6501 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6502 * with the domain of "pa". The domain of the result is the same
6505 __isl_give isl_pw_aff
*isl_multi_pw_aff_apply_pw_aff(
6506 __isl_take isl_multi_pw_aff
*mpa
, __isl_take isl_pw_aff
*pa
)
6510 if (isl_space_match(pa
->dim
, isl_dim_param
, mpa
->space
, isl_dim_param
))
6511 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6513 pa
= isl_pw_aff_align_params(pa
, isl_multi_pw_aff_get_space(mpa
));
6514 mpa
= isl_multi_pw_aff_align_params(mpa
, isl_pw_aff_get_space(pa
));
6516 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6518 isl_pw_aff_free(pa
);
6519 isl_multi_pw_aff_free(mpa
);
6523 /* Compute the pullback of "pa" by the function represented by "mpa".
6524 * In other words, plug in "mpa" in "pa".
6525 * "pa" and "mpa" are assumed to have been aligned.
6527 * The pullback is computed by applying "pa" to "mpa".
6529 static __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff_aligned(
6530 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6532 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa
, pa
);
6535 /* Compute the pullback of "pa" by the function represented by "mpa".
6536 * In other words, plug in "mpa" in "pa".
6538 * The pullback is computed by applying "pa" to "mpa".
6540 __isl_give isl_pw_aff
*isl_pw_aff_pullback_multi_pw_aff(
6541 __isl_take isl_pw_aff
*pa
, __isl_take isl_multi_pw_aff
*mpa
)
6543 return isl_multi_pw_aff_apply_pw_aff(mpa
, pa
);
6546 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6547 * In other words, plug in "mpa2" in "mpa1".
6549 * The parameters of "mpa1" and "mpa2" are assumed to have been aligned.
6551 * We pullback each member of "mpa1" in turn.
6553 static __isl_give isl_multi_pw_aff
*
6554 isl_multi_pw_aff_pullback_multi_pw_aff_aligned(
6555 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6558 isl_space
*space
= NULL
;
6560 mpa1
= isl_multi_pw_aff_cow(mpa1
);
6564 space
= isl_space_join(isl_multi_pw_aff_get_space(mpa2
),
6565 isl_multi_pw_aff_get_space(mpa1
));
6567 for (i
= 0; i
< mpa1
->n
; ++i
) {
6568 mpa1
->p
[i
] = isl_pw_aff_pullback_multi_pw_aff_aligned(
6569 mpa1
->p
[i
], isl_multi_pw_aff_copy(mpa2
));
6574 mpa1
= isl_multi_pw_aff_reset_space(mpa1
, space
);
6576 isl_multi_pw_aff_free(mpa2
);
6579 isl_space_free(space
);
6580 isl_multi_pw_aff_free(mpa1
);
6581 isl_multi_pw_aff_free(mpa2
);
6585 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6586 * In other words, plug in "mpa2" in "mpa1".
6588 __isl_give isl_multi_pw_aff
*isl_multi_pw_aff_pullback_multi_pw_aff(
6589 __isl_take isl_multi_pw_aff
*mpa1
, __isl_take isl_multi_pw_aff
*mpa2
)
6591 return isl_multi_pw_aff_align_params_multi_multi_and(mpa1
, mpa2
,
6592 &isl_multi_pw_aff_pullback_multi_pw_aff_aligned
);
6595 /* Compare two isl_affs.
6597 * Return -1 if "aff1" is "smaller" than "aff2", 1 if "aff1" is "greater"
6598 * than "aff2" and 0 if they are equal.
6600 * The order is fairly arbitrary. We do consider expressions that only involve
6601 * earlier dimensions as "smaller".
6603 int isl_aff_plain_cmp(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
6616 cmp
= isl_local_space_cmp(aff1
->ls
, aff2
->ls
);
6620 last1
= isl_seq_last_non_zero(aff1
->v
->el
+ 1, aff1
->v
->size
- 1);
6621 last2
= isl_seq_last_non_zero(aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
6623 return last1
- last2
;
6625 return isl_seq_cmp(aff1
->v
->el
, aff2
->v
->el
, aff1
->v
->size
);
6628 /* Compare two isl_pw_affs.
6630 * Return -1 if "pa1" is "smaller" than "pa2", 1 if "pa1" is "greater"
6631 * than "pa2" and 0 if they are equal.
6633 * The order is fairly arbitrary. We do consider expressions that only involve
6634 * earlier dimensions as "smaller".
6636 int isl_pw_aff_plain_cmp(__isl_keep isl_pw_aff
*pa1
,
6637 __isl_keep isl_pw_aff
*pa2
)
6650 cmp
= isl_space_cmp(pa1
->dim
, pa2
->dim
);
6654 if (pa1
->n
!= pa2
->n
)
6655 return pa1
->n
- pa2
->n
;
6657 for (i
= 0; i
< pa1
->n
; ++i
) {
6658 cmp
= isl_set_plain_cmp(pa1
->p
[i
].set
, pa2
->p
[i
].set
);
6661 cmp
= isl_aff_plain_cmp(pa1
->p
[i
].aff
, pa2
->p
[i
].aff
);