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 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
100 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
105 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
106 isl_vec_copy(aff->v));
109 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
117 return isl_aff_dup(aff);
120 void *isl_aff_free(__isl_take isl_aff *aff)
128 isl_local_space_free(aff->ls);
129 isl_vec_free(aff->v);
136 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
138 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
141 /* Externally, an isl_aff has a map space, but internally, the
142 * ls field corresponds to the domain of that space.
144 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
148 if (type == isl_dim_out)
150 if (type == isl_dim_in)
152 return isl_local_space_dim(aff->ls, type);
155 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
157 return aff ? isl_local_space_get_space(aff->ls) : NULL;
160 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
165 space = isl_local_space_get_space(aff->ls);
166 space = isl_space_from_domain(space);
167 space = isl_space_add_dims(space, isl_dim_out, 1);
171 __isl_give isl_local_space *isl_aff_get_domain_local_space(
172 __isl_keep isl_aff *aff)
174 return aff ? isl_local_space_copy(aff->ls) : NULL;
177 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
182 ls = isl_local_space_copy(aff->ls);
183 ls = isl_local_space_from_domain(ls);
184 ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
188 /* Externally, an isl_aff has a map space, but internally, the
189 * ls field corresponds to the domain of that space.
191 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
192 enum isl_dim_type type, unsigned pos)
196 if (type == isl_dim_out)
198 if (type == isl_dim_in)
200 return isl_local_space_get_dim_name(aff->ls, type, pos);
203 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
204 __isl_take isl_space *dim)
206 aff = isl_aff_cow(aff);
210 aff->ls = isl_local_space_reset_space(aff->ls, dim);
212 return isl_aff_free(aff);
221 /* Reset the space of "aff". This function is called from isl_pw_templ.c
222 * and doesn't know if the space of an element object is represented
223 * directly or through its domain. It therefore passes along both.
225 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
226 __isl_take isl_space *space, __isl_take isl_space *domain)
228 isl_space_free(space);
229 return isl_aff_reset_domain_space(aff, domain);
232 /* Reorder the coefficients of the affine expression based
233 * on the given reodering.
234 * The reordering r is assumed to have been extended with the local
237 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
238 __isl_take isl_reordering *r, int n_div)
246 res = isl_vec_alloc(vec->ctx,
247 2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
248 isl_seq_cpy(res->el, vec->el, 2);
249 isl_seq_clr(res->el + 2, res->size - 2);
250 for (i = 0; i < r->len; ++i)
251 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
253 isl_reordering_free(r);
258 isl_reordering_free(r);
262 /* Reorder the dimensions of the domain of "aff" according
263 * to the given reordering.
265 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
266 __isl_take isl_reordering *r)
268 aff = isl_aff_cow(aff);
272 r = isl_reordering_extend(r, aff->ls->div->n_row);
273 aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
274 aff->ls->div->n_row);
275 aff->ls = isl_local_space_realign(aff->ls, r);
277 if (!aff->v || !aff->ls)
278 return isl_aff_free(aff);
283 isl_reordering_free(r);
287 __isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
288 __isl_take isl_space *model)
293 if (!isl_space_match(aff->ls->dim, isl_dim_param,
294 model, isl_dim_param)) {
297 model = isl_space_drop_dims(model, isl_dim_in,
298 0, isl_space_dim(model, isl_dim_in));
299 model = isl_space_drop_dims(model, isl_dim_out,
300 0, isl_space_dim(model, isl_dim_out));
301 exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
302 exp = isl_reordering_extend_space(exp,
303 isl_aff_get_domain_space(aff));
304 aff = isl_aff_realign_domain(aff, exp);
307 isl_space_free(model);
310 isl_space_free(model);
315 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
320 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
323 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
330 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
331 if (equal < 0 || !equal)
334 return isl_vec_is_equal(aff1->v, aff2->v);
337 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
341 isl_int_set(*v, aff->v->el[0]);
345 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
349 isl_int_set(*v, aff->v->el[1]);
353 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
354 enum isl_dim_type type, int pos, isl_int *v)
359 if (type == isl_dim_out)
360 isl_die(aff->v->ctx, isl_error_invalid,
361 "output/set dimension does not have a coefficient",
363 if (type == isl_dim_in)
366 if (pos >= isl_local_space_dim(aff->ls, type))
367 isl_die(aff->v->ctx, isl_error_invalid,
368 "position out of bounds", return -1);
370 pos += isl_local_space_offset(aff->ls, type);
371 isl_int_set(*v, aff->v->el[1 + pos]);
376 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
378 aff = isl_aff_cow(aff);
382 aff->v = isl_vec_cow(aff->v);
384 return isl_aff_free(aff);
386 isl_int_set(aff->v->el[0], v);
391 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
393 aff = isl_aff_cow(aff);
397 aff->v = isl_vec_cow(aff->v);
399 return isl_aff_free(aff);
401 isl_int_set(aff->v->el[1], v);
406 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
408 if (isl_int_is_zero(v))
411 aff = isl_aff_cow(aff);
415 aff->v = isl_vec_cow(aff->v);
417 return isl_aff_free(aff);
419 isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
424 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
429 isl_int_set_si(t, v);
430 aff = isl_aff_add_constant(aff, t);
436 /* Add "v" to the numerator of the constant term of "aff".
438 __isl_give isl_aff *isl_aff_add_constant_num(__isl_take isl_aff *aff, isl_int v)
440 if (isl_int_is_zero(v))
443 aff = isl_aff_cow(aff);
447 aff->v = isl_vec_cow(aff->v);
449 return isl_aff_free(aff);
451 isl_int_add(aff->v->el[1], aff->v->el[1], v);
456 /* Add "v" to the numerator of the constant term of "aff".
458 __isl_give isl_aff *isl_aff_add_constant_num_si(__isl_take isl_aff *aff, int v)
466 isl_int_set_si(t, v);
467 aff = isl_aff_add_constant_num(aff, t);
473 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
475 aff = isl_aff_cow(aff);
479 aff->v = isl_vec_cow(aff->v);
481 return isl_aff_free(aff);
483 isl_int_set_si(aff->v->el[1], v);
488 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
489 enum isl_dim_type type, int pos, isl_int v)
494 if (type == isl_dim_out)
495 isl_die(aff->v->ctx, isl_error_invalid,
496 "output/set dimension does not have a coefficient",
497 return isl_aff_free(aff));
498 if (type == isl_dim_in)
501 if (pos >= isl_local_space_dim(aff->ls, type))
502 isl_die(aff->v->ctx, isl_error_invalid,
503 "position out of bounds", return isl_aff_free(aff));
505 aff = isl_aff_cow(aff);
509 aff->v = isl_vec_cow(aff->v);
511 return isl_aff_free(aff);
513 pos += isl_local_space_offset(aff->ls, type);
514 isl_int_set(aff->v->el[1 + pos], v);
519 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
520 enum isl_dim_type type, int pos, int v)
525 if (type == isl_dim_out)
526 isl_die(aff->v->ctx, isl_error_invalid,
527 "output/set dimension does not have a coefficient",
528 return isl_aff_free(aff));
529 if (type == isl_dim_in)
532 if (pos >= isl_local_space_dim(aff->ls, type))
533 isl_die(aff->v->ctx, isl_error_invalid,
534 "position out of bounds", return isl_aff_free(aff));
536 aff = isl_aff_cow(aff);
540 aff->v = isl_vec_cow(aff->v);
542 return isl_aff_free(aff);
544 pos += isl_local_space_offset(aff->ls, type);
545 isl_int_set_si(aff->v->el[1 + pos], v);
550 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
551 enum isl_dim_type type, int pos, isl_int v)
556 if (type == isl_dim_out)
557 isl_die(aff->v->ctx, isl_error_invalid,
558 "output/set dimension does not have a coefficient",
559 return isl_aff_free(aff));
560 if (type == isl_dim_in)
563 if (pos >= isl_local_space_dim(aff->ls, type))
564 isl_die(aff->v->ctx, isl_error_invalid,
565 "position out of bounds", return isl_aff_free(aff));
567 aff = isl_aff_cow(aff);
571 aff->v = isl_vec_cow(aff->v);
573 return isl_aff_free(aff);
575 pos += isl_local_space_offset(aff->ls, type);
576 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
581 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
582 enum isl_dim_type type, int pos, int v)
587 isl_int_set_si(t, v);
588 aff = isl_aff_add_coefficient(aff, type, pos, t);
594 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
599 return isl_local_space_get_div(aff->ls, pos);
602 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
604 aff = isl_aff_cow(aff);
607 aff->v = isl_vec_cow(aff->v);
609 return isl_aff_free(aff);
611 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
616 /* Remove divs from the local space that do not appear in the affine
618 * We currently only remove divs at the end.
619 * Some intermediate divs may also not appear directly in the affine
620 * expression, but we would also need to check that no other divs are
621 * defined in terms of them.
623 __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
632 n = isl_local_space_dim(aff->ls, isl_dim_div);
633 off = isl_local_space_offset(aff->ls, isl_dim_div);
635 pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
639 aff = isl_aff_cow(aff);
643 aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
644 aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
645 if (!aff->ls || !aff->v)
646 return isl_aff_free(aff);
651 /* Given two affine expressions "p" of length p_len (including the
652 * denominator and the constant term) and "subs" of length subs_len,
653 * plug in "subs" for the variable at position "pos".
654 * The variables of "subs" and "p" are assumed to match up to subs_len,
655 * but "p" may have additional variables.
656 * "v" is an initialized isl_int that can be used internally.
658 * In particular, if "p" represents the expression
662 * with i the variable at position "pos" and "subs" represents the expression
666 * then the result represents the expression
671 void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
672 int p_len, int subs_len, isl_int v)
674 isl_int_set(v, p[1 + pos]);
675 isl_int_set_si(p[1 + pos], 0);
676 isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
677 isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
678 isl_int_mul(p[0], p[0], subs[0]);
681 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
683 * Even though this function is only called on isl_affs with a single
684 * reference, we are careful to only change aff->v and aff->ls together.
686 static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b)
688 unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
692 ls = isl_local_space_copy(aff->ls);
693 ls = isl_local_space_swap_div(ls, a, b);
694 v = isl_vec_copy(aff->v);
699 isl_int_swap(v->el[1 + off + a], v->el[1 + off + b]);
700 isl_vec_free(aff->v);
702 isl_local_space_free(aff->ls);
708 isl_local_space_free(ls);
709 return isl_aff_free(aff);
712 /* Sort the divs in the local space of "aff" according to
713 * the comparison function "cmp_row" in isl_local_space.c
715 * Reordering divs does not change the semantics of "aff",
716 * so there is no need to call isl_aff_cow.
717 * Moreover, this function is currently only called on isl_affs
718 * with a single reference.
720 static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff)
727 n = isl_aff_dim(aff, isl_dim_div);
728 for (i = 1; i < n; ++i) {
729 for (j = i - 1; j >= 0; --j) {
730 if (isl_mat_cmp_div(aff->ls->div, j, j + 1) <= 0)
732 aff = swap_div(aff, j, j + 1);
741 /* Normalize the representation of "aff".
743 * This function should only be called of "new" isl_affs, i.e.,
744 * with only a single reference. We therefore do not need to
745 * worry about affecting other instances.
747 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
751 aff->v = isl_vec_normalize(aff->v);
753 return isl_aff_free(aff);
754 aff = sort_divs(aff);
755 aff = isl_aff_remove_unused_divs(aff);
759 /* Given f, return floor(f).
760 * If f is an integer expression, then just return f.
761 * If f is a constant, then return the constant floor(f).
762 * Otherwise, if f = g/m, write g = q m + r,
763 * create a new div d = [r/m] and return the expression q + d.
764 * The coefficients in r are taken to lie between -m/2 and m/2.
766 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
776 if (isl_int_is_one(aff->v->el[0]))
779 aff = isl_aff_cow(aff);
783 aff->v = isl_vec_cow(aff->v);
785 return isl_aff_free(aff);
787 if (isl_aff_is_cst(aff)) {
788 isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
789 isl_int_set_si(aff->v->el[0], 1);
793 div = isl_vec_copy(aff->v);
794 div = isl_vec_cow(div);
796 return isl_aff_free(aff);
798 ctx = isl_aff_get_ctx(aff);
799 isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
800 for (i = 1; i < aff->v->size; ++i) {
801 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
802 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
803 if (isl_int_gt(div->el[i], aff->v->el[0])) {
804 isl_int_sub(div->el[i], div->el[i], div->el[0]);
805 isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
809 aff->ls = isl_local_space_add_div(aff->ls, div);
811 return isl_aff_free(aff);
814 aff->v = isl_vec_extend(aff->v, size + 1);
816 return isl_aff_free(aff);
817 isl_int_set_si(aff->v->el[0], 1);
818 isl_int_set_si(aff->v->el[size], 1);
825 * aff mod m = aff - m * floor(aff/m)
827 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
831 res = isl_aff_copy(aff);
832 aff = isl_aff_scale_down(aff, m);
833 aff = isl_aff_floor(aff);
834 aff = isl_aff_scale(aff, m);
835 res = isl_aff_sub(res, aff);
842 * pwaff mod m = pwaff - m * floor(pwaff/m)
844 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
848 res = isl_pw_aff_copy(pwaff);
849 pwaff = isl_pw_aff_scale_down(pwaff, m);
850 pwaff = isl_pw_aff_floor(pwaff);
851 pwaff = isl_pw_aff_scale(pwaff, m);
852 res = isl_pw_aff_sub(res, pwaff);
857 /* Given f, return ceil(f).
858 * If f is an integer expression, then just return f.
859 * Otherwise, create a new div d = [-f] and return the expression -d.
861 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
866 if (isl_int_is_one(aff->v->el[0]))
869 aff = isl_aff_neg(aff);
870 aff = isl_aff_floor(aff);
871 aff = isl_aff_neg(aff);
876 /* Apply the expansion computed by isl_merge_divs.
877 * The expansion itself is given by "exp" while the resulting
878 * list of divs is given by "div".
880 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
881 __isl_take isl_mat *div, int *exp)
888 aff = isl_aff_cow(aff);
892 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
893 new_n_div = isl_mat_rows(div);
894 if (new_n_div < old_n_div)
895 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
896 "not an expansion", goto error);
898 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
902 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
904 for (i = new_n_div - 1; i >= 0; --i) {
905 if (j >= 0 && exp[j] == i) {
907 isl_int_swap(aff->v->el[offset + i],
908 aff->v->el[offset + j]);
911 isl_int_set_si(aff->v->el[offset + i], 0);
914 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
925 /* Add two affine expressions that live in the same local space.
927 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
928 __isl_take isl_aff *aff2)
932 aff1 = isl_aff_cow(aff1);
936 aff1->v = isl_vec_cow(aff1->v);
942 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
943 isl_int_divexact(f, aff2->v->el[0], gcd);
944 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
945 isl_int_divexact(f, aff1->v->el[0], gcd);
946 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
947 isl_int_divexact(f, aff2->v->el[0], gcd);
948 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
960 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
961 __isl_take isl_aff *aff2)
971 ctx = isl_aff_get_ctx(aff1);
972 if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
973 isl_die(ctx, isl_error_invalid,
974 "spaces don't match", goto error);
976 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
977 return add_expanded(aff1, aff2);
979 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
980 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
984 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
985 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
986 aff2 = isl_aff_expand_divs(aff2, div, exp2);
990 return add_expanded(aff1, aff2);
999 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
1000 __isl_take isl_aff *aff2)
1002 return isl_aff_add(aff1, isl_aff_neg(aff2));
1005 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
1009 if (isl_int_is_one(f))
1012 aff = isl_aff_cow(aff);
1015 aff->v = isl_vec_cow(aff->v);
1017 return isl_aff_free(aff);
1020 isl_int_gcd(gcd, aff->v->el[0], f);
1021 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
1022 isl_int_divexact(gcd, f, gcd);
1023 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1029 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
1033 if (isl_int_is_one(f))
1036 aff = isl_aff_cow(aff);
1040 if (isl_int_is_zero(f))
1041 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1042 "cannot scale down by zero", return isl_aff_free(aff));
1044 aff->v = isl_vec_cow(aff->v);
1046 return isl_aff_free(aff);
1049 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
1050 isl_int_gcd(gcd, gcd, f);
1051 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1052 isl_int_divexact(gcd, f, gcd);
1053 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
1059 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
1067 isl_int_set_ui(v, f);
1068 aff = isl_aff_scale_down(aff, v);
1074 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
1075 enum isl_dim_type type, unsigned pos, const char *s)
1077 aff = isl_aff_cow(aff);
1080 if (type == isl_dim_out)
1081 isl_die(aff->v->ctx, isl_error_invalid,
1082 "cannot set name of output/set dimension",
1083 return isl_aff_free(aff));
1084 if (type == isl_dim_in)
1086 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
1088 return isl_aff_free(aff);
1093 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
1094 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1096 aff = isl_aff_cow(aff);
1098 return isl_id_free(id);
1099 if (type == isl_dim_out)
1100 isl_die(aff->v->ctx, isl_error_invalid,
1101 "cannot set name of output/set dimension",
1103 if (type == isl_dim_in)
1105 aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
1107 return isl_aff_free(aff);
1116 /* Exploit the equalities in "eq" to simplify the affine expression
1117 * and the expressions of the integer divisions in the local space.
1118 * The integer divisions in this local space are assumed to appear
1119 * as regular dimensions in "eq".
1121 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
1122 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1130 if (eq->n_eq == 0) {
1131 isl_basic_set_free(eq);
1135 aff = isl_aff_cow(aff);
1139 aff->ls = isl_local_space_substitute_equalities(aff->ls,
1140 isl_basic_set_copy(eq));
1144 total = 1 + isl_space_dim(eq->dim, isl_dim_all);
1146 for (i = 0; i < eq->n_eq; ++i) {
1147 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
1148 if (j < 0 || j == 0 || j >= total)
1151 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
1155 isl_basic_set_free(eq);
1156 aff = isl_aff_normalize(aff);
1159 isl_basic_set_free(eq);
1164 /* Exploit the equalities in "eq" to simplify the affine expression
1165 * and the expressions of the integer divisions in the local space.
1167 static __isl_give isl_aff *isl_aff_substitute_equalities(
1168 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1174 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1176 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
1177 return isl_aff_substitute_equalities_lifted(aff, eq);
1179 isl_basic_set_free(eq);
1184 /* Look for equalities among the variables shared by context and aff
1185 * and the integer divisions of aff, if any.
1186 * The equalities are then used to eliminate coefficients and/or integer
1187 * divisions from aff.
1189 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
1190 __isl_take isl_set *context)
1192 isl_basic_set *hull;
1197 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1199 isl_basic_set *bset;
1200 isl_local_space *ls;
1201 context = isl_set_add_dims(context, isl_dim_set, n_div);
1202 ls = isl_aff_get_domain_local_space(aff);
1203 bset = isl_basic_set_from_local_space(ls);
1204 bset = isl_basic_set_lift(bset);
1205 bset = isl_basic_set_flatten(bset);
1206 context = isl_set_intersect(context,
1207 isl_set_from_basic_set(bset));
1210 hull = isl_set_affine_hull(context);
1211 return isl_aff_substitute_equalities_lifted(aff, hull);
1214 isl_set_free(context);
1218 __isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
1219 __isl_take isl_set *context)
1221 isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
1222 dom_context = isl_set_intersect_params(dom_context, context);
1223 return isl_aff_gist(aff, dom_context);
1226 /* Return a basic set containing those elements in the space
1227 * of aff where it is non-negative.
1229 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
1231 isl_constraint *ineq;
1232 isl_basic_set *bset;
1234 ineq = isl_inequality_from_aff(aff);
1236 bset = isl_basic_set_from_constraint(ineq);
1237 bset = isl_basic_set_simplify(bset);
1241 /* Return a basic set containing those elements in the domain space
1242 * of aff where it is negative.
1244 __isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff)
1246 aff = isl_aff_neg(aff);
1247 aff = isl_aff_add_constant_num_si(aff, -1);
1248 return isl_aff_nonneg_basic_set(aff);
1251 /* Return a basic set containing those elements in the space
1252 * of aff where it is zero.
1254 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1256 isl_constraint *ineq;
1257 isl_basic_set *bset;
1259 ineq = isl_equality_from_aff(aff);
1261 bset = isl_basic_set_from_constraint(ineq);
1262 bset = isl_basic_set_simplify(bset);
1266 /* Return a basic set containing those elements in the shared space
1267 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1269 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1270 __isl_take isl_aff *aff2)
1272 aff1 = isl_aff_sub(aff1, aff2);
1274 return isl_aff_nonneg_basic_set(aff1);
1277 /* Return a basic set containing those elements in the shared space
1278 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1280 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1281 __isl_take isl_aff *aff2)
1283 return isl_aff_ge_basic_set(aff2, aff1);
1286 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1287 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1289 aff1 = isl_aff_add(aff1, aff2);
1290 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1294 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1302 /* Check whether the given affine expression has non-zero coefficient
1303 * for any dimension in the given range or if any of these dimensions
1304 * appear with non-zero coefficients in any of the integer divisions
1305 * involved in the affine expression.
1307 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1308 enum isl_dim_type type, unsigned first, unsigned n)
1320 ctx = isl_aff_get_ctx(aff);
1321 if (first + n > isl_aff_dim(aff, type))
1322 isl_die(ctx, isl_error_invalid,
1323 "range out of bounds", return -1);
1325 active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1329 first += isl_local_space_offset(aff->ls, type) - 1;
1330 for (i = 0; i < n; ++i)
1331 if (active[first + i]) {
1344 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1345 enum isl_dim_type type, unsigned first, unsigned n)
1351 if (type == isl_dim_out)
1352 isl_die(aff->v->ctx, isl_error_invalid,
1353 "cannot drop output/set dimension",
1354 return isl_aff_free(aff));
1355 if (type == isl_dim_in)
1357 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1360 ctx = isl_aff_get_ctx(aff);
1361 if (first + n > isl_local_space_dim(aff->ls, type))
1362 isl_die(ctx, isl_error_invalid, "range out of bounds",
1363 return isl_aff_free(aff));
1365 aff = isl_aff_cow(aff);
1369 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1371 return isl_aff_free(aff);
1373 first += 1 + isl_local_space_offset(aff->ls, type);
1374 aff->v = isl_vec_drop_els(aff->v, first, n);
1376 return isl_aff_free(aff);
1381 /* Project the domain of the affine expression onto its parameter space.
1382 * The affine expression may not involve any of the domain dimensions.
1384 __isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
1390 n = isl_aff_dim(aff, isl_dim_in);
1391 involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
1393 return isl_aff_free(aff);
1395 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1396 "affine expression involves some of the domain dimensions",
1397 return isl_aff_free(aff));
1398 aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
1399 space = isl_aff_get_domain_space(aff);
1400 space = isl_space_params(space);
1401 aff = isl_aff_reset_domain_space(aff, space);
1405 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1406 enum isl_dim_type type, unsigned first, unsigned n)
1412 if (type == isl_dim_out)
1413 isl_die(aff->v->ctx, isl_error_invalid,
1414 "cannot insert output/set dimensions",
1415 return isl_aff_free(aff));
1416 if (type == isl_dim_in)
1418 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1421 ctx = isl_aff_get_ctx(aff);
1422 if (first > isl_local_space_dim(aff->ls, type))
1423 isl_die(ctx, isl_error_invalid, "position out of bounds",
1424 return isl_aff_free(aff));
1426 aff = isl_aff_cow(aff);
1430 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1432 return isl_aff_free(aff);
1434 first += 1 + isl_local_space_offset(aff->ls, type);
1435 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1437 return isl_aff_free(aff);
1442 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1443 enum isl_dim_type type, unsigned n)
1447 pos = isl_aff_dim(aff, type);
1449 return isl_aff_insert_dims(aff, type, pos, n);
1452 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1453 enum isl_dim_type type, unsigned n)
1457 pos = isl_pw_aff_dim(pwaff, type);
1459 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1462 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1464 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1465 return isl_pw_aff_alloc(dom, aff);
1469 #define PW isl_pw_aff
1473 #define EL_IS_ZERO is_empty
1477 #define IS_ZERO is_empty
1480 #undef DEFAULT_IS_ZERO
1481 #define DEFAULT_IS_ZERO 0
1485 #define NO_MOVE_DIMS
1489 #include <isl_pw_templ.c>
1491 static __isl_give isl_set *align_params_pw_pw_set_and(
1492 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1493 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1494 __isl_take isl_pw_aff *pwaff2))
1496 if (!pwaff1 || !pwaff2)
1498 if (isl_space_match(pwaff1->dim, isl_dim_param,
1499 pwaff2->dim, isl_dim_param))
1500 return fn(pwaff1, pwaff2);
1501 if (!isl_space_has_named_params(pwaff1->dim) ||
1502 !isl_space_has_named_params(pwaff2->dim))
1503 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1504 "unaligned unnamed parameters", goto error);
1505 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1506 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1507 return fn(pwaff1, pwaff2);
1509 isl_pw_aff_free(pwaff1);
1510 isl_pw_aff_free(pwaff2);
1514 /* Compute a piecewise quasi-affine expression with a domain that
1515 * is the union of those of pwaff1 and pwaff2 and such that on each
1516 * cell, the quasi-affine expression is the better (according to cmp)
1517 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1518 * is defined on a given cell, then the associated expression
1519 * is the defined one.
1521 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1522 __isl_take isl_pw_aff *pwaff2,
1523 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1524 __isl_take isl_aff *aff2))
1531 if (!pwaff1 || !pwaff2)
1534 ctx = isl_space_get_ctx(pwaff1->dim);
1535 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1536 isl_die(ctx, isl_error_invalid,
1537 "arguments should live in same space", goto error);
1539 if (isl_pw_aff_is_empty(pwaff1)) {
1540 isl_pw_aff_free(pwaff1);
1544 if (isl_pw_aff_is_empty(pwaff2)) {
1545 isl_pw_aff_free(pwaff2);
1549 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1550 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1552 for (i = 0; i < pwaff1->n; ++i) {
1553 set = isl_set_copy(pwaff1->p[i].set);
1554 for (j = 0; j < pwaff2->n; ++j) {
1555 struct isl_set *common;
1558 common = isl_set_intersect(
1559 isl_set_copy(pwaff1->p[i].set),
1560 isl_set_copy(pwaff2->p[j].set));
1561 better = isl_set_from_basic_set(cmp(
1562 isl_aff_copy(pwaff2->p[j].aff),
1563 isl_aff_copy(pwaff1->p[i].aff)));
1564 better = isl_set_intersect(common, better);
1565 if (isl_set_plain_is_empty(better)) {
1566 isl_set_free(better);
1569 set = isl_set_subtract(set, isl_set_copy(better));
1571 res = isl_pw_aff_add_piece(res, better,
1572 isl_aff_copy(pwaff2->p[j].aff));
1574 res = isl_pw_aff_add_piece(res, set,
1575 isl_aff_copy(pwaff1->p[i].aff));
1578 for (j = 0; j < pwaff2->n; ++j) {
1579 set = isl_set_copy(pwaff2->p[j].set);
1580 for (i = 0; i < pwaff1->n; ++i)
1581 set = isl_set_subtract(set,
1582 isl_set_copy(pwaff1->p[i].set));
1583 res = isl_pw_aff_add_piece(res, set,
1584 isl_aff_copy(pwaff2->p[j].aff));
1587 isl_pw_aff_free(pwaff1);
1588 isl_pw_aff_free(pwaff2);
1592 isl_pw_aff_free(pwaff1);
1593 isl_pw_aff_free(pwaff2);
1597 /* Compute a piecewise quasi-affine expression with a domain that
1598 * is the union of those of pwaff1 and pwaff2 and such that on each
1599 * cell, the quasi-affine expression is the maximum of those of pwaff1
1600 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1601 * cell, then the associated expression is the defined one.
1603 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1604 __isl_take isl_pw_aff *pwaff2)
1606 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1609 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1610 __isl_take isl_pw_aff *pwaff2)
1612 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1616 /* Compute a piecewise quasi-affine expression with a domain that
1617 * is the union of those of pwaff1 and pwaff2 and such that on each
1618 * cell, the quasi-affine expression is the minimum of those of pwaff1
1619 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1620 * cell, then the associated expression is the defined one.
1622 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1623 __isl_take isl_pw_aff *pwaff2)
1625 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1628 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1629 __isl_take isl_pw_aff *pwaff2)
1631 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1635 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1636 __isl_take isl_pw_aff *pwaff2, int max)
1639 return isl_pw_aff_union_max(pwaff1, pwaff2);
1641 return isl_pw_aff_union_min(pwaff1, pwaff2);
1644 /* Construct a map with as domain the domain of pwaff and
1645 * one-dimensional range corresponding to the affine expressions.
1647 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1656 dim = isl_pw_aff_get_space(pwaff);
1657 map = isl_map_empty(dim);
1659 for (i = 0; i < pwaff->n; ++i) {
1660 isl_basic_map *bmap;
1663 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1664 map_i = isl_map_from_basic_map(bmap);
1665 map_i = isl_map_intersect_domain(map_i,
1666 isl_set_copy(pwaff->p[i].set));
1667 map = isl_map_union_disjoint(map, map_i);
1670 isl_pw_aff_free(pwaff);
1675 /* Construct a map with as domain the domain of pwaff and
1676 * one-dimensional range corresponding to the affine expressions.
1678 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1682 if (isl_space_is_set(pwaff->dim))
1683 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1684 "space of input is not a map",
1685 return isl_pw_aff_free(pwaff));
1686 return map_from_pw_aff(pwaff);
1689 /* Construct a one-dimensional set with as parameter domain
1690 * the domain of pwaff and the single set dimension
1691 * corresponding to the affine expressions.
1693 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1697 if (!isl_space_is_set(pwaff->dim))
1698 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1699 "space of input is not a set",
1700 return isl_pw_aff_free(pwaff));
1701 return map_from_pw_aff(pwaff);
1704 /* Return a set containing those elements in the domain
1705 * of pwaff where it is non-negative.
1707 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1715 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1717 for (i = 0; i < pwaff->n; ++i) {
1718 isl_basic_set *bset;
1721 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1722 set_i = isl_set_from_basic_set(bset);
1723 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1724 set = isl_set_union_disjoint(set, set_i);
1727 isl_pw_aff_free(pwaff);
1732 /* Return a set containing those elements in the domain
1733 * of pwaff where it is zero (if complement is 0) or not zero
1734 * (if complement is 1).
1736 static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff,
1745 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1747 for (i = 0; i < pwaff->n; ++i) {
1748 isl_basic_set *bset;
1749 isl_set *set_i, *zero;
1751 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1752 zero = isl_set_from_basic_set(bset);
1753 set_i = isl_set_copy(pwaff->p[i].set);
1755 set_i = isl_set_subtract(set_i, zero);
1757 set_i = isl_set_intersect(set_i, zero);
1758 set = isl_set_union_disjoint(set, set_i);
1761 isl_pw_aff_free(pwaff);
1766 /* Return a set containing those elements in the domain
1767 * of pwaff where it is zero.
1769 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1771 return pw_aff_zero_set(pwaff, 0);
1774 /* Return a set containing those elements in the domain
1775 * of pwaff where it is not zero.
1777 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1779 return pw_aff_zero_set(pwaff, 1);
1782 /* Return a set containing those elements in the shared domain
1783 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1785 * We compute the difference on the shared domain and then construct
1786 * the set of values where this difference is non-negative.
1787 * If strict is set, we first subtract 1 from the difference.
1788 * If equal is set, we only return the elements where pwaff1 and pwaff2
1791 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1792 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1794 isl_set *set1, *set2;
1796 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1797 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1798 set1 = isl_set_intersect(set1, set2);
1799 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1800 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1801 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1804 isl_space *dim = isl_set_get_space(set1);
1806 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1807 aff = isl_aff_add_constant_si(aff, -1);
1808 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1813 return isl_pw_aff_zero_set(pwaff1);
1814 return isl_pw_aff_nonneg_set(pwaff1);
1817 /* Return a set containing those elements in the shared domain
1818 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1820 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1821 __isl_take isl_pw_aff *pwaff2)
1823 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1826 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1827 __isl_take isl_pw_aff *pwaff2)
1829 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1832 /* Return a set containing those elements in the shared domain
1833 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1835 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1836 __isl_take isl_pw_aff *pwaff2)
1838 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1841 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1842 __isl_take isl_pw_aff *pwaff2)
1844 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1847 /* Return a set containing those elements in the shared domain
1848 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1850 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1851 __isl_take isl_pw_aff *pwaff2)
1853 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1856 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1857 __isl_take isl_pw_aff *pwaff2)
1859 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1862 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1863 __isl_take isl_pw_aff *pwaff2)
1865 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1868 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1869 __isl_take isl_pw_aff *pwaff2)
1871 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1874 /* Return a set containing those elements in the shared domain
1875 * of the elements of list1 and list2 where each element in list1
1876 * has the relation specified by "fn" with each element in list2.
1878 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1879 __isl_take isl_pw_aff_list *list2,
1880 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1881 __isl_take isl_pw_aff *pwaff2))
1887 if (!list1 || !list2)
1890 ctx = isl_pw_aff_list_get_ctx(list1);
1891 if (list1->n < 1 || list2->n < 1)
1892 isl_die(ctx, isl_error_invalid,
1893 "list should contain at least one element", goto error);
1895 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1896 for (i = 0; i < list1->n; ++i)
1897 for (j = 0; j < list2->n; ++j) {
1900 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1901 isl_pw_aff_copy(list2->p[j]));
1902 set = isl_set_intersect(set, set_ij);
1905 isl_pw_aff_list_free(list1);
1906 isl_pw_aff_list_free(list2);
1909 isl_pw_aff_list_free(list1);
1910 isl_pw_aff_list_free(list2);
1914 /* Return a set containing those elements in the shared domain
1915 * of the elements of list1 and list2 where each element in list1
1916 * is equal to each element in list2.
1918 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1919 __isl_take isl_pw_aff_list *list2)
1921 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1924 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1925 __isl_take isl_pw_aff_list *list2)
1927 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1930 /* Return a set containing those elements in the shared domain
1931 * of the elements of list1 and list2 where each element in list1
1932 * is less than or equal to each element in list2.
1934 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1935 __isl_take isl_pw_aff_list *list2)
1937 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1940 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1941 __isl_take isl_pw_aff_list *list2)
1943 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1946 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1947 __isl_take isl_pw_aff_list *list2)
1949 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1952 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1953 __isl_take isl_pw_aff_list *list2)
1955 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1959 /* Return a set containing those elements in the shared domain
1960 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1962 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1963 __isl_take isl_pw_aff *pwaff2)
1965 isl_set *set_lt, *set_gt;
1967 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1968 isl_pw_aff_copy(pwaff2));
1969 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1970 return isl_set_union_disjoint(set_lt, set_gt);
1973 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1974 __isl_take isl_pw_aff *pwaff2)
1976 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1979 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1984 if (isl_int_is_one(v))
1986 if (!isl_int_is_pos(v))
1987 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1988 "factor needs to be positive",
1989 return isl_pw_aff_free(pwaff));
1990 pwaff = isl_pw_aff_cow(pwaff);
1996 for (i = 0; i < pwaff->n; ++i) {
1997 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1998 if (!pwaff->p[i].aff)
1999 return isl_pw_aff_free(pwaff);
2005 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
2009 pwaff = isl_pw_aff_cow(pwaff);
2015 for (i = 0; i < pwaff->n; ++i) {
2016 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
2017 if (!pwaff->p[i].aff)
2018 return isl_pw_aff_free(pwaff);
2024 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
2028 pwaff = isl_pw_aff_cow(pwaff);
2034 for (i = 0; i < pwaff->n; ++i) {
2035 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
2036 if (!pwaff->p[i].aff)
2037 return isl_pw_aff_free(pwaff);
2043 /* Assuming that "cond1" and "cond2" are disjoint,
2044 * return an affine expression that is equal to pwaff1 on cond1
2045 * and to pwaff2 on cond2.
2047 static __isl_give isl_pw_aff *isl_pw_aff_select(
2048 __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
2049 __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
2051 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
2052 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
2054 return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
2057 /* Return an affine expression that is equal to pwaff_true for elements
2058 * where "cond" is non-zero and to pwaff_false for elements where "cond"
2060 * That is, return cond ? pwaff_true : pwaff_false;
2062 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
2063 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
2065 isl_set *cond_true, *cond_false;
2067 cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
2068 cond_false = isl_pw_aff_zero_set(cond);
2069 return isl_pw_aff_select(cond_true, pwaff_true,
2070 cond_false, pwaff_false);
2073 int isl_aff_is_cst(__isl_keep isl_aff *aff)
2078 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
2081 /* Check whether pwaff is a piecewise constant.
2083 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
2090 for (i = 0; i < pwaff->n; ++i) {
2091 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
2092 if (is_cst < 0 || !is_cst)
2099 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
2100 __isl_take isl_aff *aff2)
2102 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
2103 return isl_aff_mul(aff2, aff1);
2105 if (!isl_aff_is_cst(aff2))
2106 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
2107 "at least one affine expression should be constant",
2110 aff1 = isl_aff_cow(aff1);
2114 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
2115 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
2125 static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
2126 __isl_take isl_pw_aff *pwaff2)
2128 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
2131 __isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
2132 __isl_take isl_pw_aff *pwaff2)
2134 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
2137 __isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
2138 __isl_take isl_pw_aff *pwaff2)
2140 return isl_pw_aff_union_add_(pwaff1, pwaff2);
2143 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2144 __isl_take isl_pw_aff *pwaff2)
2146 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
2149 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2150 __isl_take isl_pw_aff *pwaff2)
2152 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
2155 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2156 __isl_take isl_pw_aff *pwaff2)
2161 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2162 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2163 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
2164 isl_pw_aff_copy(pwaff2));
2165 dom = isl_set_subtract(dom, isl_set_copy(le));
2166 return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
2169 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2170 __isl_take isl_pw_aff *pwaff2)
2172 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
2175 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2176 __isl_take isl_pw_aff *pwaff2)
2181 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2182 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2183 ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
2184 isl_pw_aff_copy(pwaff2));
2185 dom = isl_set_subtract(dom, isl_set_copy(ge));
2186 return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
2189 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2190 __isl_take isl_pw_aff *pwaff2)
2192 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
2195 static __isl_give isl_pw_aff *pw_aff_list_reduce(
2196 __isl_take isl_pw_aff_list *list,
2197 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
2198 __isl_take isl_pw_aff *pwaff2))
2207 ctx = isl_pw_aff_list_get_ctx(list);
2209 isl_die(ctx, isl_error_invalid,
2210 "list should contain at least one element",
2211 return isl_pw_aff_list_free(list));
2213 res = isl_pw_aff_copy(list->p[0]);
2214 for (i = 1; i < list->n; ++i)
2215 res = fn(res, isl_pw_aff_copy(list->p[i]));
2217 isl_pw_aff_list_free(list);
2221 /* Return an isl_pw_aff that maps each element in the intersection of the
2222 * domains of the elements of list to the minimal corresponding affine
2225 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
2227 return pw_aff_list_reduce(list, &isl_pw_aff_min);
2230 /* Return an isl_pw_aff that maps each element in the intersection of the
2231 * domains of the elements of list to the maximal corresponding affine
2234 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
2236 return pw_aff_list_reduce(list, &isl_pw_aff_max);
2242 #include <isl_multi_templ.c>
2244 /* Construct an isl_multi_aff in the given space with value zero in
2245 * each of the output dimensions.
2247 __isl_give isl_multi_aff *isl_multi_aff_zero(__isl_take isl_space *space)
2255 n = isl_space_dim(space , isl_dim_out);
2256 ma = isl_multi_aff_alloc(isl_space_copy(space));
2259 isl_space_free(space);
2262 isl_local_space *ls;
2265 space = isl_space_domain(space);
2266 ls = isl_local_space_from_space(space);
2267 aff = isl_aff_zero_on_domain(ls);
2269 for (i = 0; i < n; ++i)
2270 ma = isl_multi_aff_set_aff(ma, i, isl_aff_copy(aff));
2278 /* Create an isl_multi_aff in the given space that maps each
2279 * input dimension to the corresponding output dimension.
2281 __isl_give isl_multi_aff *isl_multi_aff_identity(__isl_take isl_space *space)
2289 if (isl_space_is_set(space))
2290 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2291 "expecting map space", goto error);
2293 n = isl_space_dim(space, isl_dim_out);
2294 if (n != isl_space_dim(space, isl_dim_in))
2295 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2296 "number of input and output dimensions needs to be "
2297 "the same", goto error);
2299 ma = isl_multi_aff_alloc(isl_space_copy(space));
2302 isl_space_free(space);
2305 isl_local_space *ls;
2308 space = isl_space_domain(space);
2309 ls = isl_local_space_from_space(space);
2310 aff = isl_aff_zero_on_domain(ls);
2312 for (i = 0; i < n; ++i) {
2314 aff_i = isl_aff_copy(aff);
2315 aff_i = isl_aff_add_coefficient_si(aff_i,
2317 ma = isl_multi_aff_set_aff(ma, i, aff_i);
2325 isl_space_free(space);
2329 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2332 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
2333 __isl_take isl_multi_aff *ma)
2335 isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
2336 return isl_pw_multi_aff_alloc(dom, ma);
2339 /* Create a piecewise multi-affine expression in the given space that maps each
2340 * input dimension to the corresponding output dimension.
2342 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity(
2343 __isl_take isl_space *space)
2345 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space));
2348 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
2349 __isl_take isl_multi_aff *maff2)
2354 maff1 = isl_multi_aff_cow(maff1);
2355 if (!maff1 || !maff2)
2358 ctx = isl_multi_aff_get_ctx(maff1);
2359 if (!isl_space_is_equal(maff1->space, maff2->space))
2360 isl_die(ctx, isl_error_invalid,
2361 "spaces don't match", goto error);
2363 for (i = 0; i < maff1->n; ++i) {
2364 maff1->p[i] = isl_aff_add(maff1->p[i],
2365 isl_aff_copy(maff2->p[i]));
2370 isl_multi_aff_free(maff2);
2373 isl_multi_aff_free(maff1);
2374 isl_multi_aff_free(maff2);
2378 /* Given two multi-affine expressions A -> B and C -> D,
2379 * construct a multi-affine expression [A -> C] -> [B -> D].
2381 __isl_give isl_multi_aff *isl_multi_aff_product(
2382 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
2388 int in1, in2, out1, out2;
2390 in1 = isl_multi_aff_dim(ma1, isl_dim_in);
2391 in2 = isl_multi_aff_dim(ma2, isl_dim_in);
2392 out1 = isl_multi_aff_dim(ma1, isl_dim_out);
2393 out2 = isl_multi_aff_dim(ma2, isl_dim_out);
2394 space = isl_space_product(isl_multi_aff_get_space(ma1),
2395 isl_multi_aff_get_space(ma2));
2396 res = isl_multi_aff_alloc(isl_space_copy(space));
2397 space = isl_space_domain(space);
2399 for (i = 0; i < out1; ++i) {
2400 aff = isl_multi_aff_get_aff(ma1, i);
2401 aff = isl_aff_insert_dims(aff, isl_dim_in, in1, in2);
2402 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2403 res = isl_multi_aff_set_aff(res, i, aff);
2406 for (i = 0; i < out2; ++i) {
2407 aff = isl_multi_aff_get_aff(ma2, i);
2408 aff = isl_aff_insert_dims(aff, isl_dim_in, 0, in1);
2409 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2410 res = isl_multi_aff_set_aff(res, out1 + i, aff);
2413 isl_space_free(space);
2414 isl_multi_aff_free(ma1);
2415 isl_multi_aff_free(ma2);
2419 /* Exploit the equalities in "eq" to simplify the affine expressions.
2421 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
2422 __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
2426 maff = isl_multi_aff_cow(maff);
2430 for (i = 0; i < maff->n; ++i) {
2431 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
2432 isl_basic_set_copy(eq));
2437 isl_basic_set_free(eq);
2440 isl_basic_set_free(eq);
2441 isl_multi_aff_free(maff);
2445 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2450 maff = isl_multi_aff_cow(maff);
2454 for (i = 0; i < maff->n; ++i) {
2455 maff->p[i] = isl_aff_scale(maff->p[i], f);
2457 return isl_multi_aff_free(maff);
2463 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2464 __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2466 maff1 = isl_multi_aff_add(maff1, maff2);
2467 maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2471 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2479 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2480 __isl_keep isl_multi_aff *maff2)
2485 if (!maff1 || !maff2)
2487 if (maff1->n != maff2->n)
2489 equal = isl_space_is_equal(maff1->space, maff2->space);
2490 if (equal < 0 || !equal)
2493 for (i = 0; i < maff1->n; ++i) {
2494 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2495 if (equal < 0 || !equal)
2502 __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
2503 __isl_take isl_multi_aff *maff,
2504 enum isl_dim_type type, unsigned pos, const char *s)
2508 maff = isl_multi_aff_cow(maff);
2512 maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
2514 return isl_multi_aff_free(maff);
2516 if (type == isl_dim_out)
2518 for (i = 0; i < maff->n; ++i) {
2519 maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
2521 return isl_multi_aff_free(maff);
2527 __isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
2528 enum isl_dim_type type, unsigned first, unsigned n)
2532 maff = isl_multi_aff_cow(maff);
2536 maff->space = isl_space_drop_dims(maff->space, type, first, n);
2538 return isl_multi_aff_free(maff);
2540 if (type == isl_dim_out) {
2541 for (i = 0; i < n; ++i)
2542 isl_aff_free(maff->p[first + i]);
2543 for (i = first; i + n < maff->n; ++i)
2544 maff->p[i] = maff->p[i + n];
2549 for (i = 0; i < maff->n; ++i) {
2550 maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
2552 return isl_multi_aff_free(maff);
2558 /* Return the set of domain elements where "ma1" is lexicographically
2559 * smaller than or equal to "ma2".
2561 __isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1,
2562 __isl_take isl_multi_aff *ma2)
2564 return isl_multi_aff_lex_ge_set(ma2, ma1);
2567 /* Return the set of domain elements where "ma1" is lexicographically
2568 * greater than or equal to "ma2".
2570 __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
2571 __isl_take isl_multi_aff *ma2)
2574 isl_map *map1, *map2;
2577 map1 = isl_map_from_multi_aff(ma1);
2578 map2 = isl_map_from_multi_aff(ma2);
2579 map = isl_map_range_product(map1, map2);
2580 space = isl_space_range(isl_map_get_space(map));
2581 space = isl_space_domain(isl_space_unwrap(space));
2582 ge = isl_map_lex_ge(space);
2583 map = isl_map_intersect_range(map, isl_map_wrap(ge));
2585 return isl_map_domain(map);
2589 #define PW isl_pw_multi_aff
2591 #define EL isl_multi_aff
2593 #define EL_IS_ZERO is_empty
2597 #define IS_ZERO is_empty
2600 #undef DEFAULT_IS_ZERO
2601 #define DEFAULT_IS_ZERO 0
2606 #define NO_INVOLVES_DIMS
2607 #define NO_MOVE_DIMS
2608 #define NO_INSERT_DIMS
2612 #include <isl_pw_templ.c>
2615 #define UNION isl_union_pw_multi_aff
2617 #define PART isl_pw_multi_aff
2619 #define PARTS pw_multi_aff
2620 #define ALIGN_DOMAIN
2624 #include <isl_union_templ.c>
2626 /* Given a function "cmp" that returns the set of elements where
2627 * "ma1" is "better" than "ma2", return the intersection of this
2628 * set with "dom1" and "dom2".
2630 static __isl_give isl_set *shared_and_better(__isl_keep isl_set *dom1,
2631 __isl_keep isl_set *dom2, __isl_keep isl_multi_aff *ma1,
2632 __isl_keep isl_multi_aff *ma2,
2633 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2634 __isl_take isl_multi_aff *ma2))
2640 common = isl_set_intersect(isl_set_copy(dom1), isl_set_copy(dom2));
2641 is_empty = isl_set_plain_is_empty(common);
2642 if (is_empty >= 0 && is_empty)
2645 return isl_set_free(common);
2646 better = cmp(isl_multi_aff_copy(ma1), isl_multi_aff_copy(ma2));
2647 better = isl_set_intersect(common, better);
2652 /* Given a function "cmp" that returns the set of elements where
2653 * "ma1" is "better" than "ma2", return a piecewise multi affine
2654 * expression defined on the union of the definition domains
2655 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
2656 * "pma2" on each cell. If only one of the two input functions
2657 * is defined on a given cell, then it is considered the best.
2659 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_opt(
2660 __isl_take isl_pw_multi_aff *pma1,
2661 __isl_take isl_pw_multi_aff *pma2,
2662 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2663 __isl_take isl_multi_aff *ma2))
2666 isl_pw_multi_aff *res = NULL;
2668 isl_set *set = NULL;
2673 ctx = isl_space_get_ctx(pma1->dim);
2674 if (!isl_space_is_equal(pma1->dim, pma2->dim))
2675 isl_die(ctx, isl_error_invalid,
2676 "arguments should live in the same space", goto error);
2678 if (isl_pw_multi_aff_is_empty(pma1)) {
2679 isl_pw_multi_aff_free(pma1);
2683 if (isl_pw_multi_aff_is_empty(pma2)) {
2684 isl_pw_multi_aff_free(pma2);
2688 n = 2 * (pma1->n + 1) * (pma2->n + 1);
2689 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma1->dim), n);
2691 for (i = 0; i < pma1->n; ++i) {
2692 set = isl_set_copy(pma1->p[i].set);
2693 for (j = 0; j < pma2->n; ++j) {
2697 better = shared_and_better(pma2->p[j].set,
2698 pma1->p[i].set, pma2->p[j].maff,
2699 pma1->p[i].maff, cmp);
2700 is_empty = isl_set_plain_is_empty(better);
2701 if (is_empty < 0 || is_empty) {
2702 isl_set_free(better);
2707 set = isl_set_subtract(set, isl_set_copy(better));
2709 res = isl_pw_multi_aff_add_piece(res, better,
2710 isl_multi_aff_copy(pma2->p[j].maff));
2712 res = isl_pw_multi_aff_add_piece(res, set,
2713 isl_multi_aff_copy(pma1->p[i].maff));
2716 for (j = 0; j < pma2->n; ++j) {
2717 set = isl_set_copy(pma2->p[j].set);
2718 for (i = 0; i < pma1->n; ++i)
2719 set = isl_set_subtract(set,
2720 isl_set_copy(pma1->p[i].set));
2721 res = isl_pw_multi_aff_add_piece(res, set,
2722 isl_multi_aff_copy(pma2->p[j].maff));
2725 isl_pw_multi_aff_free(pma1);
2726 isl_pw_multi_aff_free(pma2);
2730 isl_pw_multi_aff_free(pma1);
2731 isl_pw_multi_aff_free(pma2);
2733 return isl_pw_multi_aff_free(res);
2736 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax(
2737 __isl_take isl_pw_multi_aff *pma1,
2738 __isl_take isl_pw_multi_aff *pma2)
2740 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_ge_set);
2743 /* Given two piecewise multi affine expressions, return a piecewise
2744 * multi-affine expression defined on the union of the definition domains
2745 * of the inputs that is equal to the lexicographic maximum of the two
2746 * inputs on each cell. If only one of the two inputs is defined on
2747 * a given cell, then it is considered to be the maximum.
2749 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax(
2750 __isl_take isl_pw_multi_aff *pma1,
2751 __isl_take isl_pw_multi_aff *pma2)
2753 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2754 &pw_multi_aff_union_lexmax);
2757 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin(
2758 __isl_take isl_pw_multi_aff *pma1,
2759 __isl_take isl_pw_multi_aff *pma2)
2761 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_le_set);
2764 /* Given two piecewise multi affine expressions, return a piecewise
2765 * multi-affine expression defined on the union of the definition domains
2766 * of the inputs that is equal to the lexicographic minimum of the two
2767 * inputs on each cell. If only one of the two inputs is defined on
2768 * a given cell, then it is considered to be the minimum.
2770 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin(
2771 __isl_take isl_pw_multi_aff *pma1,
2772 __isl_take isl_pw_multi_aff *pma2)
2774 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2775 &pw_multi_aff_union_lexmin);
2778 static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
2779 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2781 return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
2782 &isl_multi_aff_add);
2785 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
2786 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2788 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2792 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
2793 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2795 return isl_pw_multi_aff_union_add_(pma1, pma2);
2798 /* Given two piecewise multi-affine expressions A -> B and C -> D,
2799 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
2801 static __isl_give isl_pw_multi_aff *pw_multi_aff_product(
2802 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2806 isl_pw_multi_aff *res;
2811 n = pma1->n * pma2->n;
2812 space = isl_space_product(isl_space_copy(pma1->dim),
2813 isl_space_copy(pma2->dim));
2814 res = isl_pw_multi_aff_alloc_size(space, n);
2816 for (i = 0; i < pma1->n; ++i) {
2817 for (j = 0; j < pma2->n; ++j) {
2821 domain = isl_set_product(isl_set_copy(pma1->p[i].set),
2822 isl_set_copy(pma2->p[j].set));
2823 ma = isl_multi_aff_product(
2824 isl_multi_aff_copy(pma1->p[i].maff),
2825 isl_multi_aff_copy(pma2->p[i].maff));
2826 res = isl_pw_multi_aff_add_piece(res, domain, ma);
2830 isl_pw_multi_aff_free(pma1);
2831 isl_pw_multi_aff_free(pma2);
2834 isl_pw_multi_aff_free(pma1);
2835 isl_pw_multi_aff_free(pma2);
2839 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
2840 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2842 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2843 &pw_multi_aff_product);
2846 /* Construct a map mapping the domain of the piecewise multi-affine expression
2847 * to its range, with each dimension in the range equated to the
2848 * corresponding affine expression on its cell.
2850 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2858 map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
2860 for (i = 0; i < pma->n; ++i) {
2861 isl_multi_aff *maff;
2862 isl_basic_map *bmap;
2865 maff = isl_multi_aff_copy(pma->p[i].maff);
2866 bmap = isl_basic_map_from_multi_aff(maff);
2867 map_i = isl_map_from_basic_map(bmap);
2868 map_i = isl_map_intersect_domain(map_i,
2869 isl_set_copy(pma->p[i].set));
2870 map = isl_map_union_disjoint(map, map_i);
2873 isl_pw_multi_aff_free(pma);
2877 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2879 if (!isl_space_is_set(pma->dim))
2880 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2881 "isl_pw_multi_aff cannot be converted into an isl_set",
2882 return isl_pw_multi_aff_free(pma));
2884 return isl_map_from_pw_multi_aff(pma);
2887 /* Given a basic map with a single output dimension that is defined
2888 * in terms of the parameters and input dimensions using an equality,
2889 * extract an isl_aff that expresses the output dimension in terms
2890 * of the parameters and input dimensions.
2892 * Since some applications expect the result of isl_pw_multi_aff_from_map
2893 * to only contain integer affine expressions, we compute the floor
2894 * of the expression before returning.
2896 * This function shares some similarities with
2897 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
2899 static __isl_give isl_aff *extract_isl_aff_from_basic_map(
2900 __isl_take isl_basic_map *bmap)
2905 isl_local_space *ls;
2910 if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
2911 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2912 "basic map should have a single output dimension",
2914 offset = isl_basic_map_offset(bmap, isl_dim_out);
2915 total = isl_basic_map_total_dim(bmap);
2916 for (i = 0; i < bmap->n_eq; ++i) {
2917 if (isl_int_is_zero(bmap->eq[i][offset]))
2919 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
2920 1 + total - (offset + 1)) != -1)
2924 if (i >= bmap->n_eq)
2925 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2926 "unable to find suitable equality", goto error);
2927 ls = isl_basic_map_get_local_space(bmap);
2928 aff = isl_aff_alloc(isl_local_space_domain(ls));
2931 if (isl_int_is_neg(bmap->eq[i][offset]))
2932 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
2934 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
2935 isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
2936 isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
2937 isl_basic_map_free(bmap);
2939 aff = isl_aff_remove_unused_divs(aff);
2940 aff = isl_aff_floor(aff);
2943 isl_basic_map_free(bmap);
2947 /* Given a basic map where each output dimension is defined
2948 * in terms of the parameters and input dimensions using an equality,
2949 * extract an isl_multi_aff that expresses the output dimensions in terms
2950 * of the parameters and input dimensions.
2952 static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
2953 __isl_take isl_basic_map *bmap)
2962 ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
2963 n_out = isl_basic_map_dim(bmap, isl_dim_out);
2965 for (i = 0; i < n_out; ++i) {
2966 isl_basic_map *bmap_i;
2969 bmap_i = isl_basic_map_copy(bmap);
2970 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
2971 i + 1, n_out - (1 + i));
2972 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
2973 aff = extract_isl_aff_from_basic_map(bmap_i);
2974 ma = isl_multi_aff_set_aff(ma, i, aff);
2977 isl_basic_map_free(bmap);
2982 /* Create an isl_pw_multi_aff that is equivalent to
2983 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
2984 * The given basic map is such that each output dimension is defined
2985 * in terms of the parameters and input dimensions using an equality.
2987 static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
2988 __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
2992 ma = extract_isl_multi_aff_from_basic_map(bmap);
2993 return isl_pw_multi_aff_alloc(domain, ma);
2996 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
2997 * This obivously only works if the input "map" is single-valued.
2998 * If so, we compute the lexicographic minimum of the image in the form
2999 * of an isl_pw_multi_aff. Since the image is unique, it is equal
3000 * to its lexicographic minimum.
3001 * If the input is not single-valued, we produce an error.
3003 * As a special case, we first check if all output dimensions are uniquely
3004 * defined in terms of the parameters and input dimensions over the entire
3005 * domain. If so, we extract the desired isl_pw_multi_aff directly
3006 * from the affine hull of "map" and its domain.
3008 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
3012 isl_pw_multi_aff *pma;
3013 isl_basic_map *hull;
3018 hull = isl_map_affine_hull(isl_map_copy(map));
3019 sv = isl_basic_map_plain_is_single_valued(hull);
3021 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
3022 isl_basic_map_free(hull);
3026 sv = isl_map_is_single_valued(map);
3030 isl_die(isl_map_get_ctx(map), isl_error_invalid,
3031 "map is not single-valued", goto error);
3032 map = isl_map_make_disjoint(map);
3036 pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
3038 for (i = 0; i < map->n; ++i) {
3039 isl_pw_multi_aff *pma_i;
3040 isl_basic_map *bmap;
3041 bmap = isl_basic_map_copy(map->p[i]);
3042 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
3043 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
3053 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
3055 return isl_pw_multi_aff_from_map(set);
3058 /* Return the piecewise affine expression "set ? 1 : 0".
3060 __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
3063 isl_space *space = isl_set_get_space(set);
3064 isl_local_space *ls = isl_local_space_from_space(space);
3065 isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
3066 isl_aff *one = isl_aff_zero_on_domain(ls);
3068 one = isl_aff_add_constant_si(one, 1);
3069 pa = isl_pw_aff_alloc(isl_set_copy(set), one);
3070 set = isl_set_complement(set);
3071 pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
3076 /* Plug in "subs" for dimension "type", "pos" of "aff".
3078 * Let i be the dimension to replace and let "subs" be of the form
3082 * and "aff" of the form
3088 * (a f + d g')/(m d)
3090 * where g' is the result of plugging in "subs" in each of the integer
3093 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
3094 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
3099 aff = isl_aff_cow(aff);
3101 return isl_aff_free(aff);
3103 ctx = isl_aff_get_ctx(aff);
3104 if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
3105 isl_die(ctx, isl_error_invalid,
3106 "spaces don't match", return isl_aff_free(aff));
3107 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
3108 isl_die(ctx, isl_error_unsupported,
3109 "cannot handle divs yet", return isl_aff_free(aff));
3111 aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
3113 return isl_aff_free(aff);
3115 aff->v = isl_vec_cow(aff->v);
3117 return isl_aff_free(aff);
3119 pos += isl_local_space_offset(aff->ls, type);
3122 isl_seq_substitute(aff->v->el, pos, subs->v->el,
3123 aff->v->size, subs->v->size, v);
3129 /* Plug in "subs" for dimension "type", "pos" in each of the affine
3130 * expressions in "maff".
3132 __isl_give isl_multi_aff *isl_multi_aff_substitute(
3133 __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
3134 __isl_keep isl_aff *subs)
3138 maff = isl_multi_aff_cow(maff);
3140 return isl_multi_aff_free(maff);
3142 if (type == isl_dim_in)
3145 for (i = 0; i < maff->n; ++i) {
3146 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
3148 return isl_multi_aff_free(maff);
3154 /* Plug in "subs" for dimension "type", "pos" of "pma".
3156 * pma is of the form
3160 * while subs is of the form
3162 * v' = B_j(v) -> S_j
3164 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
3165 * has a contribution in the result, in particular
3167 * C_ij(S_j) -> M_i(S_j)
3169 * Note that plugging in S_j in C_ij may also result in an empty set
3170 * and this contribution should simply be discarded.
3172 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
3173 __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
3174 __isl_keep isl_pw_aff *subs)
3177 isl_pw_multi_aff *res;
3180 return isl_pw_multi_aff_free(pma);
3182 n = pma->n * subs->n;
3183 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
3185 for (i = 0; i < pma->n; ++i) {
3186 for (j = 0; j < subs->n; ++j) {
3188 isl_multi_aff *res_ij;
3189 common = isl_set_intersect(
3190 isl_set_copy(pma->p[i].set),
3191 isl_set_copy(subs->p[j].set));
3192 common = isl_set_substitute(common,
3193 type, pos, subs->p[j].aff);
3194 if (isl_set_plain_is_empty(common)) {
3195 isl_set_free(common);
3199 res_ij = isl_multi_aff_substitute(
3200 isl_multi_aff_copy(pma->p[i].maff),
3201 type, pos, subs->p[j].aff);
3203 res = isl_pw_multi_aff_add_piece(res, common, res_ij);
3207 isl_pw_multi_aff_free(pma);
3211 /* Extend the local space of "dst" to include the divs
3212 * in the local space of "src".
3214 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
3215 __isl_keep isl_aff *src)
3223 return isl_aff_free(dst);
3225 ctx = isl_aff_get_ctx(src);
3226 if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
3227 isl_die(ctx, isl_error_invalid,
3228 "spaces don't match", goto error);
3230 if (src->ls->div->n_row == 0)
3233 exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
3234 exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
3238 div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
3239 dst = isl_aff_expand_divs(dst, div, exp2);
3247 return isl_aff_free(dst);
3250 /* Adjust the local spaces of the affine expressions in "maff"
3251 * such that they all have the save divs.
3253 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
3254 __isl_take isl_multi_aff *maff)
3262 maff = isl_multi_aff_cow(maff);
3266 for (i = 1; i < maff->n; ++i)
3267 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
3268 for (i = 1; i < maff->n; ++i) {
3269 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
3271 return isl_multi_aff_free(maff);
3277 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
3279 aff = isl_aff_cow(aff);
3283 aff->ls = isl_local_space_lift(aff->ls);
3285 return isl_aff_free(aff);
3290 /* Lift "maff" to a space with extra dimensions such that the result
3291 * has no more existentially quantified variables.
3292 * If "ls" is not NULL, then *ls is assigned the local space that lies
3293 * at the basis of the lifting applied to "maff".
3295 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
3296 __isl_give isl_local_space **ls)
3310 isl_space *space = isl_multi_aff_get_domain_space(maff);
3311 *ls = isl_local_space_from_space(space);
3313 return isl_multi_aff_free(maff);
3318 maff = isl_multi_aff_cow(maff);
3319 maff = isl_multi_aff_align_divs(maff);
3323 n_div = isl_aff_dim(maff->p[0], isl_dim_div);
3324 space = isl_multi_aff_get_space(maff);
3325 space = isl_space_lift(isl_space_domain(space), n_div);
3326 space = isl_space_extend_domain_with_range(space,
3327 isl_multi_aff_get_space(maff));
3329 return isl_multi_aff_free(maff);
3330 isl_space_free(maff->space);
3331 maff->space = space;
3334 *ls = isl_aff_get_domain_local_space(maff->p[0]);
3336 return isl_multi_aff_free(maff);
3339 for (i = 0; i < maff->n; ++i) {
3340 maff->p[i] = isl_aff_lift(maff->p[i]);
3348 isl_local_space_free(*ls);
3349 return isl_multi_aff_free(maff);
3353 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
3355 __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
3356 __isl_keep isl_pw_multi_aff *pma, int pos)
3366 n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
3367 if (pos < 0 || pos >= n_out)
3368 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
3369 "index out of bounds", return NULL);
3371 space = isl_pw_multi_aff_get_space(pma);
3372 space = isl_space_drop_dims(space, isl_dim_out,
3373 pos + 1, n_out - pos - 1);
3374 space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
3376 pa = isl_pw_aff_alloc_size(space, pma->n);
3377 for (i = 0; i < pma->n; ++i) {
3379 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
3380 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
3386 /* Return an isl_pw_multi_aff with the given "set" as domain and
3387 * an unnamed zero-dimensional range.
3389 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
3390 __isl_take isl_set *set)
3395 space = isl_set_get_space(set);
3396 space = isl_space_from_domain(space);
3397 ma = isl_multi_aff_zero(space);
3398 return isl_pw_multi_aff_alloc(set, ma);
3401 /* Add an isl_pw_multi_aff with the given "set" as domain and
3402 * an unnamed zero-dimensional range to *user.
3404 static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
3406 isl_union_pw_multi_aff **upma = user;
3407 isl_pw_multi_aff *pma;
3409 pma = isl_pw_multi_aff_from_domain(set);
3410 *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
3415 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
3416 * an unnamed zero-dimensional range.
3418 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
3419 __isl_take isl_union_set *uset)
3422 isl_union_pw_multi_aff *upma;
3427 space = isl_union_set_get_space(uset);
3428 upma = isl_union_pw_multi_aff_empty(space);
3430 if (isl_union_set_foreach_set(uset,
3431 &add_pw_multi_aff_from_domain, &upma) < 0)
3434 isl_union_set_free(uset);
3437 isl_union_set_free(uset);
3438 isl_union_pw_multi_aff_free(upma);
3442 /* Convert "pma" to an isl_map and add it to *umap.
3444 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
3446 isl_union_map **umap = user;
3449 map = isl_map_from_pw_multi_aff(pma);
3450 *umap = isl_union_map_add_map(*umap, map);
3455 /* Construct a union map mapping the domain of the union
3456 * piecewise multi-affine expression to its range, with each dimension
3457 * in the range equated to the corresponding affine expression on its cell.
3459 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
3460 __isl_take isl_union_pw_multi_aff *upma)
3463 isl_union_map *umap;
3468 space = isl_union_pw_multi_aff_get_space(upma);
3469 umap = isl_union_map_empty(space);
3471 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
3472 &map_from_pw_multi_aff, &umap) < 0)
3475 isl_union_pw_multi_aff_free(upma);
3478 isl_union_pw_multi_aff_free(upma);
3479 isl_union_map_free(umap);
3483 /* Local data for bin_entry and the callback "fn".
3485 struct isl_union_pw_multi_aff_bin_data {
3486 isl_union_pw_multi_aff *upma2;
3487 isl_union_pw_multi_aff *res;
3488 isl_pw_multi_aff *pma;
3489 int (*fn)(void **entry, void *user);
3492 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
3493 * and call data->fn for each isl_pw_multi_aff in data->upma2.
3495 static int bin_entry(void **entry, void *user)
3497 struct isl_union_pw_multi_aff_bin_data *data = user;
3498 isl_pw_multi_aff *pma = *entry;
3501 if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
3502 data->fn, data) < 0)
3508 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
3509 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
3510 * passed as user field) and the isl_pw_multi_aff from upma2 is available
3511 * as *entry. The callback should adjust data->res if desired.
3513 static __isl_give isl_union_pw_multi_aff *bin_op(
3514 __isl_take isl_union_pw_multi_aff *upma1,
3515 __isl_take isl_union_pw_multi_aff *upma2,
3516 int (*fn)(void **entry, void *user))
3519 struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
3521 space = isl_union_pw_multi_aff_get_space(upma2);
3522 upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
3523 space = isl_union_pw_multi_aff_get_space(upma1);
3524 upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
3526 if (!upma1 || !upma2)
3530 data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
3532 if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
3533 &bin_entry, &data) < 0)
3536 isl_union_pw_multi_aff_free(upma1);
3537 isl_union_pw_multi_aff_free(upma2);
3540 isl_union_pw_multi_aff_free(upma1);
3541 isl_union_pw_multi_aff_free(upma2);
3542 isl_union_pw_multi_aff_free(data.res);
3546 /* Given two isl_multi_affs A -> B and C -> D,
3547 * construct an isl_multi_aff (A * C) -> (B, D).
3549 __isl_give isl_multi_aff *isl_multi_aff_flat_range_product(
3550 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
3560 space = isl_space_range_product(isl_multi_aff_get_space(ma1),
3561 isl_multi_aff_get_space(ma2));
3562 space = isl_space_flatten_range(space);
3563 res = isl_multi_aff_alloc(space);
3565 n1 = isl_multi_aff_dim(ma1, isl_dim_out);
3566 n2 = isl_multi_aff_dim(ma2, isl_dim_out);
3568 for (i = 0; i < n1; ++i) {
3569 aff = isl_multi_aff_get_aff(ma1, i);
3570 res = isl_multi_aff_set_aff(res, i, aff);
3573 for (i = 0; i < n2; ++i) {
3574 aff = isl_multi_aff_get_aff(ma2, i);
3575 res = isl_multi_aff_set_aff(res, n1 + i, aff);
3578 isl_multi_aff_free(ma1);
3579 isl_multi_aff_free(ma2);
3582 isl_multi_aff_free(ma1);
3583 isl_multi_aff_free(ma2);
3587 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
3588 * construct an isl_pw_multi_aff (A * C) -> (B, D).
3590 static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
3591 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3595 space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
3596 isl_pw_multi_aff_get_space(pma2));
3597 space = isl_space_flatten_range(space);
3598 return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
3599 &isl_multi_aff_flat_range_product);
3602 /* Given two isl_pw_multi_affs A -> B and C -> D,
3603 * construct an isl_pw_multi_aff (A * C) -> (B, D).
3605 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
3606 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3608 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3609 &pw_multi_aff_flat_range_product);
3612 /* If data->pma and *entry have the same domain space, then compute
3613 * their flat range product and the result to data->res.
3615 static int flat_range_product_entry(void **entry, void *user)
3617 struct isl_union_pw_multi_aff_bin_data *data = user;
3618 isl_pw_multi_aff *pma2 = *entry;
3620 if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
3621 pma2->dim, isl_dim_in))
3624 pma2 = isl_pw_multi_aff_flat_range_product(
3625 isl_pw_multi_aff_copy(data->pma),
3626 isl_pw_multi_aff_copy(pma2));
3628 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
3633 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
3634 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
3636 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
3637 __isl_take isl_union_pw_multi_aff *upma1,
3638 __isl_take isl_union_pw_multi_aff *upma2)
3640 return bin_op(upma1, upma2, &flat_range_product_entry);
3643 /* Replace the affine expressions at position "pos" in "pma" by "pa".
3644 * The parameters are assumed to have been aligned.
3646 * The implementation essentially performs an isl_pw_*_on_shared_domain,
3647 * except that it works on two different isl_pw_* types.
3649 static __isl_give isl_pw_multi_aff *pw_multi_aff_set_pw_aff(
3650 __isl_take isl_pw_multi_aff *pma, unsigned pos,
3651 __isl_take isl_pw_aff *pa)
3654 isl_pw_multi_aff *res = NULL;
3659 if (!isl_space_tuple_match(pma->dim, isl_dim_in, pa->dim, isl_dim_in))
3660 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
3661 "domains don't match", goto error);
3662 if (pos >= isl_pw_multi_aff_dim(pma, isl_dim_out))
3663 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
3664 "index out of bounds", goto error);
3667 res = isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma), n);
3669 for (i = 0; i < pma->n; ++i) {
3670 for (j = 0; j < pa->n; ++j) {
3672 isl_multi_aff *res_ij;
3675 common = isl_set_intersect(isl_set_copy(pma->p[i].set),
3676 isl_set_copy(pa->p[j].set));
3677 empty = isl_set_plain_is_empty(common);
3678 if (empty < 0 || empty) {
3679 isl_set_free(common);
3685 res_ij = isl_multi_aff_set_aff(
3686 isl_multi_aff_copy(pma->p[i].maff), pos,
3687 isl_aff_copy(pa->p[j].aff));
3688 res_ij = isl_multi_aff_gist(res_ij,
3689 isl_set_copy(common));
3691 res = isl_pw_multi_aff_add_piece(res, common, res_ij);
3695 isl_pw_multi_aff_free(pma);
3696 isl_pw_aff_free(pa);
3699 isl_pw_multi_aff_free(pma);
3700 isl_pw_aff_free(pa);
3701 return isl_pw_multi_aff_free(res);
3704 /* Replace the affine expressions at position "pos" in "pma" by "pa".
3706 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_pw_aff(
3707 __isl_take isl_pw_multi_aff *pma, unsigned pos,
3708 __isl_take isl_pw_aff *pa)
3712 if (isl_space_match(pma->dim, isl_dim_param, pa->dim, isl_dim_param))
3713 return pw_multi_aff_set_pw_aff(pma, pos, pa);
3714 if (!isl_space_has_named_params(pma->dim) ||
3715 !isl_space_has_named_params(pa->dim))
3716 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
3717 "unaligned unnamed parameters", goto error);
3718 pma = isl_pw_multi_aff_align_params(pma, isl_pw_aff_get_space(pa));
3719 pa = isl_pw_aff_align_params(pa, isl_pw_multi_aff_get_space(pma));
3720 return pw_multi_aff_set_pw_aff(pma, pos, pa);
3722 isl_pw_multi_aff_free(pma);
3723 isl_pw_aff_free(pa);