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>
17 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
18 __isl_take isl_vec *v)
25 aff = isl_calloc_type(v->ctx, struct isl_aff);
35 isl_local_space_free(ls);
40 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
49 ctx = isl_local_space_get_ctx(ls);
50 if (!isl_local_space_divs_known(ls))
51 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
54 total = isl_local_space_dim(ls, isl_dim_all);
55 v = isl_vec_alloc(ctx, 1 + 1 + total);
56 return isl_aff_alloc_vec(ls, v);
58 isl_local_space_free(ls);
62 __isl_give isl_aff *isl_aff_zero(__isl_take isl_local_space *ls)
66 aff = isl_aff_alloc(ls);
70 isl_int_set_si(aff->v->el[0], 1);
71 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
76 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
85 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
90 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
91 isl_vec_copy(aff->v));
94 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
102 return isl_aff_dup(aff);
105 void *isl_aff_free(__isl_take isl_aff *aff)
113 isl_local_space_free(aff->ls);
114 isl_vec_free(aff->v);
121 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
123 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
126 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
128 return aff ? isl_local_space_dim(aff->ls, type) : 0;
131 __isl_give isl_dim *isl_aff_get_dim(__isl_keep isl_aff *aff)
133 return aff ? isl_local_space_get_dim(aff->ls) : NULL;
136 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
138 return aff ? isl_local_space_copy(aff->ls) : NULL;
141 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
142 enum isl_dim_type type, unsigned pos)
144 return aff ? isl_local_space_get_dim_name(aff->ls, type, pos) : 0;
147 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
152 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
155 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
162 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
163 if (equal < 0 || !equal)
166 return isl_vec_is_equal(aff1->v, aff2->v);
169 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
173 isl_int_set(*v, aff->v->el[0]);
177 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
181 isl_int_set(*v, aff->v->el[1]);
185 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
186 enum isl_dim_type type, int pos, isl_int *v)
191 if (pos >= isl_local_space_dim(aff->ls, type))
192 isl_die(aff->v->ctx, isl_error_invalid,
193 "position out of bounds", return -1);
195 pos += isl_local_space_offset(aff->ls, type);
196 isl_int_set(*v, aff->v->el[1 + pos]);
201 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
203 aff = isl_aff_cow(aff);
207 aff->v = isl_vec_cow(aff->v);
209 return isl_aff_free(aff);
211 isl_int_set(aff->v->el[0], v);
216 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
218 aff = isl_aff_cow(aff);
222 aff->v = isl_vec_cow(aff->v);
224 return isl_aff_free(aff);
226 isl_int_set(aff->v->el[1], v);
231 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
233 if (isl_int_is_zero(v))
236 aff = isl_aff_cow(aff);
240 aff->v = isl_vec_cow(aff->v);
242 return isl_aff_free(aff);
244 isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
249 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
254 isl_int_set_si(t, v);
255 aff = isl_aff_add_constant(aff, t);
261 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
263 aff = isl_aff_cow(aff);
267 aff->v = isl_vec_cow(aff->v);
269 return isl_aff_free(aff);
271 isl_int_set_si(aff->v->el[1], v);
276 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
277 enum isl_dim_type type, int pos, isl_int v)
282 if (pos >= isl_local_space_dim(aff->ls, type))
283 isl_die(aff->v->ctx, isl_error_invalid,
284 "position out of bounds", return isl_aff_free(aff));
286 aff = isl_aff_cow(aff);
290 aff->v = isl_vec_cow(aff->v);
292 return isl_aff_free(aff);
294 pos += isl_local_space_offset(aff->ls, type);
295 isl_int_set(aff->v->el[1 + pos], v);
300 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
301 enum isl_dim_type type, int pos, int v)
306 if (pos >= isl_local_space_dim(aff->ls, type))
307 isl_die(aff->v->ctx, isl_error_invalid,
308 "position out of bounds", return isl_aff_free(aff));
310 aff = isl_aff_cow(aff);
314 aff->v = isl_vec_cow(aff->v);
316 return isl_aff_free(aff);
318 pos += isl_local_space_offset(aff->ls, type);
319 isl_int_set_si(aff->v->el[1 + pos], v);
324 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
325 enum isl_dim_type type, int pos, isl_int v)
330 if (pos >= isl_local_space_dim(aff->ls, type))
331 isl_die(aff->v->ctx, isl_error_invalid,
332 "position out of bounds", return isl_aff_free(aff));
334 aff = isl_aff_cow(aff);
338 aff->v = isl_vec_cow(aff->v);
340 return isl_aff_free(aff);
342 pos += isl_local_space_offset(aff->ls, type);
343 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
348 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
349 enum isl_dim_type type, int pos, int v)
354 isl_int_set_si(t, v);
355 aff = isl_aff_add_coefficient(aff, type, pos, t);
361 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
366 return isl_local_space_get_div(aff->ls, pos);
369 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
371 aff = isl_aff_cow(aff);
374 aff->v = isl_vec_cow(aff->v);
376 return isl_aff_free(aff);
378 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
383 /* Given f, return floor(f).
384 * If f is an integer expression, then just return f.
385 * Otherwise, create a new div d = [f] and return the expression d.
387 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
395 if (isl_int_is_one(aff->v->el[0]))
398 aff = isl_aff_cow(aff);
402 aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
404 return isl_aff_free(aff);
406 ctx = isl_aff_get_ctx(aff);
408 isl_vec_free(aff->v);
409 aff->v = isl_vec_alloc(ctx, size + 1);
410 aff->v = isl_vec_clr(aff->v);
412 return isl_aff_free(aff);
413 isl_int_set_si(aff->v->el[0], 1);
414 isl_int_set_si(aff->v->el[size], 1);
419 /* Given f, return ceil(f).
420 * If f is an integer expression, then just return f.
421 * Otherwise, create a new div d = [-f] and return the expression -d.
423 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
428 if (isl_int_is_one(aff->v->el[0]))
431 aff = isl_aff_neg(aff);
432 aff = isl_aff_floor(aff);
433 aff = isl_aff_neg(aff);
438 /* Apply the expansion computed by isl_merge_divs.
439 * The expansion itself is given by "exp" while the resulting
440 * list of divs is given by "div".
442 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
443 __isl_take isl_mat *div, int *exp)
450 aff = isl_aff_cow(aff);
454 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
455 new_n_div = isl_mat_rows(div);
456 if (new_n_div < old_n_div)
457 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
458 "not an expansion", goto error);
460 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
464 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
466 for (i = new_n_div - 1; i >= 0; --i) {
467 if (j >= 0 && exp[j] == i) {
469 isl_int_swap(aff->v->el[offset + i],
470 aff->v->el[offset + j]);
473 isl_int_set_si(aff->v->el[offset + i], 0);
476 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
487 /* Add two affine expressions that live in the same local space.
489 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
490 __isl_take isl_aff *aff2)
494 aff1 = isl_aff_cow(aff1);
498 aff1->v = isl_vec_cow(aff1->v);
504 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
505 isl_int_divexact(f, aff2->v->el[0], gcd);
506 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
507 isl_int_divexact(f, aff1->v->el[0], gcd);
508 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
509 isl_int_divexact(f, aff2->v->el[0], gcd);
510 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
522 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
523 __isl_take isl_aff *aff2)
533 ctx = isl_aff_get_ctx(aff1);
534 if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
535 isl_die(ctx, isl_error_invalid,
536 "spaces don't match", goto error);
538 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
539 return add_expanded(aff1, aff2);
541 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
542 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
546 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
547 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
548 aff2 = isl_aff_expand_divs(aff2, div, exp2);
552 return add_expanded(aff1, aff2);
561 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
562 __isl_take isl_aff *aff2)
564 return isl_aff_add(aff1, isl_aff_neg(aff2));
567 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
571 if (isl_int_is_one(f))
574 aff = isl_aff_cow(aff);
577 aff->v = isl_vec_cow(aff->v);
579 return isl_aff_free(aff);
582 isl_int_gcd(gcd, aff->v->el[0], f);
583 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
584 isl_int_divexact(gcd, f, gcd);
585 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
591 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
595 if (isl_int_is_one(f))
598 aff = isl_aff_cow(aff);
601 aff->v = isl_vec_cow(aff->v);
603 return isl_aff_free(aff);
606 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
607 isl_int_gcd(gcd, gcd, f);
608 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
609 isl_int_divexact(gcd, f, gcd);
610 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
616 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
624 isl_int_set_ui(v, f);
625 aff = isl_aff_scale_down(aff, v);
631 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
632 enum isl_dim_type type, unsigned pos, const char *s)
634 aff = isl_aff_cow(aff);
637 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
639 return isl_aff_free(aff);
644 /* Exploit the equalities in "eq" to simplify the affine expression
645 * and the expressions of the integer divisions in the local space.
646 * The integer divisions in this local space are assumed to appear
647 * as regular dimensions in "eq".
649 static __isl_give isl_aff *isl_aff_substitute_equalities(
650 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
659 isl_basic_set_free(eq);
663 aff = isl_aff_cow(aff);
667 aff->ls = isl_local_space_substitute_equalities(aff->ls,
668 isl_basic_set_copy(eq));
672 total = 1 + isl_dim_total(eq->dim);
674 for (i = 0; i < eq->n_eq; ++i) {
675 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
676 if (j < 0 || j == 0 || j >= total)
679 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
683 isl_basic_set_free(eq);
686 isl_basic_set_free(eq);
691 /* Look for equalities among the variables shared by context and aff
692 * and the integer divisions of aff, if any.
693 * The equalities are then used to eliminate coefficients and/or integer
694 * divisions from aff.
696 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
697 __isl_take isl_set *context)
704 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
707 context = isl_set_add_dims(context, isl_dim_set, n_div);
708 bset = isl_basic_set_from_local_space(
709 isl_aff_get_local_space(aff));
710 bset = isl_basic_set_lift(bset);
711 bset = isl_basic_set_flatten(bset);
712 context = isl_set_intersect(context,
713 isl_set_from_basic_set(bset));
716 hull = isl_set_affine_hull(context);
717 return isl_aff_substitute_equalities(aff, hull);
720 isl_set_free(context);