Get rid of the warning about ignoring the return value of fgets
[cloog.git] / source / isl / constraints.c
blobb03f5d5c0b20100fbe38956be0b659c1eda2ad55
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <ctype.h>
4 #include <cloog/isl/cloog.h>
5 #include <cloog/isl/backend.h>
6 #include <isl/aff.h>
7 #include <isl/set.h>
8 #include <isl/val.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)
17 isl_val *v;
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);
26 #else
27 #error "No integer type defined"
28 #endif
29 return v;
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);
47 #else
48 #error "No integer type defined"
49 #endif
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)
89 isl_basic_set *bset;
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;
96 int pos;
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 };
103 int i;
104 struct cloog_isl_dim ci_dim;
106 for (i = 0; i < 3; ++i) {
107 unsigned dim = isl_basic_set_dim(bset, types[i]);
108 if (pos < dim) {
109 ci_dim.type = types[i];
110 ci_dim.pos = pos;
111 return ci_dim;
113 pos -= dim;
115 assert(0);
118 static struct cloog_isl_dim set_cloog_dim_to_isl_dim(
119 CloogConstraintSet *constraints, int pos)
121 isl_basic_set *bset;
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;
135 isl_basic_set *bset;
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);
141 else
142 return NULL;
146 struct cloog_isl_other {
147 int level;
148 int found;
149 isl_constraint *u;
150 isl_constraint *l;
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;
160 CloogConstraint *cc;
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))
166 other->found = 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,
202 &l, &u))
203 return cloog_constraint_invalid();
205 other.l = l;
206 other.u = u;
207 other.found = 0;
208 other.level = level;
209 isl_basic_set_foreach_constraint(bset, &check_other_constraint, &other);
210 if (other.found) {
211 isl_constraint_free(l);
212 isl_constraint_free(u);
213 *lower = NULL;
214 return NULL;
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)
222 isl_basic_set *bset;
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)
229 isl_basic_set *bset;
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)
256 int i;
257 CloogEqualities *equal = ALLOC(CloogEqualities);
259 equal->total_dim = nb_levels - 1 + nb_parameters;
260 equal->n = n;
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;
267 return equal;
270 int cloog_equal_total_dimension(CloogEqualities *equal)
272 return equal->total_dim;
275 void cloog_equal_free(CloogEqualities *equal)
277 int i;
279 for (i = 0; i < equal->n; ++i)
280 isl_constraint_free(equal->constraints[i]);
281 free(equal->constraints);
282 free(equal->types);
283 free(equal);
286 int cloog_equal_count(CloogEqualities *equal)
288 return equal->n;
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'.
299 * For instance:
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)
308 int i;
309 isl_val *c;
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;
316 isl_val_free(c);
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;
320 isl_val_free(c);
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)){
324 isl_val_free(c);
325 continue;
327 if ((!isl_val_is_one(c) && !isl_val_is_negone(c)) ||
328 type != EQTYPE_NONE) {
329 type = EQTYPE_EXAFFINE;
330 isl_val_free(c);
331 break;
333 type = EQTYPE_PUREITEM;
334 isl_val_free(c);
336 for (i = 0; i < isl_constraint_dim(constraint, isl_dim_set); ++i) {
337 if (i == level - 1)
338 continue;
339 c = isl_constraint_get_coefficient_val(constraint, isl_dim_set, i);
340 if (isl_val_is_zero(c)){
341 isl_val_free(c);
342 continue;
344 if ((!isl_val_is_one(c) && !isl_val_is_negone(c)) ||
345 type != EQTYPE_NONE) {
346 type = EQTYPE_EXAFFINE;
347 isl_val_free(c);
348 break;
350 type = EQTYPE_PUREITEM;
351 isl_val_free(c);
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)){
356 isl_val_free(c);
357 continue;
359 if ((!isl_val_is_one(c) && !isl_val_is_negone(c)) ||
360 type != EQTYPE_NONE) {
361 type = EQTYPE_EXAFFINE;
362 isl_val_free(c);
363 break;
365 type = EQTYPE_PUREITEM;
366 isl_val_free(c);
369 if (type == EQTYPE_NONE)
370 type = EQTYPE_CONSTANT;
372 return type;
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)
400 isl_constraint *c;
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 "soft copy" of a CloogConstraintSet data
445 * structure.
447 * NOTE: this function used to return a "hard copy" (not a pointer copy) but isl
448 * doesn't provide isl_basic_set_dup() anymore and a soft copy works as well.
450 CloogConstraintSet *cloog_constraint_set_copy(CloogConstraintSet *constraints)
452 isl_basic_set *bset;
453 bset = cloog_constraints_set_to_isl(constraints);
454 return cloog_constraint_set_from_isl_basic_set(isl_basic_set_copy(bset));
459 * cloog_constraint_set_simplify function:
460 * this function simplify all constraints inside the matrix "matrix" thanks to
461 * an equality matrix "equal" that gives for some elements of the affine
462 * constraint an equality with other elements, preferably constants.
463 * For instance, if a row of the matrix contains i+j+3>=0 and the equality
464 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
465 * simplified constraints are returned back inside a new simplified matrix.
466 * - matrix is the set of constraints to simplify,
467 * - equal is the matrix of equalities,
468 * - level is a level we don't want to simplify (-1 if none),
469 * - nb_par is the number of parameters of the program.
471 * isl should have performed these simplifications already in isl_set_gist.
473 CloogConstraintSet *cloog_constraint_set_simplify(CloogConstraintSet *matrix,
474 CloogEqualities *equal, int level, int nb_par)
476 return cloog_constraint_set_copy(matrix);
480 static struct cloog_isl_dim constraint_cloog_dim_to_isl_dim(
481 CloogConstraint *constraint, int pos)
483 enum isl_dim_type types[] = { isl_dim_set, isl_dim_div, isl_dim_param };
484 int i;
485 struct cloog_isl_dim ci_dim;
487 for (i = 0; i < 3; ++i) {
488 isl_constraint *c = cloog_constraint_to_isl(constraint);
489 unsigned dim = isl_constraint_dim(c, types[i]);
490 if (pos < dim) {
491 ci_dim.type = types[i];
492 ci_dim.pos = pos;
493 return ci_dim;
495 pos -= dim;
497 assert(0);
500 static struct clast_expr *div_expr(CloogConstraint *constraint, int pos,
501 CloogNames *names)
503 int i, nb_elts;
504 unsigned dim = cloog_constraint_total_dimension(constraint);
505 isl_val *c;
506 struct clast_reduction *r;
507 struct clast_expr *e = NULL;
508 isl_aff *div;
509 cloog_int_t cint;
511 cloog_int_init(cint);
512 div = isl_constraint_get_div(cloog_constraint_to_isl(constraint), pos);
514 for (i = 0, nb_elts = 0; i < dim; ++i) {
515 struct cloog_isl_dim dim;
517 dim = constraint_cloog_dim_to_isl_dim(constraint, i);
518 if (dim.type == isl_dim_set)
519 dim.type = isl_dim_in;
520 c = isl_aff_get_coefficient_val(div, dim.type, dim.pos);
521 if (!isl_val_is_zero(c))
522 ++nb_elts;
524 isl_val_free(c);
526 c = isl_aff_get_constant_val(div);
527 if (!isl_val_is_zero(c))
528 ++nb_elts;
529 isl_val_free(c);
531 r = new_clast_reduction(clast_red_sum, nb_elts);
532 for (i = 0, nb_elts = 0; i < dim; ++i) {
533 struct clast_expr *v;
534 struct cloog_isl_dim dim;
536 dim = constraint_cloog_dim_to_isl_dim(constraint, i);
537 if (dim.type == isl_dim_set)
538 dim.type = isl_dim_in;
539 c = isl_aff_get_coefficient_val(div, dim.type, dim.pos);
540 if (isl_val_is_zero(c)){
541 isl_val_free(c);
542 continue;
545 v = cloog_constraint_variable_expr(constraint, 1 + i, names);
547 /* We are interested only in the numerator */
548 cloog_int_set_si(cint, isl_val_get_num_si(c));
549 r->elts[nb_elts++] = &new_clast_term(cint, v)->expr;
551 isl_val_free(c);
554 c = isl_aff_get_constant_val(div);
555 if (!isl_val_is_zero(c)) {
556 /* We are interested only in the numerator */
557 cloog_int_set_si(cint, isl_val_get_num_si(c));
558 r->elts[nb_elts++] = &new_clast_term(cint, NULL)->expr;
560 isl_val_free(c);
562 c = isl_aff_get_denominator_val(div);
563 isl_val_to_cloog_int(c, &cint);
564 isl_val_free(c);
565 e = &new_clast_binary(clast_bin_fdiv, &r->expr, cint)->expr;
567 cloog_int_clear(cint);
569 isl_aff_free(div);
571 return e;
575 * Return clast_expr corresponding to the variable "level" (1 based) in
576 * the given constraint.
578 struct clast_expr *cloog_constraint_variable_expr(CloogConstraint *constraint,
579 int level, CloogNames *names)
581 struct cloog_isl_dim dim;
582 const char *name;
584 assert(constraint);
586 dim = constraint_cloog_dim_to_isl_dim(constraint, level - 1);
587 if (dim.type == isl_dim_div)
588 return div_expr(constraint, dim.pos, names);
590 if (dim.type == isl_dim_set)
591 name = cloog_names_name_at_level(names, level);
592 else
593 name = names->parameters[dim.pos];
595 return &new_clast_name(name)->expr;
600 * Return true if constraint c involves variable v (zero-based).
602 int cloog_constraint_involves(CloogConstraint *constraint, int v)
604 isl_val *c;
605 int res;
607 c = cloog_constraint_coefficient_get_val(constraint, v);
608 res = !isl_val_is_zero(c);
609 isl_val_free(c);
610 return res;
613 int cloog_constraint_is_lower_bound(CloogConstraint *constraint, int v)
615 isl_val *c;
616 int res;
618 c = cloog_constraint_coefficient_get_val(constraint, v);
619 res = isl_val_is_pos(c);
620 isl_val_free(c);
621 return res;
624 int cloog_constraint_is_upper_bound(CloogConstraint *constraint, int v)
626 isl_val *c;
627 int res;
629 c = cloog_constraint_coefficient_get_val(constraint, v);
630 res = isl_val_is_neg(c);
631 isl_val_free(c);
632 return res;
635 int cloog_constraint_is_equality(CloogConstraint *constraint)
637 return isl_constraint_is_equality(cloog_constraint_to_isl(constraint));
640 CloogConstraintSet *cloog_constraint_set_drop_constraint(
641 CloogConstraintSet *constraints, CloogConstraint *constraint)
643 isl_basic_set *bset;
644 isl_constraint *c;
646 bset = cloog_constraints_set_to_isl(constraints);
647 c = cloog_constraint_to_isl(cloog_constraint_copy(constraint));
648 bset = isl_basic_set_drop_constraint(bset, c);
649 return cloog_constraint_set_from_isl_basic_set(bset);
652 void cloog_constraint_coefficient_get(CloogConstraint *constraint,
653 int var, cloog_int_t *val)
655 struct cloog_isl_dim dim;
656 isl_constraint *c;
657 isl_val *ival;
659 if (!constraint)
660 val = NULL;
662 dim = constraint_cloog_dim_to_isl_dim(constraint, var);
663 c = cloog_constraint_to_isl(constraint);
664 ival = isl_constraint_get_coefficient_val(c, dim.type, dim.pos);
666 isl_val_to_cloog_int(ival, val);
667 isl_val_free(ival);
670 isl_val *cloog_constraint_coefficient_get_val(CloogConstraint *constraint,
671 int var)
673 struct cloog_isl_dim dim;
674 isl_constraint *c;
675 isl_val *val;
677 if (!constraint)
678 return NULL;
680 dim = constraint_cloog_dim_to_isl_dim(constraint, var);
681 c = cloog_constraint_to_isl(constraint);
682 val = isl_constraint_get_coefficient_val(c, dim.type, dim.pos);
683 return val;
688 void cloog_constraint_coefficient_set(CloogConstraint *constraint,
689 int var, cloog_int_t val)
691 struct cloog_isl_dim dim;
692 isl_constraint *c;
694 assert(constraint);
696 dim = constraint_cloog_dim_to_isl_dim(constraint, var);
697 c = cloog_constraint_to_isl(constraint);
698 isl_constraint_set_coefficient_val(c, dim.type, dim.pos,
699 cloog_int_to_isl_val(isl_constraint_get_ctx(c), val));
702 void cloog_constraint_constant_get(CloogConstraint *constraint, cloog_int_t *val)
704 isl_val *ival;
705 ival = isl_constraint_get_constant_val(cloog_constraint_to_isl(constraint));
706 isl_val_to_cloog_int(ival, val);
707 isl_val_free(ival);
711 __isl_give isl_val *cloog_constraint_constant_get_val(CloogConstraint *constraint)
713 return isl_constraint_get_constant_val(cloog_constraint_to_isl(constraint));
719 * Copy the coefficient of constraint c into dst in PolyLib order,
720 * i.e., first the coefficients of the variables, then the coefficients
721 * of the parameters and finally the constant.
723 void cloog_constraint_copy_coefficients(CloogConstraint *constraint,
724 cloog_int_t *dst)
726 int i;
727 unsigned dim;
729 dim = cloog_constraint_total_dimension(constraint);
731 for (i = 0; i < dim; ++i)
732 cloog_constraint_coefficient_get(constraint, i, dst+i);
733 cloog_constraint_constant_get(constraint, dst+dim);
736 CloogConstraint *cloog_constraint_invalid(void)
738 return NULL;
741 int cloog_constraint_is_valid(CloogConstraint *constraint)
743 return constraint != NULL;
746 int cloog_constraint_total_dimension(CloogConstraint *constraint)
748 isl_constraint *c;
749 c = cloog_constraint_to_isl(constraint);
750 return isl_constraint_dim(c, isl_dim_all);
755 * Check whether there is any need for the constraint "upper" on
756 * "level" to get reduced.
757 * In case of the isl backend, there should be no need to do so
758 * if the level corresponds to an existentially quantified variable.
759 * Moreover, the way reduction is performed does not work for such
760 * variables since its position might chance during the construction
761 * of a set for reduction.
763 int cloog_constraint_needs_reduction(CloogConstraint *upper, int level)
765 isl_basic_set *bset;
766 isl_constraint *c;
767 struct cloog_isl_dim dim;
769 c = cloog_constraint_to_isl(upper);
770 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
771 dim = basic_set_cloog_dim_to_isl_dim(bset, level - 1);
772 isl_basic_set_free(bset);
774 return dim.type == isl_dim_set;
779 * Create a CloogConstraintSet containing enough information to perform
780 * a reduction on the upper equality (in this case lower is an invalid
781 * CloogConstraint) or the pair of inequalities upper and lower
782 * from within insert_modulo_guard.
783 * In the isl backend, we return a CloogConstraintSet containing both
784 * bounds, as the stride may change during the reduction and we may
785 * need to recompute the bound on the modulo expression.
787 CloogConstraintSet *cloog_constraint_set_for_reduction(CloogConstraint *upper,
788 CloogConstraint *lower)
790 struct isl_basic_set *bset;
791 isl_constraint *c;
793 c = cloog_constraint_to_isl(upper);
794 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
795 if (cloog_constraint_is_valid(lower)) {
796 c = cloog_constraint_to_isl(lower);
797 bset = isl_basic_set_add_constraint(bset,
798 isl_constraint_copy(c));
800 return cloog_constraint_set_from_isl_basic_set(bset);
804 static int add_constant_term(CloogConstraint *c, void *user)
806 isl_val **bound = (isl_val **)user;
807 isl_val *v;
809 v = cloog_constraint_constant_get_val(c);
810 *bound = isl_val_add(*bound, v);
812 return 0;
816 /* Return an isl_basic_set representation of the equality stored
817 * at position i in the given CloogEqualities.
819 static __isl_give isl_basic_set *equality_to_basic_set(CloogEqualities *equal,
820 int i)
822 isl_constraint *c;
823 isl_basic_set *bset;
824 unsigned nparam;
825 unsigned nvar;
827 c = isl_constraint_copy(equal->constraints[i]);
828 bset = isl_basic_set_from_constraint(c);
829 nparam = isl_basic_set_dim(bset, isl_dim_param);
830 nvar = isl_basic_set_dim(bset, isl_dim_set);
831 bset = isl_basic_set_add_dims(bset, isl_dim_set,
832 equal->total_dim - (nparam + nvar));
833 return bset;
837 * Reduce the modulo guard expressed by "constraints" using equalities
838 * found in outer nesting levels (stored in "equal").
839 * The modulo guard may be an equality or a pair of inequalities.
840 * In case of a pair of inequalities, *bound contains the bound on the
841 * corresponding modulo expression. If any reduction is performed
842 * then this bound is recomputed.
844 * "level" may not correspond to an existentially quantified variable.
846 * We first check if there are any equalities we can use. If not,
847 * there is again nothing to reduce.
848 * For the actual reduction, we use isl_basic_set_gist, but this
849 * function will only perform the reduction we want here if the
850 * the variable that imposes the modulo constraint has been projected
851 * out (i.e., turned into an existentially quantified variable).
852 * After the call to isl_basic_set_gist, we need to move the
853 * existential variable back into the position where the calling
854 * function expects it (assuming there are any constraints left).
855 * We do this by adding an equality between the given dimension and
856 * the existentially quantified variable.
858 * If there are no existentially quantified variables left, then
859 * we don't need to add this equality.
860 * If, on the other hand, the resulting basic set involves more
861 * than one existentially quantified variable, then the caller
862 * will not be able to handle the result, so we just return the
863 * original input instead.
865 CloogConstraintSet *cloog_constraint_set_reduce(CloogConstraintSet *constraints,
866 int level, CloogEqualities *equal, int nb_par, cloog_int_t *bound)
868 int j;
869 isl_space *idim;
870 struct isl_basic_set *eq;
871 struct isl_basic_map *id;
872 struct cloog_isl_dim dim;
873 struct isl_constraint *c;
874 unsigned constraints_dim;
875 unsigned n_div;
876 isl_basic_set *bset, *orig;
878 bset = cloog_constraints_set_to_isl(constraints);
879 orig = isl_basic_set_copy(bset);
880 dim = set_cloog_dim_to_isl_dim(constraints, level - 1);
881 assert(dim.type == isl_dim_set);
883 eq = NULL;
884 for (j = 0; j < level - 1; ++j) {
885 isl_basic_set *bset_j;
886 if (equal->types[j] != EQTYPE_EXAFFINE)
887 continue;
888 bset_j = equality_to_basic_set(equal, j);
889 if (!eq)
890 eq = bset_j;
891 else
892 eq = isl_basic_set_intersect(eq, bset_j);
894 if (!eq) {
895 isl_basic_set_free(orig);
896 return cloog_constraint_set_from_isl_basic_set(bset);
899 idim = isl_space_map_from_set(isl_basic_set_get_space(bset));
900 id = isl_basic_map_identity(idim);
901 id = isl_basic_map_remove_dims(id, isl_dim_out, dim.pos, 1);
902 bset = isl_basic_set_apply(bset, isl_basic_map_copy(id));
903 bset = isl_basic_set_apply(bset, isl_basic_map_reverse(id));
905 constraints_dim = isl_basic_set_dim(bset, isl_dim_set);
906 eq = isl_basic_set_remove_dims(eq, isl_dim_set, constraints_dim,
907 isl_basic_set_dim(eq, isl_dim_set) - constraints_dim);
908 bset = isl_basic_set_gist(bset, eq);
909 n_div = isl_basic_set_dim(bset, isl_dim_div);
910 if (n_div > 1) {
911 isl_basic_set_free(bset);
912 return cloog_constraint_set_from_isl_basic_set(orig);
914 if (n_div < 1) {
915 isl_basic_set_free(orig);
916 return cloog_constraint_set_from_isl_basic_set(bset);
919 c = isl_equality_alloc(isl_basic_set_get_local_space(bset));
920 c = isl_constraint_set_coefficient_si(c, isl_dim_div, 0, 1);
921 c = isl_constraint_set_coefficient_si(c, isl_dim_set, dim.pos, -1);
922 bset = isl_basic_set_add_constraint(bset, c);
924 cloog_int_set_si(*bound, 0);
925 isl_val *v = cloog_int_to_isl_val(isl_basic_set_get_ctx(bset), *bound);
926 constraints = cloog_constraint_set_from_isl_basic_set(bset);
927 cloog_constraint_set_foreach_constraint(constraints,
928 add_constant_term, &v);
929 isl_val_to_cloog_int(v, bound); //return the value to bound
931 isl_val_free(v);
932 isl_basic_set_free(orig);
933 return cloog_constraint_set_from_isl_basic_set(bset);
936 CloogConstraint *cloog_constraint_copy(CloogConstraint *constraint)
938 return cloog_constraint_from_isl_constraint(
939 isl_constraint_copy(cloog_constraint_to_isl(constraint)));
942 void cloog_constraint_release(CloogConstraint *constraint)
944 isl_constraint_free(cloog_constraint_to_isl(constraint));
947 struct cloog_isl_foreach {
948 int (*fn)(CloogConstraint *constraint, void *user);
949 void *user;
952 static int cloog_isl_foreach_cb(__isl_take isl_constraint *c, void *user)
954 struct cloog_isl_foreach *data = (struct cloog_isl_foreach *)user;
955 int ret;
957 if (isl_constraint_is_div_constraint(c)) {
958 isl_constraint_free(c);
959 return 0;
962 ret = data->fn(cloog_constraint_from_isl_constraint(c), data->user);
964 isl_constraint_free(c);
966 return ret;
969 int cloog_constraint_set_foreach_constraint(CloogConstraintSet *constraints,
970 int (*fn)(CloogConstraint *constraint, void *user), void *user)
972 struct cloog_isl_foreach data = { fn, user };
973 isl_basic_set *bset;
975 bset = cloog_constraints_set_to_isl(constraints);
976 return isl_basic_set_foreach_constraint(bset,
977 cloog_isl_foreach_cb, &data);
980 CloogConstraint *cloog_equal_constraint(CloogEqualities *equal, int j)
982 isl_constraint *c;
984 c = isl_constraint_copy(equal->constraints[j]);
985 return cloog_constraint_from_isl_constraint(c);
988 /* Given a stride constraint on iterator i (specified by level) of the form
990 * i = f(outer iterators) + stride * f(existentials)
992 * extract f as an isl_aff.
994 static isl_aff *extract_stride_offset(__isl_keep isl_constraint *c,
995 int level, CloogStride *stride)
997 int i;
998 isl_space *dim = isl_constraint_get_space(c);
999 isl_local_space *ls = isl_local_space_from_space(dim);
1000 isl_aff *offset = isl_aff_zero_on_domain(ls);
1001 isl_val *u;
1002 unsigned nparam, nvar;
1004 nparam = isl_constraint_dim(c, isl_dim_param);
1005 nvar = isl_constraint_dim(c, isl_dim_set);
1007 for (i = 0; i < nparam; ++i) {
1008 u = isl_constraint_get_coefficient_val(c, isl_dim_param, i);
1009 u = isl_val_mul(u, cloog_int_to_isl_val(isl_constraint_get_ctx(c), stride->factor));
1010 offset = isl_aff_set_coefficient_val(offset, isl_dim_param, i, u);
1012 for (i = 0; i < nvar; ++i) {
1013 if (i == level - 1)
1014 continue;
1015 u = isl_constraint_get_coefficient_val(c, isl_dim_set, i);
1016 u = isl_val_mul(u, cloog_int_to_isl_val(isl_constraint_get_ctx(c), stride->factor));
1017 offset = isl_aff_set_coefficient_val(offset, isl_dim_in, i, u);
1019 u = isl_constraint_get_constant_val(c);
1020 u = isl_val_mul(u, cloog_int_to_isl_val(isl_constraint_get_ctx(c), stride->factor));
1021 offset = isl_aff_set_constant_val(offset, u);
1023 return offset;
1026 /* Update the given lower bound on level such that it satisfies the stride
1027 * constraint. The computation performed here is essentially the same
1028 * as that performed in constraint_stride_lower_c.
1030 * We update the constraint
1032 * a i + f >= 0
1034 * to
1036 * i >= s * ceil((-f/a - d)/s) + d
1038 * with s the stride and d the offset encoded in the stride constraint.
1040 CloogConstraint *cloog_constraint_stride_lower_bound(CloogConstraint *c,
1041 int level, CloogStride *stride)
1043 isl_constraint *stride_c = cloog_constraint_to_isl(stride->constraint);
1044 isl_constraint *bound = cloog_constraint_to_isl(c);
1045 isl_aff *offset;
1046 isl_aff *lower;
1048 lower = isl_constraint_get_bound(bound, isl_dim_set, level - 1);
1049 isl_constraint_free(bound);
1051 offset = extract_stride_offset(stride_c, level, stride);
1053 lower = isl_aff_sub(lower, isl_aff_copy(offset));
1054 lower = isl_aff_scale_down_val(lower, cloog_int_to_isl_val(isl_constraint_get_ctx(stride_c), stride->stride));
1055 lower = isl_aff_ceil(lower);
1056 lower = isl_aff_scale_val(lower, cloog_int_to_isl_val(isl_constraint_get_ctx(stride_c), stride->stride));
1057 lower = isl_aff_add(lower, offset);
1058 lower = isl_aff_neg(lower);
1059 lower = isl_aff_add_coefficient_si(lower, isl_dim_in, level - 1, 1);
1061 bound = isl_inequality_from_aff(lower);
1063 return cloog_constraint_from_isl_constraint(bound);