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/cloog.h"
48 /******************************************************************************
49 * Memory leaks hunting *
50 ******************************************************************************/
54 * These functions and global variables are devoted to memory leaks hunting: we
55 * want to know at each moment how many CloogMatrix structures are allocated
56 * (cloog_matrix_allocated) and how many had been freed (cloog_matrix_freed).
58 * variable cloog_matrix_max gives the maximal number of CloogMatrix structures
59 * simultaneously alive (i.e. allocated and non-freed) in memory.
60 * - April 17th 2005: first version.
64 int cloog_matrix_allocated
= 0 ;
65 int cloog_matrix_freed
= 0 ;
66 int cloog_matrix_max
= 0 ;
69 /******************************************************************************
71 ******************************************************************************/
75 * CLooG makes an intensive use of matrix operations and the PolyLib do
76 * the job. Here are the interfaces to all the PolyLib calls (CLooG uses 18
77 * PolyLib functions), with or without some adaptations. If another matrix
78 * library can be used, only these functions have to be changed.
83 * cloog_matrix_print function:
84 * This function prints the content of a CloogMatrix structure (matrix) into a
85 * file (foo, possibly stdout).
87 void cloog_matrix_print(FILE * foo
, CloogMatrix
* matrix
)
91 int NbRows
= matrix
->NbRows
;
92 int NbColumns
= matrix
->NbColumns
;
94 fprintf (foo
, "%d %d\n", NbRows
, NbColumns
);
101 for (i
= 0; i
< NbRows
; i
++)
103 p
= *(matrix
->p
+ i
);
105 for (j
= 0; j
< NbColumns
; j
++)
106 value_print (foo
, " " "%4s " " ", *p
++);
114 * cloog_matrix_free function:
115 * This function frees the allocated memory for a CloogMatrix structure
119 cloog_matrix_free (CloogMatrix
* m
)
132 n
= cloog_matrix_nrows (m
) * cloog_matrix_ncolumns (m
);
134 for (i
= 0; i
< n
; i
++)
135 value_clear (m
->p
[0][i
]);
143 * cloog_matrix_alloc function:
144 * This function allocates the memory space for a CloogMatrix structure having
145 * nb_rows rows and nb_columns columns, it set its elements to 0.
148 cloog_matrix_alloc (unsigned nb_rows
, unsigned nb_columns
)
151 CloogMatrix
*res
= (CloogMatrix
*) malloc (sizeof (struct cloog_matrix
));
153 res
->NbRows
= nb_rows
;
154 res
->NbColumns
= nb_columns
;
156 if (nb_rows
== 0 || nb_columns
== 0)
157 res
->p
= (Value
**) 0;
161 int n
= nb_rows
* nb_columns
;
162 Value
*p
= (Value
*) malloc (n
* sizeof (Value
));
163 res
->p
= (Value
**) malloc (nb_rows
* sizeof (Value
*));
165 for (i
= 0; i
< n
; ++i
)
168 for (i
= 0; i
< (int) nb_rows
; i
++, p
+= nb_columns
)
176 /******************************************************************************
177 * Structure display function *
178 ******************************************************************************/
182 * cloog_loop_print_structure function:
183 * Displays a CloogMatrix structure (matrix) into a file (file, possibly stdout)
184 * in a way that trends to be understandable without falling in a deep
185 * depression or, for the lucky ones, getting a headache... It includes an
186 * indentation level (level) in order to work with others print_structure
187 * functions. Written by Olivier Chorier, Luc Marchaud, Pierre Martin and
189 * - April 24th 2005: Initial version.
190 * - June 2nd 2005: (Ced) Extraction from cloog_loop_print_structure and
191 * integration in matrix.c.
192 * - June 22rd 2005: Adaptation for GMP.
194 void cloog_matrix_print_structure(FILE * file
, CloogMatrix
* matrix
, int level
)
197 /* Display the matrix. */
198 for (i
=0; i
<matrix
->NbRows
; i
++)
199 { for(j
=0; j
<=level
; j
++)
200 fprintf(file
,"|\t") ;
204 for (j
=0; j
<matrix
->NbColumns
; j
++)
205 { value_print(file
,VALUE_FMT
,matrix
->p
[i
][j
]) ;
209 fprintf(file
,"]\n") ;
214 /******************************************************************************
216 ******************************************************************************/
220 * cloog_matrix_read function:
221 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
222 * posibly stdin) and returns a pointer this matrix.
223 * October 18th 2001: first version.
224 * - April 17th 2005: this function moved from domain.c to here.
225 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
228 CloogMatrix
* cloog_matrix_read(FILE * foo
)
229 { unsigned NbRows
, NbColumns
;
231 char *c
, s
[MAX_STRING
], str
[MAX_STRING
] ;
232 CloogMatrix
* matrix
;
235 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
236 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %u %u",&NbRows
,&NbColumns
)<2))
237 fgets(s
,MAX_STRING
,foo
) ;
239 matrix
= cloog_matrix_alloc(NbRows
,NbColumns
) ;
245 for (i
=0;i
<matrix
->NbRows
;i
++)
247 { c
= fgets(s
,MAX_STRING
,foo
) ;
248 while ((c
!= NULL
) && isspace(*c
) && (*c
!= '\n'))
251 while (c
!= NULL
&& (*c
== '#' || *c
== '\n'));
254 { fprintf(stderr
, "[CLooG]ERROR: not enough rows.\n") ;
257 for (j
=0;j
<matrix
->NbColumns
;j
++)
258 { if (c
== NULL
|| *c
== '#' || *c
== '\n')
259 { fprintf(stderr
, "[CLooG]ERROR: not enough columns.\n") ;
262 /* NdCed : Dans le n ca met strlen(str). */
263 if (sscanf(c
,"%s%n",str
,&n
) == 0)
264 { fprintf(stderr
, "[CLooG]ERROR: not enough rows.\n") ;
267 value_read(*(p
++),str
) ;
276 /******************************************************************************
277 * Processing functions *
278 ******************************************************************************/
282 * Function cloog_matrix_normalize:
283 * This function will modify the constraint system in such a way that when
284 * there is an equality depending on the element at level 'level', there are
285 * no more (in)equalities depending on this element. For instance, try
286 * test/valilache.cloog with options -f 8 -l 9, with and without the call
287 * to this function. At a given moment, for the level L we will have
288 * 32*P=L && L>=1 (P is a lower level), this constraint system cannot be
289 * translated directly into a source code. Thus, we normalize the domain to
290 * remove L from the inequalities. In our example, this leads to
291 * 32*P=L && 32*P>=1, that can be transated to the code
292 * if (P>=1) { L=32*P ; ... }. This function solves the DaeGon Kim bug.
293 * WARNING: Remember that if there is another call to Polylib after a call to
294 * this function, we have to recall this function.
295 * -June 16th 2005: first version (adaptation from URGent June-7th-2005 by
297 * - June 21rd 2005: Adaptation for GMP.
298 * - November 4th 2005: Complete rewriting, simpler and faster. It is no more an
299 * adaptation from URGent.
301 void cloog_matrix_normalize(CloogMatrix
* matrix
, int level
)
303 Value factor_i
, factor_ref
, temp_i
, temp_ref
, gcd
;
308 /* Don't "normalize" the constant term. */
309 if (level
== matrix
->NbColumns
-1)
312 /* Let us find an equality for the current level that can be propagated. */
313 for (ref
=0;ref
<matrix
->NbRows
;ref
++)
314 if (value_zero_p(matrix
->p
[ref
][0])
315 && value_notzero_p(matrix
->p
[ref
][level
]))
316 { value_init_c(gcd
) ;
317 value_init_c(temp_i
) ;
318 value_init_c(temp_ref
) ;
319 value_init_c(factor_i
) ;
320 value_init_c(factor_ref
) ;
322 /* Row "ref" is the reference equality, now let us find a row to simplify.*/
323 for (i
=ref
+1;i
<matrix
->NbRows
;i
++)
324 if (value_notzero_p(matrix
->p
[i
][level
]))
325 { /* Now let us set to 0 the "level" coefficient of row "j" using "ref".
326 * First we compute the factors to apply to each row vector element.
328 Gcd(matrix
->p
[ref
][level
], matrix
->p
[i
][level
], &gcd
) ;
329 value_division(factor_i
,matrix
->p
[ref
][level
],gcd
) ;
330 value_division(factor_ref
,matrix
->p
[i
][level
],gcd
) ;
332 /* Maybe we are simplifying an inequality: factor_i must not be <0. */
333 if (value_neg_p(factor_i
))
334 { value_absolute(factor_i
,factor_i
) ;
335 value_oppose(factor_ref
,factor_ref
) ;
338 /* Now update the vector. */
339 for (j
=1;j
<matrix
->NbColumns
;j
++)
340 { value_multiply(temp_i
,factor_i
,matrix
->p
[i
][j
]) ;
341 value_multiply(temp_ref
,factor_ref
,matrix
->p
[ref
][j
]) ;
342 value_substract(matrix
->p
[i
][j
], temp_i
, temp_ref
) ;
345 /* Normalize (divide by GCD of all elements) the updated vector. */
346 cloog_vector_normalize(&(matrix
->p
[i
][1]),matrix
->NbColumns
-1) ;
350 value_clear_c(temp_i
) ;
351 value_clear_c(temp_ref
) ;
352 value_clear_c(factor_i
) ;
353 value_clear_c(factor_ref
) ;
360 * cloog_matrix_equality_update function:
361 * this function updates a matrix of equalities where each row corresponds to
362 * the equality "=0" of an affine expression such that the entry at column
363 * "row" (="level") is not zero. This matrix is upper-triangular, except the
364 * row number "level-1" which has to be updated for the matrix to be triangular.
365 * The first element of each row gives the equality type and is not related to
366 * the expression which is equal to zero. This function achieves the processing.
367 * - equal is the matrix to be updated,
368 * - level gives the row that has to be updated (it is actually row "level-1"),
369 * - nb_par is the number of parameters of the program.
371 * - September 20th 2005: first version.
373 void cloog_matrix_equality_update(CloogMatrix
* equal
, int level
, int nb_par
)
375 Value gcd
, factor_level
, factor_outer
, temp_level
, temp_outer
;
378 value_init_c(temp_level
) ;
379 value_init_c(temp_outer
) ;
380 value_init_c(factor_level
) ;
381 value_init_c(factor_outer
) ;
383 /* For each previous level, */
384 for (i
=level
-2;i
>=0;i
--)
385 { /* if the corresponding iterator is inside the current equality and is equal
388 if (value_notzero_p(equal
->p
[level
-1][i
+1]) &&
389 value_notzero_p(equal
->p
[i
][0]))
390 { /* Compute the Greatest Common Divisor. */
391 Gcd(equal
->p
[level
-1][i
+1],equal
->p
[i
][i
+1],&gcd
) ;
393 /* Compute the factors to apply to each row vector element. */
394 value_division(factor_level
,equal
->p
[i
][i
+1],gcd
) ;
395 value_division(factor_outer
,equal
->p
[level
-1][i
+1],gcd
) ;
397 /* Now update the row 'level'. */
398 /* - the iterators, up to level, */
399 for (j
=1;j
<=level
;j
++)
400 { value_multiply(temp_level
,factor_level
,equal
->p
[level
-1][j
]) ;
401 value_multiply(temp_outer
,factor_outer
,equal
->p
[i
][j
]) ;
402 value_substract(equal
->p
[level
-1][j
], temp_level
, temp_outer
) ;
404 /* - between last useful iterator (level) and the first parameter, the
405 * matrix is sparse (full of zeroes), we just do nothing there.
406 * - the parameters and the scalar.
408 for (j
=0;j
<nb_par
+1;j
++)
409 { value_multiply(temp_level
,factor_level
,
410 equal
->p
[level
-1][equal
->NbColumns
-j
-1]) ;
411 value_multiply(temp_outer
,factor_outer
,
412 equal
->p
[i
][equal
->NbColumns
-j
-1]) ;
413 value_substract(equal
->p
[level
-1][equal
->NbColumns
-j
-1],
414 temp_level
, temp_outer
) ;
419 /* Normalize (divide by GCD of all elements) the updated equality. */
420 cloog_vector_normalize(&(equal
->p
[level
-1][1]),equal
->NbColumns
-1) ;
423 value_clear_c(temp_level
) ;
424 value_clear_c(temp_outer
) ;
425 value_clear_c(factor_level
) ;
426 value_clear_c(factor_outer
) ;
431 * cloog_matrix_copy function:
432 * this functions builds and returns a "hard copy" (not a pointer copy) of a
433 * CloogMatrix data structure.
434 * - October 26th 2005: first version.
436 CloogMatrix
* cloog_matrix_copy(CloogMatrix
* matrix
)
440 copy
= cloog_matrix_alloc(matrix
->NbRows
,matrix
->NbColumns
) ;
442 for (i
=0;i
<matrix
->NbRows
;i
++)
443 for (j
=0;j
<matrix
->NbColumns
;j
++)
444 value_assign(copy
->p
[i
][j
], matrix
->p
[i
][j
]) ;
451 * cloog_matrix_vector_copy function:
452 * this function rutuns a hard copy of the vector "vector" of length "length"
454 * - November 3rd 2005: first version.
456 Value
* cloog_matrix_vector_copy(Value
* vector
, int length
)
460 /* We allocate the memory space for the new vector, and we fill it with
461 * the original coefficients.
463 copy
= (Value
*)malloc(length
* sizeof(Value
)) ;
464 for (i
=0;i
<length
;i
++)
465 { value_init_c(copy
[i
]) ;
466 value_assign(copy
[i
],vector
[i
]) ;
474 * cloog_matrix_vector_simplify function:
475 * this function simplify an affine expression with its coefficients in
476 * "vector" of length "length" thanks to an equality matrix "equal" that gives
477 * for some elements of the affine expression an equality with other elements,
478 * preferably constants. For instance, if the vector contains i+j+3 and the
479 * equality matrix gives i=n and j=2, the vector is simplified to n+3 and is
480 * returned in a new vector.
481 * - vector is the array of affine expression coefficients
482 * - equal is the matrix of equalities,
483 * - length is the vector length,
484 * - level is a level we don't want to simplify (-1 if none),
485 * - nb_par is the number of parameters of the program.
487 * - September 20th 2005: first version.
488 * - November 2nd 2005: (debug) we are simplifying inequalities, thus we are
489 * not allowed to multiply the vector by a negative
490 * constant.Problem found after a report of Michael
493 Value
* cloog_matrix_vector_simplify(Value
*vector
, CloogMatrix
*equal
,
494 int length
, int level
, int nb_par
)
496 Value gcd
, factor_vector
, factor_equal
, temp_vector
, temp_equal
, * simplified
;
498 simplified
= cloog_matrix_vector_copy(vector
,length
) ;
501 value_init_c(temp_vector
) ;
502 value_init_c(temp_equal
) ;
503 value_init_c(factor_vector
) ;
504 value_init_c(factor_equal
) ;
506 /* For each non-null coefficient in the vector, */
507 for (i
=length
-nb_par
-2;i
>0;i
--)
509 { /* if the coefficient in not null, and there exists a useful equality */
510 if ((value_notzero_p(simplified
[i
])) &&
511 (value_notzero_p(equal
->p
[i
-1][0])))
512 { /* Compute the Greatest Common Divisor. */
513 Gcd(simplified
[i
],equal
->p
[i
-1][i
],&gcd
) ;
515 /* Compute the factors to apply to each row vector element. */
516 value_division(factor_vector
,equal
->p
[i
-1][i
],gcd
) ;
517 value_division(factor_equal
,simplified
[i
],gcd
) ;
519 /* We are simplifying an inequality: factor_vector must not be <0. */
520 if (value_neg_p(factor_vector
))
521 { value_absolute(factor_vector
,factor_vector
) ;
522 value_oppose(factor_equal
,factor_equal
) ;
525 /* Now update the vector. */
526 /* - the iterators, up to the current level, */
527 for (j
=1;j
<=length
-nb_par
-2;j
++)
528 { value_multiply(temp_vector
,factor_vector
,simplified
[j
]) ;
529 value_multiply(temp_equal
,factor_equal
,equal
->p
[i
-1][j
]) ;
530 value_substract(simplified
[j
],temp_vector
,temp_equal
) ;
532 /* - between last useful iterator (i) and the first parameter, the equal
533 * matrix is sparse (full of zeroes), we just do nothing there.
534 * - the parameters and the scalar.
536 for (j
=0;j
<nb_par
+1;j
++)
537 { value_multiply(temp_vector
,factor_vector
,simplified
[length
-1-j
]) ;
538 value_multiply(temp_equal
,factor_equal
,
539 equal
->p
[i
-1][equal
->NbColumns
-j
-1]) ;
540 value_substract(simplified
[length
-1-j
],temp_vector
,temp_equal
) ;
545 /* Normalize (divide by GCD of all elements) the updated vector. */
546 cloog_vector_normalize(&(simplified
[1]),length
-1) ;
549 value_clear_c(temp_vector
) ;
550 value_clear_c(temp_equal
) ;
551 value_clear_c(factor_vector
) ;
552 value_clear_c(factor_equal
) ;
559 * cloog_matrix_simplify function:
560 * this function simplify all constraints inside the matrix "matrix" thanks to
561 * an equality matrix "equal" that gives for some elements of the affine
562 * constraint an equality with other elements, preferably constants.
563 * For instance, if a row of the matrix contains i+j+3>=0 and the equality
564 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The
565 * simplified constraints are returned back inside a new simplified matrix.
566 * - matrix is the set of constraints to simplify,
567 * - equal is the matrix of equalities,
568 * - level is a level we don't want to simplify (-1 if none),
569 * - nb_par is the number of parameters of the program.
571 * - November 4th 2005: first version.
574 cloog_matrix_simplify (CloogMatrix
*matrix
, CloogMatrix
*equal
, int level
, int nb_par
)
577 CloogMatrix
* simplified
;
582 /* The simplified matrix is such that each row has been simplified thanks
583 * to the "equal" matrix. We allocate the memory for the simplified matrix,
584 * then for each row of the original matrix, we compute the simplified
585 * vector and we copy its content into the according simplified row.
587 simplified
= cloog_matrix_alloc(matrix
->NbRows
,matrix
->NbColumns
) ;
588 for (i
=0;i
<matrix
->NbRows
;i
++)
589 { vector
= cloog_matrix_vector_simplify(matrix
->p
[i
],equal
,matrix
->NbColumns
,
591 for (j
=0;j
<matrix
->NbColumns
;j
++)
592 value_assign(simplified
->p
[i
][j
],vector
[j
]) ;
594 cloog_matrix_vector_free(vector
,matrix
->NbColumns
) ;
597 /* After simplification, it may happen that few constraints are the same,
598 * we remove them here by replacing them with 0=0 constraints.
600 for (i
=0;i
<simplified
->NbRows
;i
++)
601 for (j
=i
+1;j
<simplified
->NbRows
;j
++)
602 { for (k
=0;k
<simplified
->NbColumns
;k
++)
603 if (value_ne(simplified
->p
[i
][k
],simplified
->p
[j
][k
]))
606 if (k
== matrix
->NbColumns
)
607 { for (k
=0;k
<matrix
->NbColumns
;k
++)
608 value_set_si(simplified
->p
[j
][k
],0) ;
617 * cloog_matrix_vector_free function:
618 * this function clears the elements of a vector "vector" of length "length",
619 * then frees the vector itself this is useful for the GMP version of CLooG
620 * which has to clear all elements.
621 * - October 29th 2005: first version.
623 void cloog_matrix_vector_free(Value
* vector
, int length
)
626 for (i
=0;i
<length
;i
++)
627 value_clear_c(vector
[i
]) ;