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 nb_scattdims
; /**< Scattering dimension number. */
21 int * scaldims
; /**< Boolean array saying whether a given
22 * scattering dimension is scalar or not.
24 CloogNames
* names
; /**< Names of iterators and parameters. */
25 CloogOptions
* options
; /**< Options on CLooG's behaviour. */
26 CloogEqualities
*equal
; /**< Matrix of equalities. */
29 typedef struct clooginfos CloogInfos
;
31 static int clast_expr_cmp(struct clast_expr
*e1
, struct clast_expr
*e2
);
32 static int clast_term_cmp(struct clast_term
*t1
, struct clast_term
*t2
);
33 static int clast_binary_cmp(struct clast_binary
*b1
, struct clast_binary
*b2
);
34 static int clast_reduction_cmp(struct clast_reduction
*r1
,
35 struct clast_reduction
*r2
);
37 static struct clast_expr
*clast_expr_copy(struct clast_expr
*e
);
39 static int clast_equal_add(CloogEqualities
*equal
,
40 CloogConstraintSet
*constraints
,
41 int level
, CloogConstraint
*constraint
,
44 static struct clast_stmt
*clast_equal(int level
, CloogInfos
*infos
);
45 static struct clast_expr
*clast_minmax(CloogConstraintSet
*constraints
,
46 int level
, int max
, int guard
,
49 static void insert_guard(CloogConstraintSet
*constraints
, int level
,
50 struct clast_stmt
***next
, CloogInfos
*infos
);
51 static int insert_modulo_guard(CloogConstraint
*upper
,
52 CloogConstraint
*lower
, int level
,
53 struct clast_stmt
***next
, CloogInfos
*infos
);
54 static int insert_equation(CloogConstraint
*upper
, CloogConstraint
*lower
,
55 int level
, struct clast_stmt
***next
, CloogInfos
*infos
);
56 static int insert_for(CloogConstraintSet
*constraints
, int level
, int otl
,
57 struct clast_stmt
***next
, CloogInfos
*infos
);
58 static void insert_block(CloogDomain
*domain
, CloogBlock
*block
, int level
,
59 struct clast_stmt
***next
, CloogInfos
*infos
);
60 static void insert_loop(CloogLoop
* loop
, int level
,
61 struct clast_stmt
***next
, CloogInfos
*infos
);
64 struct clast_name
*new_clast_name(const char *name
)
66 struct clast_name
*n
= malloc(sizeof(struct clast_name
));
67 n
->expr
.type
= clast_expr_name
;
72 struct clast_term
*new_clast_term(cloog_int_t c
, struct clast_expr
*v
)
74 struct clast_term
*t
= malloc(sizeof(struct clast_term
));
75 t
->expr
.type
= clast_expr_term
;
76 cloog_int_init(t
->val
);
77 cloog_int_set(t
->val
, c
);
82 struct clast_binary
*new_clast_binary(enum clast_bin_type t
,
83 struct clast_expr
*lhs
, cloog_int_t rhs
)
85 struct clast_binary
*b
= malloc(sizeof(struct clast_binary
));
86 b
->expr
.type
= clast_expr_bin
;
89 cloog_int_init(b
->RHS
);
90 cloog_int_set(b
->RHS
, rhs
);
94 struct clast_reduction
*new_clast_reduction(enum clast_red_type t
, int n
)
97 struct clast_reduction
*r
;
98 r
= malloc(sizeof(struct clast_reduction
)+(n
-1)*sizeof(struct clast_expr
*));
99 r
->expr
.type
= clast_expr_red
;
102 for (i
= 0; i
< n
; ++i
)
107 static void free_clast_root(struct clast_stmt
*s
);
109 const struct clast_stmt_op stmt_root
= { free_clast_root
};
111 static void free_clast_root(struct clast_stmt
*s
)
113 struct clast_root
*r
= (struct clast_root
*)s
;
114 assert(CLAST_STMT_IS_A(s
, stmt_root
));
115 cloog_names_free(r
->names
);
119 struct clast_root
*new_clast_root(CloogNames
*names
)
121 struct clast_root
*r
= malloc(sizeof(struct clast_root
));
122 r
->stmt
.op
= &stmt_root
;
124 r
->names
= cloog_names_copy(names
);
128 static void free_clast_assignment(struct clast_stmt
*s
);
130 const struct clast_stmt_op stmt_ass
= { free_clast_assignment
};
132 static void free_clast_assignment(struct clast_stmt
*s
)
134 struct clast_assignment
*a
= (struct clast_assignment
*)s
;
135 assert(CLAST_STMT_IS_A(s
, stmt_ass
));
136 free_clast_expr(a
->RHS
);
140 struct clast_assignment
*new_clast_assignment(const char *lhs
,
141 struct clast_expr
*rhs
)
143 struct clast_assignment
*a
= malloc(sizeof(struct clast_assignment
));
144 a
->stmt
.op
= &stmt_ass
;
151 static void free_clast_user_stmt(struct clast_stmt
*s
);
153 const struct clast_stmt_op stmt_user
= { free_clast_user_stmt
};
155 static void free_clast_user_stmt(struct clast_stmt
*s
)
157 struct clast_user_stmt
*u
= (struct clast_user_stmt
*)s
;
158 assert(CLAST_STMT_IS_A(s
, stmt_user
));
159 cloog_domain_free(u
->domain
);
160 cloog_statement_free(u
->statement
);
161 cloog_clast_free(u
->substitutions
);
165 struct clast_user_stmt
*new_clast_user_stmt(CloogDomain
*domain
,
166 CloogStatement
*stmt
, struct clast_stmt
*subs
)
168 struct clast_user_stmt
*u
= malloc(sizeof(struct clast_user_stmt
));
169 u
->stmt
.op
= &stmt_user
;
171 u
->domain
= cloog_domain_copy(domain
);
172 u
->statement
= cloog_statement_copy(stmt
);
173 u
->substitutions
= subs
;
177 static void free_clast_block(struct clast_stmt
*b
);
179 const struct clast_stmt_op stmt_block
= { free_clast_block
};
181 static void free_clast_block(struct clast_stmt
*s
)
183 struct clast_block
*b
= (struct clast_block
*)s
;
184 assert(CLAST_STMT_IS_A(s
, stmt_block
));
185 cloog_clast_free(b
->body
);
189 struct clast_block
*new_clast_block()
191 struct clast_block
*b
= malloc(sizeof(struct clast_block
));
192 b
->stmt
.op
= &stmt_block
;
198 static void free_clast_for(struct clast_stmt
*s
);
200 const struct clast_stmt_op stmt_for
= { free_clast_for
};
202 static void free_clast_for(struct clast_stmt
*s
)
204 struct clast_for
*f
= (struct clast_for
*)s
;
205 assert(CLAST_STMT_IS_A(s
, stmt_for
));
206 free_clast_expr(f
->LB
);
207 free_clast_expr(f
->UB
);
208 cloog_int_clear(f
->stride
);
209 cloog_clast_free(f
->body
);
213 struct clast_for
*new_clast_for(const char *it
, struct clast_expr
*LB
,
214 struct clast_expr
*UB
, CloogStride
*stride
)
216 struct clast_for
*f
= malloc(sizeof(struct clast_for
));
217 f
->stmt
.op
= &stmt_for
;
223 cloog_int_init(f
->stride
);
225 cloog_int_set(f
->stride
, stride
->stride
);
227 cloog_int_set_si(f
->stride
, 1);
231 static void free_clast_guard(struct clast_stmt
*s
);
233 const struct clast_stmt_op stmt_guard
= { free_clast_guard
};
235 static void free_clast_guard(struct clast_stmt
*s
)
238 struct clast_guard
*g
= (struct clast_guard
*)s
;
239 assert(CLAST_STMT_IS_A(s
, stmt_guard
));
240 cloog_clast_free(g
->then
);
241 for (i
= 0; i
< g
->n
; ++i
) {
242 free_clast_expr(g
->eq
[i
].LHS
);
243 free_clast_expr(g
->eq
[i
].RHS
);
248 struct clast_guard
*new_clast_guard(int n
)
251 struct clast_guard
*g
= malloc(sizeof(struct clast_guard
) +
252 (n
-1) * sizeof(struct clast_equation
));
253 g
->stmt
.op
= &stmt_guard
;
257 for (i
= 0; i
< n
; ++i
) {
264 void free_clast_name(struct clast_name
*n
)
269 void free_clast_term(struct clast_term
*t
)
271 cloog_int_clear(t
->val
);
272 free_clast_expr(t
->var
);
276 void free_clast_binary(struct clast_binary
*b
)
278 cloog_int_clear(b
->RHS
);
279 free_clast_expr(b
->LHS
);
283 void free_clast_reduction(struct clast_reduction
*r
)
286 for (i
= 0; i
< r
->n
; ++i
)
287 free_clast_expr(r
->elts
[i
]);
291 void free_clast_expr(struct clast_expr
*e
)
296 case clast_expr_name
:
297 free_clast_name((struct clast_name
*) e
);
299 case clast_expr_term
:
300 free_clast_term((struct clast_term
*) e
);
303 free_clast_reduction((struct clast_reduction
*) e
);
306 free_clast_binary((struct clast_binary
*) e
);
313 void free_clast_stmt(struct clast_stmt
*s
)
320 void cloog_clast_free(struct clast_stmt
*s
)
322 struct clast_stmt
*next
;
330 static int clast_name_cmp(struct clast_name
*n1
, struct clast_name
*n2
)
332 return n1
->name
== n2
->name
? 0 : strcmp(n1
->name
, n2
->name
);
335 static int clast_term_cmp(struct clast_term
*t1
, struct clast_term
*t2
)
338 if (!t1
->var
&& t2
->var
)
340 if (t1
->var
&& !t2
->var
)
342 c
= clast_expr_cmp(t1
->var
, t2
->var
);
345 return cloog_int_cmp(t1
->val
, t2
->val
);
348 static int clast_binary_cmp(struct clast_binary
*b1
, struct clast_binary
*b2
)
352 if (b1
->type
!= b2
->type
)
353 return b1
->type
- b2
->type
;
354 if ((c
= cloog_int_cmp(b1
->RHS
, b2
->RHS
)))
356 return clast_expr_cmp(b1
->LHS
, b2
->LHS
);
359 static int clast_reduction_cmp(struct clast_reduction
*r1
, struct clast_reduction
*r2
)
364 if (r1
->n
== 1 && r2
->n
== 1)
365 return clast_expr_cmp(r1
->elts
[0], r2
->elts
[0]);
366 if (r1
->type
!= r2
->type
)
367 return r1
->type
- r2
->type
;
369 return r1
->n
- r2
->n
;
370 for (i
= 0; i
< r1
->n
; ++i
)
371 if ((c
= clast_expr_cmp(r1
->elts
[i
], r2
->elts
[i
])))
376 static int clast_expr_cmp(struct clast_expr
*e1
, struct clast_expr
*e2
)
384 if (e1
->type
!= e2
->type
)
385 return e1
->type
- e2
->type
;
387 case clast_expr_name
:
388 return clast_name_cmp((struct clast_name
*) e1
,
389 (struct clast_name
*) e2
);
390 case clast_expr_term
:
391 return clast_term_cmp((struct clast_term
*) e1
,
392 (struct clast_term
*) e2
);
394 return clast_binary_cmp((struct clast_binary
*) e1
,
395 (struct clast_binary
*) e2
);
397 return clast_reduction_cmp((struct clast_reduction
*) e1
,
398 (struct clast_reduction
*) e2
);
404 int clast_expr_equal(struct clast_expr
*e1
, struct clast_expr
*e2
)
406 return clast_expr_cmp(e1
, e2
) == 0;
410 * Return 1 is both expressions are constant terms and e1 is bigger than e2.
412 int clast_expr_is_bigger_constant(struct clast_expr
*e1
, struct clast_expr
*e2
)
414 struct clast_term
*t1
, *t2
;
415 struct clast_reduction
*r
;
419 if (e1
->type
== clast_expr_red
) {
420 r
= (struct clast_reduction
*)e1
;
421 return r
->n
== 1 && clast_expr_is_bigger_constant(r
->elts
[0], e2
);
423 if (e2
->type
== clast_expr_red
) {
424 r
= (struct clast_reduction
*)e2
;
425 return r
->n
== 1 && clast_expr_is_bigger_constant(e1
, r
->elts
[0]);
427 if (e1
->type
!= clast_expr_term
|| e2
->type
!= clast_expr_term
)
429 t1
= (struct clast_term
*)e1
;
430 t2
= (struct clast_term
*)e2
;
431 if (t1
->var
|| t2
->var
)
433 return cloog_int_gt(t1
->val
, t2
->val
);
436 static int qsort_expr_cmp(const void *p1
, const void *p2
)
438 return clast_expr_cmp(*(struct clast_expr
**)p1
, *(struct clast_expr
**)p2
);
441 static void clast_reduction_sort(struct clast_reduction
*r
)
443 qsort(&r
->elts
[0], r
->n
, sizeof(struct clast_expr
*), qsort_expr_cmp
);
446 static int qsort_eq_cmp(const void *p1
, const void *p2
)
448 struct clast_equation
*eq1
= (struct clast_equation
*)p1
;
449 struct clast_equation
*eq2
= (struct clast_equation
*)p2
;
452 cmp
= clast_expr_cmp(eq1
->LHS
, eq2
->LHS
);
456 cmp
= clast_expr_cmp(eq1
->RHS
, eq2
->RHS
);
460 return eq1
->sign
- eq2
->sign
;
464 * Sort equations in a clast_guard.
466 static void clast_guard_sort(struct clast_guard
*g
)
468 qsort(&g
->eq
[0], g
->n
, sizeof(struct clast_equation
), qsort_eq_cmp
);
473 * Construct a (deep) copy of an expression clast.
475 static struct clast_expr
*clast_expr_copy(struct clast_expr
*e
)
480 case clast_expr_name
: {
481 struct clast_name
* n
= (struct clast_name
*) e
;
482 return &new_clast_name(n
->name
)->expr
;
484 case clast_expr_term
: {
485 struct clast_term
* t
= (struct clast_term
*) e
;
486 return &new_clast_term(t
->val
, clast_expr_copy(t
->var
))->expr
;
488 case clast_expr_red
: {
490 struct clast_reduction
*r
= (struct clast_reduction
*) e
;
491 struct clast_reduction
*r2
= new_clast_reduction(r
->type
, r
->n
);
492 for (i
= 0; i
< r
->n
; ++i
)
493 r2
->elts
[i
] = clast_expr_copy(r
->elts
[i
]);
496 case clast_expr_bin
: {
497 struct clast_binary
*b
= (struct clast_binary
*) e
;
498 return &new_clast_binary(b
->type
, clast_expr_copy(b
->LHS
), b
->RHS
)->expr
;
506 /******************************************************************************
507 * Equalities spreading functions *
508 ******************************************************************************/
512 * clast_equal_allow function:
513 * This function checks whether the options allow us to spread the equality or
514 * not. It returns 1 if so, 0 otherwise.
515 * - equal is the matrix of equalities,
516 * - level is the column number in equal of the element which is 'equal to',
517 * - line is the line number in equal of the constraint we want to study,
518 * - the infos structure gives the user all options on code printing and more.
520 * - October 27th 2005: first version (extracted from old pprint_equal_add).
522 static int clast_equal_allow(CloogEqualities
*equal
, int level
, int line
,
525 if (level
< infos
->options
->fsp
)
528 if ((cloog_equal_type(equal
, level
) == EQTYPE_EXAFFINE
) &&
529 !infos
->options
->esp
)
537 * clast_equal_add function:
538 * This function updates the row (level-1) of the equality matrix (equal) with
539 * the row that corresponds to the row (line) of the matrix (matrix). It returns
540 * 1 if the row can be updated, 0 otherwise.
541 * - equal is the matrix of equalities,
542 * - matrix is the matrix of constraints,
543 * - level is the column number in matrix of the element which is 'equal to',
544 * - line is the line number in matrix of the constraint we want to study,
545 * - the infos structure gives the user all options on code printing and more.
547 static int clast_equal_add(CloogEqualities
*equal
,
548 CloogConstraintSet
*constraints
,
549 int level
, CloogConstraint
*constraint
,
552 cloog_equal_add(equal
, constraints
, level
, constraint
,
553 infos
->names
->nb_parameters
);
555 return clast_equal_allow(equal
, level
, level
-1, infos
);
561 * clast_equal function:
562 * This function prints the substitution data of a statement into a clast_stmt.
563 * Using this function instead of pprint_equal is useful for generating
564 * a compilable pseudo-code by using preprocessor macro for each statement.
565 * By opposition to pprint_equal, the result is less human-readable. For
566 * instance this function will print (i,i+3,k,3) where pprint_equal would
567 * return (j=i+3,l=3).
568 * - level is the number of loops enclosing the statement,
569 * - the infos structure gives the user all options on code printing and more.
571 * - March 12th 2004: first version.
572 * - November 21th 2005: (debug) now works well with GMP version.
574 static struct clast_stmt
*clast_equal(int level
, CloogInfos
*infos
)
577 struct clast_expr
*e
;
578 struct clast_stmt
*a
= NULL
;
579 struct clast_stmt
**next
= &a
;
580 CloogEqualities
*equal
= infos
->equal
;
581 CloogConstraint
*equal_constraint
;
583 for (i
=infos
->names
->nb_scattering
;i
<level
-1;i
++)
584 { if (cloog_equal_type(equal
, i
+1)) {
585 equal_constraint
= cloog_equal_constraint(equal
, i
);
586 e
= clast_bound_from_constraint(equal_constraint
, i
+1, infos
->names
);
587 cloog_constraint_release(equal_constraint
);
589 e
= &new_clast_term(infos
->state
->one
, &new_clast_name(
590 cloog_names_name_at_level(infos
->names
, i
+1))->expr
)->expr
;
592 *next
= &new_clast_assignment(NULL
, e
)->stmt
;
593 next
= &(*next
)->next
;
601 * clast_bound_from_constraint function:
602 * This function returns a clast_expr containing the printing of the
603 * 'right part' of a constraint according to an element.
604 * For instance, for the constraint -3*i + 2*j - M >=0 and the element j,
605 * we have j >= (3*i + M)/2. As we are looking for integral solutions, this
606 * function should return 'ceild(3*i+M,2)'.
607 * - matrix is the polyhedron containing all the constraints,
608 * - line_num is the line number in domain of the constraint we want to print,
609 * - level is the column number in domain of the element we want to use,
610 * - names structure gives the user some options about code printing,
611 * the number of parameters in domain (nb_par), and the arrays of iterator
612 * names and parameters (iters and params).
614 * - November 2nd 2001: first version.
615 * - June 27th 2003: 64 bits version ready.
617 struct clast_expr
*clast_bound_from_constraint(CloogConstraint
*constraint
,
618 int level
, CloogNames
*names
)
620 int i
, sign
, nb_elts
=0, len
;
621 cloog_int_t
*line
, numerator
, denominator
, temp
, division
;
622 struct clast_expr
*e
= NULL
;
623 struct cloog_vec
*line_vector
;
625 len
= cloog_constraint_total_dimension(constraint
) + 2;
626 line_vector
= cloog_vec_alloc(len
);
627 line
= line_vector
->p
;
628 cloog_constraint_copy_coefficients(constraint
, line
+1);
629 cloog_int_init(temp
);
630 cloog_int_init(numerator
);
631 cloog_int_init(denominator
);
633 if (!cloog_int_is_zero(line
[level
])) {
634 struct clast_reduction
*r
;
635 /* Maybe we need to invert signs in such a way that the element sign is>0.*/
636 sign
= -cloog_int_sgn(line
[level
]);
638 for (i
= 1, nb_elts
= 0; i
<= len
- 1; ++i
)
639 if (i
!= level
&& !cloog_int_is_zero(line
[i
]))
641 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
644 /* First, we have to print the iterators and the parameters. */
645 for (i
= 1; i
<= len
- 2; i
++) {
646 struct clast_expr
*v
;
648 if (i
== level
|| cloog_int_is_zero(line
[i
]))
651 v
= cloog_constraint_variable_expr(constraint
, i
, names
);
654 cloog_int_neg(temp
,line
[i
]);
656 cloog_int_set(temp
,line
[i
]);
658 r
->elts
[nb_elts
++] = &new_clast_term(temp
, v
)->expr
;
662 cloog_int_neg(numerator
, line
[len
- 1]);
663 cloog_int_set(denominator
, line
[level
]);
666 cloog_int_set(numerator
, line
[len
- 1]);
667 cloog_int_neg(denominator
, line
[level
]);
670 /* Finally, the constant, and the final printing. */
672 if (!cloog_int_is_zero(numerator
))
673 r
->elts
[nb_elts
++] = &new_clast_term(numerator
, NULL
)->expr
;
675 if (!cloog_int_is_one(line
[level
]) && !cloog_int_is_neg_one(line
[level
]))
676 { if (!cloog_constraint_is_equality(constraint
))
677 { if (cloog_int_is_pos(line
[level
]))
678 e
= &new_clast_binary(clast_bin_cdiv
, &r
->expr
, denominator
)->expr
;
680 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, denominator
)->expr
;
682 e
= &new_clast_binary(clast_bin_div
, &r
->expr
, denominator
)->expr
;
687 free_clast_reduction(r
);
688 if (cloog_int_is_zero(numerator
))
689 e
= &new_clast_term(numerator
, NULL
)->expr
;
691 { if (!cloog_int_is_one(denominator
))
692 { if (!cloog_constraint_is_equality(constraint
)) { /* useful? */
693 if (cloog_int_is_divisible_by(numerator
, denominator
)) {
694 cloog_int_divexact(temp
, numerator
, denominator
);
695 e
= &new_clast_term(temp
, NULL
)->expr
;
698 cloog_int_init(division
);
699 cloog_int_tdiv_q(division
, numerator
, denominator
);
700 if (cloog_int_is_neg(numerator
)) {
701 if (cloog_int_is_pos(line
[level
])) {
703 e
= &new_clast_term(division
, NULL
)->expr
;
706 cloog_int_sub_ui(temp
, division
, 1);
707 e
= &new_clast_term(temp
, NULL
)->expr
;
711 { if (cloog_int_is_pos(line
[level
]))
712 { /* nb>0 need max */
713 cloog_int_add_ui(temp
, division
, 1);
714 e
= &new_clast_term(temp
, NULL
)->expr
;
718 e
= &new_clast_term(division
, NULL
)->expr
;
720 cloog_int_clear(division
);
724 e
= &new_clast_binary(clast_bin_div
,
725 &new_clast_term(numerator
, NULL
)->expr
,
729 e
= &new_clast_term(numerator
, NULL
)->expr
;
734 cloog_vec_free(line_vector
);
736 cloog_int_clear(temp
);
737 cloog_int_clear(numerator
);
738 cloog_int_clear(denominator
);
744 /* Temporary structure for communication between clast_minmax and
745 * its cloog_constraint_set_foreach_constraint callback functions.
747 struct clast_minmax_data
{
754 struct clast_reduction
*r
;
758 /* Should constraint "c" be considered by clast_minmax?
760 static int valid_bound(CloogConstraint
*c
, struct clast_minmax_data
*d
)
762 if (d
->max
&& !cloog_constraint_is_lower_bound(c
, d
->level
- 1))
764 if (!d
->max
&& !cloog_constraint_is_upper_bound(c
, d
->level
- 1))
766 if (cloog_constraint_is_equality(c
))
768 if (d
->guard
&& cloog_constraint_involves(c
, d
->guard
- 1))
775 /* Increment n for each bound that should be considered by clast_minmax.
777 static int count_bounds(CloogConstraint
*c
, void *user
)
779 struct clast_minmax_data
*d
= (struct clast_minmax_data
*) user
;
781 if (!valid_bound(c
, d
))
790 /* Update the given lower bound based on stride information.
791 * In some backends, the lower bounds are updated from within
792 * cloog_loop_stride, but other backends leave the updating to
793 * this function. In the later case, the original lower bound
794 * is known to be a constant.
795 * If the bound turns out not to be a constant, we know we
796 * are in the former case and nothing needs to be done.
797 * If the bound has already been updated and it just happens
798 * to be a constant, then this function performs an identity
799 * operation on the constant.
801 static void update_lower_bound(struct clast_expr
*expr
, int level
,
804 struct clast_term
*t
;
805 if (stride
->constraint
)
807 if (expr
->type
!= clast_expr_term
)
809 t
= (struct clast_term
*)expr
;
812 cloog_int_sub(t
->val
, t
->val
, stride
->offset
);
813 cloog_int_cdiv_q(t
->val
, t
->val
, stride
->stride
);
814 cloog_int_mul(t
->val
, t
->val
, stride
->stride
);
815 cloog_int_add(t
->val
, t
->val
, stride
->offset
);
819 /* Add all relevant bounds to r->elts and update lower bounds
820 * based on stride information.
822 static int collect_bounds(CloogConstraint
*c
, void *user
)
824 struct clast_minmax_data
*d
= (struct clast_minmax_data
*) user
;
826 if (!valid_bound(c
, d
))
829 d
->r
->elts
[d
->n
] = clast_bound_from_constraint(c
, d
->level
,
831 if (d
->lower_bound
&& d
->infos
->stride
[d
->level
- 1]) {
832 update_lower_bound(d
->r
->elts
[d
->n
], d
->level
,
833 d
->infos
->stride
[d
->level
- 1]);
843 * clast_minmax function:
844 * This function returns a clast_expr containing the printing of a minimum or a
845 * maximum of the 'right parts' of all constraints according to an element.
846 * For instance consider the constraints:
850 * if we are looking for the minimum for the element j, the function should
851 * return 'max(ceild(3*i+M,2),-2*i)'.
852 * - constraints is the constraints,
853 * - level is the column number in domain of the element we want to use,
854 * - max is a boolean set to 1 if we are looking for a maximum, 0 for a minimum,
855 * - guard is set to 0 if there is no guard, and set to the level of the element
856 * with a guard otherwise (then the function gives the max or the min only
857 * for the constraint where the guarded coefficient is 0),
858 * - lower is set to 1 if the maximum is to be used a lower bound on a loop
859 * - the infos structure gives the user some options about code printing,
860 * the number of parameters in domain (nb_par), and the arrays of iterator
861 * names and parameters (iters and params).
863 * - November 2nd 2001: first version.
865 static struct clast_expr
*clast_minmax(CloogConstraintSet
*constraints
,
866 int level
, int max
, int guard
,
870 struct clast_minmax_data data
= { level
, max
, guard
, lower_bound
, infos
};
874 cloog_constraint_set_foreach_constraint(constraints
, count_bounds
, &data
);
878 data
.r
= new_clast_reduction(max
? clast_red_max
: clast_red_min
, data
.n
);
881 cloog_constraint_set_foreach_constraint(constraints
, collect_bounds
, &data
);
883 clast_reduction_sort(data
.r
);
884 return &data
.r
->expr
;
889 * Insert modulo guards defined by existentially quantified dimensions,
890 * not involving the given level.
892 * This function is called from within insert_guard.
893 * Any constraint used in constructing a modulo guard is removed
894 * from the constraint set to avoid insert_guard
895 * adding a duplicate (pair of) constraint(s).
897 static void insert_extra_modulo_guards(CloogConstraintSet
*constraints
,
898 int level
, struct clast_stmt
***next
, CloogInfos
*infos
)
903 CloogConstraint
*upper
, *lower
;
905 total_dim
= cloog_constraint_set_total_dimension(constraints
);
906 nb_iter
= cloog_constraint_set_n_iterators(constraints
,
907 infos
->names
->nb_parameters
);
909 for (i
= total_dim
- infos
->names
->nb_parameters
; i
>= nb_iter
+ 1; i
--) {
910 if (cloog_constraint_is_valid(upper
=
911 cloog_constraint_set_defining_equality(constraints
, i
))) {
912 if (!level
|| (nb_iter
< level
) ||
913 !cloog_constraint_involves(upper
, level
-1)) {
914 insert_modulo_guard(upper
,
915 cloog_constraint_invalid(), i
, next
, infos
);
916 cloog_constraint_clear(upper
);
918 cloog_constraint_release(upper
);
919 } else if (cloog_constraint_is_valid(upper
=
920 cloog_constraint_set_defining_inequalities(constraints
,
921 i
, &lower
, infos
->names
->nb_parameters
))) {
922 if (!level
|| (nb_iter
< level
) ||
923 !cloog_constraint_involves(upper
, level
-1)) {
924 insert_modulo_guard(upper
, lower
, i
, next
, infos
);
925 cloog_constraint_clear(upper
);
926 cloog_constraint_clear(lower
);
928 cloog_constraint_release(upper
);
929 cloog_constraint_release(lower
);
935 static int clear_lower_bound_at_level(CloogConstraint
*c
, void *user
)
937 int level
= *(int *)user
;
939 if (cloog_constraint_is_lower_bound(c
, level
- 1))
940 cloog_constraint_clear(c
);
946 static int clear_upper_bound_at_level(CloogConstraint
*c
, void *user
)
948 int level
= *(int *)user
;
950 if (cloog_constraint_is_upper_bound(c
, level
- 1))
951 cloog_constraint_clear(c
);
957 /* Temporary structure for communication between insert_guard and
958 * its cloog_constraint_set_foreach_constraint callback function.
960 struct clast_guard_data
{
966 CloogConstraintSet
*copy
;
967 struct clast_guard
*g
;
971 static int guard_count_bounds(CloogConstraint
*c
, void *user
)
973 struct clast_guard_data
*d
= (struct clast_guard_data
*) user
;
981 /* Insert a guard, if necesessary, for constraint j.
983 static int insert_guard_constraint(CloogConstraint
*j
, void *user
)
985 struct clast_guard_data
*d
= (struct clast_guard_data
*) user
;
987 struct clast_expr
*v
;
988 struct clast_term
*t
;
990 if (!cloog_constraint_involves(j
, d
->i
- 1))
993 if (d
->level
&& d
->nb_iter
>= d
->level
&&
994 cloog_constraint_involves(j
, d
->level
- 1))
997 v
= cloog_constraint_variable_expr(j
, d
->i
, d
->infos
->names
);
998 d
->g
->eq
[d
->n
].LHS
= &(t
= new_clast_term(d
->infos
->state
->one
, v
))->expr
;
999 if (!d
->level
|| cloog_constraint_is_equality(j
)) {
1000 /* put the "denominator" in the LHS */
1001 cloog_constraint_coefficient_get(j
, d
->i
- 1, &t
->val
);
1002 cloog_constraint_coefficient_set(j
, d
->i
- 1, d
->infos
->state
->one
);
1003 if (cloog_int_is_neg(t
->val
)) {
1004 cloog_int_neg(t
->val
, t
->val
);
1005 cloog_constraint_coefficient_set(j
, d
->i
- 1, d
->infos
->state
->negone
);
1007 if (d
->level
|| cloog_constraint_is_equality(j
))
1008 d
->g
->eq
[d
->n
].sign
= 0;
1009 else if (cloog_constraint_is_lower_bound(j
, d
->i
- 1))
1010 d
->g
->eq
[d
->n
].sign
= 1;
1012 d
->g
->eq
[d
->n
].sign
= -1;
1013 d
->g
->eq
[d
->n
].RHS
= clast_bound_from_constraint(j
, d
->i
, d
->infos
->names
);
1017 if (cloog_constraint_is_lower_bound(j
, d
->i
- 1)) {
1019 d
->g
->eq
[d
->n
].sign
= 1;
1022 d
->g
->eq
[d
->n
].sign
= -1;
1025 guarded
= (d
->nb_iter
>= d
->level
) ? d
->level
: 0 ;
1026 d
->g
->eq
[d
->n
].RHS
= clast_minmax(d
->copy
, d
->i
, minmax
, guarded
, 0,
1031 /* 'elimination' of the current constraint, this avoid to use one
1032 * constraint more than once. The current line is always eliminated,
1033 * and the next lines if they are in a min or a max.
1035 cloog_constraint_clear(j
);
1040 cloog_constraint_set_foreach_constraint(d
->copy
,
1041 clear_lower_bound_at_level
, &d
->i
);
1042 else if (minmax
== 0)
1043 cloog_constraint_set_foreach_constraint(d
->copy
,
1044 clear_upper_bound_at_level
, &d
->i
);
1051 * insert_guard function:
1052 * This function inserts a guard in the clast.
1053 * A guard on an element (level) is :
1054 * -> the conjunction of all the existing constraints where the coefficient of
1055 * this element is 0 if the element is an iterator,
1056 * -> the conjunction of all the existing constraints if the element isn't an
1058 * For instance, considering these constraints and the element j:
1061 * this function should return 'if (2*i+M>=0) {'.
1062 * - matrix is the polyhedron containing all the constraints,
1063 * - level is the column number of the element in matrix we want to use,
1064 * - the infos structure gives the user some options about code printing,
1065 * the number of parameters in matrix (nb_par), and the arrays of iterator
1066 * names and parameters (iters and params).
1068 * - November 3rd 2001: first version.
1069 * - November 14th 2001: a lot of 'purifications'.
1070 * - July 31th 2002: (debug) some guard parts are no more redundants.
1071 * - August 12th 2002: polyhedra union ('or' conditions) are now supported.
1072 * - October 27th 2005: polyhedra union ('or' conditions) are no more supported
1073 * (the need came from loop_simplify that may result in
1074 * domain unions, now it should be fixed directly in
1075 * cloog_loop_simplify).
1077 static void insert_guard(CloogConstraintSet
*constraints
, int level
,
1078 struct clast_stmt
***next
, CloogInfos
*infos
)
1081 struct clast_guard_data data
= { level
, infos
, 0 };
1086 data
.copy
= cloog_constraint_set_copy(constraints
);
1088 insert_extra_modulo_guards(data
.copy
, level
, next
, infos
);
1090 cloog_constraint_set_foreach_constraint(constraints
,
1091 guard_count_bounds
, &data
);
1093 data
.g
= new_clast_guard(data
.n
);
1096 /* Well, it looks complicated because I wanted to have a particular, more
1097 * readable, ordering, obviously this function may be far much simpler !
1099 data
.nb_iter
= cloog_constraint_set_n_iterators(constraints
,
1100 infos
->names
->nb_parameters
);
1102 /* We search for guard parts. */
1103 total_dim
= cloog_constraint_set_total_dimension(constraints
);
1104 for (data
.i
= 1; data
.i
<= total_dim
; data
.i
++)
1105 cloog_constraint_set_foreach_constraint(data
.copy
,
1106 insert_guard_constraint
, &data
);
1108 cloog_constraint_set_free(data
.copy
);
1112 clast_guard_sort(data
.g
);
1113 **next
= &data
.g
->stmt
;
1114 *next
= &data
.g
->then
;
1116 free_clast_stmt(&data
.g
->stmt
);
1120 * Check if the constant "cst" satisfies the modulo guard that
1121 * would be introduced by insert_computed_modulo_guard.
1122 * The constant is assumed to have been reduced prior to calling
1125 static int constant_modulo_guard_is_satisfied(CloogConstraint
*lower
,
1126 cloog_int_t bound
, cloog_int_t cst
)
1128 if (cloog_constraint_is_valid(lower
))
1129 return cloog_int_le(cst
, bound
);
1131 return cloog_int_is_zero(cst
);
1135 * Insert a modulo guard "r % mod == 0" or "r % mod <= bound",
1136 * depending on whether lower represents a valid constraint.
1138 static void insert_computed_modulo_guard(struct clast_reduction
*r
,
1139 CloogConstraint
*lower
, cloog_int_t mod
, cloog_int_t bound
,
1140 struct clast_stmt
***next
)
1142 struct clast_expr
*e
;
1143 struct clast_guard
*g
;
1145 e
= &new_clast_binary(clast_bin_mod
, &r
->expr
, mod
)->expr
;
1146 g
= new_clast_guard(1);
1147 if (!cloog_constraint_is_valid(lower
)) {
1149 cloog_int_set_si(bound
, 0);
1150 g
->eq
[0].RHS
= &new_clast_term(bound
, NULL
)->expr
;
1154 g
->eq
[0].RHS
= &new_clast_term(bound
, NULL
)->expr
;
1163 /* Try and eliminate coefficients from a modulo constraint based on
1164 * stride information of an earlier level.
1165 * The modulo of the constraint being constructed is "m".
1166 * The stride information at level "level" is given by "stride"
1167 * and indicated that the iterator i at level "level" is equal to
1168 * some expression modulo stride->stride.
1169 * If stride->stride is a multiple of "m' then i is also equal to
1170 * the expression modulo m and so we can eliminate the coefficient of i.
1172 * If stride->constraint is NULL, then i has a constant value modulo m, stored
1173 * stride->offset. We simply multiply this constant with the coefficient
1174 * of i and add the result to the constant term, reducing it modulo m.
1176 * If stride->constraint is not NULL, then it is a constraint of the form
1180 * with s equal to stride->stride, e an expression in terms of the
1181 * parameters and earlier iterators and a some arbitrary expression
1182 * in terms of existentially quantified variables.
1183 * stride->factor is a value f such that f * k = -1 mod s.
1184 * Adding stride->constraint f * c times to the current modulo constraint,
1185 * with c the coefficient of i eliminates i in favor of parameters and
1186 * earlier variables.
1188 static void eliminate_using_stride_constraint(cloog_int_t
*line
, int len
,
1189 int nb_iter
, CloogStride
*stride
, int level
, cloog_int_t m
)
1193 if (!cloog_int_is_divisible_by(stride
->stride
, m
))
1196 if (stride
->constraint
) {
1202 cloog_int_mul(t
, line
[level
], stride
->factor
);
1203 for (i
= 1; i
< level
; ++i
) {
1204 cloog_constraint_coefficient_get(stride
->constraint
,
1206 cloog_int_addmul(line
[i
], t
, v
);
1207 cloog_int_fdiv_r(line
[i
], line
[i
], m
);
1209 for (i
= nb_iter
+ 1; i
<= len
- 2; ++i
) {
1210 cloog_constraint_coefficient_get(stride
->constraint
,
1211 i
- nb_iter
- 1 + level
, &v
);
1212 cloog_int_addmul(line
[i
], t
, v
);
1213 cloog_int_fdiv_r(line
[i
], line
[i
], m
);
1215 cloog_constraint_constant_get(stride
->constraint
, &v
);
1216 cloog_int_addmul(line
[len
- 1], t
, v
);
1217 cloog_int_fdiv_r(line
[len
- 1], line
[len
- 1], m
);
1221 cloog_int_addmul(line
[len
- 1], line
[level
], stride
->offset
);
1222 cloog_int_fdiv_r(line
[len
- 1], line
[len
- 1], m
);
1225 cloog_int_set_si(line
[level
], 0);
1229 /* Temporary structure for communication between insert_modulo_guard and
1230 * its cloog_constraint_set_foreach_constraint callback function.
1232 struct clast_modulo_guard_data
{
1233 CloogConstraint
*lower
;
1235 struct clast_stmt
***next
;
1238 cloog_int_t val
, bound
;
1242 /* Insert a modulo guard for constraint c.
1243 * The constraint may be either an equality or an inequality.
1244 * Since this function returns -1, it is only called on a single constraint.
1245 * In case of an inequality, the constraint is usually an upper bound
1246 * on d->level. However, if this variable is an existentially
1247 * quantified variable, the upper bound constraint may get removed
1248 * as trivially holding and then this function is called with
1249 * a lower bound instead. In this case, we need to adjust the constraint
1250 * based on the sum of the constant terms of the lower and upper bound
1251 * stored in d->bound.
1253 static int insert_modulo_guard_constraint(CloogConstraint
*c
, void *user
)
1255 struct clast_modulo_guard_data
*d
= (struct clast_modulo_guard_data
*) user
;
1256 int level
= d
->level
;
1257 CloogInfos
*infos
= d
->infos
;
1258 int i
, nb_elts
= 0, len
, len2
, nb_iter
, nb_par
;
1260 struct cloog_vec
*line_vector
;
1263 len
= cloog_constraint_total_dimension(c
) + 2;
1264 len2
= cloog_equal_total_dimension(infos
->equal
) + 2;
1265 nb_par
= infos
->names
->nb_parameters
;
1266 nb_iter
= len
- 2 - nb_par
;
1268 line_vector
= cloog_vec_alloc(len
);
1269 line
= line_vector
->p
;
1270 cloog_constraint_copy_coefficients(c
, line
+ 1);
1272 if (cloog_int_is_pos(line
[level
])) {
1273 cloog_seq_neg(line
+ 1, line
+ 1, len
- 1);
1274 if (!cloog_constraint_is_equality(c
))
1275 cloog_int_add(line
[len
- 1], line
[len
- 1], d
->bound
);
1277 cloog_int_neg(line
[level
], line
[level
]);
1278 assert(cloog_int_is_pos(line
[level
]));
1281 for (i
= 1; i
<= len
-1; ++i
) {
1284 cloog_int_fdiv_r(line
[i
], line
[i
], line
[level
]);
1285 if (cloog_int_is_zero(line
[i
]))
1293 if (nb_elts
|| !cloog_int_is_zero(line
[len
-1])) {
1294 struct clast_reduction
*r
;
1297 r
= new_clast_reduction(clast_red_sum
, nb_elts
+ 1);
1300 /* First, the modulo guard : the iterators... */
1301 for (i
= level
- 1; i
>= 1; --i
)
1302 eliminate_using_stride_constraint(line
, len
, nb_iter
,
1303 infos
->stride
[i
- 1], i
, line
[level
]);
1304 for (i
=1;i
<=nb_iter
;i
++) {
1305 if (i
== level
|| cloog_int_is_zero(line
[i
]))
1308 name
= cloog_names_name_at_level(infos
->names
, i
);
1310 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
],
1311 &new_clast_name(name
)->expr
)->expr
;
1314 /* ...the parameters... */
1315 for (i
=nb_iter
+1;i
<=len
-2;i
++) {
1316 if (cloog_int_is_zero(line
[i
]))
1319 name
= infos
->names
->parameters
[i
-nb_iter
-1] ;
1320 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
],
1321 &new_clast_name(name
)->expr
)->expr
;
1324 constant
= nb_elts
== 0;
1325 /* ...the constant. */
1326 if (!cloog_int_is_zero(line
[len
-1]))
1327 r
->elts
[nb_elts
++] = &new_clast_term(line
[len
-1], NULL
)->expr
;
1329 /* our initial computation may have been an overestimate */
1333 d
->empty
= !constant_modulo_guard_is_satisfied(d
->lower
, d
->bound
,
1335 free_clast_reduction(r
);
1337 insert_computed_modulo_guard(r
, d
->lower
, line
[level
], d
->bound
,
1341 cloog_vec_free(line_vector
);
1348 * insert_modulo_guard:
1349 * This function inserts a modulo guard corresponding to an equality
1350 * or a pair of inequalities.
1351 * Returns 0 if the modulo guard is discovered to be unsatisfiable.
1353 * See insert_equation.
1354 * - matrix is the polyhedron containing all the constraints,
1355 * - upper and lower are the line numbers of the constraint in matrix
1356 * we want to print; in particular, if we want to print an equality,
1357 * then lower == -1 and upper is the row of the equality; if we want
1358 * to print an inequality, then upper is the row of the upper bound
1359 * and lower in the row of the lower bound
1360 * - level is the column number of the element in matrix we want to use,
1361 * - the infos structure gives the user some options about code printing,
1362 * the number of parameters in matrix (nb_par), and the arrays of iterator
1363 * names and parameters (iters and params).
1365 static int insert_modulo_guard(CloogConstraint
*upper
,
1366 CloogConstraint
*lower
, int level
,
1367 struct clast_stmt
***next
, CloogInfos
*infos
)
1370 CloogConstraintSet
*set
;
1371 struct clast_modulo_guard_data data
= { lower
, level
, next
, infos
, 0 };
1373 cloog_int_init(data
.val
);
1374 cloog_constraint_coefficient_get(upper
, level
-1, &data
.val
);
1375 if (cloog_int_is_one(data
.val
) || cloog_int_is_neg_one(data
.val
)) {
1376 cloog_int_clear(data
.val
);
1380 nb_par
= infos
->names
->nb_parameters
;
1382 cloog_int_init(data
.bound
);
1383 /* Check if would be emitting the redundant constraint mod(e,m) <= m-1 */
1384 if (cloog_constraint_is_valid(lower
)) {
1385 cloog_constraint_constant_get(upper
, &data
.val
);
1386 cloog_constraint_constant_get(lower
, &data
.bound
);
1387 cloog_int_add(data
.bound
, data
.val
, data
.bound
);
1388 cloog_constraint_coefficient_get(lower
, level
-1, &data
.val
);
1389 cloog_int_sub_ui(data
.val
, data
.val
, 1);
1390 if (cloog_int_eq(data
.val
, data
.bound
)) {
1391 cloog_int_clear(data
.val
);
1392 cloog_int_clear(data
.bound
);
1397 set
= cloog_constraint_set_for_reduction(upper
, lower
);
1398 set
= cloog_constraint_set_reduce(set
, level
, infos
->equal
, nb_par
, &data
.bound
);
1399 cloog_constraint_set_foreach_constraint(set
,
1400 insert_modulo_guard_constraint
, &data
);
1402 cloog_constraint_set_free(set
);
1403 cloog_int_clear(data
.val
);
1404 cloog_int_clear(data
.bound
);
1411 * We found an equality or a pair of inequalities identifying
1412 * a loop with a single iteration, but the user wants us to generate
1413 * a loop anyway, so we do it here.
1415 static int insert_equation_as_loop(CloogConstraint
*upper
,
1416 CloogConstraint
*lower
, int level
, struct clast_stmt
***next
,
1419 const char *iterator
= cloog_names_name_at_level(infos
->names
, level
);
1420 struct clast_expr
*e1
, *e2
;
1421 struct clast_for
*f
;
1423 e2
= clast_bound_from_constraint(upper
, level
, infos
->names
);
1424 if (!cloog_constraint_is_valid(lower
))
1425 e1
= clast_expr_copy(e2
);
1427 e1
= clast_bound_from_constraint(lower
, level
, infos
->names
);
1428 f
= new_clast_for(iterator
, e1
, e2
, infos
->stride
[level
-1]);
1432 cloog_constraint_release(lower
);
1433 cloog_constraint_release(upper
);
1439 * insert_equation function:
1440 * This function inserts an equality
1441 * constraint according to an element in the clast.
1442 * Returns 1 if the calling function should recurse into inner loops.
1444 * An equality can be preceded by a 'modulo guard'.
1445 * For instance, consider the constraint i -2*j = 0 and the
1446 * element j: pprint_equality should return 'if(i%2==0) { j = i/2 ;'.
1447 * - matrix is the polyhedron containing all the constraints,
1448 * - num is the line number of the constraint in matrix we want to print,
1449 * - level is the column number of the element in matrix we want to use,
1450 * - the infos structure gives the user some options about code printing,
1451 * the number of parameters in matrix (nb_par), and the arrays of iterator
1452 * names and parameters (iters and params).
1454 * - November 13th 2001: first version.
1455 * - June 26th 2003: simplification of the modulo guards (remove parts such as
1456 * modulo is 0, compare vivien or vivien2 with a previous
1457 * version for an idea).
1458 * - June 29th 2003: non-unit strides support.
1459 * - July 14th 2003: (debug) no more print the constant in the modulo guard when
1460 * it was previously included in a stride calculation.
1462 static int insert_equation(CloogConstraint
*upper
, CloogConstraint
*lower
,
1463 int level
, struct clast_stmt
***next
, CloogInfos
*infos
)
1465 struct clast_expr
*e
;
1466 struct clast_assignment
*ass
;
1468 if (!infos
->options
->otl
)
1469 return insert_equation_as_loop(upper
, lower
, level
, next
, infos
);
1471 if (!insert_modulo_guard(upper
, lower
, level
, next
, infos
)) {
1472 cloog_constraint_release(lower
);
1473 cloog_constraint_release(upper
);
1478 if (cloog_constraint_is_valid(lower
) ||
1479 !clast_equal_add(infos
->equal
, NULL
, level
, upper
, infos
))
1480 { /* Finally, the equality. */
1482 /* If we have to make a block by dimension, we start the block. Function
1483 * pprint knows if there is an equality, if this is the case, it checks
1484 * for the same following condition to close the brace.
1486 if (infos
->options
->block
) {
1487 struct clast_block
*b
= new_clast_block();
1492 e
= clast_bound_from_constraint(upper
, level
, infos
->names
);
1493 ass
= new_clast_assignment(cloog_names_name_at_level(infos
->names
, level
), e
);
1495 **next
= &ass
->stmt
;
1496 *next
= &(**next
)->next
;
1499 cloog_constraint_release(lower
);
1500 cloog_constraint_release(upper
);
1507 * Insert a loop that is executed exactly once as an assignment.
1508 * In particular, the loop
1510 * for (i = e; i <= e; ++i) {
1520 static void insert_otl_for(CloogConstraintSet
*constraints
, int level
,
1521 struct clast_expr
*e
, struct clast_stmt
***next
, CloogInfos
*infos
)
1523 const char *iterator
;
1525 iterator
= cloog_names_name_at_level(infos
->names
, level
);
1527 if (!clast_equal_add(infos
->equal
, constraints
, level
,
1528 cloog_constraint_invalid(), infos
)) {
1529 struct clast_assignment
*ass
;
1530 if (infos
->options
->block
) {
1531 struct clast_block
*b
= new_clast_block();
1535 ass
= new_clast_assignment(iterator
, e
);
1536 **next
= &ass
->stmt
;
1537 *next
= &(**next
)->next
;
1545 * Insert a loop that is executed at most once as an assignment followed
1546 * by a guard. In particular, the loop
1548 * for (i = e1; i <= e2; ++i) {
1560 static void insert_guarded_otl_for(CloogConstraintSet
*constraints
, int level
,
1561 struct clast_expr
*e1
, struct clast_expr
*e2
,
1562 struct clast_stmt
***next
, CloogInfos
*infos
)
1564 const char *iterator
;
1565 struct clast_assignment
*ass
;
1566 struct clast_guard
*guard
;
1568 iterator
= cloog_names_name_at_level(infos
->names
, level
);
1570 if (infos
->options
->block
) {
1571 struct clast_block
*b
= new_clast_block();
1575 ass
= new_clast_assignment(iterator
, e1
);
1576 **next
= &ass
->stmt
;
1577 *next
= &(**next
)->next
;
1579 guard
= new_clast_guard(1);
1580 guard
->eq
[0].sign
= -1;
1581 guard
->eq
[0].LHS
= &new_clast_term(infos
->state
->one
,
1582 &new_clast_name(iterator
)->expr
)->expr
;
1583 guard
->eq
[0].RHS
= e2
;
1585 **next
= &guard
->stmt
;
1586 *next
= &guard
->then
;
1591 * insert_for function:
1592 * This function inserts a for loop in the clast.
1593 * Returns 1 if the calling function should recurse into inner loops.
1595 * A loop header according to an element is the conjunction of a minimum and a
1596 * maximum on a given element (they give the loop bounds).
1597 * For instance, considering these constraints and the element j:
1601 * this function should return 'for (j=max(-i+9*M,4*M),j<=5*M;j++) {'.
1602 * - constraints contains all constraints,
1603 * - level is the column number of the element in matrix we want to use,
1604 * - otl is set if the loop is executed at most once,
1605 * - the infos structure gives the user some options about code printing,
1606 * the number of parameters in matrix (nb_par), and the arrays of iterator
1607 * names and parameters (iters and params).
1609 static int insert_for(CloogConstraintSet
*constraints
, int level
, int otl
,
1610 struct clast_stmt
***next
, CloogInfos
*infos
)
1612 const char *iterator
;
1613 struct clast_expr
*e1
;
1614 struct clast_expr
*e2
;
1616 e1
= clast_minmax(constraints
, level
, 1, 0, 1, infos
);
1617 e2
= clast_minmax(constraints
, level
, 0, 0, 0, infos
);
1619 if (clast_expr_is_bigger_constant(e1
, e2
)) {
1620 free_clast_expr(e1
);
1621 free_clast_expr(e2
);
1625 /* If min and max are not equal there is a 'for' else, there is a '='.
1626 * In the special case e1 = e2 = NULL, this is an infinite loop
1627 * so this is not a '='.
1629 if (e1
&& e2
&& infos
->options
->otl
&& clast_expr_equal(e1
, e2
)) {
1630 free_clast_expr(e2
);
1631 insert_otl_for(constraints
, level
, e1
, next
, infos
);
1633 insert_guarded_otl_for(constraints
, level
, e1
, e2
, next
, infos
);
1635 struct clast_for
*f
;
1636 iterator
= cloog_names_name_at_level(infos
->names
, level
);
1637 f
= new_clast_for(iterator
, e1
, e2
, infos
->stride
[level
-1]);
1647 * insert_block function:
1648 * This function inserts a statement block.
1649 * - block is the statement block,
1650 * - level is the number of loops enclosing the statement,
1651 * - the infos structure gives the user some options about code printing,
1652 * the number of parameters in domain (nb_par), and the arrays of iterator
1653 * names and parameters (iters and params).
1655 * - September 21th 2003: first version (pick from pprint function).
1657 static void insert_block(CloogDomain
*domain
, CloogBlock
*block
, int level
,
1658 struct clast_stmt
***next
, CloogInfos
*infos
)
1660 CloogStatement
* statement
;
1661 struct clast_stmt
*subs
;
1666 for (statement
= block
->statement
; statement
; statement
= statement
->next
) {
1667 CloogStatement
*s_next
= statement
->next
;
1669 subs
= clast_equal(level
,infos
);
1671 statement
->next
= NULL
;
1672 **next
= &new_clast_user_stmt(domain
, statement
, subs
)->stmt
;
1673 statement
->next
= s_next
;
1674 *next
= &(**next
)->next
;
1680 * insert_loop function:
1681 * This function converts the content of a CloogLoop structure (loop) into a
1682 * clast_stmt (inserted at **next).
1683 * The iterator (level) of
1684 * the current loop is given by 'level': this is the column number of the
1685 * domain corresponding to the current loop iterator. The data of a loop are
1686 * written in this order:
1687 * 1. The guard of the loop, i.e. each constraint in the domain that does not
1688 * depend on the iterator (when the entry in the column 'level' is 0).
1689 * 2. The iteration domain of the iterator, given by the constraints in the
1690 * domain depending on the iterator, i.e.:
1691 * * an equality if the iterator has only one value (possibly preceded by
1692 * a guard verifying if this value is integral), *OR*
1693 * * a loop from the minimum possible value of the iterator to the maximum
1695 * 3. The included statement block.
1696 * 4. The inner loops (recursive call).
1697 * 5. The following loops (recursive call).
1698 * - level is the recursion level or the iteration level that we are printing,
1699 * - the infos structure gives the user some options about code printing,
1700 * the number of parameters in domain (nb_par), and the arrays of iterator
1701 * names and parameters (iters and params).
1703 * - November 2nd 2001: first version.
1704 * - March 6th 2003: infinite domain support.
1705 * - April 19th 2003: (debug) NULL loop support.
1706 * - June 29th 2003: non-unit strides support.
1707 * - April 28th 2005: (debug) level is level+equality when print statement!
1708 * - June 16th 2005: (debug) the N. Vasilache normalization step has been
1709 * added to avoid iteration duplication (see DaeGon Kim
1710 * bug in cloog_program_generate). Try vasilache.cloog
1711 * with and without the call to cloog_polylib_matrix_normalize,
1712 * using -f 8 -l 9 options for an idea.
1713 * - September 15th 2005: (debug) don't close equality braces when unnecessary.
1714 * - October 16th 2005: (debug) scalar value is saved for next loops.
1716 static void insert_loop(CloogLoop
* loop
, int level
,
1717 struct clast_stmt
***next
, CloogInfos
*infos
)
1720 CloogConstraintSet
*constraints
, *temp
;
1721 struct clast_stmt
**top
= *next
;
1722 CloogConstraint
*i
, *j
;
1725 /* It can happen that loop be NULL when an input polyhedron is empty. */
1729 /* The constraints do not always have a shape that allows us to generate code from it,
1730 * thus we normalize it, we also simplify it with the equalities.
1732 temp
= cloog_domain_constraints(loop
->domain
);
1733 cloog_constraint_set_normalize(temp
,level
);
1734 constraints
= cloog_constraint_set_simplify(temp
,infos
->equal
,level
,
1735 infos
->names
->nb_parameters
);
1736 cloog_constraint_set_free(temp
);
1738 infos
->stride
[level
- 1] = loop
->stride
;
1740 /* First of all we have to print the guard. */
1741 insert_guard(constraints
,level
, next
, infos
);
1743 if (level
&& cloog_constraint_set_contains_level(constraints
, level
,
1744 infos
->names
->nb_parameters
)) {
1745 /* We scan all the constraints to know in which case we are :
1746 * [[if] equation] or [for].
1748 if (cloog_constraint_is_valid(i
=
1749 cloog_constraint_set_defining_equality(constraints
, level
))) {
1750 empty_loop
= !insert_equation(i
, cloog_constraint_invalid(),
1751 level
, next
, infos
);
1753 } else if (cloog_constraint_is_valid(i
=
1754 cloog_constraint_set_defining_inequalities(constraints
,
1755 level
, &j
, infos
->names
->nb_parameters
))) {
1756 empty_loop
= !insert_equation(i
, j
, level
, next
, infos
);
1758 empty_loop
= !insert_for(constraints
, level
, loop
->otl
, next
, infos
);
1762 /* Finally, if there is an included statement block, print it. */
1763 insert_block(loop
->unsimplified
, loop
->block
, level
+equality
, next
, infos
);
1765 /* Go to the next level. */
1766 if (loop
->inner
!= NULL
)
1767 insert_loop(loop
->inner
, level
+1, next
, infos
);
1771 cloog_equal_del(infos
->equal
,level
);
1772 cloog_constraint_set_free(constraints
);
1774 /* Go to the next loop on the same level. */
1776 top
= &(*top
)->next
;
1777 if (loop
->next
!= NULL
)
1778 insert_loop(loop
->next
, level
, &top
,infos
);
1782 struct clast_stmt
*cloog_clast_create(CloogProgram
*program
,
1783 CloogOptions
*options
)
1785 CloogInfos
*infos
= ALLOC(CloogInfos
);
1787 struct clast_stmt
*root
= &new_clast_root(program
->names
)->stmt
;
1788 struct clast_stmt
**next
= &root
->next
;
1790 infos
->state
= options
->state
;
1791 infos
->names
= program
->names
;
1792 infos
->options
= options
;
1793 infos
->scaldims
= program
->scaldims
;
1794 infos
->nb_scattdims
= program
->nb_scattdims
;
1796 /* Allocation for the array of strides, there is a +1 since the statement can
1797 * be included inside an external loop without iteration domain.
1799 nb_levels
= program
->names
->nb_scattering
+program
->names
->nb_iterators
+1;
1800 infos
->stride
= ALLOCN(CloogStride
*, nb_levels
);
1802 infos
->equal
= cloog_equal_alloc(nb_levels
,
1803 nb_levels
, program
->names
->nb_parameters
);
1805 insert_loop(program
->loop
, 0, &next
, infos
);
1807 cloog_equal_free(infos
->equal
);
1809 free(infos
->stride
);
1816 struct clast_stmt
*cloog_clast_create_from_input(CloogInput
*input
,
1817 CloogOptions
*options
)
1819 CloogProgram
*program
;
1820 struct clast_stmt
*root
;
1822 program
= cloog_program_alloc(input
->context
, input
->ud
, options
);
1825 program
= cloog_program_generate(program
, options
);
1827 root
= cloog_clast_create(program
, options
);
1828 cloog_program_free(program
);