2 #include "../include/cloog/cloog.h"
4 #define ALLOC(type) (type*)malloc(sizeof(type))
5 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
8 * CloogInfos structure:
9 * this structure contains all the informations necessary for pretty printing,
10 * they come from the original CloogProgram structure (language, names), from
11 * genereral options (options) or are built only for pretty printing (stride).
12 * This structure is mainly there to reduce the number of function parameters,
13 * since most pprint.c functions need most of its field.
16 { Value
* stride
; /**< The stride for each iterator. */
17 int nb_scattdims
; /**< Scattering dimension number. */
18 int * scaldims
; /**< Boolean array saying whether a given
19 * scattering dimension is scalar or not.
21 CloogNames
* names
; /**< Names of iterators and parameters. */
22 CloogOptions
* options
; /**< Options on CLooG's behaviour. */
23 CloogMatrix
*equal
; /**< Matrix of equalities. */
26 typedef struct clooginfos CloogInfos
;
28 static int clast_term_equal(struct clast_term
*t1
, struct clast_term
*t2
);
29 static int clast_binary_equal(struct clast_binary
*b1
, struct clast_binary
*b2
);
30 static int clast_reduction_equal(struct clast_reduction
*r1
,
31 struct clast_reduction
*r2
);
33 static int clast_equal_type(CloogMatrix
*equal
, int level
, int line
);
34 static int clast_equal_add(CloogMatrix
*equal
, CloogMatrix
*matrix
, int level
,
35 int line
, CloogInfos
*infos
);
36 static void clast_equal_del(CloogMatrix
* equal
, int level
);
38 static struct clast_stmt
* clast_equal(CloogInfos
*infos
);
39 static struct clast_stmt
* clast_equal_cpp(int level
, CloogInfos
*infos
);
40 static struct clast_expr
*clast_line(CloogMatrix
*matrix
,
41 int line_num
, int level
, CloogInfos
*infos
);
42 static struct clast_expr
*clast_minmax(CloogMatrix
*matrix
,
43 int level
, int max
, int guard
,
45 static void insert_guard(CloogMatrix
*matrix
, int level
,
46 struct clast_stmt
***next
, CloogInfos
*infos
);
47 static void insert_modulo_guard(CloogMatrix
*matrix
, int num
, int level
,
48 struct clast_stmt
***next
, CloogInfos
*infos
);
49 static void insert_equality(CloogMatrix
*matrix
, int num
,
50 int level
, struct clast_stmt
***next
, CloogInfos
*infos
);
51 static void insert_for(CloogMatrix
*matrix
, int level
,
52 struct clast_stmt
***next
, CloogInfos
*infos
);
53 static void insert_scalar(CloogLoop
*loop
, int level
, int *scalar
,
54 struct clast_stmt
***next
, CloogInfos
*infos
);
55 static void insert_block(CloogBlock
*block
, int level
,
56 struct clast_stmt
***next
, CloogInfos
*infos
);
57 static void insert_loop(CloogLoop
* loop
, int level
, int scalar
,
58 struct clast_stmt
***next
, CloogInfos
*infos
);
61 struct clast_term
*new_clast_term(Value c
, const char *v
)
63 struct clast_term
*t
= malloc(sizeof(struct clast_term
));
64 t
->expr
.type
= expr_term
;
66 value_assign(t
->val
, c
);
71 struct clast_binary
*new_clast_binary(enum clast_bin_type t
,
72 struct clast_expr
*lhs
, Value rhs
)
74 struct clast_binary
*b
= malloc(sizeof(struct clast_binary
));
75 b
->expr
.type
= expr_bin
;
79 value_assign(b
->RHS
, rhs
);
83 struct clast_reduction
*new_clast_reduction(enum clast_red_type t
, int n
)
86 struct clast_reduction
*r
;
87 r
= malloc(sizeof(struct clast_reduction
)+(n
-1)*sizeof(struct clast_expr
*));
88 r
->expr
.type
= expr_red
;
91 for (i
= 0; i
< n
; ++i
)
96 struct clast_assignment
*new_clast_assignment(const char *lhs
,
97 struct clast_expr
*rhs
)
99 struct clast_assignment
*a
= malloc(sizeof(struct clast_assignment
));
100 a
->stmt
.type
= stmt_ass
;
107 struct clast_user_stmt
*new_clast_user_stmt(CloogStatement
*stmt
,
108 struct clast_stmt
*subs
)
110 struct clast_user_stmt
*u
= malloc(sizeof(struct clast_user_stmt
));
111 u
->stmt
.type
= stmt_user
;
114 u
->substitutions
= subs
;
118 struct clast_block
*new_clast_block()
120 struct clast_block
*b
= malloc(sizeof(struct clast_block
));
121 b
->stmt
.type
= stmt_block
;
127 struct clast_for
*new_clast_for(const char *it
, struct clast_expr
*LB
,
128 struct clast_expr
*UB
, Value stride
)
130 struct clast_for
*f
= malloc(sizeof(struct clast_for
));
131 f
->stmt
.type
= stmt_for
;
137 value_init(f
->stride
);
138 value_assign(f
->stride
, stride
);
142 struct clast_guard
*new_clast_guard(int n
)
145 struct clast_guard
*g
= malloc(sizeof(struct clast_guard
) +
146 (n
-1) * sizeof(struct clast_equation
));
147 g
->stmt
.type
= stmt_guard
;
151 for (i
= 0; i
< n
; ++i
) {
158 void free_clast_term(struct clast_term
*t
)
164 void free_clast_binary(struct clast_binary
*b
)
167 free_clast_expr(b
->LHS
);
171 void free_clast_reduction(struct clast_reduction
*r
)
174 for (i
= 0; i
< r
->n
; ++i
)
175 free_clast_expr(r
->elts
[i
]);
179 void free_clast_expr(struct clast_expr
*e
)
185 free_clast_term((struct clast_term
*) e
);
188 free_clast_reduction((struct clast_reduction
*) e
);
191 free_clast_binary((struct clast_binary
*) e
);
198 void free_clast_assignment(struct clast_assignment
*a
)
200 free_clast_expr(a
->RHS
);
204 void free_clast_user_stmt(struct clast_user_stmt
*u
)
206 cloog_clast_free(u
->substitutions
);
210 void free_clast_for(struct clast_for
*f
)
212 free_clast_expr(f
->LB
);
213 free_clast_expr(f
->UB
);
214 value_clear(f
->stride
);
215 cloog_clast_free(f
->body
);
219 void free_clast_guard(struct clast_guard
*g
)
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 void free_clast_block(struct clast_block
*b
)
232 cloog_clast_free(b
->body
);
236 void cloog_clast_free(struct clast_stmt
*s
)
238 struct clast_stmt
*next
;
243 free_clast_assignment((struct clast_assignment
*) s
);
246 free_clast_for((struct clast_for
*) s
);
249 free_clast_guard((struct clast_guard
*) s
);
252 free_clast_user_stmt((struct clast_user_stmt
*) s
);
255 free_clast_block((struct clast_block
*) s
);
264 int clast_term_equal(struct clast_term
*t1
, struct clast_term
*t2
)
266 if (t1
->var
!= t2
->var
)
268 return value_eq(t1
->val
, t2
->val
);
271 int clast_binary_equal(struct clast_binary
*b1
, struct clast_binary
*b2
)
273 if (b1
->type
!= b2
->type
)
275 if (value_ne(b1
->RHS
, b2
->RHS
))
277 return clast_expr_equal(b1
->LHS
, b2
->LHS
);
280 int clast_reduction_equal(struct clast_reduction
*r1
, struct clast_reduction
*r2
)
283 if (r1
->type
== clast_red_max
&& r2
->type
== clast_red_min
&&
284 r1
->n
== 1 && r2
->n
== 1)
285 return clast_expr_equal(r1
->elts
[0], r2
->elts
[0]);
286 if (r1
->type
!= r2
->type
)
290 for (i
= 0; i
< r1
->n
; ++i
)
291 if (!clast_expr_equal(r1
->elts
[i
], r2
->elts
[i
]))
296 int clast_expr_equal(struct clast_expr
*e1
, struct clast_expr
*e2
)
302 if (e1
->type
!= e2
->type
)
306 return clast_term_equal((struct clast_term
*) e1
,
307 (struct clast_term
*) e2
);
309 return clast_binary_equal((struct clast_binary
*) e1
,
310 (struct clast_binary
*) e2
);
312 return clast_reduction_equal((struct clast_reduction
*) e1
,
313 (struct clast_reduction
*) e2
);
320 /******************************************************************************
321 * Equalities spreading functions *
322 ******************************************************************************/
325 /* Equalities are stored inside a CloogMatrix data structure called "equal".
326 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
327 * dimensions + 1, the "+ 1" is because a statement can be included inside an
328 * external loop without iteration domain), and (nb_scattering + nb_iterators +
329 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
330 * type). The ith row corresponds to the equality "= 0" for the ith dimension
331 * iterator. The first column gives the equality type (0: no equality, then
332 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
333 * the current level is found, the corresponding row is updated. Then the
334 * equality if it exists is used to simplify expressions (e.g. if we have
335 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
336 * the pprint call, the corresponding row is reset to zero.
341 * clast_equal_type function :
342 * This function returns the type of the equality in the constraint (line) of
343 * (equal) for the element (level). An equality is 'constant' iff all other
344 * factors are null except the constant one. It is a 'pure item' iff one and
345 * only one factor is non null and is 1 or -1. Otherwise it is an 'affine
348 * i = -13 is constant, i = j, j = -M are pure items,
349 * j = 2*M, i = j+1 are affine expressions.
350 * When the equality comes from a 'one time loop', (line) is ONE_TIME_LOOP.
351 * This case require a specific treatment since we have to study all the
353 * - equal is the matrix of equalities,
354 * - level is the column number in equal of the element which is 'equal to',
355 * - line is the line number in equal of the constraint we want to study;
356 * if it is -1, all lines must be studied.
358 * - July 3rd 2002: first version, called pprint_equal_isconstant.
359 * - July 6th 2002: adaptation for the 3 types.
360 * - June 15th 2005: (debug) expr = domain->Constraint[line] was evaluated
361 * before checking if line != ONE_TIME_LOOP. Since
362 * ONE_TIME_LOOP is -1, an invalid read was possible.
363 * - October 19th 2005: Removal of the once-time-loop specific processing.
365 int clast_equal_type(CloogMatrix
*equal
, int level
, int line
)
370 expr
= equal
->p
[line
] ;
372 /* There is only one non null factor, and it must be +1 or -1 for
373 * iterators or parameters.
375 for (i
=1;i
<=equal
->NbColumns
-2;i
++)
376 if (value_notzero_p(expr
[i
]) && (i
!= level
))
377 { if ((value_notone_p(expr
[i
]) && value_notmone_p(expr
[i
])) || (one
!= 0))
378 return EQTYPE_EXAFFINE
;
382 /* if the constant factor is non null, it must be alone. */
384 { if (value_notzero_p(expr
[equal
->NbColumns
-1]))
385 return EQTYPE_EXAFFINE
;
388 return EQTYPE_CONSTANT
;
390 return EQTYPE_PUREITEM
;
395 * clast_equal_allow function:
396 * This function checks whether the options allow us to spread the equality or
397 * not. It returns 1 if so, 0 otherwise.
398 * - equal is the matrix of equalities,
399 * - level is the column number in equal of the element which is 'equal to',
400 * - line is the line number in equal of the constraint we want to study,
401 * - the infos structure gives the user all options on code printing and more.
403 * - October 27th 2005: first version (extracted from old pprint_equal_add).
405 int clast_equal_allow(CloogMatrix
*equal
, int level
, int line
, CloogInfos
*infos
)
407 if ((!infos
->options
->csp
&& !infos
->options
->esp
) ||
408 (level
< infos
->options
->fsp
))
411 if (infos
->options
->csp
&&
412 (clast_equal_type(equal
,level
,line
) == EQTYPE_EXAFFINE
) &&
413 !infos
->options
->esp
)
421 * clast_equal_add function:
422 * This function updates the row (level-1) of the equality matrix (equal) with
423 * the row that corresponds to the row (line) of the matrix (matrix). It returns
424 * 1 if the row can be updated, 0 otherwise.
425 * - equal is the matrix of equalities,
426 * - matrix is the matrix of constraints,
427 * - level is the column number in matrix of the element which is 'equal to',
428 * - line is the line number in matrix of the constraint we want to study,
429 * - the infos structure gives the user all options on code printing and more.
431 * - July 2nd 2002: first version.
432 * - October 19th 2005: Addition of the once-time-loop specific processing.
434 int clast_equal_add(CloogMatrix
*equal
, CloogMatrix
*matrix
, int level
, int line
,
438 Value numerator
, denominator
, division
, modulo
;
440 /* If we are in the case of a loop running once, this means that the equality
441 * comes from an inequality. Here we find this inequality.
443 if (line
== ONE_TIME_LOOP
)
444 { for (i
=0;i
<matrix
->NbRows
;i
++)
445 if ((value_notzero_p(matrix
->p
[i
][0]))&&
446 (value_notzero_p(matrix
->p
[i
][level
])))
449 /* Since in once-time-loops, equalities derive from inequalities, we
450 * may have to offset the values. For instance if we have 2i>=3, the
451 * equality is in fact i=2. This may happen when the level coefficient is
452 * not 1 or -1 and the scalar value is not zero. In any other case (e.g.,
453 * if the inequality is an expression including outer loop counters or
454 * parameters) the once time loop would not have been detected
455 * because of floord and ceild functions.
457 if (value_ne_si(matrix
->p
[i
][level
],1) &&
458 value_ne_si(matrix
->p
[i
][level
],-1) &&
459 value_notzero_p(matrix
->p
[i
][matrix
->NbColumns
-1]))
460 { value_init_c(numerator
) ;
461 value_init_c(denominator
) ;
462 value_init_c(division
) ;
463 value_init_c(modulo
) ;
465 value_assign(denominator
,matrix
->p
[i
][level
]) ;
466 value_absolute(denominator
,denominator
) ;
467 value_assign(numerator
,matrix
->p
[i
][matrix
->NbColumns
-1]) ;
468 value_modulus(modulo
,numerator
,denominator
) ;
469 value_division(division
,numerator
,denominator
) ;
471 /* There are 4 scenarios:
472 * di +n >= 0 --> i + (n div d) >= 0
473 * -di +n >= 0 --> -i + (n div d) >= 0
474 * di -n >= 0 --> if (n%d == 0) i + ((-n div d)+1) >= 0
475 * else i + (-n div d) >= 0
476 * -di -n >= 0 --> if (n%d == 0) -i + ((-n div d)-1) >= 0
477 * else -i + (-n div d) >= 0
478 * In the following we distinct the scalar value setting and the
481 if (value_pos_p(numerator
) || value_zero_p(modulo
))
482 value_assign(matrix
->p
[i
][matrix
->NbColumns
-1],division
) ;
484 { if (value_pos_p(matrix
->p
[i
][level
]))
485 value_increment(matrix
->p
[i
][matrix
->NbColumns
-1],division
) ;
487 value_decrement(matrix
->p
[i
][matrix
->NbColumns
-1],division
) ;
490 if (value_pos_p(matrix
->p
[i
][level
]))
491 value_set_si(matrix
->p
[i
][level
],1) ;
493 value_set_si(matrix
->p
[i
][level
],-1) ;
495 value_clear_c(numerator
) ;
496 value_clear_c(denominator
) ;
497 value_clear_c(division
) ;
498 value_clear_c(modulo
) ;
505 /* We update the line of equal corresponding to level:
506 * - the first element gives the equality type,
508 value_set_si(equal
->p
[level
-1][0],clast_equal_type(matrix
,level
,line
)) ;
509 /* - the other elements corresponding to the equality itself
510 * (the iterators up to level, then the parameters and the scalar).
512 for (i
=1;i
<=level
;i
++)
513 value_assign(equal
->p
[level
-1][i
],matrix
->p
[line
][i
]) ;
514 for (i
=0;i
<infos
->names
->nb_parameters
+1;i
++)
515 value_assign(equal
->p
[level
-1][equal
->NbColumns
-i
-1],
516 matrix
->p
[line
][matrix
->NbColumns
-i
-1]) ;
518 cloog_matrix_equality_update(equal
,level
,infos
->names
->nb_parameters
) ;
520 return (clast_equal_allow(equal
,level
,level
-1,infos
)) ;
525 * clast_equal_del function :
526 * This function reset the equality corresponding to the iterator (level)
527 * in the equality matrix (equal).
528 * - July 2nd 2002: first version.
530 void clast_equal_del(CloogMatrix
* equal
, int level
)
534 for (i
=0;i
<equal
->NbColumns
;i
++)
535 value_set_si(equal
->p
[level
-1][i
],0) ;
542 * clast_equal function:
543 * This function returns the content an equality matrix (equal) into a clast_stmt.
544 * - the infos structure gives the user all options on code printing and more.
546 * - July 2nd 2002: first version.
547 * - March 16th 2003: return now a string instead of printing directly and do
548 * not write 'Sx()' if there is no spreading, but only 'Sx'.
550 struct clast_stmt
* clast_equal(CloogInfos
*infos
)
554 struct clast_expr
*e
;
555 struct clast_stmt
*a
= NULL
;
556 struct clast_stmt
**next
= &a
;
557 CloogMatrix
*equal
= infos
->equal
;
561 /* It is not necessary to print here the scattering iterators since they
562 * never appear in the statement bodies.
564 for (i
=infos
->names
->nb_scattering
;i
<equal
->NbRows
;i
++)
565 { if (value_notzero_p(equal
->p
[i
][0])&&clast_equal_allow(equal
,i
+1,i
,infos
)) {
566 iterator
= i
- infos
->names
->nb_scattering
;
568 /* pprint_line needs to know that the current line is an equality, so
569 * we temporary remove the equality type and set it to zero (the equality
572 value_assign(type
,equal
->p
[i
][0]) ;
573 value_set_si(equal
->p
[i
][0],0) ;
574 e
= clast_line(equal
,i
,i
+1,infos
) ;
575 value_assign(equal
->p
[i
][0],type
) ;
576 *next
= &new_clast_assignment(infos
->names
->iterators
[iterator
], e
)->stmt
;
577 next
= &(*next
)->next
;
580 value_clear_c(type
) ;
587 * clast_equal_cpp function:
588 * This function prints the substitution data of a statement into a clast_stmt.
589 * Using this function instead of pprint_equal is useful for generating
590 * a compilable pseudo-code by using preprocessor macro for each statement.
591 * By opposition to pprint_equal, the result is less human-readable. For
592 * instance this function will print (i,i+3,k,3) where pprint_equal would
593 * return (j=i+3,l=3).
594 * - level is the number of loops enclosing the statement,
595 * - the infos structure gives the user all options on code printing and more.
597 * - March 12th 2004: first version.
598 * - November 21th 2005: (debug) now works well with GMP version.
600 struct clast_stmt
* clast_equal_cpp(int level
, CloogInfos
*infos
)
604 struct clast_expr
*e
;
605 struct clast_stmt
*a
= NULL
;
606 struct clast_stmt
**next
= &a
;
607 CloogMatrix
*equal
= infos
->equal
;
611 for (i
=infos
->names
->nb_scattering
;i
<level
-1;i
++)
612 { if (value_notzero_p(equal
->p
[i
][0]))
613 { /* pprint_line needs to know that the current line is an equality, so
614 * we temporary remove the equality type and set it to zero (the equality
617 value_assign(type
,equal
->p
[i
][0]) ;
618 value_set_si(equal
->p
[i
][0],0) ;
619 e
= clast_line(equal
,i
,i
+1,infos
) ;
620 value_assign(equal
->p
[i
][0],type
) ;
622 value_set_si(type
, 1);
623 e
= &new_clast_term(type
,
624 infos
->names
->iterators
[i
-infos
->names
->nb_scattering
])->expr
;
626 *next
= &new_clast_assignment(NULL
, e
)->stmt
;
627 next
= &(*next
)->next
;
629 value_clear_c(type
) ;
636 * clast_line function:
637 * This function returns a clast_expr containing the printing of the 'right part'
638 * of a constraint according to an element.
639 * For instance, for the constraint -3*i + 2*j - M >=0 and the element j,
640 * we have j >= (3*i + M)/2. As we are looking for integral solutions, this
641 * function should return 'ceild(3*i+M,2)'.
642 * - matrix is the polyhedron containing all the constraints,
643 * - line_num is the line number in domain of the constraint we want to print,
644 * - level is the column number in domain of the element we want to use,
645 * - the infos structure gives the user some options about code printing,
646 * the number of parameters in domain (nb_par), and the arrays of iterator
647 * names and parameters (iters and params).
649 * - November 2nd 2001: first version.
650 * - June 27th 2003: 64 bits version ready.
652 struct clast_expr
*clast_line(CloogMatrix
*matrix
,
653 int line_num
, int level
, CloogInfos
*infos
)
655 int i
, nb_iter
, sign
, nb_elts
=0 ;
657 Value
* line
, numerator
, denominator
, temp
, division
;
658 struct clast_expr
*e
= NULL
;
660 line
= matrix
->p
[line_num
] ;
662 value_init_c(numerator
) ;
663 value_init_c(denominator
) ;
665 if (value_notzero_p(line
[level
])) {
666 struct clast_reduction
*r
;
667 /* Maybe we need to invert signs in such a way that the element sign is>0.*/
668 sign
= value_pos_p(line
[level
]) ? -1 : 1 ;
670 for (i
= 1, nb_elts
= 0; i
<= matrix
->NbColumns
- 1; ++i
)
671 if (i
!= level
&& value_notzero_p(line
[i
]))
673 r
= new_clast_reduction(clast_red_sum
, nb_elts
);
676 /* First, we have to print the iterators. */
677 nb_iter
= matrix
->NbColumns
- 2 - infos
->names
->nb_parameters
;
678 for (i
=1;i
<=nb_iter
;i
++)
679 if ((i
!= level
) && value_notzero_p(line
[i
]))
680 { if (i
<= infos
->names
->nb_scattering
)
681 name
= infos
->names
->scattering
[i
-1] ;
683 name
= infos
->names
->iterators
[i
-infos
->names
->nb_scattering
-1] ;
686 value_oppose(temp
,line
[i
]) ;
688 value_assign(temp
,line
[i
]) ;
690 r
->elts
[nb_elts
++] = &new_clast_term(temp
, name
)->expr
;
693 /* Next, the parameters. */
694 for (i
=nb_iter
+1;i
<=matrix
->NbColumns
-2;i
++)
695 if ((i
!= level
) && value_notzero_p(line
[i
]))
696 { name
= infos
->names
->parameters
[i
-nb_iter
-1] ;
699 value_oppose(temp
,line
[i
]) ;
701 value_assign(temp
,line
[i
]) ;
703 r
->elts
[nb_elts
++] = &new_clast_term(temp
, name
)->expr
;
707 { value_oppose(numerator
,line
[matrix
->NbColumns
- 1]) ;
708 value_assign(denominator
,line
[level
]) ;
711 { value_assign(numerator
,line
[matrix
->NbColumns
- 1]) ;
712 value_oppose(denominator
,line
[level
]) ;
715 /* Finally, the constant, and the final printing. */
717 if (value_notzero_p(numerator
))
718 r
->elts
[nb_elts
++] = &new_clast_term(numerator
, NULL
)->expr
;
720 if (value_notone_p(line
[level
]) && value_notmone_p(line
[level
]))
721 { if (value_one_p(line
[0]))
722 { if (value_pos_p(line
[level
]))
723 e
= &new_clast_binary(clast_bin_cdiv
, &r
->expr
, denominator
)->expr
;
725 e
= &new_clast_binary(clast_bin_fdiv
, &r
->expr
, denominator
)->expr
;
727 e
= &new_clast_binary(clast_bin_div
, &r
->expr
, denominator
)->expr
;
732 free_clast_reduction(r
);
733 if (value_zero_p(numerator
))
734 e
= &new_clast_term(numerator
, NULL
)->expr
;
736 { if (value_notone_p(denominator
))
737 { if (value_one_p(line
[0])) /* useful? */
738 { value_modulus(temp
,numerator
,denominator
) ;
739 if (value_zero_p(temp
))
740 { value_division(temp
,numerator
,denominator
) ;
741 e
= &new_clast_term(temp
, NULL
)->expr
;
744 { value_init_c(division
) ;
745 value_division(division
,numerator
,denominator
) ;
746 if (value_neg_p(numerator
)) {
747 if (value_pos_p(line
[level
])) {
749 e
= &new_clast_term(division
, NULL
)->expr
;
752 value_decrement(temp
,division
) ;
753 e
= &new_clast_term(temp
, NULL
)->expr
;
757 { if (value_pos_p(line
[level
]))
758 { /* nb>0 need max */
759 value_increment(temp
,division
) ;
760 e
= &new_clast_term(temp
, NULL
)->expr
;
764 e
= &new_clast_term(division
, NULL
)->expr
;
766 value_clear_c(division
) ;
770 e
= &new_clast_binary(clast_bin_div
,
771 &new_clast_term(numerator
, NULL
)->expr
,
775 e
= &new_clast_term(numerator
, NULL
)->expr
;
780 value_clear_c(temp
) ;
781 value_clear_c(numerator
) ;
782 value_clear_c(denominator
) ;
789 * clast_minmax function:
790 * This function returns a clast_expr containing the printing of a minimum or a
791 * maximum of the 'right parts' of all constraints according to an element.
792 * For instance consider the constraints:
796 * if we are looking for the minimum for the element j, the function should
797 * return 'max(ceild(3*i+M,2),-2*i)'.
798 * - matrix is the polyhedron containing all the constraints,
799 * - level is the column number in domain of the element we want to use,
800 * - max is a boolean set to 1 if we are looking for a maximum, 0 for a minimum,
801 * - guard is set to 0 if there is no guard, and set to the level of the element
802 * with a guard otherwise (then the function gives the max or the min only
803 * for the constraint where the guarded coefficient is 0),
804 * - the infos structure gives the user some options about code printing,
805 * the number of parameters in domain (nb_par), and the arrays of iterator
806 * names and parameters (iters and params).
808 * - November 2nd 2001: first version.
810 struct clast_expr
*clast_minmax(CloogMatrix
*matrix
,
811 int level
, int max
, int guard
,
814 struct clast_reduction
*r
;
816 for (i
=0, n
=0;i
<matrix
->NbRows
;i
++)
817 if (((max
&& value_pos_p(matrix
->p
[i
][level
])) ||
818 (!max
&& value_neg_p(matrix
->p
[i
][level
]))) &&
819 (!guard
|| value_zero_p(matrix
->p
[i
][guard
])) &&
820 (value_notzero_p(matrix
->p
[i
][0])))
824 r
= new_clast_reduction(max
? clast_red_max
: clast_red_min
, n
);
826 for (i
=0, n
=0;i
<matrix
->NbRows
;i
++)
827 if (((max
&& value_pos_p(matrix
->p
[i
][level
])) ||
828 (!max
&& value_neg_p(matrix
->p
[i
][level
]))) &&
829 (!guard
|| value_zero_p(matrix
->p
[i
][guard
])) &&
830 (value_notzero_p(matrix
->p
[i
][0])))
831 r
->elts
[n
++] = clast_line(matrix
,i
,level
,infos
);
838 * insert_guard function:
839 * This function inserts a guard in the clast.
840 * A guard on an element (level) is :
841 * -> the conjunction of all the existing constraints where the coefficient of
842 * this element is 0 if the element is an iterator,
843 * -> the conjunction of all the existing constraints if the element isn't an
845 * For instance, considering these constraints and the element j:
848 * this function should return 'if (2*i+M>=0) {'.
849 * - matrix is the polyhedron containing all the constraints,
850 * - level is the column number of the element in matrix we want to use,
851 * - the infos structure gives the user some options about code printing,
852 * the number of parameters in matrix (nb_par), and the arrays of iterator
853 * names and parameters (iters and params).
855 * - November 3rd 2001: first version.
856 * - November 14th 2001: a lot of 'purifications'.
857 * - July 31th 2002: (debug) some guard parts are no more redundants.
858 * - August 12th 2002: polyhedra union ('or' conditions) are now supported.
859 * - October 27th 2005: polyhedra union ('or' conditions) are no more supported
860 * (the need came from loop_simplify that may result in
861 * domain unions, now it should be fixed directly in
862 * cloog_loop_simplify).
864 void insert_guard(CloogMatrix
*matrix
, int level
,
865 struct clast_stmt
***next
, CloogInfos
*infos
)
867 int i
, j
, k
, l
, guarded
, minmax
=-1, nb_and
= 0, nb_iter
;
870 struct clast_guard
*g
;
877 value_set_si(one
, 1);
879 g
= new_clast_guard(2 * (matrix
->NbColumns
-2));
881 /* Well, it looks complicated because I wanted to have a particular, more
882 * readable, ordering, obviously this function may be far much simpler !
884 copy
= cloog_matrix_copy(matrix
) ;
886 nb_iter
= copy
->NbColumns
- 2 - infos
->names
->nb_parameters
;
889 /* We search for guard parts. */
890 for (i
=1;i
<=copy
->NbColumns
-2;i
++)
891 for (j
=0;j
<copy
->NbRows
;j
++)
892 if (value_notzero_p(copy
->p
[j
][i
]) &&
893 (value_zero_p(copy
->p
[j
][level
]) || (nb_iter
< level
))) {
894 struct clast_term
*t
;
896 { if (i
<= infos
->names
->nb_scattering
)
897 name
= infos
->names
->scattering
[i
-1] ;
899 name
= infos
->names
->iterators
[i
-infos
->names
->nb_scattering
-1] ;
902 name
= infos
->names
->parameters
[i
-(nb_iter
+1)] ;
904 g
->eq
[nb_and
].LHS
= &(t
= new_clast_term(one
, name
))->expr
;
905 if (value_zero_p(copy
->p
[j
][0])) {
906 /* put the "denominator" in the LHS */
907 value_assign(t
->val
, copy
->p
[j
][i
]);
908 value_set_si(copy
->p
[j
][i
], 1);
909 g
->eq
[nb_and
].sign
= 0;
910 g
->eq
[nb_and
].RHS
= clast_line(copy
,j
,i
,infos
) ;
911 value_assign(copy
->p
[j
][i
], t
->val
);
913 if (value_pos_p(copy
->p
[j
][i
])) {
915 g
->eq
[nb_and
].sign
= 1;
918 g
->eq
[nb_and
].sign
= -1;
921 guarded
= (nb_iter
>= level
) ? level
: 0 ;
922 g
->eq
[nb_and
].RHS
= clast_minmax(copy
,i
,minmax
,guarded
,infos
) ;
926 /* 'elimination' of the current constraint, this avoid to use one
927 * constraint more than once. The current line is always eliminated,
928 * and the next lines if they are in a min or a max.
930 for (k
=i
;k
<=copy
->NbColumns
-2;k
++)
931 value_set_si(copy
->p
[j
][k
],0) ;
934 for (l
=j
+1;l
<copy
->NbRows
;l
++)
935 if (((minmax
== 1) && value_pos_p(copy
->p
[l
][i
])) ||
936 ((minmax
== 0) && value_neg_p(copy
->p
[l
][i
])))
937 for (k
=i
;k
<=copy
->NbColumns
-2;k
++)
938 value_set_si(copy
->p
[l
][k
],0) ;
940 cloog_matrix_free(copy
) ;
955 * insert_modulo_guard:
956 * This function inserts a modulo guard corresponding to an equality.
957 * See insert_equality.
958 * - matrix is the polyhedron containing all the constraints,
959 * - num is the line number of the constraint in matrix we want to print,
960 * - level is the column number of the element in matrix we want to use,
961 * - the infos structure gives the user some options about code printing,
962 * the number of parameters in matrix (nb_par), and the arrays of iterator
963 * names and parameters (iters and params).
965 void insert_modulo_guard(CloogMatrix
*matrix
, int num
, int level
,
966 struct clast_stmt
***next
, CloogInfos
*infos
)
968 int i
, nb_elts
= 0, len
, nb_iter
, in_stride
= 0;
972 if (value_one_p(matrix
->p
[num
][level
]) || value_mone_p(matrix
->p
[num
][level
]))
977 len
= matrix
->NbColumns
;
978 nb_iter
= matrix
->NbColumns
- 2 - infos
->names
->nb_parameters
;
980 line_vector
= Vector_Alloc(len
);
981 line
= line_vector
->p
;
982 if (value_neg_p(matrix
->p
[num
][level
]))
983 Vector_Copy(matrix
->p
[num
]+1, line
+1, len
-1);
985 value_set_si(val
, -1);
986 Vector_Scale(matrix
->p
[num
]+1, line
+1, val
, len
-1);
988 value_oppose(line
[level
], line
[level
]);
989 assert(value_pos_p(line
[level
]));
991 for (i
= 1, nb_elts
= 0; i
<= len
-1; ++i
) {
994 value_pmodulus(line
[i
],line
[i
],line
[level
]);
995 if (value_zero_p(line
[i
]))
999 value_modulus(val
,infos
->stride
[i
-1],line
[level
]);
1000 /* We need to know if an element of the equality has not to be printed
1001 * because of a stride that guarantees that this element can be divided by
1002 * the current coefficient. Because when there is a constant element, it
1003 * is included in the stride calculation (more exactly in the strided
1004 * iterator new lower bound: the 'offset') and we have not to print it.
1006 if (value_zero_p(val
)) {
1016 if (nb_elts
|| (value_notzero_p(line
[len
-1]) && (!in_stride
))) {
1017 struct clast_reduction
*r
;
1018 struct clast_expr
*e
;
1019 struct clast_guard
*g
;
1022 r
= new_clast_reduction(clast_red_sum
, nb_elts
+1);
1025 /* First, the modulo guard : the iterators... */
1026 for (i
=1;i
<=nb_iter
;i
++) {
1027 if (i
== level
|| value_zero_p(line
[i
]))
1029 value_modulus(val
,infos
->stride
[i
-1],line
[level
]);
1030 if (value_zero_p(val
))
1033 if (i
<= infos
->names
->nb_scattering
)
1034 name
= infos
->names
->scattering
[i
-1];
1036 name
= infos
->names
->iterators
[i
-infos
->names
->nb_scattering
-1];
1038 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
], name
)->expr
;
1041 /* ...the parameters... */
1042 for (i
=nb_iter
+1;i
<=len
-2;i
++) {
1043 if (value_zero_p(line
[i
]))
1046 name
= infos
->names
->parameters
[i
-nb_iter
-1] ;
1047 r
->elts
[nb_elts
++] = &new_clast_term(line
[i
], name
)->expr
;
1050 /* ...the constant. */
1051 if (value_notzero_p(line
[len
-1]))
1052 r
->elts
[nb_elts
++] = &new_clast_term(line
[len
-1], NULL
)->expr
;
1054 /* our initial computation may have been an overestimate */
1057 e
= &new_clast_binary(clast_bin_mod
, &r
->expr
, line
[level
])->expr
;
1058 g
= new_clast_guard(1);
1060 value_set_si(val
, 0);
1061 g
->eq
[0].RHS
= &new_clast_term(val
, NULL
)->expr
;
1068 Vector_Free(line_vector
);
1075 * insert_equality function:
1076 * This function inserts an equality
1077 * constraint according to an element in the clast.
1078 * An equality can be preceded by a 'modulo guard'.
1079 * For instance, consider the constraint i -2*j = 0 and the
1080 * element j: pprint_equality should return 'if(i%2==0) { j = i/2 ;'.
1081 * - matrix is the polyhedron containing all the constraints,
1082 * - num is the line number of the constraint in matrix we want to print,
1083 * - level is the column number of the element in matrix we want to use,
1084 * - the infos structure gives the user some options about code printing,
1085 * the number of parameters in matrix (nb_par), and the arrays of iterator
1086 * names and parameters (iters and params).
1088 * - November 13th 2001: first version.
1089 * - June 26th 2003: simplification of the modulo guards (remove parts such as
1090 * modulo is 0, compare vivien or vivien2 with a previous
1091 * version for an idea).
1092 * - June 29th 2003: non-unit strides support.
1093 * - July 14th 2003: (debug) no more print the constant in the modulo guard when
1094 * it was previously included in a stride calculation.
1096 void insert_equality(CloogMatrix
*matrix
, int num
,
1097 int level
, struct clast_stmt
***next
, CloogInfos
*infos
)
1099 struct clast_expr
*e
;
1100 struct clast_assignment
*ass
;
1102 insert_modulo_guard(matrix
, num
, level
, next
, infos
);
1104 if (!clast_equal_add(infos
->equal
,matrix
,level
,num
,infos
))
1105 { /* Finally, the equality. */
1107 /* If we have to make a block by dimension, we start the block. Function
1108 * pprint knows if there is an equality, if this is the case, it checks
1109 * for the same following condition to close the brace.
1111 if (infos
->options
->block
) {
1112 struct clast_block
*b
= new_clast_block();
1117 e
= clast_line(matrix
,num
,level
,infos
) ;
1118 if (level
<= infos
->names
->nb_scattering
)
1119 ass
= new_clast_assignment(infos
->names
->scattering
[level
-1], e
);
1121 ass
= new_clast_assignment(
1122 infos
->names
->iterators
[level
-infos
->names
->nb_scattering
-1], e
);
1124 **next
= &ass
->stmt
;
1125 *next
= &(**next
)->next
;
1133 * insert_for function:
1134 * This function inserts a for loop in the clast.
1135 * A loop header according to an element is the conjonction of a minimum and a
1136 * maximum on the element (they give the loop bounds).
1137 * For instance, considering these constraints and the element j:
1141 * this function should return 'for (j=max(-i+9*M,4*M),j<=5*M;j++) {'.
1142 * - matrix is the polyhedron containing all the constraints,
1143 * - level is the column number of the element in matrix we want to use,
1144 * - the infos structure gives the user some options about code printing,
1145 * the number of parameters in matrix (nb_par), and the arrays of iterator
1146 * names and parameters (iters and params).
1148 * - July 2nd 2002: first version (pick from pprint function).
1149 * - March 6th 2003: infinite domain support.
1150 * - June 29th 2003: non-unit strides support.
1152 void insert_for(CloogMatrix
*matrix
, int level
,
1153 struct clast_stmt
***next
, CloogInfos
*infos
)
1156 struct clast_expr
*e1
;
1157 struct clast_expr
*e2
;
1158 struct clast_assignment
*ass
;
1160 if (level
<= infos
->names
->nb_scattering
)
1161 iterator
= infos
->names
->scattering
[level
-1] ;
1163 iterator
= infos
->names
->iterators
[level
-infos
->names
->nb_scattering
-1] ;
1165 e1
= clast_minmax(matrix
,level
,1,0,infos
) ;
1166 e2
= clast_minmax(matrix
,level
,0,0,infos
) ;
1168 /* If min and max are not equal there is a 'for' else, there is a '='.
1169 * In the special case e1 = e2 = NULL, this is an infinite loop
1170 * so this is not a '='.
1172 if (!clast_expr_equal(e1
, e2
) || !infos
->options
->otl
|| (!e1
&& !e2
)) {
1173 struct clast_for
*f
= new_clast_for(iterator
, e1
, e2
, infos
->stride
[level
-1]);
1177 else if (!clast_equal_add(infos
->equal
,matrix
,level
,ONE_TIME_LOOP
,infos
)) {
1178 if (infos
->options
->block
) {
1179 struct clast_block
*b
= new_clast_block();
1183 ass
= new_clast_assignment(iterator
, e1
);
1184 **next
= &ass
->stmt
;
1185 *next
= &(**next
)->next
;
1193 * insert_scalar function:
1194 * This function inserts assignments to the scalar values
1195 * that follows the level (level). It finds by scanning (loop) by inner level,
1196 * the first CloogBlock data structure (at this step, all blocks has the same
1197 * scalar vector information after (level)), and prints all the adjacent
1198 * scalar values following (level), if it is required by options in (info).
1199 * - loop is the loop structure to begin the search for a block,
1200 * - level is the current loop level,
1201 * - scalar points to the number of scalar values already visited,
1202 * - the infos structure gives the user options about code printing and more.
1204 * - September 12th 2005: first version.
1206 void insert_scalar(CloogLoop
*loop
, int level
, int *scalar
,
1207 struct clast_stmt
***next
, CloogInfos
*infos
)
1209 struct clast_block
*b
;
1210 struct clast_term
*t
;
1212 if ((!infos
->options
->csp
) &&
1213 (level
+(*scalar
) <= infos
->nb_scattdims
) &&
1214 (infos
->scaldims
[level
+(*scalar
)-1]))
1215 { while (loop
->block
== NULL
)
1216 loop
= loop
->inner
;
1218 while ((level
+(*scalar
) <= infos
->nb_scattdims
) &&
1219 (infos
->scaldims
[level
+(*scalar
)-1])) {
1220 if (infos
->options
->block
) {
1221 b
= new_clast_block();
1226 t
= new_clast_term(loop
->block
->scaldims
[(*scalar
)], NULL
);
1227 **next
= &new_clast_assignment(infos
->names
->scalars
[(*scalar
)],
1229 *next
= &(**next
)->next
;
1240 * insert_block function:
1241 * This function inserts a statement block.
1242 * - block is the statement block,
1243 * - level is the number of loops enclosing the statement,
1244 * - the infos structure gives the user some options about code printing,
1245 * the number of parameters in domain (nb_par), and the arrays of iterator
1246 * names and parameters (iters and params).
1248 * - September 21th 2003: first version (pick from pprint function).
1250 void insert_block(CloogBlock
*block
, int level
,
1251 struct clast_stmt
***next
, CloogInfos
*infos
)
1253 CloogStatement
* statement
;
1254 struct clast_stmt
*subs
;
1259 for (statement
= block
->statement
; statement
; statement
= statement
->next
) {
1260 if (infos
->options
->cpp
== 0)
1261 subs
= clast_equal(infos
);
1263 subs
= clast_equal_cpp(level
,infos
);
1265 **next
= &new_clast_user_stmt(statement
, subs
)->stmt
;
1266 *next
= &(**next
)->next
;
1272 * insert_loop function:
1273 * This function concerts the content of a CloogLoop structure (loop) into a
1274 * clast_stmt (inserted at **next).
1275 * The iterator (level) of
1276 * the current loop is given by 'level': this is the column number of the
1277 * domain corresponding to the current loop iterator. The data of a loop are
1278 * written in this order:
1279 * 1. The guard of the loop, i.e. each constraint in the domain that do not
1280 * depend on the iterator (when the entry in the column 'level' is 0).
1281 * 2. The iteration domain of the iterator, given by the constraints in the
1282 * domain depending on the iterator, i.e.:
1283 * * an equality if the iterator has only one value (possibly preceded by
1284 * a guard verifying if this value is integral), *OR*
1285 * * a loop from the minimum possible value of the iterator to the maximum
1287 * 3. The included statement block.
1288 * 4. The inner loops (recursive call).
1289 * 5. The following loops (recursive call).
1290 * - level is the recursion level or the iteration level that we are printing,
1291 * - the infos structure gives the user some options about code printing,
1292 * the number of parameters in domain (nb_par), and the arrays of iterator
1293 * names and parameters (iters and params).
1295 * - November 2nd 2001: first version.
1296 * - March 6th 2003: infinite domain support.
1297 * - April 19th 2003: (debug) NULL loop support.
1298 * - June 29th 2003: non-unit strides support.
1299 * - April 28th 2005: (debug) level is level+equality when print statement!
1300 * - June 16th 2005: (debug) the N. Vasilache normalization step has been
1301 * added to avoid iteration duplication (see DaeGon Kim
1302 * bug in cloog_program_generate). Try vasilache.cloog
1303 * with and without the call to cloog_matrix_normalize,
1304 * using -f 8 -l 9 options for an idea.
1305 * - September 15th 2005: (debug) don't close equality braces when unnecessary.
1306 * - October 16th 2005: (debug) scalar value is saved for next loops.
1308 void insert_loop(CloogLoop
* loop
, int level
, int scalar
,
1309 struct clast_stmt
***next
, CloogInfos
*infos
)
1311 int i
, equality
=0, scalar_level
;
1312 CloogMatrix
* matrix
, * temp
;
1313 struct clast_stmt
**top
= *next
;
1315 /* It can happen that loop be NULL when an input polyhedron is empty. */
1319 /* The matrix has not always a shape that allows us to generate code from it,
1320 * thus we normalize it, we also simplify it with the matrix of equalities.
1322 temp
= cloog_domain_domain2matrix(loop
->domain
);
1323 cloog_matrix_normalize(temp
,level
);
1324 matrix
= cloog_matrix_simplify(temp
,infos
->equal
,level
,
1325 infos
->names
->nb_parameters
);
1326 cloog_matrix_free(temp
);
1327 value_assign(infos
->stride
[level
-1],loop
->stride
);
1329 /* First of all we have to print the guard. */
1330 insert_guard(matrix
,level
, next
, infos
);
1332 /* Then we print scalar dimensions. */
1333 scalar_level
= scalar
;
1334 insert_scalar(loop
,level
,&scalar
, next
, infos
);
1336 if ((matrix
->NbColumns
- 2 - infos
->names
->nb_parameters
>= level
)) {
1337 /* We scan all the constraints to know in which case we are :
1338 * [[if] equality] or [for].
1340 for (i
=0;i
<matrix
->NbRows
;i
++)
1341 if (value_zero_p(matrix
->p
[i
][0]) &&
1342 value_notzero_p(matrix
->p
[i
][level
]))
1343 { /* If there is an equality, we can print it directly -no ambiguity-.
1344 * PolyLib can give more than one equality, we use just the first one
1345 * (this is a PolyLib problem, but all equalities are equivalent).
1347 insert_equality(matrix
,i
,level
, next
, infos
);
1353 insert_for(matrix
, level
, next
, infos
);
1356 /* Finally, if there is an included statement block, print it. */
1357 insert_block(loop
->block
, level
+equality
, next
, infos
);
1359 /* Go to the next level. */
1360 if (loop
->inner
!= NULL
)
1361 insert_loop(loop
->inner
, level
+1,scalar
, next
, infos
);
1363 clast_equal_del(infos
->equal
,level
);
1364 cloog_matrix_free(matrix
);
1366 /* Go to the next loop on the same level. */
1368 top
= &(*top
)->next
;
1369 if (loop
->next
!= NULL
)
1370 insert_loop(loop
->next
, level
,scalar_level
, &top
,infos
);
1374 struct clast_stmt
*cloog_clast_create(CloogProgram
*program
,
1375 CloogOptions
*options
)
1377 CloogInfos
*infos
= ALLOC(CloogInfos
);
1379 struct clast_stmt
*root
= NULL
;
1380 struct clast_stmt
**next
= &root
;
1382 infos
->names
= program
->names
;
1383 infos
->options
= options
;
1384 infos
->scaldims
= program
->scaldims
;
1385 infos
->nb_scattdims
= program
->nb_scattdims
;
1387 /* Allocation for the array of strides, there is a +1 since the statement can
1388 * be included inside an external loop without iteration domain.
1390 nb_levels
= program
->names
->nb_scattering
+program
->names
->nb_iterators
+1;
1391 infos
->stride
= ALLOCN(Value
, nb_levels
);
1392 for (i
= 0; i
< nb_levels
; ++i
)
1393 value_init_c(infos
->stride
[i
]);
1395 infos
->equal
= cloog_matrix_alloc(nb_levels
,
1396 nb_levels
+ program
->names
->nb_parameters
+ 1);
1398 insert_loop(program
->loop
, 1, 0, &next
, infos
);
1400 cloog_matrix_free(infos
->equal
);
1402 for (i
= 0; i
< nb_levels
; ++i
)
1403 value_clear_c(infos
->stride
[i
]);
1404 free(infos
->stride
);