2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2013 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 #include <isl_ctx_private.h>
16 #include <isl_map_private.h>
17 #include <isl_union_map_private.h>
18 #include <isl_aff_private.h>
19 #include <isl_space_private.h>
20 #include <isl_local_space_private.h>
21 #include <isl_vec_private.h>
22 #include <isl_mat_private.h>
23 #include <isl/constraint.h>
26 #include <isl_val_private.h>
27 #include <isl/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 that is equal to the specified dimension
114 __isl_give isl_aff
*isl_aff_var_on_domain(__isl_take isl_local_space
*ls
,
115 enum isl_dim_type type
, unsigned pos
)
123 space
= isl_local_space_get_space(ls
);
126 if (isl_space_is_map(space
))
127 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
128 "expecting (parameter) set space", goto error
);
129 if (pos
>= isl_local_space_dim(ls
, type
))
130 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
131 "position out of bounds", goto error
);
133 isl_space_free(space
);
134 aff
= isl_aff_alloc(ls
);
138 pos
+= isl_local_space_offset(aff
->ls
, type
);
140 isl_int_set_si(aff
->v
->el
[0], 1);
141 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
142 isl_int_set_si(aff
->v
->el
[1 + pos
], 1);
146 isl_local_space_free(ls
);
147 isl_space_free(space
);
151 /* Return a piecewise affine expression that is equal to
152 * the specified dimension in "ls".
154 __isl_give isl_pw_aff
*isl_pw_aff_var_on_domain(__isl_take isl_local_space
*ls
,
155 enum isl_dim_type type
, unsigned pos
)
157 return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, type
, pos
));
160 __isl_give isl_aff
*isl_aff_copy(__isl_keep isl_aff
*aff
)
169 __isl_give isl_aff
*isl_aff_dup(__isl_keep isl_aff
*aff
)
174 return isl_aff_alloc_vec(isl_local_space_copy(aff
->ls
),
175 isl_vec_copy(aff
->v
));
178 __isl_give isl_aff
*isl_aff_cow(__isl_take isl_aff
*aff
)
186 return isl_aff_dup(aff
);
189 void *isl_aff_free(__isl_take isl_aff
*aff
)
197 isl_local_space_free(aff
->ls
);
198 isl_vec_free(aff
->v
);
205 isl_ctx
*isl_aff_get_ctx(__isl_keep isl_aff
*aff
)
207 return aff
? isl_local_space_get_ctx(aff
->ls
) : NULL
;
210 /* Externally, an isl_aff has a map space, but internally, the
211 * ls field corresponds to the domain of that space.
213 int isl_aff_dim(__isl_keep isl_aff
*aff
, enum isl_dim_type type
)
217 if (type
== isl_dim_out
)
219 if (type
== isl_dim_in
)
221 return isl_local_space_dim(aff
->ls
, type
);
224 __isl_give isl_space
*isl_aff_get_domain_space(__isl_keep isl_aff
*aff
)
226 return aff
? isl_local_space_get_space(aff
->ls
) : NULL
;
229 __isl_give isl_space
*isl_aff_get_space(__isl_keep isl_aff
*aff
)
234 space
= isl_local_space_get_space(aff
->ls
);
235 space
= isl_space_from_domain(space
);
236 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
240 __isl_give isl_local_space
*isl_aff_get_domain_local_space(
241 __isl_keep isl_aff
*aff
)
243 return aff
? isl_local_space_copy(aff
->ls
) : NULL
;
246 __isl_give isl_local_space
*isl_aff_get_local_space(__isl_keep isl_aff
*aff
)
251 ls
= isl_local_space_copy(aff
->ls
);
252 ls
= isl_local_space_from_domain(ls
);
253 ls
= isl_local_space_add_dims(ls
, isl_dim_out
, 1);
257 /* Externally, an isl_aff has a map space, but internally, the
258 * ls field corresponds to the domain of that space.
260 const char *isl_aff_get_dim_name(__isl_keep isl_aff
*aff
,
261 enum isl_dim_type type
, unsigned pos
)
265 if (type
== isl_dim_out
)
267 if (type
== isl_dim_in
)
269 return isl_local_space_get_dim_name(aff
->ls
, type
, pos
);
272 __isl_give isl_aff
*isl_aff_reset_domain_space(__isl_take isl_aff
*aff
,
273 __isl_take isl_space
*dim
)
275 aff
= isl_aff_cow(aff
);
279 aff
->ls
= isl_local_space_reset_space(aff
->ls
, dim
);
281 return isl_aff_free(aff
);
290 /* Reset the space of "aff". This function is called from isl_pw_templ.c
291 * and doesn't know if the space of an element object is represented
292 * directly or through its domain. It therefore passes along both.
294 __isl_give isl_aff
*isl_aff_reset_space_and_domain(__isl_take isl_aff
*aff
,
295 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
297 isl_space_free(space
);
298 return isl_aff_reset_domain_space(aff
, domain
);
301 /* Reorder the coefficients of the affine expression based
302 * on the given reodering.
303 * The reordering r is assumed to have been extended with the local
306 static __isl_give isl_vec
*vec_reorder(__isl_take isl_vec
*vec
,
307 __isl_take isl_reordering
*r
, int n_div
)
315 res
= isl_vec_alloc(vec
->ctx
,
316 2 + isl_space_dim(r
->dim
, isl_dim_all
) + n_div
);
317 isl_seq_cpy(res
->el
, vec
->el
, 2);
318 isl_seq_clr(res
->el
+ 2, res
->size
- 2);
319 for (i
= 0; i
< r
->len
; ++i
)
320 isl_int_set(res
->el
[2 + r
->pos
[i
]], vec
->el
[2 + i
]);
322 isl_reordering_free(r
);
327 isl_reordering_free(r
);
331 /* Reorder the dimensions of the domain of "aff" according
332 * to the given reordering.
334 __isl_give isl_aff
*isl_aff_realign_domain(__isl_take isl_aff
*aff
,
335 __isl_take isl_reordering
*r
)
337 aff
= isl_aff_cow(aff
);
341 r
= isl_reordering_extend(r
, aff
->ls
->div
->n_row
);
342 aff
->v
= vec_reorder(aff
->v
, isl_reordering_copy(r
),
343 aff
->ls
->div
->n_row
);
344 aff
->ls
= isl_local_space_realign(aff
->ls
, r
);
346 if (!aff
->v
|| !aff
->ls
)
347 return isl_aff_free(aff
);
352 isl_reordering_free(r
);
356 __isl_give isl_aff
*isl_aff_align_params(__isl_take isl_aff
*aff
,
357 __isl_take isl_space
*model
)
362 if (!isl_space_match(aff
->ls
->dim
, isl_dim_param
,
363 model
, isl_dim_param
)) {
366 model
= isl_space_drop_dims(model
, isl_dim_in
,
367 0, isl_space_dim(model
, isl_dim_in
));
368 model
= isl_space_drop_dims(model
, isl_dim_out
,
369 0, isl_space_dim(model
, isl_dim_out
));
370 exp
= isl_parameter_alignment_reordering(aff
->ls
->dim
, model
);
371 exp
= isl_reordering_extend_space(exp
,
372 isl_aff_get_domain_space(aff
));
373 aff
= isl_aff_realign_domain(aff
, exp
);
376 isl_space_free(model
);
379 isl_space_free(model
);
384 int isl_aff_plain_is_zero(__isl_keep isl_aff
*aff
)
389 return isl_seq_first_non_zero(aff
->v
->el
+ 1, aff
->v
->size
- 1) < 0;
392 int isl_aff_plain_is_equal(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
399 equal
= isl_local_space_is_equal(aff1
->ls
, aff2
->ls
);
400 if (equal
< 0 || !equal
)
403 return isl_vec_is_equal(aff1
->v
, aff2
->v
);
406 int isl_aff_get_denominator(__isl_keep isl_aff
*aff
, isl_int
*v
)
410 isl_int_set(*v
, aff
->v
->el
[0]);
414 /* Return the common denominator of "aff".
416 __isl_give isl_val
*isl_aff_get_denominator_val(__isl_keep isl_aff
*aff
)
423 ctx
= isl_aff_get_ctx(aff
);
424 return isl_val_int_from_isl_int(ctx
, aff
->v
->el
[0]);
427 int isl_aff_get_constant(__isl_keep isl_aff
*aff
, isl_int
*v
)
431 isl_int_set(*v
, aff
->v
->el
[1]);
435 /* Return the constant term of "aff".
437 __isl_give isl_val
*isl_aff_get_constant_val(__isl_keep isl_aff
*aff
)
445 ctx
= isl_aff_get_ctx(aff
);
446 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1], aff
->v
->el
[0]);
447 return isl_val_normalize(v
);
450 int isl_aff_get_coefficient(__isl_keep isl_aff
*aff
,
451 enum isl_dim_type type
, int pos
, isl_int
*v
)
456 if (type
== isl_dim_out
)
457 isl_die(aff
->v
->ctx
, isl_error_invalid
,
458 "output/set dimension does not have a coefficient",
460 if (type
== isl_dim_in
)
463 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
464 isl_die(aff
->v
->ctx
, isl_error_invalid
,
465 "position out of bounds", return -1);
467 pos
+= isl_local_space_offset(aff
->ls
, type
);
468 isl_int_set(*v
, aff
->v
->el
[1 + pos
]);
473 /* Return the coefficient of the variable of type "type" at position "pos"
476 __isl_give isl_val
*isl_aff_get_coefficient_val(__isl_keep isl_aff
*aff
,
477 enum isl_dim_type type
, int pos
)
485 ctx
= isl_aff_get_ctx(aff
);
486 if (type
== isl_dim_out
)
487 isl_die(ctx
, isl_error_invalid
,
488 "output/set dimension does not have a coefficient",
490 if (type
== isl_dim_in
)
493 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
494 isl_die(ctx
, isl_error_invalid
,
495 "position out of bounds", return NULL
);
497 pos
+= isl_local_space_offset(aff
->ls
, type
);
498 v
= isl_val_rat_from_isl_int(ctx
, aff
->v
->el
[1 + pos
], aff
->v
->el
[0]);
499 return isl_val_normalize(v
);
502 __isl_give isl_aff
*isl_aff_set_denominator(__isl_take isl_aff
*aff
, isl_int v
)
504 aff
= isl_aff_cow(aff
);
508 aff
->v
= isl_vec_cow(aff
->v
);
510 return isl_aff_free(aff
);
512 isl_int_set(aff
->v
->el
[0], v
);
517 __isl_give isl_aff
*isl_aff_set_constant(__isl_take isl_aff
*aff
, isl_int v
)
519 aff
= isl_aff_cow(aff
);
523 aff
->v
= isl_vec_cow(aff
->v
);
525 return isl_aff_free(aff
);
527 isl_int_set(aff
->v
->el
[1], v
);
532 /* Replace the constant term of "aff" by "v".
534 __isl_give isl_aff
*isl_aff_set_constant_val(__isl_take isl_aff
*aff
,
535 __isl_take isl_val
*v
)
540 if (!isl_val_is_rat(v
))
541 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
542 "expecting rational value", goto error
);
544 if (isl_int_eq(aff
->v
->el
[1], v
->n
) &&
545 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
550 aff
= isl_aff_cow(aff
);
553 aff
->v
= isl_vec_cow(aff
->v
);
557 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
558 isl_int_set(aff
->v
->el
[1], v
->n
);
559 } else if (isl_int_is_one(v
->d
)) {
560 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
562 isl_seq_scale(aff
->v
->el
+ 1,
563 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
564 isl_int_mul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
565 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
566 aff
->v
= isl_vec_normalize(aff
->v
);
579 __isl_give isl_aff
*isl_aff_add_constant(__isl_take isl_aff
*aff
, isl_int v
)
581 if (isl_int_is_zero(v
))
584 aff
= isl_aff_cow(aff
);
588 aff
->v
= isl_vec_cow(aff
->v
);
590 return isl_aff_free(aff
);
592 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
);
597 /* Add "v" to the constant term of "aff".
599 __isl_give isl_aff
*isl_aff_add_constant_val(__isl_take isl_aff
*aff
,
600 __isl_take isl_val
*v
)
605 if (isl_val_is_zero(v
)) {
610 if (!isl_val_is_rat(v
))
611 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
612 "expecting rational value", goto error
);
614 aff
= isl_aff_cow(aff
);
618 aff
->v
= isl_vec_cow(aff
->v
);
622 if (isl_int_is_one(v
->d
)) {
623 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
624 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
625 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
->n
);
626 aff
->v
= isl_vec_normalize(aff
->v
);
630 isl_seq_scale(aff
->v
->el
+ 1,
631 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
632 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
->n
);
633 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
634 aff
->v
= isl_vec_normalize(aff
->v
);
647 __isl_give isl_aff
*isl_aff_add_constant_si(__isl_take isl_aff
*aff
, int v
)
652 isl_int_set_si(t
, v
);
653 aff
= isl_aff_add_constant(aff
, t
);
659 /* Add "v" to the numerator of the constant term of "aff".
661 __isl_give isl_aff
*isl_aff_add_constant_num(__isl_take isl_aff
*aff
, isl_int v
)
663 if (isl_int_is_zero(v
))
666 aff
= isl_aff_cow(aff
);
670 aff
->v
= isl_vec_cow(aff
->v
);
672 return isl_aff_free(aff
);
674 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
);
679 /* Add "v" to the numerator of the constant term of "aff".
681 __isl_give isl_aff
*isl_aff_add_constant_num_si(__isl_take isl_aff
*aff
, int v
)
689 isl_int_set_si(t
, v
);
690 aff
= isl_aff_add_constant_num(aff
, t
);
696 __isl_give isl_aff
*isl_aff_set_constant_si(__isl_take isl_aff
*aff
, int v
)
698 aff
= isl_aff_cow(aff
);
702 aff
->v
= isl_vec_cow(aff
->v
);
704 return isl_aff_free(aff
);
706 isl_int_set_si(aff
->v
->el
[1], v
);
711 __isl_give isl_aff
*isl_aff_set_coefficient(__isl_take isl_aff
*aff
,
712 enum isl_dim_type type
, int pos
, isl_int v
)
717 if (type
== isl_dim_out
)
718 isl_die(aff
->v
->ctx
, isl_error_invalid
,
719 "output/set dimension does not have a coefficient",
720 return isl_aff_free(aff
));
721 if (type
== isl_dim_in
)
724 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
725 isl_die(aff
->v
->ctx
, isl_error_invalid
,
726 "position out of bounds", return isl_aff_free(aff
));
728 aff
= isl_aff_cow(aff
);
732 aff
->v
= isl_vec_cow(aff
->v
);
734 return isl_aff_free(aff
);
736 pos
+= isl_local_space_offset(aff
->ls
, type
);
737 isl_int_set(aff
->v
->el
[1 + pos
], v
);
742 __isl_give isl_aff
*isl_aff_set_coefficient_si(__isl_take isl_aff
*aff
,
743 enum isl_dim_type type
, int pos
, int v
)
748 if (type
== isl_dim_out
)
749 isl_die(aff
->v
->ctx
, isl_error_invalid
,
750 "output/set dimension does not have a coefficient",
751 return isl_aff_free(aff
));
752 if (type
== isl_dim_in
)
755 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
756 isl_die(aff
->v
->ctx
, isl_error_invalid
,
757 "position out of bounds", return isl_aff_free(aff
));
759 aff
= isl_aff_cow(aff
);
763 aff
->v
= isl_vec_cow(aff
->v
);
765 return isl_aff_free(aff
);
767 pos
+= isl_local_space_offset(aff
->ls
, type
);
768 isl_int_set_si(aff
->v
->el
[1 + pos
], v
);
773 /* Replace the coefficient of the variable of type "type" at position "pos"
776 __isl_give isl_aff
*isl_aff_set_coefficient_val(__isl_take isl_aff
*aff
,
777 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
782 if (type
== isl_dim_out
)
783 isl_die(aff
->v
->ctx
, isl_error_invalid
,
784 "output/set dimension does not have a coefficient",
786 if (type
== isl_dim_in
)
789 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
790 isl_die(aff
->v
->ctx
, isl_error_invalid
,
791 "position out of bounds", goto error
);
793 if (!isl_val_is_rat(v
))
794 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
795 "expecting rational value", goto error
);
797 pos
+= isl_local_space_offset(aff
->ls
, type
);
798 if (isl_int_eq(aff
->v
->el
[1 + pos
], v
->n
) &&
799 isl_int_eq(aff
->v
->el
[0], v
->d
)) {
804 aff
= isl_aff_cow(aff
);
807 aff
->v
= isl_vec_cow(aff
->v
);
811 if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
812 isl_int_set(aff
->v
->el
[1 + pos
], v
->n
);
813 } else if (isl_int_is_one(v
->d
)) {
814 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
816 isl_seq_scale(aff
->v
->el
+ 1,
817 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
818 isl_int_mul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
819 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
820 aff
->v
= isl_vec_normalize(aff
->v
);
833 __isl_give isl_aff
*isl_aff_add_coefficient(__isl_take isl_aff
*aff
,
834 enum isl_dim_type type
, int pos
, isl_int v
)
839 if (type
== isl_dim_out
)
840 isl_die(aff
->v
->ctx
, isl_error_invalid
,
841 "output/set dimension does not have a coefficient",
842 return isl_aff_free(aff
));
843 if (type
== isl_dim_in
)
846 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
847 isl_die(aff
->v
->ctx
, isl_error_invalid
,
848 "position out of bounds", return isl_aff_free(aff
));
850 aff
= isl_aff_cow(aff
);
854 aff
->v
= isl_vec_cow(aff
->v
);
856 return isl_aff_free(aff
);
858 pos
+= isl_local_space_offset(aff
->ls
, type
);
859 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
);
864 /* Add "v" to the coefficient of the variable of type "type"
865 * at position "pos" of "aff".
867 __isl_give isl_aff
*isl_aff_add_coefficient_val(__isl_take isl_aff
*aff
,
868 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
873 if (isl_val_is_zero(v
)) {
878 if (type
== isl_dim_out
)
879 isl_die(aff
->v
->ctx
, isl_error_invalid
,
880 "output/set dimension does not have a coefficient",
882 if (type
== isl_dim_in
)
885 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
886 isl_die(aff
->v
->ctx
, isl_error_invalid
,
887 "position out of bounds", goto error
);
889 if (!isl_val_is_rat(v
))
890 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
891 "expecting rational value", goto error
);
893 aff
= isl_aff_cow(aff
);
897 aff
->v
= isl_vec_cow(aff
->v
);
901 pos
+= isl_local_space_offset(aff
->ls
, type
);
902 if (isl_int_is_one(v
->d
)) {
903 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
904 } else if (isl_int_eq(aff
->v
->el
[0], v
->d
)) {
905 isl_int_add(aff
->v
->el
[1 + pos
], aff
->v
->el
[1 + pos
], v
->n
);
906 aff
->v
= isl_vec_normalize(aff
->v
);
910 isl_seq_scale(aff
->v
->el
+ 1,
911 aff
->v
->el
+ 1, v
->d
, aff
->v
->size
- 1);
912 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
->n
);
913 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], v
->d
);
914 aff
->v
= isl_vec_normalize(aff
->v
);
927 __isl_give isl_aff
*isl_aff_add_coefficient_si(__isl_take isl_aff
*aff
,
928 enum isl_dim_type type
, int pos
, int v
)
933 isl_int_set_si(t
, v
);
934 aff
= isl_aff_add_coefficient(aff
, type
, pos
, t
);
940 __isl_give isl_aff
*isl_aff_get_div(__isl_keep isl_aff
*aff
, int pos
)
945 return isl_local_space_get_div(aff
->ls
, pos
);
948 __isl_give isl_aff
*isl_aff_neg(__isl_take isl_aff
*aff
)
950 aff
= isl_aff_cow(aff
);
953 aff
->v
= isl_vec_cow(aff
->v
);
955 return isl_aff_free(aff
);
957 isl_seq_neg(aff
->v
->el
+ 1, aff
->v
->el
+ 1, aff
->v
->size
- 1);
962 /* Remove divs from the local space that do not appear in the affine
964 * We currently only remove divs at the end.
965 * Some intermediate divs may also not appear directly in the affine
966 * expression, but we would also need to check that no other divs are
967 * defined in terms of them.
969 __isl_give isl_aff
*isl_aff_remove_unused_divs( __isl_take isl_aff
*aff
)
978 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
979 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
981 pos
= isl_seq_last_non_zero(aff
->v
->el
+ 1 + off
, n
) + 1;
985 aff
= isl_aff_cow(aff
);
989 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, isl_dim_div
, pos
, n
- pos
);
990 aff
->v
= isl_vec_drop_els(aff
->v
, 1 + off
+ pos
, n
- pos
);
991 if (!aff
->ls
|| !aff
->v
)
992 return isl_aff_free(aff
);
997 /* Given two affine expressions "p" of length p_len (including the
998 * denominator and the constant term) and "subs" of length subs_len,
999 * plug in "subs" for the variable at position "pos".
1000 * The variables of "subs" and "p" are assumed to match up to subs_len,
1001 * but "p" may have additional variables.
1002 * "v" is an initialized isl_int that can be used internally.
1004 * In particular, if "p" represents the expression
1008 * with i the variable at position "pos" and "subs" represents the expression
1012 * then the result represents the expression
1017 void isl_seq_substitute(isl_int
*p
, int pos
, isl_int
*subs
,
1018 int p_len
, int subs_len
, isl_int v
)
1020 isl_int_set(v
, p
[1 + pos
]);
1021 isl_int_set_si(p
[1 + pos
], 0);
1022 isl_seq_combine(p
+ 1, subs
[0], p
+ 1, v
, subs
+ 1, subs_len
- 1);
1023 isl_seq_scale(p
+ subs_len
, p
+ subs_len
, subs
[0], p_len
- subs_len
);
1024 isl_int_mul(p
[0], p
[0], subs
[0]);
1027 /* Look for any divs in the aff->ls with a denominator equal to one
1028 * and plug them into the affine expression and any subsequent divs
1029 * that may reference the div.
1031 static __isl_give isl_aff
*plug_in_integral_divs(__isl_take isl_aff
*aff
)
1037 isl_local_space
*ls
;
1043 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1045 for (i
= 0; i
< n
; ++i
) {
1046 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][0]))
1048 ls
= isl_local_space_copy(aff
->ls
);
1049 ls
= isl_local_space_substitute_seq(ls
, isl_dim_div
, i
,
1050 aff
->ls
->div
->row
[i
], len
, i
+ 1, n
- (i
+ 1));
1051 vec
= isl_vec_copy(aff
->v
);
1052 vec
= isl_vec_cow(vec
);
1058 pos
= isl_local_space_offset(aff
->ls
, isl_dim_div
) + i
;
1059 isl_seq_substitute(vec
->el
, pos
, aff
->ls
->div
->row
[i
],
1064 isl_vec_free(aff
->v
);
1066 isl_local_space_free(aff
->ls
);
1073 isl_local_space_free(ls
);
1074 return isl_aff_free(aff
);
1077 /* Look for any divs j that appear with a unit coefficient inside
1078 * the definitions of other divs i and plug them into the definitions
1081 * In particular, an expression of the form
1083 * floor((f(..) + floor(g(..)/n))/m)
1087 * floor((n * f(..) + g(..))/(n * m))
1089 * This simplification is correct because we can move the expression
1090 * f(..) into the inner floor in the original expression to obtain
1092 * floor(floor((n * f(..) + g(..))/n)/m)
1094 * from which we can derive the simplified expression.
1096 static __isl_give isl_aff
*plug_in_unit_divs(__isl_take isl_aff
*aff
)
1104 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1105 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1106 for (i
= 1; i
< n
; ++i
) {
1107 for (j
= 0; j
< i
; ++j
) {
1108 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][1 + off
+ j
]))
1110 aff
->ls
= isl_local_space_substitute_seq(aff
->ls
,
1111 isl_dim_div
, j
, aff
->ls
->div
->row
[j
],
1112 aff
->v
->size
, i
, 1);
1114 return isl_aff_free(aff
);
1121 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
1123 * Even though this function is only called on isl_affs with a single
1124 * reference, we are careful to only change aff->v and aff->ls together.
1126 static __isl_give isl_aff
*swap_div(__isl_take isl_aff
*aff
, int a
, int b
)
1128 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1129 isl_local_space
*ls
;
1132 ls
= isl_local_space_copy(aff
->ls
);
1133 ls
= isl_local_space_swap_div(ls
, a
, b
);
1134 v
= isl_vec_copy(aff
->v
);
1139 isl_int_swap(v
->el
[1 + off
+ a
], v
->el
[1 + off
+ b
]);
1140 isl_vec_free(aff
->v
);
1142 isl_local_space_free(aff
->ls
);
1148 isl_local_space_free(ls
);
1149 return isl_aff_free(aff
);
1152 /* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
1154 * We currently do not actually remove div "b", but simply add its
1155 * coefficient to that of "a" and then zero it out.
1157 static __isl_give isl_aff
*merge_divs(__isl_take isl_aff
*aff
, int a
, int b
)
1159 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1161 if (isl_int_is_zero(aff
->v
->el
[1 + off
+ b
]))
1164 aff
->v
= isl_vec_cow(aff
->v
);
1166 return isl_aff_free(aff
);
1168 isl_int_add(aff
->v
->el
[1 + off
+ a
],
1169 aff
->v
->el
[1 + off
+ a
], aff
->v
->el
[1 + off
+ b
]);
1170 isl_int_set_si(aff
->v
->el
[1 + off
+ b
], 0);
1175 /* Sort the divs in the local space of "aff" according to
1176 * the comparison function "cmp_row" in isl_local_space.c,
1177 * combining the coefficients of identical divs.
1179 * Reordering divs does not change the semantics of "aff",
1180 * so there is no need to call isl_aff_cow.
1181 * Moreover, this function is currently only called on isl_affs
1182 * with a single reference.
1184 static __isl_give isl_aff
*sort_divs(__isl_take isl_aff
*aff
)
1192 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
1193 n
= isl_aff_dim(aff
, isl_dim_div
);
1194 for (i
= 1; i
< n
; ++i
) {
1195 for (j
= i
- 1; j
>= 0; --j
) {
1196 int cmp
= isl_mat_cmp_div(aff
->ls
->div
, j
, j
+ 1);
1200 aff
= merge_divs(aff
, j
, j
+ 1);
1202 aff
= swap_div(aff
, j
, j
+ 1);
1211 /* Normalize the representation of "aff".
1213 * This function should only be called of "new" isl_affs, i.e.,
1214 * with only a single reference. We therefore do not need to
1215 * worry about affecting other instances.
1217 __isl_give isl_aff
*isl_aff_normalize(__isl_take isl_aff
*aff
)
1221 aff
->v
= isl_vec_normalize(aff
->v
);
1223 return isl_aff_free(aff
);
1224 aff
= plug_in_integral_divs(aff
);
1225 aff
= plug_in_unit_divs(aff
);
1226 aff
= sort_divs(aff
);
1227 aff
= isl_aff_remove_unused_divs(aff
);
1231 /* Given f, return floor(f).
1232 * If f is an integer expression, then just return f.
1233 * If f is a constant, then return the constant floor(f).
1234 * Otherwise, if f = g/m, write g = q m + r,
1235 * create a new div d = [r/m] and return the expression q + d.
1236 * The coefficients in r are taken to lie between -m/2 and m/2.
1238 __isl_give isl_aff
*isl_aff_floor(__isl_take isl_aff
*aff
)
1248 if (isl_int_is_one(aff
->v
->el
[0]))
1251 aff
= isl_aff_cow(aff
);
1255 aff
->v
= isl_vec_cow(aff
->v
);
1257 return isl_aff_free(aff
);
1259 if (isl_aff_is_cst(aff
)) {
1260 isl_int_fdiv_q(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1261 isl_int_set_si(aff
->v
->el
[0], 1);
1265 div
= isl_vec_copy(aff
->v
);
1266 div
= isl_vec_cow(div
);
1268 return isl_aff_free(aff
);
1270 ctx
= isl_aff_get_ctx(aff
);
1271 isl_int_fdiv_q(aff
->v
->el
[0], aff
->v
->el
[0], ctx
->two
);
1272 for (i
= 1; i
< aff
->v
->size
; ++i
) {
1273 isl_int_fdiv_r(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1274 isl_int_fdiv_q(aff
->v
->el
[i
], aff
->v
->el
[i
], div
->el
[0]);
1275 if (isl_int_gt(div
->el
[i
], aff
->v
->el
[0])) {
1276 isl_int_sub(div
->el
[i
], div
->el
[i
], div
->el
[0]);
1277 isl_int_add_ui(aff
->v
->el
[i
], aff
->v
->el
[i
], 1);
1281 aff
->ls
= isl_local_space_add_div(aff
->ls
, div
);
1283 return isl_aff_free(aff
);
1285 size
= aff
->v
->size
;
1286 aff
->v
= isl_vec_extend(aff
->v
, size
+ 1);
1288 return isl_aff_free(aff
);
1289 isl_int_set_si(aff
->v
->el
[0], 1);
1290 isl_int_set_si(aff
->v
->el
[size
], 1);
1292 aff
= isl_aff_normalize(aff
);
1299 * aff mod m = aff - m * floor(aff/m)
1301 __isl_give isl_aff
*isl_aff_mod(__isl_take isl_aff
*aff
, isl_int m
)
1305 res
= isl_aff_copy(aff
);
1306 aff
= isl_aff_scale_down(aff
, m
);
1307 aff
= isl_aff_floor(aff
);
1308 aff
= isl_aff_scale(aff
, m
);
1309 res
= isl_aff_sub(res
, aff
);
1316 * aff mod m = aff - m * floor(aff/m)
1318 * with m an integer value.
1320 __isl_give isl_aff
*isl_aff_mod_val(__isl_take isl_aff
*aff
,
1321 __isl_take isl_val
*m
)
1328 if (!isl_val_is_int(m
))
1329 isl_die(isl_val_get_ctx(m
), isl_error_invalid
,
1330 "expecting integer modulo", goto error
);
1332 res
= isl_aff_copy(aff
);
1333 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(m
));
1334 aff
= isl_aff_floor(aff
);
1335 aff
= isl_aff_scale_val(aff
, m
);
1336 res
= isl_aff_sub(res
, aff
);
1347 * pwaff mod m = pwaff - m * floor(pwaff/m)
1349 __isl_give isl_pw_aff
*isl_pw_aff_mod(__isl_take isl_pw_aff
*pwaff
, isl_int m
)
1353 res
= isl_pw_aff_copy(pwaff
);
1354 pwaff
= isl_pw_aff_scale_down(pwaff
, m
);
1355 pwaff
= isl_pw_aff_floor(pwaff
);
1356 pwaff
= isl_pw_aff_scale(pwaff
, m
);
1357 res
= isl_pw_aff_sub(res
, pwaff
);
1364 * pa mod m = pa - m * floor(pa/m)
1366 * with m an integer value.
1368 __isl_give isl_pw_aff
*isl_pw_aff_mod_val(__isl_take isl_pw_aff
*pa
,
1369 __isl_take isl_val
*m
)
1373 if (!isl_val_is_int(m
))
1374 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
1375 "expecting integer modulo", goto error
);
1376 pa
= isl_pw_aff_mod(pa
, m
->n
);
1380 isl_pw_aff_free(pa
);
1385 /* Given f, return ceil(f).
1386 * If f is an integer expression, then just return f.
1387 * Otherwise, let f be the expression
1393 * floor((e + m - 1)/m)
1395 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
1400 if (isl_int_is_one(aff
->v
->el
[0]))
1403 aff
= isl_aff_cow(aff
);
1406 aff
->v
= isl_vec_cow(aff
->v
);
1408 return isl_aff_free(aff
);
1410 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1411 isl_int_sub_ui(aff
->v
->el
[1], aff
->v
->el
[1], 1);
1412 aff
= isl_aff_floor(aff
);
1417 /* Apply the expansion computed by isl_merge_divs.
1418 * The expansion itself is given by "exp" while the resulting
1419 * list of divs is given by "div".
1421 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
1422 __isl_take isl_mat
*div
, int *exp
)
1429 aff
= isl_aff_cow(aff
);
1433 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1434 new_n_div
= isl_mat_rows(div
);
1435 if (new_n_div
< old_n_div
)
1436 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
1437 "not an expansion", goto error
);
1439 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
1443 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
1445 for (i
= new_n_div
- 1; i
>= 0; --i
) {
1446 if (j
>= 0 && exp
[j
] == i
) {
1448 isl_int_swap(aff
->v
->el
[offset
+ i
],
1449 aff
->v
->el
[offset
+ j
]);
1452 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
1455 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
1466 /* Add two affine expressions that live in the same local space.
1468 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
1469 __isl_take isl_aff
*aff2
)
1473 aff1
= isl_aff_cow(aff1
);
1477 aff1
->v
= isl_vec_cow(aff1
->v
);
1483 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
1484 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1485 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
1486 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
1487 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
1488 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1489 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
1501 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
1502 __isl_take isl_aff
*aff2
)
1512 ctx
= isl_aff_get_ctx(aff1
);
1513 if (!isl_space_is_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
1514 isl_die(ctx
, isl_error_invalid
,
1515 "spaces don't match", goto error
);
1517 if (aff1
->ls
->div
->n_row
== 0 && aff2
->ls
->div
->n_row
== 0)
1518 return add_expanded(aff1
, aff2
);
1520 exp1
= isl_alloc_array(ctx
, int, aff1
->ls
->div
->n_row
);
1521 exp2
= isl_alloc_array(ctx
, int, aff2
->ls
->div
->n_row
);
1525 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
1526 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
1527 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
1531 return add_expanded(aff1
, aff2
);
1540 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
1541 __isl_take isl_aff
*aff2
)
1543 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
1546 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
1550 if (isl_int_is_one(f
))
1553 aff
= isl_aff_cow(aff
);
1556 aff
->v
= isl_vec_cow(aff
->v
);
1558 return isl_aff_free(aff
);
1560 if (isl_int_is_pos(f
) && isl_int_is_divisible_by(aff
->v
->el
[0], f
)) {
1561 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], f
);
1566 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
1567 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1568 isl_int_divexact(gcd
, f
, gcd
);
1569 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1575 /* Multiple "aff" by "v".
1577 __isl_give isl_aff
*isl_aff_scale_val(__isl_take isl_aff
*aff
,
1578 __isl_take isl_val
*v
)
1583 if (isl_val_is_one(v
)) {
1588 if (!isl_val_is_rat(v
))
1589 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1590 "expecting rational factor", goto error
);
1592 aff
= isl_aff_scale(aff
, v
->n
);
1593 aff
= isl_aff_scale_down(aff
, v
->d
);
1603 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
1607 if (isl_int_is_one(f
))
1610 aff
= isl_aff_cow(aff
);
1614 if (isl_int_is_zero(f
))
1615 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1616 "cannot scale down by zero", return isl_aff_free(aff
));
1618 aff
->v
= isl_vec_cow(aff
->v
);
1620 return isl_aff_free(aff
);
1623 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
1624 isl_int_gcd(gcd
, gcd
, f
);
1625 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1626 isl_int_divexact(gcd
, f
, gcd
);
1627 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1633 /* Divide "aff" by "v".
1635 __isl_give isl_aff
*isl_aff_scale_down_val(__isl_take isl_aff
*aff
,
1636 __isl_take isl_val
*v
)
1641 if (isl_val_is_one(v
)) {
1646 if (!isl_val_is_rat(v
))
1647 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1648 "expecting rational factor", goto error
);
1649 if (!isl_val_is_pos(v
))
1650 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1651 "factor needs to be positive", goto error
);
1653 aff
= isl_aff_scale(aff
, v
->d
);
1654 aff
= isl_aff_scale_down(aff
, v
->n
);
1664 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
1672 isl_int_set_ui(v
, f
);
1673 aff
= isl_aff_scale_down(aff
, v
);
1679 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
1680 enum isl_dim_type type
, unsigned pos
, const char *s
)
1682 aff
= isl_aff_cow(aff
);
1685 if (type
== isl_dim_out
)
1686 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1687 "cannot set name of output/set dimension",
1688 return isl_aff_free(aff
));
1689 if (type
== isl_dim_in
)
1691 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
1693 return isl_aff_free(aff
);
1698 __isl_give isl_aff
*isl_aff_set_dim_id(__isl_take isl_aff
*aff
,
1699 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1701 aff
= isl_aff_cow(aff
);
1703 return isl_id_free(id
);
1704 if (type
== isl_dim_out
)
1705 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1706 "cannot set name of output/set dimension",
1708 if (type
== isl_dim_in
)
1710 aff
->ls
= isl_local_space_set_dim_id(aff
->ls
, type
, pos
, id
);
1712 return isl_aff_free(aff
);
1721 /* Exploit the equalities in "eq" to simplify the affine expression
1722 * and the expressions of the integer divisions in the local space.
1723 * The integer divisions in this local space are assumed to appear
1724 * as regular dimensions in "eq".
1726 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
1727 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1735 if (eq
->n_eq
== 0) {
1736 isl_basic_set_free(eq
);
1740 aff
= isl_aff_cow(aff
);
1744 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
1745 isl_basic_set_copy(eq
));
1746 aff
->v
= isl_vec_cow(aff
->v
);
1747 if (!aff
->ls
|| !aff
->v
)
1750 total
= 1 + isl_space_dim(eq
->dim
, isl_dim_all
);
1752 for (i
= 0; i
< eq
->n_eq
; ++i
) {
1753 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
1754 if (j
< 0 || j
== 0 || j
>= total
)
1757 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
1761 isl_basic_set_free(eq
);
1762 aff
= isl_aff_normalize(aff
);
1765 isl_basic_set_free(eq
);
1770 /* Exploit the equalities in "eq" to simplify the affine expression
1771 * and the expressions of the integer divisions in the local space.
1773 static __isl_give isl_aff
*isl_aff_substitute_equalities(
1774 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1780 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1782 eq
= isl_basic_set_add_dims(eq
, isl_dim_set
, n_div
);
1783 return isl_aff_substitute_equalities_lifted(aff
, eq
);
1785 isl_basic_set_free(eq
);
1790 /* Look for equalities among the variables shared by context and aff
1791 * and the integer divisions of aff, if any.
1792 * The equalities are then used to eliminate coefficients and/or integer
1793 * divisions from aff.
1795 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
1796 __isl_take isl_set
*context
)
1798 isl_basic_set
*hull
;
1803 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1805 isl_basic_set
*bset
;
1806 isl_local_space
*ls
;
1807 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
1808 ls
= isl_aff_get_domain_local_space(aff
);
1809 bset
= isl_basic_set_from_local_space(ls
);
1810 bset
= isl_basic_set_lift(bset
);
1811 bset
= isl_basic_set_flatten(bset
);
1812 context
= isl_set_intersect(context
,
1813 isl_set_from_basic_set(bset
));
1816 hull
= isl_set_affine_hull(context
);
1817 return isl_aff_substitute_equalities_lifted(aff
, hull
);
1820 isl_set_free(context
);
1824 __isl_give isl_aff
*isl_aff_gist_params(__isl_take isl_aff
*aff
,
1825 __isl_take isl_set
*context
)
1827 isl_set
*dom_context
= isl_set_universe(isl_aff_get_domain_space(aff
));
1828 dom_context
= isl_set_intersect_params(dom_context
, context
);
1829 return isl_aff_gist(aff
, dom_context
);
1832 /* Return a basic set containing those elements in the space
1833 * of aff where it is non-negative.
1834 * If "rational" is set, then return a rational basic set.
1836 static __isl_give isl_basic_set
*aff_nonneg_basic_set(
1837 __isl_take isl_aff
*aff
, int rational
)
1839 isl_constraint
*ineq
;
1840 isl_basic_set
*bset
;
1842 ineq
= isl_inequality_from_aff(aff
);
1844 bset
= isl_basic_set_from_constraint(ineq
);
1846 bset
= isl_basic_set_set_rational(bset
);
1847 bset
= isl_basic_set_simplify(bset
);
1851 /* Return a basic set containing those elements in the space
1852 * of aff where it is non-negative.
1854 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
1856 return aff_nonneg_basic_set(aff
, 0);
1859 /* Return a basic set containing those elements in the domain space
1860 * of aff where it is negative.
1862 __isl_give isl_basic_set
*isl_aff_neg_basic_set(__isl_take isl_aff
*aff
)
1864 aff
= isl_aff_neg(aff
);
1865 aff
= isl_aff_add_constant_num_si(aff
, -1);
1866 return isl_aff_nonneg_basic_set(aff
);
1869 /* Return a basic set containing those elements in the space
1870 * of aff where it is zero.
1871 * If "rational" is set, then return a rational basic set.
1873 static __isl_give isl_basic_set
*aff_zero_basic_set(__isl_take isl_aff
*aff
,
1876 isl_constraint
*ineq
;
1877 isl_basic_set
*bset
;
1879 ineq
= isl_equality_from_aff(aff
);
1881 bset
= isl_basic_set_from_constraint(ineq
);
1883 bset
= isl_basic_set_set_rational(bset
);
1884 bset
= isl_basic_set_simplify(bset
);
1888 /* Return a basic set containing those elements in the space
1889 * of aff where it is zero.
1891 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
1893 return aff_zero_basic_set(aff
, 0);
1896 /* Return a basic set containing those elements in the shared space
1897 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1899 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
1900 __isl_take isl_aff
*aff2
)
1902 aff1
= isl_aff_sub(aff1
, aff2
);
1904 return isl_aff_nonneg_basic_set(aff1
);
1907 /* Return a basic set containing those elements in the shared space
1908 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1910 __isl_give isl_basic_set
*isl_aff_le_basic_set(__isl_take isl_aff
*aff1
,
1911 __isl_take isl_aff
*aff2
)
1913 return isl_aff_ge_basic_set(aff2
, aff1
);
1916 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
1917 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
1919 aff1
= isl_aff_add(aff1
, aff2
);
1920 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
1924 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
1932 /* Check whether the given affine expression has non-zero coefficient
1933 * for any dimension in the given range or if any of these dimensions
1934 * appear with non-zero coefficients in any of the integer divisions
1935 * involved in the affine expression.
1937 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
1938 enum isl_dim_type type
, unsigned first
, unsigned n
)
1950 ctx
= isl_aff_get_ctx(aff
);
1951 if (first
+ n
> isl_aff_dim(aff
, type
))
1952 isl_die(ctx
, isl_error_invalid
,
1953 "range out of bounds", return -1);
1955 active
= isl_local_space_get_active(aff
->ls
, aff
->v
->el
+ 2);
1959 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
1960 for (i
= 0; i
< n
; ++i
)
1961 if (active
[first
+ i
]) {
1974 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
1975 enum isl_dim_type type
, unsigned first
, unsigned n
)
1981 if (type
== isl_dim_out
)
1982 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1983 "cannot drop output/set dimension",
1984 return isl_aff_free(aff
));
1985 if (type
== isl_dim_in
)
1987 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1990 ctx
= isl_aff_get_ctx(aff
);
1991 if (first
+ n
> isl_local_space_dim(aff
->ls
, type
))
1992 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
1993 return isl_aff_free(aff
));
1995 aff
= isl_aff_cow(aff
);
1999 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
2001 return isl_aff_free(aff
);
2003 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2004 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
2006 return isl_aff_free(aff
);
2011 /* Project the domain of the affine expression onto its parameter space.
2012 * The affine expression may not involve any of the domain dimensions.
2014 __isl_give isl_aff
*isl_aff_project_domain_on_params(__isl_take isl_aff
*aff
)
2020 n
= isl_aff_dim(aff
, isl_dim_in
);
2021 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, 0, n
);
2023 return isl_aff_free(aff
);
2025 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
2026 "affine expression involves some of the domain dimensions",
2027 return isl_aff_free(aff
));
2028 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, 0, n
);
2029 space
= isl_aff_get_domain_space(aff
);
2030 space
= isl_space_params(space
);
2031 aff
= isl_aff_reset_domain_space(aff
, space
);
2035 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
2036 enum isl_dim_type type
, unsigned first
, unsigned n
)
2042 if (type
== isl_dim_out
)
2043 isl_die(aff
->v
->ctx
, isl_error_invalid
,
2044 "cannot insert output/set dimensions",
2045 return isl_aff_free(aff
));
2046 if (type
== isl_dim_in
)
2048 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
2051 ctx
= isl_aff_get_ctx(aff
);
2052 if (first
> isl_local_space_dim(aff
->ls
, type
))
2053 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
2054 return isl_aff_free(aff
));
2056 aff
= isl_aff_cow(aff
);
2060 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
2062 return isl_aff_free(aff
);
2064 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
2065 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
2067 return isl_aff_free(aff
);
2072 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
2073 enum isl_dim_type type
, unsigned n
)
2077 pos
= isl_aff_dim(aff
, type
);
2079 return isl_aff_insert_dims(aff
, type
, pos
, n
);
2082 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
2083 enum isl_dim_type type
, unsigned n
)
2087 pos
= isl_pw_aff_dim(pwaff
, type
);
2089 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
2092 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
2094 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
2095 return isl_pw_aff_alloc(dom
, aff
);
2099 #define PW isl_pw_aff
2103 #define EL_IS_ZERO is_empty
2107 #define IS_ZERO is_empty
2110 #undef DEFAULT_IS_ZERO
2111 #define DEFAULT_IS_ZERO 0
2115 #define NO_MOVE_DIMS
2119 #include <isl_pw_templ.c>
2121 static __isl_give isl_set
*align_params_pw_pw_set_and(
2122 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
2123 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2124 __isl_take isl_pw_aff
*pwaff2
))
2126 if (!pwaff1
|| !pwaff2
)
2128 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
2129 pwaff2
->dim
, isl_dim_param
))
2130 return fn(pwaff1
, pwaff2
);
2131 if (!isl_space_has_named_params(pwaff1
->dim
) ||
2132 !isl_space_has_named_params(pwaff2
->dim
))
2133 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
2134 "unaligned unnamed parameters", goto error
);
2135 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
2136 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
2137 return fn(pwaff1
, pwaff2
);
2139 isl_pw_aff_free(pwaff1
);
2140 isl_pw_aff_free(pwaff2
);
2144 /* Compute a piecewise quasi-affine expression with a domain that
2145 * is the union of those of pwaff1 and pwaff2 and such that on each
2146 * cell, the quasi-affine expression is the better (according to cmp)
2147 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
2148 * is defined on a given cell, then the associated expression
2149 * is the defined one.
2151 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2152 __isl_take isl_pw_aff
*pwaff2
,
2153 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
2154 __isl_take isl_aff
*aff2
))
2161 if (!pwaff1
|| !pwaff2
)
2164 ctx
= isl_space_get_ctx(pwaff1
->dim
);
2165 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
2166 isl_die(ctx
, isl_error_invalid
,
2167 "arguments should live in same space", goto error
);
2169 if (isl_pw_aff_is_empty(pwaff1
)) {
2170 isl_pw_aff_free(pwaff1
);
2174 if (isl_pw_aff_is_empty(pwaff2
)) {
2175 isl_pw_aff_free(pwaff2
);
2179 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
2180 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
2182 for (i
= 0; i
< pwaff1
->n
; ++i
) {
2183 set
= isl_set_copy(pwaff1
->p
[i
].set
);
2184 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2185 struct isl_set
*common
;
2188 common
= isl_set_intersect(
2189 isl_set_copy(pwaff1
->p
[i
].set
),
2190 isl_set_copy(pwaff2
->p
[j
].set
));
2191 better
= isl_set_from_basic_set(cmp(
2192 isl_aff_copy(pwaff2
->p
[j
].aff
),
2193 isl_aff_copy(pwaff1
->p
[i
].aff
)));
2194 better
= isl_set_intersect(common
, better
);
2195 if (isl_set_plain_is_empty(better
)) {
2196 isl_set_free(better
);
2199 set
= isl_set_subtract(set
, isl_set_copy(better
));
2201 res
= isl_pw_aff_add_piece(res
, better
,
2202 isl_aff_copy(pwaff2
->p
[j
].aff
));
2204 res
= isl_pw_aff_add_piece(res
, set
,
2205 isl_aff_copy(pwaff1
->p
[i
].aff
));
2208 for (j
= 0; j
< pwaff2
->n
; ++j
) {
2209 set
= isl_set_copy(pwaff2
->p
[j
].set
);
2210 for (i
= 0; i
< pwaff1
->n
; ++i
)
2211 set
= isl_set_subtract(set
,
2212 isl_set_copy(pwaff1
->p
[i
].set
));
2213 res
= isl_pw_aff_add_piece(res
, set
,
2214 isl_aff_copy(pwaff2
->p
[j
].aff
));
2217 isl_pw_aff_free(pwaff1
);
2218 isl_pw_aff_free(pwaff2
);
2222 isl_pw_aff_free(pwaff1
);
2223 isl_pw_aff_free(pwaff2
);
2227 /* Compute a piecewise quasi-affine expression with a domain that
2228 * is the union of those of pwaff1 and pwaff2 and such that on each
2229 * cell, the quasi-affine expression is the maximum of those of pwaff1
2230 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2231 * cell, then the associated expression is the defined one.
2233 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2234 __isl_take isl_pw_aff
*pwaff2
)
2236 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
2239 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
2240 __isl_take isl_pw_aff
*pwaff2
)
2242 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2246 /* Compute a piecewise quasi-affine expression with a domain that
2247 * is the union of those of pwaff1 and pwaff2 and such that on each
2248 * cell, the quasi-affine expression is the minimum of those of pwaff1
2249 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2250 * cell, then the associated expression is the defined one.
2252 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2253 __isl_take isl_pw_aff
*pwaff2
)
2255 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
2258 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
2259 __isl_take isl_pw_aff
*pwaff2
)
2261 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
2265 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
2266 __isl_take isl_pw_aff
*pwaff2
, int max
)
2269 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
2271 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
2274 /* Construct a map with as domain the domain of pwaff and
2275 * one-dimensional range corresponding to the affine expressions.
2277 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2286 dim
= isl_pw_aff_get_space(pwaff
);
2287 map
= isl_map_empty(dim
);
2289 for (i
= 0; i
< pwaff
->n
; ++i
) {
2290 isl_basic_map
*bmap
;
2293 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
2294 map_i
= isl_map_from_basic_map(bmap
);
2295 map_i
= isl_map_intersect_domain(map_i
,
2296 isl_set_copy(pwaff
->p
[i
].set
));
2297 map
= isl_map_union_disjoint(map
, map_i
);
2300 isl_pw_aff_free(pwaff
);
2305 /* Construct a map with as domain the domain of pwaff and
2306 * one-dimensional range corresponding to the affine expressions.
2308 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2312 if (isl_space_is_set(pwaff
->dim
))
2313 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2314 "space of input is not a map",
2315 return isl_pw_aff_free(pwaff
));
2316 return map_from_pw_aff(pwaff
);
2319 /* Construct a one-dimensional set with as parameter domain
2320 * the domain of pwaff and the single set dimension
2321 * corresponding to the affine expressions.
2323 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
2327 if (!isl_space_is_set(pwaff
->dim
))
2328 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2329 "space of input is not a set",
2330 return isl_pw_aff_free(pwaff
));
2331 return map_from_pw_aff(pwaff
);
2334 /* Return a set containing those elements in the domain
2335 * of pwaff where it is non-negative.
2337 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
2345 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2347 for (i
= 0; i
< pwaff
->n
; ++i
) {
2348 isl_basic_set
*bset
;
2352 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2353 bset
= aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2355 set_i
= isl_set_from_basic_set(bset
);
2356 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
2357 set
= isl_set_union_disjoint(set
, set_i
);
2360 isl_pw_aff_free(pwaff
);
2365 /* Return a set containing those elements in the domain
2366 * of pwaff where it is zero (if complement is 0) or not zero
2367 * (if complement is 1).
2369 static __isl_give isl_set
*pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
,
2378 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
2380 for (i
= 0; i
< pwaff
->n
; ++i
) {
2381 isl_basic_set
*bset
;
2382 isl_set
*set_i
, *zero
;
2385 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
2386 bset
= aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
2388 zero
= isl_set_from_basic_set(bset
);
2389 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
2391 set_i
= isl_set_subtract(set_i
, zero
);
2393 set_i
= isl_set_intersect(set_i
, zero
);
2394 set
= isl_set_union_disjoint(set
, set_i
);
2397 isl_pw_aff_free(pwaff
);
2402 /* Return a set containing those elements in the domain
2403 * of pwaff where it is zero.
2405 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
2407 return pw_aff_zero_set(pwaff
, 0);
2410 /* Return a set containing those elements in the domain
2411 * of pwaff where it is not zero.
2413 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
2415 return pw_aff_zero_set(pwaff
, 1);
2418 /* Return a set containing those elements in the shared domain
2419 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2421 * We compute the difference on the shared domain and then construct
2422 * the set of values where this difference is non-negative.
2423 * If strict is set, we first subtract 1 from the difference.
2424 * If equal is set, we only return the elements where pwaff1 and pwaff2
2427 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
2428 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
2430 isl_set
*set1
, *set2
;
2432 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
2433 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
2434 set1
= isl_set_intersect(set1
, set2
);
2435 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
2436 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
2437 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
2440 isl_space
*dim
= isl_set_get_space(set1
);
2442 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
2443 aff
= isl_aff_add_constant_si(aff
, -1);
2444 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
2449 return isl_pw_aff_zero_set(pwaff1
);
2450 return isl_pw_aff_nonneg_set(pwaff1
);
2453 /* Return a set containing those elements in the shared domain
2454 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2456 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2457 __isl_take isl_pw_aff
*pwaff2
)
2459 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
2462 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2463 __isl_take isl_pw_aff
*pwaff2
)
2465 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2468 /* Return a set containing those elements in the shared domain
2469 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2471 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2472 __isl_take isl_pw_aff
*pwaff2
)
2474 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2477 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2478 __isl_take isl_pw_aff
*pwaff2
)
2480 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2483 /* Return a set containing those elements in the shared domain
2484 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2486 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2487 __isl_take isl_pw_aff
*pwaff2
)
2489 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2492 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2493 __isl_take isl_pw_aff
*pwaff2
)
2495 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2498 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2499 __isl_take isl_pw_aff
*pwaff2
)
2501 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2504 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2505 __isl_take isl_pw_aff
*pwaff2
)
2507 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2510 /* Return a set containing those elements in the shared domain
2511 * of the elements of list1 and list2 where each element in list1
2512 * has the relation specified by "fn" with each element in list2.
2514 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2515 __isl_take isl_pw_aff_list
*list2
,
2516 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2517 __isl_take isl_pw_aff
*pwaff2
))
2523 if (!list1
|| !list2
)
2526 ctx
= isl_pw_aff_list_get_ctx(list1
);
2527 if (list1
->n
< 1 || list2
->n
< 1)
2528 isl_die(ctx
, isl_error_invalid
,
2529 "list should contain at least one element", goto error
);
2531 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2532 for (i
= 0; i
< list1
->n
; ++i
)
2533 for (j
= 0; j
< list2
->n
; ++j
) {
2536 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2537 isl_pw_aff_copy(list2
->p
[j
]));
2538 set
= isl_set_intersect(set
, set_ij
);
2541 isl_pw_aff_list_free(list1
);
2542 isl_pw_aff_list_free(list2
);
2545 isl_pw_aff_list_free(list1
);
2546 isl_pw_aff_list_free(list2
);
2550 /* Return a set containing those elements in the shared domain
2551 * of the elements of list1 and list2 where each element in list1
2552 * is equal to each element in list2.
2554 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2555 __isl_take isl_pw_aff_list
*list2
)
2557 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
2560 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
2561 __isl_take isl_pw_aff_list
*list2
)
2563 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
2566 /* Return a set containing those elements in the shared domain
2567 * of the elements of list1 and list2 where each element in list1
2568 * is less than or equal to each element in list2.
2570 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
2571 __isl_take isl_pw_aff_list
*list2
)
2573 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
2576 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
2577 __isl_take isl_pw_aff_list
*list2
)
2579 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
2582 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
2583 __isl_take isl_pw_aff_list
*list2
)
2585 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
2588 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
2589 __isl_take isl_pw_aff_list
*list2
)
2591 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
2595 /* Return a set containing those elements in the shared domain
2596 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2598 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2599 __isl_take isl_pw_aff
*pwaff2
)
2601 isl_set
*set_lt
, *set_gt
;
2603 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
2604 isl_pw_aff_copy(pwaff2
));
2605 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
2606 return isl_set_union_disjoint(set_lt
, set_gt
);
2609 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2610 __isl_take isl_pw_aff
*pwaff2
)
2612 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
2615 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
2620 if (isl_int_is_one(v
))
2622 if (!isl_int_is_pos(v
))
2623 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2624 "factor needs to be positive",
2625 return isl_pw_aff_free(pwaff
));
2626 pwaff
= isl_pw_aff_cow(pwaff
);
2632 for (i
= 0; i
< pwaff
->n
; ++i
) {
2633 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
2634 if (!pwaff
->p
[i
].aff
)
2635 return isl_pw_aff_free(pwaff
);
2641 /* Divide "pa" by "f".
2643 __isl_give isl_pw_aff
*isl_pw_aff_scale_down_val(__isl_take isl_pw_aff
*pa
,
2644 __isl_take isl_val
*f
)
2651 if (isl_val_is_one(f
)) {
2656 if (!isl_val_is_rat(f
))
2657 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
2658 "expecting rational factor", goto error
);
2659 if (!isl_val_is_pos(f
))
2660 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
2661 "factor needs to be positive", goto error
);
2663 pa
= isl_pw_aff_cow(pa
);
2669 for (i
= 0; i
< pa
->n
; ++i
) {
2670 pa
->p
[i
].aff
= isl_aff_scale_down_val(pa
->p
[i
].aff
,
2679 isl_pw_aff_free(pa
);
2684 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
2688 pwaff
= isl_pw_aff_cow(pwaff
);
2694 for (i
= 0; i
< pwaff
->n
; ++i
) {
2695 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
2696 if (!pwaff
->p
[i
].aff
)
2697 return isl_pw_aff_free(pwaff
);
2703 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
2707 pwaff
= isl_pw_aff_cow(pwaff
);
2713 for (i
= 0; i
< pwaff
->n
; ++i
) {
2714 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
2715 if (!pwaff
->p
[i
].aff
)
2716 return isl_pw_aff_free(pwaff
);
2722 /* Assuming that "cond1" and "cond2" are disjoint,
2723 * return an affine expression that is equal to pwaff1 on cond1
2724 * and to pwaff2 on cond2.
2726 static __isl_give isl_pw_aff
*isl_pw_aff_select(
2727 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
2728 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
2730 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
2731 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
2733 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
2736 /* Return an affine expression that is equal to pwaff_true for elements
2737 * where "cond" is non-zero and to pwaff_false for elements where "cond"
2739 * That is, return cond ? pwaff_true : pwaff_false;
2741 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
2742 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
2744 isl_set
*cond_true
, *cond_false
;
2746 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
2747 cond_false
= isl_pw_aff_zero_set(cond
);
2748 return isl_pw_aff_select(cond_true
, pwaff_true
,
2749 cond_false
, pwaff_false
);
2752 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
2757 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
2760 /* Check whether pwaff is a piecewise constant.
2762 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
2769 for (i
= 0; i
< pwaff
->n
; ++i
) {
2770 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
2771 if (is_cst
< 0 || !is_cst
)
2778 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
2779 __isl_take isl_aff
*aff2
)
2781 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
2782 return isl_aff_mul(aff2
, aff1
);
2784 if (!isl_aff_is_cst(aff2
))
2785 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
2786 "at least one affine expression should be constant",
2789 aff1
= isl_aff_cow(aff1
);
2793 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
2794 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
2804 /* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant.
2806 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
2807 __isl_take isl_aff
*aff2
)
2812 is_cst
= isl_aff_is_cst(aff2
);
2816 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
2817 "second argument should be a constant", goto error
);
2822 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
2824 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2825 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2828 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
2829 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
2832 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2833 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2844 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2845 __isl_take isl_pw_aff
*pwaff2
)
2847 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
2850 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2851 __isl_take isl_pw_aff
*pwaff2
)
2853 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
2856 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
2857 __isl_take isl_pw_aff
*pwaff2
)
2859 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
2862 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2863 __isl_take isl_pw_aff
*pwaff2
)
2865 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
2868 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2869 __isl_take isl_pw_aff
*pwaff2
)
2871 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
2874 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2875 __isl_take isl_pw_aff
*pa2
)
2877 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
2880 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
2882 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2883 __isl_take isl_pw_aff
*pa2
)
2887 is_cst
= isl_pw_aff_is_cst(pa2
);
2891 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2892 "second argument should be a piecewise constant",
2894 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
2896 isl_pw_aff_free(pa1
);
2897 isl_pw_aff_free(pa2
);
2901 /* Compute the quotient of the integer division of "pa1" by "pa2"
2902 * with rounding towards zero.
2903 * "pa2" is assumed to be a piecewise constant.
2905 * In particular, return
2907 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
2910 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
2911 __isl_take isl_pw_aff
*pa2
)
2917 is_cst
= isl_pw_aff_is_cst(pa2
);
2921 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2922 "second argument should be a piecewise constant",
2925 pa1
= isl_pw_aff_div(pa1
, pa2
);
2927 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
2928 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
2929 c
= isl_pw_aff_ceil(pa1
);
2930 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
2932 isl_pw_aff_free(pa1
);
2933 isl_pw_aff_free(pa2
);
2937 /* Compute the remainder of the integer division of "pa1" by "pa2"
2938 * with rounding towards zero.
2939 * "pa2" is assumed to be a piecewise constant.
2941 * In particular, return
2943 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
2946 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
2947 __isl_take isl_pw_aff
*pa2
)
2952 is_cst
= isl_pw_aff_is_cst(pa2
);
2956 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2957 "second argument should be a piecewise constant",
2959 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
2960 res
= isl_pw_aff_mul(pa2
, res
);
2961 res
= isl_pw_aff_sub(pa1
, res
);
2964 isl_pw_aff_free(pa1
);
2965 isl_pw_aff_free(pa2
);
2969 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2970 __isl_take isl_pw_aff
*pwaff2
)
2975 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2976 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2977 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
2978 isl_pw_aff_copy(pwaff2
));
2979 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
2980 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
2983 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2984 __isl_take isl_pw_aff
*pwaff2
)
2986 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
2989 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2990 __isl_take isl_pw_aff
*pwaff2
)
2995 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2996 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2997 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
2998 isl_pw_aff_copy(pwaff2
));
2999 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
3000 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
3003 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
3004 __isl_take isl_pw_aff
*pwaff2
)
3006 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
3009 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
3010 __isl_take isl_pw_aff_list
*list
,
3011 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
3012 __isl_take isl_pw_aff
*pwaff2
))
3021 ctx
= isl_pw_aff_list_get_ctx(list
);
3023 isl_die(ctx
, isl_error_invalid
,
3024 "list should contain at least one element",
3025 return isl_pw_aff_list_free(list
));
3027 res
= isl_pw_aff_copy(list
->p
[0]);
3028 for (i
= 1; i
< list
->n
; ++i
)
3029 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
3031 isl_pw_aff_list_free(list
);
3035 /* Return an isl_pw_aff that maps each element in the intersection of the
3036 * domains of the elements of list to the minimal corresponding affine
3039 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
3041 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
3044 /* Return an isl_pw_aff that maps each element in the intersection of the
3045 * domains of the elements of list to the maximal corresponding affine
3048 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
3050 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
3053 /* Mark the domains of "pwaff" as rational.
3055 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__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
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
3067 if (!pwaff
->p
[i
].set
)
3068 return isl_pw_aff_free(pwaff
);
3074 /* Mark the domains of the elements of "list" as rational.
3076 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
3077 __isl_take isl_pw_aff_list
*list
)
3087 for (i
= 0; i
< n
; ++i
) {
3090 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
3091 pa
= isl_pw_aff_set_rational(pa
);
3092 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
3098 /* Check that the domain space of "aff" matches "space".
3100 * Return 0 on success and -1 on error.
3102 int isl_aff_check_match_domain_space(__isl_keep isl_aff
*aff
,
3103 __isl_keep isl_space
*space
)
3105 isl_space
*aff_space
;
3111 aff_space
= isl_aff_get_domain_space(aff
);
3113 match
= isl_space_match(space
, isl_dim_param
, aff_space
, isl_dim_param
);
3117 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3118 "parameters don't match", goto error
);
3119 match
= isl_space_tuple_match(space
, isl_dim_in
,
3120 aff_space
, isl_dim_set
);
3124 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
3125 "domains don't match", goto error
);
3126 isl_space_free(aff_space
);
3129 isl_space_free(aff_space
);
3136 #include <isl_multi_templ.c>
3138 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
3141 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
3142 __isl_take isl_multi_aff
*ma
)
3144 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
3145 return isl_pw_multi_aff_alloc(dom
, ma
);
3148 /* Create a piecewise multi-affine expression in the given space that maps each
3149 * input dimension to the corresponding output dimension.
3151 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
3152 __isl_take isl_space
*space
)
3154 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
3157 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*maff1
,
3158 __isl_take isl_multi_aff
*maff2
)
3160 return isl_multi_aff_bin_op(maff1
, maff2
, &isl_aff_add
);
3163 /* Subtract "ma2" from "ma1" and return the result.
3165 __isl_give isl_multi_aff
*isl_multi_aff_sub(__isl_take isl_multi_aff
*ma1
,
3166 __isl_take isl_multi_aff
*ma2
)
3168 return isl_multi_aff_bin_op(ma1
, ma2
, &isl_aff_sub
);
3171 /* Given two multi-affine expressions A -> B and C -> D,
3172 * construct a multi-affine expression [A -> C] -> [B -> D].
3174 __isl_give isl_multi_aff
*isl_multi_aff_product(
3175 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
3181 int in1
, in2
, out1
, out2
;
3183 in1
= isl_multi_aff_dim(ma1
, isl_dim_in
);
3184 in2
= isl_multi_aff_dim(ma2
, isl_dim_in
);
3185 out1
= isl_multi_aff_dim(ma1
, isl_dim_out
);
3186 out2
= isl_multi_aff_dim(ma2
, isl_dim_out
);
3187 space
= isl_space_product(isl_multi_aff_get_space(ma1
),
3188 isl_multi_aff_get_space(ma2
));
3189 res
= isl_multi_aff_alloc(isl_space_copy(space
));
3190 space
= isl_space_domain(space
);
3192 for (i
= 0; i
< out1
; ++i
) {
3193 aff
= isl_multi_aff_get_aff(ma1
, i
);
3194 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, in1
, in2
);
3195 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
3196 res
= isl_multi_aff_set_aff(res
, i
, aff
);
3199 for (i
= 0; i
< out2
; ++i
) {
3200 aff
= isl_multi_aff_get_aff(ma2
, i
);
3201 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, 0, in1
);
3202 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
3203 res
= isl_multi_aff_set_aff(res
, out1
+ i
, aff
);
3206 isl_space_free(space
);
3207 isl_multi_aff_free(ma1
);
3208 isl_multi_aff_free(ma2
);
3212 /* Exploit the equalities in "eq" to simplify the affine expressions.
3214 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
3215 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
3219 maff
= isl_multi_aff_cow(maff
);
3223 for (i
= 0; i
< maff
->n
; ++i
) {
3224 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
3225 isl_basic_set_copy(eq
));
3230 isl_basic_set_free(eq
);
3233 isl_basic_set_free(eq
);
3234 isl_multi_aff_free(maff
);
3238 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
3243 maff
= isl_multi_aff_cow(maff
);
3247 for (i
= 0; i
< maff
->n
; ++i
) {
3248 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
3250 return isl_multi_aff_free(maff
);
3256 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
3257 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
3259 maff1
= isl_multi_aff_add(maff1
, maff2
);
3260 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
3264 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
3272 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff
*maff1
,
3273 __isl_keep isl_multi_aff
*maff2
)
3278 if (!maff1
|| !maff2
)
3280 if (maff1
->n
!= maff2
->n
)
3282 equal
= isl_space_is_equal(maff1
->space
, maff2
->space
);
3283 if (equal
< 0 || !equal
)
3286 for (i
= 0; i
< maff1
->n
; ++i
) {
3287 equal
= isl_aff_plain_is_equal(maff1
->p
[i
], maff2
->p
[i
]);
3288 if (equal
< 0 || !equal
)
3295 /* Return the set of domain elements where "ma1" is lexicographically
3296 * smaller than or equal to "ma2".
3298 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
3299 __isl_take isl_multi_aff
*ma2
)
3301 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
3304 /* Return the set of domain elements where "ma1" is lexicographically
3305 * greater than or equal to "ma2".
3307 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
3308 __isl_take isl_multi_aff
*ma2
)
3311 isl_map
*map1
, *map2
;
3314 map1
= isl_map_from_multi_aff(ma1
);
3315 map2
= isl_map_from_multi_aff(ma2
);
3316 map
= isl_map_range_product(map1
, map2
);
3317 space
= isl_space_range(isl_map_get_space(map
));
3318 space
= isl_space_domain(isl_space_unwrap(space
));
3319 ge
= isl_map_lex_ge(space
);
3320 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
3322 return isl_map_domain(map
);
3326 #define PW isl_pw_multi_aff
3328 #define EL isl_multi_aff
3330 #define EL_IS_ZERO is_empty
3334 #define IS_ZERO is_empty
3337 #undef DEFAULT_IS_ZERO
3338 #define DEFAULT_IS_ZERO 0
3343 #define NO_INVOLVES_DIMS
3344 #define NO_MOVE_DIMS
3345 #define NO_INSERT_DIMS
3349 #include <isl_pw_templ.c>
3352 #define UNION isl_union_pw_multi_aff
3354 #define PART isl_pw_multi_aff
3356 #define PARTS pw_multi_aff
3357 #define ALIGN_DOMAIN
3361 #include <isl_union_templ.c>
3363 /* Given a function "cmp" that returns the set of elements where
3364 * "ma1" is "better" than "ma2", return the intersection of this
3365 * set with "dom1" and "dom2".
3367 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
3368 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
3369 __isl_keep isl_multi_aff
*ma2
,
3370 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3371 __isl_take isl_multi_aff
*ma2
))
3377 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
3378 is_empty
= isl_set_plain_is_empty(common
);
3379 if (is_empty
>= 0 && is_empty
)
3382 return isl_set_free(common
);
3383 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
3384 better
= isl_set_intersect(common
, better
);
3389 /* Given a function "cmp" that returns the set of elements where
3390 * "ma1" is "better" than "ma2", return a piecewise multi affine
3391 * expression defined on the union of the definition domains
3392 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
3393 * "pma2" on each cell. If only one of the two input functions
3394 * is defined on a given cell, then it is considered the best.
3396 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
3397 __isl_take isl_pw_multi_aff
*pma1
,
3398 __isl_take isl_pw_multi_aff
*pma2
,
3399 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
3400 __isl_take isl_multi_aff
*ma2
))
3403 isl_pw_multi_aff
*res
= NULL
;
3405 isl_set
*set
= NULL
;
3410 ctx
= isl_space_get_ctx(pma1
->dim
);
3411 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
3412 isl_die(ctx
, isl_error_invalid
,
3413 "arguments should live in the same space", goto error
);
3415 if (isl_pw_multi_aff_is_empty(pma1
)) {
3416 isl_pw_multi_aff_free(pma1
);
3420 if (isl_pw_multi_aff_is_empty(pma2
)) {
3421 isl_pw_multi_aff_free(pma2
);
3425 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
3426 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
3428 for (i
= 0; i
< pma1
->n
; ++i
) {
3429 set
= isl_set_copy(pma1
->p
[i
].set
);
3430 for (j
= 0; j
< pma2
->n
; ++j
) {
3434 better
= shared_and_better(pma2
->p
[j
].set
,
3435 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
3436 pma1
->p
[i
].maff
, cmp
);
3437 is_empty
= isl_set_plain_is_empty(better
);
3438 if (is_empty
< 0 || is_empty
) {
3439 isl_set_free(better
);
3444 set
= isl_set_subtract(set
, isl_set_copy(better
));
3446 res
= isl_pw_multi_aff_add_piece(res
, better
,
3447 isl_multi_aff_copy(pma2
->p
[j
].maff
));
3449 res
= isl_pw_multi_aff_add_piece(res
, set
,
3450 isl_multi_aff_copy(pma1
->p
[i
].maff
));
3453 for (j
= 0; j
< pma2
->n
; ++j
) {
3454 set
= isl_set_copy(pma2
->p
[j
].set
);
3455 for (i
= 0; i
< pma1
->n
; ++i
)
3456 set
= isl_set_subtract(set
,
3457 isl_set_copy(pma1
->p
[i
].set
));
3458 res
= isl_pw_multi_aff_add_piece(res
, set
,
3459 isl_multi_aff_copy(pma2
->p
[j
].maff
));
3462 isl_pw_multi_aff_free(pma1
);
3463 isl_pw_multi_aff_free(pma2
);
3467 isl_pw_multi_aff_free(pma1
);
3468 isl_pw_multi_aff_free(pma2
);
3470 return isl_pw_multi_aff_free(res
);
3473 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
3474 __isl_take isl_pw_multi_aff
*pma1
,
3475 __isl_take isl_pw_multi_aff
*pma2
)
3477 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
3480 /* Given two piecewise multi affine expressions, return a piecewise
3481 * multi-affine expression defined on the union of the definition domains
3482 * of the inputs that is equal to the lexicographic maximum of the two
3483 * inputs on each cell. If only one of the two inputs is defined on
3484 * a given cell, then it is considered to be the maximum.
3486 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
3487 __isl_take isl_pw_multi_aff
*pma1
,
3488 __isl_take isl_pw_multi_aff
*pma2
)
3490 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3491 &pw_multi_aff_union_lexmax
);
3494 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
3495 __isl_take isl_pw_multi_aff
*pma1
,
3496 __isl_take isl_pw_multi_aff
*pma2
)
3498 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
3501 /* Given two piecewise multi affine expressions, return a piecewise
3502 * multi-affine expression defined on the union of the definition domains
3503 * of the inputs that is equal to the lexicographic minimum of the two
3504 * inputs on each cell. If only one of the two inputs is defined on
3505 * a given cell, then it is considered to be the minimum.
3507 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
3508 __isl_take isl_pw_multi_aff
*pma1
,
3509 __isl_take isl_pw_multi_aff
*pma2
)
3511 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3512 &pw_multi_aff_union_lexmin
);
3515 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
3516 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3518 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
3519 &isl_multi_aff_add
);
3522 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
3523 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3525 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3529 static __isl_give isl_pw_multi_aff
*pw_multi_aff_sub(
3530 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3532 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
3533 &isl_multi_aff_sub
);
3536 /* Subtract "pma2" from "pma1" and return the result.
3538 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_sub(
3539 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3541 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3545 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
3546 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3548 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
3551 /* Given two piecewise multi-affine expressions A -> B and C -> D,
3552 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
3554 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
3555 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3559 isl_pw_multi_aff
*res
;
3564 n
= pma1
->n
* pma2
->n
;
3565 space
= isl_space_product(isl_space_copy(pma1
->dim
),
3566 isl_space_copy(pma2
->dim
));
3567 res
= isl_pw_multi_aff_alloc_size(space
, n
);
3569 for (i
= 0; i
< pma1
->n
; ++i
) {
3570 for (j
= 0; j
< pma2
->n
; ++j
) {
3574 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
3575 isl_set_copy(pma2
->p
[j
].set
));
3576 ma
= isl_multi_aff_product(
3577 isl_multi_aff_copy(pma1
->p
[i
].maff
),
3578 isl_multi_aff_copy(pma2
->p
[i
].maff
));
3579 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
3583 isl_pw_multi_aff_free(pma1
);
3584 isl_pw_multi_aff_free(pma2
);
3587 isl_pw_multi_aff_free(pma1
);
3588 isl_pw_multi_aff_free(pma2
);
3592 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
3593 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3595 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3596 &pw_multi_aff_product
);
3599 /* Construct a map mapping the domain of the piecewise multi-affine expression
3600 * to its range, with each dimension in the range equated to the
3601 * corresponding affine expression on its cell.
3603 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3611 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
3613 for (i
= 0; i
< pma
->n
; ++i
) {
3614 isl_multi_aff
*maff
;
3615 isl_basic_map
*bmap
;
3618 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
3619 bmap
= isl_basic_map_from_multi_aff(maff
);
3620 map_i
= isl_map_from_basic_map(bmap
);
3621 map_i
= isl_map_intersect_domain(map_i
,
3622 isl_set_copy(pma
->p
[i
].set
));
3623 map
= isl_map_union_disjoint(map
, map_i
);
3626 isl_pw_multi_aff_free(pma
);
3630 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3635 if (!isl_space_is_set(pma
->dim
))
3636 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
3637 "isl_pw_multi_aff cannot be converted into an isl_set",
3638 return isl_pw_multi_aff_free(pma
));
3640 return isl_map_from_pw_multi_aff(pma
);
3643 /* Given a basic map with a single output dimension that is defined
3644 * in terms of the parameters and input dimensions using an equality,
3645 * extract an isl_aff that expresses the output dimension in terms
3646 * of the parameters and input dimensions.
3648 * Since some applications expect the result of isl_pw_multi_aff_from_map
3649 * to only contain integer affine expressions, we compute the floor
3650 * of the expression before returning.
3652 * This function shares some similarities with
3653 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
3655 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
3656 __isl_take isl_basic_map
*bmap
)
3661 isl_local_space
*ls
;
3666 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
3667 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3668 "basic map should have a single output dimension",
3670 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
3671 total
= isl_basic_map_total_dim(bmap
);
3672 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
3673 if (isl_int_is_zero(bmap
->eq
[i
][offset
]))
3675 if (isl_seq_first_non_zero(bmap
->eq
[i
] + offset
+ 1,
3676 1 + total
- (offset
+ 1)) != -1)
3680 if (i
>= bmap
->n_eq
)
3681 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3682 "unable to find suitable equality", goto error
);
3683 ls
= isl_basic_map_get_local_space(bmap
);
3684 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
3687 if (isl_int_is_neg(bmap
->eq
[i
][offset
]))
3688 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3690 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3691 isl_seq_clr(aff
->v
->el
+ 1 + offset
, aff
->v
->size
- (1 + offset
));
3692 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[i
][offset
]);
3693 isl_basic_map_free(bmap
);
3695 aff
= isl_aff_remove_unused_divs(aff
);
3696 aff
= isl_aff_floor(aff
);
3699 isl_basic_map_free(bmap
);
3703 /* Given a basic map where each output dimension is defined
3704 * in terms of the parameters and input dimensions using an equality,
3705 * extract an isl_multi_aff that expresses the output dimensions in terms
3706 * of the parameters and input dimensions.
3708 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
3709 __isl_take isl_basic_map
*bmap
)
3718 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
3719 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
3721 for (i
= 0; i
< n_out
; ++i
) {
3722 isl_basic_map
*bmap_i
;
3725 bmap_i
= isl_basic_map_copy(bmap
);
3726 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
3727 i
+ 1, n_out
- (1 + i
));
3728 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
3729 aff
= extract_isl_aff_from_basic_map(bmap_i
);
3730 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3733 isl_basic_map_free(bmap
);
3738 /* Create an isl_pw_multi_aff that is equivalent to
3739 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
3740 * The given basic map is such that each output dimension is defined
3741 * in terms of the parameters and input dimensions using an equality.
3743 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
3744 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
3748 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
3749 return isl_pw_multi_aff_alloc(domain
, ma
);
3752 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3753 * This obviously only works if the input "map" is single-valued.
3754 * If so, we compute the lexicographic minimum of the image in the form
3755 * of an isl_pw_multi_aff. Since the image is unique, it is equal
3756 * to its lexicographic minimum.
3757 * If the input is not single-valued, we produce an error.
3759 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
3760 __isl_take isl_map
*map
)
3764 isl_pw_multi_aff
*pma
;
3766 sv
= isl_map_is_single_valued(map
);
3770 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
3771 "map is not single-valued", goto error
);
3772 map
= isl_map_make_disjoint(map
);
3776 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
3778 for (i
= 0; i
< map
->n
; ++i
) {
3779 isl_pw_multi_aff
*pma_i
;
3780 isl_basic_map
*bmap
;
3781 bmap
= isl_basic_map_copy(map
->p
[i
]);
3782 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
3783 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
3793 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3794 * taking into account that the output dimension at position "d"
3795 * can be represented as
3797 * x = floor((e(...) + c1) / m)
3799 * given that constraint "i" is of the form
3801 * e(...) + c1 - m x >= 0
3804 * Let "map" be of the form
3808 * We construct a mapping
3810 * A -> [A -> x = floor(...)]
3812 * apply that to the map, obtaining
3814 * [A -> x = floor(...)] -> B
3816 * and equate dimension "d" to x.
3817 * We then compute a isl_pw_multi_aff representation of the resulting map
3818 * and plug in the mapping above.
3820 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
3821 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
3825 isl_local_space
*ls
;
3833 isl_pw_multi_aff
*pma
;
3836 is_set
= isl_map_is_set(map
);
3838 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3839 ctx
= isl_map_get_ctx(map
);
3840 space
= isl_space_domain(isl_map_get_space(map
));
3841 n_in
= isl_space_dim(space
, isl_dim_set
);
3842 n
= isl_space_dim(space
, isl_dim_all
);
3844 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
3846 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
3847 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
3849 isl_basic_map_free(hull
);
3851 ls
= isl_local_space_from_space(isl_space_copy(space
));
3852 aff
= isl_aff_alloc_vec(ls
, v
);
3853 aff
= isl_aff_floor(aff
);
3855 isl_space_free(space
);
3856 ma
= isl_multi_aff_from_aff(aff
);
3858 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
3859 ma
= isl_multi_aff_range_product(ma
,
3860 isl_multi_aff_from_aff(aff
));
3863 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
3864 map
= isl_map_apply_domain(map
, insert
);
3865 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
3866 pma
= isl_pw_multi_aff_from_map(map
);
3867 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
3872 /* Is constraint "c" of the form
3874 * e(...) + c1 - m x >= 0
3878 * -e(...) + c2 + m x >= 0
3880 * where m > 1 and e only depends on parameters and input dimemnsions?
3882 * "offset" is the offset of the output dimensions
3883 * "pos" is the position of output dimension x.
3885 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
3887 if (isl_int_is_zero(c
[offset
+ d
]))
3889 if (isl_int_is_one(c
[offset
+ d
]))
3891 if (isl_int_is_negone(c
[offset
+ d
]))
3893 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
3895 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
3896 total
- (offset
+ d
+ 1)) != -1)
3901 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3903 * As a special case, we first check if there is any pair of constraints,
3904 * shared by all the basic maps in "map" that force a given dimension
3905 * to be equal to the floor of some affine combination of the input dimensions.
3907 * In particular, if we can find two constraints
3909 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
3913 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
3915 * where m > 1 and e only depends on parameters and input dimemnsions,
3918 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
3920 * then we know that we can take
3922 * x = floor((e(...) + c1) / m)
3924 * without having to perform any computation.
3926 * Note that we know that
3930 * If c1 + c2 were 0, then we would have detected an equality during
3931 * simplification. If c1 + c2 were negative, then we would have detected
3934 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
3935 __isl_take isl_map
*map
)
3941 isl_basic_map
*hull
;
3943 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
3948 dim
= isl_map_dim(map
, isl_dim_out
);
3949 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3950 total
= 1 + isl_basic_map_total_dim(hull
);
3952 for (d
= 0; d
< dim
; ++d
) {
3953 for (i
= 0; i
< n
; ++i
) {
3954 if (!is_potential_div_constraint(hull
->ineq
[i
],
3957 for (j
= i
+ 1; j
< n
; ++j
) {
3958 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
3959 hull
->ineq
[j
] + 1, total
- 1))
3961 isl_int_add(sum
, hull
->ineq
[i
][0],
3963 if (isl_int_abs_lt(sum
,
3964 hull
->ineq
[i
][offset
+ d
]))
3971 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
3973 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
3977 isl_basic_map_free(hull
);
3978 return pw_multi_aff_from_map_base(map
);
3981 isl_basic_map_free(hull
);
3985 /* Given an affine expression
3987 * [A -> B] -> f(A,B)
3989 * construct an isl_multi_aff
3993 * such that dimension "d" in B' is set to "aff" and the remaining
3994 * dimensions are set equal to the corresponding dimensions in B.
3995 * "n_in" is the dimension of the space A.
3996 * "n_out" is the dimension of the space B.
3998 * If "is_set" is set, then the affine expression is of the form
4002 * and we construct an isl_multi_aff
4006 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
4007 unsigned n_in
, unsigned n_out
, int is_set
)
4011 isl_space
*space
, *space2
;
4012 isl_local_space
*ls
;
4014 space
= isl_aff_get_domain_space(aff
);
4015 ls
= isl_local_space_from_space(isl_space_copy(space
));
4016 space2
= isl_space_copy(space
);
4018 space2
= isl_space_range(isl_space_unwrap(space2
));
4019 space
= isl_space_map_from_domain_and_range(space
, space2
);
4020 ma
= isl_multi_aff_alloc(space
);
4021 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
4023 for (i
= 0; i
< n_out
; ++i
) {
4026 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
4027 isl_dim_set
, n_in
+ i
);
4028 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
4031 isl_local_space_free(ls
);
4036 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4037 * taking into account that the dimension at position "d" can be written as
4039 * x = m a + f(..) (1)
4041 * where m is equal to "gcd".
4042 * "i" is the index of the equality in "hull" that defines f(..).
4043 * In particular, the equality is of the form
4045 * f(..) - x + m g(existentials) = 0
4049 * -f(..) + x + m g(existentials) = 0
4051 * We basically plug (1) into "map", resulting in a map with "a"
4052 * in the range instead of "x". The corresponding isl_pw_multi_aff
4053 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
4055 * Specifically, given the input map
4059 * We first wrap it into a set
4063 * and define (1) on top of the corresponding space, resulting in "aff".
4064 * We use this to create an isl_multi_aff that maps the output position "d"
4065 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
4066 * We plug this into the wrapped map, unwrap the result and compute the
4067 * corresponding isl_pw_multi_aff.
4068 * The result is an expression
4076 * so that we can plug that into "aff", after extending the latter to
4082 * If "map" is actually a set, then there is no "A" space, meaning
4083 * that we do not need to perform any wrapping, and that the result
4084 * of the recursive call is of the form
4088 * which is plugged into a mapping of the form
4092 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
4093 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
4098 isl_local_space
*ls
;
4101 isl_pw_multi_aff
*pma
, *id
;
4107 is_set
= isl_map_is_set(map
);
4109 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
4110 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4111 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4116 set
= isl_map_wrap(map
);
4117 space
= isl_space_map_from_set(isl_set_get_space(set
));
4118 ma
= isl_multi_aff_identity(space
);
4119 ls
= isl_local_space_from_space(isl_set_get_space(set
));
4120 aff
= isl_aff_alloc(ls
);
4122 isl_int_set_si(aff
->v
->el
[0], 1);
4123 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
4124 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
4127 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
4129 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
4131 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
4132 set
= isl_set_preimage_multi_aff(set
, ma
);
4134 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
4139 map
= isl_set_unwrap(set
);
4140 pma
= isl_pw_multi_aff_from_map(set
);
4143 space
= isl_pw_multi_aff_get_domain_space(pma
);
4144 space
= isl_space_map_from_set(space
);
4145 id
= isl_pw_multi_aff_identity(space
);
4146 pma
= isl_pw_multi_aff_range_product(id
, pma
);
4148 id
= isl_pw_multi_aff_from_multi_aff(ma
);
4149 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
4151 isl_basic_map_free(hull
);
4155 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4157 * As a special case, we first check if all output dimensions are uniquely
4158 * defined in terms of the parameters and input dimensions over the entire
4159 * domain. If so, we extract the desired isl_pw_multi_aff directly
4160 * from the affine hull of "map" and its domain.
4162 * Otherwise, we check if any of the output dimensions is "strided".
4163 * That is, we check if can be written as
4167 * with m greater than 1, a some combination of existentiall quantified
4168 * variables and f and expression in the parameters and input dimensions.
4169 * If so, we remove the stride in pw_multi_aff_from_map_stride.
4171 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
4174 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
4178 isl_basic_map
*hull
;
4188 hull
= isl_map_affine_hull(isl_map_copy(map
));
4189 sv
= isl_basic_map_plain_is_single_valued(hull
);
4191 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
4193 hull
= isl_basic_map_free(hull
);
4197 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
4198 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
4201 isl_basic_map_free(hull
);
4202 return pw_multi_aff_from_map_check_div(map
);
4207 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
4208 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
4210 for (i
= 0; i
< n_out
; ++i
) {
4211 for (j
= 0; j
< hull
->n_eq
; ++j
) {
4212 isl_int
*eq
= hull
->eq
[j
];
4213 isl_pw_multi_aff
*res
;
4215 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
4216 !isl_int_is_negone(eq
[o_out
+ i
]))
4218 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
4220 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
4221 n_out
- (i
+ 1)) != -1)
4223 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
4224 if (isl_int_is_zero(gcd
))
4226 if (isl_int_is_one(gcd
))
4229 res
= pw_multi_aff_from_map_stride(map
, hull
,
4237 isl_basic_map_free(hull
);
4238 return pw_multi_aff_from_map_check_div(map
);
4244 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
4246 return isl_pw_multi_aff_from_map(set
);
4249 /* Convert "map" into an isl_pw_multi_aff (if possible) and
4252 static int pw_multi_aff_from_map(__isl_take isl_map
*map
, void *user
)
4254 isl_union_pw_multi_aff
**upma
= user
;
4255 isl_pw_multi_aff
*pma
;
4257 pma
= isl_pw_multi_aff_from_map(map
);
4258 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4260 return *upma
? 0 : -1;
4263 /* Try and create an isl_union_pw_multi_aff that is equivalent
4264 * to the given isl_union_map.
4265 * The isl_union_map is required to be single-valued in each space.
4266 * Otherwise, an error is produced.
4268 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_map(
4269 __isl_take isl_union_map
*umap
)
4272 isl_union_pw_multi_aff
*upma
;
4274 space
= isl_union_map_get_space(umap
);
4275 upma
= isl_union_pw_multi_aff_empty(space
);
4276 if (isl_union_map_foreach_map(umap
, &pw_multi_aff_from_map
, &upma
) < 0)
4277 upma
= isl_union_pw_multi_aff_free(upma
);
4278 isl_union_map_free(umap
);
4283 /* Try and create an isl_union_pw_multi_aff that is equivalent
4284 * to the given isl_union_set.
4285 * The isl_union_set is required to be a singleton in each space.
4286 * Otherwise, an error is produced.
4288 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_union_set(
4289 __isl_take isl_union_set
*uset
)
4291 return isl_union_pw_multi_aff_from_union_map(uset
);
4294 /* Return the piecewise affine expression "set ? 1 : 0".
4296 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
4299 isl_space
*space
= isl_set_get_space(set
);
4300 isl_local_space
*ls
= isl_local_space_from_space(space
);
4301 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
4302 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
4304 one
= isl_aff_add_constant_si(one
, 1);
4305 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
4306 set
= isl_set_complement(set
);
4307 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
4312 /* Plug in "subs" for dimension "type", "pos" of "aff".
4314 * Let i be the dimension to replace and let "subs" be of the form
4318 * and "aff" of the form
4324 * (a f + d g')/(m d)
4326 * where g' is the result of plugging in "subs" in each of the integer
4329 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
4330 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
4335 aff
= isl_aff_cow(aff
);
4337 return isl_aff_free(aff
);
4339 ctx
= isl_aff_get_ctx(aff
);
4340 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
4341 isl_die(ctx
, isl_error_invalid
,
4342 "spaces don't match", return isl_aff_free(aff
));
4343 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
4344 isl_die(ctx
, isl_error_unsupported
,
4345 "cannot handle divs yet", return isl_aff_free(aff
));
4347 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
4349 return isl_aff_free(aff
);
4351 aff
->v
= isl_vec_cow(aff
->v
);
4353 return isl_aff_free(aff
);
4355 pos
+= isl_local_space_offset(aff
->ls
, type
);
4358 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
4359 aff
->v
->size
, subs
->v
->size
, v
);
4365 /* Plug in "subs" for dimension "type", "pos" in each of the affine
4366 * expressions in "maff".
4368 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
4369 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
4370 __isl_keep isl_aff
*subs
)
4374 maff
= isl_multi_aff_cow(maff
);
4376 return isl_multi_aff_free(maff
);
4378 if (type
== isl_dim_in
)
4381 for (i
= 0; i
< maff
->n
; ++i
) {
4382 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
4384 return isl_multi_aff_free(maff
);
4390 /* Plug in "subs" for dimension "type", "pos" of "pma".
4392 * pma is of the form
4396 * while subs is of the form
4398 * v' = B_j(v) -> S_j
4400 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
4401 * has a contribution in the result, in particular
4403 * C_ij(S_j) -> M_i(S_j)
4405 * Note that plugging in S_j in C_ij may also result in an empty set
4406 * and this contribution should simply be discarded.
4408 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
4409 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
4410 __isl_keep isl_pw_aff
*subs
)
4413 isl_pw_multi_aff
*res
;
4416 return isl_pw_multi_aff_free(pma
);
4418 n
= pma
->n
* subs
->n
;
4419 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
4421 for (i
= 0; i
< pma
->n
; ++i
) {
4422 for (j
= 0; j
< subs
->n
; ++j
) {
4424 isl_multi_aff
*res_ij
;
4427 common
= isl_set_intersect(
4428 isl_set_copy(pma
->p
[i
].set
),
4429 isl_set_copy(subs
->p
[j
].set
));
4430 common
= isl_set_substitute(common
,
4431 type
, pos
, subs
->p
[j
].aff
);
4432 empty
= isl_set_plain_is_empty(common
);
4433 if (empty
< 0 || empty
) {
4434 isl_set_free(common
);
4440 res_ij
= isl_multi_aff_substitute(
4441 isl_multi_aff_copy(pma
->p
[i
].maff
),
4442 type
, pos
, subs
->p
[j
].aff
);
4444 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
4448 isl_pw_multi_aff_free(pma
);
4451 isl_pw_multi_aff_free(pma
);
4452 isl_pw_multi_aff_free(res
);
4456 /* Compute the preimage of a range of dimensions in the affine expression "src"
4457 * under "ma" and put the result in "dst". The number of dimensions in "src"
4458 * that precede the range is given by "n_before". The number of dimensions
4459 * in the range is given by the number of output dimensions of "ma".
4460 * The number of dimensions that follow the range is given by "n_after".
4461 * If "has_denom" is set (to one),
4462 * then "src" and "dst" have an extra initial denominator.
4463 * "n_div_ma" is the number of existentials in "ma"
4464 * "n_div_bset" is the number of existentials in "src"
4465 * The resulting "dst" (which is assumed to have been allocated by
4466 * the caller) contains coefficients for both sets of existentials,
4467 * first those in "ma" and then those in "src".
4468 * f, c1, c2 and g are temporary objects that have been initialized
4471 * Let src represent the expression
4473 * (a(p) + f_u u + b v + f_w w + c(divs))/d
4475 * and let ma represent the expressions
4477 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
4479 * We start out with the following expression for dst:
4481 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d
4483 * with the multiplication factor f initially equal to 1
4484 * and f \sum_i b_i v_i kept separately.
4485 * For each x_i that we substitute, we multiply the numerator
4486 * (and denominator) of dst by c_1 = m_i and add the numerator
4487 * of the x_i expression multiplied by c_2 = f b_i,
4488 * after removing the common factors of c_1 and c_2.
4489 * The multiplication factor f also needs to be multiplied by c_1
4490 * for the next x_j, j > i.
4492 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
4493 __isl_keep isl_multi_aff
*ma
, int n_before
, int n_after
,
4494 int n_div_ma
, int n_div_bmap
,
4495 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
4498 int n_param
, n_in
, n_out
;
4501 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
4502 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
4503 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
4505 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
+ n_before
);
4506 o_dst
= o_src
= has_denom
+ 1 + n_param
+ n_before
;
4507 isl_seq_clr(dst
+ o_dst
, n_in
);
4510 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_after
);
4513 isl_seq_clr(dst
+ o_dst
, n_div_ma
);
4515 isl_seq_cpy(dst
+ o_dst
, src
+ o_src
, n_div_bmap
);
4517 isl_int_set_si(f
, 1);
4519 for (i
= 0; i
< n_out
; ++i
) {
4520 int offset
= has_denom
+ 1 + n_param
+ n_before
+ i
;
4522 if (isl_int_is_zero(src
[offset
]))
4524 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
4525 isl_int_mul(c2
, f
, src
[offset
]);
4526 isl_int_gcd(g
, c1
, c2
);
4527 isl_int_divexact(c1
, c1
, g
);
4528 isl_int_divexact(c2
, c2
, g
);
4530 isl_int_mul(f
, f
, c1
);
4533 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
4534 c2
, ma
->p
[i
]->v
->el
+ o_src
, 1 + n_param
);
4535 o_dst
+= 1 + n_param
;
4536 o_src
+= 1 + n_param
;
4537 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_before
);
4539 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
4540 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_in
);
4543 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_after
);
4545 isl_seq_combine(dst
+ o_dst
, c1
, dst
+ o_dst
,
4546 c2
, ma
->p
[i
]->v
->el
+ o_src
, n_div_ma
);
4549 isl_seq_scale(dst
+ o_dst
, dst
+ o_dst
, c1
, n_div_bmap
);
4551 isl_int_mul(dst
[0], dst
[0], c1
);
4555 /* Compute the pullback of "aff" by the function represented by "ma".
4556 * In other words, plug in "ma" in "aff". The result is an affine expression
4557 * defined over the domain space of "ma".
4559 * If "aff" is represented by
4561 * (a(p) + b x + c(divs))/d
4563 * and ma is represented by
4565 * x = D(p) + F(y) + G(divs')
4567 * then the result is
4569 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
4571 * The divs in the local space of the input are similarly adjusted
4572 * through a call to isl_local_space_preimage_multi_aff.
4574 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
4575 __isl_take isl_multi_aff
*ma
)
4577 isl_aff
*res
= NULL
;
4578 isl_local_space
*ls
;
4579 int n_div_aff
, n_div_ma
;
4580 isl_int f
, c1
, c2
, g
;
4582 ma
= isl_multi_aff_align_divs(ma
);
4586 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
4587 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
4589 ls
= isl_aff_get_domain_local_space(aff
);
4590 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
4591 res
= isl_aff_alloc(ls
);
4600 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, 0, 0, n_div_ma
, n_div_aff
,
4609 isl_multi_aff_free(ma
);
4610 res
= isl_aff_normalize(res
);
4614 isl_multi_aff_free(ma
);
4619 /* Compute the pullback of "ma1" by the function represented by "ma2".
4620 * In other words, plug in "ma2" in "ma1".
4622 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
4623 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
4626 isl_space
*space
= NULL
;
4628 ma2
= isl_multi_aff_align_divs(ma2
);
4629 ma1
= isl_multi_aff_cow(ma1
);
4633 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
4634 isl_multi_aff_get_space(ma1
));
4636 for (i
= 0; i
< ma1
->n
; ++i
) {
4637 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
4638 isl_multi_aff_copy(ma2
));
4643 ma1
= isl_multi_aff_reset_space(ma1
, space
);
4644 isl_multi_aff_free(ma2
);
4647 isl_space_free(space
);
4648 isl_multi_aff_free(ma2
);
4649 isl_multi_aff_free(ma1
);
4653 /* Extend the local space of "dst" to include the divs
4654 * in the local space of "src".
4656 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
4657 __isl_keep isl_aff
*src
)
4665 return isl_aff_free(dst
);
4667 ctx
= isl_aff_get_ctx(src
);
4668 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
4669 isl_die(ctx
, isl_error_invalid
,
4670 "spaces don't match", goto error
);
4672 if (src
->ls
->div
->n_row
== 0)
4675 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
4676 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
4680 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
4681 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
4689 return isl_aff_free(dst
);
4692 /* Adjust the local spaces of the affine expressions in "maff"
4693 * such that they all have the save divs.
4695 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
4696 __isl_take isl_multi_aff
*maff
)
4704 maff
= isl_multi_aff_cow(maff
);
4708 for (i
= 1; i
< maff
->n
; ++i
)
4709 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
4710 for (i
= 1; i
< maff
->n
; ++i
) {
4711 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
4713 return isl_multi_aff_free(maff
);
4719 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
4721 aff
= isl_aff_cow(aff
);
4725 aff
->ls
= isl_local_space_lift(aff
->ls
);
4727 return isl_aff_free(aff
);
4732 /* Lift "maff" to a space with extra dimensions such that the result
4733 * has no more existentially quantified variables.
4734 * If "ls" is not NULL, then *ls is assigned the local space that lies
4735 * at the basis of the lifting applied to "maff".
4737 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
4738 __isl_give isl_local_space
**ls
)
4752 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
4753 *ls
= isl_local_space_from_space(space
);
4755 return isl_multi_aff_free(maff
);
4760 maff
= isl_multi_aff_cow(maff
);
4761 maff
= isl_multi_aff_align_divs(maff
);
4765 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
4766 space
= isl_multi_aff_get_space(maff
);
4767 space
= isl_space_lift(isl_space_domain(space
), n_div
);
4768 space
= isl_space_extend_domain_with_range(space
,
4769 isl_multi_aff_get_space(maff
));
4771 return isl_multi_aff_free(maff
);
4772 isl_space_free(maff
->space
);
4773 maff
->space
= space
;
4776 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
4778 return isl_multi_aff_free(maff
);
4781 for (i
= 0; i
< maff
->n
; ++i
) {
4782 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
4790 isl_local_space_free(*ls
);
4791 return isl_multi_aff_free(maff
);
4795 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
4797 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
4798 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
4808 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
4809 if (pos
< 0 || pos
>= n_out
)
4810 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4811 "index out of bounds", return NULL
);
4813 space
= isl_pw_multi_aff_get_space(pma
);
4814 space
= isl_space_drop_dims(space
, isl_dim_out
,
4815 pos
+ 1, n_out
- pos
- 1);
4816 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
4818 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
4819 for (i
= 0; i
< pma
->n
; ++i
) {
4821 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
4822 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
4828 /* Return an isl_pw_multi_aff with the given "set" as domain and
4829 * an unnamed zero-dimensional range.
4831 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
4832 __isl_take isl_set
*set
)
4837 space
= isl_set_get_space(set
);
4838 space
= isl_space_from_domain(space
);
4839 ma
= isl_multi_aff_zero(space
);
4840 return isl_pw_multi_aff_alloc(set
, ma
);
4843 /* Add an isl_pw_multi_aff with the given "set" as domain and
4844 * an unnamed zero-dimensional range to *user.
4846 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
4848 isl_union_pw_multi_aff
**upma
= user
;
4849 isl_pw_multi_aff
*pma
;
4851 pma
= isl_pw_multi_aff_from_domain(set
);
4852 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4857 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
4858 * an unnamed zero-dimensional range.
4860 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
4861 __isl_take isl_union_set
*uset
)
4864 isl_union_pw_multi_aff
*upma
;
4869 space
= isl_union_set_get_space(uset
);
4870 upma
= isl_union_pw_multi_aff_empty(space
);
4872 if (isl_union_set_foreach_set(uset
,
4873 &add_pw_multi_aff_from_domain
, &upma
) < 0)
4876 isl_union_set_free(uset
);
4879 isl_union_set_free(uset
);
4880 isl_union_pw_multi_aff_free(upma
);
4884 /* Convert "pma" to an isl_map and add it to *umap.
4886 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
4888 isl_union_map
**umap
= user
;
4891 map
= isl_map_from_pw_multi_aff(pma
);
4892 *umap
= isl_union_map_add_map(*umap
, map
);
4897 /* Construct a union map mapping the domain of the union
4898 * piecewise multi-affine expression to its range, with each dimension
4899 * in the range equated to the corresponding affine expression on its cell.
4901 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
4902 __isl_take isl_union_pw_multi_aff
*upma
)
4905 isl_union_map
*umap
;
4910 space
= isl_union_pw_multi_aff_get_space(upma
);
4911 umap
= isl_union_map_empty(space
);
4913 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4914 &map_from_pw_multi_aff
, &umap
) < 0)
4917 isl_union_pw_multi_aff_free(upma
);
4920 isl_union_pw_multi_aff_free(upma
);
4921 isl_union_map_free(umap
);
4925 /* Local data for bin_entry and the callback "fn".
4927 struct isl_union_pw_multi_aff_bin_data
{
4928 isl_union_pw_multi_aff
*upma2
;
4929 isl_union_pw_multi_aff
*res
;
4930 isl_pw_multi_aff
*pma
;
4931 int (*fn
)(void **entry
, void *user
);
4934 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
4935 * and call data->fn for each isl_pw_multi_aff in data->upma2.
4937 static int bin_entry(void **entry
, void *user
)
4939 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4940 isl_pw_multi_aff
*pma
= *entry
;
4943 if (isl_hash_table_foreach(data
->upma2
->dim
->ctx
, &data
->upma2
->table
,
4944 data
->fn
, data
) < 0)
4950 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
4951 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
4952 * passed as user field) and the isl_pw_multi_aff from upma2 is available
4953 * as *entry. The callback should adjust data->res if desired.
4955 static __isl_give isl_union_pw_multi_aff
*bin_op(
4956 __isl_take isl_union_pw_multi_aff
*upma1
,
4957 __isl_take isl_union_pw_multi_aff
*upma2
,
4958 int (*fn
)(void **entry
, void *user
))
4961 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
4963 space
= isl_union_pw_multi_aff_get_space(upma2
);
4964 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
4965 space
= isl_union_pw_multi_aff_get_space(upma1
);
4966 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
4968 if (!upma1
|| !upma2
)
4972 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->dim
),
4974 if (isl_hash_table_foreach(upma1
->dim
->ctx
, &upma1
->table
,
4975 &bin_entry
, &data
) < 0)
4978 isl_union_pw_multi_aff_free(upma1
);
4979 isl_union_pw_multi_aff_free(upma2
);
4982 isl_union_pw_multi_aff_free(upma1
);
4983 isl_union_pw_multi_aff_free(upma2
);
4984 isl_union_pw_multi_aff_free(data
.res
);
4988 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4989 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4991 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
4992 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4996 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4997 isl_pw_multi_aff_get_space(pma2
));
4998 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4999 &isl_multi_aff_range_product
);
5002 /* Given two isl_pw_multi_affs A -> B and C -> D,
5003 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5005 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
5006 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5008 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5009 &pw_multi_aff_range_product
);
5012 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5013 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5015 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
5016 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5020 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
5021 isl_pw_multi_aff_get_space(pma2
));
5022 space
= isl_space_flatten_range(space
);
5023 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
5024 &isl_multi_aff_flat_range_product
);
5027 /* Given two isl_pw_multi_affs A -> B and C -> D,
5028 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5030 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
5031 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
5033 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
5034 &pw_multi_aff_flat_range_product
);
5037 /* If data->pma and *entry have the same domain space, then compute
5038 * their flat range product and the result to data->res.
5040 static int flat_range_product_entry(void **entry
, void *user
)
5042 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
5043 isl_pw_multi_aff
*pma2
= *entry
;
5045 if (!isl_space_tuple_match(data
->pma
->dim
, isl_dim_in
,
5046 pma2
->dim
, isl_dim_in
))
5049 pma2
= isl_pw_multi_aff_flat_range_product(
5050 isl_pw_multi_aff_copy(data
->pma
),
5051 isl_pw_multi_aff_copy(pma2
));
5053 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
5058 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
5059 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
5061 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
5062 __isl_take isl_union_pw_multi_aff
*upma1
,
5063 __isl_take isl_union_pw_multi_aff
*upma2
)
5065 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
5068 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5069 * The parameters are assumed to have been aligned.
5071 * The implementation essentially performs an isl_pw_*_on_shared_domain,
5072 * except that it works on two different isl_pw_* types.
5074 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
5075 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5076 __isl_take isl_pw_aff
*pa
)
5079 isl_pw_multi_aff
*res
= NULL
;
5084 if (!isl_space_tuple_match(pma
->dim
, isl_dim_in
, pa
->dim
, isl_dim_in
))
5085 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5086 "domains don't match", goto error
);
5087 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
5088 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5089 "index out of bounds", goto error
);
5092 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
5094 for (i
= 0; i
< pma
->n
; ++i
) {
5095 for (j
= 0; j
< pa
->n
; ++j
) {
5097 isl_multi_aff
*res_ij
;
5100 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
5101 isl_set_copy(pa
->p
[j
].set
));
5102 empty
= isl_set_plain_is_empty(common
);
5103 if (empty
< 0 || empty
) {
5104 isl_set_free(common
);
5110 res_ij
= isl_multi_aff_set_aff(
5111 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
5112 isl_aff_copy(pa
->p
[j
].aff
));
5113 res_ij
= isl_multi_aff_gist(res_ij
,
5114 isl_set_copy(common
));
5116 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
5120 isl_pw_multi_aff_free(pma
);
5121 isl_pw_aff_free(pa
);
5124 isl_pw_multi_aff_free(pma
);
5125 isl_pw_aff_free(pa
);
5126 return isl_pw_multi_aff_free(res
);
5129 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5131 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
5132 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
5133 __isl_take isl_pw_aff
*pa
)
5137 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
5138 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5139 if (!isl_space_has_named_params(pma
->dim
) ||
5140 !isl_space_has_named_params(pa
->dim
))
5141 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5142 "unaligned unnamed parameters", goto error
);
5143 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
5144 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
5145 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
5147 isl_pw_multi_aff_free(pma
);
5148 isl_pw_aff_free(pa
);
5152 /* Check that the domain space of "pa" matches "space".
5154 * Return 0 on success and -1 on error.
5156 int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff
*pa
,
5157 __isl_keep isl_space
*space
)
5159 isl_space
*pa_space
;
5165 pa_space
= isl_pw_aff_get_space(pa
);
5167 match
= isl_space_match(space
, isl_dim_param
, pa_space
, isl_dim_param
);
5171 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5172 "parameters don't match", goto error
);
5173 match
= isl_space_tuple_match(space
, isl_dim_in
, pa_space
, isl_dim_in
);
5177 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
5178 "domains don't match", goto error
);
5179 isl_space_free(pa_space
);
5182 isl_space_free(pa_space
);
5189 #include <isl_multi_templ.c>
5191 /* Scale the elements of "pma" by the corresponding elements of "mv".
5193 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_scale_multi_val(
5194 __isl_take isl_pw_multi_aff
*pma
, __isl_take isl_multi_val
*mv
)
5198 pma
= isl_pw_multi_aff_cow(pma
);
5201 if (!isl_space_tuple_match(pma
->dim
, isl_dim_out
,
5202 mv
->space
, isl_dim_set
))
5203 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
5204 "spaces don't match", goto error
);
5205 if (!isl_space_match(pma
->dim
, isl_dim_param
,
5206 mv
->space
, isl_dim_param
)) {
5207 pma
= isl_pw_multi_aff_align_params(pma
,
5208 isl_multi_val_get_space(mv
));
5209 mv
= isl_multi_val_align_params(mv
,
5210 isl_pw_multi_aff_get_space(pma
));
5215 for (i
= 0; i
< pma
->n
; ++i
) {
5216 pma
->p
[i
].maff
= isl_multi_aff_scale_multi_val(pma
->p
[i
].maff
,
5217 isl_multi_val_copy(mv
));
5218 if (!pma
->p
[i
].maff
)
5222 isl_multi_val_free(mv
);
5225 isl_multi_val_free(mv
);
5226 isl_pw_multi_aff_free(pma
);
5230 /* Internal data structure for isl_union_pw_multi_aff_scale_multi_val.
5231 * mv contains the mv argument.
5232 * res collects the results.
5234 struct isl_union_pw_multi_aff_scale_multi_val_data
{
5236 isl_union_pw_multi_aff
*res
;
5239 /* This function is called for each entry of an isl_union_pw_multi_aff.
5240 * If the space of the entry matches that of data->mv,
5241 * then apply isl_pw_multi_aff_scale_multi_val and add the result
5244 static int union_pw_multi_aff_scale_multi_val_entry(void **entry
, void *user
)
5246 struct isl_union_pw_multi_aff_scale_multi_val_data
*data
= user
;
5247 isl_pw_multi_aff
*pma
= *entry
;
5251 if (!isl_space_tuple_match(pma
->dim
, isl_dim_out
,
5252 data
->mv
->space
, isl_dim_set
))
5255 pma
= isl_pw_multi_aff_copy(pma
);
5256 pma
= isl_pw_multi_aff_scale_multi_val(pma
,
5257 isl_multi_val_copy(data
->mv
));
5258 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma
);
5265 /* Scale the elements of "upma" by the corresponding elements of "mv",
5266 * for those entries that match the space of "mv".
5268 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_scale_multi_val(
5269 __isl_take isl_union_pw_multi_aff
*upma
, __isl_take isl_multi_val
*mv
)
5271 struct isl_union_pw_multi_aff_scale_multi_val_data data
;
5273 upma
= isl_union_pw_multi_aff_align_params(upma
,
5274 isl_multi_val_get_space(mv
));
5275 mv
= isl_multi_val_align_params(mv
,
5276 isl_union_pw_multi_aff_get_space(upma
));
5281 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma
->dim
),
5283 if (isl_hash_table_foreach(upma
->dim
->ctx
, &upma
->table
,
5284 &union_pw_multi_aff_scale_multi_val_entry
, &data
) < 0)
5287 isl_multi_val_free(mv
);
5288 isl_union_pw_multi_aff_free(upma
);
5291 isl_multi_val_free(mv
);
5292 isl_union_pw_multi_aff_free(upma
);