2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012 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_mat_private.h>
22 #include <isl_list_private.h>
23 #include <isl/constraint.h>
26 #include <isl_config.h>
28 __isl_give isl_aff
*isl_aff_alloc_vec(__isl_take isl_local_space
*ls
,
29 __isl_take isl_vec
*v
)
36 aff
= isl_calloc_type(v
->ctx
, struct isl_aff
);
46 isl_local_space_free(ls
);
51 __isl_give isl_aff
*isl_aff_alloc(__isl_take isl_local_space
*ls
)
60 ctx
= isl_local_space_get_ctx(ls
);
61 if (!isl_local_space_divs_known(ls
))
62 isl_die(ctx
, isl_error_invalid
, "local space has unknown divs",
64 if (!isl_local_space_is_set(ls
))
65 isl_die(ctx
, isl_error_invalid
,
66 "domain of affine expression should be a set",
69 total
= isl_local_space_dim(ls
, isl_dim_all
);
70 v
= isl_vec_alloc(ctx
, 1 + 1 + total
);
71 return isl_aff_alloc_vec(ls
, v
);
73 isl_local_space_free(ls
);
77 __isl_give isl_aff
*isl_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
81 aff
= isl_aff_alloc(ls
);
85 isl_int_set_si(aff
->v
->el
[0], 1);
86 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
91 /* Return a piecewise affine expression defined on the specified domain
92 * that is equal to zero.
94 __isl_give isl_pw_aff
*isl_pw_aff_zero_on_domain(__isl_take isl_local_space
*ls
)
96 return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls
));
99 /* Return an affine expression that is equal to the specified dimension
102 __isl_give isl_aff
*isl_aff_var_on_domain(__isl_take isl_local_space
*ls
,
103 enum isl_dim_type type
, unsigned pos
)
111 space
= isl_local_space_get_space(ls
);
114 if (isl_space_is_map(space
))
115 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
116 "expecting (parameter) set space", goto error
);
117 if (pos
>= isl_local_space_dim(ls
, type
))
118 isl_die(isl_space_get_ctx(space
), isl_error_invalid
,
119 "position out of bounds", goto error
);
121 isl_space_free(space
);
122 aff
= isl_aff_alloc(ls
);
126 pos
+= isl_local_space_offset(aff
->ls
, type
);
128 isl_int_set_si(aff
->v
->el
[0], 1);
129 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
130 isl_int_set_si(aff
->v
->el
[1 + pos
], 1);
134 isl_local_space_free(ls
);
135 isl_space_free(space
);
139 /* Return a piecewise affine expression that is equal to
140 * the specified dimension in "ls".
142 __isl_give isl_pw_aff
*isl_pw_aff_var_on_domain(__isl_take isl_local_space
*ls
,
143 enum isl_dim_type type
, unsigned pos
)
145 return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls
, type
, pos
));
148 __isl_give isl_aff
*isl_aff_copy(__isl_keep isl_aff
*aff
)
157 __isl_give isl_aff
*isl_aff_dup(__isl_keep isl_aff
*aff
)
162 return isl_aff_alloc_vec(isl_local_space_copy(aff
->ls
),
163 isl_vec_copy(aff
->v
));
166 __isl_give isl_aff
*isl_aff_cow(__isl_take isl_aff
*aff
)
174 return isl_aff_dup(aff
);
177 void *isl_aff_free(__isl_take isl_aff
*aff
)
185 isl_local_space_free(aff
->ls
);
186 isl_vec_free(aff
->v
);
193 isl_ctx
*isl_aff_get_ctx(__isl_keep isl_aff
*aff
)
195 return aff
? isl_local_space_get_ctx(aff
->ls
) : NULL
;
198 /* Externally, an isl_aff has a map space, but internally, the
199 * ls field corresponds to the domain of that space.
201 int isl_aff_dim(__isl_keep isl_aff
*aff
, enum isl_dim_type type
)
205 if (type
== isl_dim_out
)
207 if (type
== isl_dim_in
)
209 return isl_local_space_dim(aff
->ls
, type
);
212 __isl_give isl_space
*isl_aff_get_domain_space(__isl_keep isl_aff
*aff
)
214 return aff
? isl_local_space_get_space(aff
->ls
) : NULL
;
217 __isl_give isl_space
*isl_aff_get_space(__isl_keep isl_aff
*aff
)
222 space
= isl_local_space_get_space(aff
->ls
);
223 space
= isl_space_from_domain(space
);
224 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
228 __isl_give isl_local_space
*isl_aff_get_domain_local_space(
229 __isl_keep isl_aff
*aff
)
231 return aff
? isl_local_space_copy(aff
->ls
) : NULL
;
234 __isl_give isl_local_space
*isl_aff_get_local_space(__isl_keep isl_aff
*aff
)
239 ls
= isl_local_space_copy(aff
->ls
);
240 ls
= isl_local_space_from_domain(ls
);
241 ls
= isl_local_space_add_dims(ls
, isl_dim_out
, 1);
245 /* Externally, an isl_aff has a map space, but internally, the
246 * ls field corresponds to the domain of that space.
248 const char *isl_aff_get_dim_name(__isl_keep isl_aff
*aff
,
249 enum isl_dim_type type
, unsigned pos
)
253 if (type
== isl_dim_out
)
255 if (type
== isl_dim_in
)
257 return isl_local_space_get_dim_name(aff
->ls
, type
, pos
);
260 __isl_give isl_aff
*isl_aff_reset_domain_space(__isl_take isl_aff
*aff
,
261 __isl_take isl_space
*dim
)
263 aff
= isl_aff_cow(aff
);
267 aff
->ls
= isl_local_space_reset_space(aff
->ls
, dim
);
269 return isl_aff_free(aff
);
278 /* Reset the space of "aff". This function is called from isl_pw_templ.c
279 * and doesn't know if the space of an element object is represented
280 * directly or through its domain. It therefore passes along both.
282 __isl_give isl_aff
*isl_aff_reset_space_and_domain(__isl_take isl_aff
*aff
,
283 __isl_take isl_space
*space
, __isl_take isl_space
*domain
)
285 isl_space_free(space
);
286 return isl_aff_reset_domain_space(aff
, domain
);
289 /* Reorder the coefficients of the affine expression based
290 * on the given reodering.
291 * The reordering r is assumed to have been extended with the local
294 static __isl_give isl_vec
*vec_reorder(__isl_take isl_vec
*vec
,
295 __isl_take isl_reordering
*r
, int n_div
)
303 res
= isl_vec_alloc(vec
->ctx
,
304 2 + isl_space_dim(r
->dim
, isl_dim_all
) + n_div
);
305 isl_seq_cpy(res
->el
, vec
->el
, 2);
306 isl_seq_clr(res
->el
+ 2, res
->size
- 2);
307 for (i
= 0; i
< r
->len
; ++i
)
308 isl_int_set(res
->el
[2 + r
->pos
[i
]], vec
->el
[2 + i
]);
310 isl_reordering_free(r
);
315 isl_reordering_free(r
);
319 /* Reorder the dimensions of the domain of "aff" according
320 * to the given reordering.
322 __isl_give isl_aff
*isl_aff_realign_domain(__isl_take isl_aff
*aff
,
323 __isl_take isl_reordering
*r
)
325 aff
= isl_aff_cow(aff
);
329 r
= isl_reordering_extend(r
, aff
->ls
->div
->n_row
);
330 aff
->v
= vec_reorder(aff
->v
, isl_reordering_copy(r
),
331 aff
->ls
->div
->n_row
);
332 aff
->ls
= isl_local_space_realign(aff
->ls
, r
);
334 if (!aff
->v
|| !aff
->ls
)
335 return isl_aff_free(aff
);
340 isl_reordering_free(r
);
344 __isl_give isl_aff
*isl_aff_align_params(__isl_take isl_aff
*aff
,
345 __isl_take isl_space
*model
)
350 if (!isl_space_match(aff
->ls
->dim
, isl_dim_param
,
351 model
, isl_dim_param
)) {
354 model
= isl_space_drop_dims(model
, isl_dim_in
,
355 0, isl_space_dim(model
, isl_dim_in
));
356 model
= isl_space_drop_dims(model
, isl_dim_out
,
357 0, isl_space_dim(model
, isl_dim_out
));
358 exp
= isl_parameter_alignment_reordering(aff
->ls
->dim
, model
);
359 exp
= isl_reordering_extend_space(exp
,
360 isl_aff_get_domain_space(aff
));
361 aff
= isl_aff_realign_domain(aff
, exp
);
364 isl_space_free(model
);
367 isl_space_free(model
);
372 int isl_aff_plain_is_zero(__isl_keep isl_aff
*aff
)
377 return isl_seq_first_non_zero(aff
->v
->el
+ 1, aff
->v
->size
- 1) < 0;
380 int isl_aff_plain_is_equal(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
387 equal
= isl_local_space_is_equal(aff1
->ls
, aff2
->ls
);
388 if (equal
< 0 || !equal
)
391 return isl_vec_is_equal(aff1
->v
, aff2
->v
);
394 int isl_aff_get_denominator(__isl_keep isl_aff
*aff
, isl_int
*v
)
398 isl_int_set(*v
, aff
->v
->el
[0]);
402 int isl_aff_get_constant(__isl_keep isl_aff
*aff
, isl_int
*v
)
406 isl_int_set(*v
, aff
->v
->el
[1]);
410 int isl_aff_get_coefficient(__isl_keep isl_aff
*aff
,
411 enum isl_dim_type type
, int pos
, isl_int
*v
)
416 if (type
== isl_dim_out
)
417 isl_die(aff
->v
->ctx
, isl_error_invalid
,
418 "output/set dimension does not have a coefficient",
420 if (type
== isl_dim_in
)
423 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
424 isl_die(aff
->v
->ctx
, isl_error_invalid
,
425 "position out of bounds", return -1);
427 pos
+= isl_local_space_offset(aff
->ls
, type
);
428 isl_int_set(*v
, aff
->v
->el
[1 + pos
]);
433 __isl_give isl_aff
*isl_aff_set_denominator(__isl_take isl_aff
*aff
, isl_int v
)
435 aff
= isl_aff_cow(aff
);
439 aff
->v
= isl_vec_cow(aff
->v
);
441 return isl_aff_free(aff
);
443 isl_int_set(aff
->v
->el
[0], v
);
448 __isl_give isl_aff
*isl_aff_set_constant(__isl_take isl_aff
*aff
, isl_int v
)
450 aff
= isl_aff_cow(aff
);
454 aff
->v
= isl_vec_cow(aff
->v
);
456 return isl_aff_free(aff
);
458 isl_int_set(aff
->v
->el
[1], v
);
463 __isl_give isl_aff
*isl_aff_add_constant(__isl_take isl_aff
*aff
, isl_int v
)
465 if (isl_int_is_zero(v
))
468 aff
= isl_aff_cow(aff
);
472 aff
->v
= isl_vec_cow(aff
->v
);
474 return isl_aff_free(aff
);
476 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
);
481 __isl_give isl_aff
*isl_aff_add_constant_si(__isl_take isl_aff
*aff
, int v
)
486 isl_int_set_si(t
, v
);
487 aff
= isl_aff_add_constant(aff
, t
);
493 /* Add "v" to the numerator of the constant term of "aff".
495 __isl_give isl_aff
*isl_aff_add_constant_num(__isl_take isl_aff
*aff
, isl_int v
)
497 if (isl_int_is_zero(v
))
500 aff
= isl_aff_cow(aff
);
504 aff
->v
= isl_vec_cow(aff
->v
);
506 return isl_aff_free(aff
);
508 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], v
);
513 /* Add "v" to the numerator of the constant term of "aff".
515 __isl_give isl_aff
*isl_aff_add_constant_num_si(__isl_take isl_aff
*aff
, int v
)
523 isl_int_set_si(t
, v
);
524 aff
= isl_aff_add_constant_num(aff
, t
);
530 __isl_give isl_aff
*isl_aff_set_constant_si(__isl_take isl_aff
*aff
, int v
)
532 aff
= isl_aff_cow(aff
);
536 aff
->v
= isl_vec_cow(aff
->v
);
538 return isl_aff_free(aff
);
540 isl_int_set_si(aff
->v
->el
[1], v
);
545 __isl_give isl_aff
*isl_aff_set_coefficient(__isl_take isl_aff
*aff
,
546 enum isl_dim_type type
, int pos
, isl_int v
)
551 if (type
== isl_dim_out
)
552 isl_die(aff
->v
->ctx
, isl_error_invalid
,
553 "output/set dimension does not have a coefficient",
554 return isl_aff_free(aff
));
555 if (type
== isl_dim_in
)
558 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
559 isl_die(aff
->v
->ctx
, isl_error_invalid
,
560 "position out of bounds", return isl_aff_free(aff
));
562 aff
= isl_aff_cow(aff
);
566 aff
->v
= isl_vec_cow(aff
->v
);
568 return isl_aff_free(aff
);
570 pos
+= isl_local_space_offset(aff
->ls
, type
);
571 isl_int_set(aff
->v
->el
[1 + pos
], v
);
576 __isl_give isl_aff
*isl_aff_set_coefficient_si(__isl_take isl_aff
*aff
,
577 enum isl_dim_type type
, int pos
, int v
)
582 if (type
== isl_dim_out
)
583 isl_die(aff
->v
->ctx
, isl_error_invalid
,
584 "output/set dimension does not have a coefficient",
585 return isl_aff_free(aff
));
586 if (type
== isl_dim_in
)
589 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
590 isl_die(aff
->v
->ctx
, isl_error_invalid
,
591 "position out of bounds", return isl_aff_free(aff
));
593 aff
= isl_aff_cow(aff
);
597 aff
->v
= isl_vec_cow(aff
->v
);
599 return isl_aff_free(aff
);
601 pos
+= isl_local_space_offset(aff
->ls
, type
);
602 isl_int_set_si(aff
->v
->el
[1 + pos
], v
);
607 __isl_give isl_aff
*isl_aff_add_coefficient(__isl_take isl_aff
*aff
,
608 enum isl_dim_type type
, int pos
, isl_int v
)
613 if (type
== isl_dim_out
)
614 isl_die(aff
->v
->ctx
, isl_error_invalid
,
615 "output/set dimension does not have a coefficient",
616 return isl_aff_free(aff
));
617 if (type
== isl_dim_in
)
620 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
621 isl_die(aff
->v
->ctx
, isl_error_invalid
,
622 "position out of bounds", return isl_aff_free(aff
));
624 aff
= isl_aff_cow(aff
);
628 aff
->v
= isl_vec_cow(aff
->v
);
630 return isl_aff_free(aff
);
632 pos
+= isl_local_space_offset(aff
->ls
, type
);
633 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
);
638 __isl_give isl_aff
*isl_aff_add_coefficient_si(__isl_take isl_aff
*aff
,
639 enum isl_dim_type type
, int pos
, int v
)
644 isl_int_set_si(t
, v
);
645 aff
= isl_aff_add_coefficient(aff
, type
, pos
, t
);
651 __isl_give isl_aff
*isl_aff_get_div(__isl_keep isl_aff
*aff
, int pos
)
656 return isl_local_space_get_div(aff
->ls
, pos
);
659 __isl_give isl_aff
*isl_aff_neg(__isl_take isl_aff
*aff
)
661 aff
= isl_aff_cow(aff
);
664 aff
->v
= isl_vec_cow(aff
->v
);
666 return isl_aff_free(aff
);
668 isl_seq_neg(aff
->v
->el
+ 1, aff
->v
->el
+ 1, aff
->v
->size
- 1);
673 /* Remove divs from the local space that do not appear in the affine
675 * We currently only remove divs at the end.
676 * Some intermediate divs may also not appear directly in the affine
677 * expression, but we would also need to check that no other divs are
678 * defined in terms of them.
680 __isl_give isl_aff
*isl_aff_remove_unused_divs( __isl_take isl_aff
*aff
)
689 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
690 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
692 pos
= isl_seq_last_non_zero(aff
->v
->el
+ 1 + off
, n
) + 1;
696 aff
= isl_aff_cow(aff
);
700 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, isl_dim_div
, pos
, n
- pos
);
701 aff
->v
= isl_vec_drop_els(aff
->v
, 1 + off
+ pos
, n
- pos
);
702 if (!aff
->ls
|| !aff
->v
)
703 return isl_aff_free(aff
);
708 /* Given two affine expressions "p" of length p_len (including the
709 * denominator and the constant term) and "subs" of length subs_len,
710 * plug in "subs" for the variable at position "pos".
711 * The variables of "subs" and "p" are assumed to match up to subs_len,
712 * but "p" may have additional variables.
713 * "v" is an initialized isl_int that can be used internally.
715 * In particular, if "p" represents the expression
719 * with i the variable at position "pos" and "subs" represents the expression
723 * then the result represents the expression
728 void isl_seq_substitute(isl_int
*p
, int pos
, isl_int
*subs
,
729 int p_len
, int subs_len
, isl_int v
)
731 isl_int_set(v
, p
[1 + pos
]);
732 isl_int_set_si(p
[1 + pos
], 0);
733 isl_seq_combine(p
+ 1, subs
[0], p
+ 1, v
, subs
+ 1, subs_len
- 1);
734 isl_seq_scale(p
+ subs_len
, p
+ subs_len
, subs
[0], p_len
- subs_len
);
735 isl_int_mul(p
[0], p
[0], subs
[0]);
738 /* Look for any divs in the aff->ls with a denominator equal to one
739 * and plug them into the affine expression and any subsequent divs
740 * that may reference the div.
742 static __isl_give isl_aff
*plug_in_integral_divs(__isl_take isl_aff
*aff
)
754 n
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
756 for (i
= 0; i
< n
; ++i
) {
757 if (!isl_int_is_one(aff
->ls
->div
->row
[i
][0]))
759 ls
= isl_local_space_copy(aff
->ls
);
760 ls
= isl_local_space_substitute_seq(ls
, isl_dim_div
, i
,
761 aff
->ls
->div
->row
[i
], len
, i
+ 1);
762 vec
= isl_vec_copy(aff
->v
);
763 vec
= isl_vec_cow(vec
);
769 pos
= isl_local_space_offset(aff
->ls
, isl_dim_div
) + i
;
770 isl_seq_substitute(vec
->el
, pos
, aff
->ls
->div
->row
[i
],
775 isl_vec_free(aff
->v
);
777 isl_local_space_free(aff
->ls
);
784 isl_local_space_free(ls
);
785 return isl_aff_free(aff
);
788 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
790 * Even though this function is only called on isl_affs with a single
791 * reference, we are careful to only change aff->v and aff->ls together.
793 static __isl_give isl_aff
*swap_div(__isl_take isl_aff
*aff
, int a
, int b
)
795 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
799 ls
= isl_local_space_copy(aff
->ls
);
800 ls
= isl_local_space_swap_div(ls
, a
, b
);
801 v
= isl_vec_copy(aff
->v
);
806 isl_int_swap(v
->el
[1 + off
+ a
], v
->el
[1 + off
+ b
]);
807 isl_vec_free(aff
->v
);
809 isl_local_space_free(aff
->ls
);
815 isl_local_space_free(ls
);
816 return isl_aff_free(aff
);
819 /* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
821 * We currently do not actually remove div "b", but simply add its
822 * coefficient to that of "a" and then zero it out.
824 static __isl_give isl_aff
*merge_divs(__isl_take isl_aff
*aff
, int a
, int b
)
826 unsigned off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
828 if (isl_int_is_zero(aff
->v
->el
[1 + off
+ b
]))
831 aff
->v
= isl_vec_cow(aff
->v
);
833 return isl_aff_free(aff
);
835 isl_int_add(aff
->v
->el
[1 + off
+ a
],
836 aff
->v
->el
[1 + off
+ a
], aff
->v
->el
[1 + off
+ b
]);
837 isl_int_set_si(aff
->v
->el
[1 + off
+ b
], 0);
842 /* Sort the divs in the local space of "aff" according to
843 * the comparison function "cmp_row" in isl_local_space.c,
844 * combining the coefficients of identical divs.
846 * Reordering divs does not change the semantics of "aff",
847 * so there is no need to call isl_aff_cow.
848 * Moreover, this function is currently only called on isl_affs
849 * with a single reference.
851 static __isl_give isl_aff
*sort_divs(__isl_take isl_aff
*aff
)
859 off
= isl_local_space_offset(aff
->ls
, isl_dim_div
);
860 n
= isl_aff_dim(aff
, isl_dim_div
);
861 for (i
= 1; i
< n
; ++i
) {
862 for (j
= i
- 1; j
>= 0; --j
) {
863 int cmp
= isl_mat_cmp_div(aff
->ls
->div
, j
, j
+ 1);
867 aff
= merge_divs(aff
, j
, j
+ 1);
869 aff
= swap_div(aff
, j
, j
+ 1);
878 /* Normalize the representation of "aff".
880 * This function should only be called of "new" isl_affs, i.e.,
881 * with only a single reference. We therefore do not need to
882 * worry about affecting other instances.
884 __isl_give isl_aff
*isl_aff_normalize(__isl_take isl_aff
*aff
)
888 aff
->v
= isl_vec_normalize(aff
->v
);
890 return isl_aff_free(aff
);
891 aff
= plug_in_integral_divs(aff
);
892 aff
= sort_divs(aff
);
893 aff
= isl_aff_remove_unused_divs(aff
);
897 /* Given f, return floor(f).
898 * If f is an integer expression, then just return f.
899 * If f is a constant, then return the constant floor(f).
900 * Otherwise, if f = g/m, write g = q m + r,
901 * create a new div d = [r/m] and return the expression q + d.
902 * The coefficients in r are taken to lie between -m/2 and m/2.
904 __isl_give isl_aff
*isl_aff_floor(__isl_take isl_aff
*aff
)
914 if (isl_int_is_one(aff
->v
->el
[0]))
917 aff
= isl_aff_cow(aff
);
921 aff
->v
= isl_vec_cow(aff
->v
);
923 return isl_aff_free(aff
);
925 if (isl_aff_is_cst(aff
)) {
926 isl_int_fdiv_q(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
927 isl_int_set_si(aff
->v
->el
[0], 1);
931 div
= isl_vec_copy(aff
->v
);
932 div
= isl_vec_cow(div
);
934 return isl_aff_free(aff
);
936 ctx
= isl_aff_get_ctx(aff
);
937 isl_int_fdiv_q(aff
->v
->el
[0], aff
->v
->el
[0], ctx
->two
);
938 for (i
= 1; i
< aff
->v
->size
; ++i
) {
939 isl_int_fdiv_r(div
->el
[i
], div
->el
[i
], div
->el
[0]);
940 isl_int_fdiv_q(aff
->v
->el
[i
], aff
->v
->el
[i
], div
->el
[0]);
941 if (isl_int_gt(div
->el
[i
], aff
->v
->el
[0])) {
942 isl_int_sub(div
->el
[i
], div
->el
[i
], div
->el
[0]);
943 isl_int_add_ui(aff
->v
->el
[i
], aff
->v
->el
[i
], 1);
947 aff
->ls
= isl_local_space_add_div(aff
->ls
, div
);
949 return isl_aff_free(aff
);
952 aff
->v
= isl_vec_extend(aff
->v
, size
+ 1);
954 return isl_aff_free(aff
);
955 isl_int_set_si(aff
->v
->el
[0], 1);
956 isl_int_set_si(aff
->v
->el
[size
], 1);
958 aff
= isl_aff_normalize(aff
);
965 * aff mod m = aff - m * floor(aff/m)
967 __isl_give isl_aff
*isl_aff_mod(__isl_take isl_aff
*aff
, isl_int m
)
971 res
= isl_aff_copy(aff
);
972 aff
= isl_aff_scale_down(aff
, m
);
973 aff
= isl_aff_floor(aff
);
974 aff
= isl_aff_scale(aff
, m
);
975 res
= isl_aff_sub(res
, aff
);
982 * pwaff mod m = pwaff - m * floor(pwaff/m)
984 __isl_give isl_pw_aff
*isl_pw_aff_mod(__isl_take isl_pw_aff
*pwaff
, isl_int m
)
988 res
= isl_pw_aff_copy(pwaff
);
989 pwaff
= isl_pw_aff_scale_down(pwaff
, m
);
990 pwaff
= isl_pw_aff_floor(pwaff
);
991 pwaff
= isl_pw_aff_scale(pwaff
, m
);
992 res
= isl_pw_aff_sub(res
, pwaff
);
997 /* Given f, return ceil(f).
998 * If f is an integer expression, then just return f.
999 * Otherwise, let f be the expression
1005 * floor((e + m - 1)/m)
1007 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
1012 if (isl_int_is_one(aff
->v
->el
[0]))
1015 aff
= isl_aff_cow(aff
);
1018 aff
->v
= isl_vec_cow(aff
->v
);
1020 return isl_aff_free(aff
);
1022 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1023 isl_int_sub_ui(aff
->v
->el
[1], aff
->v
->el
[1], 1);
1024 aff
= isl_aff_floor(aff
);
1029 /* Apply the expansion computed by isl_merge_divs.
1030 * The expansion itself is given by "exp" while the resulting
1031 * list of divs is given by "div".
1033 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
1034 __isl_take isl_mat
*div
, int *exp
)
1041 aff
= isl_aff_cow(aff
);
1045 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1046 new_n_div
= isl_mat_rows(div
);
1047 if (new_n_div
< old_n_div
)
1048 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
1049 "not an expansion", goto error
);
1051 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
1055 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
1057 for (i
= new_n_div
- 1; i
>= 0; --i
) {
1058 if (j
>= 0 && exp
[j
] == i
) {
1060 isl_int_swap(aff
->v
->el
[offset
+ i
],
1061 aff
->v
->el
[offset
+ j
]);
1064 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
1067 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
1078 /* Add two affine expressions that live in the same local space.
1080 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
1081 __isl_take isl_aff
*aff2
)
1085 aff1
= isl_aff_cow(aff1
);
1089 aff1
->v
= isl_vec_cow(aff1
->v
);
1095 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
1096 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1097 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
1098 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
1099 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
1100 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1101 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
1113 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
1114 __isl_take isl_aff
*aff2
)
1124 ctx
= isl_aff_get_ctx(aff1
);
1125 if (!isl_space_is_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
1126 isl_die(ctx
, isl_error_invalid
,
1127 "spaces don't match", goto error
);
1129 if (aff1
->ls
->div
->n_row
== 0 && aff2
->ls
->div
->n_row
== 0)
1130 return add_expanded(aff1
, aff2
);
1132 exp1
= isl_alloc_array(ctx
, int, aff1
->ls
->div
->n_row
);
1133 exp2
= isl_alloc_array(ctx
, int, aff2
->ls
->div
->n_row
);
1137 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
1138 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
1139 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
1143 return add_expanded(aff1
, aff2
);
1152 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
1153 __isl_take isl_aff
*aff2
)
1155 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
1158 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
1162 if (isl_int_is_one(f
))
1165 aff
= isl_aff_cow(aff
);
1168 aff
->v
= isl_vec_cow(aff
->v
);
1170 return isl_aff_free(aff
);
1173 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
1174 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1175 isl_int_divexact(gcd
, f
, gcd
);
1176 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1182 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
1186 if (isl_int_is_one(f
))
1189 aff
= isl_aff_cow(aff
);
1193 if (isl_int_is_zero(f
))
1194 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1195 "cannot scale down by zero", return isl_aff_free(aff
));
1197 aff
->v
= isl_vec_cow(aff
->v
);
1199 return isl_aff_free(aff
);
1202 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
1203 isl_int_gcd(gcd
, gcd
, f
);
1204 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1205 isl_int_divexact(gcd
, f
, gcd
);
1206 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1212 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
1220 isl_int_set_ui(v
, f
);
1221 aff
= isl_aff_scale_down(aff
, v
);
1227 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
1228 enum isl_dim_type type
, unsigned pos
, const char *s
)
1230 aff
= isl_aff_cow(aff
);
1233 if (type
== isl_dim_out
)
1234 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1235 "cannot set name of output/set dimension",
1236 return isl_aff_free(aff
));
1237 if (type
== isl_dim_in
)
1239 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
1241 return isl_aff_free(aff
);
1246 __isl_give isl_aff
*isl_aff_set_dim_id(__isl_take isl_aff
*aff
,
1247 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1249 aff
= isl_aff_cow(aff
);
1251 return isl_id_free(id
);
1252 if (type
== isl_dim_out
)
1253 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1254 "cannot set name of output/set dimension",
1256 if (type
== isl_dim_in
)
1258 aff
->ls
= isl_local_space_set_dim_id(aff
->ls
, type
, pos
, id
);
1260 return isl_aff_free(aff
);
1269 /* Exploit the equalities in "eq" to simplify the affine expression
1270 * and the expressions of the integer divisions in the local space.
1271 * The integer divisions in this local space are assumed to appear
1272 * as regular dimensions in "eq".
1274 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
1275 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1283 if (eq
->n_eq
== 0) {
1284 isl_basic_set_free(eq
);
1288 aff
= isl_aff_cow(aff
);
1292 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
1293 isl_basic_set_copy(eq
));
1294 aff
->v
= isl_vec_cow(aff
->v
);
1295 if (!aff
->ls
|| !aff
->v
)
1298 total
= 1 + isl_space_dim(eq
->dim
, isl_dim_all
);
1300 for (i
= 0; i
< eq
->n_eq
; ++i
) {
1301 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
1302 if (j
< 0 || j
== 0 || j
>= total
)
1305 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
1309 isl_basic_set_free(eq
);
1310 aff
= isl_aff_normalize(aff
);
1313 isl_basic_set_free(eq
);
1318 /* Exploit the equalities in "eq" to simplify the affine expression
1319 * and the expressions of the integer divisions in the local space.
1321 static __isl_give isl_aff
*isl_aff_substitute_equalities(
1322 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1328 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1330 eq
= isl_basic_set_add(eq
, isl_dim_set
, n_div
);
1331 return isl_aff_substitute_equalities_lifted(aff
, eq
);
1333 isl_basic_set_free(eq
);
1338 /* Look for equalities among the variables shared by context and aff
1339 * and the integer divisions of aff, if any.
1340 * The equalities are then used to eliminate coefficients and/or integer
1341 * divisions from aff.
1343 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
1344 __isl_take isl_set
*context
)
1346 isl_basic_set
*hull
;
1351 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1353 isl_basic_set
*bset
;
1354 isl_local_space
*ls
;
1355 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
1356 ls
= isl_aff_get_domain_local_space(aff
);
1357 bset
= isl_basic_set_from_local_space(ls
);
1358 bset
= isl_basic_set_lift(bset
);
1359 bset
= isl_basic_set_flatten(bset
);
1360 context
= isl_set_intersect(context
,
1361 isl_set_from_basic_set(bset
));
1364 hull
= isl_set_affine_hull(context
);
1365 return isl_aff_substitute_equalities_lifted(aff
, hull
);
1368 isl_set_free(context
);
1372 __isl_give isl_aff
*isl_aff_gist_params(__isl_take isl_aff
*aff
,
1373 __isl_take isl_set
*context
)
1375 isl_set
*dom_context
= isl_set_universe(isl_aff_get_domain_space(aff
));
1376 dom_context
= isl_set_intersect_params(dom_context
, context
);
1377 return isl_aff_gist(aff
, dom_context
);
1380 /* Return a basic set containing those elements in the space
1381 * of aff where it is non-negative.
1382 * If "rational" is set, then return a rational basic set.
1384 static __isl_give isl_basic_set
*aff_nonneg_basic_set(
1385 __isl_take isl_aff
*aff
, int rational
)
1387 isl_constraint
*ineq
;
1388 isl_basic_set
*bset
;
1390 ineq
= isl_inequality_from_aff(aff
);
1392 bset
= isl_basic_set_from_constraint(ineq
);
1394 bset
= isl_basic_set_set_rational(bset
);
1395 bset
= isl_basic_set_simplify(bset
);
1399 /* Return a basic set containing those elements in the space
1400 * of aff where it is non-negative.
1402 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
1404 return aff_nonneg_basic_set(aff
, 0);
1407 /* Return a basic set containing those elements in the domain space
1408 * of aff where it is negative.
1410 __isl_give isl_basic_set
*isl_aff_neg_basic_set(__isl_take isl_aff
*aff
)
1412 aff
= isl_aff_neg(aff
);
1413 aff
= isl_aff_add_constant_num_si(aff
, -1);
1414 return isl_aff_nonneg_basic_set(aff
);
1417 /* Return a basic set containing those elements in the space
1418 * of aff where it is zero.
1419 * If "rational" is set, then return a rational basic set.
1421 static __isl_give isl_basic_set
*aff_zero_basic_set(__isl_take isl_aff
*aff
,
1424 isl_constraint
*ineq
;
1425 isl_basic_set
*bset
;
1427 ineq
= isl_equality_from_aff(aff
);
1429 bset
= isl_basic_set_from_constraint(ineq
);
1431 bset
= isl_basic_set_set_rational(bset
);
1432 bset
= isl_basic_set_simplify(bset
);
1436 /* Return a basic set containing those elements in the space
1437 * of aff where it is zero.
1439 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
1441 return aff_zero_basic_set(aff
, 0);
1444 /* Return a basic set containing those elements in the shared space
1445 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1447 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
1448 __isl_take isl_aff
*aff2
)
1450 aff1
= isl_aff_sub(aff1
, aff2
);
1452 return isl_aff_nonneg_basic_set(aff1
);
1455 /* Return a basic set containing those elements in the shared space
1456 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1458 __isl_give isl_basic_set
*isl_aff_le_basic_set(__isl_take isl_aff
*aff1
,
1459 __isl_take isl_aff
*aff2
)
1461 return isl_aff_ge_basic_set(aff2
, aff1
);
1464 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
1465 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
1467 aff1
= isl_aff_add(aff1
, aff2
);
1468 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
1472 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
1480 /* Check whether the given affine expression has non-zero coefficient
1481 * for any dimension in the given range or if any of these dimensions
1482 * appear with non-zero coefficients in any of the integer divisions
1483 * involved in the affine expression.
1485 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
1486 enum isl_dim_type type
, unsigned first
, unsigned n
)
1498 ctx
= isl_aff_get_ctx(aff
);
1499 if (first
+ n
> isl_aff_dim(aff
, type
))
1500 isl_die(ctx
, isl_error_invalid
,
1501 "range out of bounds", return -1);
1503 active
= isl_local_space_get_active(aff
->ls
, aff
->v
->el
+ 2);
1507 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
1508 for (i
= 0; i
< n
; ++i
)
1509 if (active
[first
+ i
]) {
1522 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
1523 enum isl_dim_type type
, unsigned first
, unsigned n
)
1529 if (type
== isl_dim_out
)
1530 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1531 "cannot drop output/set dimension",
1532 return isl_aff_free(aff
));
1533 if (type
== isl_dim_in
)
1535 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1538 ctx
= isl_aff_get_ctx(aff
);
1539 if (first
+ n
> isl_local_space_dim(aff
->ls
, type
))
1540 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
1541 return isl_aff_free(aff
));
1543 aff
= isl_aff_cow(aff
);
1547 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
1549 return isl_aff_free(aff
);
1551 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
1552 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
1554 return isl_aff_free(aff
);
1559 /* Project the domain of the affine expression onto its parameter space.
1560 * The affine expression may not involve any of the domain dimensions.
1562 __isl_give isl_aff
*isl_aff_project_domain_on_params(__isl_take isl_aff
*aff
)
1568 n
= isl_aff_dim(aff
, isl_dim_in
);
1569 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, 0, n
);
1571 return isl_aff_free(aff
);
1573 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1574 "affine expression involves some of the domain dimensions",
1575 return isl_aff_free(aff
));
1576 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, 0, n
);
1577 space
= isl_aff_get_domain_space(aff
);
1578 space
= isl_space_params(space
);
1579 aff
= isl_aff_reset_domain_space(aff
, space
);
1583 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
1584 enum isl_dim_type type
, unsigned first
, unsigned n
)
1590 if (type
== isl_dim_out
)
1591 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1592 "cannot insert output/set dimensions",
1593 return isl_aff_free(aff
));
1594 if (type
== isl_dim_in
)
1596 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1599 ctx
= isl_aff_get_ctx(aff
);
1600 if (first
> isl_local_space_dim(aff
->ls
, type
))
1601 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
1602 return isl_aff_free(aff
));
1604 aff
= isl_aff_cow(aff
);
1608 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
1610 return isl_aff_free(aff
);
1612 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
1613 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
1615 return isl_aff_free(aff
);
1620 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
1621 enum isl_dim_type type
, unsigned n
)
1625 pos
= isl_aff_dim(aff
, type
);
1627 return isl_aff_insert_dims(aff
, type
, pos
, n
);
1630 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
1631 enum isl_dim_type type
, unsigned n
)
1635 pos
= isl_pw_aff_dim(pwaff
, type
);
1637 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
1640 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
1642 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
1643 return isl_pw_aff_alloc(dom
, aff
);
1647 #define PW isl_pw_aff
1651 #define EL_IS_ZERO is_empty
1655 #define IS_ZERO is_empty
1658 #undef DEFAULT_IS_ZERO
1659 #define DEFAULT_IS_ZERO 0
1663 #define NO_MOVE_DIMS
1667 #include <isl_pw_templ.c>
1669 static __isl_give isl_set
*align_params_pw_pw_set_and(
1670 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
1671 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
1672 __isl_take isl_pw_aff
*pwaff2
))
1674 if (!pwaff1
|| !pwaff2
)
1676 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
1677 pwaff2
->dim
, isl_dim_param
))
1678 return fn(pwaff1
, pwaff2
);
1679 if (!isl_space_has_named_params(pwaff1
->dim
) ||
1680 !isl_space_has_named_params(pwaff2
->dim
))
1681 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
1682 "unaligned unnamed parameters", goto error
);
1683 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
1684 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
1685 return fn(pwaff1
, pwaff2
);
1687 isl_pw_aff_free(pwaff1
);
1688 isl_pw_aff_free(pwaff2
);
1692 /* Compute a piecewise quasi-affine expression with a domain that
1693 * is the union of those of pwaff1 and pwaff2 and such that on each
1694 * cell, the quasi-affine expression is the better (according to cmp)
1695 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1696 * is defined on a given cell, then the associated expression
1697 * is the defined one.
1699 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
1700 __isl_take isl_pw_aff
*pwaff2
,
1701 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
1702 __isl_take isl_aff
*aff2
))
1709 if (!pwaff1
|| !pwaff2
)
1712 ctx
= isl_space_get_ctx(pwaff1
->dim
);
1713 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
1714 isl_die(ctx
, isl_error_invalid
,
1715 "arguments should live in same space", goto error
);
1717 if (isl_pw_aff_is_empty(pwaff1
)) {
1718 isl_pw_aff_free(pwaff1
);
1722 if (isl_pw_aff_is_empty(pwaff2
)) {
1723 isl_pw_aff_free(pwaff2
);
1727 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
1728 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
1730 for (i
= 0; i
< pwaff1
->n
; ++i
) {
1731 set
= isl_set_copy(pwaff1
->p
[i
].set
);
1732 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1733 struct isl_set
*common
;
1736 common
= isl_set_intersect(
1737 isl_set_copy(pwaff1
->p
[i
].set
),
1738 isl_set_copy(pwaff2
->p
[j
].set
));
1739 better
= isl_set_from_basic_set(cmp(
1740 isl_aff_copy(pwaff2
->p
[j
].aff
),
1741 isl_aff_copy(pwaff1
->p
[i
].aff
)));
1742 better
= isl_set_intersect(common
, better
);
1743 if (isl_set_plain_is_empty(better
)) {
1744 isl_set_free(better
);
1747 set
= isl_set_subtract(set
, isl_set_copy(better
));
1749 res
= isl_pw_aff_add_piece(res
, better
,
1750 isl_aff_copy(pwaff2
->p
[j
].aff
));
1752 res
= isl_pw_aff_add_piece(res
, set
,
1753 isl_aff_copy(pwaff1
->p
[i
].aff
));
1756 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1757 set
= isl_set_copy(pwaff2
->p
[j
].set
);
1758 for (i
= 0; i
< pwaff1
->n
; ++i
)
1759 set
= isl_set_subtract(set
,
1760 isl_set_copy(pwaff1
->p
[i
].set
));
1761 res
= isl_pw_aff_add_piece(res
, set
,
1762 isl_aff_copy(pwaff2
->p
[j
].aff
));
1765 isl_pw_aff_free(pwaff1
);
1766 isl_pw_aff_free(pwaff2
);
1770 isl_pw_aff_free(pwaff1
);
1771 isl_pw_aff_free(pwaff2
);
1775 /* Compute a piecewise quasi-affine expression with a domain that
1776 * is the union of those of pwaff1 and pwaff2 and such that on each
1777 * cell, the quasi-affine expression is the maximum of those of pwaff1
1778 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1779 * cell, then the associated expression is the defined one.
1781 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
1782 __isl_take isl_pw_aff
*pwaff2
)
1784 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
1787 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
1788 __isl_take isl_pw_aff
*pwaff2
)
1790 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
1794 /* Compute a piecewise quasi-affine expression with a domain that
1795 * is the union of those of pwaff1 and pwaff2 and such that on each
1796 * cell, the quasi-affine expression is the minimum of those of pwaff1
1797 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1798 * cell, then the associated expression is the defined one.
1800 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
1801 __isl_take isl_pw_aff
*pwaff2
)
1803 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
1806 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
1807 __isl_take isl_pw_aff
*pwaff2
)
1809 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
1813 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
1814 __isl_take isl_pw_aff
*pwaff2
, int max
)
1817 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
1819 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
1822 /* Construct a map with as domain the domain of pwaff and
1823 * one-dimensional range corresponding to the affine expressions.
1825 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1834 dim
= isl_pw_aff_get_space(pwaff
);
1835 map
= isl_map_empty(dim
);
1837 for (i
= 0; i
< pwaff
->n
; ++i
) {
1838 isl_basic_map
*bmap
;
1841 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
1842 map_i
= isl_map_from_basic_map(bmap
);
1843 map_i
= isl_map_intersect_domain(map_i
,
1844 isl_set_copy(pwaff
->p
[i
].set
));
1845 map
= isl_map_union_disjoint(map
, map_i
);
1848 isl_pw_aff_free(pwaff
);
1853 /* Construct a map with as domain the domain of pwaff and
1854 * one-dimensional range corresponding to the affine expressions.
1856 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1860 if (isl_space_is_set(pwaff
->dim
))
1861 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
1862 "space of input is not a map",
1863 return isl_pw_aff_free(pwaff
));
1864 return map_from_pw_aff(pwaff
);
1867 /* Construct a one-dimensional set with as parameter domain
1868 * the domain of pwaff and the single set dimension
1869 * corresponding to the affine expressions.
1871 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1875 if (!isl_space_is_set(pwaff
->dim
))
1876 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
1877 "space of input is not a set",
1878 return isl_pw_aff_free(pwaff
));
1879 return map_from_pw_aff(pwaff
);
1882 /* Return a set containing those elements in the domain
1883 * of pwaff where it is non-negative.
1885 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
1893 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
1895 for (i
= 0; i
< pwaff
->n
; ++i
) {
1896 isl_basic_set
*bset
;
1900 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
1901 bset
= aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
1903 set_i
= isl_set_from_basic_set(bset
);
1904 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
1905 set
= isl_set_union_disjoint(set
, set_i
);
1908 isl_pw_aff_free(pwaff
);
1913 /* Return a set containing those elements in the domain
1914 * of pwaff where it is zero (if complement is 0) or not zero
1915 * (if complement is 1).
1917 static __isl_give isl_set
*pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
,
1926 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
1928 for (i
= 0; i
< pwaff
->n
; ++i
) {
1929 isl_basic_set
*bset
;
1930 isl_set
*set_i
, *zero
;
1933 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
1934 bset
= aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
1936 zero
= isl_set_from_basic_set(bset
);
1937 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
1939 set_i
= isl_set_subtract(set_i
, zero
);
1941 set_i
= isl_set_intersect(set_i
, zero
);
1942 set
= isl_set_union_disjoint(set
, set_i
);
1945 isl_pw_aff_free(pwaff
);
1950 /* Return a set containing those elements in the domain
1951 * of pwaff where it is zero.
1953 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
1955 return pw_aff_zero_set(pwaff
, 0);
1958 /* Return a set containing those elements in the domain
1959 * of pwaff where it is not zero.
1961 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
1963 return pw_aff_zero_set(pwaff
, 1);
1966 /* Return a set containing those elements in the shared domain
1967 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1969 * We compute the difference on the shared domain and then construct
1970 * the set of values where this difference is non-negative.
1971 * If strict is set, we first subtract 1 from the difference.
1972 * If equal is set, we only return the elements where pwaff1 and pwaff2
1975 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
1976 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
1978 isl_set
*set1
, *set2
;
1980 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
1981 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
1982 set1
= isl_set_intersect(set1
, set2
);
1983 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
1984 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
1985 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
1988 isl_space
*dim
= isl_set_get_space(set1
);
1990 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1991 aff
= isl_aff_add_constant_si(aff
, -1);
1992 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
1997 return isl_pw_aff_zero_set(pwaff1
);
1998 return isl_pw_aff_nonneg_set(pwaff1
);
2001 /* Return a set containing those elements in the shared domain
2002 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2004 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2005 __isl_take isl_pw_aff
*pwaff2
)
2007 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
2010 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2011 __isl_take isl_pw_aff
*pwaff2
)
2013 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2016 /* Return a set containing those elements in the shared domain
2017 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2019 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2020 __isl_take isl_pw_aff
*pwaff2
)
2022 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2025 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2026 __isl_take isl_pw_aff
*pwaff2
)
2028 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2031 /* Return a set containing those elements in the shared domain
2032 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2034 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2035 __isl_take isl_pw_aff
*pwaff2
)
2037 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2040 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2041 __isl_take isl_pw_aff
*pwaff2
)
2043 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2046 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2047 __isl_take isl_pw_aff
*pwaff2
)
2049 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2052 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2053 __isl_take isl_pw_aff
*pwaff2
)
2055 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2058 /* Return a set containing those elements in the shared domain
2059 * of the elements of list1 and list2 where each element in list1
2060 * has the relation specified by "fn" with each element in list2.
2062 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2063 __isl_take isl_pw_aff_list
*list2
,
2064 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2065 __isl_take isl_pw_aff
*pwaff2
))
2071 if (!list1
|| !list2
)
2074 ctx
= isl_pw_aff_list_get_ctx(list1
);
2075 if (list1
->n
< 1 || list2
->n
< 1)
2076 isl_die(ctx
, isl_error_invalid
,
2077 "list should contain at least one element", goto error
);
2079 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2080 for (i
= 0; i
< list1
->n
; ++i
)
2081 for (j
= 0; j
< list2
->n
; ++j
) {
2084 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2085 isl_pw_aff_copy(list2
->p
[j
]));
2086 set
= isl_set_intersect(set
, set_ij
);
2089 isl_pw_aff_list_free(list1
);
2090 isl_pw_aff_list_free(list2
);
2093 isl_pw_aff_list_free(list1
);
2094 isl_pw_aff_list_free(list2
);
2098 /* Return a set containing those elements in the shared domain
2099 * of the elements of list1 and list2 where each element in list1
2100 * is equal to each element in list2.
2102 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2103 __isl_take isl_pw_aff_list
*list2
)
2105 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
2108 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
2109 __isl_take isl_pw_aff_list
*list2
)
2111 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
2114 /* Return a set containing those elements in the shared domain
2115 * of the elements of list1 and list2 where each element in list1
2116 * is less than or equal to each element in list2.
2118 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
2119 __isl_take isl_pw_aff_list
*list2
)
2121 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
2124 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
2125 __isl_take isl_pw_aff_list
*list2
)
2127 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
2130 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
2131 __isl_take isl_pw_aff_list
*list2
)
2133 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
2136 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
2137 __isl_take isl_pw_aff_list
*list2
)
2139 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
2143 /* Return a set containing those elements in the shared domain
2144 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2146 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2147 __isl_take isl_pw_aff
*pwaff2
)
2149 isl_set
*set_lt
, *set_gt
;
2151 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
2152 isl_pw_aff_copy(pwaff2
));
2153 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
2154 return isl_set_union_disjoint(set_lt
, set_gt
);
2157 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2158 __isl_take isl_pw_aff
*pwaff2
)
2160 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
2163 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
2168 if (isl_int_is_one(v
))
2170 if (!isl_int_is_pos(v
))
2171 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2172 "factor needs to be positive",
2173 return isl_pw_aff_free(pwaff
));
2174 pwaff
= isl_pw_aff_cow(pwaff
);
2180 for (i
= 0; i
< pwaff
->n
; ++i
) {
2181 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
2182 if (!pwaff
->p
[i
].aff
)
2183 return isl_pw_aff_free(pwaff
);
2189 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
2193 pwaff
= isl_pw_aff_cow(pwaff
);
2199 for (i
= 0; i
< pwaff
->n
; ++i
) {
2200 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
2201 if (!pwaff
->p
[i
].aff
)
2202 return isl_pw_aff_free(pwaff
);
2208 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
2212 pwaff
= isl_pw_aff_cow(pwaff
);
2218 for (i
= 0; i
< pwaff
->n
; ++i
) {
2219 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
2220 if (!pwaff
->p
[i
].aff
)
2221 return isl_pw_aff_free(pwaff
);
2227 /* Assuming that "cond1" and "cond2" are disjoint,
2228 * return an affine expression that is equal to pwaff1 on cond1
2229 * and to pwaff2 on cond2.
2231 static __isl_give isl_pw_aff
*isl_pw_aff_select(
2232 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
2233 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
2235 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
2236 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
2238 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
2241 /* Return an affine expression that is equal to pwaff_true for elements
2242 * where "cond" is non-zero and to pwaff_false for elements where "cond"
2244 * That is, return cond ? pwaff_true : pwaff_false;
2246 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
2247 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
2249 isl_set
*cond_true
, *cond_false
;
2251 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
2252 cond_false
= isl_pw_aff_zero_set(cond
);
2253 return isl_pw_aff_select(cond_true
, pwaff_true
,
2254 cond_false
, pwaff_false
);
2257 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
2262 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
2265 /* Check whether pwaff is a piecewise constant.
2267 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
2274 for (i
= 0; i
< pwaff
->n
; ++i
) {
2275 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
2276 if (is_cst
< 0 || !is_cst
)
2283 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
2284 __isl_take isl_aff
*aff2
)
2286 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
2287 return isl_aff_mul(aff2
, aff1
);
2289 if (!isl_aff_is_cst(aff2
))
2290 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
2291 "at least one affine expression should be constant",
2294 aff1
= isl_aff_cow(aff1
);
2298 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
2299 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
2309 /* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant.
2311 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
2312 __isl_take isl_aff
*aff2
)
2317 is_cst
= isl_aff_is_cst(aff2
);
2321 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
2322 "second argument should be a constant", goto error
);
2327 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
2329 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2330 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2333 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
2334 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
2337 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2338 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2349 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2350 __isl_take isl_pw_aff
*pwaff2
)
2352 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
2355 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2356 __isl_take isl_pw_aff
*pwaff2
)
2358 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
2361 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
2362 __isl_take isl_pw_aff
*pwaff2
)
2364 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
2367 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2368 __isl_take isl_pw_aff
*pwaff2
)
2370 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
2373 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2374 __isl_take isl_pw_aff
*pwaff2
)
2376 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
2379 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2380 __isl_take isl_pw_aff
*pa2
)
2382 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
2385 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
2387 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2388 __isl_take isl_pw_aff
*pa2
)
2392 is_cst
= isl_pw_aff_is_cst(pa2
);
2396 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2397 "second argument should be a piecewise constant",
2399 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
2401 isl_pw_aff_free(pa1
);
2402 isl_pw_aff_free(pa2
);
2406 /* Compute the quotient of the integer division of "pa1" by "pa2"
2407 * with rounding towards zero.
2408 * "pa2" is assumed to be a piecewise constant.
2410 * In particular, return
2412 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
2415 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
2416 __isl_take isl_pw_aff
*pa2
)
2422 is_cst
= isl_pw_aff_is_cst(pa2
);
2426 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2427 "second argument should be a piecewise constant",
2430 pa1
= isl_pw_aff_div(pa1
, pa2
);
2432 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
2433 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
2434 c
= isl_pw_aff_ceil(pa1
);
2435 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
2437 isl_pw_aff_free(pa1
);
2438 isl_pw_aff_free(pa2
);
2442 /* Compute the remainder of the integer division of "pa1" by "pa2"
2443 * with rounding towards zero.
2444 * "pa2" is assumed to be a piecewise constant.
2446 * In particular, return
2448 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
2451 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
2452 __isl_take isl_pw_aff
*pa2
)
2457 is_cst
= isl_pw_aff_is_cst(pa2
);
2461 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2462 "second argument should be a piecewise constant",
2464 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
2465 res
= isl_pw_aff_mul(pa2
, res
);
2466 res
= isl_pw_aff_sub(pa1
, res
);
2469 isl_pw_aff_free(pa1
);
2470 isl_pw_aff_free(pa2
);
2474 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2475 __isl_take isl_pw_aff
*pwaff2
)
2480 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2481 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2482 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
2483 isl_pw_aff_copy(pwaff2
));
2484 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
2485 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
2488 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2489 __isl_take isl_pw_aff
*pwaff2
)
2491 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
2494 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2495 __isl_take isl_pw_aff
*pwaff2
)
2500 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2501 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2502 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
2503 isl_pw_aff_copy(pwaff2
));
2504 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
2505 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
2508 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2509 __isl_take isl_pw_aff
*pwaff2
)
2511 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
2514 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
2515 __isl_take isl_pw_aff_list
*list
,
2516 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2517 __isl_take isl_pw_aff
*pwaff2
))
2526 ctx
= isl_pw_aff_list_get_ctx(list
);
2528 isl_die(ctx
, isl_error_invalid
,
2529 "list should contain at least one element",
2530 return isl_pw_aff_list_free(list
));
2532 res
= isl_pw_aff_copy(list
->p
[0]);
2533 for (i
= 1; i
< list
->n
; ++i
)
2534 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
2536 isl_pw_aff_list_free(list
);
2540 /* Return an isl_pw_aff that maps each element in the intersection of the
2541 * domains of the elements of list to the minimal corresponding affine
2544 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
2546 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
2549 /* Return an isl_pw_aff that maps each element in the intersection of the
2550 * domains of the elements of list to the maximal corresponding affine
2553 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
2555 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
2558 /* Mark the domains of "pwaff" as rational.
2560 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__isl_take isl_pw_aff
*pwaff
)
2564 pwaff
= isl_pw_aff_cow(pwaff
);
2570 for (i
= 0; i
< pwaff
->n
; ++i
) {
2571 pwaff
->p
[i
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
2572 if (!pwaff
->p
[i
].set
)
2573 return isl_pw_aff_free(pwaff
);
2579 /* Mark the domains of the elements of "list" as rational.
2581 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
2582 __isl_take isl_pw_aff_list
*list
)
2591 for (i
= 0; i
< list
->n
; ++i
) {
2594 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
2595 pa
= isl_pw_aff_set_rational(pa
);
2596 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
2605 #include <isl_multi_templ.c>
2607 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2610 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
2611 __isl_take isl_multi_aff
*ma
)
2613 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
2614 return isl_pw_multi_aff_alloc(dom
, ma
);
2617 /* Create a piecewise multi-affine expression in the given space that maps each
2618 * input dimension to the corresponding output dimension.
2620 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
2621 __isl_take isl_space
*space
)
2623 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
2626 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*maff1
,
2627 __isl_take isl_multi_aff
*maff2
)
2632 maff1
= isl_multi_aff_cow(maff1
);
2633 if (!maff1
|| !maff2
)
2636 ctx
= isl_multi_aff_get_ctx(maff1
);
2637 if (!isl_space_is_equal(maff1
->space
, maff2
->space
))
2638 isl_die(ctx
, isl_error_invalid
,
2639 "spaces don't match", goto error
);
2641 for (i
= 0; i
< maff1
->n
; ++i
) {
2642 maff1
->p
[i
] = isl_aff_add(maff1
->p
[i
],
2643 isl_aff_copy(maff2
->p
[i
]));
2648 isl_multi_aff_free(maff2
);
2651 isl_multi_aff_free(maff1
);
2652 isl_multi_aff_free(maff2
);
2656 /* Given two multi-affine expressions A -> B and C -> D,
2657 * construct a multi-affine expression [A -> C] -> [B -> D].
2659 __isl_give isl_multi_aff
*isl_multi_aff_product(
2660 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
2666 int in1
, in2
, out1
, out2
;
2668 in1
= isl_multi_aff_dim(ma1
, isl_dim_in
);
2669 in2
= isl_multi_aff_dim(ma2
, isl_dim_in
);
2670 out1
= isl_multi_aff_dim(ma1
, isl_dim_out
);
2671 out2
= isl_multi_aff_dim(ma2
, isl_dim_out
);
2672 space
= isl_space_product(isl_multi_aff_get_space(ma1
),
2673 isl_multi_aff_get_space(ma2
));
2674 res
= isl_multi_aff_alloc(isl_space_copy(space
));
2675 space
= isl_space_domain(space
);
2677 for (i
= 0; i
< out1
; ++i
) {
2678 aff
= isl_multi_aff_get_aff(ma1
, i
);
2679 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, in1
, in2
);
2680 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
2681 res
= isl_multi_aff_set_aff(res
, i
, aff
);
2684 for (i
= 0; i
< out2
; ++i
) {
2685 aff
= isl_multi_aff_get_aff(ma2
, i
);
2686 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, 0, in1
);
2687 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
2688 res
= isl_multi_aff_set_aff(res
, out1
+ i
, aff
);
2691 isl_space_free(space
);
2692 isl_multi_aff_free(ma1
);
2693 isl_multi_aff_free(ma2
);
2697 /* Exploit the equalities in "eq" to simplify the affine expressions.
2699 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
2700 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
2704 maff
= isl_multi_aff_cow(maff
);
2708 for (i
= 0; i
< maff
->n
; ++i
) {
2709 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
2710 isl_basic_set_copy(eq
));
2715 isl_basic_set_free(eq
);
2718 isl_basic_set_free(eq
);
2719 isl_multi_aff_free(maff
);
2723 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
2728 maff
= isl_multi_aff_cow(maff
);
2732 for (i
= 0; i
< maff
->n
; ++i
) {
2733 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
2735 return isl_multi_aff_free(maff
);
2741 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
2742 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
2744 maff1
= isl_multi_aff_add(maff1
, maff2
);
2745 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
2749 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
2757 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff
*maff1
,
2758 __isl_keep isl_multi_aff
*maff2
)
2763 if (!maff1
|| !maff2
)
2765 if (maff1
->n
!= maff2
->n
)
2767 equal
= isl_space_is_equal(maff1
->space
, maff2
->space
);
2768 if (equal
< 0 || !equal
)
2771 for (i
= 0; i
< maff1
->n
; ++i
) {
2772 equal
= isl_aff_plain_is_equal(maff1
->p
[i
], maff2
->p
[i
]);
2773 if (equal
< 0 || !equal
)
2780 /* Return the set of domain elements where "ma1" is lexicographically
2781 * smaller than or equal to "ma2".
2783 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
2784 __isl_take isl_multi_aff
*ma2
)
2786 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
2789 /* Return the set of domain elements where "ma1" is lexicographically
2790 * greater than or equal to "ma2".
2792 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
2793 __isl_take isl_multi_aff
*ma2
)
2796 isl_map
*map1
, *map2
;
2799 map1
= isl_map_from_multi_aff(ma1
);
2800 map2
= isl_map_from_multi_aff(ma2
);
2801 map
= isl_map_range_product(map1
, map2
);
2802 space
= isl_space_range(isl_map_get_space(map
));
2803 space
= isl_space_domain(isl_space_unwrap(space
));
2804 ge
= isl_map_lex_ge(space
);
2805 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
2807 return isl_map_domain(map
);
2811 #define PW isl_pw_multi_aff
2813 #define EL isl_multi_aff
2815 #define EL_IS_ZERO is_empty
2819 #define IS_ZERO is_empty
2822 #undef DEFAULT_IS_ZERO
2823 #define DEFAULT_IS_ZERO 0
2828 #define NO_INVOLVES_DIMS
2829 #define NO_MOVE_DIMS
2830 #define NO_INSERT_DIMS
2834 #include <isl_pw_templ.c>
2837 #define UNION isl_union_pw_multi_aff
2839 #define PART isl_pw_multi_aff
2841 #define PARTS pw_multi_aff
2842 #define ALIGN_DOMAIN
2846 #include <isl_union_templ.c>
2848 /* Given a function "cmp" that returns the set of elements where
2849 * "ma1" is "better" than "ma2", return the intersection of this
2850 * set with "dom1" and "dom2".
2852 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
2853 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
2854 __isl_keep isl_multi_aff
*ma2
,
2855 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
2856 __isl_take isl_multi_aff
*ma2
))
2862 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
2863 is_empty
= isl_set_plain_is_empty(common
);
2864 if (is_empty
>= 0 && is_empty
)
2867 return isl_set_free(common
);
2868 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
2869 better
= isl_set_intersect(common
, better
);
2874 /* Given a function "cmp" that returns the set of elements where
2875 * "ma1" is "better" than "ma2", return a piecewise multi affine
2876 * expression defined on the union of the definition domains
2877 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
2878 * "pma2" on each cell. If only one of the two input functions
2879 * is defined on a given cell, then it is considered the best.
2881 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
2882 __isl_take isl_pw_multi_aff
*pma1
,
2883 __isl_take isl_pw_multi_aff
*pma2
,
2884 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
2885 __isl_take isl_multi_aff
*ma2
))
2888 isl_pw_multi_aff
*res
= NULL
;
2890 isl_set
*set
= NULL
;
2895 ctx
= isl_space_get_ctx(pma1
->dim
);
2896 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
2897 isl_die(ctx
, isl_error_invalid
,
2898 "arguments should live in the same space", goto error
);
2900 if (isl_pw_multi_aff_is_empty(pma1
)) {
2901 isl_pw_multi_aff_free(pma1
);
2905 if (isl_pw_multi_aff_is_empty(pma2
)) {
2906 isl_pw_multi_aff_free(pma2
);
2910 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
2911 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
2913 for (i
= 0; i
< pma1
->n
; ++i
) {
2914 set
= isl_set_copy(pma1
->p
[i
].set
);
2915 for (j
= 0; j
< pma2
->n
; ++j
) {
2919 better
= shared_and_better(pma2
->p
[j
].set
,
2920 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
2921 pma1
->p
[i
].maff
, cmp
);
2922 is_empty
= isl_set_plain_is_empty(better
);
2923 if (is_empty
< 0 || is_empty
) {
2924 isl_set_free(better
);
2929 set
= isl_set_subtract(set
, isl_set_copy(better
));
2931 res
= isl_pw_multi_aff_add_piece(res
, better
,
2932 isl_multi_aff_copy(pma2
->p
[j
].maff
));
2934 res
= isl_pw_multi_aff_add_piece(res
, set
,
2935 isl_multi_aff_copy(pma1
->p
[i
].maff
));
2938 for (j
= 0; j
< pma2
->n
; ++j
) {
2939 set
= isl_set_copy(pma2
->p
[j
].set
);
2940 for (i
= 0; i
< pma1
->n
; ++i
)
2941 set
= isl_set_subtract(set
,
2942 isl_set_copy(pma1
->p
[i
].set
));
2943 res
= isl_pw_multi_aff_add_piece(res
, set
,
2944 isl_multi_aff_copy(pma2
->p
[j
].maff
));
2947 isl_pw_multi_aff_free(pma1
);
2948 isl_pw_multi_aff_free(pma2
);
2952 isl_pw_multi_aff_free(pma1
);
2953 isl_pw_multi_aff_free(pma2
);
2955 return isl_pw_multi_aff_free(res
);
2958 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
2959 __isl_take isl_pw_multi_aff
*pma1
,
2960 __isl_take isl_pw_multi_aff
*pma2
)
2962 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
2965 /* Given two piecewise multi affine expressions, return a piecewise
2966 * multi-affine expression defined on the union of the definition domains
2967 * of the inputs that is equal to the lexicographic maximum of the two
2968 * inputs on each cell. If only one of the two inputs is defined on
2969 * a given cell, then it is considered to be the maximum.
2971 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
2972 __isl_take isl_pw_multi_aff
*pma1
,
2973 __isl_take isl_pw_multi_aff
*pma2
)
2975 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
2976 &pw_multi_aff_union_lexmax
);
2979 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
2980 __isl_take isl_pw_multi_aff
*pma1
,
2981 __isl_take isl_pw_multi_aff
*pma2
)
2983 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
2986 /* Given two piecewise multi affine expressions, return a piecewise
2987 * multi-affine expression defined on the union of the definition domains
2988 * of the inputs that is equal to the lexicographic minimum of the two
2989 * inputs on each cell. If only one of the two inputs is defined on
2990 * a given cell, then it is considered to be the minimum.
2992 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
2993 __isl_take isl_pw_multi_aff
*pma1
,
2994 __isl_take isl_pw_multi_aff
*pma2
)
2996 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
2997 &pw_multi_aff_union_lexmin
);
3000 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
3001 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3003 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
3004 &isl_multi_aff_add
);
3007 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
3008 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3010 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3014 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
3015 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3017 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
3020 /* Given two piecewise multi-affine expressions A -> B and C -> D,
3021 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
3023 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
3024 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3028 isl_pw_multi_aff
*res
;
3033 n
= pma1
->n
* pma2
->n
;
3034 space
= isl_space_product(isl_space_copy(pma1
->dim
),
3035 isl_space_copy(pma2
->dim
));
3036 res
= isl_pw_multi_aff_alloc_size(space
, n
);
3038 for (i
= 0; i
< pma1
->n
; ++i
) {
3039 for (j
= 0; j
< pma2
->n
; ++j
) {
3043 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
3044 isl_set_copy(pma2
->p
[j
].set
));
3045 ma
= isl_multi_aff_product(
3046 isl_multi_aff_copy(pma1
->p
[i
].maff
),
3047 isl_multi_aff_copy(pma2
->p
[i
].maff
));
3048 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
3052 isl_pw_multi_aff_free(pma1
);
3053 isl_pw_multi_aff_free(pma2
);
3056 isl_pw_multi_aff_free(pma1
);
3057 isl_pw_multi_aff_free(pma2
);
3061 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
3062 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3064 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3065 &pw_multi_aff_product
);
3068 /* Construct a map mapping the domain of the piecewise multi-affine expression
3069 * to its range, with each dimension in the range equated to the
3070 * corresponding affine expression on its cell.
3072 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3080 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
3082 for (i
= 0; i
< pma
->n
; ++i
) {
3083 isl_multi_aff
*maff
;
3084 isl_basic_map
*bmap
;
3087 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
3088 bmap
= isl_basic_map_from_multi_aff(maff
);
3089 map_i
= isl_map_from_basic_map(bmap
);
3090 map_i
= isl_map_intersect_domain(map_i
,
3091 isl_set_copy(pma
->p
[i
].set
));
3092 map
= isl_map_union_disjoint(map
, map_i
);
3095 isl_pw_multi_aff_free(pma
);
3099 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3104 if (!isl_space_is_set(pma
->dim
))
3105 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
3106 "isl_pw_multi_aff cannot be converted into an isl_set",
3107 return isl_pw_multi_aff_free(pma
));
3109 return isl_map_from_pw_multi_aff(pma
);
3112 /* Given a basic map with a single output dimension that is defined
3113 * in terms of the parameters and input dimensions using an equality,
3114 * extract an isl_aff that expresses the output dimension in terms
3115 * of the parameters and input dimensions.
3117 * Since some applications expect the result of isl_pw_multi_aff_from_map
3118 * to only contain integer affine expressions, we compute the floor
3119 * of the expression before returning.
3121 * This function shares some similarities with
3122 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
3124 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
3125 __isl_take isl_basic_map
*bmap
)
3130 isl_local_space
*ls
;
3135 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
3136 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3137 "basic map should have a single output dimension",
3139 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
3140 total
= isl_basic_map_total_dim(bmap
);
3141 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
3142 if (isl_int_is_zero(bmap
->eq
[i
][offset
]))
3144 if (isl_seq_first_non_zero(bmap
->eq
[i
] + offset
+ 1,
3145 1 + total
- (offset
+ 1)) != -1)
3149 if (i
>= bmap
->n_eq
)
3150 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3151 "unable to find suitable equality", goto error
);
3152 ls
= isl_basic_map_get_local_space(bmap
);
3153 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
3156 if (isl_int_is_neg(bmap
->eq
[i
][offset
]))
3157 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3159 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3160 isl_seq_clr(aff
->v
->el
+ 1 + offset
, aff
->v
->size
- (1 + offset
));
3161 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[i
][offset
]);
3162 isl_basic_map_free(bmap
);
3164 aff
= isl_aff_remove_unused_divs(aff
);
3165 aff
= isl_aff_floor(aff
);
3168 isl_basic_map_free(bmap
);
3172 /* Given a basic map where each output dimension is defined
3173 * in terms of the parameters and input dimensions using an equality,
3174 * extract an isl_multi_aff that expresses the output dimensions in terms
3175 * of the parameters and input dimensions.
3177 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
3178 __isl_take isl_basic_map
*bmap
)
3187 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
3188 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
3190 for (i
= 0; i
< n_out
; ++i
) {
3191 isl_basic_map
*bmap_i
;
3194 bmap_i
= isl_basic_map_copy(bmap
);
3195 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
3196 i
+ 1, n_out
- (1 + i
));
3197 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
3198 aff
= extract_isl_aff_from_basic_map(bmap_i
);
3199 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3202 isl_basic_map_free(bmap
);
3207 /* Create an isl_pw_multi_aff that is equivalent to
3208 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
3209 * The given basic map is such that each output dimension is defined
3210 * in terms of the parameters and input dimensions using an equality.
3212 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
3213 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
3217 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
3218 return isl_pw_multi_aff_alloc(domain
, ma
);
3221 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3222 * This obviously only works if the input "map" is single-valued.
3223 * If so, we compute the lexicographic minimum of the image in the form
3224 * of an isl_pw_multi_aff. Since the image is unique, it is equal
3225 * to its lexicographic minimum.
3226 * If the input is not single-valued, we produce an error.
3228 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
3229 __isl_take isl_map
*map
)
3233 isl_pw_multi_aff
*pma
;
3235 sv
= isl_map_is_single_valued(map
);
3239 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
3240 "map is not single-valued", goto error
);
3241 map
= isl_map_make_disjoint(map
);
3245 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
3247 for (i
= 0; i
< map
->n
; ++i
) {
3248 isl_pw_multi_aff
*pma_i
;
3249 isl_basic_map
*bmap
;
3250 bmap
= isl_basic_map_copy(map
->p
[i
]);
3251 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
3252 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
3262 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3263 * taking into account that the output dimension at position "d"
3264 * can be represented as
3266 * x = floor((e(...) + c1) / m)
3268 * given that constraint "i" is of the form
3270 * e(...) + c1 - m x >= 0
3273 * Let "map" be of the form
3277 * We construct a mapping
3279 * A -> [A -> x = floor(...)]
3281 * apply that to the map, obtaining
3283 * [A -> x = floor(...)] -> B
3285 * and equate dimension "d" to x.
3286 * We then compute a isl_pw_multi_aff representation of the resulting map
3287 * and plug in the mapping above.
3289 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
3290 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
3294 isl_local_space
*ls
;
3302 isl_pw_multi_aff
*pma
;
3305 is_set
= isl_map_is_set(map
);
3307 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3308 ctx
= isl_map_get_ctx(map
);
3309 space
= isl_space_domain(isl_map_get_space(map
));
3310 n_in
= isl_space_dim(space
, isl_dim_set
);
3311 n
= isl_space_dim(space
, isl_dim_all
);
3313 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
3315 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
3316 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
3318 isl_basic_map_free(hull
);
3320 ls
= isl_local_space_from_space(isl_space_copy(space
));
3321 aff
= isl_aff_alloc_vec(ls
, v
);
3322 aff
= isl_aff_floor(aff
);
3324 isl_space_free(space
);
3325 ma
= isl_multi_aff_from_aff(aff
);
3327 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
3328 ma
= isl_multi_aff_range_product(ma
,
3329 isl_multi_aff_from_aff(aff
));
3332 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
3333 map
= isl_map_apply_domain(map
, insert
);
3334 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
3335 pma
= isl_pw_multi_aff_from_map(map
);
3336 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
3341 /* Is constraint "c" of the form
3343 * e(...) + c1 - m x >= 0
3347 * -e(...) + c2 + m x >= 0
3349 * where m > 1 and e only depends on parameters and input dimemnsions?
3351 * "offset" is the offset of the output dimensions
3352 * "pos" is the position of output dimension x.
3354 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
3356 if (isl_int_is_zero(c
[offset
+ d
]))
3358 if (isl_int_is_one(c
[offset
+ d
]))
3360 if (isl_int_is_negone(c
[offset
+ d
]))
3362 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
3364 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
3365 total
- (offset
+ d
+ 1)) != -1)
3370 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3372 * As a special case, we first check if there is any pair of constraints,
3373 * shared by all the basic maps in "map" that force a given dimension
3374 * to be equal to the floor of some affine combination of the input dimensions.
3376 * In particular, if we can find two constraints
3378 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
3382 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
3384 * where m > 1 and e only depends on parameters and input dimemnsions,
3387 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
3389 * then we know that we can take
3391 * x = floor((e(...) + c1) / m)
3393 * without having to perform any computation.
3395 * Note that we know that
3399 * If c1 + c2 were 0, then we would have detected an equality during
3400 * simplification. If c1 + c2 were negative, then we would have detected
3403 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
3404 __isl_take isl_map
*map
)
3410 isl_basic_map
*hull
;
3412 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
3417 dim
= isl_map_dim(map
, isl_dim_out
);
3418 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3419 total
= 1 + isl_basic_map_total_dim(hull
);
3421 for (d
= 0; d
< dim
; ++d
) {
3422 for (i
= 0; i
< n
; ++i
) {
3423 if (!is_potential_div_constraint(hull
->ineq
[i
],
3426 for (j
= i
+ 1; j
< n
; ++j
) {
3427 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
3428 hull
->ineq
[j
] + 1, total
- 1))
3430 isl_int_add(sum
, hull
->ineq
[i
][0],
3432 if (isl_int_abs_lt(sum
,
3433 hull
->ineq
[i
][offset
+ d
]))
3440 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
3442 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
3446 isl_basic_map_free(hull
);
3447 return pw_multi_aff_from_map_base(map
);
3450 isl_basic_map_free(hull
);
3454 /* Given an affine expression
3456 * [A -> B] -> f(A,B)
3458 * construct an isl_multi_aff
3462 * such that dimension "d" in B' is set to "aff" and the remaining
3463 * dimensions are set equal to the corresponding dimensions in B.
3464 * "n_in" is the dimension of the space A.
3465 * "n_out" is the dimension of the space B.
3467 * If "is_set" is set, then the affine expression is of the form
3471 * and we construct an isl_multi_aff
3475 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
3476 unsigned n_in
, unsigned n_out
, int is_set
)
3480 isl_space
*space
, *space2
;
3481 isl_local_space
*ls
;
3483 space
= isl_aff_get_domain_space(aff
);
3484 ls
= isl_local_space_from_space(isl_space_copy(space
));
3485 space2
= isl_space_copy(space
);
3487 space2
= isl_space_range(isl_space_unwrap(space2
));
3488 space
= isl_space_map_from_domain_and_range(space
, space2
);
3489 ma
= isl_multi_aff_alloc(space
);
3490 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
3492 for (i
= 0; i
< n_out
; ++i
) {
3495 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3496 isl_dim_set
, n_in
+ i
);
3497 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3500 isl_local_space_free(ls
);
3505 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3506 * taking into account that the dimension at position "d" can be written as
3508 * x = m a + f(..) (1)
3510 * where m is equal to "gcd".
3511 * "i" is the index of the equality in "hull" that defines f(..).
3512 * In particular, the equality is of the form
3514 * f(..) - x + m g(existentials) = 0
3518 * -f(..) + x + m g(existentials) = 0
3520 * We basically plug (1) into "map", resulting in a map with "a"
3521 * in the range instead of "x". The corresponding isl_pw_multi_aff
3522 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
3524 * Specifically, given the input map
3528 * We first wrap it into a set
3532 * and define (1) on top of the corresponding space, resulting in "aff".
3533 * We use this to create an isl_multi_aff that maps the output position "d"
3534 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
3535 * We plug this into the wrapped map, unwrap the result and compute the
3536 * corresponding isl_pw_multi_aff.
3537 * The result is an expression
3545 * so that we can plug that into "aff", after extending the latter to
3551 * If "map" is actually a set, then there is no "A" space, meaning
3552 * that we do not need to perform any wrapping, and that the result
3553 * of the recursive call is of the form
3557 * which is plugged into a mapping of the form
3561 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
3562 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
3567 isl_local_space
*ls
;
3570 isl_pw_multi_aff
*pma
, *id
;
3576 is_set
= isl_map_is_set(map
);
3578 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
3579 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
3580 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
3585 set
= isl_map_wrap(map
);
3586 space
= isl_space_map_from_set(isl_set_get_space(set
));
3587 ma
= isl_multi_aff_identity(space
);
3588 ls
= isl_local_space_from_space(isl_set_get_space(set
));
3589 aff
= isl_aff_alloc(ls
);
3591 isl_int_set_si(aff
->v
->el
[0], 1);
3592 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
3593 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
3596 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
3598 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
3600 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
3601 set
= isl_set_preimage_multi_aff(set
, ma
);
3603 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
3608 map
= isl_set_unwrap(set
);
3609 pma
= isl_pw_multi_aff_from_map(set
);
3612 space
= isl_pw_multi_aff_get_domain_space(pma
);
3613 space
= isl_space_map_from_set(space
);
3614 id
= isl_pw_multi_aff_identity(space
);
3615 pma
= isl_pw_multi_aff_range_product(id
, pma
);
3617 id
= isl_pw_multi_aff_from_multi_aff(ma
);
3618 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
3620 isl_basic_map_free(hull
);
3624 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3626 * As a special case, we first check if all output dimensions are uniquely
3627 * defined in terms of the parameters and input dimensions over the entire
3628 * domain. If so, we extract the desired isl_pw_multi_aff directly
3629 * from the affine hull of "map" and its domain.
3631 * Otherwise, we check if any of the output dimensions is "strided".
3632 * That is, we check if can be written as
3636 * with m greater than 1, a some combination of existentiall quantified
3637 * variables and f and expression in the parameters and input dimensions.
3638 * If so, we remove the stride in pw_multi_aff_from_map_stride.
3640 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
3643 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
3647 isl_basic_map
*hull
;
3657 hull
= isl_map_affine_hull(isl_map_copy(map
));
3658 sv
= isl_basic_map_plain_is_single_valued(hull
);
3660 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
3662 hull
= isl_basic_map_free(hull
);
3666 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
3667 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
3670 isl_basic_map_free(hull
);
3671 return pw_multi_aff_from_map_check_div(map
);
3676 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
3677 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
3679 for (i
= 0; i
< n_out
; ++i
) {
3680 for (j
= 0; j
< hull
->n_eq
; ++j
) {
3681 isl_int
*eq
= hull
->eq
[j
];
3682 isl_pw_multi_aff
*res
;
3684 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
3685 !isl_int_is_negone(eq
[o_out
+ i
]))
3687 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
3689 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
3690 n_out
- (i
+ 1)) != -1)
3692 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
3693 if (isl_int_is_zero(gcd
))
3695 if (isl_int_is_one(gcd
))
3698 res
= pw_multi_aff_from_map_stride(map
, hull
,
3706 isl_basic_map_free(hull
);
3707 return pw_multi_aff_from_map_check_div(map
);
3713 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
3715 return isl_pw_multi_aff_from_map(set
);
3718 /* Return the piecewise affine expression "set ? 1 : 0".
3720 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
3723 isl_space
*space
= isl_set_get_space(set
);
3724 isl_local_space
*ls
= isl_local_space_from_space(space
);
3725 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
3726 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
3728 one
= isl_aff_add_constant_si(one
, 1);
3729 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
3730 set
= isl_set_complement(set
);
3731 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
3736 /* Plug in "subs" for dimension "type", "pos" of "aff".
3738 * Let i be the dimension to replace and let "subs" be of the form
3742 * and "aff" of the form
3748 * (a f + d g')/(m d)
3750 * where g' is the result of plugging in "subs" in each of the integer
3753 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
3754 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
3759 aff
= isl_aff_cow(aff
);
3761 return isl_aff_free(aff
);
3763 ctx
= isl_aff_get_ctx(aff
);
3764 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
3765 isl_die(ctx
, isl_error_invalid
,
3766 "spaces don't match", return isl_aff_free(aff
));
3767 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
3768 isl_die(ctx
, isl_error_unsupported
,
3769 "cannot handle divs yet", return isl_aff_free(aff
));
3771 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
3773 return isl_aff_free(aff
);
3775 aff
->v
= isl_vec_cow(aff
->v
);
3777 return isl_aff_free(aff
);
3779 pos
+= isl_local_space_offset(aff
->ls
, type
);
3782 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
3783 aff
->v
->size
, subs
->v
->size
, v
);
3789 /* Plug in "subs" for dimension "type", "pos" in each of the affine
3790 * expressions in "maff".
3792 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
3793 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
3794 __isl_keep isl_aff
*subs
)
3798 maff
= isl_multi_aff_cow(maff
);
3800 return isl_multi_aff_free(maff
);
3802 if (type
== isl_dim_in
)
3805 for (i
= 0; i
< maff
->n
; ++i
) {
3806 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
3808 return isl_multi_aff_free(maff
);
3814 /* Plug in "subs" for dimension "type", "pos" of "pma".
3816 * pma is of the form
3820 * while subs is of the form
3822 * v' = B_j(v) -> S_j
3824 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
3825 * has a contribution in the result, in particular
3827 * C_ij(S_j) -> M_i(S_j)
3829 * Note that plugging in S_j in C_ij may also result in an empty set
3830 * and this contribution should simply be discarded.
3832 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
3833 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
3834 __isl_keep isl_pw_aff
*subs
)
3837 isl_pw_multi_aff
*res
;
3840 return isl_pw_multi_aff_free(pma
);
3842 n
= pma
->n
* subs
->n
;
3843 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
3845 for (i
= 0; i
< pma
->n
; ++i
) {
3846 for (j
= 0; j
< subs
->n
; ++j
) {
3848 isl_multi_aff
*res_ij
;
3851 common
= isl_set_intersect(
3852 isl_set_copy(pma
->p
[i
].set
),
3853 isl_set_copy(subs
->p
[j
].set
));
3854 common
= isl_set_substitute(common
,
3855 type
, pos
, subs
->p
[j
].aff
);
3856 empty
= isl_set_plain_is_empty(common
);
3857 if (empty
< 0 || empty
) {
3858 isl_set_free(common
);
3864 res_ij
= isl_multi_aff_substitute(
3865 isl_multi_aff_copy(pma
->p
[i
].maff
),
3866 type
, pos
, subs
->p
[j
].aff
);
3868 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
3872 isl_pw_multi_aff_free(pma
);
3875 isl_pw_multi_aff_free(pma
);
3876 isl_pw_multi_aff_free(res
);
3880 /* Compute the preimage of the affine expression "src" under "ma"
3881 * and put the result in "dst". If "has_denom" is set (to one),
3882 * then "src" and "dst" have an extra initial denominator.
3883 * "n_div_ma" is the number of existentials in "ma"
3884 * "n_div_bset" is the number of existentials in "src"
3885 * The resulting "dst" (which is assumed to have been allocated by
3886 * the caller) contains coefficients for both sets of existentials,
3887 * first those in "ma" and then those in "src".
3888 * f, c1, c2 and g are temporary objects that have been initialized
3891 * Let src represent the expression
3893 * (a(p) + b x + c(divs))/d
3895 * and let ma represent the expressions
3897 * x_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
3899 * We start out with the following expression for dst:
3901 * (a(p) + 0 y + 0 divs' + f \sum_i b_i x_i + c(divs))/d
3903 * with the multiplication factor f initially equal to 1.
3904 * For each x_i that we substitute, we multiply the numerator
3905 * (and denominator) of dst by c_1 = m_i and add the numerator
3906 * of the x_i expression multiplied by c_2 = f b_i,
3907 * after removing the common factors of c_1 and c_2.
3908 * The multiplication factor f also needs to be multiplied by c_1
3909 * for the next x_j, j > i.
3911 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
3912 __isl_keep isl_multi_aff
*ma
, int n_div_ma
, int n_div_bset
,
3913 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
3916 int n_param
, n_in
, n_out
;
3919 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
3920 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
3921 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3923 o_div_bset
= has_denom
+ 1 + n_param
+ n_in
+ n_div_ma
;
3925 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
);
3926 isl_seq_clr(dst
+ has_denom
+ 1 + n_param
, n_in
+ n_div_ma
);
3927 isl_seq_cpy(dst
+ o_div_bset
,
3928 src
+ has_denom
+ 1 + n_param
+ n_out
, n_div_bset
);
3930 isl_int_set_si(f
, 1);
3932 for (i
= 0; i
< n_out
; ++i
) {
3933 if (isl_int_is_zero(src
[has_denom
+ 1 + n_param
+ i
]))
3935 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
3936 isl_int_mul(c2
, f
, src
[has_denom
+ 1 + n_param
+ i
]);
3937 isl_int_gcd(g
, c1
, c2
);
3938 isl_int_divexact(c1
, c1
, g
);
3939 isl_int_divexact(c2
, c2
, g
);
3941 isl_int_mul(f
, f
, c1
);
3942 isl_seq_combine(dst
+ has_denom
, c1
, dst
+ has_denom
,
3943 c2
, ma
->p
[i
]->v
->el
+ 1, ma
->p
[i
]->v
->size
- 1);
3944 isl_seq_scale(dst
+ o_div_bset
,
3945 dst
+ o_div_bset
, c1
, n_div_bset
);
3947 isl_int_mul(dst
[0], dst
[0], c1
);
3951 /* Compute the pullback of "aff" by the function represented by "ma".
3952 * In other words, plug in "ma" in "aff". The result is an affine expression
3953 * defined over the domain space of "ma".
3955 * If "aff" is represented by
3957 * (a(p) + b x + c(divs))/d
3959 * and ma is represented by
3961 * x = D(p) + F(y) + G(divs')
3963 * then the result is
3965 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
3967 * The divs in the local space of the input are similarly adjusted
3968 * through a call to isl_local_space_preimage_multi_aff.
3970 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
3971 __isl_take isl_multi_aff
*ma
)
3973 isl_aff
*res
= NULL
;
3974 isl_local_space
*ls
;
3975 int n_div_aff
, n_div_ma
;
3976 isl_int f
, c1
, c2
, g
;
3978 ma
= isl_multi_aff_align_divs(ma
);
3982 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
3983 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
3985 ls
= isl_aff_get_domain_local_space(aff
);
3986 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
3987 res
= isl_aff_alloc(ls
);
3996 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, n_div_ma
, n_div_aff
,
4005 isl_multi_aff_free(ma
);
4006 res
= isl_aff_normalize(res
);
4010 isl_multi_aff_free(ma
);
4015 /* Compute the pullback of "ma1" by the function represented by "ma2".
4016 * In other words, plug in "ma2" in "ma1".
4018 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
4019 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
4022 isl_space
*space
= NULL
;
4024 ma2
= isl_multi_aff_align_divs(ma2
);
4025 ma1
= isl_multi_aff_cow(ma1
);
4029 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
4030 isl_multi_aff_get_space(ma1
));
4032 for (i
= 0; i
< ma1
->n
; ++i
) {
4033 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
4034 isl_multi_aff_copy(ma2
));
4039 ma1
= isl_multi_aff_reset_space(ma1
, space
);
4040 isl_multi_aff_free(ma2
);
4043 isl_space_free(space
);
4044 isl_multi_aff_free(ma2
);
4045 isl_multi_aff_free(ma1
);
4049 /* Extend the local space of "dst" to include the divs
4050 * in the local space of "src".
4052 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
4053 __isl_keep isl_aff
*src
)
4061 return isl_aff_free(dst
);
4063 ctx
= isl_aff_get_ctx(src
);
4064 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
4065 isl_die(ctx
, isl_error_invalid
,
4066 "spaces don't match", goto error
);
4068 if (src
->ls
->div
->n_row
== 0)
4071 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
4072 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
4076 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
4077 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
4085 return isl_aff_free(dst
);
4088 /* Adjust the local spaces of the affine expressions in "maff"
4089 * such that they all have the save divs.
4091 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
4092 __isl_take isl_multi_aff
*maff
)
4100 maff
= isl_multi_aff_cow(maff
);
4104 for (i
= 1; i
< maff
->n
; ++i
)
4105 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
4106 for (i
= 1; i
< maff
->n
; ++i
) {
4107 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
4109 return isl_multi_aff_free(maff
);
4115 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
4117 aff
= isl_aff_cow(aff
);
4121 aff
->ls
= isl_local_space_lift(aff
->ls
);
4123 return isl_aff_free(aff
);
4128 /* Lift "maff" to a space with extra dimensions such that the result
4129 * has no more existentially quantified variables.
4130 * If "ls" is not NULL, then *ls is assigned the local space that lies
4131 * at the basis of the lifting applied to "maff".
4133 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
4134 __isl_give isl_local_space
**ls
)
4148 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
4149 *ls
= isl_local_space_from_space(space
);
4151 return isl_multi_aff_free(maff
);
4156 maff
= isl_multi_aff_cow(maff
);
4157 maff
= isl_multi_aff_align_divs(maff
);
4161 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
4162 space
= isl_multi_aff_get_space(maff
);
4163 space
= isl_space_lift(isl_space_domain(space
), n_div
);
4164 space
= isl_space_extend_domain_with_range(space
,
4165 isl_multi_aff_get_space(maff
));
4167 return isl_multi_aff_free(maff
);
4168 isl_space_free(maff
->space
);
4169 maff
->space
= space
;
4172 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
4174 return isl_multi_aff_free(maff
);
4177 for (i
= 0; i
< maff
->n
; ++i
) {
4178 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
4186 isl_local_space_free(*ls
);
4187 return isl_multi_aff_free(maff
);
4191 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
4193 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
4194 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
4204 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
4205 if (pos
< 0 || pos
>= n_out
)
4206 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4207 "index out of bounds", return NULL
);
4209 space
= isl_pw_multi_aff_get_space(pma
);
4210 space
= isl_space_drop_dims(space
, isl_dim_out
,
4211 pos
+ 1, n_out
- pos
- 1);
4212 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
4214 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
4215 for (i
= 0; i
< pma
->n
; ++i
) {
4217 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
4218 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
4224 /* Return an isl_pw_multi_aff with the given "set" as domain and
4225 * an unnamed zero-dimensional range.
4227 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
4228 __isl_take isl_set
*set
)
4233 space
= isl_set_get_space(set
);
4234 space
= isl_space_from_domain(space
);
4235 ma
= isl_multi_aff_zero(space
);
4236 return isl_pw_multi_aff_alloc(set
, ma
);
4239 /* Add an isl_pw_multi_aff with the given "set" as domain and
4240 * an unnamed zero-dimensional range to *user.
4242 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
4244 isl_union_pw_multi_aff
**upma
= user
;
4245 isl_pw_multi_aff
*pma
;
4247 pma
= isl_pw_multi_aff_from_domain(set
);
4248 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4253 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
4254 * an unnamed zero-dimensional range.
4256 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
4257 __isl_take isl_union_set
*uset
)
4260 isl_union_pw_multi_aff
*upma
;
4265 space
= isl_union_set_get_space(uset
);
4266 upma
= isl_union_pw_multi_aff_empty(space
);
4268 if (isl_union_set_foreach_set(uset
,
4269 &add_pw_multi_aff_from_domain
, &upma
) < 0)
4272 isl_union_set_free(uset
);
4275 isl_union_set_free(uset
);
4276 isl_union_pw_multi_aff_free(upma
);
4280 /* Convert "pma" to an isl_map and add it to *umap.
4282 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
4284 isl_union_map
**umap
= user
;
4287 map
= isl_map_from_pw_multi_aff(pma
);
4288 *umap
= isl_union_map_add_map(*umap
, map
);
4293 /* Construct a union map mapping the domain of the union
4294 * piecewise multi-affine expression to its range, with each dimension
4295 * in the range equated to the corresponding affine expression on its cell.
4297 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
4298 __isl_take isl_union_pw_multi_aff
*upma
)
4301 isl_union_map
*umap
;
4306 space
= isl_union_pw_multi_aff_get_space(upma
);
4307 umap
= isl_union_map_empty(space
);
4309 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4310 &map_from_pw_multi_aff
, &umap
) < 0)
4313 isl_union_pw_multi_aff_free(upma
);
4316 isl_union_pw_multi_aff_free(upma
);
4317 isl_union_map_free(umap
);
4321 /* Local data for bin_entry and the callback "fn".
4323 struct isl_union_pw_multi_aff_bin_data
{
4324 isl_union_pw_multi_aff
*upma2
;
4325 isl_union_pw_multi_aff
*res
;
4326 isl_pw_multi_aff
*pma
;
4327 int (*fn
)(void **entry
, void *user
);
4330 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
4331 * and call data->fn for each isl_pw_multi_aff in data->upma2.
4333 static int bin_entry(void **entry
, void *user
)
4335 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4336 isl_pw_multi_aff
*pma
= *entry
;
4339 if (isl_hash_table_foreach(data
->upma2
->dim
->ctx
, &data
->upma2
->table
,
4340 data
->fn
, data
) < 0)
4346 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
4347 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
4348 * passed as user field) and the isl_pw_multi_aff from upma2 is available
4349 * as *entry. The callback should adjust data->res if desired.
4351 static __isl_give isl_union_pw_multi_aff
*bin_op(
4352 __isl_take isl_union_pw_multi_aff
*upma1
,
4353 __isl_take isl_union_pw_multi_aff
*upma2
,
4354 int (*fn
)(void **entry
, void *user
))
4357 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
4359 space
= isl_union_pw_multi_aff_get_space(upma2
);
4360 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
4361 space
= isl_union_pw_multi_aff_get_space(upma1
);
4362 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
4364 if (!upma1
|| !upma2
)
4368 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->dim
),
4370 if (isl_hash_table_foreach(upma1
->dim
->ctx
, &upma1
->table
,
4371 &bin_entry
, &data
) < 0)
4374 isl_union_pw_multi_aff_free(upma1
);
4375 isl_union_pw_multi_aff_free(upma2
);
4378 isl_union_pw_multi_aff_free(upma1
);
4379 isl_union_pw_multi_aff_free(upma2
);
4380 isl_union_pw_multi_aff_free(data
.res
);
4384 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4385 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4387 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
4388 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4392 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4393 isl_pw_multi_aff_get_space(pma2
));
4394 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4395 &isl_multi_aff_range_product
);
4398 /* Given two isl_pw_multi_affs A -> B and C -> D,
4399 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4401 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
4402 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4404 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4405 &pw_multi_aff_range_product
);
4408 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4409 * construct an isl_pw_multi_aff (A * C) -> (B, D).
4411 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
4412 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4416 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4417 isl_pw_multi_aff_get_space(pma2
));
4418 space
= isl_space_flatten_range(space
);
4419 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4420 &isl_multi_aff_flat_range_product
);
4423 /* Given two isl_pw_multi_affs A -> B and C -> D,
4424 * construct an isl_pw_multi_aff (A * C) -> (B, D).
4426 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
4427 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4429 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4430 &pw_multi_aff_flat_range_product
);
4433 /* If data->pma and *entry have the same domain space, then compute
4434 * their flat range product and the result to data->res.
4436 static int flat_range_product_entry(void **entry
, void *user
)
4438 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4439 isl_pw_multi_aff
*pma2
= *entry
;
4441 if (!isl_space_tuple_match(data
->pma
->dim
, isl_dim_in
,
4442 pma2
->dim
, isl_dim_in
))
4445 pma2
= isl_pw_multi_aff_flat_range_product(
4446 isl_pw_multi_aff_copy(data
->pma
),
4447 isl_pw_multi_aff_copy(pma2
));
4449 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
4454 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
4455 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
4457 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
4458 __isl_take isl_union_pw_multi_aff
*upma1
,
4459 __isl_take isl_union_pw_multi_aff
*upma2
)
4461 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
4464 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4465 * The parameters are assumed to have been aligned.
4467 * The implementation essentially performs an isl_pw_*_on_shared_domain,
4468 * except that it works on two different isl_pw_* types.
4470 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
4471 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
4472 __isl_take isl_pw_aff
*pa
)
4475 isl_pw_multi_aff
*res
= NULL
;
4480 if (!isl_space_tuple_match(pma
->dim
, isl_dim_in
, pa
->dim
, isl_dim_in
))
4481 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4482 "domains don't match", goto error
);
4483 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
4484 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4485 "index out of bounds", goto error
);
4488 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
4490 for (i
= 0; i
< pma
->n
; ++i
) {
4491 for (j
= 0; j
< pa
->n
; ++j
) {
4493 isl_multi_aff
*res_ij
;
4496 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
4497 isl_set_copy(pa
->p
[j
].set
));
4498 empty
= isl_set_plain_is_empty(common
);
4499 if (empty
< 0 || empty
) {
4500 isl_set_free(common
);
4506 res_ij
= isl_multi_aff_set_aff(
4507 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
4508 isl_aff_copy(pa
->p
[j
].aff
));
4509 res_ij
= isl_multi_aff_gist(res_ij
,
4510 isl_set_copy(common
));
4512 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
4516 isl_pw_multi_aff_free(pma
);
4517 isl_pw_aff_free(pa
);
4520 isl_pw_multi_aff_free(pma
);
4521 isl_pw_aff_free(pa
);
4522 return isl_pw_multi_aff_free(res
);
4525 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4527 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
4528 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
4529 __isl_take isl_pw_aff
*pa
)
4533 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
4534 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
4535 if (!isl_space_has_named_params(pma
->dim
) ||
4536 !isl_space_has_named_params(pa
->dim
))
4537 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4538 "unaligned unnamed parameters", goto error
);
4539 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
4540 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
4541 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
4543 isl_pw_multi_aff_free(pma
);
4544 isl_pw_aff_free(pa
);
4551 #include <isl_multi_templ.c>