4 #include <cloog/isl/cloog.h>
5 #include <cloog/isl/backend.h>
10 #define ALLOC(type) (type*)malloc(sizeof(type))
11 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
13 CloogConstraintSet
*cloog_constraint_set_from_isl_basic_set(struct isl_basic_set
*bset
)
15 return (CloogConstraintSet
*)bset
;
18 CloogConstraint
*cloog_constraint_from_isl_constraint(struct isl_constraint
*constraint
)
20 return (CloogConstraint
*)constraint
;
23 isl_basic_set
*cloog_constraints_set_to_isl(CloogConstraintSet
*constraints
)
25 return (isl_basic_set
*)constraints
;
29 /******************************************************************************
30 * Memory leaks hunting *
31 ******************************************************************************/
35 void cloog_constraint_set_free(CloogConstraintSet
*constraints
)
37 isl_basic_set_free(cloog_constraints_set_to_isl(constraints
));
41 int cloog_constraint_set_contains_level(CloogConstraintSet
*constraints
,
42 int level
, int nb_parameters
)
45 bset
= cloog_constraints_set_to_isl(constraints
);
46 return isl_basic_set_dim(bset
, isl_dim_set
) >= level
;
49 struct cloog_isl_dim
{
50 enum isl_dim_type type
;
54 static struct cloog_isl_dim
basic_set_cloog_dim_to_isl_dim(
55 __isl_keep isl_basic_set
*bset
, int pos
)
57 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
59 struct cloog_isl_dim ci_dim
;
61 for (i
= 0; i
< 3; ++i
) {
62 unsigned dim
= isl_basic_set_dim(bset
, types
[i
]);
64 ci_dim
.type
= types
[i
];
73 static struct cloog_isl_dim
set_cloog_dim_to_isl_dim(
74 CloogConstraintSet
*constraints
, int pos
)
78 bset
= cloog_constraints_set_to_isl(constraints
);
79 return basic_set_cloog_dim_to_isl_dim(bset
, pos
);
82 /* Check if the variable at position level is defined by an
83 * equality. If so, return the row number. Otherwise, return -1.
85 CloogConstraint
*cloog_constraint_set_defining_equality(
86 CloogConstraintSet
*constraints
, int level
)
88 struct isl_constraint
*c
;
89 struct cloog_isl_dim dim
;
92 bset
= cloog_constraints_set_to_isl(constraints
);
93 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
94 if (isl_basic_set_has_defining_equality(bset
, dim
.type
, dim
.pos
, &c
))
95 return cloog_constraint_from_isl_constraint(c
);
101 /* Check if the variable (e) at position level is defined by a
102 * pair of inequalities
103 * <a, i> + -m e + <b, p> + k1 >= 0
104 * <-a, i> + m e + <-b, p> + k2 >= 0
105 * with 0 <= k1 + k2 < m
106 * If so return the row number of the upper bound and set *lower
107 * to the row number of the lower bound. If not, return -1.
109 * If the variable at position level occurs in any other constraint,
110 * then we currently return -1. The modulo guard that we would generate
111 * would still be correct, but we would also need to generate
112 * guards corresponding to the other constraints, and this has not
113 * been implemented yet.
115 CloogConstraint
*cloog_constraint_set_defining_inequalities(
116 CloogConstraintSet
*constraints
,
117 int level
, CloogConstraint
**lower
, int nb_par
)
119 struct isl_constraint
*u
;
120 struct isl_constraint
*l
;
121 struct isl_constraint
*c
;
122 struct cloog_isl_dim dim
;
123 struct isl_basic_set
*bset
;
125 bset
= cloog_constraints_set_to_isl(constraints
);
126 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
127 if (!isl_basic_set_has_defining_inequalities(bset
, dim
.type
, dim
.pos
,
129 return cloog_constraint_invalid();
130 for (c
= isl_basic_set_first_constraint(isl_basic_set_copy(bset
)); c
;
131 c
= isl_constraint_next(c
)) {
132 if (isl_constraint_is_equal(c
, l
))
134 if (isl_constraint_is_equal(c
, u
))
136 *lower
= cloog_constraint_from_isl_constraint(c
);
137 if (cloog_constraint_involves(*lower
, level
-1)) {
138 isl_constraint_free(l
);
139 isl_constraint_free(u
);
141 isl_constraint_free(c
);
145 *lower
= cloog_constraint_from_isl_constraint(l
);
146 return cloog_constraint_from_isl_constraint(u
);
149 int cloog_constraint_set_total_dimension(CloogConstraintSet
*constraints
)
152 bset
= cloog_constraints_set_to_isl(constraints
);
153 return isl_basic_set_total_dim(bset
);
156 int cloog_constraint_set_n_iterators(CloogConstraintSet
*constraints
, int n_par
)
159 bset
= cloog_constraints_set_to_isl(constraints
);
160 return isl_basic_set_dim(bset
, isl_dim_set
);
164 /******************************************************************************
165 * Equalities spreading functions *
166 ******************************************************************************/
169 /* Equalities are stored inside a Matrix data structure called "equal".
170 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
171 * dimensions + 1, the "+ 1" is because a statement can be included inside an
172 * external loop without iteration domain), and (nb_scattering + nb_iterators +
173 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
174 * type). The ith row corresponds to the equality "= 0" for the ith dimension
175 * iterator. The first column gives the equality type (0: no equality, then
176 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
177 * the current level is found, the corresponding row is updated. Then the
178 * equality if it exists is used to simplify expressions (e.g. if we have
179 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
180 * the pprint call, the corresponding row is reset to zero.
183 CloogEqualities
*cloog_equal_alloc(int n
, int nb_levels
, int nb_parameters
)
186 CloogEqualities
*equal
= ALLOC(CloogEqualities
);
188 equal
->total_dim
= nb_levels
- 1 + nb_parameters
;
190 equal
->constraints
= ALLOCN(CloogConstraintSet
*, n
);
191 equal
->types
= ALLOCN(int, n
);
192 for (i
= 0; i
< n
; ++i
) {
193 equal
->constraints
[i
] = NULL
;
194 equal
->types
[i
] = EQTYPE_NONE
;
199 int cloog_equal_total_dimension(CloogEqualities
*equal
)
201 return equal
->total_dim
;
204 void cloog_equal_free(CloogEqualities
*equal
)
209 for (i
= 0; i
< equal
->n
; ++i
) {
210 bset
= cloog_constraints_set_to_isl(equal
->constraints
[i
]);
211 isl_basic_set_free(bset
);
213 free(equal
->constraints
);
218 int cloog_equal_count(CloogEqualities
*equal
)
225 * cloog_constraint_equal_type function :
226 * This function returns the type of the equality in the constraint (line) of
227 * (constraints) for the element (level). An equality is 'constant' iff all
228 * other factors are null except the constant one. It is a 'pure item' iff
229 * it is equal or opposite to a single variable or parameter.
230 * Otherwise it is an 'affine expression'.
232 * i = -13 is constant, i = j, j = -M are pure items,
233 * j = 2*M, i = j+1, 2*j = M are affine expressions.
235 * - constraints is the matrix of constraints,
236 * - level is the column number in equal of the element which is 'equal to',
238 static int cloog_constraint_equal_type(CloogConstraint
*cc
, int level
)
242 int type
= EQTYPE_NONE
;
243 struct isl_constraint
*constraint
= &cc
->isl
;
246 isl_constraint_get_constant(constraint
, &c
);
247 if (!isl_int_is_zero(c
))
248 type
= EQTYPE_CONSTANT
;
249 isl_constraint_get_coefficient(constraint
, isl_dim_set
, level
- 1, &c
);
250 if (!isl_int_is_one(c
) && !isl_int_is_negone(c
))
251 type
= EQTYPE_EXAFFINE
;
252 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_param
); ++i
) {
253 isl_constraint_get_coefficient(constraint
, isl_dim_param
, i
, &c
);
254 if (isl_int_is_zero(c
))
256 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
257 type
!= EQTYPE_NONE
) {
258 type
= EQTYPE_EXAFFINE
;
261 type
= EQTYPE_PUREITEM
;
263 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_set
); ++i
) {
266 isl_constraint_get_coefficient(constraint
, isl_dim_set
, i
, &c
);
267 if (isl_int_is_zero(c
))
269 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
270 type
!= EQTYPE_NONE
) {
271 type
= EQTYPE_EXAFFINE
;
274 type
= EQTYPE_PUREITEM
;
276 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_div
); ++i
) {
277 isl_constraint_get_coefficient(constraint
, isl_dim_div
, i
, &c
);
278 if (isl_int_is_zero(c
))
280 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
281 type
!= EQTYPE_NONE
) {
282 type
= EQTYPE_EXAFFINE
;
285 type
= EQTYPE_PUREITEM
;
289 if (type
== EQTYPE_NONE
)
290 type
= EQTYPE_CONSTANT
;
296 int cloog_equal_type(CloogEqualities
*equal
, int level
)
298 return equal
->types
[level
-1];
303 * cloog_equal_add function:
304 * This function updates the row (level-1) of the equality matrix (equal) with
305 * the row that corresponds to the row (line) of the matrix (matrix).
306 * - equal is the matrix of equalities,
307 * - matrix is the matrix of constraints,
308 * - level is the column number in matrix of the element which is 'equal to',
309 * - line is the line number in matrix of the constraint we want to study,
310 * - the infos structure gives the user all options on code printing and more.
312 * line is set to an invalid constraint for equalities that CLooG itself has
313 * discovered because the lower and upper bound of a loop happened to be equal.
314 * This situation shouldn't happen in the isl port since isl should
315 * have found the equality itself.
317 void cloog_equal_add(CloogEqualities
*equal
, CloogConstraintSet
*matrix
,
318 int level
, CloogConstraint
*line
, int nb_par
)
320 struct isl_basic_set
*bset
;
322 assert(cloog_constraint_is_valid(line
));
324 equal
->types
[level
-1] = cloog_constraint_equal_type(line
, level
);
325 bset
= isl_basic_set_from_constraint(isl_constraint_copy(&line
->isl
));
326 nparam
= isl_basic_set_n_param(bset
);
327 bset
= isl_basic_set_extend(bset
, nparam
,
328 equal
->total_dim
- nparam
, 0, 0, 0);
329 bset
= isl_basic_set_finalize(bset
);
330 equal
->constraints
[level
-1] =
331 cloog_constraint_set_from_isl_basic_set(bset
);
336 * cloog_equal_del function :
337 * This function reset the equality corresponding to the iterator (level)
338 * in the equality matrix (equal).
339 * - July 2nd 2002: first version.
341 void cloog_equal_del(CloogEqualities
*equal
, int level
)
344 bset
= cloog_constraints_set_to_isl(equal
->constraints
[level
- 1]);
345 equal
->types
[level
-1] = EQTYPE_NONE
;
346 isl_basic_set_free(bset
);
347 equal
->constraints
[level
-1] = NULL
;
352 /******************************************************************************
353 * Processing functions *
354 ******************************************************************************/
357 * Function cloog_constraint_set_normalize:
358 * This function will modify the constraint system in such a way that when
359 * there is an equality depending on the element at level 'level', there are
360 * no more (in)equalities depending on this element.
362 * The simplified form of isl automatically satisfies this condition.
364 void cloog_constraint_set_normalize(CloogConstraintSet
*matrix
, int level
)
371 * cloog_constraint_set_copy function:
372 * this functions builds and returns a "hard copy" (not a pointer copy) of a
373 * CloogConstraintSet data structure.
375 CloogConstraintSet
*cloog_constraint_set_copy(CloogConstraintSet
*constraints
)
378 bset
= cloog_constraints_set_to_isl(constraints
);
379 return cloog_constraint_set_from_isl_basic_set(isl_basic_set_dup(bset
));
384 * cloog_constraint_set_simplify function:
385 * this function simplify all constraints inside the matrix "matrix" thanks to
386 * an equality matrix "equal" that gives for some elements of the affine
387 * constraint an equality with other elements, preferably constants.
388 * For instance, if a row of the matrix contains i+j+3>=0 and the equality
389 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
390 * simplified constraints are returned back inside a new simplified matrix.
391 * - matrix is the set of constraints to simplify,
392 * - equal is the matrix of equalities,
393 * - level is a level we don't want to simplify (-1 if none),
394 * - nb_par is the number of parameters of the program.
396 * isl should have performed these simplifications already in isl_set_gist.
398 CloogConstraintSet
*cloog_constraint_set_simplify(CloogConstraintSet
*matrix
,
399 CloogEqualities
*equal
, int level
, int nb_par
)
401 return cloog_constraint_set_copy(matrix
);
405 static struct cloog_isl_dim
constraint_cloog_dim_to_isl_dim(
406 CloogConstraint
*constraint
, int pos
)
408 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
410 struct cloog_isl_dim ci_dim
;
412 for (i
= 0; i
< 3; ++i
) {
413 unsigned dim
= isl_constraint_dim(&constraint
->isl
, types
[i
]);
415 ci_dim
.type
= types
[i
];
424 static struct clast_expr
*div_expr(CloogConstraint
*constraint
, int pos
,
428 unsigned dim
= cloog_constraint_total_dimension(constraint
);
430 struct clast_reduction
*r
;
431 struct clast_expr
*e
= NULL
;
434 div
= isl_constraint_div(&constraint
->isl
, pos
);
437 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
438 struct cloog_isl_dim dim
;
440 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
441 isl_div_get_coefficient(div
, dim
.type
, dim
.pos
, &c
);
442 if (!cloog_int_is_zero(c
))
445 isl_div_get_constant(div
, &c
);
446 if (!cloog_int_is_zero(c
))
449 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
450 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
451 struct clast_expr
*v
;
452 struct cloog_isl_dim dim
;
454 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
455 isl_div_get_coefficient(div
, dim
.type
, dim
.pos
, &c
);
456 if (cloog_int_is_zero(c
))
459 v
= cloog_constraint_variable_expr(constraint
, 1 + i
, names
);
461 r
->elts
[nb_elts
++] = &new_clast_term(c
, v
)->expr
;
463 isl_div_get_constant(div
, &c
);
464 if (!cloog_int_is_zero(c
))
465 r
->elts
[nb_elts
++] = &new_clast_term(c
, NULL
)->expr
;
467 isl_div_get_denominator(div
, &c
);
468 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, c
)->expr
;
478 * Return clast_expr corresponding to the variable "level" (1 based) in
479 * the given constraint.
481 struct clast_expr
*cloog_constraint_variable_expr(CloogConstraint
*constraint
,
482 int level
, CloogNames
*names
)
484 struct cloog_isl_dim dim
;
489 dim
= constraint_cloog_dim_to_isl_dim(constraint
, level
- 1);
490 if (dim
.type
== isl_dim_div
)
491 return div_expr(constraint
, dim
.pos
, names
);
493 if (dim
.type
== isl_dim_set
)
494 name
= cloog_names_name_at_level(names
, level
);
496 name
= names
->parameters
[dim
.pos
];
498 return &new_clast_name(name
)->expr
;
503 * Return true if constraint c involves variable v (zero-based).
505 int cloog_constraint_involves(CloogConstraint
*constraint
, int v
)
511 cloog_constraint_coefficient_get(constraint
, v
, &c
);
512 res
= !isl_int_is_zero(c
);
517 int cloog_constraint_is_lower_bound(CloogConstraint
*constraint
, int v
)
523 cloog_constraint_coefficient_get(constraint
, v
, &c
);
524 res
= isl_int_is_pos(c
);
529 int cloog_constraint_is_upper_bound(CloogConstraint
*constraint
, int v
)
535 cloog_constraint_coefficient_get(constraint
, v
, &c
);
536 res
= isl_int_is_neg(c
);
541 int cloog_constraint_is_equality(CloogConstraint
*constraint
)
543 return isl_constraint_is_equality(&constraint
->isl
);
546 void cloog_constraint_clear(CloogConstraint
*constraint
)
548 isl_constraint_clear(&constraint
->isl
);
551 void cloog_constraint_coefficient_get(CloogConstraint
*constraint
,
552 int var
, cloog_int_t
*val
)
554 struct cloog_isl_dim dim
;
559 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
560 isl_constraint_get_coefficient(&constraint
->isl
, dim
.type
, dim
.pos
, val
);
563 void cloog_constraint_coefficient_set(CloogConstraint
*constraint
,
564 int var
, cloog_int_t val
)
566 struct cloog_isl_dim dim
;
570 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
571 isl_constraint_set_coefficient(&constraint
->isl
, dim
.type
, dim
.pos
, val
);
574 void cloog_constraint_constant_get(CloogConstraint
*constraint
, cloog_int_t
*val
)
576 isl_constraint_get_constant(&constraint
->isl
, val
);
580 * Copy the coefficient of constraint c into dst in PolyLib order,
581 * i.e., first the coefficients of the variables, then the coefficients
582 * of the parameters and finally the constant.
584 void cloog_constraint_copy_coefficients(CloogConstraint
*constraint
,
590 dim
= isl_constraint_dim(&constraint
->isl
, isl_dim_all
);
592 for (i
= 0; i
< dim
; ++i
)
593 cloog_constraint_coefficient_get(constraint
, i
, dst
+i
);
594 cloog_constraint_constant_get(constraint
, dst
+dim
);
597 CloogConstraint
*cloog_constraint_invalid(void)
602 int cloog_constraint_is_valid(CloogConstraint
*constraint
)
604 return constraint
!= NULL
;
607 int cloog_constraint_total_dimension(CloogConstraint
*constraint
)
609 return isl_constraint_dim(&constraint
->isl
, isl_dim_all
);
614 * Check whether there is any need for the constraint "upper" on
615 * "level" to get reduced.
616 * In case of the isl backend, there should be no need to do so
617 * if the level corresponds to an existentially quantified variable.
618 * Moreover, the way reduction is performed does not work for such
619 * variables since its position might chance during the construction
620 * of a set for reduction.
622 int cloog_constraint_needs_reduction(CloogConstraint
*upper
, int level
)
625 struct cloog_isl_dim dim
;
627 bset
= isl_basic_set_from_constraint(isl_constraint_copy(&upper
->isl
));
628 dim
= basic_set_cloog_dim_to_isl_dim(bset
, level
- 1);
629 isl_basic_set_free(bset
);
631 return dim
.type
== isl_dim_set
;
636 * Create a CloogConstraintSet containing enough information to perform
637 * a reduction on the upper equality (in this case lower is an invalid
638 * CloogConstraint) or the pair of inequalities upper and lower
639 * from within insert_modulo_guard.
640 * In the isl backend, we return a CloogConstraintSet containing both
641 * bounds, as the stride may change during the reduction and we may
642 * need to recompute the bound on the modulo expression.
644 CloogConstraintSet
*cloog_constraint_set_for_reduction(CloogConstraint
*upper
,
645 CloogConstraint
*lower
)
647 struct isl_basic_set
*bset
;
649 bset
= isl_basic_set_from_constraint(isl_constraint_copy(&upper
->isl
));
650 if (cloog_constraint_is_valid(lower
))
651 bset
= isl_basic_set_add_constraint(bset
,
652 isl_constraint_copy(&lower
->isl
));
653 return cloog_constraint_set_from_isl_basic_set(bset
);
657 static int add_constant_term(CloogConstraint
*c
, void *user
)
659 isl_int
*bound
= (isl_int
*)user
;
664 cloog_constraint_constant_get(c
, &v
);
665 isl_int_add(*bound
, *bound
, v
);
673 * Reduce the modulo guard expressed by "constraints" using equalities
674 * found in outer nesting levels (stored in "equal").
675 * The modulo guard may be an equality or a pair of inequalities.
676 * In case of a pair of inequalities, *bound contains the bound on the
677 * corresponding modulo expression. If any reduction is performed
678 * then this bound is recomputed.
680 * "level" may not correspond to an existentially quantified variable.
682 * We first check if there are any equalities we can use. If not,
683 * there is again nothing to reduce.
684 * For the actual reduction, we use isl_basic_set_gist, but this
685 * function will only perform the reduction we want here if the
686 * the variable that imposes the modulo constraint has been projected
687 * out (i.e., turned into an existentially quantified variable).
688 * After the call to isl_basic_set_gist, we need to move the
689 * existential variable back into the position where the calling
690 * function expects it (assuming there are any constraints left).
691 * We do this by adding an equality between the given dimension and
692 * the existentially quantified variable.
694 * If there are no existentially quantified variables left, then
695 * we don't need to add this equality.
696 * If, on the other hand, the resulting basic set involves more
697 * than one existentially quantified variable, then the caller
698 * will not be able to handle the result, so we just return the
699 * original input instead.
701 CloogConstraintSet
*cloog_constraint_set_reduce(CloogConstraintSet
*constraints
,
702 int level
, CloogEqualities
*equal
, int nb_par
, cloog_int_t
*bound
)
707 struct isl_basic_set
*eq
;
708 struct isl_basic_map
*id
;
709 struct cloog_isl_dim dim
;
710 struct isl_constraint
*c
;
712 unsigned constraints_dim
;
715 isl_basic_set
*bset
, *orig
;
717 bset
= cloog_constraints_set_to_isl(constraints
);
718 orig
= isl_basic_set_copy(bset
);
719 ctx
= isl_basic_set_get_ctx(bset
);
720 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
721 assert(dim
.type
== isl_dim_set
);
724 for (j
= 0; j
< level
- 1; ++j
) {
725 isl_basic_set
*bset_j
;
726 if (equal
->types
[j
] != EQTYPE_EXAFFINE
)
728 bset_j
= cloog_constraints_set_to_isl(equal
->constraints
[j
]);
730 eq
= isl_basic_set_copy(bset_j
);
732 eq
= isl_basic_set_intersect(eq
,
733 isl_basic_set_copy(bset_j
));
736 isl_basic_set_free(orig
);
737 return cloog_constraint_set_from_isl_basic_set(bset
);
740 idim
= isl_dim_map_from_set(isl_basic_set_get_dim(bset
));
741 id
= isl_basic_map_identity(idim
);
742 id
= isl_basic_map_remove_dims(id
, isl_dim_out
, dim
.pos
, 1);
743 bset
= isl_basic_set_apply(bset
, isl_basic_map_copy(id
));
744 bset
= isl_basic_set_apply(bset
, isl_basic_map_reverse(id
));
746 constraints_dim
= isl_basic_set_dim(bset
, isl_dim_set
);
747 eq
= isl_basic_set_remove_dims(eq
, isl_dim_set
, constraints_dim
,
748 isl_basic_set_dim(eq
, isl_dim_set
) - constraints_dim
);
749 bset
= isl_basic_set_gist(bset
, eq
);
750 n_div
= isl_basic_set_dim(bset
, isl_dim_div
);
752 isl_basic_set_free(bset
);
753 return cloog_constraint_set_from_isl_basic_set(orig
);
756 isl_basic_set_free(orig
);
757 return cloog_constraint_set_from_isl_basic_set(bset
);
760 div
= isl_basic_set_div(isl_basic_set_copy(bset
), 0);
761 c
= isl_equality_alloc(isl_basic_set_get_dim(bset
));
762 c
= isl_constraint_add_div(c
, div
, &pos
);
763 isl_constraint_set_coefficient_si(c
, isl_dim_set
, dim
.pos
, 1);
764 isl_constraint_set_coefficient_si(c
, isl_dim_div
, pos
, -1);
765 bset
= isl_basic_set_add_constraint(bset
, c
);
767 isl_int_set_si(*bound
, 0);
768 constraints
= cloog_constraint_set_from_isl_basic_set(bset
);
769 cloog_constraint_set_foreach_constraint(constraints
,
770 add_constant_term
, bound
);
772 isl_basic_set_free(orig
);
773 return cloog_constraint_set_from_isl_basic_set(bset
);
776 CloogConstraint
*cloog_constraint_copy(CloogConstraint
*constraint
)
778 return cloog_constraint_from_isl_constraint(
779 isl_constraint_copy(&constraint
->isl
));
782 void cloog_constraint_release(CloogConstraint
*constraint
)
784 isl_constraint_free(&constraint
->isl
);
787 struct cloog_isl_foreach
{
788 int (*fn
)(CloogConstraint
*constraint
, void *user
);
792 static int cloog_isl_foreach_cb(__isl_take isl_constraint
*c
, void *user
)
794 struct cloog_isl_foreach
*data
= (struct cloog_isl_foreach
*)user
;
797 if (isl_constraint_is_div_constraint(c
)) {
798 isl_constraint_free(c
);
802 ret
= data
->fn(cloog_constraint_from_isl_constraint(c
), data
->user
);
804 isl_constraint_free(c
);
809 int cloog_constraint_set_foreach_constraint(CloogConstraintSet
*constraints
,
810 int (*fn
)(CloogConstraint
*constraint
, void *user
), void *user
)
812 struct cloog_isl_foreach data
= { fn
, user
};
815 bset
= cloog_constraints_set_to_isl(constraints
);
816 return isl_basic_set_foreach_constraint(bset
,
817 cloog_isl_foreach_cb
, &data
);
820 CloogConstraint
*cloog_equal_constraint(CloogEqualities
*equal
, int j
)
823 bset
= cloog_constraints_set_to_isl(equal
->constraints
[j
]);
824 return cloog_constraint_from_isl_constraint(
825 isl_basic_set_first_constraint(isl_basic_set_copy(bset
)));
828 /* Given a stride constraint on iterator i (specified by level) of the form
830 * i = f(outer iterators) + stride * f(existentials)
832 * extract f as an isl_aff.
834 static isl_aff
*extract_stride_offset(__isl_keep isl_constraint
*c
,
835 int level
, CloogStride
*stride
)
838 isl_dim
*dim
= isl_constraint_get_dim(c
);
839 isl_local_space
*ls
= isl_local_space_from_dim(dim
);
840 isl_aff
*offset
= isl_aff_zero(ls
);
842 unsigned nparam
, nvar
;
846 nparam
= isl_constraint_dim(c
, isl_dim_param
);
847 nvar
= isl_constraint_dim(c
, isl_dim_set
);
849 for (i
= 0; i
< nparam
; ++i
) {
850 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &u
);
851 isl_int_mul(u
, u
, stride
->factor
);
852 offset
= isl_aff_set_coefficient(offset
, isl_dim_param
, i
, u
);
854 for (i
= 0; i
< nvar
; ++i
) {
857 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &u
);
858 isl_int_mul(u
, u
, stride
->factor
);
859 offset
= isl_aff_set_coefficient(offset
, isl_dim_set
, i
, u
);
861 isl_constraint_get_constant(c
, &u
);
862 isl_int_mul(u
, u
, stride
->factor
);
863 offset
= isl_aff_set_constant(offset
, u
);
870 /* Update the given lower bound on level such that it satisfies the stride
871 * constraint. The computation performed here is essentially the same
872 * as that performed in constraint_stride_lower_c.
874 * We update the constraint
880 * i >= s * ceil((-f/a - d)/s) + d
882 * with s the stride and d the offset encoded in the stride constraint.
884 CloogConstraint
*cloog_constraint_stride_lower_bound(CloogConstraint
*c
,
885 int level
, CloogStride
*stride
)
887 isl_constraint
*stride_c
= &stride
->constraint
->isl
;
888 isl_constraint
*bound
= &c
->isl
;
892 lower
= isl_constraint_get_bound(bound
, isl_dim_set
, level
- 1);
893 isl_constraint_free(bound
);
895 offset
= extract_stride_offset(stride_c
, level
, stride
);
897 lower
= isl_aff_sub(lower
, isl_aff_copy(offset
));
898 lower
= isl_aff_scale_down(lower
, stride
->stride
);
899 lower
= isl_aff_ceil(lower
);
900 lower
= isl_aff_scale(lower
, stride
->stride
);
901 lower
= isl_aff_add(lower
, offset
);
902 lower
= isl_aff_neg(lower
);
903 lower
= isl_aff_add_coefficient_si(lower
, isl_dim_set
, level
- 1, 1);
905 bound
= isl_inequality_from_aff(lower
);
907 return cloog_constraint_from_isl_constraint(bound
);