2 * Copyright 2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 #include <isl_map_private.h>
12 #include <isl_aff_private.h>
13 #include <isl_local_space_private.h>
14 #include <isl_mat_private.h>
15 #include <isl/constraint.h>
19 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
20 __isl_take isl_vec *v)
27 aff = isl_calloc_type(v->ctx, struct isl_aff);
37 isl_local_space_free(ls);
42 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
51 ctx = isl_local_space_get_ctx(ls);
52 if (!isl_local_space_divs_known(ls))
53 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
56 total = isl_local_space_dim(ls, isl_dim_all);
57 v = isl_vec_alloc(ctx, 1 + 1 + total);
58 return isl_aff_alloc_vec(ls, v);
60 isl_local_space_free(ls);
64 __isl_give isl_aff *isl_aff_zero(__isl_take isl_local_space *ls)
68 aff = isl_aff_alloc(ls);
72 isl_int_set_si(aff->v->el[0], 1);
73 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
78 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
87 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
92 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
93 isl_vec_copy(aff->v));
96 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
104 return isl_aff_dup(aff);
107 void *isl_aff_free(__isl_take isl_aff *aff)
115 isl_local_space_free(aff->ls);
116 isl_vec_free(aff->v);
123 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
125 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
128 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
130 return aff ? isl_local_space_dim(aff->ls, type) : 0;
133 __isl_give isl_dim *isl_aff_get_dim(__isl_keep isl_aff *aff)
135 return aff ? isl_local_space_get_dim(aff->ls) : NULL;
138 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
140 return aff ? isl_local_space_copy(aff->ls) : NULL;
143 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
144 enum isl_dim_type type, unsigned pos)
146 return aff ? isl_local_space_get_dim_name(aff->ls, type, pos) : 0;
149 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
154 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
157 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
164 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
165 if (equal < 0 || !equal)
168 return isl_vec_is_equal(aff1->v, aff2->v);
171 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
175 isl_int_set(*v, aff->v->el[0]);
179 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
183 isl_int_set(*v, aff->v->el[1]);
187 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
188 enum isl_dim_type type, int pos, isl_int *v)
193 if (pos >= isl_local_space_dim(aff->ls, type))
194 isl_die(aff->v->ctx, isl_error_invalid,
195 "position out of bounds", return -1);
197 pos += isl_local_space_offset(aff->ls, type);
198 isl_int_set(*v, aff->v->el[1 + pos]);
203 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
205 aff = isl_aff_cow(aff);
209 aff->v = isl_vec_cow(aff->v);
211 return isl_aff_free(aff);
213 isl_int_set(aff->v->el[0], v);
218 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
220 aff = isl_aff_cow(aff);
224 aff->v = isl_vec_cow(aff->v);
226 return isl_aff_free(aff);
228 isl_int_set(aff->v->el[1], v);
233 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
235 if (isl_int_is_zero(v))
238 aff = isl_aff_cow(aff);
242 aff->v = isl_vec_cow(aff->v);
244 return isl_aff_free(aff);
246 isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
251 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
256 isl_int_set_si(t, v);
257 aff = isl_aff_add_constant(aff, t);
263 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
265 aff = isl_aff_cow(aff);
269 aff->v = isl_vec_cow(aff->v);
271 return isl_aff_free(aff);
273 isl_int_set_si(aff->v->el[1], v);
278 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
279 enum isl_dim_type type, int pos, isl_int v)
284 if (pos >= isl_local_space_dim(aff->ls, type))
285 isl_die(aff->v->ctx, isl_error_invalid,
286 "position out of bounds", return isl_aff_free(aff));
288 aff = isl_aff_cow(aff);
292 aff->v = isl_vec_cow(aff->v);
294 return isl_aff_free(aff);
296 pos += isl_local_space_offset(aff->ls, type);
297 isl_int_set(aff->v->el[1 + pos], v);
302 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
303 enum isl_dim_type type, int pos, int v)
308 if (pos >= isl_local_space_dim(aff->ls, type))
309 isl_die(aff->v->ctx, isl_error_invalid,
310 "position out of bounds", return isl_aff_free(aff));
312 aff = isl_aff_cow(aff);
316 aff->v = isl_vec_cow(aff->v);
318 return isl_aff_free(aff);
320 pos += isl_local_space_offset(aff->ls, type);
321 isl_int_set_si(aff->v->el[1 + pos], v);
326 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
327 enum isl_dim_type type, int pos, isl_int v)
332 if (pos >= isl_local_space_dim(aff->ls, type))
333 isl_die(aff->v->ctx, isl_error_invalid,
334 "position out of bounds", return isl_aff_free(aff));
336 aff = isl_aff_cow(aff);
340 aff->v = isl_vec_cow(aff->v);
342 return isl_aff_free(aff);
344 pos += isl_local_space_offset(aff->ls, type);
345 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
350 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
351 enum isl_dim_type type, int pos, int v)
356 isl_int_set_si(t, v);
357 aff = isl_aff_add_coefficient(aff, type, pos, t);
363 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
368 return isl_local_space_get_div(aff->ls, pos);
371 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
373 aff = isl_aff_cow(aff);
376 aff->v = isl_vec_cow(aff->v);
378 return isl_aff_free(aff);
380 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
385 /* Given f, return floor(f).
386 * If f is an integer expression, then just return f.
387 * Otherwise, create a new div d = [f] and return the expression d.
389 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
397 if (isl_int_is_one(aff->v->el[0]))
400 aff = isl_aff_cow(aff);
404 aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
406 return isl_aff_free(aff);
408 ctx = isl_aff_get_ctx(aff);
410 isl_vec_free(aff->v);
411 aff->v = isl_vec_alloc(ctx, size + 1);
412 aff->v = isl_vec_clr(aff->v);
414 return isl_aff_free(aff);
415 isl_int_set_si(aff->v->el[0], 1);
416 isl_int_set_si(aff->v->el[size], 1);
421 /* Given f, return ceil(f).
422 * If f is an integer expression, then just return f.
423 * Otherwise, create a new div d = [-f] and return the expression -d.
425 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
430 if (isl_int_is_one(aff->v->el[0]))
433 aff = isl_aff_neg(aff);
434 aff = isl_aff_floor(aff);
435 aff = isl_aff_neg(aff);
440 /* Apply the expansion computed by isl_merge_divs.
441 * The expansion itself is given by "exp" while the resulting
442 * list of divs is given by "div".
444 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
445 __isl_take isl_mat *div, int *exp)
452 aff = isl_aff_cow(aff);
456 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
457 new_n_div = isl_mat_rows(div);
458 if (new_n_div < old_n_div)
459 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
460 "not an expansion", goto error);
462 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
466 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
468 for (i = new_n_div - 1; i >= 0; --i) {
469 if (j >= 0 && exp[j] == i) {
471 isl_int_swap(aff->v->el[offset + i],
472 aff->v->el[offset + j]);
475 isl_int_set_si(aff->v->el[offset + i], 0);
478 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
489 /* Add two affine expressions that live in the same local space.
491 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
492 __isl_take isl_aff *aff2)
496 aff1 = isl_aff_cow(aff1);
500 aff1->v = isl_vec_cow(aff1->v);
506 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
507 isl_int_divexact(f, aff2->v->el[0], gcd);
508 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
509 isl_int_divexact(f, aff1->v->el[0], gcd);
510 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
511 isl_int_divexact(f, aff2->v->el[0], gcd);
512 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
524 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
525 __isl_take isl_aff *aff2)
535 ctx = isl_aff_get_ctx(aff1);
536 if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
537 isl_die(ctx, isl_error_invalid,
538 "spaces don't match", goto error);
540 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
541 return add_expanded(aff1, aff2);
543 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
544 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
548 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
549 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
550 aff2 = isl_aff_expand_divs(aff2, div, exp2);
554 return add_expanded(aff1, aff2);
563 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
564 __isl_take isl_aff *aff2)
566 return isl_aff_add(aff1, isl_aff_neg(aff2));
569 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
573 if (isl_int_is_one(f))
576 aff = isl_aff_cow(aff);
579 aff->v = isl_vec_cow(aff->v);
581 return isl_aff_free(aff);
584 isl_int_gcd(gcd, aff->v->el[0], f);
585 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
586 isl_int_divexact(gcd, f, gcd);
587 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
593 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
597 if (isl_int_is_one(f))
600 aff = isl_aff_cow(aff);
603 aff->v = isl_vec_cow(aff->v);
605 return isl_aff_free(aff);
608 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
609 isl_int_gcd(gcd, gcd, f);
610 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
611 isl_int_divexact(gcd, f, gcd);
612 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
618 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
626 isl_int_set_ui(v, f);
627 aff = isl_aff_scale_down(aff, v);
633 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
634 enum isl_dim_type type, unsigned pos, const char *s)
636 aff = isl_aff_cow(aff);
639 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
641 return isl_aff_free(aff);
646 /* Exploit the equalities in "eq" to simplify the affine expression
647 * and the expressions of the integer divisions in the local space.
648 * The integer divisions in this local space are assumed to appear
649 * as regular dimensions in "eq".
651 static __isl_give isl_aff *isl_aff_substitute_equalities(
652 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
661 isl_basic_set_free(eq);
665 aff = isl_aff_cow(aff);
669 aff->ls = isl_local_space_substitute_equalities(aff->ls,
670 isl_basic_set_copy(eq));
674 total = 1 + isl_dim_total(eq->dim);
676 for (i = 0; i < eq->n_eq; ++i) {
677 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
678 if (j < 0 || j == 0 || j >= total)
681 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
685 isl_basic_set_free(eq);
688 isl_basic_set_free(eq);
693 /* Look for equalities among the variables shared by context and aff
694 * and the integer divisions of aff, if any.
695 * The equalities are then used to eliminate coefficients and/or integer
696 * divisions from aff.
698 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
699 __isl_take isl_set *context)
706 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
709 context = isl_set_add_dims(context, isl_dim_set, n_div);
710 bset = isl_basic_set_from_local_space(
711 isl_aff_get_local_space(aff));
712 bset = isl_basic_set_lift(bset);
713 bset = isl_basic_set_flatten(bset);
714 context = isl_set_intersect(context,
715 isl_set_from_basic_set(bset));
718 hull = isl_set_affine_hull(context);
719 return isl_aff_substitute_equalities(aff, hull);
722 isl_set_free(context);
726 /* Return a basic set containing those elements in the shared space
727 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
729 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
730 __isl_take isl_aff *aff2)
732 isl_constraint *ineq;
734 aff1 = isl_aff_sub(aff1, aff2);
735 ineq = isl_inequality_from_aff(aff1);
737 return isl_basic_set_from_constraint(ineq);