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, create a new div d = [-f] and return the expression -d.
999 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
1004 if (isl_int_is_one(aff
->v
->el
[0]))
1007 aff
= isl_aff_neg(aff
);
1008 aff
= isl_aff_floor(aff
);
1009 aff
= isl_aff_neg(aff
);
1014 /* Apply the expansion computed by isl_merge_divs.
1015 * The expansion itself is given by "exp" while the resulting
1016 * list of divs is given by "div".
1018 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
1019 __isl_take isl_mat
*div
, int *exp
)
1026 aff
= isl_aff_cow(aff
);
1030 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1031 new_n_div
= isl_mat_rows(div
);
1032 if (new_n_div
< old_n_div
)
1033 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
1034 "not an expansion", goto error
);
1036 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
1040 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
1042 for (i
= new_n_div
- 1; i
>= 0; --i
) {
1043 if (j
>= 0 && exp
[j
] == i
) {
1045 isl_int_swap(aff
->v
->el
[offset
+ i
],
1046 aff
->v
->el
[offset
+ j
]);
1049 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
1052 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
1063 /* Add two affine expressions that live in the same local space.
1065 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
1066 __isl_take isl_aff
*aff2
)
1070 aff1
= isl_aff_cow(aff1
);
1074 aff1
->v
= isl_vec_cow(aff1
->v
);
1080 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
1081 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1082 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
1083 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
1084 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
1085 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
1086 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
1098 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
1099 __isl_take isl_aff
*aff2
)
1109 ctx
= isl_aff_get_ctx(aff1
);
1110 if (!isl_space_is_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
1111 isl_die(ctx
, isl_error_invalid
,
1112 "spaces don't match", goto error
);
1114 if (aff1
->ls
->div
->n_row
== 0 && aff2
->ls
->div
->n_row
== 0)
1115 return add_expanded(aff1
, aff2
);
1117 exp1
= isl_alloc_array(ctx
, int, aff1
->ls
->div
->n_row
);
1118 exp2
= isl_alloc_array(ctx
, int, aff2
->ls
->div
->n_row
);
1122 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
1123 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
1124 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
1128 return add_expanded(aff1
, aff2
);
1137 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
1138 __isl_take isl_aff
*aff2
)
1140 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
1143 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
1147 if (isl_int_is_one(f
))
1150 aff
= isl_aff_cow(aff
);
1153 aff
->v
= isl_vec_cow(aff
->v
);
1155 return isl_aff_free(aff
);
1158 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
1159 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1160 isl_int_divexact(gcd
, f
, gcd
);
1161 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1167 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
1171 if (isl_int_is_one(f
))
1174 aff
= isl_aff_cow(aff
);
1178 if (isl_int_is_zero(f
))
1179 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1180 "cannot scale down by zero", return isl_aff_free(aff
));
1182 aff
->v
= isl_vec_cow(aff
->v
);
1184 return isl_aff_free(aff
);
1187 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
1188 isl_int_gcd(gcd
, gcd
, f
);
1189 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
1190 isl_int_divexact(gcd
, f
, gcd
);
1191 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
1197 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
1205 isl_int_set_ui(v
, f
);
1206 aff
= isl_aff_scale_down(aff
, v
);
1212 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
1213 enum isl_dim_type type
, unsigned pos
, const char *s
)
1215 aff
= isl_aff_cow(aff
);
1218 if (type
== isl_dim_out
)
1219 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1220 "cannot set name of output/set dimension",
1221 return isl_aff_free(aff
));
1222 if (type
== isl_dim_in
)
1224 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
1226 return isl_aff_free(aff
);
1231 __isl_give isl_aff
*isl_aff_set_dim_id(__isl_take isl_aff
*aff
,
1232 enum isl_dim_type type
, unsigned pos
, __isl_take isl_id
*id
)
1234 aff
= isl_aff_cow(aff
);
1236 return isl_id_free(id
);
1237 if (type
== isl_dim_out
)
1238 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1239 "cannot set name of output/set dimension",
1241 if (type
== isl_dim_in
)
1243 aff
->ls
= isl_local_space_set_dim_id(aff
->ls
, type
, pos
, id
);
1245 return isl_aff_free(aff
);
1254 /* Exploit the equalities in "eq" to simplify the affine expression
1255 * and the expressions of the integer divisions in the local space.
1256 * The integer divisions in this local space are assumed to appear
1257 * as regular dimensions in "eq".
1259 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
1260 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1268 if (eq
->n_eq
== 0) {
1269 isl_basic_set_free(eq
);
1273 aff
= isl_aff_cow(aff
);
1277 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
1278 isl_basic_set_copy(eq
));
1282 total
= 1 + isl_space_dim(eq
->dim
, isl_dim_all
);
1284 for (i
= 0; i
< eq
->n_eq
; ++i
) {
1285 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
1286 if (j
< 0 || j
== 0 || j
>= total
)
1289 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
1293 isl_basic_set_free(eq
);
1294 aff
= isl_aff_normalize(aff
);
1297 isl_basic_set_free(eq
);
1302 /* Exploit the equalities in "eq" to simplify the affine expression
1303 * and the expressions of the integer divisions in the local space.
1305 static __isl_give isl_aff
*isl_aff_substitute_equalities(
1306 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
1312 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1314 eq
= isl_basic_set_add(eq
, isl_dim_set
, n_div
);
1315 return isl_aff_substitute_equalities_lifted(aff
, eq
);
1317 isl_basic_set_free(eq
);
1322 /* Look for equalities among the variables shared by context and aff
1323 * and the integer divisions of aff, if any.
1324 * The equalities are then used to eliminate coefficients and/or integer
1325 * divisions from aff.
1327 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
1328 __isl_take isl_set
*context
)
1330 isl_basic_set
*hull
;
1335 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
1337 isl_basic_set
*bset
;
1338 isl_local_space
*ls
;
1339 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
1340 ls
= isl_aff_get_domain_local_space(aff
);
1341 bset
= isl_basic_set_from_local_space(ls
);
1342 bset
= isl_basic_set_lift(bset
);
1343 bset
= isl_basic_set_flatten(bset
);
1344 context
= isl_set_intersect(context
,
1345 isl_set_from_basic_set(bset
));
1348 hull
= isl_set_affine_hull(context
);
1349 return isl_aff_substitute_equalities_lifted(aff
, hull
);
1352 isl_set_free(context
);
1356 __isl_give isl_aff
*isl_aff_gist_params(__isl_take isl_aff
*aff
,
1357 __isl_take isl_set
*context
)
1359 isl_set
*dom_context
= isl_set_universe(isl_aff_get_domain_space(aff
));
1360 dom_context
= isl_set_intersect_params(dom_context
, context
);
1361 return isl_aff_gist(aff
, dom_context
);
1364 /* Return a basic set containing those elements in the space
1365 * of aff where it is non-negative.
1366 * If "rational" is set, then return a rational basic set.
1368 static __isl_give isl_basic_set
*aff_nonneg_basic_set(
1369 __isl_take isl_aff
*aff
, int rational
)
1371 isl_constraint
*ineq
;
1372 isl_basic_set
*bset
;
1374 ineq
= isl_inequality_from_aff(aff
);
1376 bset
= isl_basic_set_from_constraint(ineq
);
1378 bset
= isl_basic_set_set_rational(bset
);
1379 bset
= isl_basic_set_simplify(bset
);
1383 /* Return a basic set containing those elements in the space
1384 * of aff where it is non-negative.
1386 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
1388 return aff_nonneg_basic_set(aff
, 0);
1391 /* Return a basic set containing those elements in the domain space
1392 * of aff where it is negative.
1394 __isl_give isl_basic_set
*isl_aff_neg_basic_set(__isl_take isl_aff
*aff
)
1396 aff
= isl_aff_neg(aff
);
1397 aff
= isl_aff_add_constant_num_si(aff
, -1);
1398 return isl_aff_nonneg_basic_set(aff
);
1401 /* Return a basic set containing those elements in the space
1402 * of aff where it is zero.
1403 * If "rational" is set, then return a rational basic set.
1405 static __isl_give isl_basic_set
*aff_zero_basic_set(__isl_take isl_aff
*aff
,
1408 isl_constraint
*ineq
;
1409 isl_basic_set
*bset
;
1411 ineq
= isl_equality_from_aff(aff
);
1413 bset
= isl_basic_set_from_constraint(ineq
);
1415 bset
= isl_basic_set_set_rational(bset
);
1416 bset
= isl_basic_set_simplify(bset
);
1420 /* Return a basic set containing those elements in the space
1421 * of aff where it is zero.
1423 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
1425 return aff_zero_basic_set(aff
, 0);
1428 /* Return a basic set containing those elements in the shared space
1429 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1431 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
1432 __isl_take isl_aff
*aff2
)
1434 aff1
= isl_aff_sub(aff1
, aff2
);
1436 return isl_aff_nonneg_basic_set(aff1
);
1439 /* Return a basic set containing those elements in the shared space
1440 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1442 __isl_give isl_basic_set
*isl_aff_le_basic_set(__isl_take isl_aff
*aff1
,
1443 __isl_take isl_aff
*aff2
)
1445 return isl_aff_ge_basic_set(aff2
, aff1
);
1448 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
1449 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
1451 aff1
= isl_aff_add(aff1
, aff2
);
1452 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
1456 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
1464 /* Check whether the given affine expression has non-zero coefficient
1465 * for any dimension in the given range or if any of these dimensions
1466 * appear with non-zero coefficients in any of the integer divisions
1467 * involved in the affine expression.
1469 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
1470 enum isl_dim_type type
, unsigned first
, unsigned n
)
1482 ctx
= isl_aff_get_ctx(aff
);
1483 if (first
+ n
> isl_aff_dim(aff
, type
))
1484 isl_die(ctx
, isl_error_invalid
,
1485 "range out of bounds", return -1);
1487 active
= isl_local_space_get_active(aff
->ls
, aff
->v
->el
+ 2);
1491 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
1492 for (i
= 0; i
< n
; ++i
)
1493 if (active
[first
+ i
]) {
1506 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
1507 enum isl_dim_type type
, unsigned first
, unsigned n
)
1513 if (type
== isl_dim_out
)
1514 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1515 "cannot drop output/set dimension",
1516 return isl_aff_free(aff
));
1517 if (type
== isl_dim_in
)
1519 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1522 ctx
= isl_aff_get_ctx(aff
);
1523 if (first
+ n
> isl_local_space_dim(aff
->ls
, type
))
1524 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
1525 return isl_aff_free(aff
));
1527 aff
= isl_aff_cow(aff
);
1531 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
1533 return isl_aff_free(aff
);
1535 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
1536 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
1538 return isl_aff_free(aff
);
1543 /* Project the domain of the affine expression onto its parameter space.
1544 * The affine expression may not involve any of the domain dimensions.
1546 __isl_give isl_aff
*isl_aff_project_domain_on_params(__isl_take isl_aff
*aff
)
1552 n
= isl_aff_dim(aff
, isl_dim_in
);
1553 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, 0, n
);
1555 return isl_aff_free(aff
);
1557 isl_die(isl_aff_get_ctx(aff
), isl_error_invalid
,
1558 "affine expression involves some of the domain dimensions",
1559 return isl_aff_free(aff
));
1560 aff
= isl_aff_drop_dims(aff
, isl_dim_in
, 0, n
);
1561 space
= isl_aff_get_domain_space(aff
);
1562 space
= isl_space_params(space
);
1563 aff
= isl_aff_reset_domain_space(aff
, space
);
1567 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
1568 enum isl_dim_type type
, unsigned first
, unsigned n
)
1574 if (type
== isl_dim_out
)
1575 isl_die(aff
->v
->ctx
, isl_error_invalid
,
1576 "cannot insert output/set dimensions",
1577 return isl_aff_free(aff
));
1578 if (type
== isl_dim_in
)
1580 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
1583 ctx
= isl_aff_get_ctx(aff
);
1584 if (first
> isl_local_space_dim(aff
->ls
, type
))
1585 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
1586 return isl_aff_free(aff
));
1588 aff
= isl_aff_cow(aff
);
1592 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
1594 return isl_aff_free(aff
);
1596 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
1597 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
1599 return isl_aff_free(aff
);
1604 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
1605 enum isl_dim_type type
, unsigned n
)
1609 pos
= isl_aff_dim(aff
, type
);
1611 return isl_aff_insert_dims(aff
, type
, pos
, n
);
1614 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
1615 enum isl_dim_type type
, unsigned n
)
1619 pos
= isl_pw_aff_dim(pwaff
, type
);
1621 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
1624 __isl_give isl_pw_aff
*isl_pw_aff_from_aff(__isl_take isl_aff
*aff
)
1626 isl_set
*dom
= isl_set_universe(isl_aff_get_domain_space(aff
));
1627 return isl_pw_aff_alloc(dom
, aff
);
1631 #define PW isl_pw_aff
1635 #define EL_IS_ZERO is_empty
1639 #define IS_ZERO is_empty
1642 #undef DEFAULT_IS_ZERO
1643 #define DEFAULT_IS_ZERO 0
1647 #define NO_MOVE_DIMS
1651 #include <isl_pw_templ.c>
1653 static __isl_give isl_set
*align_params_pw_pw_set_and(
1654 __isl_take isl_pw_aff
*pwaff1
, __isl_take isl_pw_aff
*pwaff2
,
1655 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
1656 __isl_take isl_pw_aff
*pwaff2
))
1658 if (!pwaff1
|| !pwaff2
)
1660 if (isl_space_match(pwaff1
->dim
, isl_dim_param
,
1661 pwaff2
->dim
, isl_dim_param
))
1662 return fn(pwaff1
, pwaff2
);
1663 if (!isl_space_has_named_params(pwaff1
->dim
) ||
1664 !isl_space_has_named_params(pwaff2
->dim
))
1665 isl_die(isl_pw_aff_get_ctx(pwaff1
), isl_error_invalid
,
1666 "unaligned unnamed parameters", goto error
);
1667 pwaff1
= isl_pw_aff_align_params(pwaff1
, isl_pw_aff_get_space(pwaff2
));
1668 pwaff2
= isl_pw_aff_align_params(pwaff2
, isl_pw_aff_get_space(pwaff1
));
1669 return fn(pwaff1
, pwaff2
);
1671 isl_pw_aff_free(pwaff1
);
1672 isl_pw_aff_free(pwaff2
);
1676 /* Compute a piecewise quasi-affine expression with a domain that
1677 * is the union of those of pwaff1 and pwaff2 and such that on each
1678 * cell, the quasi-affine expression is the better (according to cmp)
1679 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1680 * is defined on a given cell, then the associated expression
1681 * is the defined one.
1683 static __isl_give isl_pw_aff
*pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
1684 __isl_take isl_pw_aff
*pwaff2
,
1685 __isl_give isl_basic_set
*(*cmp
)(__isl_take isl_aff
*aff1
,
1686 __isl_take isl_aff
*aff2
))
1693 if (!pwaff1
|| !pwaff2
)
1696 ctx
= isl_space_get_ctx(pwaff1
->dim
);
1697 if (!isl_space_is_equal(pwaff1
->dim
, pwaff2
->dim
))
1698 isl_die(ctx
, isl_error_invalid
,
1699 "arguments should live in same space", goto error
);
1701 if (isl_pw_aff_is_empty(pwaff1
)) {
1702 isl_pw_aff_free(pwaff1
);
1706 if (isl_pw_aff_is_empty(pwaff2
)) {
1707 isl_pw_aff_free(pwaff2
);
1711 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
1712 res
= isl_pw_aff_alloc_size(isl_space_copy(pwaff1
->dim
), n
);
1714 for (i
= 0; i
< pwaff1
->n
; ++i
) {
1715 set
= isl_set_copy(pwaff1
->p
[i
].set
);
1716 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1717 struct isl_set
*common
;
1720 common
= isl_set_intersect(
1721 isl_set_copy(pwaff1
->p
[i
].set
),
1722 isl_set_copy(pwaff2
->p
[j
].set
));
1723 better
= isl_set_from_basic_set(cmp(
1724 isl_aff_copy(pwaff2
->p
[j
].aff
),
1725 isl_aff_copy(pwaff1
->p
[i
].aff
)));
1726 better
= isl_set_intersect(common
, better
);
1727 if (isl_set_plain_is_empty(better
)) {
1728 isl_set_free(better
);
1731 set
= isl_set_subtract(set
, isl_set_copy(better
));
1733 res
= isl_pw_aff_add_piece(res
, better
,
1734 isl_aff_copy(pwaff2
->p
[j
].aff
));
1736 res
= isl_pw_aff_add_piece(res
, set
,
1737 isl_aff_copy(pwaff1
->p
[i
].aff
));
1740 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1741 set
= isl_set_copy(pwaff2
->p
[j
].set
);
1742 for (i
= 0; i
< pwaff1
->n
; ++i
)
1743 set
= isl_set_subtract(set
,
1744 isl_set_copy(pwaff1
->p
[i
].set
));
1745 res
= isl_pw_aff_add_piece(res
, set
,
1746 isl_aff_copy(pwaff2
->p
[j
].aff
));
1749 isl_pw_aff_free(pwaff1
);
1750 isl_pw_aff_free(pwaff2
);
1754 isl_pw_aff_free(pwaff1
);
1755 isl_pw_aff_free(pwaff2
);
1759 /* Compute a piecewise quasi-affine expression with a domain that
1760 * is the union of those of pwaff1 and pwaff2 and such that on each
1761 * cell, the quasi-affine expression is the maximum of those of pwaff1
1762 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1763 * cell, then the associated expression is the defined one.
1765 static __isl_give isl_pw_aff
*pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
1766 __isl_take isl_pw_aff
*pwaff2
)
1768 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_ge_basic_set
);
1771 __isl_give isl_pw_aff
*isl_pw_aff_union_max(__isl_take isl_pw_aff
*pwaff1
,
1772 __isl_take isl_pw_aff
*pwaff2
)
1774 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
1778 /* Compute a piecewise quasi-affine expression with a domain that
1779 * is the union of those of pwaff1 and pwaff2 and such that on each
1780 * cell, the quasi-affine expression is the minimum of those of pwaff1
1781 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1782 * cell, then the associated expression is the defined one.
1784 static __isl_give isl_pw_aff
*pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
1785 __isl_take isl_pw_aff
*pwaff2
)
1787 return pw_aff_union_opt(pwaff1
, pwaff2
, &isl_aff_le_basic_set
);
1790 __isl_give isl_pw_aff
*isl_pw_aff_union_min(__isl_take isl_pw_aff
*pwaff1
,
1791 __isl_take isl_pw_aff
*pwaff2
)
1793 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
,
1797 __isl_give isl_pw_aff
*isl_pw_aff_union_opt(__isl_take isl_pw_aff
*pwaff1
,
1798 __isl_take isl_pw_aff
*pwaff2
, int max
)
1801 return isl_pw_aff_union_max(pwaff1
, pwaff2
);
1803 return isl_pw_aff_union_min(pwaff1
, pwaff2
);
1806 /* Construct a map with as domain the domain of pwaff and
1807 * one-dimensional range corresponding to the affine expressions.
1809 static __isl_give isl_map
*map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1818 dim
= isl_pw_aff_get_space(pwaff
);
1819 map
= isl_map_empty(dim
);
1821 for (i
= 0; i
< pwaff
->n
; ++i
) {
1822 isl_basic_map
*bmap
;
1825 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
1826 map_i
= isl_map_from_basic_map(bmap
);
1827 map_i
= isl_map_intersect_domain(map_i
,
1828 isl_set_copy(pwaff
->p
[i
].set
));
1829 map
= isl_map_union_disjoint(map
, map_i
);
1832 isl_pw_aff_free(pwaff
);
1837 /* Construct a map with as domain the domain of pwaff and
1838 * one-dimensional range corresponding to the affine expressions.
1840 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1844 if (isl_space_is_set(pwaff
->dim
))
1845 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
1846 "space of input is not a map",
1847 return isl_pw_aff_free(pwaff
));
1848 return map_from_pw_aff(pwaff
);
1851 /* Construct a one-dimensional set with as parameter domain
1852 * the domain of pwaff and the single set dimension
1853 * corresponding to the affine expressions.
1855 __isl_give isl_set
*isl_set_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1859 if (!isl_space_is_set(pwaff
->dim
))
1860 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
1861 "space of input is not a set",
1862 return isl_pw_aff_free(pwaff
));
1863 return map_from_pw_aff(pwaff
);
1866 /* Return a set containing those elements in the domain
1867 * of pwaff where it is non-negative.
1869 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
1877 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
1879 for (i
= 0; i
< pwaff
->n
; ++i
) {
1880 isl_basic_set
*bset
;
1884 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
1885 bset
= aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
1887 set_i
= isl_set_from_basic_set(bset
);
1888 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
1889 set
= isl_set_union_disjoint(set
, set_i
);
1892 isl_pw_aff_free(pwaff
);
1897 /* Return a set containing those elements in the domain
1898 * of pwaff where it is zero (if complement is 0) or not zero
1899 * (if complement is 1).
1901 static __isl_give isl_set
*pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
,
1910 set
= isl_set_empty(isl_pw_aff_get_domain_space(pwaff
));
1912 for (i
= 0; i
< pwaff
->n
; ++i
) {
1913 isl_basic_set
*bset
;
1914 isl_set
*set_i
, *zero
;
1917 rational
= isl_set_has_rational(pwaff
->p
[i
].set
);
1918 bset
= aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
),
1920 zero
= isl_set_from_basic_set(bset
);
1921 set_i
= isl_set_copy(pwaff
->p
[i
].set
);
1923 set_i
= isl_set_subtract(set_i
, zero
);
1925 set_i
= isl_set_intersect(set_i
, zero
);
1926 set
= isl_set_union_disjoint(set
, set_i
);
1929 isl_pw_aff_free(pwaff
);
1934 /* Return a set containing those elements in the domain
1935 * of pwaff where it is zero.
1937 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
1939 return pw_aff_zero_set(pwaff
, 0);
1942 /* Return a set containing those elements in the domain
1943 * of pwaff where it is not zero.
1945 __isl_give isl_set
*isl_pw_aff_non_zero_set(__isl_take isl_pw_aff
*pwaff
)
1947 return pw_aff_zero_set(pwaff
, 1);
1950 /* Return a set containing those elements in the shared domain
1951 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1953 * We compute the difference on the shared domain and then construct
1954 * the set of values where this difference is non-negative.
1955 * If strict is set, we first subtract 1 from the difference.
1956 * If equal is set, we only return the elements where pwaff1 and pwaff2
1959 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
1960 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
1962 isl_set
*set1
, *set2
;
1964 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
1965 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
1966 set1
= isl_set_intersect(set1
, set2
);
1967 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
1968 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
1969 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
1972 isl_space
*dim
= isl_set_get_space(set1
);
1974 aff
= isl_aff_zero_on_domain(isl_local_space_from_space(dim
));
1975 aff
= isl_aff_add_constant_si(aff
, -1);
1976 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
1981 return isl_pw_aff_zero_set(pwaff1
);
1982 return isl_pw_aff_nonneg_set(pwaff1
);
1985 /* Return a set containing those elements in the shared domain
1986 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1988 static __isl_give isl_set
*pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
1989 __isl_take isl_pw_aff
*pwaff2
)
1991 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
1994 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
1995 __isl_take isl_pw_aff
*pwaff2
)
1997 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_eq_set
);
2000 /* Return a set containing those elements in the shared domain
2001 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2003 static __isl_give isl_set
*pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2004 __isl_take isl_pw_aff
*pwaff2
)
2006 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
2009 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
2010 __isl_take isl_pw_aff
*pwaff2
)
2012 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ge_set
);
2015 /* Return a set containing those elements in the shared domain
2016 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2018 static __isl_give isl_set
*pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2019 __isl_take isl_pw_aff
*pwaff2
)
2021 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
2024 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
2025 __isl_take isl_pw_aff
*pwaff2
)
2027 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_gt_set
);
2030 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
2031 __isl_take isl_pw_aff
*pwaff2
)
2033 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
2036 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
2037 __isl_take isl_pw_aff
*pwaff2
)
2039 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
2042 /* Return a set containing those elements in the shared domain
2043 * of the elements of list1 and list2 where each element in list1
2044 * has the relation specified by "fn" with each element in list2.
2046 static __isl_give isl_set
*pw_aff_list_set(__isl_take isl_pw_aff_list
*list1
,
2047 __isl_take isl_pw_aff_list
*list2
,
2048 __isl_give isl_set
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2049 __isl_take isl_pw_aff
*pwaff2
))
2055 if (!list1
|| !list2
)
2058 ctx
= isl_pw_aff_list_get_ctx(list1
);
2059 if (list1
->n
< 1 || list2
->n
< 1)
2060 isl_die(ctx
, isl_error_invalid
,
2061 "list should contain at least one element", goto error
);
2063 set
= isl_set_universe(isl_pw_aff_get_domain_space(list1
->p
[0]));
2064 for (i
= 0; i
< list1
->n
; ++i
)
2065 for (j
= 0; j
< list2
->n
; ++j
) {
2068 set_ij
= fn(isl_pw_aff_copy(list1
->p
[i
]),
2069 isl_pw_aff_copy(list2
->p
[j
]));
2070 set
= isl_set_intersect(set
, set_ij
);
2073 isl_pw_aff_list_free(list1
);
2074 isl_pw_aff_list_free(list2
);
2077 isl_pw_aff_list_free(list1
);
2078 isl_pw_aff_list_free(list2
);
2082 /* Return a set containing those elements in the shared domain
2083 * of the elements of list1 and list2 where each element in list1
2084 * is equal to each element in list2.
2086 __isl_give isl_set
*isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list
*list1
,
2087 __isl_take isl_pw_aff_list
*list2
)
2089 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_eq_set
);
2092 __isl_give isl_set
*isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list
*list1
,
2093 __isl_take isl_pw_aff_list
*list2
)
2095 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ne_set
);
2098 /* Return a set containing those elements in the shared domain
2099 * of the elements of list1 and list2 where each element in list1
2100 * is less than or equal to each element in list2.
2102 __isl_give isl_set
*isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list
*list1
,
2103 __isl_take isl_pw_aff_list
*list2
)
2105 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_le_set
);
2108 __isl_give isl_set
*isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list
*list1
,
2109 __isl_take isl_pw_aff_list
*list2
)
2111 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_lt_set
);
2114 __isl_give isl_set
*isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list
*list1
,
2115 __isl_take isl_pw_aff_list
*list2
)
2117 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_ge_set
);
2120 __isl_give isl_set
*isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list
*list1
,
2121 __isl_take isl_pw_aff_list
*list2
)
2123 return pw_aff_list_set(list1
, list2
, &isl_pw_aff_gt_set
);
2127 /* Return a set containing those elements in the shared domain
2128 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2130 static __isl_give isl_set
*pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2131 __isl_take isl_pw_aff
*pwaff2
)
2133 isl_set
*set_lt
, *set_gt
;
2135 set_lt
= isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1
),
2136 isl_pw_aff_copy(pwaff2
));
2137 set_gt
= isl_pw_aff_gt_set(pwaff1
, pwaff2
);
2138 return isl_set_union_disjoint(set_lt
, set_gt
);
2141 __isl_give isl_set
*isl_pw_aff_ne_set(__isl_take isl_pw_aff
*pwaff1
,
2142 __isl_take isl_pw_aff
*pwaff2
)
2144 return align_params_pw_pw_set_and(pwaff1
, pwaff2
, &pw_aff_ne_set
);
2147 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
2152 if (isl_int_is_one(v
))
2154 if (!isl_int_is_pos(v
))
2155 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
2156 "factor needs to be positive",
2157 return isl_pw_aff_free(pwaff
));
2158 pwaff
= isl_pw_aff_cow(pwaff
);
2164 for (i
= 0; i
< pwaff
->n
; ++i
) {
2165 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
2166 if (!pwaff
->p
[i
].aff
)
2167 return isl_pw_aff_free(pwaff
);
2173 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
2177 pwaff
= isl_pw_aff_cow(pwaff
);
2183 for (i
= 0; i
< pwaff
->n
; ++i
) {
2184 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
2185 if (!pwaff
->p
[i
].aff
)
2186 return isl_pw_aff_free(pwaff
);
2192 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
2196 pwaff
= isl_pw_aff_cow(pwaff
);
2202 for (i
= 0; i
< pwaff
->n
; ++i
) {
2203 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
2204 if (!pwaff
->p
[i
].aff
)
2205 return isl_pw_aff_free(pwaff
);
2211 /* Assuming that "cond1" and "cond2" are disjoint,
2212 * return an affine expression that is equal to pwaff1 on cond1
2213 * and to pwaff2 on cond2.
2215 static __isl_give isl_pw_aff
*isl_pw_aff_select(
2216 __isl_take isl_set
*cond1
, __isl_take isl_pw_aff
*pwaff1
,
2217 __isl_take isl_set
*cond2
, __isl_take isl_pw_aff
*pwaff2
)
2219 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, cond1
);
2220 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, cond2
);
2222 return isl_pw_aff_add_disjoint(pwaff1
, pwaff2
);
2225 /* Return an affine expression that is equal to pwaff_true for elements
2226 * where "cond" is non-zero and to pwaff_false for elements where "cond"
2228 * That is, return cond ? pwaff_true : pwaff_false;
2230 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_pw_aff
*cond
,
2231 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
2233 isl_set
*cond_true
, *cond_false
;
2235 cond_true
= isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond
));
2236 cond_false
= isl_pw_aff_zero_set(cond
);
2237 return isl_pw_aff_select(cond_true
, pwaff_true
,
2238 cond_false
, pwaff_false
);
2241 int isl_aff_is_cst(__isl_keep isl_aff
*aff
)
2246 return isl_seq_first_non_zero(aff
->v
->el
+ 2, aff
->v
->size
- 2) == -1;
2249 /* Check whether pwaff is a piecewise constant.
2251 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff
*pwaff
)
2258 for (i
= 0; i
< pwaff
->n
; ++i
) {
2259 int is_cst
= isl_aff_is_cst(pwaff
->p
[i
].aff
);
2260 if (is_cst
< 0 || !is_cst
)
2267 __isl_give isl_aff
*isl_aff_mul(__isl_take isl_aff
*aff1
,
2268 __isl_take isl_aff
*aff2
)
2270 if (!isl_aff_is_cst(aff2
) && isl_aff_is_cst(aff1
))
2271 return isl_aff_mul(aff2
, aff1
);
2273 if (!isl_aff_is_cst(aff2
))
2274 isl_die(isl_aff_get_ctx(aff1
), isl_error_invalid
,
2275 "at least one affine expression should be constant",
2278 aff1
= isl_aff_cow(aff1
);
2282 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[1]);
2283 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[0]);
2293 /* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant.
2295 __isl_give isl_aff
*isl_aff_div(__isl_take isl_aff
*aff1
,
2296 __isl_take isl_aff
*aff2
)
2301 is_cst
= isl_aff_is_cst(aff2
);
2305 isl_die(isl_aff_get_ctx(aff2
), isl_error_invalid
,
2306 "second argument should be a constant", goto error
);
2311 neg
= isl_int_is_neg(aff2
->v
->el
[1]);
2313 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2314 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2317 aff1
= isl_aff_scale(aff1
, aff2
->v
->el
[0]);
2318 aff1
= isl_aff_scale_down(aff1
, aff2
->v
->el
[1]);
2321 isl_int_neg(aff2
->v
->el
[0], aff2
->v
->el
[0]);
2322 isl_int_neg(aff2
->v
->el
[1], aff2
->v
->el
[1]);
2333 static __isl_give isl_pw_aff
*pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2334 __isl_take isl_pw_aff
*pwaff2
)
2336 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_add
);
2339 __isl_give isl_pw_aff
*isl_pw_aff_add(__isl_take isl_pw_aff
*pwaff1
,
2340 __isl_take isl_pw_aff
*pwaff2
)
2342 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_add
);
2345 __isl_give isl_pw_aff
*isl_pw_aff_union_add(__isl_take isl_pw_aff
*pwaff1
,
2346 __isl_take isl_pw_aff
*pwaff2
)
2348 return isl_pw_aff_union_add_(pwaff1
, pwaff2
);
2351 static __isl_give isl_pw_aff
*pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2352 __isl_take isl_pw_aff
*pwaff2
)
2354 return isl_pw_aff_on_shared_domain(pwaff1
, pwaff2
, &isl_aff_mul
);
2357 __isl_give isl_pw_aff
*isl_pw_aff_mul(__isl_take isl_pw_aff
*pwaff1
,
2358 __isl_take isl_pw_aff
*pwaff2
)
2360 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_mul
);
2363 static __isl_give isl_pw_aff
*pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2364 __isl_take isl_pw_aff
*pa2
)
2366 return isl_pw_aff_on_shared_domain(pa1
, pa2
, &isl_aff_div
);
2369 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
2371 __isl_give isl_pw_aff
*isl_pw_aff_div(__isl_take isl_pw_aff
*pa1
,
2372 __isl_take isl_pw_aff
*pa2
)
2376 is_cst
= isl_pw_aff_is_cst(pa2
);
2380 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2381 "second argument should be a piecewise constant",
2383 return isl_pw_aff_align_params_pw_pw_and(pa1
, pa2
, &pw_aff_div
);
2385 isl_pw_aff_free(pa1
);
2386 isl_pw_aff_free(pa2
);
2390 /* Compute the quotient of the integer division of "pa1" by "pa2"
2391 * with rounding towards zero.
2392 * "pa2" is assumed to be a piecewise constant.
2394 * In particular, return
2396 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
2399 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_q(__isl_take isl_pw_aff
*pa1
,
2400 __isl_take isl_pw_aff
*pa2
)
2406 is_cst
= isl_pw_aff_is_cst(pa2
);
2410 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2411 "second argument should be a piecewise constant",
2414 pa1
= isl_pw_aff_div(pa1
, pa2
);
2416 cond
= isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1
));
2417 f
= isl_pw_aff_floor(isl_pw_aff_copy(pa1
));
2418 c
= isl_pw_aff_ceil(pa1
);
2419 return isl_pw_aff_cond(isl_set_indicator_function(cond
), f
, c
);
2421 isl_pw_aff_free(pa1
);
2422 isl_pw_aff_free(pa2
);
2426 /* Compute the remainder of the integer division of "pa1" by "pa2"
2427 * with rounding towards zero.
2428 * "pa2" is assumed to be a piecewise constant.
2430 * In particular, return
2432 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
2435 __isl_give isl_pw_aff
*isl_pw_aff_tdiv_r(__isl_take isl_pw_aff
*pa1
,
2436 __isl_take isl_pw_aff
*pa2
)
2441 is_cst
= isl_pw_aff_is_cst(pa2
);
2445 isl_die(isl_pw_aff_get_ctx(pa2
), isl_error_invalid
,
2446 "second argument should be a piecewise constant",
2448 res
= isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1
), isl_pw_aff_copy(pa2
));
2449 res
= isl_pw_aff_mul(pa2
, res
);
2450 res
= isl_pw_aff_sub(pa1
, res
);
2453 isl_pw_aff_free(pa1
);
2454 isl_pw_aff_free(pa2
);
2458 static __isl_give isl_pw_aff
*pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2459 __isl_take isl_pw_aff
*pwaff2
)
2464 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2465 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2466 le
= isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1
),
2467 isl_pw_aff_copy(pwaff2
));
2468 dom
= isl_set_subtract(dom
, isl_set_copy(le
));
2469 return isl_pw_aff_select(le
, pwaff1
, dom
, pwaff2
);
2472 __isl_give isl_pw_aff
*isl_pw_aff_min(__isl_take isl_pw_aff
*pwaff1
,
2473 __isl_take isl_pw_aff
*pwaff2
)
2475 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_min
);
2478 static __isl_give isl_pw_aff
*pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2479 __isl_take isl_pw_aff
*pwaff2
)
2484 dom
= isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
)),
2485 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
)));
2486 ge
= isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1
),
2487 isl_pw_aff_copy(pwaff2
));
2488 dom
= isl_set_subtract(dom
, isl_set_copy(ge
));
2489 return isl_pw_aff_select(ge
, pwaff1
, dom
, pwaff2
);
2492 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
2493 __isl_take isl_pw_aff
*pwaff2
)
2495 return isl_pw_aff_align_params_pw_pw_and(pwaff1
, pwaff2
, &pw_aff_max
);
2498 static __isl_give isl_pw_aff
*pw_aff_list_reduce(
2499 __isl_take isl_pw_aff_list
*list
,
2500 __isl_give isl_pw_aff
*(*fn
)(__isl_take isl_pw_aff
*pwaff1
,
2501 __isl_take isl_pw_aff
*pwaff2
))
2510 ctx
= isl_pw_aff_list_get_ctx(list
);
2512 isl_die(ctx
, isl_error_invalid
,
2513 "list should contain at least one element",
2514 return isl_pw_aff_list_free(list
));
2516 res
= isl_pw_aff_copy(list
->p
[0]);
2517 for (i
= 1; i
< list
->n
; ++i
)
2518 res
= fn(res
, isl_pw_aff_copy(list
->p
[i
]));
2520 isl_pw_aff_list_free(list
);
2524 /* Return an isl_pw_aff that maps each element in the intersection of the
2525 * domains of the elements of list to the minimal corresponding affine
2528 __isl_give isl_pw_aff
*isl_pw_aff_list_min(__isl_take isl_pw_aff_list
*list
)
2530 return pw_aff_list_reduce(list
, &isl_pw_aff_min
);
2533 /* Return an isl_pw_aff that maps each element in the intersection of the
2534 * domains of the elements of list to the maximal corresponding affine
2537 __isl_give isl_pw_aff
*isl_pw_aff_list_max(__isl_take isl_pw_aff_list
*list
)
2539 return pw_aff_list_reduce(list
, &isl_pw_aff_max
);
2542 /* Mark the domains of "pwaff" as rational.
2544 __isl_give isl_pw_aff
*isl_pw_aff_set_rational(__isl_take isl_pw_aff
*pwaff
)
2548 pwaff
= isl_pw_aff_cow(pwaff
);
2554 for (i
= 0; i
< pwaff
->n
; ++i
) {
2555 pwaff
->p
[i
].set
= isl_set_set_rational(pwaff
->p
[i
].set
);
2556 if (!pwaff
->p
[i
].set
)
2557 return isl_pw_aff_free(pwaff
);
2563 /* Mark the domains of the elements of "list" as rational.
2565 __isl_give isl_pw_aff_list
*isl_pw_aff_list_set_rational(
2566 __isl_take isl_pw_aff_list
*list
)
2575 for (i
= 0; i
< list
->n
; ++i
) {
2578 pa
= isl_pw_aff_list_get_pw_aff(list
, i
);
2579 pa
= isl_pw_aff_set_rational(pa
);
2580 list
= isl_pw_aff_list_set_pw_aff(list
, i
, pa
);
2589 #include <isl_multi_templ.c>
2591 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2594 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_multi_aff(
2595 __isl_take isl_multi_aff
*ma
)
2597 isl_set
*dom
= isl_set_universe(isl_multi_aff_get_domain_space(ma
));
2598 return isl_pw_multi_aff_alloc(dom
, ma
);
2601 /* Create a piecewise multi-affine expression in the given space that maps each
2602 * input dimension to the corresponding output dimension.
2604 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_identity(
2605 __isl_take isl_space
*space
)
2607 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space
));
2610 __isl_give isl_multi_aff
*isl_multi_aff_add(__isl_take isl_multi_aff
*maff1
,
2611 __isl_take isl_multi_aff
*maff2
)
2616 maff1
= isl_multi_aff_cow(maff1
);
2617 if (!maff1
|| !maff2
)
2620 ctx
= isl_multi_aff_get_ctx(maff1
);
2621 if (!isl_space_is_equal(maff1
->space
, maff2
->space
))
2622 isl_die(ctx
, isl_error_invalid
,
2623 "spaces don't match", goto error
);
2625 for (i
= 0; i
< maff1
->n
; ++i
) {
2626 maff1
->p
[i
] = isl_aff_add(maff1
->p
[i
],
2627 isl_aff_copy(maff2
->p
[i
]));
2632 isl_multi_aff_free(maff2
);
2635 isl_multi_aff_free(maff1
);
2636 isl_multi_aff_free(maff2
);
2640 /* Given two multi-affine expressions A -> B and C -> D,
2641 * construct a multi-affine expression [A -> C] -> [B -> D].
2643 __isl_give isl_multi_aff
*isl_multi_aff_product(
2644 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
2650 int in1
, in2
, out1
, out2
;
2652 in1
= isl_multi_aff_dim(ma1
, isl_dim_in
);
2653 in2
= isl_multi_aff_dim(ma2
, isl_dim_in
);
2654 out1
= isl_multi_aff_dim(ma1
, isl_dim_out
);
2655 out2
= isl_multi_aff_dim(ma2
, isl_dim_out
);
2656 space
= isl_space_product(isl_multi_aff_get_space(ma1
),
2657 isl_multi_aff_get_space(ma2
));
2658 res
= isl_multi_aff_alloc(isl_space_copy(space
));
2659 space
= isl_space_domain(space
);
2661 for (i
= 0; i
< out1
; ++i
) {
2662 aff
= isl_multi_aff_get_aff(ma1
, i
);
2663 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, in1
, in2
);
2664 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
2665 res
= isl_multi_aff_set_aff(res
, i
, aff
);
2668 for (i
= 0; i
< out2
; ++i
) {
2669 aff
= isl_multi_aff_get_aff(ma2
, i
);
2670 aff
= isl_aff_insert_dims(aff
, isl_dim_in
, 0, in1
);
2671 aff
= isl_aff_reset_domain_space(aff
, isl_space_copy(space
));
2672 res
= isl_multi_aff_set_aff(res
, out1
+ i
, aff
);
2675 isl_space_free(space
);
2676 isl_multi_aff_free(ma1
);
2677 isl_multi_aff_free(ma2
);
2681 /* Exploit the equalities in "eq" to simplify the affine expressions.
2683 static __isl_give isl_multi_aff
*isl_multi_aff_substitute_equalities(
2684 __isl_take isl_multi_aff
*maff
, __isl_take isl_basic_set
*eq
)
2688 maff
= isl_multi_aff_cow(maff
);
2692 for (i
= 0; i
< maff
->n
; ++i
) {
2693 maff
->p
[i
] = isl_aff_substitute_equalities(maff
->p
[i
],
2694 isl_basic_set_copy(eq
));
2699 isl_basic_set_free(eq
);
2702 isl_basic_set_free(eq
);
2703 isl_multi_aff_free(maff
);
2707 __isl_give isl_multi_aff
*isl_multi_aff_scale(__isl_take isl_multi_aff
*maff
,
2712 maff
= isl_multi_aff_cow(maff
);
2716 for (i
= 0; i
< maff
->n
; ++i
) {
2717 maff
->p
[i
] = isl_aff_scale(maff
->p
[i
], f
);
2719 return isl_multi_aff_free(maff
);
2725 __isl_give isl_multi_aff
*isl_multi_aff_add_on_domain(__isl_keep isl_set
*dom
,
2726 __isl_take isl_multi_aff
*maff1
, __isl_take isl_multi_aff
*maff2
)
2728 maff1
= isl_multi_aff_add(maff1
, maff2
);
2729 maff1
= isl_multi_aff_gist(maff1
, isl_set_copy(dom
));
2733 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff
*maff
)
2741 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff
*maff1
,
2742 __isl_keep isl_multi_aff
*maff2
)
2747 if (!maff1
|| !maff2
)
2749 if (maff1
->n
!= maff2
->n
)
2751 equal
= isl_space_is_equal(maff1
->space
, maff2
->space
);
2752 if (equal
< 0 || !equal
)
2755 for (i
= 0; i
< maff1
->n
; ++i
) {
2756 equal
= isl_aff_plain_is_equal(maff1
->p
[i
], maff2
->p
[i
]);
2757 if (equal
< 0 || !equal
)
2764 /* Return the set of domain elements where "ma1" is lexicographically
2765 * smaller than or equal to "ma2".
2767 __isl_give isl_set
*isl_multi_aff_lex_le_set(__isl_take isl_multi_aff
*ma1
,
2768 __isl_take isl_multi_aff
*ma2
)
2770 return isl_multi_aff_lex_ge_set(ma2
, ma1
);
2773 /* Return the set of domain elements where "ma1" is lexicographically
2774 * greater than or equal to "ma2".
2776 __isl_give isl_set
*isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff
*ma1
,
2777 __isl_take isl_multi_aff
*ma2
)
2780 isl_map
*map1
, *map2
;
2783 map1
= isl_map_from_multi_aff(ma1
);
2784 map2
= isl_map_from_multi_aff(ma2
);
2785 map
= isl_map_range_product(map1
, map2
);
2786 space
= isl_space_range(isl_map_get_space(map
));
2787 space
= isl_space_domain(isl_space_unwrap(space
));
2788 ge
= isl_map_lex_ge(space
);
2789 map
= isl_map_intersect_range(map
, isl_map_wrap(ge
));
2791 return isl_map_domain(map
);
2795 #define PW isl_pw_multi_aff
2797 #define EL isl_multi_aff
2799 #define EL_IS_ZERO is_empty
2803 #define IS_ZERO is_empty
2806 #undef DEFAULT_IS_ZERO
2807 #define DEFAULT_IS_ZERO 0
2812 #define NO_INVOLVES_DIMS
2813 #define NO_MOVE_DIMS
2814 #define NO_INSERT_DIMS
2818 #include <isl_pw_templ.c>
2821 #define UNION isl_union_pw_multi_aff
2823 #define PART isl_pw_multi_aff
2825 #define PARTS pw_multi_aff
2826 #define ALIGN_DOMAIN
2830 #include <isl_union_templ.c>
2832 /* Given a function "cmp" that returns the set of elements where
2833 * "ma1" is "better" than "ma2", return the intersection of this
2834 * set with "dom1" and "dom2".
2836 static __isl_give isl_set
*shared_and_better(__isl_keep isl_set
*dom1
,
2837 __isl_keep isl_set
*dom2
, __isl_keep isl_multi_aff
*ma1
,
2838 __isl_keep isl_multi_aff
*ma2
,
2839 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
2840 __isl_take isl_multi_aff
*ma2
))
2846 common
= isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
2847 is_empty
= isl_set_plain_is_empty(common
);
2848 if (is_empty
>= 0 && is_empty
)
2851 return isl_set_free(common
);
2852 better
= cmp(isl_multi_aff_copy(ma1
), isl_multi_aff_copy(ma2
));
2853 better
= isl_set_intersect(common
, better
);
2858 /* Given a function "cmp" that returns the set of elements where
2859 * "ma1" is "better" than "ma2", return a piecewise multi affine
2860 * expression defined on the union of the definition domains
2861 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
2862 * "pma2" on each cell. If only one of the two input functions
2863 * is defined on a given cell, then it is considered the best.
2865 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_opt(
2866 __isl_take isl_pw_multi_aff
*pma1
,
2867 __isl_take isl_pw_multi_aff
*pma2
,
2868 __isl_give isl_set
*(*cmp
)(__isl_take isl_multi_aff
*ma1
,
2869 __isl_take isl_multi_aff
*ma2
))
2872 isl_pw_multi_aff
*res
= NULL
;
2874 isl_set
*set
= NULL
;
2879 ctx
= isl_space_get_ctx(pma1
->dim
);
2880 if (!isl_space_is_equal(pma1
->dim
, pma2
->dim
))
2881 isl_die(ctx
, isl_error_invalid
,
2882 "arguments should live in the same space", goto error
);
2884 if (isl_pw_multi_aff_is_empty(pma1
)) {
2885 isl_pw_multi_aff_free(pma1
);
2889 if (isl_pw_multi_aff_is_empty(pma2
)) {
2890 isl_pw_multi_aff_free(pma2
);
2894 n
= 2 * (pma1
->n
+ 1) * (pma2
->n
+ 1);
2895 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma1
->dim
), n
);
2897 for (i
= 0; i
< pma1
->n
; ++i
) {
2898 set
= isl_set_copy(pma1
->p
[i
].set
);
2899 for (j
= 0; j
< pma2
->n
; ++j
) {
2903 better
= shared_and_better(pma2
->p
[j
].set
,
2904 pma1
->p
[i
].set
, pma2
->p
[j
].maff
,
2905 pma1
->p
[i
].maff
, cmp
);
2906 is_empty
= isl_set_plain_is_empty(better
);
2907 if (is_empty
< 0 || is_empty
) {
2908 isl_set_free(better
);
2913 set
= isl_set_subtract(set
, isl_set_copy(better
));
2915 res
= isl_pw_multi_aff_add_piece(res
, better
,
2916 isl_multi_aff_copy(pma2
->p
[j
].maff
));
2918 res
= isl_pw_multi_aff_add_piece(res
, set
,
2919 isl_multi_aff_copy(pma1
->p
[i
].maff
));
2922 for (j
= 0; j
< pma2
->n
; ++j
) {
2923 set
= isl_set_copy(pma2
->p
[j
].set
);
2924 for (i
= 0; i
< pma1
->n
; ++i
)
2925 set
= isl_set_subtract(set
,
2926 isl_set_copy(pma1
->p
[i
].set
));
2927 res
= isl_pw_multi_aff_add_piece(res
, set
,
2928 isl_multi_aff_copy(pma2
->p
[j
].maff
));
2931 isl_pw_multi_aff_free(pma1
);
2932 isl_pw_multi_aff_free(pma2
);
2936 isl_pw_multi_aff_free(pma1
);
2937 isl_pw_multi_aff_free(pma2
);
2939 return isl_pw_multi_aff_free(res
);
2942 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmax(
2943 __isl_take isl_pw_multi_aff
*pma1
,
2944 __isl_take isl_pw_multi_aff
*pma2
)
2946 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_ge_set
);
2949 /* Given two piecewise multi affine expressions, return a piecewise
2950 * multi-affine expression defined on the union of the definition domains
2951 * of the inputs that is equal to the lexicographic maximum of the two
2952 * inputs on each cell. If only one of the two inputs is defined on
2953 * a given cell, then it is considered to be the maximum.
2955 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmax(
2956 __isl_take isl_pw_multi_aff
*pma1
,
2957 __isl_take isl_pw_multi_aff
*pma2
)
2959 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
2960 &pw_multi_aff_union_lexmax
);
2963 static __isl_give isl_pw_multi_aff
*pw_multi_aff_union_lexmin(
2964 __isl_take isl_pw_multi_aff
*pma1
,
2965 __isl_take isl_pw_multi_aff
*pma2
)
2967 return pw_multi_aff_union_opt(pma1
, pma2
, &isl_multi_aff_lex_le_set
);
2970 /* Given two piecewise multi affine expressions, return a piecewise
2971 * multi-affine expression defined on the union of the definition domains
2972 * of the inputs that is equal to the lexicographic minimum of the two
2973 * inputs on each cell. If only one of the two inputs is defined on
2974 * a given cell, then it is considered to be the minimum.
2976 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_lexmin(
2977 __isl_take isl_pw_multi_aff
*pma1
,
2978 __isl_take isl_pw_multi_aff
*pma2
)
2980 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
2981 &pw_multi_aff_union_lexmin
);
2984 static __isl_give isl_pw_multi_aff
*pw_multi_aff_add(
2985 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
2987 return isl_pw_multi_aff_on_shared_domain(pma1
, pma2
,
2988 &isl_multi_aff_add
);
2991 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_add(
2992 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
2994 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
2998 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_union_add(
2999 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3001 return isl_pw_multi_aff_union_add_(pma1
, pma2
);
3004 /* Given two piecewise multi-affine expressions A -> B and C -> D,
3005 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
3007 static __isl_give isl_pw_multi_aff
*pw_multi_aff_product(
3008 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3012 isl_pw_multi_aff
*res
;
3017 n
= pma1
->n
* pma2
->n
;
3018 space
= isl_space_product(isl_space_copy(pma1
->dim
),
3019 isl_space_copy(pma2
->dim
));
3020 res
= isl_pw_multi_aff_alloc_size(space
, n
);
3022 for (i
= 0; i
< pma1
->n
; ++i
) {
3023 for (j
= 0; j
< pma2
->n
; ++j
) {
3027 domain
= isl_set_product(isl_set_copy(pma1
->p
[i
].set
),
3028 isl_set_copy(pma2
->p
[j
].set
));
3029 ma
= isl_multi_aff_product(
3030 isl_multi_aff_copy(pma1
->p
[i
].maff
),
3031 isl_multi_aff_copy(pma2
->p
[i
].maff
));
3032 res
= isl_pw_multi_aff_add_piece(res
, domain
, ma
);
3036 isl_pw_multi_aff_free(pma1
);
3037 isl_pw_multi_aff_free(pma2
);
3040 isl_pw_multi_aff_free(pma1
);
3041 isl_pw_multi_aff_free(pma2
);
3045 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_product(
3046 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
3048 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
3049 &pw_multi_aff_product
);
3052 /* Construct a map mapping the domain of the piecewise multi-affine expression
3053 * to its range, with each dimension in the range equated to the
3054 * corresponding affine expression on its cell.
3056 __isl_give isl_map
*isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3064 map
= isl_map_empty(isl_pw_multi_aff_get_space(pma
));
3066 for (i
= 0; i
< pma
->n
; ++i
) {
3067 isl_multi_aff
*maff
;
3068 isl_basic_map
*bmap
;
3071 maff
= isl_multi_aff_copy(pma
->p
[i
].maff
);
3072 bmap
= isl_basic_map_from_multi_aff(maff
);
3073 map_i
= isl_map_from_basic_map(bmap
);
3074 map_i
= isl_map_intersect_domain(map_i
,
3075 isl_set_copy(pma
->p
[i
].set
));
3076 map
= isl_map_union_disjoint(map
, map_i
);
3079 isl_pw_multi_aff_free(pma
);
3083 __isl_give isl_set
*isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
)
3088 if (!isl_space_is_set(pma
->dim
))
3089 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
3090 "isl_pw_multi_aff cannot be converted into an isl_set",
3091 return isl_pw_multi_aff_free(pma
));
3093 return isl_map_from_pw_multi_aff(pma
);
3096 /* Given a basic map with a single output dimension that is defined
3097 * in terms of the parameters and input dimensions using an equality,
3098 * extract an isl_aff that expresses the output dimension in terms
3099 * of the parameters and input dimensions.
3101 * Since some applications expect the result of isl_pw_multi_aff_from_map
3102 * to only contain integer affine expressions, we compute the floor
3103 * of the expression before returning.
3105 * This function shares some similarities with
3106 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
3108 static __isl_give isl_aff
*extract_isl_aff_from_basic_map(
3109 __isl_take isl_basic_map
*bmap
)
3114 isl_local_space
*ls
;
3119 if (isl_basic_map_dim(bmap
, isl_dim_out
) != 1)
3120 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3121 "basic map should have a single output dimension",
3123 offset
= isl_basic_map_offset(bmap
, isl_dim_out
);
3124 total
= isl_basic_map_total_dim(bmap
);
3125 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
3126 if (isl_int_is_zero(bmap
->eq
[i
][offset
]))
3128 if (isl_seq_first_non_zero(bmap
->eq
[i
] + offset
+ 1,
3129 1 + total
- (offset
+ 1)) != -1)
3133 if (i
>= bmap
->n_eq
)
3134 isl_die(isl_basic_map_get_ctx(bmap
), isl_error_invalid
,
3135 "unable to find suitable equality", goto error
);
3136 ls
= isl_basic_map_get_local_space(bmap
);
3137 aff
= isl_aff_alloc(isl_local_space_domain(ls
));
3140 if (isl_int_is_neg(bmap
->eq
[i
][offset
]))
3141 isl_seq_cpy(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3143 isl_seq_neg(aff
->v
->el
+ 1, bmap
->eq
[i
], offset
);
3144 isl_seq_clr(aff
->v
->el
+ 1 + offset
, aff
->v
->size
- (1 + offset
));
3145 isl_int_abs(aff
->v
->el
[0], bmap
->eq
[i
][offset
]);
3146 isl_basic_map_free(bmap
);
3148 aff
= isl_aff_remove_unused_divs(aff
);
3149 aff
= isl_aff_floor(aff
);
3152 isl_basic_map_free(bmap
);
3156 /* Given a basic map where each output dimension is defined
3157 * in terms of the parameters and input dimensions using an equality,
3158 * extract an isl_multi_aff that expresses the output dimensions in terms
3159 * of the parameters and input dimensions.
3161 static __isl_give isl_multi_aff
*extract_isl_multi_aff_from_basic_map(
3162 __isl_take isl_basic_map
*bmap
)
3171 ma
= isl_multi_aff_alloc(isl_basic_map_get_space(bmap
));
3172 n_out
= isl_basic_map_dim(bmap
, isl_dim_out
);
3174 for (i
= 0; i
< n_out
; ++i
) {
3175 isl_basic_map
*bmap_i
;
3178 bmap_i
= isl_basic_map_copy(bmap
);
3179 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
,
3180 i
+ 1, n_out
- (1 + i
));
3181 bmap_i
= isl_basic_map_project_out(bmap_i
, isl_dim_out
, 0, i
);
3182 aff
= extract_isl_aff_from_basic_map(bmap_i
);
3183 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3186 isl_basic_map_free(bmap
);
3191 /* Create an isl_pw_multi_aff that is equivalent to
3192 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
3193 * The given basic map is such that each output dimension is defined
3194 * in terms of the parameters and input dimensions using an equality.
3196 static __isl_give isl_pw_multi_aff
*plain_pw_multi_aff_from_map(
3197 __isl_take isl_set
*domain
, __isl_take isl_basic_map
*bmap
)
3201 ma
= extract_isl_multi_aff_from_basic_map(bmap
);
3202 return isl_pw_multi_aff_alloc(domain
, ma
);
3205 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3206 * This obviously only works if the input "map" is single-valued.
3207 * If so, we compute the lexicographic minimum of the image in the form
3208 * of an isl_pw_multi_aff. Since the image is unique, it is equal
3209 * to its lexicographic minimum.
3210 * If the input is not single-valued, we produce an error.
3212 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_base(
3213 __isl_take isl_map
*map
)
3217 isl_pw_multi_aff
*pma
;
3219 sv
= isl_map_is_single_valued(map
);
3223 isl_die(isl_map_get_ctx(map
), isl_error_invalid
,
3224 "map is not single-valued", goto error
);
3225 map
= isl_map_make_disjoint(map
);
3229 pma
= isl_pw_multi_aff_empty(isl_map_get_space(map
));
3231 for (i
= 0; i
< map
->n
; ++i
) {
3232 isl_pw_multi_aff
*pma_i
;
3233 isl_basic_map
*bmap
;
3234 bmap
= isl_basic_map_copy(map
->p
[i
]);
3235 pma_i
= isl_basic_map_lexmin_pw_multi_aff(bmap
);
3236 pma
= isl_pw_multi_aff_add_disjoint(pma
, pma_i
);
3246 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3247 * taking into account that the output dimension at position "d"
3248 * can be represented as
3250 * x = floor((e(...) + c1) / m)
3252 * given that constraint "i" is of the form
3254 * e(...) + c1 - m x >= 0
3257 * Let "map" be of the form
3261 * We construct a mapping
3263 * A -> [A -> x = floor(...)]
3265 * apply that to the map, obtaining
3267 * [A -> x = floor(...)] -> B
3269 * and equate dimension "d" to x.
3270 * We then compute a isl_pw_multi_aff representation of the resulting map
3271 * and plug in the mapping above.
3273 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_div(
3274 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
)
3278 isl_local_space
*ls
;
3286 isl_pw_multi_aff
*pma
;
3289 is_set
= isl_map_is_set(map
);
3291 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3292 ctx
= isl_map_get_ctx(map
);
3293 space
= isl_space_domain(isl_map_get_space(map
));
3294 n_in
= isl_space_dim(space
, isl_dim_set
);
3295 n
= isl_space_dim(space
, isl_dim_all
);
3297 v
= isl_vec_alloc(ctx
, 1 + 1 + n
);
3299 isl_int_neg(v
->el
[0], hull
->ineq
[i
][offset
+ d
]);
3300 isl_seq_cpy(v
->el
+ 1, hull
->ineq
[i
], 1 + n
);
3302 isl_basic_map_free(hull
);
3304 ls
= isl_local_space_from_space(isl_space_copy(space
));
3305 aff
= isl_aff_alloc_vec(ls
, v
);
3306 aff
= isl_aff_floor(aff
);
3308 isl_space_free(space
);
3309 ma
= isl_multi_aff_from_aff(aff
);
3311 ma
= isl_multi_aff_identity(isl_space_map_from_set(space
));
3312 ma
= isl_multi_aff_range_product(ma
,
3313 isl_multi_aff_from_aff(aff
));
3316 insert
= isl_map_from_multi_aff(isl_multi_aff_copy(ma
));
3317 map
= isl_map_apply_domain(map
, insert
);
3318 map
= isl_map_equate(map
, isl_dim_in
, n_in
, isl_dim_out
, d
);
3319 pma
= isl_pw_multi_aff_from_map(map
);
3320 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
3325 /* Is constraint "c" of the form
3327 * e(...) + c1 - m x >= 0
3331 * -e(...) + c2 + m x >= 0
3333 * where m > 1 and e only depends on parameters and input dimemnsions?
3335 * "offset" is the offset of the output dimensions
3336 * "pos" is the position of output dimension x.
3338 static int is_potential_div_constraint(isl_int
*c
, int offset
, int d
, int total
)
3340 if (isl_int_is_zero(c
[offset
+ d
]))
3342 if (isl_int_is_one(c
[offset
+ d
]))
3344 if (isl_int_is_negone(c
[offset
+ d
]))
3346 if (isl_seq_first_non_zero(c
+ offset
, d
) != -1)
3348 if (isl_seq_first_non_zero(c
+ offset
+ d
+ 1,
3349 total
- (offset
+ d
+ 1)) != -1)
3354 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3356 * As a special case, we first check if there is any pair of constraints,
3357 * shared by all the basic maps in "map" that force a given dimension
3358 * to be equal to the floor of some affine combination of the input dimensions.
3360 * In particular, if we can find two constraints
3362 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
3366 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
3368 * where m > 1 and e only depends on parameters and input dimemnsions,
3371 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
3373 * then we know that we can take
3375 * x = floor((e(...) + c1) / m)
3377 * without having to perform any computation.
3379 * Note that we know that
3383 * If c1 + c2 were 0, then we would have detected an equality during
3384 * simplification. If c1 + c2 were negative, then we would have detected
3387 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_check_div(
3388 __isl_take isl_map
*map
)
3394 isl_basic_map
*hull
;
3396 hull
= isl_map_unshifted_simple_hull(isl_map_copy(map
));
3401 dim
= isl_map_dim(map
, isl_dim_out
);
3402 offset
= isl_basic_map_offset(hull
, isl_dim_out
);
3403 total
= 1 + isl_basic_map_total_dim(hull
);
3405 for (d
= 0; d
< dim
; ++d
) {
3406 for (i
= 0; i
< n
; ++i
) {
3407 if (!is_potential_div_constraint(hull
->ineq
[i
],
3410 for (j
= i
+ 1; j
< n
; ++j
) {
3411 if (!isl_seq_is_neg(hull
->ineq
[i
] + 1,
3412 hull
->ineq
[j
] + 1, total
- 1))
3414 isl_int_add(sum
, hull
->ineq
[i
][0],
3416 if (isl_int_abs_lt(sum
,
3417 hull
->ineq
[i
][offset
+ d
]))
3424 if (isl_int_is_pos(hull
->ineq
[j
][offset
+ d
]))
3426 return pw_multi_aff_from_map_div(map
, hull
, d
, j
);
3430 isl_basic_map_free(hull
);
3431 return pw_multi_aff_from_map_base(map
);
3434 isl_basic_map_free(hull
);
3438 /* Given an affine expression
3440 * [A -> B] -> f(A,B)
3442 * construct an isl_multi_aff
3446 * such that dimension "d" in B' is set to "aff" and the remaining
3447 * dimensions are set equal to the corresponding dimensions in B.
3448 * "n_in" is the dimension of the space A.
3449 * "n_out" is the dimension of the space B.
3451 * If "is_set" is set, then the affine expression is of the form
3455 * and we construct an isl_multi_aff
3459 static __isl_give isl_multi_aff
*range_map(__isl_take isl_aff
*aff
, int d
,
3460 unsigned n_in
, unsigned n_out
, int is_set
)
3464 isl_space
*space
, *space2
;
3465 isl_local_space
*ls
;
3467 space
= isl_aff_get_domain_space(aff
);
3468 ls
= isl_local_space_from_space(isl_space_copy(space
));
3469 space2
= isl_space_copy(space
);
3471 space2
= isl_space_range(isl_space_unwrap(space2
));
3472 space
= isl_space_map_from_domain_and_range(space
, space2
);
3473 ma
= isl_multi_aff_alloc(space
);
3474 ma
= isl_multi_aff_set_aff(ma
, d
, aff
);
3476 for (i
= 0; i
< n_out
; ++i
) {
3479 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
3480 isl_dim_set
, n_in
+ i
);
3481 ma
= isl_multi_aff_set_aff(ma
, i
, aff
);
3484 isl_local_space_free(ls
);
3489 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3490 * taking into account that the dimension at position "d" can be written as
3492 * x = m a + f(..) (1)
3494 * where m is equal to "gcd".
3495 * "i" is the index of the equality in "hull" that defines f(..).
3496 * In particular, the equality is of the form
3498 * f(..) - x + m g(existentials) = 0
3502 * -f(..) + x + m g(existentials) = 0
3504 * We basically plug (1) into "map", resulting in a map with "a"
3505 * in the range instead of "x". The corresponding isl_pw_multi_aff
3506 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
3508 * Specifically, given the input map
3512 * We first wrap it into a set
3516 * and define (1) on top of the corresponding space, resulting in "aff".
3517 * We use this to create an isl_multi_aff that maps the output position "d"
3518 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
3519 * We plug this into the wrapped map, unwrap the result and compute the
3520 * corresponding isl_pw_multi_aff.
3521 * The result is an expression
3529 * so that we can plug that into "aff", after extending the latter to
3535 * If "map" is actually a set, then there is no "A" space, meaning
3536 * that we do not need to perform any wrapping, and that the result
3537 * of the recursive call is of the form
3541 * which is plugged into a mapping of the form
3545 static __isl_give isl_pw_multi_aff
*pw_multi_aff_from_map_stride(
3546 __isl_take isl_map
*map
, __isl_take isl_basic_map
*hull
, int d
, int i
,
3551 isl_local_space
*ls
;
3554 isl_pw_multi_aff
*pma
, *id
;
3560 is_set
= isl_map_is_set(map
);
3562 n_in
= isl_basic_map_dim(hull
, isl_dim_in
);
3563 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
3564 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
3569 set
= isl_map_wrap(map
);
3570 space
= isl_space_map_from_set(isl_set_get_space(set
));
3571 ma
= isl_multi_aff_identity(space
);
3572 ls
= isl_local_space_from_space(isl_set_get_space(set
));
3573 aff
= isl_aff_alloc(ls
);
3575 isl_int_set_si(aff
->v
->el
[0], 1);
3576 if (isl_int_is_one(hull
->eq
[i
][o_out
+ d
]))
3577 isl_seq_neg(aff
->v
->el
+ 1, hull
->eq
[i
],
3580 isl_seq_cpy(aff
->v
->el
+ 1, hull
->eq
[i
],
3582 isl_int_set(aff
->v
->el
[1 + o_out
+ d
], gcd
);
3584 ma
= isl_multi_aff_set_aff(ma
, n_in
+ d
, isl_aff_copy(aff
));
3585 set
= isl_set_preimage_multi_aff(set
, ma
);
3587 ma
= range_map(aff
, d
, n_in
, n_out
, is_set
);
3592 map
= isl_set_unwrap(set
);
3593 pma
= isl_pw_multi_aff_from_map(set
);
3596 space
= isl_pw_multi_aff_get_domain_space(pma
);
3597 space
= isl_space_map_from_set(space
);
3598 id
= isl_pw_multi_aff_identity(space
);
3599 pma
= isl_pw_multi_aff_range_product(id
, pma
);
3601 id
= isl_pw_multi_aff_from_multi_aff(ma
);
3602 pma
= isl_pw_multi_aff_pullback_pw_multi_aff(id
, pma
);
3604 isl_basic_map_free(hull
);
3608 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3610 * As a special case, we first check if all output dimensions are uniquely
3611 * defined in terms of the parameters and input dimensions over the entire
3612 * domain. If so, we extract the desired isl_pw_multi_aff directly
3613 * from the affine hull of "map" and its domain.
3615 * Otherwise, we check if any of the output dimensions is "strided".
3616 * That is, we check if can be written as
3620 * with m greater than 1, a some combination of existentiall quantified
3621 * variables and f and expression in the parameters and input dimensions.
3622 * If so, we remove the stride in pw_multi_aff_from_map_stride.
3624 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
3627 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_map(__isl_take isl_map
*map
)
3631 isl_basic_map
*hull
;
3641 hull
= isl_map_affine_hull(isl_map_copy(map
));
3642 sv
= isl_basic_map_plain_is_single_valued(hull
);
3644 return plain_pw_multi_aff_from_map(isl_map_domain(map
), hull
);
3646 hull
= isl_basic_map_free(hull
);
3650 n_div
= isl_basic_map_dim(hull
, isl_dim_div
);
3651 o_div
= isl_basic_map_offset(hull
, isl_dim_div
);
3654 isl_basic_map_free(hull
);
3655 return pw_multi_aff_from_map_check_div(map
);
3660 n_out
= isl_basic_map_dim(hull
, isl_dim_out
);
3661 o_out
= isl_basic_map_offset(hull
, isl_dim_out
);
3663 for (i
= 0; i
< n_out
; ++i
) {
3664 for (j
= 0; j
< hull
->n_eq
; ++j
) {
3665 isl_int
*eq
= hull
->eq
[j
];
3666 isl_pw_multi_aff
*res
;
3668 if (!isl_int_is_one(eq
[o_out
+ i
]) &&
3669 !isl_int_is_negone(eq
[o_out
+ i
]))
3671 if (isl_seq_first_non_zero(eq
+ o_out
, i
) != -1)
3673 if (isl_seq_first_non_zero(eq
+ o_out
+ i
+ 1,
3674 n_out
- (i
+ 1)) != -1)
3676 isl_seq_gcd(eq
+ o_div
, n_div
, &gcd
);
3677 if (isl_int_is_zero(gcd
))
3679 if (isl_int_is_one(gcd
))
3682 res
= pw_multi_aff_from_map_stride(map
, hull
,
3690 isl_basic_map_free(hull
);
3691 return pw_multi_aff_from_map_check_div(map
);
3697 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_set(__isl_take isl_set
*set
)
3699 return isl_pw_multi_aff_from_map(set
);
3702 /* Return the piecewise affine expression "set ? 1 : 0".
3704 __isl_give isl_pw_aff
*isl_set_indicator_function(__isl_take isl_set
*set
)
3707 isl_space
*space
= isl_set_get_space(set
);
3708 isl_local_space
*ls
= isl_local_space_from_space(space
);
3709 isl_aff
*zero
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
3710 isl_aff
*one
= isl_aff_zero_on_domain(ls
);
3712 one
= isl_aff_add_constant_si(one
, 1);
3713 pa
= isl_pw_aff_alloc(isl_set_copy(set
), one
);
3714 set
= isl_set_complement(set
);
3715 pa
= isl_pw_aff_add_disjoint(pa
, isl_pw_aff_alloc(set
, zero
));
3720 /* Plug in "subs" for dimension "type", "pos" of "aff".
3722 * Let i be the dimension to replace and let "subs" be of the form
3726 * and "aff" of the form
3732 * (a f + d g')/(m d)
3734 * where g' is the result of plugging in "subs" in each of the integer
3737 __isl_give isl_aff
*isl_aff_substitute(__isl_take isl_aff
*aff
,
3738 enum isl_dim_type type
, unsigned pos
, __isl_keep isl_aff
*subs
)
3743 aff
= isl_aff_cow(aff
);
3745 return isl_aff_free(aff
);
3747 ctx
= isl_aff_get_ctx(aff
);
3748 if (!isl_space_is_equal(aff
->ls
->dim
, subs
->ls
->dim
))
3749 isl_die(ctx
, isl_error_invalid
,
3750 "spaces don't match", return isl_aff_free(aff
));
3751 if (isl_local_space_dim(subs
->ls
, isl_dim_div
) != 0)
3752 isl_die(ctx
, isl_error_unsupported
,
3753 "cannot handle divs yet", return isl_aff_free(aff
));
3755 aff
->ls
= isl_local_space_substitute(aff
->ls
, type
, pos
, subs
);
3757 return isl_aff_free(aff
);
3759 aff
->v
= isl_vec_cow(aff
->v
);
3761 return isl_aff_free(aff
);
3763 pos
+= isl_local_space_offset(aff
->ls
, type
);
3766 isl_seq_substitute(aff
->v
->el
, pos
, subs
->v
->el
,
3767 aff
->v
->size
, subs
->v
->size
, v
);
3773 /* Plug in "subs" for dimension "type", "pos" in each of the affine
3774 * expressions in "maff".
3776 __isl_give isl_multi_aff
*isl_multi_aff_substitute(
3777 __isl_take isl_multi_aff
*maff
, enum isl_dim_type type
, unsigned pos
,
3778 __isl_keep isl_aff
*subs
)
3782 maff
= isl_multi_aff_cow(maff
);
3784 return isl_multi_aff_free(maff
);
3786 if (type
== isl_dim_in
)
3789 for (i
= 0; i
< maff
->n
; ++i
) {
3790 maff
->p
[i
] = isl_aff_substitute(maff
->p
[i
], type
, pos
, subs
);
3792 return isl_multi_aff_free(maff
);
3798 /* Plug in "subs" for dimension "type", "pos" of "pma".
3800 * pma is of the form
3804 * while subs is of the form
3806 * v' = B_j(v) -> S_j
3808 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
3809 * has a contribution in the result, in particular
3811 * C_ij(S_j) -> M_i(S_j)
3813 * Note that plugging in S_j in C_ij may also result in an empty set
3814 * and this contribution should simply be discarded.
3816 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_substitute(
3817 __isl_take isl_pw_multi_aff
*pma
, enum isl_dim_type type
, unsigned pos
,
3818 __isl_keep isl_pw_aff
*subs
)
3821 isl_pw_multi_aff
*res
;
3824 return isl_pw_multi_aff_free(pma
);
3826 n
= pma
->n
* subs
->n
;
3827 res
= isl_pw_multi_aff_alloc_size(isl_space_copy(pma
->dim
), n
);
3829 for (i
= 0; i
< pma
->n
; ++i
) {
3830 for (j
= 0; j
< subs
->n
; ++j
) {
3832 isl_multi_aff
*res_ij
;
3835 common
= isl_set_intersect(
3836 isl_set_copy(pma
->p
[i
].set
),
3837 isl_set_copy(subs
->p
[j
].set
));
3838 common
= isl_set_substitute(common
,
3839 type
, pos
, subs
->p
[j
].aff
);
3840 empty
= isl_set_plain_is_empty(common
);
3841 if (empty
< 0 || empty
) {
3842 isl_set_free(common
);
3848 res_ij
= isl_multi_aff_substitute(
3849 isl_multi_aff_copy(pma
->p
[i
].maff
),
3850 type
, pos
, subs
->p
[j
].aff
);
3852 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
3856 isl_pw_multi_aff_free(pma
);
3859 isl_pw_multi_aff_free(pma
);
3860 isl_pw_multi_aff_free(res
);
3864 /* Compute the preimage of the affine expression "src" under "ma"
3865 * and put the result in "dst". If "has_denom" is set (to one),
3866 * then "src" and "dst" have an extra initial denominator.
3867 * "n_div_ma" is the number of existentials in "ma"
3868 * "n_div_bset" is the number of existentials in "src"
3869 * The resulting "dst" (which is assumed to have been allocated by
3870 * the caller) contains coefficients for both sets of existentials,
3871 * first those in "ma" and then those in "src".
3872 * f, c1, c2 and g are temporary objects that have been initialized
3875 * Let src represent the expression
3877 * (a(p) + b x + c(divs))/d
3879 * and let ma represent the expressions
3881 * x_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
3883 * We start out with the following expression for dst:
3885 * (a(p) + 0 y + 0 divs' + f \sum_i b_i x_i + c(divs))/d
3887 * with the multiplication factor f initially equal to 1.
3888 * For each x_i that we substitute, we multiply the numerator
3889 * (and denominator) of dst by c_1 = m_i and add the numerator
3890 * of the x_i expression multiplied by c_2 = f b_i,
3891 * after removing the common factors of c_1 and c_2.
3892 * The multiplication factor f also needs to be multiplied by c_1
3893 * for the next x_j, j > i.
3895 void isl_seq_preimage(isl_int
*dst
, isl_int
*src
,
3896 __isl_keep isl_multi_aff
*ma
, int n_div_ma
, int n_div_bset
,
3897 isl_int f
, isl_int c1
, isl_int c2
, isl_int g
, int has_denom
)
3900 int n_param
, n_in
, n_out
;
3903 n_param
= isl_multi_aff_dim(ma
, isl_dim_param
);
3904 n_in
= isl_multi_aff_dim(ma
, isl_dim_in
);
3905 n_out
= isl_multi_aff_dim(ma
, isl_dim_out
);
3907 o_div_bset
= has_denom
+ 1 + n_param
+ n_in
+ n_div_ma
;
3909 isl_seq_cpy(dst
, src
, has_denom
+ 1 + n_param
);
3910 isl_seq_clr(dst
+ has_denom
+ 1 + n_param
, n_in
+ n_div_ma
);
3911 isl_seq_cpy(dst
+ o_div_bset
,
3912 src
+ has_denom
+ 1 + n_param
+ n_out
, n_div_bset
);
3914 isl_int_set_si(f
, 1);
3916 for (i
= 0; i
< n_out
; ++i
) {
3917 if (isl_int_is_zero(src
[has_denom
+ 1 + n_param
+ i
]))
3919 isl_int_set(c1
, ma
->p
[i
]->v
->el
[0]);
3920 isl_int_mul(c2
, f
, src
[has_denom
+ 1 + n_param
+ i
]);
3921 isl_int_gcd(g
, c1
, c2
);
3922 isl_int_divexact(c1
, c1
, g
);
3923 isl_int_divexact(c2
, c2
, g
);
3925 isl_int_mul(f
, f
, c1
);
3926 isl_seq_combine(dst
+ has_denom
, c1
, dst
+ has_denom
,
3927 c2
, ma
->p
[i
]->v
->el
+ 1, ma
->p
[i
]->v
->size
- 1);
3928 isl_seq_scale(dst
+ o_div_bset
,
3929 dst
+ o_div_bset
, c1
, n_div_bset
);
3931 isl_int_mul(dst
[0], dst
[0], c1
);
3935 /* Compute the pullback of "aff" by the function represented by "ma".
3936 * In other words, plug in "ma" in "aff". The result is an affine expression
3937 * defined over the domain space of "ma".
3939 * If "aff" is represented by
3941 * (a(p) + b x + c(divs))/d
3943 * and ma is represented by
3945 * x = D(p) + F(y) + G(divs')
3947 * then the result is
3949 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
3951 * The divs in the local space of the input are similarly adjusted
3952 * through a call to isl_local_space_preimage_multi_aff.
3954 __isl_give isl_aff
*isl_aff_pullback_multi_aff(__isl_take isl_aff
*aff
,
3955 __isl_take isl_multi_aff
*ma
)
3957 isl_aff
*res
= NULL
;
3958 isl_local_space
*ls
;
3959 int n_div_aff
, n_div_ma
;
3960 isl_int f
, c1
, c2
, g
;
3962 ma
= isl_multi_aff_align_divs(ma
);
3966 n_div_aff
= isl_aff_dim(aff
, isl_dim_div
);
3967 n_div_ma
= ma
->n
? isl_aff_dim(ma
->p
[0], isl_dim_div
) : 0;
3969 ls
= isl_aff_get_domain_local_space(aff
);
3970 ls
= isl_local_space_preimage_multi_aff(ls
, isl_multi_aff_copy(ma
));
3971 res
= isl_aff_alloc(ls
);
3980 isl_seq_preimage(res
->v
->el
, aff
->v
->el
, ma
, n_div_ma
, n_div_aff
,
3989 isl_multi_aff_free(ma
);
3990 res
= isl_aff_normalize(res
);
3994 isl_multi_aff_free(ma
);
3999 /* Compute the pullback of "ma1" by the function represented by "ma2".
4000 * In other words, plug in "ma2" in "ma1".
4002 __isl_give isl_multi_aff
*isl_multi_aff_pullback_multi_aff(
4003 __isl_take isl_multi_aff
*ma1
, __isl_take isl_multi_aff
*ma2
)
4006 isl_space
*space
= NULL
;
4008 ma2
= isl_multi_aff_align_divs(ma2
);
4009 ma1
= isl_multi_aff_cow(ma1
);
4013 space
= isl_space_join(isl_multi_aff_get_space(ma2
),
4014 isl_multi_aff_get_space(ma1
));
4016 for (i
= 0; i
< ma1
->n
; ++i
) {
4017 ma1
->p
[i
] = isl_aff_pullback_multi_aff(ma1
->p
[i
],
4018 isl_multi_aff_copy(ma2
));
4023 ma1
= isl_multi_aff_reset_space(ma1
, space
);
4024 isl_multi_aff_free(ma2
);
4027 isl_space_free(space
);
4028 isl_multi_aff_free(ma2
);
4029 isl_multi_aff_free(ma1
);
4033 /* Extend the local space of "dst" to include the divs
4034 * in the local space of "src".
4036 __isl_give isl_aff
*isl_aff_align_divs(__isl_take isl_aff
*dst
,
4037 __isl_keep isl_aff
*src
)
4045 return isl_aff_free(dst
);
4047 ctx
= isl_aff_get_ctx(src
);
4048 if (!isl_space_is_equal(src
->ls
->dim
, dst
->ls
->dim
))
4049 isl_die(ctx
, isl_error_invalid
,
4050 "spaces don't match", goto error
);
4052 if (src
->ls
->div
->n_row
== 0)
4055 exp1
= isl_alloc_array(ctx
, int, src
->ls
->div
->n_row
);
4056 exp2
= isl_alloc_array(ctx
, int, dst
->ls
->div
->n_row
);
4060 div
= isl_merge_divs(src
->ls
->div
, dst
->ls
->div
, exp1
, exp2
);
4061 dst
= isl_aff_expand_divs(dst
, div
, exp2
);
4069 return isl_aff_free(dst
);
4072 /* Adjust the local spaces of the affine expressions in "maff"
4073 * such that they all have the save divs.
4075 __isl_give isl_multi_aff
*isl_multi_aff_align_divs(
4076 __isl_take isl_multi_aff
*maff
)
4084 maff
= isl_multi_aff_cow(maff
);
4088 for (i
= 1; i
< maff
->n
; ++i
)
4089 maff
->p
[0] = isl_aff_align_divs(maff
->p
[0], maff
->p
[i
]);
4090 for (i
= 1; i
< maff
->n
; ++i
) {
4091 maff
->p
[i
] = isl_aff_align_divs(maff
->p
[i
], maff
->p
[0]);
4093 return isl_multi_aff_free(maff
);
4099 __isl_give isl_aff
*isl_aff_lift(__isl_take isl_aff
*aff
)
4101 aff
= isl_aff_cow(aff
);
4105 aff
->ls
= isl_local_space_lift(aff
->ls
);
4107 return isl_aff_free(aff
);
4112 /* Lift "maff" to a space with extra dimensions such that the result
4113 * has no more existentially quantified variables.
4114 * If "ls" is not NULL, then *ls is assigned the local space that lies
4115 * at the basis of the lifting applied to "maff".
4117 __isl_give isl_multi_aff
*isl_multi_aff_lift(__isl_take isl_multi_aff
*maff
,
4118 __isl_give isl_local_space
**ls
)
4132 isl_space
*space
= isl_multi_aff_get_domain_space(maff
);
4133 *ls
= isl_local_space_from_space(space
);
4135 return isl_multi_aff_free(maff
);
4140 maff
= isl_multi_aff_cow(maff
);
4141 maff
= isl_multi_aff_align_divs(maff
);
4145 n_div
= isl_aff_dim(maff
->p
[0], isl_dim_div
);
4146 space
= isl_multi_aff_get_space(maff
);
4147 space
= isl_space_lift(isl_space_domain(space
), n_div
);
4148 space
= isl_space_extend_domain_with_range(space
,
4149 isl_multi_aff_get_space(maff
));
4151 return isl_multi_aff_free(maff
);
4152 isl_space_free(maff
->space
);
4153 maff
->space
= space
;
4156 *ls
= isl_aff_get_domain_local_space(maff
->p
[0]);
4158 return isl_multi_aff_free(maff
);
4161 for (i
= 0; i
< maff
->n
; ++i
) {
4162 maff
->p
[i
] = isl_aff_lift(maff
->p
[i
]);
4170 isl_local_space_free(*ls
);
4171 return isl_multi_aff_free(maff
);
4175 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
4177 __isl_give isl_pw_aff
*isl_pw_multi_aff_get_pw_aff(
4178 __isl_keep isl_pw_multi_aff
*pma
, int pos
)
4188 n_out
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
4189 if (pos
< 0 || pos
>= n_out
)
4190 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4191 "index out of bounds", return NULL
);
4193 space
= isl_pw_multi_aff_get_space(pma
);
4194 space
= isl_space_drop_dims(space
, isl_dim_out
,
4195 pos
+ 1, n_out
- pos
- 1);
4196 space
= isl_space_drop_dims(space
, isl_dim_out
, 0, pos
);
4198 pa
= isl_pw_aff_alloc_size(space
, pma
->n
);
4199 for (i
= 0; i
< pma
->n
; ++i
) {
4201 aff
= isl_multi_aff_get_aff(pma
->p
[i
].maff
, pos
);
4202 pa
= isl_pw_aff_add_piece(pa
, isl_set_copy(pma
->p
[i
].set
), aff
);
4208 /* Return an isl_pw_multi_aff with the given "set" as domain and
4209 * an unnamed zero-dimensional range.
4211 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_from_domain(
4212 __isl_take isl_set
*set
)
4217 space
= isl_set_get_space(set
);
4218 space
= isl_space_from_domain(space
);
4219 ma
= isl_multi_aff_zero(space
);
4220 return isl_pw_multi_aff_alloc(set
, ma
);
4223 /* Add an isl_pw_multi_aff with the given "set" as domain and
4224 * an unnamed zero-dimensional range to *user.
4226 static int add_pw_multi_aff_from_domain(__isl_take isl_set
*set
, void *user
)
4228 isl_union_pw_multi_aff
**upma
= user
;
4229 isl_pw_multi_aff
*pma
;
4231 pma
= isl_pw_multi_aff_from_domain(set
);
4232 *upma
= isl_union_pw_multi_aff_add_pw_multi_aff(*upma
, pma
);
4237 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
4238 * an unnamed zero-dimensional range.
4240 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_from_domain(
4241 __isl_take isl_union_set
*uset
)
4244 isl_union_pw_multi_aff
*upma
;
4249 space
= isl_union_set_get_space(uset
);
4250 upma
= isl_union_pw_multi_aff_empty(space
);
4252 if (isl_union_set_foreach_set(uset
,
4253 &add_pw_multi_aff_from_domain
, &upma
) < 0)
4256 isl_union_set_free(uset
);
4259 isl_union_set_free(uset
);
4260 isl_union_pw_multi_aff_free(upma
);
4264 /* Convert "pma" to an isl_map and add it to *umap.
4266 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff
*pma
, void *user
)
4268 isl_union_map
**umap
= user
;
4271 map
= isl_map_from_pw_multi_aff(pma
);
4272 *umap
= isl_union_map_add_map(*umap
, map
);
4277 /* Construct a union map mapping the domain of the union
4278 * piecewise multi-affine expression to its range, with each dimension
4279 * in the range equated to the corresponding affine expression on its cell.
4281 __isl_give isl_union_map
*isl_union_map_from_union_pw_multi_aff(
4282 __isl_take isl_union_pw_multi_aff
*upma
)
4285 isl_union_map
*umap
;
4290 space
= isl_union_pw_multi_aff_get_space(upma
);
4291 umap
= isl_union_map_empty(space
);
4293 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma
,
4294 &map_from_pw_multi_aff
, &umap
) < 0)
4297 isl_union_pw_multi_aff_free(upma
);
4300 isl_union_pw_multi_aff_free(upma
);
4301 isl_union_map_free(umap
);
4305 /* Local data for bin_entry and the callback "fn".
4307 struct isl_union_pw_multi_aff_bin_data
{
4308 isl_union_pw_multi_aff
*upma2
;
4309 isl_union_pw_multi_aff
*res
;
4310 isl_pw_multi_aff
*pma
;
4311 int (*fn
)(void **entry
, void *user
);
4314 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
4315 * and call data->fn for each isl_pw_multi_aff in data->upma2.
4317 static int bin_entry(void **entry
, void *user
)
4319 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4320 isl_pw_multi_aff
*pma
= *entry
;
4323 if (isl_hash_table_foreach(data
->upma2
->dim
->ctx
, &data
->upma2
->table
,
4324 data
->fn
, data
) < 0)
4330 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
4331 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
4332 * passed as user field) and the isl_pw_multi_aff from upma2 is available
4333 * as *entry. The callback should adjust data->res if desired.
4335 static __isl_give isl_union_pw_multi_aff
*bin_op(
4336 __isl_take isl_union_pw_multi_aff
*upma1
,
4337 __isl_take isl_union_pw_multi_aff
*upma2
,
4338 int (*fn
)(void **entry
, void *user
))
4341 struct isl_union_pw_multi_aff_bin_data data
= { NULL
, NULL
, NULL
, fn
};
4343 space
= isl_union_pw_multi_aff_get_space(upma2
);
4344 upma1
= isl_union_pw_multi_aff_align_params(upma1
, space
);
4345 space
= isl_union_pw_multi_aff_get_space(upma1
);
4346 upma2
= isl_union_pw_multi_aff_align_params(upma2
, space
);
4348 if (!upma1
|| !upma2
)
4352 data
.res
= isl_union_pw_multi_aff_alloc(isl_space_copy(upma1
->dim
),
4354 if (isl_hash_table_foreach(upma1
->dim
->ctx
, &upma1
->table
,
4355 &bin_entry
, &data
) < 0)
4358 isl_union_pw_multi_aff_free(upma1
);
4359 isl_union_pw_multi_aff_free(upma2
);
4362 isl_union_pw_multi_aff_free(upma1
);
4363 isl_union_pw_multi_aff_free(upma2
);
4364 isl_union_pw_multi_aff_free(data
.res
);
4368 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4369 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4371 static __isl_give isl_pw_multi_aff
*pw_multi_aff_range_product(
4372 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4376 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4377 isl_pw_multi_aff_get_space(pma2
));
4378 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4379 &isl_multi_aff_range_product
);
4382 /* Given two isl_pw_multi_affs A -> B and C -> D,
4383 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4385 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_range_product(
4386 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4388 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4389 &pw_multi_aff_range_product
);
4392 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4393 * construct an isl_pw_multi_aff (A * C) -> (B, D).
4395 static __isl_give isl_pw_multi_aff
*pw_multi_aff_flat_range_product(
4396 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4400 space
= isl_space_range_product(isl_pw_multi_aff_get_space(pma1
),
4401 isl_pw_multi_aff_get_space(pma2
));
4402 space
= isl_space_flatten_range(space
);
4403 return isl_pw_multi_aff_on_shared_domain_in(pma1
, pma2
, space
,
4404 &isl_multi_aff_flat_range_product
);
4407 /* Given two isl_pw_multi_affs A -> B and C -> D,
4408 * construct an isl_pw_multi_aff (A * C) -> (B, D).
4410 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_flat_range_product(
4411 __isl_take isl_pw_multi_aff
*pma1
, __isl_take isl_pw_multi_aff
*pma2
)
4413 return isl_pw_multi_aff_align_params_pw_pw_and(pma1
, pma2
,
4414 &pw_multi_aff_flat_range_product
);
4417 /* If data->pma and *entry have the same domain space, then compute
4418 * their flat range product and the result to data->res.
4420 static int flat_range_product_entry(void **entry
, void *user
)
4422 struct isl_union_pw_multi_aff_bin_data
*data
= user
;
4423 isl_pw_multi_aff
*pma2
= *entry
;
4425 if (!isl_space_tuple_match(data
->pma
->dim
, isl_dim_in
,
4426 pma2
->dim
, isl_dim_in
))
4429 pma2
= isl_pw_multi_aff_flat_range_product(
4430 isl_pw_multi_aff_copy(data
->pma
),
4431 isl_pw_multi_aff_copy(pma2
));
4433 data
->res
= isl_union_pw_multi_aff_add_pw_multi_aff(data
->res
, pma2
);
4438 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
4439 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
4441 __isl_give isl_union_pw_multi_aff
*isl_union_pw_multi_aff_flat_range_product(
4442 __isl_take isl_union_pw_multi_aff
*upma1
,
4443 __isl_take isl_union_pw_multi_aff
*upma2
)
4445 return bin_op(upma1
, upma2
, &flat_range_product_entry
);
4448 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4449 * The parameters are assumed to have been aligned.
4451 * The implementation essentially performs an isl_pw_*_on_shared_domain,
4452 * except that it works on two different isl_pw_* types.
4454 static __isl_give isl_pw_multi_aff
*pw_multi_aff_set_pw_aff(
4455 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
4456 __isl_take isl_pw_aff
*pa
)
4459 isl_pw_multi_aff
*res
= NULL
;
4464 if (!isl_space_tuple_match(pma
->dim
, isl_dim_in
, pa
->dim
, isl_dim_in
))
4465 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4466 "domains don't match", goto error
);
4467 if (pos
>= isl_pw_multi_aff_dim(pma
, isl_dim_out
))
4468 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4469 "index out of bounds", goto error
);
4472 res
= isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma
), n
);
4474 for (i
= 0; i
< pma
->n
; ++i
) {
4475 for (j
= 0; j
< pa
->n
; ++j
) {
4477 isl_multi_aff
*res_ij
;
4480 common
= isl_set_intersect(isl_set_copy(pma
->p
[i
].set
),
4481 isl_set_copy(pa
->p
[j
].set
));
4482 empty
= isl_set_plain_is_empty(common
);
4483 if (empty
< 0 || empty
) {
4484 isl_set_free(common
);
4490 res_ij
= isl_multi_aff_set_aff(
4491 isl_multi_aff_copy(pma
->p
[i
].maff
), pos
,
4492 isl_aff_copy(pa
->p
[j
].aff
));
4493 res_ij
= isl_multi_aff_gist(res_ij
,
4494 isl_set_copy(common
));
4496 res
= isl_pw_multi_aff_add_piece(res
, common
, res_ij
);
4500 isl_pw_multi_aff_free(pma
);
4501 isl_pw_aff_free(pa
);
4504 isl_pw_multi_aff_free(pma
);
4505 isl_pw_aff_free(pa
);
4506 return isl_pw_multi_aff_free(res
);
4509 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4511 __isl_give isl_pw_multi_aff
*isl_pw_multi_aff_set_pw_aff(
4512 __isl_take isl_pw_multi_aff
*pma
, unsigned pos
,
4513 __isl_take isl_pw_aff
*pa
)
4517 if (isl_space_match(pma
->dim
, isl_dim_param
, pa
->dim
, isl_dim_param
))
4518 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
4519 if (!isl_space_has_named_params(pma
->dim
) ||
4520 !isl_space_has_named_params(pa
->dim
))
4521 isl_die(isl_pw_multi_aff_get_ctx(pma
), isl_error_invalid
,
4522 "unaligned unnamed parameters", goto error
);
4523 pma
= isl_pw_multi_aff_align_params(pma
, isl_pw_aff_get_space(pa
));
4524 pa
= isl_pw_aff_align_params(pa
, isl_pw_multi_aff_get_space(pma
));
4525 return pw_multi_aff_set_pw_aff(pma
, pos
, pa
);
4527 isl_pw_multi_aff_free(pma
);
4528 isl_pw_aff_free(pa
);
4535 #include <isl_multi_templ.c>