2 /**-------------------------------------------------------------------**
4 **-------------------------------------------------------------------**
6 **-------------------------------------------------------------------**
7 ** First version: april 17th 2005 **
8 **-------------------------------------------------------------------**/
11 /******************************************************************************
12 * CLooG : the Chunky Loop Generator (experimental) *
13 ******************************************************************************
15 * Copyright (C) 2005 Cedric Bastoul *
17 * This is free software; you can redistribute it and/or modify it under the *
18 * terms of the GNU General Public License as published by the Free Software *
19 * Foundation; either version 2 of the License, or (at your option) any later *
22 * This software is distributed in the hope that it will be useful, but *
23 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
24 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License *
27 * You should have received a copy of the GNU General Public License along *
28 * with software; if not, write to the Free Software Foundation, Inc., *
29 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
31 * CLooG, the Chunky Loop Generator *
32 * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr *
34 ******************************************************************************/
35 /* CAUTION: the english used for comments is probably the worst you ever read,
36 * please feel free to correct and improve it !
43 #include <cloog/polylib/cloog.h>
46 #define ALLOC(type) (type*)malloc(sizeof(type))
47 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
50 /******************************************************************************
52 ******************************************************************************/
56 * CLooG makes an intensive use of matrix operations and the PolyLib do
57 * the job. Here are the interfaces to all the PolyLib calls (CLooG uses 18
58 * PolyLib functions), with or without some adaptations. If another matrix
59 * library can be used, only these functions have to be changed.
64 * cloog_matrix_print function:
65 * This function prints the content of a Matrix structure (matrix) into a
66 * file (foo, possibly stdout).
68 void cloog_matrix_print(FILE * foo
, Matrix
* matrix
)
69 { Matrix_Print(foo
,P_VALUE_FMT
,matrix
) ;
74 * cloog_matrix_free function:
75 * This function frees the allocated memory for a Matrix structure
78 void cloog_matrix_free(Matrix
* matrix
)
83 void cloog_constraint_set_free(CloogConstraintSet
*constraints
)
85 cloog_matrix_free(constraints
);
88 int cloog_constraint_set_contains_level(CloogConstraintSet
*constraints
,
89 int level
, int nb_parameters
)
91 return constraints
->NbColumns
- 2 - nb_parameters
>= level
;
94 /* Check if the variable at position level is defined by an
95 * equality. If so, return the row number. Otherwise, return -1.
97 * If there is an equality, we can print it directly -no ambiguity-.
98 * PolyLib can give more than one equality, we use just the first one
99 * (this is a PolyLib problem, but all equalities are equivalent).
101 CloogConstraint
cloog_constraint_set_defining_equality(CloogConstraintSet
*matrix
, int level
)
103 CloogConstraint constraint
;
106 constraint
.set
= matrix
;
107 for (i
= 0; i
< matrix
->NbRows
; i
++)
108 if (value_zero_p(matrix
->p
[i
][0]) &&
109 value_notzero_p(matrix
->p
[i
][level
])) {
110 constraint
.line
= &matrix
->p
[i
];
113 return cloog_constraint_invalid();
116 /* Check if two vectors are eachothers opposite.
117 * Return 1 if they are, 0 if they are not.
119 static int Vector_Opposite(Value
*p1
, Value
*p2
, unsigned len
)
123 for (i
= 0; i
< len
; ++i
) {
124 if (value_abs_ne(p1
[i
], p2
[i
]))
126 if (value_zero_p(p1
[i
]))
128 if (value_eq(p1
[i
], p2
[i
]))
134 /* Check if the variable (e) at position level is defined by a
135 * pair of inequalities
136 * <a, i> + -m e + <b, p> + k1 >= 0
137 * <-a, i> + m e + <-b, p> + k2 >= 0
138 * with 0 <= k1 + k2 < m
139 * If so return the row number of the upper bound and set *lower
140 * to the row number of the lower bound. If not, return -1.
142 * If the variable at position level occurs in any other constraint,
143 * then we currently return -1. The modulo guard that we would generate
144 * would still be correct, but we would also need to generate
145 * guards corresponding to the other constraints, and this has not
146 * been implemented yet.
148 CloogConstraint
cloog_constraint_set_defining_inequalities(CloogConstraintSet
*matrix
,
149 int level
, CloogConstraint
*lower
, int nb_par
)
153 unsigned len
= matrix
->NbColumns
- 2;
154 unsigned nb_iter
= len
- nb_par
;
155 CloogConstraint constraint
;
157 constraint
.set
= matrix
;
159 for (i
= 0; i
< matrix
->NbRows
; i
++) {
160 if (value_zero_p(matrix
->p
[i
][level
]))
162 if (value_zero_p(matrix
->p
[i
][0]))
163 return cloog_constraint_invalid();
164 if (value_one_p(matrix
->p
[i
][level
]))
165 return cloog_constraint_invalid();
166 if (value_mone_p(matrix
->p
[i
][level
]))
167 return cloog_constraint_invalid();
168 if (First_Non_Zero(matrix
->p
[i
]+level
+1,
169 (1+nb_iter
)-(level
+1)) != -1)
170 return cloog_constraint_invalid();
171 for (j
= i
+1; j
< matrix
->NbRows
; ++j
) {
172 if (value_zero_p(matrix
->p
[j
][level
]))
174 if (value_zero_p(matrix
->p
[j
][0]))
175 return cloog_constraint_invalid();
176 if (value_one_p(matrix
->p
[j
][level
]))
177 return cloog_constraint_invalid();
178 if (value_mone_p(matrix
->p
[j
][level
]))
179 return cloog_constraint_invalid();
180 if (First_Non_Zero(matrix
->p
[j
]+level
+1,
181 (1+nb_iter
)-(level
+1)) != -1)
182 return cloog_constraint_invalid();
185 value_addto(m
, matrix
->p
[i
][1+len
], matrix
->p
[j
][1+len
]);
186 if (value_neg_p(m
) ||
187 value_abs_ge(m
, matrix
->p
[i
][level
])) {
189 return cloog_constraint_invalid();
193 if (!Vector_Opposite(matrix
->p
[i
]+1, matrix
->p
[j
]+1,
195 return cloog_constraint_invalid();
196 for (k
= j
+1; k
< matrix
->NbRows
; ++k
)
197 if (value_notzero_p(matrix
->p
[k
][level
]))
198 return cloog_constraint_invalid();
199 if (value_pos_p(matrix
->p
[i
][level
])) {
200 lower
->line
= &matrix
->p
[i
];
201 constraint
.line
= &matrix
->p
[j
];
203 lower
->line
= &matrix
->p
[j
];
204 constraint
.line
= &matrix
->p
[i
];
209 return cloog_constraint_invalid();
212 int cloog_constraint_set_total_dimension(CloogConstraintSet
*constraints
)
214 return constraints
->NbColumns
- 2;
217 int cloog_constraint_set_n_iterators(CloogConstraintSet
*constraint
, int nb_par
)
219 return cloog_constraint_set_total_dimension(constraint
) - nb_par
;
222 int cloog_equal_total_dimension(CloogEqualities
*equal
)
224 return cloog_constraint_set_total_dimension(equal
->constraints
);
227 int cloog_constraint_total_dimension(CloogConstraint constraint
)
229 return cloog_constraint_set_total_dimension(constraint
.set
);
233 * cloog_matrix_alloc function:
234 * This function allocates the memory space for a Matrix structure having
235 * nb_rows rows and nb_columns columns, it set its elements to 0.
237 Matrix
* cloog_matrix_alloc(unsigned nb_rows
, unsigned nb_columns
)
239 return Matrix_Alloc(nb_rows
,nb_columns
) ;
244 * cloog_matrix_matrix function:
245 * This function converts a PolyLib Matrix to a Matrix structure.
247 Matrix
* cloog_matrix_matrix(Matrix
*matrix
)
253 /******************************************************************************
254 * Structure display function *
255 ******************************************************************************/
259 * cloog_loop_print_structure function:
260 * Displays a Matrix structure (matrix) into a file (file, possibly stdout)
261 * in a way that trends to be understandable without falling in a deep
262 * depression or, for the lucky ones, getting a headache... It includes an
263 * indentation level (level) in order to work with others print_structure
264 * functions. Written by Olivier Chorier, Luc Marchaud, Pierre Martin and
266 * - April 24th 2005: Initial version.
267 * - June 2nd 2005: (Ced) Extraction from cloog_loop_print_structure and
268 * integration in matrix.c.
269 * - June 22rd 2005: Adaptation for GMP.
271 void cloog_matrix_print_structure(FILE * file
, Matrix
* matrix
, int level
)
274 /* Display the matrix. */
275 for (i
=0; i
<matrix
->NbRows
; i
++)
276 { for(j
=0; j
<=level
; j
++)
277 fprintf(file
,"|\t") ;
281 for (j
=0; j
<matrix
->NbColumns
; j
++)
282 { value_print(file
,P_VALUE_FMT
,matrix
->p
[i
][j
]) ;
286 fprintf(file
,"]\n") ;
291 /******************************************************************************
293 ******************************************************************************/
297 * cloog_matrix_read function:
298 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
299 * posibly stdin) and returns a pointer this matrix.
300 * October 18th 2001: first version.
301 * - April 17th 2005: this function moved from domain.c to here.
302 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
305 Matrix
* cloog_matrix_read(FILE * foo
)
306 { unsigned NbRows
, NbColumns
;
308 char *c
, s
[MAX_STRING
], str
[MAX_STRING
] ;
312 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
313 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %u %u",&NbRows
,&NbColumns
)<2))
314 fgets(s
,MAX_STRING
,foo
) ;
316 matrix
= cloog_matrix_alloc(NbRows
,NbColumns
) ;
319 for (i
=0;i
<matrix
->NbRows
;i
++)
321 { c
= fgets(s
,MAX_STRING
,foo
) ;
322 while ((c
!= NULL
) && isspace(*c
) && (*c
!= '\n'))
325 while (c
!= NULL
&& (*c
== '#' || *c
== '\n'));
328 cloog_die("not enough rows.\n");
329 for (j
=0;j
<matrix
->NbColumns
;j
++)
330 { if (c
== NULL
|| *c
== '#' || *c
== '\n')
331 cloog_die("not enough columns.\n");
332 /* NdCed : Dans le n ca met strlen(str). */
333 if (sscanf(c
,"%s%n",str
,&n
) == 0)
334 cloog_die("not enough rows.\n");
335 value_read(*(p
++),str
) ;
344 /******************************************************************************
345 * Equalities spreading functions *
346 ******************************************************************************/
349 /* Equalities are stored inside a Matrix data structure called "equal".
350 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total
351 * dimensions + 1, the "+ 1" is because a statement can be included inside an
352 * external loop without iteration domain), and (nb_scattering + nb_iterators +
353 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality
354 * type). The ith row corresponds to the equality "= 0" for the ith dimension
355 * iterator. The first column gives the equality type (0: no equality, then
356 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for
357 * the current level is found, the corresponding row is updated. Then the
358 * equality if it exists is used to simplify expressions (e.g. if we have
359 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of
360 * the pprint call, the corresponding row is reset to zero.
363 CloogEqualities
*cloog_equal_alloc(int n
, int nb_levels
,
367 CloogEqualities
*equal
= ALLOC(CloogEqualities
);
369 equal
->constraints
= cloog_matrix_alloc(n
, nb_levels
+ nb_parameters
+ 1);
370 equal
->types
= ALLOCN(int, n
);
371 for (i
= 0; i
< n
; ++i
)
372 equal
->types
[i
] = EQTYPE_NONE
;
376 void cloog_equal_free(CloogEqualities
*equal
)
378 cloog_matrix_free(equal
->constraints
);
383 int cloog_equal_count(CloogEqualities
*equal
)
385 return equal
->constraints
->NbRows
;
388 CloogConstraintSet
*cloog_equal_constraints(CloogEqualities
*equal
)
390 return equal
->constraints
;
395 * cloog_constraint_equal_type function :
396 * This function returns the type of the equality in the constraint (line) of
397 * (constraints) for the element (level). An equality is 'constant' iff all
398 * other factors are null except the constant one. It is a 'pure item' iff
399 * it is equal or opposite to a single variable or parameter.
400 * Otherwise it is an 'affine expression'.
402 * i = -13 is constant, i = j, j = -M are pure items,
403 * j = 2*M, i = j+1, 2*j = M are affine expressions.
405 * - constraints is the matrix of constraints,
406 * - level is the column number in equal of the element which is 'equal to',
408 * - July 3rd 2002: first version, called pprint_equal_isconstant.
409 * - July 6th 2002: adaptation for the 3 types.
410 * - June 15th 2005: (debug) expr = domain->Constraint[line] was evaluated
411 * before checking if line != ONE_TIME_LOOP. Since
412 * ONE_TIME_LOOP is -1, an invalid read was possible.
413 * - October 19th 2005: Removal of the once-time-loop specific processing.
415 static int cloog_constraint_equal_type(CloogConstraint constraint
, int level
)
420 expr
= *constraint
.line
;
422 if (value_notone_p(expr
[level
]) && value_notmone_p(expr
[level
]))
423 return EQTYPE_EXAFFINE
;
425 /* There is only one non null factor, and it must be +1 or -1 for
426 * iterators or parameters.
428 for (i
=1;i
<=constraint
.set
->NbColumns
-2;i
++)
429 if (value_notzero_p(expr
[i
]) && (i
!= level
))
430 { if ((value_notone_p(expr
[i
]) && value_notmone_p(expr
[i
])) || (one
!= 0))
431 return EQTYPE_EXAFFINE
;
435 /* if the constant factor is non null, it must be alone. */
437 { if (value_notzero_p(expr
[constraint
.set
->NbColumns
-1]))
438 return EQTYPE_EXAFFINE
;
441 return EQTYPE_CONSTANT
;
443 return EQTYPE_PUREITEM
;
447 int cloog_equal_type(CloogEqualities
*equal
, int level
)
449 return equal
->types
[level
-1];
454 * cloog_equal_update function:
455 * this function updates a matrix of equalities where each row corresponds to
456 * the equality "=0" of an affine expression such that the entry at column
457 * "row" (="level") is not zero. This matrix is upper-triangular, except the
458 * row number "level-1" which has to be updated for the matrix to be triangular.
459 * This function achieves the processing.
460 * - equal is the matrix to be updated,
461 * - level gives the row that has to be updated (it is actually row "level-1"),
462 * - nb_par is the number of parameters of the program.
464 * - September 20th 2005: first version.
466 static void cloog_equal_update(CloogEqualities
*equal
, int level
, int nb_par
)
468 Value gcd
, factor_level
, factor_outer
, temp_level
, temp_outer
;
471 value_init(temp_level
);
472 value_init(temp_outer
);
473 value_init(factor_level
);
474 value_init(factor_outer
);
476 /* For each previous level, */
477 for (i
=level
-2;i
>=0;i
--)
478 { /* if the corresponding iterator is inside the current equality and is equal
481 if (value_notzero_p(equal
->constraints
->p
[level
-1][i
+1]) && equal
->types
[i
])
482 { /* Compute the Greatest Common Divisor. */
483 Gcd(equal
->constraints
->p
[level
-1][i
+1],
484 equal
->constraints
->p
[i
][i
+1], &gcd
);
486 /* Compute the factors to apply to each row vector element. */
487 value_division(factor_level
, equal
->constraints
->p
[i
][i
+1], gcd
);
488 value_division(factor_outer
, equal
->constraints
->p
[level
-1][i
+1], gcd
);
490 /* Now update the row 'level'. */
491 /* - the iterators, up to level, */
492 for (j
=1;j
<=level
;j
++)
493 { value_multiply(temp_level
, factor_level
,
494 equal
->constraints
->p
[level
-1][j
]);
495 value_multiply(temp_outer
, factor_outer
, equal
->constraints
->p
[i
][j
]);
496 value_substract(equal
->constraints
->p
[level
-1][j
], temp_level
, temp_outer
);
498 /* - between last useful iterator (level) and the first parameter, the
499 * matrix is sparse (full of zeroes), we just do nothing there.
500 * - the parameters and the scalar.
502 for (j
=0;j
<nb_par
+1;j
++)
503 { value_multiply(temp_level
,factor_level
,
504 equal
->constraints
->p
[level
-1]
505 [equal
->constraints
->NbColumns
-j
-1]);
506 value_multiply(temp_outer
,factor_outer
,
507 equal
->constraints
->p
[i
][equal
->constraints
->NbColumns
-j
-1]);
508 value_substract(equal
->constraints
->p
[level
-1]
509 [equal
->constraints
->NbColumns
-j
-1],
510 temp_level
,temp_outer
) ;
515 /* Normalize (divide by GCD of all elements) the updated equality. */
516 Vector_Normalize(&(equal
->constraints
->p
[level
-1][1]),
517 equal
->constraints
->NbColumns
-1);
520 value_clear(temp_level
);
521 value_clear(temp_outer
);
522 value_clear(factor_level
);
523 value_clear(factor_outer
);
528 * cloog_equal_add function:
529 * This function updates the row (level-1) of the equality matrix (equal) with
530 * the row that corresponds to the row (line) of the matrix (matrix).
531 * - equal is the matrix of equalities,
532 * - matrix is the matrix of constraints,
533 * - level is the column number in matrix of the element which is 'equal to',
534 * - line is the line number in matrix of the constraint we want to study,
535 * - the infos structure gives the user all options on code printing and more.
537 * - July 2nd 2002: first version.
538 * - October 19th 2005: Addition of the once-time-loop specific processing.
540 void cloog_equal_add(CloogEqualities
*equal
, CloogConstraintSet
*matrix
,
541 int level
, CloogConstraint line
, int nb_par
)
545 Value numerator
, denominator
, division
, modulo
;
547 /* If we are in the case of a loop running once, this means that the equality
548 * comes from an inequality. Here we find this inequality.
550 if (!cloog_constraint_is_valid(line
))
551 { for (i
= cloog_constraint_first(matrix
);
552 cloog_constraint_is_valid(i
); i
= cloog_constraint_next(i
))
553 if ((value_notzero_p(i
.line
[0][0]))&& (value_notzero_p(i
.line
[0][level
])))
556 /* Since in once-time-loops, equalities derive from inequalities, we
557 * may have to offset the values. For instance if we have 2i>=3, the
558 * equality is in fact i=2. This may happen when the level coefficient is
559 * not 1 or -1 and the scalar value is not zero. In any other case (e.g.,
560 * if the inequality is an expression including outer loop counters or
561 * parameters) the once time loop would not have been detected
562 * because of floord and ceild functions.
564 if (value_ne_si(i
.line
[0][level
],1) &&
565 value_ne_si(i
.line
[0][level
],-1) &&
566 value_notzero_p(i
.line
[0][matrix
->NbColumns
-1])) {
567 value_init(numerator
);
568 value_init(denominator
);
569 value_init(division
);
572 value_assign(denominator
,i
.line
[0][level
]) ;
573 value_absolute(denominator
,denominator
) ;
574 value_assign(numerator
,i
.line
[0][matrix
->NbColumns
-1]) ;
575 value_modulus(modulo
,numerator
,denominator
) ;
576 value_division(division
,numerator
,denominator
) ;
578 /* There are 4 scenarios:
579 * di +n >= 0 --> i + (n div d) >= 0
580 * -di +n >= 0 --> -i + (n div d) >= 0
581 * di -n >= 0 --> if (n%d == 0) i + ((-n div d)+1) >= 0
582 * else i + (-n div d) >= 0
583 * -di -n >= 0 --> if (n%d == 0) -i + ((-n div d)-1) >= 0
584 * else -i + (-n div d) >= 0
585 * In the following we distinct the scalar value setting and the
588 if (value_pos_p(numerator
) || value_zero_p(modulo
))
589 value_assign(i
.line
[0][matrix
->NbColumns
-1],division
) ;
591 { if (value_pos_p(i
.line
[0][level
]))
592 value_increment(i
.line
[0][matrix
->NbColumns
-1],division
) ;
594 value_decrement(i
.line
[0][matrix
->NbColumns
-1],division
) ;
597 if (value_pos_p(i
.line
[0][level
]))
598 value_set_si(i
.line
[0][level
],1) ;
600 value_set_si(i
.line
[0][level
],-1) ;
602 value_clear(numerator
);
603 value_clear(denominator
);
604 value_clear(division
);
611 assert(cloog_constraint_is_valid(line
));
613 /* We update the line of equal corresponding to level:
614 * - the first element gives the equality type,
616 equal
->types
[level
-1] = cloog_constraint_equal_type(line
, level
);
617 /* - the other elements corresponding to the equality itself
618 * (the iterators up to level, then the parameters and the scalar).
620 for (j
=1;j
<=level
;j
++)
621 value_assign(equal
->constraints
->p
[level
-1][j
], line
.line
[0][j
]);
622 for (j
= 0; j
< nb_par
+ 1; j
++)
623 value_assign(equal
->constraints
->p
[level
-1][equal
->constraints
->NbColumns
-j
-1],
624 line
.line
[0][line
.set
->NbColumns
-j
-1]);
626 cloog_equal_update(equal
, level
, nb_par
);
631 * cloog_equal_del function :
632 * This function reset the equality corresponding to the iterator (level)
633 * in the equality matrix (equal).
634 * - July 2nd 2002: first version.
636 void cloog_equal_del(CloogEqualities
*equal
, int level
)
638 equal
->types
[level
-1] = EQTYPE_NONE
;
643 /******************************************************************************
644 * Processing functions *
645 ******************************************************************************/
648 * Function cloog_constraint_set_normalize:
649 * This function will modify the constraint system in such a way that when
650 * there is an equality depending on the element at level 'level', there are
651 * no more (in)equalities depending on this element. For instance, try
652 * test/valilache.cloog with options -f 8 -l 9, with and without the call
653 * to this function. At a given moment, for the level L we will have
654 * 32*P=L && L>=1 (P is a lower level), this constraint system cannot be
655 * translated directly into a source code. Thus, we normalize the domain to
656 * remove L from the inequalities. In our example, this leads to
657 * 32*P=L && 32*P>=1, that can be transated to the code
658 * if (P>=1) { L=32*P ; ... }. This function solves the DaeGon Kim bug.
659 * WARNING: Remember that if there is another call to Polylib after a call to
660 * this function, we have to recall this function.
661 * -June 16th 2005: first version (adaptation from URGent June-7th-2005 by
663 * - June 21rd 2005: Adaptation for GMP.
664 * - November 4th 2005: Complete rewriting, simpler and faster. It is no more an
665 * adaptation from URGent.
667 void cloog_constraint_set_normalize(CloogConstraintSet
*matrix
, int level
)
669 Value factor_i
, factor_ref
, temp_i
, temp_ref
, gcd
;
674 /* Don't "normalize" the constant term. */
675 if (level
== matrix
->NbColumns
-1)
678 /* Let us find an equality for the current level that can be propagated. */
679 for (ref
=0;ref
<matrix
->NbRows
;ref
++)
680 if (value_zero_p(matrix
->p
[ref
][0]) && value_notzero_p(matrix
->p
[ref
][level
]))
683 value_init(temp_ref
);
684 value_init(factor_i
);
685 value_init(factor_ref
);
687 /* Row "ref" is the reference equality, now let us find a row to simplify.*/
688 for (i
=ref
+1;i
<matrix
->NbRows
;i
++)
689 if (value_notzero_p(matrix
->p
[i
][level
]))
690 { /* Now let us set to 0 the "level" coefficient of row "j" using "ref".
691 * First we compute the factors to apply to each row vector element.
693 Gcd(matrix
->p
[ref
][level
],matrix
->p
[i
][level
],&gcd
) ;
694 value_division(factor_i
,matrix
->p
[ref
][level
],gcd
) ;
695 value_division(factor_ref
,matrix
->p
[i
][level
],gcd
) ;
697 /* Maybe we are simplifying an inequality: factor_i must not be <0. */
698 if (value_neg_p(factor_i
))
699 { value_absolute(factor_i
,factor_i
) ;
700 value_oppose(factor_ref
,factor_ref
) ;
703 /* Now update the vector. */
704 for (j
=1;j
<matrix
->NbColumns
;j
++)
705 { value_multiply(temp_i
,factor_i
,matrix
->p
[i
][j
]) ;
706 value_multiply(temp_ref
,factor_ref
,matrix
->p
[ref
][j
]) ;
707 value_substract(matrix
->p
[i
][j
],temp_i
,temp_ref
) ;
710 /* Normalize (divide by GCD of all elements) the updated vector. */
711 Vector_Normalize(&(matrix
->p
[i
][1]),matrix
->NbColumns
-1) ;
716 value_clear(temp_ref
);
717 value_clear(factor_i
);
718 value_clear(factor_ref
);
726 * cloog_constraint_set_copy function:
727 * this functions builds and returns a "hard copy" (not a pointer copy) of a
728 * Matrix data structure.
729 * - October 26th 2005: first version.
731 CloogConstraintSet
*cloog_constraint_set_copy(CloogConstraintSet
*matrix
)
735 copy
= cloog_matrix_alloc(matrix
->NbRows
,matrix
->NbColumns
) ;
737 for (i
=0;i
<matrix
->NbRows
;i
++)
738 for (j
=0;j
<matrix
->NbColumns
;j
++)
739 value_assign(copy
->p
[i
][j
],matrix
->p
[i
][j
]) ;
746 * cloog_matrix_vector_copy function:
747 * this function rutuns a hard copy of the vector "vector" of length "length"
749 * - November 3rd 2005: first version.
751 static Value
*cloog_matrix_vector_copy(Value
*vector
, int length
)
755 /* We allocate the memory space for the new vector, and we fill it with
756 * the original coefficients.
758 copy
= (Value
*)malloc(length
* sizeof(Value
)) ;
759 for (i
=0;i
<length
;i
++) {
761 value_assign(copy
[i
],vector
[i
]);
769 * cloog_matrix_vector_free function:
770 * this function clears the elements of a vector "vector" of length "length",
771 * then frees the vector itself this is useful for the GMP version of CLooG
772 * which has to clear all elements.
773 * - October 29th 2005: first version.
775 static void cloog_matrix_vector_free(Value
* vector
, int length
)
778 for (i
=0;i
<length
;i
++)
779 value_clear(vector
[i
]);
785 * cloog_equal_vector_simplify function:
786 * this function simplify an affine expression with its coefficients in
787 * "vector" of length "length" thanks to an equality matrix "equal" that gives
788 * for some elements of the affine expression an equality with other elements,
789 * preferably constants. For instance, if the vector contains i+j+3 and the
790 * equality matrix gives i=n and j=2, the vector is simplified to n+3 and is
791 * returned in a new vector.
792 * - vector is the array of affine expression coefficients
793 * - equal is the matrix of equalities,
794 * - length is the vector length,
795 * - level is a level we don't want to simplify (-1 if none),
796 * - nb_par is the number of parameters of the program.
798 * - September 20th 2005: first version.
799 * - November 2nd 2005: (debug) we are simplifying inequalities, thus we are
800 * not allowed to multiply the vector by a negative
801 * constant.Problem found after a report of Michael
804 Value
*cloog_equal_vector_simplify(CloogEqualities
*equal
, Value
*vector
,
805 int length
, int level
, int nb_par
)
807 Value gcd
, factor_vector
, factor_equal
, temp_vector
, temp_equal
, * simplified
;
809 simplified
= cloog_matrix_vector_copy(vector
,length
) ;
812 value_init(temp_vector
);
813 value_init(temp_equal
);
814 value_init(factor_vector
);
815 value_init(factor_equal
);
817 /* For each non-null coefficient in the vector, */
818 for (i
=length
-nb_par
-2;i
>0;i
--)
820 { /* if the coefficient in not null, and there exists a useful equality */
821 if ((value_notzero_p(simplified
[i
])) && equal
->types
[i
-1])
822 { /* Compute the Greatest Common Divisor. */
823 Gcd(simplified
[i
], equal
->constraints
->p
[i
-1][i
], &gcd
);
825 /* Compute the factors to apply to each row vector element. */
826 value_division(factor_vector
, equal
->constraints
->p
[i
-1][i
], gcd
);
827 value_division(factor_equal
,simplified
[i
],gcd
) ;
829 /* We are simplifying an inequality: factor_vector must not be <0. */
830 if (value_neg_p(factor_vector
))
831 { value_absolute(factor_vector
,factor_vector
) ;
832 value_oppose(factor_equal
,factor_equal
) ;
835 /* Now update the vector. */
836 /* - the iterators, up to the current level, */
837 for (j
=1;j
<=length
-nb_par
-2;j
++)
838 { value_multiply(temp_vector
,factor_vector
,simplified
[j
]) ;
839 value_multiply(temp_equal
, factor_equal
, equal
->constraints
->p
[i
-1][j
]);
840 value_substract(simplified
[j
],temp_vector
,temp_equal
) ;
842 /* - between last useful iterator (i) and the first parameter, the equal
843 * matrix is sparse (full of zeroes), we just do nothing there.
844 * - the parameters and the scalar.
846 for (j
=0;j
<nb_par
+1;j
++)
847 { value_multiply(temp_vector
,factor_vector
,simplified
[length
-1-j
]) ;
848 value_multiply(temp_equal
,factor_equal
,
849 equal
->constraints
->p
[i
-1][equal
->constraints
->NbColumns
-j
-1]);
850 value_substract(simplified
[length
-1-j
],temp_vector
,temp_equal
) ;
855 /* Normalize (divide by GCD of all elements) the updated vector. */
856 Vector_Normalize(&(simplified
[1]),length
-1) ;
859 value_clear(temp_vector
);
860 value_clear(temp_equal
);
861 value_clear(factor_vector
);
862 value_clear(factor_equal
);
869 * cloog_constraint_set_simplify function:
870 * this function simplify all constraints inside the matrix "matrix" thanks to
871 * an equality matrix "equal" that gives for some elements of the affine
872 * constraint an equality with other elements, preferably constants.
873 * For instance, if a row of the matrix contains i+j+3>=0 and the equality
874 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
875 * simplified constraints are returned back inside a new simplified matrix.
876 * - matrix is the set of constraints to simplify,
877 * - equal is the matrix of equalities,
878 * - level is a level we don't want to simplify (-1 if none),
879 * - nb_par is the number of parameters of the program.
881 * - November 4th 2005: first version.
883 CloogConstraintSet
*cloog_constraint_set_simplify(CloogConstraintSet
*matrix
,
884 CloogEqualities
*equal
, int level
, int nb_par
)
887 Matrix
* simplified
;
892 /* The simplified matrix is such that each row has been simplified thanks
893 * tho the "equal" matrix. We allocate the memory for the simplified matrix,
894 * then for each row of the original matrix, we compute the simplified
895 * vector and we copy its content into the according simplified row.
897 simplified
= cloog_matrix_alloc(matrix
->NbRows
,matrix
->NbColumns
) ;
898 for (i
=0;i
<matrix
->NbRows
;i
++)
899 { vector
= cloog_equal_vector_simplify(equal
, matrix
->p
[i
],
900 matrix
->NbColumns
, level
, nb_par
);
901 for (j
=0;j
<matrix
->NbColumns
;j
++)
902 value_assign(simplified
->p
[i
][j
],vector
[j
]) ;
904 cloog_matrix_vector_free(vector
,matrix
->NbColumns
) ;
907 /* After simplification, it may happen that few constraints are the same,
908 * we remove them here by replacing them with 0=0 constraints.
910 for (i
=0;i
<simplified
->NbRows
;i
++)
911 for (j
=i
+1;j
<simplified
->NbRows
;j
++)
912 { for (k
=0;k
<simplified
->NbColumns
;k
++)
913 if (value_ne(simplified
->p
[i
][k
],simplified
->p
[j
][k
]))
916 if (k
== matrix
->NbColumns
)
917 { for (k
=0;k
<matrix
->NbColumns
;k
++)
918 value_set_si(simplified
->p
[j
][k
],0) ;
927 * Return clast_expr corresponding to the variable "level" (1 based) in
928 * the given constraint.
930 struct clast_expr
*cloog_constraint_variable_expr(CloogConstraint constraint
,
931 int level
, CloogNames
*names
)
933 int total_dim
, nb_iter
;
936 total_dim
= cloog_constraint_total_dimension(constraint
);
937 nb_iter
= total_dim
- names
->nb_parameters
;
939 if (level
<= nb_iter
)
940 name
= cloog_names_name_at_level(names
, level
);
942 name
= names
->parameters
[level
- (nb_iter
+1)] ;
944 return &new_clast_name(name
)->expr
;
949 * Return true if constraint c involves variable v (zero-based).
951 int cloog_constraint_involves(CloogConstraint constraint
, int v
)
953 return value_notzero_p(constraint
.line
[0][1+v
]);
956 int cloog_constraint_is_lower_bound(CloogConstraint constraint
, int v
)
958 return value_pos_p(constraint
.line
[0][1+v
]);
961 int cloog_constraint_is_upper_bound(CloogConstraint constraint
, int v
)
963 return value_neg_p(constraint
.line
[0][1+v
]);
966 int cloog_constraint_is_equality(CloogConstraint constraint
)
968 return value_zero_p(constraint
.line
[0][0]);
971 void cloog_constraint_clear(CloogConstraint constraint
)
975 for (k
= 1; k
<= constraint
.set
->NbColumns
- 2; k
++)
976 value_set_si(constraint
.line
[0][k
], 0);
979 void cloog_constraint_coefficient_get(CloogConstraint constraint
,
982 value_assign(*val
, constraint
.line
[0][1+var
]);
985 void cloog_constraint_coefficient_set(CloogConstraint constraint
,
988 value_assign(constraint
.line
[0][1+var
], val
);
991 void cloog_constraint_constant_get(CloogConstraint constraint
, cloog_int_t
*val
)
993 value_assign(*val
, constraint
.line
[0][constraint
.set
->NbColumns
-1]);
997 * Copy the coefficient of constraint c into dst in PolyLib order,
998 * i.e., first the coefficients of the variables, then the coefficients
999 * of the parameters and finally the constant.
1001 void cloog_constraint_copy_coefficients(CloogConstraint constraint
,
1004 Vector_Copy(constraint
.line
[0]+1, dst
, constraint
.set
->NbColumns
-1);
1007 CloogConstraint
cloog_constraint_invalid(void)
1015 int cloog_constraint_is_valid(CloogConstraint constraint
)
1017 return constraint
.set
!= NULL
&& constraint
.line
!= NULL
;
1021 * Create a CloogConstraintSet containing enough information to perform
1022 * a reduction on the upper equality (in this case lower is an invalid
1023 * CloogConstraint) or the pair of inequalities upper and lower
1024 * from within insert_modulo_guard.
1025 * In the PolyLib backend, we return a CloogConstraintSet containting only
1026 * the upper bound. The reduction will not change the stride so there
1027 * will be no need to recompute the bound on the modulo expression.
1029 CloogConstraintSet
*cloog_constraint_set_for_reduction(CloogConstraint upper
,
1030 CloogConstraint lower
)
1032 CloogConstraintSet
*set
;
1034 set
= cloog_matrix_alloc(1, upper
.set
->NbColumns
);
1035 Vector_Copy(upper
.line
[0], set
->p
[0], set
->NbColumns
);
1040 /* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
1041 static void Euclid(cloog_int_t a
, cloog_int_t b
,
1042 cloog_int_t
*x
, cloog_int_t
*y
, cloog_int_t
*g
)
1044 cloog_int_t c
, d
, e
, f
, tmp
;
1050 cloog_int_init(tmp
);
1051 cloog_int_abs(c
, a
);
1052 cloog_int_abs(d
, b
);
1053 cloog_int_set_si(e
, 1);
1054 cloog_int_set_si(f
, 0);
1055 while (cloog_int_is_pos(d
)) {
1056 cloog_int_tdiv_q(tmp
, c
, d
);
1057 cloog_int_mul(tmp
, tmp
, f
);
1058 cloog_int_sub(e
, e
, tmp
);
1059 cloog_int_tdiv_q(tmp
, c
, d
);
1060 cloog_int_mul(tmp
, tmp
, d
);
1061 cloog_int_sub(c
, c
, tmp
);
1062 cloog_int_swap(c
, d
);
1063 cloog_int_swap(e
, f
);
1065 cloog_int_set(*g
, c
);
1066 if (cloog_int_is_zero(a
))
1067 cloog_int_set_si(*x
, 0);
1068 else if (cloog_int_is_pos(a
))
1069 cloog_int_set(*x
, e
);
1070 else cloog_int_neg(*x
, e
);
1071 if (cloog_int_is_zero(b
))
1072 cloog_int_set_si(*y
, 0);
1074 cloog_int_mul(tmp
, a
, *x
);
1075 cloog_int_sub(tmp
, c
, tmp
);
1076 cloog_int_divexact(*y
, tmp
, b
);
1082 cloog_int_clear(tmp
);
1086 * Reduce the modulo guard expressed by "contraints" using equalities
1087 * found in outer nesting levels (stored in "equal").
1088 * The modulo guard may be an equality or a pair of inequalities.
1089 * In case of a pair of inequalities, "constraints" only contains the
1090 * upper bound and *bound contains the bound on the
1091 * corresponding modulo expression. The bound is left untouched by
1094 CloogConstraintSet
*cloog_constraint_set_reduce(CloogConstraintSet
*constraints
,
1095 int level
, CloogEqualities
*equal
, int nb_par
, cloog_int_t
*bound
)
1097 int i
, j
, k
, len
, len2
, nb_iter
;
1098 struct cloog_vec
*line_vector2
;
1099 cloog_int_t
*line
, *line2
, val
, x
, y
, g
;
1101 len
= constraints
->NbColumns
;
1102 len2
= cloog_equal_total_dimension(equal
) + 2;
1103 nb_iter
= len
- 2 - nb_par
;
1105 cloog_int_init(val
);
1110 line_vector2
= cloog_vec_alloc(len2
);
1111 line2
= line_vector2
->p
;
1113 line
= constraints
->p
[0];
1114 if (cloog_int_is_pos(line
[level
]))
1115 cloog_seq_neg(line
+1, line
+1, len
-1);
1116 cloog_int_neg(line
[level
], line
[level
]);
1117 assert(cloog_int_is_pos(line
[level
]));
1119 for (i
= nb_iter
; i
>= 1; --i
) {
1122 cloog_int_fdiv_r(line
[i
], line
[i
], line
[level
]);
1123 if (cloog_int_is_zero(line
[i
]))
1126 /* Look for an earlier variable that is also a multiple of line[level]
1127 * and check whether we can use the corresponding affine expression
1128 * to "reduce" the modulo guard, where reduction means that we eliminate
1129 * a variable, possibly at the expense of introducing other variables
1130 * with smaller index.
1132 for (j
= level
-1; j
>= 0; --j
) {
1133 CloogConstraint equal_constraint
;
1134 if (cloog_equal_type(equal
, j
+1) != EQTYPE_EXAFFINE
)
1136 equal_constraint
= cloog_equal_constraint(equal
, j
);
1137 cloog_constraint_coefficient_get(equal_constraint
, j
, &val
);
1138 if (!cloog_int_is_divisible_by(val
, line
[level
])) {
1139 cloog_constraint_release(equal_constraint
);
1142 cloog_constraint_coefficient_get(equal_constraint
, i
-1, &val
);
1143 if (cloog_int_is_divisible_by(val
, line
[level
])) {
1144 cloog_constraint_release(equal_constraint
);
1147 for (k
= j
; k
> i
; --k
) {
1148 cloog_constraint_coefficient_get(equal_constraint
, k
-1, &val
);
1149 if (cloog_int_is_zero(val
))
1151 if (!cloog_int_is_divisible_by(val
, line
[level
]))
1155 cloog_constraint_release(equal_constraint
);
1158 cloog_constraint_coefficient_get(equal_constraint
, i
-1, &val
);
1159 Euclid(val
, line
[level
], &x
, &y
, &g
);
1160 if (!cloog_int_is_divisible_by(val
, line
[i
])) {
1161 cloog_constraint_release(equal_constraint
);
1164 cloog_int_divexact(val
, line
[i
], g
);
1165 cloog_int_neg(val
, val
);
1166 cloog_int_mul(val
, val
, x
);
1167 cloog_int_set_si(y
, 1);
1168 /* Add (equal->p[j][i])^{-1} * line[i] times the equality */
1169 cloog_constraint_copy_coefficients(equal_constraint
, line2
+1);
1170 cloog_seq_combine(line
+1, y
, line
+1, val
, line2
+1, i
);
1171 cloog_seq_combine(line
+len
-nb_par
-1, y
, line
+len
-nb_par
-1,
1172 val
, line2
+len2
-nb_par
-1, nb_par
+1);
1173 cloog_constraint_release(equal_constraint
);
1178 cloog_vec_free(line_vector2
);
1180 cloog_int_clear(val
);
1185 /* Make sure the line is not inverted again in the calling function. */
1186 cloog_int_neg(line
[level
], line
[level
]);
1191 CloogConstraint
cloog_constraint_first(CloogConstraintSet
*constraints
)
1194 if (constraints
->NbRows
== 0)
1195 return cloog_constraint_invalid();
1196 c
.set
= constraints
;
1197 c
.line
= &constraints
->p
[0];
1201 CloogConstraint
cloog_constraint_next(CloogConstraint constraint
)
1203 CloogConstraint c
= constraint
;
1205 if (c
.line
== c
.set
->p
+ c
.set
->NbRows
) {
1212 CloogConstraint
cloog_constraint_copy(CloogConstraint constraint
)
1217 void cloog_constraint_release(CloogConstraint constraint
)
1221 CloogConstraint
cloog_equal_constraint(CloogEqualities
*equal
, int j
)
1224 c
.set
= equal
->constraints
;
1225 c
.line
= &equal
->constraints
->p
[j
];