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);
963 * aff mod m = aff - m * floor(aff/m)
965 __isl_give isl_aff
*isl_aff_mod(__isl_take isl_aff
*aff
, isl_int m
)
969 res
= isl_aff_copy(aff
);
970 aff
= isl_aff_scale_down(aff
, m
);
971 aff
= isl_aff_floor(aff
);
972 aff
= isl_aff_scale(aff
, m
);
973 res
= isl_aff_sub(res
, aff
);
980 * pwaff mod m = pwaff - m * floor(pwaff/m)
982 __isl_give isl_pw_aff
*isl_pw_aff_mod(__isl_take isl_pw_aff
*pwaff
, isl_int m
)
986 res
= isl_pw_aff_copy(pwaff
);
987 pwaff
= isl_pw_aff_scale_down(pwaff
, m
);
988 pwaff
= isl_pw_aff_floor(pwaff
);
989 pwaff
= isl_pw_aff_scale(pwaff
, m
);
990 res
= isl_pw_aff_sub(res
, pwaff
);
995 /* Given f, return ceil(f).
996 * If f is an integer expression, then just return f.
997 * Otherwise, let f be the expression
1003 * floor((e + m - 1)/m)
1005 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
1010 if (isl_int_is_one(aff
->v
->el
[0]))
1013 aff
= isl_aff_cow(aff
);
1016 aff
->v
= isl_vec_cow(aff
->v
);
1018 return isl_aff_free(aff
);
1020 isl_int_add(aff
->v
->el
[1], aff
->v
->el
[1], aff
->v
->el
[0]);
1021 isl_int_sub_ui(aff
->v
->el
[1], aff
->v
->el
[1], 1);
1022 aff
= isl_aff_floor(aff
);
1027 /* Apply the expansion computed by isl_merge_divs.
1028 * The expansion itself is given by "exp" while the resulting
1029 * list of divs is given by "div".
1031 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
1032 __isl_take isl_mat
*div
, int *exp
)
1039 aff
= isl_aff_cow(aff
);
1043 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1044 new_n_div
= isl_mat_rows(div
);
1045 if (new_n_div
< old_n_div
)
1046 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
1047 "not an expansion", goto error
);
1049 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
1053 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
1055 for (i
= new_n_div
- 1; i
>= 0; --i
) {
1056 if (j
>= 0 && exp
[j
] == i
) {
1058 isl_int_swap(aff
->v
->el
[offset
+ i
],
1059 aff
->v
->el
[offset
+ j
]);
1062 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
1065 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
1076 /* Add two affine expressions that live in the same local space.
1078 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
1079 __isl_take isl_aff
*aff2
)
1083 aff1
= isl_aff_cow(aff1
);
1087 aff1
->v
= isl_vec_cow(aff1
->v
);
1093 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
1094 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1095 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
1096 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
1097 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
1098 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1099 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
1111 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
1112 __isl_take isl_aff
*aff2
)
1122 ctx
= isl_aff_get_ctx(aff1
);
1123 if (!isl_space_is_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
1124 isl_die(ctx
, isl_error_invalid
,
1125 "spaces don't match", goto error
);
1127 if (aff1
->ls
->div
->n_row
== 0 && aff2
->ls
->div
->n_row
== 0)
1128 return add_expanded(aff1
, aff2
);
1130 exp1
= isl_alloc_array(ctx
, int, aff1
->ls
->div
->n_row
);
1131 exp2
= isl_alloc_array(ctx
, int, aff2
->ls
->div
->n_row
);
1135 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
1136 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
1137 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
1141 return add_expanded(aff1
, aff2
);
1150 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
1151 __isl_take isl_aff
*aff2
)
1153 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
1156 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
1160 if (isl_int_is_one(f
))
1163 aff
= isl_aff_cow(aff
);
1166 aff
->v
= isl_vec_cow(aff
->v
);
1168 return isl_aff_free(aff
);
1171 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
1172 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1173 isl_int_divexact(gcd
, f
, gcd
);
1174 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1180 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
1184 if (isl_int_is_one(f
))
1187 aff
= isl_aff_cow(aff
);
1191 if (isl_int_is_zero(f
))
1192 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1193 "cannot scale down by zero", return isl_aff_free(aff
));
1195 aff
->v
= isl_vec_cow(aff
->v
);
1197 return isl_aff_free(aff
);
1200 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
1201 isl_int_gcd(gcd
, gcd
, f
);
1202 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1203 isl_int_divexact(gcd
, f
, gcd
);
1204 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1210 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
1218 isl_int_set_ui(v
, f
);
1219 aff
= isl_aff_scale_down(aff
, v
);
1225 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
1226 enum isl_dim_type type
, unsigned pos
, const char *s
)
1228 aff
= isl_aff_cow(aff
);
1231 if (type
== isl_dim_out
)
1232 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1233 "cannot set name of output/set dimension",
1234 return isl_aff_free(aff
));
1235 if (type
== isl_dim_in
)
1237 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
1239 return isl_aff_free(aff
);
1244 __isl_give isl_aff
*isl_aff_set_dim_id(__isl_take isl_aff
*aff
,
1245 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1247 aff
= isl_aff_cow(aff
);
1249 return isl_id_free(id
);
1250 if (type
== isl_dim_out
)
1251 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1252 "cannot set name of output/set dimension",
1254 if (type
== isl_dim_in
)
1256 aff
->ls
= isl_local_space_set_dim_id(aff
->ls
, type
, pos
, id
);
1258 return isl_aff_free(aff
);
1267 /* Exploit the equalities in "eq" to simplify the affine expression
1268 * and the expressions of the integer divisions in the local space.
1269 * The integer divisions in this local space are assumed to appear
1270 * as regular dimensions in "eq".
1272 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
1273 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1281 if (eq
->n_eq
== 0) {
1282 isl_basic_set_free(eq
);
1286 aff
= isl_aff_cow(aff
);
1290 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
1291 isl_basic_set_copy(eq
));
1292 aff
->v
= isl_vec_cow(aff
->v
);
1293 if (!aff
->ls
|| !aff
->v
)
1296 total
= 1 + isl_space_dim(eq
->dim
, isl_dim_all
);
1298 for (i
= 0; i
< eq
->n_eq
; ++i
) {
1299 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
1300 if (j
< 0 || j
== 0 || j
>= total
)
1303 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
1307 isl_basic_set_free(eq
);
1308 aff
= isl_aff_normalize(aff
);
1311 isl_basic_set_free(eq
);
1316 /* Exploit the equalities in "eq" to simplify the affine expression
1317 * and the expressions of the integer divisions in the local space.
1319 static __isl_give isl_aff
*isl_aff_substitute_equalities(
1320 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1326 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1328 eq
= isl_basic_set_add(eq
, isl_dim_set
, n_div
);
1329 return isl_aff_substitute_equalities_lifted(aff
, eq
);
1331 isl_basic_set_free(eq
);
1336 /* Look for equalities among the variables shared by context and aff
1337 * and the integer divisions of aff, if any.
1338 * The equalities are then used to eliminate coefficients and/or integer
1339 * divisions from aff.
1341 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
1342 __isl_take isl_set
*context
)
1344 isl_basic_set
*hull
;
1349 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1351 isl_basic_set
*bset
;
1352 isl_local_space
*ls
;
1353 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
1354 ls
= isl_aff_get_domain_local_space(aff
);
1355 bset
= isl_basic_set_from_local_space(ls
);
1356 bset
= isl_basic_set_lift(bset
);
1357 bset
= isl_basic_set_flatten(bset
);
1358 context
= isl_set_intersect(context
,
1359 isl_set_from_basic_set(bset
));
1362 hull
= isl_set_affine_hull(context
);
1363 return isl_aff_substitute_equalities_lifted(aff
, hull
);
1366 isl_set_free(context
);
1370 __isl_give isl_aff
*isl_aff_gist_params(__isl_take isl_aff
*aff
,
1371 __isl_take isl_set
*context
)
1373 isl_set
*dom_context
= isl_set_universe(isl_aff_get_domain_space(aff
));
1374 dom_context
= isl_set_intersect_params(dom_context
, context
);
1375 return isl_aff_gist(aff
, dom_context
);
1378 /* Return a basic set containing those elements in the space
1379 * of aff where it is non-negative.
1380 * If "rational" is set, then return a rational basic set.
1382 static __isl_give isl_basic_set
*aff_nonneg_basic_set(
1383 __isl_take isl_aff
*aff
, int rational
)
1385 isl_constraint
*ineq
;
1386 isl_basic_set
*bset
;
1388 ineq
= isl_inequality_from_aff(aff
);
1390 bset
= isl_basic_set_from_constraint(ineq
);
1392 bset
= isl_basic_set_set_rational(bset
);
1393 bset
= isl_basic_set_simplify(bset
);
1397 /* Return a basic set containing those elements in the space
1398 * of aff where it is non-negative.
1400 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
1402 return aff_nonneg_basic_set(aff
, 0);
1405 /* Return a basic set containing those elements in the domain space
1406 * of aff where it is negative.
1408 __isl_give isl_basic_set
*isl_aff_neg_basic_set(__isl_take isl_aff
*aff
)
1410 aff
= isl_aff_neg(aff
);
1411 aff
= isl_aff_add_constant_num_si(aff
, -1);
1412 return isl_aff_nonneg_basic_set(aff
);
1415 /* Return a basic set containing those elements in the space
1416 * of aff where it is zero.
1417 * If "rational" is set, then return a rational basic set.
1419 static __isl_give isl_basic_set
*aff_zero_basic_set(__isl_take isl_aff
*aff
,
1422 isl_constraint
*ineq
;
1423 isl_basic_set
*bset
;
1425 ineq
= isl_equality_from_aff(aff
);
1427 bset
= isl_basic_set_from_constraint(ineq
);
1429 bset
= isl_basic_set_set_rational(bset
);
1430 bset
= isl_basic_set_simplify(bset
);
1434 /* Return a basic set containing those elements in the space
1435 * of aff where it is zero.
1437 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
1439 return aff_zero_basic_set(aff
, 0);
1442 /* Return a basic set containing those elements in the shared space
1443 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1445 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
1446 __isl_take isl_aff
*aff2
)
1448 aff1
= isl_aff_sub(aff1
, aff2
);
1450 return isl_aff_nonneg_basic_set(aff1
);
1453 /* Return a basic set containing those elements in the shared space
1454 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1456 __isl_give isl_basic_set
*isl_aff_le_basic_set(__isl_take isl_aff
*aff1
,
1457 __isl_take isl_aff
*aff2
)
1459 return isl_aff_ge_basic_set(aff2
, aff1
);
1462 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
1463 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
1465 aff1
= isl_aff_add(aff1
, aff2
);
1466 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
1470 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
1478 /* Check whether the given affine expression has non-zero coefficient
1479 * for any dimension in the given range or if any of these dimensions
1480 * appear with non-zero coefficients in any of the integer divisions
1481 * involved in the affine expression.
1483 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
1484 enum isl_dim_type type
, unsigned first
, unsigned n
)
1496 ctx
= isl_aff_get_ctx(aff
);
1497 if (first
+ n
> isl_aff_dim(aff
, type
))
1498 isl_die(ctx
, isl_error_invalid
,
1499 "range out of bounds", return -1);
1501 active
= isl_local_space_get_active(aff
->ls
, aff
->v
->el
+ 2);
1505 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
1506 for (i
= 0; i
< n
; ++i
)
1507 if (active
[first
+ i
]) {
1520 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
1521 enum isl_dim_type type
, unsigned first
, unsigned n
)
1527 if (type
== isl_dim_out
)
1528 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1529 "cannot drop output/set dimension",
1530 return isl_aff_free(aff
));
1531 if (type
== isl_dim_in
)
1533 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1536 ctx
= isl_aff_get_ctx(aff
);
1537 if (first
+ n
> isl_local_space_dim(aff
->ls
, type
))
1538 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
1539 return isl_aff_free(aff
));
1541 aff
= isl_aff_cow(aff
);
1545 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
1547 return isl_aff_free(aff
);
1549 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
1550 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
1552 return isl_aff_free(aff
);
1557 /* Project the domain of the affine expression onto its parameter space.
1558 * The affine expression may not involve any of the domain dimensions.
1560 __isl_give isl_aff
*isl_aff_project_domain_on_params(__isl_take isl_aff
*aff
)
1566 n
= isl_aff_dim(aff
, isl_dim_in
);
1567 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, 0, n
);
1569 return isl_aff_free(aff
);
1571 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1572 "affine expression involves some of the domain dimensions",
1573 return isl_aff_free(aff
));
1574 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, 0, n
);
1575 space
= isl_aff_get_domain_space(aff
);
1576 space
= isl_space_params(space
);
1577 aff
= isl_aff_reset_domain_space(aff
, space
);
1581 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
1582 enum isl_dim_type type
, unsigned first
, unsigned n
)
1588 if (type
== isl_dim_out
)
1589 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1590 "cannot insert output/set dimensions",
1591 return isl_aff_free(aff
));
1592 if (type
== isl_dim_in
)
1594 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1597 ctx
= isl_aff_get_ctx(aff
);
1598 if (first
> isl_local_space_dim(aff
->ls
, type
))
1599 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
1600 return isl_aff_free(aff
));
1602 aff
= isl_aff_cow(aff
);
1606 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
1608 return isl_aff_free(aff
);
1610 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
1611 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
1613 return isl_aff_free(aff
);
1618 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
1619 enum isl_dim_type type
, unsigned n
)
1623 pos
= isl_aff_dim(aff
, type
);
1625 return isl_aff_insert_dims(aff
, type
, pos
, n
);
1628 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
1629 enum isl_dim_type type
, unsigned n
)
1633 pos
= isl_pw_aff_dim(pwaff
, type
);
1635 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
1638 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
1640 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
1641 return isl_pw_aff_alloc(dom
, aff
);
1645 #define PW isl_pw_aff
1649 #define EL_IS_ZERO is_empty
1653 #define IS_ZERO is_empty
1656 #undef DEFAULT_IS_ZERO
1657 #define DEFAULT_IS_ZERO 0
1661 #define NO_MOVE_DIMS
1665 #include <isl_pw_templ.c>
1667 static __isl_give isl_set
*align_params_pw_pw_set_and(
1668 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
1669 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
1670 __isl_take isl_pw_aff
*pwaff2
))
1672 if (!pwaff1
|| !pwaff2
)
1674 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
1675 pwaff2
->dim
, isl_dim_param
))
1676 return fn(pwaff1
, pwaff2
);
1677 if (!isl_space_has_named_params(pwaff1
->dim
) ||
1678 !isl_space_has_named_params(pwaff2
->dim
))
1679 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
1680 "unaligned unnamed parameters", goto error
);
1681 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
1682 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
1683 return fn(pwaff1
, pwaff2
);
1685 isl_pw_aff_free(pwaff1
);
1686 isl_pw_aff_free(pwaff2
);
1690 /* Compute a piecewise quasi-affine expression with a domain that
1691 * is the union of those of pwaff1 and pwaff2 and such that on each
1692 * cell, the quasi-affine expression is the better (according to cmp)
1693 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1694 * is defined on a given cell, then the associated expression
1695 * is the defined one.
1697 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
1698 __isl_take isl_pw_aff
*pwaff2
,
1699 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
1700 __isl_take isl_aff
*aff2
))
1707 if (!pwaff1
|| !pwaff2
)
1710 ctx
= isl_space_get_ctx(pwaff1
->dim
);
1711 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
1712 isl_die(ctx
, isl_error_invalid
,
1713 "arguments should live in same space", goto error
);
1715 if (isl_pw_aff_is_empty(pwaff1
)) {
1716 isl_pw_aff_free(pwaff1
);
1720 if (isl_pw_aff_is_empty(pwaff2
)) {
1721 isl_pw_aff_free(pwaff2
);
1725 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
1726 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
1728 for (i
= 0; i
< pwaff1
->n
; ++i
) {
1729 set
= isl_set_copy(pwaff1
->p
[i
].set
);
1730 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1731 struct isl_set
*common
;
1734 common
= isl_set_intersect(
1735 isl_set_copy(pwaff1
->p
[i
].set
),
1736 isl_set_copy(pwaff2
->p
[j
].set
));
1737 better
= isl_set_from_basic_set(cmp(
1738 isl_aff_copy(pwaff2
->p
[j
].aff
),
1739 isl_aff_copy(pwaff1
->p
[i
].aff
)));
1740 better
= isl_set_intersect(common
, better
);
1741 if (isl_set_plain_is_empty(better
)) {
1742 isl_set_free(better
);
1745 set
= isl_set_subtract(set
, isl_set_copy(better
));
1747 res
= isl_pw_aff_add_piece(res
, better
,
1748 isl_aff_copy(pwaff2
->p
[j
].aff
));
1750 res
= isl_pw_aff_add_piece(res
, set
,
1751 isl_aff_copy(pwaff1
->p
[i
].aff
));
1754 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1755 set
= isl_set_copy(pwaff2
->p
[j
].set
);
1756 for (i
= 0; i
< pwaff1
->n
; ++i
)
1757 set
= isl_set_subtract(set
,
1758 isl_set_copy(pwaff1
->p
[i
].set
));
1759 res
= isl_pw_aff_add_piece(res
, set
,
1760 isl_aff_copy(pwaff2
->p
[j
].aff
));
1763 isl_pw_aff_free(pwaff1
);
1764 isl_pw_aff_free(pwaff2
);
1768 isl_pw_aff_free(pwaff1
);
1769 isl_pw_aff_free(pwaff2
);
1773 /* Compute a piecewise quasi-affine expression with a domain that
1774 * is the union of those of pwaff1 and pwaff2 and such that on each
1775 * cell, the quasi-affine expression is the maximum of those of pwaff1
1776 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1777 * cell, then the associated expression is the defined one.
1779 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
1780 __isl_take isl_pw_aff
*pwaff2
)
1782 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
1785 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
1786 __isl_take isl_pw_aff
*pwaff2
)
1788 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
1792 /* Compute a piecewise quasi-affine expression with a domain that
1793 * is the union of those of pwaff1 and pwaff2 and such that on each
1794 * cell, the quasi-affine expression is the minimum of those of pwaff1
1795 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1796 * cell, then the associated expression is the defined one.
1798 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
1799 __isl_take isl_pw_aff
*pwaff2
)
1801 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
1804 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
1805 __isl_take isl_pw_aff
*pwaff2
)
1807 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
1811 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
1812 __isl_take isl_pw_aff
*pwaff2
, int max
)
1815 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
1817 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
1820 /* Construct a map with as domain the domain of pwaff and
1821 * one-dimensional range corresponding to the affine expressions.
1823 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1832 dim
= isl_pw_aff_get_space(pwaff
);
1833 map
= isl_map_empty(dim
);
1835 for (i
= 0; i
< pwaff
->n
; ++i
) {
1836 isl_basic_map
*bmap
;
1839 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
1840 map_i
= isl_map_from_basic_map(bmap
);
1841 map_i
= isl_map_intersect_domain(map_i
,
1842 isl_set_copy(pwaff
->p
[i
].set
));
1843 map
= isl_map_union_disjoint(map
, map_i
);
1846 isl_pw_aff_free(pwaff
);
1851 /* Construct a map with as domain the domain of pwaff and
1852 * one-dimensional range corresponding to the affine expressions.
1854 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1858 if (isl_space_is_set(pwaff
->dim
))
1859 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
1860 "space of input is not a map",
1861 return isl_pw_aff_free(pwaff
));
1862 return map_from_pw_aff(pwaff
);
1865 /* Construct a one-dimensional set with as parameter domain
1866 * the domain of pwaff and the single set dimension
1867 * corresponding to the affine expressions.
1869 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1873 if (!isl_space_is_set(pwaff
->dim
))
1874 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
1875 "space of input is not a set",
1876 return isl_pw_aff_free(pwaff
));
1877 return map_from_pw_aff(pwaff
);
1880 /* Return a set containing those elements in the domain
1881 * of pwaff where it is non-negative.
1883 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
1891 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
1893 for (i
= 0; i
< pwaff
->n
; ++i
) {
1894 isl_basic_set
*bset
;
1898 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
1899 bset
= aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
1901 set_i
= isl_set_from_basic_set(bset
);
1902 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
1903 set
= isl_set_union_disjoint(set
, set_i
);
1906 isl_pw_aff_free(pwaff
);
1911 /* Return a set containing those elements in the domain
1912 * of pwaff where it is zero (if complement is 0) or not zero
1913 * (if complement is 1).
1915 static __isl_give isl_set
*pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
,
1924 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
1926 for (i
= 0; i
< pwaff
->n
; ++i
) {
1927 isl_basic_set
*bset
;
1928 isl_set
*set_i
, *zero
;
1931 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
1932 bset
= aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
1934 zero
= isl_set_from_basic_set(bset
);
1935 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
1937 set_i
= isl_set_subtract(set_i
, zero
);
1939 set_i
= isl_set_intersect(set_i
, zero
);
1940 set
= isl_set_union_disjoint(set
, set_i
);
1943 isl_pw_aff_free(pwaff
);
1948 /* Return a set containing those elements in the domain
1949 * of pwaff where it is zero.
1951 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
1953 return pw_aff_zero_set(pwaff
, 0);
1956 /* Return a set containing those elements in the domain
1957 * of pwaff where it is not zero.
1959 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
1961 return pw_aff_zero_set(pwaff
, 1);
1964 /* Return a set containing those elements in the shared domain
1965 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1967 * We compute the difference on the shared domain and then construct
1968 * the set of values where this difference is non-negative.
1969 * If strict is set, we first subtract 1 from the difference.
1970 * If equal is set, we only return the elements where pwaff1 and pwaff2
1973 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
1974 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
1976 isl_set
*set1
, *set2
;
1978 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
1979 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
1980 set1
= isl_set_intersect(set1
, set2
);
1981 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
1982 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
1983 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
1986 isl_space
*dim
= isl_set_get_space(set1
);
1988 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1989 aff
= isl_aff_add_constant_si(aff
, -1);
1990 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
1995 return isl_pw_aff_zero_set(pwaff1
);
1996 return isl_pw_aff_nonneg_set(pwaff1
);
1999 /* Return a set containing those elements in the shared domain
2000 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2002 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2003 __isl_take isl_pw_aff
*pwaff2
)
2005 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
2008 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
2009 __isl_take isl_pw_aff
*pwaff2
)
2011 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2014 /* Return a set containing those elements in the shared domain
2015 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2017 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2018 __isl_take isl_pw_aff
*pwaff2
)
2020 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2023 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2024 __isl_take isl_pw_aff
*pwaff2
)
2026 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2029 /* Return a set containing those elements in the shared domain
2030 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2032 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2033 __isl_take isl_pw_aff
*pwaff2
)
2035 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2038 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2039 __isl_take isl_pw_aff
*pwaff2
)
2041 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2044 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2045 __isl_take isl_pw_aff
*pwaff2
)
2047 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2050 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2051 __isl_take isl_pw_aff
*pwaff2
)
2053 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2056 /* Return a set containing those elements in the shared domain
2057 * of the elements of list1 and list2 where each element in list1
2058 * has the relation specified by "fn" with each element in list2.
2060 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2061 __isl_take isl_pw_aff_list
*list2
,
2062 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2063 __isl_take isl_pw_aff
*pwaff2
))
2069 if (!list1
|| !list2
)
2072 ctx
= isl_pw_aff_list_get_ctx(list1
);
2073 if (list1
->n
< 1 || list2
->n
< 1)
2074 isl_die(ctx
, isl_error_invalid
,
2075 "list should contain at least one element", goto error
);
2077 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2078 for (i
= 0; i
< list1
->n
; ++i
)
2079 for (j
= 0; j
< list2
->n
; ++j
) {
2082 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2083 isl_pw_aff_copy(list2
->p
[j
]));
2084 set
= isl_set_intersect(set
, set_ij
);
2087 isl_pw_aff_list_free(list1
);
2088 isl_pw_aff_list_free(list2
);
2091 isl_pw_aff_list_free(list1
);
2092 isl_pw_aff_list_free(list2
);
2096 /* Return a set containing those elements in the shared domain
2097 * of the elements of list1 and list2 where each element in list1
2098 * is equal to each element in list2.
2100 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2101 __isl_take isl_pw_aff_list
*list2
)
2103 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
2106 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
2107 __isl_take isl_pw_aff_list
*list2
)
2109 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
2112 /* Return a set containing those elements in the shared domain
2113 * of the elements of list1 and list2 where each element in list1
2114 * is less than or equal to each element in list2.
2116 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
2117 __isl_take isl_pw_aff_list
*list2
)
2119 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
2122 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
2123 __isl_take isl_pw_aff_list
*list2
)
2125 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
2128 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
2129 __isl_take isl_pw_aff_list
*list2
)
2131 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
2134 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
2135 __isl_take isl_pw_aff_list
*list2
)
2137 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
2141 /* Return a set containing those elements in the shared domain
2142 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2144 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2145 __isl_take isl_pw_aff
*pwaff2
)
2147 isl_set
*set_lt
, *set_gt
;
2149 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
2150 isl_pw_aff_copy(pwaff2
));
2151 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
2152 return isl_set_union_disjoint(set_lt
, set_gt
);
2155 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2156 __isl_take isl_pw_aff
*pwaff2
)
2158 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
2161 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
2166 if (isl_int_is_one(v
))
2168 if (!isl_int_is_pos(v
))
2169 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2170 "factor needs to be positive",
2171 return isl_pw_aff_free(pwaff
));
2172 pwaff
= isl_pw_aff_cow(pwaff
);
2178 for (i
= 0; i
< pwaff
->n
; ++i
) {
2179 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
2180 if (!pwaff
->p
[i
].aff
)
2181 return isl_pw_aff_free(pwaff
);
2187 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
2191 pwaff
= isl_pw_aff_cow(pwaff
);
2197 for (i
= 0; i
< pwaff
->n
; ++i
) {
2198 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
2199 if (!pwaff
->p
[i
].aff
)
2200 return isl_pw_aff_free(pwaff
);
2206 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
2210 pwaff
= isl_pw_aff_cow(pwaff
);
2216 for (i
= 0; i
< pwaff
->n
; ++i
) {
2217 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
2218 if (!pwaff
->p
[i
].aff
)
2219 return isl_pw_aff_free(pwaff
);
2225 /* Assuming that "cond1" and "cond2" are disjoint,
2226 * return an affine expression that is equal to pwaff1 on cond1
2227 * and to pwaff2 on cond2.
2229 static __isl_give isl_pw_aff
*isl_pw_aff_select(
2230 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
2231 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
2233 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
2234 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
2236 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
2239 /* Return an affine expression that is equal to pwaff_true for elements
2240 * where "cond" is non-zero and to pwaff_false for elements where "cond"
2242 * That is, return cond ? pwaff_true : pwaff_false;
2244 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
2245 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
2247 isl_set
*cond_true
, *cond_false
;
2249 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
2250 cond_false
= isl_pw_aff_zero_set(cond
);
2251 return isl_pw_aff_select(cond_true
, pwaff_true
,
2252 cond_false
, pwaff_false
);
2255 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
2260 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
2263 /* Check whether pwaff is a piecewise constant.
2265 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
2272 for (i
= 0; i
< pwaff
->n
; ++i
) {
2273 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
2274 if (is_cst
< 0 || !is_cst
)
2281 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
2282 __isl_take isl_aff
*aff2
)
2284 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
2285 return isl_aff_mul(aff2
, aff1
);
2287 if (!isl_aff_is_cst(aff2
))
2288 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
2289 "at least one affine expression should be constant",
2292 aff1
= isl_aff_cow(aff1
);
2296 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
2297 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
2307 /* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant.
2309 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
2310 __isl_take isl_aff
*aff2
)
2315 is_cst
= isl_aff_is_cst(aff2
);
2319 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
2320 "second argument should be a constant", goto error
);
2325 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
2327 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2328 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2331 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
2332 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
2335 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2336 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2347 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2348 __isl_take isl_pw_aff
*pwaff2
)
2350 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
2353 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2354 __isl_take isl_pw_aff
*pwaff2
)
2356 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
2359 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
2360 __isl_take isl_pw_aff
*pwaff2
)
2362 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
2365 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2366 __isl_take isl_pw_aff
*pwaff2
)
2368 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
2371 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2372 __isl_take isl_pw_aff
*pwaff2
)
2374 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
2377 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2378 __isl_take isl_pw_aff
*pa2
)
2380 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
2383 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
2385 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2386 __isl_take isl_pw_aff
*pa2
)
2390 is_cst
= isl_pw_aff_is_cst(pa2
);
2394 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2395 "second argument should be a piecewise constant",
2397 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
2399 isl_pw_aff_free(pa1
);
2400 isl_pw_aff_free(pa2
);
2404 /* Compute the quotient of the integer division of "pa1" by "pa2"
2405 * with rounding towards zero.
2406 * "pa2" is assumed to be a piecewise constant.
2408 * In particular, return
2410 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
2413 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
2414 __isl_take isl_pw_aff
*pa2
)
2420 is_cst
= isl_pw_aff_is_cst(pa2
);
2424 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2425 "second argument should be a piecewise constant",
2428 pa1
= isl_pw_aff_div(pa1
, pa2
);
2430 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
2431 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
2432 c
= isl_pw_aff_ceil(pa1
);
2433 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
2435 isl_pw_aff_free(pa1
);
2436 isl_pw_aff_free(pa2
);
2440 /* Compute the remainder of the integer division of "pa1" by "pa2"
2441 * with rounding towards zero.
2442 * "pa2" is assumed to be a piecewise constant.
2444 * In particular, return
2446 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
2449 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
2450 __isl_take isl_pw_aff
*pa2
)
2455 is_cst
= isl_pw_aff_is_cst(pa2
);
2459 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2460 "second argument should be a piecewise constant",
2462 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
2463 res
= isl_pw_aff_mul(pa2
, res
);
2464 res
= isl_pw_aff_sub(pa1
, res
);
2467 isl_pw_aff_free(pa1
);
2468 isl_pw_aff_free(pa2
);
2472 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2473 __isl_take isl_pw_aff
*pwaff2
)
2478 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2479 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2480 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
2481 isl_pw_aff_copy(pwaff2
));
2482 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
2483 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
2486 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2487 __isl_take isl_pw_aff
*pwaff2
)
2489 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
2492 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2493 __isl_take isl_pw_aff
*pwaff2
)
2498 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2499 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2500 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
2501 isl_pw_aff_copy(pwaff2
));
2502 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
2503 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
2506 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2507 __isl_take isl_pw_aff
*pwaff2
)
2509 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
2512 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
2513 __isl_take isl_pw_aff_list
*list
,
2514 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2515 __isl_take isl_pw_aff
*pwaff2
))
2524 ctx
= isl_pw_aff_list_get_ctx(list
);
2526 isl_die(ctx
, isl_error_invalid
,
2527 "list should contain at least one element",
2528 return isl_pw_aff_list_free(list
));
2530 res
= isl_pw_aff_copy(list
->p
[0]);
2531 for (i
= 1; i
< list
->n
; ++i
)
2532 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
2534 isl_pw_aff_list_free(list
);
2538 /* Return an isl_pw_aff that maps each element in the intersection of the
2539 * domains of the elements of list to the minimal corresponding affine
2542 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
2544 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
2547 /* Return an isl_pw_aff that maps each element in the intersection of the
2548 * domains of the elements of list to the maximal corresponding affine
2551 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
2553 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
2556 /* Mark the domains of "pwaff" as rational.
2558 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__isl_take isl_pw_aff
*pwaff
)
2562 pwaff
= isl_pw_aff_cow(pwaff
);
2568 for (i
= 0; i
< pwaff
->n
; ++i
) {
2569 pwaff
->p
[i
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
2570 if (!pwaff
->p
[i
].set
)
2571 return isl_pw_aff_free(pwaff
);
2577 /* Mark the domains of the elements of "list" as rational.
2579 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
2580 __isl_take isl_pw_aff_list
*list
)
2589 for (i
= 0; i
< list
->n
; ++i
) {
2592 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
2593 pa
= isl_pw_aff_set_rational(pa
);
2594 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
2603 #include <isl_multi_templ.c>
2605 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2608 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
2609 __isl_take isl_multi_aff
*ma
)
2611 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
2612 return isl_pw_multi_aff_alloc(dom
, ma
);
2615 /* Create a piecewise multi-affine expression in the given space that maps each
2616 * input dimension to the corresponding output dimension.
2618 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
2619 __isl_take isl_space
*space
)
2621 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
2624 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*maff1
,
2625 __isl_take isl_multi_aff
*maff2
)
2630 maff1
= isl_multi_aff_cow(maff1
);
2631 if (!maff1
|| !maff2
)
2634 ctx
= isl_multi_aff_get_ctx(maff1
);
2635 if (!isl_space_is_equal(maff1
->space
, maff2
->space
))
2636 isl_die(ctx
, isl_error_invalid
,
2637 "spaces don't match", goto error
);
2639 for (i
= 0; i
< maff1
->n
; ++i
) {
2640 maff1
->p
[i
] = isl_aff_add(maff1
->p
[i
],
2641 isl_aff_copy(maff2
->p
[i
]));
2646 isl_multi_aff_free(maff2
);
2649 isl_multi_aff_free(maff1
);
2650 isl_multi_aff_free(maff2
);
2654 /* Given two multi-affine expressions A -> B and C -> D,
2655 * construct a multi-affine expression [A -> C] -> [B -> D].
2657 __isl_give isl_multi_aff
*isl_multi_aff_product(
2658 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
2664 int in1
, in2
, out1
, out2
;
2666 in1
= isl_multi_aff_dim(ma1
, isl_dim_in
);
2667 in2
= isl_multi_aff_dim(ma2
, isl_dim_in
);
2668 out1
= isl_multi_aff_dim(ma1
, isl_dim_out
);
2669 out2
= isl_multi_aff_dim(ma2
, isl_dim_out
);
2670 space
= isl_space_product(isl_multi_aff_get_space(ma1
),
2671 isl_multi_aff_get_space(ma2
));
2672 res
= isl_multi_aff_alloc(isl_space_copy(space
));
2673 space
= isl_space_domain(space
);
2675 for (i
= 0; i
< out1
; ++i
) {
2676 aff
= isl_multi_aff_get_aff(ma1
, i
);
2677 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, in1
, in2
);
2678 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
2679 res
= isl_multi_aff_set_aff(res
, i
, aff
);
2682 for (i
= 0; i
< out2
; ++i
) {
2683 aff
= isl_multi_aff_get_aff(ma2
, i
);
2684 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, 0, in1
);
2685 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
2686 res
= isl_multi_aff_set_aff(res
, out1
+ i
, aff
);
2689 isl_space_free(space
);
2690 isl_multi_aff_free(ma1
);
2691 isl_multi_aff_free(ma2
);
2695 /* Exploit the equalities in "eq" to simplify the affine expressions.
2697 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
2698 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
2702 maff
= isl_multi_aff_cow(maff
);
2706 for (i
= 0; i
< maff
->n
; ++i
) {
2707 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
2708 isl_basic_set_copy(eq
));
2713 isl_basic_set_free(eq
);
2716 isl_basic_set_free(eq
);
2717 isl_multi_aff_free(maff
);
2721 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
2726 maff
= isl_multi_aff_cow(maff
);
2730 for (i
= 0; i
< maff
->n
; ++i
) {
2731 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
2733 return isl_multi_aff_free(maff
);
2739 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
2740 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
2742 maff1
= isl_multi_aff_add(maff1
, maff2
);
2743 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
2747 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
2755 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff
*maff1
,
2756 __isl_keep isl_multi_aff
*maff2
)
2761 if (!maff1
|| !maff2
)
2763 if (maff1
->n
!= maff2
->n
)
2765 equal
= isl_space_is_equal(maff1
->space
, maff2
->space
);
2766 if (equal
< 0 || !equal
)
2769 for (i
= 0; i
< maff1
->n
; ++i
) {
2770 equal
= isl_aff_plain_is_equal(maff1
->p
[i
], maff2
->p
[i
]);
2771 if (equal
< 0 || !equal
)
2778 /* Return the set of domain elements where "ma1" is lexicographically
2779 * smaller than or equal to "ma2".
2781 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
2782 __isl_take isl_multi_aff
*ma2
)
2784 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
2787 /* Return the set of domain elements where "ma1" is lexicographically
2788 * greater than or equal to "ma2".
2790 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
2791 __isl_take isl_multi_aff
*ma2
)
2794 isl_map
*map1
, *map2
;
2797 map1
= isl_map_from_multi_aff(ma1
);
2798 map2
= isl_map_from_multi_aff(ma2
);
2799 map
= isl_map_range_product(map1
, map2
);
2800 space
= isl_space_range(isl_map_get_space(map
));
2801 space
= isl_space_domain(isl_space_unwrap(space
));
2802 ge
= isl_map_lex_ge(space
);
2803 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
2805 return isl_map_domain(map
);
2809 #define PW isl_pw_multi_aff
2811 #define EL isl_multi_aff
2813 #define EL_IS_ZERO is_empty
2817 #define IS_ZERO is_empty
2820 #undef DEFAULT_IS_ZERO
2821 #define DEFAULT_IS_ZERO 0
2826 #define NO_INVOLVES_DIMS
2827 #define NO_MOVE_DIMS
2828 #define NO_INSERT_DIMS
2832 #include <isl_pw_templ.c>
2835 #define UNION isl_union_pw_multi_aff
2837 #define PART isl_pw_multi_aff
2839 #define PARTS pw_multi_aff
2840 #define ALIGN_DOMAIN
2844 #include <isl_union_templ.c>
2846 /* Given a function "cmp" that returns the set of elements where
2847 * "ma1" is "better" than "ma2", return the intersection of this
2848 * set with "dom1" and "dom2".
2850 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
2851 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
2852 __isl_keep isl_multi_aff
*ma2
,
2853 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
2854 __isl_take isl_multi_aff
*ma2
))
2860 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
2861 is_empty
= isl_set_plain_is_empty(common
);
2862 if (is_empty
>= 0 && is_empty
)
2865 return isl_set_free(common
);
2866 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
2867 better
= isl_set_intersect(common
, better
);
2872 /* Given a function "cmp" that returns the set of elements where
2873 * "ma1" is "better" than "ma2", return a piecewise multi affine
2874 * expression defined on the union of the definition domains
2875 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
2876 * "pma2" on each cell. If only one of the two input functions
2877 * is defined on a given cell, then it is considered the best.
2879 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
2880 __isl_take isl_pw_multi_aff
*pma1
,
2881 __isl_take isl_pw_multi_aff
*pma2
,
2882 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
2883 __isl_take isl_multi_aff
*ma2
))
2886 isl_pw_multi_aff
*res
= NULL
;
2888 isl_set
*set
= NULL
;
2893 ctx
= isl_space_get_ctx(pma1
->dim
);
2894 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
2895 isl_die(ctx
, isl_error_invalid
,
2896 "arguments should live in the same space", goto error
);
2898 if (isl_pw_multi_aff_is_empty(pma1
)) {
2899 isl_pw_multi_aff_free(pma1
);
2903 if (isl_pw_multi_aff_is_empty(pma2
)) {
2904 isl_pw_multi_aff_free(pma2
);
2908 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
2909 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
2911 for (i
= 0; i
< pma1
->n
; ++i
) {
2912 set
= isl_set_copy(pma1
->p
[i
].set
);
2913 for (j
= 0; j
< pma2
->n
; ++j
) {
2917 better
= shared_and_better(pma2
->p
[j
].set
,
2918 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
2919 pma1
->p
[i
].maff
, cmp
);
2920 is_empty
= isl_set_plain_is_empty(better
);
2921 if (is_empty
< 0 || is_empty
) {
2922 isl_set_free(better
);
2927 set
= isl_set_subtract(set
, isl_set_copy(better
));
2929 res
= isl_pw_multi_aff_add_piece(res
, better
,
2930 isl_multi_aff_copy(pma2
->p
[j
].maff
));
2932 res
= isl_pw_multi_aff_add_piece(res
, set
,
2933 isl_multi_aff_copy(pma1
->p
[i
].maff
));
2936 for (j
= 0; j
< pma2
->n
; ++j
) {
2937 set
= isl_set_copy(pma2
->p
[j
].set
);
2938 for (i
= 0; i
< pma1
->n
; ++i
)
2939 set
= isl_set_subtract(set
,
2940 isl_set_copy(pma1
->p
[i
].set
));
2941 res
= isl_pw_multi_aff_add_piece(res
, set
,
2942 isl_multi_aff_copy(pma2
->p
[j
].maff
));
2945 isl_pw_multi_aff_free(pma1
);
2946 isl_pw_multi_aff_free(pma2
);
2950 isl_pw_multi_aff_free(pma1
);
2951 isl_pw_multi_aff_free(pma2
);
2953 return isl_pw_multi_aff_free(res
);
2956 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
2957 __isl_take isl_pw_multi_aff
*pma1
,
2958 __isl_take isl_pw_multi_aff
*pma2
)
2960 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
2963 /* Given two piecewise multi affine expressions, return a piecewise
2964 * multi-affine expression defined on the union of the definition domains
2965 * of the inputs that is equal to the lexicographic maximum of the two
2966 * inputs on each cell. If only one of the two inputs is defined on
2967 * a given cell, then it is considered to be the maximum.
2969 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
2970 __isl_take isl_pw_multi_aff
*pma1
,
2971 __isl_take isl_pw_multi_aff
*pma2
)
2973 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
2974 &pw_multi_aff_union_lexmax
);
2977 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
2978 __isl_take isl_pw_multi_aff
*pma1
,
2979 __isl_take isl_pw_multi_aff
*pma2
)
2981 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
2984 /* Given two piecewise multi affine expressions, return a piecewise
2985 * multi-affine expression defined on the union of the definition domains
2986 * of the inputs that is equal to the lexicographic minimum of the two
2987 * inputs on each cell. If only one of the two inputs is defined on
2988 * a given cell, then it is considered to be the minimum.
2990 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
2991 __isl_take isl_pw_multi_aff
*pma1
,
2992 __isl_take isl_pw_multi_aff
*pma2
)
2994 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
2995 &pw_multi_aff_union_lexmin
);
2998 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
2999 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3001 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
3002 &isl_multi_aff_add
);
3005 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
3006 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3008 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3012 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
3013 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3015 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
3018 /* Given two piecewise multi-affine expressions A -> B and C -> D,
3019 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
3021 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
3022 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3026 isl_pw_multi_aff
*res
;
3031 n
= pma1
->n
* pma2
->n
;
3032 space
= isl_space_product(isl_space_copy(pma1
->dim
),
3033 isl_space_copy(pma2
->dim
));
3034 res
= isl_pw_multi_aff_alloc_size(space
, n
);
3036 for (i
= 0; i
< pma1
->n
; ++i
) {
3037 for (j
= 0; j
< pma2
->n
; ++j
) {
3041 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
3042 isl_set_copy(pma2
->p
[j
].set
));
3043 ma
= isl_multi_aff_product(
3044 isl_multi_aff_copy(pma1
->p
[i
].maff
),
3045 isl_multi_aff_copy(pma2
->p
[i
].maff
));
3046 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
3050 isl_pw_multi_aff_free(pma1
);
3051 isl_pw_multi_aff_free(pma2
);
3054 isl_pw_multi_aff_free(pma1
);
3055 isl_pw_multi_aff_free(pma2
);
3059 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
3060 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3062 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3063 &pw_multi_aff_product
);
3066 /* Construct a map mapping the domain of the piecewise multi-affine expression
3067 * to its range, with each dimension in the range equated to the
3068 * corresponding affine expression on its cell.
3070 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3078 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
3080 for (i
= 0; i
< pma
->n
; ++i
) {
3081 isl_multi_aff
*maff
;
3082 isl_basic_map
*bmap
;
3085 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
3086 bmap
= isl_basic_map_from_multi_aff(maff
);
3087 map_i
= isl_map_from_basic_map(bmap
);
3088 map_i
= isl_map_intersect_domain(map_i
,
3089 isl_set_copy(pma
->p
[i
].set
));
3090 map
= isl_map_union_disjoint(map
, map_i
);
3093 isl_pw_multi_aff_free(pma
);
3097 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3102 if (!isl_space_is_set(pma
->dim
))
3103 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
3104 "isl_pw_multi_aff cannot be converted into an isl_set",
3105 return isl_pw_multi_aff_free(pma
));
3107 return isl_map_from_pw_multi_aff(pma
);
3110 /* Given a basic map with a single output dimension that is defined
3111 * in terms of the parameters and input dimensions using an equality,
3112 * extract an isl_aff that expresses the output dimension in terms
3113 * of the parameters and input dimensions.
3115 * Since some applications expect the result of isl_pw_multi_aff_from_map
3116 * to only contain integer affine expressions, we compute the floor
3117 * of the expression before returning.
3119 * This function shares some similarities with
3120 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
3122 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
3123 __isl_take isl_basic_map
*bmap
)
3128 isl_local_space
*ls
;
3133 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
3134 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3135 "basic map should have a single output dimension",
3137 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
3138 total
= isl_basic_map_total_dim(bmap
);
3139 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
3140 if (isl_int_is_zero(bmap
->eq
[i
][offset
]))
3142 if (isl_seq_first_non_zero(bmap
->eq
[i
] + offset
+ 1,
3143 1 + total
- (offset
+ 1)) != -1)
3147 if (i
>= bmap
->n_eq
)
3148 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3149 "unable to find suitable equality", goto error
);
3150 ls
= isl_basic_map_get_local_space(bmap
);
3151 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
3154 if (isl_int_is_neg(bmap
->eq
[i
][offset
]))
3155 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3157 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3158 isl_seq_clr(aff
->v
->el
+ 1 + offset
, aff
->v
->size
- (1 + offset
));
3159 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[i
][offset
]);
3160 isl_basic_map_free(bmap
);
3162 aff
= isl_aff_remove_unused_divs(aff
);
3163 aff
= isl_aff_floor(aff
);
3166 isl_basic_map_free(bmap
);
3170 /* Given a basic map where each output dimension is defined
3171 * in terms of the parameters and input dimensions using an equality,
3172 * extract an isl_multi_aff that expresses the output dimensions in terms
3173 * of the parameters and input dimensions.
3175 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
3176 __isl_take isl_basic_map
*bmap
)
3185 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
3186 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
3188 for (i
= 0; i
< n_out
; ++i
) {
3189 isl_basic_map
*bmap_i
;
3192 bmap_i
= isl_basic_map_copy(bmap
);
3193 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
3194 i
+ 1, n_out
- (1 + i
));
3195 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
3196 aff
= extract_isl_aff_from_basic_map(bmap_i
);
3197 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3200 isl_basic_map_free(bmap
);
3205 /* Create an isl_pw_multi_aff that is equivalent to
3206 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
3207 * The given basic map is such that each output dimension is defined
3208 * in terms of the parameters and input dimensions using an equality.
3210 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
3211 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
3215 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
3216 return isl_pw_multi_aff_alloc(domain
, ma
);
3219 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3220 * This obviously only works if the input "map" is single-valued.
3221 * If so, we compute the lexicographic minimum of the image in the form
3222 * of an isl_pw_multi_aff. Since the image is unique, it is equal
3223 * to its lexicographic minimum.
3224 * If the input is not single-valued, we produce an error.
3226 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
3227 __isl_take isl_map
*map
)
3231 isl_pw_multi_aff
*pma
;
3233 sv
= isl_map_is_single_valued(map
);
3237 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
3238 "map is not single-valued", goto error
);
3239 map
= isl_map_make_disjoint(map
);
3243 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
3245 for (i
= 0; i
< map
->n
; ++i
) {
3246 isl_pw_multi_aff
*pma_i
;
3247 isl_basic_map
*bmap
;
3248 bmap
= isl_basic_map_copy(map
->p
[i
]);
3249 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
3250 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
3260 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3261 * taking into account that the output dimension at position "d"
3262 * can be represented as
3264 * x = floor((e(...) + c1) / m)
3266 * given that constraint "i" is of the form
3268 * e(...) + c1 - m x >= 0
3271 * Let "map" be of the form
3275 * We construct a mapping
3277 * A -> [A -> x = floor(...)]
3279 * apply that to the map, obtaining
3281 * [A -> x = floor(...)] -> B
3283 * and equate dimension "d" to x.
3284 * We then compute a isl_pw_multi_aff representation of the resulting map
3285 * and plug in the mapping above.
3287 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
3288 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
3292 isl_local_space
*ls
;
3300 isl_pw_multi_aff
*pma
;
3303 is_set
= isl_map_is_set(map
);
3305 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3306 ctx
= isl_map_get_ctx(map
);
3307 space
= isl_space_domain(isl_map_get_space(map
));
3308 n_in
= isl_space_dim(space
, isl_dim_set
);
3309 n
= isl_space_dim(space
, isl_dim_all
);
3311 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
3313 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
3314 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
3316 isl_basic_map_free(hull
);
3318 ls
= isl_local_space_from_space(isl_space_copy(space
));
3319 aff
= isl_aff_alloc_vec(ls
, v
);
3320 aff
= isl_aff_floor(aff
);
3322 isl_space_free(space
);
3323 ma
= isl_multi_aff_from_aff(aff
);
3325 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
3326 ma
= isl_multi_aff_range_product(ma
,
3327 isl_multi_aff_from_aff(aff
));
3330 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
3331 map
= isl_map_apply_domain(map
, insert
);
3332 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
3333 pma
= isl_pw_multi_aff_from_map(map
);
3334 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
3339 /* Is constraint "c" of the form
3341 * e(...) + c1 - m x >= 0
3345 * -e(...) + c2 + m x >= 0
3347 * where m > 1 and e only depends on parameters and input dimemnsions?
3349 * "offset" is the offset of the output dimensions
3350 * "pos" is the position of output dimension x.
3352 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
3354 if (isl_int_is_zero(c
[offset
+ d
]))
3356 if (isl_int_is_one(c
[offset
+ d
]))
3358 if (isl_int_is_negone(c
[offset
+ d
]))
3360 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
3362 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
3363 total
- (offset
+ d
+ 1)) != -1)
3368 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3370 * As a special case, we first check if there is any pair of constraints,
3371 * shared by all the basic maps in "map" that force a given dimension
3372 * to be equal to the floor of some affine combination of the input dimensions.
3374 * In particular, if we can find two constraints
3376 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
3380 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
3382 * where m > 1 and e only depends on parameters and input dimemnsions,
3385 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
3387 * then we know that we can take
3389 * x = floor((e(...) + c1) / m)
3391 * without having to perform any computation.
3393 * Note that we know that
3397 * If c1 + c2 were 0, then we would have detected an equality during
3398 * simplification. If c1 + c2 were negative, then we would have detected
3401 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
3402 __isl_take isl_map
*map
)
3408 isl_basic_map
*hull
;
3410 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
3415 dim
= isl_map_dim(map
, isl_dim_out
);
3416 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3417 total
= 1 + isl_basic_map_total_dim(hull
);
3419 for (d
= 0; d
< dim
; ++d
) {
3420 for (i
= 0; i
< n
; ++i
) {
3421 if (!is_potential_div_constraint(hull
->ineq
[i
],
3424 for (j
= i
+ 1; j
< n
; ++j
) {
3425 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
3426 hull
->ineq
[j
] + 1, total
- 1))
3428 isl_int_add(sum
, hull
->ineq
[i
][0],
3430 if (isl_int_abs_lt(sum
,
3431 hull
->ineq
[i
][offset
+ d
]))
3438 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
3440 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
3444 isl_basic_map_free(hull
);
3445 return pw_multi_aff_from_map_base(map
);
3448 isl_basic_map_free(hull
);
3452 /* Given an affine expression
3454 * [A -> B] -> f(A,B)
3456 * construct an isl_multi_aff
3460 * such that dimension "d" in B' is set to "aff" and the remaining
3461 * dimensions are set equal to the corresponding dimensions in B.
3462 * "n_in" is the dimension of the space A.
3463 * "n_out" is the dimension of the space B.
3465 * If "is_set" is set, then the affine expression is of the form
3469 * and we construct an isl_multi_aff
3473 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
3474 unsigned n_in
, unsigned n_out
, int is_set
)
3478 isl_space
*space
, *space2
;
3479 isl_local_space
*ls
;
3481 space
= isl_aff_get_domain_space(aff
);
3482 ls
= isl_local_space_from_space(isl_space_copy(space
));
3483 space2
= isl_space_copy(space
);
3485 space2
= isl_space_range(isl_space_unwrap(space2
));
3486 space
= isl_space_map_from_domain_and_range(space
, space2
);
3487 ma
= isl_multi_aff_alloc(space
);
3488 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
3490 for (i
= 0; i
< n_out
; ++i
) {
3493 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3494 isl_dim_set
, n_in
+ i
);
3495 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3498 isl_local_space_free(ls
);
3503 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3504 * taking into account that the dimension at position "d" can be written as
3506 * x = m a + f(..) (1)
3508 * where m is equal to "gcd".
3509 * "i" is the index of the equality in "hull" that defines f(..).
3510 * In particular, the equality is of the form
3512 * f(..) - x + m g(existentials) = 0
3516 * -f(..) + x + m g(existentials) = 0
3518 * We basically plug (1) into "map", resulting in a map with "a"
3519 * in the range instead of "x". The corresponding isl_pw_multi_aff
3520 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
3522 * Specifically, given the input map
3526 * We first wrap it into a set
3530 * and define (1) on top of the corresponding space, resulting in "aff".
3531 * We use this to create an isl_multi_aff that maps the output position "d"
3532 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
3533 * We plug this into the wrapped map, unwrap the result and compute the
3534 * corresponding isl_pw_multi_aff.
3535 * The result is an expression
3543 * so that we can plug that into "aff", after extending the latter to
3549 * If "map" is actually a set, then there is no "A" space, meaning
3550 * that we do not need to perform any wrapping, and that the result
3551 * of the recursive call is of the form
3555 * which is plugged into a mapping of the form
3559 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
3560 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
3565 isl_local_space
*ls
;
3568 isl_pw_multi_aff
*pma
, *id
;
3574 is_set
= isl_map_is_set(map
);
3576 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
3577 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
3578 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
3583 set
= isl_map_wrap(map
);
3584 space
= isl_space_map_from_set(isl_set_get_space(set
));
3585 ma
= isl_multi_aff_identity(space
);
3586 ls
= isl_local_space_from_space(isl_set_get_space(set
));
3587 aff
= isl_aff_alloc(ls
);
3589 isl_int_set_si(aff
->v
->el
[0], 1);
3590 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
3591 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
3594 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
3596 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
3598 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
3599 set
= isl_set_preimage_multi_aff(set
, ma
);
3601 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
3606 map
= isl_set_unwrap(set
);
3607 pma
= isl_pw_multi_aff_from_map(set
);
3610 space
= isl_pw_multi_aff_get_domain_space(pma
);
3611 space
= isl_space_map_from_set(space
);
3612 id
= isl_pw_multi_aff_identity(space
);
3613 pma
= isl_pw_multi_aff_range_product(id
, pma
);
3615 id
= isl_pw_multi_aff_from_multi_aff(ma
);
3616 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
3618 isl_basic_map_free(hull
);
3622 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3624 * As a special case, we first check if all output dimensions are uniquely
3625 * defined in terms of the parameters and input dimensions over the entire
3626 * domain. If so, we extract the desired isl_pw_multi_aff directly
3627 * from the affine hull of "map" and its domain.
3629 * Otherwise, we check if any of the output dimensions is "strided".
3630 * That is, we check if can be written as
3634 * with m greater than 1, a some combination of existentiall quantified
3635 * variables and f and expression in the parameters and input dimensions.
3636 * If so, we remove the stride in pw_multi_aff_from_map_stride.
3638 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
3641 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
3645 isl_basic_map
*hull
;
3655 hull
= isl_map_affine_hull(isl_map_copy(map
));
3656 sv
= isl_basic_map_plain_is_single_valued(hull
);
3658 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
3660 hull
= isl_basic_map_free(hull
);
3664 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
3665 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
3668 isl_basic_map_free(hull
);
3669 return pw_multi_aff_from_map_check_div(map
);
3674 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
3675 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
3677 for (i
= 0; i
< n_out
; ++i
) {
3678 for (j
= 0; j
< hull
->n_eq
; ++j
) {
3679 isl_int
*eq
= hull
->eq
[j
];
3680 isl_pw_multi_aff
*res
;
3682 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
3683 !isl_int_is_negone(eq
[o_out
+ i
]))
3685 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
3687 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
3688 n_out
- (i
+ 1)) != -1)
3690 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
3691 if (isl_int_is_zero(gcd
))
3693 if (isl_int_is_one(gcd
))
3696 res
= pw_multi_aff_from_map_stride(map
, hull
,
3704 isl_basic_map_free(hull
);
3705 return pw_multi_aff_from_map_check_div(map
);
3711 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
3713 return isl_pw_multi_aff_from_map(set
);
3716 /* Return the piecewise affine expression "set ? 1 : 0".
3718 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
3721 isl_space
*space
= isl_set_get_space(set
);
3722 isl_local_space
*ls
= isl_local_space_from_space(space
);
3723 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
3724 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
3726 one
= isl_aff_add_constant_si(one
, 1);
3727 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
3728 set
= isl_set_complement(set
);
3729 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
3734 /* Plug in "subs" for dimension "type", "pos" of "aff".
3736 * Let i be the dimension to replace and let "subs" be of the form
3740 * and "aff" of the form
3746 * (a f + d g')/(m d)
3748 * where g' is the result of plugging in "subs" in each of the integer
3751 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
3752 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
3757 aff
= isl_aff_cow(aff
);
3759 return isl_aff_free(aff
);
3761 ctx
= isl_aff_get_ctx(aff
);
3762 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
3763 isl_die(ctx
, isl_error_invalid
,
3764 "spaces don't match", return isl_aff_free(aff
));
3765 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
3766 isl_die(ctx
, isl_error_unsupported
,
3767 "cannot handle divs yet", return isl_aff_free(aff
));
3769 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
3771 return isl_aff_free(aff
);
3773 aff
->v
= isl_vec_cow(aff
->v
);
3775 return isl_aff_free(aff
);
3777 pos
+= isl_local_space_offset(aff
->ls
, type
);
3780 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
3781 aff
->v
->size
, subs
->v
->size
, v
);
3787 /* Plug in "subs" for dimension "type", "pos" in each of the affine
3788 * expressions in "maff".
3790 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
3791 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
3792 __isl_keep isl_aff
*subs
)
3796 maff
= isl_multi_aff_cow(maff
);
3798 return isl_multi_aff_free(maff
);
3800 if (type
== isl_dim_in
)
3803 for (i
= 0; i
< maff
->n
; ++i
) {
3804 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
3806 return isl_multi_aff_free(maff
);
3812 /* Plug in "subs" for dimension "type", "pos" of "pma".
3814 * pma is of the form
3818 * while subs is of the form
3820 * v' = B_j(v) -> S_j
3822 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
3823 * has a contribution in the result, in particular
3825 * C_ij(S_j) -> M_i(S_j)
3827 * Note that plugging in S_j in C_ij may also result in an empty set
3828 * and this contribution should simply be discarded.
3830 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
3831 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
3832 __isl_keep isl_pw_aff
*subs
)
3835 isl_pw_multi_aff
*res
;
3838 return isl_pw_multi_aff_free(pma
);
3840 n
= pma
->n
* subs
->n
;
3841 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
3843 for (i
= 0; i
< pma
->n
; ++i
) {
3844 for (j
= 0; j
< subs
->n
; ++j
) {
3846 isl_multi_aff
*res_ij
;
3849 common
= isl_set_intersect(
3850 isl_set_copy(pma
->p
[i
].set
),
3851 isl_set_copy(subs
->p
[j
].set
));
3852 common
= isl_set_substitute(common
,
3853 type
, pos
, subs
->p
[j
].aff
);
3854 empty
= isl_set_plain_is_empty(common
);
3855 if (empty
< 0 || empty
) {
3856 isl_set_free(common
);
3862 res_ij
= isl_multi_aff_substitute(
3863 isl_multi_aff_copy(pma
->p
[i
].maff
),
3864 type
, pos
, subs
->p
[j
].aff
);
3866 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
3870 isl_pw_multi_aff_free(pma
);
3873 isl_pw_multi_aff_free(pma
);
3874 isl_pw_multi_aff_free(res
);
3878 /* Compute the preimage of the affine expression "src" under "ma"
3879 * and put the result in "dst". If "has_denom" is set (to one),
3880 * then "src" and "dst" have an extra initial denominator.
3881 * "n_div_ma" is the number of existentials in "ma"
3882 * "n_div_bset" is the number of existentials in "src"
3883 * The resulting "dst" (which is assumed to have been allocated by
3884 * the caller) contains coefficients for both sets of existentials,
3885 * first those in "ma" and then those in "src".
3886 * f, c1, c2 and g are temporary objects that have been initialized
3889 * Let src represent the expression
3891 * (a(p) + b x + c(divs))/d
3893 * and let ma represent the expressions
3895 * x_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
3897 * We start out with the following expression for dst:
3899 * (a(p) + 0 y + 0 divs' + f \sum_i b_i x_i + c(divs))/d
3901 * with the multiplication factor f initially equal to 1.
3902 * For each x_i that we substitute, we multiply the numerator
3903 * (and denominator) of dst by c_1 = m_i and add the numerator
3904 * of the x_i expression multiplied by c_2 = f b_i,
3905 * after removing the common factors of c_1 and c_2.
3906 * The multiplication factor f also needs to be multiplied by c_1
3907 * for the next x_j, j > i.
3909 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
3910 __isl_keep isl_multi_aff
*ma
, int n_div_ma
, int n_div_bset
,
3911 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
3914 int n_param
, n_in
, n_out
;
3917 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
3918 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
3919 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3921 o_div_bset
= has_denom
+ 1 + n_param
+ n_in
+ n_div_ma
;
3923 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
);
3924 isl_seq_clr(dst
+ has_denom
+ 1 + n_param
, n_in
+ n_div_ma
);
3925 isl_seq_cpy(dst
+ o_div_bset
,
3926 src
+ has_denom
+ 1 + n_param
+ n_out
, n_div_bset
);
3928 isl_int_set_si(f
, 1);
3930 for (i
= 0; i
< n_out
; ++i
) {
3931 if (isl_int_is_zero(src
[has_denom
+ 1 + n_param
+ i
]))
3933 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
3934 isl_int_mul(c2
, f
, src
[has_denom
+ 1 + n_param
+ i
]);
3935 isl_int_gcd(g
, c1
, c2
);
3936 isl_int_divexact(c1
, c1
, g
);
3937 isl_int_divexact(c2
, c2
, g
);
3939 isl_int_mul(f
, f
, c1
);
3940 isl_seq_combine(dst
+ has_denom
, c1
, dst
+ has_denom
,
3941 c2
, ma
->p
[i
]->v
->el
+ 1, ma
->p
[i
]->v
->size
- 1);
3942 isl_seq_scale(dst
+ o_div_bset
,
3943 dst
+ o_div_bset
, c1
, n_div_bset
);
3945 isl_int_mul(dst
[0], dst
[0], c1
);
3949 /* Compute the pullback of "aff" by the function represented by "ma".
3950 * In other words, plug in "ma" in "aff". The result is an affine expression
3951 * defined over the domain space of "ma".
3953 * If "aff" is represented by
3955 * (a(p) + b x + c(divs))/d
3957 * and ma is represented by
3959 * x = D(p) + F(y) + G(divs')
3961 * then the result is
3963 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
3965 * The divs in the local space of the input are similarly adjusted
3966 * through a call to isl_local_space_preimage_multi_aff.
3968 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
3969 __isl_take isl_multi_aff
*ma
)
3971 isl_aff
*res
= NULL
;
3972 isl_local_space
*ls
;
3973 int n_div_aff
, n_div_ma
;
3974 isl_int f
, c1
, c2
, g
;
3976 ma
= isl_multi_aff_align_divs(ma
);
3980 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
3981 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
3983 ls
= isl_aff_get_domain_local_space(aff
);
3984 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
3985 res
= isl_aff_alloc(ls
);
3994 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, n_div_ma
, n_div_aff
,
4003 isl_multi_aff_free(ma
);
4004 res
= isl_aff_normalize(res
);
4008 isl_multi_aff_free(ma
);
4013 /* Compute the pullback of "ma1" by the function represented by "ma2".
4014 * In other words, plug in "ma2" in "ma1".
4016 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
4017 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
4020 isl_space
*space
= NULL
;
4022 ma2
= isl_multi_aff_align_divs(ma2
);
4023 ma1
= isl_multi_aff_cow(ma1
);
4027 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
4028 isl_multi_aff_get_space(ma1
));
4030 for (i
= 0; i
< ma1
->n
; ++i
) {
4031 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
4032 isl_multi_aff_copy(ma2
));
4037 ma1
= isl_multi_aff_reset_space(ma1
, space
);
4038 isl_multi_aff_free(ma2
);
4041 isl_space_free(space
);
4042 isl_multi_aff_free(ma2
);
4043 isl_multi_aff_free(ma1
);
4047 /* Extend the local space of "dst" to include the divs
4048 * in the local space of "src".
4050 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
4051 __isl_keep isl_aff
*src
)
4059 return isl_aff_free(dst
);
4061 ctx
= isl_aff_get_ctx(src
);
4062 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
4063 isl_die(ctx
, isl_error_invalid
,
4064 "spaces don't match", goto error
);
4066 if (src
->ls
->div
->n_row
== 0)
4069 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
4070 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
4074 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
4075 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
4083 return isl_aff_free(dst
);
4086 /* Adjust the local spaces of the affine expressions in "maff"
4087 * such that they all have the save divs.
4089 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
4090 __isl_take isl_multi_aff
*maff
)
4098 maff
= isl_multi_aff_cow(maff
);
4102 for (i
= 1; i
< maff
->n
; ++i
)
4103 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
4104 for (i
= 1; i
< maff
->n
; ++i
) {
4105 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
4107 return isl_multi_aff_free(maff
);
4113 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
4115 aff
= isl_aff_cow(aff
);
4119 aff
->ls
= isl_local_space_lift(aff
->ls
);
4121 return isl_aff_free(aff
);
4126 /* Lift "maff" to a space with extra dimensions such that the result
4127 * has no more existentially quantified variables.
4128 * If "ls" is not NULL, then *ls is assigned the local space that lies
4129 * at the basis of the lifting applied to "maff".
4131 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
4132 __isl_give isl_local_space
**ls
)
4146 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
4147 *ls
= isl_local_space_from_space(space
);
4149 return isl_multi_aff_free(maff
);
4154 maff
= isl_multi_aff_cow(maff
);
4155 maff
= isl_multi_aff_align_divs(maff
);
4159 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
4160 space
= isl_multi_aff_get_space(maff
);
4161 space
= isl_space_lift(isl_space_domain(space
), n_div
);
4162 space
= isl_space_extend_domain_with_range(space
,
4163 isl_multi_aff_get_space(maff
));
4165 return isl_multi_aff_free(maff
);
4166 isl_space_free(maff
->space
);
4167 maff
->space
= space
;
4170 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
4172 return isl_multi_aff_free(maff
);
4175 for (i
= 0; i
< maff
->n
; ++i
) {
4176 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
4184 isl_local_space_free(*ls
);
4185 return isl_multi_aff_free(maff
);
4189 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
4191 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
4192 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
4202 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
4203 if (pos
< 0 || pos
>= n_out
)
4204 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4205 "index out of bounds", return NULL
);
4207 space
= isl_pw_multi_aff_get_space(pma
);
4208 space
= isl_space_drop_dims(space
, isl_dim_out
,
4209 pos
+ 1, n_out
- pos
- 1);
4210 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
4212 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
4213 for (i
= 0; i
< pma
->n
; ++i
) {
4215 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
4216 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
4222 /* Return an isl_pw_multi_aff with the given "set" as domain and
4223 * an unnamed zero-dimensional range.
4225 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
4226 __isl_take isl_set
*set
)
4231 space
= isl_set_get_space(set
);
4232 space
= isl_space_from_domain(space
);
4233 ma
= isl_multi_aff_zero(space
);
4234 return isl_pw_multi_aff_alloc(set
, ma
);
4237 /* Add an isl_pw_multi_aff with the given "set" as domain and
4238 * an unnamed zero-dimensional range to *user.
4240 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
4242 isl_union_pw_multi_aff
**upma
= user
;
4243 isl_pw_multi_aff
*pma
;
4245 pma
= isl_pw_multi_aff_from_domain(set
);
4246 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4251 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
4252 * an unnamed zero-dimensional range.
4254 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
4255 __isl_take isl_union_set
*uset
)
4258 isl_union_pw_multi_aff
*upma
;
4263 space
= isl_union_set_get_space(uset
);
4264 upma
= isl_union_pw_multi_aff_empty(space
);
4266 if (isl_union_set_foreach_set(uset
,
4267 &add_pw_multi_aff_from_domain
, &upma
) < 0)
4270 isl_union_set_free(uset
);
4273 isl_union_set_free(uset
);
4274 isl_union_pw_multi_aff_free(upma
);
4278 /* Convert "pma" to an isl_map and add it to *umap.
4280 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
4282 isl_union_map
**umap
= user
;
4285 map
= isl_map_from_pw_multi_aff(pma
);
4286 *umap
= isl_union_map_add_map(*umap
, map
);
4291 /* Construct a union map mapping the domain of the union
4292 * piecewise multi-affine expression to its range, with each dimension
4293 * in the range equated to the corresponding affine expression on its cell.
4295 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
4296 __isl_take isl_union_pw_multi_aff
*upma
)
4299 isl_union_map
*umap
;
4304 space
= isl_union_pw_multi_aff_get_space(upma
);
4305 umap
= isl_union_map_empty(space
);
4307 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4308 &map_from_pw_multi_aff
, &umap
) < 0)
4311 isl_union_pw_multi_aff_free(upma
);
4314 isl_union_pw_multi_aff_free(upma
);
4315 isl_union_map_free(umap
);
4319 /* Local data for bin_entry and the callback "fn".
4321 struct isl_union_pw_multi_aff_bin_data
{
4322 isl_union_pw_multi_aff
*upma2
;
4323 isl_union_pw_multi_aff
*res
;
4324 isl_pw_multi_aff
*pma
;
4325 int (*fn
)(void **entry
, void *user
);
4328 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
4329 * and call data->fn for each isl_pw_multi_aff in data->upma2.
4331 static int bin_entry(void **entry
, void *user
)
4333 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4334 isl_pw_multi_aff
*pma
= *entry
;
4337 if (isl_hash_table_foreach(data
->upma2
->dim
->ctx
, &data
->upma2
->table
,
4338 data
->fn
, data
) < 0)
4344 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
4345 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
4346 * passed as user field) and the isl_pw_multi_aff from upma2 is available
4347 * as *entry. The callback should adjust data->res if desired.
4349 static __isl_give isl_union_pw_multi_aff
*bin_op(
4350 __isl_take isl_union_pw_multi_aff
*upma1
,
4351 __isl_take isl_union_pw_multi_aff
*upma2
,
4352 int (*fn
)(void **entry
, void *user
))
4355 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
4357 space
= isl_union_pw_multi_aff_get_space(upma2
);
4358 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
4359 space
= isl_union_pw_multi_aff_get_space(upma1
);
4360 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
4362 if (!upma1
|| !upma2
)
4366 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->dim
),
4368 if (isl_hash_table_foreach(upma1
->dim
->ctx
, &upma1
->table
,
4369 &bin_entry
, &data
) < 0)
4372 isl_union_pw_multi_aff_free(upma1
);
4373 isl_union_pw_multi_aff_free(upma2
);
4376 isl_union_pw_multi_aff_free(upma1
);
4377 isl_union_pw_multi_aff_free(upma2
);
4378 isl_union_pw_multi_aff_free(data
.res
);
4382 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4383 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4385 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
4386 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4390 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4391 isl_pw_multi_aff_get_space(pma2
));
4392 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4393 &isl_multi_aff_range_product
);
4396 /* Given two isl_pw_multi_affs A -> B and C -> D,
4397 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4399 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
4400 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4402 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4403 &pw_multi_aff_range_product
);
4406 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4407 * construct an isl_pw_multi_aff (A * C) -> (B, D).
4409 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
4410 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4414 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4415 isl_pw_multi_aff_get_space(pma2
));
4416 space
= isl_space_flatten_range(space
);
4417 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4418 &isl_multi_aff_flat_range_product
);
4421 /* Given two isl_pw_multi_affs A -> B and C -> D,
4422 * construct an isl_pw_multi_aff (A * C) -> (B, D).
4424 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
4425 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4427 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4428 &pw_multi_aff_flat_range_product
);
4431 /* If data->pma and *entry have the same domain space, then compute
4432 * their flat range product and the result to data->res.
4434 static int flat_range_product_entry(void **entry
, void *user
)
4436 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4437 isl_pw_multi_aff
*pma2
= *entry
;
4439 if (!isl_space_tuple_match(data
->pma
->dim
, isl_dim_in
,
4440 pma2
->dim
, isl_dim_in
))
4443 pma2
= isl_pw_multi_aff_flat_range_product(
4444 isl_pw_multi_aff_copy(data
->pma
),
4445 isl_pw_multi_aff_copy(pma2
));
4447 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
4452 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
4453 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
4455 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
4456 __isl_take isl_union_pw_multi_aff
*upma1
,
4457 __isl_take isl_union_pw_multi_aff
*upma2
)
4459 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
4462 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4463 * The parameters are assumed to have been aligned.
4465 * The implementation essentially performs an isl_pw_*_on_shared_domain,
4466 * except that it works on two different isl_pw_* types.
4468 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
4469 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
4470 __isl_take isl_pw_aff
*pa
)
4473 isl_pw_multi_aff
*res
= NULL
;
4478 if (!isl_space_tuple_match(pma
->dim
, isl_dim_in
, pa
->dim
, isl_dim_in
))
4479 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4480 "domains don't match", goto error
);
4481 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
4482 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4483 "index out of bounds", goto error
);
4486 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
4488 for (i
= 0; i
< pma
->n
; ++i
) {
4489 for (j
= 0; j
< pa
->n
; ++j
) {
4491 isl_multi_aff
*res_ij
;
4494 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
4495 isl_set_copy(pa
->p
[j
].set
));
4496 empty
= isl_set_plain_is_empty(common
);
4497 if (empty
< 0 || empty
) {
4498 isl_set_free(common
);
4504 res_ij
= isl_multi_aff_set_aff(
4505 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
4506 isl_aff_copy(pa
->p
[j
].aff
));
4507 res_ij
= isl_multi_aff_gist(res_ij
,
4508 isl_set_copy(common
));
4510 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
4514 isl_pw_multi_aff_free(pma
);
4515 isl_pw_aff_free(pa
);
4518 isl_pw_multi_aff_free(pma
);
4519 isl_pw_aff_free(pa
);
4520 return isl_pw_multi_aff_free(res
);
4523 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4525 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
4526 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
4527 __isl_take isl_pw_aff
*pa
)
4531 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
4532 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
4533 if (!isl_space_has_named_params(pma
->dim
) ||
4534 !isl_space_has_named_params(pa
->dim
))
4535 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4536 "unaligned unnamed parameters", goto error
);
4537 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
4538 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
4539 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
4541 isl_pw_multi_aff_free(pma
);
4542 isl_pw_aff_free(pa
);
4549 #include <isl_multi_templ.c>