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_map_private.h>
13 #include <isl_aff_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_local_space_private.h>
16 #include <isl_mat_private.h>
17 #include <isl/constraint.h>
21 __isl_give isl_aff
*isl_aff_alloc_vec(__isl_take isl_local_space
*ls
,
22 __isl_take isl_vec
*v
)
29 aff
= isl_calloc_type(v
->ctx
, struct isl_aff
);
39 isl_local_space_free(ls
);
44 __isl_give isl_aff
*isl_aff_alloc(__isl_take isl_local_space
*ls
)
53 ctx
= isl_local_space_get_ctx(ls
);
54 if (!isl_local_space_divs_known(ls
))
55 isl_die(ctx
, isl_error_invalid
, "local space has unknown divs",
58 total
= isl_local_space_dim(ls
, isl_dim_all
);
59 v
= isl_vec_alloc(ctx
, 1 + 1 + total
);
60 return isl_aff_alloc_vec(ls
, v
);
62 isl_local_space_free(ls
);
66 __isl_give isl_aff
*isl_aff_zero(__isl_take isl_local_space
*ls
)
70 aff
= isl_aff_alloc(ls
);
74 isl_int_set_si(aff
->v
->el
[0], 1);
75 isl_seq_clr(aff
->v
->el
+ 1, aff
->v
->size
- 1);
80 __isl_give isl_aff
*isl_aff_copy(__isl_keep isl_aff
*aff
)
89 __isl_give isl_aff
*isl_aff_dup(__isl_keep isl_aff
*aff
)
94 return isl_aff_alloc_vec(isl_local_space_copy(aff
->ls
),
95 isl_vec_copy(aff
->v
));
98 __isl_give isl_aff
*isl_aff_cow(__isl_take isl_aff
*aff
)
106 return isl_aff_dup(aff
);
109 void *isl_aff_free(__isl_take isl_aff
*aff
)
117 isl_local_space_free(aff
->ls
);
118 isl_vec_free(aff
->v
);
125 isl_ctx
*isl_aff_get_ctx(__isl_keep isl_aff
*aff
)
127 return aff
? isl_local_space_get_ctx(aff
->ls
) : NULL
;
130 int isl_aff_dim(__isl_keep isl_aff
*aff
, enum isl_dim_type type
)
132 return aff
? isl_local_space_dim(aff
->ls
, type
) : 0;
135 __isl_give isl_dim
*isl_aff_get_dim(__isl_keep isl_aff
*aff
)
137 return aff
? isl_local_space_get_dim(aff
->ls
) : NULL
;
140 __isl_give isl_local_space
*isl_aff_get_local_space(__isl_keep isl_aff
*aff
)
142 return aff
? isl_local_space_copy(aff
->ls
) : NULL
;
145 const char *isl_aff_get_dim_name(__isl_keep isl_aff
*aff
,
146 enum isl_dim_type type
, unsigned pos
)
148 return aff
? isl_local_space_get_dim_name(aff
->ls
, type
, pos
) : 0;
151 __isl_give isl_aff
*isl_aff_reset_dim(__isl_take isl_aff
*aff
,
152 __isl_take isl_dim
*dim
)
154 aff
= isl_aff_cow(aff
);
158 aff
->ls
= isl_local_space_reset_dim(aff
->ls
, dim
);
160 return isl_aff_free(aff
);
169 /* Reorder the coefficients of the affine expression based
170 * on the given reodering.
171 * The reordering r is assumed to have been extended with the local
174 static __isl_give isl_vec
*vec_reorder(__isl_take isl_vec
*vec
,
175 __isl_take isl_reordering
*r
, int n_div
)
183 res
= isl_vec_alloc(vec
->ctx
, 2 + isl_dim_total(r
->dim
) + n_div
);
184 isl_seq_cpy(res
->el
, vec
->el
, 2);
185 isl_seq_clr(res
->el
+ 2, res
->size
- 2);
186 for (i
= 0; i
< r
->len
; ++i
)
187 isl_int_set(res
->el
[2 + r
->pos
[i
]], vec
->el
[2 + i
]);
189 isl_reordering_free(r
);
194 isl_reordering_free(r
);
198 /* Reorder the dimensions of "aff" according to the given reordering.
200 __isl_give isl_aff
*isl_aff_realign(__isl_take isl_aff
*aff
,
201 __isl_take isl_reordering
*r
)
203 aff
= isl_aff_cow(aff
);
207 r
= isl_reordering_extend(r
, aff
->ls
->div
->n_row
);
208 aff
->v
= vec_reorder(aff
->v
, isl_reordering_copy(r
),
209 aff
->ls
->div
->n_row
);
210 aff
->ls
= isl_local_space_realign(aff
->ls
, r
);
212 if (!aff
->v
|| !aff
->ls
)
213 return isl_aff_free(aff
);
218 isl_reordering_free(r
);
222 int isl_aff_plain_is_zero(__isl_keep isl_aff
*aff
)
227 return isl_seq_first_non_zero(aff
->v
->el
+ 1, aff
->v
->size
- 1) < 0;
230 int isl_aff_plain_is_equal(__isl_keep isl_aff
*aff1
, __isl_keep isl_aff
*aff2
)
237 equal
= isl_local_space_is_equal(aff1
->ls
, aff2
->ls
);
238 if (equal
< 0 || !equal
)
241 return isl_vec_is_equal(aff1
->v
, aff2
->v
);
244 int isl_aff_get_denominator(__isl_keep isl_aff
*aff
, isl_int
*v
)
248 isl_int_set(*v
, aff
->v
->el
[0]);
252 int isl_aff_get_constant(__isl_keep isl_aff
*aff
, isl_int
*v
)
256 isl_int_set(*v
, aff
->v
->el
[1]);
260 int isl_aff_get_coefficient(__isl_keep isl_aff
*aff
,
261 enum isl_dim_type type
, int pos
, isl_int
*v
)
266 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
267 isl_die(aff
->v
->ctx
, isl_error_invalid
,
268 "position out of bounds", return -1);
270 pos
+= isl_local_space_offset(aff
->ls
, type
);
271 isl_int_set(*v
, aff
->v
->el
[1 + pos
]);
276 __isl_give isl_aff
*isl_aff_set_denominator(__isl_take isl_aff
*aff
, isl_int v
)
278 aff
= isl_aff_cow(aff
);
282 aff
->v
= isl_vec_cow(aff
->v
);
284 return isl_aff_free(aff
);
286 isl_int_set(aff
->v
->el
[0], v
);
291 __isl_give isl_aff
*isl_aff_set_constant(__isl_take isl_aff
*aff
, isl_int v
)
293 aff
= isl_aff_cow(aff
);
297 aff
->v
= isl_vec_cow(aff
->v
);
299 return isl_aff_free(aff
);
301 isl_int_set(aff
->v
->el
[1], v
);
306 __isl_give isl_aff
*isl_aff_add_constant(__isl_take isl_aff
*aff
, isl_int v
)
308 if (isl_int_is_zero(v
))
311 aff
= isl_aff_cow(aff
);
315 aff
->v
= isl_vec_cow(aff
->v
);
317 return isl_aff_free(aff
);
319 isl_int_addmul(aff
->v
->el
[1], aff
->v
->el
[0], v
);
324 __isl_give isl_aff
*isl_aff_add_constant_si(__isl_take isl_aff
*aff
, int v
)
329 isl_int_set_si(t
, v
);
330 aff
= isl_aff_add_constant(aff
, t
);
336 __isl_give isl_aff
*isl_aff_set_constant_si(__isl_take isl_aff
*aff
, int v
)
338 aff
= isl_aff_cow(aff
);
342 aff
->v
= isl_vec_cow(aff
->v
);
344 return isl_aff_free(aff
);
346 isl_int_set_si(aff
->v
->el
[1], v
);
351 __isl_give isl_aff
*isl_aff_set_coefficient(__isl_take isl_aff
*aff
,
352 enum isl_dim_type type
, int pos
, isl_int v
)
357 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
358 isl_die(aff
->v
->ctx
, isl_error_invalid
,
359 "position out of bounds", return isl_aff_free(aff
));
361 aff
= isl_aff_cow(aff
);
365 aff
->v
= isl_vec_cow(aff
->v
);
367 return isl_aff_free(aff
);
369 pos
+= isl_local_space_offset(aff
->ls
, type
);
370 isl_int_set(aff
->v
->el
[1 + pos
], v
);
375 __isl_give isl_aff
*isl_aff_set_coefficient_si(__isl_take isl_aff
*aff
,
376 enum isl_dim_type type
, int pos
, int v
)
381 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
382 isl_die(aff
->v
->ctx
, isl_error_invalid
,
383 "position out of bounds", return isl_aff_free(aff
));
385 aff
= isl_aff_cow(aff
);
389 aff
->v
= isl_vec_cow(aff
->v
);
391 return isl_aff_free(aff
);
393 pos
+= isl_local_space_offset(aff
->ls
, type
);
394 isl_int_set_si(aff
->v
->el
[1 + pos
], v
);
399 __isl_give isl_aff
*isl_aff_add_coefficient(__isl_take isl_aff
*aff
,
400 enum isl_dim_type type
, int pos
, isl_int v
)
405 if (pos
>= isl_local_space_dim(aff
->ls
, type
))
406 isl_die(aff
->v
->ctx
, isl_error_invalid
,
407 "position out of bounds", return isl_aff_free(aff
));
409 aff
= isl_aff_cow(aff
);
413 aff
->v
= isl_vec_cow(aff
->v
);
415 return isl_aff_free(aff
);
417 pos
+= isl_local_space_offset(aff
->ls
, type
);
418 isl_int_addmul(aff
->v
->el
[1 + pos
], aff
->v
->el
[0], v
);
423 __isl_give isl_aff
*isl_aff_add_coefficient_si(__isl_take isl_aff
*aff
,
424 enum isl_dim_type type
, int pos
, int v
)
429 isl_int_set_si(t
, v
);
430 aff
= isl_aff_add_coefficient(aff
, type
, pos
, t
);
436 __isl_give isl_div
*isl_aff_get_div(__isl_keep isl_aff
*aff
, int pos
)
441 return isl_local_space_get_div(aff
->ls
, pos
);
444 __isl_give isl_aff
*isl_aff_neg(__isl_take isl_aff
*aff
)
446 aff
= isl_aff_cow(aff
);
449 aff
->v
= isl_vec_cow(aff
->v
);
451 return isl_aff_free(aff
);
453 isl_seq_neg(aff
->v
->el
+ 1, aff
->v
->el
+ 1, aff
->v
->size
- 1);
458 /* Given f, return floor(f).
459 * If f is an integer expression, then just return f.
460 * Otherwise, create a new div d = [f] and return the expression d.
462 __isl_give isl_aff
*isl_aff_floor(__isl_take isl_aff
*aff
)
470 if (isl_int_is_one(aff
->v
->el
[0]))
473 aff
= isl_aff_cow(aff
);
477 aff
->ls
= isl_local_space_add_div(aff
->ls
, isl_vec_copy(aff
->v
));
479 return isl_aff_free(aff
);
481 ctx
= isl_aff_get_ctx(aff
);
483 isl_vec_free(aff
->v
);
484 aff
->v
= isl_vec_alloc(ctx
, size
+ 1);
485 aff
->v
= isl_vec_clr(aff
->v
);
487 return isl_aff_free(aff
);
488 isl_int_set_si(aff
->v
->el
[0], 1);
489 isl_int_set_si(aff
->v
->el
[size
], 1);
494 /* Given f, return ceil(f).
495 * If f is an integer expression, then just return f.
496 * Otherwise, create a new div d = [-f] and return the expression -d.
498 __isl_give isl_aff
*isl_aff_ceil(__isl_take isl_aff
*aff
)
503 if (isl_int_is_one(aff
->v
->el
[0]))
506 aff
= isl_aff_neg(aff
);
507 aff
= isl_aff_floor(aff
);
508 aff
= isl_aff_neg(aff
);
513 /* Apply the expansion computed by isl_merge_divs.
514 * The expansion itself is given by "exp" while the resulting
515 * list of divs is given by "div".
517 __isl_give isl_aff
*isl_aff_expand_divs( __isl_take isl_aff
*aff
,
518 __isl_take isl_mat
*div
, int *exp
)
525 aff
= isl_aff_cow(aff
);
529 old_n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
530 new_n_div
= isl_mat_rows(div
);
531 if (new_n_div
< old_n_div
)
532 isl_die(isl_mat_get_ctx(div
), isl_error_invalid
,
533 "not an expansion", goto error
);
535 aff
->v
= isl_vec_extend(aff
->v
, aff
->v
->size
+ new_n_div
- old_n_div
);
539 offset
= 1 + isl_local_space_offset(aff
->ls
, isl_dim_div
);
541 for (i
= new_n_div
- 1; i
>= 0; --i
) {
542 if (j
>= 0 && exp
[j
] == i
) {
544 isl_int_swap(aff
->v
->el
[offset
+ i
],
545 aff
->v
->el
[offset
+ j
]);
548 isl_int_set_si(aff
->v
->el
[offset
+ i
], 0);
551 aff
->ls
= isl_local_space_replace_divs(aff
->ls
, isl_mat_copy(div
));
562 /* Add two affine expressions that live in the same local space.
564 static __isl_give isl_aff
*add_expanded(__isl_take isl_aff
*aff1
,
565 __isl_take isl_aff
*aff2
)
569 aff1
= isl_aff_cow(aff1
);
573 aff1
->v
= isl_vec_cow(aff1
->v
);
579 isl_int_gcd(gcd
, aff1
->v
->el
[0], aff2
->v
->el
[0]);
580 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
581 isl_seq_scale(aff1
->v
->el
+ 1, aff1
->v
->el
+ 1, f
, aff1
->v
->size
- 1);
582 isl_int_divexact(f
, aff1
->v
->el
[0], gcd
);
583 isl_seq_addmul(aff1
->v
->el
+ 1, f
, aff2
->v
->el
+ 1, aff1
->v
->size
- 1);
584 isl_int_divexact(f
, aff2
->v
->el
[0], gcd
);
585 isl_int_mul(aff1
->v
->el
[0], aff1
->v
->el
[0], f
);
597 __isl_give isl_aff
*isl_aff_add(__isl_take isl_aff
*aff1
,
598 __isl_take isl_aff
*aff2
)
608 ctx
= isl_aff_get_ctx(aff1
);
609 if (!isl_dim_equal(aff1
->ls
->dim
, aff2
->ls
->dim
))
610 isl_die(ctx
, isl_error_invalid
,
611 "spaces don't match", goto error
);
613 if (aff1
->ls
->div
->n_row
== 0 && aff2
->ls
->div
->n_row
== 0)
614 return add_expanded(aff1
, aff2
);
616 exp1
= isl_alloc_array(ctx
, int, aff1
->ls
->div
->n_row
);
617 exp2
= isl_alloc_array(ctx
, int, aff2
->ls
->div
->n_row
);
621 div
= isl_merge_divs(aff1
->ls
->div
, aff2
->ls
->div
, exp1
, exp2
);
622 aff1
= isl_aff_expand_divs(aff1
, isl_mat_copy(div
), exp1
);
623 aff2
= isl_aff_expand_divs(aff2
, div
, exp2
);
627 return add_expanded(aff1
, aff2
);
636 __isl_give isl_aff
*isl_aff_sub(__isl_take isl_aff
*aff1
,
637 __isl_take isl_aff
*aff2
)
639 return isl_aff_add(aff1
, isl_aff_neg(aff2
));
642 __isl_give isl_aff
*isl_aff_scale(__isl_take isl_aff
*aff
, isl_int f
)
646 if (isl_int_is_one(f
))
649 aff
= isl_aff_cow(aff
);
652 aff
->v
= isl_vec_cow(aff
->v
);
654 return isl_aff_free(aff
);
657 isl_int_gcd(gcd
, aff
->v
->el
[0], f
);
658 isl_int_divexact(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
659 isl_int_divexact(gcd
, f
, gcd
);
660 isl_seq_scale(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
666 __isl_give isl_aff
*isl_aff_scale_down(__isl_take isl_aff
*aff
, isl_int f
)
670 if (isl_int_is_one(f
))
673 aff
= isl_aff_cow(aff
);
676 aff
->v
= isl_vec_cow(aff
->v
);
678 return isl_aff_free(aff
);
681 isl_seq_gcd(aff
->v
->el
+ 1, aff
->v
->size
- 1, &gcd
);
682 isl_int_gcd(gcd
, gcd
, f
);
683 isl_seq_scale_down(aff
->v
->el
+ 1, aff
->v
->el
+ 1, gcd
, aff
->v
->size
- 1);
684 isl_int_divexact(gcd
, f
, gcd
);
685 isl_int_mul(aff
->v
->el
[0], aff
->v
->el
[0], gcd
);
691 __isl_give isl_aff
*isl_aff_scale_down_ui(__isl_take isl_aff
*aff
, unsigned f
)
699 isl_int_set_ui(v
, f
);
700 aff
= isl_aff_scale_down(aff
, v
);
706 __isl_give isl_aff
*isl_aff_set_dim_name(__isl_take isl_aff
*aff
,
707 enum isl_dim_type type
, unsigned pos
, const char *s
)
709 aff
= isl_aff_cow(aff
);
712 aff
->ls
= isl_local_space_set_dim_name(aff
->ls
, type
, pos
, s
);
714 return isl_aff_free(aff
);
719 /* Exploit the equalities in "eq" to simplify the affine expression
720 * and the expressions of the integer divisions in the local space.
721 * The integer divisions in this local space are assumed to appear
722 * as regular dimensions in "eq".
724 static __isl_give isl_aff
*isl_aff_substitute_equalities_lifted(
725 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
734 isl_basic_set_free(eq
);
738 aff
= isl_aff_cow(aff
);
742 aff
->ls
= isl_local_space_substitute_equalities(aff
->ls
,
743 isl_basic_set_copy(eq
));
747 total
= 1 + isl_dim_total(eq
->dim
);
749 for (i
= 0; i
< eq
->n_eq
; ++i
) {
750 j
= isl_seq_last_non_zero(eq
->eq
[i
], total
+ n_div
);
751 if (j
< 0 || j
== 0 || j
>= total
)
754 isl_seq_elim(aff
->v
->el
+ 1, eq
->eq
[i
], j
, total
,
758 isl_basic_set_free(eq
);
761 isl_basic_set_free(eq
);
766 /* Exploit the equalities in "eq" to simplify the affine expression
767 * and the expressions of the integer divisions in the local space.
769 static __isl_give isl_aff
*isl_aff_substitute_equalities(
770 __isl_take isl_aff
*aff
, __isl_take isl_basic_set
*eq
)
776 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
778 eq
= isl_basic_set_add(eq
, isl_dim_set
, n_div
);
779 return isl_aff_substitute_equalities_lifted(aff
, eq
);
781 isl_basic_set_free(eq
);
786 /* Look for equalities among the variables shared by context and aff
787 * and the integer divisions of aff, if any.
788 * The equalities are then used to eliminate coefficients and/or integer
789 * divisions from aff.
791 __isl_give isl_aff
*isl_aff_gist(__isl_take isl_aff
*aff
,
792 __isl_take isl_set
*context
)
799 n_div
= isl_local_space_dim(aff
->ls
, isl_dim_div
);
802 context
= isl_set_add_dims(context
, isl_dim_set
, n_div
);
803 bset
= isl_basic_set_from_local_space(
804 isl_aff_get_local_space(aff
));
805 bset
= isl_basic_set_lift(bset
);
806 bset
= isl_basic_set_flatten(bset
);
807 context
= isl_set_intersect(context
,
808 isl_set_from_basic_set(bset
));
811 hull
= isl_set_affine_hull(context
);
812 return isl_aff_substitute_equalities_lifted(aff
, hull
);
815 isl_set_free(context
);
819 /* Return a basic set containing those elements in the space
820 * of aff where it is non-negative.
822 __isl_give isl_basic_set
*isl_aff_nonneg_basic_set(__isl_take isl_aff
*aff
)
824 isl_constraint
*ineq
;
826 ineq
= isl_inequality_from_aff(aff
);
828 return isl_basic_set_from_constraint(ineq
);
831 /* Return a basic set containing those elements in the space
832 * of aff where it is zero.
834 __isl_give isl_basic_set
*isl_aff_zero_basic_set(__isl_take isl_aff
*aff
)
836 isl_constraint
*ineq
;
838 ineq
= isl_equality_from_aff(aff
);
840 return isl_basic_set_from_constraint(ineq
);
843 /* Return a basic set containing those elements in the shared space
844 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
846 __isl_give isl_basic_set
*isl_aff_ge_basic_set(__isl_take isl_aff
*aff1
,
847 __isl_take isl_aff
*aff2
)
849 aff1
= isl_aff_sub(aff1
, aff2
);
851 return isl_aff_nonneg_basic_set(aff1
);
854 __isl_give isl_aff
*isl_aff_add_on_domain(__isl_keep isl_set
*dom
,
855 __isl_take isl_aff
*aff1
, __isl_take isl_aff
*aff2
)
857 aff1
= isl_aff_add(aff1
, aff2
);
858 aff1
= isl_aff_gist(aff1
, isl_set_copy(dom
));
862 int isl_aff_is_empty(__isl_keep isl_aff
*aff
)
870 /* Set active[i] to 1 if the dimension at position i is involved
871 * in the affine expression.
873 static int set_active(__isl_keep isl_aff
*aff
, int *active
)
882 total
= aff
->v
->size
- 2;
883 for (i
= 0; i
< total
; ++i
)
884 active
[i
] = !isl_int_is_zero(aff
->v
->el
[2 + i
]);
886 offset
= isl_local_space_offset(aff
->ls
, isl_dim_div
) - 1;
887 for (i
= aff
->ls
->div
->n_row
- 1; i
>= 0; --i
) {
888 if (!active
[offset
+ i
])
890 for (j
= 0; j
< total
; ++j
)
892 !isl_int_is_zero(aff
->ls
->div
->row
[i
][2 + j
]);
898 /* Check whether the given affine expression has non-zero coefficient
899 * for any dimension in the given range or if any of these dimensions
900 * appear with non-zero coefficients in any of the integer divisions
901 * involved in the affine expression.
903 int isl_aff_involves_dims(__isl_keep isl_aff
*aff
,
904 enum isl_dim_type type
, unsigned first
, unsigned n
)
916 ctx
= isl_aff_get_ctx(aff
);
917 if (first
+ n
> isl_aff_dim(aff
, type
))
918 isl_die(ctx
, isl_error_invalid
,
919 "range out of bounds", return -1);
921 active
= isl_calloc_array(ctx
, int,
922 isl_local_space_dim(aff
->ls
, isl_dim_all
));
923 if (set_active(aff
, active
) < 0)
926 first
+= isl_local_space_offset(aff
->ls
, type
) - 1;
927 for (i
= 0; i
< n
; ++i
)
928 if (active
[first
+ i
]) {
941 __isl_give isl_aff
*isl_aff_drop_dims(__isl_take isl_aff
*aff
,
942 enum isl_dim_type type
, unsigned first
, unsigned n
)
948 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
951 ctx
= isl_aff_get_ctx(aff
);
952 if (first
+ n
> isl_aff_dim(aff
, type
))
953 isl_die(ctx
, isl_error_invalid
, "range out of bounds",
954 return isl_aff_free(aff
));
956 aff
= isl_aff_cow(aff
);
960 aff
->ls
= isl_local_space_drop_dims(aff
->ls
, type
, first
, n
);
962 return isl_aff_free(aff
);
964 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
965 aff
->v
= isl_vec_drop_els(aff
->v
, first
, n
);
967 return isl_aff_free(aff
);
972 __isl_give isl_aff
*isl_aff_insert_dims(__isl_take isl_aff
*aff
,
973 enum isl_dim_type type
, unsigned first
, unsigned n
)
979 if (n
== 0 && !isl_local_space_is_named_or_nested(aff
->ls
, type
))
982 ctx
= isl_aff_get_ctx(aff
);
983 if (first
> isl_aff_dim(aff
, type
))
984 isl_die(ctx
, isl_error_invalid
, "position out of bounds",
985 return isl_aff_free(aff
));
987 aff
= isl_aff_cow(aff
);
991 aff
->ls
= isl_local_space_insert_dims(aff
->ls
, type
, first
, n
);
993 return isl_aff_free(aff
);
995 first
+= 1 + isl_local_space_offset(aff
->ls
, type
);
996 aff
->v
= isl_vec_insert_zero_els(aff
->v
, first
, n
);
998 return isl_aff_free(aff
);
1003 __isl_give isl_aff
*isl_aff_add_dims(__isl_take isl_aff
*aff
,
1004 enum isl_dim_type type
, unsigned n
)
1008 pos
= isl_aff_dim(aff
, type
);
1010 return isl_aff_insert_dims(aff
, type
, pos
, n
);
1013 __isl_give isl_pw_aff
*isl_pw_aff_add_dims(__isl_take isl_pw_aff
*pwaff
,
1014 enum isl_dim_type type
, unsigned n
)
1018 pos
= isl_pw_aff_dim(pwaff
, type
);
1020 return isl_pw_aff_insert_dims(pwaff
, type
, pos
, n
);
1024 #define PW isl_pw_aff
1028 #define EL_IS_ZERO is_empty
1032 #define IS_ZERO is_empty
1038 #define NO_MOVE_DIMS
1042 #include <isl_pw_templ.c>
1044 /* Compute a piecewise quasi-affine expression with a domain that
1045 * is the union of those of pwaff1 and pwaff2 and such that on each
1046 * cell, the quasi-affine expression is the maximum of those of pwaff1
1047 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1048 * cell, then the associated expression is the defined one.
1050 __isl_give isl_pw_aff
*isl_pw_aff_max(__isl_take isl_pw_aff
*pwaff1
,
1051 __isl_take isl_pw_aff
*pwaff2
)
1058 if (!pwaff1
|| !pwaff2
)
1061 ctx
= isl_dim_get_ctx(pwaff1
->dim
);
1062 if (!isl_dim_equal(pwaff1
->dim
, pwaff2
->dim
))
1063 isl_die(ctx
, isl_error_invalid
,
1064 "arguments should live in same space", goto error
);
1066 if (isl_pw_aff_is_empty(pwaff1
)) {
1067 isl_pw_aff_free(pwaff1
);
1071 if (isl_pw_aff_is_empty(pwaff2
)) {
1072 isl_pw_aff_free(pwaff2
);
1076 n
= 2 * (pwaff1
->n
+ 1) * (pwaff2
->n
+ 1);
1077 res
= isl_pw_aff_alloc_(isl_dim_copy(pwaff1
->dim
), n
);
1079 for (i
= 0; i
< pwaff1
->n
; ++i
) {
1080 set
= isl_set_copy(pwaff1
->p
[i
].set
);
1081 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1082 struct isl_set
*common
;
1085 common
= isl_set_intersect(
1086 isl_set_copy(pwaff1
->p
[i
].set
),
1087 isl_set_copy(pwaff2
->p
[j
].set
));
1088 ge
= isl_set_from_basic_set(isl_aff_ge_basic_set(
1089 isl_aff_copy(pwaff2
->p
[j
].aff
),
1090 isl_aff_copy(pwaff1
->p
[i
].aff
)));
1091 ge
= isl_set_intersect(common
, ge
);
1092 if (isl_set_plain_is_empty(ge
)) {
1096 set
= isl_set_subtract(set
, isl_set_copy(ge
));
1098 res
= isl_pw_aff_add_piece(res
, ge
,
1099 isl_aff_copy(pwaff2
->p
[j
].aff
));
1101 res
= isl_pw_aff_add_piece(res
, set
,
1102 isl_aff_copy(pwaff1
->p
[i
].aff
));
1105 for (j
= 0; j
< pwaff2
->n
; ++j
) {
1106 set
= isl_set_copy(pwaff2
->p
[j
].set
);
1107 for (i
= 0; i
< pwaff1
->n
; ++i
)
1108 set
= isl_set_subtract(set
,
1109 isl_set_copy(pwaff1
->p
[i
].set
));
1110 res
= isl_pw_aff_add_piece(res
, set
,
1111 isl_aff_copy(pwaff2
->p
[j
].aff
));
1114 isl_pw_aff_free(pwaff1
);
1115 isl_pw_aff_free(pwaff2
);
1119 isl_pw_aff_free(pwaff1
);
1120 isl_pw_aff_free(pwaff2
);
1124 /* Construct a map with as domain the domain of pwaff and
1125 * one-dimensional range corresponding to the affine expressions.
1127 __isl_give isl_map
*isl_map_from_pw_aff(__isl_take isl_pw_aff
*pwaff
)
1136 dim
= isl_pw_aff_get_dim(pwaff
);
1137 dim
= isl_dim_from_domain(dim
);
1138 dim
= isl_dim_add(dim
, isl_dim_out
, 1);
1139 map
= isl_map_empty(dim
);
1141 for (i
= 0; i
< pwaff
->n
; ++i
) {
1142 isl_basic_map
*bmap
;
1145 bmap
= isl_basic_map_from_aff(isl_aff_copy(pwaff
->p
[i
].aff
));
1146 map_i
= isl_map_from_basic_map(bmap
);
1147 map_i
= isl_map_intersect_domain(map_i
,
1148 isl_set_copy(pwaff
->p
[i
].set
));
1149 map
= isl_map_union_disjoint(map
, map_i
);
1152 isl_pw_aff_free(pwaff
);
1157 /* Return a set containing those elements in the domain
1158 * of pwaff where it is non-negative.
1160 __isl_give isl_set
*isl_pw_aff_nonneg_set(__isl_take isl_pw_aff
*pwaff
)
1168 set
= isl_set_empty(isl_pw_aff_get_dim(pwaff
));
1170 for (i
= 0; i
< pwaff
->n
; ++i
) {
1171 isl_basic_set
*bset
;
1174 bset
= isl_aff_nonneg_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
));
1175 set_i
= isl_set_from_basic_set(bset
);
1176 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
1177 set
= isl_set_union_disjoint(set
, set_i
);
1180 isl_pw_aff_free(pwaff
);
1185 /* Return a set containing those elements in the domain
1186 * of pwaff where it is zero.
1188 __isl_give isl_set
*isl_pw_aff_zero_set(__isl_take isl_pw_aff
*pwaff
)
1196 set
= isl_set_empty(isl_pw_aff_get_dim(pwaff
));
1198 for (i
= 0; i
< pwaff
->n
; ++i
) {
1199 isl_basic_set
*bset
;
1202 bset
= isl_aff_zero_basic_set(isl_aff_copy(pwaff
->p
[i
].aff
));
1203 set_i
= isl_set_from_basic_set(bset
);
1204 set_i
= isl_set_intersect(set_i
, isl_set_copy(pwaff
->p
[i
].set
));
1205 set
= isl_set_union_disjoint(set
, set_i
);
1208 isl_pw_aff_free(pwaff
);
1213 /* Return a set containing those elements in the shared domain
1214 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1216 * We compute the difference on the shared domain and then construct
1217 * the set of values where this difference is non-negative.
1218 * If strict is set, we first subtract 1 from the difference.
1219 * If equal is set, we only return the elements where pwaff1 and pwaff2
1222 static __isl_give isl_set
*pw_aff_gte_set(__isl_take isl_pw_aff
*pwaff1
,
1223 __isl_take isl_pw_aff
*pwaff2
, int strict
, int equal
)
1225 isl_set
*set1
, *set2
;
1227 set1
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff1
));
1228 set2
= isl_pw_aff_domain(isl_pw_aff_copy(pwaff2
));
1229 set1
= isl_set_intersect(set1
, set2
);
1230 pwaff1
= isl_pw_aff_intersect_domain(pwaff1
, isl_set_copy(set1
));
1231 pwaff2
= isl_pw_aff_intersect_domain(pwaff2
, isl_set_copy(set1
));
1232 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_neg(pwaff2
));
1235 isl_dim
*dim
= isl_set_get_dim(set1
);
1237 aff
= isl_aff_zero(isl_local_space_from_dim(dim
));
1238 aff
= isl_aff_add_constant_si(aff
, -1);
1239 pwaff1
= isl_pw_aff_add(pwaff1
, isl_pw_aff_alloc(set1
, aff
));
1244 return isl_pw_aff_zero_set(pwaff1
);
1245 return isl_pw_aff_nonneg_set(pwaff1
);
1248 /* Return a set containing those elements in the shared domain
1249 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1251 __isl_give isl_set
*isl_pw_aff_eq_set(__isl_take isl_pw_aff
*pwaff1
,
1252 __isl_take isl_pw_aff
*pwaff2
)
1254 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 1);
1257 /* Return a set containing those elements in the shared domain
1258 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1260 __isl_give isl_set
*isl_pw_aff_ge_set(__isl_take isl_pw_aff
*pwaff1
,
1261 __isl_take isl_pw_aff
*pwaff2
)
1263 return pw_aff_gte_set(pwaff1
, pwaff2
, 0, 0);
1266 /* Return a set containing those elements in the shared domain
1267 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1269 __isl_give isl_set
*isl_pw_aff_gt_set(__isl_take isl_pw_aff
*pwaff1
,
1270 __isl_take isl_pw_aff
*pwaff2
)
1272 return pw_aff_gte_set(pwaff1
, pwaff2
, 1, 0);
1275 __isl_give isl_set
*isl_pw_aff_le_set(__isl_take isl_pw_aff
*pwaff1
,
1276 __isl_take isl_pw_aff
*pwaff2
)
1278 return isl_pw_aff_ge_set(pwaff2
, pwaff1
);
1281 __isl_give isl_set
*isl_pw_aff_lt_set(__isl_take isl_pw_aff
*pwaff1
,
1282 __isl_take isl_pw_aff
*pwaff2
)
1284 return isl_pw_aff_gt_set(pwaff2
, pwaff1
);
1287 __isl_give isl_pw_aff
*isl_pw_aff_scale_down(__isl_take isl_pw_aff
*pwaff
,
1292 if (isl_int_is_one(v
))
1294 if (!isl_int_is_pos(v
))
1295 isl_die(isl_pw_aff_get_ctx(pwaff
), isl_error_invalid
,
1296 "factor needs to be positive",
1297 return isl_pw_aff_free(pwaff
));
1298 pwaff
= isl_pw_aff_cow(pwaff
);
1304 for (i
= 0; i
< pwaff
->n
; ++i
) {
1305 pwaff
->p
[i
].aff
= isl_aff_scale_down(pwaff
->p
[i
].aff
, v
);
1306 if (!pwaff
->p
[i
].aff
)
1307 return isl_pw_aff_free(pwaff
);
1313 __isl_give isl_pw_aff
*isl_pw_aff_floor(__isl_take isl_pw_aff
*pwaff
)
1317 pwaff
= isl_pw_aff_cow(pwaff
);
1323 for (i
= 0; i
< pwaff
->n
; ++i
) {
1324 pwaff
->p
[i
].aff
= isl_aff_floor(pwaff
->p
[i
].aff
);
1325 if (!pwaff
->p
[i
].aff
)
1326 return isl_pw_aff_free(pwaff
);
1332 __isl_give isl_pw_aff
*isl_pw_aff_ceil(__isl_take isl_pw_aff
*pwaff
)
1336 pwaff
= isl_pw_aff_cow(pwaff
);
1342 for (i
= 0; i
< pwaff
->n
; ++i
) {
1343 pwaff
->p
[i
].aff
= isl_aff_ceil(pwaff
->p
[i
].aff
);
1344 if (!pwaff
->p
[i
].aff
)
1345 return isl_pw_aff_free(pwaff
);
1351 /* Return an affine expression that is equal to pwaff_true for elements
1352 * in "cond" and to pwaff_false for elements not in "cond".
1353 * That is, return cond ? pwaff_true : pwaff_false;
1355 __isl_give isl_pw_aff
*isl_pw_aff_cond(__isl_take isl_set
*cond
,
1356 __isl_take isl_pw_aff
*pwaff_true
, __isl_take isl_pw_aff
*pwaff_false
)
1360 comp
= isl_set_complement(isl_set_copy(cond
));
1361 pwaff_true
= isl_pw_aff_intersect_domain(pwaff_true
, cond
);
1362 pwaff_false
= isl_pw_aff_intersect_domain(pwaff_false
, comp
);
1364 return isl_pw_aff_add_disjoint(pwaff_true
, pwaff_false
);