4 #include <cloog/isl/cloog.h>
5 #include <cloog/isl/backend.h>
9 #include <isl/val_gmp.h>
12 #define ALLOC(type) (type*)malloc(sizeof(type))
13 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
15 __isl_give isl_val
*cloog_int_to_isl_val(isl_ctx
* ctx
, cloog_int_t c
)
18 #if defined(CLOOG_INT_INT)
19 v
= isl_val_int_from_si(ctx
, c
);
20 #elif defined(CLOOG_INT_LONG)
21 v
= isl_val_int_from_si(ctx
, c
);
22 #elif defined(CLOOG_INT_LONG_LONG)
23 v
= isl_val_int_from_si(ctx
, c
);
24 #elif defined(CLOOG_INT_GMP)
25 v
= isl_val_int_from_gmp(ctx
, c
);
27 #error "No integer type defined"
33 * CLooG'll be dealing in integers so we expect numerator/1 form
34 * from isl_val. Thus get numerator to assign to cloog_int
36 void isl_val_to_cloog_int(__isl_keep isl_val
*val
, cloog_int_t
*cint
)
38 assert(isl_val_is_int(val
));
39 #if defined(CLOOG_INT_INT)
40 *cint
= isl_val_get_num_si(val
);
41 #elif defined(CLOOG_INT_LONG)
42 *cint
= isl_val_get_num_si(val
);
43 #elif defined(CLOOG_INT_LONG_LONG)
44 *cint
= isl_val_get_num_si(val
);
45 #elif defined(CLOOG_INT_GMP)
46 isl_val_get_num_gmp(val
, *cint
);
48 #error "No integer type defined"
53 CloogConstraintSet
*cloog_constraint_set_from_isl_basic_set(struct isl_basic_set
*bset
)
55 return (CloogConstraintSet
*)bset
;
58 CloogConstraint
*cloog_constraint_from_isl_constraint(struct isl_constraint
*constraint
)
60 return (CloogConstraint
*)constraint
;
63 isl_constraint
*cloog_constraint_to_isl(CloogConstraint
*constraint
)
65 return (isl_constraint
*)constraint
;
68 isl_basic_set
*cloog_constraints_set_to_isl(CloogConstraintSet
*constraints
)
70 return (isl_basic_set
*)constraints
;
74 /******************************************************************************
75 * Memory leaks hunting *
76 ******************************************************************************/
80 void cloog_constraint_set_free(CloogConstraintSet
*constraints
)
82 isl_basic_set_free(cloog_constraints_set_to_isl(constraints
));
86 int cloog_constraint_set_contains_level(CloogConstraintSet
*constraints
,
87 int level
, int nb_parameters
)
90 bset
= cloog_constraints_set_to_isl(constraints
);
91 return isl_basic_set_dim(bset
, isl_dim_set
) >= level
;
94 struct cloog_isl_dim
{
95 enum isl_dim_type type
;
99 static struct cloog_isl_dim
basic_set_cloog_dim_to_isl_dim(
100 __isl_keep isl_basic_set
*bset
, int pos
)
102 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
104 struct cloog_isl_dim ci_dim
;
106 for (i
= 0; i
< 3; ++i
) {
107 unsigned dim
= isl_basic_set_dim(bset
, types
[i
]);
109 ci_dim
.type
= types
[i
];
118 static struct cloog_isl_dim
set_cloog_dim_to_isl_dim(
119 CloogConstraintSet
*constraints
, int pos
)
123 bset
= cloog_constraints_set_to_isl(constraints
);
124 return basic_set_cloog_dim_to_isl_dim(bset
, pos
);
127 /* Check if the variable at position level is defined by an
128 * equality. If so, return the row number. Otherwise, return -1.
130 CloogConstraint
*cloog_constraint_set_defining_equality(
131 CloogConstraintSet
*constraints
, int level
)
133 struct isl_constraint
*c
;
134 struct cloog_isl_dim dim
;
137 bset
= cloog_constraints_set_to_isl(constraints
);
138 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
139 if (isl_basic_set_has_defining_equality(bset
, dim
.type
, dim
.pos
, &c
))
140 return cloog_constraint_from_isl_constraint(c
);
146 struct cloog_isl_other
{
154 /* Set other->found to 1 if the given constraint involves other->level
155 * and is different from other->u and other->l.
157 static int check_other_constraint(__isl_take isl_constraint
*c
, void *user
)
159 struct cloog_isl_other
*other
= user
;
162 if (!isl_constraint_is_equal(c
, other
->l
) &&
163 !isl_constraint_is_equal(c
, other
->u
)) {
164 cc
= cloog_constraint_from_isl_constraint(c
);
165 if (cloog_constraint_involves(cc
, other
->level
- 1))
169 isl_constraint_free(c
);
171 return other
->found
? -1 : 0;
175 /* Check if the variable (e) at position level is defined by a
176 * pair of inequalities
177 * <a, i> + -m e + <b, p> + k1 >= 0
178 * <-a, i> + m e + <-b, p> + k2 >= 0
179 * with 0 <= k1 + k2 < m
180 * If so return the row number of the upper bound and set *lower
181 * to the row number of the lower bound. If not, return -1.
183 * If the variable at position level occurs in any other constraint,
184 * then we currently return -1. The modulo guard that we would generate
185 * would still be correct, but we would also need to generate
186 * guards corresponding to the other constraints, and this has not
187 * been implemented yet.
189 CloogConstraint
*cloog_constraint_set_defining_inequalities(
190 CloogConstraintSet
*constraints
,
191 int level
, CloogConstraint
**lower
, int nb_par
)
193 struct isl_constraint
*u
;
194 struct isl_constraint
*l
;
195 struct cloog_isl_dim dim
;
196 struct isl_basic_set
*bset
;
197 struct cloog_isl_other other
;
199 bset
= cloog_constraints_set_to_isl(constraints
);
200 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
201 if (!isl_basic_set_has_defining_inequalities(bset
, dim
.type
, dim
.pos
,
203 return cloog_constraint_invalid();
209 isl_basic_set_foreach_constraint(bset
, &check_other_constraint
, &other
);
211 isl_constraint_free(l
);
212 isl_constraint_free(u
);
216 *lower
= cloog_constraint_from_isl_constraint(l
);
217 return cloog_constraint_from_isl_constraint(u
);
220 int cloog_constraint_set_total_dimension(CloogConstraintSet
*constraints
)
223 bset
= cloog_constraints_set_to_isl(constraints
);
224 return isl_basic_set_total_dim(bset
);
227 int cloog_constraint_set_n_iterators(CloogConstraintSet
*constraints
, int n_par
)
230 bset
= cloog_constraints_set_to_isl(constraints
);
231 return isl_basic_set_dim(bset
, isl_dim_set
);
235 /******************************************************************************
236 * Equalities spreading functions *
237 ******************************************************************************/
240 /* Equalities are stored inside a Matrix data structure called "equal".
241 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
242 * dimensions + 1, the "+ 1" is because a statement can be included inside an
243 * external loop without iteration domain), and (nb_scattering + nb_iterators +
244 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
245 * type). The ith row corresponds to the equality "= 0" for the ith dimension
246 * iterator. The first column gives the equality type (0: no equality, then
247 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
248 * the current level is found, the corresponding row is updated. Then the
249 * equality if it exists is used to simplify expressions (e.g. if we have
250 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
251 * the pprint call, the corresponding row is reset to zero.
254 CloogEqualities
*cloog_equal_alloc(int n
, int nb_levels
, int nb_parameters
)
257 CloogEqualities
*equal
= ALLOC(CloogEqualities
);
259 equal
->total_dim
= nb_levels
- 1 + nb_parameters
;
261 equal
->constraints
= ALLOCN(isl_constraint
*, n
);
262 equal
->types
= ALLOCN(int, n
);
263 for (i
= 0; i
< n
; ++i
) {
264 equal
->constraints
[i
] = NULL
;
265 equal
->types
[i
] = EQTYPE_NONE
;
270 int cloog_equal_total_dimension(CloogEqualities
*equal
)
272 return equal
->total_dim
;
275 void cloog_equal_free(CloogEqualities
*equal
)
279 for (i
= 0; i
< equal
->n
; ++i
)
280 isl_constraint_free(equal
->constraints
[i
]);
281 free(equal
->constraints
);
286 int cloog_equal_count(CloogEqualities
*equal
)
293 * cloog_constraint_equal_type function :
294 * This function returns the type of the equality in the constraint (line) of
295 * (constraints) for the element (level). An equality is 'constant' iff all
296 * other factors are null except the constant one. It is a 'pure item' iff
297 * it is equal or opposite to a single variable or parameter.
298 * Otherwise it is an 'affine expression'.
300 * i = -13 is constant, i = j, j = -M are pure items,
301 * j = 2*M, i = j+1, 2*j = M are affine expressions.
303 * - constraints is the matrix of constraints,
304 * - level is the column number in equal of the element which is 'equal to',
306 static int cloog_constraint_equal_type(CloogConstraint
*cc
, int level
)
310 int type
= EQTYPE_NONE
;
311 struct isl_constraint
*constraint
= cloog_constraint_to_isl(cc
);
313 c
= isl_constraint_get_constant_val(constraint
);
314 if (!isl_val_is_zero(c
))
315 type
= EQTYPE_CONSTANT
;
317 c
= isl_constraint_get_coefficient_val(constraint
, isl_dim_set
, level
- 1);
318 if (!isl_val_is_one(c
) && !isl_val_is_negone(c
))
319 type
= EQTYPE_EXAFFINE
;
321 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_param
); ++i
) {
322 c
= isl_constraint_get_coefficient_val(constraint
, isl_dim_param
, i
);
323 if (isl_val_is_zero(c
)){
327 if ((!isl_val_is_one(c
) && !isl_val_is_negone(c
)) ||
328 type
!= EQTYPE_NONE
) {
329 type
= EQTYPE_EXAFFINE
;
333 type
= EQTYPE_PUREITEM
;
336 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_set
); ++i
) {
339 c
= isl_constraint_get_coefficient_val(constraint
, isl_dim_set
, i
);
340 if (isl_val_is_zero(c
)){
344 if ((!isl_val_is_one(c
) && !isl_val_is_negone(c
)) ||
345 type
!= EQTYPE_NONE
) {
346 type
= EQTYPE_EXAFFINE
;
350 type
= EQTYPE_PUREITEM
;
353 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_div
); ++i
) {
354 c
= isl_constraint_get_coefficient_val(constraint
, isl_dim_div
, i
);
355 if (isl_val_is_zero(c
)){
359 if ((!isl_val_is_one(c
) && !isl_val_is_negone(c
)) ||
360 type
!= EQTYPE_NONE
) {
361 type
= EQTYPE_EXAFFINE
;
365 type
= EQTYPE_PUREITEM
;
369 if (type
== EQTYPE_NONE
)
370 type
= EQTYPE_CONSTANT
;
376 int cloog_equal_type(CloogEqualities
*equal
, int level
)
378 return equal
->types
[level
-1];
383 * cloog_equal_add function:
384 * This function updates the row (level-1) of the equality matrix (equal) with
385 * the row that corresponds to the row (line) of the matrix (matrix).
386 * - equal is the matrix of equalities,
387 * - matrix is the matrix of constraints,
388 * - level is the column number in matrix of the element which is 'equal to',
389 * - line is the line number in matrix of the constraint we want to study,
390 * - the infos structure gives the user all options on code printing and more.
392 * line is set to an invalid constraint for equalities that CLooG itself has
393 * discovered because the lower and upper bound of a loop happened to be equal.
394 * This situation shouldn't happen in the isl port since isl should
395 * have found the equality itself.
397 void cloog_equal_add(CloogEqualities
*equal
, CloogConstraintSet
*matrix
,
398 int level
, CloogConstraint
*line
, int nb_par
)
401 assert(cloog_constraint_is_valid(line
));
403 equal
->types
[level
-1] = cloog_constraint_equal_type(line
, level
);
404 c
= cloog_constraint_to_isl(line
);
405 equal
->constraints
[level
- 1] = isl_constraint_copy(c
);
410 * cloog_equal_del function :
411 * This function reset the equality corresponding to the iterator (level)
412 * in the equality matrix (equal).
413 * - July 2nd 2002: first version.
415 void cloog_equal_del(CloogEqualities
*equal
, int level
)
417 equal
->types
[level
-1] = EQTYPE_NONE
;
418 isl_constraint_free(equal
->constraints
[level
- 1]);
419 equal
->constraints
[level
-1] = NULL
;
424 /******************************************************************************
425 * Processing functions *
426 ******************************************************************************/
429 * Function cloog_constraint_set_normalize:
430 * This function will modify the constraint system in such a way that when
431 * there is an equality depending on the element at level 'level', there are
432 * no more (in)equalities depending on this element.
434 * The simplified form of isl automatically satisfies this condition.
436 void cloog_constraint_set_normalize(CloogConstraintSet
*matrix
, int level
)
443 * cloog_constraint_set_copy function:
444 * this functions builds and returns a "hard copy" (not a pointer copy) of a
445 * CloogConstraintSet data structure.
447 CloogConstraintSet
*cloog_constraint_set_copy(CloogConstraintSet
*constraints
)
450 bset
= cloog_constraints_set_to_isl(constraints
);
451 return cloog_constraint_set_from_isl_basic_set(isl_basic_set_dup(bset
));
456 * cloog_constraint_set_simplify function:
457 * this function simplify all constraints inside the matrix "matrix" thanks to
458 * an equality matrix "equal" that gives for some elements of the affine
459 * constraint an equality with other elements, preferably constants.
460 * For instance, if a row of the matrix contains i+j+3>=0 and the equality
461 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
462 * simplified constraints are returned back inside a new simplified matrix.
463 * - matrix is the set of constraints to simplify,
464 * - equal is the matrix of equalities,
465 * - level is a level we don't want to simplify (-1 if none),
466 * - nb_par is the number of parameters of the program.
468 * isl should have performed these simplifications already in isl_set_gist.
470 CloogConstraintSet
*cloog_constraint_set_simplify(CloogConstraintSet
*matrix
,
471 CloogEqualities
*equal
, int level
, int nb_par
)
473 return cloog_constraint_set_copy(matrix
);
477 static struct cloog_isl_dim
constraint_cloog_dim_to_isl_dim(
478 CloogConstraint
*constraint
, int pos
)
480 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
482 struct cloog_isl_dim ci_dim
;
484 for (i
= 0; i
< 3; ++i
) {
485 isl_constraint
*c
= cloog_constraint_to_isl(constraint
);
486 unsigned dim
= isl_constraint_dim(c
, types
[i
]);
488 ci_dim
.type
= types
[i
];
497 static struct clast_expr
*div_expr(CloogConstraint
*constraint
, int pos
,
501 unsigned dim
= cloog_constraint_total_dimension(constraint
);
503 struct clast_reduction
*r
;
504 struct clast_expr
*e
= NULL
;
508 cloog_int_init(cint
);
509 div
= isl_constraint_get_div(cloog_constraint_to_isl(constraint
), pos
);
511 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
512 struct cloog_isl_dim dim
;
514 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
515 if (dim
.type
== isl_dim_set
)
516 dim
.type
= isl_dim_in
;
517 c
= isl_aff_get_coefficient_val(div
, dim
.type
, dim
.pos
);
518 if (!isl_val_is_zero(c
))
523 c
= isl_aff_get_constant_val(div
);
524 if (!isl_val_is_zero(c
))
528 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
529 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
530 struct clast_expr
*v
;
531 struct cloog_isl_dim dim
;
533 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
534 if (dim
.type
== isl_dim_set
)
535 dim
.type
= isl_dim_in
;
536 c
= isl_aff_get_coefficient_val(div
, dim
.type
, dim
.pos
);
537 if (isl_val_is_zero(c
)){
542 v
= cloog_constraint_variable_expr(constraint
, 1 + i
, names
);
544 /* We are interested only in the numerator */
545 cloog_int_set_si(cint
, isl_val_get_num_si(c
));
546 r
->elts
[nb_elts
++] = &new_clast_term(cint
, v
)->expr
;
551 c
= isl_aff_get_constant_val(div
);
552 if (!isl_val_is_zero(c
)) {
553 /* We are interested only in the numerator */
554 cloog_int_set_si(cint
, isl_val_get_num_si(c
));
555 r
->elts
[nb_elts
++] = &new_clast_term(cint
, NULL
)->expr
;
559 c
= isl_aff_get_denominator_val(div
);
560 isl_val_to_cloog_int(c
, &cint
);
562 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, cint
)->expr
;
564 cloog_int_clear(cint
);
572 * Return clast_expr corresponding to the variable "level" (1 based) in
573 * the given constraint.
575 struct clast_expr
*cloog_constraint_variable_expr(CloogConstraint
*constraint
,
576 int level
, CloogNames
*names
)
578 struct cloog_isl_dim dim
;
583 dim
= constraint_cloog_dim_to_isl_dim(constraint
, level
- 1);
584 if (dim
.type
== isl_dim_div
)
585 return div_expr(constraint
, dim
.pos
, names
);
587 if (dim
.type
== isl_dim_set
)
588 name
= cloog_names_name_at_level(names
, level
);
590 name
= names
->parameters
[dim
.pos
];
592 return &new_clast_name(name
)->expr
;
597 * Return true if constraint c involves variable v (zero-based).
599 int cloog_constraint_involves(CloogConstraint
*constraint
, int v
)
604 c
= cloog_constraint_coefficient_get_val(constraint
, v
);
605 res
= !isl_val_is_zero(c
);
610 int cloog_constraint_is_lower_bound(CloogConstraint
*constraint
, int v
)
615 c
= cloog_constraint_coefficient_get_val(constraint
, v
);
616 res
= isl_val_is_pos(c
);
621 int cloog_constraint_is_upper_bound(CloogConstraint
*constraint
, int v
)
626 c
= cloog_constraint_coefficient_get_val(constraint
, v
);
627 res
= isl_val_is_neg(c
);
632 int cloog_constraint_is_equality(CloogConstraint
*constraint
)
634 return isl_constraint_is_equality(cloog_constraint_to_isl(constraint
));
637 CloogConstraintSet
*cloog_constraint_set_drop_constraint(
638 CloogConstraintSet
*constraints
, CloogConstraint
*constraint
)
643 bset
= cloog_constraints_set_to_isl(constraints
);
644 c
= cloog_constraint_to_isl(cloog_constraint_copy(constraint
));
645 bset
= isl_basic_set_drop_constraint(bset
, c
);
646 return cloog_constraint_set_from_isl_basic_set(bset
);
649 void cloog_constraint_coefficient_get(CloogConstraint
*constraint
,
650 int var
, cloog_int_t
*val
)
652 struct cloog_isl_dim dim
;
659 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
660 c
= cloog_constraint_to_isl(constraint
);
661 ival
= isl_constraint_get_coefficient_val(c
, dim
.type
, dim
.pos
);
663 isl_val_to_cloog_int(ival
, val
);
667 isl_val
*cloog_constraint_coefficient_get_val(CloogConstraint
*constraint
,
670 struct cloog_isl_dim dim
;
677 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
678 c
= cloog_constraint_to_isl(constraint
);
679 val
= isl_constraint_get_coefficient_val(c
, dim
.type
, dim
.pos
);
685 void cloog_constraint_coefficient_set(CloogConstraint
*constraint
,
686 int var
, cloog_int_t val
)
688 struct cloog_isl_dim dim
;
693 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
694 c
= cloog_constraint_to_isl(constraint
);
695 isl_constraint_set_coefficient_val(c
, dim
.type
, dim
.pos
,
696 cloog_int_to_isl_val(isl_constraint_get_ctx(c
), val
));
699 void cloog_constraint_constant_get(CloogConstraint
*constraint
, cloog_int_t
*val
)
702 ival
= isl_constraint_get_constant_val(cloog_constraint_to_isl(constraint
));
703 isl_val_to_cloog_int(ival
, val
);
708 __isl_give isl_val
*cloog_constraint_constant_get_val(CloogConstraint
*constraint
)
710 return isl_constraint_get_constant_val(cloog_constraint_to_isl(constraint
));
716 * Copy the coefficient of constraint c into dst in PolyLib order,
717 * i.e., first the coefficients of the variables, then the coefficients
718 * of the parameters and finally the constant.
720 void cloog_constraint_copy_coefficients(CloogConstraint
*constraint
,
726 dim
= cloog_constraint_total_dimension(constraint
);
728 for (i
= 0; i
< dim
; ++i
)
729 cloog_constraint_coefficient_get(constraint
, i
, dst
+i
);
730 cloog_constraint_constant_get(constraint
, dst
+dim
);
733 CloogConstraint
*cloog_constraint_invalid(void)
738 int cloog_constraint_is_valid(CloogConstraint
*constraint
)
740 return constraint
!= NULL
;
743 int cloog_constraint_total_dimension(CloogConstraint
*constraint
)
746 c
= cloog_constraint_to_isl(constraint
);
747 return isl_constraint_dim(c
, isl_dim_all
);
752 * Check whether there is any need for the constraint "upper" on
753 * "level" to get reduced.
754 * In case of the isl backend, there should be no need to do so
755 * if the level corresponds to an existentially quantified variable.
756 * Moreover, the way reduction is performed does not work for such
757 * variables since its position might chance during the construction
758 * of a set for reduction.
760 int cloog_constraint_needs_reduction(CloogConstraint
*upper
, int level
)
764 struct cloog_isl_dim dim
;
766 c
= cloog_constraint_to_isl(upper
);
767 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
768 dim
= basic_set_cloog_dim_to_isl_dim(bset
, level
- 1);
769 isl_basic_set_free(bset
);
771 return dim
.type
== isl_dim_set
;
776 * Create a CloogConstraintSet containing enough information to perform
777 * a reduction on the upper equality (in this case lower is an invalid
778 * CloogConstraint) or the pair of inequalities upper and lower
779 * from within insert_modulo_guard.
780 * In the isl backend, we return a CloogConstraintSet containing both
781 * bounds, as the stride may change during the reduction and we may
782 * need to recompute the bound on the modulo expression.
784 CloogConstraintSet
*cloog_constraint_set_for_reduction(CloogConstraint
*upper
,
785 CloogConstraint
*lower
)
787 struct isl_basic_set
*bset
;
790 c
= cloog_constraint_to_isl(upper
);
791 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
792 if (cloog_constraint_is_valid(lower
)) {
793 c
= cloog_constraint_to_isl(lower
);
794 bset
= isl_basic_set_add_constraint(bset
,
795 isl_constraint_copy(c
));
797 return cloog_constraint_set_from_isl_basic_set(bset
);
801 static int add_constant_term(CloogConstraint
*c
, void *user
)
803 isl_val
**bound
= (isl_val
**)user
;
806 v
= cloog_constraint_constant_get_val(c
);
807 *bound
= isl_val_add(*bound
, v
);
813 /* Return an isl_basic_set representation of the equality stored
814 * at position i in the given CloogEqualities.
816 static __isl_give isl_basic_set
*equality_to_basic_set(CloogEqualities
*equal
,
824 c
= isl_constraint_copy(equal
->constraints
[i
]);
825 bset
= isl_basic_set_from_constraint(c
);
826 nparam
= isl_basic_set_dim(bset
, isl_dim_param
);
827 nvar
= isl_basic_set_dim(bset
, isl_dim_set
);
828 bset
= isl_basic_set_add_dims(bset
, isl_dim_set
,
829 equal
->total_dim
- (nparam
+ nvar
));
834 * Reduce the modulo guard expressed by "constraints" using equalities
835 * found in outer nesting levels (stored in "equal").
836 * The modulo guard may be an equality or a pair of inequalities.
837 * In case of a pair of inequalities, *bound contains the bound on the
838 * corresponding modulo expression. If any reduction is performed
839 * then this bound is recomputed.
841 * "level" may not correspond to an existentially quantified variable.
843 * We first check if there are any equalities we can use. If not,
844 * there is again nothing to reduce.
845 * For the actual reduction, we use isl_basic_set_gist, but this
846 * function will only perform the reduction we want here if the
847 * the variable that imposes the modulo constraint has been projected
848 * out (i.e., turned into an existentially quantified variable).
849 * After the call to isl_basic_set_gist, we need to move the
850 * existential variable back into the position where the calling
851 * function expects it (assuming there are any constraints left).
852 * We do this by adding an equality between the given dimension and
853 * the existentially quantified variable.
855 * If there are no existentially quantified variables left, then
856 * we don't need to add this equality.
857 * If, on the other hand, the resulting basic set involves more
858 * than one existentially quantified variable, then the caller
859 * will not be able to handle the result, so we just return the
860 * original input instead.
862 CloogConstraintSet
*cloog_constraint_set_reduce(CloogConstraintSet
*constraints
,
863 int level
, CloogEqualities
*equal
, int nb_par
, cloog_int_t
*bound
)
867 struct isl_basic_set
*eq
;
868 struct isl_basic_map
*id
;
869 struct cloog_isl_dim dim
;
870 struct isl_constraint
*c
;
871 unsigned constraints_dim
;
873 isl_basic_set
*bset
, *orig
;
875 bset
= cloog_constraints_set_to_isl(constraints
);
876 orig
= isl_basic_set_copy(bset
);
877 dim
= set_cloog_dim_to_isl_dim(constraints
, level
- 1);
878 assert(dim
.type
== isl_dim_set
);
881 for (j
= 0; j
< level
- 1; ++j
) {
882 isl_basic_set
*bset_j
;
883 if (equal
->types
[j
] != EQTYPE_EXAFFINE
)
885 bset_j
= equality_to_basic_set(equal
, j
);
889 eq
= isl_basic_set_intersect(eq
, bset_j
);
892 isl_basic_set_free(orig
);
893 return cloog_constraint_set_from_isl_basic_set(bset
);
896 idim
= isl_space_map_from_set(isl_basic_set_get_space(bset
));
897 id
= isl_basic_map_identity(idim
);
898 id
= isl_basic_map_remove_dims(id
, isl_dim_out
, dim
.pos
, 1);
899 bset
= isl_basic_set_apply(bset
, isl_basic_map_copy(id
));
900 bset
= isl_basic_set_apply(bset
, isl_basic_map_reverse(id
));
902 constraints_dim
= isl_basic_set_dim(bset
, isl_dim_set
);
903 eq
= isl_basic_set_remove_dims(eq
, isl_dim_set
, constraints_dim
,
904 isl_basic_set_dim(eq
, isl_dim_set
) - constraints_dim
);
905 bset
= isl_basic_set_gist(bset
, eq
);
906 n_div
= isl_basic_set_dim(bset
, isl_dim_div
);
908 isl_basic_set_free(bset
);
909 return cloog_constraint_set_from_isl_basic_set(orig
);
912 isl_basic_set_free(orig
);
913 return cloog_constraint_set_from_isl_basic_set(bset
);
916 c
= isl_equality_alloc(isl_basic_set_get_local_space(bset
));
917 c
= isl_constraint_set_coefficient_si(c
, isl_dim_div
, 0, 1);
918 c
= isl_constraint_set_coefficient_si(c
, isl_dim_set
, dim
.pos
, -1);
919 bset
= isl_basic_set_add_constraint(bset
, c
);
921 cloog_int_set_si(*bound
, 0);
922 isl_val
*v
= cloog_int_to_isl_val(isl_basic_set_get_ctx(bset
), *bound
);
923 constraints
= cloog_constraint_set_from_isl_basic_set(bset
);
924 cloog_constraint_set_foreach_constraint(constraints
,
925 add_constant_term
, &v
);
926 isl_val_to_cloog_int(v
, bound
); //return the value to bound
929 isl_basic_set_free(orig
);
930 return cloog_constraint_set_from_isl_basic_set(bset
);
933 CloogConstraint
*cloog_constraint_copy(CloogConstraint
*constraint
)
935 return cloog_constraint_from_isl_constraint(
936 isl_constraint_copy(cloog_constraint_to_isl(constraint
)));
939 void cloog_constraint_release(CloogConstraint
*constraint
)
941 isl_constraint_free(cloog_constraint_to_isl(constraint
));
944 struct cloog_isl_foreach
{
945 int (*fn
)(CloogConstraint
*constraint
, void *user
);
949 static int cloog_isl_foreach_cb(__isl_take isl_constraint
*c
, void *user
)
951 struct cloog_isl_foreach
*data
= (struct cloog_isl_foreach
*)user
;
954 if (isl_constraint_is_div_constraint(c
)) {
955 isl_constraint_free(c
);
959 ret
= data
->fn(cloog_constraint_from_isl_constraint(c
), data
->user
);
961 isl_constraint_free(c
);
966 int cloog_constraint_set_foreach_constraint(CloogConstraintSet
*constraints
,
967 int (*fn
)(CloogConstraint
*constraint
, void *user
), void *user
)
969 struct cloog_isl_foreach data
= { fn
, user
};
972 bset
= cloog_constraints_set_to_isl(constraints
);
973 return isl_basic_set_foreach_constraint(bset
,
974 cloog_isl_foreach_cb
, &data
);
977 CloogConstraint
*cloog_equal_constraint(CloogEqualities
*equal
, int j
)
981 c
= isl_constraint_copy(equal
->constraints
[j
]);
982 return cloog_constraint_from_isl_constraint(c
);
985 /* Given a stride constraint on iterator i (specified by level) of the form
987 * i = f(outer iterators) + stride * f(existentials)
989 * extract f as an isl_aff.
991 static isl_aff
*extract_stride_offset(__isl_keep isl_constraint
*c
,
992 int level
, CloogStride
*stride
)
995 isl_space
*dim
= isl_constraint_get_space(c
);
996 isl_local_space
*ls
= isl_local_space_from_space(dim
);
997 isl_aff
*offset
= isl_aff_zero_on_domain(ls
);
999 unsigned nparam
, nvar
;
1001 nparam
= isl_constraint_dim(c
, isl_dim_param
);
1002 nvar
= isl_constraint_dim(c
, isl_dim_set
);
1004 for (i
= 0; i
< nparam
; ++i
) {
1005 u
= isl_constraint_get_coefficient_val(c
, isl_dim_param
, i
);
1006 u
= isl_val_mul(u
, cloog_int_to_isl_val(isl_constraint_get_ctx(c
), stride
->factor
));
1007 offset
= isl_aff_set_coefficient_val(offset
, isl_dim_param
, i
, u
);
1009 for (i
= 0; i
< nvar
; ++i
) {
1012 u
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, i
);
1013 u
= isl_val_mul(u
, cloog_int_to_isl_val(isl_constraint_get_ctx(c
), stride
->factor
));
1014 offset
= isl_aff_set_coefficient_val(offset
, isl_dim_in
, i
, u
);
1016 u
= isl_constraint_get_constant_val(c
);
1017 u
= isl_val_mul(u
, cloog_int_to_isl_val(isl_constraint_get_ctx(c
), stride
->factor
));
1018 offset
= isl_aff_set_constant_val(offset
, u
);
1023 /* Update the given lower bound on level such that it satisfies the stride
1024 * constraint. The computation performed here is essentially the same
1025 * as that performed in constraint_stride_lower_c.
1027 * We update the constraint
1033 * i >= s * ceil((-f/a - d)/s) + d
1035 * with s the stride and d the offset encoded in the stride constraint.
1037 CloogConstraint
*cloog_constraint_stride_lower_bound(CloogConstraint
*c
,
1038 int level
, CloogStride
*stride
)
1040 isl_constraint
*stride_c
= cloog_constraint_to_isl(stride
->constraint
);
1041 isl_constraint
*bound
= cloog_constraint_to_isl(c
);
1045 lower
= isl_constraint_get_bound(bound
, isl_dim_set
, level
- 1);
1046 isl_constraint_free(bound
);
1048 offset
= extract_stride_offset(stride_c
, level
, stride
);
1050 lower
= isl_aff_sub(lower
, isl_aff_copy(offset
));
1051 lower
= isl_aff_scale_down_val(lower
, cloog_int_to_isl_val(isl_constraint_get_ctx(stride_c
), stride
->stride
));
1052 lower
= isl_aff_ceil(lower
);
1053 lower
= isl_aff_scale_val(lower
, cloog_int_to_isl_val(isl_constraint_get_ctx(stride_c
), stride
->stride
));
1054 lower
= isl_aff_add(lower
, offset
);
1055 lower
= isl_aff_neg(lower
);
1056 lower
= isl_aff_add_coefficient_si(lower
, isl_dim_in
, level
- 1, 1);
1058 bound
= isl_inequality_from_aff(lower
);
1060 return cloog_constraint_from_isl_constraint(bound
);