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_constraint
*cloog_constraint_to_isl(CloogConstraint
*constraint
)
25 return (isl_constraint
*)constraint
;
28 isl_basic_set
*cloog_constraints_set_to_isl(CloogConstraintSet
*constraints
)
30 return (isl_basic_set
*)constraints
;
34 /******************************************************************************
35 * Memory leaks hunting *
36 ******************************************************************************/
40 void cloog_constraint_set_free(CloogConstraintSet
*constraints
)
42 isl_basic_set_free(cloog_constraints_set_to_isl(constraints
));
46 int cloog_constraint_set_contains_level(CloogConstraintSet
*constraints
,
47 int level
, int nb_parameters
)
50 bset
= cloog_constraints_set_to_isl(constraints
);
51 return isl_basic_set_dim(bset
, isl_dim_set
) >= level
;
54 struct cloog_isl_dim
{
55 enum isl_dim_type type
;
59 static struct cloog_isl_dim
basic_set_cloog_dim_to_isl_dim(
60 __isl_keep isl_basic_set
*bset
, int pos
)
62 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
64 struct cloog_isl_dim ci_dim
;
66 for (i
= 0; i
< 3; ++i
) {
67 unsigned dim
= isl_basic_set_dim(bset
, types
[i
]);
69 ci_dim
.type
= types
[i
];
78 static struct cloog_isl_dim
set_cloog_dim_to_isl_dim(
79 CloogConstraintSet
*constraints
, int pos
)
83 bset
= cloog_constraints_set_to_isl(constraints
);
84 return basic_set_cloog_dim_to_isl_dim(bset
, pos
);
87 /* Check if the variable at position level is defined by an
88 * equality. If so, return the row number. Otherwise, return -1.
90 CloogConstraint
*cloog_constraint_set_defining_equality(
91 CloogConstraintSet
*constraints
, int level
)
93 struct isl_constraint
*c
;
94 struct cloog_isl_dim dim
;
97 bset
= cloog_constraints_set_to_isl(constraints
);
98 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
99 if (isl_basic_set_has_defining_equality(bset
, dim
.type
, dim
.pos
, &c
))
100 return cloog_constraint_from_isl_constraint(c
);
106 struct cloog_isl_other
{
114 /* Set other->found to 1 if the given constraint involves other->level
115 * and is different from other->u and other->l.
117 static int check_other_constraint(__isl_take isl_constraint
*c
, void *user
)
119 struct cloog_isl_other
*other
= user
;
122 if (!isl_constraint_is_equal(c
, other
->l
) &&
123 !isl_constraint_is_equal(c
, other
->u
)) {
124 cc
= cloog_constraint_from_isl_constraint(c
);
125 if (cloog_constraint_involves(cc
, other
->level
- 1))
129 isl_constraint_free(c
);
131 return other
->found
? -1 : 0;
135 /* Check if the variable (e) at position level is defined by a
136 * pair of inequalities
137 * <a, i> + -m e + <b, p> + k1 >= 0
138 * <-a, i> + m e + <-b, p> + k2 >= 0
139 * with 0 <= k1 + k2 < m
140 * If so return the row number of the upper bound and set *lower
141 * to the row number of the lower bound. If not, return -1.
143 * If the variable at position level occurs in any other constraint,
144 * then we currently return -1. The modulo guard that we would generate
145 * would still be correct, but we would also need to generate
146 * guards corresponding to the other constraints, and this has not
147 * been implemented yet.
149 CloogConstraint
*cloog_constraint_set_defining_inequalities(
150 CloogConstraintSet
*constraints
,
151 int level
, CloogConstraint
**lower
, int nb_par
)
153 struct isl_constraint
*u
;
154 struct isl_constraint
*l
;
155 struct cloog_isl_dim dim
;
156 struct isl_basic_set
*bset
;
157 struct cloog_isl_other other
;
159 bset
= cloog_constraints_set_to_isl(constraints
);
160 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
161 if (!isl_basic_set_has_defining_inequalities(bset
, dim
.type
, dim
.pos
,
163 return cloog_constraint_invalid();
169 isl_basic_set_foreach_constraint(bset
, &check_other_constraint
, &other
);
171 isl_constraint_free(l
);
172 isl_constraint_free(u
);
176 *lower
= cloog_constraint_from_isl_constraint(l
);
177 return cloog_constraint_from_isl_constraint(u
);
180 int cloog_constraint_set_total_dimension(CloogConstraintSet
*constraints
)
183 bset
= cloog_constraints_set_to_isl(constraints
);
184 return isl_basic_set_total_dim(bset
);
187 int cloog_constraint_set_n_iterators(CloogConstraintSet
*constraints
, int n_par
)
190 bset
= cloog_constraints_set_to_isl(constraints
);
191 return isl_basic_set_dim(bset
, isl_dim_set
);
195 /******************************************************************************
196 * Equalities spreading functions *
197 ******************************************************************************/
200 /* Equalities are stored inside a Matrix data structure called "equal".
201 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
202 * dimensions + 1, the "+ 1" is because a statement can be included inside an
203 * external loop without iteration domain), and (nb_scattering + nb_iterators +
204 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
205 * type). The ith row corresponds to the equality "= 0" for the ith dimension
206 * iterator. The first column gives the equality type (0: no equality, then
207 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
208 * the current level is found, the corresponding row is updated. Then the
209 * equality if it exists is used to simplify expressions (e.g. if we have
210 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
211 * the pprint call, the corresponding row is reset to zero.
214 CloogEqualities
*cloog_equal_alloc(int n
, int nb_levels
, int nb_parameters
)
217 CloogEqualities
*equal
= ALLOC(CloogEqualities
);
219 equal
->total_dim
= nb_levels
- 1 + nb_parameters
;
221 equal
->constraints
= ALLOCN(isl_constraint
*, n
);
222 equal
->types
= ALLOCN(int, n
);
223 for (i
= 0; i
< n
; ++i
) {
224 equal
->constraints
[i
] = NULL
;
225 equal
->types
[i
] = EQTYPE_NONE
;
230 int cloog_equal_total_dimension(CloogEqualities
*equal
)
232 return equal
->total_dim
;
235 void cloog_equal_free(CloogEqualities
*equal
)
239 for (i
= 0; i
< equal
->n
; ++i
)
240 isl_constraint_free(equal
->constraints
[i
]);
241 free(equal
->constraints
);
246 int cloog_equal_count(CloogEqualities
*equal
)
253 * cloog_constraint_equal_type function :
254 * This function returns the type of the equality in the constraint (line) of
255 * (constraints) for the element (level). An equality is 'constant' iff all
256 * other factors are null except the constant one. It is a 'pure item' iff
257 * it is equal or opposite to a single variable or parameter.
258 * Otherwise it is an 'affine expression'.
260 * i = -13 is constant, i = j, j = -M are pure items,
261 * j = 2*M, i = j+1, 2*j = M are affine expressions.
263 * - constraints is the matrix of constraints,
264 * - level is the column number in equal of the element which is 'equal to',
266 static int cloog_constraint_equal_type(CloogConstraint
*cc
, int level
)
270 int type
= EQTYPE_NONE
;
271 struct isl_constraint
*constraint
= cloog_constraint_to_isl(cc
);
274 isl_constraint_get_constant(constraint
, &c
);
275 if (!isl_int_is_zero(c
))
276 type
= EQTYPE_CONSTANT
;
277 isl_constraint_get_coefficient(constraint
, isl_dim_set
, level
- 1, &c
);
278 if (!isl_int_is_one(c
) && !isl_int_is_negone(c
))
279 type
= EQTYPE_EXAFFINE
;
280 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_param
); ++i
) {
281 isl_constraint_get_coefficient(constraint
, isl_dim_param
, i
, &c
);
282 if (isl_int_is_zero(c
))
284 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
285 type
!= EQTYPE_NONE
) {
286 type
= EQTYPE_EXAFFINE
;
289 type
= EQTYPE_PUREITEM
;
291 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_set
); ++i
) {
294 isl_constraint_get_coefficient(constraint
, isl_dim_set
, i
, &c
);
295 if (isl_int_is_zero(c
))
297 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
298 type
!= EQTYPE_NONE
) {
299 type
= EQTYPE_EXAFFINE
;
302 type
= EQTYPE_PUREITEM
;
304 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_div
); ++i
) {
305 isl_constraint_get_coefficient(constraint
, isl_dim_div
, i
, &c
);
306 if (isl_int_is_zero(c
))
308 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
309 type
!= EQTYPE_NONE
) {
310 type
= EQTYPE_EXAFFINE
;
313 type
= EQTYPE_PUREITEM
;
317 if (type
== EQTYPE_NONE
)
318 type
= EQTYPE_CONSTANT
;
324 int cloog_equal_type(CloogEqualities
*equal
, int level
)
326 return equal
->types
[level
-1];
331 * cloog_equal_add function:
332 * This function updates the row (level-1) of the equality matrix (equal) with
333 * the row that corresponds to the row (line) of the matrix (matrix).
334 * - equal is the matrix of equalities,
335 * - matrix is the matrix of constraints,
336 * - level is the column number in matrix of the element which is 'equal to',
337 * - line is the line number in matrix of the constraint we want to study,
338 * - the infos structure gives the user all options on code printing and more.
340 * line is set to an invalid constraint for equalities that CLooG itself has
341 * discovered because the lower and upper bound of a loop happened to be equal.
342 * This situation shouldn't happen in the isl port since isl should
343 * have found the equality itself.
345 void cloog_equal_add(CloogEqualities
*equal
, CloogConstraintSet
*matrix
,
346 int level
, CloogConstraint
*line
, int nb_par
)
349 assert(cloog_constraint_is_valid(line
));
351 equal
->types
[level
-1] = cloog_constraint_equal_type(line
, level
);
352 c
= cloog_constraint_to_isl(line
);
353 equal
->constraints
[level
- 1] = isl_constraint_copy(c
);
358 * cloog_equal_del function :
359 * This function reset the equality corresponding to the iterator (level)
360 * in the equality matrix (equal).
361 * - July 2nd 2002: first version.
363 void cloog_equal_del(CloogEqualities
*equal
, int level
)
365 equal
->types
[level
-1] = EQTYPE_NONE
;
366 isl_constraint_free(equal
->constraints
[level
- 1]);
367 equal
->constraints
[level
-1] = NULL
;
372 /******************************************************************************
373 * Processing functions *
374 ******************************************************************************/
377 * Function cloog_constraint_set_normalize:
378 * This function will modify the constraint system in such a way that when
379 * there is an equality depending on the element at level 'level', there are
380 * no more (in)equalities depending on this element.
382 * The simplified form of isl automatically satisfies this condition.
384 void cloog_constraint_set_normalize(CloogConstraintSet
*matrix
, int level
)
391 * cloog_constraint_set_copy function:
392 * this functions builds and returns a "hard copy" (not a pointer copy) of a
393 * CloogConstraintSet data structure.
395 CloogConstraintSet
*cloog_constraint_set_copy(CloogConstraintSet
*constraints
)
398 bset
= cloog_constraints_set_to_isl(constraints
);
399 return cloog_constraint_set_from_isl_basic_set(isl_basic_set_dup(bset
));
404 * cloog_constraint_set_simplify function:
405 * this function simplify all constraints inside the matrix "matrix" thanks to
406 * an equality matrix "equal" that gives for some elements of the affine
407 * constraint an equality with other elements, preferably constants.
408 * For instance, if a row of the matrix contains i+j+3>=0 and the equality
409 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
410 * simplified constraints are returned back inside a new simplified matrix.
411 * - matrix is the set of constraints to simplify,
412 * - equal is the matrix of equalities,
413 * - level is a level we don't want to simplify (-1 if none),
414 * - nb_par is the number of parameters of the program.
416 * isl should have performed these simplifications already in isl_set_gist.
418 CloogConstraintSet
*cloog_constraint_set_simplify(CloogConstraintSet
*matrix
,
419 CloogEqualities
*equal
, int level
, int nb_par
)
421 return cloog_constraint_set_copy(matrix
);
425 static struct cloog_isl_dim
constraint_cloog_dim_to_isl_dim(
426 CloogConstraint
*constraint
, int pos
)
428 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
430 struct cloog_isl_dim ci_dim
;
432 for (i
= 0; i
< 3; ++i
) {
433 isl_constraint
*c
= cloog_constraint_to_isl(constraint
);
434 unsigned dim
= isl_constraint_dim(c
, types
[i
]);
436 ci_dim
.type
= types
[i
];
445 static struct clast_expr
*div_expr(CloogConstraint
*constraint
, int pos
,
449 unsigned dim
= cloog_constraint_total_dimension(constraint
);
451 struct clast_reduction
*r
;
452 struct clast_expr
*e
= NULL
;
455 div
= isl_constraint_get_div(cloog_constraint_to_isl(constraint
), pos
);
458 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
459 struct cloog_isl_dim dim
;
461 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
462 if (dim
.type
== isl_dim_set
)
463 dim
.type
= isl_dim_in
;
464 isl_aff_get_coefficient(div
, dim
.type
, dim
.pos
, &c
);
465 if (!cloog_int_is_zero(c
))
468 isl_aff_get_constant(div
, &c
);
469 if (!cloog_int_is_zero(c
))
472 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
473 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
474 struct clast_expr
*v
;
475 struct cloog_isl_dim dim
;
477 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
478 if (dim
.type
== isl_dim_set
)
479 dim
.type
= isl_dim_in
;
480 isl_aff_get_coefficient(div
, dim
.type
, dim
.pos
, &c
);
481 if (cloog_int_is_zero(c
))
484 v
= cloog_constraint_variable_expr(constraint
, 1 + i
, names
);
486 r
->elts
[nb_elts
++] = &new_clast_term(c
, v
)->expr
;
488 isl_aff_get_constant(div
, &c
);
489 if (!cloog_int_is_zero(c
))
490 r
->elts
[nb_elts
++] = &new_clast_term(c
, NULL
)->expr
;
492 isl_aff_get_denominator(div
, &c
);
493 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, c
)->expr
;
503 * Return clast_expr corresponding to the variable "level" (1 based) in
504 * the given constraint.
506 struct clast_expr
*cloog_constraint_variable_expr(CloogConstraint
*constraint
,
507 int level
, CloogNames
*names
)
509 struct cloog_isl_dim dim
;
514 dim
= constraint_cloog_dim_to_isl_dim(constraint
, level
- 1);
515 if (dim
.type
== isl_dim_div
)
516 return div_expr(constraint
, dim
.pos
, names
);
518 if (dim
.type
== isl_dim_set
)
519 name
= cloog_names_name_at_level(names
, level
);
521 name
= names
->parameters
[dim
.pos
];
523 return &new_clast_name(name
)->expr
;
528 * Return true if constraint c involves variable v (zero-based).
530 int cloog_constraint_involves(CloogConstraint
*constraint
, int v
)
536 cloog_constraint_coefficient_get(constraint
, v
, &c
);
537 res
= !isl_int_is_zero(c
);
542 int cloog_constraint_is_lower_bound(CloogConstraint
*constraint
, int v
)
548 cloog_constraint_coefficient_get(constraint
, v
, &c
);
549 res
= isl_int_is_pos(c
);
554 int cloog_constraint_is_upper_bound(CloogConstraint
*constraint
, int v
)
560 cloog_constraint_coefficient_get(constraint
, v
, &c
);
561 res
= isl_int_is_neg(c
);
566 int cloog_constraint_is_equality(CloogConstraint
*constraint
)
568 return isl_constraint_is_equality(cloog_constraint_to_isl(constraint
));
571 CloogConstraintSet
*cloog_constraint_set_drop_constraint(
572 CloogConstraintSet
*constraints
, CloogConstraint
*constraint
)
577 bset
= cloog_constraints_set_to_isl(constraints
);
578 c
= cloog_constraint_to_isl(cloog_constraint_copy(constraint
));
579 bset
= isl_basic_set_drop_constraint(bset
, c
);
580 return cloog_constraint_set_from_isl_basic_set(bset
);
583 void cloog_constraint_coefficient_get(CloogConstraint
*constraint
,
584 int var
, cloog_int_t
*val
)
586 struct cloog_isl_dim dim
;
592 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
593 c
= cloog_constraint_to_isl(constraint
);
594 isl_constraint_get_coefficient(c
, dim
.type
, dim
.pos
, val
);
597 void cloog_constraint_coefficient_set(CloogConstraint
*constraint
,
598 int var
, cloog_int_t val
)
600 struct cloog_isl_dim dim
;
605 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
606 c
= cloog_constraint_to_isl(constraint
);
607 isl_constraint_set_coefficient(c
, dim
.type
, dim
.pos
, val
);
610 void cloog_constraint_constant_get(CloogConstraint
*constraint
, cloog_int_t
*val
)
612 isl_constraint_get_constant(cloog_constraint_to_isl(constraint
), val
);
616 * Copy the coefficient of constraint c into dst in PolyLib order,
617 * i.e., first the coefficients of the variables, then the coefficients
618 * of the parameters and finally the constant.
620 void cloog_constraint_copy_coefficients(CloogConstraint
*constraint
,
626 dim
= cloog_constraint_total_dimension(constraint
);
628 for (i
= 0; i
< dim
; ++i
)
629 cloog_constraint_coefficient_get(constraint
, i
, dst
+i
);
630 cloog_constraint_constant_get(constraint
, dst
+dim
);
633 CloogConstraint
*cloog_constraint_invalid(void)
638 int cloog_constraint_is_valid(CloogConstraint
*constraint
)
640 return constraint
!= NULL
;
643 int cloog_constraint_total_dimension(CloogConstraint
*constraint
)
646 c
= cloog_constraint_to_isl(constraint
);
647 return isl_constraint_dim(c
, isl_dim_all
);
652 * Check whether there is any need for the constraint "upper" on
653 * "level" to get reduced.
654 * In case of the isl backend, there should be no need to do so
655 * if the level corresponds to an existentially quantified variable.
656 * Moreover, the way reduction is performed does not work for such
657 * variables since its position might chance during the construction
658 * of a set for reduction.
660 int cloog_constraint_needs_reduction(CloogConstraint
*upper
, int level
)
664 struct cloog_isl_dim dim
;
666 c
= cloog_constraint_to_isl(upper
);
667 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
668 dim
= basic_set_cloog_dim_to_isl_dim(bset
, level
- 1);
669 isl_basic_set_free(bset
);
671 return dim
.type
== isl_dim_set
;
676 * Create a CloogConstraintSet containing enough information to perform
677 * a reduction on the upper equality (in this case lower is an invalid
678 * CloogConstraint) or the pair of inequalities upper and lower
679 * from within insert_modulo_guard.
680 * In the isl backend, we return a CloogConstraintSet containing both
681 * bounds, as the stride may change during the reduction and we may
682 * need to recompute the bound on the modulo expression.
684 CloogConstraintSet
*cloog_constraint_set_for_reduction(CloogConstraint
*upper
,
685 CloogConstraint
*lower
)
687 struct isl_basic_set
*bset
;
690 c
= cloog_constraint_to_isl(upper
);
691 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
692 if (cloog_constraint_is_valid(lower
)) {
693 c
= cloog_constraint_to_isl(lower
);
694 bset
= isl_basic_set_add_constraint(bset
,
695 isl_constraint_copy(c
));
697 return cloog_constraint_set_from_isl_basic_set(bset
);
701 static int add_constant_term(CloogConstraint
*c
, void *user
)
703 isl_int
*bound
= (isl_int
*)user
;
708 cloog_constraint_constant_get(c
, &v
);
709 isl_int_add(*bound
, *bound
, v
);
717 /* Return an isl_basic_set representation of the equality stored
718 * at position i in the given CloogEqualities.
720 static __isl_give isl_basic_set
*equality_to_basic_set(CloogEqualities
*equal
,
728 c
= isl_constraint_copy(equal
->constraints
[i
]);
729 bset
= isl_basic_set_from_constraint(c
);
730 nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
731 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
732 bset
= isl_basic_set_add_dims(bset
, isl_dim_set
,
733 equal
->total_dim
- (nparam
+ nvar
));
738 * Reduce the modulo guard expressed by "constraints" using equalities
739 * found in outer nesting levels (stored in "equal").
740 * The modulo guard may be an equality or a pair of inequalities.
741 * In case of a pair of inequalities, *bound contains the bound on the
742 * corresponding modulo expression. If any reduction is performed
743 * then this bound is recomputed.
745 * "level" may not correspond to an existentially quantified variable.
747 * We first check if there are any equalities we can use. If not,
748 * there is again nothing to reduce.
749 * For the actual reduction, we use isl_basic_set_gist, but this
750 * function will only perform the reduction we want here if the
751 * the variable that imposes the modulo constraint has been projected
752 * out (i.e., turned into an existentially quantified variable).
753 * After the call to isl_basic_set_gist, we need to move the
754 * existential variable back into the position where the calling
755 * function expects it (assuming there are any constraints left).
756 * We do this by adding an equality between the given dimension and
757 * the existentially quantified variable.
759 * If there are no existentially quantified variables left, then
760 * we don't need to add this equality.
761 * If, on the other hand, the resulting basic set involves more
762 * than one existentially quantified variable, then the caller
763 * will not be able to handle the result, so we just return the
764 * original input instead.
766 CloogConstraintSet
*cloog_constraint_set_reduce(CloogConstraintSet
*constraints
,
767 int level
, CloogEqualities
*equal
, int nb_par
, cloog_int_t
*bound
)
771 struct isl_basic_set
*eq
;
772 struct isl_basic_map
*id
;
773 struct cloog_isl_dim dim
;
774 struct isl_constraint
*c
;
775 unsigned constraints_dim
;
777 isl_basic_set
*bset
, *orig
;
779 bset
= cloog_constraints_set_to_isl(constraints
);
780 orig
= isl_basic_set_copy(bset
);
781 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
782 assert(dim
.type
== isl_dim_set
);
785 for (j
= 0; j
< level
- 1; ++j
) {
786 isl_basic_set
*bset_j
;
787 if (equal
->types
[j
] != EQTYPE_EXAFFINE
)
789 bset_j
= equality_to_basic_set(equal
, j
);
793 eq
= isl_basic_set_intersect(eq
, bset_j
);
796 isl_basic_set_free(orig
);
797 return cloog_constraint_set_from_isl_basic_set(bset
);
800 idim
= isl_space_map_from_set(isl_basic_set_get_space(bset
));
801 id
= isl_basic_map_identity(idim
);
802 id
= isl_basic_map_remove_dims(id
, isl_dim_out
, dim
.pos
, 1);
803 bset
= isl_basic_set_apply(bset
, isl_basic_map_copy(id
));
804 bset
= isl_basic_set_apply(bset
, isl_basic_map_reverse(id
));
806 constraints_dim
= isl_basic_set_dim(bset
, isl_dim_set
);
807 eq
= isl_basic_set_remove_dims(eq
, isl_dim_set
, constraints_dim
,
808 isl_basic_set_dim(eq
, isl_dim_set
) - constraints_dim
);
809 bset
= isl_basic_set_gist(bset
, eq
);
810 n_div
= isl_basic_set_dim(bset
, isl_dim_div
);
812 isl_basic_set_free(bset
);
813 return cloog_constraint_set_from_isl_basic_set(orig
);
816 isl_basic_set_free(orig
);
817 return cloog_constraint_set_from_isl_basic_set(bset
);
820 c
= isl_equality_alloc(isl_basic_set_get_local_space(bset
));
821 c
= isl_constraint_set_coefficient_si(c
, isl_dim_div
, 0, 1);
822 c
= isl_constraint_set_coefficient_si(c
, isl_dim_set
, dim
.pos
, -1);
823 bset
= isl_basic_set_add_constraint(bset
, c
);
825 isl_int_set_si(*bound
, 0);
826 constraints
= cloog_constraint_set_from_isl_basic_set(bset
);
827 cloog_constraint_set_foreach_constraint(constraints
,
828 add_constant_term
, bound
);
830 isl_basic_set_free(orig
);
831 return cloog_constraint_set_from_isl_basic_set(bset
);
834 CloogConstraint
*cloog_constraint_copy(CloogConstraint
*constraint
)
836 return cloog_constraint_from_isl_constraint(
837 isl_constraint_copy(cloog_constraint_to_isl(constraint
)));
840 void cloog_constraint_release(CloogConstraint
*constraint
)
842 isl_constraint_free(cloog_constraint_to_isl(constraint
));
845 struct cloog_isl_foreach
{
846 int (*fn
)(CloogConstraint
*constraint
, void *user
);
850 static int cloog_isl_foreach_cb(__isl_take isl_constraint
*c
, void *user
)
852 struct cloog_isl_foreach
*data
= (struct cloog_isl_foreach
*)user
;
855 if (isl_constraint_is_div_constraint(c
)) {
856 isl_constraint_free(c
);
860 ret
= data
->fn(cloog_constraint_from_isl_constraint(c
), data
->user
);
862 isl_constraint_free(c
);
867 int cloog_constraint_set_foreach_constraint(CloogConstraintSet
*constraints
,
868 int (*fn
)(CloogConstraint
*constraint
, void *user
), void *user
)
870 struct cloog_isl_foreach data
= { fn
, user
};
873 bset
= cloog_constraints_set_to_isl(constraints
);
874 return isl_basic_set_foreach_constraint(bset
,
875 cloog_isl_foreach_cb
, &data
);
878 CloogConstraint
*cloog_equal_constraint(CloogEqualities
*equal
, int j
)
882 c
= isl_constraint_copy(equal
->constraints
[j
]);
883 return cloog_constraint_from_isl_constraint(c
);
886 /* Given a stride constraint on iterator i (specified by level) of the form
888 * i = f(outer iterators) + stride * f(existentials)
890 * extract f as an isl_aff.
892 static isl_aff
*extract_stride_offset(__isl_keep isl_constraint
*c
,
893 int level
, CloogStride
*stride
)
896 isl_space
*dim
= isl_constraint_get_space(c
);
897 isl_local_space
*ls
= isl_local_space_from_space(dim
);
898 isl_aff
*offset
= isl_aff_zero_on_domain(ls
);
900 unsigned nparam
, nvar
;
904 nparam
= isl_constraint_dim(c
, isl_dim_param
);
905 nvar
= isl_constraint_dim(c
, isl_dim_set
);
907 for (i
= 0; i
< nparam
; ++i
) {
908 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &u
);
909 isl_int_mul(u
, u
, stride
->factor
);
910 offset
= isl_aff_set_coefficient(offset
, isl_dim_param
, i
, u
);
912 for (i
= 0; i
< nvar
; ++i
) {
915 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &u
);
916 isl_int_mul(u
, u
, stride
->factor
);
917 offset
= isl_aff_set_coefficient(offset
, isl_dim_in
, i
, u
);
919 isl_constraint_get_constant(c
, &u
);
920 isl_int_mul(u
, u
, stride
->factor
);
921 offset
= isl_aff_set_constant(offset
, u
);
928 /* Update the given lower bound on level such that it satisfies the stride
929 * constraint. The computation performed here is essentially the same
930 * as that performed in constraint_stride_lower_c.
932 * We update the constraint
938 * i >= s * ceil((-f/a - d)/s) + d
940 * with s the stride and d the offset encoded in the stride constraint.
942 CloogConstraint
*cloog_constraint_stride_lower_bound(CloogConstraint
*c
,
943 int level
, CloogStride
*stride
)
945 isl_constraint
*stride_c
= cloog_constraint_to_isl(stride
->constraint
);
946 isl_constraint
*bound
= cloog_constraint_to_isl(c
);
950 lower
= isl_constraint_get_bound(bound
, isl_dim_set
, level
- 1);
951 isl_constraint_free(bound
);
953 offset
= extract_stride_offset(stride_c
, level
, stride
);
955 lower
= isl_aff_sub(lower
, isl_aff_copy(offset
));
956 lower
= isl_aff_scale_down(lower
, stride
->stride
);
957 lower
= isl_aff_ceil(lower
);
958 lower
= isl_aff_scale(lower
, stride
->stride
);
959 lower
= isl_aff_add(lower
, offset
);
960 lower
= isl_aff_neg(lower
);
961 lower
= isl_aff_add_coefficient_si(lower
, isl_dim_in
, level
- 1, 1);
963 bound
= isl_inequality_from_aff(lower
);
965 return cloog_constraint_from_isl_constraint(bound
);