3 #include "../include/cloog/cloog.h"
5 #define ALLOC(type) (type*)malloc(sizeof(type))
6 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
9 * CloogInfos structure:
10 * this structure contains all the informations necessary for pretty printing,
11 * they come from the original CloogProgram structure (language, names), from
12 * genereral options (options) or are built only for pretty printing (stride).
13 * This structure is mainly there to reduce the number of function parameters,
14 * since most pprint.c functions need most of its field.
17 { Value
* stride
; /**< The stride for each iterator. */
18 int nb_scattdims
; /**< Scattering dimension number. */
19 int * scaldims
; /**< Boolean array saying whether a given
20 * scattering dimension is scalar or not.
22 CloogNames
* names
; /**< Names of iterators and parameters. */
23 CloogOptions
* options
; /**< Options on CLooG's behaviour. */
24 CloogMatrix
*equal
; /**< Matrix of equalities. */
27 typedef struct clooginfos CloogInfos
;
29 static int clast_term_equal(struct clast_term
*t1
, struct clast_term
*t2
);
30 static int clast_binary_equal(struct clast_binary
*b1
, struct clast_binary
*b2
);
31 static int clast_reduction_equal(struct clast_reduction
*r1
,
32 struct clast_reduction
*r2
);
34 static int clast_equal_type(CloogMatrix
*equal
, int level
, int line
);
35 static int clast_equal_add(CloogMatrix
*equal
, CloogMatrix
*matrix
, int level
,
36 int line
, CloogInfos
*infos
);
37 static void clast_equal_del(CloogMatrix
* equal
, int level
);
39 static struct clast_stmt
* clast_equal(CloogInfos
*infos
);
40 static struct clast_stmt
* clast_equal_cpp(int level
, CloogInfos
*infos
);
41 static struct clast_expr
*clast_minmax(CloogMatrix
*matrix
,
42 int level
, int max
, int guard
,
44 static void insert_guard(CloogMatrix
*matrix
, int level
,
45 struct clast_stmt
***next
, CloogInfos
*infos
);
46 static void insert_modulo_guard(CloogMatrix
*matrix
, int num
, int level
,
47 struct clast_stmt
***next
, CloogInfos
*infos
);
48 static void insert_equality(CloogMatrix
*matrix
, int num
,
49 int level
, struct clast_stmt
***next
, CloogInfos
*infos
);
50 static void insert_for(CloogMatrix
*matrix
, int level
,
51 struct clast_stmt
***next
, CloogInfos
*infos
);
52 static void insert_scalar(CloogLoop
*loop
, int level
, int *scalar
,
53 struct clast_stmt
***next
, CloogInfos
*infos
);
54 static void insert_block(CloogBlock
*block
, int level
,
55 struct clast_stmt
***next
, CloogInfos
*infos
);
56 static void insert_loop(CloogLoop
* loop
, int level
, int scalar
,
57 struct clast_stmt
***next
, CloogInfos
*infos
);
60 struct clast_term
*new_clast_term(Value c
, const char *v
)
62 struct clast_term
*t
= malloc(sizeof(struct clast_term
));
63 t
->expr
.type
= expr_term
;
65 value_assign(t
->val
, c
);
70 struct clast_binary
*new_clast_binary(enum clast_bin_type t
,
71 struct clast_expr
*lhs
, Value rhs
)
73 struct clast_binary
*b
= malloc(sizeof(struct clast_binary
));
74 b
->expr
.type
= expr_bin
;
78 value_assign(b
->RHS
, rhs
);
82 struct clast_reduction
*new_clast_reduction(enum clast_red_type t
, int n
)
85 struct clast_reduction
*r
;
86 r
= malloc(sizeof(struct clast_reduction
)+(n
-1)*sizeof(struct clast_expr
*));
87 r
->expr
.type
= expr_red
;
90 for (i
= 0; i
< n
; ++i
)
95 static void free_clast_root(struct clast_stmt
*s
);
97 struct clast_stmt_op stmt_root
= { free_clast_root
};
99 static void free_clast_root(struct clast_stmt
*s
)
101 struct clast_root
*r
= (struct clast_root
*)s
;
102 assert(CLAST_STMT_IS_A(s
, stmt_root
));
103 cloog_names_free(r
->names
);
107 struct clast_root
*new_clast_root(CloogNames
*names
)
109 struct clast_root
*r
= malloc(sizeof(struct clast_root
));
110 r
->stmt
.op
= &stmt_root
;
112 r
->names
= cloog_names_copy(names
);
116 static void free_clast_assignment(struct clast_stmt
*s
);
118 struct clast_stmt_op stmt_ass
= { free_clast_assignment
};
120 static void free_clast_assignment(struct clast_stmt
*s
)
122 struct clast_assignment
*a
= (struct clast_assignment
*)s
;
123 assert(CLAST_STMT_IS_A(s
, stmt_ass
));
124 free_clast_expr(a
->RHS
);
128 struct clast_assignment
*new_clast_assignment(const char *lhs
,
129 struct clast_expr
*rhs
)
131 struct clast_assignment
*a
= malloc(sizeof(struct clast_assignment
));
132 a
->stmt
.op
= &stmt_ass
;
139 static void free_clast_user_stmt(struct clast_stmt
*s
);
141 struct clast_stmt_op stmt_user
= { free_clast_user_stmt
};
143 static void free_clast_user_stmt(struct clast_stmt
*s
)
145 struct clast_user_stmt
*u
= (struct clast_user_stmt
*)s
;
146 assert(CLAST_STMT_IS_A(s
, stmt_user
));
147 cloog_clast_free(u
->substitutions
);
151 struct clast_user_stmt
*new_clast_user_stmt(CloogStatement
*stmt
,
152 struct clast_stmt
*subs
)
154 struct clast_user_stmt
*u
= malloc(sizeof(struct clast_user_stmt
));
155 u
->stmt
.op
= &stmt_user
;
158 u
->substitutions
= subs
;
162 static void free_clast_block(struct clast_stmt
*b
);
164 struct clast_stmt_op stmt_block
= { free_clast_block
};
166 static void free_clast_block(struct clast_stmt
*s
)
168 struct clast_block
*b
= (struct clast_block
*)s
;
169 assert(CLAST_STMT_IS_A(s
, stmt_block
));
170 cloog_clast_free(b
->body
);
174 struct clast_block
*new_clast_block()
176 struct clast_block
*b
= malloc(sizeof(struct clast_block
));
177 b
->stmt
.op
= &stmt_block
;
183 static void free_clast_for(struct clast_stmt
*s
);
185 struct clast_stmt_op stmt_for
= { free_clast_for
};
187 static void free_clast_for(struct clast_stmt
*s
)
189 struct clast_for
*f
= (struct clast_for
*)s
;
190 assert(CLAST_STMT_IS_A(s
, stmt_for
));
191 free_clast_expr(f
->LB
);
192 free_clast_expr(f
->UB
);
193 value_clear(f
->stride
);
194 cloog_clast_free(f
->body
);
198 struct clast_for
*new_clast_for(const char *it
, struct clast_expr
*LB
,
199 struct clast_expr
*UB
, Value stride
)
201 struct clast_for
*f
= malloc(sizeof(struct clast_for
));
202 f
->stmt
.op
= &stmt_for
;
208 value_init(f
->stride
);
209 value_assign(f
->stride
, stride
);
213 static void free_clast_guard(struct clast_stmt
*s
);
215 struct clast_stmt_op stmt_guard
= { free_clast_guard
};
217 static void free_clast_guard(struct clast_stmt
*s
)
220 struct clast_guard
*g
= (struct clast_guard
*)s
;
221 assert(CLAST_STMT_IS_A(s
, stmt_guard
));
222 cloog_clast_free(g
->then
);
223 for (i
= 0; i
< g
->n
; ++i
) {
224 free_clast_expr(g
->eq
[i
].LHS
);
225 free_clast_expr(g
->eq
[i
].RHS
);
230 struct clast_guard
*new_clast_guard(int n
)
233 struct clast_guard
*g
= malloc(sizeof(struct clast_guard
) +
234 (n
-1) * sizeof(struct clast_equation
));
235 g
->stmt
.op
= &stmt_guard
;
239 for (i
= 0; i
< n
; ++i
) {
246 void free_clast_term(struct clast_term
*t
)
252 void free_clast_binary(struct clast_binary
*b
)
255 free_clast_expr(b
->LHS
);
259 void free_clast_reduction(struct clast_reduction
*r
)
262 for (i
= 0; i
< r
->n
; ++i
)
263 free_clast_expr(r
->elts
[i
]);
267 void free_clast_expr(struct clast_expr
*e
)
273 free_clast_term((struct clast_term
*) e
);
276 free_clast_reduction((struct clast_reduction
*) e
);
279 free_clast_binary((struct clast_binary
*) e
);
286 void free_clast_stmt(struct clast_stmt
*s
)
293 void cloog_clast_free(struct clast_stmt
*s
)
295 struct clast_stmt
*next
;
303 static int clast_term_equal(struct clast_term
*t1
, struct clast_term
*t2
)
305 if (t1
->var
!= t2
->var
)
307 return value_eq(t1
->val
, t2
->val
);
310 static int clast_binary_equal(struct clast_binary
*b1
, struct clast_binary
*b2
)
312 if (b1
->type
!= b2
->type
)
314 if (value_ne(b1
->RHS
, b2
->RHS
))
316 return clast_expr_equal(b1
->LHS
, b2
->LHS
);
319 static int clast_reduction_equal(struct clast_reduction
*r1
, struct clast_reduction
*r2
)
322 if (r1
->type
== clast_red_max
&& r2
->type
== clast_red_min
&&
323 r1
->n
== 1 && r2
->n
== 1)
324 return clast_expr_equal(r1
->elts
[0], r2
->elts
[0]);
325 if (r1
->type
!= r2
->type
)
329 for (i
= 0; i
< r1
->n
; ++i
)
330 if (!clast_expr_equal(r1
->elts
[i
], r2
->elts
[i
]))
335 int clast_expr_equal(struct clast_expr
*e1
, struct clast_expr
*e2
)
341 if (e1
->type
!= e2
->type
)
345 return clast_term_equal((struct clast_term
*) e1
,
346 (struct clast_term
*) e2
);
348 return clast_binary_equal((struct clast_binary
*) e1
,
349 (struct clast_binary
*) e2
);
351 return clast_reduction_equal((struct clast_reduction
*) e1
,
352 (struct clast_reduction
*) e2
);
359 /******************************************************************************
360 * Equalities spreading functions *
361 ******************************************************************************/
364 /* Equalities are stored inside a CloogMatrix data structure called "equal".
365 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
366 * dimensions + 1, the "+ 1" is because a statement can be included inside an
367 * external loop without iteration domain), and (nb_scattering + nb_iterators +
368 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
369 * type). The ith row corresponds to the equality "= 0" for the ith dimension
370 * iterator. The first column gives the equality type (0: no equality, then
371 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
372 * the current level is found, the corresponding row is updated. Then the
373 * equality if it exists is used to simplify expressions (e.g. if we have
374 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
375 * the pprint call, the corresponding row is reset to zero.
380 * clast_equal_type function :
381 * This function returns the type of the equality in the constraint (line) of
382 * (equal) for the element (level). An equality is 'constant' iff all other
383 * factors are null except the constant one. It is a 'pure item' iff one and
384 * only one factor is non null and is 1 or -1. Otherwise it is an 'affine
387 * i = -13 is constant, i = j, j = -M are pure items,
388 * j = 2*M, i = j+1 are affine expressions.
389 * When the equality comes from a 'one time loop', (line) is ONE_TIME_LOOP.
390 * This case require a specific treatment since we have to study all the
392 * - equal is the matrix of equalities,
393 * - level is the column number in equal of the element which is 'equal to',
394 * - line is the line number in equal of the constraint we want to study;
395 * if it is -1, all lines must be studied.
397 * - July 3rd 2002: first version, called pprint_equal_isconstant.
398 * - July 6th 2002: adaptation for the 3 types.
399 * - June 15th 2005: (debug) expr = domain->Constraint[line] was evaluated
400 * before checking if line != ONE_TIME_LOOP. Since
401 * ONE_TIME_LOOP is -1, an invalid read was possible.
402 * - October 19th 2005: Removal of the once-time-loop specific processing.
404 static int clast_equal_type(CloogMatrix
*equal
, int level
, int line
)
408 /* There is only one non null factor, and it must be +1 or -1 for
409 * iterators or parameters.
411 for (i
=1;i
<=equal
->NbColumns
-2;i
++)
412 if (value_notzero_p(cloog_matrix_element(equal
, line
, i
)) && (i
!= level
))
413 { if ((value_notone_p(cloog_matrix_element(equal
, line
, i
))
414 && value_notmone_p(cloog_matrix_element(equal
, line
, i
)))
416 return EQTYPE_EXAFFINE
;
420 /* if the constant factor is non null, it must be alone. */
422 { if (value_notzero_p(cloog_matrix_element(equal
, line
, equal
->NbColumns
-1)))
423 return EQTYPE_EXAFFINE
;
426 return EQTYPE_CONSTANT
;
428 return EQTYPE_PUREITEM
;
433 * clast_equal_allow function:
434 * This function checks whether the options allow us to spread the equality or
435 * not. It returns 1 if so, 0 otherwise.
436 * - equal is the matrix of equalities,
437 * - level is the column number in equal of the element which is 'equal to',
438 * - line is the line number in equal of the constraint we want to study,
439 * - the infos structure gives the user all options on code printing and more.
441 * - October 27th 2005: first version (extracted from old pprint_equal_add).
443 static int clast_equal_allow(CloogMatrix
*equal
, int level
, int line
, CloogInfos
*infos
)
445 if ((!infos
->options
->csp
&& !infos
->options
->esp
) ||
446 (level
< infos
->options
->fsp
))
449 if (infos
->options
->csp
&&
450 (clast_equal_type(equal
,level
,line
) == EQTYPE_EXAFFINE
) &&
451 !infos
->options
->esp
)
459 * clast_equal_add function:
460 * This function updates the row (level-1) of the equality matrix (equal) with
461 * the row that corresponds to the row (line) of the matrix (matrix). It returns
462 * 1 if the row can be updated, 0 otherwise.
463 * - equal is the matrix of equalities,
464 * - matrix is the matrix of constraints,
465 * - level is the column number in matrix of the element which is 'equal to',
466 * - line is the line number in matrix of the constraint we want to study,
467 * - the infos structure gives the user all options on code printing and more.
469 * - July 2nd 2002: first version.
470 * - October 19th 2005: Addition of the once-time-loop specific processing.
472 static int clast_equal_add(CloogMatrix
*equal
, CloogMatrix
*matrix
, int level
, int line
,
476 Value numerator
, denominator
, division
, modulo
;
478 /* If we are in the case of a loop running once, this means that the equality
479 * comes from an inequality. Here we find this inequality.
481 if (line
== ONE_TIME_LOOP
)
482 { for (i
=0;i
<matrix
->NbRows
;i
++)
483 if ((value_notzero_p(cloog_matrix_element(matrix
, i
, 0)))&&
484 (value_notzero_p(cloog_matrix_element(matrix
, i
, level
))))
487 /* Since in once-time-loops, equalities derive from inequalities, we
488 * may have to offset the values. For instance if we have 2i>=3, the
489 * equality is in fact i=2. This may happen when the level coefficient is
490 * not 1 or -1 and the scalar value is not zero. In any other case (e.g.,
491 * if the inequality is an expression including outer loop counters or
492 * parameters) the once time loop would not have been detected
493 * because of floord and ceild functions.
495 if (value_ne_si(cloog_matrix_element(matrix
, i
, level
),1) &&
496 value_ne_si(cloog_matrix_element(matrix
, i
, level
),-1) &&
497 value_notzero_p(cloog_matrix_element(matrix
, i
, matrix
->NbColumns
-1)))
498 { value_init_c(numerator
) ;
499 value_init_c(denominator
) ;
500 value_init_c(division
) ;
501 value_init_c(modulo
) ;
503 value_assign(denominator
,cloog_matrix_element(matrix
, i
, level
)) ;
504 value_absolute(denominator
,denominator
) ;
505 value_assign(numerator
,cloog_matrix_element(matrix
, i
, matrix
->NbColumns
-1)) ;
506 value_modulus(modulo
,numerator
,denominator
) ;
507 value_division(division
,numerator
,denominator
) ;
509 /* There are 4 scenarios:
510 * di +n >= 0 --> i + (n div d) >= 0
511 * -di +n >= 0 --> -i + (n div d) >= 0
512 * di -n >= 0 --> if (n%d == 0) i + ((-n div d)+1) >= 0
513 * else i + (-n div d) >= 0
514 * -di -n >= 0 --> if (n%d == 0) -i + ((-n div d)-1) >= 0
515 * else -i + (-n div d) >= 0
516 * In the following we distinct the scalar value setting and the
519 if (value_pos_p(numerator
) || value_zero_p(modulo
))
520 cloog_matrix_element_assign (matrix
, i
, matrix
->NbColumns
-1, division
);
522 { if (value_pos_p(cloog_matrix_element(matrix
, i
, level
)))
523 cloog_matrix_element_increment (matrix
, i
, matrix
->NbColumns
-1,division
) ;
525 cloog_matrix_element_decrement (matrix
, i
, matrix
->NbColumns
-1,division
) ;
528 if (value_pos_p(cloog_matrix_element(matrix
, i
, level
)))
529 cloog_matrix_element_set_si(matrix
, i
, level
, 1) ;
531 cloog_matrix_element_set_si(matrix
, i
, level
, -1) ;
533 value_clear_c(numerator
) ;
534 value_clear_c(denominator
) ;
535 value_clear_c(division
) ;
536 value_clear_c(modulo
) ;
543 /* We update the line of equal corresponding to level:
544 * - the first element gives the equality type,
546 cloog_matrix_element_set_si(equal
, level
-1, 0, clast_equal_type(matrix
,level
,line
)) ;
547 /* - the other elements corresponding to the equality itself
548 * (the iterators up to level, then the parameters and the scalar).
550 for (i
=1;i
<=level
;i
++)
551 cloog_matrix_element_assign(equal
, level
-1, i
, cloog_matrix_element(matrix
, line
, i
)) ;
552 for (i
=0;i
<infos
->names
->nb_parameters
+1;i
++)
553 cloog_matrix_element_assign(equal
, level
-1, equal
->NbColumns
-i
-1,
554 cloog_matrix_element(matrix
, line
, matrix
->NbColumns
-i
-1)) ;
556 cloog_matrix_equality_update(equal
,level
,infos
->names
->nb_parameters
) ;
558 return (clast_equal_allow(equal
,level
,level
-1,infos
)) ;
563 * clast_equal_del function :
564 * This function reset the equality corresponding to the iterator (level)
565 * in the equality matrix (equal).
566 * - July 2nd 2002: first version.
568 static void clast_equal_del(CloogMatrix
* equal
, int level
)
572 for (i
=0;i
<equal
->NbColumns
;i
++)
573 cloog_matrix_element_set_si(equal
, level
-1, i
, 0) ;
580 * clast_equal function:
581 * This function returns the content an equality matrix (equal) into a clast_stmt.
582 * - the infos structure gives the user all options on code printing and more.
584 * - July 2nd 2002: first version.
585 * - March 16th 2003: return now a string instead of printing directly and do
586 * not write 'Sx()' if there is no spreading, but only 'Sx'.
588 static struct clast_stmt
* clast_equal(CloogInfos
*infos
)
592 struct clast_expr
*e
;
593 struct clast_stmt
*a
= NULL
;
594 struct clast_stmt
**next
= &a
;
595 CloogMatrix
*equal
= infos
->equal
;
599 /* It is not necessary to print here the scattering iterators since they
600 * never appear in the statement bodies.
602 for (i
=infos
->names
->nb_scattering
;i
<equal
->NbRows
;i
++)
603 { if (value_notzero_p(cloog_matrix_element(equal
, i
, 0))&&clast_equal_allow(equal
,i
+1,i
,infos
)) {
604 iterator
= i
- infos
->names
->nb_scattering
;
606 /* pprint_line needs to know that the current line is an equality, so
607 * we temporary remove the equality type and set it to zero (the equality
610 value_assign(type
,cloog_matrix_element(equal
, i
, 0)) ;
611 cloog_matrix_element_set_si(equal
, i
, 0, 0) ;
612 e
= clast_bound_from_constraint(equal
, i
, i
+1, infos
->names
);
613 cloog_matrix_element_assign(equal
, i
, 0, type
) ;
614 *next
= &new_clast_assignment(infos
->names
->iterators
[iterator
], e
)->stmt
;
615 next
= &(*next
)->next
;
618 value_clear_c(type
) ;
625 * clast_equal_cpp function:
626 * This function prints the substitution data of a statement into a clast_stmt.
627 * Using this function instead of pprint_equal is useful for generating
628 * a compilable pseudo-code by using preprocessor macro for each statement.
629 * By opposition to pprint_equal, the result is less human-readable. For
630 * instance this function will print (i,i+3,k,3) where pprint_equal would
631 * return (j=i+3,l=3).
632 * - level is the number of loops enclosing the statement,
633 * - the infos structure gives the user all options on code printing and more.
635 * - March 12th 2004: first version.
636 * - November 21th 2005: (debug) now works well with GMP version.
638 static struct clast_stmt
* clast_equal_cpp(int level
, CloogInfos
*infos
)
642 struct clast_expr
*e
;
643 struct clast_stmt
*a
= NULL
;
644 struct clast_stmt
**next
= &a
;
645 CloogMatrix
*equal
= infos
->equal
;
649 for (i
=infos
->names
->nb_scattering
;i
<level
-1;i
++)
650 { if (value_notzero_p(cloog_matrix_element(equal
, i
, 0)))
651 { /* pprint_line needs to know that the current line is an equality, so
652 * we temporary remove the equality type and set it to zero (the equality
655 value_assign(type
,cloog_matrix_element(equal
, i
, 0)) ;
656 cloog_matrix_element_set_si(equal
, i
, 0, 0) ;
657 e
= clast_bound_from_constraint(equal
, i
, i
+1, infos
->names
);
658 cloog_matrix_element_assign(equal
, i
, 0, type
) ;
660 value_set_si(type
, 1);
661 e
= &new_clast_term(type
,
662 infos
->names
->iterators
[i
-infos
->names
->nb_scattering
])->expr
;
664 *next
= &new_clast_assignment(NULL
, e
)->stmt
;
665 next
= &(*next
)->next
;
667 value_clear_c(type
) ;
674 * clast_bound_from_constraint function:
675 * This function returns a clast_expr containing the printing of the
676 * 'right part' of a constraint according to an element.
677 * For instance, for the constraint -3*i + 2*j - M >=0 and the element j,
678 * we have j >= (3*i + M)/2. As we are looking for integral solutions, this
679 * function should return 'ceild(3*i+M,2)'.
680 * - matrix is the polyhedron containing all the constraints,
681 * - line_num is the line number in domain of the constraint we want to print,
682 * - level is the column number in domain of the element we want to use,
683 * - names structure gives the user some options about code printing,
684 * the number of parameters in domain (nb_par), and the arrays of iterator
685 * names and parameters (iters and params).
687 * - November 2nd 2001: first version.
688 * - June 27th 2003: 64 bits version ready.
690 struct clast_expr
*clast_bound_from_constraint(CloogMatrix
*matrix
,
691 int line_num
, int level
,
694 int i
, nb_iter
, sign
, nb_elts
=0 ;
696 Value numerator
, denominator
, temp
, division
;
697 struct clast_expr
*e
= NULL
;
700 value_init_c(numerator
) ;
701 value_init_c(denominator
) ;
703 if (value_notzero_p(cloog_matrix_element(matrix
, line_num
, level
))) {
704 struct clast_reduction
*r
;
705 /* Maybe we need to invert signs in such a way that the element sign is>0.*/
706 sign
= value_pos_p(cloog_matrix_element(matrix
, line_num
, level
)) ? -1 : 1 ;
708 for (i
= 1, nb_elts
= 0; i
<= matrix
->NbColumns
- 1; ++i
)
709 if (i
!= level
&& value_notzero_p(cloog_matrix_element(matrix
, line_num
, i
)))
711 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
714 /* First, we have to print the iterators. */
715 nb_iter
= matrix
->NbColumns
- 2 - names
->nb_parameters
;
716 for (i
=1;i
<=nb_iter
;i
++)
717 if ((i
!= level
) && value_notzero_p(cloog_matrix_element(matrix
, line_num
, i
))) {
718 if (i
<= names
->nb_scattering
)
719 name
= names
->scattering
[i
-1];
721 name
= names
->iterators
[i
-names
->nb_scattering
-1];
724 value_oppose(temp
,cloog_matrix_element(matrix
, line_num
, i
)) ;
726 value_assign(temp
,cloog_matrix_element(matrix
, line_num
, i
)) ;
728 r
->elts
[nb_elts
++] = &new_clast_term(temp
, name
)->expr
;
731 /* Next, the parameters. */
732 for (i
=nb_iter
+1;i
<=matrix
->NbColumns
-2;i
++)
733 if ((i
!= level
) && value_notzero_p(cloog_matrix_element(matrix
, line_num
, i
))) {
734 name
= names
->parameters
[i
-nb_iter
-1];
737 value_oppose(temp
,cloog_matrix_element(matrix
, line_num
, i
)) ;
739 value_assign(temp
,cloog_matrix_element(matrix
, line_num
, i
)) ;
741 r
->elts
[nb_elts
++] = &new_clast_term(temp
, name
)->expr
;
746 value_oppose(numerator
,cloog_matrix_element(matrix
, line_num
, matrix
->NbColumns
- 1)) ;
747 value_assign(denominator
,cloog_matrix_element(matrix
, line_num
, level
)) ;
751 value_assign(numerator
,cloog_matrix_element(matrix
, line_num
, matrix
->NbColumns
- 1)) ;
752 value_oppose(denominator
,cloog_matrix_element(matrix
, line_num
, level
)) ;
755 /* Finally, the constant, and the final printing. */
757 if (value_notzero_p(numerator
))
758 r
->elts
[nb_elts
++] = &new_clast_term(numerator
, NULL
)->expr
;
760 if (value_notone_p(cloog_matrix_element(matrix
, line_num
, level
))
761 && value_notmone_p(cloog_matrix_element(matrix
, line_num
, level
)))
762 { if (value_one_p(cloog_matrix_element(matrix
, line_num
, 0)))
763 { if (value_pos_p(cloog_matrix_element(matrix
, line_num
, level
)))
764 e
= &new_clast_binary(clast_bin_cdiv
, &r
->expr
, denominator
)->expr
;
766 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, denominator
)->expr
;
768 e
= &new_clast_binary(clast_bin_div
, &r
->expr
, denominator
)->expr
;
773 free_clast_reduction(r
);
774 if (value_zero_p(numerator
))
775 e
= &new_clast_term(numerator
, NULL
)->expr
;
777 { if (value_notone_p(denominator
))
778 { if (value_one_p(cloog_matrix_element(matrix
, line_num
, 0))) /* useful? */
779 { value_modulus(temp
,numerator
,denominator
) ;
780 if (value_zero_p(temp
))
781 { value_division(temp
,numerator
,denominator
) ;
782 e
= &new_clast_term(temp
, NULL
)->expr
;
785 { value_init_c(division
) ;
786 value_division(division
,numerator
,denominator
) ;
787 if (value_neg_p(numerator
)) {
788 if (value_pos_p(cloog_matrix_element(matrix
, line_num
, level
))) {
790 e
= &new_clast_term(division
, NULL
)->expr
;
793 value_decrement(temp
,division
) ;
794 e
= &new_clast_term(temp
, NULL
)->expr
;
798 { if (value_pos_p(cloog_matrix_element(matrix
, line_num
, level
)))
799 { /* nb>0 need max */
800 value_increment(temp
,division
) ;
801 e
= &new_clast_term(temp
, NULL
)->expr
;
805 e
= &new_clast_term(division
, NULL
)->expr
;
807 value_clear_c(division
) ;
811 e
= &new_clast_binary(clast_bin_div
,
812 &new_clast_term(numerator
, NULL
)->expr
,
816 e
= &new_clast_term(numerator
, NULL
)->expr
;
821 value_clear_c(temp
) ;
822 value_clear_c(numerator
) ;
823 value_clear_c(denominator
) ;
830 * clast_minmax function:
831 * This function returns a clast_expr containing the printing of a minimum or a
832 * maximum of the 'right parts' of all constraints according to an element.
833 * For instance consider the constraints:
837 * if we are looking for the minimum for the element j, the function should
838 * return 'max(ceild(3*i+M,2),-2*i)'.
839 * - matrix is the polyhedron containing all the constraints,
840 * - level is the column number in domain of the element we want to use,
841 * - max is a boolean set to 1 if we are looking for a maximum, 0 for a minimum,
842 * - guard is set to 0 if there is no guard, and set to the level of the element
843 * with a guard otherwise (then the function gives the max or the min only
844 * for the constraint where the guarded coefficient is 0),
845 * - the infos structure gives the user some options about code printing,
846 * the number of parameters in domain (nb_par), and the arrays of iterator
847 * names and parameters (iters and params).
849 * - November 2nd 2001: first version.
851 static struct clast_expr
*clast_minmax(CloogMatrix
*matrix
,
852 int level
, int max
, int guard
,
855 struct clast_reduction
*r
;
857 for (i
=0, n
=0;i
<matrix
->NbRows
;i
++)
858 if (((max
&& value_pos_p(cloog_matrix_element(matrix
, i
, level
))) ||
859 (!max
&& value_neg_p(cloog_matrix_element(matrix
, i
, level
)))) &&
860 (!guard
|| value_zero_p(cloog_matrix_element(matrix
, i
, guard
))) &&
861 (value_notzero_p(cloog_matrix_element(matrix
, i
, 0))))
865 r
= new_clast_reduction(max
? clast_red_max
: clast_red_min
, n
);
867 for (i
=0, n
=0;i
<matrix
->NbRows
;i
++)
868 if (((max
&& value_pos_p(cloog_matrix_element(matrix
, i
, level
))) ||
869 (!max
&& value_neg_p(cloog_matrix_element(matrix
, i
, level
)))) &&
870 (!guard
|| value_zero_p(cloog_matrix_element(matrix
, i
, guard
))) &&
871 (value_notzero_p(cloog_matrix_element(matrix
, i
, 0))))
872 r
->elts
[n
++] = clast_bound_from_constraint(matrix
,i
,level
,infos
->names
);
879 * insert_guard function:
880 * This function inserts a guard in the clast.
881 * A guard on an element (level) is :
882 * -> the conjunction of all the existing constraints where the coefficient of
883 * this element is 0 if the element is an iterator,
884 * -> the conjunction of all the existing constraints if the element isn't an
886 * For instance, considering these constraints and the element j:
889 * this function should return 'if (2*i+M>=0) {'.
890 * - matrix is the polyhedron containing all the constraints,
891 * - level is the column number of the element in matrix we want to use,
892 * - the infos structure gives the user some options about code printing,
893 * the number of parameters in matrix (nb_par), and the arrays of iterator
894 * names and parameters (iters and params).
896 * - November 3rd 2001: first version.
897 * - November 14th 2001: a lot of 'purifications'.
898 * - July 31th 2002: (debug) some guard parts are no more redundants.
899 * - August 12th 2002: polyhedra union ('or' conditions) are now supported.
900 * - October 27th 2005: polyhedra union ('or' conditions) are no more supported
901 * (the need came from loop_simplify that may result in
902 * domain unions, now it should be fixed directly in
903 * cloog_loop_simplify).
905 static void insert_guard(CloogMatrix
*matrix
, int level
,
906 struct clast_stmt
***next
, CloogInfos
*infos
)
908 int i
, j
, k
, l
, guarded
, minmax
=-1, nb_and
= 0, nb_iter
;
911 struct clast_guard
*g
;
918 value_set_si(one
, 1);
920 g
= new_clast_guard(2 * (matrix
->NbColumns
-2));
922 /* Well, it looks complicated because I wanted to have a particular, more
923 * readable, ordering, obviously this function may be far much simpler !
925 copy
= cloog_matrix_copy(matrix
) ;
927 nb_iter
= copy
->NbColumns
- 2 - infos
->names
->nb_parameters
;
930 /* We search for guard parts. */
931 for (i
=1;i
<=copy
->NbColumns
-2;i
++)
932 for (j
=0;j
<copy
->NbRows
;j
++)
933 if (value_notzero_p(cloog_matrix_element(copy
, j
, i
)) &&
934 (value_zero_p(cloog_matrix_element(copy
, j
, level
)) || (nb_iter
< level
))) {
935 struct clast_term
*t
;
937 { if (i
<= infos
->names
->nb_scattering
)
938 name
= infos
->names
->scattering
[i
-1] ;
940 name
= infos
->names
->iterators
[i
-infos
->names
->nb_scattering
-1] ;
943 name
= infos
->names
->parameters
[i
-(nb_iter
+1)] ;
945 g
->eq
[nb_and
].LHS
= &(t
= new_clast_term(one
, name
))->expr
;
946 if (value_zero_p(cloog_matrix_element(copy
, j
, 0))) {
947 /* put the "denominator" in the LHS */
948 value_assign(t
->val
, cloog_matrix_element(copy
, j
, i
));
949 cloog_matrix_element_set_si(copy
, j
, i
, 1);
950 g
->eq
[nb_and
].sign
= 0;
951 g
->eq
[nb_and
].RHS
= clast_bound_from_constraint(copy
,j
,i
,infos
->names
);
952 cloog_matrix_element_assign(copy
, j
, i
, t
->val
);
954 if (value_pos_p(cloog_matrix_element(copy
, j
, i
))) {
956 g
->eq
[nb_and
].sign
= 1;
959 g
->eq
[nb_and
].sign
= -1;
962 guarded
= (nb_iter
>= level
) ? level
: 0 ;
963 g
->eq
[nb_and
].RHS
= clast_minmax(copy
,i
,minmax
,guarded
,infos
) ;
967 /* 'elimination' of the current constraint, this avoid to use one
968 * constraint more than once. The current line is always eliminated,
969 * and the next lines if they are in a min or a max.
971 for (k
=i
;k
<=copy
->NbColumns
-2;k
++)
972 cloog_matrix_element_set_si(copy
, j
, k
, 0) ;
975 for (l
=j
+1;l
<copy
->NbRows
;l
++)
976 if (((minmax
== 1) && value_pos_p(cloog_matrix_element(copy
, l
, i
))) ||
977 ((minmax
== 0) && value_neg_p(cloog_matrix_element(copy
, l
, i
))))
978 for (k
=i
;k
<=copy
->NbColumns
-2;k
++)
979 cloog_matrix_element_set_si(copy
, l
, k
, 0) ;
981 cloog_matrix_free(copy
) ;
988 free_clast_stmt(&g
->stmt
);
995 /* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
996 static void Euclid(Value a
, Value b
, Value
*x
, Value
*y
, Value
*g
)
998 Value c
, d
, e
, f
, tmp
;
1005 value_absolute(c
, a
);
1006 value_absolute(d
, b
);
1009 while(value_pos_p(d
)) {
1010 value_division(tmp
, c
, d
);
1011 value_multiply(tmp
, tmp
, f
);
1012 value_subtract(e
, e
, tmp
);
1013 value_division(tmp
, c
, d
);
1014 value_multiply(tmp
, tmp
, d
);
1015 value_subtract(c
, c
, tmp
);
1019 value_assign(*g
, c
);
1020 if (value_zero_p(a
))
1021 value_set_si(*x
, 0);
1022 else if (value_pos_p(a
))
1023 value_assign(*x
, e
);
1024 else value_oppose(*x
, e
);
1025 if (value_zero_p(b
))
1026 value_set_si(*y
, 0);
1028 value_multiply(tmp
, a
, *x
);
1029 value_subtract(tmp
, c
, tmp
);
1030 value_division(*y
, tmp
, b
);
1041 * insert_modulo_guard:
1042 * This function inserts a modulo guard corresponding to an equality.
1043 * See insert_equality.
1044 * - matrix is the polyhedron containing all the constraints,
1045 * - num is the line number of the constraint in matrix we want to print,
1046 * - level is the column number of the element in matrix we want to use,
1047 * - the infos structure gives the user some options about code printing,
1048 * the number of parameters in matrix (nb_par), and the arrays of iterator
1049 * names and parameters (iters and params).
1051 static void insert_modulo_guard(CloogMatrix
*matrix
, int num
, int level
,
1052 struct clast_stmt
***next
, CloogInfos
*infos
)
1054 int i
, j
, k
, nb_elts
= 0, len
, nb_iter
, in_stride
= 0, nb_par
;
1055 Vector
*line_vector
;
1056 Value
*line
, val
, x
, y
, g
;
1058 if (value_one_p(cloog_matrix_element(matrix
, num
, level
)) || value_mone_p(cloog_matrix_element(matrix
, num
, level
)))
1066 len
= matrix
->NbColumns
;
1067 nb_par
= infos
->names
->nb_parameters
;
1068 nb_iter
= matrix
->NbColumns
- 2 - nb_par
;
1070 line_vector
= Vector_Alloc(len
);
1071 line
= line_vector
->p
;
1072 if (value_neg_p(cloog_matrix_element(matrix
, num
, level
)))
1073 Vector_Copy(matrix
->p
[num
]+1, line
+1, len
-1);
1075 value_set_si(val
, -1);
1076 Vector_Scale(matrix
->p
[num
]+1, line
+1, val
, len
-1);
1078 value_oppose(line
[level
], line
[level
]);
1079 assert(value_pos_p(line
[level
]));
1082 for (i
= nb_iter
; i
>= 1; --i
) {
1085 value_pmodulus(line
[i
],line
[i
],line
[level
]);
1086 if (value_zero_p(line
[i
]))
1089 /* Look for an earlier variable that is also a multiple of line[level]
1090 * and check whether we can use the corresponding affine expression
1091 * to "reduce" the modulo guard, where reduction means that we eliminate
1092 * a variable, possibly at the expense of introducing other variables
1093 * with smaller index.
1095 for (j
= level
-1; j
>= 0; --j
) {
1096 if (value_cmp_si(cloog_matrix_element(infos
->equal
, j
, 0), EQTYPE_EXAFFINE
) != 0)
1098 value_modulus(val
, cloog_matrix_element(infos
->equal
, j
, 1+j
), line
[level
]);
1099 if (value_notzero_p(val
))
1101 value_modulus(val
, cloog_matrix_element(infos
->equal
, j
, i
), line
[level
]);
1102 if (value_zero_p(val
))
1104 for (k
= j
; k
> i
; --k
) {
1105 if (value_zero_p(cloog_matrix_element(infos
->equal
, j
, k
)))
1107 value_modulus(val
, cloog_matrix_element(infos
->equal
, j
, k
), line
[level
]);
1108 if (value_notzero_p(val
))
1113 Euclid(cloog_matrix_element(infos
->equal
, j
, i
), line
[level
], &x
, &y
, &g
);
1114 value_modulus(val
, line
[i
], g
);
1115 if (value_notzero_p(val
))
1117 value_division(val
, line
[i
], g
);
1118 value_oppose(val
, val
);
1119 value_multiply(val
, val
, x
);
1121 /* Add (infos->equal->p[j][i])^{-1} * line[i] times the equality */
1122 Vector_Combine(line
+1, infos
->equal
->p
[j
]+1, line
+1, y
, val
, i
);
1123 Vector_Combine(line
+len
-nb_par
-1,
1124 infos
->equal
->p
[j
]+infos
->equal
->NbColumns
-nb_par
-1,
1125 line
+len
-nb_par
-1, y
, val
, nb_par
+1);
1129 value_pmodulus(line
[i
],line
[i
],line
[level
]);
1130 assert(value_zero_p(line
[i
]));
1134 value_modulus(val
,infos
->stride
[i
-1],line
[level
]);
1135 /* We need to know if an element of the equality has not to be printed
1136 * because of a stride that guarantees that this element can be divided by
1137 * the current coefficient. Because when there is a constant element, it
1138 * is included in the stride calculation (more exactly in the strided
1139 * iterator new lower bound: the 'offset') and we have not to print it.
1141 if (value_zero_p(val
)) {
1148 for (i
= nb_iter
+1; i
<= len
-1; ++i
) {
1149 value_pmodulus(line
[i
],line
[i
],line
[level
]);
1150 if (value_zero_p(line
[i
]))
1156 if (nb_elts
|| (value_notzero_p(line
[len
-1]) && (!in_stride
))) {
1157 struct clast_reduction
*r
;
1158 struct clast_expr
*e
;
1159 struct clast_guard
*g
;
1162 r
= new_clast_reduction(clast_red_sum
, nb_elts
+1);
1165 /* First, the modulo guard : the iterators... */
1166 for (i
=1;i
<=nb_iter
;i
++) {
1167 if (i
== level
|| value_zero_p(line
[i
]))
1169 value_modulus(val
,infos
->stride
[i
-1],line
[level
]);
1170 if (value_zero_p(val
))
1173 if (i
<= infos
->names
->nb_scattering
)
1174 name
= infos
->names
->scattering
[i
-1];
1176 name
= infos
->names
->iterators
[i
-infos
->names
->nb_scattering
-1];
1178 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
], name
)->expr
;
1181 /* ...the parameters... */
1182 for (i
=nb_iter
+1;i
<=len
-2;i
++) {
1183 if (value_zero_p(line
[i
]))
1186 name
= infos
->names
->parameters
[i
-nb_iter
-1] ;
1187 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
], name
)->expr
;
1190 /* ...the constant. */
1191 if (value_notzero_p(line
[len
-1]))
1192 r
->elts
[nb_elts
++] = &new_clast_term(line
[len
-1], NULL
)->expr
;
1194 /* our initial computation may have been an overestimate */
1197 e
= &new_clast_binary(clast_bin_mod
, &r
->expr
, line
[level
])->expr
;
1198 g
= new_clast_guard(1);
1200 value_set_si(val
, 0);
1201 g
->eq
[0].RHS
= &new_clast_term(val
, NULL
)->expr
;
1208 Vector_Free(line_vector
);
1218 * insert_equality function:
1219 * This function inserts an equality
1220 * constraint according to an element in the clast.
1221 * An equality can be preceded by a 'modulo guard'.
1222 * For instance, consider the constraint i -2*j = 0 and the
1223 * element j: pprint_equality should return 'if(i%2==0) { j = i/2 ;'.
1224 * - matrix is the polyhedron containing all the constraints,
1225 * - num is the line number of the constraint in matrix we want to print,
1226 * - level is the column number of the element in matrix we want to use,
1227 * - the infos structure gives the user some options about code printing,
1228 * the number of parameters in matrix (nb_par), and the arrays of iterator
1229 * names and parameters (iters and params).
1231 * - November 13th 2001: first version.
1232 * - June 26th 2003: simplification of the modulo guards (remove parts such as
1233 * modulo is 0, compare vivien or vivien2 with a previous
1234 * version for an idea).
1235 * - June 29th 2003: non-unit strides support.
1236 * - July 14th 2003: (debug) no more print the constant in the modulo guard when
1237 * it was previously included in a stride calculation.
1239 static void insert_equality(CloogMatrix
*matrix
, int num
,
1240 int level
, struct clast_stmt
***next
, CloogInfos
*infos
)
1242 struct clast_expr
*e
;
1243 struct clast_assignment
*ass
;
1245 insert_modulo_guard(matrix
, num
, level
, next
, infos
);
1247 if (!clast_equal_add(infos
->equal
,matrix
,level
,num
,infos
))
1248 { /* Finally, the equality. */
1250 /* If we have to make a block by dimension, we start the block. Function
1251 * pprint knows if there is an equality, if this is the case, it checks
1252 * for the same following condition to close the brace.
1254 if (infos
->options
->block
) {
1255 struct clast_block
*b
= new_clast_block();
1260 e
= clast_bound_from_constraint(matrix
,num
,level
,infos
->names
);
1261 if (level
<= infos
->names
->nb_scattering
)
1262 ass
= new_clast_assignment(infos
->names
->scattering
[level
-1], e
);
1264 ass
= new_clast_assignment(
1265 infos
->names
->iterators
[level
-infos
->names
->nb_scattering
-1], e
);
1267 **next
= &ass
->stmt
;
1268 *next
= &(**next
)->next
;
1276 * insert_for function:
1277 * This function inserts a for loop in the clast.
1278 * A loop header according to an element is the conjonction of a minimum and a
1279 * maximum on the element (they give the loop bounds).
1280 * For instance, considering these constraints and the element j:
1284 * this function should return 'for (j=max(-i+9*M,4*M),j<=5*M;j++) {'.
1285 * - matrix is the polyhedron containing all the constraints,
1286 * - level is the column number of the element in matrix we want to use,
1287 * - the infos structure gives the user some options about code printing,
1288 * the number of parameters in matrix (nb_par), and the arrays of iterator
1289 * names and parameters (iters and params).
1291 * - July 2nd 2002: first version (pick from pprint function).
1292 * - March 6th 2003: infinite domain support.
1293 * - June 29th 2003: non-unit strides support.
1295 static void insert_for(CloogMatrix
*matrix
, int level
,
1296 struct clast_stmt
***next
, CloogInfos
*infos
)
1299 struct clast_expr
*e1
;
1300 struct clast_expr
*e2
;
1301 struct clast_assignment
*ass
;
1303 if (level
<= infos
->names
->nb_scattering
)
1304 iterator
= infos
->names
->scattering
[level
-1] ;
1306 iterator
= infos
->names
->iterators
[level
-infos
->names
->nb_scattering
-1] ;
1308 e1
= clast_minmax(matrix
,level
,1,0,infos
) ;
1309 e2
= clast_minmax(matrix
,level
,0,0,infos
) ;
1311 /* If min and max are not equal there is a 'for' else, there is a '='.
1312 * In the special case e1 = e2 = NULL, this is an infinite loop
1313 * so this is not a '='.
1315 if (!clast_expr_equal(e1
, e2
) || !infos
->options
->otl
|| (!e1
&& !e2
)) {
1316 struct clast_for
*f
= new_clast_for(iterator
, e1
, e2
, infos
->stride
[level
-1]);
1320 else if (!clast_equal_add(infos
->equal
,matrix
,level
,ONE_TIME_LOOP
,infos
)) {
1321 if (infos
->options
->block
) {
1322 struct clast_block
*b
= new_clast_block();
1326 ass
= new_clast_assignment(iterator
, e1
);
1327 **next
= &ass
->stmt
;
1328 *next
= &(**next
)->next
;
1336 * insert_scalar function:
1337 * This function inserts assignments to the scalar values
1338 * that follows the level (level). It finds by scanning (loop) by inner level,
1339 * the first CloogBlock data structure (at this step, all blocks has the same
1340 * scalar vector information after (level)), and prints all the adjacent
1341 * scalar values following (level), if it is required by options in (info).
1342 * - loop is the loop structure to begin the search for a block,
1343 * - level is the current loop level,
1344 * - scalar points to the number of scalar values already visited,
1345 * - the infos structure gives the user options about code printing and more.
1347 * - September 12th 2005: first version.
1349 static void insert_scalar(CloogLoop
*loop
, int level
, int *scalar
,
1350 struct clast_stmt
***next
, CloogInfos
*infos
)
1352 struct clast_block
*b
;
1353 struct clast_term
*t
;
1355 if ((!infos
->options
->csp
) &&
1356 (level
+(*scalar
) <= infos
->nb_scattdims
) &&
1357 (infos
->scaldims
[level
+(*scalar
)-1]))
1358 { while (loop
->block
== NULL
)
1359 loop
= loop
->inner
;
1361 while ((level
+(*scalar
) <= infos
->nb_scattdims
) &&
1362 (infos
->scaldims
[level
+(*scalar
)-1])) {
1363 if (infos
->options
->block
) {
1364 b
= new_clast_block();
1369 t
= new_clast_term(loop
->block
->scaldims
[(*scalar
)], NULL
);
1370 **next
= &new_clast_assignment(infos
->names
->scalars
[(*scalar
)],
1372 *next
= &(**next
)->next
;
1383 * insert_block function:
1384 * This function inserts a statement block.
1385 * - block is the statement block,
1386 * - level is the number of loops enclosing the statement,
1387 * - the infos structure gives the user some options about code printing,
1388 * the number of parameters in domain (nb_par), and the arrays of iterator
1389 * names and parameters (iters and params).
1391 * - September 21th 2003: first version (pick from pprint function).
1393 static void insert_block(CloogBlock
*block
, int level
,
1394 struct clast_stmt
***next
, CloogInfos
*infos
)
1396 CloogStatement
* statement
;
1397 struct clast_stmt
*subs
;
1402 for (statement
= block
->statement
; statement
; statement
= statement
->next
) {
1403 if (infos
->options
->cpp
== 0)
1404 subs
= clast_equal(infos
);
1406 subs
= clast_equal_cpp(level
,infos
);
1408 **next
= &new_clast_user_stmt(statement
, subs
)->stmt
;
1409 *next
= &(**next
)->next
;
1415 * insert_loop function:
1416 * This function concerts the content of a CloogLoop structure (loop) into a
1417 * clast_stmt (inserted at **next).
1418 * The iterator (level) of
1419 * the current loop is given by 'level': this is the column number of the
1420 * domain corresponding to the current loop iterator. The data of a loop are
1421 * written in this order:
1422 * 1. The guard of the loop, i.e. each constraint in the domain that do not
1423 * depend on the iterator (when the entry in the column 'level' is 0).
1424 * 2. The iteration domain of the iterator, given by the constraints in the
1425 * domain depending on the iterator, i.e.:
1426 * * an equality if the iterator has only one value (possibly preceded by
1427 * a guard verifying if this value is integral), *OR*
1428 * * a loop from the minimum possible value of the iterator to the maximum
1430 * 3. The included statement block.
1431 * 4. The inner loops (recursive call).
1432 * 5. The following loops (recursive call).
1433 * - level is the recursion level or the iteration level that we are printing,
1434 * - the infos structure gives the user some options about code printing,
1435 * the number of parameters in domain (nb_par), and the arrays of iterator
1436 * names and parameters (iters and params).
1438 * - November 2nd 2001: first version.
1439 * - March 6th 2003: infinite domain support.
1440 * - April 19th 2003: (debug) NULL loop support.
1441 * - June 29th 2003: non-unit strides support.
1442 * - April 28th 2005: (debug) level is level+equality when print statement!
1443 * - June 16th 2005: (debug) the N. Vasilache normalization step has been
1444 * added to avoid iteration duplication (see DaeGon Kim
1445 * bug in cloog_program_generate). Try vasilache.cloog
1446 * with and without the call to cloog_matrix_normalize,
1447 * using -f 8 -l 9 options for an idea.
1448 * - September 15th 2005: (debug) don't close equality braces when unnecessary.
1449 * - October 16th 2005: (debug) scalar value is saved for next loops.
1451 static void insert_loop(CloogLoop
* loop
, int level
, int scalar
,
1452 struct clast_stmt
***next
, CloogInfos
*infos
)
1454 int i
, equality
=0, scalar_level
;
1455 CloogMatrix
* matrix
;
1456 struct clast_stmt
**top
= *next
;
1458 /* It can happen that loop be NULL when an input polyhedron is empty. */
1462 /* The matrix has not always a shape that allows us to generate code from it,
1463 * thus we normalize it, we also simplify it with the matrix of equalities.
1465 matrix
= cloog_simplify_domain_matrix_with_equalities
1466 (loop
->domain
, level
, infos
->equal
, infos
->names
->nb_parameters
);
1467 value_assign(infos
->stride
[level
-1],loop
->stride
);
1469 /* First of all we have to print the guard. */
1470 insert_guard(matrix
,level
, next
, infos
);
1472 /* Then we print scalar dimensions. */
1473 scalar_level
= scalar
;
1474 insert_scalar(loop
,level
,&scalar
, next
, infos
);
1476 if ((matrix
->NbColumns
- 2 - infos
->names
->nb_parameters
>= level
)) {
1477 /* We scan all the constraints to know in which case we are :
1478 * [[if] equality] or [for].
1480 for (i
=0;i
<matrix
->NbRows
;i
++)
1481 if (value_zero_p(cloog_matrix_element(matrix
, i
, 0)) &&
1482 value_notzero_p(cloog_matrix_element(matrix
, i
, level
)))
1483 { /* If there is an equality, we can print it directly -no ambiguity-.
1484 * PolyLib can give more than one equality, we use just the first one
1485 * (this is a PolyLib problem, but all equalities are equivalent).
1487 insert_equality(matrix
,i
,level
, next
, infos
);
1493 insert_for(matrix
, level
, next
, infos
);
1496 /* Finally, if there is an included statement block, print it. */
1497 insert_block(loop
->block
, level
+equality
, next
, infos
);
1499 /* Go to the next level. */
1500 if (loop
->inner
!= NULL
)
1501 insert_loop(loop
->inner
, level
+1,scalar
, next
, infos
);
1503 clast_equal_del(infos
->equal
,level
);
1504 cloog_matrix_free(matrix
);
1506 /* Go to the next loop on the same level. */
1508 top
= &(*top
)->next
;
1509 if (loop
->next
!= NULL
)
1510 insert_loop(loop
->next
, level
,scalar_level
, &top
,infos
);
1514 struct clast_stmt
*cloog_clast_create(CloogProgram
*program
,
1515 CloogOptions
*options
)
1517 CloogInfos
*infos
= ALLOC(CloogInfos
);
1519 struct clast_stmt
*root
= &new_clast_root(program
->names
)->stmt
;
1520 struct clast_stmt
**next
= &root
->next
;
1522 infos
->names
= program
->names
;
1523 infos
->options
= options
;
1524 infos
->scaldims
= program
->scaldims
;
1525 infos
->nb_scattdims
= program
->nb_scattdims
;
1527 /* Allocation for the array of strides, there is a +1 since the statement can
1528 * be included inside an external loop without iteration domain.
1530 nb_levels
= program
->names
->nb_scattering
+program
->names
->nb_iterators
+1;
1531 infos
->stride
= ALLOCN(Value
, nb_levels
);
1532 for (i
= 0; i
< nb_levels
; ++i
)
1533 value_init_c(infos
->stride
[i
]);
1535 infos
->equal
= cloog_matrix_alloc(nb_levels
,
1536 nb_levels
+ program
->names
->nb_parameters
+ 1);
1538 insert_loop(program
->loop
, 1, 0, &next
, infos
);
1540 cloog_matrix_free(infos
->equal
);
1542 for (i
= 0; i
< nb_levels
; ++i
)
1543 value_clear_c(infos
->stride
[i
]);
1544 free(infos
->stride
);