4 #include <cloog/isl/cloog.h>
5 #include <cloog/isl/backend.h>
9 #define ALLOC(type) (type*)malloc(sizeof(type))
10 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
13 /******************************************************************************
14 * Memory leaks hunting *
15 ******************************************************************************/
19 * These global variables are devoted to memory leaks hunting in the PolyLib
20 * backend. The isl backend has its own memory leak detection facilities.
22 int cloog_matrix_allocated
= 0;
23 int cloog_matrix_freed
= 0;
24 int cloog_matrix_max
= 0;
27 void cloog_constraint_set_free(CloogConstraintSet
*constraints
)
29 isl_basic_set_free(constraints
);
33 int cloog_constraint_set_contains_level(CloogConstraintSet
*constraints
,
34 int level
, int nb_parameters
)
36 return isl_basic_set_n_dim(constraints
) >= level
;
39 struct cloog_isl_dim
{
40 enum isl_dim_type type
;
44 static struct cloog_isl_dim
set_cloog_dim_to_isl_dim(
45 CloogConstraintSet
*bset
, int pos
)
47 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
49 struct cloog_isl_dim ci_dim
;
51 for (i
= 0; i
< 3; ++i
) {
52 unsigned dim
= isl_basic_set_dim(bset
, types
[i
]);
54 ci_dim
.type
= types
[i
];
63 /* Check if the variable at position level is defined by an
64 * equality. If so, return the row number. Otherwise, return -1.
66 CloogConstraint
cloog_constraint_set_defining_equality(
67 CloogConstraintSet
*bset
, int level
)
69 struct isl_constraint
*c
;
70 struct cloog_isl_dim dim
;
72 dim
= set_cloog_dim_to_isl_dim(bset
, level
- 1);
73 if (isl_basic_set_has_defining_equality(bset
, dim
.type
, dim
.pos
, &c
))
80 /* Check if the variable (e) at position level is defined by a
81 * pair of inequalities
82 * <a, i> + -m e + <b, p> + k1 >= 0
83 * <-a, i> + m e + <-b, p> + k2 >= 0
84 * with 0 <= k1 + k2 < m
85 * If so return the row number of the upper bound and set *lower
86 * to the row number of the lower bound. If not, return -1.
88 * If the variable at position level occurs in any other constraint,
89 * then we currently return -1. The modulo guard that we would generate
90 * would still be correct, but we would also need to generate
91 * guards corresponding to the other constraints, and this has not
92 * been implemented yet.
94 CloogConstraint
cloog_constraint_set_defining_inequalities(
95 CloogConstraintSet
*bset
,
96 int level
, CloogConstraint
*lower
, int nb_par
)
98 struct isl_constraint
*upper
;
99 struct isl_constraint
*c
;
100 struct cloog_isl_dim dim
;
102 dim
= set_cloog_dim_to_isl_dim(bset
, level
- 1);
103 if (!isl_basic_set_has_defining_inequalities(bset
, dim
.type
, dim
.pos
,
105 return cloog_constraint_invalid();
106 for (c
= isl_basic_set_first_constraint(isl_basic_set_copy(bset
)); c
;
107 c
= isl_constraint_next(c
)) {
108 if (isl_constraint_is_equal(c
, *lower
))
110 if (isl_constraint_is_equal(c
, upper
))
112 if (cloog_constraint_involves(c
, level
-1)) {
113 isl_constraint_free(*lower
);
114 isl_constraint_free(upper
);
116 isl_constraint_free(c
);
123 int cloog_constraint_set_total_dimension(CloogConstraintSet
*constraints
)
125 return isl_basic_set_total_dim(constraints
);
128 int cloog_constraint_set_n_iterators(CloogConstraintSet
*constraints
, int n_par
)
130 return isl_basic_set_n_dim(constraints
);
134 /******************************************************************************
135 * Equalities spreading functions *
136 ******************************************************************************/
139 /* Equalities are stored inside a CloogMatrix data structure called "equal".
140 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
141 * dimensions + 1, the "+ 1" is because a statement can be included inside an
142 * external loop without iteration domain), and (nb_scattering + nb_iterators +
143 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
144 * type). The ith row corresponds to the equality "= 0" for the ith dimension
145 * iterator. The first column gives the equality type (0: no equality, then
146 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
147 * the current level is found, the corresponding row is updated. Then the
148 * equality if it exists is used to simplify expressions (e.g. if we have
149 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
150 * the pprint call, the corresponding row is reset to zero.
153 CloogEqualities
*cloog_equal_alloc(int n
, int nb_levels
, int nb_parameters
)
156 CloogEqualities
*equal
= ALLOC(CloogEqualities
);
158 equal
->total_dim
= nb_levels
- 1 + nb_parameters
;
160 equal
->constraints
= ALLOCN(struct isl_basic_set
*, n
);
161 equal
->types
= ALLOCN(int, n
);
162 for (i
= 0; i
< n
; ++i
) {
163 equal
->constraints
[i
] = NULL
;
164 equal
->types
[i
] = EQTYPE_NONE
;
169 int cloog_equal_total_dimension(CloogEqualities
*equal
)
171 return equal
->total_dim
;
174 void cloog_equal_free(CloogEqualities
*equal
)
178 for (i
= 0; i
< equal
->n
; ++i
)
179 isl_basic_set_free(equal
->constraints
[i
]);
180 free(equal
->constraints
);
185 int cloog_equal_count(CloogEqualities
*equal
)
192 * cloog_constraint_equal_type function :
193 * This function returns the type of the equality in the constraint (line) of
194 * (constraints) for the element (level). An equality is 'constant' iff all
196 * factors are null except the constant one. It is a 'pure item' iff one and
197 * only one factor is non null and is 1 or -1. Otherwise it is an 'affine
200 * i = -13 is constant, i = j, j = -M are pure items,
201 * j = 2*M, i = j+1 are affine expressions.
202 * When the equality comes from a 'one time loop', (line) is ONE_TIME_LOOP.
203 * This case require a specific treatment since we have to study all the
205 * - constraints is the matrix of constraints,
206 * - level is the column number in equal of the element which is 'equal to',
207 * - line is the line number in equal of the constraint we want to study;
208 * if it is -1, all lines must be studied.
210 static int cloog_constraint_equal_type(CloogConstraint constraint
, int level
)
214 int type
= EQTYPE_NONE
;
217 isl_constraint_get_constant(constraint
, &c
);
218 if (!isl_int_is_zero(c
))
219 type
= EQTYPE_CONSTANT
;
220 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_param
); ++i
) {
221 isl_constraint_get_coefficient(constraint
, isl_dim_param
, i
, &c
);
222 if (isl_int_is_zero(c
))
224 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
225 type
!= EQTYPE_NONE
) {
226 type
= EQTYPE_EXAFFINE
;
229 type
= EQTYPE_PUREITEM
;
231 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_set
); ++i
) {
234 isl_constraint_get_coefficient(constraint
, isl_dim_set
, i
, &c
);
235 if (isl_int_is_zero(c
))
237 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
238 type
!= EQTYPE_NONE
) {
239 type
= EQTYPE_EXAFFINE
;
242 type
= EQTYPE_PUREITEM
;
244 for (i
= 0; i
< isl_constraint_dim(constraint
, isl_dim_div
); ++i
) {
245 isl_constraint_get_coefficient(constraint
, isl_dim_div
, i
, &c
);
246 if (isl_int_is_zero(c
))
248 if ((!isl_int_is_one(c
) && !isl_int_is_negone(c
)) ||
249 type
!= EQTYPE_NONE
) {
250 type
= EQTYPE_EXAFFINE
;
253 type
= EQTYPE_PUREITEM
;
257 if (type
== EQTYPE_NONE
)
258 type
= EQTYPE_CONSTANT
;
264 int cloog_equal_type(CloogEqualities
*equal
, int level
)
266 return equal
->types
[level
-1];
271 * cloog_equal_add function:
272 * This function updates the row (level-1) of the equality matrix (equal) with
273 * the row that corresponds to the row (line) of the matrix (matrix).
274 * - equal is the matrix of equalities,
275 * - matrix is the matrix of constraints,
276 * - level is the column number in matrix of the element which is 'equal to',
277 * - line is the line number in matrix of the constraint we want to study,
278 * - the infos structure gives the user all options on code printing and more.
280 * line is set to and invalid constraint for equalities that CLooG itself has
281 * discovered because the lower and upper bound of a loop happened to be equal.
282 * This situation shouldn't happen in the isl port since isl should
283 * have found the equality itself.
285 void cloog_equal_add(CloogEqualities
*equal
, CloogConstraintSet
*matrix
,
286 int level
, CloogConstraint line
, int nb_par
)
288 struct isl_basic_set
*bset
;
290 assert(cloog_constraint_is_valid(line
));
292 equal
->types
[level
-1] = cloog_constraint_equal_type(line
, level
);
293 bset
= isl_basic_set_from_constraint(isl_constraint_copy(line
));
294 nparam
= isl_basic_set_n_param(bset
);
295 bset
= isl_basic_set_extend(bset
, nparam
,
296 equal
->total_dim
- nparam
, 0, 0, 0);
297 bset
= isl_basic_set_finalize(bset
);
298 equal
->constraints
[level
-1] = bset
;
303 * cloog_equal_del function :
304 * This function reset the equality corresponding to the iterator (level)
305 * in the equality matrix (equal).
306 * - July 2nd 2002: first version.
308 void cloog_equal_del(CloogEqualities
*equal
, int level
)
310 equal
->types
[level
-1] = EQTYPE_NONE
;
311 isl_basic_set_free(equal
->constraints
[level
-1]);
312 equal
->constraints
[level
-1] = NULL
;
317 /******************************************************************************
318 * Processing functions *
319 ******************************************************************************/
322 * Function cloog_constraint_set_normalize:
323 * This function will modify the constraint system in such a way that when
324 * there is an equality depending on the element at level 'level', there are
325 * no more (in)equalities depending on this element.
327 * The simplified form of isl automatically satisfies this condition.
329 void cloog_constraint_set_normalize(CloogConstraintSet
*matrix
, int level
)
336 * cloog_constraint_set_copy function:
337 * this functions builds and returns a "hard copy" (not a pointer copy) of a
338 * CloogConstraintSet data structure.
340 CloogConstraintSet
*cloog_constraint_set_copy(CloogConstraintSet
*bset
)
342 return isl_basic_set_dup(bset
);
347 * cloog_constraint_set_simplify function:
348 * this function simplify all constraints inside the matrix "matrix" thanks to
349 * an equality matrix "equal" that gives for some elements of the affine
350 * constraint an equality with other elements, preferably constants.
351 * For instance, if a row of the matrix contains i+j+3>=0 and the equality
352 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
353 * simplified constraints are returned back inside a new simplified matrix.
354 * - matrix is the set of constraints to simplify,
355 * - equal is the matrix of equalities,
356 * - level is a level we don't want to simplify (-1 if none),
357 * - nb_par is the number of parameters of the program.
359 * isl should have performed these simplifications already in isl_set_gist.
361 CloogConstraintSet
*cloog_constraint_set_simplify(CloogConstraintSet
*matrix
,
362 CloogEqualities
*equal
, int level
, int nb_par
)
364 return cloog_constraint_set_copy(matrix
);
368 static struct cloog_isl_dim
constraint_cloog_dim_to_isl_dim(
369 CloogConstraint constraint
, int pos
)
371 enum isl_dim_type types
[] = { isl_dim_set
, isl_dim_div
, isl_dim_param
};
373 struct cloog_isl_dim ci_dim
;
375 for (i
= 0; i
< 3; ++i
) {
376 unsigned dim
= isl_constraint_dim(constraint
, types
[i
]);
378 ci_dim
.type
= types
[i
];
387 static struct clast_expr
*div_expr(CloogConstraint constraint
, int pos
,
391 unsigned dim
= cloog_constraint_total_dimension(constraint
);
393 struct clast_reduction
*r
;
394 struct clast_expr
*e
= NULL
;
397 div
= isl_constraint_div(constraint
, pos
);
400 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
401 struct cloog_isl_dim dim
;
403 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
404 isl_div_get_coefficient(div
, dim
.type
, dim
.pos
, &c
);
405 if (!cloog_int_is_zero(c
))
408 isl_div_get_constant(div
, &c
);
409 if (!cloog_int_is_zero(c
))
412 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
413 for (i
= 0, nb_elts
= 0; i
< dim
; ++i
) {
414 struct clast_expr
*v
;
415 struct cloog_isl_dim dim
;
417 dim
= constraint_cloog_dim_to_isl_dim(constraint
, i
);
418 isl_div_get_coefficient(div
, dim
.type
, dim
.pos
, &c
);
419 if (cloog_int_is_zero(c
))
422 v
= cloog_constraint_variable_expr(constraint
, 1 + i
, names
);
424 r
->elts
[nb_elts
++] = &new_clast_term(c
, v
)->expr
;
426 isl_div_get_constant(div
, &c
);
427 if (!cloog_int_is_zero(c
))
428 r
->elts
[nb_elts
++] = &new_clast_term(c
, NULL
)->expr
;
430 isl_div_get_denominator(div
, &c
);
431 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, c
)->expr
;
439 * Return clast_expr corresponding to the variable "level" (1 based) in
440 * the given constraint.
442 struct clast_expr
*cloog_constraint_variable_expr(CloogConstraint constraint
,
443 int level
, CloogNames
*names
)
445 struct cloog_isl_dim dim
;
450 dim
= constraint_cloog_dim_to_isl_dim(constraint
, level
- 1);
451 if (dim
.type
== isl_dim_div
)
452 return div_expr(constraint
, dim
.pos
, names
);
454 if (dim
.type
== isl_dim_set
)
455 name
= cloog_names_name_at_level(names
, level
);
457 name
= names
->parameters
[dim
.pos
];
459 return &new_clast_name(name
)->expr
;
464 * Return true if constraint c involves variable v (zero-based).
466 int cloog_constraint_involves(CloogConstraint constraint
, int v
)
472 cloog_constraint_coefficient_get(constraint
, v
, &c
);
473 res
= !isl_int_is_zero(c
);
478 int cloog_constraint_is_lower_bound(CloogConstraint constraint
, int v
)
484 cloog_constraint_coefficient_get(constraint
, v
, &c
);
485 res
= isl_int_is_pos(c
);
490 int cloog_constraint_is_upper_bound(CloogConstraint constraint
, int v
)
496 cloog_constraint_coefficient_get(constraint
, v
, &c
);
497 res
= isl_int_is_neg(c
);
502 int cloog_constraint_is_equality(CloogConstraint constraint
)
504 return isl_constraint_is_equality(constraint
);
507 void cloog_constraint_clear(CloogConstraint constraint
)
509 isl_constraint_clear(constraint
);
512 void cloog_constraint_coefficient_get(CloogConstraint constraint
,
513 int var
, cloog_int_t
*val
)
515 struct cloog_isl_dim dim
;
520 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
521 isl_constraint_get_coefficient(constraint
, dim
.type
, dim
.pos
, val
);
524 void cloog_constraint_coefficient_set(CloogConstraint constraint
,
525 int var
, cloog_int_t val
)
527 struct cloog_isl_dim dim
;
531 dim
= constraint_cloog_dim_to_isl_dim(constraint
, var
);
532 isl_constraint_set_coefficient(constraint
, dim
.type
, dim
.pos
, val
);
535 void cloog_constraint_constant_get(CloogConstraint constraint
, cloog_int_t
*val
)
537 isl_constraint_get_constant(constraint
, val
);
541 * Copy the coefficient of constraint c into dst in PolyLib order,
542 * i.e., first the coefficients of the variables, then the coefficients
543 * of the parameters and finally the constant.
545 void cloog_constraint_copy_coefficients(CloogConstraint constraint
,
551 dim
= isl_constraint_dim(constraint
, isl_dim_all
);
553 for (i
= 0; i
< dim
; ++i
)
554 cloog_constraint_coefficient_get(constraint
, i
, dst
+i
);
555 cloog_constraint_constant_get(constraint
, dst
+dim
);
558 CloogConstraint
cloog_constraint_invalid(void)
563 int cloog_constraint_is_valid(CloogConstraint constraint
)
565 return constraint
!= NULL
;
568 int cloog_constraint_total_dimension(CloogConstraint constraint
)
570 return isl_constraint_dim(constraint
, isl_dim_all
);
573 CloogConstraint
cloog_constraint_first(CloogConstraintSet
*constraints
)
575 return isl_basic_set_first_constraint(isl_basic_set_copy(constraints
));
578 CloogConstraint
cloog_constraint_next(CloogConstraint constraint
)
580 return isl_constraint_next(constraint
);
583 CloogConstraint
cloog_constraint_copy(CloogConstraint constraint
)
585 return isl_constraint_copy(constraint
);
588 void cloog_constraint_release(CloogConstraint constraint
)
590 isl_constraint_free(constraint
);
593 CloogConstraint
cloog_equal_constraint(CloogEqualities
*equal
, int j
)
595 return isl_basic_set_first_constraint(
596 isl_basic_set_copy(equal
->constraints
[j
]));