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
);