2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
5 * Use of this software is governed by the GNU LGPLv2.1 license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 #include <isl_ctx_private.h>
13 #include <isl_map_private.h>
14 #include <isl_aff_private.h>
15 #include <isl_space_private.h>
16 #include <isl_local_space_private.h>
17 #include <isl_mat_private.h>
18 #include <isl_list_private.h>
19 #include <isl/constraint.h>
23 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
24 __isl_take isl_vec *v)
31 aff = isl_calloc_type(v->ctx, struct isl_aff);
41 isl_local_space_free(ls);
46 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
55 ctx = isl_local_space_get_ctx(ls);
56 if (!isl_local_space_divs_known(ls))
57 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
59 if (!isl_local_space_is_set(ls))
60 isl_die(ctx, isl_error_invalid,
61 "domain of affine expression should be a set",
64 total = isl_local_space_dim(ls, isl_dim_all);
65 v = isl_vec_alloc(ctx, 1 + 1 + total);
66 return isl_aff_alloc_vec(ls, v);
68 isl_local_space_free(ls);
72 __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
76 aff = isl_aff_alloc(ls);
80 isl_int_set_si(aff->v->el[0], 1);
81 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
86 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
95 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
100 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
101 isl_vec_copy(aff->v));
104 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
112 return isl_aff_dup(aff);
115 void *isl_aff_free(__isl_take isl_aff *aff)
123 isl_local_space_free(aff->ls);
124 isl_vec_free(aff->v);
131 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
133 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
136 /* Externally, an isl_aff has a map space, but internally, the
137 * ls field corresponds to the domain of that space.
139 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
143 if (type == isl_dim_out)
145 if (type == isl_dim_in)
147 return isl_local_space_dim(aff->ls, type);
150 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
152 return aff ? isl_local_space_get_space(aff->ls) : NULL;
155 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
160 space = isl_local_space_get_space(aff->ls);
161 space = isl_space_from_domain(space);
162 space = isl_space_add_dims(space, isl_dim_out, 1);
166 __isl_give isl_local_space *isl_aff_get_domain_local_space(
167 __isl_keep isl_aff *aff)
169 return aff ? isl_local_space_copy(aff->ls) : NULL;
172 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
177 ls = isl_local_space_copy(aff->ls);
178 ls = isl_local_space_from_domain(ls);
179 ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
183 /* Externally, an isl_aff has a map space, but internally, the
184 * ls field corresponds to the domain of that space.
186 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
187 enum isl_dim_type type, unsigned pos)
191 if (type == isl_dim_out)
193 if (type == isl_dim_in)
195 return isl_local_space_get_dim_name(aff->ls, type, pos);
198 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
199 __isl_take isl_space *dim)
201 aff = isl_aff_cow(aff);
205 aff->ls = isl_local_space_reset_space(aff->ls, dim);
207 return isl_aff_free(aff);
216 /* Reset the space of "aff". This function is called from isl_pw_templ.c
217 * and doesn't know if the space of an element object is represented
218 * directly or through its domain. It therefore passes along both.
220 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
221 __isl_take isl_space *space, __isl_take isl_space *domain)
223 isl_space_free(space);
224 return isl_aff_reset_domain_space(aff, domain);
227 /* Reorder the coefficients of the affine expression based
228 * on the given reodering.
229 * The reordering r is assumed to have been extended with the local
232 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
233 __isl_take isl_reordering *r, int n_div)
241 res = isl_vec_alloc(vec->ctx,
242 2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
243 isl_seq_cpy(res->el, vec->el, 2);
244 isl_seq_clr(res->el + 2, res->size - 2);
245 for (i = 0; i < r->len; ++i)
246 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
248 isl_reordering_free(r);
253 isl_reordering_free(r);
257 /* Reorder the dimensions of the domain of "aff" according
258 * to the given reordering.
260 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
261 __isl_take isl_reordering *r)
263 aff = isl_aff_cow(aff);
267 r = isl_reordering_extend(r, aff->ls->div->n_row);
268 aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
269 aff->ls->div->n_row);
270 aff->ls = isl_local_space_realign(aff->ls, r);
272 if (!aff->v || !aff->ls)
273 return isl_aff_free(aff);
278 isl_reordering_free(r);
282 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
287 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
290 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
297 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
298 if (equal < 0 || !equal)
301 return isl_vec_is_equal(aff1->v, aff2->v);
304 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
308 isl_int_set(*v, aff->v->el[0]);
312 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
316 isl_int_set(*v, aff->v->el[1]);
320 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
321 enum isl_dim_type type, int pos, isl_int *v)
326 if (type == isl_dim_out)
327 isl_die(aff->v->ctx, isl_error_invalid,
328 "output/set dimension does not have a coefficient",
330 if (type == isl_dim_in)
333 if (pos >= isl_local_space_dim(aff->ls, type))
334 isl_die(aff->v->ctx, isl_error_invalid,
335 "position out of bounds", return -1);
337 pos += isl_local_space_offset(aff->ls, type);
338 isl_int_set(*v, aff->v->el[1 + pos]);
343 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
345 aff = isl_aff_cow(aff);
349 aff->v = isl_vec_cow(aff->v);
351 return isl_aff_free(aff);
353 isl_int_set(aff->v->el[0], v);
358 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
360 aff = isl_aff_cow(aff);
364 aff->v = isl_vec_cow(aff->v);
366 return isl_aff_free(aff);
368 isl_int_set(aff->v->el[1], v);
373 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
375 if (isl_int_is_zero(v))
378 aff = isl_aff_cow(aff);
382 aff->v = isl_vec_cow(aff->v);
384 return isl_aff_free(aff);
386 isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
391 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
396 isl_int_set_si(t, v);
397 aff = isl_aff_add_constant(aff, t);
403 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
405 aff = isl_aff_cow(aff);
409 aff->v = isl_vec_cow(aff->v);
411 return isl_aff_free(aff);
413 isl_int_set_si(aff->v->el[1], v);
418 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
419 enum isl_dim_type type, int pos, isl_int v)
424 if (type == isl_dim_out)
425 isl_die(aff->v->ctx, isl_error_invalid,
426 "output/set dimension does not have a coefficient",
427 return isl_aff_free(aff));
428 if (type == isl_dim_in)
431 if (pos >= isl_local_space_dim(aff->ls, type))
432 isl_die(aff->v->ctx, isl_error_invalid,
433 "position out of bounds", return isl_aff_free(aff));
435 aff = isl_aff_cow(aff);
439 aff->v = isl_vec_cow(aff->v);
441 return isl_aff_free(aff);
443 pos += isl_local_space_offset(aff->ls, type);
444 isl_int_set(aff->v->el[1 + pos], v);
449 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
450 enum isl_dim_type type, int pos, int v)
455 if (type == isl_dim_out)
456 isl_die(aff->v->ctx, isl_error_invalid,
457 "output/set dimension does not have a coefficient",
458 return isl_aff_free(aff));
459 if (type == isl_dim_in)
462 if (pos >= isl_local_space_dim(aff->ls, type))
463 isl_die(aff->v->ctx, isl_error_invalid,
464 "position out of bounds", return isl_aff_free(aff));
466 aff = isl_aff_cow(aff);
470 aff->v = isl_vec_cow(aff->v);
472 return isl_aff_free(aff);
474 pos += isl_local_space_offset(aff->ls, type);
475 isl_int_set_si(aff->v->el[1 + pos], v);
480 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
481 enum isl_dim_type type, int pos, isl_int v)
486 if (type == isl_dim_out)
487 isl_die(aff->v->ctx, isl_error_invalid,
488 "output/set dimension does not have a coefficient",
489 return isl_aff_free(aff));
490 if (type == isl_dim_in)
493 if (pos >= isl_local_space_dim(aff->ls, type))
494 isl_die(aff->v->ctx, isl_error_invalid,
495 "position out of bounds", return isl_aff_free(aff));
497 aff = isl_aff_cow(aff);
501 aff->v = isl_vec_cow(aff->v);
503 return isl_aff_free(aff);
505 pos += isl_local_space_offset(aff->ls, type);
506 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
511 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
512 enum isl_dim_type type, int pos, int v)
517 isl_int_set_si(t, v);
518 aff = isl_aff_add_coefficient(aff, type, pos, t);
524 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
529 return isl_local_space_get_div(aff->ls, pos);
532 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
534 aff = isl_aff_cow(aff);
537 aff->v = isl_vec_cow(aff->v);
539 return isl_aff_free(aff);
541 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
546 /* Given f, return floor(f).
547 * If f is an integer expression, then just return f.
548 * Otherwise, if f = g/m, write g = q m + r,
549 * create a new div d = [r/m] and return the expression q + d.
550 * The coefficients in r are taken to lie between -m/2 and m/2.
552 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
562 if (isl_int_is_one(aff->v->el[0]))
565 aff = isl_aff_cow(aff);
569 aff->v = isl_vec_cow(aff->v);
570 div = isl_vec_copy(aff->v);
571 div = isl_vec_cow(div);
573 return isl_aff_free(aff);
575 ctx = isl_aff_get_ctx(aff);
576 isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
577 for (i = 1; i < aff->v->size; ++i) {
578 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
579 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
580 if (isl_int_gt(div->el[i], aff->v->el[0])) {
581 isl_int_sub(div->el[i], div->el[i], div->el[0]);
582 isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
586 aff->ls = isl_local_space_add_div(aff->ls, div);
588 return isl_aff_free(aff);
591 aff->v = isl_vec_extend(aff->v, size + 1);
593 return isl_aff_free(aff);
594 isl_int_set_si(aff->v->el[0], 1);
595 isl_int_set_si(aff->v->el[size], 1);
602 * aff mod m = aff - m * floor(aff/m)
604 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
608 res = isl_aff_copy(aff);
609 aff = isl_aff_scale_down(aff, m);
610 aff = isl_aff_floor(aff);
611 aff = isl_aff_scale(aff, m);
612 res = isl_aff_sub(res, aff);
619 * pwaff mod m = pwaff - m * floor(pwaff/m)
621 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
625 res = isl_pw_aff_copy(pwaff);
626 pwaff = isl_pw_aff_scale_down(pwaff, m);
627 pwaff = isl_pw_aff_floor(pwaff);
628 pwaff = isl_pw_aff_scale(pwaff, m);
629 res = isl_pw_aff_sub(res, pwaff);
634 /* Given f, return ceil(f).
635 * If f is an integer expression, then just return f.
636 * Otherwise, create a new div d = [-f] and return the expression -d.
638 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
643 if (isl_int_is_one(aff->v->el[0]))
646 aff = isl_aff_neg(aff);
647 aff = isl_aff_floor(aff);
648 aff = isl_aff_neg(aff);
653 /* Apply the expansion computed by isl_merge_divs.
654 * The expansion itself is given by "exp" while the resulting
655 * list of divs is given by "div".
657 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
658 __isl_take isl_mat *div, int *exp)
665 aff = isl_aff_cow(aff);
669 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
670 new_n_div = isl_mat_rows(div);
671 if (new_n_div < old_n_div)
672 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
673 "not an expansion", goto error);
675 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
679 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
681 for (i = new_n_div - 1; i >= 0; --i) {
682 if (j >= 0 && exp[j] == i) {
684 isl_int_swap(aff->v->el[offset + i],
685 aff->v->el[offset + j]);
688 isl_int_set_si(aff->v->el[offset + i], 0);
691 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
702 /* Add two affine expressions that live in the same local space.
704 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
705 __isl_take isl_aff *aff2)
709 aff1 = isl_aff_cow(aff1);
713 aff1->v = isl_vec_cow(aff1->v);
719 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
720 isl_int_divexact(f, aff2->v->el[0], gcd);
721 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
722 isl_int_divexact(f, aff1->v->el[0], gcd);
723 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
724 isl_int_divexact(f, aff2->v->el[0], gcd);
725 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
737 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
738 __isl_take isl_aff *aff2)
748 ctx = isl_aff_get_ctx(aff1);
749 if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
750 isl_die(ctx, isl_error_invalid,
751 "spaces don't match", goto error);
753 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
754 return add_expanded(aff1, aff2);
756 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
757 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
761 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
762 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
763 aff2 = isl_aff_expand_divs(aff2, div, exp2);
767 return add_expanded(aff1, aff2);
776 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
777 __isl_take isl_aff *aff2)
779 return isl_aff_add(aff1, isl_aff_neg(aff2));
782 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
786 if (isl_int_is_one(f))
789 aff = isl_aff_cow(aff);
792 aff->v = isl_vec_cow(aff->v);
794 return isl_aff_free(aff);
797 isl_int_gcd(gcd, aff->v->el[0], f);
798 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
799 isl_int_divexact(gcd, f, gcd);
800 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
806 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
810 if (isl_int_is_one(f))
813 aff = isl_aff_cow(aff);
816 aff->v = isl_vec_cow(aff->v);
818 return isl_aff_free(aff);
821 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
822 isl_int_gcd(gcd, gcd, f);
823 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
824 isl_int_divexact(gcd, f, gcd);
825 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
831 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
839 isl_int_set_ui(v, f);
840 aff = isl_aff_scale_down(aff, v);
846 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
847 enum isl_dim_type type, unsigned pos, const char *s)
849 aff = isl_aff_cow(aff);
852 if (type == isl_dim_out)
853 isl_die(aff->v->ctx, isl_error_invalid,
854 "cannot set name of output/set dimension",
855 return isl_aff_free(aff));
856 if (type == isl_dim_in)
858 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
860 return isl_aff_free(aff);
865 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
866 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
868 aff = isl_aff_cow(aff);
870 return isl_id_free(id);
871 if (type == isl_dim_out)
872 isl_die(aff->v->ctx, isl_error_invalid,
873 "cannot set name of output/set dimension",
875 if (type == isl_dim_in)
877 aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
879 return isl_aff_free(aff);
888 /* Exploit the equalities in "eq" to simplify the affine expression
889 * and the expressions of the integer divisions in the local space.
890 * The integer divisions in this local space are assumed to appear
891 * as regular dimensions in "eq".
893 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
894 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
903 isl_basic_set_free(eq);
907 aff = isl_aff_cow(aff);
911 aff->ls = isl_local_space_substitute_equalities(aff->ls,
912 isl_basic_set_copy(eq));
916 total = 1 + isl_space_dim(eq->dim, isl_dim_all);
918 for (i = 0; i < eq->n_eq; ++i) {
919 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
920 if (j < 0 || j == 0 || j >= total)
923 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
927 isl_basic_set_free(eq);
930 isl_basic_set_free(eq);
935 /* Exploit the equalities in "eq" to simplify the affine expression
936 * and the expressions of the integer divisions in the local space.
938 static __isl_give isl_aff *isl_aff_substitute_equalities(
939 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
945 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
947 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
948 return isl_aff_substitute_equalities_lifted(aff, eq);
950 isl_basic_set_free(eq);
955 /* Look for equalities among the variables shared by context and aff
956 * and the integer divisions of aff, if any.
957 * The equalities are then used to eliminate coefficients and/or integer
958 * divisions from aff.
960 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
961 __isl_take isl_set *context)
968 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
972 context = isl_set_add_dims(context, isl_dim_set, n_div);
973 ls = isl_aff_get_domain_local_space(aff);
974 bset = isl_basic_set_from_local_space(ls);
975 bset = isl_basic_set_lift(bset);
976 bset = isl_basic_set_flatten(bset);
977 context = isl_set_intersect(context,
978 isl_set_from_basic_set(bset));
981 hull = isl_set_affine_hull(context);
982 return isl_aff_substitute_equalities_lifted(aff, hull);
985 isl_set_free(context);
989 /* Return a basic set containing those elements in the space
990 * of aff where it is non-negative.
992 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
994 isl_constraint *ineq;
996 ineq = isl_inequality_from_aff(aff);
998 return isl_basic_set_from_constraint(ineq);
1001 /* Return a basic set containing those elements in the space
1002 * of aff where it is zero.
1004 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1006 isl_constraint *ineq;
1008 ineq = isl_equality_from_aff(aff);
1010 return isl_basic_set_from_constraint(ineq);
1013 /* Return a basic set containing those elements in the shared space
1014 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1016 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1017 __isl_take isl_aff *aff2)
1019 aff1 = isl_aff_sub(aff1, aff2);
1021 return isl_aff_nonneg_basic_set(aff1);
1024 /* Return a basic set containing those elements in the shared space
1025 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1027 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1028 __isl_take isl_aff *aff2)
1030 return isl_aff_ge_basic_set(aff2, aff1);
1033 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1034 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1036 aff1 = isl_aff_add(aff1, aff2);
1037 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1041 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1049 /* Check whether the given affine expression has non-zero coefficient
1050 * for any dimension in the given range or if any of these dimensions
1051 * appear with non-zero coefficients in any of the integer divisions
1052 * involved in the affine expression.
1054 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1055 enum isl_dim_type type, unsigned first, unsigned n)
1067 ctx = isl_aff_get_ctx(aff);
1068 if (first + n > isl_aff_dim(aff, type))
1069 isl_die(ctx, isl_error_invalid,
1070 "range out of bounds", return -1);
1072 active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1076 first += isl_local_space_offset(aff->ls, type) - 1;
1077 for (i = 0; i < n; ++i)
1078 if (active[first + i]) {
1091 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1092 enum isl_dim_type type, unsigned first, unsigned n)
1098 if (type == isl_dim_out)
1099 isl_die(aff->v->ctx, isl_error_invalid,
1100 "cannot drop output/set dimension",
1101 return isl_aff_free(aff));
1102 if (type == isl_dim_in)
1104 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1107 ctx = isl_aff_get_ctx(aff);
1108 if (first + n > isl_local_space_dim(aff->ls, type))
1109 isl_die(ctx, isl_error_invalid, "range out of bounds",
1110 return isl_aff_free(aff));
1112 aff = isl_aff_cow(aff);
1116 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1118 return isl_aff_free(aff);
1120 first += 1 + isl_local_space_offset(aff->ls, type);
1121 aff->v = isl_vec_drop_els(aff->v, first, n);
1123 return isl_aff_free(aff);
1128 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1129 enum isl_dim_type type, unsigned first, unsigned n)
1135 if (type == isl_dim_out)
1136 isl_die(aff->v->ctx, isl_error_invalid,
1137 "cannot insert output/set dimensions",
1138 return isl_aff_free(aff));
1139 if (type == isl_dim_in)
1141 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1144 ctx = isl_aff_get_ctx(aff);
1145 if (first > isl_local_space_dim(aff->ls, type))
1146 isl_die(ctx, isl_error_invalid, "position out of bounds",
1147 return isl_aff_free(aff));
1149 aff = isl_aff_cow(aff);
1153 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1155 return isl_aff_free(aff);
1157 first += 1 + isl_local_space_offset(aff->ls, type);
1158 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1160 return isl_aff_free(aff);
1165 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1166 enum isl_dim_type type, unsigned n)
1170 pos = isl_aff_dim(aff, type);
1172 return isl_aff_insert_dims(aff, type, pos, n);
1175 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1176 enum isl_dim_type type, unsigned n)
1180 pos = isl_pw_aff_dim(pwaff, type);
1182 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1185 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1187 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1188 return isl_pw_aff_alloc(dom, aff);
1192 #define PW isl_pw_aff
1196 #define EL_IS_ZERO is_empty
1200 #define IS_ZERO is_empty
1206 #define NO_MOVE_DIMS
1210 #include <isl_pw_templ.c>
1212 static __isl_give isl_set *align_params_pw_pw_set_and(
1213 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1214 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1215 __isl_take isl_pw_aff *pwaff2))
1217 if (!pwaff1 || !pwaff2)
1219 if (isl_space_match(pwaff1->dim, isl_dim_param,
1220 pwaff2->dim, isl_dim_param))
1221 return fn(pwaff1, pwaff2);
1222 if (!isl_space_has_named_params(pwaff1->dim) ||
1223 !isl_space_has_named_params(pwaff2->dim))
1224 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1225 "unaligned unnamed parameters", goto error);
1226 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1227 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1228 return fn(pwaff1, pwaff2);
1230 isl_pw_aff_free(pwaff1);
1231 isl_pw_aff_free(pwaff2);
1235 /* Compute a piecewise quasi-affine expression with a domain that
1236 * is the union of those of pwaff1 and pwaff2 and such that on each
1237 * cell, the quasi-affine expression is the better (according to cmp)
1238 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1239 * is defined on a given cell, then the associated expression
1240 * is the defined one.
1242 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1243 __isl_take isl_pw_aff *pwaff2,
1244 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1245 __isl_take isl_aff *aff2))
1252 if (!pwaff1 || !pwaff2)
1255 ctx = isl_space_get_ctx(pwaff1->dim);
1256 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1257 isl_die(ctx, isl_error_invalid,
1258 "arguments should live in same space", goto error);
1260 if (isl_pw_aff_is_empty(pwaff1)) {
1261 isl_pw_aff_free(pwaff1);
1265 if (isl_pw_aff_is_empty(pwaff2)) {
1266 isl_pw_aff_free(pwaff2);
1270 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1271 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1273 for (i = 0; i < pwaff1->n; ++i) {
1274 set = isl_set_copy(pwaff1->p[i].set);
1275 for (j = 0; j < pwaff2->n; ++j) {
1276 struct isl_set *common;
1279 common = isl_set_intersect(
1280 isl_set_copy(pwaff1->p[i].set),
1281 isl_set_copy(pwaff2->p[j].set));
1282 better = isl_set_from_basic_set(cmp(
1283 isl_aff_copy(pwaff2->p[j].aff),
1284 isl_aff_copy(pwaff1->p[i].aff)));
1285 better = isl_set_intersect(common, better);
1286 if (isl_set_plain_is_empty(better)) {
1287 isl_set_free(better);
1290 set = isl_set_subtract(set, isl_set_copy(better));
1292 res = isl_pw_aff_add_piece(res, better,
1293 isl_aff_copy(pwaff2->p[j].aff));
1295 res = isl_pw_aff_add_piece(res, set,
1296 isl_aff_copy(pwaff1->p[i].aff));
1299 for (j = 0; j < pwaff2->n; ++j) {
1300 set = isl_set_copy(pwaff2->p[j].set);
1301 for (i = 0; i < pwaff1->n; ++i)
1302 set = isl_set_subtract(set,
1303 isl_set_copy(pwaff1->p[i].set));
1304 res = isl_pw_aff_add_piece(res, set,
1305 isl_aff_copy(pwaff2->p[j].aff));
1308 isl_pw_aff_free(pwaff1);
1309 isl_pw_aff_free(pwaff2);
1313 isl_pw_aff_free(pwaff1);
1314 isl_pw_aff_free(pwaff2);
1318 /* Compute a piecewise quasi-affine expression with a domain that
1319 * is the union of those of pwaff1 and pwaff2 and such that on each
1320 * cell, the quasi-affine expression is the maximum of those of pwaff1
1321 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1322 * cell, then the associated expression is the defined one.
1324 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1325 __isl_take isl_pw_aff *pwaff2)
1327 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1330 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1331 __isl_take isl_pw_aff *pwaff2)
1333 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1336 /* Compute a piecewise quasi-affine expression with a domain that
1337 * is the union of those of pwaff1 and pwaff2 and such that on each
1338 * cell, the quasi-affine expression is the minimum of those of pwaff1
1339 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1340 * cell, then the associated expression is the defined one.
1342 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1343 __isl_take isl_pw_aff *pwaff2)
1345 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1348 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1349 __isl_take isl_pw_aff *pwaff2)
1351 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_min);
1354 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1355 __isl_take isl_pw_aff *pwaff2, int max)
1358 return isl_pw_aff_union_max(pwaff1, pwaff2);
1360 return isl_pw_aff_union_min(pwaff1, pwaff2);
1363 /* Construct a map with as domain the domain of pwaff and
1364 * one-dimensional range corresponding to the affine expressions.
1366 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1375 dim = isl_pw_aff_get_space(pwaff);
1376 map = isl_map_empty(dim);
1378 for (i = 0; i < pwaff->n; ++i) {
1379 isl_basic_map *bmap;
1382 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1383 map_i = isl_map_from_basic_map(bmap);
1384 map_i = isl_map_intersect_domain(map_i,
1385 isl_set_copy(pwaff->p[i].set));
1386 map = isl_map_union_disjoint(map, map_i);
1389 isl_pw_aff_free(pwaff);
1394 /* Construct a map with as domain the domain of pwaff and
1395 * one-dimensional range corresponding to the affine expressions.
1397 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1399 if (isl_space_is_set(pwaff->dim))
1400 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1401 "space of input is not a map",
1402 return isl_pw_aff_free(pwaff));
1403 return map_from_pw_aff(pwaff);
1406 /* Construct a one-dimensional set with as parameter domain
1407 * the domain of pwaff and the single set dimension
1408 * corresponding to the affine expressions.
1410 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1412 if (!isl_space_is_set(pwaff->dim))
1413 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1414 "space of input is not a set",
1415 return isl_pw_aff_free(pwaff));
1416 return map_from_pw_aff(pwaff);
1419 /* Return a set containing those elements in the domain
1420 * of pwaff where it is non-negative.
1422 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1430 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1432 for (i = 0; i < pwaff->n; ++i) {
1433 isl_basic_set *bset;
1436 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1437 set_i = isl_set_from_basic_set(bset);
1438 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1439 set = isl_set_union_disjoint(set, set_i);
1442 isl_pw_aff_free(pwaff);
1447 /* Return a set containing those elements in the domain
1448 * of pwaff where it is zero.
1450 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1458 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1460 for (i = 0; i < pwaff->n; ++i) {
1461 isl_basic_set *bset;
1464 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1465 set_i = isl_set_from_basic_set(bset);
1466 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1467 set = isl_set_union_disjoint(set, set_i);
1470 isl_pw_aff_free(pwaff);
1475 /* Return a set containing those elements in the domain
1476 * of pwaff where it is not zero.
1478 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1480 return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1483 /* Return a set containing those elements in the shared domain
1484 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1486 * We compute the difference on the shared domain and then construct
1487 * the set of values where this difference is non-negative.
1488 * If strict is set, we first subtract 1 from the difference.
1489 * If equal is set, we only return the elements where pwaff1 and pwaff2
1492 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1493 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1495 isl_set *set1, *set2;
1497 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1498 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1499 set1 = isl_set_intersect(set1, set2);
1500 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1501 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1502 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1505 isl_space *dim = isl_set_get_space(set1);
1507 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1508 aff = isl_aff_add_constant_si(aff, -1);
1509 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1514 return isl_pw_aff_zero_set(pwaff1);
1515 return isl_pw_aff_nonneg_set(pwaff1);
1518 /* Return a set containing those elements in the shared domain
1519 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1521 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1522 __isl_take isl_pw_aff *pwaff2)
1524 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1527 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1528 __isl_take isl_pw_aff *pwaff2)
1530 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1533 /* Return a set containing those elements in the shared domain
1534 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1536 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1537 __isl_take isl_pw_aff *pwaff2)
1539 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1542 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1543 __isl_take isl_pw_aff *pwaff2)
1545 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1548 /* Return a set containing those elements in the shared domain
1549 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1551 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1552 __isl_take isl_pw_aff *pwaff2)
1554 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1557 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1558 __isl_take isl_pw_aff *pwaff2)
1560 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1563 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1564 __isl_take isl_pw_aff *pwaff2)
1566 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1569 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1570 __isl_take isl_pw_aff *pwaff2)
1572 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1575 /* Return a set containing those elements in the shared domain
1576 * of the elements of list1 and list2 where each element in list1
1577 * has the relation specified by "fn" with each element in list2.
1579 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1580 __isl_take isl_pw_aff_list *list2,
1581 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1582 __isl_take isl_pw_aff *pwaff2))
1588 if (!list1 || !list2)
1591 ctx = isl_pw_aff_list_get_ctx(list1);
1592 if (list1->n < 1 || list2->n < 1)
1593 isl_die(ctx, isl_error_invalid,
1594 "list should contain at least one element", goto error);
1596 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1597 for (i = 0; i < list1->n; ++i)
1598 for (j = 0; j < list2->n; ++j) {
1601 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1602 isl_pw_aff_copy(list2->p[j]));
1603 set = isl_set_intersect(set, set_ij);
1606 isl_pw_aff_list_free(list1);
1607 isl_pw_aff_list_free(list2);
1610 isl_pw_aff_list_free(list1);
1611 isl_pw_aff_list_free(list2);
1615 /* Return a set containing those elements in the shared domain
1616 * of the elements of list1 and list2 where each element in list1
1617 * is equal to each element in list2.
1619 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1620 __isl_take isl_pw_aff_list *list2)
1622 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1625 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1626 __isl_take isl_pw_aff_list *list2)
1628 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1631 /* Return a set containing those elements in the shared domain
1632 * of the elements of list1 and list2 where each element in list1
1633 * is less than or equal to each element in list2.
1635 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1636 __isl_take isl_pw_aff_list *list2)
1638 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1641 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1642 __isl_take isl_pw_aff_list *list2)
1644 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1647 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1648 __isl_take isl_pw_aff_list *list2)
1650 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1653 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1654 __isl_take isl_pw_aff_list *list2)
1656 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1660 /* Return a set containing those elements in the shared domain
1661 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1663 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1664 __isl_take isl_pw_aff *pwaff2)
1666 isl_set *set_lt, *set_gt;
1668 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1669 isl_pw_aff_copy(pwaff2));
1670 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1671 return isl_set_union_disjoint(set_lt, set_gt);
1674 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1675 __isl_take isl_pw_aff *pwaff2)
1677 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1680 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1685 if (isl_int_is_one(v))
1687 if (!isl_int_is_pos(v))
1688 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1689 "factor needs to be positive",
1690 return isl_pw_aff_free(pwaff));
1691 pwaff = isl_pw_aff_cow(pwaff);
1697 for (i = 0; i < pwaff->n; ++i) {
1698 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1699 if (!pwaff->p[i].aff)
1700 return isl_pw_aff_free(pwaff);
1706 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1710 pwaff = isl_pw_aff_cow(pwaff);
1716 for (i = 0; i < pwaff->n; ++i) {
1717 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1718 if (!pwaff->p[i].aff)
1719 return isl_pw_aff_free(pwaff);
1725 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1729 pwaff = isl_pw_aff_cow(pwaff);
1735 for (i = 0; i < pwaff->n; ++i) {
1736 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1737 if (!pwaff->p[i].aff)
1738 return isl_pw_aff_free(pwaff);
1744 /* Return an affine expression that is equal to pwaff_true for elements
1745 * in "cond" and to pwaff_false for elements not in "cond".
1746 * That is, return cond ? pwaff_true : pwaff_false;
1748 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1749 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1753 comp = isl_set_complement(isl_set_copy(cond));
1754 pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1755 pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1757 return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1760 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1765 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1768 /* Check whether pwaff is a piecewise constant.
1770 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1777 for (i = 0; i < pwaff->n; ++i) {
1778 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1779 if (is_cst < 0 || !is_cst)
1786 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1787 __isl_take isl_aff *aff2)
1789 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1790 return isl_aff_mul(aff2, aff1);
1792 if (!isl_aff_is_cst(aff2))
1793 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1794 "at least one affine expression should be constant",
1797 aff1 = isl_aff_cow(aff1);
1801 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1802 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1812 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1813 __isl_take isl_pw_aff *pwaff2)
1818 if (!pwaff1 || !pwaff2)
1821 n = pwaff1->n * pwaff2->n;
1822 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1824 for (i = 0; i < pwaff1->n; ++i) {
1825 for (j = 0; j < pwaff2->n; ++j) {
1828 common = isl_set_intersect(
1829 isl_set_copy(pwaff1->p[i].set),
1830 isl_set_copy(pwaff2->p[j].set));
1831 if (isl_set_plain_is_empty(common)) {
1832 isl_set_free(common);
1836 prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1837 isl_aff_copy(pwaff2->p[j].aff));
1839 res = isl_pw_aff_add_piece(res, common, prod);
1843 isl_pw_aff_free(pwaff1);
1844 isl_pw_aff_free(pwaff2);
1847 isl_pw_aff_free(pwaff1);
1848 isl_pw_aff_free(pwaff2);
1852 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1853 __isl_take isl_pw_aff *pwaff2)
1855 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1858 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1859 __isl_take isl_pw_aff *pwaff2)
1863 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1864 isl_pw_aff_copy(pwaff2));
1865 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1868 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1869 __isl_take isl_pw_aff *pwaff2)
1871 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1874 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1875 __isl_take isl_pw_aff *pwaff2)
1879 le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1880 isl_pw_aff_copy(pwaff2));
1881 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1884 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1885 __isl_take isl_pw_aff *pwaff2)
1887 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1890 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1891 __isl_take isl_pw_aff_list *list,
1892 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1893 __isl_take isl_pw_aff *pwaff2))
1902 ctx = isl_pw_aff_list_get_ctx(list);
1904 isl_die(ctx, isl_error_invalid,
1905 "list should contain at least one element",
1906 return isl_pw_aff_list_free(list));
1908 res = isl_pw_aff_copy(list->p[0]);
1909 for (i = 1; i < list->n; ++i)
1910 res = fn(res, isl_pw_aff_copy(list->p[i]));
1912 isl_pw_aff_list_free(list);
1916 /* Return an isl_pw_aff that maps each element in the intersection of the
1917 * domains of the elements of list to the minimal corresponding affine
1920 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1922 return pw_aff_list_reduce(list, &isl_pw_aff_min);
1925 /* Return an isl_pw_aff that maps each element in the intersection of the
1926 * domains of the elements of list to the maximal corresponding affine
1929 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1931 return pw_aff_list_reduce(list, &isl_pw_aff_max);