4 #include "../include/cloog/cloog.h"
6 #define ALLOC(type) (type*)malloc(sizeof(type))
7 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
10 * CloogInfos structure:
11 * this structure contains all the informations necessary for pretty printing,
12 * they come from the original CloogProgram structure (language, names), from
13 * genereral options (options) or are built only for pretty printing (stride).
14 * This structure is mainly there to reduce the number of function parameters,
15 * since most pprint.c functions need most of its field.
18 CloogState
*state
; /**< State. */
20 int stride_level
; /**< Number of valid entries in stride array. */
21 int nb_scattdims
; /**< Scattering dimension number. */
22 int * scaldims
; /**< Boolean array saying whether a given
23 * scattering dimension is scalar or not.
25 CloogNames
* names
; /**< Names of iterators and parameters. */
26 CloogOptions
* options
; /**< Options on CLooG's behaviour. */
27 CloogEqualities
*equal
; /**< Matrix of equalities. */
30 typedef struct clooginfos CloogInfos
;
32 static int clast_expr_cmp(struct clast_expr
*e1
, struct clast_expr
*e2
);
33 static int clast_term_cmp(struct clast_term
*t1
, struct clast_term
*t2
);
34 static int clast_binary_cmp(struct clast_binary
*b1
, struct clast_binary
*b2
);
35 static int clast_reduction_cmp(struct clast_reduction
*r1
,
36 struct clast_reduction
*r2
);
38 static struct clast_expr
*clast_expr_copy(struct clast_expr
*e
);
40 static int clast_equal_add(CloogEqualities
*equal
,
41 CloogConstraintSet
*constraints
,
42 int level
, CloogConstraint
*constraint
,
45 static struct clast_stmt
*clast_equal(int level
, CloogInfos
*infos
);
46 static struct clast_expr
*clast_minmax(CloogConstraintSet
*constraints
,
47 int level
, int max
, int guard
,
48 int lower_bound
, int no_earlier
,
50 static void insert_guard(CloogConstraintSet
*constraints
, int level
,
51 struct clast_stmt
***next
, CloogInfos
*infos
);
52 static int insert_modulo_guard(CloogConstraint
*upper
,
53 CloogConstraint
*lower
, int level
,
54 struct clast_stmt
***next
, CloogInfos
*infos
);
55 static int insert_equation(CloogDomain
*domain
, CloogConstraint
*upper
,
56 CloogConstraint
*lower
, int level
,
57 struct clast_stmt
***next
, CloogInfos
*infos
);
58 static int insert_for(CloogDomain
*domain
, CloogConstraintSet
*constraints
,
59 int level
, int otl
, struct clast_stmt
***next
,
61 static void insert_block(CloogDomain
*domain
, CloogBlock
*block
, int level
,
62 struct clast_stmt
***next
, CloogInfos
*infos
);
63 static void insert_loop(CloogLoop
* loop
, int level
,
64 struct clast_stmt
***next
, CloogInfos
*infos
);
67 struct clast_name
*new_clast_name(const char *name
)
69 struct clast_name
*n
= malloc(sizeof(struct clast_name
));
70 n
->expr
.type
= clast_expr_name
;
75 struct clast_term
*new_clast_term(cloog_int_t c
, struct clast_expr
*v
)
77 struct clast_term
*t
= malloc(sizeof(struct clast_term
));
78 t
->expr
.type
= clast_expr_term
;
79 cloog_int_init(t
->val
);
80 cloog_int_set(t
->val
, c
);
85 struct clast_binary
*new_clast_binary(enum clast_bin_type t
,
86 struct clast_expr
*lhs
, cloog_int_t rhs
)
88 struct clast_binary
*b
= malloc(sizeof(struct clast_binary
));
89 b
->expr
.type
= clast_expr_bin
;
92 cloog_int_init(b
->RHS
);
93 cloog_int_set(b
->RHS
, rhs
);
97 struct clast_reduction
*new_clast_reduction(enum clast_red_type t
, int n
)
100 struct clast_reduction
*r
;
101 r
= malloc(sizeof(struct clast_reduction
)+(n
-1)*sizeof(struct clast_expr
*));
102 r
->expr
.type
= clast_expr_red
;
105 for (i
= 0; i
< n
; ++i
)
110 static void free_clast_root(struct clast_stmt
*s
);
112 const struct clast_stmt_op stmt_root
= { free_clast_root
};
114 static void free_clast_root(struct clast_stmt
*s
)
116 struct clast_root
*r
= (struct clast_root
*)s
;
117 assert(CLAST_STMT_IS_A(s
, stmt_root
));
118 cloog_names_free(r
->names
);
122 struct clast_root
*new_clast_root(CloogNames
*names
)
124 struct clast_root
*r
= malloc(sizeof(struct clast_root
));
125 r
->stmt
.op
= &stmt_root
;
127 r
->names
= cloog_names_copy(names
);
131 static void free_clast_assignment(struct clast_stmt
*s
);
133 const struct clast_stmt_op stmt_ass
= { free_clast_assignment
};
135 static void free_clast_assignment(struct clast_stmt
*s
)
137 struct clast_assignment
*a
= (struct clast_assignment
*)s
;
138 assert(CLAST_STMT_IS_A(s
, stmt_ass
));
139 free_clast_expr(a
->RHS
);
143 struct clast_assignment
*new_clast_assignment(const char *lhs
,
144 struct clast_expr
*rhs
)
146 struct clast_assignment
*a
= malloc(sizeof(struct clast_assignment
));
147 a
->stmt
.op
= &stmt_ass
;
154 static void free_clast_user_stmt(struct clast_stmt
*s
);
156 const struct clast_stmt_op stmt_user
= { free_clast_user_stmt
};
158 static void free_clast_user_stmt(struct clast_stmt
*s
)
160 struct clast_user_stmt
*u
= (struct clast_user_stmt
*)s
;
161 assert(CLAST_STMT_IS_A(s
, stmt_user
));
162 cloog_domain_free(u
->domain
);
163 cloog_statement_free(u
->statement
);
164 cloog_clast_free(u
->substitutions
);
168 struct clast_user_stmt
*new_clast_user_stmt(CloogDomain
*domain
,
169 CloogStatement
*stmt
, struct clast_stmt
*subs
)
171 struct clast_user_stmt
*u
= malloc(sizeof(struct clast_user_stmt
));
172 u
->stmt
.op
= &stmt_user
;
174 u
->domain
= cloog_domain_copy(domain
);
175 u
->statement
= cloog_statement_copy(stmt
);
176 u
->substitutions
= subs
;
180 static void free_clast_block(struct clast_stmt
*b
);
182 const struct clast_stmt_op stmt_block
= { free_clast_block
};
184 static void free_clast_block(struct clast_stmt
*s
)
186 struct clast_block
*b
= (struct clast_block
*)s
;
187 assert(CLAST_STMT_IS_A(s
, stmt_block
));
188 cloog_clast_free(b
->body
);
192 struct clast_block
*new_clast_block()
194 struct clast_block
*b
= malloc(sizeof(struct clast_block
));
195 b
->stmt
.op
= &stmt_block
;
201 static void free_clast_for(struct clast_stmt
*s
);
203 const struct clast_stmt_op stmt_for
= { free_clast_for
};
205 static void free_clast_for(struct clast_stmt
*s
)
207 struct clast_for
*f
= (struct clast_for
*)s
;
208 assert(CLAST_STMT_IS_A(s
, stmt_for
));
209 cloog_domain_free(f
->domain
);
210 free_clast_expr(f
->LB
);
211 free_clast_expr(f
->UB
);
212 cloog_int_clear(f
->stride
);
213 cloog_clast_free(f
->body
);
214 if (f
->private_vars
) free(f
->private_vars
);
215 if (f
->reduction_vars
) free(f
->reduction_vars
);
219 struct clast_for
*new_clast_for(CloogDomain
*domain
, const char *it
,
220 struct clast_expr
*LB
, struct clast_expr
*UB
,
223 struct clast_for
*f
= malloc(sizeof(struct clast_for
));
224 f
->stmt
.op
= &stmt_for
;
226 f
->domain
= cloog_domain_copy(domain
);
231 f
->parallel
= CLAST_PARALLEL_NOT
;
232 f
->private_vars
= NULL
;
233 f
->reduction_vars
= NULL
;
234 cloog_int_init(f
->stride
);
236 cloog_int_set(f
->stride
, stride
->stride
);
238 cloog_int_set_si(f
->stride
, 1);
242 static void free_clast_guard(struct clast_stmt
*s
);
244 const struct clast_stmt_op stmt_guard
= { free_clast_guard
};
246 static void free_clast_guard(struct clast_stmt
*s
)
249 struct clast_guard
*g
= (struct clast_guard
*)s
;
250 assert(CLAST_STMT_IS_A(s
, stmt_guard
));
251 cloog_clast_free(g
->then
);
252 for (i
= 0; i
< g
->n
; ++i
) {
253 free_clast_expr(g
->eq
[i
].LHS
);
254 free_clast_expr(g
->eq
[i
].RHS
);
259 struct clast_guard
*new_clast_guard(int n
)
262 struct clast_guard
*g
= malloc(sizeof(struct clast_guard
) +
263 (n
-1) * sizeof(struct clast_equation
));
264 g
->stmt
.op
= &stmt_guard
;
268 for (i
= 0; i
< n
; ++i
) {
275 void free_clast_name(struct clast_name
*n
)
280 void free_clast_term(struct clast_term
*t
)
282 cloog_int_clear(t
->val
);
283 free_clast_expr(t
->var
);
287 void free_clast_binary(struct clast_binary
*b
)
289 cloog_int_clear(b
->RHS
);
290 free_clast_expr(b
->LHS
);
294 void free_clast_reduction(struct clast_reduction
*r
)
297 for (i
= 0; i
< r
->n
; ++i
)
298 free_clast_expr(r
->elts
[i
]);
302 void free_clast_expr(struct clast_expr
*e
)
307 case clast_expr_name
:
308 free_clast_name((struct clast_name
*) e
);
310 case clast_expr_term
:
311 free_clast_term((struct clast_term
*) e
);
314 free_clast_reduction((struct clast_reduction
*) e
);
317 free_clast_binary((struct clast_binary
*) e
);
324 void free_clast_stmt(struct clast_stmt
*s
)
331 void cloog_clast_free(struct clast_stmt
*s
)
333 struct clast_stmt
*next
;
341 static int clast_name_cmp(struct clast_name
*n1
, struct clast_name
*n2
)
343 return n1
->name
== n2
->name
? 0 : strcmp(n1
->name
, n2
->name
);
346 static int clast_term_cmp(struct clast_term
*t1
, struct clast_term
*t2
)
349 if (!t1
->var
&& t2
->var
)
351 if (t1
->var
&& !t2
->var
)
353 c
= clast_expr_cmp(t1
->var
, t2
->var
);
356 return cloog_int_cmp(t1
->val
, t2
->val
);
359 static int clast_binary_cmp(struct clast_binary
*b1
, struct clast_binary
*b2
)
363 if (b1
->type
!= b2
->type
)
364 return b1
->type
- b2
->type
;
365 if ((c
= cloog_int_cmp(b1
->RHS
, b2
->RHS
)))
367 return clast_expr_cmp(b1
->LHS
, b2
->LHS
);
370 static int clast_reduction_cmp(struct clast_reduction
*r1
, struct clast_reduction
*r2
)
375 if (r1
->n
== 1 && r2
->n
== 1)
376 return clast_expr_cmp(r1
->elts
[0], r2
->elts
[0]);
377 if (r1
->type
!= r2
->type
)
378 return r1
->type
- r2
->type
;
380 return r1
->n
- r2
->n
;
381 for (i
= 0; i
< r1
->n
; ++i
)
382 if ((c
= clast_expr_cmp(r1
->elts
[i
], r2
->elts
[i
])))
387 static int clast_expr_cmp(struct clast_expr
*e1
, struct clast_expr
*e2
)
395 if (e1
->type
!= e2
->type
)
396 return e1
->type
- e2
->type
;
398 case clast_expr_name
:
399 return clast_name_cmp((struct clast_name
*) e1
,
400 (struct clast_name
*) e2
);
401 case clast_expr_term
:
402 return clast_term_cmp((struct clast_term
*) e1
,
403 (struct clast_term
*) e2
);
405 return clast_binary_cmp((struct clast_binary
*) e1
,
406 (struct clast_binary
*) e2
);
408 return clast_reduction_cmp((struct clast_reduction
*) e1
,
409 (struct clast_reduction
*) e2
);
415 int clast_expr_equal(struct clast_expr
*e1
, struct clast_expr
*e2
)
417 return clast_expr_cmp(e1
, e2
) == 0;
421 * Return 1 is both expressions are constant terms and e1 is bigger than e2.
423 int clast_expr_is_bigger_constant(struct clast_expr
*e1
, struct clast_expr
*e2
)
425 struct clast_term
*t1
, *t2
;
426 struct clast_reduction
*r
;
430 if (e1
->type
== clast_expr_red
) {
431 r
= (struct clast_reduction
*)e1
;
432 return r
->n
== 1 && clast_expr_is_bigger_constant(r
->elts
[0], e2
);
434 if (e2
->type
== clast_expr_red
) {
435 r
= (struct clast_reduction
*)e2
;
436 return r
->n
== 1 && clast_expr_is_bigger_constant(e1
, r
->elts
[0]);
438 if (e1
->type
!= clast_expr_term
|| e2
->type
!= clast_expr_term
)
440 t1
= (struct clast_term
*)e1
;
441 t2
= (struct clast_term
*)e2
;
442 if (t1
->var
|| t2
->var
)
444 return cloog_int_gt(t1
->val
, t2
->val
);
447 static int qsort_expr_cmp(const void *p1
, const void *p2
)
449 return clast_expr_cmp(*(struct clast_expr
**)p1
, *(struct clast_expr
**)p2
);
452 static void clast_reduction_sort(struct clast_reduction
*r
)
454 qsort(&r
->elts
[0], r
->n
, sizeof(struct clast_expr
*), qsort_expr_cmp
);
457 static int qsort_eq_cmp(const void *p1
, const void *p2
)
459 struct clast_equation
*eq1
= (struct clast_equation
*)p1
;
460 struct clast_equation
*eq2
= (struct clast_equation
*)p2
;
463 cmp
= clast_expr_cmp(eq1
->LHS
, eq2
->LHS
);
467 cmp
= clast_expr_cmp(eq1
->RHS
, eq2
->RHS
);
471 return eq1
->sign
- eq2
->sign
;
475 * Sort equations in a clast_guard.
477 static void clast_guard_sort(struct clast_guard
*g
)
479 qsort(&g
->eq
[0], g
->n
, sizeof(struct clast_equation
), qsort_eq_cmp
);
484 * Construct a (deep) copy of an expression clast.
486 static struct clast_expr
*clast_expr_copy(struct clast_expr
*e
)
491 case clast_expr_name
: {
492 struct clast_name
* n
= (struct clast_name
*) e
;
493 return &new_clast_name(n
->name
)->expr
;
495 case clast_expr_term
: {
496 struct clast_term
* t
= (struct clast_term
*) e
;
497 return &new_clast_term(t
->val
, clast_expr_copy(t
->var
))->expr
;
499 case clast_expr_red
: {
501 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
502 struct clast_reduction
*r2
= new_clast_reduction(r
->type
, r
->n
);
503 for (i
= 0; i
< r
->n
; ++i
)
504 r2
->elts
[i
] = clast_expr_copy(r
->elts
[i
]);
507 case clast_expr_bin
: {
508 struct clast_binary
*b
= (struct clast_binary
*) e
;
509 return &new_clast_binary(b
->type
, clast_expr_copy(b
->LHS
), b
->RHS
)->expr
;
517 /******************************************************************************
518 * Equalities spreading functions *
519 ******************************************************************************/
523 * clast_equal_allow function:
524 * This function checks whether the options allow us to spread the equality or
525 * not. It returns 1 if so, 0 otherwise.
526 * - equal is the matrix of equalities,
527 * - level is the column number in equal of the element which is 'equal to',
528 * - line is the line number in equal of the constraint we want to study,
529 * - the infos structure gives the user all options on code printing and more.
531 * - October 27th 2005: first version (extracted from old pprint_equal_add).
533 static int clast_equal_allow(CloogEqualities
*equal
, int level
, int line
,
536 if (level
< infos
->options
->fsp
)
539 if ((cloog_equal_type(equal
, level
) == EQTYPE_EXAFFINE
) &&
540 !infos
->options
->esp
)
548 * clast_equal_add function:
549 * This function updates the row (level-1) of the equality matrix (equal) with
550 * the row that corresponds to the row (line) of the matrix (matrix). It returns
551 * 1 if the row can be updated, 0 otherwise.
552 * - equal is the matrix of equalities,
553 * - matrix is the matrix of constraints,
554 * - level is the column number in matrix of the element which is 'equal to',
555 * - line is the line number in matrix of the constraint we want to study,
556 * - the infos structure gives the user all options on code printing and more.
558 static int clast_equal_add(CloogEqualities
*equal
,
559 CloogConstraintSet
*constraints
,
560 int level
, CloogConstraint
*constraint
,
563 cloog_equal_add(equal
, constraints
, level
, constraint
,
564 infos
->names
->nb_parameters
);
566 return clast_equal_allow(equal
, level
, level
-1, infos
);
572 * clast_equal function:
573 * This function prints the substitution data of a statement into a clast_stmt.
574 * Using this function instead of pprint_equal is useful for generating
575 * a compilable pseudo-code by using preprocessor macro for each statement.
576 * By opposition to pprint_equal, the result is less human-readable. For
577 * instance this function will print (i,i+3,k,3) where pprint_equal would
578 * return (j=i+3,l=3).
579 * - level is the number of loops enclosing the statement,
580 * - the infos structure gives the user all options on code printing and more.
582 * - March 12th 2004: first version.
583 * - November 21th 2005: (debug) now works well with GMP version.
585 static struct clast_stmt
*clast_equal(int level
, CloogInfos
*infos
)
588 struct clast_expr
*e
;
589 struct clast_stmt
*a
= NULL
;
590 struct clast_stmt
**next
= &a
;
591 CloogEqualities
*equal
= infos
->equal
;
592 CloogConstraint
*equal_constraint
;
594 for (i
=infos
->names
->nb_scattering
;i
<level
-1;i
++)
595 { if (cloog_equal_type(equal
, i
+1)) {
596 equal_constraint
= cloog_equal_constraint(equal
, i
);
597 e
= clast_bound_from_constraint(equal_constraint
, i
+1, infos
->names
);
598 cloog_constraint_release(equal_constraint
);
600 e
= &new_clast_term(infos
->state
->one
, &new_clast_name(
601 cloog_names_name_at_level(infos
->names
, i
+1))->expr
)->expr
;
603 *next
= &new_clast_assignment(NULL
, e
)->stmt
;
604 next
= &(*next
)->next
;
612 * clast_bound_from_constraint function:
613 * This function returns a clast_expr containing the printing of the
614 * 'right part' of a constraint according to an element.
615 * For instance, for the constraint -3*i + 2*j - M >=0 and the element j,
616 * we have j >= (3*i + M)/2. As we are looking for integral solutions, this
617 * function should return 'ceild(3*i+M,2)'.
618 * - matrix is the polyhedron containing all the constraints,
619 * - line_num is the line number in domain of the constraint we want to print,
620 * - level is the column number in domain of the element we want to use,
621 * - names structure gives the user some options about code printing,
622 * the number of parameters in domain (nb_par), and the arrays of iterator
623 * names and parameters (iters and params).
625 * - November 2nd 2001: first version.
626 * - June 27th 2003: 64 bits version ready.
628 struct clast_expr
*clast_bound_from_constraint(CloogConstraint
*constraint
,
629 int level
, CloogNames
*names
)
631 int i
, sign
, nb_elts
=0, len
;
632 cloog_int_t
*line
, numerator
, denominator
, temp
, division
;
633 struct clast_expr
*e
= NULL
;
634 struct cloog_vec
*line_vector
;
636 len
= cloog_constraint_total_dimension(constraint
) + 2;
637 line_vector
= cloog_vec_alloc(len
);
638 line
= line_vector
->p
;
639 cloog_constraint_copy_coefficients(constraint
, line
+1);
640 cloog_int_init(temp
);
641 cloog_int_init(numerator
);
642 cloog_int_init(denominator
);
644 if (!cloog_int_is_zero(line
[level
])) {
645 struct clast_reduction
*r
;
646 /* Maybe we need to invert signs in such a way that the element sign is>0.*/
647 sign
= -cloog_int_sgn(line
[level
]);
649 for (i
= 1, nb_elts
= 0; i
<= len
- 1; ++i
)
650 if (i
!= level
&& !cloog_int_is_zero(line
[i
]))
652 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
655 /* First, we have to print the iterators and the parameters. */
656 for (i
= 1; i
<= len
- 2; i
++) {
657 struct clast_expr
*v
;
659 if (i
== level
|| cloog_int_is_zero(line
[i
]))
662 v
= cloog_constraint_variable_expr(constraint
, i
, names
);
665 cloog_int_neg(temp
,line
[i
]);
667 cloog_int_set(temp
,line
[i
]);
669 r
->elts
[nb_elts
++] = &new_clast_term(temp
, v
)->expr
;
673 cloog_int_neg(numerator
, line
[len
- 1]);
674 cloog_int_set(denominator
, line
[level
]);
677 cloog_int_set(numerator
, line
[len
- 1]);
678 cloog_int_neg(denominator
, line
[level
]);
681 /* Finally, the constant, and the final printing. */
683 if (!cloog_int_is_zero(numerator
))
684 r
->elts
[nb_elts
++] = &new_clast_term(numerator
, NULL
)->expr
;
686 if (!cloog_int_is_one(line
[level
]) && !cloog_int_is_neg_one(line
[level
]))
687 { if (!cloog_constraint_is_equality(constraint
))
688 { if (cloog_int_is_pos(line
[level
]))
689 e
= &new_clast_binary(clast_bin_cdiv
, &r
->expr
, denominator
)->expr
;
691 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, denominator
)->expr
;
693 e
= &new_clast_binary(clast_bin_div
, &r
->expr
, denominator
)->expr
;
698 free_clast_reduction(r
);
699 if (cloog_int_is_zero(numerator
))
700 e
= &new_clast_term(numerator
, NULL
)->expr
;
702 { if (!cloog_int_is_one(denominator
))
703 { if (!cloog_constraint_is_equality(constraint
)) { /* useful? */
704 if (cloog_int_is_divisible_by(numerator
, denominator
)) {
705 cloog_int_divexact(temp
, numerator
, denominator
);
706 e
= &new_clast_term(temp
, NULL
)->expr
;
709 cloog_int_init(division
);
710 cloog_int_tdiv_q(division
, numerator
, denominator
);
711 if (cloog_int_is_neg(numerator
)) {
712 if (cloog_int_is_pos(line
[level
])) {
714 e
= &new_clast_term(division
, NULL
)->expr
;
717 cloog_int_sub_ui(temp
, division
, 1);
718 e
= &new_clast_term(temp
, NULL
)->expr
;
722 { if (cloog_int_is_pos(line
[level
]))
723 { /* nb>0 need max */
724 cloog_int_add_ui(temp
, division
, 1);
725 e
= &new_clast_term(temp
, NULL
)->expr
;
729 e
= &new_clast_term(division
, NULL
)->expr
;
731 cloog_int_clear(division
);
735 e
= &new_clast_binary(clast_bin_div
,
736 &new_clast_term(numerator
, NULL
)->expr
,
740 e
= &new_clast_term(numerator
, NULL
)->expr
;
745 cloog_vec_free(line_vector
);
747 cloog_int_clear(temp
);
748 cloog_int_clear(numerator
);
749 cloog_int_clear(denominator
);
755 /* Temporary structure for communication between clast_minmax and
756 * its cloog_constraint_set_foreach_constraint callback functions.
758 struct clast_minmax_data
{
766 struct clast_reduction
*r
;
770 /* Should constraint "c" be considered by clast_minmax?
772 * If d->no_earlier is set, then the constraint may not involve
773 * any earlier variables.
775 static int valid_bound(CloogConstraint
*c
, struct clast_minmax_data
*d
)
779 if (d
->max
&& !cloog_constraint_is_lower_bound(c
, d
->level
- 1))
781 if (!d
->max
&& !cloog_constraint_is_upper_bound(c
, d
->level
- 1))
783 if (cloog_constraint_is_equality(c
))
785 if (d
->guard
&& cloog_constraint_involves(c
, d
->guard
- 1))
789 for (i
= 0; i
< d
->level
- 1; ++i
)
790 if (cloog_constraint_involves(c
, i
))
797 /* Increment n for each bound that should be considered by clast_minmax.
799 static int count_bounds(CloogConstraint
*c
, void *user
)
801 struct clast_minmax_data
*d
= (struct clast_minmax_data
*) user
;
803 if (!valid_bound(c
, d
))
812 /* Update the given lower bound based on stride information,
813 * for those cases where the stride offset is represented by
815 * Note that cloog_loop_stride may have already performed a
816 * similar update of the lower bounds, but the updated lower
817 * bounds may have been eliminated because they are redundant
818 * by definition. On the other hand, performing the update
819 * on an already updated constraint is an identity operation
820 * and is therefore harmless.
822 static CloogConstraint
*update_lower_bound_c(CloogConstraint
*c
, int level
,
825 if (!stride
->constraint
)
827 return cloog_constraint_stride_lower_bound(c
, level
, stride
);
831 /* Update the given lower bound based on stride information.
832 * If the stride offset is represented by a constraint,
833 * then we have already performed the update in update_lower_bound_c.
834 * Otherwise, the original lower bound is known to be a constant.
835 * If the bound has already been updated and it just happens
836 * to be a constant, then this function performs an identity
837 * operation on the constant.
839 static void update_lower_bound(struct clast_expr
*expr
, int level
,
842 struct clast_term
*t
;
843 if (stride
->constraint
)
845 if (expr
->type
!= clast_expr_term
)
847 t
= (struct clast_term
*)expr
;
850 cloog_int_sub(t
->val
, t
->val
, stride
->offset
);
851 cloog_int_cdiv_q(t
->val
, t
->val
, stride
->stride
);
852 cloog_int_mul(t
->val
, t
->val
, stride
->stride
);
853 cloog_int_add(t
->val
, t
->val
, stride
->offset
);
857 /* Add all relevant bounds to r->elts and update lower bounds
858 * based on stride information.
860 static int collect_bounds(CloogConstraint
*c
, void *user
)
862 struct clast_minmax_data
*d
= (struct clast_minmax_data
*) user
;
864 if (!valid_bound(c
, d
))
867 c
= cloog_constraint_copy(c
);
869 if (d
->lower_bound
&& d
->infos
->stride
[d
->level
- 1])
870 c
= update_lower_bound_c(c
, d
->level
, d
->infos
->stride
[d
->level
- 1]);
872 d
->r
->elts
[d
->n
] = clast_bound_from_constraint(c
, d
->level
,
874 if (d
->lower_bound
&& d
->infos
->stride
[d
->level
- 1]) {
875 update_lower_bound(d
->r
->elts
[d
->n
], d
->level
,
876 d
->infos
->stride
[d
->level
- 1]);
879 cloog_constraint_release(c
);
888 * clast_minmax function:
889 * This function returns a clast_expr containing the printing of a minimum or a
890 * maximum of the 'right parts' of all constraints according to an element.
891 * For instance consider the constraints:
895 * if we are looking for the minimum for the element j, the function should
896 * return 'max(ceild(3*i+M,2),-2*i)'.
897 * - constraints is the constraints,
898 * - level is the column number in domain of the element we want to use,
899 * - max is a boolean set to 1 if we are looking for a maximum, 0 for a minimum,
900 * - guard is set to 0 if there is no guard, and set to the level of the element
901 * with a guard otherwise (then the function gives the max or the min only
902 * for the constraint where the guarded coefficient is 0),
903 * - lower is set to 1 if the maximum is to be used a lower bound on a loop
904 * - no_earlier is set if no constraints should be used that involve
905 * earlier dimensions,
906 * - the infos structure gives the user some options about code printing,
907 * the number of parameters in domain (nb_par), and the arrays of iterator
908 * names and parameters (iters and params).
910 * - November 2nd 2001: first version.
912 static struct clast_expr
*clast_minmax(CloogConstraintSet
*constraints
,
913 int level
, int max
, int guard
,
914 int lower_bound
, int no_earlier
,
917 struct clast_minmax_data data
= { level
, max
, guard
, lower_bound
,
922 cloog_constraint_set_foreach_constraint(constraints
, count_bounds
, &data
);
926 data
.r
= new_clast_reduction(max
? clast_red_max
: clast_red_min
, data
.n
);
929 cloog_constraint_set_foreach_constraint(constraints
, collect_bounds
, &data
);
931 clast_reduction_sort(data
.r
);
932 return &data
.r
->expr
;
937 * Insert modulo guards defined by existentially quantified dimensions,
938 * not involving the given level.
940 * This function is called from within insert_guard.
941 * Any constraint used in constructing a modulo guard is removed
942 * from the constraint set to avoid insert_guard
943 * adding a duplicate (pair of) constraint(s).
945 * Return the updated CloogConstraintSet.
947 static CloogConstraintSet
*insert_extra_modulo_guards(
948 CloogConstraintSet
*constraints
, int level
,
949 struct clast_stmt
***next
, CloogInfos
*infos
)
954 CloogConstraint
*upper
, *lower
;
956 total_dim
= cloog_constraint_set_total_dimension(constraints
);
957 nb_iter
= cloog_constraint_set_n_iterators(constraints
,
958 infos
->names
->nb_parameters
);
960 for (i
= total_dim
- infos
->names
->nb_parameters
; i
>= nb_iter
+ 1; i
--) {
961 if (cloog_constraint_is_valid(upper
=
962 cloog_constraint_set_defining_equality(constraints
, i
))) {
963 if (!level
|| (nb_iter
< level
) ||
964 !cloog_constraint_involves(upper
, level
-1)) {
965 insert_modulo_guard(upper
,
966 cloog_constraint_invalid(), i
, next
, infos
);
967 constraints
= cloog_constraint_set_drop_constraint(constraints
,
970 cloog_constraint_release(upper
);
971 } else if (cloog_constraint_is_valid(upper
=
972 cloog_constraint_set_defining_inequalities(constraints
,
973 i
, &lower
, infos
->names
->nb_parameters
))) {
974 if (!level
|| (nb_iter
< level
) ||
975 !cloog_constraint_involves(upper
, level
-1)) {
976 insert_modulo_guard(upper
, lower
, i
, next
, infos
);
977 constraints
= cloog_constraint_set_drop_constraint(constraints
,
979 constraints
= cloog_constraint_set_drop_constraint(constraints
,
982 cloog_constraint_release(upper
);
983 cloog_constraint_release(lower
);
991 /* Temporary structure for communication between insert_guard and
992 * its cloog_constraint_set_foreach_constraint callback function.
994 struct clast_guard_data
{
1000 CloogConstraintSet
*copy
;
1001 struct clast_guard
*g
;
1008 static int guard_count_bounds(CloogConstraint
*c
, void *user
)
1010 struct clast_guard_data
*d
= (struct clast_guard_data
*) user
;
1018 /* Insert a guard, if necesessary, for constraint j.
1020 * If the constraint involves any earlier dimensions, then we have
1021 * already considered it during a previous iteration over the constraints.
1023 * If we have already generated a min [max] for the current level d->i
1024 * and if the current constraint is an upper [lower] bound, then we
1025 * can skip the constraint as it will already have been used
1026 * in that previously generated min [max].
1028 static int insert_guard_constraint(CloogConstraint
*j
, void *user
)
1031 struct clast_guard_data
*d
= (struct clast_guard_data
*) user
;
1033 int individual_constraint
;
1034 struct clast_expr
*v
;
1035 struct clast_term
*t
;
1037 if (!cloog_constraint_involves(j
, d
->i
- 1))
1040 for (i
= 0; i
< d
->i
- 1; ++i
)
1041 if (cloog_constraint_involves(j
, i
))
1044 if (d
->level
&& d
->nb_iter
>= d
->level
&&
1045 cloog_constraint_involves(j
, d
->level
- 1))
1048 individual_constraint
= !d
->level
|| cloog_constraint_is_equality(j
);
1049 if (!individual_constraint
) {
1050 if (d
->max
&& cloog_constraint_is_lower_bound(j
, d
->i
- 1))
1052 if (d
->min
&& cloog_constraint_is_upper_bound(j
, d
->i
- 1))
1056 v
= cloog_constraint_variable_expr(j
, d
->i
, d
->infos
->names
);
1057 d
->g
->eq
[d
->n
].LHS
= &(t
= new_clast_term(d
->infos
->state
->one
, v
))->expr
;
1058 if (individual_constraint
) {
1059 /* put the "denominator" in the LHS */
1060 cloog_constraint_coefficient_get(j
, d
->i
- 1, &t
->val
);
1061 cloog_constraint_coefficient_set(j
, d
->i
- 1, d
->infos
->state
->one
);
1062 if (cloog_int_is_neg(t
->val
)) {
1063 cloog_int_neg(t
->val
, t
->val
);
1064 cloog_constraint_coefficient_set(j
, d
->i
- 1, d
->infos
->state
->negone
);
1066 if (d
->level
|| cloog_constraint_is_equality(j
))
1067 d
->g
->eq
[d
->n
].sign
= 0;
1068 else if (cloog_constraint_is_lower_bound(j
, d
->i
- 1))
1069 d
->g
->eq
[d
->n
].sign
= 1;
1071 d
->g
->eq
[d
->n
].sign
= -1;
1072 d
->g
->eq
[d
->n
].RHS
= clast_bound_from_constraint(j
, d
->i
, d
->infos
->names
);
1076 if (cloog_constraint_is_lower_bound(j
, d
->i
- 1)) {
1079 d
->g
->eq
[d
->n
].sign
= 1;
1083 d
->g
->eq
[d
->n
].sign
= -1;
1086 guarded
= (d
->nb_iter
>= d
->level
) ? d
->level
: 0 ;
1087 d
->g
->eq
[d
->n
].RHS
= clast_minmax(d
->copy
, d
->i
, minmax
, guarded
, 0, 1,
1097 * insert_guard function:
1098 * This function inserts a guard in the clast.
1099 * A guard on an element (level) is :
1100 * -> the conjunction of all the existing constraints where the coefficient of
1101 * this element is 0 if the element is an iterator,
1102 * -> the conjunction of all the existing constraints if the element isn't an
1104 * For instance, considering these constraints and the element j:
1107 * this function should return 'if (2*i+M>=0) {'.
1108 * - matrix is the polyhedron containing all the constraints,
1109 * - level is the column number of the element in matrix we want to use,
1110 * - the infos structure gives the user some options about code printing,
1111 * the number of parameters in matrix (nb_par), and the arrays of iterator
1112 * names and parameters (iters and params).
1114 * - November 3rd 2001: first version.
1115 * - November 14th 2001: a lot of 'purifications'.
1116 * - July 31th 2002: (debug) some guard parts are no more redundants.
1117 * - August 12th 2002: polyhedra union ('or' conditions) are now supported.
1118 * - October 27th 2005: polyhedra union ('or' conditions) are no more supported
1119 * (the need came from loop_simplify that may result in
1120 * domain unions, now it should be fixed directly in
1121 * cloog_loop_simplify).
1123 static void insert_guard(CloogConstraintSet
*constraints
, int level
,
1124 struct clast_stmt
***next
, CloogInfos
*infos
)
1127 struct clast_guard_data data
= { level
, infos
, 0 };
1132 data
.copy
= cloog_constraint_set_copy(constraints
);
1134 data
.copy
= insert_extra_modulo_guards(data
.copy
, level
, next
, infos
);
1136 cloog_constraint_set_foreach_constraint(constraints
,
1137 guard_count_bounds
, &data
);
1139 data
.g
= new_clast_guard(data
.n
);
1142 /* Well, it looks complicated because I wanted to have a particular, more
1143 * readable, ordering, obviously this function may be far much simpler !
1145 data
.nb_iter
= cloog_constraint_set_n_iterators(constraints
,
1146 infos
->names
->nb_parameters
);
1148 /* We search for guard parts. */
1149 total_dim
= cloog_constraint_set_total_dimension(constraints
);
1150 for (data
.i
= 1; data
.i
<= total_dim
; data
.i
++) {
1153 cloog_constraint_set_foreach_constraint(data
.copy
,
1154 insert_guard_constraint
, &data
);
1157 cloog_constraint_set_free(data
.copy
);
1161 clast_guard_sort(data
.g
);
1162 **next
= &data
.g
->stmt
;
1163 *next
= &data
.g
->then
;
1165 free_clast_stmt(&data
.g
->stmt
);
1169 * Check if the constant "cst" satisfies the modulo guard that
1170 * would be introduced by insert_computed_modulo_guard.
1171 * The constant is assumed to have been reduced prior to calling
1174 static int constant_modulo_guard_is_satisfied(CloogConstraint
*lower
,
1175 cloog_int_t bound
, cloog_int_t cst
)
1177 if (cloog_constraint_is_valid(lower
))
1178 return cloog_int_le(cst
, bound
);
1180 return cloog_int_is_zero(cst
);
1184 * Insert a modulo guard "r % mod == 0" or "r % mod <= bound",
1185 * depending on whether lower represents a valid constraint.
1187 static void insert_computed_modulo_guard(struct clast_reduction
*r
,
1188 CloogConstraint
*lower
, cloog_int_t mod
, cloog_int_t bound
,
1189 struct clast_stmt
***next
)
1191 struct clast_expr
*e
;
1192 struct clast_guard
*g
;
1194 e
= &new_clast_binary(clast_bin_mod
, &r
->expr
, mod
)->expr
;
1195 g
= new_clast_guard(1);
1196 if (!cloog_constraint_is_valid(lower
)) {
1198 cloog_int_set_si(bound
, 0);
1199 g
->eq
[0].RHS
= &new_clast_term(bound
, NULL
)->expr
;
1203 g
->eq
[0].RHS
= &new_clast_term(bound
, NULL
)->expr
;
1212 /* Try and eliminate coefficients from a modulo constraint based on
1213 * stride information of an earlier level.
1214 * The modulo of the constraint being constructed is "m".
1215 * The stride information at level "level" is given by "stride"
1216 * and indicated that the iterator i at level "level" is equal to
1217 * some expression modulo stride->stride.
1218 * If stride->stride is a multiple of "m' then i is also equal to
1219 * the expression modulo m and so we can eliminate the coefficient of i.
1221 * If stride->constraint is NULL, then i has a constant value modulo m, stored
1222 * stride->offset. We simply multiply this constant with the coefficient
1223 * of i and add the result to the constant term, reducing it modulo m.
1225 * If stride->constraint is not NULL, then it is a constraint of the form
1229 * with s equal to stride->stride, e an expression in terms of the
1230 * parameters and earlier iterators and a some arbitrary expression
1231 * in terms of existentially quantified variables.
1232 * stride->factor is a value f such that f * k = -1 mod s.
1233 * Adding stride->constraint f * c times to the current modulo constraint,
1234 * with c the coefficient of i eliminates i in favor of parameters and
1235 * earlier variables.
1237 static void eliminate_using_stride_constraint(cloog_int_t
*line
, int len
,
1238 int nb_iter
, CloogStride
*stride
, int level
, cloog_int_t m
)
1242 if (!cloog_int_is_divisible_by(stride
->stride
, m
))
1245 if (stride
->constraint
) {
1251 cloog_int_mul(t
, line
[level
], stride
->factor
);
1252 for (i
= 1; i
< level
; ++i
) {
1253 cloog_constraint_coefficient_get(stride
->constraint
,
1255 cloog_int_addmul(line
[i
], t
, v
);
1256 cloog_int_fdiv_r(line
[i
], line
[i
], m
);
1258 s_len
= cloog_constraint_total_dimension(stride
->constraint
)+2;
1259 for (i
= nb_iter
+ 1; i
<= len
- 2; ++i
) {
1260 cloog_constraint_coefficient_get(stride
->constraint
,
1261 i
- (len
- s_len
) - 1, &v
);
1262 cloog_int_addmul(line
[i
], t
, v
);
1263 cloog_int_fdiv_r(line
[i
], line
[i
], m
);
1265 cloog_constraint_constant_get(stride
->constraint
, &v
);
1266 cloog_int_addmul(line
[len
- 1], t
, v
);
1267 cloog_int_fdiv_r(line
[len
- 1], line
[len
- 1], m
);
1271 cloog_int_addmul(line
[len
- 1], line
[level
], stride
->offset
);
1272 cloog_int_fdiv_r(line
[len
- 1], line
[len
- 1], m
);
1275 cloog_int_set_si(line
[level
], 0);
1279 /* Temporary structure for communication between insert_modulo_guard and
1280 * its cloog_constraint_set_foreach_constraint callback function.
1282 struct clast_modulo_guard_data
{
1283 CloogConstraint
*lower
;
1285 struct clast_stmt
***next
;
1288 cloog_int_t val
, bound
;
1292 /* Insert a modulo guard for constraint c.
1293 * The constraint may be either an equality or an inequality.
1294 * Since this function returns -1, it is only called on a single constraint.
1295 * In case of an inequality, the constraint is usually an upper bound
1296 * on d->level. However, if this variable is an existentially
1297 * quantified variable, the upper bound constraint may get removed
1298 * as trivially holding and then this function is called with
1299 * a lower bound instead. In this case, we need to adjust the constraint
1300 * based on the sum of the constant terms of the lower and upper bound
1301 * stored in d->bound.
1303 static int insert_modulo_guard_constraint(CloogConstraint
*c
, void *user
)
1305 struct clast_modulo_guard_data
*d
= (struct clast_modulo_guard_data
*) user
;
1306 int level
= d
->level
;
1307 CloogInfos
*infos
= d
->infos
;
1308 int i
, nb_elts
= 0, len
, nb_iter
, nb_par
;
1310 struct cloog_vec
*line_vector
;
1313 len
= cloog_constraint_total_dimension(c
) + 2;
1314 nb_par
= infos
->names
->nb_parameters
;
1315 nb_iter
= len
- 2 - nb_par
;
1317 line_vector
= cloog_vec_alloc(len
);
1318 line
= line_vector
->p
;
1319 cloog_constraint_copy_coefficients(c
, line
+ 1);
1321 if (cloog_int_is_pos(line
[level
])) {
1322 cloog_seq_neg(line
+ 1, line
+ 1, len
- 1);
1323 if (!cloog_constraint_is_equality(c
))
1324 cloog_int_add(line
[len
- 1], line
[len
- 1], d
->bound
);
1326 cloog_int_neg(line
[level
], line
[level
]);
1327 assert(cloog_int_is_pos(line
[level
]));
1330 for (i
= 1; i
<= len
-1; ++i
) {
1333 cloog_int_fdiv_r(line
[i
], line
[i
], line
[level
]);
1334 if (cloog_int_is_zero(line
[i
]))
1342 if (nb_elts
|| !cloog_int_is_zero(line
[len
-1])) {
1343 struct clast_reduction
*r
;
1346 r
= new_clast_reduction(clast_red_sum
, nb_elts
+ 1);
1349 /* First, the modulo guard : the iterators... */
1351 if (i
> infos
->stride_level
)
1352 i
= infos
->stride_level
;
1354 eliminate_using_stride_constraint(line
, len
, nb_iter
,
1355 infos
->stride
[i
- 1], i
, line
[level
]);
1356 for (i
=1;i
<=nb_iter
;i
++) {
1357 if (i
== level
|| cloog_int_is_zero(line
[i
]))
1360 name
= cloog_names_name_at_level(infos
->names
, i
);
1362 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
],
1363 &new_clast_name(name
)->expr
)->expr
;
1366 /* ...the parameters... */
1367 for (i
=nb_iter
+1;i
<=len
-2;i
++) {
1368 if (cloog_int_is_zero(line
[i
]))
1371 name
= infos
->names
->parameters
[i
-nb_iter
-1] ;
1372 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
],
1373 &new_clast_name(name
)->expr
)->expr
;
1376 constant
= nb_elts
== 0;
1377 /* ...the constant. */
1378 if (!cloog_int_is_zero(line
[len
-1]))
1379 r
->elts
[nb_elts
++] = &new_clast_term(line
[len
-1], NULL
)->expr
;
1381 /* our initial computation may have been an overestimate */
1385 d
->empty
= !constant_modulo_guard_is_satisfied(d
->lower
, d
->bound
,
1387 free_clast_reduction(r
);
1389 insert_computed_modulo_guard(r
, d
->lower
, line
[level
], d
->bound
,
1393 cloog_vec_free(line_vector
);
1400 * insert_modulo_guard:
1401 * This function inserts a modulo guard corresponding to an equality
1402 * or a pair of inequalities.
1403 * Returns 0 if the modulo guard is discovered to be unsatisfiable.
1405 * See insert_equation.
1406 * - matrix is the polyhedron containing all the constraints,
1407 * - upper and lower are the line numbers of the constraint in matrix
1408 * we want to print; in particular, if we want to print an equality,
1409 * then lower == -1 and upper is the row of the equality; if we want
1410 * to print an inequality, then upper is the row of the upper bound
1411 * and lower in the row of the lower bound
1412 * - level is the column number of the element in matrix we want to use,
1413 * - the infos structure gives the user some options about code printing,
1414 * the number of parameters in matrix (nb_par), and the arrays of iterator
1415 * names and parameters (iters and params).
1417 static int insert_modulo_guard(CloogConstraint
*upper
,
1418 CloogConstraint
*lower
, int level
,
1419 struct clast_stmt
***next
, CloogInfos
*infos
)
1422 CloogConstraintSet
*set
;
1423 struct clast_modulo_guard_data data
= { lower
, level
, next
, infos
, 0 };
1425 cloog_int_init(data
.val
);
1426 cloog_constraint_coefficient_get(upper
, level
-1, &data
.val
);
1427 if (cloog_int_is_one(data
.val
) || cloog_int_is_neg_one(data
.val
)) {
1428 cloog_int_clear(data
.val
);
1432 nb_par
= infos
->names
->nb_parameters
;
1434 cloog_int_init(data
.bound
);
1435 /* Check if would be emitting the redundant constraint mod(e,m) <= m-1 */
1436 if (cloog_constraint_is_valid(lower
)) {
1437 cloog_constraint_constant_get(upper
, &data
.val
);
1438 cloog_constraint_constant_get(lower
, &data
.bound
);
1439 cloog_int_add(data
.bound
, data
.val
, data
.bound
);
1440 cloog_constraint_coefficient_get(lower
, level
-1, &data
.val
);
1441 cloog_int_sub_ui(data
.val
, data
.val
, 1);
1442 if (cloog_int_eq(data
.val
, data
.bound
)) {
1443 cloog_int_clear(data
.val
);
1444 cloog_int_clear(data
.bound
);
1449 if (cloog_constraint_needs_reduction(upper
, level
)) {
1450 set
= cloog_constraint_set_for_reduction(upper
, lower
);
1451 set
= cloog_constraint_set_reduce(set
, level
, infos
->equal
,
1452 nb_par
, &data
.bound
);
1453 cloog_constraint_set_foreach_constraint(set
,
1454 insert_modulo_guard_constraint
, &data
);
1455 cloog_constraint_set_free(set
);
1457 insert_modulo_guard_constraint(upper
, &data
);
1459 cloog_int_clear(data
.val
);
1460 cloog_int_clear(data
.bound
);
1467 * We found an equality or a pair of inequalities identifying
1468 * a loop with a single iteration, but the user wants us to generate
1469 * a loop anyway, so we do it here.
1471 static int insert_equation_as_loop(CloogDomain
*domain
, CloogConstraint
*upper
,
1472 CloogConstraint
*lower
, int level
, struct clast_stmt
***next
,
1475 const char *iterator
= cloog_names_name_at_level(infos
->names
, level
);
1476 struct clast_expr
*e1
, *e2
;
1477 struct clast_for
*f
;
1479 e2
= clast_bound_from_constraint(upper
, level
, infos
->names
);
1480 if (!cloog_constraint_is_valid(lower
))
1481 e1
= clast_expr_copy(e2
);
1483 e1
= clast_bound_from_constraint(lower
, level
, infos
->names
);
1485 f
= new_clast_for(domain
, iterator
, e1
, e2
, infos
->stride
[level
-1]);
1489 cloog_constraint_release(lower
);
1490 cloog_constraint_release(upper
);
1496 * insert_equation function:
1497 * This function inserts an equality
1498 * constraint according to an element in the clast.
1499 * Returns 1 if the calling function should recurse into inner loops.
1501 * An equality can be preceded by a 'modulo guard'.
1502 * For instance, consider the constraint i -2*j = 0 and the
1503 * element j: pprint_equality should return 'if(i%2==0) { j = i/2 ;'.
1504 * - matrix is the polyhedron containing all the constraints,
1505 * - num is the line number of the constraint in matrix we want to print,
1506 * - level is the column number of the element in matrix we want to use,
1507 * - the infos structure gives the user some options about code printing,
1508 * the number of parameters in matrix (nb_par), and the arrays of iterator
1509 * names and parameters (iters and params).
1511 * - November 13th 2001: first version.
1512 * - June 26th 2003: simplification of the modulo guards (remove parts such as
1513 * modulo is 0, compare vivien or vivien2 with a previous
1514 * version for an idea).
1515 * - June 29th 2003: non-unit strides support.
1516 * - July 14th 2003: (debug) no more print the constant in the modulo guard when
1517 * it was previously included in a stride calculation.
1519 static int insert_equation(CloogDomain
*domain
, CloogConstraint
*upper
,
1520 CloogConstraint
*lower
, int level
, struct clast_stmt
1521 ***next
, CloogInfos
*infos
)
1523 struct clast_expr
*e
;
1524 struct clast_assignment
*ass
;
1526 if (!infos
->options
->otl
)
1527 return insert_equation_as_loop(domain
, upper
, lower
, level
, next
, infos
);
1529 if (!insert_modulo_guard(upper
, lower
, level
, next
, infos
)) {
1530 cloog_constraint_release(lower
);
1531 cloog_constraint_release(upper
);
1536 if (cloog_constraint_is_valid(lower
) ||
1537 !clast_equal_add(infos
->equal
, NULL
, level
, upper
, infos
))
1538 { /* Finally, the equality. */
1540 /* If we have to make a block by dimension, we start the block. Function
1541 * pprint knows if there is an equality, if this is the case, it checks
1542 * for the same following condition to close the brace.
1544 if (infos
->options
->block
) {
1545 struct clast_block
*b
= new_clast_block();
1550 e
= clast_bound_from_constraint(upper
, level
, infos
->names
);
1551 ass
= new_clast_assignment(cloog_names_name_at_level(infos
->names
, level
), e
);
1553 **next
= &ass
->stmt
;
1554 *next
= &(**next
)->next
;
1557 cloog_constraint_release(lower
);
1558 cloog_constraint_release(upper
);
1565 * Insert a loop that is executed exactly once as an assignment.
1566 * In particular, the loop
1568 * for (i = e; i <= e; ++i) {
1578 static void insert_otl_for(CloogConstraintSet
*constraints
, int level
,
1579 struct clast_expr
*e
, struct clast_stmt
***next
, CloogInfos
*infos
)
1581 const char *iterator
;
1583 iterator
= cloog_names_name_at_level(infos
->names
, level
);
1585 if (!clast_equal_add(infos
->equal
, constraints
, level
,
1586 cloog_constraint_invalid(), infos
)) {
1587 struct clast_assignment
*ass
;
1588 if (infos
->options
->block
) {
1589 struct clast_block
*b
= new_clast_block();
1593 ass
= new_clast_assignment(iterator
, e
);
1594 **next
= &ass
->stmt
;
1595 *next
= &(**next
)->next
;
1603 * Insert a loop that is executed at most once as an assignment followed
1604 * by a guard. In particular, the loop
1606 * for (i = e1; i <= e2; ++i) {
1618 static void insert_guarded_otl_for(CloogConstraintSet
*constraints
, int level
,
1619 struct clast_expr
*e1
, struct clast_expr
*e2
,
1620 struct clast_stmt
***next
, CloogInfos
*infos
)
1622 const char *iterator
;
1623 struct clast_assignment
*ass
;
1624 struct clast_guard
*guard
;
1626 iterator
= cloog_names_name_at_level(infos
->names
, level
);
1628 if (infos
->options
->block
) {
1629 struct clast_block
*b
= new_clast_block();
1633 ass
= new_clast_assignment(iterator
, e1
);
1634 **next
= &ass
->stmt
;
1635 *next
= &(**next
)->next
;
1637 guard
= new_clast_guard(1);
1638 guard
->eq
[0].sign
= -1;
1639 guard
->eq
[0].LHS
= &new_clast_term(infos
->state
->one
,
1640 &new_clast_name(iterator
)->expr
)->expr
;
1641 guard
->eq
[0].RHS
= e2
;
1643 **next
= &guard
->stmt
;
1644 *next
= &guard
->then
;
1649 * insert_for function:
1650 * This function inserts a for loop in the clast.
1651 * Returns 1 if the calling function should recurse into inner loops.
1653 * A loop header according to an element is the conjunction of a minimum and a
1654 * maximum on a given element (they give the loop bounds).
1655 * For instance, considering these constraints and the element j:
1659 * this function should return 'for (j=max(-i+9*M,4*M),j<=5*M;j++) {'.
1660 * - constraints contains all constraints,
1661 * - level is the column number of the element in matrix we want to use,
1662 * - otl is set if the loop is executed at most once,
1663 * - the infos structure gives the user some options about code printing,
1664 * the number of parameters in matrix (nb_par), and the arrays of iterator
1665 * names and parameters (iters and params).
1667 static int insert_for(CloogDomain
*domain
, CloogConstraintSet
*constraints
,
1668 int level
, int otl
, struct clast_stmt
***next
,
1671 const char *iterator
;
1672 struct clast_expr
*e1
;
1673 struct clast_expr
*e2
;
1675 e1
= clast_minmax(constraints
, level
, 1, 0, 1, 0, infos
);
1676 e2
= clast_minmax(constraints
, level
, 0, 0, 0, 0, infos
);
1678 if (clast_expr_is_bigger_constant(e1
, e2
)) {
1679 free_clast_expr(e1
);
1680 free_clast_expr(e2
);
1684 /* If min and max are not equal there is a 'for' else, there is a '='.
1685 * In the special case e1 = e2 = NULL, this is an infinite loop
1686 * so this is not a '='.
1688 if (e1
&& e2
&& infos
->options
->otl
&& clast_expr_equal(e1
, e2
)) {
1689 free_clast_expr(e2
);
1690 insert_otl_for(constraints
, level
, e1
, next
, infos
);
1692 insert_guarded_otl_for(constraints
, level
, e1
, e2
, next
, infos
);
1694 struct clast_for
*f
;
1695 iterator
= cloog_names_name_at_level(infos
->names
, level
);
1697 f
= new_clast_for(domain
, iterator
, e1
, e2
, infos
->stride
[level
-1]);
1707 * insert_block function:
1708 * This function inserts a statement block.
1709 * - block is the statement block,
1710 * - level is the number of loops enclosing the statement,
1711 * - the infos structure gives the user some options about code printing,
1712 * the number of parameters in domain (nb_par), and the arrays of iterator
1713 * names and parameters (iters and params).
1715 * - September 21th 2003: first version (pick from pprint function).
1717 static void insert_block(CloogDomain
*domain
, CloogBlock
*block
, int level
,
1718 struct clast_stmt
***next
, CloogInfos
*infos
)
1720 CloogStatement
* statement
;
1721 struct clast_stmt
*subs
;
1726 for (statement
= block
->statement
; statement
; statement
= statement
->next
) {
1727 CloogStatement
*s_next
= statement
->next
;
1729 subs
= clast_equal(level
,infos
);
1731 statement
->next
= NULL
;
1732 **next
= &new_clast_user_stmt(domain
, statement
, subs
)->stmt
;
1733 statement
->next
= s_next
;
1734 *next
= &(**next
)->next
;
1740 * insert_loop function:
1741 * This function converts the content of a CloogLoop structure (loop) into a
1742 * clast_stmt (inserted at **next).
1743 * The iterator (level) of
1744 * the current loop is given by 'level': this is the column number of the
1745 * domain corresponding to the current loop iterator. The data of a loop are
1746 * written in this order:
1747 * 1. The guard of the loop, i.e. each constraint in the domain that does not
1748 * depend on the iterator (when the entry in the column 'level' is 0).
1749 * 2. The iteration domain of the iterator, given by the constraints in the
1750 * domain depending on the iterator, i.e.:
1751 * * an equality if the iterator has only one value (possibly preceded by
1752 * a guard verifying if this value is integral), *OR*
1753 * * a loop from the minimum possible value of the iterator to the maximum
1755 * 3. The included statement block.
1756 * 4. The inner loops (recursive call).
1757 * 5. The following loops (recursive call).
1758 * - level is the recursion level or the iteration level that we are printing,
1759 * - the infos structure gives the user some options about code printing,
1760 * the number of parameters in domain (nb_par), and the arrays of iterator
1761 * names and parameters (iters and params).
1763 * - November 2nd 2001: first version.
1764 * - March 6th 2003: infinite domain support.
1765 * - April 19th 2003: (debug) NULL loop support.
1766 * - June 29th 2003: non-unit strides support.
1767 * - April 28th 2005: (debug) level is level+equality when print statement!
1768 * - June 16th 2005: (debug) the N. Vasilache normalization step has been
1769 * added to avoid iteration duplication (see DaeGon Kim
1770 * bug in cloog_program_generate). Try vasilache.cloog
1771 * with and without the call to cloog_polylib_matrix_normalize,
1772 * using -f 8 -l 9 options for an idea.
1773 * - September 15th 2005: (debug) don't close equality braces when unnecessary.
1774 * - October 16th 2005: (debug) scalar value is saved for next loops.
1776 static void insert_loop(CloogLoop
* loop
, int level
,
1777 struct clast_stmt
***next
, CloogInfos
*infos
)
1780 CloogConstraintSet
*constraints
, *temp
;
1781 struct clast_stmt
**top
= *next
;
1782 CloogConstraint
*i
, *j
;
1785 /* It can happen that loop be NULL when an input polyhedron is empty. */
1789 /* The constraints do not always have a shape that allows us to generate code from it,
1790 * thus we normalize it, we also simplify it with the equalities.
1792 temp
= cloog_domain_constraints(loop
->domain
);
1793 cloog_constraint_set_normalize(temp
,level
);
1794 constraints
= cloog_constraint_set_simplify(temp
,infos
->equal
,level
,
1795 infos
->names
->nb_parameters
);
1796 cloog_constraint_set_free(temp
);
1798 infos
->stride
[level
- 1] = loop
->stride
;
1799 infos
->stride_level
++;
1802 /* First of all we have to print the guard. */
1803 insert_guard(constraints
,level
, next
, infos
);
1805 if (level
&& cloog_constraint_set_contains_level(constraints
, level
,
1806 infos
->names
->nb_parameters
)) {
1807 /* We scan all the constraints to know in which case we are :
1808 * [[if] equation] or [for].
1810 if (cloog_constraint_is_valid(i
=
1811 cloog_constraint_set_defining_equality(constraints
, level
))) {
1812 empty_loop
= !insert_equation(loop
->unsimplified
, i
,
1813 cloog_constraint_invalid(), level
, next
,
1816 } else if (cloog_constraint_is_valid(i
=
1817 cloog_constraint_set_defining_inequalities(constraints
,
1818 level
, &j
, infos
->names
->nb_parameters
))) {
1819 empty_loop
= !insert_equation(loop
->unsimplified
, i
, j
, level
, next
,
1822 empty_loop
= !insert_for(loop
->unsimplified
, constraints
, level
,
1823 loop
->otl
, next
, infos
);
1827 /* Finally, if there is an included statement block, print it. */
1828 insert_block(loop
->unsimplified
, loop
->block
, level
+equality
, next
, infos
);
1830 /* Go to the next level. */
1831 if (loop
->inner
!= NULL
)
1832 insert_loop(loop
->inner
, level
+1, next
, infos
);
1836 cloog_equal_del(infos
->equal
,level
);
1837 infos
->stride_level
--;
1839 cloog_constraint_set_free(constraints
);
1841 /* Go to the next loop on the same level. */
1843 top
= &(*top
)->next
;
1844 if (loop
->next
!= NULL
)
1845 insert_loop(loop
->next
, level
, &top
,infos
);
1849 struct clast_stmt
*cloog_clast_create(CloogProgram
*program
,
1850 CloogOptions
*options
)
1852 CloogInfos
*infos
= ALLOC(CloogInfos
);
1854 struct clast_stmt
*root
= &new_clast_root(program
->names
)->stmt
;
1855 struct clast_stmt
**next
= &root
->next
;
1857 infos
->state
= options
->state
;
1858 infos
->names
= program
->names
;
1859 infos
->options
= options
;
1860 infos
->scaldims
= program
->scaldims
;
1861 infos
->nb_scattdims
= program
->nb_scattdims
;
1863 /* Allocation for the array of strides, there is a +1 since the statement can
1864 * be included inside an external loop without iteration domain.
1866 nb_levels
= program
->names
->nb_scattering
+program
->names
->nb_iterators
+1;
1867 infos
->stride
= ALLOCN(CloogStride
*, nb_levels
);
1868 infos
->stride_level
= 0;
1870 infos
->equal
= cloog_equal_alloc(nb_levels
,
1871 nb_levels
, program
->names
->nb_parameters
);
1873 insert_loop(program
->loop
, 0, &next
, infos
);
1875 cloog_equal_free(infos
->equal
);
1877 free(infos
->stride
);
1884 struct clast_stmt
*cloog_clast_create_from_input(CloogInput
*input
,
1885 CloogOptions
*options
)
1887 CloogProgram
*program
;
1888 struct clast_stmt
*root
;
1890 program
= cloog_program_alloc(input
->context
, input
->ud
, options
);
1893 program
= cloog_program_generate(program
, options
);
1895 root
= cloog_clast_create(program
, options
);
1896 cloog_program_free(program
);
1901 /* Adds to the list if not already in it */
1902 static int add_if_new(void **list
, int num
, void *new, int size
)
1906 for (i
=0; i
<num
; i
++) {
1907 if (!memcmp((*list
) + i
*size
, new, size
)) break;
1911 *list
= realloc(*list
, (num
+1)*size
);
1912 memcpy(*list
+ num
*size
, new, size
);
1920 /* Concatenates all elements of list2 that are not in list1;
1921 * Returns the new size of the list */
1922 int concat_if_new(void **list1
, int num1
, void *list2
, int num2
, int size
)
1926 for (i
=0; i
<num2
; i
++) {
1927 ret
= add_if_new(list1
, num1
, (char *)list2
+ i
*size
, size
);
1934 /* Compares list1 to list2
1935 * Returns 0 if both have the same elements; returns -1 if all elements of
1936 * list1 are strictly contained in list2; 1 otherwise
1938 int list_compare(const int *list1
, int num1
, const int *list2
, int num2
)
1942 for (i
=0; i
<num1
; i
++) {
1943 for (j
=0; j
<num2
; j
++) {
1944 if (list1
[i
] == list2
[j
]) break;
1961 * A multi-purpose function to traverse and get information on Clast
1964 * node: clast node where processing should start
1967 * A list of loops under clast_stmt 'node' filtered in two ways: (1) it contains
1968 * statements appearing in 'stmts_filter', (2) loop iterator's name is 'iter'
1969 * If iter' is set to NULL, no filtering based on iterator name is done
1971 * iter: loop iterator name
1972 * stmts_filter: list of statement numbers for filtering (1-indexed)
1973 * nstmts_filter: number of statements in stmts_filter
1975 * FilterType: match exact (i.e., loops containing only and all those statements
1976 * in stmts_filter) or subset, i.e., loops which have only those statements
1977 * that appear in stmts_filter
1979 * To disable all filtering, set 'iter' to NULL, provide all statement
1980 * numbers in 'stmts_filter' and set FilterType to subset
1984 * stmts: an array of statement numbers under node
1985 * nstmts: number of stmt numbers pointed to by stmts
1986 * loops: list of clast loops
1987 * nloops: number of clast loops in loops
1990 void clast_filter(struct clast_stmt
*node
,
1992 struct clast_for
***loops
, int *nloops
,
1993 int **stmts
, int *nstmts
)
1995 int num_next_stmts
, num_next_loops
, ret
, *stmts_next
;
1996 struct clast_for
**loops_next
;
2007 ClastFilterType filter_type
= filter
.filter_type
;
2008 const char *iter
= filter
.iter
;
2009 int nstmts_filter
= filter
.nstmts_filter
;
2010 const int *stmts_filter
= filter
.stmts_filter
;
2012 if (CLAST_STMT_IS_A(node
, stmt_root
)) {
2013 // printf("root stmt\n");
2014 struct clast_root
*root
= (struct clast_root
*) node
;
2015 clast_filter((root
->stmt
).next
, filter
, &loops_next
,
2016 &num_next_loops
, &stmts_next
, &num_next_stmts
);
2017 *nstmts
= concat_if_new((void **)stmts
, *nstmts
, stmts_next
, num_next_stmts
, sizeof(int));
2018 *nloops
= concat_if_new((void **)loops
, *nloops
, loops_next
, num_next_loops
,
2019 sizeof(struct clast_stmt
*));
2024 if (CLAST_STMT_IS_A(node
, stmt_guard
)) {
2025 // printf("guard stmt\n");
2026 struct clast_guard
*guard
= (struct clast_guard
*) node
;
2027 clast_filter(guard
->then
, filter
, &loops_next
,
2028 &num_next_loops
, &stmts_next
, &num_next_stmts
);
2029 *nstmts
= concat_if_new((void **)stmts
, *nstmts
, stmts_next
, num_next_stmts
, sizeof(int));
2030 *nloops
= concat_if_new((void **)loops
, *nloops
, loops_next
, num_next_loops
,
2031 sizeof(struct clast_stmt
*));
2034 clast_filter((guard
->stmt
).next
, filter
, &loops_next
,
2035 &num_next_loops
, &stmts_next
, &num_next_stmts
);
2036 *nstmts
= concat_if_new((void **)stmts
, *nstmts
, stmts_next
, num_next_stmts
, sizeof(int));
2037 *nloops
= concat_if_new((void **)loops
, *nloops
, loops_next
, num_next_loops
,
2038 sizeof(struct clast_stmt
*));
2043 if (CLAST_STMT_IS_A(node
, stmt_user
)) {
2044 struct clast_user_stmt
*user_stmt
= (struct clast_user_stmt
*) node
;
2045 // printf("user stmt: S%d\n", user_stmt->statement->number);
2046 ret
= add_if_new((void **)stmts
, *nstmts
, &user_stmt
->statement
->number
, sizeof(int));
2047 if (ret
) (*nstmts
)++;
2048 clast_filter((user_stmt
->stmt
).next
, filter
, &loops_next
,
2049 &num_next_loops
, &stmts_next
, &num_next_stmts
);
2050 *nstmts
= concat_if_new((void **)stmts
, *nstmts
, stmts_next
, num_next_stmts
, sizeof(int));
2051 *nloops
= concat_if_new((void **)loops
, *nloops
, loops_next
, num_next_loops
,
2052 sizeof(struct clast_stmt
*));
2056 if (CLAST_STMT_IS_A(node
, stmt_for
)) {
2057 struct clast_for
*for_stmt
= (struct clast_for
*) node
;
2058 clast_filter(for_stmt
->body
, filter
, &loops_next
,
2059 &num_next_loops
, &stmts_next
, &num_next_stmts
);
2060 *nstmts
= concat_if_new((void **)stmts
, *nstmts
, stmts_next
, num_next_stmts
, sizeof(int));
2061 *nloops
= concat_if_new((void **)loops
, *nloops
, loops_next
, num_next_loops
,
2062 sizeof(struct clast_stmt
*));
2064 if (iter
== NULL
|| !strcmp(for_stmt
->iterator
, iter
)) {
2065 if (stmts_filter
== NULL
||
2066 (filter_type
== subset
&& list_compare(stmts_next
, num_next_stmts
,
2067 stmts_filter
, nstmts_filter
) <= 0)
2068 || (filter_type
== exact
&& list_compare(stmts_next
, num_next_stmts
,
2069 stmts_filter
, nstmts_filter
) == 0 )) {
2070 ret
= add_if_new((void **)loops
, *nloops
, &for_stmt
, sizeof(struct clast_for
*));
2071 if (ret
) (*nloops
)++;
2077 clast_filter((for_stmt
->stmt
).next
, filter
, &loops_next
,
2078 &num_next_loops
, &stmts_next
, &num_next_stmts
);
2079 *nstmts
= concat_if_new((void **)stmts
, *nstmts
, stmts_next
, num_next_stmts
, sizeof(int));
2080 *nloops
= concat_if_new((void **)loops
, *nloops
, loops_next
, num_next_loops
,
2081 sizeof(struct clast_stmt
*));